Imagem Digital
Conceitos, Processamento e
Análise
Parte 1: Conceitos básicos
1. Imagem e funções
2. Imagem digital: amostragem, quantização e codificação
3. Re-amostragem de funções
Imagem:
Modelo Matemático: Função
Níveis de cinza
100%
80%
60%
40%
20%
0%
x
Posição ao longo da linha
L
L : 0, w 0, h  2  C
u 
   L
v
L(u,v)
v
u
Função
Imagem colorida
v
G
R
u
B
Imagem coloridas como 3 canais de cor
canal verde
Imagem Digital
Amostragem, quantização e
codificação
Amostragem, quantização e
codificação de f(x)
f(x)
amostra
partição do eixo x
x
Amostragem, quantização e
codificação de f(x)
f(x)
6

5

4
3
2


amostra
quantizada









1
0
x
codificação = (3, 4, 5, 5, 4, 2, 2, 3, 5, 5, 4, 2)
Anatomia das máquinas atuais
Câmeras atuais
Digitalização de Imagens
Discretização espacial (amostragem)
Processos básicos
64x54
amostragem
Imagem de tons
contínuos
Imagem amostrada
quantização
55 55 55 55 55 55 55
55 20 22 23 45 55 55
64x54 - 16 cores
55 55 10 09 11 55 55
55 55 43 42 70 55 55
55 55 28 76 22 55 55
8*55, 1*20, 1*22, 1*23, ….
55 55 55 55 55
55
55
codificação
Imagem amostrada,
quantizada e codificada
Imagem amostrada e
quantizada
Imagem Digital:
Histogramas
Uma outra maneira de ver a informação da imagem: probabilidade de
ocorrência de um determinado valor, uso do intervalo [0,255], contraste,...
Histogramas de Imagem Colorida
Propriedades básicas de uma
Imagem Digital
Problemas associados a re-amostragem de
um sinal digital f(x)
f(x)
6

5

4
3
2
1

função original






função reconstruída
pelo vizinho mais
próximo



0
função reconstruída
por interpolação
linear

x
(a) aumento de resolução
Re-amostragem de f(x)
f(x)
6

5

4
3
2
1

função original






função reconstruída
pelo vizinho mais
próximo



0
função reconstruída
por interpolação
linear

x
(b) redução de resolução
Freqüência de Amostragem
f(x)
x
f(x)
x
Imagem Digital
Conceitos, Processamento e Análise
Parte 2 - Eliminação de ruídos e realce de
arestas
Aplicações da Transformada de
Fourier
Redução de ruídos
• Dada uma imagem I com um ruído n, reduza n o
máximo que puder (preferencialmente elimine n
completamente) sem alterar significativamente I.
Iˆ(i, j)  I (i, j)  n(i, j)
s
SNR 
n
s
SNRdB  10log10
n
s
 100
20 dB significam
n
Dois tipos básicos de ruídos
• Ruído Gaussiano branco : processo estocástico
de média zero, independente do tempo e dos
espaço.
n (i, j ) ~ n (i  i0 , j  j0 ) é o mesmo processo estocástico
que não varia no tempo.
n (i, j )  0
n (i, j )
é uma variável aleatória com a distribuição:
x2
G ( x) 

1
2 2
e
2 
Dois tipos básicos de ruídos
• Ruído impulsivo: causado por erro de
transmissão, CCDs defeituosos, etc...
Também chamado de pico e de sal e pimenta.
xl
0
nsp (i, j )  
imin  y (imax  imin ) x  l
x, y  0,1
são v.a. uniformemente distribuídas
imin, imax, e l são parâmetos de controle da quantidade de ruídos.
Exemplo de ruído Gaussiano (=5) e Impulsivo (
=0.99)
Imagem com ruído impulsivo
Uso da mediana
223
204
204
204
204
204
204
204
204
204
204
204
204
223
171
120
120
120
18
120
50
120
120
120
120
120
120
171
171
120
120
120
116
120
120
120
120
120
120
120
120
171
138
120
120
120
120
120
50
120
97
120
120
120
120
171
171
120
120
120
120
120
120
120
120
120
187
120
120
242
172
120
120
120
120
120
120
120
120
120
120
120
120
171
171
120
120
120
120
120
179
120
120
120
120
167
120
171
171
120
120
120
120
120
120
235
120
120
120
120
120
171
171
120
120
120
120
120
120
235
120
76
175
120
120
171
171
120
120
120
120
120
120
120
120
120
120
120
120
171
171
120
120
120
120
120
120
120
123
120
120
214
120
114
171
120
120
120
120
120
120
120
120
120
120
120
143
171
171
120
120
120
232
120
120
198
120
120
120
120
120
171
203
171
171
171
171
171
171
171
171
205
171
171
171
203
Iij = mediana Ωij
Sinal com ruído
f3( x ) := 10 cos( 2  x )6 sin( 10  x ).8 cos( 40  x )
20
15
10
5
0
-5
-10
-15
-20
Suavização
f
h
f i 1  2 f i  f i 1
hi 
4
Filtragem Gaussiana
20
15
10
5
0
-5
-10
-15
-20
w1+w2+w3
filtro
w1+w2
Mascara ou Filtro
f i 1  2 f i  f i 1
hi 
4
ou:
hi 
n 1
g
k 0
( k i )
fi
se l  1
0
1 / 4
se l  1


