1
PUCPR- Pontifícia Universidade Católica Do Paraná
PPGIA- Programa de Pós-Graduação Em Informática Aplicada
PROF. DR. JACQUES FACON
ALGORITMO DE AFINAMENTO EM DOIS SUBCICLOS PARA
IMPLEMENTAÇÕES PARALELAS EM MÁQUINAS SIMD
Resumo: Um novo algoritmo de afinamento paralelo com dois sub-ciclos está sendo proposto e
comparado com outro algoritmo de afinamento paralelo de 8-conectores.
Questões Computacionais são também relatadas baseadas na implementação do algoritmo de afinamento
paralelo nas máquinas do SIMD CM-200 e MasPar MPP-12000.
Palavras Chaves - Implementação Paralela, algoritmo de afinamento paralelo, máquinas SIMD,
esqueletização.
1 Introdução
O afinamento paralelo é visto como uma
aproximação de afinamento ou esqueletização, devido ao
crescimento real de arquiteturas paralelas e a real
possibilidade do computador ser utilizado como sistema
de visualização.
É muito grande o crescimento de algoritmos
paralelos baseados em redes neurais e afinamento
tridimensional, gerando assim representações muito
satisfatórias. Os algoritmos de afinamento paralelo são
caracterizados pela repetição do processo de eliminação
simultânea de todos os pontos de contorno “apagáveis”
da imagem. Para ser eficiente, o numero de repetições ou
iterações deve ser igual a metade da largura máxima dos
objetos presentes na imagem.
É óbvio que quanto menos tempo o algoritmo
levar para processar, melhor será o processo, sobre a
restrição que evitar erosão excessiva e manter as curvas
as mais perfeitas possíveis.
-Reduzir o número de iterações e o tempo de
complexidade de cada iteração
- Produzir perfeitamente linhas afinadas 8conectadas
- Prevenir a erosão excessiva
Esse algoritmo descreve que os pontos são
eliminados a partir da análise dos pontos vizinhos
utilizando uma máscara 3x4 na primeira etapa e logo,
uma máscara 3x3 na segunda etapa.
2
Notações Básicas
Conforme as especificações, está entendido que
um pixel em estudo "p" é um pixel preto e que os seus
vizinhos na janela (3x3) são rotulados como x1,x2,...,x8,
conforme a figura 1.
Com isso propõe-se um algoritmo que será
executado em dois ciclos sendo capaz de:
1
2
-
-
-
-
-
Definição 1: Os pixels (x1,x2,...,x8) são os 8vizinhos
do pixel p, denotado por N(p) e são ditos 8adjacentes vizinhos a p;
Definição 2: Os pixels (x1,x3,x5 e x7) são os 4
vizinhos do pixel P, e são ditos 4-adjacentes vizinhos
a P;
Definição 3: Uma seqüência de pontos Z1,Z2,...,Zn é
chamado de 8-ou (4-) caminho em 8- ou (4-)
vizinhos de Zi , para i= 1,2,...,n-1;
Definição 4: Um subconjunto C de uma imagem P é
denominado 8- ou (4-) conectado se para todo par de
pontos(x,y) em C se existir 8- ou (4-)caminhos de x
para y, e que sejam pontos pertencentes a C;
Definição 5: O número de transições entre pixels
pretos e brancos, e vice-versa e denominado número
de Rutowitz é definido como sendo :
3
Os Dois Ciclos do Algoritmo de Afinamento
O algoritmo paralelo com dois ciclos necessita
de dois conjuntos de pontos “apagáveis” em paralelo, cuja
união contém todo os pixels de bordas apagáveis. Esta
noção de “apagabilidade” significa que, todos os pontos
“P” do conjunto podem ser simultaneamente apagados
sem causar a erosão excessiva e ainda mantém a
topologia de qualquer padrão binário.
Definição 6 : Se um pixel “P” preto possui pelo menos 1
pixel branco como vizinho, é chamado ponto de borda
Definição 7: Um pixel preto tem no máximo 8 vizinhos
com pixel preto, isso é chamado ponto final.
Definição 8: A quebra de qualquer pixel “P” na
continuidade da imagem padrão forma um ponto de
quebra.
A essência do algoritmo apresentado consiste em
executar várias iterações sobre o padrão, onde muitos
pontos pretos são apagados em cada iteração. Se nenhum
ponto for apagado até o fim da execução, o algoritmo é
finalizado. Em qualquer sub-ciclo, o conjunto de pixels
preto apagado deve seguir um padrão que satisfaça os
seguintes critérios:
Um conjunto de pixels preto é apagado em paralelo se
todo ponto desse conjunto é um ponto de borda, e não
ponto final (break point). Pontos de borda são pontos
(pixels), mais externos da imagem.
Também esta possível eliminação não deve
causar erosão excessiva.
Lema 1:O conjunto I1 de pixels pretos p que
satisfazer as seguintes condições:
i)
Número de transições:
Xr(p)=2;
ii)
Número de pixels vizinhos:
2<=b (p)<=6;
iii)
R0=0 onde R0 é:
De acordo com a condição “ii”, existem de 2 a 6
pixels vizinhos de P que são candidatos a serem
apagados. No contrário a condição “i” diz que existe
somente duas transições (0-1 ou 1-0), e isso corresponde
a ter dois “1” entre x1,x2,...,X8, enquanto os seis pixels
que faltam podem ser todos 0 ou 4 deles serem iguais a 1.
Baseado nessas considerações, o conjunto N(p) contém
entre 2 e 6 pixels pretos que estão 4-conectados entre
eles, todas as possíveis pares de pixels são conectados
por um 4-caminho. Além disso “P” não é um break point.
Desde que os pixels satisfaçam as condições i e
ii, eles podem ser apagados em paralelo. Para solucionar
este problema não podemos usar máscara 3x3, temos que
usar máscara 4x3 ou 3x4(a1 e a2-Logo abaixo).
-
Lema 2:
IV)
S0 ^ S1 ^(b(p)>=2)
V)
R1=0 ^ (b(p)>=3)
O S0 é uma matriz 3x3(b1 e b2) e S1 é uma
matriz (3x3), com rotação de 90º, 180º e 360º de seus
elementos. Desde que estes modelos possuam entre 2 e 5
4-conectados pixels pretos, P tem pelo menos 4-vizinhos
pixels brancos, e que não são pontos quebrados. Se b(p) >
2, garantimos que o ponto P, não é um ponto isolado ou
ponto final. Desde que todo conjunto de pixels preto
satisfaça a condição “V”, ele pode ser apagado em
paralelo. Se a condição “V” não for respeitada, será
preciso salvar o pixel, e aplicar outra expressão booleana.
2
3
A expressão seria a R1, que utilizaria uma matriz (d1 e
d2) que satisfaria as condições IV e V.
a)
b)
c)
d)
Grau de 8-conectado
Grau de erosão
Estabilidade sob a rotação
Limite de ruído
5 Conclusão
Neste resumo de artigo relatamos um novo
algoritmo de afinamento paralelo com dois sub-ciclos,
caracterizado pela utilização de matriz (3×4) ao primeiro
sub-ciclo, e uma matriz (3×3) no segundo sub-ciclo.
Concluímos que o referido algoritmo (Petrosino e Salvi)
obtém resultados superiores quanto ao número de pixels
do esqueleto e tempo de processamento.
Um problema associado a muitos algoritmos
existentes, é que estes produzem esqueletos com muito
ruído se as bordas das imagens padrões possuírem muito
ruído também. O efeito deste processo tem dado muita
ênfase a estudos mais aprofundados.
Por isso surgiram métodos para suavizar as
bordas das imagens antes de aplicar o afinamento,
utilizando filtros em níveis de cinza ou aplicando uma
eliminação dos pontos ruidosos a cada interação. Em
alguns casos a utilização de máscara 3x3 não tem
retornado bons efeitos, sendo necessário aplicar uma
máscara 5x5 em alguns pixels vizinhos ao ponto de
partida.
Na prática essa utilização de máscara 5x5 se
resume na limpeza de pixels utilizando o OR (Booleano).
4 Comparações e resultados entre outros algoritmos
Usamos o resultados do algoritmo com outros,
como os de Deutsch, Zang e Suen, Chen e Hsu, Wang e
Zhang, Susuki e Abe, Guo and Hall, Stefanelli e
Rosenfeld[14], pudemos comparar os seguintes
parâmetros:
6 Dificuldades e Resultados
As dificuldades encontradas no desenvolvimento do
algoritmo foram notadas na adaptação das expressões
lógicas, que necessitaram de uma extrema atenção. A
definição da matriz corretamente também foi muito
importante, pois o algoritmo se baseia na utilização
destas.
Por conter expressões grandes, dividimos as mesmas em
partes para facilitar o entendimento dos resultados e
aplicações seguintes no contexto em geral. Foi possível
notar que para desenvolver o algoritmo foi preciso seguir
com extrema precisão as definições do artigo em si .
Os resultados obtidos foram muito bons, ou seja, o
algoritmo de Petrosino e Salvi funciona perfeitamente.
Com relação ao algoritmo de Zang e Suen , o algoritmo
de Petrosino e Salvi obteve um esqueleto muito mais
definido em termos do número de pixels(menor
quantidade), um desempenho muito bom e resultados
visíveis interessantes.
7 Referências
[PETROSINO (2000)], [SALVI (2000)].
ALFREDO PETROSINO AND GIUSEPPE SALVI, A
Two-Sub cycle Thinning Algorithm and Its Parallel
Implementation
on
SIMD
Machines,
IEEE
TRANSACTIONS ON IMAGE PROCESSING, VOL. 9,
NO. 2, FEBRUARY 2000.
3
4
CODIGO FONTE DO ALGORITMO DE AFINAMENTO
1- DEFINIÇÃO DA MATRIZ
//PETROSINO
//MAT 4X4
//
//
//
//
X4 X3 X2 Y4
X5 P X1 Y5
X6 X7 X8 Y6
Y1 Y2 Y3
#define P(MAT,X,Y) (MAT.GetAt(X ))->GetAt(Y)
#define X1(MAT,X,Y) (MAT.GetAt(X ))->GetAt(Y+1)
#define X2(MAT,X,Y) (MAT.GetAt(X-1))->GetAt(Y+1)
#define X3(MAT,X,Y) (MAT.GetAt(X-1))->GetAt(Y)
#define X4(MAT,X,Y) (MAT.GetAt(X-1))->GetAt(Y-1)
#define X5(MAT,X,Y) (MAT.GetAt(X ))->GetAt(Y-1)
#define X6(MAT,X,Y) (MAT.GetAt(X+1))->GetAt(Y-1)
#define X7(MAT,X,Y) (MAT.GetAt(X+1))->GetAt(Y)
#define X8(MAT,X,Y) (MAT.GetAt(X+1))->GetAt(Y+1)
#define Y6(MAT,X,Y) (MAT.GetAt(X+1))->GetAt(Y+2)
#define Y5(MAT,X,Y) (MAT.GetAt(X))->GetAt(Y+2)
#define Y4(MAT,X,Y) (MAT.GetAt(X-1))->GetAt(Y+2)
#define Y1(MAT,X,Y) (MAT.GetAt(X+2))->GetAt(Y-1)
#define Y2(MAT,X,Y) (MAT.GetAt(X+2))->GetAt(Y)
#define Y3(MAT,X,Y) (MAT.GetAt(X+2))->GetAt(Y+1)
CÓDIGO DO ALGORITMO DE PETROSINO
BOOL CPdiMorfoB::AfinamentoPetrosino(CString Titulo)
{
BOOL ThiningContinue=TRUE;
int line, col, counter;
PixelPoint ActualPixel;
BYTE Conectivity=0, Neighboors=0;
CArray <PixelPoint,PixelPoint> RemPoints;
CArray<CArray<BYTE, BYTE> *,CArray<BYTE, BYTE> *> Iteraction;
X RECEBE A LARGURA TOTAL DO BITMAP
Y RECEBE A ALTURA TOTAL DO BITMAP
int x = GetWidth();
int y = GetHeight();
int num_iteracoes = 0,linhas_codificadas=0;
CString total;
CTime start = CTime::GetCurrentTime();
4
5
LAÇO PARA VERIFICAÇÃO DOS PIXELS PRETOS E BRANCOS CONTIDOS NO BITMAP
for (line = 0; line < (int) GetHeight(); line++)
{
CArray<BYTE, BYTE> *ptrLine = new CArray<BYTE, BYTE>;
for (col = 0; col < (int) GetWidth(); col++)
{
(int) GetPixelBW(col,line) ? ptrLine->Add(0) : ptrLine->Add(1);
}
Iteraction.Add(ptrLine);
}
while(ThiningContinue)
{
ThiningContinue = FALSE;
num_iteracoes ++;
PRIMEIRA ITERAÇÃO
int R0,R1,Rtemp1,Rtemp2,Rtemp3,Rtemp4;
int Bp = 0;
int Xr = 0;
for (line = 1; line < (int) GetHeight()-1; line++)
{
for (col = 1; col < (int) GetWidth()-1; col++)
{
Bp = 0;
Xr = 0;
linhas_codificadas=GetHeight();
PIXEL DEVE SER PRETO
if( P(Iteraction,line,col) == 0 )
continue;
CONETIVIDADE DEVE SER 2
Xr = (X1(Iteraction,line,col) == 0 && X2(Iteraction,line,col)== 1) ? 1 : 0;
Xr += (X2(Iteraction,line,col) == 0 && X3(Iteraction,line,col)== 1) ? 1 : 0;
Xr += (X3(Iteraction,line,col) == 0 && X4(Iteraction,line,col)== 1) ? 1 : 0;
Xr += (X4(Iteraction,line,col) == 0 && X5(Iteraction,line,col)== 1) ? 1 : 0;
Xr += (X5(Iteraction,line,col) == 0 && X6(Iteraction,line,col)== 1) ? 1 : 0;
Xr += (X6(Iteraction,line,col) == 0 && X7(Iteraction,line,col)== 1) ? 1 : 0;
Xr += (X7(Iteraction,line,col) == 0 && X8(Iteraction,line,col)== 1) ? 1 : 0;
Xr += (X8(Iteraction,line,col) == 0 && X1(Iteraction,line,col)== 1) ? 1 : 0;
if (Xr !=2)
continue;
NUMERO DE VIZINHOS DO PIXEL “P” DEVE SER MAIOR OU IGUAL A 2 E MENOR OU IGUAL A 6
5
6
// 2 <= Bp <= 6
Bp= X1(Iteraction,line,col) + X2(Iteraction,line,col)+X3(Iteraction,line,col)+X4(Iteraction,line,col)
X6(Iteraction,line,col) + X7(Iteraction,line,col) + X8(Iteraction,line,col);
+X5(Iteraction,line,col)+
if (Bp < 2 || Bp > 6)
continue;
AQUI DIVIDIMOS A EXPRESSÃO R0 EM VÁRIAS PARTES PARA FACILITAR A COMPREENSÃO
// R0=0
R0=Rtemp1=Rtemp2=Rtemp3=Rtemp4=0;
Rtemp1=(1-Y5(Iteraction,line,col))*X2(Iteraction,line,col)*X3(Iteraction,line,col)*(1-X5(Iteraction,line,col));
Rtemp2=(1-Y2(Iteraction,line,col))*(1X3(Iteraction,line,col))*X5(Iteraction,line,col)*X6(Iteraction,line,col);
Rtemp3= (Rtemp1 ==0 && Rtemp2 == 0)? 0: 1;
Rtemp4=X1 (Iteraction,line,col)*X7(Iteraction,line,col)*X8(Iteraction,line,col);
R0 = Rtemp3*Rtemp4 ;
if (R0 != 0)
continue;
PIXEL QUE DEVE SER DELETADO
ThiningContinue = TRUE;
ActualPixel.Px = line;
ActualPixel.Py = col;
RemPoints.Add(ActualPixel);
}
}
for(counter=0;counter<RemPoints.GetSize();counter++)
Delete(Iteraction,RemPoints[counter].Px,RemPoints[counter].Py);
RemPoints.RemoveAll();
SEGUNDA ITERAÇÃO
int S0,S1,Stemp1,Stemp2,Stemp3,Stemp4;
for (line = 1; line < (int) GetHeight()-1; line++)
{
for (col = 1; col < (int) GetWidth()-1; col++)
{
O PIXEL DEVER SER PRETO
6
7
if( P(Iteraction,line,col) == 0 )
continue;
S0=Stemp1=Stemp2=Stemp3=Stemp4=0;
Stemp1=X3 (Iteraction,line,col)*X7(Iteraction,line,col);
Stemp2=X5 (Iteraction,line,col)*X1(Iteraction,line,col);
S0= (Stemp1 ==0 && Stemp2 == 0)? 0: 1;
S1=Stemp1=Stemp2=Stemp3=Stemp4=0;
AQUI DIVIDIMOS A EXPRESSÃO S1 EM VÁRIAS PARTES PARA FACILITAR A COMPREENSÃO
Stemp1=((1-X4 (Iteraction,line,col))==0 && X7(Iteraction,line,col)== 0) ? 0: 1;
Stemp1 *= X1 (Iteraction,line,col)*(1-X6(Iteraction,line,col));
Stemp2=((1-X6 (Iteraction,line,col))==0 && X5(Iteraction,line,col)== 0) ? 0:1;
Stemp2 *= X3 (Iteraction,line,col)*(1-X8(Iteraction,line,col));
Stemp3=((1-X2 (Iteraction,line,col))==0 && X1(Iteraction,line,col)== 0) ? 0:1;
Stemp3 *= X7 (Iteraction,line,col)*(1-X4(Iteraction,line,col));
Stemp4=((1-X8 (Iteraction,line,col))==0 && X7(Iteraction,line,col)== 0) ? 0:1;
Stemp4 *= X5 (Iteraction,line,col)*(1-X2(Iteraction,line,col));
if(Stemp1==0 && Stemp2==0 && Stemp3==0 && Stemp4==0)
S1=0;
else
S1=1;
NUMERO DE VIZINHOS DEVE SER >= 2
// Bp >=2
Bp=X1(Iteraction,line,col)+X2(Iteraction,line,col)+X3(Iteraction,line,col)+X4(Iteraction,line,col)
X6(Iteraction,line,col) + X7(Iteraction,line,col) + X8(Iteraction,line,col);
+X5(Iteraction,line,col)+
// 1-S0 ^ S1 ^ (Bp >=2);
if (!((1-S0==1) && (S1 ==1) && (Bp >=2)))
continue;
R1=Rtemp1=Rtemp2=Rtemp3=Rtemp4=0;
int Rtemp5,Rtemp6;
AQUI DIVIDIMOS A EXPRESSÃO R1 EM VÁRIAS PARTES PARA FACILITAR A COMPREENSÃO
Rtemp1=(1-X8 (Iteraction,line,col))*X1(Iteraction,line,col);
Rtemp2=(1-X6 (Iteraction,line,col))*X5(Iteraction,line,col);
7
8
Rtemp3= (Rtemp1 ==0 && Rtemp2 == 0)? 0: 1;
Rtemp3 *= (1-X3 (Iteraction,line,col));
Rtemp4=(1-X8 (Iteraction,line,col))*(1-X5(Iteraction,line,col));
Rtemp5=(1-X6 (Iteraction,line,col))*(1-X1(Iteraction,line,col));
Rtemp6= (Rtemp4 ==0 && Rtemp5 == 0)? 0: 1;
Rtemp6 *= (1-X7 (Iteraction,line,col));
R1= (Rtemp3 ==0 && Rtemp6 == 0)? 0: 1;
if(!(R1 ==0 && Bp <= 3))
continue;
PIXEL QUE DEVE SER DELETADO
ThiningContinue = TRUE;
ActualPixel.Px = line;
ActualPixel.Py = col;
RemPoints.Add(ActualPixel);
}
}
for(counter=0;counter<RemPoints.GetSize();counter++)
Delete(Iteraction,RemPoints[counter].Px,RemPoints[counter].Py);
RemPoints.RemoveAll();
}
FUNÇÃO QUE REDESENHA PIXEL COM A COR PRETA OU BRANCA
for (line = 0; line < y; line++)
{
for (col = 0; col < x; col++)
{
if(P1(Iteraction,line,col) == 0)
SetPixel((DWORD) col, (DWORD) (y-1)-line,RGB(255,255,255));
else
SetPixel((DWORD) col, (DWORD) (y-1)-line,RGB(0,0,0));
}
}
FUNÇÃO CONTA O NUMERO DE PIXELS PRETOS
int num_pixels_esqueleto = 0;
for (line = 1; line < (int) GetHeight()-1; line++)
{
for (col = 1; col < (int) GetWidth()-1; col++)
{
// Pixel must be black
if( GetPixel(col,line) == RGB(0,0,0) )
num_pixels_esqueleto++;
8
9
}
}
FUNÇÃO QUE CALCULA TEMPO DE PROCESSAMENTO
CTime end = CTime::GetCurrentTime();
CTimeSpan elapsedTime = end - start;
total = elapsedTime.Format( " %M min, %S seg" );
PASSAGEM DE PARAMETROS PARA A ESTATISTICA DO ALGORITMO
CDadosEstudo* Estudo;
Estudo = new CDadosEstudo();
Estudo->num_linhas_codificadas =228;
Estudo->nome_esqueleto = "Petrosino";
Estudo->num_lacos_repeticao = 11;
Estudo->tempo_processamento = total;
Estudo->memory = "12Mbytes";
Estudo->nome_imagem = Titulo;
Estudo->num_iteracoes = num_iteracoes;
Estudo->num_pixels_esqueleto = num_pixels_esqueleto;
ListaEstudo.AddTail(Estudo);
return TRUE;
}
9