O ruído digital é um defeito da imagem, que consiste em áreas localizadas aleatoriamente que estão próximas do tamanho de um pixel e diferem da imagem original em brilho ou cor. A redução de ruído desempenha um papel importante na transmissão, processamento e compressão de sequências de vídeo e imagens.

O ruído de vídeo pode ocorrer por vários motivos:

1. Equipamento de captura de vídeo imperfeito.

2. Más condições de filmagem - como filmagem noturna de fotos/vídeos, filmagem em condições meteorológicas adversas.

3. Interferência durante a transmissão em canais analógicos - interferência de fontes de campos eletromagnéticos, ruído intrínseco de componentes ativos (amplificadores) da linha de transmissão. Um exemplo é um sinal de televisão.

4. Filtrando imprecisões ao extrair sinais de luminância e diferença de cor de um sinal composto analógico, etc.

A quantidade de ruído em uma imagem pode variar de uma mancha quase imperceptível em uma fotografia digital tirada com boa luz, até fotografias astronômicas nas quais o ruído obscurece grande parte das informações úteis que só podem ser obtidas por meio de processamento de imagem trabalhoso.

O ruído pode ser de diferentes tipos, dependendo da natureza da distribuição aleatória do ruído na imagem. Na prática, os tipos mais comuns são:

Ruído Gaussiano Branco

Um dos ruídos mais comuns é o ruído gaussiano aditivo, que se caracteriza por adicionar valores com distribuição normal e média zero a cada pixel de uma imagem. O termo "aditivo" significa que esse tipo de ruído é adicionado ao sinal útil. Ocorre quando as condições de recepção do sinal são ruins.

ruído digital

A causa do ruído digital é mais frequentemente associada às características do equipamento usado para fotografar - geralmente com sensibilidade à luz insuficiente da matriz. Esse tipo de ruído é caracterizado pela substituição de alguns dos pixels da imagem pelos valores de uma variável fixa ou aleatória. Se o brilho dos pontos for aproximadamente igual, o ruído digital também é chamado de "impulsivo". Se a intensidade dos pontos pode mudar de preto para branco, esse ruído é chamado de ruído de sal e pimenta.

Normalmente, esse tipo de ruído afeta apenas um pequeno número de pixels em uma imagem.

Ruído combinado

Muito menos frequentemente há casos em que a imagem em um volume igual é ruidosa com ruído gaussiano e pulsos aleatórios. Este conjunto é chamado de ruído combinado.

Defeitos de digitalização de imagem

Efeitos estranhos, como rachaduras, arranhões, hematomas, também podem aparecer na imagem. Esses artefatos não possuem uma estrutura homogênea, a determinação de sua forma e localização está basicamente além da análise matemática. Defeitos desse tipo só podem ser combatidos com o auxílio do processamento manual de imagens, portanto, não são considerados neste trabalho.

Algoritmos de remoção de ruído

Há um grande número de algoritmos para remover ruídos de imagens e eles podem ser usados ​​não apenas por programas especiais de processamento, mas também por algumas câmeras de foto e vídeo. Apesar disso, ainda não existe um algoritmo de filtragem universal, pois ao processar uma imagem, há sempre a necessidade de escolher entre o grau de eliminação de efeitos indesejados e a preservação de pequenos detalhes que possuem características semelhantes ao ruído. Além disso, um algoritmo que lida facilmente com um tipo de ruído só pode estragar a imagem com outro tipo de ruído.

Vamos considerar alguns dos algoritmos de redução de ruído de imagem mais conhecidos.

Média de pixel linear

A ideia mais simples para remoção de ruído é calcular a média dos valores de pixel na vizinhança espacial. Como o ruído varia independentemente de pixel para pixel, o ruído dos pixels adjacentes se cancela quando somados. Uma janela retangular é definida, que é sobreposta em cada pixel da imagem por sua vez. O valor do pixel central é calculado com base na análise de todos os pixels vizinhos que se enquadram na área da janela. Assim, quanto maior a janela tirada, mais valor médio será obtido no final, o que leva a um forte efeito de desfoque.

Na versão mais simples, a análise dos pixels vizinhos consiste em encontrar sua média aritmética. Para reduzir a influência de pixels que não pertencem à mesma área que o considerado (por exemplo, um contorno escuro sobre um fundo claro), você pode introduzir um certo limite numérico e levar em consideração apenas os vizinhos cuja diferença do pixel central não excede este limite. Quanto maior o valor do limiar, mais forte será a média. A variante considerada pode ser complicada pela introdução de coeficientes de peso para cada pixel vizinho, dependendo de sua distância do centro da área em consideração.

Esse método também pode ser aplicado no domínio do tempo, calculando a média de cada pixel sobre os quadros adjacentes do fluxo de vídeo (cada pixel será calculado sobre os pixels localizados na mesma posição em quadros adjacentes).

Este algoritmo é muito simples, mas não dá um bom resultado, ao mesmo tempo levando a um forte desfoque dos detalhes da imagem.

Filtro Gaussiano

Possui um princípio de funcionamento semelhante ao método anterior e também pertence ao número de filtros anti-aliasing. No entanto, a redução de ruído usando um filtro de média linear tem uma desvantagem significativa: todos os vizinhos do pixel processado têm o mesmo efeito no resultado, independentemente da distância dele. O filtro gaussiano também faz a média do pixel central e seus vizinhos em uma determinada área, só que isso acontece de acordo com uma determinada lei, que é definida pela função gaussiana.

Onde o parâmetro y especifica o grau de desfoque e o parâmetro A fornece normalização. Como resultado, o pixel central da área considerada terá o maior valor correspondente ao pico da distribuição gaussiana. Os valores dos elementos restantes terão cada vez menos efeito à medida que você se afasta do centro.

O filtro de matriz calculado pela fórmula especificada é chamado de Gaussiano; quanto maior o tamanho, mais forte o desfoque (para um y fixo). Como esse filtro é separável, ele pode ser representado como:

Segue-se que a convolução pode ser realizada sequencialmente em linhas e colunas, o que leva a uma aceleração significativa do método para tamanhos de filtro grandes.

Algoritmo 2Dcleaner

Substitui cada pixel na imagem pelo valor médio dos pixels vizinhos, obtidos em uma área limitada por algum raio. Neste caso, nem todos os pontos que se enquadram no raio são considerados, mas apenas aqueles cujo valor difere do pixel central por não mais que algum valor pré-determinado (limiar). Devido a isso, áreas com cores uniformes são mais borradas do que bordas afiadas de objetos. Isso reduz o ruído de baixo nível na imagem, mantendo os detalhes finos intactos.

Filtragem mediana

Algoritmos lineares se mostram muito eficazes na supressão de ruído gaussiano, quando os pixels vizinhos, embora tenham algum espalhamento aleatório de valores, ainda permanecem dentro de algum valor médio característico da área a que pertencem. No entanto, às vezes você precisa lidar com imagens distorcidas por outros tipos de interferência. Um exemplo dessa interferência é o ruído de impulso, que se manifesta na presença de pontos aleatórios de brilho aleatório na imagem. A média neste caso “mancha” cada um desses pontos nos pixels vizinhos, levando a uma deterioração na qualidade da imagem.

A filtragem mediana é a maneira padrão de suprimir o ruído de impulso. Esse método de processamento de imagem não linear elimina picos, mas, ao contrário dos algoritmos de média linear, deixa intactas as sequências de pixels monótonas. Devido a isso, os filtros medianos são capazes de preservar sem distorção os contornos dos objetos e as diferenças entre áreas de brilho diferente, suprimindo efetivamente ruídos não correlacionados e detalhes de pequeno tamanho.

Princípio de filtragem: Uma determinada janela de tamanho ímpar é definida, sequencialmente sobreposta em cada pixel da imagem. Entre todos os pixels que se enquadram na área considerada, inclusive o central, busca-se o valor mediano, que acaba sendo atribuído ao pixel central da área. A mediana neste caso é o elemento do meio da matriz de valores de pixels classificados pertencentes à região. O tamanho ímpar da janela é escolhido precisamente para garantir a existência do pixel do meio.

Também é possível usar um filtro mediano para suprimir o ruído branco gaussiano na imagem. No entanto, um estudo de supressão de ruído utilizando filtragem mediana mostra que sua eficácia na resolução deste problema é inferior à da filtragem linear.

A filtragem mediana tem uma desvantagem inerente à maioria dos filtros de redução de ruído - quando o tamanho da máscara é aumentado para melhorar o grau de redução de ruído, a nitidez da imagem diminui e seus contornos ficam borrados. No entanto, é possível minimizar os efeitos negativos aplicando a filtragem mediana com um tamanho de máscara dinâmico (filtragem mediana aditiva) Seu princípio permanece o mesmo, apenas o tamanho da janela deslizante de filtragem pode mudar dependendo do brilho dos pixels vizinhos.

Nitidez de imagem

Quase todos os algoritmos de redução de ruído na imagem levam ao seu desfoque, como resultado, pequenos detalhes são perdidos e a percepção da imagem é difícil. Para compensar parcialmente esse efeito negativo e restaurar o contraste perdido do contorno e as transições de cores, o filtro de nitidez de imagem é capaz. A nitidez também pode depender de muitos outros fatores - da qualidade da lente, da abertura usada, da espessura do filtro anti-moiré encontrado na matriz da maioria das câmeras digitais, que desfoca a imagem em vários graus. Além disso, a nitidez das imagens muitas vezes precisa ser aumentada após a redução do seu tamanho, pois nesse caso parte da informação é inevitavelmente perdida e, com ela, a nitidez dos contornos.

O mascaramento de nitidez é uma técnica que, ao aumentar o contraste das transições entre os tons de uma imagem, melhora sua percepção visual devido à ilusão de nitidez. De fato, a nitidez permanece no mesmo nível, porque em princípio é impossível restaurar os detalhes perdidos da imagem, mas melhorar o contraste entre áreas de brilho diferente leva ao fato de que a imagem é percebida como mais clara.

Figura 5.1 - Ilustração do conceito de "nitidez do contorno"

A nitidez da imagem depende da magnitude da diferença de brilho entre as áreas (W) que formam seus contornos e da nitidez da mudança nessa diferença (H).

A técnica de mascaramento de nitidez foi aplicada pela primeira vez ao processamento de fotografias de filme. O método adaptado para o processamento digital de imagens difere pouco do original: a chamada “máscara de nitidez” é subtraída da imagem - sua cópia borrada e invertida. O resultado é uma nova imagem contendo apenas os contornos claros do original. Contornos escuros podem ser obtidos simplesmente invertendo o resultado.

Se você subtrair ainda mais as bordas escuras da imagem original e adicionar bordas claras, obterá um aumento significativo no contraste a cada diferença de brilho.

Qualquer um dos filtros de redução de ruído, como o filtro Gaussiano, pode ser usado para desfocar o original para obter uma “máscara de nitidez”.

Figura 5.2 - O resultado da aplicação de mascaramento sem nitidez

A operação de convolução é bastante utilizada no processamento de imagens. Além de nitidez, é usado para desfocar, aumentar o brilho, iluminar, etc.

A convolução da imagem é a operação de calcular um novo valor de um determinado pixel, que leva em consideração os valores de seus pixels vizinhos ao redor. Em um sentido geral, este termo significa alguma ação que é realizada em cada parte da imagem.

O principal elemento da convolução é a máscara de convolução - esta é uma matriz (de tamanho e proporção arbitrários). Muitas vezes, essa máscara é chamada de filtro, núcleo, modelo ou janela. Os valores dos elementos da matriz são geralmente chamados de coeficientes.

Na maioria das vezes, uma matriz quadrada é usada como kernel de convolução.

O processamento da imagem pela operação de convolução ocorre da seguinte forma: O elemento central da matriz, denominado “âncora”, é sucessivamente sobreposto a cada pixel da imagem. O novo valor do pixel considerado é calculado como a soma dos valores dos pixels vizinhos multiplicados por seus coeficientes de máscara de convolução correspondentes.

O efeito resultante depende do kernel de convolução selecionado.

O kernel do filtro boost tem um valor maior que 1 no ponto (0, 0), com a soma total de todos os valores igual a 1. Por exemplo, um filtro boost é filtros com kernels dados por matrizes:

O efeito de aumento do contraste é alcançado devido ao fato de o filtro enfatizar a diferença entre as intensidades dos pixels vizinhos, removendo essas intensidades umas das outras. Este efeito será mais forte quanto maior for o valor do termo central do kernel.