g l  2 / 4 se l  0
1 / 4 se l  1


se l  1
0
Convolução
n 1
hi   g ( k i ) f i
k 0
t 
h( x ) 
 g (t  x) f ( x)dt
t  

h( x)  f  g   f (u) g ( x  u)du

Ilustação da convolução
t 
h( x ) 
g
(
t

x
)
f
(
x
)
dt

t  
Ilustração da convolução
t 
h( x ) 
g
(
t

x
)
f
(
x
)
dt

t  
Discretização da Gaussiana 1D
1
e
2 
G ( x) 
0.3

x2
2
0.2
0.1
-4
-3
1
1
4
-2
2
-1
0
1
1
1
64
1
2
1
1
16
6
15
20
15
3
4
6
6
1
4
4
1
2
Discretização da Gaussiana 2D
G ( x, y ) 
1
1 
2

16

1

1
e
2 
2
4
2
1
2

1

x2  y2
2
2
1
4
1 
7
273 
4

1
4
7
4
16
26
26
41
16
26
16
4
26
7
16
4
1
4

7

4
1

Separabilidade do filtro gaussiano
207
247
38
131
38
62
90
129
234
231
211
175
44
1
26
236
58
75
128
112
210
141
125
168
58
1
1
4
2
1
1 
2
16 

1
2
4
2
1
2

1

130
117
129
125
90
88
129
93
92
130
117
129
125
90
88
129
93
92
1
185
113
84
93
145
207
151
66
18
107
84
111
154
140
130
1 
1 
2
4 
1 
Imagem filtrada com um filtro passa baixa
Arestas e cantos
• Locais de mudanças significativas na intensidade da
imagem
Edgedels = edge elements
Tipos de arestas
degrau(step)
rampa(ramp)
cume(roof)
impulso(spike)
Gráfico sem e com ruído
Derivadas e arestas
f(x)
f(x)+n(x)
| f'(x)+n'(x) |
f"(x)+n"(x)
Série de Taylor
(x 2 ) "
f ( x  x)  f ( x)  (x) f ( x) 
f ( x)  O(x 3 )
2
'
Com x=1, f(x)=fi e f(x+x)=fi+1
f i 1  f i  f
'
1

f
2
i
"
i
(a)
"
(b)
Com x=-1, f(x)=fi e f(x+x)=fi-1
f i 1  f i  f
'
i
1

f
2
i
Aproximações para derivadas
f(x)
fi-1
i-1
(a-b) 
(a+b) 
f
'
f
"
i
i
fi
fi+1
i
i+1
x
 ( f i 1  f i 1 ) / 2
 ( fi 1  2 fi  fi 1 )
Em 2D
Gradiente
 f




x
f ( x, y )   f


y 


f  x, y  f xn 1 , ym   f  xn , ym 

x
x
f x, y  f xn , ym1   f xn , ym 

y
x
 1 1
1
1
 
Convolution Kernels
Laplaciano
2 f
2 f
 f ( x, y ) 

2
x
y 2
2
4
1
1


 4  20 4 
1
4
1 

Finite differences
I x  I *1 1
I
Khurram Hassan-Shafique
1
Iy  I * 
 1
Classical Operators
Prewitt’s Operator
1 1
1 1


