Nelson Ismar da Silva Junior
Orientador: Prof. Arnaldo de Albuquerque Araújo
UM SISTEMA DE COMPRESSÃO DE IMAGENS
APLICADO A DOCUMENTOS HISTÓRICOS
Dissertação
apresentada
ao
Departamento
de
Ciência
da
Computação do Instituto de Ciências
Exatas da Universidade Federal de
Minas Gerais, como requisito parcial
para a obtenção do grau de Mestre em
Ciência da Computação.
UNIVERSIDADE FEDERAL DE MINAS GERAIS
Instituto de Ciências Exatas
Departamento de Ciência da Computação
Belo Horizonte
1993
O capinar é sozinho,
mas a colheita é coletiva.
Guimarães Rosa
RESUMO
Este trabalho descreve o estudo e a implementação de técnicas de compressão de
imagens digitais, voltadas para o armazenamento de imagens, em plataformas IBM
PC compatíveis e padrão gráfico SVGA. Apresenta conceitos do Processamento Digital
de Imagens relacionados ao tema e descreve detalhadamente os algoritmos
implementados. Em seguida, mostra como foi realizada a parametrização das rotinas,
adequando-as a um conjunto de imagens de documentos históricos. Os resultados da
compressão e descompressão das imagens são avaliados. É proposto, como aplicação
das rotinas implementadas, um sistema gerenciador de banco de dados de imagens de
documentos históricos.
This work describes the study and implementation of digital images compression
techniques images storage, based on IBM PC compatibles and SVGA graphic card,
introduces the Digital Image Processing involved concepts and describes in detail the
implemented algorithms. Next, it shows how the parametrization of the routines was
carried out. The image compression and decompression results are analised. As an
application, an historical documents images database management system is
proposed.
Sumário
1. Introdução
1.1 Motivação
1.2 Organização do Trabalho
2.Conceitos
2.1 Sistema Visual Humano
Lei de Weber-Fechner
Efeito Mach Band
Excitação e Inibição
Células Ganglionares
Córtex Visual
Modelo para o Sistema Visual Humano
2.2 Compressão de Imagens
Mapeamento
Quantização
Quantização de Lloyd-Max
Codificação
Entropia
Código de Huffman
Código de Lempel-Ziv
Medidas de Distorção
Imagens Gráficas
2.3 Classificação das Técnicas
2.4 Conclusão
3. Algoritmos
3.1 RLC - Run Length Coding (Codificação Seqüencial)
Descrição do Método
Algoritmo de Compressão
Algoritmo de Descompressão
Código Modificado de Huffman
Variações do Método
3.2 MREAD - Modified Relative Element Address Designate Coding
Descrição do Método
Algoritmo de Compressão
Algoritmo de Descompressão
Variações do Método
01
02
02
04
04
05
07
07
08
09
10
11
11
13
14
16
17
18
19
20
21
21
22
24
24
25
25
26
26
28
28
29
30
31
31
3.3 BTC - Block Truncation Coding (Truncagem de Blocos)
Descrição do Método
Algoritmo de Compressão
Algoritmo de Descompressão
Parâmetros Estatísticos
Quantização dos Parâmetros
Seleção do Plano de Bits
Variações do Método
3.4 PCM - Pulse Code Modulation
Descrição do Método
Algoritmo de Compressão
Algoritmo de Descompressão
3.5 DPCM Differential Pulse Code Modulation
Descrição do Método
Algoritmo de Compressão
Algoritmo de Descompressão
Codificação Preditiva Preservadora de Informação
DM - Delta Modulation
DPCM Unidimensional
DPCM Bidimensional
DPCM Adaptativo
3.6 TC - Transform Coding
Descrição do Método
Algoritmo de Compressão
Algoritmo de Descompressão
Codificações Zonal e Por Limiar
Alocação de Bits
Compressão Híbrida
Codificação Adaptativa
3.7 PC - Pyramid Coding
Descrição do Método
Algoritmo de Compressão
Algoritmo de Descompressão
Quantização
Codificação
3.8 VQ - Vector Quantization (Quantização Vetorial)
Definição
Dicionário de Vetores
Algoritmo LBG
Scalar Quantization/Vector Quantization e
Vector Quantization/Vector Quantization
Classified VQ Coding
Predictive VQ Coding
Adaptive Transform VQ Coding
BTC/VQ Coding
3.9 Técnicas de Segunda Geração
3.10 Formatos
31
31
32
32
33
34
35
37
38
38
40
40
41
42
43
43
44
44
45
45
45
46
46
48
48
48
49
49
50
50
51
54
54
54
55
55
55
56
56
56
58
59
59
60
60
61
Padrões de Formatos de Imagens
Formato BM
Formato JPEG
3.11 Conclusão
4. Descrição do Sistema
4.1 Hardware
4.2 Apresentação do Sistema
Compressão
Descompressão
Conversão de Arquivos BM
Medidas de Distorção
Algoritmo LBG
Interface PixelWare
Estrutura Interna
4.3 Algoritmos
RLC - Run Length Coding
MREAD - Modified Relative Element
Address Designate Coding
BTC - Block Truncation Coding
PCM - Pulse Code Modulation
DPCM - Differential Pulse Code Modulation
PC - Pyramid Coding
DCT - Discrete Cosine Transform Coding
VQ - Vector Quantization
VQ Pura
VQ/BTC
4.4 Conclusões
5. Resultados
6. Conclusões
Apêndices
A - Código Modificado de Huffman
A1 - Bits Menos Significativos para Seqüências de Brancos
A2 - Bits Mais Significativos para Seqüências de Brancos
A3 - Bits Menos Significativos para Seqüências de Pretos
A4 - Bits Mais Significativos para Seqüências de Pretos
B - Código de Huffman para Modos do Algoritmo MREAD
C - Compressão DPCM
C1 - Compressão Sem Perda de Informação
C1.1 Bits Menos Significativos (erros entre -31 e 31)
C1.2 Bits Mais Significativos (erros < -31)
C1.3 Bits Mais Significativos (erros > 31)
61
61
62
66
67
67
68
68
69
69
70
70
71
73
74
74
75
76
77
78
80
82
83
83
84
84
85
C2 - Compressão Com Perda de Informação
C2.1 Quantização em 16 Níveis
C2.2 Quantização em 8 níveis
C2.3 Quantização em 2 níveis
C2.4 Quantização Adaptativa
D - Compressão PC
D1 - Matriz de Convolução
D2 - Códigos de Huffman
D2.1 Quantização em 3 Níveis
D2.2 Quantização em 5 Níveis
D2.3 Quantização em 9 Níveis
D2.4 Quantização em 17 Níveis
E - Compressão DCT
E1 - Matriz de Alocação de Bits
E2 - Quantização
F - Compressão VQ
F1 - Alfabeto VQ Pura
F2 - Alfabetos VQ/BTC
F2.1 Bit Maps
F2.2 Parâmetros Estatísticos
Referências Bibliográficas
Bibliografia Recomendada
Lista de Figuras
Figura 2.1
Figura 2.2
Figura 2.3
Figura 2.4
Figura 2.5
Figura 2.6
Figura 2.7
Figura 2.8
Figura 2.9
Figura 2.10
Figura 2.11
Figura 2.12
Figura 2.13
Figura 3.1
Figura 3.2
Figura 3.3
Figura 3.4
Figura 3.5
Figura 3.6
Figura 3.7
Figura 3.8
Figura 3.9
Figura 3.10
Figura 3.11
Figura 3.12
Figura 3.13
Figura 3.14
Figura 3.15
Figura 3.16
Figura 3.17
Figura 3.18
Figura 3.19
Figura 3.20
Figura 3.21
Figura 3.22
Figura 3.23
Experimento de Weber-Fechner
∆L/L em função de log(L)
Ilustração do efeito mach band
Inibição lateral
Resposta espacial das células da retina
Modelo do sistema visual humano
Modelo da compressão de imagens
Mapeamento da codificação seqüencial
Mapeamento por transformação linear
Quantização: relação entre entrada e saída
Construção do código de Huffman
Evolução da razão de compressão média das técnicas
de primeira geração
Razão de compressão média das técnicas de primeira
e segunda gerações
Modelo markoviano para representação de sinais binários
CCITT - codificação READ modificado: modos de
codificação e pixels de referência
Blocos originais reconstruídos por truncagem de blocos
Bits independentes em bloco 4x4, compressão BTC
PCM básico
Saltos de luminância na compressão PCM
Exemplo de quantização com pseudo-ruído
Compressão DPCM
DM - típicos sinais de entrada e saída
Pixels usados na predição bidimensional
Compressão por transformada
Exemplos de zonas usadas na compressão DCT
Exemplo de alocação de bits a 0,5 bits/pixel para a
codificação zonal, bloco de 16x16 pixels
Representação gráfica unidimensional da geração da
pirâmide gaussiana
Impulso ω(r) em função do parâmetro a
Compressão SQ/VQ
Compressão VQ/VQ
Classificação de vetores
Matriz de atribuição de bits - compressão adaptativa
por transformada/VQ
Header das imagens BM na versão 2.0
Valores possíveis para os parâmetros de compressão do
formato BM
Compressão DCT (JPEG)
Preparação dos coeficientes quantizados para codificação
06
06
07
08
09
10
11
12
12
14
18
22
22
27
33
34
38
39
39
41
42
44
45
47
49
50
51
53
58
58
59
60
62
63
63
Figura 3.24
Figura 3.25
Figura 3.26
Figura 4.1
Figura 4.2
Figura 4.3
Figura 5.1
Figura 5.2
Figura 5.3
Figura 5.4
Figura 5.5
Figura 5.6
Figura 5.7
Figura 5.8
Figura 5.9
Figura 5.10
Figura 5.11
Figura 5.12
entrópica
Descompressão DCT
Compressão JPEG sem perda de informação
Predição por vizinhança
Interface PixelWare - algoritmos de compressão de
imagens disponíveis
Interface PixelWare - resultados de compressão
Módulos do sistema de compressão de imagens
Imagens-amostras originais (8 bits/pixel)
Imagens-amostras originais (1 bit/pixel)
Imagem 1, reconstruída, PCM
Imagem 1, reconstruída, BTC
Imagem 1, reconstruída, DPCM
Distribuição típica dos erros de predição nas
imagens-amostras
Pirâmides da compressão PC, Imagem 1
Imagem 1, reconstruída, PC
Imagem 1, reconstruída, DCT
Imagem 1, reconstruída, VQ
Imagem 6 original, VQ pura e associada a BTC
Imagem 1, reconstruída, JPEG
64
65
65
65
71
72
73
Lista de Tabelas
Tabela 2.1
Tabela 2.2
Tabela 3.1
Tabela 3.2
Tabela 3.4
Tabela 5.1
Tabela 5.2
Limites de intervalos e valores representativos para
quantização em 4 níveis, para a distribuição gaussiana,
média zero e variância um
Códigos típicos
CCITT - READ modificado: tabela de códigos
Combinações permitidas para média e desvio padrão a
16 níveis de cinza, compressão BTC
Codificação adaptativa do plano de bits a 256 níveis de cinza
Resultados da compressão e descompressão da Imagem 1
(1 bit/pixel)
Resultados da compressão e descompressão da Imagem 1
(8 bits/pixel)
16
17
30
35
38
Lista de Abreviações
BTC
BM
CBM
CCITT
DBMS
DCT
DM
DPCM
EDIC
Block Truncation Coding
Bit Map
Compressed Bit Map
International Telegraph and Telephone Consultative Committee
Database Managing System
Discrete Cosine Transform
Delta Modulation
Differential Pulse Code Modulation
Edge Difference Coding
ISO
JPEG
KLT
LBG
MAE
MSE
MREAD
PC
PCM
PDI
PSNR
RAC
READ
RLC
SNR
SQ
TC
VQ
International Standard Organization
Joint Photographic Experts Group
Karhunen-Loève Transform
Linde, Buzo and Gray
Mean Absolute Error
Mean Square Error
Modified Relative Element Address Coding
Pyramid Coding
Pulse Coding Modulation
Processamento Digital de Imagens
Peak Signal to Noise Ratio
Relative Address Coding
Relative Element Address Coding
Run Length Coding
Signal to Noise Ratio
Scalar Quantization
Transform Coding
Vector Quantization
1. INTRODUÇÃO
O processamento digital de imagens (PDI) [GW87] é uma ciência relativamente recente,
tendo proporcionado suas primeiras aplicações reais na década de 60, com o surgimento
dos computadores de terceira geração, que ofereciam a velocidade e a capacidade de
armazenamento requeridas para implementações de seus algoritmos.
Uma das primeiras aplicações do PDI foi o processamento das imagens da sonda americana
Ranger 7. O sistema de captura de imagens da sonda, devido a suas limitações, fornecia
imagens com inúmeros tipos de degradação, como borramento, distorções geométricas e
ruído de fundo. Essas imagens foram processadas com sucesso por computadores digitais e,
desde então, as imagens geradas nas missões espaciais têm sido rotineiramente tratadas
pelo PDI.
Paralelamente, foi ampliado o campo de aplicações do PDI, de maneira que hoje essas são
encontradas nos ramos da medicina (radiografias, tomografias, cintilografias), biologia,
geografia, cartografia, meteorologia, astronomia, geologia, arqueologia, indústria e defesa,
dentre outros.
O PDI pode ser dividido em quatro áreas, de acordo com o objetivo do processamento
[GW87]:
•
•
•
•
Realce: visa a melhoria da qualidade da imagem. A qualidade de uma imagem pode ser
definida por critérios subjetivos (pode-se torná-la mais atrativa ao observador), ou
objetivos (aumento de contraste, intensificação de contornos, redução de ruído).
Restauração: procura eliminar degradações ocorridas no processo de geração da
imagem (distorções geométricas e fotométricas causadas por falhas no sensoriamento,
perturbações atmosféricas e mecânicas).
Análise: o seu objetivo é o de extrair informações contidas nos vários objetos de uma
imagem, de maneira automática, sem que seja necessária a intervenção humana. O
reconhecimento de padrões é uma aplicação direta das técnicas de análise de imagens.
Compressão: visa a redução da quantidade de bits necessária ao armazenamento ou à
transmissão de imagens digitais.
Uma imagem monocromática é definida [GW87] como uma função bidimensional de
intensidade luminosa I(x,y), onde x e y representam coordenadas espaciais e o valor de
I(x,y) é proporcional ao brilho (ou nível de cinza) no ponto (x,y).
Uma imagem digital, f(m,n), é o produto da discretização de I(x,y), em termos de
coordenadas espaciais e intensidade luminosa. Pode-se considerar uma imagem digital
como uma matriz, cujos índices de linha e coluna identificam um ponto da imagem,
enquanto que cada elemento da matriz identifica o nível de cinza naquele ponto. Os
elementos desta matriz são chamados de picture elements, pixels ou pels.
A quantidade de dados necessária para se representar cenas através de imagens digitais é
geralmente elevada. O objetivo da codificação, ou compressão de imagens é o de reduzir,
tanto quanto possível, o número de bits necessários a esta representação.
A compressão de imagens apresenta três campos básicos de aplicação [GW87]: (a)
armazenamento; (b) transmissão; (c) análise de imagens. Os métodos de compressão de
imagens são aplicáveis a qualquer um dos campos, mas é importante observar que, a
escolha de uma determinada técnica depende, além de outros fatores, da aplicação
específica.
São exemplos de aplicações da compressão de imagens, (a) a otimização da utilização de
recursos de memória de bancos de imagens para uso científico, educacional, médico,
artístico, etc.; (b) transmissão de imagens comprimidas de satélites, TV, radar,
teleconferência, fac-símile e outros tipos de comunicação via sinais digitais; (c) redução da
quantidade de dados processados por algoritmos de reconhecimento de padrões.
1.1 Motivação
O objetivo primário do trabalho aqui desenvolvido foi o de se executar um estudo intensivo
da compressão de imagens, visando à formação de uma base de conhecimentos em uma
área ainda não explorada pelo Núcleo de Processamento Digital de Imagens do DCCUFMG.
Paralelamente, a implementação de algoritmos e a sua avaliação com relação a uma
aplicação específica complementam a base teórica construída, fornecendo subsídios para
futuras incursões neste campo.
A aplicação definida foi a utilização dos algoritmos de compressão de imagens para a
construção de um banco de imagens de documentos históricos. Para tal aplicação, é
imprescindível que as imagens comprimidas sejam rapidamente recuperadas e exibidas.
Além disso, são desejáveis altas razões de compressão e baixo grau de distorção com
relação à imagem original. Dentre os diversos algoritmos estudados, foram selecionados
para a implementação aqueles que melhor se adequaram a tais restrições.
1.2 Organização do Trabalho
O presente trabalho encontra-se subdividido em seis capítulos e seis apêndices. O Capítulo
2 apresenta revisão bibliográfica sobre o tema compressão de imagens, procurando explorar
os conceitos fundamentais de PDI relacionados ao assunto. As diferentes etapas do
processo de compressão de imagens digitais são caracterizadas e são definidos critérios de
avaliação dos resultados. Classificam-se as técnicas de compressão de imagens, conforme
variados critérios e discute-se a sua evolução.
Os algoritmos de compressão de imagens mais importantes são analisados em detalhe e são
citadas algumas de suas principais variações no Capítulo 3. Os formatos de imagens raster
BM (Bit Map) e JPEG (Joint Photographic Experts Group) são apresentados.
O Capítulo 4 descreve as rotinas de compressão de imagens implementadas e as interfaces
que as disponibilizam. São definidos os parâmetros utilizados na implementação,
adequados a um conjunto de imagens de documentos históricos. É descrita a estrutura
modular do sistema, bem como a sintaxe das funções e dos utilitários disponíveis. Para os
casos em que é possível a priori a determinação da razão de compressão obtida, esta é
apresentada.
O Capítulo 5 descreve a aplicação das rotinas implementadas ao conjunto de imagens de
documentos históricos. É feito estudo comparativo do desempenho de cada algoritmo para
esta classe de imagens, considerando-se os aspectos de distorção final, tempos de
compressão e descompressão e razões de compressão obtidas. Como referência na
avaliação, também são apresentados os resultados obtidos pelo algoritmo proposto pelo
JPEG.
No Capítulo 6, são feitas as considerações finais, concluindo-se o trabalho.
Nos apêndices encontram-se os parâmetros de compressão adotados nas implementações e
definidos com base em estudos feitos com o conjunto de imagens-amostras de documentos
históricos.
2. CONCEITOS
Este capítulo apresenta conceitos não triviais do PDI, relacionados à compressão de
imagens, mencionados ao longo do trabalho.
Inicialmente, são discutidas as características do sistema visual humano, exploradas pelos
algoritmos desenvolvidos até hoje, e constrói-se um modelo de seu funcionamento. Ilustrase que, devido a tais características, determinados elementos de informação de uma imagem
podem ser desprezados, uma vez que são naturalmente filtrados pelo sistema visual
humano. Como conseqüência, a quantidade de bits necessária para a formação da imagem
pode ser reduzida.
Em seguida, é definido o processo de compressão de imagens, através da enumeração e
discussão das etapas que o compõem. São apresentados os critérios matemáticos de
medidas de distorção e os principais mecanismos de codificação disponíveis. Classificamse as técnicas de compressão de imagens quanto à preservação da imagem final, quanto ao
domínio em que atuam, quanto a sua fundamentação e quanto aos parâmetros da
compressão.
2.1 Sistema Visual Humano
Em muitas das aplicações do PDI, o objetivo final é a análise visual subjetiva da imagem,
realizada pelo observador [Lim90]. Este fato justifica o estudo do sistema visual humano,
na medida em que as técnicas de PDI utilizadas em tais aplicações devem ser adequadas ao
mesmo. Neste item discutem-se brevemente as características do sistema visual humano,
relacionando-as com os aspectos fundamentais da compressão de imagens. Constrói-se em
seguida um modelo de seu funcionamento.
Do ponto de vista funcional [KIK85], o olho é um órgão de forma aproximadamente
esférica, com cerca de 2 cm de diâmetro, que captura a luz do meio externo e a focaliza em
sua superfície posterior. Na interface com o meio externo, à frente do olho, encontra-se a
córnea, uma membrana transparente e rígida. A principal função da córnea é refratar a luz
incidente, como uma lente convexa. A córnea é responsável por 2/3 do desvio total da luz,
para uma correta focalização.
Atrás da córnea encontra-se a íris. Controlando o tamanho da pupila, orifício no seu centro,
a íris altera a quantidade de luz que penetra no olho. Seu diâmetro pode variar de 2 a 9 mm.
Esta abertura pode ser modelada como um filtro bidimensional passa-baixas, sendo a
freqüência de corte mais alta correspondente à menor abertura. Aumentos contínuos no
tamanho da pupila implicam em redução da freqüência de corte.
Entre a íris e o humor existe um conjunto de fibras transparentes, que constituem a lente do
olho. Com uma forma biconvexa, a lente completa de maneira acurada a focalização da luz.
A forma da lente não é perfeita, o que causa aberração esférica, manifestada como um
ligeiro borramento no plano focal. Tal borramento pode ser modelado como um filtro
passa-baixas.
A retina, superfície na qual se forma a imagem, cobre aproximadamente 65% da parte
interna do olho. Ela é a responsável pela conversão da luz em sinais nervosos. Existem dois
tipos de células receptoras de luz na retina, os cones e os bastonetes. Os cones, cujo número
é de aproximadamente 7 milhões, são menos sensíveis que os bastonetes, detectam cores e
distingüem detalhes em uma imagem. Os bastonetes, que somam aproximadamente 120
milhões, são mais sensíveis à luz que os cones, identificam formas e não percebem cores.
Cones e bastonetes encontram-se distribuídos ao longo da retina de maneira irregular.
Diretamente no foco da retina há uma pequena depressão, a fóvea. Não há bastonetes nesta
região e a maioria dos cones do olho se encontra ali. Isto explica o fato de que uma visão
detalhada só é obtida com a fixação do olhar em um objeto (imagem formada na fóvea).
Depois que os feixes de nervos direito e esquerdo deixam os olhos, eles se encontram em
um ponto chamado quiasma. Cada feixe é subdividido em dois outros, que se misturam
com um feixe do outro olho, formando dois novos feixes. Essa mistura é parcialmente
responsável pela visão estereoscópica. As fibras continuam o seu caminho até o córtex
visual, onde os sinais nervosos são processados.
Lei de Weber-Fechner
Os fotoreceptores são responsáveis pela transformação da luz incidente em sinais elétricos e
pela compressão de sua faixa dinâmica. Esta compressão é realizada, de acordo com a Lei
de Weber-Fechner [KIK85], segundo uma função logarítmica. O seguinte experimento
ilustra a relação:
se um campo visual de luminância L é dividido em duas partes por uma linha reta e a
luminância de uma das partes é aumentada em um ∆L (Figura 2.1), progressivamente, até
que um observador perceba a variação, a razão ∆L/L permanece constante para grandes
variações de L (Figura 2.2).
Figura 2.1 - Experimento de Weber-Fechner.
Figura 2.2 - ∆L/L em função de log(L) [Lim90].
Isto significa que, quando L aumenta, aumenta também o ∆L necessário à percepção da
diferença de luminância das duas áreas. Assim, o sistema visual mantém constante a sua
sensibilidade em relação a uma larga faixa dinâmica de intensidade luminosa (Figura 2.2).
Pode-se escrever:
∆L/L ≅ constante, ou
(2.1)
dL/L = d(log L) ≅ constante
(2.2)
Este experimento explica parcialmente o fato de que a presença de ruído aleatório
uniformemente distribuído é mais visível em regiões escuras da imagem. Para as regiões
mais claras, um nível mais elevado de ruído é necessário para torná-lo igualmente
perceptível.
Efeito Mach Band
Outro efeito que merece ser comentado neste trabalho é o conhecido como mach band
[Lim90]. Considere-se a Figura 2.3. Apesar das intensidades dentro de cada uma das faixas
verticais de cinza serem constantes, apresenta-se ao observador a ilusão de que há um
aumento de intensidade na borda esquerda de cada faixa e uma diminuição da mesma na
borda direita, o que produz um efeito de realce de bordas. Isto sugere que a preservação
precisa das bordas não é necessária na compressão de imagens [Lim90].
Excitação e Inibição
As conexões entre as células das retinas são responsáveis pela chamada inibição lateral
[KIK85], cujo mecanismo é ilustrado na Figura 2.4. Quando uma célula A é excitada,
produz um trem de pulsos, de freqüência diretamente proporcional à intensidade da luz
(Figura 2.4 a). Se outra célula vizinha B é também excitada, esta inibe o trem de pulsos
gerado em A (Figura 2.4 b). A desinibição de A ocorre quando o efeito causado por B é
inibido pela excitação de uma terceira célula, C, nas vizinhanças de B, mas distante o
suficiente de A para não poder agir sobre ela.
Figura 2.3 - Ilustração do efeito mach band
Se a resposta destas células for considerada espacialmente, será obtida a função mostrada
na Figura 2.5. Claramente, este comportamento corresponde a uma filtragem passa-altas.
Células Ganglionares
Define-se como campo receptivo de uma célula, a área da retina que pode influenciar o seu
comportamento, e como excitação mais efetiva aquela que provoca na célula a geração de
um trem de pulsos de máxima freqüência. Devido às ligações entre as células, o campo
receptivo é dividido em dois tipos de regiões, as excitatórias e as inibitórias.
A excitação mais efetiva para uma célula ganglionar é um círculo iluminado, de diâmetro
igual a 0,2 mm, enquanto que o seu campo receptivo também é circular, com áreas
excitatórias no centro e nas bordas, respectivamente. Neste nível do sistema visual, a
informação é processada independentemente da orientação espacial da excitação e também
da intensidade luminosa (áreas circulares), sendo importantes apenas as diferenças dentro
do campo receptivo. Estas células desempenham, evidentemente, importante papel na
detecção de contraste e de bordas, o que pode ser modelado como uma filtragem
bidimensional passa-altas.
Figura 2.4 - Inibição lateral, a) ativação, b) inibição, c) desinibição [KIK85].
Figura 2.5 - Resposta espacial das células da retina [KIK85].
Córtex Visual
Localizado na parte posterior do cérebro, o córtex visual é uma camada de 2 mm de
espessura, formada por poucos tipos de células nervosas.
As células do tipo simples possuem campo receptivo elíptico, com o centro em forma de
barra, circundado por duas regiões opostas, excitatória e inibitória. A excitação mais efetiva
é uma faixa orientada na mesma direção que a barra central do campo receptivo. Neste
nível, o sistema visual humano processa orientações específicas. Para uma orientação fixa,
se a excitação é rotacionada no campo receptivo, o trem de pulsos varia senoidalmente. É
interessante notar-se a similaridade entre este fenômeno e as várias máscaras usadas na
detecção de bordas e linhas por operadores locais, como Roberts, Sobel, Kirsh, etc.,
[Lim90].
As células do tipo complexo também são sensíveis a orientação da excitação, porém, não é
importante a posição da excitação no campo receptivo. A excitação mais efetiva para as
células do tipo hipercomplexo também exige uma orientação específica, mas, além disso,
requer uma descontinuidade, tal como a interrupção de uma linha, ou a existência de um
vértice.
Modelo para o Sistema Visual Humano
Todas as propriedades descritas nessa seção podem ser sumarizadas pelo diagrama da
Figura 2.6. São caracterizadas as diversas etapas do processamento realizado pelo sistema
visual humano nos sinais visuais que recebe.
O primeiro bloco representa uma filtragem espacial isotrópica passa-baixas, representando
a aberração da lente, o efeito da dilatação da pupila e a limitação da freqüência induzida
pelo número finito de fotoreceptores. É seguido pelo comportamento não linear dos
fotoreceptores, representado por uma curva logarítmica simples. No nível da retina, esta
transformação não linear é seguida por uma filtragem isotrópica passa-altas, correspondente
à inibição lateral. Finalmente, um banco de filtros direcionais atua sobre os estímulos, ao
nível das células do córtex.
Figura 2.6 - Modelo do sistema visual humano [KIK85].
2.2 Compressão de Imagens
O processo de compressão de imagens [GW87] pode ser modelado por uma seqüência de
três operações, como ilustra a Figura 2.7. O mapeamento transforma os dados de entrada
(imagem original) do domínio dos níveis de cinza, para outro domínio específico, onde a
quantização e a codificação poderão ser mais eficientemente aplicadas. Na quantização,
cada dado mapeado é restrito a um conjunto finito de valores possíveis, para que uma
quantidade menor de bits possa representá-lo. Finalmente, na codificação, uma palavra é
associada a cada saída quantizada.
Mapeamento
Tranforma o conjunto de números que representa os níveis de cinza em um outro conjunto
de números.
Em uma das técnicas de compressão de imagens, por exemplo, a seqüência de pixels da
imagem f(m1,n1), f(m1,n2), . . . , f(mM,nN) é mapeada em uma seqüência de pares (g1,l1), (g2,l2)
,. . ., (gk,lk), onde g representa o nível de cinza e l o tamanho da i-ésima seqüência (Figura
2.8). Este mapeamento é do tipo reversível, dado que a seqüência de pixels original pode
ser reconstruída de maneira exata, a partir dos dados mapeados.
Figura 2.7 - Modelo da compressão de imagens [GW87].
Figura 2.8 - Mapeamento da codificação seqüencial [GW87].
Um outro exemplo de mapeamento é a transformação linear ilustrada na Figura 2.9, que
pode ser expressa pela relação:
Y = AX.
(2.3)
A transformação pode ser ou não reversível, dependendo da matriz A utilizada. Neste caso,
a matriz de pixels X, com x1 = f(m1,n1), x2 = f(m1,n2),. . ., xT = f(mM,nN),é transformada na
matriz de coeficientes Y. Particularmente, se os elementos x1 , x2 , . . ., xT são altamente
correlacionados, a matriz A é escolhida de forma que os coeficientes y1 , y2, . . ., yT sejam
menos correlacionados, para que se possa codificá-los mais eficientemente.
yO
L
M
y P
M
P
M
.P
M
P
.P
M
M
.P
M
Ny P
Q
21
2
T
a
L
M
a
M
M
.
M
.
M
M
.
M
Na
11
1
=
T1
Figura 2.9 -Mapeamento por transformação linear.
O mapeamento por diferença será obtido se for usada a matriz:
a 12
a 22
.
.
.
aT 2
.
.
.
.
.
.
.
.
.
.
.
.
. a 1n
. a 2n
. .
. .
. .
. aTT
xO
O
L
M
P
x P
M
P
P
M
P
.P
M
P
P
.P
M
P
M
P
.P
M
P
Q Nx P
Q
1
2
T
1
L
M
1
M
M
0
M
.
M
M
.
M
.
M
M
0
M
M
N0
0 0
.
−1 0
.
1 −1 0
0 1 −1
.
.
.
.
.
.
.
.
.
.
.
.
. .
0
. .
0
. .
0
. .
0
. .
.
. .
.
. −1 1
. 0 −1
0
0
0
0
.
.
0
1
O
P
P
P
P
P
P
P
P
P
P
P
Q
na Equação 2.3.
O primeiro elemento de Y é y1 = x1. Entretanto, todos os outros coeficientes são obtidos por:
yi = xi -1 - xi
.
(2.4)
Se os níveis de pixels adjacentes da imagem são próximos, então, na média, as diferenças yi
serão de menor amplitude, requerendo menos bits na sua codificação. O mapeamento por
diferença é também reversível.
Quantização
Considere-se o número de valores possíveis para cada coeficiente yi resultante da
transformação linear representada por (2.3). Cada coeficiente é uma combinação linear de n
pixels, isto é:
yi = ai1 x1 + ai2 x2 + . . . + aiT xT .
(2.5)
L
Se cada elemento xj no somatório acima pode assumir 2 diferentes valores, então, cada
L
LT
termo aij xj também assumirá 2 valores. Conseqüentemente, yi assumirá 2 diferentes
valores, resultando na necessidade de B = L.T bits para sua representação. Esta conclusão
indica que se deve reduzir a quantidade B de bits, para que se possa efetivamente
comprimir a imagem. A solução é a restrição do domínio de yi.
A quantização é um processo, cuja saída só pode apresentar um número limitado de valores
possíveis. Uma das maneiras de se obter a quantização de um determinado conjunto de
valores é dividir-se a entrada em um certo número de intervalos, como ilustrado na Figura
2.10.
Se um valor de entrada se encontra dentro do k-ésimo intervalo, o valor de saída
corresponde ao valor representativo daquele intervalo (por exemplo, seu ponto médio). A
quantização uniforme é aquela na qual todos os intervalos são iguais, enquanto que na
quantização não uniforme, os tamanhos dos intervalos diferem entre si.
A quantização é uma operação irreversível, porque, dado um certo valor de saída, o valor
de entrada que o originou não pode ser exatamente determinado.
Figura 2.10 - Quantização: relação entre entrada e saída.
Para alguns tipos de mapeamento, melhores resultados podem ser obtidos com o uso de
diferentes esquemas de quantizacão, de acordo com a natureza dos coeficientes. Assim,
para um conjunto de coeficientes de maior variância, um maior número de intervalos
poderia ser definido.
Quantização de Lloyd-Max
Seja V [Lim90] um valor escalar a se quantizar, L o total de níveis de reconstrução usados
na sua representação e Vq o resultado da quantização, de maneira que:
Vq = Q(V) = ri,
di-1 < V ≤ di,
(2.6)
onde Q representa a operação de quantização, ri (para 0 ≤ i ≤ L) os níveis de reconstrução e
di (0 ≤ i ≤ L) os L+1 limites de decisão.
Vq pode ser expresso como:
Vq = Q(V) = V + eq,
(2.7)
2
onde a grandeza e q pode ser vista como uma medida de distorção d(V , Vq). Os níveis de
reconstrução e limites de decisão podem ser determinados pela minimização de uma função
apoiada em d(V , Vq), como a distorção média D, dada por:
di
D = E[d(V , Vq)] =
z
d(V0 , Vq) pf(V0) dV0 .
V 0 = di − 1
(2.8)
Para um quantizador uniforme, tem-se:
∆
di - di-1 =
1≤i≤L e
(2.9)
1≤ i≤ L,
ri = (di + di-1)/2
(2.10)
onde ∆ é igual ao intervalo entre dois níveis de reconstrução consecutivos.
No caso da quantização não uniforme, a determinação de ri e di é freqüentemente baseada
no critério do mínimo erro médio quadrático (MMSE - Minimum Mean Square Error)
(quantização de Lloyd-Max). Assumindo-se V como uma variável aleatória com função
densidade de probabilidade pf(V0), e usando-se o critério MMSE, determinam-se rk e dk pela
minimização da distorção média:
2
2
D = E[d(V , Vq)] = E[e q] = E[(Vq - V0) ]
(2.11)
∞
z
2
pf(V0) (Vq - V0) dV0 .
=
V 0 =−∞
(2.12)
Sendo V0 um dos L valores de reconstrução, tem-se:
L
D=
∑
i =1
di
z
2
pf(V0) (ri - V0) dV0 .
V 0 = di − 1
(2.13)
Para a minimização de D, pode-se provar [Lim90] que:
dk
z
z
1 ≤ i ≤ L
rk + rk + 1
2
1≤ i≤ L-
V 0 pV d
V 0 idV 0
rk =
V 0 = dk − 1
dk
pV d
V 0 idV 0
V 0 = dk − 1
(2.14)
dk =
1
d0 = - ∞
dL = ∞
As expressões acima afirmam que o nível de reconstrução rk é o centróide de pf(V0) no
intervalo dk ≤ 0 ≤ dk-1 e que o nível de decisão dk (exceto para k=0 e k=L) é o ponto médio
entre os níveis de reconstrução rk e rk+1 . O problema representado pelas Equações 2.14 foi
solucionado para algumas funções densidade de probabilidade, como a gaussiana. A Tabela
2.1 apresenta os valores rk e dk para esta distribuição, com quantização em 2 bits.
rk
dk
-1,5104
-0,4528
0,4528
1,5104
-0,9816
0
0,9816
∞
∞
Tabela 2.1 - Limites de intervalos e valores representativos para quantização em 4 níveis, para a distribuição
gaussiana, média igual a zero e variância igual a um [Lim90].
Codificação
Define-se uma palavra como um conjunto de bits ao qual se atribui um significado único. O
termo código representa um conjunto de palavras que é associado a um conjunto de valores.
A entrada da codificação é representada pelos T elementos do vetor v da Figura 2.7.
Supondo-se que cada elemento vi possa assumir um entre s valores (w1, w2,. . .,ws), a
codificação define para cada vi uma palavra binária ci, que estabelece uma correspondência
biunívoca com o valor assumido, wi . O processo é portanto reversível, dado que para uma
palavra ci , o valor wi pode ser exatamente determinado.
Um código de tamanho fixo é um conjunto de palavras que possuem o mesmo número de
bits. Um código unicamente decodificável é aquele do qual qualquer combinação de
palavras só pode ser decodificada de uma maneira, sem ambigüidades. Assim, o código
composto pelas palavras c1 = "0", c2 = "1", c3 = "01", c4 = "10" não é unicamente
decodificável, porque, a seqüência de bits "0011" poderia ser interpretada como a seqüência
das palavras c1c1c2 c2, ou c1c3c2 .
Um código instantâneo é aquele que pode ser imediatamente decodificável, ou seja, uma
vez lido o último bit de uma palavra, esta é reconhecida, sem que o valor dos bits que ainda
não foram lidos interfiram na sua interpretação. A Tabela 2.2 ilustra três tipos de códigos
usados para a representação de oito valores possíveis.
Entrada
Natural
Huffman
S2
w1
w2
w3
w4
w5
w6
w7
w8
"000"
"001"
"010"
"011"
"100"
"101"
"110"
"111"
"1"
"00"
"011"
"01010"
"01011"
"010010"
"010011"
"010001"
"00"
"01"
"10"
"1100"
"1101"
"1110"
"111100"
"111101"
Tabela 2.2 - Códigos típicos [GW87].
É desejável a determinação de um código com o menor número de bits possível. Uma vez
S
que podem ser definidas 2 palavras de mesmo tamanho b = log2 S bits, o código natural
S
com b bits pode representar até 2 valores de entrada. Este código é ótimo quando os
valores de entrada são equiprováveis, ou seja:
P(w1) = P(w2) = . . . = P(wS).
(2.15)
Para os casos em que as probabilidades diferem a cada wi , utilizam-se palavras de tamanho
variável, atribuindo às menores os valores mais prováveis, o que implicará numa redução
do número de bits gerado pela codificação.
Entropia
O termo entropia representa o grau de aleatoriedade de um conjunto de variáveis aleatórias
[GW87]. Supondo-se a existência de um conjunto de S variáveis aleatórias a1, a2 , . . . , aS ,
com probabilidades P(a1) ,P(a2) , . . . ,P(aS) , a entropia é definida como:
S
H=-
∑
k =1
(2.16)
Pk log2 Pk (bits)
Em geral, para o conjunto, o valor da entropia varia entre 0 e log2 S. No caso da
compressão de imagens, representa a quantidade de informação associada ao conjunto de
valores de entrada do sinal, definindo um limite inferior para o número médio de bits
necessário à codificação do mesmo. Portanto, o conjunto de variáveis aleatórias w1, w2,. .
.,wS, que representa os níveis de cinza de uma imagem digital, com probabilidades P1, P2, . .
. , PS , não pode ser codificado com o uso de menos que H bits/pixel, em média.
Isto significa que a entropia pode ser usada como critério de avaliação de desempenho de
um código particular. Se um código formado pelo conjunto de palavras c1, c2,. . ., cS de
comprimentos β1 , β2 ,. . ., βS , o número médio de bits requerido na codificação será:
S
R=
∑
βk Pk
k =1
(2.17)
Se o valor de R é próximo do valor de H, a codificação está próxima do ótimo.
O termo razão de compressão (Rc) define a relação entre o número de bits da imagem
original e o número de bits da imagem comprimida. Para imagens a 8 bits/pixel, tem-se:
Rc = (8 bits/pixel) / Hc,
onde Hc é a entropia efetiva da imagem comprimida, em bits/pixel.
Códigos de Huffman
Um método para geração de códigos ótimos unicamente decodificáveis, que resulta em taxa
média mínima de bits, é o chamado método de Huffman [Lim90].
O algoritmo consiste na determinação dos valores de P1, P2, . . . , PS, seleção sucessiva do
par de valores de menor magnitude, aglutinação dos mesmos e associação do novo valor
gerado a um caminho dentro de uma árvore binária. Ao final do processo, os caminhos
definidos da raiz até cada uma das folhas determinarão os códigos para os valores w1, w2,. .
.,wS. A Figura 2.11 ilustra a geração de código de Huffman para um universo de S = 6
valores possíveis.
O algoritmo descrito acima gera palavras de tamanho variável, associando claramente aos
valores mais prováveis, palavras de menor comprimento. Para os valores da Figura 2.11,
podem-se calcular:
H=
-1 * [(0,4 * log 0,4) + (0,3 * log 0,3) + (0,1 * log 0,1) +
+ (0,1 * 0,1) + (0,06 * log 0,06) + (0,04 * log 0,04)] =
R=
2,14 bits
1 * 0,4 + 2 * 0,3 + 3 * 0,1 + 4 * 0,1 + 5 * 0,06 + 5 * 0,04 =
2,20 bits
Níveis
Pk
Passo 1
Passo 2
Passo 3
Passo 4
Passo 5
ck
w1
w2
w3
w4
w5
0,4
0,3
0,1
0,1
0,06
0,4
0,3
0,1
0,1
0,1
0,4
0,3
0,1
0,2
0,4
0,3
0,3
0,4
0,6
1,0
w6
0,04
"0"
"11"
"100"
"1011"
"10101
"
"10100
"
Figura 2.11 - Construção do código de Huffman.
Código de Lempel-Ziv
O esquema de codificação proposto por Lempel e Ziv [ZL78], ao contrário do código de
Huffman, não necessita do conhecimento prévio da tabela de palavras e não gera palavras
de tamanhos diferentes para valores com diferentes probabilidades. O processo de
codificação se inicia com uma tabela contendo tantas palavras quantos forem os valores
possíveis, sendo estas palavras de tamanho fixo, ou variável. Na medida em que o processo
de codificação avança, novas palavras são adicionadas ao código, adaptativamente.
Por exemplo, para 4 possíveis valores, a,b,c, e d, a tabela inicial seria:
a:
b:
c:
d:
"00"
"01"
"10"
"11".
Considerando-se a seqüência a ser codificada abab, o algoritmo procura, a partir da posição
corrente, o maior padrão reconhecível dentro da seqüência. Assim, num primeiro passo, o
maior padrão reconhecido seria a, surgindo um padrão novo, ab. Para este último é criada
uma nova entrada na tabela, que passa a ser a seguinte:
a:
b:
c:
d:
ab:
"000"
"001"
"010"
"011"
"100".
Neste momento, o valor "000" é armazenado (ou transmitido), indicando o primeiro padrão
processado. No próximo passo, a partir do segundo elemento da seqüência, procura-se
novamente pelo maior padrão reconhecido, neste caso, b. Uma nova palavra é criada para
ba, e é armazenado o valor de b:
a:
b:
c:
d:
ab:
ba:
"000"
"001"
"010"
"011"
"100"
"101".
Na decodificação, tendo sido recebidas as palavras correspondentes a a e b, gera-se também
o valor do padrão ab. Em um terceiro passo, o padrão ab já é reconhecido. Aqui é possível
a primeira compressão, substituindo as duas palavras de 2 bits inicialmente necessárias para
a codificação de ab por uma palavra de 3 bits.
A codificação Lempel-Ziv é usada em alguns formatos de imagens digitais, como o GIF
(Graphics Interchange Format) e TIFF (Tag Image File Format) [KL92].
Medidas de Distorção
As técnicas normalmente utilizadas em compressão de imagens resultam em um certo grau
de degradação da imagem original. O erro médio quadrático (MSE - Mean Square Error) é
um critério amplamente usado na aferição da fidelidade da imagem reconstruída, sendo
definido para uma imagem M x N como [Jain81]:
N
MSE = 1/(NM)
M
∑∑
2
E(ui,j - u'i,j) ,
i =1 j =1
(2.18)
onde ui,j e u'i,j representam os pixels da imagem original e reconstruída, respectivamente e E,
a função esperança matemática. Experimentalmente, o MSE é estimado pelo MSE
amostral:
N
MSE = 1/(NM)
M
∑∑
2
(ui,j - u'i,j) .
i =1 j =1
(2.19)
Opcionalmente, pode-se usar o erro médio absoluto (MAE - Mean Absolute Error),
definico como:
N
MAE = 1/(NM)
M
∑∑
|ui,j - u'i,j|.
i =1 j =1
(2.20)
Há duas definições para a razão sinal/ruído (SNR - Signal to Noise Ratio) correspondente
ao erro descrito acima:
2
PSNR = 10 log10 [(valor de pico da imagem original) / MSE]
(dB)
(2.21)
2
SNR = 10 log10 (σu / MSE)
(2.22)
(dB),
2
onde σu é a variância da imagem original. Tipicamente, o valor de pico usado no cálculo de
PSNR é igual a 255 (imagens de 8 bits/pixel).
Imagens Gráficas
Este trabalho se referirá em diversas seções ao termo imagem gráfica. Mitchell [MD80]
define a imagem gráfica como a imagem de cena gerada artificialmente, usando-se número
limitado de níveis de cinza arranjados segundo um determinado padrão, para conter
informações. Incluem esta categoria as imagens não naturais, como as de documentos,
mapas, telas de computador, desenhos, etc.
2.3 Classificação das Técnicas
As técnicas de compressão de imagens podem ser classificadas segundo diversos aspectos.
Quanto à preservação da informação [RJ91]: os níveis de qualidade e
inteligibilidade toleráveis na imagem reconstruída variam amplamente, de acordo com a
aplicação. Em alguns casos, é desejável que a imagem original seja preservada na sua
totalidade. As técnicas de codificação utilizadas com esta restrição são as chamadas
preservadoras de informação. Em outras situações, admite-se que a imagem sofra um
determinado grau de degradação, de forma que mais elevados índices de compressão sejam
atingidos. Tais técnicas são conhecidas como não preservadoras de informação.
•
Quanto ao domínio [Prat78]: os métodos que combinam espacialmente valores de
pixels de uma maneira definida são chamados métodos do domínio espacial. Aqueles que
utilizam, ao invés disso, um conjunto de coeficientes de transformada, são os métodos do
•
domínio das transformadas. Os métodos híbridos processam as imagens em ambos os
domínios.
Quanto à sua fundamentação [KIK85]: dois aspectos tornam possível a
compressão de imagens. Em primeiro lugar, os dados originados de uma imagem não são
aleatórios. Amostras adjacentes possuem níveis de cinza próximos, exibindo portanto uma
•
Figura 2.12 - Evolução da razão de compressão média das técnicas de primeira geração [KIK85].
Figura 2.13 - Razão de compressão média das técnicas de primeira e segunda gerações [KIK85].
correlação espacial importante. Se tal correlação for adequadamente explorada, a
quantidade de bits necessária à representação da imagem pode ser reduzida. As chamadas
técnicas de primeira geração são aquelas baseadas nessa visão clássica do problema da
compressão de imagens. Em segundo lugar, a grande maioria dos sistemas de
processamento de imagens tem como usuário final o olho humano. O mecanismo de
percepção visual do cérebro, mais recentemente estudado, apresenta determinadas
particularidades (como a sensibilidade direcional dos neurônios do córtex visual) que são
exploradas pelas técnicas de segunda geração. A Figura 2.12 ilustra a evolução das razões
de compressão obtidas pelas técnicas de primeira geração, indicando que foi atingido um
patamar de saturação em torno de 10:1. A Figura 2.13 mostra a mesma evolução, levandose em conta o surgimento das técnicas de segunda geração.
Quanto aos parâmetros de codificação [KIK85]: os parâmetros de codificação
podem ser fixos durante todo o processamento, ou podem ser adaptativos, variando dentro
da imagem de acordo com as suas características locais.
•
2.4 Conclusão
Neste capítulo, foram apresentados os conceitos envolvidos com a compressão de imagens,
e a descrição do funcionamento do sistema visual humano. O modelo ilustrado na Figura
2.6 mostra que o mecanismo de percepção dos sinais visuais apresenta propriedades que
podem ser exploradas pelos algoritmos de compressão de imagens. O componente que
introduz uma filtragem passa-baixas, em função da aberração esférica e da imperfeição da
lente do olho, provoca um borramento da imagem original e permite o descarte de uma
determinada informação de bordas e ruídos. O caráter logarítmico da percepção relativa de
luminância, representado pelo segundo elemento do modelo, ilustra como as regiões de alta
freqüência são mascaradas de acordo com a luminância de fundo, enquanto que a resposta
espacial das células da retina indica uma faixa de freqüência de percepção preferencial
(terceiro elemento do modelo). Finalmente, a especialização das células do córtex visual
revela a presença de diferentes padrões de sensibilização das mesmas, incluindo formas e
direções definidas para cada tipo de célula, o que sugere a decomposição das imagens em
componentes direcionais e a codificação destes em separado.
A abordagem da teoria de compressão de imagens procurou definir o processo, dividindo-o
nas etapas de mapeamento, quantização e codificação. A análise de tais etapas indica com
clareza os pontos onde ocorre a redução da entropia da imagem e, em alguns casos, a perda
de qualidade da mesma em relação à original. Foi apresentada a quantização de Lloyd-Max,
utilizada neste trabalho, bem como os algoritmos de geração de códigos de Huffman e
Lempel-Ziv. Os parâmetros de medida de distorção foram definidos também neste capítulo.
Nos capítulos seguintes, são discutidos em detalhe os principais algoritmos, sua
implementação e é feita a análise dos resultados obtidos na compressão das imagens de
documentos históricos.
3. ALGORITMOS
Neste capítulo, são descritas as principais técnicas de compressão de imagens
desenvolvidas até hoje: Run Length Coding e Modified Relative Element Address Designate
Coding (ambas aplicáveis a imagens binárias), Pulse Code Modulation, Differential Pulse
Code Modulation, Block Truncation, Pyramid Coding, Transform Coding e Vector
Quantization (aplicáveis a imagens com múltiplos níveis de cinza). Além destas, cita três
das chamadas técnicas de segunda geração: codificação de contorno-textura, decomposição
direcional e codificação de bordas.
Para cada uma das técnicas, são apresentados os algoritmos de compressão e
descompressão de maneira estruturada. Quando conveniente, são discutidos aspectos
matemáticos e estatísticos relacionados às operações de quantização e codificação. São
ainda definidas algumas variações que visam à melhor adequação dos algoritmos a uma
determinada aplicação ou à melhoria de seu desempenho. Também são apresentadas
algumas tabelas de parâmetros, que complementam a definição dos algoritmos.
Finalmente, apresentam-se os formatos de imagens BM e JPEG, sendo o primeiro o
adotado nas implementações e servindo o segundo como padrão de comparação na
posterior análise dos resultados.
Procura-se neste capítulo, não só a complementação da revisão bibliográfica iniciada no
capítulo anterior, como também o estabelecimento de um paralelo entre os diversos
algoritmos implementados, analisando-se os níveis de compressão que cada um deles pode
atingir, assim como a distorção causada nas imagens.
3.1 RLC - Run Length Coding (Codificação Seqüencial)
Um dos primeiros algoritmos de compressão de imagens [JN84] [Jain89]‚ um método
muito aplicado para imagens binárias, embora também possa ser utilizado na codificação de
imagens com múltiplos níveis de cinza.
Trata-se de uma técnica preservadora de informação, de fácil implementação, que gera
imagens binárias com entropia de até 1 bit/pixel, dependendo das características da
imagem.
Descrição do Método
Baseando-se no fato de que as imagens binárias são constituídas de seqüências alternadas
de pixels brancos e pretos, ao invés de se codificarem os pixels individualmente, codificamse as quantidades de pixels brancos (ou pretos) dentro de cada seqüência. Como as
seqüências de brancos e pretos se alternam, não é necessária a codificação do nível.
A codificação seqüencial faz, invariavelmente, uso de palavras de tamanho variável, visto
que, em geral, seqüências grandes de um nível são menos freqüentes que as seqüências
menores. Uma vez que não há quantização, a imagem pode ser restaurada com exatidão, a
menos que ocorram erros na transmissão ou armazenamento. A codificação é feita linha a
linha.
Para simplificação, assume-se que todas as linhas sejam iniciadas por uma seqüência de
brancos (0 brancos, se a linha começar com um pixel preto). A cada final de linha, uma
palavra especial é adicionada ao código.
Algoritmo de Compressão
início
para cada linha da imagem faça
palavra resultante = '' "
nível = 0 (branco)
repita
R = número de ocorrências de pixels subseqüentes e adjacentes iguais a
nível
consultar na tabela de código a palavra correspondente a R
concatenar a palavra obtida à palavra resultante
se nível = 0
então nível = 1
senão nível = 0
fim se
até final da linha
concatenar palavra correspondente ao fim de linha à palavra resultante
armazenar a palavra resultante gerada para a linha
fim para
armazenar palavra correspondente ao fim de imagem
fim.
Algoritmo de Descompressão
início
palavra = '' "
nível = 0
repita
ler próximo bit da imagem codificada
concatenar bit lido com palavra
se palavra existente
então determinar R correspondente
palavra = '' "
se (não é final de linha) e (não é final de imagem)
então gerar seqüência de R bytes com valor igual a
nível
se nível = 0
então nível = 1
senão nível = 0
fim se
senão se não é final de imagem
então nível = 0
fim se
fim se
fim se
até = final de imagem
fim.
Código Modificado de Huffman
O CCITT (International Telegraph and Telephone Consultative Committee) definiu uma
variação do algoritmo de Huffman [HR80], descrito no capítulo anterior, permitindo que
seqüências maiores pudessem ser codificadas, sem que isso acarretasse um aumento
exagerado no tamanho das palavras.
O Apêndice A apresenta o código modificado de Huffman, para um alfabeto de no máximo
R = 1728 pixels em seqüência. O sistema de codificação define a seqüência R como a soma
de dois termos, cujas palavras representativas são concatenadas para geração da palavra
final. O primeiro dos termos é igual ao quociente da divisão inteira de R por 64 e o
segundo, igual ao resto desta mesma divisão:
R = 64p + q
(p = 0,1,2,...,27)
(q = 0,1,2,...,63)
(3.1)
As palavras terminais no Apêndice A representam o valor de q e as palavras mais
significativas representam o valor de 64 p.
Sinais de uma fonte binária podem ser codificados com H(x) bits/símbolo, ao invés de 1
bit/símbolo, onde H(x) é a entropia da fonte. A redundância da fonte binária é portanto, 1 H(x). No caso de fontes com H(x) << 1, uma importante grandeza é o ganho máximo de
codificação seqüencial, ou máxima compressão, max Grlc, definido como:
max Grlc = 1 / H(x).
(3.2)
A Figura 3.1a ilustra o modelo markoviano de primeira ordem usado no estudo das fontes
binárias. Os estados possíveis são B e W, com as correspondentes probabilidades de
transição tw, tb :
tw = p { X(n) = B / X(n-1) = W }
(3.3)
tb = p { X(n) = W / X(n-1) = B }.
(3.4)
As probabilidades de estado P(W) = P { X(n) = W } e P(B) = P { X(n) = B } são
determinadas por :
P(W) = 1 - P(B) = tb / ( tw + tb)
(3.5)
P(B) = tw / ( tw + tb)
(3.6)
Figura 3.1 - Modelo markoviano para representação de sinais binários [JN84].
Note-se que as probabilidades de estado somam 1 por definição, enquanto que as
probabilidades de transição não estão sujeitas a esta restrição. Assim, para sinais
caracterizados por longas cadeias de brancos e pretos, (Figura 3.1b) :
tw << 1, tb << 1, tw + tb << 1,
(3.7)
enquanto que no outro extremo, se tb = tw = 1, a seqüência máxima é de 1 (Figura 3.1c).
A probabilidade de uma cadeia de Rk pixels no estado S [JN84]:
P(Rk / S) = ts(1-ts) Rk-1 ;
(Rk = 1,2,....,) (S = B,W,. . .)
(3.8)
onde o termo da direita representa a probabilidade de (Rk-1) transições para o mesmo
estado, seguida por uma transição para o estado oposto, o que encerra a seqüência.
Assumindo-se 3.7, a esperança matemática de um valor R, condicionado a um estado S ‚
dada por :
E [R/S] = 1 / ts;
S = B,W.
(3.9)
Reescrevendo-se 3.8,
P(Rk/S) = (E [R/S] - 1) -1 [ 1 - ( E [R/S] ) -1 ] Rk
(3.10)
A última equação implica em uma distribuição geométrica, ou exponencial discreta, para a
seqüência R.
Variações do Método
A principal variação proposta para codificação seqüencial de imagens binárias [Yasu80] é a
utilização de algoritmos para processamento bidimensional, nos quais também a correlação
vertical é explorada. São exemplos desses algoritmos, os chamados RAC (Relative Address
Coding), EDIC (Edge Difference Coding) e READ (Relative Element Address Designate
Coding) [Yasu80].
3.2 MREAD - Modified Relative Element Address Designate Coding
Dos mais eficientes algoritmos para compressão, sem perda de informação, de imagens
binárias. Recomendado pela CCITT [Jain89], MREAD é um método de codificação
bidimensional linha a linha [HR80], [Yasu80], no qual a posição de cada elemento de
transição na linha atual é codificada em relação a um outro pixel de transição localizado na
linha imediatamente anterior, ou na própria linha a ser codificada.
Proporciona razões de compressão acima das obtidas pela compressão seqüencial [HR80],
sendo também de fácil implementação.
Descrição do Método
O algoritmo se baseia na definição de pixels de referência durante a codificação das
seqüências de brancos e pretos, em relação aos quais será examinada a posição do próximo
pixel de transição a ser codificado. Um pixel de transição é aquele cujo nível difere do nível
do pixel imediatamente anterior, na mesma linha. A técnica faz uso de 5 pixels de transição
de referência, definidos como na Figura 3.2:
•
•
•
•
•
a0 : elemento inicial de transição da linha a ser codificada, definido pelo modo anterior
de codificação usado (discutido mais adiante). No início da codificação de uma linha‚
assumido como um pixel imaginário situado imediatamente à esquerda do primeiro
elemento da linha.
a1 : o próximo elemento de transição à direita de a0 (possui nível oposto ao de a0).
a2 : o próximo elemento de transição à direita de a1.
b1 : o próximo elemento de transição à direita de a0 mas, na linha anterior à codificada,
ou linha de referência.
b2 : próximo elemento de transição à direita de b1.
Se algum dos elementos de referência citados acima não existir, é assumido como estando
em uma posição imaginária, imediatamente à direita do último pixel da linha em questão.
Para a codificação, dependendo da posição relativa entre os pixels de referência, um dos
seguintes modos é ativado:
•
•
•
modo de passagem : ocorre quando b2 está à esquerda de a1 (Figura 3.2a). Após a
codificação, o pixel a0 é locado no elemento da linha de codificação, imediatamente
abaixo de b2.
modo horizontal : quando o modo de passagem não ocorre, sendo |a1b1| > 3. Neste
caso, as distâncias a0a1 e a1a2 são codificadas pelo código modificado de Huffman
(Apêndice A). Depois da codificação, a nova posição de a0 é ajustada para a2. Se o
modo está ativo para o primeiro pixel da linha de codificação, o valor (a0a1 - 1) é
codificado, ao invés de a0a1.
modo vertical : a1 é codificado relativamente a b1, pela distância a1b1, com os valores
0,1,2 e 3, à direita ou à esquerda de b1, sendo codificados conforme a Tabela 3.1. O
novo valor de a0 é setado para a1.
Observe-se que a primeira linha da imagem, por não possuir linha de referência, é
codificada pelo algoritmo RLC.
Modo
Elementos a codificar
Palavra
Passagem
Horizontal
Vertical
b1,b2
a0a1,a1a2
a1 sob b1
a1 à direita de b1
"0001"
"001"+M(a0a1)+M(a1a2)
"1"
"011"
"000011"
"0000011"
"010"
"000010"
"0000010"
a1 à esquerda de b1
a1b1=0
a1b1=1
a1b1=2
a1b1=3
a1b1=1
a1b1=2
a1b1=3
Tabela 3.1 - CCITT-READ modificado: tabela de códigos. M(a0a1) e M(a1a2) são palavras provenientes do
código modificado de Huffman (Apêndice A) [Jain89].
Algoritmo de Compressão
início
codificar primeira linha por RLC
para cada uma das outras linhas da imagem, na ordem em que ocorrem, faça
palavra resultante = '' "
repita
definir a0, a1, a2, b1, b2
se b2 < a1
então definir palavra pelo modo de passagem
a0 = b2
senão se |a1b1| < 3
então definir palavra pelo modo vertical
a0 = a1
senão se a0 = 0
entao a0a1 = a0a1 - 1
fim se
definir palavra pelo modo horizontal
a0 = a2
fim se
fim se
concatenar palavra à palavra resultante
concatenar palavra de fim de linha à palavra resultante
enquanto não fim de linha
armazenar palavra resultante
fim para
fim.
Algoritmo de Descompressão
início
decodificar primeira linha por RLC
repita
repita
identificar modo
definir novas posições dos pixels de referência
gerar seqüências de pixels
até fim de linha
até fim de imagem
fim.
Variações do Método
No caso da codificação MREAD aplicada à transmissão de imagens, recomenda-se
[Yasu80] que a cada k linhas seja codificada uma linha pelo algoritmo unidimensional
RLC. Isto reduzirá ligeiramente a razão de compressão obtida, eliminando entretanto, a
propagação de erros de transmissão.
Um quarto modo é ainda sugerido [Yasu80] para imagens que possuam muitas áreas com
seqüências de poucos pixels de mesmo nível (por exemplo, áreas de dithering). Trata-se do
modo descomprimido, no qual os pixels não são codificados.
3.3 BTC - Block Truncation Coding (Truncagem de Blocos)
Este algoritmo foi originalmente proposto por Mitchell [DM79], [MD80] para compressão
de imagens digitais com múltiplos níveis de cinza. Apresenta baixa sensibilidade a erros e é
de fácil implementação. Trata-se de uma técnica não preservadora de informação e, na sua
versão básica, gera imagens com entropia de 1 a 2 bits/pixel. É recomendado para
compressão de imagens gráficas.
Descrição do Método
O método consiste na divisão da imagem original em blocos de tamanho n x n mutuamente
exclusivos e exaustivos. Os k = n2 pixels de cada bloco são divididos em dois grupos
conforme apresentem níveis de cinza superiores ou inferiores a um limiar de quantização
calculado. O bloco é armazenado como um plano de bits, juntamente com seus parâmetros
estatísticos, permitindo, na descompressão, que a imagem seja reconstruída.
O brilho, contraste e as características mais perceptíveis da imagem são preservados. Na
ausência de grandes variações de níveis de cinza em um bloco, as pequenas variações são
mantidas. Esta característica é coerente com o sistema visual humano, que tende a mascarar
pequenas variações vizinhas a regiões de altas freqüências (Capítulo 2).
Algoritmo de Compressão
início
dividir a imagem em blocos de tamanho n x n (geralmente n = 4)
para cada bloco obtido faça
palavra resultante = '' "
calcular parâmetros do bloco
calcular limiar
para cada pixel do bloco faça
se valor do pixel < limiar
então concatenar 0 à palavra resultante
senão concatenar 1 à palavra resultante
fim se
fim para
codificar parâmetros do bloco e concatená-los à palavra resultante
armazenar palavra resultante
fim para
fim.
Algoritmo de Descompressão
início
repita
ler próxima palavra
dividir a palavra em 2 partes, referentes ao plano de bits e aos parâmetros do bloco
decodificar plano de bits e parâmetros
calcular níveis de reconstrução do bloco
reconstruir bloco de acordo com o plano de bits e com os níveis de reconstrução
calculados
até último bloco reconstruído
fim.
Figura 3.2 - CCITT - Codificação READ modificado: modos de codificação e pixels de referência [Jain89].
Parâmetros Estatísticos
Os parâmetros estatísticos calculados para cada bloco são a média aritmética (primeiro
momento), que corresponde à informação de brilho e a variância (segundo momento),
correspondente ao contraste. Estes valores, depois de calculados, são quantizados, no caso
mais simples, com 8 bits cada. Na descompressão, bloco é reconstruído com dois níveis de
cinza. Os pixels com valores maiores que o limiar de quantização binária recebem o valor b
e os pixels com valores menores ou iguais ao limiar, o valor a.
O primeiro e o segundo momentos são calculados pelas equações:
χ
χ2
σ
k
=
(1 / k)
∑
i =1
k
=
(1 / k)
∑
i =1
=
Xi
Xi2
(χ2 - (χ)2)1/2,
(3.11)
(3.12)
(3.13)
onde Xi= X1,X2,X3,. . . ,Xk são os valores dos pixels do bloco.
Sendo q o número de pixels com valores maiores que o limiar em um bloco (que
corresponde a uma das ocorrências Xi), os valores de reconstrução a e b são calculados de
modo a se preservar χ e σ :
kχ = (k - q)a + qb
(3.14)
kχ2 = (k - q)a2 + qb2
(3.15)
Resolvendo-se o sistema para a e b, tem-se:
a = χ - σ (q / (k - q))1/2
b = χ + σ ((k - q) / q)1/2
(3.16)
(3.17)
Exemplo de BTC aplicada a dois blocos pode ser visto na Figura 3.3.
Quantização dos Parâmetros
A média e desvio padrão podem ser codificados simultaneamente, dado que a média não é
uma grandeza crítica em uma área de grande variância, mas precisa ser reconstruída com
exatidão em áreas de baixa variância.
A Tabela 3.2 ilustra as combinações de média e desvio padrão sugeridas [MD80] para
imagens com até 16 níveis de cinza. Observe-se que são necessárias 64 palavras diferentes.
Uma alternativa mais simples, que resultaria em menor razão de compressão, seria a
codificação em separado dos valores de χ e σ quantizados a 8 bits cada. Entretanto,
evidências experimentais demonstram que a utilização de 6 bits para χ e 4 para σ introduz
poucos erros perceptíveis na imagem reconstruída.
BLOCOS ORIGINAIS
15
15
15
15
5
5
15
15
5
5
15
15
χ = 9.6
σ = 5.5
4
3
2
4
|
|
|
|
4
3
2
3
4
3
2
3
4
3
3
3
BLOCOS RECONSTRUÍDOS
4
4
3
3
χ = 3.2
σ = 0.6
15
15
15
15
4
4
15
15
4
4
15
15
χ = 10
σ= 6
4
4
4
4
|
|
|
|
4
3
3
3
4
3
3
3
4
3
3
3
4
4
3
3
χ=3
σ=1
Figura 3.3 - Blocos originais reconstruídos por truncagem de blocos. Parâmetros estatísticos originais e
quantizados indicados [MD80].
σ
χ
No. de palavras
0
1
2
3
0 - 15
1 - 14
1,3,5,7,9,11,13,15
2,4,6,8,10,12,14
16
14
8
7
4
5
6
7
2,4,6,8,10,12,14
2,5,8,11,14
3,6,9,12
4,7,10
7
5
4
3
Total 64
Tabela 3.2 - Combinações permitidas para média e desvio padrão a 16 níveis de cinza, codificação BTC
[MD80].
Seleção do Plano de Bits
Na codificação, é necessário que seja definido um limiar de quantização para que possa ser
gerado o plano de bits. O método mais simples considera a própria média como valor do
limiar.
O uso dos parâmetros de fidelidade MSE e MAE também é aplicável na determinação do
limiar, através da minimização das funções [DM79] :
k − q −1
Jmse =
∑
i =1
(Yi - a1)2 +
k − q −1
Jmae =
∑
i =1
k
∑
(Yi - b1)2
i = k −q
e
(3.18)
k
|Yi - a2| +
∑
i = k −q
|Yi - b2|,
(3.19)
onde Y1,Y2,. . .,Yk representam os valores de Xi, em ordem crescente, de modo que:
Y1 <= Y2 <= Yk
e
(3.20)
Yi,
(3.21)
k − q −1
a1 = (1 / (k - q))
∑
i =1
k
∑
Yi,
(3.22)
a2 = mediana de (Y1,Y2,. . .,Yk-q-1),
(3.23)
b2 = mediana de (Yk-q,. . .,Yk).
(3.24)
b1 = (1 / q)
i = k −q
As funções acima podem ser minimizadas pelo cálculo exaustivo dos parâmetros MSE e
MAE, para todos os limiares possíveis, no máximo k-1.
Esta alternativa implica, evidentemente, em um ganho na qualidade da imagem
descomprimida, em detrimento do tempo de processamento necessário durante a
codificação.
Uma terceira alternativa seria a preservação, não só da média e variância, como também do
terceiro momento, χ3, definido como:
χ3 = (1 / k)
k
∑
i =1
Xi3 = (1 / k)
k
∑
i =1
Yi3.
(3.25)
O problema se resume, então, em encontrar os valores de a, b e q, preservando-se χ, χ2 e χ3
(q definirá o limiar, já que especifica o número de Xi maiores que este último):
kχ = (k - q) a + qb
(3.26)
kχ2 = (k - q) a2 + qb2
(3.27)
kχ3 = (k - q) a3 + qb3,
(3.28)
a = χ - σ (q / (k - q))1/2
(3.29)
b = χ + σ ((k - q) / q)1/2
(3.30)
q = (k / 2) [1 + A (1 / (A2 + 4))1/2], onde
(3.31)
A = (3 χ χ2- 2 χ3 (χ)3)/ σ3
(3.32)
σ ≠ 0 (se σ = 0, a = b = χ)
(3.33)
o que implica em:
A última alternativa mencionada apresenta complexidade computacional intermediária às
duas primeiras para a compressão, sem acarretar custo extra durante a descompressão.
No caso de imagens gráficas, foi comprovado [MD80] que uma operação de suavização,
através do uso de filtragem espacial passa-baixas, resulta em uma imagem reconstruída
com menor MSE. A janela de convolução espacial sugerida é a mostrada abaixo:
0. 0
L
M
0, 1
M
M
N0, 0
0.1 0, 0
0, 6 0, 1
0, 1 0, 0
O
P
P
P
Q
O propósito da suavização é o de reduzir o ruído da imagem original, que implica em
quantizações incorretas para os pixels com níveis de cinza próximos ao valor do limiar.
Imagens gráficas apresentam uma certa continuidade bidimensional, e a filtragem
mencionada tende a tornar o nível de cinza de um pixel mais próximo dos níveis de seus
vizinhos.
Variações do Método
Lema e Mitchell [LM84] propuseram a substituição do segundo momento pelo primeiro
momento absoluto (Absolute Moment BTC), definido como:
α = (1 / k)
k
∑
i =1
|Xi - χ|,
(3.34)
e que pode ser calculado com menor esforço computacional:
α = (2 / k) γ
(3.35)
Com os valores a e b iguais a:
b = χ + (γ / q)
(3.36)
a = χ - (γ / (k - q)),
γ = kα / 2 =
∑
para Xi ≥ χ
onde
(3.37)
(Xi - χq).
(3.38)
A redução do número de bits na representação do mapa binário foi proposta por Mitchell e
Delp [MD80]. Baseia-se no fato de que alguns padrões do plano de bits são mais freqüentes
que outros, e consiste na codificação de apenas parte dos bits, sendo o restante inferido
durante a decodificação. A Figura 3.4 mostra 8 bits independentes de um bloco, em
destaque. Tais bits seriam codificados enquanto que os bits dependentes, na descompressão,
receberiam valores como se segue:
B
C
E
H
I
L
N
O
=
=
=
=
=
=
=
=
(A e D)
(A e D)
(A e M)
(D e P)
(A e M)
(D e P)
(M e P)
(M e P)
ou
ou
ou
ou
ou
ou
ou
ou
(F e J)
(G e K)
(F e G)
(F e G)
(J e K)
(J e K)
(F e J)
(G e K)
A
E
I
M
B
F
J
N
C
G
K
O
D
H
L
P
Figura 3.4 - Bits independentes em bloco 4x4, compressão BTC (pixels em negrito representam os bits
independentes codificados) [MD80].
Esta técnica preserva todas as bordas horizontais e verticais, e algumas diagonais. A
redução na entropia da imagem reconstruída seria de 0,5 bits/pixel.
Os mesmos autores sugerem que o número de bits alocados por plano seja proporcional ao
segundo momento, com a utilização de palavras de tamanho variável (Tabela 3.3).
Modo
σ
No. de bits (bloco 4x4)
1
2
3
17-256
1-16
<1
16
8
0
Tabela 3.3 - Codificação adaptativa do plano de bits a 256 níveis de cinza [MD80].
3.4 PCM - Pulse Code Modulation
O mais simples e conhecido algoritmo de compressão de imagens analógicas e digitais com
múltiplos níveis de cinza [JN84] é uma técnica não preservadora de informação, que resulta
em razões de compressão não superiores a 2:1 (4 bits/pixel).
Descrição do Método
O método PCM básico é descrito pelo diagrama da Figura 3.5.
Figura 3.5 - PCM básico [Lim90].
É, geralmente, utilizado para se obter uma imagem digital original a partir de uma imagem
analógica, a uma entropia de 8 bits/pixel, na maioria dos casos. A digitalização da imagem
analógica é obtida pela quantização do sinal de entrada. A quantização pode ser uniforme
ou não.
Em condições ideais, o ruído de quantização pode ser modelado, aproximadamente, como
ruído uniformemente distribuído. Este ruído começa a ser perceptível a partir de entropias
de 5 a 6 bits/pixel e, atingindo-se o patamar de 3 a 4 bits/pixel, pode ser identificado pelas
falsas linhas de contorno, originadas pelos saltos de luminância na imagem reconstruída,
em regiões onde há pequenas variações na imagem original (Figura 3.6).
Figura 3.6 - Saltos de luminância que causam o aparecimento de falsas linhas de contorno na compressão
PCM [Lim90].
Algoritmo de Compressão
início
para cada pixel da imagem faça
efetuar quantização
atribuir à palavra resultante o valor do intervalo de reconstrução obtido
armazenar palavra resultante
fim para
fim.
Algoritmo de Descompressão
início
para cada pixel da imagem faça
ler palavra correspondente
atribuir ao pixel o nível de reconstrução do intervalo de quantização obtido
fim para
fim.
Variações do Método
Uma maneira simples de aumentar o desempenho da compressão PCM [Lim90] é a
utilização de quantização não uniforme, uma vez que as intensidades não se encontram
distribuídas de maneira equalizada na imagem. Para se obter quantização não linear, aplicase uma função não linear à imagem original, procede-se à quantização e, em seguida,
aplica-se o inverso da função. Tal função deve ser escolhida de maneira que o resultado de
sua aplicação seja aproximadamente equiprovável para toda a faixa dinâmica.
Outra alternativa para se melhorar a eficiência da compressão PCM é a redução do efeito de
falso contorno, através da adição de ruído à imagem reconstruída, pela técnica proposta por
Roberts [Lim90]. Um ruído branco w(m,n) é adicionado à imagem original f(m,n) antes da
quantização, sendo subtraído após a reconstrução da imagem (Figura 3.7). Uma vez que a
função geradora do ruído é conhecida, independentemente da imagem, esta não necessita
ser armazenada ou transmitida, o que significa que não há impacto na entropia final da
imagem comprimida. Uma seqüência de ruído branco com função densidade de
probabilidade uniforme dada por:
1
, - ∆ / 2 ≤ w 0 ≤ ∆ / 2,
Pw (w0) = ∆
(3.39)
0 , outros casos,
R
|
S
|
T
onde ∆ é o tamanho do intervalo de quantização, pode ser usada.
Figura 3.7 - Exemplo de quantização com pseudo-ruído [Prat78].
3.5 DPCM - Differential Pulse Code Modulation
Trata-se de uma extensão do algoritmo PCM, proposta por Cutler em 1952 [Prat78]. É uma
técnica preditiva não preservadora de informação. Resulta em entropias em torno dos 3
bits/pixel.
Descrição do Método
A Figura 3.8 contém o diagrama da compressão DPCM. A idéia básica em torno do
algoritmo é a de se remover a redundância existente entre pixels vizinhos, codificando-se
apenas a informação nova.
Figura 3.8 - Compressão DPCM [Lim90].
Para se codificar o pixel corrente f(m,n), este é predito com base nos valores reconstruídos
dos pixels anteriores, gerando um valor fr(m,n). Na Figura 3.8, assume-se que os valores
f'(m-1 , n), f'(m , n-1), f'(m-1 , n-1), . . . foram reconstruídos antes da codificação.
O erro de predição e(m , n) é quantizado via PCM, uniformemente ou não. O erro
quantizado eq(m , n) é então armazenado. Na descompressão, eq(m , n) é adicionado a fr(m ,
n),a predição de f(m , n). O algoritmo DPCM pode ser descrito pelas equações:
e(m , n)
eq(m , n)
f'(m , n)
=
=
=
f(m , n) - fr(m , n)
Q[e(m , n)],
fr(m , n) + eq(m , n)
(3.40)
(3.41)
(3.42)
onde Q é a quantização PCM. De (2.40) e (2.42), o ruído de quantização é dado por:
EQ(m , n)
=
f'(m , n) - f(m , n) =
eq(m , n) - e(m , n)
(3.43)
A compressão DPCM pode ser vista como uma generalização da compressão PCM.
Especificamente, DPCM equivale a PCM quando fr(m , n) = 0.
O valor de f(m , n) é predito por combinação linear dos valores prévios reconstruídos:
fr(m , n) =
∑ ∑ a( k , k ) f ' ( m − k , n − k ),
1
2
1
2
k 1∈Ra k 2 ∈Ra
(3.44)
onde Ra é a região de (k1 , k2) na qual a(k1 , k2) ≠ 0.
Um aspecto importante da descompressão DPCM é que a predição é baseada nos valores
quantizados, e não nos valores originais de entrada (previsão em feedback). Assim, o erro
de quantização é retro-alimentado no quantizador no passo seguinte, o que produz um
efeito estabilizador, que previne o acúmulo de erros no sinal reconstruído.
Algoritmo de Compressão
início
salvar linha(s) de referência
para cada linha da imagem (exceto a(s) de referência) faça
atualizar pixel(s) de referência
salvar valor do primeiro pixel
acumulador = 0
para cada pixel da linha (exceto o primeiro) faça
efetuar previsão com base no(s) pixel(s) de referência
erro = valor do pixel corrente - previsão
erro = erro +acumulador
quantizar erro
acumulador = erro - erro quantizado
salvar palavra correspondente ao nível de quantização do erro
atualizar pixel(s) de referência
fim para
fim para
fim.
Algoritmo de Descompressão
início
ler linha(s) de referência
para cada linha da imagem (exceto a(s) de referência) faça
atualizar pixel(s) de referência
ler valor do primeiro pixel
para cada pixel da linha (exceto o primeiro) faça
efetuar previsão com base no(s) pixel(s) de referência
ler nível de quantização correspondente ao erro corrente
obter erro corrente
pixel corrente = valor previsto + erro corrente
atualizar pixel(s) de referência
fim para
fim para
fim.
Codificação Preditiva Preservadora de Informação
Uma vez que valores genéricos de entrada f(n) são inteiros e, restringindo-se os valores da
previsão fr(n) também a inteiros, a seqüência de valores de erros e(n) torna-se uma
seqüência de números inteiros que pode ser codificada sem distorções, por exemplo, pelo
código de Huffman [Lim90]. O codificador/decodificador resultante atingirá entropias
limitadas inferiormente pela entropia da seqüência de erros e(n).
DM - Delta Modulation
Uma variação do algoritmo DPCM, conhecida como Delta Modulation ou modulação delta
[Lim90], é aquela que utiliza um quantizador de 1 bit, com a seguinte função de previsão:
fr(m , n) = f(m , n-1),
(3.45)
ou seja, o valor previsto para o pixel corrente é igual ao valor do pixel imediatamente
anterior, na mesma linha.
A Figura 3.9 ilustra sinais de entrada e saída típicos da compressão DM. Suas principais
limitações são os fenômenos conhecidos como sobrecarga de borda e ruído granular. O
primeiro ocorre sempre que há um grande salto ou discontinuidade no sinal, aos quais o
quantizador só pode responder em muitos passos consecutivos. O ruído granular é
caracterizado pela natureza flutuante do sinal de saída, para regiões de sinal de entrada
quase constante.
Figura 3.9 - DM - Típicos sinais de entrada e saída [Jain89].
DPCM Unidimensional
Nesta variação do método [Lim90], cada linha da imagem é codificada independentemente.
Geralmente, uma representação de uma série autoregressiva é utilizada como definição da
função de previsão.
DPCM Bidimensional
Quando uma ou mais linhas anteriores são consideradas na função de previsão, de maneira
a se explorar também a correlação vertical entre os pixels vizinhos [Lim90]. Geralmente
são considerados apenas os pixels das linhas anterior e corrente, ilustrados na Figura 3.10.
DPCM Adaptativo
O desempenho do método pode ser aumentado com a utilização de quantizadores e/ou
preditores adaptativos às variações locais da imagem [Lim90].
No caso de um preditor adaptativo, a técnica mais comum usa várias funções de predição,
cada uma delas apropriada à correlação predominante em uma direção. A direção de
máxima correlação é calculada e o preditor mais adequado é aplicado individualmente a
cada pixel. Preditores adaptativos aumentam a qualidade da imagem, especialmente nas
bordas.
Para uma função de predição fixa, a variância do erro de predição varia com a região da
imagem. Os intervalos de quantização podem ser variáveis de acordo com a variância do
erro de predição a cada passo da compressão.
Figura 3.10 - Pixels (A,B,C,D) usados na predição bidimensional [Jain89].
3.6 TC - Transform Coding
Para aplicações que necessitam de altas taxas de compressão, acima de 8:1 (1 bit/pixel)
[Lim90], [NL80], o uso de transformadas na compressão de imagens com quantização
escalar (ou vetorial) apresenta desempenho superior ao de técnicas como PCM e DPCM. A
compressão por transformadas, entretanto, é de custo computacional e complexidade de
implementação mais elevados.
Descrição do Método
Na codificação por transformadas, a imagem é transformada para um domínio
significativamente diferente daquele das intensidades, ou níveis de cinza, sendo os
coeficientes resultantes quantizados e codificados.
A técnica explora o fato de que para imagens típicas, uma grande quantidade de energia
está concentrada em uma pequena fração dos coeficientes. Esta propriedade é conhecida
como compactação de energia. Graças a ela, é possível se codificar apenas uma parte dos
coeficientes de transformada, sem que a imagem original seja seriamente afetada.
O processo de compressão e descompressão é ilustrado pelo diagrama da Figura 3.11.
Durante a compressão, a imagem f(m, n) é transformada e os coeficientes Tf(m,n) são
quantizados. Os valores quantizados Tfq(m,n) são então codificados. Na descompressão, as
palavras são decodificadas e aos coeficientes resultantes Tfq(m,n) é aplicado o inverso da
transformada, obtendo-se assim a imagem reconstruída, fr(m,n) .
Algumas propriedades são desejáveis na transformada a se utilizar: por exemplo, deve
haver meios eficientes para o seu cálculo. As transformadas consideradas na compressão de
imagens são as lineares, expressas genericamente por:
M −1 N −1
∑ ∑ f (m, n) a (m, n) ,
(3.46)
∑ ∑ Tf (m, n) b(m, n) ,
(3.47)
Tf(m,n) =
m= 0 n = 0
M −1 N −1
f(m,n) =
m= 0 n = 0
onde f(m,n) e Tf(m,n) são seqüências de M x N valores e a e b são funções de base que
satisfazem a (3.46) e (3.47).
Figura 3.11 - Compressão por transformada [Lim90].
Outra propriedade desejável é a redução da correlação de Tf(m,n) em relação a f(m,n), que
pode ser obtida pela escolha adequada da função b.
Muitas transformadas têm sido consideradas na compressão de imagens, diferindo entre si
em compactação de energia e custo computacional. A transformada de Karhunen-Loève
(KLT) é aquela que apresenta maior compactação de energia. Entretanto, devido às
dificuldades de implementação de um algoritmo eficiente para o seu cálculo, é de interesse
apenas teórico. Muitas outras tranformadas foram criadas e utilizadas na compactação de
imagens.
Na compressão por transformada, a imagem é dividida em blocos de subimagens e cada
bloco é codificado separadamente. Dessa meneira, é possível a codificação adaptativa.
Outras vantagens da subdivisão da imagem original para aplicação da transformada são a
redução da capacidade de memória requerida no processamento e dos custos
computacionais. Naturalmente, existe um limite mínimo para o tamanho dos blocos, já que
para blocos menores é reduzida a correlação dentro dos mesmos e aumentada a correlação
entre blocos (não explorada pelo método). Tamanhos de blocos típicos são 8x8 e 16x16
pixels.
Algoritmo de Compressão
início
dividir a imagem em blocos p x q
para cada bloco da imagem faça
calcular a matriz resultante da aplicação da transformada
efetuar alocação de bits e quantização dos coeficientes
codificar coeficientes quantizados
salvar palavra correspondente ao bloco
fim para
fim.
Algoritmo de Descompressão
início
para cada bloco da imagem faça
decodificar palavra correspondente e montar bloco
aplicar a tranformada inversa, obtendo os valores dos pixels do bloco
fim para
fim.
Codificações Zonal e Por Limiar
A compressão de imagens por transformada explora a propriedade de compactação de
energia. Apenas uma pequena fração dos coeficientes é codificada. Existem dois
procedimentos principais na determinação desses coeficientes e de como serão codificados:
a codificação zonal e a codificação por limiar [Lim90].
Na codificação zonal, apenas aqueles coeficientes que pertencem a uma determinada região
do bloco são codificados. A definição da zona de codificação depende de fatores como a
razão de compressão desejada e o tipo de tranformada aplicada. Dois tipos de zoneamentos
para a transformada do cosseno (DCT) são ilustrados na Figura 3.12, sendo apenas aqueles
da região sombreada codificados (para os restantes, assume-se o valor zero).
Na codificação por limiar, os coeficientes são codificados, desde que sejam maiores que um
limiar definido. Estritamente do ponto de vista da compactação de energia, é o
procedimento preferível, uma vez que, na codificação zonal, coeficientes de baixa
magnitude podem ser codificados e coeficientes de alta magnitude, descartados. Entretanto,
a posição dos coeficientes a codificar não é conhecida a priori e deve ser também
codificada, quando da utilização de um limiar. A codificação por limiar é um método
adaptativo, pois a escolha dos coeficientes varia de acordo com as características locais da
imagem.
Figura 3.12- Exemplos de zonas usadas na compressão DCT (Discrete Cosine Transform) [Lim90].
Alocação de Bits
A distribuição dos bits de codificação ao longo de um bloco não deve ser uniforme
[Lim90], alocando-se mais bits para coeficientes de maior variância esperada. No caso da
transformada do cosseno, a variância é muito maior para os coeficientes de baixa
freqüência. Um exemplo de alocação de bits em um bloco de 16x16 pixels, com entropia de
0,5 bits/pixel para esta transforrmada é mostrado na Figura 3.13. O número em cada
posição representa o número de bits alocado para cada coeficiente, na codificação zonal.
A escolha dos níveis de reconstrução na quantização depende não só do número de bits
alocados, mas também da variância esperada. Para se eliminar esta última dependência,
cada coeficiente pode ser normalizado pelo desvio padrão esperado e apenas um conjunto
de níveis de quantização ser usado para um dado número de bits.
Compressão Híbrida
A compressão por transformada híbrida combina o alto desempenho da transformada com a
simplicidade de implementação do algoritmo DPCM [Lim90].
A imagem f(m,n) é transformada unidimensionalmente (por exemplo, por DCT), ao longo
de cada linha (ou coluna). O resultado, Tf(m,n), é então codificado por DPCM, ao longo de
cada coluna (ou linha), de acordo com o diagrama da Figura 3.14. A transformada 1D reduz
ainda mais a correlação entre os pixels de cada linha do que o faria a codificação DPCM, se
aplicada separadamente, enquanto que é de implementação e custo computacional menores
que a transformada 2D.
Figura 3.13 - Exemplo de alocação de bits a 0,5 bits/pixel para a codificação DCT zonal, com bloco de 16x16
pixels [Lim90].
Codificação Adaptativa
Outro método de se codificar uma imagem adaptativamente através do uso de
transformadas é sugerido por Pearlman [Pear90]. Se cada bloco é codificado com um
número fixo de bits, haverá uma grande variação na distorção média dos blocos. Do ponto
de vista da visão humana, é mais adequada uma estratégia de codificação que permita que
seja mantida a distorção constante através da variação da quantidade de bits por bloco.
3.7 PC - Pyramid Coding
Esta técnica de redução da correlação entre os pixels de imagens combina características
das técnicas preditivas e de transformadas [Lim90], [BA83], resultando em razões de
compressão de 4:1 (2 bits/pixel) a 16:1 (0,5 bits/pixel), com perda de informação.
Descrição do Método
Seja f0(m,n) a imagem original M x N a ser comprimida. f0(m,n) é definida como a base da
pirâmide, ou o nível 0 da mesma.
A imagem que se encontra a um nível acima da base, f1(m,n), é o resultado da aplicação de
filtragem passa-baixas e de sub-amostragem de f0(m,n), sendo essa seqüência de operações
denominada função redução. A função redução pode ser aplicada novamente a f1(m,n),
gerando o nível 2 da pirâmide f2(m,n), e assim sucessivamente, até que um nível final K seja
atingido. Tem-se portanto a generalização:
fL = Redução(fL-1).
(3.48)
Dependendo do filtro usado e também da subamostragem, há muitas variações no método.
Na representação da pirâmide gaussiana [BA83], é usada uma janela de convolução w(r,s)
de dimensões 5 x 5 pixels, como ilustra a Figura 3.14.
Figura 3.14 - Representação gráfica unidimensional da geração da pirâmide gaussiana [Lim90].
A aplicação da função redução se resume a:
2
fL(m,n) =
2
∑ ∑ w( r , s) f
( 2 n + r , 2 m + s),
L−1
r =−2 s =−2
(3.49)
sendo 0 < L < K, 0 ≤ i ≤ CL e 0 ≤ j ≤ RL, onde CL e RL são as dimensões da imagem no
nível L da pirâmide. Note-se que a cada redução, a imagem apresenta o número de pixels
dividido por 4. A geração da pirâmide gaussiana exige que a sua base apresente dimensões
B
C = MC 2 + 1,
B
R = MR 2 + 1,
(3.50)
(3.51)
onde MC, MR e B são números inteiros.
As dimensões de fL são:
B-L
CL = MC 2 + 1,
B-L
RL = MR 2 + 1.
(3.52)
(3.53)
Burt e Adelson sugerem a utilização da janela w(r,s) definida da seguinte forma:
ω (r) ω (s)
(separabilidade)
(3.54)
∑ ω(r )
=
(normalização)
(3.55)
ω (i)
ω (0) =
ω (1) =
ω (2) =
=
ω (-i) i = 0,1,2,. . . (simetria)
a
1/4
1/4 - a/2.
w(r,s) =
2
r =−2
1
(3.56)
(3.57)
(3.58)
(3.59)
A constante a é um parâmetro livre, tipicamente entre 0,3 e 0,6. A seqüência de ω (r) para
diversos valores de a é ilustrada na Figura 3.15 quando a é igual a 0,4, ω (r) é de forma
aproximadamente gaussiana.
Pode-se definir agora a função expansão como o inverso da função redução. O seu efeito é
a obtenção por interpolação de uma imagem no nível L-1, a partir do nível L:
ϕ L = Expansão(fL+1), ou
2
2
i − r j − sI
F
G
H2 , 2 J
K,
ϕ L(m,n) = 4 ∑ ∑ w( r , s) fL + 1
r =−2 s =−2
(3.60)
(3.61)
onde apenas os termos para os quais (m-r)/2 e (n-s)/2 são inteiros são incluídos no
somatório.
Figura 3.15 - Impulso ω (r) em função do parâmetro a [Lim90].
A idéia básica do algoritmo é a de se construir uma imagem reduzida de f0, f1, que
expandida, servirá como predição de f0. Para se obter compressão, a imagem do erro de
predição e0 é codificada. Aplicando-se este processo a todos os níveis da pirâmide, exceto o
último, tem-se uma definição formal do método.
A pirâmide laplaciana é construída pela seqüência de imagens e0, e1, e2 . . . eK:
eL = fL - Expansão(fL+1),
(3.62)
sendo eK = fK.
Algoritmo de Compressão
início
K=0
KL = índice do último nível da pirâmide
repita
a partir de fK , gere fK+1 ,com base na função redução definida (pirâmide gaussiana)
K=K+1
até K = KL
ϕ K = fKL
repita
a partir de
ϕ K , gere ϕ K-1 , com base na função expansão definida
K=K-1
até K = 1
para nível = 0 até KL-1 faça
enível = fnível - ϕ nível (pirâmide laplaciana)
fim para
quantize pirâmide laplaciana
codifique resultado da quantização
fim.
Algoritmo de Descompressão
início
decodifique pirâmide laplaciana
dequantize resultado da decodificação
KL = índice do último nível da pirâmide
fKL = eKL
K = KL
repita
ϕ K-1 ,com base na função expansão definida
ϕ K-1 , gere o nível K-1 da pirâmide gaussiana, fK-1 = ϕ K-1+ eK-1
a partir de fK , gere
a partir de
K=K-1
até K = 1
imagem reconstrída = f0
fim.
Quantização
A entropia final obtida pode ser substancialmente reduzida pela quantização dos valores
dos pixels a cada nível da pirâmide laplaciana. Com a escolha adequada dos níveis de
quantização, os erros decorrentes dessa operação podem implicar em degradações pouco
perceptíveis pelo observador.
Imagens de níveis superiores na pirâmide apresentam mais baixas freqüências e,
conseqüentemente, necessitam de mais bits por pixel na sua codificação, devido à maior
sensibilidade do olho humano a ruídos nessas regiões, conforme visto no Capítulo 2. Os
pixels de altas freqüências, na base da pirâmide, amostrados com maior freqüência, podem
ser quantizados mais grosseiramente.
Codificação
O uso de palavras de tamanho variável é recomendado, uma vez que favorece ainda mais a
redução da entropia final da imagem.
3.8 VQ -Vector Quantization (Quantização Vetorial)
Numerosas técnicas de compressão de imagens têm sido propostas, muitas delas discutidas
neste trabalho. Tais técnicas exploram usualmente as redundâncias estatísticas e
psicovisuais da imagem, de maneira a reduzir a entropia das mesmas. Uma deficiência
encontrada na maioria dessas técnicas convencionais é que a quantização é realizada sobre
valores individuais, o que mantém algum nível de correlação ou dependência entre os
valores quantizados. Um melhor desempenho é alcançável pela quantização de vetores, ao
invés de escalares, mesmo se a fonte apresenta a propriedade de ausência de memória
(quando um determinado estado independe dos estados anteriores) [NK88].
Definição
A quantização vetorial pode ser definida como um mapeamento Q do espaço euclideano kdimensional ℜ k , em um subconjunto finito Y de ℜ k :
→ Y,
Q : ℜk 
(3.63)
onde Y = ( χ i ; i=1,2,. . . P) é o conjunto de valores representativos do universo e P o
número de vetores em Y. A quantização vetorial pode ser vista também como uma
combinação de duas funções, um codificador, que recebe o vetor de entrada x e gera o
endereço do vetor de representação especificado por Q(x), e um decodificador, que usa o
endereço para gerar o vetor de representação χ .
Se uma medida de distorção d(x,χ ), representando a penalidade ou custo associado aos
vetores x por χ pode ser definida, então o mapeamento ótimo é aquele que minimiza
d(x,χ ). Como alternativa mais simples, adota-se o MSE como medida de distorção.
Dicionário de Vetores
O objetivo da definição de um quantizador vetorial ótimo, consistindo de P vetores é o de
minimizar a distorção esperada.
Linde, Buzo e Gray [LBG80], a partir da teoria desenvolvida por Lloyd, propuseram o
algoritmo hoje conhecido por LBG, que garante, no mínimo, otimização local. Tal
algoritmo é usado amplamente no projeto de quantizadores vetoriais, devido a sua
eficiência e versatilidade, podendo ser aplicado tanto para o caso em que é conhecida a
distribuição probabilística da fonte, quanto através de uma longa seqüência de treinamento,
constituída por vários vetores amostrados da própria fonte. Na página seguinte, apresentase o algoritmo LBG para distribuição indeterminada, em versão simplificada.
Algoritmo LBG
No algoritmo LBG, durante a otimização do dicionário, apenas partições ou subconjuntos
da seqüência de treinamento são consideradas. Uma vez que o dicionário final Y é obtido,
este é aplicado a vetores não pertencentes à seqüência de treinamento pela regra do vizinho
mais próximo. Se a seqüência é sufucientemente grande, o quantizador obtido para a
distribuição da amostra apresentará bons resultados também para a distribuição real. Podese demonstrar ainda [LBG80] que o algoritmo sempre converge para um quantizador fixo
em um número finito de iterações.
O resultado final Y é altamente sensível ao alfabeto inicial A0 escolhido. Há várias maneiras
de se determinar A0. No método mais simples, os primeiros P vetores na seqüência são
selecionados. Não se trata de técnica muito recomendável, dada a proximidade entre os
vetores. Pode-se também escolher P vetores igualmente espaçados ao longo de toda a
seqüência. Em uma terceira técnica, o centróide da seqüência é calculado e dá origem a
dois outros próximos, através da introdução de pequenas perturbações no mesmo. O
algoritmo LGB é aplicado no par de vetores resultante, de maneira a se obter um
quantizador de dois níveis. A cada vetor resultante, é novamente introduzida uma
perturbação, gerando-se agora quatro vetores. O procedimento é repetido sucessivamente,
até que P vetores tenham sido criados, originando-se a seqüência inicial.
Algoritmo LBG
início
sejam
P, número de vetores do dicionário,
ε , limiar de distorção,
A0 ,dicionário inicial de vetores,
xj , j = 0, . . ., p-1, seqüência de vetores de treinamento
t=0
D-1 =
∞
fim = falso
enquanto não(fim) faça
dado At = {yi;i = 1,. . . ,P}
e sendo a partição P(At) = {Si; i = 1,. . .,P},
para indice = 1 até P faça
distorção[índice] = 0
contador[índice] = 0
somatório[índice] = 0
fim para
para j = 0 até p-1 faça
dMIN =
∞
para i=1 até P faça
se d(xj ,yi)
≤ dMIN
então
dMIN = d(xj ,yi)
índice = i
xj pertence a Si
fim se
fim para
distorção[índice] = distorção[índice] + dMIN
contador[índice] = contador[índice] + 1
somatório[índice] = somatório[índice] + xj
fim para
Dm = 0
para i = 1 até N faça
Dm = Dm + somatório[i]
fim para
Dt = Dt/p
se (Dt-1 - Dt)/Dt
≤ε
então
dicionário final Y = At
senão
fim = verdadeiro
para i = 1 até P faça
yi = somatório[i]/contador[i]
fim para
At+1 = At
t=t+1
fim se
fim enquanto
fim.
SQ/VQ - Scalar Quantization/Vector Quantization e
VQ/VQ - Vector Quantization/Vector Quantization
Finamore, Nunes e Fortes [FNF89] propuseram a utilização de quantização vetorial na
compressão de imagens através da aplicação dos algoritmos SQ/VQ e VQ/VQ.
O primeiro consiste na quantização escalar da imagem f (SQ) em dois níveis, obtendo-se
como resultado a imagem fq, codificada a no máximo 1 bit/pixel, pelo algoritmo RLC. A
imagem g = f - fq, é codificada por quantização vetorial (VQ) (Figura 3.16).
O algoritmo VQ/VQ apresenta a mesma idéia anterior, com a diferença de que a primeira
quantização também é vetorial (Figura 3.17).
Classified VQ Coding
Imagens comprimidas por VQ a entropias muito baixas apresentam usualmente distorções
de borda, devido ao reduzido número de vetores do dicionário. Ramamurthi e Gersho
[RG86] minimizaram este problema pela classificação de cada vetor da imagem de acordo
com categorias pré-definidas, por exemplo, de vetores de borda e de textura, e codificação
de acordo com o quantizador mais apropriado. A extensão da idéia leva à utilização de um
número maior de categorias, com vários tipos de classe de bordas (Figura 3.18). Operadores
de gradiente são aplicados aos vetores para efeito de classificação.
Figura 3.16 - Compressão SQ/VQ [FNF89].
Figura 3.17 - Compressão VQ/VQ [FNF89].
Figura 3.18 - Classificação de vetores [NK88].
Predictive VQ Coding
A dependência estatística entre vetores consecutivos sugere uma melhora no desempenho
dos algoritmos VQ a partir da exploração da correlação intervetorial. O algoritmo DPCM
pode ser generalizado para o plano vetorial, de modo que o codificador seja composto por
um preditor e um quantizador de erros vetoriais.
Adaptive Tranform VQ Coding
Na compressão adaptativa por transformada, diversas matrizes de atribuição de bits são
definidas, sendo cada bloco de coeficientes classificado conforme a atividade local e
recebendo a atribuição de bits mais adequada. Por esse método, uma quantidade
significativa de coeficientes de alta freqüência é descartada, o que resulta em perda de
qualidade da imagem reconstruída.
A Figura 3.19 ilustra um esquema alternativo de compressão, pelo qual a região de 0 bits
alocados do bloco é codificada por VQ. Desta maneira, obtém-se um aumento na qualidade
final, que, apesar do ligeiro aumento da entropia final da imagem, é compensador,
principalmente para altas razões de compressão [NK88].
BTC/VQ Coding
Udpikar e Raina [UR87] sugeriram a utilização de quantizadores vetoriais em conjunto com
a codificação BTC, para se elevarem as razões de compressão finais.
A idéia se resume no uso de dois dicionários de vetores, um para os parâmetros estatísticos
da compressão BTC χ e σ , bidimensional, e outro para o mapa de bits, binário e de
dimensão igual ao tamanho do bloco utilizado. Segundo os autores, poucas perturbações
perceptíveis extras são introduzidas na imagem, com um ganho de 100% em relação à
compressão (1 bit/pixel para blocos de 4 x 4 pixels).
Figura 3.19 - Matriz de atribuição de bits - Compressão adaptativa por transformada/VQ [NK88].
3.9 Técnicas de Segunda Geração
A idéia por trás das técnicas de segunda geração é a de se explorar o mecanismo de
percepção visual humano para redução da entropia de imagens. Ao invés de levar em conta
os pixels individuais, o sistema visual humano identifica características específicas da
imagem, como contornos (altos gradientes) e texturas (subregiões delimitadas por
contornos, contendo padrões repetitivos). A combinação de tais características [KIK85]
tende a formar objetos reconhecíveis, que podem ser comparados com um vasto número de
entidades similares contidas na memória do observador, o que culmina no final do processo
com a interpretação da cena.
Os principais algoritmos de segunda geração são brevemente descritos a seguir [KIK85],
[KBL87]:
Codificação de bordas: divide as imagens em dois tipos de sinal, os de altas e os de baixas
freqüências. A combinação da alta sensibilidade do olho humano à posição e orientação de
contornos com a baixa sensibilidade a diferenças de amplitude, sugere a codificação das
bordas (como em uma imagem binária) separadamente das regiões de baixas freqüências,
que contêm menor quantidade de informação. As razões de compressão obtidas são da
ordem de 1 bit/pixel. Os principais passos do algoritmo são:
•
•
•
•
obtenção das bordas através da aplicação de gradiente ou filtros laplacianos;
codificação binária da informação de bordas;
filtragem passa-baixas para extração da informação de baixa freqüencia;
codificação da informação de baixa freqüência por subamostragem ou transformadas.
Decomposição direcional: pode ser considerada uma variação da codificação de bordas e
assegura a preservação otimizada das linhas de contorno, através do uso de filtros
direcionais em direções pré-definidas. A aplicação deste e de outros recursos proporciona
razões de compressão de até 0,1 bits/pixel.
Codificação de contorno-textura: similar à codificação de bordas, esta técnica segmenta a
imagem em diversas regiões de contorno e textura. A forma da distribuição das
intensidades dentro de cada região é codificada pela aproximação a funções polinomiais
bidimensionais de primeira ou segunda ordem. Ruídos granulares são removidos no préprocessamento e adicionados de forma pseudo-aleatória na descompressão. Razões de
compressão entre 0,15 e 0,5 bits/pixel são obtidas por este método.
As técnicas de segunda geração não foram consideradas neste trabalho, devido aos altos
custos computacionais envolvidos na compressão e descompressão de imagens, que
inviabilizariam a utilização prática dos algoritmos.
3.10 Formatos
Padrões de Formatos de Imagens
A implementação dos algoritmos neste trabalho, foi realizada com base no formato padrão
de imagens digitais estabelecido por Davis [Davi92].
Como referência para avaliação quantitativa e qualitativa dos resultados obtidos, adotou-se
o padrão de codificação internacional proposto pelo JPEG (Joint Photographic Experts
Group) [ISO91].
Formato BM
O formato BM (bit map) de codificação de imagens foi criado visando a simplificação da
aplicação de algoritmos de processamento digital de imagens [Davi92]. Este formato foi
proposto como padrão da interface PixelWare e adotado nas implementações deste
trabalho.
O formato BM reserva originalmente (versão 1.0) um byte para cada pixel da imagem, sem
efetuar nenhuma compactação. Para definição dos demais parâmetros da imagem, foi
incluído um header, de 1024 bytes no início do arquivo. Este header contém também,
opcionalmente, o conteúdo da look-up table, segundo o padrão VGA.
Para poder representar agora imagens compactadas, foi necessária a alteração da
configuração do header, de maneira a indicar os parâmetros da compressão. Assim, os
arquivos de imagens compactados recebem a extensão CBM (Compressed Bit Map),
possuindo o header as informações necessárias à descompressão da imagem nos 12 bytes,
ocupados pelo campo compression. Para imagens não comprimidas, a extensão permanece
BM, sendo os bytes de compression iguais a zero. As imagens BM na versão 2.0
apresentam a seguinte estrutura:
Campo
Tipo
Descrição
width
height
version
num_planes
bits_per_plane
image_type
word
word
byte
byte
byte
byte
palette
768 bytes
compression
12 bytes
oldwidth
oldheight
filler
word
word
232 bytes
largura da imagem (pixels)
altura da imagem (pixels)
02H = (versão 2.0)
número de planos de cor
número de bits por pixel por plano
código para o modelo de arquivamento:
00H = EGA/VGA, paleta básica de 16 cores
01H = MCGA/SVGA, look-up table de 256 linhas
FFH = sem paleta
256 x R/G/B. Valores no padrão dos registros D/A das
placas VGA/SVGA (valores entre 0 e 63)
algoritmo de compressão utilizado e parâmetros
respectivos
largura da imagem original (pixels)
altura da imagem original (pixels)
reservado para uso futuro (todos os bytes setados para
00H)
Figura 3.20 - Header das imagens BM na versão 2.0.
Os valores possíveis para cada um dos 12 bytes do campo de compression são apresentados
na Figura 3.21.
Formato JPEG
A norma internacional que define o formato JPEG [ISO91] é aplicável a imagens digitais
com múltiplos níveis de cinza, ou coloridas. É utilizável em inúmeras aplicações que
requerem o uso de imagens comprimidas, não se prestando entretanto à codificação de
imagens binárias.
Byte 1
Significado
Demais bytes
Valor
Significado
00H
01H
02H
imagem descomprimida
RLC (imagens binárias)
MREAD (imagens binárias)
todos
todos
2
3
00H
00H
00H
00H
uso futuro
uso futuro
uso futuro
tabela modificada de Huffman para
seqüências de brancos
tabela modificada de Huffman para
seqüências de pretos
uso futuro
uso futuro
blocos 4x4
blocos 16x16
arquivo original no formato BM
descomprimido
arquivo original no formato BM
comprimido pelo algoritmo PCM
uso futuro
uso futuro
compressão sem perda de informação
compressão com perda de informação
quantização fixa não uniforme
quantização adaptativa uniforme
níveis de quantização
8 níveis de quantização
DPCM convencional
DM
uso futuro
uso futuro
geração de arquivos da pirâmide
gaussiana
geração de arquivos da pirâmide
laplaciana
uso futuro
uso futuro
VQ associada ao algoritmo BTC
VQ pura
uso futuro
01H
03H
BTC
demais
2
3
4
00H
00H
00H
01H
00H
01H
04H
DPCM
demais
2
3
demais
2
3
00H
00H
00H
01H
00H
01H
00H
01H
00H
01H
00H
00H
01H
4
01H
todos
todos
2
00H
00H
03H
08H
00H
4
5
6
05H
06H
07H
08H
PC
DCT
PCM
VQ
demais
Figura 3.21 - Valores possíveis para os parâmetros de compressão do formato BM
A compressão JPEG pode ser representada na Figura 3.22. O diagrama apresentado resume
o algoritmo, uma vez que todos os processos especificados pela norma internacional são
aplicados a imagens individuais, independentemente.
Figura 3.22 - Compressão DCT (JPEG) [ISO91].
Os elementos da imagem são agrupados em blocos de 8 x 8 pixels, sendo a cada bloco
aplicada a transformada do cosseno, originando-se um conjunto de 64 valores, ou
coeficientes DCT. Cada um deles é quantizado, usando-se um dos valores correspondentes
de uma tabela de 64 valores. A norma internacional não especifica valores default para a
tabela, sendo a sua escolha feita em função da qualidade final da imagem, características
particulares da fonte e condições de reprodução.
Após a quantização, os coeficientes, denominados DC (o primeiro) e AC (os 63 restantes)
são preparados para a codificação entrópica (Figura 3.23). O coeficiente DC anterior é
usado na predição do coeficiente corrente, sendo a diferença codificada. Os 63 coeficientes
AC são convertidos em uma seqüência uni-dimensional em zig-zag.
Figura 3.23 - Preparação dos coeficientes quantizados para codificação entrópica [ISO91].
Um entre dois processos de codificação entrópica é utilizado, a codificação de Huffman, ou
a codificação aritmética. Em ambos os casos, especificações para a escolha das tabelas
devem ser fornecidas.
A Figura 3.24 ilustra os procedimentos principais da descompressão JPEG. Cada processo
aplica o inverso do processo correspondente na compressão.
A norma especifica ainda procedimentos para compressão de imagens digitais sem perda de
informação (Figura 3.25). Neste caso, um preditor combina os valores reconstruídos a partir
de até 3 valores vizinhos, a, b e c, para definir o valor do pixel na posição x (Figura 3.26).
A predição é subtraída do valor real na posição x e a diferença é codificada entropicamente.
Figura 3.24 - Descompressão DCT (JPEG) [ISO91].
Figura 3.25 - Compressão JPEG sem perda de informação [ISO91].
Figura 3.26 - Predição por vizinhança [ISO91].
3.11 Conclusão
Apresentaram-se neste capítulo os principais algoritmos de compressão de imagens, de
primeira e segunda gerações. No caso das imagens binárias, tanto RLC quanto MREAD
garantem a fidelidade total da imagem reconstruída, para fins de armazenamento. A razão
de compressão final obtida para ambos é muito sensível às características da imagem
processada, mas, em média se situa na faixa dos 3:1. O algoritmo RLC pode utilizar um
mecanistmo de codificação com palavras de tamanho variável, como o código de Huffman.
MREAD é uma técnica mais recente, que oferece melhores resultados em termos de
compressão, valendo-se também de códigos com palavras de tamanho variável.
Quanto aos algoritmos para imagens com múltiplos níveis de cinza, foram descritos aqueles
que trabalham com blocos (BTC, TC, VQ), com linhas (PCM, DPCM) e com ambos (PC).
Genericamente, os algoritmos do segundo grupo oferecem desempenho inferior aos demais,
uma vez que não exploram com eficiência a correlação entre elementos situados além das
linhas de referência (correlação vertical). As razões de compressão também são
dependentes das características da imagem original, situando-se entre 3:1 e 16:1. Os
melhores resultados são atingidos pelos algoritmos de segunda geração, como os aqui
citados, codificação de contorno-textura, decomposição direcional e codificação de bordas,
que podem alcançar compressões da ordem de 100:1. Entretanto, a complexidade das
implementações e os elevados tempos de processamento são fatores impeditivos de sua
utilização, na aplicação aqui proposta.
O formato BM foi detalhadamente descrito, uma vez que foi o formato adotado nas
implementações deste trabalho. Como padrão de comparação, o formato JPEG, que utiliza
a transformada do cosseno associada à codificação preditiva, também foi abordado.
O capítulo seguinte pretende detalhar as implementações efetuadas, incluindo a delimitação
dos parâmetros adotados em cada uma delas. Para muitos dos algoritmos implementados,
disponibilizaram-se diferentes alternativas, permitindo ao usuário maior flexibilidade na
adequação de sua aplicação.
4. DESCRIÇÃO DO SISTEMA
O sistema de compressão de imagens desenvolvido foi implementado em duas versões
diferentes. A primeira delas disponibiliza rotinas de compressão na plataforma PixelWare,
desenvolvida no Departamento de Ciência da Computação da UFMG [Davi92]. Na segunda
versão, os algoritmos de compressão e rotinas auxiliares foram implementados na própia
interface do sistema operacional MS-DOS, sendo executados no nível de linha de comando.
Optou-se pela implementação de algoritmos básicos, que proporcionassem uma visão
global das diversas técnicas existentes e que indicassem, em futuros trabalhos, as soluções
mais adequadas para aplicações específicas de compressão de imagens. Entretanto, tendo
em vista a restrição estabelecida com relação ao tempo de recuperação das imagens,
algoritmos de mais alta complexidade computacional não foram implementados.
Como complementação do trabalho, foram implementadas rotinas para cálculo de
parâmetros estatísticos (MSE e SNR), conversão de arquivos BM da versão 1 para a versão
2 e vice-versa, manipulação de amostras de vetores e otimização do alfabeto de vetores
usados pelo algoritmo VQ.
4.1 Hardware
As rotinas de compressão de imagens foram desenvolvidas essencialmente para a
plataforma IBM PC, sendo recomendado o uso dos processadores 386/486.
Para nenhuma das interfaces é exigida memória estendida ou expandida. A configuração
mínima do equipamento é a seguinte [Davi92]:
•
•
•
•
•
CPU 80x86;
640 Kbytes de memória RAM;
monitor de vídeo e placa gráfica no padrão SuperVGA, sendo a placa baseada em chip
set Ahead, ATI, Chips & Technologies, Everex, Paradise, Trident, Tseng ou Video
Seven, ou no padrão VESA;
mouse padrão Microsoft
coprocessador aritmético opcional.
4.2 Apresentação do Sistema
Interface MS-DOS
Dentro da interface do sistema operacional DOS, as rotinas de compressão, descompressão
e auxiliares são acionadas através da linha de comando. São os seguintes os executáveis
disponíveis:
Compressão
CRUSH método [opções] infile [outfile] [filtfile],
onde, os métodos e opções correspondentes são:
RLC = Run-Length Coding (imagens binárias);
BTC = Block Truncation Coding;
/f: cria imagem BM resultante da filtragem passa-baixas no préprocessamento. Se usada, é necessária a especificação do nome do
arquivo filtfile;
/h: compressão alta, blocos de 16x16 pixels;
/s: compressão normal, blocos de 4x4 pixels (default);
/p: comprime fontes CBM comprimidas pelo algoritmo PCM;
READ = Modified READ (imagens binárias);
/b: usa tabela de Huffman para seqüências de pretos (default);
/w : usa tabela de Huffman para seqüências de brancos;
PCM = Pulse Code Modulation
DPCM = Differential Pulse Code Modulation
/a: quantização adaptativa uniforme (compressão com perda);
/d: Delta Modulation, quantização em 2 níveis (compressão com perda, /f
assumido);
/f: quantização fixa não uniforme (compressão com perda, default);
/h: quantização em 8 níveis (compressão com perda);
/i: compressão sem perda (default);
/l: compressão com perda;
/s:quantização em 16 níveis (compressão com perda, default);
LPYR = Laplacian Pyramid Coding
DCT = Discrete Cosine Transform
VQ = Vector Quantization
/i: VQ pura;
/b:VQ/BTC;
opções genéricas:
/e: não exibe mensagens durante o processamento;
/r: exibe na tela relátorio com resultados da compressão.
A opção /r emite relatório, contendo os seguintes dados:
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
nome do arquivo de entrada;
versão do arquivo de entrada;
número de planos de bits do arquivo de entrada;
número de bits por plano do arquivo de entrada;
tipo de imagem do arquivo de entrada;
tamanho do cabeçalho do arquivo de entrada;
largura da imagem original;
altura da imagem original;
número de bytes da imagem original;
largura da imagem reconstruída;
altura da imagem reconstruída;
número de bytes da imagem reconstruída;
número de bytes da imagem comprimida;
entropia da imagem comprimida;
razão de compressão obtida.
A extensão de infile deve ser obrigatoriamente BM, exceto para a fonte PCM na
codificação BTC, quando deve ser CBM. A extensão de outfile deve ser CBM e, se não
informado o nome do arquivo, será assumido o mesmo contido em infile. A extensão de
filtfile deve ser BM.
Descompressão
UNCRUSH infile [outfile],
onde infile deve ter a extensão CBM e outfile, BM, sendo para este último assumido o
mesmo nome contido em infile, se não informado.
Conversão de Aquivos BM
Os seguintes utilitários realizam a conversão de arquivos BM da versão 1 para a 2:
BM12BM2 infile
e da versão 2 para a versão 1:
BM22BM1 infile,
onde infile deve ter a extensão BM.
Medidas de Distorção
Para estudo comparativo entre as imagens original e reconstruída foi desenvolvido este
utilitário, que calcula o MSE e SNR para duas imagens BM, que podem ter ou não as
mesmas dimensões, dependendo do algoritmo de compressão usado (Capítulo 3). No
último caso, os valores são calculados levando-se em consideração as menores dimensões x
e y encontradas nas duas imagens, disponíveis nos arquivos infile1 e infile2:
MSE infile1 infile2,
onde infile1 e infile2 devem ter a extensão BM.
Algoritmo LBG
O algoritmo de geração dos alfabetos de 256 vetores foi implementado no ambiente UNIX,
enquanto que a rotina de geração e ordenação das amostras de vetores, no ambiente DOS.
O seguinte utilitário gera amostras de vetores a partir de imagens-amostras, ordena-as e
aglutina arquivos ordenados, para quantização vetorial, no sistema operacional MS-DOS:
VECTOR algoritmo opção infile in/outfile [outfile],
onde, os algoritmos disponíveis são:
VQ = (VQ Pura);
BTC = (VQ/BTC)
e as opções:
/s: gera arquivo(s) de amostras de vetores a partir de imagem BM (requer dois
outfiles para BTC, gerando arquivos já ordenados);
/o: ordena vetores do arquivo de amostras (apenas para VQ);
/m: concatena dois arquivos de vetores de amostras ordenados.
Quando o algoritmo é VQ e a opção /s ou /o, um infile e um outfile são requeridos. Se o
algoritmo é BTC, um infile e dois outfiles devem ser informados. Neste caso, o primeiro
outfile especificado conterá as amostras de vetores de bit maps e o segundo, as amostras de
vetores de parâmetros estatísticos, ambos já ordenados (por isso não é permitido o
parâmetro /o associado a BTC). O uso a opção /m em ambos os algoritmos concatenará
dois infiles de vetores, armazenando o resultado em outfile. Para a opção /s, o arquivo de
entrada deve ter a extensão BM.
O seguinte utilitário disponível no sistema operacional UNIX gera alfabetos otimizados de
256 vetores a partir de arquivos de amostras de vetores ordenados:
VECTOR algoritmo infile [infile] [outfile].
No caso do algoritmo BTC, dois infiles são necessários, contendo, o primeiro, os vetores de
bitmaps ordenados e o segundo, os vetores de parâmetros estatísticos. No arquivo de saída,
outfile, é gerado o dicionário de vetores ótimos.
Interface PixelWare
Sobre a plataforma PixelWare [Davi92], as mesmas alternativas para compressão e
descompressão de imagens foram implementadas. A estrutura de menus e janelas de
diálogo facilita a utilização do sistema e permite estudos mais completos, através do uso de
outras rotinas de processamento digital de imagens, já disponíveis no sistema.
As Figuras 4.1 e 4.2 ilustram o uso das rotinas implementadas dentro da interface
PixelWare.
Figura 4.1 - Interface Pixelware - Algoritmos de compressão de imagens disponíveis.
Figura 4.2 - Interface Pixelware - Resultados de compressão.
Estrutura Interna
O chamado Sistema de Compressão de Imagens contém rotinas modularizadas e
estruturadas conforme o diagrama da Figura 4.3.
Cada um dos módulos do sistema corresponde a um programa fonte escrito em C.
Excetuando-se os módulos principais CRUSH, UNCRUSH, MSE, VECTOR e
COMPRESS, existe um header para cada módulo, contendo os protótipos de funções e
definições. Além disso, foram criados os módulos SCITYPE e SCICONST, que contêm
declarações e definições globais, respectivamente. O módulo COMPRESS foi anexado ao
sistema PixelWare e utiliza as mesmas funções disponíveis nos módulos utilizados por
CRUSH/UNCRUSH.
São as seguintes as funções de cada módulo:
•
•
•
•
•
•
•
•
•
•
scibyte: funções de manipulação de bytes;
scibuf: funções de gerenciamento de buffers para processamento;
scihuff: funções para manipulação de códigos de Huffman;
scifile: funções de leitura e escrita em arquivos;
scistat: funções geradoras de dados estatísticos;
scirlc: compressão e descompressão RLC;
sciread: compressão e descompressão READ;
scibtc: compressão e descompressão BTC;
scipcm: compressão e descompressão PCM;
scidpcm: compressão e descompressão DPCM;
•
•
•
scipyr: compressão e descompressão PC;
scitrans: compressão e descompressão DCT;
scivq: compressão e descompressão VQ.
Figura 4.3 - Módulos do sistema de compressão de imagens
4.3 Algoritmos
A compressão de imagens binárias é um campo amplamente explorado e diversas
aplicações, a exemplo da transmissão de fac-símiles, têm sido desenvolvidas. Dois
algoritmos foram implementados para compressão de imagens, RLC e MREAD. A
compressão de arquivos binários BM foi implementada considerando-se que cada pixel da
imagem apresenta os valores 0 (preto) ou 255 (braco). Neste caso, o formato BM adiciona 7
bits/pixel extras, uma vez que a imagem necessitaria de apenas 1 bit/pixel para sua
codificação.
O problema da compressão de imagens digitais com múltiplos níveis de cinza apresenta
uma maior complexidade, sendo as suas aplicações cada vez mais numerosas. Os seguintes
algoritmos foram definidos para implementação: BTC, PCM, DPCM, PC, DCT e VQ.
RLC - Run Length Coding
A rotina implementada adota na codificação das seqüências de brancos (255) e pretos (0) o
código modificado de Huffman recomendado pela CCITT [HR80]. As seguintes variáveis
contêm tal código, listado no Apêndice A:
static mhconstcodetype rlclowhuffmanw[64]: tabela de bits menos significativos, para
seqüências de brancos de 0 a 63 pixels;
static mhconstcodetype rlchighhuffmanw[28]: tabela de bits mais significativos, para
seqüências de brancos de 64 a 1791 pixels (usada em associação com a tabela anterior);
static mhconstcodetype rlclowhuffmanb[64]: tabela de bits menos significativos, para
seqüências de pretos de 0 a 63 pixels;
static mhconstcodetype rlchighhuffmanb[28]: tabela de bits mais significativos, para
seqüências de pretos de 64 a 1791 pixels (usada em associação com a tabela anterior).
A razão de compressão obtida pela aplicação do algoritmo é variável, de acordo com as
características da imagem. Deve-se observar que a compressão real é inferior, quando
aplicada aos arquivos BM, já que este formato adiciona 7 bits/pixel de redundância a
imagens binárias. A imagem reconstruída apresenta as mesmas dimensões da imagem
original, pois a codificação é feita pixel a pixel.
As funções de compressão e descompressão de imagens se encontram no módulo
SCIRLC.C:
void rlc_encode_image(char *infile,char *outfile,struct bmheadertype *h,
unsigned long int *savedbytes);
void rlc_decode_image(FILE *inf,FILE *outf,int dx,int dy),
onde :
infile = nome do arquivo de entrada da compressão (BM);
outfile = nome do arquivo de saída da compressão (CBM);
h = header do arquivo de saída da compressão;
savedbytes = número de bytes da imagem resultante da compressão (excluído o
cabeçalho);
inf = arquivo de entrada da descompressão (CBM);
outf = arquivo de saída da descompressão (BM);
dx = largura da imagem reconstruída, em pixels;
dy = altura da imagem reconstruída, em pixels.
MREAD - Modified Relative Element Address Designate Coding
Os modos são codificados conforme o código descrito no Apêndice B e contido na variável:
static mhconstcodetype readhuffman[9].
O método preserva as dimensões originais da imagem e proporciona razões de compressão
variáveis, normalmente superiores às obtidas pelo BTC. É também pertinente a observação
sobre a razão de compressão real feita no item anterior.
São as seguintes as funções de compressão e descompressão, disponíveis no módulo
SCIREAD.C:
void read_encode_image(char *infile,char *outfile,boolean bestw,
struct bmheadertype *h,
unsigned long int *savedbytes);
void read_decode_image(FILE *inf,FILE *outf,int dx,int dy,int best),
onde,
infile = nome do arquivo de entrada da compressão (BM);
outfile = nome do arquivo de saída da compressão (CBM);
bestw = variável lógica, indica que será usado o código de Huffman para seqüências
de brancos (TRUE), ou pretos (FALSE), na codificação das distâncias
de
referência;
h = header do arquivo de saída da compressão;
savedbytes = número de bytes da imagem resultante da compressão (excluído o
cabeçalho);
inf = arquivo de entrada da descompressão(CBM);
outf = arquivo de saída da descompressão (BM);
dx = largura da imagem reconstruída, em pixels;
dy = altura da imagem reconstruída, em pixels;
best = idem a bestw, na decodificação.
BTC - Block Truncation Coding
O algoritmo BTC foi implementado para dois diferentes níveis de compressão, a 2 e 1
bits/pixel, usando-se, respectivamente, blocos de 4x4 e 16x16 pixels. A palavra
representativa de cada bloco é composta por um bit map (16 bits para o bloco 4x4 e 256
bits para o bloco 16x16), acrescido de mais 8 bits que representam a média calculada para o
bloco e outros 8 bits para a variância. Sendo assim, a razão de compressão obtida é fixa:
Rc
Rc
=
=
[(8 bits/pixel) * 16 pixels] / (16 + 8 + 8) bits
4:1, ou 2 bits/pixel
(Bloco 4x4)
(4.1)
=
=
[(8 bits/pixel) * 256 pixels] / (256 + 8 + 8) bits
7,53:1, ou 1,06 bits/pixel
(Bloco 8x8)
(4.2)
O método BTC, por não tratar os pixels individualmente, mas em blocos, pode não
preservar as dimensões originais da imagem. Na implementação deste trabalho, a imagem
sofre inicialmente uma adequação aos valores de dx e dy, de maneira a não permanecerem
blocos incompletos:
Novo dx = dx - (dx mod Sb);
(4.3)
Novo dy = dy - (dy mod Sb),
(4.4)
onde Sb é a dimensão do bloco (4 ou 16) e mod representa o resto de divisão inteira.
Opcionalmente, pode-se aplicar no pré-processamento a operação de filtragem definida no
Capítulo 3. Além disso, a rotina desenvolvida aceita como entrada um arquivo BM
comprimido pelo algoritmo PCM (extensão CBM), ou seja, a 4 bits/pixel, gerando um
segundo arquivo com extensão CBM. Neste caso, na descompressão, é gerado outro aquivo
CBM, a 4 bits/pixel.
O módulo SCIBTC.C disponibiliza as seguintes rotinas de compressão e descompressão:
void btc_encode_image(char *infile,char *outfile,char *filtfile,boolean high,
boolean filt,struct bmheadertype *h,
boolean pcmsource,
unsigned long int *savedbytes);
void btc_decode_image(FILE *inf,FILE *outf,int dx,int dy,boolean high,
boolean pcmsource),
onde,
infile = nome do arquivo de entrada da compressão, ou pré-processamento (BM,
ou CBM);
outfile = nome do arquivo de saída da compressão (CBM);
filtfile = nome do arquivo de saída do pré-processamento e entrada da
compressão, quando é solicitada a filtragem (BM);
high = variável lógica, indica que será usado o bloco de 16x16 (TRUE) ou o
bloco 4x4 (FALSE);
filt = variável lógica, indica que será executado o pré-processamento (TRUE);
h = header do arquivo de saída da compressão;
pcmsource = variável lógica, indica que a imagem original já foi comprimida pelo
algoritmo PCM (TRUE);
savedbytes = número de bytes da imagem resultante da compressão (excluído o
cabeçalho);
inf = arquivo de entrada da descompressão (CBM);
outf = arquivo de saída da descompressão (BM);
dx = largura da imagem reconstruída, em pixels;
dy = altura da imagem reconstruída, em pixels.
PCM - Pulse Code Modulation
Na compressão PCM, adotou-se uma quantização uniforme e não adaptativa, em 16 níveis.
A codificação usa palavras de tamanho fixo de 4 bits. Como resultado, uma razão de
compressão fixa de 2:1 é obtida. O processamento é feito pixel a pixel e, portanto, não há
alteração no tamanho original da imagem.
Listam-se abaixo as rotinas implementadas no módulo SCIPCM.C:
void pcm_encode_image(char *infile,char *outfile,struct bmheadertype *h,
unsigned long int *savedbytes);
void pcm_decode_image(FILE *inf,FILE *outf,int dx,int dy),
onde,
infile = nome do arquivo de entrada da compressão, (BM);
outfile = nome do arquivo de saída da compressão (CBM);
h = header do arquivo de saída da compressão;
savedbytes = número de bytes da imagem resultante da compressão
(excluído o cabeçalho);
inf = arquivo de entrada da descompressão (CBM);
outf = arquivo de saída da descompressão (BM);
dx = largura da imagem reconstruída, em pixels;
dy = altura da imagem reconstruída, em pixels.
DPCM - Differential Pulse Code Modulation
O algoritmo DPCM foi implementado em dois modos. No primeiro modo, não há perda da
informação, ao contrário do segundo.
Na compressão DPCM, sem distorção da imagem reconstruída, não há quantização dos
erros de predição. O pixel corrente da imagem é previsto a partir do pixel anterior, segundo
a seguinte regra:
f(m,n) = f(m-1,n),
(4.5)
onde x e y representam, respectivamente, a linha e a coluna em que se encontra o pixel
corrente. Foi adotada portanto a predição uniforme linear. O erro de predição é codificado
pelo código de Huffman, estando as palavras nas seguintes variáveis:
static mhconstcodetype dpcmlowhuffman[63]: palavras para erros de baixa
magnitude, situados no intervalo (fechado) -31 a +31. Caso o erro se situe fora
deste intervalo, há composição com as palavras de uma das duas tabelas abaixo
(Apêndice C1.1);
static mhconstcodetype dpcmhighhuffmann[7]: palavras que compõem os bits
mais significativos da palavra final, que representa um erro de predição no
intervalo (fechado) -255 a -32 (Apêndice C1.2);
static mhconstcodetype dpcmhighhuffmanp[7]: idem para o intervalo (fechado)
+32 a +255 (Apêndice C1.3).
Como se pode observar, a razão de compressão obtida é variável.
Na compressão com distorções, a mesma regra de predição foi adotada, tendo sido
implementados os seguintes recursos:
•
•
quantização em 16, 8 ou 2 níveis (DM);
quantização fixa não uniforme, ou adaptativa uniforme;
A combinação dos dois itens acima é livre, com exceção da modulação delta, que deve se
restringir à quantização fixa não uniforme.
Para codificação dos erros quantizados, os códigos de Huffman listados no Apêndice C2
foram usados:
static mhconstcodetype dpcmslossyhuffman[16]: palavras que representam os
erros de predição quantizados em 16 níveis (Apêndice C2.1);
static mhconstcodetype dpcmhlossyhuffman[8]: idem, para a quantização em 8
níveis (Apêndice C2.2);
static mhconstcodetype dpcmdlossyhuffman[2]: idem, para a quantização em 2
níveis (Apêndice C2.3).
No caso da quantização fixa não uniforme, os valores representativos e os limites de cada
intervalo de quantização foram calculados a partir de estudo estatístico das imagensamostra, considerando-se as tabelas de Lloyd-Max para distribuições gaussianas (vide
Capítulo 5), contidas no Apêndice C2:
static int dpcmslossybound[16]: limites superiores (abertos) dos intervalos de
quantização em 16 níveis (Apêndice C2.1);
static int dpcmhlossybound[8]: idem, para quantização em 8 níveis (Apêndice
C2.2);
static int dpcmdlossybound[3]: idem, para modulação delta (Apêndice C2.3);
static int dpcmslossylevels[16]: valores representativos de cada intervalo de
quantização em 16 níveis (Apêndice C2.1);
static int dpcmhlossylevels[8]: idem, para quantização em 8 níveis (Apêndice
C2.2);
static int dpcmdlossylevels[2]: idem, para modulação delta (Apêndice C2.3).
No caso da quantização adaptativa, os limites dos intervalos dividem sempre a faixa de
quantização em intervalos de mesmo tamanho (quantização uniforme). Entretanto, a faixa
de valores considerada varia de acordo com as características locais da imagem. A idéia é
que existe um compromisso entre os efeitos de sobrecarga de borda e granularidade. Se a
luminância ao longo de uma linha aumenta bruscamente, implicando em altas amplitudes
dos erros de predição, o tamanho dos níveis de reconstrução deve também ser ampliado, de
maneira a reduzir a sobrecarga de borda. Ao contrário, em uma região de baixa freqüência,
o tamanho dos níveis deve ser reduzido, o que aumentará a sensibilidade da quantização e,
conseqüentemente, reduzirá o ruído granular.
As constantes abaixo contêm os fatores multiplicativos adotados na implementação de
acordo com os níveis crescentes de erros de predição (Apêndice C2.4):
static double smult[9]: fator de multiplicação dos intervalos de quantização
adaptativa para 16 níveis;
static double hmult[5]: fator de multiplicação dos intervalos de quantização
adaptativa para 8 níveis.
Foram as seguintes as rotinas implementadas no módulo SCIDPCM.C:
void dpcm_encode_image(char *infile,char *outfile,boolean lossy,
boolean adaptive,boolean high,boolean delta,
struct bmheadertype *h,
unsigned long int *savedbytes);
void dpcm_decode_image(FILE *inf,FILE *outf,int dx,int dy,boolean lossy,
boolean adaptive,boolean high,boolean delta),
onde,
infile = nome do arquivo de entrada da compressão (BM);
outfile = nome do arquivo de saída da compressão (CBM);
lossy = indica compressão com perda de informação (TRUE);
adaptive = indica compressão adaptativa (TRUE);
high = indica quantização em 16 (TRUE) ou 8 níveis (FALSE);
delta = indica quantização em 2 níveis - DM (TRUE);
h = header do arquivo de saída da compressão;
savedbytes = número de bytes da imagem resultante da compressão (excluído o
cabeçalho);
inf = arquivo de entrada da descompressão (CBM);
outf = arquivo de saída da descompressão (BM);
dx = largura da imagem reconstruída, em pixels;
dy = altura da imagem reconstruída, em pixels.
PC - Pyramid Coding
O algoritmo PC implementado utiliza as funções de redução e expansão definidas no
Capítulo 3, sendo necessária a adequação do tamanho da imagem às dimensões da janela de
convolução, o que implica quase sempre em uma imagem reconstruída de dimensões
menores do que as da original.
A codificação é feita em 8 bits/pixel para o último nível da pirâmide gaussiana e por
intermédio de palavras de tamanho variável para os níveis da pirâmide laplaciana, o que
resulta em compressão variável. Na implementação deste trabalho, são geradas pirâmides
gaussianas com 5 níveis.
As pirâmides geradas durante o processamento têm cada um dos seus níveis armazenados
no formato BM, para posteriores estudos. Os arquivos são criados no diretório corrente e
recebem os seguintes nomes:
GPYRn.BM: nível n da pirâmide gaussiana;
XGPYRn.BM: nível n da pirâmide gaussiana expandida;
LPYRn.BM: nível n da pirâmide laplaciana;
A janela de convolução da função de redução descrita no Apêndice D1 é armazenada na
variável:
static const double cwindow[5][5].
A quantização é feita adaptativamente, de acordo com o nível da pirâmide, de maneira que,
nos níveis mais altos, onde prevalecem as altas freqüências, um número maior de intervalos
é definido.Os erros são quantizados e codificados conforme os intervalos e códigos de
Huffman das tabelas abaixo (Apêndice D2):
static mhconstcodetype plossyhuffman[4][17]:códigos de Huffman para
codificação dos níveis de 1,2,3 e 4 da pirâmide, com, respectivamente, 3,5,9 e 17
níveis de quantização;
static int plossybound[4][17]: limites superiores (abertos) dos intervalos de
quantização para os níveis 1,2 3 e 4 da pirâmide;
static int plossylevels[4][17]: valores representativos dos intervalos de
quantização para os níveis 1,2 3 e 4 da pirâmide;
As seguintes funções realizam a compressão e descompressão PC (SCIPYR.C):
void lpyr_encode_image(char *infile,char *outfile,
struct bmheadertype *h,
unsigned long int *savedbytes);
void lpyr_decode_image(FILE *inf,FILE *outf,struct bmheadertype *header),
onde,
infile = nome do arquivo de entrada da compressão (BM);
outfile = nome do arquivo de saída da compressão (CBM);
h = header do arquivo de saída da compressão;
savedbytes = número de bytes da imagem resultante da compressão (excluído o
cabeçalho);
inf = arquivo de entrada da descompressão (CBM);
outf = arquivo de saída da descompressão (BM).
DCT - Discrete Cosine Transform Coding
Na compressão por transformada, optou-se pela tranformada do cosseno, devido a sua
ampla utilização. A quantização é feita através de matriz de alocação de 64 bits (Apêndice
E1) e o tamanho do bloco adotado foi de 8x8 pixels. Os limites dos intervalos de
quantização e seus valores representativos foram obtidos através de estudos das imagens
consideradas neste trabalho (vide Capítulo 5). São as seguintes as variáveis que interferem
na quantização:
static tblocktype lowqtable: matriz de alocação de bits;
static qtabletype qbounds: tabela de limites dos intervalos de quantização;
static qtabletype qvalues: tabela contendo os valores representativos de cada
intervalo.
Os valores que preenchem as variáveis acima estão disponíveis no arquivo de dados:
SCIDTCDT.DAT.
A razão de compressão final é fixa:
Rc
=
=
[(8 bits/pixel) * 64 pixels] / (64 bits)
8:1, ou 1 bit/pixel
(4.6)
As seguintes funções realizam a compressão e descompressão DCT (SCIDCT.C):
void dct_encode_image(char *infile,char *outfile,struct bmheadertype *h,
unsigned long int *savedbytes);
void dct_decode_image(FILE *inf,FILE *outf,int dx,int dy),
onde,
infile = nome do arquivo de entrada da compressão (BM);
outfile = nome do arquivo de saída da compressão (CBM);
h = header do arquivo de saída da compressão;
savedbytes = número de bytes da imagem resultante da compressão (excluído o
cabeçalho);
inf = arquivo de entrada da descompressão (CBM);
outf = arquivo de saída da descompressão (BM);
dx = largura da imagem reconstruída, em pixels;
dy = altura da imagem reconstruída, em pixels.
Cabe observar que, por razões de simplificação e, dado que o algoritmo JPEG utiliza o
algoritmo DCT, não foi implementada a transformada rápida do cosseno neste sistema, o
que implica em um aumento substancial dos tempos de compressão e descompressão
obtidos. Entretanto, dada a estrutura modularizada do sistema, esta poderá ser futuramente
implementada.
VQ - Vector Quantization
A quantização vetorial foi aplicada de duas maneiras diferentes. Como primeira alternativa,
implementou-se o que se convencionou chamar de quantização vetorial pura, ou seja
aplicada diretamente sobre a imagem, não efetuando nenhum tipo de mapeamento. Numa
segunda variação, a quantização vetorial foi associada à truncagem de blocos (BTC). Em
ambos os casos, o tamanho da imagem resultante pode apresentar pequena diferença em
relação ao tamanho da imagem original, devido ao fato do algoritmo trabalhar em blocos de
tamanho definido.
Ambas as implementações considereram blocos de tamanho 4x4 pixels e dicionários (ou
alfabetos) de 256 vetores. Os alfabetos foram gerados a partir das imagens-amostras,
através do algoritmo LBG detalhado no Capítulo 3.
VQ Pura
Na quantização vetorial pura divide-se a imagem em blocos de pixels. A cada um destes
blocos se associa um único bloco do dicionário de vetores, o qual representará o bloco
original na imagem reconstruída. Os 256 blocos são codificados pela utilização de palavras
de tamanho fixo de 8 bits, o que resulta na seguinte razão de compressão fixa:
Rc = (16 pixels x 8 bits/pixel) / 8 bits = 16:1, ou 0.5 bits/pixel.
(4.7)
A escolha do vetor mais próximo ao original se dá pelo critério do menor MSE calculado.
O Apêndice F1 apresenta o dicionário de vetores otimizado pelo algoritmo LBG,
considerando-se os vetores das imagens-amostras. O dicionário é armazenado no arquivo
SCIVQVQ.ALF e é carregado em tempo de execução na variável:
static alphatype alphaimg
VQ/BTC
Aqui são necessários dois dicionários de vetores, o primeiro representativo dos mapas de
bits resultantes da aplicação da truncagem de blocos e, portanto, com dimensão 16, o
segundo, representativo da média e variância calculadas para cada bloco, e, em
conseqüência, bidimensional. Os 256 blocos de cada dicionário também são codificados
com palavras de tamanho fixo 8 bits, o que resulta em razão de compressão igual a:
Rc = 2 x (16 pixels x 8bits/pixel) / 8 bits = 8:1, ou 1,0 bit/pixel.
(4.8)
Para os vetores dos parâmetros estatísticos, é usado o critério do menor MSE. Para os
vetores do mapa de bits, basta que se determine o número de pixels com valores
coincidentes, optando-se por aquele vetor que apresentar o maior (no caso de empate,
escolhe-se o último vetor selecionado).
O Apêndice F2 apresenta os alfabetos VQ/BTC obtidos a partir da otimização LBG para as
amostras. Tais alfabetos são carregados nas variáveis listadas abaixo, a partir dos dados
constantes nos arquivos SCIVQBTB.ALF e SCIVQBTP.ALF.
static alphatype alphaimg
static ralphatype alphabtc
4.4 Conclusões
No presente capítulo, foram apresentados os principais elementos da interface das rotinas
de compressão de imagens. Foram também relacionados os algoritmos implementados e
definida a parametrização selecionada para a aplicação estudada.
O objetivo da implementação foi o de fornecer um conjunto básico de rotinas de
compressão de imagens para uso genérico, adequando-as ao caso específico das imagens-
amostras deste trabalho. As rotinas podem ser utilizadas com outras imagens, sem que se
proceda a um ajuste fino dos seus parâmetros, oferecendo, na maioria dos casos, resultados
satisfatórios. As variações implementadas dentro dos algoritmos procuraram indicar alguns
dos possíveis refinamentos, sem pretender, entretanto, esgotar todo o seu universo.
A interface PixelWare possibilita ao usuário realizar, dentro do mesmo ambiente, uma
gama variada de operações de pré e pós-processamentos, melhorando o resultado final da
compressão. No nível de linha de comandos DOS, o sistema apresenta-se com interface
mais simples e de utilização mais rápida.
No capítulo seguinte são discutidos os resultados obtidos com a aplicação dos algoritmos a
imagens de documentos históricos.
5. Resultados
Este capítulo descreve a aplicação das rotinas de compressão de imagens selecionadas a um
conjunto de imagens de documentos históricos. Para otimização dos resultados, os
parâmetros dos algoritmos foram ajustados a este conjunto de imagens, a partir de estudos
estatísticos realizados nos ensaios. Em seguida, compararam-se os resultados obtidos, sob
três aspectos: tempos normalizados de compressão e descompressão, razão de compressão e
distorção da imagem reconstruída. Como referência, o algoritmo JPEG também foi
aplicado a cada uma das imagens.
As imagens originais representadas na Figura 5.1 (8 bits/pixel) foram obtidas através de
scanner, a 150 dpi. As imagens da Figura 5.1 não sofreram qualquer operação de préprocessamento, embora, em aplicação real, fosse desejável que a tais imagens fosse
aplicado algum tipo de transformação da escala de cinza, de modo a aumentar a sua
legibilidade e melhor adequá-las aos algoritmos. No caso dos algoritmos RLC e MREAD,
às imagens originais foi aplicada transformação por limiar, gerando o conjunto de imagensamostras binárias da Figura 5.2 (1 bit/pixel).
Observe-se que as imagens-amostras são produto do recorte das imagens dos documentos
inteiros, não mostrados aqui, por razões de simplificação. Os resultados apresentados,
entretanto, foram obtidos a partir do tratamento destas últimas.
5.1 Imagens Binárias
As imagens da figura 5.2 foram comprimidas pelos algoritmos RLC e MREAD. A Tabela
5.1 apresenta os resultados obtidos para a Imagem 1, considerando-se as variações
implementadas no algoritmo MREAD (código modificado de Huffman para seqüências de
brancos e pretos). Observe-se que os valores da tabela se referem ao documento inteiro e
não apenas à fração ilustrada na Figura 5.2. Os tempos de compressão e descompressão
foram medidos sob as mesmas condições de processamento, em um microcomputador PC386, com 8 Mbytes de RAM, 25 MHz, co-processador 80387 e unidade de disco rígido de
80 Mbytes.
As razões de compressão apresentadas foram calculadas com base na entropia real da
imagem original, 1 bit/pixel e não com base na entropia das imagens BM, 8 bits/pixel. Se
for considerada esta última, as razões de compressão finais deverão ser multiplicadas por
oito, o que representa a redução real no tamanho do arquivo BM que contém a imagem (em
cerca de 16 vezes).
Como já esperado, o algoritmo MREAD mostrou-se superior, com relação à entropia final
da imagem. Isto se deve, principalmente, à natureza bidimensional deste algoritmo, que
explora a correlação existente entre duas linhas sucessivas da imagem.
Foi verificado que, na maioria das vezes, os modos de passagem e vertical (Capítulo 3) são
acionados. Como a codificação destes modos é mais rápida (não há necessidade de se
realizar pesquisa na tabela de Huffman), há uma redução do tempo de compressão e
descompressão, com relação ao algoritmo RLC, que efetua estas consultas a cada seqüência
de brancos ou pretos.
Para o conjunto de imagens utilizado, observou-se uma discreta superioridade da tabela de
Huffman para seqüências de pretos no algoritmo MREAD. O uso de uma ou outra é
bastante dependente da imagem (ou do conjunto de imagens) e é interessante que se
proceda a um estudo preliminar, antes de se optar por uma delas. Em linhas gerais, a tabela
de pretos é mais recomendada para documentos que apresentem muitas regiões de altas
freqüências,o que favorece a codificação de pequenos comprimentos a0a1 e a1a2.
Ambos, RLC e MREAD são algoritmos preservadores de informação, não havendo
portanto diferença entre as imagens original e reconstruída (MSE = 0).
Figura 5.1 - Recortes das imagens-amostras originais (256x256 pixels, 8 bits/pixel).
Figura 5.2 - Recortes das imagens-amostras originais (256x256 pixels, 1 bit/pixel).
Algoritmo
RLC
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
452x457
13515
Rc
1,91:1
Entropia
0,52
MSE
0
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
0,45
0,32
0,23
0,28
0,23
0,28
---------
MREAD/b
452x457
10648
2,42:1
0,41
0
---------
MREAD/w
452x457
11786
2,19:1
0,46
0
---------
Tabela 5.1 - Resultados da compressão e decompressão da Imagem 1, (206564 bytes,
452x457 pixels, 1 bit/pixel).
5.2 Imagens com Múltiplos Níveis de Cinza
Às imagens da Figura 5.1 foram aplicados os outros algoritmos implementados neste
trabalho, com todas as suas variações. As condições de processamento definidas no item
anterior foram mantidas. A Tabela 5.2 resume os resultados obtidos para a Imagem 1.
Algoritmo
BTC/s
BTC/h
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
452x456
448x448
51528
26656
Rc
4,00:1
7,53:1
Entropia
2,00
1,06
MSE
94,6
224,5
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
0,27
0,27
0,32
0,20
26,3
22,5
BTC/f/s
452x456
51528
4,00:1
2,0
94,6
26,3
1,93
0,30
BTC/f/h
448x448
26656
7,53:1
1,06
224,5
22,5
1,72
0,22
BTC/p/s
452x456
38646
5,33:1
1,50
245,6
22,2
0,57
0,47
BTC/p/h
448x448
25872
7,76:1
1,03
474,8
19,3
0,5
0,42
PCM
452x456
103056
2,00:1
4,00
19,9
33,1
0,23
0,25
DPCM/i
DPCM/l/f/s
452x457
452x457
202544
88966
1,02:1
2,32:1
7,84
3,88
0
91,2
--------26,5
2,00
1,12
3,37
1,52
DPCM/l/f/h
452x457
68510
3,01:1
2,65
146,8
24,4
0,91
1,17
DPCM/l/a/s
452x457
82726
2,50:1
3,2
95,8
26,2
1,18
1,63
DPCM/l/a/h
452x457
69487
2,97:1
2,69
155,3
24,1
1,10
1,42
DPCM/l/d
452x457
26616
7,76:1
1,03
430,2
19,7
0,57
0,50
PC
449x449
48010
4,20:1
1,90
138,0
24,6
18,63
8,87
DCT(*)
256x256
8182
8,00:1
1,00
366,3
20,4
18,01
19,74
VQ/i
452x456
12882
16,00:1
0,50
177,7
23,6
26,87
0,17
VQ/b
452x456
25764
8,00:1
1,00
290,1
21,4
20,60
0,28
JPEGa
JPEGb
452x457
452x457
90428
50350
2,28:1
4,10:1
3,48
1,95
11,4
51,0
35,4
28,9
0,47
0,47
0,47
0,46
JPEGc
452x457
6784
30,40:1
0,26
419,2
19,8
0,38
0,28
Tabela 5.2 - Resultados da compressão e descompressão da Imagem 1, (206564 bytes,
452x457 pixels, 8 bit/pixel). (*) Algoritmo DCT aplicado à imagem 256x256 da Figura 5.2,
resultados estimados.
PCM - Pulse Code Modulation
O algoritmo PCM comprimiu as imagens a uma taxa de 2:1, a menor obtida nos ensaios.
Naturalmente, esta taxa é muito pequena para que se aplique o algoritmo isoladamente,
embora a qualidade da imagem reconstruída tenha sido considerada boa. De fato, a coluna
MSE indica um valor reduzido para esta grandeza, que dá uma idéia do grau de desvio dos
níveis de cinza dos pixels da imagem (Capítulo 2). Uma vez que tais erros estão limitados à
metade do intervalo de quantização, no caso, oito, o valor do MSE tende a ser pequeno.
A Figura 5.3 ilustra o resultado da compressão da Imagem 1. Um leve efeito de falsos
contornos, causado pela quantização dos níveis de cinza, pode ser percebido na região
superior da imagem, onde há uma predominância de níveis de cinza mais elevados.
Figura 5.3 - Imagem 1, reconstruída , PCM (2 bits/pixel).
BTC - Block Truncation Coding
Algoritmo
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
Rc
Entropia
MSE
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
BTC/s
452x456
51528
4,00:1
2,00
94,6
26,3
0,27
0,32
BTC/h
448x448
26656
7,53:1
1,06
224,5
22,5
0,27
0,20
BTC/f/s
452x456
51528
4,00:1
2,0
94,6
26,3
1,93
0,30
BTC/f/h
448x448
26656
7,53:1
1,06
224,5
22,5
1,72
0,22
BTC/p/s
452x456
38646
5,33:1
1,50
245,6
22,2
0,57
0,47
BTC/p/h
448x448
25872
7,76:1
1,03
474,8
19,3
0,5
0,42
Tabela 5.3 - Resultados da compressão e descompressão da Imagem 1, BTC, (206564
bytes, 452x457 pixels, 8 bit/pixel).
O algoritmo BTC apresentou resultados mais favoráveis que o anterior, com relação à
compressão obtida, com razões de compressão variáveis entre 4:1 e 7,76:1. A Figura 5.4
mostra o resultado das seis variações implementadas, para a Imagem 1 da Figura 5.1.
Os tempos de compressão e, especialmente o de descompressão, foram considerados
satisfatórios. Os melhores resultados foram obtidos quando se usaram blocos de tamanho
8x8 pixels, pelo fato de haver menos blocos a processar. O aumento do tempo no
processamento devido à filtragem passa-baixas não chegou a inviabilizar a sua utilização,
visto que o tempo de compressão não é um fator crítico neste trabalho e que não há pósprocessamento envolvido. Entretanto, com relação à qualidade da imagem reconstruída,
não se observou significativa diferença entre o resultado das compressões sem e com préprocessamento.
Figura 5.4 - Imagem 1, reconstruída , BTC, a) 8x8 (2 bits/pixel); b) 4x4, associado a PCM
(1,5 bits/pixel); c) 4x4, pré-processado (2 bits/pixel); d) 16x16 (1,06 bits/pixel); e) 16x16,
associado a PCM (1,03 bits/pixel); f) 16x16, pré-processado (1,06 bits/pixel).
Os ensaios com blocos de tamanho 4x4 pixels não associados ao algoritmo PCM, embora
proporcionando razões de compressão inferiores, apresentaram os melhores resultados, no
que se refere à qualidade da imagem. Ao contrário das imagens resultantes do
processamento de blocos 8x8, é quase imperceptível o efeito de blocagem, característico do
algoritmo BTC. Para aplicações que exijam maiores razões de compressão, a utilização dos
blocos 8x8 pode ser viável, tendo em vista a legibilidade ainda aceitável das imagens
obtidas.
A combinação BTC/PCM não acrescentou grandes avanços em termos de razão de
compressão e, ao mesmo tempo, aumentou o tempo de descompressão e a qualidade final,
ressaltando o efeito de blocagem, tanto para blocos 8x8, quanto para blocos 4x4. Isto
ocorreu na medida em que a imagem com apenas 16 níveis teve suavizadas as diferenças
estatísticas dentro dos blocos, formando grandes áreas uniformes. A qualidade final da
imagem para blocos 8x8 foi considerada inadequada para aplicações reais.
DPCM - Differential Pulse Code Modulation
Algoritmo
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
DPCM/i
DPCM/l/f/s
452x457
452x457
202544
88966
1,02:1
2,32:1
7,84
3,88
0
91,2
DPCM/l/f/h
452x457
68510
3,01:1
2,65
DPCM/l/a/s
452x457
82726
2,50:1
3,2
DPCM/l/a/h
452x457
69487
2,97:1
DPCM/l/d
452x457
26616
7,76:1
Rc
Entropia
MSE
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
--------26,5
2,00
1,12
3,37
1,52
146,8
24,4
0,91
1,17
95,8
26,2
1,18
1,63
2,69
155,3
24,1
1,10
1,42
1,03
430,2
19,7
0,57
0,50
Tabela 5.4 - Resultados da compressão e descompressão da Imagem 1, DPCM, (206564
bytes, 452x457 pixels, 8 bit/pixel).
O algoritmo DPCM, juntamente com o BTC, foi o implementado com o maior número de
variações. A Figura 5.5 ilustra as imagens resultantes da compressão da Imagem 1 da
Figura 5.1.
Os códigos utilizados na codificação dos erros de predição foram definidos através da
observação das curvas de distribuição dos erros, que mostrou comportamento gaussiano
(Figura 5.6). Os limites e valores representativos dos intervalos de quantização foram
obtidos pela tabela de quantizadores de Lloyd-Max [Jain89], adequada aos parâmetros
média e variância dos erros das imagens-amostras.
As razões de compressão proporcionadas pelo algoritmo DPCM são muito baixas para que
este possa ser utilizado isoladamente em uma aplicação (exceto no caso da modulação delta
- DM). Melhores desempenhos poderiam ser obtidos, se fosse combinado com outras
técnicas, como por exemplo a compressão por transformadas (o algoritmo JPEG faz uso de
técnica preditiva na codificação dos coeficientes DC). Também com relação aos tempos de
processamento, os resultados não são satisfatórios.
A qualidade final das imagens pode ser considerada boa. A compressão DM deixa a desejar
neste aspecto, apesar da maior razão de compressão. Pode-se observar na Figura 5.5d o
efeito de sobrecarga de borda (Capítulo 3), que provoca borramento nas regiões de fronteira
entre baixas e altas amplitudes. No caso da Figura 5.5a, a imagem reconstruída é idêntica à
original, mas a entropia final é praticamente a mesma, com um ganho muito pequeno em
termos de espaço de memória.
A quantização adaptativa, para todo o conjunto de imagens, aumentou em cerca de 15% a
razão de compressão, sem alterar significativamente os tempos de processamento e a
qualidade final das imagens.
Figura 5.5 - Imagem 1 , reconstruída, DPCM, a) sem distorção (7,84 bits/pixel); b)
quantização fixa, em 16 níveis (3,88 bits/pixel); c) quantização fixa, em 8 níveis, (2,65
bits/pixel); d) quantização fixa, em dois níveis (DM) (1,03 bits/pixel); e) quantização
adaptativa, em 16 níveis (3,2 bits/pixel); f) quantização.adaptativa, em 8 níveis (2,69
bits/pixel).
-127
127
Figura 5.6 - Distribuição típica dos erros de predição nas imagens-amostras.
PC - Pyramid Coding
Algoritmo
PC
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
449x449
48010
Rc
4,20:1
Entropia
1,90
MSE
138,0
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
18,63
8,87
24,6
Tabela 5.5 - Resultados da compressão e descompressão da Imagem 1, PC, (206564 bytes,
452x457 pixels, 8 bit/pixel).
A compressão piramidal (PC), considerada por alguns autores como um algoritmo híbrido
de primeira geração [KIK85], apresentou resultados medianos em termos de qualidade de
imagem e praticamente inaceitáveis em termos de tempo de processamento, embora seja
bastante interessante sob o ponto de vista acadêmico. A aplicação deste algoritmo à
Imagem 1 da Figura 5.1 originou as pirâmides da Figura 5.7.
A pirâmide gaussiana, que é produto da aplicação da função de redução (Capítulo 3),
introduz uma filtragem passa-baixas sucessiva, em cada nível. O último nível desta
pirâmide é codificado juntamente com os restantes da pirâmide laplaciana. Esta última é o
resultado da operação de subtração entre a primeira e a pirâmide gaussiana expandida.
Observa-se que a pirâmide laplaciana retém apenas a informação de alta freqüência a cada
nível, podendo ser mais eficientemente codificada por técnica preditiva. A Imagem 1 da
Figura 5.1 reconstruída por este algoritmo é ilustrada na Figura 5.8. Note-se que as
dimensões finais desta imagem foram reduzidas mais significativamente do que nos outros
algoritmos.
DCT - Discrete Cosine Transform
Algoritmo
DCT(*)
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
256x256
8182
Rc
8,00:1
Entropia
1,00
MSE
366,3
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
18,01
19,74
20,4
Tabela 5.6 - Resultados da compressão e descompressão da Imagem 1, DCT, (206564
bytes, 452x457 pixels, 8 bit/pixel).
O algoritmo DCT foi implementado em versão simplificada, não tendo sido visados baixos
tempos de compressão e descompressão. Portanto, os resultados obtidos não devem ser
diretamente comparados com os demais, para fins de determinação de desempenho relativo.
No caso da transformada do cosseno, será mais adequada a comparação com os resultados
do algoritmo JPEG.
A matriz de alocação de bits (Apêndice E) foi determinada com base nas referências
bibliográficas [Lim90], [Jain89] ,[Cost93], para uma razão de compressão intermediária
(8:1). Para cada valor desta matriz (e não para cada posição) foi definido um quantizador
diferente. Portanto, foi necessário o estabelecimento de sete quantizadores, para 1,2,3,4,5,6
e 8 bits.
Figura 5.7 - Pirâmides da compressão PC, Imagem 1.
Figura 5.8 - Imagem 1, reconstruída, PC (1,9 bits/pixel).
Idealmente, um quantizador teria que ser definido para cada posição da matriz, uma vez que
cada uma delas apresenta diferentes médias e variâncias. No sentido de se simplificar a
definição dos quantizadores, adotaram-se os valores médios destes parâmetros,
consideradas aquelas posições do bloco quantizadas com uma mesma quantidade de bits.
Na definição dos limites e valores representativos de cada intervalo foram usadas as tabelas
de quantização de Lloyd-Max [Jain89], para distribuição gaussiana, com o devido ajuste de
média e variância (valores indicados no Apêndice E).
O resultado da compressão da Imagem 1, ilustrado na Figura 5.9, mostra uma deterioração
da imagem, com a introdução de ruído granular, causado pela quantização e pelo descarte
dos coeficientes do bloco. Para a razão de compressão final obtida, a qualidade da imagem
reconstruída pode ser considerada aceitável.
Figura 5.9 - Imagem 1, reconstruída, DCT (1 bit/pixel).
VQ - Vector Quantization
O algoritmo VQ foi aquele que, dentre os implementados, apresentou os melhores
resultados em termos de razão de compressão, chegando a 16:1, sem que a qualidade final
fosse seriamente comprometida.
Algoritmo
VQ/i
VQ/b
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
452x456
452x456
12882
25764
Rc
16,00:1
8,00:1
Entropia
0,50
1,00
MSE
177,7
290,1
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
26,87
20,60
0,17
0,28
23,6
21,4
Tabela 5.6 - Resultados da compressão e descompressão da Imagem 1, VQ, (206564 bytes,
452x457 pixels, 8 bit/pixel).
A quantização vetorial pura apresenta a vantagem da facilidade de implementação e dos
altos níveis de compressão. A VQ associada ao algoritmo BTC, além de proporcionar
compressões de apenas oito vezes, apresentou maior deterioração da imagem, ainda que
sem a introdução do efeito de blocagem. Entretanto, mostrou-se mais eficiente no
tratamento de imagens que não integraram o conjunto de amostras usado na otimização dos
alfabetos e apresentou menores tempos de compressão. A Figura 5.10 ilustra os resultados
da utilização das duas variações da quantização vetorial implementadas. A Figura 5.11
mostra os resultados da compressão e descompressão de uma imagem de documento
estranha ao conjunto que originou os alfabetos.
Figura 5.10 - Imagem 1, reconstruída, VQ, a) pura (0,5 bits/pixel); b) associada a BTC (1
bit/pixel).
Com relação aos tempos de processamento, os valores obtidos na descompressão foram
bastante reduzidos, uma vez que, não é necessário grande volume de cálculos para o caso
VQ/BTC e nenhum cálculo no caso de VQ pura (apenas a consulta à tabela de vetores
representativos). O tempo de compressão elevado, em função da determinação do vetor
mais adequado do dicionário não é crítico e não inviabiliza portanto a utilização prática do
algoritmo.
Figura 5.11- Imagem 6, a) original; b) VQ pura (0,5 bits/pixel); c) associada a BTC (1
bit/pixel).
JPEG - Joint Photographic Experts Group
Algoritmo
Dimensões
Tamanho
Imagem
Imagem
Final
Reconstr.
Comprimida
(bits/pixel)
(pixels)
. (bytes)
JPEGa
452x457
90428
2,28:1
3,48
11,4
JPEGb
JPEGc
452x457
452x457
50350
6784
4,10:1
30,40:1
1,95
0,26
51,0
419,2
Rc
Entropia
MSE
SNR
Tempo
Tempo
(dB)
Compr.
Desc.
(min.)
(min.)
35,4
0,47
0,47
28,9
19,8
0,47
0,38
0,46
0,28
Tabela 5.7 - Resultados da compressão e descompressão da Imagem 1, JPEG, (206564
bytes, 452x457 pixels, 8 bit/pixel).
As imagens-amostras também foram comprimidas pelo algoritmo JPEG, disponível no
utilitário Image Alchemy [Hand91]. O formato permite a compressão com ajuste da
qualidade final da imagem desejada (e conseqüentemente da razão de compressão). Para
comparação com os resultados obtidos pelos outros algoritmos, três níveis foram definidos,
próximos ao mínimo e máximo de compressão possíveis e a um valor intermediário. A
Tabela 5.2 apresenta tais resultados.
Os tempos de compressão e descompressão estão dentro dos valores apresentados por
alguns dos algoritmos implementados e são considerados baixos. O ensaio JPEGa foi o que
apresentou as maiores entropias, comprimindo a Imagem 1 a uma razão de 2,28:1,
comparável à dos algoritmos PCM e DPCM, mas com melhores índices de distorção. O
ensaio JPEGb, com uma razão de compressão intermediária, apresenta também aceitáveis
índices de distorção, semelhantes aos obtidos pelo algoritmo BTC com blocos de tamanho
4x4 pixels. Já o terceiro ensaio, JPEGc, maximizou a razão de compressão chegando a
atingir os 32:1. Entretanto, uma inspeção visual desqualifica as imagens reconstruídas,
tendo em vista a grande distorção introduzida nas mesmas. A Figura 5.12 ilustra os
resultados dos três ensaios.
Figura 5.12 - Imagem 1, reconstruída, JPEG, a) 3,48 bits/pixel; b) 1,95 bits/pixel; c) 0,26
bits/pixel.
5.3 Banco de Dados de Imagens de Documentos Históricos
A conservação e restauração de documentos históricos e trabalhos de arte em papel tem
como primeira etapa a elaboração de diagnóstico do estado de conservação do objeto
[ASL+92], [ALSC93]. Esta fase consiste de análises visual, física e química e tem como
objetivo a determinação das técnicas a serem empregadas no trabalho. A restauração é
documentada através de fotografias e relatórios técnicos, que são, geralmente, armazenados
e manipulados manualmente. Conseqüentemente, o tempo necessário à recuperação de
informações, durante o processo de restauração, é elevado. Por este motivo, há interesse em
se utilizar um sistema de processamento de imagens para armazenamento de informações
gráficas e alfanuméricas. Este sistema permitiria acesso rápido aos dados e disponibilizaria
recursos de pesquisa com referências cruzadas, importantes durante o trabalho. O sistema
poderia ainda integrar recursos de realce de imagens, permitindo, por exemplo, que fosse
ressaltado o contraste de um determinado documento.
A Figura 5.13 descreve a arquitetura do sistema proposto. A interface com o usuário
oferece recursos básicos de scanning, processamento de imagens e acesso à base de dados
alfanuméricos. A base de dados é dividida em duas, uma para o armazenamento dos dados
convencionais relacionados aos documentos, e outra para o armazenamento das imagens
dos documentos. Os dados alfanuméricos são gerenciados através de procedimentos
convencionais de DBMS (Database Managing System), enquanto que as imagens são
armazenadas em campos longos e manipuladas por rotinas especiais para realce,
compressão e exibição.
Figura 5.13 - Arquitetura do sistema proposto [ASL+92].
Naturalmente, é desejável que o espaço de memória ocupado pelas imagens seja o menor
possível, reduzindo-se os custos de implantação do sistema. Por outro lado, a
operacionalidade do sistema exige baixos tempos de recuperação das imagens. Finalmente,
a qualidade das imagens reconstruídas deve permitir que as informações gráficas
necessárias ao trabalho de conservação sejam obtidas. Dentre os algoritmos implementados,
a quantização vetorial pura é a que melhor se adequa à restrições acima. Dentro do universo
de documentos disponíveis, seriam definidos alguns para compor a massa de amostras
usada na otimização do dicionário de vetores (acredita-se que cerca de 6 documentos
seriam suficientes). Esta escolha poderia seguir um critério de classificação de documentos,
que procurasse agrupá-los de acordo com suas características (manuscritos, documentos
contendo desenhos, etc.). Uma vez definidos tais documentos, as imagens seriam obtidas e
seria gerado o dicionário, a partir do qual todas as imagens seriam comprimidas, reduzindose em 16 vezes o espaço necessário ao seu armazenamento. As Figuras 5.14 a 5.19 ilustram
o resultado da compressão e descompressão VQ pura das imagens-amostras adotadas neste
trabalho.
Figura 5.14 - Imagem 1, reconstruída (452x456 pixels, 0,5 bits/pixel).
Figura 5.15 - Imagem 2, reconstruída (545x460 pixels, 0,5 bits/pixel).
Figura 5.16 - Imagem 3, reconstruída (448x460 pixels, 0,5 bits/pixel).
Figura 5.17 - Imagem 4, reconstruída (545x492 pixels, 0,5 bits/pixel).
Figura 5.18 - Imagem 5, reconstruída (557x444 pixels, 0,5 bits/pixel).
Figura 5.19 - Imagem 6, reconstruída (358x465 pixels, 0,5 bits/pixel).
5.3 Conclusões
Foram implementados ao todo oito algoritmos de compressão de imagens, sendo dois deles
utilizados com imagens binárias e o restante com imagens de múltiplos níveis de cinza.
Estes algoritmos foram testados com um conjunto de imagens de documentos históricos e
tiveram seus parâmetros de operação ajustados às imagens-amostras. Os resultados foram
compilados e o desempenho dos algoritmos em termos de velocidade de processamento,
qualidade das imagens e grau de compressão foi analisado.
No caso das imagens binárias, o algoritmo MREAD mostrou ser mais eficiente que o
algoritmo RLC, como já esperado, devido a sua capacidade de explorar a correlação entre
linhas subseqüentes da imagem. A razão de compressão líquida obtida esteve em torno dos
2:1, sendo que em ambos os casos não há distorção entre as imagens originais e as
reconstruídas. No caso dos arquivos BM, a redução real no tamanho dos arquivos chega aos
16:1, devido às características deste formato. Os tempos de compressão e descompressão
foram considerados baixos.
Para as imagens com múltiplos níveis de cinza, pode-se classificar os algoritmos em três
diferentes grupos, de acordo com as razões de compressão obtidas. Os algoritmos menos
evoluídos estão no primeiro grupo, com razões de compressão em torno dos 2:1. São eles
PCM e DPCM, nas suas diversas variações, excetuando-se a chamada modulação delta
(DM). Concluiu-se que tais algoritmos não devem ser usados isoladamente, devido a seu
baixo desempenho, sendo recomendáveis apenas em conjunto com outros elementos de
codificação, como no caso do algoritmo JPEG para os coeficiente DC, que são codificados
preditivamente (Capítulo 3). O segundo grupo é o dos algoritmos que proporcionam razões
de compressão de 4:1 a 8:1, como os algoritmos BTC, DCT, PC e DPCM (DM). Para estes,
a qualidade das imagens reconstruídas, de uma maneira geral; foi considerada satisfatória,
assim como as razões de compressão obtidas. No caso dos algoritmos PC e DCT, os tempos
de processamento mostraram-se proibitivos, sendo a sua utilização possível apenas após
terem sofrido otimizações em sua implementação. O terceiro e último grupo é composto
pelos algoritmos de mais alta performance, a quantização vetorial e o algoritmo JPEG, este
último não implementado, servindo apenas como referência. Com razões de compressão
variáveis entre os 8:1 e os 16:1, tais algoritmos conseguem reunir ao mesmo tempo
velocidade de processamento (pelo menos no caso da descompressão, que é essencial), boa
qualidade das imagens reconstruídas e facilidade de implementação (no caso da
quantização vetorial).
Como aplicação, foi proposto um sistema para armazenamento de dados referentes a
documentos históricos. Os dados gerenciados por este sistema seriam gráficos (imagens) e
alfanuméricos (informações sobre o processo de conservação dos documentos).
Observando-se as restrições impostas pela aplicação (baixos tempos de recuperação, altas
razões de compressão e adequada qualidade final), indicou-se a quantização vetorial pura
para compressão das imagens. As imagens reconstruídas dos documentos usados como
amostras neste trabalho, resultantes da aplicação deste algoritmo, foram apresentadas.
6. CONCLUSÕES
O objetivo deste trabalho foi o de se proceder a um estudo extensivo das técnicas de
compressão de imagens mais adequadas a uma aplicação prática que vise exclusivamente
ao seu armazenamento e recuperação, tal como seria um banco de dados de imagens de
documentos históricos. Dentro desta proposta, foram abordados os conceitos fundamentais
do Processamento Digital de Imagens relacionados ao tema e analisaram-se diversos
algoritmos propostos durante as duas últimas décadas, além de suas mais recentes
evoluções. A partir deste estudo, foram definidos aqueles algoritmos que seriam
implementados. Estes algoritmos foram escolhidos basicamente por características como
simplicidade de implementação, facilidade de parametrização em função de diferentes
conjuntos de imagens, tempos de descompressão (ou recuperação) menos elevados, altas
razões de compressão e distorções reduzidas das imagens reconstruídas em relação às
originais. Outros aspectos serviram como balizadores do estudo, além destes já
mencionados: procurou-se também realizar uma investigação sobre métodos mais
modernos, como os de segunda geração e sobre os mecanismos de funcionamento do
sistema visual humano, de maneira a se compreender como tais técnicas foram idealizadas
e como elas exploram estes mecanismos.
Foram apresentados os conceitos envolvidos com a compressão de imagens, e a descrição
do funcionamento do sistema visual humano. Mostrou-se que o mecanismo de percepção
dos sinais visuais apresenta propriedades que podem ser exploradas pelos algoritmos de
compressão de imagens. O componente que introduz uma filtragem passa-baixas, em
função da aberração esférica e da imperfeição da lente do olho, provoca um borramento da
imagem original e permite o descarte de uma determinada informação de bordas e ruídos. O
caráter logarítmico da percepção relativa de luminância, ilustra como as regiões de alta
freqüência são mascaradas de acordo com a luminância de fundo, enquanto que a resposta
espacial das células da retina indica uma faixa de freqüência de percepção preferencial. A
especialização das células do córtex visual revela a presença de diferentes padrões de
sensibilização das mesmas, incluindo formas e direções definidas para cada tipo de célula,
o que sugere a decomposição das imagens em componentes direcionais e a codificação
destes em separado.
A abordagem da teoria de compressão de imagens definiu o processo, dividindo-o nas
etapas de mapeamento, quantização e codificação. A análise de tais etapas indicou os
pontos onde ocorre a redução da entropia da imagem e, em alguns casos, a perda de
qualidade da mesma em relação à original. Foi apresentada a quantização de Lloyd-Max,
utilizada neste trabalho, bem como os algoritmos de geração de códigos de Huffman e
Lempel-Ziv. Parâmetros de medida de distorção foram definidos.
As técnicas selecionadas foram implementadas, em sua maioria, em versões básicas, sem
que fosse feito um esforço intensivo de otimização de desempenho, devido ao grande
número de algoritmos e variações selecionados. Implementaram-se ao todo oito algoritmos
de compressão e descompressão de imagens, com 20 variações: Run Length Coding (RLC),
Modified Realative Element Address Designate (MREAD), Pulse Code Modulation (PCM),
Differential Pulse Code Modulation (DPCM), Block Truncation (BTC), Pyramid Coding
(PC), Discrete Cosine Transform (DCT) e Vector Quantization (VQ). Estes algoritmos
podem ser, a partir deste trabalho, otimizados e adaptados ou ainda combinados entre si ou
com outras técnicas, melhorando-se os resultados obtidos. As rotinas de compressão de
imagens foram disponibilizadas em interface gráfica (sistema PixelWare), que permite que
o usuário trabalhe de maneira interativa com as imagens e realize análises das mesmas,
dentro de um único ambiente. Como alternativa mais simples, apenas para a geração de
arquivos de imagens comprimidas e descomprimidas, as rotinas também foram
disponibilizadas na interface do sistema operacional MS-DOS. Além dos programas para
compressão e descompressão de imagens, nomeados, respectivamente CRUSH e
UNCRUSH, outras rotinas auxiliares foram implementadas ao logo dos trabalhos, como
VECTOR, que gera e gerencia massas de amostras de vetores para geração de alfabetos
pelo algoritmo LBG, usados na compressão VQ, e MSE, que calcula os parâmetros de
distorção entre imagens adotados. O formato BM foi detalhadamente descrito, uma vez que
foi o formato adotado nas implementações. Como padrão de comparação, o formato JPEG,
que utiliza a transformada do cosseno associada à codificação preditiva, também foi
abordado.
Terminadas as implementações, adotou-se um conjunto de imagens como amostras para a
determinação dos parâmetros de operação dos algoritmos, como quantizadores, alfabetos de
vetores e matrizes de alocação de bits. Nesta etapa, realizou-se um ajuste fino dos
algoritmos, adequando-os ao conjunto de imagens previamente definido. Compararam-se
os desempenhos dos algoritmos implementados entre si e com o formato JPEG. Como
resultado, mostrou-se que muitas das variações implementadas são absolutamente viáveis,
se encontrando no mesmo nível que pacotes comerciais. Algumas deficiências poderão ser
eliminadas no futuro, visando otimização de desempenho, redução de distorções e aumento
das razões de compressão.
No caso das imagens binárias, o algoritmo MREAD mostrou ser mais eficiente que o
algoritmo RLC, devido a sua capacidade de explorar a correlação entre linhas subseqüentes
da imagem. A razão de compressão líquida obtida esteve em torno dos 2:1, sendo que em
ambos os casos não há distorção entre as imagens originais e as reconstruídas. No caso dos
arquivos BM, a redução real no tamanho dos arquivos chega aos 16:1, devido às
características deste formato. Os tempos de compressão e descompressão foram
considerados baixos.
Para as imagens com múltiplos níveis de cinza, classificaram-se os algoritmos em três
diferentes grupos, de acordo com as razões de compressão obtidas. Os algoritmos menos
evoluídos estão no primeiro grupo, com razões de compressão em torno dos 2:1. São eles
PCM e DPCM, nas suas diversas variações, excetuando-se a modulação delta (DM).
Concluiu-se que tais algoritmos não devem ser usados isoladamente, devido a seu baixo
desempenho, sendo recomendáveis apenas em conjunto com outros elementos de
codificação. O segundo grupo é o dos algoritmos que proporcionam razões de compressão
de 4:1 a 8:1, como os algoritmos BTC, DCT, PC e DPCM (DM). Para estes, a qualidade
das imagens reconstruídas, de uma maneira geral; foi considerada satisfatória, assim como
as razões de compressão obtidas. No caso dos algoritmos PC e DCT, os tempos de
processamento mostraram-se proibitivos, sendo a sua utilização possível apenas após terem
sofrido otimizações em sua implementação. O terceiro e último grupo é composto pelos
algoritmos de mais alta performance, a quantização vetorial e o algoritmo JPEG, este
último não implementado, servindo apenas como referência. Com razões de compressão
variáveis entre os 8:1 e os 16:1, tais algoritmos conseguem reunir ao mesmo tempo
velocidade de processamento (pelo menos no caso da descompressão, que é essencial), boa
qualidade das imagens reconstruídas e facilidade de implementação (no caso da
quantização vetorial).
Como aplicação, foi proposto um sistema para armazenamento de dados referentes a
documentos históricos. Os dados gerenciados por este sistema seriam gráficos (imagens) e
alfanuméricos (informações sobre o processo de conservação dos documentos).
Observando-se as restrições impostas pela aplicação (baixos tempos de recuperação, altas
razões de compressão e adequada qualidade final), indicou-se a quantização vetorial pura
para compressão das imagens. Imagens reconstruídas de documentos, resultantes da
aplicação deste algoritmo, foram apresentadas.
REFERÊNCIAS BIBLIOGRÁFICAS
[ALSC93]
[ASL+92]
6th
[BA83]
[Cost93]
[Davi92]
[DM79]
[FNF89]
[Geus90]
[GW87]
[Hand91]
[HR80]
[HW85]
[ISO91]
[Jain81]
[Jain89]
[JN84]
[KL92]
[KBL87]
[KIK85]
Araújo, A.A., Laender, A.F.H., Silva Jr., N.I., Coutinho, R.N., Image
Coding for Storing Historical Documents in a Database, Picture Coding
Symposium, 1993.
Araújo, A.A., Silva Jr., N.I., Laender, A.F.H., A Digital Image Processing
and Information Retrieval System of Brazilian Historical Documents,
EUROSIPCO, 1992.
Burt, P.J., Adelson, E.H., The Laplacian Pyramids as a Compact
Image Code, IEEE Trans. on Communications, pp. 532-540, 1983.
Costa, C.A.R., Técnicas de Compressão de Seqüências de Imagens
Visando Transmissão em Tempo Real, Universidade Estadual de
Campinas, 1993.
Davis, Jr., C.A., Pixelware, um Sistema de Processamento Digital de
Imagens, UFMG, 1992.
Delp, E.J., Mitchell, O.R., Image Compression Using Block
Truncation Coding, IEEE Trans. on Communications, pp. 13351342, 1979.
Finamore, W.A., Nunes, P.R.R.L., Fortes, J.M.P., Compression of
Historical Document Images, ICIP 89, Vol. 1, pp. 242-246, 1989.
Geus, P.L., Approaches to Live Image Transmission between
Workstations over Limited-Bandwidth Networks, University of
Manchester, 1990.
Gonzalez, R.C., Wintz, P., Digital Image Processing, Addison-Wesley, 2nd
Ed., 1977.
Handmade Software Inc., Image Alchemy Version 1.4, User's Manual,
Handmade Software, 1991.
Hunter, R., Robinson, H., International Digital Facsimile Coding
Standards, Proc. IEEE, pp. 854-867, 1980.
Hang, H.M., Woods, J.W., Predictive Vector Quantization of
Images, IEEE Trans. on Communications, pp. 1208,1219, 1985.
ISO/IEC, Digital Compression and Coding of Continuous-Tone Still
Images, Part I: Requirements and Guidelines, ISO/IEC, 1991.
Jain, A.K., Image Compression: A Review, Proc. IEEE, pp. 349389, 1981.
Jain, A.K., Fundamentals of Digital Image Processing, Prentice-Hall, 1989.
Jayant, N.S., Noll, P., Digital Coding of Waveforms, Principles and
Applications to Speech and Video, Prentice-Hall, 1984.
Kay, D.C., Levine, J.R., Graphics File Formats, McGraw Hill, 1992.
Kunt, M., Bernard, M., Leonardi, R., Recent Results in High
Compression Image Coding, IEEE Trans. on Circuits and Systems,
November, 1987.
Kunt, M., Iconomopoulos, A., Kocher, M., Second Generation
Image Coding Techniques, Proc. IEEE, pp. 549-575, 1985.
[LBG80]
[Lim90]
[LM84]
[MD80]
[NK88]
[NL80]
[Pear90]
[Prat78]
[RG86]
[RJ91]
[UR87]
[Yasu80]
[ZL78]
Linde, Y., Buzo, A., Gray, R.M., An Algorithm for Vector
Quantizer Design, IEEE Trans. on Communications, pp. 84-95,
1980.
Lim, J.S., Two-Dimensional Signal and Image Processing, Prentice-Hall,
1990.
Lema, M.D., Mitchell, R., Absolute Moment Block Truncation
Coding and Its Application to Color Images, IEEE Trans. on
Communications, pp. 1148-1157, 1984.
Mitchell, O.R., Delp, E.J., Multilevel Graphics Representation
Using Block Truncation Coding, Proc. IEEE, pp. 868-873, 1980.
Nasrabadi, N.M., King, R.A., Image Coding Using Vector
Quantization : A Review, IEEE Trans. on Communications, pp.
957-971, 1988.
Netravali, A.N., Limb, J., Picture Coding: A Review, Proc. IEEE,
pp. 366-406, 1980.
Pearlman, W.A., Adaptive Cossine Transform Image Coding with
Constant Block Distortion, IEEE Trans. on Communications, pp.
698-702, 1990.
Pratt, W.K., Digital Image Processing, John Wiley & Sons, 1978.
Ramamurthi, B., Gersho, A., Classified Vector Quantization of
Images, IEEE Trans. on Communications, pp. 1105-1115, 1986.
Rabbani, M., Jones, P.W., Digital Image Compression Techniques, The
International Society for Optical Engineering, 1991.
Udpikar, V.R., Raina, J.P., BTC Image Coding Using Vector
Quantization, IEEE Trans. on Communications, pp. 352-356, 1987.
Yasuda, Y., Overview of Digital Facsimile Coding Techniques in
Japan, Proc. IEEE, pp. 830-845, 1980.
Ziv, J., Lempel, A., Compression of Individual Sequences via
Variable-Rate Coding, IEEE Trans. on Information Theory, pp.
530-536, 1978.
Bibliografia Recomendada
[Ahme74]
[AG86]
[APM86]
[AG86]
Ahmed, N., Discrete Cosine Transform, IEEE Trans. on
Communications, pp. 90-93, 1974.
Alvarez, L., Garcia, N., Some Results on Vector Quantization,
EURASIP 86, Signal Processing III, pp. 797-800, 1986.
Anastassiou, D., Pennebaker, W., Mitchell, J.L., Gray Scale Image
Coding for Freeze-Frame Video-Conferencing, IEEE Trans. on
Communications, pp. 382-394, 1986.
Aravind, R., Gersho, A., Image Coding Below 0.5 Bits per Pixel
Using Vector Quantization, EUSIPCO 86, Signal Processing III,
pp. 757-759, 1986.
[AG83]
[BF86]
[BK86]
[BS80]
[Burr]
[CB90]
[CB92]
[CP84]
[Dohe80]
[DKS90]
[ES86]
[FDU80]
[FNS91]
[Fuki78]
[GBS86]
[GN89]
[GRK90]
[Goed]
[GS86]
Arce, G.R., Gallagher, Jr., N.C., BTC Image Coding Using Median
Filter Roots, IEEE Trans. on Communications, pp. 784-793, 1983.
Benelli, G., Fantacci, R., Image Data Compression Techniques
Using Kalman and Alpha-Beta Filters, EUSIPCO 86, Signal
Processing III, pp. 785-788, 1986.
Bernard, M., Kunt, M., Linear Prediction in Directional Images,
EUSIPCO 86, Signal Processing III, pp. 805-808, 1986.
Bodson, D., Schaphorst, R., Compression and Error Sensivity of TwoDimensional Facsimile Coding Techniques, Proc. IEEE , pp. 846-853,
1980.
Burrus, C.S., DFT/FFT and Convolution Algorithms Theory and
Implementation, 1985.
Chen, D., Bovik, A.C., Visual Pattern Coding, IEEE Trans. on
Communications, pp. 2137-2145, 1990.
Chen, D., Bovik, A.C., Hierarchical Visual Pattern Image Coding,
IEEE Trans. on Communications, pp. 671-675, 1992.
Chen, W.H., Pratt, W.K., Scene Adaptive Coder, IEEE Trans. on
Communications, pp. 225-232, 1984.
Doherty, B., Comparison of Facsimile Data Compression Schemes,
IEEE Trans. on Communications, pp. 2023-2024, 1980.
Du Buf, J.M.H., Kardan, M., Spann, M., Texture Feature
Performance for Image Segmentation, Pattern Recognition, Vol.
23, No. 3/4, pp.291-309, 1990.
Eggerton, J.D., Srinath, M.D., A Visually Weighted Quantization
Scheme for Image Bandwidth Compression at Low Data Rate,
IEEE Trans. on Communications, pp. 840-847, 1986.
Frank, A.J.,Daniels, J.D., Unangst, D.R., Progressive Image
Transmission Using a Growth-Geometry Coding, Proc. IEEE, pp.
897-905, 1980.
Finamore, W.A., Nunes, P.R.R.L., Silva, A.A., Uma Variação do
Algoritmo de Lempel-Ziv, 9o. Simpósio Brasileiro de Telecomunicações,
1991.
Fukinuki, T., Notchless Bi-Level Quantizer for Fac-Simile and Its
Effects in Coding of Digital Pictures, IEEE Trans. on
Communications, pp. 611-618, 1978.
Goldberg, M., Boucher, P.R., Shlien, S., Image Compression
Using Adaptive Vector Quantization, IEEE Trans. on
Communications, pp. 180-187, 1986.
Garrido, D.P., Nunes, R.R.L., An Edge/Non-Edge Image
Compression Algorithm, ICIP 89, Vol. 1, pp. 519-523, 1989.
Giunta, G., Reed, T.R., Kunt, M., Image Sequence Coding Using
Oriented Edges, EUSIPCO 90, Signal Processing, pp. 429-439,
1990.
Goedel, T.W., A Two-Dimensional Quantizer for Coding of Digital
Imagery, IEEE Trans. on Communications, pp. 60-67, 1981.
Goldberg, M., Sun, H., Image Sequence Coding Using Vector
Quantization, IEEE Trans. on Communications, pp.703-710, 1986.
[GD86]
[Habi81]
[Hara]
[Held]
[IC81]
[Jame]
[Jaya74]
[KJ80]
[KO85]
[KS81]
[KB86]
[Know80]
[LR81]
[Makh75]
[MPAP89]
[MT81]
[MY81]
[Mitc80]
Götze, M., Du, Y., Adaptive Transform Coding of Images Using
Vector Quantization, EUSIPCO 86, Signal Processing III, pp. 789792, 1986.
Habibi, A., An Adaptive Strategy for Hybrid Image Coding, IEEE
Trans. on Communications, pp. 1736-1740, 1981.
Haralick, R.M., Statistical and Structural Approaches to Textures,
Proc. IEEE, pp. 786-804, 1979.
Held, G., Data Compression Techniques and Applications Hardware and Software Considerations, 1988.
Ismail, M.G., Clarke, R.J., Adaptive Block/Location Coding of
Facsimile Signals Using Subsampling and Interpolation for Pre and
Postprocessing, IEEE Trans. on Communications, pp. 1925-1934,
1981.
James, M., Pattern Recognition, 1988.
Jayant, N.S., Digital Coding of Speech Waveforms: PCM, DPCM
and DM Quantizers, Proc. IEEE, pp. 611-632, 1974.
Kunt, M., Johnsen, O., Block Coding of Graphics: A Tutorial
Review, Proc. IEEE, pp. 770-786, 1980.
Kaneko, T., Okudaira, M., Encoding of Arbitrary Curves Based on
the Chain Code Representation, IEEE trans. on Communications,
pp. 697-707, 1985.
Kim, J., Segin, P., A Conditional Incremental-Runlength Code
Based on Two-Dimensional Markov Model, IEEE Trans. on
Communications, pp. 1527-1532, 1981.
Kirchhoff, H.J., Besslich, P.W., A Hybrid Image Coding Scheme
Using Adaptive Local Resolution, EUSIPCO 86, Signal Processing
III, pp. 747-750, 1986.
Knowlton, K., Progressive Transmission of Grey-Scale and Binary
Pictures by Simple, Efficient, and Lossless Encoding Schemes,
Proc. IEEE, pp. 885-896, 1980.
Langdon, G.G. Jr., Rissanen, J., Compression of Black-White
Images with Arithmetic Coding, IEEE Trans. on Communications,
pp. 858-867, 1981.
Makhoul, J., Linear Prediction: A Tutorial Review, Proc. IEEE, pp.
561-580, 1975.
Mitchell, J.L.,Pennebaker, W.B., Anastassiou, D., Pennington,
K.S., Graphics Image Coding for Freeze-Frame Video
Conferencing, IEEE Trans. on Communications, pp. 515-522,
1989.
Mark, J.W., Todd, T.D., A Nonuniform Sampling Approach to
Data Compression, IEEE Trans on Communications, pp. 24-32,
1981.
Meiri, A.Z., Yudilevich, E., A Pinned Sine Transform Image Coder,
IEEE Trans. on Communications, pp. 1728-1734, 1981.
Mitchell, O.R., Multilevel Graphics Representation Using Block
Truncation Coding, Proc. IEEE , July, 1980.
[MB84]
[MDV81]
[MB81]
[Morr74]
[MMY84]
[Muss85]
[NF90]
[NH88]
[NP77]
[NM80]
[Nill85]
[NAS92]
[OP83]
[Otsu]
[PCC+80]
[RC89]
[Tam83]
[Ting80]
Modestino, J.W., Bhaskaran, V., Adaptive Two-Dimensional Tree
Encoding of Images Using Spatial Masking, IEEE Trans. on
Communications, pp. 177-189, 1984.
Modestino, J.W.,Daut, D.G., Vickers, A.L., Combinated SourceChannel Coding of Images Using the Block Cosine Transform,
IEEE Trans. on Communications, pp. 177-199, 1984.
Modestino, J.W., Bhaskaran, V., Robust Two-Dimensional Tree
Encoding of Images, IEEE Trans. on Communications, pp. 17861798, 1981.
Morrin, T.H., A Black-White Representation of Gray-Scale Picture,
IEEE Trans. on Computers, pp. 184-186, 1974.
Murakami, H.,Matsumoto, S., Yamamoto, H., Algorithm for
Construction of Variable Lenght Code with Limited Maximum
Word Lenght, IEEE Trans on Communications, pp. 1157-1159,
1984.
Mussmann, H.G., Advances in Picture Coding, Proc. IEEE, pp.
523-548, 1985.
Nasrabadi, N.M., Feng, Y., Image Compression Using AdressVector Quantization, IEEE Trans. on Communications, pp. 21662173, 1990.
Netravali, A.N., Haskell, B.G., Digital Pictures, Representation and
Compression, At&T Bell Laboratories, 1988.
Netravali, A.N., Prasada, B., Adaptive Quantization of Picture
Signals Using Spatial Masking, Proc. IEEE, pp. 536,548, 1977.
Netravali, A.N., Ordering Techniques for Facsimile Coding: A
Review, Proc. IEEE, pp. 796-806, 1980.
Nill, N.B., A Visual Model Weighted Cosine Transform for Image
Compression and Quality Assesment, IEEE Trans. on
Communications, pp. 551-557, 1985.
Nunes, P.R.R.L., Alcaim, A., Silva, M.R.L.F., Compression of
Satellite Images for Remote Sensing Applications, XVII Congress
of ISPR, 1992.
O'Leary, D.P., Peleg, S., Digital Image Compression by Outer
Product Expansion, IEEE Trans. on Communications, pp. 441-444,
1983.
Otsu, N., A Threshold Selection Method from Gray-Level
Histograms, IEEE Trans. Syst. Man Cybern., pp. 62-66, 1979.
Pratt, W.K., Capitant, P., Chen, W., Hamilton, E.R., Wallis, R.H.,
Combined Symbol Matching Data Compression System, Proc.
IEEE, pp. 786-796, 1980.
Ramabadran, T.V., Cohn, D.L., An Adaptive Algorithm for the
Compression of Computer Data, IEEE Trans on Communications,
pp. 317-323, 1989.
Tam, T.O., Line-Adaptive Hybrid Coding of Images, IEEE Trans.
on Communications, pp. 445-450, 1983.
Ting, D., Digital Processing Techniques for Encoding Graphics,
Proc. IEEE, pp. 757-769, 1980.
[UOI80]
[WCK86]
[WKG83]
[WR79]
[Yama79]
[Yasu85]
[YDH80]
[YY84]
[ZEC84]
Usubuchi, T., Omachi, T., Iinuma, K., Adaptive Predictive Coding
for Newspaper Facsimile, Proc. IEEE, pp. 807-813, 1980.
Walach, E., Chevion D., Karnin, E., On Modification of BTC
Approach to Image Compression, EUSIPCO 86, Signal Processing
III, 1986.
Wilson, R., Knutson, H.E., Granlund, G.H., Anisotropic
Nonstationary Image Estimation and Its Applications Part II Predictive Coding, IEEE Trans. on Communications, pp. 398-406,
1983.
Weszka, J.S., Rosenfeld, A., Histogram Modification for Threshold
Selection, IEEE Trans. on Syst. Man Cybern., pp. 38-52, 1979.
Yamada, T., Edge-Difference Coding - A New Efficient
Redundancy Reduction Technique for Facsimile Signals, IEEE
Trans. on Communications, pp. 1210-1217, 1979.
Yasuda, Y., Advances in Fax, Proc. IEEE, pp. 706-730, 1985.
Yasuda, Y., Dubois, M., Huang, T.S., Data Compression for Check
Processing Machines, Proc. IEEE, pp. 874-885, 1980.
Yasuhara, M., Yasumoto, Y., An Improved Adaptive Predictor in
DPCM Based on the Kalman Filter and Its Application to
Handwriting Signal Encoding, IEEE Trans. on Communications,
pp. 484-488, 1984.
Zetteberg, L.H., Ericsson, S., Couturier, C., DPCM Picture Coding
with Two-Dimensional Control of Adaptive Quantization, IEEE
Trans. on Communications, pp. 457-462, 1984.
APÊNDICES
A - Código Modificado de Huffman
A1 - Bits menos significativos para seqüências de brancos
Seqüência
Palavra
Seqüência
Palavra
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"00110101"
"000111"
"0111"
"1000"
"1011"
"1100"
"1110"
"1111"
"10011"
"10100"
"00111"
"01000"
"001000
"000011"
"110100"
"110101"
"101010"
"101011"
"0100111"
"0001100"
"0001000"
"0010111"
"0000011"
"0000100"
"0101000"
"0101011"
"0010011"
"0100100"
"0011000"
"00000010"
"00000011"
"00011010"
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
"00011011"
"00010010"
"00010011"
"00010100"
"00010101"
"00010110"
"00010111"
"00101000"
"00101001"
"00101010"
"00101011"
"00101100"
"00101101"
"00000100"
"00000101"
"00001010"
"00001011"
"01010010"
"01010011"
"01010100"
"01010101"
"00100100"
"00100101"
"01011000"
"01011001"
"01011010"
"01011011"
"01001010"
"01001011"
"00110010"
"00110011"
"00110100"
A2 - Bits mais significativos para seqüências de brancos
Seqüência/64 (divisão inteira)
Palavra
fim de linha
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"0000000000"
"11011"
"10010"
"010111"
"0110111"
"00110110"
"00110111"
"01100100"
"01100101"
"01101000"
"01100111"
"011001100"
"011001101"
"011010010"
"011010011"
"011010100"
"011010101"
"011010110"
"011010111"
"011011000"
"011011001"
"011011010"
22
23
24
25
26
27
"011011011"
"010011000"
"010011001"
"010011010"
"011000"
"010011011"
A3 - Bits menos significativos para seqüências de pretos
Seqüência
Palavra
Seqüência
Palavra
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"0000110111"
"010"
"11"
"10"
"011"
"0011"
"0010"
"00011"
"000101"
"000100"
"0000100"
"0000101"
"0000111"
"00000100"
"00000111"
"000011000"
"0000010111"
"0000011000"
"0000001000"
"00001100111"
"00001101000"
"00001101100"
"00000110111"
"00000101000"
"00000010111"
"00000011000"
"000011001010"
"000011001011"
"000011001100"
"000011001101"
"000001101000"
"000001101001"
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
"000001101010"
"000001101011"
"000011010010"
"000011010011"
"000011010100"
"000011010101"
"000011010110"
"000011010111"
"000001101100"
"000001101101"
"000011011010"
"000011011011"
"00001010100"
"00001010101"
"000001010110"
"000001010111"
"000001100100"
"000001100101"
"000001010010"
"000001010011"
"000000100100"
"000000110111"
"000000111000"
"000000100111"
"000000101000"
"000001011000"
"000001011001"
"000000101011"
"000000101100"
"000001011010"
"000001100110"
"000001100111"
A4 - Bits significativos para seqüências de pretos
Seqüência/64 (divisão inteira)
Palavra
fim de linha
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"00000000001"
"0000001111"
"000011001000"
"000011001001"
"000001011011"
"000000110011"
"000000110100"
"000000110101"
"0000001101100"
"0000001101101"
"0000001001010"
"0000001001011"
"0000001001100"
"0000001001101"
"0000001110010"
"0000001110011"
"0000001110100"
"0000001110101"
18
19
20
21
22
23
24
25
26
27
"0000001110110"
"0000001110111"
"0000001010010"
"0000001010011"
"0000001010100"
"0000001010101"
"0000001011010"
"0000001011011"
"0000001100100"
"0000001100101"
B - Código de Huffman para modos do algoritmo MREAD
Modo
Palavra
fim de linha
pass
horizontal
vertical
vertical - complementos
"0000001"
"0001"
"001"
"1"
"011"
"000011"
"0000011"
"010"
"000010"
"0000010"
C - Compressão DPCM
C1 - Compressão sem perda de informação
C1.1 - Bits menos significativos (erros entre -31 e + 31)
Erro
Palavra
Erro
Palavra
-31
-30
-29
-28
-27
-26
-25
-24
-23
-22
-21
-20
-19
-18
-17
-16
-15
-14
-13
-12
-11
-10
-9
-8
-7
-6
-5
-4
-3
-2
-1
0
"000001011000"
"000000111000"
"000000100100"
"000001010011"
"000001100100"
"000001010111"
"000001010101"
"000001010100"
"000011011010"
"000001101101"
"000011010111"
"000011010100"
"000011010011"
"000001101011"
"000001101001"
"000011001101"
"000011001011"
"000011001010"
"00000010111"
"00000110111"
"00001101000"
"0000110111"
"0000011000"
"000011000"
"00000111"
"0000111"
"000100"
"000101"
"0011"
"010"
"10"
"11"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"011"
"0010"
"00011"
"0000100"
"0000101"
"00000100"
"0000010111"
"0000001000"
"00001100111"
"00001101100"
"00000101000"
"00000011000"
"000011001100"
"000001101000"
"000001101010"
"000011010010"
"000011010101"
"000011010110"
"000001101100"
"000011011011"
"000001010110"
"000001100101"
"000001010010"
"000000110111"
"000000100111"
"000001011001"
"000000101011"
"000000101100"
"000001011010"
"000001100110"
"000001100111"
C1.2 - Bits mais significativos (erros < -31)
Erro/-32 (divisão inteira)
Palavra
1
2
3
4
5
6
7
"0000001111"
"000001011011"
"000011001001"
"000011001000"
"0000001001010"
"0000001101101"
"0000001101100"
C1.3 - Bits mais significativos (erros > +31)
Erro/32 (divisão inteira)
Palavra
1
2
3
4
5
6
7
"00000000001"
"000000110011"
"000000110100"
"000000110101"
"0000001001100"
"0000001001101"
"0000001110010"
C2 - Compressão com perda de informação
C2.1 - Quantização em 16 níveis (Lloyd-Max, distribuição gaussiana)
Nível
Limite Superior (aberto)
Valor Representativo
Palavra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-46
-35
-27
-21
-15
-10
-5
0
5
10
15
21
27
35
46
255
-52
-39
-31
-24
-18
-12
-7
-2
2
7
12
18
24
31
39
52
"00000111"
"0000101"
"0000111"
"0000110"
"000100"
"000101"
"010"
"10"
"11"
"011"
"0011"
"0010"
"00011"
"0000100"
"00000110"
"00000100"
C2.2 - Quantização em 8 níveis (Lloyd-Max, distribuição gaussiana)
Nível
Limite Superior (aberto)
Valor Representativo
Palavra
1
2
3
4
5
6
7
8
-33
-20
-10
0
10
20
33
255
-41
`-26
-14
-5
5
15
26
41
"1111110"
"111110"
"1110"
"10"
"0"
"110"
"11110"
"1111111"
C2.3 - Quantização em 2 níveis (Lloyd-Max, distribuição gaussiana)
Nível
Limite Superior (aberto)
Valor Representativo
Palavra
1
2
0
255
-15
15
"1"
"0"
C2.4 - Quantização adaptativa - fatores de multiplicação de intervalos
Níveis
Nível de Quantização
Fator
16
0 (estado inicial)
1
2
3
4
5
6
7
8
0 (estado inicial)
1
2
3
4
1
0.6
0.8
0.9
1.0
1.2
1.5
2.0
4.0
1
0.6
1.0
1.5
4.0
8
D - Compressão PC
D1 - Matriz de convolução
0
1
2
3
4
0
1
2
3
4
0.0025
0.0125
0.0200
0.0125
0.0025
0.0125
0.0625
0.1000
0.0625
0.0125
0.02
0.10
0.16
0.10
0.02
0.0125
0.0625
0.1000
0.0625
0.0125
0.0025
0.0125
0.0200
0.0125
0.0025
D2 Códigos de Huffman
D2.1 - Quantização em 3 níveis (Lloyd-Max, distribuição gaussiana)
Nível
Limite Superior(aberto)
Valor Representativo
Palavra
1
2
3
-11
11
255
-23
0
23
"00",
"1"
"01"
D2.2 - Quantização em 5 níveis (Lloyd-Max, distribuição gaussiana)
Nível
Limite Superior (aberto)
Valor Representativo
Palavra
1
2
-24
-7
-33
-15
"0000"
"01"
3
4
5
7
24
255
0
15
33
"1"
"001"
"0001"
D2.3 - Quantização em 9 níveis (Lloyd-Max, distribuição gaussiana)
Nível
Limite Superior (aberto)
Valor Representativo
Palavra
1
2
3
4
5
6
7
8
9
-35
-23
-13
-4
4
13
23
35
255
-43
-28
-17
-8
0
8
17
28
43
"00010"
"0011"
"010"
"10"
"11"
"011"
"0010"
"0000"
"00011"
D2.4 - Quantização em 17 níveis (Lloyd-Max, distribuição gaussiana)
Nível
Limite Superior (aberto)
Valor Representativo
Palavra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-47
-36
-29
-22
-17
-12
-7
-2
2
7
12
17
22
29
36
47
255
-53
-40
-32
-25
-19
-14
-9
-5
0
5
9
14
19
25
32
40
53
"00000111"
"0000101"
"0000111"
"000000"
"000100"
"0010"
"010"
"10"
"11"
"011"
"0011"
"00011"
"000101"
"0000110"
"0000100"
"00000110"
"00000100"
E - Compressão DCT
E1 - Matriz de alocação de bits
0
1
2
3
4
5
6
7
0
8
6
5
3
1
0
0
0
1
6
6
5
2
1
0
0
0
2
5
5
2
1
0
0
0
0
3
3
2
1
0
0
0
0
0
4
1
1
0
0
0
0
0
0
5
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
E2 - Quantização (Lloyd-Max, distribuição gaussiana)
Bits
1
Limites Superiores (abertos)
Valores Representativos
0
-25,25
2
3
4
-39,0,39
-87,-52,-25,0,25,52,87
-127,-97,-76,-58,-42,-27,-13,0,13,27,42,58,76,97,127
5
-187,-157,-136,-120,-106,-93,-81,-71,-61,-51,-42,-33,25,-16,8,0,8,16,25,33,42,51,61,71,81,93,106,120,136,157,187,
6
-279,-246,-223,-206,-191,-178,-166,-156,-146,-137,128,-120,-113,-105,-98,-92,-85,-79,-72,-66,-60,-55,49,-43,-38,-32,-27,-21,-16,-10,5,0,5,10,16,21,27,32,38,43,49,55,60,66,72,79,85,92,98,
105,113,120,128,137,146,156,166,178,191,206,223,24
6,279,
-2021,-1932,-1902,-1872,-1851,-1831,-1815,-1799,1786,-1773,-1762,-1750,-1741,-1731,-1722,-1713,1704,-1696,-1689,-1681,-1674,-1667,-1661,-1654,1648,-1642,-1636,-1630,-1624,-1619,-1613,-1608,1603,-1598,-1593,-1588,-1583,-1578,-1574,-1569,1565,-1560,-1556,-1552,-1548,-1543,-1539,-1535,1531,-1527,-1523,-1519,-1516,-1512,-1508,-1504,1501,-1497,-1493,-1490,-1486,-1483,-1479,-1476,1472,-1469,-1465,-1462,-1459,-1455,-1452,-1449,1446,-1442,-1439,-1436,-1433,-1430,-1427,-1423,1420,-1417,-1414,-1411,-1408,-1405,-1402,-1399,1396,-1393,-1390,-1387,-1384,-1381,-1378,-1375,1372,-1369,-1366,-1364,-1361,-1358,-1355,-1352,1349,-1346,-1343,-1341,-1338,-1335,-1332,-1330,1327,-1324,-1321,-1318,-1315,-1312,-1310,-1307,1304,-1301,-1298,-1296,-1293,-1290,1287,1285,1287,1290,1293,1296,1298,1301,1304,1307
,1310,1312,1315,1318,1321,1324,1327,1330,1332,133
5,1338,1341,1343,1346,1349,1352,1355,1358,1361,13
64,1366,1369,1372,1375,1378,1381,1384,1387,1390,1
393,1396,1399,1402,1405,1408,1411,1414,1417,1420,
1423,1427,1430,1433,1436,1439,1442,1446,1449,1452
,1455,1459,1462,1465,1469,1472,1476,1479,1483,148
6,1490,1493,1497,1501,1504,1508,1512,1516,1519,15
23,1527,1531,1535,1539,1543,1548,1552,1556,1560,1
565,1569,1574,1578,1583,1588,1593,1598,1603,1608,
1613,1619,1624,1630,1636,1642,1648,1654,1661,1667
,1674,1681,1689,1696,1704,1713,1722,1731,1741,175
0,1762,1773,1786,1799,1815,1831,1851,1872,1902,19
32,2021,
8
-60,-18,18,60
-107,-67,-37,-12,12,37,67,107
-144,-109,-85,-66,-49,-34,-20,6,6,20,34,49,66,85,109,144
-205,-169,-146,-127,-112,-99,-87,-76,-66,-54,-47,-38,29,-20,-12,4,4,12,20,29,38,47,54,66,76,87,99,112,127,146,169,20
5
-299,-259,-233,-214,-198,-184,-172,-161,-151,-141,133,-124,-116,-109,-102,-95,-88,-82,-76,-69,-63,-57,52,-46,-40,-35,-29,-24,-18,-13,-8,2,2,8,13,18,24,29,35,40,46,52,57,63,69,76,82,88,95,10
2,109,116,124,133,141,151,161,172,184,198,214,233,2
59,299
-2052,-1969,-1932,-1895,-1872,-1849,-1831,-1813,1799,-1785,-1773,-1761,-1750,-1740,-1731,-1721,1713,-1704,-1696,-1688,-1680,-1671,-1666,-1660,1654,-1648,-1642,-1636,-1626,-1616,-1615,-1613,1608,-1603,-1598,-1593,-1588,-1583,-1578,-1574,1569,-1565,-1560,-1556,-1552,-1547,-1543,-1539,1535,-1531,-1527,-1523,-1519,-1516,-1512,-1508,1504,-1501,-1495,-1490,-1488,-1486,-1483,-1479,1476,-1472,-1469,-1465,-1462,-1459,-1455,-1452,1449,-1446,-1442,-1439,-1436,-1433,-1430,-1427,1423,-1420,-1417,-1414,-1411,-1408,-1405,-1402,1399,-1396,-1393,-1390,-1387,-1384,-1381,-1378,1375,-1372,-1369,-1366,-1364,-1361,-1358,-1355,1352,-1349,-1346,-1343,-1341,-1338,-1335,-1332,1329,-1327,-1324,-1321,-1318,-1315,-1312,-1310,1307,-1304,-1300,-1295,-1294,-1293,-1290,1286,1286,1290,1293,1294,1295,1300,1304,1307,1310
,1312,1315,1318,1321,1324,1327,1329,1332,1335,133
8,1341,1343,1346,1349,1352,1355,1358,1361,1364,13
66,1369,1372,1375,1378,1381,1384,1387,1390,1393,1
396,1399,1402,1405,1408,1411,1414,1417,1420,1423,
1427,1430,1433,1436,1439,1442,1446,1449,1452,1455
,1459,1462,1465,1469,1472,1476,1479,1483,1486,148
8,1490,1495,1501,1504,1508,1512,1516,1519,1523,15
27,1531,1535,1539,1543,1547,1552,1556,1560,1565,1
569,1574,1578,1583,1588,1593,1598,1603,1608,1613,
1615,1616,1626,1636,1642,1648,1654,1660,1666,1671
,1680,1688,1696,1704,1713,1721,1731,1740,1750,176
1,1773,1785,1799,1813,1831,1849,1872,1895,1932,19
69,2052
F - Compressão VQ
F1 - AlfabetoVQ Pura
Vetor
Valores
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
166,119,72,78,137,130,49,64,163,155,90,55,161,150,156,156,
142,157,158,163,167,156,158,163,162,162,163,152,161,163,161,167,
116,52,45,61,146,90,43,56,146,143,132,132,142,140,148,141,
169,168,169,169,165,166,165,166,167,159,162,159,152,164,163,161,
148,137,93,101,145,114,73,119,151,81,72,143,144,59,82,127,
145,148,150,144,147,145,151,149,141,138,130,128,121,73,49,65,
133,147,184,186,124,146,179,186,129,148,181,186,141,153,180,179,
179,187,189,193,187,190,189,133,193,187,193,76,185,190,174,176,
138,145,141,86,141,150,147,84,145,147,145,90,139,149,140,94,
105,107,115,115,148,169,163,171,177,175,172,176,178,178,184,185,
134,136,129,138,59,51,55,64,82,78,71,56,40,45,43,43,
147,151,147,137,150,152,143,76,147,156,142,43,152,153,139,49,
141,83,82,140,88,77,112,143,129,120,129,148,139,142,146,160,
147,150,147,132,156,153,154,151,155,155,154,153,153,155,155,150,
160,157,161,155,155,156,155,160,162,158,156,155,154,146,157,158,
164,166,164,174,167,163,172,157,168,169,165,174,170,166,169,165,
127,127,125,126,124,128,126,128,126,124,128,132,121,124,134,135,
201,122,69,133,58,108,202,184,185,196,177,183,188,183,185,173,
159,160,160,164,157,156,156,158,150,150,146,145,142,135,127,122,
163,164,159,160,154,144,160,152,155,156,164,165,158,166,161,164,
57,67,80,90,127,118,97,92,143,140,95,78,140,139,77,78,
122,141,148,153,90,127,148,154,105,120,148,153,124,133,148,148,
136,138,138,134,135,135,136,133,132,133,131,124,133,132,130,121,
48,81,149,150,46,82,150,148,52,73,146,150,56,68,134,147,
108,66,69,107,140,133,131,131,145,143,144,133,139,142,141,141,
156,154,147,129,165,159,141,110,164,158,132,105,162,156,154,136,
58,132,158,144,138,143,152,151,146,142,152,147,141,140,146,154,
86,40,56,102,78,87,98,135,44,41,30,31,91,111,134,128,
140,145,124,58,145,143,110,52,141,134,79,60,118,108,54,57,
55,55,92,144,54,52,108,148,51,64,130,150,79,111,147,146,
185,179,189,180,187,196,137,45,185,92,62,153,78,74,191,179,
168,174,191,176,178,190,187,78,191,189,59,182,176,96,186,182,
104,105,100,109,101,99,85,97,88,97,77,83,80,89,89,88,
68,72,106,128,61,52,56,60,127,117,118,125,147,151,148,148,
40,45,100,140,43,39,90,139,46,43,62,141,48,48,63,133,
167,183,176,79,174,182,69,183,183,74,187,191,93,172,196,179,
134,123,112,118,136,120,104,118,137,122,102,118,135,121,101,117,
139,120,115,188,170,136,86,192,173,160,83,195,165,144,98,192,
43,41,39,39,51,71,40,41,97,136,72,32,119,133,88,57,
43,72,45,49,56,91,87,67,50,138,137,119,56,143,136,124,
189,188,153,82,192,190,83,72,181,186,70,63,186,185,125,115,
144,149,151,147,148,148,141,101,144,135,89,38,145,118,41,47,
159,171,132,61,183,200,59,90,192,73,80,207,71,76,183,192,
48,35,37,43,65,87,112,118,120,130,135,131,133,137,137,130,
156,118,163,175,107,112,179,114,74,178,148,83,187,176,56,184,
152,156,158,156,155,156,150,153,137,150,153,152,71,137,152,154,
58,129,148,122,56,139,146,140,95,146,149,143,124,144,151,148,
100,109,118,122,104,111,117,123,105,109,120,125,103,113,116,120,
145,146,148,151,147,151,146,147,147,147,146,116,139,147,114,51,
124,157,176,163,78,133,150,135,68,59,60,77,137,156,173,176,
125,130,124,97,127,125,113,87,126,120,106,80,122,124,117,88,
134,136,96,81,115,97,51,63,88,47,62,106,52,53,100,129,
188,195,189,101,188,192,176,80,188,192,169,93,193,194,155,191,
184,190,188,185,184,176,181,187,189,191,185,183,181,182,186,187,
199,203,206,205,201,200,189,197,174,161,111,194,202,181,109,200,
197,200,198,194,194,193,186,185,143,120,180,192,186,199,198,198,
207,209,206,198,205,206,200,155,203,201,125,187,198,154,189,201,
193,193,191,191,183,189,186,188,194,186,194,192,184,190,178,187,
153,150,125,43,150,149,135,40,145,152,133,41,144,151,131,51,
F1 - AlfabetoVQ Pura (continuação)
Vetor
Valores
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
196,195,198,198,188,188,189,178,192,195,192,196,191,189,193,190,
181,183,178,177,181,188,187,178,156,156,164,172,82,71,80,67,
183,184,185,186,189,188,193,191,176,180,177,183,185,185,191,188,
183,183,179,183,184,184,185,187,175,179,177,189,88,79,89,174,
76,77,180,181,58,187,187,164,182,193,180,126,190,179,149,54,
112,144,173,160,121,88,135,150,204,187,105,126,193,192,147,132,
185,188,186,188,185,184,184,187,184,184,185,193,190,191,195,109,
183,185,181,185,185,185,187,189,179,187,201,177,192,182,82,61,
192,189,95,82,192,194,197,191,197,191,197,194,192,195,195,189,
111,120,155,154,190,181,196,200,207,206,210,209,206,209,210,208,
171,177,174,170,182,172,174,175,173,173,169,176,173,174,172,168,
192,193,151,198,175,123,197,197,151,197,192,195,202,202,200,198,
196,205,202,179,184,164,113,108,182,190,189,190,195,195,190,204,
172,174,182,172,181,178,181,187,178,179,179,174,177,180,180,183,
193,174,162,178,102,173,192,195,198,194,199,203,200,203,205,205,
188,190,189,123,187,178,185,190,179,188,187,187,180,189,191,185,
207,211,209,208,209,210,207,209,209,202,196,205,182,118,169,206,
193,148,171,206,174,108,186,197,189,101,109,156,201,200,201,202,
169,175,175,125,164,115,57,33,30,27,45,67,86,121,140,167,
177,115,203,206,167,150,206,204,118,193,205,204,158,202,208,200,
189,188,190,189,188,189,189,188,193,190,188,194,190,189,191,171,
188,183,186,188,192,172,186,189,157,182,189,190,74,197,191,194,
72,160,190,189,71,199,185,182,186,184,181,180,189,181,184,178,
192,196,175,103,188,194,193,83,195,194,194,188,192,196,192,201,
153,184,191,188,177,186,201,75,184,193,81,72,185,114,62,162,
163,168,165,156,163,166,161,170,169,173,170,172,162,167,161,163,
176,156,85,156,182,82,69,75,190,71,70,107,171,185,173,187,
105,169,193,177,103,108,165,190,183,176,193,192,201,203,203,199,
176,164,118,165,172,83,98,107,93,74,89,144,75,115,177,169,
72,189,190,187,186,190,185,182,191,186,183,182,184,180,179,179,
191,166,99,181,184,195,102,104,198,203,195,166,196,201,194,193,
203,202,202,200,194,190,201,199,126,103,184,195,184,95,186,193,
201,202,172,144,201,196,114,196,203,183,133,204,197,112,180,208,
181,177,173,179,185,186,185,182,182,183,185,186,186,184,183,187,
170,93,162,170,62,56,199,183,45,73,119,120,69,51,60,146,
59,55,201,188,56,159,190,176,136,194,179,178,172,181,183,186,
188,187,176,184,186,186,181,178,188,183,181,162,186,187,182,179,
190,182,192,188,181,189,178,187,187,181,186,187,189,189,191,196,
187,127,66,198,177,62,117,194,112,70,200,186,63,166,186,178,
159,188,193,59,182,184,171,165,178,186,177,187,186,175,183,174,
194,186,133,189,189,184,111,189,198,187,105,193,191,186,106,177,
192,198,92,190,195,181,168,198,188,161,194,193,182,188,198,190,
200,206,193,160,203,198,146,168,203,119,200,202,136,190,204,193,
167,169,171,82,181,190,116,63,180,166,40,109,173,49,73,180,
131,192,189,186,198,185,184,185,182,183,183,184,184,186,186,187,
166,171,169,171,171,166,166,172,159,170,166,162,173,161,167,170,
175,184,182,184,186,177,180,191,182,181,189,179,183,189,191,43,
187,189,190,186,186,184,181,182,176,177,186,185,187,183,175,179,
196,199,200,199,198,202,198,200,187,184,192,186,90,110,178,174,
182,178,145,161,186,170,148,151,180,173,144,150,177,172,146,162,
188,188,192,192,170,169,177,183,173,173,158,164,187,185,188,177,
167,162,165,171,167,174,173,176,171,166,171,167,167,173,170,177,
145,137,114,65,152,156,159,151,156,156,161,158,158,158,157,152,
177,191,185,184,183,187,148,189,171,58,91,187,88,50,173,193,
190,195,132,191,198,195,101,192,201,198,109,137,205,199,200,190,
181,170,185,186,175,191,202,179,183,169,85,58,82,61,126,194,
188,188,187,184,189,188,190,185,183,180,174,171,172,162,140,129,
130,60,70,83,175,130,68,69,184,191,196,185,184,184,182,181,
173,181,190,189,173,178,157,92,105,92,143,186,176,195,196,194,
163,138,173,187,178,185,171,170,189,185,187,181,186,189,190,186,
175,183,179,182,182,189,190,179,132,97,64,72,59,52,59,60,
143,137,45,30,142,134,36,30,140,126,32,36,130,113,38,48,
68,70,66,59,55,58,119,181,153,191,193,183,184,183,178,172,
181,172,181,181,173,181,173,178,179,175,181,182,178,176,179,171,
123
124
125
192,185,188,192,187,187,191,190,181,189,193,190,184,162,180,189,
54,86,198,192,185,204,189,189,189,183,187,183,185,186,187,175,
188,170,80,63,127,72,93,191,155,176,198,177,183,184,181,172,
F1 - AlfabetoVQ Pura (continuação)
Vetor
Valores
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
174
176
177
178
179
180
181
182
183
184
185
186
187
188
189
156,178,200,190,97,188,185,149,103,193,199,120,165,202,180,129,
187,187,185,169,194,191,190,191,191,188,190,186,192,192,192,191,
43,36,30,36,41,38,41,36,32,40,37,32,34,30,34,33,
185,192,52,65,202,81,61,199,106,59,189,179,58,140,192,177,
71,68,63,72,44,52,52,44,177,170,137,155,187,161,179,176,
182,186,199,199,125,199,201,192,187,193,196,185,196,192,186,184,
90,91,112,98,62,51,58,55,85,62,50,49,148,149,139,128,
174,181,183,190,139,188,194,191,78,140,192,189,73,74,180,192,
162,198,185,87,174,136,71,162,66,140,198,189,190,199,186,183,
176,177,184,175,182,182,187,185,189,193,177,168,168,90,175,187,
179,171,172,175,166,178,174,157,175,169,169,170,179,176,167,173,
180,186,105,82,193,177,75,78,187,178,180,193,181,186,195,183,
190,196,188,183,175,115,87,182,66,74,64,176,104,70,62,183,
185,182,173,184,181,179,172,185,184,179,176,179,187,174,145,185,
177,177,186,185,165,179,179,182,150,172,182,180,164,163,182,183,
181,185,184,185,180,188,193,198,198,196,162,130,141,46,44,42,
66,53,68,183,57,114,201,189,186,194,190,189,191,185,184,178,
185,185,180,187,179,179,188,171,186,184,176,189,182,181,185,178,
198,195,196,197,175,183,190,183,127,100,88,102,162,192,196,158,
196,193,174,183,137,98,62,44,83,92,134,53,160,197,153,58,
186,168,142,148,184,183,170,163,178,184,183,179,184,183,184,180,
183,179,182,184,181,181,183,179,184,182,185,189,149,174,174,175,
170,179,183,185,182,183,182,179,181,181,188,52,181,193,68,74,
178,135,185,189,171,153,195,190,86,193,198,171,81,197,183,115,
180,115,198,191,169,163,188,152,161,189,203,104,200,206,194,175,
178,181,178,174,166,159,169,175,183,184,178,176,180,178,178,183,
182,180,177,58,183,175,51,114,161,41,98,120,56,83,150,107,
63,48,50,67,185,195,197,200,185,185,185,182,189,183,183,180,
213,213,213,212,213,213,213,213,213,213,213,213,213,213,213,213,
198,197,194,188,115,106,157,188,185,162,198,196,181,187,201,194,
107,93,58,44,108,127,93,45,124,133,134,70,121,134,131,95,
205,205,206,206,204,204,204,205,202,202,203,204,199,202,202,203,
218,218,218,218,218,218,218,218,218,218,218,218,218,218,218,218,
150,195,199,172,139,131,200,201,181,99,136,200,200,192,85,137,
187,186,119,165,66,41,63,170,195,95,48,173,185,88,131,200,
126,198,209,207,200,208,209,209,206,209,210,209,207,208,208,209,
210,209,210,209,210,209,210,209,210,209,208,208,209,209,209,207,
210,212,206,196,206,206,202,132,209,203,201,198,209,205,205,209,
185,185,195,192,196,197,188,195,192,192,197,192,192,189,188,194,
199,207,210,211,198,208,210,211,203,208,210,211,209,210,211,211,
202,196,197,197,208,206,205,207,209,208,208,207,210,209,209,208,
188,193,195,191,192,189,193,192,193,192,193,194,145,198,192,190,
159,184,179,51,182,207,90,108,194,151,61,208,185,58,175,193,
100,139,199,202,110,83,191,201,136,75,181,189,189,115,162,186,
196,191,94,181,195,170,95,204,198,113,150,200,197,88,175,191,
185,62,178,186,62,180,193,171,187,191,185,177,188,186,177,179,
160,108,86,59,54,48,38,134,43,83,183,183,152,193,183,178,
197,198,197,197,198,196,196,197,197,200,198,198,199,195,196,198,
202,207,210,207,205,207,208,186,168,200,183,121,110,197,199,109,
112,190,200,139,116,198,193,102,154,196,169,149,199,201,168,198,
191,191,180,194,190,194,197,194,197,193,190,191,188,189,194,196,
166,85,191,190,111,100,202,197,81,165,199,199,80,189,197,194,
189,140,154,203,200,110,190,204,190,103,201,202,167,122,190,193,
194,181,90,188,194,85,186,196,110,163,195,190,115,194,186,182,
178,187,184,189,179,186,194,164,182,190,175,62,186,168,61,190,
189,190,203,203,97,202,205,198,94,201,202,197,140,202,195,197,
210,211,212,210,212,211,210,211,210,207,206,205,178,168,123,113,
128,133,173,158,58,52,59,80,168,187,189,185,184,184,187,178,
107,194,205,205,119,202,206,204,194,206,208,204,204,205,202,203,
203,204,206,206,203,206,205,200,205,204,204,193,206,202,115,197,
197,197,193,119,197,196,189,91,191,197,176,90,194,195,164,91,
194,84,71,116,175,181,196,195,182,194,192,192,194,191,189,193,
206,205,207,204,207,208,207,198,202,207,198,120,205,193,141,186,
188,193,188,187,195,185,185,193,189,178,191,186,193,105,74,168,
190
210,210,212,209,210,213,212,207,211,211,210,198,210,210,202,133,
F1 - AlfabetoVQ Pura (continuação)
Vetor
Valores
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
77,59,109,196,178,182,197,190,184,187,184,181,183,185,184,175,
198,207,180,104,199,202,127,151,198,198,91,191,202,186,93,195,
101,194,201,194,101,196,197,195,103,185,193,198,143,196,198,197,
193,193,192,172,192,196,172,152,197,192,100,148,186,192,90,94,
199,206,198,99,206,208,200,193,209,209,206,209,210,209,208,209,
209,211,212,211,210,211,212,211,181,199,209,211,111,184,210,211,
194,197,193,196,198,194,193,171,192,193,193,98,198,196,194,88,
143,153,186,196,100,95,79,67,58,68,126,176,197,197,200,190,
197,111,188,203,180,194,205,205,200,202,207,208,203,207,207,205,
188,195,189,193,195,185,195,191,180,191,187,189,195,193,192,194,
197,196,197,193,191,198,192,198,194,185,191,191,197,200,200,197,
195,206,205,206,197,196,203,198,101,202,202,194,196,201,205,196,
191,166,107,183,206,202,195,198,211,210,210,209,210,211,210,208,
182,125,182,193,192,83,104,170,198,168,186,197,196,192,204,201,
164,160,157,160,156,162,161,155,160,159,156,160,163,161,160,131,
180,181,185,183,146,159,162,178,76,69,177,188,69,182,189,186,
145,157,155,158,144,161,159,157,54,82,150,142,53,39,74,154,
162,35,31,164,162,37,28,164,159,37,29,158,166,33,28,152,
52,44,38,44,145,147,155,145,159,160,156,143,151,151,137,146,
142,151,155,154,139,148,149,148,149,151,151,152,139,150,152,149,
182,171,166,185,182,149,151,185,186,136,161,184,177,149,174,190,
121,42,36,61,142,73,37,51,142,98,31,50,135,106,40,47,
149,144,66,49,152,139,64,47,139,147,71,47,154,146,89,54,
62,100,150,144,51,62,105,151,82,68,50,74,135,100,67,61,
163,158,163,156,160,167,163,160,153,161,156,163,167,160,162,164,
146,103,50,100,143,103,49,97,148,102,49,85,145,104,50,83,
130,131,135,137,142,142,139,141,139,146,143,144,143,145,138,145,
138,156,156,162,74,107,157,156,48,58,134,154,52,70,153,152,
158,156,152,160,90,74,72,73,140,103,58,51,164,165,69,62,
128,56,41,118,139,49,45,131,137,49,44,138,134,46,51,128,
153,157,149,155,115,117,145,147,65,65,71,114,128,92,63,92,
127,134,74,49,138,138,126,114,132,143,142,148,143,144,147,142,
187,49,121,185,106,57,187,164,42,92,153,168,43,145,184,176,
97,44,37,65,109,43,50,67,103,41,49,89,100,50,51,116,
153,150,145,158,154,157,155,155,149,150,152,155,152,156,151,157,
151,147,143,145,146,141,143,145,142,137,139,139,144,138,144,142,
146,151,155,152,147,140,122,91,118,68,53,49,69,59,75,68,
41,46,75,133,68,37,33,113,111,47,33,83,114,53,36,81,
121,122,109,39,94,129,110,36,42,75,89,49,90,84,56,51,
135,139,146,138,115,138,146,139,64,137,144,141,45,119,137,141,
41,108,119,95,44,114,124,98,39,96,116,103,40,64,111,98,
122,52,59,128,101,41,68,135,76,42,64,136,71,38,53,115,
51,46,42,47,68,35,35,40,109,52,31,37,116,77,32,29,
57,59,121,154,144,151,156,153,153,156,153,153,147,153,150,151,
186,187,187,183,183,155,144,148,157,75,88,100,180,124,79,78,
107,35,124,147,114,30,129,148,112,33,132,151,96,31,139,145,
45,37,52,46,42,27,54,33,33,42,66,44,58,63,120,92,
184,83,138,184,93,79,189,181,67,194,193,183,191,186,183,175,
115,137,143,145,70,107,135,146,46,52,97,133,45,35,40,91,
42,31,129,135,33,30,138,137,34,28,136,138,35,30,124,130,
134,115,53,37,117,77,33,49,68,45,33,48,46,46,46,41,
113,91,69,70,120,71,65,136,88,57,124,170,69,95,161,155,
173,122,58,156,132,64,181,190,78,198,184,179,173,176,180,43,
92,70,119,146,104,51,93,150,119,60,77,147,125,71,66,137,
43,67,76,93,85,147,44,157,182,97,122,156,83,97,164,159,
51,130,152,154,48,138,151,153,48,139,155,151,49,129,156,148,
121,92,65,73,56,38,36,66,37,79,119,107,91,124,140,121,
39,67,99,113,37,40,73,94,31,32,35,53,43,39,33,35,
90,93,84,90,131,123,127,116,21,20,30,35,21,22,18,16,
139,151,118,50,146,149,115,46,153,153,152,137,150,157,148,155,
115,135,141,109,81,132,138,99,62,137,137,71,67,128,123,73,
44,44,46,59,38,44,65,86,35,35,88,126,37,38,75,126,
69,55,52,57,77,83,94,76,126,131,133,108,44,36,29,44,
51,64,130,148,51,69,144,148,104,140,152,138,143,151,146,145,
255
151,148,146,150,152,148,155,150,131,139,149,140,60,63,108,139,
F2 - Alfabetos VQ/BTC
F2.1 - Bit Maps
Vetor
Valores
Vetor
Valores
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
1,0,0,0,1,1,0,0,1,1,0,0,1,1,1,1,
0,1,1,1,0,0,0,1,1,0,1,0,1,1,0,1,
1,0,0,0,1,0,0,0,1,1,1,1,1,1,1,1,
1,1,1,0,0,0,1,0,1,0,0,0,0,0,1,1,
1,1,0,0,0,0,0,1,1,0,0,1,1,0,0,0,
1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,
0,0,1,1,0,1,1,0,1,0,0,1,0,0,1,1,
1,0,0,0,1,1,1,1,0,0,0,0,0,1,0,1,
1,1,0,0,1,0,1,0,1,0,0,0,1,1,0,0,
0,0,0,0,1,1,1,1,0,1,1,1,1,0,0,1,
1,1,1,1,0,0,0,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,
1,1,0,0,0,0,1,1,1,1,1,0,0,1,0,0,
0,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,
1,1,1,0,0,1,0,1,0,1,0,0,0,1,1,1,
0,1,1,1,0,0,1,0,1,1,1,1,0,0,1,0,
0,1,1,0,1,1,0,0,0,0,1,0,0,1,0,1,
0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,
0,0,1,0,0,1,0,0,1,1,1,1,0,0,0,0,
1,0,0,1,0,0,0,0,0,1,1,0,1,0,0,1,
1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,
1,1,1,1,0,0,1,0,0,0,1,1,0,0,1,0,
1,1,0,0,1,1,0,1,1,1,1,1,0,0,0,0,
0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,
0,0,0,0,1,1,0,1,1,0,1,0,1,0,1,1,
0,1,1,1,1,1,1,0,0,1,1,0,0,0,0,1,
0,1,0,1,1,0,0,1,1,0,0,0,1,0,1,1,
0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,1,
1,0,0,0,1,1,1,0,1,1,0,0,1,1,1,0,
0,0,1,1,0,0,1,1,0,0,1,1,0,1,1,1,
1,1,1,1,1,1,1,0,1,0,0,1,1,0,1,1,
0,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,
1,1,0,0,1,0,0,1,1,0,1,0,1,1,0,0,
0,0,1,1,0,0,0,0,1,1,1,0,1,1,1,1,
0,0,0,1,0,0,1,1,0,0,1,1,0,0,0,1,
1,1,1,0,1,1,0,0,0,0,0,0,0,0,1,0,
1,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,
0,1,0,1,1,1,0,1,1,0,0,1,1,1,0,1,
0,0,0,0,1,0,0,0,1,1,0,0,1,1,1,0,
0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,
1,1,0,0,1,1,0,0,1,0,0,0,1,1,0,0,
1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,0,
0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,1,
0,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,
1,0,1,0,1,0,0,0,0,1,1,0,1,0,0,1,
0,0,0,1,0,0,1,1,1,0,1,1,0,0,1,1,
0,0,0,1,0,1,1,1,0,1,0,1,0,1,1,0,
0,1,1,1,1,0,1,0,0,0,1,1,1,0,1,0,
0,0,0,1,1,0,1,1,1,1,1,0,0,1,0,0,
0,1,1,0,0,1,1,1,0,0,0,0,1,1,1,1,
1,1,1,1,1,0,1,0,0,1,0,0,0,1,0,0,
0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,1,
1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,
1,0,0,1,1,0,0,1,1,1,0,1,0,0,1,0,
0,1,1,1,0,0,1,1,1,0,0,1,0,0,0,1,
0,0,0,1,0,1,1,0,1,0,1,1,1,1,0,0,
0,0,0,0,1,1,0,0,1,0,0,0,1,0,1,1,
1,0,1,1,0,1,0,0,1,0,1,1,0,0,0,0,
1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
1,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,
1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,0,
1,0,0,1,1,0,1,1,0,0,0,1,1,1,1,0,
0,0,0,1,1,0,0,1,1,1,1,1,0,0,0,1,
0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,
0,0,0,1,0,0,0,0,1,0,0,0,1,1,1,0,
1,1,1,0,0,0,0,1,1,1,0,1,1,0,1,0,
1,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,
1,1,0,0,1,0,1,1,1,1,0,0,0,0,1,1,
0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,1,
0,1,1,0,1,1,1,1,1,0,0,0,1,1,0,1,
0,1,1,1,0,0,0,1,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,0,0,0,0,1,1,1,0,1,0,
0,0,1,0,0,0,0,1,1,1,1,0,0,0,0,1,
0,0,0,1,0,1,0,1,1,1,1,1,0,0,0,1,
0,1,0,0,1,0,1,1,1,0,1,0,1,1,1,1,
1,1,0,1,1,0,1,0,0,1,0,0,1,1,0,1,
0,1,1,1,1,0,1,1,0,0,0,0,1,1,0,1,
1,1,1,0,1,0,0,0,0,0,0,0,0,0,1,1,
1,0,1,0,0,1,0,0,1,0,1,0,1,1,1,0,
1,0,0,1,1,0,1,0,1,0,0,1,0,1,1,0,
0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,
0,1,1,1,0,1,1,0,1,1,0,0,1,1,1,0,
1,0,0,0,0,1,1,0,1,0,1,1,1,1,1,1,
0,1,1,1,1,1,1,0,1,1,0,0,1,0,0,1,
0,1,0,0,0,0,0,1,1,1,1,0,1,1,0,0,
1,0,0,1,1,0,0,0,1,0,0,0,1,1,1,1,
0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,
0,1,0,1,1,0,0,1,0,0,0,0,0,1,1,1,
0,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,
0,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,
1,1,0,1,0,0,1,1,0,0,0,1,1,0,0,0,
0,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1,
1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,1,
1,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,
0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,1,1,1,1,1,0,1,0,1,1,1,1,
0,1,1,0,0,1,0,1,0,0,1,1,1,1,1,1,
1,1,0,1,1,0,0,1,1,0,1,1,0,1,1,1,
0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,
1,1,1,1,1,1,0,1,1,1,0,0,0,0,0,1,
0,0,0,0,1,0,1,1,1,0,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,1,0,0,0,0,1,1,1,
1,1,1,0,1,1,0,0,1,0,0,0,0,0,0,1,
0,1,1,0,1,1,1,0,0,0,1,1,1,0,0,0,
0,1,1,0,1,0,1,1,0,1,0,0,1,0,1,1,
0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,
0,1,1,1,0,0,1,0,0,0,1,0,0,1,1,1,
1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,0,
0,1,0,1,0,1,1,1,1,0,0,0,0,0,1,1,
1,0,0,1,0,0,1,1,0,0,0,0,1,1,1,0,
0,0,0,1,1,1,0,1,0,1,1,0,0,1,0,1,
0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,0,1,1,0,0,1,1,
0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,1,
1,1,1,1,1,1,1,1,1,0,1,1,0,0,1,1,
0,0,0,0,1,1,0,1,0,1,1,1,1,1,0,0,
0,0,0,0,0,1,0,0,1,1,1,1,1,1,1,1,
1,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,
F2.1 - Bit Maps (continuação)
Vetor
Valores
Vetor
Valores
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
174
176
177
178
179
180
181
0,0,0,1,0,0,0,0,1,1,1,1,0,1,1,0,
1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,
1,1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,
0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,
0,0,1,1,0,1,0,0,0,1,1,1,0,1,1,0,
1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1,
0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,
1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,
1,1,1,0,0,1,1,0,0,0,1,0,0,1,1,0,
0,0,0,0,1,0,1,1,1,0,0,1,1,1,1,1,
1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,0,
1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,
0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,
1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
1,1,1,1,0,0,1,1,0,0,1,1,0,0,1,1,
0,1,1,0,0,0,0,1,0,1,0,0,1,1,1,1,
1,1,1,0,1,0,0,1,1,1,1,1,0,0,0,0,
1,0,1,0,0,1,0,0,1,0,0,1,1,1,1,0,
1,1,0,0,1,1,0,0,1,1,1,1,1,1,1,1,
1,1,1,1,1,0,0,1,0,0,0,1,0,0,0,1,
1,1,1,1,1,0,0,1,1,1,1,0,0,0,0,0,
0,1,0,1,0,0,1,1,1,0,0,0,0,0,1,1,
1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,
0,0,0,0,0,1,1,1,1,1,1,1,0,0,1,1,
0,1,0,0,0,0,1,0,1,0,0,1,1,0,1,0,
1,1,1,1,1,0,0,1,0,0,0,0,1,0,0,0,
1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,0,
1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,1,
1,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,
0,0,1,1,1,1,1,1,1,1,1,0,1,1,0,0,
1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,
0,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,
1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,1,
1,1,1,0,1,1,0,1,1,0,1,0,0,0,0,0,
0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,
0,1,1,1,0,0,1,1,0,0,1,1,0,1,1,1,
1,1,1,0,0,0,1,0,1,1,0,1,1,1,0,1,
0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,1,
0,1,1,1,1,0,0,1,1,0,0,0,0,0,1,0,
1,0,1,1,1,1,1,1,0,1,0,1,0,0,0,1,
0,1,1,0,0,0,1,1,1,0,1,1,1,1,0,1,
0,0,1,1,1,0,0,1,1,0,1,0,1,0,0,1,
0,1,1,0,0,0,1,0,1,1,1,1,0,1,1,1,
1,0,0,0,1,1,0,0,0,0,1,1,0,1,1,0,
1,1,1,0,1,1,1,0,0,1,0,1,0,0,0,0,
1,1,1,1,0,0,1,1,0,1,1,0,0,1,1,0,
0,0,0,1,0,1,0,1,0,1,1,1,1,0,0,1,
0,0,1,1,1,0,0,0,1,0,1,1,1,0,1,1,
1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,1,
1,1,1,0,0,1,1,1,0,0,1,1,0,0,0,1,
0,1,1,1,0,0,1,1,0,0,0,1,1,0,0,1,
1,1,1,0,1,1,0,1,1,0,0,1,1,0,0,1,
1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,
1,0,1,0,0,0,0,0,0,0,1,1,0,1,1,1,
1,0,0,1,1,0,0,1,1,0,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,1,1,0,1,1,0,0,
0,1,1,0,0,1,1,0,1,1,0,1,1,1,0,1,
1,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,
0,0,1,1,1,0,1,1,0,0,1,1,0,1,1,1,
1,1,1,1,1,0,1,1,1,0,1,1,0,0,1,1,
1,1,0,1,1,0,1,1,0,0,1,1,0,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,1,
0,1,0,1,0,1,1,1,0,0,1,0,1,0,0,1,
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
0,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,
0,1,1,1,0,1,0,0,1,0,1,0,1,1,0,1,
0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,
1,1,1,0,1,0,0,0,1,1,1,0,1,1,0,0,
0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,
1,1,1,0,1,1,0,0,1,0,0,1,1,1,0,1,
1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,0,
1,1,1,0,1,1,0,1,1,1,0,1,1,0,0,0,
0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,
1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,
0,1,1,1,1,1,1,0,0,0,1,0,1,1,1,1,
1,0,0,1,1,0,0,1,1,1,0,1,1,1,1,1,
1,1,1,1,1,0,0,1,0,0,0,0,0,0,0,1,
1,0,1,0,0,1,0,0,1,1,0,0,1,1,0,1,
1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,
0,0,0,0,1,1,0,0,1,1,1,1,1,1,1,0,
1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,0,
1,1,1,1,1,1,1,0,1,1,0,1,0,0,0,0,
0,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,
1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,1,
1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,
0,0,0,0,1,1,0,0,1,1,1,1,1,1,1,1,
0,0,0,0,1,0,1,1,1,1,0,1,0,1,1,1,
1,1,1,1,1,1,0,1,0,0,1,1,0,0,0,0,
1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,
1,1,0,0,1,1,0,0,1,1,0,0,1,1,1,0,
0,1,1,1,0,0,1,1,0,0,0,0,1,1,1,0,
0,1,1,1,1,0,0,1,0,0,1,1,1,0,0,1,
1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,
0,1,0,1,0,1,1,0,1,1,1,1,1,1,0,1,
0,1,1,1,0,0,1,1,0,0,1,1,0,0,1,1,
1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,
1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,
0,1,1,1,0,1,1,1,1,0,0,1,1,0,0,0,
1,1,0,0,1,1,1,0,1,1,1,1,1,1,1,0,
1,1,1,1,0,0,1,1,0,0,1,1,0,0,1,1,
1,0,0,1,1,0,0,0,1,0,0,1,1,0,0,1,
1,1,0,1,1,1,0,1,1,0,1,0,0,1,0,0,
1,1,1,0,0,0,1,1,0,1,0,0,0,1,1,1,
1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,
1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,
1,1,1,0,1,1,1,1,0,0,0,1,0,0,0,0,
0,1,0,0,1,1,1,1,1,1,0,1,0,1,0,1,
0,1,0,1,0,1,1,0,0,1,1,1,0,0,1,1,
1,0,0,1,0,0,0,1,1,0,0,1,0,0,0,1,
0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0,
0,0,0,0,1,0,1,1,0,1,1,0,1,0,1,1,
1,0,1,1,0,0,1,1,0,0,0,0,0,1,0,1,
1,0,0,1,0,0,1,1,1,0,0,1,0,0,1,1,
0,0,0,0,1,0,0,0,0,1,1,1,1,1,1,1,
0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,1,
1,1,1,1,0,0,1,1,0,0,1,1,0,0,0,1,
0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,
1,1,1,0,1,0,1,0,0,0,0,1,0,0,1,1,
1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1,
1,0,0,0,1,1,1,1,1,0,1,1,0,1,1,0,
1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,
0,0,0,0,0,1,0,1,1,1,1,1,0,1,1,1,
0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,
1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,
1,0,1,1,1,0,0,1,1,0,0,1,1,0,0,1,
0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,
1,1,0,0,1,1,0,0,1,0,1,0,1,1,1,1,
182
183
184
185
186
1,1,1,0,1,1,1,0,1,0,1,0,0,1,1,0,
0,0,1,1,0,0,0,0,1,0,1,1,1,1,1,1,
0,0,1,1,0,1,1,1,0,0,1,1,0,1,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,
1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,
251
252
253
254
255
1,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,
0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,
0,0,0,0,1,1,1,1,0,1,1,1,0,1,1,0,
0,0,1,1,0,1,1,0,0,1,1,0,0,1,1,1,
1,1,1,1,1,1,0,1,1,0,0,1,0,0,1,1,
F2.2 - Parâmetros Estatísticos
Vetor
Valores (média, variância)
Vetor
Valores (média, variância)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
122.660061,14.630208,
166.452982,11.892417,
122.040132,48.739144,
173.017442,15.075194,
108.786830,25.603797,
126.507530,37.913354,
168.801006,14.994211,
188.790179,11.757936,
132.122984,14.118011,
168.367537,20.926672,
80.671528,45.943914,
150.756818,34.378218,
136.084722,17.540129,
160.048112,10.046899,
163.393162,11.390590,
178.673684,6.540500,
133.819318,9.643674,
160.767747,13.222796,
162.712500,8.489610,
165.196003,8.672572,
120.901786,10.189024,
147.586806,12.329706,
146.445975,8.841190,
115.084777,46.716264,
144.495640,17.098156,
149.882161,9.620783,
154.375833,17.040189,
101.379425,32.421676,
118.547991,18.543485,
102.179630,42.834359,
144.066886,34.196265,
164.165296,15.263474,
112.072222,13.952094,
110.237903,34.461273,
71.432500,47.574724,
149.158654,19.076350,
127.995833,10.793350,
147.395047,15.932904,
63.345982,42.804012,
96.626225,39.374008,
147.464120,27.407595,
126.075321,21.465227,
151.743207,23.045187,
119.758427,34.202556,
136.722458,13.005624,
153.695455,11.845430,
134.383255,25.088648,
138.633333,8.784531,
143.055664,9.253168,
143.308712,21.085851,
127.375000,15.023367,
95.835648,19.817961,
164.937500,26.354108,
191.809593,6.749799,
187.887801,15.697598,
199.670455,13.076421,
193.939167,10.445313,
191.238750,8.159979,
169.176948,56.737147,
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
197.685788,9.493933,
166.693097,38.433735,
189.020631,7.910595,
163.111979,32.363907,
171.565000,33.901940,
149.070312,42.335843,
195.541912,8.875598,
170.449548,40.928777,
195.918750,17.705241,
192.786538,11.883032,
184.575000,11.874762,
192.384740,9.387552,
196.509511,13.669685,
188.994693,9.735927,
186.981456,10.660254,
186.892045,13.127433,
204.685000,10.940076,
180.506250,16.770973,
93.243056,81.271253,
193.649038,8.657977,
199.902289,9.842769,
179.046145,13.426672,
179.971208,27.167321,
191.127604,16.453671,
184.598485,42.340967,
173.776119,6.686184,
135.447368,64.118648,
193.313596,14.144015,
142.708022,50.246103,
180.667411,11.153793,
159.511130,45.010744,
184.062500,19.276676,
179.906609,22.124966,
190.992585,5.089260,
130.200397,70.729887,
177.508721,32.585712,
190.060096,6.926521,
193.334936,7.115701,
148.653409,76.053402,
180.273098,43.885322,
176.797554,17.925692,
190.798537,11.107092,
195.667254,11.266166,
138.684211,72.721698,
187.311141,4.931310,
176.110950,9.070012,
186.568681,8.804794,
193.310577,5.284038,
188.790064,19.922855,
173.326888,10.614507,
187.537202,6.930832,
185.662371,7.799866,
157.221154,11.393311,
158.507353,50.789223,
190.475260,9.400847,
170.021368,50.288550,
181.898515,5.937358,
140.678571,59.136092,
178.641204,9.827631,
F2.2 - Parâmetros Estatísticos (continuação)
Vetor
Valores
Vetor
Valores
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
174
176
177
178
179
180
181
185.522368,10.033033,
134.057031,50.321358,
113.522879,55.464425,
125.916096,65.265764,
184.010000,6.874449,
195.237926,6.942452,
166.664062,44.212118,
156.497748,59.969791,
174.326480,21.872126,
201.791667,7.175377,
28.702035,17.599197,
135.592988,80.699642,
112.257812,83.246407,
190.619318,13.597420,
102.882955,52.733041,
161.832880,39.625734,
182.313131,13.071722,
187.833104,8.464343,
182.739500,10.333967,
163.610294,66.267441,
125.059524,82.014340,
182.809028,8.088034,
184.737500,5.066198,
151.646341,50.826926,
149.091500,59.985026,
188.923828,5.642872,
184.343750,14.917069,
119.530172,73.664363,
180.893797,8.438465,
186.192434,6.230871,
145.275768,67.748333,
172.900162,27.438398,
176.276290,12.273802,
184.255357,9.104918,
107.279948,71.130481,
154.093112,66.939966,
220.364583,3.505430,
186.673387,25.138086,
125.076087,31.326579,
215.109076,2.626171,
221.658046,2.488395,
178.708841,37.690167,
156.101562,37.209096,
216.540179,2.820415,
219.651950,2.421615,
214.713579,3.813705,
204.952148,4.702638,
217.858173,4.166176,
218.152574,2.559545,
211.706344,2.887396,
155.631579,28.152531,
164.875496,49.608060,
177.146127,51.463984,
200.558532,32.739367,
131.071314,32.199903,
212.921429,7.140859,
200.870471,26.940700,
162.038068,56.234577,
197.984375,6.899427,
182.924851,34.365686,
182.961648,48.395458,
195.787660,29.632303,
192.158288,32.018139,
209.534091,6.140207,
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
186.463608,30.814727,
207.333183,4.280317,
190.756860,36.869838,
212.988542,4.095297,
186.683494,37.063218,
174.332163,38.815585,
195.636905,37.459646,
171.299375,45.017260,
209.497951,11.829298,
194.562500,23.165508,
190.416274,42.702860,
181.761765,39.313982,
211.127301,4.367664,
196.015306,4.869968,
209.482955,3.443493,
201.384259,20.799785,
213.510954,2.721503,
176.455078,42.333093,
167.530899,6.454589,
170.367618,11.589771,
140.431352,41.635281,
92.952560,67.985326,
126.284299,55.141515,
157.369411,7.937777,
170.856647,7.963566,
84.691092,57.082710,
122.803161,42.095873,
108.654634,41.772873,
168.299457,9.488372,
92.160618,54.645172,
152.642113,8.244507,
139.631410,22.370575,
129.780114,44.055526,
97.387769,60.224057,
134.622962,37.718196,
141.555804,27.657741,
117.867537,62.906599,
54.305651,35.891715,
160.505271,6.938280,
155.146046,8.969142,
116.400773,39.912972,
76.089844,38.323472,
68.123106,56.743121,
144.239583,13.516810,
105.281960,61.438518,
89.318412,32.061222,
49.841734,46.257243,
158.117077,15.087337,
151.047743,13.871393,
87.503378,48.909380,
42.920608,23.521458,
160.841755,21.365525,
83.937500,65.749475,
95.830177,47.807520,
39.741848,35.823962,
116.045551,26.441737,
137.222128,31.558736,
88.783764,40.972353,
108.029533,48.757433,
123.399390,25.829741,
76.215909,59.089488,
63.768382,27.353785,
57.273674,55.311442,
140.467905,16.886357,
182
183
184
185
186
206.455943,17.473661,
175.158125,47.080384,
201.303571,4.074751,
206.282328,23.800252,
177.204861,61.019771,
251
252
253
254
255
131.397569,19.520900,
78.166016,29.305242,
70.815000,68.088864,
129.656977,26.571149,
140.935516,12.468876,