A filtragem aprimorada de contraste linear baseada em convolução pode causar halos de cores visíveis ao redor das bordas da imagem.

Compensação de diferença de luz

Os problemas de iluminação da imagem ocorrem com mais frequência quando janelas, o sol ou outras fontes de luz não regulamentadas entram no quadro.

Essa situação é chamada de "excesso de luz" e leva ao fato de que, devido à iluminação de contraforte muito brilhante, os detalhes e as cores dos objetos localizados no fundo de objetos muito brilhantes são perdidos, tornando-se difíceis de distinguir.

A situação de falta de luz também é frequentemente encontrada. Pode ser causado por fotografar em salas escuras com pouca iluminação, bem como uma faixa de sensibilidade limitada do equipamento de vídeo.

Algoritmo Retinex de Escala Única

Quando você tenta clarear a imagem aumentando o brilho de cada pixel em algum valor fixo, inicialmente as áreas claras podem ficar completamente superexpostas.

Nesses casos, é necessário aplicar a correção de cor “inteligente”, que seria capaz de uniformizar a iluminação da imagem, processando as áreas claras em menor grau do que as escuras.

Esses requisitos são atendidos pelo algoritmo Single Scale Retinex baseado nos princípios dos receptores da retina. O objetivo principal do algoritmo é dividir a imagem em componentes que são responsáveis ​​separadamente pela iluminação e detalhes. Como os problemas na imagem estão relacionados à iluminação da cena, então, tendo recebido o componente responsável pela iluminação, torna-se possível transformá-lo separadamente da imagem, aumentando significativamente sua qualidade.

Qualquer imagem pode ser representada como um produto de um sinal de alta frequência (reflexão - R) e um sinal de baixa frequência (iluminação - I).

S(x,y) = I(x,y) * R(x,y)(5,6)

Figura 5.3 - Representação da imagem no algoritmo Retinex.

Uma imagem aproximada da iluminação pode ser obtida usando filtragem passa-baixa - em outras palavras, basta desfocar a imagem original, por exemplo, com um filtro gaussiano.

onde G -- filtro gaussiano

Como o logaritmo do sinal não altera a frequência, e devido às propriedades da função logarítmica (o logaritmo do produto é igual à soma dos logaritmos dos fatores), a tarefa de separar o produto dos sinais pode ser simplificado para o problema de separar a soma dos sinais.

Depois disso, resta apenas pegar o expoente do sinal recebido para devolvê-lo à escala de amplitude original. O componente de alta frequência resultante pode ser adicionado à imagem original desfocada e iluminada, que atua como um novo modelo de iluminação.

O efeito obtido pela equalização da luz pode ser muito forte (as áreas escuras terão o mesmo brilho que as claras). Para reduzir o efeito, você pode simplesmente misturar a imagem processada com a original em uma determinada proporção.

Correção de gama

O objetivo original da correção de gama é compensar as diferenças nas cores exibidas em diferentes dispositivos de saída para que a imagem tenha a mesma aparência quando visualizada em monitores diferentes. Devido à forma não linear da função de potência aplicada, a correção de gama também possibilita aumentar o contraste das áreas escuras da imagem sem destacar detalhes brilhantes e sem perder a visibilidade dos limites dos objetos da imagem.

As informações de luminância em formato analógico na televisão, bem como em formato digital nos formatos gráficos mais comuns, são armazenadas em uma escala não linear. O brilho de um pixel em uma tela de monitor pode ser considerado proporcional

onde I é o brilho do pixel na tela do monitor (ou o brilho dos componentes de cores, vermelho, verde e azul separadamente),

V é um valor numérico de cor de 0 a 1, e

r -- índice de correção de gama .

Se r for menor que 1, então a característica de transferência de nível será convexa e a imagem resultante será mais clara que a original. Se r for maior que 1, então a característica de transferência de nível será côncava e a imagem resultante será mais escura que a original.

Por padrão, o parâmetro r é 1, o que corresponde a uma transmissão linear de níveis e sem correção de gama.

Seleção de contorno da imagem

A análise de contorno pode ser usada para descrever, reconhecer, comparar e pesquisar objetos gráficos representados como contornos externos. Como o uso de contornos exclui os pontos internos do objeto da consideração, isso pode reduzir significativamente a complexidade computacional e algorítmica dessas operações.

Figura 5.4 - Alteração do tipo de função de potência em função do parâmetro r

O contorno de um objeto é uma lista de pontos que representam uma curva em uma imagem que separa o objeto do plano de fundo. Na maioria das vezes, há um salto no brilho ou na cor ao longo do contorno.

Para simplificar a busca de contornos na imagem, você pode pré-binarizá-la.

O filtro Sobel destaca as bordas dos objetos com base em seu brilho. Como o componente de cor não é levado em consideração, as imagens devem primeiro ser convertidas em escala de cinza.

O filtro Sobel é aplicado sequencialmente a cada pixel, calculando o valor aproximado de seu gradiente de brilho. O gradiente para cada ponto da imagem (função de brilho) é um vetor bidimensional cujos componentes são as derivadas horizontais e verticais do brilho da imagem.

Em cada ponto da imagem, o vetor gradiente é orientado na direção do maior aumento de brilho e seu comprimento corresponde à quantidade de mudança de brilho. Esses dados nos permitem fazer uma suposição sobre a probabilidade de encontrar o ponto considerado na fronteira de um determinado objeto, bem como sobre a orientação dessa fronteira.

Que. o resultado da operação do operador de Sobel em um ponto na região de brilho constante será um vetor zero e em um ponto situado na fronteira de regiões de brilho diferente - um vetor cruzando a fronteira na direção de brilho crescente.

Para calcular os valores aproximados das derivadas em cada ponto da imagem, o filtro Sobel utiliza uma convolução com matriz 3×3.

Coeficientes da matriz de Sobel:

O valor final do gradiente é calculado por aproximação de acordo com a fórmula:

|G| = |Gx| + |Gy|

Detector de Limites Kenny

Embora o trabalho de Kenny tenha sido feito nos primeiros dias da visão computacional (1986), o detector de borda de Kenny ainda é um dos melhores detectores atuais. O método de Kenny é um algoritmo de vários estágios e inclui as seguintes etapas:

1. Limpando a imagem de ruídos e detalhes desnecessários.

2. Limpando a imagem de ruídos e detalhes desnecessários.

3. Pesquise gradientes de imagem, por exemplo, usando o operador Sobel.

4. Supressão de não-máximos. Apenas máximos locais são marcados como limites.

5. Filtragem de limiar duplo. Os limites potenciais são definidos por limites.

6. Traçando caminhos (vincule arestas a caminhos)

Como o menor ruído na imagem pode quebrar a integridade de seus contornos, é recomendável filtrar a imagem usando qualquer método de redução de ruído antes de iniciar a busca. Devido à alta velocidade de operação e facilidade de implementação, o filtro gaussiano é o mais utilizado. As bordas em uma imagem podem estar em direções diferentes, então o algoritmo de Kenny usa quatro filtros para detectar bordas horizontais, verticais e diagonais. Utilizando um operador de detecção de borda (por exemplo, o operador de Sobel) obtém-se o valor da primeira derivada na direção horizontal (Gy) e na direção vertical (Gx). A partir deste gradiente, você pode obter o ângulo da direção da borda:

O ângulo de direção da borda é arredondado para um dos quatro ângulos que representam vertical, horizontal e duas diagonais (por exemplo, 0, 45, 90 e 135 graus). Somente esses pixels são declarados como bordas, nos quais o máximo local do gradiente na direção do vetor gradiente é atingido. O valor da direção deve ser um múltiplo de 45°. Depois de suprimir não-máximos, as bordas se tornam mais precisas e finas.

Na próxima etapa, a filtragem de limiar determina para cada pixel considerado se ele pertence aos limites da imagem. Quanto maior o limiar, mais uniformes serão os contornos encontrados, porém, arestas fracas podem ser ignoradas. Por outro lado, diminuir o limiar aumenta a suscetibilidade do algoritmo ao ruído. A detecção de borda Kenny usa dois limites de filtragem: se o valor do pixel estiver acima do limite superior, assume o valor máximo (o limite é considerado confiável), se for inferior, o pixel é suprimido, pontos com um valor que cai no intervalo entre os limites assumem um valor médio fixo (eles serão refinados na próxima etapa).

O último estágio do processamento da imagem é unir bordas individuais em contornos uniformes. Os pixels que receberam o valor médio na etapa anterior são suprimidos (se não tocarem em nenhuma das bordas já detectadas) ou anexados ao contorno correspondente.

Segmentação

A maioria das imagens obtidas dos equipamentos de foto e vídeo são raster, ou seja, consistem em pontos coloridos dispostos em uma grade retangular. No entanto, as pessoas percebem o mundo ao seu redor como uma coleção de objetos sólidos, e não uma matriz de pontos. O cérebro humano é capaz de unir os detalhes díspares da imagem em áreas homogêneas, dividindo-a claramente em objetos em um nível subconsciente. Esse processo é chamado de segmentação e pode ser implementado programaticamente ao resolver o problema de análise de imagens de computador e reconhecimento de padrões. A segmentação é realizada nas primeiras etapas de análise, e a qualidade de sua implementação pode ter um forte impacto em sua velocidade e precisão.

Os métodos de segmentação podem ser divididos em duas classes: automáticos - não requerem interação do usuário e interativos - utilizando a entrada do usuário diretamente no processo.

No primeiro caso, nenhuma informação a priori sobre as propriedades das regiões é usada, mas algumas condições são impostas na própria partição da imagem (por exemplo, todas as regiões devem ser uniformes em cor e textura). Uma vez que esta formulação do problema de segmentação não utiliza informações a priori sobre os objetos representados, os métodos deste grupo são universais e aplicáveis ​​a quaisquer imagens.

Para uma avaliação aproximada da qualidade de um método em uma tarefa específica, geralmente são fixadas várias propriedades que uma boa segmentação deve ter:

§ Homogeneidade de regiões (uniformidade de cor ou textura);

§ dissimilaridade de regiões vizinhas;

§ suavidade da fronteira da região;

§ um pequeno número de pequenos "buracos" dentro das regiões;

Segmentação de limite

O processamento de limiar é o método mais simples orientado ao processamento de imagens, cujas áreas homogêneas individuais diferem em brilho médio. No entanto, se a imagem estiver desigualmente iluminada, alguns dos objetos podem corresponder em intensidade com o fundo, o que tornará a segmentação de limiar ineficaz.

O tipo de segmentação por limiar mais simples e ao mesmo tempo frequentemente usado é a segmentação binária, quando apenas dois tipos de áreas homogêneas são distinguidos na imagem.

Neste caso, a transformação de cada ponto da imagem de origem na imagem de saída é realizada de acordo com a regra:

onde x0 é o único parâmetro de processamento chamado de limite. Os níveis de brilho de saída y0 e y1 podem ser arbitrários, eles apenas executam as funções de marcas, com a ajuda de que o mapa resultante é marcado - atribuindo seus pontos às classes K1 ou K2, respectivamente. Se a preparação resultante estiver preparada para a percepção visual, geralmente seus valores correspondem aos níveis de preto e branco. Se houver mais de duas classes, uma família de limiares deve ser especificada durante a delimitação, separando os brilhos de diferentes classes uns dos outros.

A segmentação por limiar é adequada para selecionar um pequeno número de objetos sem interseção em uma imagem que tenha uma estrutura uniforme e se destaque nitidamente do plano de fundo. Com o aumento do grau de heterogeneidade da imagem e, consequentemente, do número de segmentos e sua complexidade, esse tipo de segmentação torna-se ineficiente.

Segmentação baseada no particionamento de um gráfico

Os métodos da teoria dos grafos são uma das áreas mais ativamente em desenvolvimento na segmentação de imagens.

A ideia geral dos métodos deste grupo é a seguinte. A imagem é representada como um gráfico ponderado, com vértices nos pontos da imagem. O peso da borda do gráfico reflete a semelhança dos pontos em algum sentido (a distância entre os pontos ao longo de alguma métrica). O particionamento da imagem é modelado por cortes de gráfico.

Normalmente, nos métodos da teoria dos grafos, é introduzido um funcional de “custo” de corte, que reflete a qualidade da segmentação resultante. Assim, o problema de particionar uma imagem em regiões homogêneas é reduzido a um problema de otimização de encontrar um corte de custo mínimo em um grafo. Essa abordagem permite, além da uniformidade da cor e textura dos segmentos, controlar a forma dos segmentos, seu tamanho, a complexidade das bordas, etc.