1 1
1
 1
Differentiate
Smooth
1 1 1
1 1 1


1
1
 
1 0  1
1 0  1


1 0  1
1 1 1
0 0 0


 1  1  1
Khurram Hassan-Shafique
Classical Operators
Sobel’s Operator
1 1 
2 2


1 1 
Smooth
1
 1
1 0  1 
2 0  2


1 0  1 
Differentiate
1 2 1
1 2 1


1
1
 
2
1
1
0

0
0


 1  2  1
Khurram Hassan-Shafique
Detecting Edges in Image
• Sobel Edge Detector
*
1 0  1 
2 0  2


1 0  1 
d
I
dx
Image I
*
2
1
1
0

0
0


 1  2  1
d  d 
 I    I 
 dx   dy 
2
2
Edges
Threshold
d
I
dy
Khurram Hassan-Shafique
Sobel Edge Detector
d
I
dx
I
d
I
dy
Khurram Hassan-Shafique
Sobel Edge Detector
d  d 
   I    I 
 dx   dy 
2
2
I
  Threshold  100
Khurram Hassan-Shafique
Filtros de realce de bordas
Gradiente
Roberts
Sobel
Laplaciano
Vertical
0
0


0
1
1
2
4

1
0
 1


0
Horizontal
 1
0 

0 

0
1
0
 1
 2

 1

0
0
0
1
4
1
0 
 1

0 

 1
0


0
 1
1
0

4

1
0
1
0
2
0
2
0
0

0

 1
0 

1 

Imagem filtrada com um filtro passa alta
Filtragem LoG do Juiz Virtual
L  255  L
L  0.30 R  0.59G  0.11B
filtro
gaussiano
filtro
laplaciano
1 2 1
1 

2
4
2

16 
1 2 1
 0 1 0 
1 4 1


 0 1 0 
Imagem Digital
Conceitos, Processamento e Análise
Parte 3 - Processamentos apenas
no espaço das cores
Correção gama
Ajustes de contraste e iluminação
Correção gama
L

L
Probabilidade
Função de densidade
de probabilidade
CDF(x)
1
DF(x)
0
Função de densidade
acumulada de
probabilidade
1
x0 x1
x
x1
P{x0  x  x1}   DF ( x)dx
x0
0
x
1
x
CDF ( x )  P{0  x  x}   DF ( x)dx
0
DF ( x) 
x
d
CDF ( x )
dx
Mudança de variavel y = f (x)
x  f 1 ( y)
y=f(x)
1
1
Transformaçã
o monotônica
e limitada ao
intervalo [0,1]
0
1
x
0
1
d
d
dx
DF ( y )  CDF ( y )  CDF ( x)
dx
dy
dy
y
dx
 DF ( x)
dy
DF(y)
f ( x)  CDF ( x)
dy
1
 DF (x )
