Mini relatório – Algoritmo Detecção do Topo da Rolha
Projecto iVlab
Data 02-04-06
Versão 2.0
Participantes
Catarina Santiago
Gabriel Silva
Ricardo Cardoso
Docente
Américo Azevedo
1. Propósito do documento
Este documento visa a apresentação e descrição de alguns algoritmos
implementados para detectar a rolha no caso das câmaras de topo.
Dá-se uma breve descrição de três algoritmos que assentam em técnicas
distintas.
2. Descrição
1ª Abordagem
Inicialmente usou-se um método simples que consistia em:
1. determinar um valor de threshold;
2. varrer a imagem em busca de transições;
3. determinar o centro e o raio da rolha;
1º - determinar o valor de threshold Æ primeiro é contruído o histograma da imagem e,
o valor de threshold corresponde ao valor para o qual se obtem 85% do total do
histograma, isto é, cada barra do histograma é somada até se atingir 85% e, essa barra
corresponderá ao valor de threshold utilizado para separar a rolha do fundo ( note-se que
este valor foi obtido por via experimental).
0
255
85%
valor de threshold
2º - varrer a imagem em busca de transições Æ uma vez obtido o valor de threshold a
imagem é varrida da esquerda para a direita, da direita para a esquerda, de cima para
baixo e, por fim de baixo para cima em busca de transições de luminância, ou seja, em
busca de pixels contíguos que tenham o seu valor de cada um dos lados do threshold.
Assim, ao percorrer uma linha (no caso das transições horizontais, coluna no caso de
transições verticais) sempre que se verifica uma transição na cor esse valor é
armazenado num vector e passa-se para a linha (coluna) seguinte.
3º - determinar o centro e o raio da rolha Æ uma vez determinados todos os pontos
que correspondem à borda é usado o método dos mínimos quadrados para estimar o raio
e o centro da rolha, assim partindo da equação da circunferência tem-se:
(x - x o )2 + ( y - y o )2
= r2
Onde:
xo,yo correspondem ao centro da rolha;
r é raio da rolha;
x,y são as coordenadas de um dado ponto da circunferência.
Desenvolvendo a equação obtem-se:
2
2
x 2 − 2 x × xo + xo + y 2 − 2 y × y o + y o = r 2 ⇔
2
2
(
2 xo × x − 2 y o × y + xo + y o − r 2 = − x 2 + y 2
)
Onde se dispõe dos valores de x e y e se pretende estimar os valores de x0, y0 e r. Assim,
transformando a equação anterior na forma matricial tem-se:
Y =θT × X
onde,
2 x0
⎡
⎤
⎢
θ = ⎢ − 2 y 0 ⎥⎥
⎢⎣ x02 + y 02 − r 2 ⎥⎦
,
⎡ x⎤
X = ⎢⎢ y ⎥⎥
⎢⎣ 1 ⎥⎦
e
(
y = − x2 + y2
)
E por resolução da equação anterior se obtem
θ = (X T × X ) × X T × Y , donde são facilmente retirados os parâmetros pretendidos.
−1
2ª Abordagem
Tendo em vista melhorar o algoritmo de detecção da rolha utilizou-se a seguinte
estratégia:
1º - tornar a imagem mais clara;
2º - aplicar um filtro apropriado para detectar transições;
3º - passar a imagem que resultou da etapa anterior para escala de cinzas;
4º - aplicar um algoritmo de detecção de circunferências.
A imagem original é a seguinte:
Fig. 1 Imagem original do topo da rolha
1º - tornar a imagem mais clara Æ cada componente (vermelho, azul e verde) de cada
pixel é multiplicada por 2 e é-lhe adicionado um bias de 9, ou seja:
novo_pixel.r=antigo_pixel*2+9, obtendo-se a seguinte imagem
Fig. 2 Imagem do topo usando um filtro para tornar a imagem mais clara
2º - filtro para detecção de transiçõesÆ o filtro utilizado foi o seguinte:
-2
-2
-2
-2
16
-2
-2
-2
-2
Este filtro baseia-se no filtro proposto por Prewitt do Laplaciano de 8 vizinhos,
no entanto, após alguns testes em torno deste algoritmo chegou-se à conclusão que a sua
multiplicação por dois produzia resultados melhores, como se pode ver na imagem
seguinte:
Fig. 3 Imagem após ter passado pelo filtro: esquerda - sem multiplicar por 2, direita - multiplicado
por 2
4º - passar a imagem para escala de cinzas Æ para tal faz-se uso da seguinte expressão
Y=0.299R+0.587G+0.144B, obtendo-se:
Fig. 4 Imagem em escala de cinza
5º- aplicar a transformada de Hough para circunferências Æ para tal faz-se uso da
equação da circunferência
(x − x0 )2 + ( y − y 0 )2 = r 2 , que parameterizada resulta em
x0 = x − r cos(θ )
y 0 = y − r sin(θ )
Ora, para um conjunto de raios que varia entre 78 e 82 pixeles é aplicado o
algoritmo que consiste em:
- Varrer toda a imagem em busca de pixels brancos;
- Sempre que se encontra um pixel branco, para um dado raio, são
determinados os centros das várias circunferências que passam por ele, para
tal faz-se variar o parâmetro θ entre 0º e 360º;
- Para cada raio é criada uma matriz que contém os vários centros de massa e,
sempre que é detectado um possível centro é incrementada a respectiva
posição na matriz, note-se que esta matriz é indexada pelos valores resultante
do x0 e y0.
- Por fim, determina-se a posição que contém o valor mais alto, obtendo-se
desta forma o raio e o centro da rolha.
De facto, este algoritmo mostrou bons resultados, no entanto, o tempo de
execução é muito demorado e, dado tratar-se de um processo que dispõe de pouco
tempo para fazer todo o processamento, achou-se por bem abandonar este tipo de
abordagem.
3ª Abordagem
Assim, optou-se por utilizar a 1ª abordagem, mas tentando melhorar o valor de
threshold, usando o método de Otsu. Os passos seguidos foram:
1º - determinar o valor de threshold óptimo pelo método de Otsu;
2º - fazer o varrimento da figura em busca de transições;
3º - fazer estimativa do centro da rolha;
4º - eliminar os pontos que distam de um certo valor do centro da rolha
estimado;
5º - determinar o centro e o raio da rolha pelo do método dos mínimos
quadrados, utilizando os pontos que sobreviveram ao algoritmo anterior;
1º - determinar o valor óptimo de threshold Æ estando a imagem em escala de cinza e,
dado, que a rolha tem uma intensidade bastante diferente do fundo é possível aplicar o
método de Otsu.
Este algoritmo faz uso do histograma normalizado da figura, onde o número
total de pontos para cada valor de intensidade (0..255) é dividido pelo número total de
pontos da imagem, como tal, obtem-se uma distribuição de probabilidade para cada
nível de intensidade. De seguida, calcula-se a variância (equação seguinte) para cada
nível de intensidade e a que tiver maior valor corresponderá ao valor de threshold
óptimo.
σ B2 (Topt ) = max (σ B2 (k )) = max
1≤ k ≤ N max
1≤ k ≤ N max
(μT .ω (k ) − μ (K ))2 ∀k ∈ 1, N ,
max
ω (k )(1 − ω (k ))
onde
N (l )
,
2
l =1 N
k
N (l )
μ (k ) = ∑ l. 2 ,
N
l =1
k
ω (k ) = ∑
μT =
N max
N (l )
∑ l. N
l =1
2
2º - fazer o varrimento da figura em busca de transições Æ uma vez obtido o valor de
threshold basta varrer a figura em busca de zonas que contêm dois pixels consecutivos
com valores de intensidade de lados diferentes do valor de threshold, como explicado na
1ª abordagem.
3º - fazer estimativa do centro da rolha Æ após determinar todos os pontos que
correspondam a transições faz-se uma estimativa do centro da rolha através do
somatório das coordenadas dos vários pontos tidos como transições, ou seja:
1 p
xCM = ∑ xi
p i =1
y CM =
1 p
∑ yi
p i =1
4º - eliminar pontos que distam de um certo valor do centro da rolha estimado Æ
dado poderem existir poeiras, ou imperfeições nos suportes que transportam as rolhas,
que irão influenciar negativamente a determinação do raio e do centro da rolha, torna-se
necessário eliminar pontos que distem um dado valor do centro estimado.
Desta forma, os pixels que correspondem a transições e que distem do centro da
rolha mais de 100 pixels são ignorados para efeitos de determinação dos parâmetros que
caracterizam o raio e o centro da rolha. Note-se que o valor de 100 pixeles foi esolhido
na medida em que, em média as rolhas utilizadas têm cerca de 82 pixeles de raio.
5º - determinar o centro e o raio da rolha pelo método dos mínimos quadrados Æ
após a eliminação dos pontos menos prováveis de fazerem parte da borda da rolha podese usar o método dos mínimos quadrados para obter os parâmetros pretendidos (raio e
centro).