Para encontrar o corte de custo mínimo, vários métodos são usados: algoritmos gulosos (uma aresta é escolhida em cada etapa para que o custo total do corte seja mínimo), métodos de programação dinâmica (é garantido que, escolhendo a aresta ótima em cada etapa , terminaremos com o caminho ótimo), algoritmo Dijkstra, etc.

Interpolação

Em computação gráfica, o método de interpolação é frequentemente usado no processo de alteração da escala das imagens. Ao alterar o número de pixels da imagem, a interpolação ajuda a evitar a pixelização excessiva da imagem quando ela é ampliada ou a perda de detalhes importantes quando ela é reduzida.

Durante o processo de interpolação, pontos adicionais são inseridos entre os pixels da imagem, cujo tom e cor estimados são calculados usando um algoritmo especial baseado na análise de dados disponíveis em áreas vizinhas. Infelizmente, como qualquer interpolação é apenas uma aproximação, a imagem invariavelmente perderá qualidade sempre que for interpolada.

Interpolação do vizinho mais próximo

Este algoritmo é o tipo mais simples de interpolação, simplesmente aumentando cada pixel da imagem para a escala necessária. Requer o menor tempo de processamento, mas leva aos piores resultados.

Interpolação Bilinear

Este tipo de interpolação é realizado para cada coordenada da grade bidimensional. A imagem é considerada como uma superfície, cor - a terceira dimensão. Se a imagem for colorida, a interpolação será realizada separadamente para três cores. Para cada ponto desconhecido na nova imagem, a interpolação bilinear considera um quadrado de quatro pixels conhecidos ao seu redor. A média ponderada desses quatro pixels é usada como valor interpolado. Como resultado, as imagens parecem muito mais suaves do que o resultado do método do vizinho mais próximo.

A interpolação bilinear funciona bem em valores inteiros grandes de fatores de escala, no entanto, desfoca bastante as bordas nítidas da imagem.

A interpolação bicúbica vai um passo além da bilinear, considerando uma matriz de 4x4 pixels ao redor - 16 no total. Como eles estão a distâncias diferentes do pixel desconhecido, os pixels mais próximos ganham mais peso no cálculo. A interpolação bicúbica produz imagens significativamente mais nítidas do que os dois métodos anteriores e é sem dúvida a melhor em termos de tempo de processamento e qualidade de saída. Por esse motivo, tornou-se padrão em muitos programas de edição de imagem (incluindo Adobe Photoshop), drivers de impressora e interpolação de câmera integrada.

A imagem dimensionada pode ficar significativamente menos nítida. Algoritmos de interpolação que preservam melhor a nitidez também são mais propensos a moiré, enquanto aqueles que eliminam moiré tendem a produzir resultados mais suaves. Infelizmente, essa troca de escala não pode ser evitada.

Uma das melhores maneiras de combater isso é aplicar uma máscara de nitidez imediatamente após o dimensionamento, mesmo que o original já tenha sido afiado.

5.2 Justificativa para a escolha dos algoritmos utilizados no subsistema

O principal requisito para o pacote de software desenvolvido foi minimizar o atraso de reprodução do fluxo de vídeo durante seu processamento preliminar em um cluster de computação. Além disso, o disparo pode ocorrer em qualquer condição, o que significa que em pouco tempo foi necessário implementar um grande número de filtros simples para neutralizar vários efeitos negativos. Além disso, foi necessário estudar um grande número de fatores negativos que aparecem no vídeo em pouco tempo e implementar filtros simples para neutralizá-los. Algoritmos que satisfaçam os requisitos apresentados devem ser de fácil acesso, bem otimizados, ter alta confiabilidade e, ao mesmo tempo, ser de fácil implementação. As funções da biblioteca OpenCV possuem tais propriedades, portanto, ao escolher métodos específicos para implementação de filtros de processamento de fluxo de vídeo, foi dada prioridade aos algoritmos contidos nesta biblioteca de uma forma ou de outra.

Todos os algoritmos considerados na parte teórica do trabalho de qualificação final foram implementados em forma de teste de forma a comparar as suas características na prática. Em particular, foi dada preferência a um compromisso entre a velocidade de processamento de um quadro de fluxo de vídeo e a qualidade do resultado.

Como resultado, os seguintes algoritmos foram escolhidos para implementar os filtros de processamento de fluxo de vídeo no cluster de computação:

1. O algoritmo Gaussiano foi escolhido para remover o ruído “aditivo branco”. Como o método de redução de ruído mais comum, é muito bem otimizado e, portanto, possui alta velocidade.

2. O algoritmo Gaussiano foi escolhido para remover o ruído “aditivo branco”. Como o método de redução de ruído mais comum, é muito bem otimizado e, portanto, possui uma alta velocidade de operação.

3. A filtragem mediana foi escolhida para remover o ruído de “impulso”. Esse método também é bem otimizado e foi projetado especificamente para eliminar ruídos impulsivos e de sal e pimenta.

4. A convolução foi escolhida para tornar a imagem mais nítida, pois funciona muito mais rápido do que o mascaramento sem nitidez, ao mesmo tempo em que fornece resultados aceitáveis.

5. A biblioteca OpenCV não contém algoritmos de correção de cores - portanto, decidiu-se implementar o algoritmo Retinex de escala única mais comum e bem documentado. Este método tem uma eficiência muito alta, mas requer otimização para agilizar o trabalho.

6. O algoritmo Kenny foi escolhido como método de detecção de bordas, pois apresenta resultados melhores que o filtro Sobel.

7. O algoritmo de segmentação piramidal apresentado na biblioteca OpenCV é extremamente lento, então optou-se por utilizar o algoritmo de segmentação anteriormente considerado em grafos.

8. interpolação - o método de interpolação bicúbica foi escolhido como o compromisso mais razoável entre a velocidade do trabalho e a qualidade do resultado.

Instalação e configuração do software utilizado.

O cluster de computação usado estava executando o GNU Linux (Ubuntu)

Depois de instalar o sistema operacional, você precisa instalar várias bibliotecas que suportam leitura e gravação de arquivos de imagem, desenho na tela, trabalho com vídeo, etc.

Instalando o CMake

O projeto é construído usando CMake (requer versão 2.6 ou superior). Você pode instalá-lo com o comando:

apt-get install cmake

Você também pode precisar das seguintes bibliotecas:

build-essential libjpeg62-dev libtiff4-dev libjasper-dev libopenexr-dev libtbb-dev libeigen2-dev libfaac-dev libopencore-amrnb-dev libopencore-amrwb-dev libtheora-dev libvorbis-dev libxvidcore-dev

Instalando o ffmpeg

Para que o opencv processe os arquivos de vídeo corretamente, você precisa instalar a biblioteca ffmpeg. Isso é feito com os seguintes comandos:

1) Baixando os códigos fonte da biblioteca

wget http://ffmpeg.org/releases/ffmpeg-0.7-rc1.tar.gz

2) Descompactando o arquivo com códigos fonte

tar -xvzf ffmpeg-0.7-rc1.tar.gz

3) Configuração da biblioteca

configure --enable-gpl --enable-version3 --enable-nonfree --enable-postproc

enable-libfaac --enable-libopencore-amrnb --enable-libopencore-amrwb

Enable-libtheora --enable-libvorbis --enable-libxvid --enable-x11grab

Enable-swscale --enable-shared

4) Construindo e instalando a biblioteca

Instalação GTK

A exibição de janelas OpenCV requer GTK+ 2.x ou superior instalado, incluindo arquivos de cabeçalho (libgtk2.0-dev)

apt-get install libgtk2.0-dev

Instalando o Opencv

Após instalar todas as bibliotecas relacionadas, a instalação do opencv2.2 é feita com os seguintes comandos:

1) Baixando os códigos fonte da biblioteca OpenCV

http://downloads.sourceforge.net/project/opencvlibrary/opencv-unix/2.2/OpenCV-2.2.0.tar.bz2

2) Descompactando o arquivo com códigos fonte

tar -xvf OpenCV-2.2.0.tar.bz2

3) gerando um Makefile usando CMake.

4) construindo e instalando a biblioteca OpenCV

5) Você também pode precisar definir o caminho para as bibliotecas

export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH

Instalação e compilação do pacote de software desenvolvido

É necessário copiar os códigos-fonte dos programas do disco anexo a esta nota explicativa. Copie o arquivo em lote build_all.sh para a mesma pasta e execute-o. Se o compilador gcc estiver instalado no sistema, a compilação acontecerá automaticamente.

DIGITAL TRATAMENTO SINAIS

Tópico 17. PROCESSAMENTO DE IMAGEM

Não há nada além da imaginação do homem.

Tito Lucrécio. Filósofo e poeta romano. século 1 BC e.

A imaginação é uma coisa boa. Mas tirar um vagabundo do porão, lavá-lo, transformá-lo em um Apollo, embalá-lo em uma caixa de fósforos e enviá-lo por e-mail a um amigo, um bom programa gráfico fará melhor.

Anatoly Pyshmintsev, geofísico de Novosibirsk da Escola Ural. século 20

Introdução.

1. Conceitos básicos. Representação gráfica de imagens. Representação da cor em computação gráfica. Modelo de cores RGB. Sistema de cores CIE XYZ.

2. Transformações geométricas de imagens raster. Áreas e fases de transformação. Amostragem. Série de interpolação de recuperação de sinal bidimensional. Distorções de frequência de imagens e sua eliminação. Reamostragem de imagem.

3. Filtragem de imagens. Filtros de linha. Filtros de suavização. Filtros de contraste. filtros de diferença. Convolução cíclica bidimensional. filtros não lineares. Filtragem de limite. filtragem mediana. Filtros extremos.

4. Compressão de imagem. Algoritmos de codificação de comprimento de repetição (RLE). Algoritmos de dicionário. Algoritmos de codificação estatística. Compressão de imagem com perdas. Estimativa de perda de imagem. Transformada de Fourier. Transformada Wavelet.

INTRODUÇÃO

O escopo da pesquisa no campo da imagem digital está crescendo rapidamente. Isso ocorre porque o processamento de imagem é um processamento de sinal multidimensional e a maioria dos sinais no mundo real é multidimensional.

Uma imagem em representação matemática é um sinal bidimensional que carrega uma enorme quantidade de informações. Uma imagem colorida de 500 × 500 elementos é uma matriz de várias centenas de milhares de bytes. É possível processar essas informações apenas por uma organização racional de cálculos. Para tarefas específicas de processamento de imagem, métodos de processamento eficientes podem ser aplicados, levando em consideração as características e limitações dessa tarefa específica. Mas se falamos de processamento de imagem para resolver uma ampla classe de problemas, é necessário destacar um conjunto de operações padrão a partir das quais algoritmos podem ser construídos para resolver problemas arbitrários. Isso inclui transformações lineares, convolução 2D e transformações discretas de Fourier 2D.

Mas no processamento de imagens, as transformações não lineares também são amplamente utilizadas. A peculiaridade das imagens é que os elementos individuais da imagem estão em certa conexão com os elementos vizinhos. Portanto, a maioria dos algoritmos de transformação de imagens são de natureza local, ou seja, eles processam imagens por grupos de elementos localizados na vizinhança de um dado. As transformações lineares satisfazem a propriedade de localidade e permitem a construção de algoritmos cuja complexidade computacional não depende muito do tamanho da vizinhança coberta. As mesmas propriedades são necessárias para transformações de imagem não lineares. A classe de tais transformações inclui algoritmos, que são chamados de algoritmos de filtragem de classificação, baseados no cálculo de estatísticas de imagem de classificação local. Ao calcular as estatísticas de classificação e seus derivados, são possíveis simplificações relacionadas à redundância de informações das imagens. O algoritmo mais conhecido desta classe é o algoritmo de filtragem mediana. Outros exemplos de algoritmos de classificação são algoritmos de filtragem extrema que substituem o elemento de imagem analisado por um máximo ou mínimo na vizinhança. Outra propriedade dos algoritmos de classificação é a adaptação local às características da imagem processada e o potencial de uso não apenas para suavização e remoção de ruído, mas também para extração de recursos no reconhecimento automático de imagens.