dx
DF ( x)
DF ( y) 
1
DF ( x)
0
1
x
Equalização de Histograma
L
nj
j 0
n
L'  f ( L)  
1.6
nj
n
1.4
1.2
1
0.8
0.6
0.4
0.2
0
1
2
3
4
5
6
7
8
9
10
11
L
Equalização do histograma
Tons de cinza e negativo
Lx,y = 0.299Rx,y + 0.587Gx,y + 0.114Bx,y
tons de cinza
Lx,y = 255 - Lx,y
Outros exemplos com o
PaintShopProtm
Quantização de cores
Quantização de 24 para 8 bits
A qualidade depende da imagem
Corte mediano
Corte mediano
HDRI (High Dynamic Range Image)
Resultado esperado da Q3 do T1
Imagem Digital
Conceitos, Processamento e Análise
Parte 4 - Codificação e armazenamento
de Imagens
compressão e formatos de
arquivos
Organização de pixels num array
no formato TGA (targa)
y
h-1
...
3
2
1
0
b
b
Pixel (x,y)
g
g
0
r
r
a
a
b
g
r
1
a
b
…
unsigned char *bgra_vector;
…
offset=4*(w*y+x);
blue = bgra_vector[offset];
green = bgra_vector[offset+1];
red
= bgra_vector[offset+2];
alpha = bgra_vector[offset+3];
g
r
w-1
a
x
Outra ordem no plano
Tipo Abstrato Imagem
/*- implementação do tipo Imagem
Image *imgCreate (int w, int h);
void
struct image_imp {
imgDestroy (Image *image);
int width;
/* largura (width) em pixels
*/
int height;
/* altura (height) em pixels
*/
float
int imgGetWidth(Image * image);
*/
*buf;
/* buffer RGB
*/
};
int imgGetHeight(Image * image);
float * imgGetRGBData(Image * image);
void imgSetPixel3fv(Image *image, int x, int y, float * color);
void imgSetPixel3ubv(Image *image, int x, int y, unsigned char *color);
void imgGetPixel3fv(Image *image, int x, int y, float *color);
void imgGetPixel3ubv(Image *image, int x, int y, unsigned char *color);
Image * imgReadBMP(char *filename);
int imgWriteBMP(char *filename, Image * image);
Image * imgCopy(Image * image);
Image * imgGrey(Image * image);
Image * imgResize(Image * img0, int w1, int h1);
Arquivos Targa RGBA
Pixels (bgra,bgra, …,bgra)
Cabeçalho
unsigned char imageType=2
/* RGB(A) sem compressão */
unsigned char bitDepth=32; /* 32 bits por pixel */
unsigned char byteZero=0;
short int
shortZero=0;
/* usado para escrever um byte zero no arquivo */
/* usado para escrever um short int zero no arquivo */
/* escreve o cabecalho */
putc(byteZero,filePtr);
/*
no. de caracteres no campo de id da imagem */
putc(byteZero,filePtr);
/*
imagem nao tem palheta de cores */
putc(imageType,filePtr);
/* = 2 -> imagem "true color" (RGBA) */
putuint(shortZero,filePtr);/* info sobre a tabela de cores (inexistente) */
putuint(shortZero,filePtr);
/* idem */
putc(byteZero,filePtr);
/* idem */
putuint(shortZero,filePtr);
/* =0 origem em x */
putuint(shortZero,filePtr);
/* =0 origem em y */
putuint(img->width,filePtr);
/* largura da imagem em pixels */
putuint(img->height,filePtr);
/* altura da imagem em pixels */
putc(bitDepth,filePtr);
/* numero de bits de um pixel */
putc(byteZero, filePtr);
/* origem canto inf esquedo sem entrelacamento */
Organização de pixels num array
no formato PPM (o mais simples)
0
0
1
2
3
...
h-1
1
00
01
02
03
04
15
16
17
18
...
y
...
2
05
06
07
08
09 10
x
w-1
11
Pixel (x,y)
unsigned char *rgb_vector;
…
offset=3*(w*y+x);
red
= rgb_vector[offset];
green = rgb_vector[offset+1];
blue = rgb_vector[offset+2];
12 13
14
Formato PPM
• File_signature "P6".
• White_space (blanks, TABs, CRs, LFs).
• Width, w, (ASCII decimal characters).
• White_space (blanks, TABs, CRs, LFs).
• Height, h, (ASCII decimal characters).
• White_space (blanks, TABs, CRs, LFs).
• Max_color, max, (ASCII decimal characters).
• White_space (blanks, TABs, CRs, LFs).
• Pixels, (3*w*h bytes rgb components of pixels)
• Comments from # to the end of line
• lines  70 characters
Formato PPM
exemplo
P6
# Created by Paint Shop Pro
358 539
255
=?:?A<AC>CE@EFAFGBGHCGHCGHB . . .
Gravação em PPM
int ppm_write(int w, int h, unsigned char *rgb, char *file_name)
{
FILE *fp;
fp = fopen(file_name, "wb");
if (fp == NULL)
return 0;
if (fprintf(fp, "P6\n%d %d\n255\n", w, h) <= 0)
{
fclose(fp);
return 0;
}
if (fwrite(rgb, 3*w*h, 1, fp) != 1)
{
fclose(fp);
return 0;
}
fclose(fp);
return 1;
}
Leitura em PPM
int ppm_read(int *p_w, int *p_h, unsigned char **p_rgb, char *file_name)
{
FILE *fp;
char line[80];
int rgb_size;
int max;
fp = fopen(file_name, "rb");
if (fp == NULL) {
printf(”Error reading %s",file_name); return 0;}
fgets(line,80,fp);
if(strcmp(line,"P6\n")) {
printf(”Wrong signature\n"); return 0; }
while (fscanf( fp, " %d ", p_w ) != 1)
fgets(line, 80, fp);
while (fscanf( fp, " %d ", p_h ) != 1)
fgets(line, 80, fp);
while (fscanf( fp, " %d", &max ) != 1)
fgets(line, 80, fp);
fgetc(fp);
rgb_size=3*(*p_w)*(*p_h);
(*p_rgb) = (unsigned char *) calloc(rgb_size, 1);
if ((*p_rgb) != NULL)
fread( (*p_rgb), rgb_size, 1, fp );
fclose(fp);
return 1;
}
Programa Simples
void main(void){
int w, h;
// dimensões da imagem
unsigned char *rgb;
// bytes de rgb
unsigned char r,g,b,grey; // componentes de cor
int x,y;
long int k;
if (ppm_read(&w,&h,&rgb,"test_in.ppm")==0) return;
for (y = 0; y < h; y++) {
for (x = 0; x < w; x++)
{
k = 3*(y*w+x);
r = rgb[k];
g = rgb[k+1];
b = rgb[k+2];
grey = (unsigned char)(0.3*r+0.6*g+0.1*b);
rgb[k] = grey;
rgb[k+1] = grey;
rgb[k+2] = grey;
}
}
ppm_write(w, h, rgb, "test_out.ppm");
free(rgb);
}
Arquivo BMP
16
17
18
...
00
01
02
03
Pixel 0
04
Pixel 1
05
06
07
08
Pixel 2
Organização dos pixels de uma imagem RGB
no arquivo BMP
09
10
Pixel 3
11
12
13
14
Pixel 4
colocado para garantir
múltiplo de 4
15
Microsoft Windows Bitmap - BMP
Características Principais
•
•
•
•
Mono, 4-bit, 8-bit, 24-bit
Tipo de compressão: RLE / não comprimido
Tamanho máximo: 64K x 64K pixels
Seções (versão 3):
Header
Info. Header
Palette
Bitmap Data
BMP - Header
typedef struct _Win3xBitmapHeader
{
WORD
DWORD
WORD
WORD
DWORD
Type;
/* Image file type 4D42h (“BM”)*/
FileSize;
/* File size (bytes)
*/
Reserved1; /* Reserved (always 0) */
Reserved2; /* Reserved (always 0) */
Offset;
/* Offset to bitmap data in bytes
} WIN3XHEAD;
*/
BMP - Information Header
typedef struct _Win3xBitmapInfoHeader
{
DWORD Size;
/* Size of this Header (40) */
DWORD Width;
/* Image width (pixels) */
DWORD Height;
/* Image height (pixels) */
WORD Planes;
/* Number of Planes (always=1) */
WORD BitCount;
/* Bits per pixel (1/4/8 or 24)*/
DWORD Compression;
/* Compression (0/1/2)
*/
DWORD SizeImage;
/* Size of bitmap (bytes) */
DWORD XPelsPerMeter; /* Horz. resol.(pixels/m) */
DWORD YPelsPerMeter; /* Vert. resol.(pixels/m)
*/
DWORD ClrUsed;
/* Num of colors in the image
*/
DWORD ClrImportant;
/* Num of important colors */
} WIN3XINFOHEADER;
BMP - Palette
typedef struct _Win3xPalette
{
RGBQUAD Palette[ ]; /* 2, 16, or 256 elem. */
} WIN3XPALETTE;
typedef
{
BYTE
BYTE
BYTE
BYTE
struct _Win3xRgbQuad
Blue; /* 8-bit blue component */
Green; /* 8-bit green component */
Red; /* 8-bit red component
Reserved; /* Reserved (= 0)
} RGBQUAD;
*/
*/
BMP - Image Data
Notas
Cada scan line em um arquivo BMP é sempre um múltiplo de 4.
Imagens com1-, 4-, e 8-bits usam uma palheta de cores.
Imagens com 24-bits guardam a cor diretamente, na ordem azul,
verde e vermelho.
O armazenamento da imagem é sempre feito a partir do canto
esquerdo inferior.
Esquemas de armazenamento de imagens
Plano de Cores
Azul
Verde
Verm.
06
Informação é uma
componente da cor
06
07
08
09
...
00
01
02
03
(Data Buffer – Java)
04
05
06
Organização dos pixels de uma
imagem por planos de cores
Codificação uniforme
Uniforme
tons
# pixels
código
tam.
# bits
0
1900
000
3
5700
1/7
2500
001
3
7500
2/7
2100
010
3
6300
3/7
1600
011
3
4800
4/7
800
100
3
2400
5/7
600
101
3
1800
6/7
300
110
3
900
1
200
111
3
600
TOTAL
30000
Podemos melhorar?
Construção da Árvore Huffman
1/7
2500
1/7
2500
2/7
2100
2/7
2100
0
1900
0
1900
3/7
1600
3/7
1600
4/7
800
4/7
800
5/7
600
5/7
600
6/7
300
n0
500
1
200
n0
6/7
1
Construção da Árvore Huffman
1/7
2500
1/7
2500
2/7
2100
2/7
2100
0
1900
0
1900
3/7
1600
3/7
1600
4/7
800
n1
1100
5/7
600
4/7
800
n0
500
n1
n0
5/7
6/7
1
Construção da Árvore Huffman
1/7
2500
1/7
2500
2/7
2100
2/7
2100
0
1900
0
1900
3/7
1600
n2
1900
n1
1100
3/7
1600
4/7
800
n2
4/7
n1
n0
5/7
6/7
1
Construção da Árvore Huffman
1/7
2500
n3
3500
2/7
2100
1/7
2500
0
1900
2/7
2100
n2
1900
0
1900
3/7
1600
n3
3/7
n2
4/7
n1
n0
5/7
6/7
1
Construção da Árvore Huffman
n3
3500
n4
4000
1/7
2500
n3
3500
2/7
2100
1/7
2500
0
1900
n4
n3
3/7
n2
4/7
n1
n0
5/7
6/7
1
2/7
0
Construção da Árvore Huffman
n4
4000
n5
6000
n3
3500
n4
4000
1/7
2500
n6
1/7
n3
3/7
n2
4/7
n1
n0
5/7
6/7
1
n4
n5
2/7
0
Construção da Árvore Huffman
n6
n4
n5
n3
3/7
n2
110
4/7
n1
1110
n0
5/7
11111
6/7
111101
1
111100
1/7
2/7
0
10
01
00
Codificação de Huffman
Uniforme
tons
Huffman
# pixels
código
tam.
# bits
código
tam.
# bits
0
1900
000
3
5700
00
2
3800
1/7
2500
001
3
7500
10
2
5000
2/7
2100
010
3
6300
01
2
4200
3/7
1600
011
3
4800
110
3
4800
4/7
800
100
3
2400
1110
4
3200
5/7
600
101
3
1800
11111
5
3000
6/7
300
110
3
900
111101
6
1800
1
200
111
3
600
111100
6
1200
TOTAL
30000
TOTAL
27000
Redundância de Codificação
r
p(r)
0
1/7
2/7
3/7
4/7
5/7
6/7
1
0.19
0.25
0.21
0.16
0.08
0.06
0.03
0.02
1.00
Code 1
l(r)
000
001
010
011
100
101
110
111
3
3
3
3
3
3
3
3
Lavg=
l(r)p(r)
0.57
0.75
0.63
0.48
0.24
0.18
0.09
0.06
3.00
Code 2
l(r)
11
01
10
001
0001
00001
000001
000000
2
2
2
3
4
5
6
6
Lavg=
l(r)p(r)
0.38
0.50
0.42
0.48
0.32
0.30
0.18
0.12
2.70
rk = tons de cinza em uma imagem, k=0, 1, ..., 1
p(rk) = nk / n
onde nk = número de pixels com tom rk
n = número de pixels da imagem
01 10
001
Lavg 
 1
 l r pr 
k 0
k
0001
k
00001
000000
000001
11
Resultado da Teoria da Informação
 1 
lopt rk   log2 
 pr  

k 

r
0
1/7
2/7
3/7
4/7
5/7
6/7
1
p(r)
0.19
0.25
0.21
0.16
0.08
0.06
0.03
0.02
=1.00
Code 1
000
001
010
011
100
101
110
111
l(r)
3
3
3
3
3
3
3
3
Lavg =
l(r)p(r)
0.57
0.75
0.63
0.48
0.24
0.18
0.09
0.06
3.00
núm erode bits
Code 2
l(r)
11
01
10
001
0001
00001
000001
000000
2
2
2
3
4
5
6
6
Lavg =
l(r)p(r)
0.38
0.50
0.42
0.48
0.32
0.30
0.18
0.12
2.70
log(1/p)
log(1/p)*p
2.4
2.0
2.3
2.6
3.6
4.1
5.1
5.6
Lopt =
0.46
0.50
0.47
0.42
0.29
0.24
0.15
0.11
2.65
Compressão de imagens
Compressão de
Imagens
Sem Perda
Com Perda
• Preserva exatamente o
conteúdo da imagem
• Taxas de compressão 3 : 1
• Preserva de forma controlada
o nível de qualidade da
imagem
• Taxas de compressão que
chegam a valores de mais de
100 : 1
Métodos de compressão
• Sem perdas
– Run length encoding (RLE) - repetição
– Huffman coding - histograma
– Predictive coding - diferenças
– Block coding (LZW) - dicionário
• Com perdas
– Truncation coding - reduz a representação
– Predictive coding - descarta diferenças altas
– Block coding - dicionário aproximado
– Transform coding - descarta frequencias altas
Métodos compostos: JPEG, MPEG
Processo de compressão e
descompressão
Dados da
Imagem
Original
Dados da
Imagem
Original
32, 45, 57,
68, 23, 100,
98, ...
32, 45, 57,
68, 23, 100,
98, ...

Compressão
da imagem

Descompressão
da imagem
32, 45, 57,
68, 23, 100,
98, ...
Imagem Comprimida
Transporte e/ou
Armazenamento
32, 45, 57,
68, 23, 100,
98, ...
Imagem Comprimida
Fundamentos da Compressão de
Imagens
A compressão de uma imagem é obtida quando se elimina a
redundância de:
•codificação
•entre pixels
•psico-visual
Redundância entre pixels
640 colunas x 480 linhas x 1 byte/pixel = 300 KBytes
480*(1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0) = ~18 Kbytes
onde 1 = 32 bytes de preto e 0 = 32 bytes de branco
Compressão - RLE
Objetivo
Reduzir a quantidade de dados redundantes.
Exemplo
AAAAAAxxx
6A3x
Caracterísiticas
Simples e rápido, porém a eficiência depende da
imagem a ser comprimida.
Run-Length Encoding
76
76
76
76
76
78
76 | 5
79
79
78 | 1
79
79
80
79 | 4
80
80 | 2
imagem binária
...
0
0
0
0
7
0
0
0
1
1
1
4
1
0
0
0
5
0
0
1
Compressão do jpeg
Aplicações são tecnologicamente complexas:
exemplo: algoritmo do JPEG
8x8 blocks
Source
Image
B
R
G
DCT-based encoding
FDCT
Quantizer
Entropy
Encoder
Table
Table
Compressed
image data
Equations for JPEG DCT
• Forward DCT:
7
7
1
(2i  1)  x  
(2 j  1)  y  
DCT ( x, y)  CxC y  Spixel(i, j )  cos
 cos
4
16
16
x 0 y 0
whereCxC y 
1
for x,y  0; otherwiseCx , C y  1.
2
• Inverse DCT:
1 7 7
(2 x  1) j  
(2 y  1)
pixel ( x, y )    Ci C j DCT (i, j )  cos
 cos
4 x 0 y 0
16
i 
where Ci , C j 
1
for i, j  0; otherwise Ci , C j  1.
2
Increasing frequency
Visualization of Basis Functions
Increasing frequency
T1 Comparação de cores
p1
p2
int comparaCor(const void * p1, const void * p2)
{
int *c1 = (int *) p1; /* aponta para o byte red da cor 1 */
int *c2 = (int *) p2; /* aponta para o byte red da cor 2 */
/* compara o canal vermelho */
if (*c1 < *c2) return -1;
if (*c1 > *c2) return 1;
/* compara o canal verde, uma vez que o vermelho e' igual */
c1++; c2++;
if (*c1 < *c2) return -1;
if (*c1 > *c2) return 1;
/* compara o canal azul, uma vez que o vermelho e o azul sao iguais */
c1++; c2++;
if (*c1 < *c2) return -1;
if (*c1 > *c2) return 1;
/* sao iguais */
return 0;
}
T1 Median Cut
k0
typedef struct {
int axis;
float error;
int k0;
int k1;
float red,green,blue;
} Cell;
k1