No processamento de imagens, métodos de processamento de sinais unidimensionais são amplamente utilizados, caso seja possível generalizá-los para sinais multidimensionais. Ao mesmo tempo, deve-se levar em conta que os métodos matemáticos para descrever sistemas multidimensionais não são completos. Sistemas multidimensionais possuem um grande número de graus de liberdade, e seu projeto adquire flexibilidade que não é característica de sistemas unidimensionais. Ao mesmo tempo, polinômios multidimensionais não podem ser decompostos em fatores simples, o que complica a análise e síntese de sistemas multidimensionais.

17.1. Conceitos Básicos

Representação gráfica de imagens. Para representar a informação gráfica em um plano bidimensional (tela do monitor), são utilizadas duas abordagens: raster e vetorial.

Com a abordagem vetorial, a informação gráfica é descrita como um conjunto de objetos geométricos abstratos - linhas retas, segmentos, curvas, retângulos, etc. A descrição vetorial pressupõe um conhecimento a priori sobre a estrutura da imagem.

Os gráficos raster operam em imagens arbitrárias na forma de bitmaps. Um raster é uma descrição de uma imagem em um plano, dividindo-a (amostrando) em elementos idênticos ao longo de uma grade regular e atribuindo a cada elemento sua própria cor e quaisquer outros atributos. O raster mais simples é o retangular, o mais econômico em termos de número de amostras para transmissão de imagens é o hexagonal. Matematicamente, um raster é uma aproximação constante por partes no plano de uma função de imagem contínua.

Um elemento de um raster é chamado de pixel. Identificação de pixel padrão:

f(i, j) = (A(i, j),C(i, j)), (17.1.1)

onde A(i, j) Ì R2 - área do pixel, C(i, j) Î C - atributo do pixel (geralmente cor). Os dois atributos mais usados ​​são:

C(i, j) = I(i, j) - intensidade (brilho) de um pixel;

C(i, j) = (R(i, j), G(i, j), B(i, j)) - atributos de cor no modelo de cores RGB.

Em forma de matriz:

Mij ​​= (Aij, Cij).

Ao amostrar imagens contínuas, os valores Aij podem ser definidos de duas maneiras, seja como os valores dos pontos Aij = (i, j) para os quais os atributos Cij são definidos, ou como os valores dos quadrados Aij = (i, i+1) × (j, j+1) ou qualquer outra forma, com a definição de Cij pelos valores médios dentro desta forma (Fig. 17.1.1).

Na prática, como regra, X e Y são conjuntos limitados de inteiros não negativos de um raster quadrado ou retangular com uma proporção (proporção) da largura para a altura do raster, que é escrito como, por exemplo, "4:3".

Representação da cor em computação gráfica. O conceito de cor é baseado na percepção pelos olhos humanos de ondas eletromagnéticas em uma determinada faixa de frequência. A luz do dia que percebemos tem comprimentos de onda λ variando de 400 nm (violeta) a 700 nm (vermelho). A descrição do fluxo de luz pode ser sua função espectral I(λ). A luz é chamada monocromática se seu espectro tem apenas um comprimento de onda específico.

Existem dois tipos de receptores na retina: bastonetes e cones. A sensibilidade espectral dos bastões (Fig. 17.1.2) é diretamente proporcional ao brilho da luz incidente. Os cones são divididos em três tipos, cada um com uma certa sensibilidade em faixas limitadas com máximos para as cores vermelha, verde e azul, e perdem drasticamente sua sensibilidade no escuro. A suscetibilidade do olho ao azul é muito menor do que aos outros dois. Uma propriedade importante da percepção humana da luz é a linearidade ao adicionar cores com diferentes comprimentos de onda.

Modelo de cores RGB (Vermelho, Verde, Azul - vermelho, verde, azul) em computação gráfica é atualmente o mais comum. Neste modelo, a função espectral é representada como a soma das curvas de sensibilidade para cada tipo de cone com coeficientes de peso não negativos (normalizados de 0 a 1), que são denotados como R, G e B. O modelo é caracterizado por a propriedade de aditividade para obter novas cores. Por exemplo, a codificação de funções espectrais:

Preto: fpreto = 0, (R, G, B) = (0,0,0);

Violeta violeta = fred + fazul, (R, G, B) = (1,0,1);

Branco fbranco = fred + fverde + fazul, (R, G, B) = (1,1,1).

O espaço de cores tridimensional do modelo RGB é mostrado na fig. 17.1.3. Devido às peculiaridades da percepção da luz pelos receptores, nem todas as cores visíveis aos humanos são representáveis ​​neste modelo. No entanto, a proporção de cores reproduzíveis é muito maior do que a proporção de cores que não são representáveis ​​neste modelo.

Sistema de cores CIE XYZ. O padrão internacional de representação de cores CIE (CIE - Commission Internationale de l "Eclairage) foi adotado em 1931 pela Comissão Internacional de Iluminação. Ele define três funções básicas ρX (λ), ρY (λ), ρZ (λ), dependendo da comprimento de onda , cujas combinações lineares com coeficientes não negativos (X, Y e Z) produzem todas as cores visíveis ao homem. Essas funções levam em consideração a percepção relativa da intensidade da luz pelos receptores do olho. No espaço tridimensional, o CIE sistema de cores forma um cone no primeiro quadrante e é usado para exibição de alta qualidade de imagens coloridas.

17.2. Transformações geométricas de bitmaps

Áreas e fases de transformação. As imagens podem ser divididas em texturais e detalhadas. Nas imagens de textura, todas as amostras (elementos) carregam informações (uma imagem na tela da TV). Uma imagem detalhada é uma imagem na qual objetos interferentes, fundo e objetos úteis podem ser distinguidos.

Existem três grupos principais de algoritmos de processamento de imagem em computadores:

1. Processamento de imagem primário (preliminar) para fins de restauração, limpeza de ruído aleatório, melhoria da qualidade, correção de distorções geométricas de sistemas ópticos (desfocagem, aberrações, etc.).

2. Descrição de imagens, reconhecimento de padrões. É realizado para determinar os parâmetros de detalhes da imagem e inclui: encontrar áreas da imagem uniformes em termos de iluminação e cor, destacar sinais da forma das imagens, determinar as coordenadas de pontos especiais de objetos, etc.

3. Codificação eficiente para reduzir a quantidade de transmissão e armazenamento.

A maioria dos métodos de pré-processamento são baseados no uso de filtros lineares espacialmente invariantes (LPI). Algoritmos lineares são executados usando análogos 2D de filtros 1D FIR e IIR. Eles podem ser usados, por exemplo, na implementação de filtros para reduzir o nível de ruído nas imagens.

Os filtros FIR são implementados usando o método de convolução. A vantagem dos filtros 2D FIR é a visibilidade, simplicidade e estabilidade absoluta. Os filtros IIR são implementados usando equações de diferença e transformadas z. Eles são mais rápidos que os filtros FIR, mas podem ser instáveis. A síntese de filtros IIR bidimensionais difere da síntese de filtros unidimensionais, pois para uma função bidimensional não é possível selecionar explicitamente os polos.

Métodos não lineares também podem ser necessários para restaurar imagens e melhorar sua qualidade. Assim, por exemplo, para suprimir o ruído e ao mesmo tempo preservar a parte do contorno das imagens, é necessário aplicar filtros não lineares ou lineares espacialmente não invariantes (SPNI), que são implementados por algoritmos de classificação. Todos os filtros não lineares de classificação são baseados em algoritmos rápidos para calcular histogramas locais.

Um desses métodos é a filtragem mediana. O uso de filtros medianos é eficaz para suprimir certos tipos de ruído e ruído periódico sem distorcer simultaneamente o sinal, por exemplo, para suprimir rajadas de emissões de ruído, incluindo quedas de linha. O método também pode ser usado para resolver problemas relacionados ao reconhecimento, por exemplo, para destacar linhas finas e pequenos objetos isolados.

Os algoritmos de descrição e reconhecimento de imagens, via de regra, são não lineares e de natureza heurística. Os sinais de objetos geralmente são a área da imagem do objeto, o perímetro do contorno da imagem, a razão da área para o quadrado do perímetro da imagem. A forma de um objeto pode ser caracterizada pelo raio do círculo inscrito na imagem ou circunscrito ao redor da imagem do objeto, o comprimento do vetor raio mínimo e máximo do “centro de massa” da imagem.

Amostragem. As transformações de imagem em um computador e o armazenamento dos dados processados ​​são realizados de forma discreta. A amostragem é usada para obter uma representação discreta de imagens analógicas contínuas do mundo real. Na prática, é realizado por dispositivos de entrada (câmera digital, scanner ou outros). Para a percepção visual de imagens processadas em dispositivos de saída (display, plotter, etc.), uma imagem analógica é reconstruída de acordo com sua representação discretizada.

No caso mais simples de imagens em preto e branco, temos uma matriz bidimensional sa(x, y). Para imagens coloridas no modelo RGB, levando em consideração a propriedade de aditividade ao adicionar cores, cada camada R, G e B também pode ser considerada e processada como uma matriz bidimensional, com posterior somatória dos resultados.

Das maneiras de generalizar a discretização periódica unidimensional para o caso bidimensional, a mais simples é a discretização periódica em coordenadas retangulares:

s(n, m) = sa(nDx, mDy),

onde Dx e Dy são os intervalos de amostragem horizontal e vertical do sinal contínuo bidimensional sa(x, y) com coordenadas xey contínuas. Abaixo, os valores de Dx e Dy, como no caso unidimensional, são tomados iguais a 1.

A discretização de um sinal bidimensional também leva à periodização de seu espectro e vice-versa. A condição de equivalência informacional das representações de coordenadas e frequências de um sinal discreto também é preservada com um número igual de pontos de amostragem nas faixas principais do sinal. Para discretização retangular, as transformadas de Fourier direta e inversa são definidas pelas expressões:

S(k, l) =s(n, m) exp(-jn2pk/N-jm2pl/M), (17.2.1)

S(k, l) =exp(-jn2pk/N) s(n,m)exp(-jm2pl/M), (17.2.1")

s(n, m) =S(k, l) exp(-jn2pk/N-jm2pl/M). (17.2.2)

s(n, m) = exp(-jn2pk/N) S(k, l) exp(-jm2pl/M). (17.2.2")

Arroz. 17.2.1. Periodização do espectro.

Essas expressões mostram que uma DFT 2D sobre um raster de amostragem de dados retangular pode ser calculada usando DFTs seriais 1D. As segundas somas das expressões (17.2.1") e (17.2.2") são as DFTs unidimensionais das seções das funções s(n, m) e S(k, l) ao longo das linhas n e k, respectivamente, e as primeiras são as DFTs unidimensionais das funções calculadas nas seções por m e l. Em outras palavras, as matrizes iniciais de valores s(n, m) e S(k, l) são primeiro recalculadas em matrizes intermediárias com DFT por linhas (ou por colunas), e matrizes intermediárias são recalculadas em matrizes finais com DFT por colunas (ou, respectivamente, por linhas).

Para que a repetição periódica do espectro (Fig. 17.2.1), causada pela amostragem de um sinal analógico com frequência Fx=1/Dx e Fy=1/Dy, não altere o espectro na frequência principal (em relação ao espectro do sinal analógico original), é necessário e suficiente que as componentes de frequência máxima fmax no espectro do sinal analógico, tanto em linhas como em colunas, não ultrapassem a frequência de Nyquist (fmax. x £ fN = Fx/2, fmáx. y £ fM = Fy/2). Isso significa que a frequência de amostragem do sinal deve ser pelo menos duas vezes maior que o componente de frequência máxima no espectro do sinal:

Fx ³ 2fmáx. x, Fy ³ 2fmax. sim, (17.2.3)

o que garante que as funções espectrais atinjam valores zero nas extremidades da faixa principal do espectro.

Série de interpolação de recuperação de sinal bidimensional. Se o sinal contínuo sa(x, y) é um sinal de espectro limitado, e os períodos de amostragem são escolhidos suficientemente pequenos e os espectros dos períodos vizinhos não se sobrepõem:

Sa(Wx, Wy) = 0 para |Wx|p/Dx, |Wy|p/Dx,

então, como no caso unidimensional, o sinal sa(x, y) pode ser reconstruído a partir de um sinal discreto usando o análogo bidimensional da série Kotelnikov-Shannon:

sa(x, y) = Sn Sm s(n, m) . (17.2.4)

Distorções de frequência de imagens e sua eliminação. Um sinal com espectro ilimitado também pode ser amostrado, mas neste caso há uma sobreposição de espectros em períodos adjacentes, enquanto frequências altas, superiores às frequências de Nyquist, serão "mascaradas", como no caso unidimensional, sob as baixas frequências do período principal. O efeito de "reflexão" dos limites do período dá uma imagem ainda mais complexa devido à interferência de frequências refletidas em diferentes coordenadas. Um efeito semelhante, conhecido como aliasing, também ocorrerá quando a imagem for subamostrada. Este efeito pode ser observado especialmente claramente em mudanças contrastantes acentuadas no brilho.

Para combater tais fenômenos, é usada pré-filtragem (anti-aliasing) - convolução preliminar de uma imagem analógica com uma função de filtro de peso que corta componentes de alta frequência que podem levar a aliasing. No caso bidimensional, a filtragem é descrita da seguinte forma:

z(x, y) = h(x", y") ③③ s(x-x", y-y"). (17.2.5)

Deve-se notar que as imagens analógicas existem apenas na faixa óptica, por exemplo, na forma de uma exibição de luz em uma tela, papel fotográfico ou filme, mas não podem existir na memória do computador. Portanto, a implementação física da pré-filtragem só é possível ao registrar uma imagem desfocando-a, o que, via de regra, não é utilizado. As informações primárias devem sempre ser registradas com o máximo de integridade e precisão, e a limpeza das informações primárias de detalhes desnecessários e redundância é uma questão de processamento de dados subsequente. Portanto, em relação à equação 17.2.5, a pré-filtragem bidimensional, em sua implementação prática, pode ser apenas uma filtragem de imagens amostradas com grande margem sobre a faixa de frequência principal (com resolução excessiva), e é utilizada, via de regra, , ao reamostrar para uma etapa maior, por exemplo, ao compactar imagens. A pré-filtragem também pode ser incorporada aos algoritmos de imagem.

Na fig. 17.2.3 e abaixo, a Tabela 17.2.1 mostra exemplos dos filtros anti-aliasing unidimensionais mais comuns. Eles também podem ser implementados na forma de filtros analógicos e são usados, por exemplo, ao transmitir linhas de imagem de televisão em forma analógica em canais de rádio (anti-aliasing horizontal). Em princípio, uma operação semelhante pode ser realizada em colunas (duplicado - imagem) e, após a soma da imagem, uma operação completa de anti-aliasing será executada, mas esse método pertence mais ao campo da pesquisa científica especial.

Tabela 17.2.1.

Funções básicas de peso

janela de oportunidade	função de peso	transformada de Fourier
Natural (P)	П(t) = 1, |t|£t; П(t) = 0, |t|>t	П(w) = 2t sinc
Barlett (D)		B(w) = t sinc2(wt/2).
Henning, Hanna	p(t) = 0,5	0,5p(w)+0,25p(w+p/t)+0,25p(w-p/t)
Hamming	p(t) = 0,54+0,46 cos(pt/t)	0,54P(w)+0,23P(w+p/t)+0,23P(w-p/t)
Carré (2ª janela)	p(t) = b(t) sinc(pt/t)	t B(w)*P(w), P(w) = 1 para |w|
Laplace-Gauss	p(t) = exp[-b2(t/t)2/2]	[(t/b) exp(-t2w2/(2b2))] ③ P(w)

Análogos bidimensionais de filtros unidimensionais f1(x) são construídos em duas variantes de simetria: ou em função do raio:

f2(x, y) = f1(),

ou como obra:

f2(x, y) = f1(x) × f1(y).

A primeira opção é mais correta, mas a segunda tem a propriedade de separabilidade, ou seja, a convolução bidimensional pode ser realizada por duas convoluções unidimensionais sequencialmente em linhas com f1(x) e em colunas com f1(y).

Reamostragem de imagem ou reamostragem é uma mudança na taxa de amostragem de um sinal digital. Para imagens digitais, isso significa redimensionar a imagem.

Existem vários algoritmos de reamostragem de imagem. Por exemplo, para aumentar a imagem em 2 vezes usando o método de interpolação bilinear, colunas e linhas intermediárias são obtidas por interpolação linear dos valores das colunas e linhas vizinhas. É possível obter cada ponto da nova imagem como uma soma ponderada de um número maior de pontos da imagem original (bicúbica e outros tipos de interpolação). A reamostragem da mais alta qualidade é obtida ao usar algoritmos que levam em consideração não apenas o tempo, mas também o domínio da frequência do sinal.

Considere um algoritmo de reamostragem com preservação máxima das informações de frequência da imagem. Consideraremos o funcionamento do algoritmo em sinais unidimensionais, uma vez que uma imagem bidimensional pode primeiro ser esticada ou comprimida horizontalmente (em linhas) e depois verticalmente (em colunas), e a reamostragem de uma imagem bidimensional pode ser reduzido a reamostragem de sinais unidimensionais.

Suponha que tenhamos um sinal unidimensional (Fig. 17.2.4), dado no intervalo 0-T e discretizado com um passo Dt=1 (N intervalos). É necessário "esticar" o sinal em m vezes. O espectro do sinal mostrado na figura é calculado pela transformada rápida de Fourier (FFT, o número de amostras de espectro é igual ao número de amostras de sinal) e é dado na faixa principal de FFT (0-2p, frequência Nyquist wN = p/Dt = p, ou 0,5N de acordo com a numeração das amostras do espectro com um passo ao longo do espectro Df = 1/T ou Dw = 2p/T). O alongamento requer 2 passos.

O primeiro passo é a interpolação zero, que aumenta o comprimento do sinal em m vezes. (Fig. 17.2.5). É necessário multiplicar todas as amostras do sinal original por m e, em seguida, após cada amostra de sinal, inserir o valor zero de m-1. No intervalo 0-T, cujo valor permanece inalterado, há agora m vezes mais intervalos de amostragem (mN), e a nova etapa de amostragem será igual a Dx=Dt/m. Assim, a nova frequência de Nyquist para este sinal é mp/Dt = mp. Mas o valor físico do passo do espectro em unidades de frequência é o oposto do valor físico do intervalo de ajuste do sinal (Df = 1/T) e, portanto, a FFT em mN pontos de sinal calculará mN pontos do espectro em a faixa principal da FFT de 0-2pm com o passo do espectro do sinal original, no qual estarão presentes m-períodos do espectro do sinal original (um lado principal e m-1).

A segunda etapa é filtrar as bandas laterais do espectro usando um filtro passa-baixa, seja no domínio do tempo ou espectral. Na fig. 17.2.6, o espectro foi limpo e a transformada inversa de Fourier foi realizada, obtendo-se um sinal m vezes maior que o sinal original com total preservação de todas as informações de frequência.

De acordo com um princípio semelhante, um algoritmo para compactar (decimar) um sinal por n vezes pode ser construído, enquanto a ordem dos passos é invertida. Ao comprimir o sinal, a etapa de amostragem do sinal é aumentada e, consequentemente, a frequência de Nyquist é reduzida, enquanto as altas frequências de corte (ruído e partes de alta frequência insignificantes do espectro do sinal) serão refletidas da borda da faixa principal e adicionados às informações principais, criando distorções. Para eliminar esse fenômeno, o sinal é primeiro filtrado passa-baixo com uma frequência de corte igual à nova frequência de Nyquist (anti-aliasing), e só então o sinal é dizimado por afinamento.

Quando a reamostragem é realizada apenas no domínio do tempo, os algoritmos de alongamento e compressão geralmente são combinados em um único processo sequencial com a configuração da mudança da etapa de amostragem na forma da razão m/n, que permite definir valores inteiros de m e n para valores fracionários da mudança da etapa de amostragem. Isso simplifica muito os algoritmos e melhora a eficiência e a qualidade de seu trabalho. Por exemplo, quando o sinal é esticado 1,5 vezes em m/n = 3/2, o sinal é esticado primeiro 3 vezes (uma adição simples e uniforme de zeros a todas as amostras, então a filtragem passa-baixa é realizada, após o que o sinal é dizimado por um fator de dois. O filtro anti-aliasing não é necessário, pois sua frequência de corte se sobrepõe à frequência do primeiro filtro passa-baixa. Na operação de compressão reversa (por exemplo, m/n = 2/3 ), da mesma forma, apenas o filtro anti-aliasing é usado.

17.3. filtragem de imagem

A filtragem de imagens é uma operação que resulta em uma imagem de mesmo tamanho, obtida da original de acordo com algumas regras. Normalmente, a intensidade (cor) de cada pixel na imagem resultante é determinada pelas intensidades (cores) dos pixels localizados em alguma de sua vizinhança na imagem original.

As regras de filtragem podem ser muito diversas. A filtragem de imagens é uma das operações mais fundamentais da visão computacional, reconhecimento de padrões e processamento de imagens. A grande maioria dos métodos de processamento de imagens começa com uma ou outra filtragem das imagens originais.

Filtros de linha tem uma descrição matemática muito simples. Assumiremos que a imagem original de meio-tom A é dada e denotaremos as intensidades de seus pixels por A(x, y). Um filtro linear é definido por uma função de valor real h (kernel de filtro) definida em um raster. A filtragem em si é realizada usando a operação de convolução discreta (soma ponderada):

B(x, y) = h(i, j) ③③A(x, y) = h(i, j) A(x-i, y-j). (17.3.1)

O resultado é a imagem B. Normalmente, o kernel do filtro é diferente de zero apenas em alguma vizinhança N do ponto (0, 0). Fora dessa vizinhança, h(i, j) é igual a zero, ou muito próximo a isso, e pode ser desprezado. A soma é realizada sobre (i, j) н N, e o valor de cada pixel B(x, y) é determinado pelos pixels da imagem A que se encontram na janela N centrada no ponto (x, y) ( denotado é o conjunto N(x, y) ). Um kernel de filtro definido em uma vizinhança retangular N pode ser pensado como uma matriz m por n onde os comprimentos dos lados são números ímpares. Ao especificar o kernel como uma matriz, ele deve ser centralizado. Se um pixel (x, y) está localizado nas proximidades das bordas da imagem, então as coordenadas A(x-i, y-j) para certos (i, j) podem corresponder a pixels A inexistentes fora da imagem. Este problema pode ser resolvido de várias maneiras.

Não filtre esses pixels cortando a imagem B nas bordas ou aplicando os valores originais da imagem A para seus valores.

Não inclua o pixel ausente na soma distribuindo seu peso h(i, j) uniformemente entre outros pixels na vizinhança N(x, y).

Redefina os valores de pixel fora dos limites da imagem usando a extrapolação.

Redefina os valores dos pixels fora das bordas da imagem, usando a continuação espelhada da imagem.

A escolha do método é feita levando em consideração as características específicas do filtro e da imagem.

Filtros de suavização. O filtro de suavização retangular mais simples de raio r é dado por uma matriz (2r+1) × (2r+1), cujos valores são 1/(2r+1)2, e a soma dos valores é 1. Este é o análogo 2D do filtro de média móvel 1D de passagem baixa em forma de U. Ao filtrar com esse kernel, o valor do pixel é substituído pelo valor médio do pixel em um quadrado 2r+1 ao redor dele. Exemplo de máscara de filtro 3×3:

.

Uma das aplicações dos filtros é a redução de ruído. O ruído varia independentemente de pixel para pixel e, desde que a expectativa matemática do valor do ruído seja zero, o ruído dos pixels vizinhos se cancelará quando somados. Quanto maior a janela de filtragem, menor a intensidade média de ruído, no entanto, o desfoque correspondente de detalhes significativos da imagem também ocorrerá. A imagem de um ponto branco em um fundo preto durante a filtragem (reação a um único pulso) será um quadrado cinza uniforme.

A redução de ruído usando um filtro retangular tem uma desvantagem significativa: todos os pixels na máscara de filtro a qualquer distância do processado têm o mesmo efeito no resultado. Um resultado um pouco melhor é obtido modificando o filtro com um aumento no peso do ponto central:

.

Uma redução de ruído mais efetiva pode ser alcançada se a influência dos pixels no resultado diminuir com o aumento da distância do processado. Esta propriedade é possuída por um filtro Gaussiano com um kernel: h(i, j) = (1/2ps2) exp(-(i2+j2)/2s2). O filtro gaussiano tem um kernel diferente de zero de tamanho infinito. No entanto, o valor do kernel do filtro diminui muito rapidamente para n) e, portanto, na prática, pode-se limitar a convolução com uma pequena janela em torno de (0, 0), por exemplo, tomando o raio da janela igual a 3σ.

A filtragem gaussiana também é suavizada. No entanto, ao contrário do filtro retangular, a imagem de um ponto com filtragem gaussiana será um ponto borrado simétrico, com diminuição do brilho do meio para as bordas. O grau de desfoque da imagem é determinado pelo parâmetro σ.

Filtros de contraste . Se os filtros de suavização reduzem o contraste local da imagem, desfocando-a, os filtros de aprimoramento de contraste produzem o efeito oposto e, em essência, são filtros de altas frequências espaciais. O kernel do filtro boost em (0, 0) tem um valor maior que 1, com uma soma total de valores igual a 1. Por exemplo, filtros boost são filtros com um kernel dado por matrizes:

. .

Um exemplo de aplicação do filtro é mostrado na fig. 17.3.1. O efeito de aumento do contraste é alcançado devido ao fato de o filtro enfatizar a diferença entre as intensidades dos pixels vizinhos, removendo essas intensidades umas das outras. Este efeito será mais forte quanto maior for o valor do termo central do kernel. Um artefato característico da filtragem de aprimoramento de contraste linear é a luz perceptível e halos escuros menos perceptíveis ao redor das bordas.

Filtros de diferença são filtros lineares definidos por aproximações discretas de operadores diferenciais (pelo método das diferenças finitas). Esses filtros desempenham um papel importante em muitas aplicações, por exemplo, na busca de bordas em uma imagem.

O operador diferencial mais simples é a derivada x d/dx, que é definida para funções contínuas. Variantes comuns de operadores semelhantes para imagens discretas são os filtros Prewitt e Sobel:

. .

Filtros que aproximam o operador derivativo em relação à coordenada y d/dy são obtidos por transposição de matrizes.

O algoritmo mais simples para calcular a norma do gradiente sobre três pontos adjacentes:

G(x, y) = .

Uma fórmula de cálculo simplificada também é usada:

Calculando a norma de um gradiente sobre quatro pontos adjacentes (operador de Roberts):

O algoritmo de Sobel usa oito amostras de brilho nas proximidades do ponto central:

G(x, y) = , G(x, y) @ ,

Gxx, y = - ,

Gyx, y = - .

Juntamente com uma definição mais precisa da norma gradiente, o algoritmo de Sobel também permite determinar a direção do vetor gradiente no plano de análise da imagem na forma de um ângulo j entre o vetor gradiente e a direção das linhas da matriz:

j(x, y) = argtg(Gyx, y /Gxx, y).

Ao contrário dos filtros de suavização e aumento de contraste que não alteram a intensidade média da imagem, como resultado da aplicação de operadores de diferença, como regra, obtém-se uma imagem com valor médio de pixel próximo a zero. As gotas verticais (bordas) da imagem original correspondem a pixels com grandes valores de módulo na imagem resultante. Portanto, os filtros de diferença também são chamados de filtros de detecção de limite de objeto.

Da mesma forma que os filtros acima, o método das diferenças finitas pode ser usado para compor filtros para outros operadores diferenciais. Em particular, o operador diferencial de Laplace (Laplaciano) D= 𝝏2/𝝏x2 + 𝝏2/𝝏y2, que é importante para muitas aplicações, pode ser aproximado para imagens discretas por um filtro com uma matriz (uma das opções):

.

Como visto na fig. 17.3.2, como resultado da aplicação do Laplaciano discreto, grandes valores em valor absoluto correspondem a diferenças de brilho verticais e horizontais. Um filtro é, portanto, um filtro que encontra limites de qualquer orientação. Encontrar bordas em uma imagem pode ser feito aplicando este filtro e pegando todos os pixels cujo valor absoluto excede um determinado limite.

No entanto, este algoritmo tem desvantagens significativas. A principal delas é a incerteza na escolha do valor limite. Para diferentes partes da imagem, um resultado aceitável geralmente é obtido em limiares significativamente diferentes. Além disso, os filtros diferenciais são muito sensíveis ao ruído da imagem.

Convolução cíclica bidimensional. Tal como acontece com os sinais 1D, a convolução 2D pode ser realizada no domínio da frequência espacial usando algoritmos FFT e multiplicando os espectros de imagem 2D e o kernel do filtro. Também é cíclico, e geralmente é realizado em uma versão deslizante. Levando em conta a ciclicidade, para calcular o padrão constante do espectro do kernel, as dimensões da máscara de filtro do kernel são duplicadas ao longo dos eixos e preenchidas com zeros, e as mesmas dimensões da máscara são usadas para destacar a janela que desliza sobre a imagem, dentro da qual a FFT é executada. A implementação de um filtro FIR com uma FFT é especialmente eficiente se o filtro tiver uma grande área de referência.

Filtros não lineares . No processamento digital de imagens, algoritmos não lineares baseados em estatísticas de classificação são amplamente utilizados para restaurar imagens danificadas por vários modelos de ruído. Eles permitem evitar distorções adicionais da imagem ao remover o ruído, além de melhorar significativamente os resultados dos filtros em imagens com alto grau de ruído.

Vamos introduzir o conceito de uma vizinhança M de um elemento de imagem A(x, y), que é central para esta vizinhança. No caso mais simples, a vizinhança M contém N-pixels - pontos que caem na máscara de filtro, incluindo (ou não) o central. Os valores desses N-elementos podem ser colocados em uma série variacional V(r), classificados em ordem crescente (ou decrescente), e certos momentos desta série podem ser calculados, por exemplo, o valor médio do brilho mN e a dispersão dN. O cálculo do valor de saída do filtro, que substitui a amostra central, é realizado pela fórmula:

B(x, y) = aÀ(x, y) + (1-a)mN. (17.3.2)

O valor do coeficiente a = está associado a uma certa dependência com as estatísticas das amostras na janela do filtro, por exemplo:

a = dN/(dN + k dS), (17.3.3)

onde dS é a variância do ruído sobre a imagem como um todo ou sobre a vizinhança S para S > M e MОS, k é a constante de confiança da variância da vizinhança S. Como segue desta fórmula, para k=1 e dN » dS, a » 0,5 ocorre, e o valor de B(x, y) = (A(x, y) + mN)/2, ou seja, eles se somam igualmente sobre os valores da amostra central e o valor médio dos pixels de seu bairro M. Com um aumento nos valores de dN, a contribuição do valor da referência central para o resultado aumenta; com uma diminuição, o valor de mN. O peso da contribuição dos valores médios sobre a vizinhança M pode ser alterado pelo valor do coeficiente k.

A escolha de uma função estatística e a natureza da dependência do coeficiente a sobre ela podem ser bastante diversas (por exemplo, de acordo com as variâncias das diferenças nas leituras no bairro M com uma leitura central), e depende tanto de do tamanho da abertura do filtro e da natureza das imagens e do ruído. Em essência, o valor do coeficiente a deve especificar o grau de dano à amostra central e, consequentemente, a função de empréstimo para sua correção das amostras do bairro M.

Os tipos mais simples e comuns de filtros não lineares para processamento de imagens são filtros de limiar e de mediana.

Filtragem de limite é dado, por exemplo, da seguinte forma:

B(x, y) =

Valor pé o limite do filtro. Se o valor do ponto central do filtro exceder o valor médio das amostras mN em sua vizinhança M pelo valor limite, então ele é substituído pelo valor médio. O valor limite pode ser constante ou funcionalmente dependente do valor do ponto central.

Filtragem mediana é definido da seguinte forma:

B(x, y) = med (M(x, y)),

ou seja, o resultado da filtragem é o valor mediano dos pixels da vizinhança, cuja forma é determinada pela máscara do filtro. A filtragem mediana pode remover efetivamente o ruído de uma imagem que afeta pixels individuais de forma independente. Por exemplo, tais interferências são pixels "quebrados" durante o disparo digital, ruído de "neve", quando alguns pixels são substituídos por pixels com intensidade máxima, etc. A vantagem da filtragem mediana é que um pixel "quente" em um fundo escuro será substituído escuro, e não "manchado" ao redor do bairro.

A filtragem mediana tem uma seletividade pronunciada em relação aos elementos da matriz, que são um componente não monotônico de uma sequência de números dentro da abertura do filtro. Ao mesmo tempo, o filtro mediano deixa o componente monotônico da sequência inalterado. Devido a esse recurso, os filtros medianos, com uma abertura selecionada de forma otimizada, preservam as bordas nítidas dos objetos sem distorção, suprimindo ruídos não correlacionados ou fracamente correlacionados e detalhes de tamanho pequeno.

Filtros extremos determinado pelas regras:

Bmin(x, y) = min(M(x, y)),

Bmax(x, y) = max (M(x, y)),

ou seja, o resultado da filtragem são os valores mínimo e máximo de pixel na máscara de filtro. Tais filtros são aplicados, via de regra, para imagens binárias.

17.4. COMPRESSÃO DE IMAGEM

Uma imagem típica com uma resolução de cerca de 3000×2000 a 24 bits por pixel para transmissão de cores tem um tamanho de 17 megabytes. Para dispositivos profissionais, o tamanho do raster de imagem resultante pode ser muito maior, a profundidade de cor é de até 48 bits por pixel e o tamanho de uma imagem pode ser superior a 200 megabytes. Portanto, algoritmos de compressão de imagem são muito relevantes para reduzir a quantidade de dados que representam uma imagem.

Existem duas classes principais de algoritmos:

1. Compressão sem perdas A (compressão sem perdas), se existe tal algoritmo inverso A-1 que para qualquer h - imagem A[h] = h1 temos A-1 = h. A compactação sem perdas é usada em formatos de imagem gráfica como: GIF, PCX, PNG, TGA, TIFF e é usada no processamento de informações primárias especialmente valiosas (imagens médicas, imagens aéreas e espaciais, etc.), quando até mesmo a menor distorção indesejada

2. Compressão com perdas, se não fornecer a capacidade de restaurar com precisão a imagem original. O algoritmo de recuperação de imagem aproximado emparelhado com A será indicado como A*. O par (A, A*) é escolhido para fornecer altas taxas de compressão, mantendo a qualidade visual. A compressão com perdas é aplicada em formatos gráficos: JPEG, JPEG2000, etc.

Todos os algoritmos e declarações se aplicam tanto a imagens quanto a sequências arbitrárias, cujos elementos podem assumir um número finito de valores. Ao mesmo tempo, deve-se levar em consideração que não existem algoritmos ideais que possam compactar qualquer conjunto de dados sem perda.

Algoritmos de Codificação de Comprimento de Repetição (RLE) baseiam-se em um princípio simples: substituir grupos repetidos de elementos da sequência original por um par (quantidade, elemento) ou apenas por uma quantidade.

nível de bits. Consideraremos os dados originais no nível de uma sequência de bits, por exemplo, representando uma imagem em preto e branco. Geralmente há vários 0s ou 1s seguidos, e o número de dígitos idênticos consecutivos pode ser codificado. Mas o número de repetições também deve ser codificado em bits. Pode-se considerar que cada número de repetições muda de 0 a 7 (código de 3 bits), alternando a sequência de códigos de uns e zeros. Por exemplo, as sequências podem ser comparadas com os números 7 0 4, ou seja, 7 uns, 0 zeros, 4 uns, enquanto temos um novo ano - Quanto mais longas forem as sequências de bits idênticos, maior será o efeito. Assim, uma sequência de 21 uns, 21 zeros, 3 uns e 7 zeros é codificada da seguinte forma: , ou seja, da sequência original de 51 bits, temos uma sequência de 36 bits.

Nível de bytes. Vamos supor que a entrada seja uma imagem em tons de cinza, onde 1 byte é alocado para o valor de intensidade do pixel, enquanto a expectativa de uma longa cadeia de bits idênticos é significativamente reduzida.

Vamos dividir o fluxo de entrada em bytes (código de 0 a 255) e codificar os bytes repetidos como um par (número, letra). Um único byte não pode ser alterado. Assim, os bytes AABBBCDAA codificam (2A) (3B) (C) (D) (2A).

No entanto, as modificações desse algoritmo raramente são usadas sozinhas (por exemplo, no formato PCX), porque a subclasse de sequências na qual o algoritmo é eficaz é relativamente estreita. Mais frequentemente, eles são usados ​​como um dos estágios do pipeline de compactação.

Algoritmos de dicionário em vez de codificar apenas um elemento da sequência de entrada, é realizada a codificação de uma cadeia de elementos. Isso usa um dicionário de strings (criado a partir da sequência de entrada) para codificar novas.

O algoritmo LZ77 foi um dos primeiros a usar um dicionário. Os N últimos elementos já codificados da sequência são usados ​​como um dicionário. Durante a compactação, a subsequência do dicionário "desliza" sobre a sequência de entrada. A cadeia de elementos na saída é codificada da seguinte forma: a posição da parte correspondente da cadeia de elementos processada no dicionário - deslocamento (relativo à posição atual), comprimento, o primeiro elemento após a parte correspondente da cadeia. O comprimento da cadeia correspondente é limitado de cima pelo número n. Assim, a tarefa é encontrar a maior string do dicionário que corresponda à sequência processada. Se não houver correspondências, o deslocamento zero, comprimento um e o primeiro elemento da sequência não codificada serão gravados.

O esquema de codificação descrito acima leva ao conceito de uma janela deslizante, que consiste em duas partes:

Uma subsequência de elementos já codificados de comprimento N-dicionário - buffer de pesquisa;

A subsequência de comprimento n da cadeia de elementos para a qual será feita uma tentativa de encontrar uma correspondência é o buffer de antecipação.

A decodificação de uma sequência compactada é a decodificação dos códigos gravados: cada entrada é combinada com uma cadeia de um dicionário e um elemento explicitamente escrito, após o qual o dicionário é deslocado. O dicionário é recriado à medida que o algoritmo de decodificação é executado.

Este algoritmo é o ancestral de toda uma família de algoritmos. Suas vantagens incluem um grau de compressão decente em sequências suficientemente grandes e descompressão rápida. As desvantagens incluem baixa velocidade de compactação e menor taxa de compactação do que algoritmos alternativos.

Algoritmo LZW. O dicionário neste algoritmo é uma tabela que é preenchida com cadeias de elementos à medida que o algoritmo é executado. O processo de compactação procura a string mais longa já gravada no dicionário. Cada vez que uma nova string de elementos não é encontrada no dicionário, ela é adicionada ao dicionário e o código da string é registrado. Em teoria, não há limite para o tamanho da tabela, mas o limite de tamanho melhora a taxa de compressão, uma vez que cadeias desnecessárias (não-ocorrentes) se acumulam. Quanto mais entradas uma tabela tiver, mais informações precisam ser alocadas aos códigos de loja.

A decodificação consiste na decodificação direta de códigos, ou seja, na construção de um dicionário e na saída das cadeias correspondentes. O dicionário é inicializado da mesma forma que no codificador. As vantagens do algoritmo incluem um alto grau de compactação e uma velocidade bastante alta, tanto de compactação quanto de decodificação.

Algoritmos de codificação de entropia atribua a cada elemento da sequência um código para que seu comprimento corresponda à probabilidade de ocorrência do elemento. A compressão ocorre substituindo elementos da sequência original que possuem o mesmo comprimento (cada elemento ocupa o mesmo número de bits) por elementos de comprimentos diferentes, proporcionais ao logaritmo negativo da probabilidade, ou seja, elementos que ocorrem com mais frequência do que outros possuem um código de menor comprimento.

O algoritmo de Huffman usa um código de prefixo de comprimento variável que possui uma propriedade especial: códigos mais curtos não correspondem ao prefixo (parte inicial) dos mais longos. Tal código permite a codificação um-para-um. O processo de compressão consiste em substituir cada elemento da sequência de entrada pelo seu código. A construção de um conjunto de códigos geralmente é realizada usando os chamados árvores de código.

O algoritmo de Huffman é de duas passagens. A primeira passagem pela imagem cria uma tabela de pesos dos elementos e, durante a segunda passagem, ocorre a codificação. Existem implementações do algoritmo de tabela fixa. Muitas vezes acontece que a distribuição de probabilidade a priori dos elementos do alfabeto é desconhecida, uma vez que toda a sequência não está disponível de uma só vez, enquanto modificações adaptativas do algoritmo de Huffman são usadas.

Compressão de imagem com perdas. A quantidade de informação necessária para armazenar imagens é geralmente grande. Os algoritmos clássicos, sendo algoritmos de uso geral, não levam em consideração que a informação que está sendo compactada é uma imagem - um objeto bidimensional e não fornecem um grau suficiente de compactação.

A compressão com perdas é baseada nas características da percepção humana da imagem: a maior sensibilidade em uma determinada faixa de comprimentos de onda de cores, a capacidade de perceber a imagem como um todo, sem perceber pequenas distorções. A principal classe de imagens em que os algoritmos de compactação com perdas se concentram são fotografias, imagens com transições de cores suaves.

Estimativa de perda de imagem. Existem muitas medidas para estimar perdas em imagens após sua restauração (decodificação) a partir das compactadas, porém, para todas elas, duas imagens podem ser selecionadas de tal forma que sua medida de diferença seja grande o suficiente, mas as diferenças serão quase imperceptíveis para o olho. E vice-versa - você pode pegar imagens que diferem muito a olho nu, mas têm uma pequena diferença.

A medida numérica padrão de perda geralmente é o desvio padrão (RMS) dos valores de pixel da imagem reconstruída do original. No entanto, a "medida" mais importante de avaliação de perdas é a opinião do observador. Quanto menos diferenças (ou melhor, sua ausência) um observador detectar, maior será a qualidade do algoritmo de compressão. Os algoritmos de compactação com perdas geralmente permitem que o usuário escolha a quantidade de dados "perdidos", ou seja, o direito de escolher entre a qualidade e o tamanho da imagem compactada. Naturalmente, quanto melhor a qualidade visual em uma taxa de compressão mais alta, melhor o algoritmo.

Transformada de Fourier. No caso geral, a imagem pode ser considerada em função de duas variáveis, definidas nos pontos do raster final. O conjunto de tais funções nos pontos de um raster finito fixo forma um espaço euclidiano de dimensão finita, e a eles pode ser aplicada a transformada discreta de Fourier, ou seja, a representação espectral da imagem. Ele fornece:

Não correlacionamento e independência dos coeficientes do espectro, ou seja, a precisão da representação de um coeficiente não depende de nenhum outro.

- Compactação de energia. A transformação armazena as informações básicas em um pequeno número de coeficientes. Esta propriedade é mais pronunciada em imagens fotorrealistas.

Os coeficientes de representação espectrais são as amplitudes das frequências espaciais da imagem. No caso de imagens com transições suaves, a maior parte da informação está contida no espectro de baixa frequência.

O algoritmo de compressão usado no formato JPEG é baseado na transformada discreta de Fourier de cosseno. O esquema de compressão no algoritmo é um pipeline, onde esta transformação é apenas uma das etapas, mas uma das principais. O algoritmo contém as seguintes operações principais:

1. Transfira para o espaço de cores YCbCr. Aqui Y é o componente luma, Cb e Cr são os componentes de crominância. O olho humano é mais sensível ao brilho do que à cor. Portanto, é mais importante manter maior precisão ao transmitir Y do que ao transmitir Cb e Cr.

2. Transformada discreta de cosseno (DCT). A imagem é dividida em blocos de 8 × 8. Uma transformação discreta de cosseno é aplicada a cada bloco (separadamente para os componentes Y, Cb e Cr).

3. Redução de componentes de alta frequência em matrizes DCT. O olho humano dificilmente percebe mudanças nos componentes de alta frequência, portanto, os coeficientes responsáveis ​​pelas altas frequências podem ser armazenados com menor precisão.

4. Ordenação em ziguezague de matrizes. Este é um passe de matriz especial para obter uma sequência unidimensional. Primeiro vem o elemento T00, depois T01, T10, T1. Além disso, para imagens fotorrealistas típicas, primeiro haverá coeficientes diferentes de zero correspondentes aos componentes de baixa frequência e depois muitos zeros (componentes de alta frequência).

5. Compressão primeiro pelo método RLE e depois pelo método Huffman.

O algoritmo de recuperação de imagem funciona na ordem inversa. A taxa de compressão é de 5 a 100 ou mais vezes. Ao mesmo tempo, a qualidade visual da maioria das imagens fotorrealistas permanece em um bom nível quando compactada até 15 vezes. O algoritmo e o formato são os mais comuns para transferir e armazenar imagens coloridas.

Transformação wavelet sinais é uma generalização da transformada clássica de Fourier. O termo "wavelet" (wavelet) na tradução do inglês significa "onda pequena (curta)". Wavelets são um nome generalizado para famílias de funções matemáticas de uma certa forma que são locais no tempo e na frequência, e nas quais todas as funções são obtidas a partir de uma função base deslocando-a e expandindo-a ao longo do eixo do tempo.

Em algoritmos de compressão com perdas, via de regra, todas as operações do pipeline de compressão são preservadas com a substituição da transformada discreta de Fourier por uma transformada discreta wavelet. As transformadas wavelet têm uma localização espacial de frequência muito boa e superam as tradicionais transformadas de Fourier neste indicador. Neste caso, torna-se possível aplicar uma quantização mais forte, melhorando as propriedades da sequência para compressão posterior. Algoritmos de compressão de imagem baseados nesta transformação, com a mesma taxa de compressão, apresentam melhores resultados na preservação da qualidade da imagem.

literatura

46. ​​et al. Algoritmos rápidos no processamento digital de imagens. - M.: Rádio e comunicação, 1984. - 224 p.

47. Processamento de imagem Soyfer. Parte 2. Métodos e algoritmos. - Revista Educacional Soros nº 3, 1996.

48. Ruído de cartilagem de imagens baseadas em algoritmos não lineares usando estatísticas de classificação. - Universidade Estadual de Yaroslavl, 2007.

49. Sistemas de vigilância de televisão Andreev. Parte II. Aritmética - bases lógicas e algoritmos. Tutorial. - São Petersburgo: São Petersburgo, GUITMO, 2005. - 88s.

51. Introdução ao Processamento Digital de Sinais (Fundamentos Matemáticos) - M.: Universidade Estadual de Moscou, Laboratório de Computação Gráfica e Multimídia, 2002. - http://pv. *****/dsp/dspcurso. pdf, http://dsp-book. *****/dspcurso. djvu, http://geogin. *****/archiv/dsp/dsp4.pdf.

1i. e outros fundamentos algorítmicos de gráficos raster. – Universidade de Tecnologias de Informação da Internet. – http://www. *****/goto/course/rastergraph/

2i. Lukin-Electronic Systems: Notas de Aula. ITMO, 2004. - São Petersburgo, ITMO IFF, 2004. - http://iff. *****/kons/oes/KL. htm

Sobre os erros observados e sugestões de adições: ****@***ru.

direito autoral©2008DavydovUMA.V.

Laboratório nº 1

Algoritmos de Processamento de Imagem

Operação de convolução

A convolução é um algoritmo muito amplo que pode ser usado tanto para pré-processamento de imagens quanto para reconhecimento e identificação de objetos. Seja a imagem dada por uma matriz de brilho bidimensional F" , e a matriz de resposta ao impulso H. Convolução matemática de uma matriz F com núcleo H pode ser definida pela seguinte fórmula:

Onde M2xN2 - tamanho da matriz do kernel de convolução. Tamanho da matriz Fé igual a (M1+M2-1)x(N1+N2-1), onde M1xN1 - o tamanho da matriz original F" . Matriz Fé obtido do original adicionando elementos nas bordas da matriz de acordo com alguma regra para trazê-la ao tamanho necessário. Normalmente, a matriz original é preenchida com zeros nas bordas para metade da largura da matriz. H esquerda e direita e, respectivamente, metade da altura para cima e o mesmo para baixo. Então o tamanho da matriz resultante R será o mesmo que a matriz F" .

A convolução pode ser calculada diretamente "executando" uma matriz sobre outra, como já mostrado acima. Na fig. 1 mostra o esquema para calcular a convolução (o tamanho da matriz da máscara é igual a 3x3). O operador de convolução pode ser visto como uma matriz de coeficientes (máscaras) que são multiplicados elemento a elemento com o fragmento de imagem selecionado, seguido de somatório para obter um novo valor do elemento da imagem filtrada. Essa matriz pode ser de tamanho arbitrário, não necessariamente quadrada.

Arroz. 1. Implementação da operação de convolução.

Exercício

Implemente um algoritmo que realize a operação de convolução da imagem original com uma máscara-matriz.

O tamanho e o tipo da máscara-matriz são definidos pelo usuário.

Use as seguintes matrizes de máscara para implementar vários algoritmos de processamento de imagem:

• para suavizar e suprimir o ruído na imagem, uma máscara de matriz 3x3 da seguinte forma é usada:

para enfatizar os contornos, são usadas máscaras de matriz da seguinte forma:

1/9*

A máscara da seguinte forma é usada para selecionar contornos:

4. Implemente um filtro mediano, que é usado para suprimir o ruído de ponto e impulso. O pixel da imagem e seus vizinhos na área em consideração são alinhados em uma série variacional (em valores de pixel ascendentes ou descendentes) e o valor central dessa série variacional é selecionado como um novo valor de pixel. O resultado da filtragem média é que qualquer ruído aleatório contido na imagem será efetivamente eliminado. Isso ocorre porque qualquer mudança abrupta aleatória na intensidade do pixel dentro da região em consideração será classificada, ou seja, ele será colocado na parte superior ou inferior dos valores classificados nessa região e não será contado, pois o valor central é sempre selecionado para o novo valor do elemento.

5. Implemente o algoritmo de gravação. A gravação é feita de maneira semelhante aos algoritmos de média ou aprimoramento de borda. Cada pixel na imagem é processado por um núcleo de relevo 3x3 (matriz-máscara). Por exemplo, como um núcleo de relevo, você pode usar a seguinte matriz de máscara:

Depois que o valor do pixel é processado pelo mecanismo de gravação, é adicionado 128. Assim, o valor dos pixels de fundo se tornará a cor cinza média (vermelho = 128, verde = 128, azul = 128). Valores superiores a 255 podem ser arredondados para 255.

Na versão em relevo da imagem, os contornos parecem ser extrudados acima da superfície. A direção do realce da imagem pode ser alterada alterando as posições 1 e -1 no kernel. Se, por exemplo, os valores 1 e -1 forem trocados, a direção da luz de fundo será invertida.

6. Aquarela de imagens. O filtro de aquarela transforma a imagem, e depois de processada parece que foi escrita em aquarela:

O primeiro passo para aplicar um filtro de aquarela é suavizar as cores da imagem. Uma maneira de suavizar é aplicar a média de cor mediana em cada ponto. O valor da cor de cada pixel e seus 24 vizinhos (o tamanho da máscara-matriz é 5x5) são organizados em uma série variacional em ordem decrescente ou crescente. O valor de cor mediano (décimo terceiro) na série de variação é atribuído ao pixel central.

depois de suavizar as cores, você precisa aplicar um filtro de aprimoramento de borda para destacar as bordas das transições de cores.

Representação de imagem

Existem dois tipos principais de representações de imagens - vetoriais e raster.

Na representação vetorial, a imagem é descrita por um conjunto de linhas (vetores), que contém as coordenadas dos pontos inicial e final, a curvatura das linhas e outras características geométricas. também descrito. Em outras palavras, uma representação raster requer a formação de algum modelo matemático. Portanto, a representação vetorial é utilizada principalmente na resolução de problemas de síntese de imagens. Embora alguns algoritmos de reconhecimento de imagem exijam uma representação vetorial para seu trabalho, que deve ser obtida a partir da imagem original.

Uma imagem raster é uma ou mais matrizes que descrevem a distribuição espacial das características da imagem em uma determinada grade de coordenadas cartesianas. Neste caso, a imagem é construída a partir de um conjunto de pontos e possui uma estrutura raster. O elemento principal de uma representação raster de uma imagem é um pixel (abreviação da frase "picture elements" - elementos de imagem), que possui coordenadas em um sistema de coordenadas raster e alguns atributos (cor, brilho, transparência, etc.). O número de pixels ao longo das coordenadas X e Y (horizontal e verticalmente) define a resolução (dimensão) da representação da imagem. A cor de um pixel é dada por sua profundidade, que é o número de bits necessários para especificar qualquer cor.

As imagens raster, dependendo dos métodos de definição da cor de um pixel e das propriedades da imagem original, são divididas em:

Binário

Meio-tom

Paleta

cor cheia

Na representação binária, a cor de um pixel pode ser branca ou preta e é codificada em um bit. A imagem é uma matriz. Cada elemento I (i , j ) desta matriz tem um valor de 0 ou 1, onde i é o número da linha e é o número da coluna j do elemento correspondente ao pixel dado (Fig. 1).

Nas imagens em tons de cinza, os pixels representam valores de brilho correspondentes aos tons de cinza. Índices de matriz que descrevem a imagem de meio-tom definem a posição do pixel no raster e o valor do elemento da matriz

- define seu brilho I (i, j) (Fig. 2).

As imagens da paleta são descritas por duas matrizes (Fig. 3). Um armazena os valores dos índices, que especificam o acesso à linha da matriz da paleta. A matriz da paleta é um mapa de cores. Ele contém 3 grupos de colunas - correspondentes às cores vermelho "R", verde "G" e azul "B". Eles definem a cor do pixel correspondente.

Uma paleta é uma matriz Nc 3, onde Nc é o número de cores.

Algoritmos de pré-processamento de imagem

As imagens coloridas são construídas no formato RGB e representam três matrizes R (i , j ), G (i , j ), B (i , j ) . Os elementos correspondentes de cada matriz contêm as intensidades das cores vermelha, verde e azul para o pixel especificado pelos índices da matriz. Assim, uma imagem colorida não possui um mapa de cores e a cor de cada pixel é representada por três números retirados das matrizes correspondentes (Fig. 4).

O formato dos números em matrizes pode ser inteiro ou ponto flutuante. O primeiro caso refere-se às chamadas imagens digitalizadas obtidas por meio de diversos dispositivos – scanners, câmeras digitais, câmeras de televisão, etc. É neste formato que as informações sobre as imagens são armazenadas em arquivos gráficos padrão.

A segunda opção é utilizada para representação interna de imagens durante o seu processamento. Nesse caso, é conveniente normalizar os dados de intensidade para um intervalo, por exemplo, para o intervalo , e realizar vários cálculos com números flutuantes e, em seguida, converter o resultado para o formato inteiro original. Este método permite reduzir erros de cálculo e melhorar a precisão do resultado do processamento.

Para imagens totalmente coloridas, uma das opções é o número máximo de cores que podem ser representadas nesse formato. As imagens mais usadas têm 16, 256, 65536 (High Color) e 10,7 milhões (True Color) cores.

Algoritmos de pré-processamento de imagem

	0 0 0 0 1 1 1 0 0	120 122 125 128 115 117 118
	1 0 0 0 1 1 1 1 0	119 121 124 125 128 130 133
	1 1 0 0 1 1 0 0 1	122 122 124 123 127 126 128
		120 121 123 125 127 125 126
	1 1 1 0 1 1 0 0 0
		118 110 109 108 108 109 110
	0 0 1 0 0 1 0 0 1

Algoritmos de pré-processamento de imagem

Matriz de Índice

31 15 03 09

matriz de paleta

Algoritmos de pré-processamento de imagem

Uma imagem colorida pode ser representada não apenas no formato RGB, mas também usando outros sistemas de cores.

No sistema HSB, a cor é representada pelas seguintes características de cor: Matiz - tom da cor;

Saturação - saturação; Brilho - brilho.

Acredita-se que esse sistema de cores corresponda às peculiaridades da percepção humana da cor.

No sistema LAB, a cor é considerada como uma combinação de brilho (luminosidade) e dois valores de crominância independentes, que determinam a verdadeira cor de um pixel. Cromaticidade A - o componente de cor é selecionado na faixa de magenta a verde. Cromaticidade B - o segundo componente de cor é selecionado na faixa de amarelo a azul.

Existem outros sistemas de representação de cores. Naturalmente, eles estão todos conectados, e de uma representação pode-se obter outra. A variedade de sistemas de cores se deve às tarefas resolvidas com sua ajuda. Por exemplo, é mais conveniente realizar a correção de cores no sistema LAB, para reproduzir a imagem na tela do monitor no sistema RGB, é melhor imprimir,

Algoritmos de pré-processamento de imagem

usando a representação CMYK. No entanto, em qualquer caso, ao processar imagens e reconhecê-las, eles trabalham com uma representação raster de imagens contendo uma ou mais matrizes.

Classificação de algoritmos de pré-processamento

Os algoritmos de pré-processamento de imagem são divididos em diferentes grupos, dependendo do recurso de classificação. Todos os algoritmos de pré-processamento devem melhorar a qualidade das imagens de alguma forma ou convertê-las em uma forma que seja mais conveniente para o processamento subsequente.

Algoritmos destinados a melhorar a reprodução de cores de uma imagem são chamados de algoritmos de correção de cores. Este grupo também inclui algoritmos que trabalham com imagens em tons de cinza que alteram suas características de brilho e contraste.

Algoritmos destinados a processar as características espaciais das imagens são chamados de algoritmos. filtragem espacial. Este grupo inclui algoritmos de supressão de ruído, algoritmos de suavização espacial e algoritmos de amplificação espacial, algoritmos para supressão e amplificação de frequências espaciais.

Algoritmos que realizam operações geométricas em uma imagem são chamados algoritmos de processamento geométrico. Esses incluem:

Algoritmos de pré-processamento de imagem

– Cortar uma imagem - seleção de uma determinada parte de uma forma retangular da imagem original;

– Redimensionamento de imagem. Esses algoritmos usam vários métodos de interpolação para preencher corretamente os pixels ausentes na imagem ampliada ou recalcular os valores de pixel quando a imagem for reduzida.

– Rotação da imagem. Esses algoritmos giram a imagem original em um determinado ângulo, recalculando corretamente os valores de pixel usando vários métodos de interpolação.

Algoritmos que realizam transformações de um sistema de cores para outro são chamados algoritmos de conversão de cores. Eles também incluem algoritmos para converter imagens coloridas em escala de cinza e algoritmos de binarização que convertem a imagem original em uma imagem binária.

Algoritmos que selecionam algumas áreas na imagem original de acordo com várias condições, muitas vezes informais, são chamados de algoritmos de segmentação. Um exemplo de tal algoritmo pode ser, por exemplo, um algoritmo que deve destacar áreas de texto e informações gráficas em uma imagem de documento ou um algoritmo que destaca áreas em uma imagem de texto que pertencem a palavras individuais.

Algoritmos de pré-processamento de imagem

Algoritmos de filtragem espacial

A filtragem espacial de uma imagem em forma matemática é uma convolução discreta de uma imagem discreta com alguma resposta ao impulso de um filtro espacial

Se (i, j)	Im(i m , j n )h (m , n ), onde:

m N11 n N21

Im, Se matrizes das imagens originais e filtradas, h é a matriz da resposta ao impulso do filtro,

N 11 , N 21 limites inferiores e superiores das colunas de resposta ao impulso, N 12 , N 22 limites esquerdo e direito das linhas de resposta ao impulso.

A matriz de resposta ao impulso pode ser obtida calculando o filtro espacial com base nos parâmetros fornecidos. Uma grande quantidade de literatura sobre filtragem digital é dedicada a métodos de cálculo de filtros espaciais, por exemplo. Para cálculos práticos, você pode usar pacotes matemáticos padrão, por exemplo, o sistema “MATLAB” inclui o sistema de cálculo de filtro “Image Filter Design”.

Observe que a filtragem também pode ser realizada no domínio da frequência. Naquilo

Algoritmos de pré-processamento de imagem

Nesse caso, a ordem de filtragem é a seguinte:

Converta a imagem do domínio espacial para o domínio da frequência usando a transformada discreta de Fourier 2D

Realize a multiplicação por elementos da matriz de frequência da imagem pela matriz de frequência do filtro

O resultado obtido é convertido em domínio espacial usando a transformada discreta bidimensional inversa de Fourier.

Im(x, y)	Im(f x , f y )	Se (f x , f y ) Im(f x , f y ) H (f x , f y )	Se (fx, fy)		Se (x, y).

A filtragem de imagens no domínio da frequência raramente é utilizada devido à grande quantidade de cálculos. No entanto, esse método de filtragem é amplamente utilizado em cálculos teóricos na análise de opções de processamento de imagens. Ele permite que você visualize com bastante clareza que tipo de filtragem é necessária. Por exemplo, se você precisar destacar mudanças acentuadas no brilho da imagem, é óbvio que você precisa usar filtros passa-altas. Pelo contrário, se você precisar se livrar do ruído de baixa frequência - circuitos trêmulos, picos individuais, etc., precisará usar filtros passa-baixa. Parâmetros de filtro específicos são selecionados com base na análise de frequência de interferência e nas propriedades da imagem original.