Visão Computacional – 2ªTrabalho
1
ÍNDICE
Introdução ......................................................1
Problema ........................................................1
Decomposição Quadtree ...........................................2
Transformada de Hough ...........................................3
Somatório por linhas da matriz de imagem ........................6
Descrição dos algoritmos implementados ..........................9
Conclusões e comentários finais ................................10
Bibliografia ...................................................10
M
ar
tin
ho
Apêndice A – Resultados finais .................................11
Jo
sé
Pa
ul
o
Pa
ix
ão
Apêndice B – Programas implementados ...........................14
INTRODUÇÃO
O acesso a documentos antigos, em geral raros, está sujeito a condicionantes físicas de
localização e conservação. Assim a consulta de umdocumento num determinado arquivo pode estar
sujeita a autorizações especiais, de forma a limitar o número de consultas e promover a sua
conservação.
O processamento digital de imagem, permite a consulta á distancia deste tipo de documentos,
sem acelerar a sua degradação. A réplica digital de um documento pode ser analisada
exaustivamente de forma a estudar características particulares, re mover eventuais de feitos e
recuperar a informação contida no documento original.
PROBLEMA
No âmbito da realização deste trabalho pretende-se identificar a localização das linhas de uma
pauta musical. A imagem da pauta está no ficheiro P1VR50BW.BMP . P ara efeitos de teste e
desenvolvimento dos algoritmos implementados foram utilizadas imagens parciais contidas nos
fi cheiros PAUTA.BMP e TESTE256.MAT.
Nas secções seguintes deste relatório são apresentadas as diferentes metodologias abordadas
na resolução do problema.
Visão Computacional – 2ªTrabalho
2
Visão Computacional – 2ªTrabalho
DECOMPOSIÇÃO QUADTREE (QTDEMO.M )
3
TRANSFORMADA DE HOUGH
A decomposição Quadtree usa-se em aplicações de compressão e análise de imagens. Este
operador divide a imagem em blocos que contêm elementos de imagem com características
"se melhantes" . Os blocos podem-se considerar "se melhantes" se a gama de valores dos seus
M
ar
tin
ho
elementos (pixels) não exc eder um determinado threshold.
Uma forma fundamental de representar os objectos é através de funções matemáticas que
descrevam as curvas de fronteira. Um mé todo muito eficaz de utilizar este tipo de informação é a
transfor mada de Hough, assim chamada depois que P aul Hough a apresentou em 1962 sendo o
método patenteado pela IBM.
A transformada de Hough tornou-se na década de oitenta uma ferramenta básica no domínio
da visão artificial para o reconhecimento de linhas rectas, círculos e elipses. Funções matemáticas
complexas, embora teoricamente possíveis de utilizar, não podem ser aplicáveis devido á sua
grande exigência computacional, pelo que o método é normal mente restrito a equações de fronteira
de primeira e segunda ordens (linhas rectas e secções cónicas). P ara o problema em questão vamos
de seguida considerar a e xtracção de linhas rectas.
Na Transfor mada de Hough original, a i magem é convertida numa for ma binaria através de
um threshold. Qualquer ponto cujo gradiente esteja acima do threshold é considerado como
pertencente à fronteira. Esta técnica é boa para imagens com um forte contraste, mas a sua
aplicabilidade é reduzida para imagens mais escuras.
A Transformada de Hough é aplicada entre o espaço cartesiano e um espaço parametrizado no
qual a linha recta (ou outra formulação de fronteira) possa ser definida. Se considerarmos a
for mulação cartesiana normal de uma linha recta:
Pa
ix
ão
y – mx – c = 0
As imagens anteriores contém os blocos e a correspondente média dos seus elementos. Neste
exemplo uma imagem (128x128) é subdividida em 4 blocos (64x64). Sempre que os pixels de um
Pa
ul
o
bloco não fore msemelhantes este é subdividido sucessivamente em blocos de dimensão inferior.
(1)
podemos tomar as duas constantes m e c como parâmetros que definem a linha. Se escolhermos um
ponto no eixo cartesiano [x,y], este pode ser considerado como pertencente a uma família de linhas
definidas por diferentes valores de m e de c. Um ponto [xi,yi] no espaço cartesiano irá corresponder
a uma linha no espaço m-c com a equação c = -xi m + yi. Assim, se tomar mos um conjunto de
pontos no espaço cartesiano, estes irão corresponder a um conjunto de linhas no espaço m-c como
se mostra no grá fico seguinte:
A imagem obtida no final corresponde à original e está dividida em 3235 blocos. A posterior
análise destes blocos permitira retirar da imagem a informação pretendida.
O elevado número de blocos obtido para a partição de imagem com dimensão 128x128 será
Jo
sé
amplamente incrementado para a imagem total com dimensão 1251x1727, aproximando-se de
400000 blocos. Uma análise dos blocos para identificar a localização das linhas da pauta musical
apresenta-se assim extremamente pesada a nível computacional, pelo que esta metodologia não foi
implementada no âmbito da realização deste trabalho.
Correspondê ncia entre os pontos n o espaço car tesiano e as linhas no espaç o parametrizado m-c.
Se esses pontos forem colineares, é fácil de ver que todas as linhas se intersectam num único
ponto, e que esse ponto define a inclinaç ão m e o offset c da linha. Na prática poderemos ter muitas
linhas, sendo a técnica dividir o espaço m-c em pequenas áreas , contando o número de linhas que
se cruzam. O valor [m,c] no centro da área com o maior número de linhas é usado como a
estimativa da linha mais provável no espaço cartesiano. Infelizmente, se considerarmos todas as
linhas possíveis que possam aparecer numa imagem, o parâmetro de declive m cobre uma gama
infinita. Por estara zão a parametrização [m,c] é difícil de utilizar.
Visão Computacional – 2ªTrabalho
4
Visão Computacional – 2ªTrabalho
Uma segunda parametrização, mais vantajosa, é exemplificada no gráfico seguinte:
Na aplicação da Transformada de Hough, os valores de r estão limitados à dimensão da
imagem e m aná lise e a valores discretos do ângulo θ . Assim, para θ = 1º o ficheiro do MatLab
VCHOUGH.M (listagem em ane xo) produziu os resultados apresentados nas figuras seguintes:
Uma linha pode ser representada pela sua mais curta distância da origem(r) e a sua orientação
(q).A partir do gráfico podemos obter uma equação para a linha equivalente à equação (1):
( 2)
Pa
ix
ão
De modo a saber a correspondência de um ponto em [ xi,yi] no espaço r-θ , faz-se a seguinte
substituição:
M = x i2 + y i2
Onde φ é uma constante definida por:
xi
2
i
2
i
x +y
,
Sin (φ ) =
yi
2
i
x + y 2i
Jo
sé
r = M {Cos ( φ ) Cos (θ ) + Sin (φ ) Sin (θ ) }
Pa
ul
o
O que nos permite escrever a equação (2) na for ma:
Cos (φ ) =
M
ar
tin
ho
P arametrizaç ão r-θ de uma linha
r = x Cos(θ) + y Sin( θ)
Temos agora que um ponto no espaço cartesiano corresponde a uma curva sinusoidal no
espaço r-θ . Neste espaço, um maior número de intersecções das curvas sinusoidais correspondem a
valores de r e θ prefer enciais, como se mostra de seguida:
O s resultado anteriores foram obtidos ao fim de 8 segundos comr ecurso a 8184412 bytes.
Transfor mada de Hough no espaço r-θ
5
Visão Computacional – 2ªTrabalho
6
Visão Computacional – 2ªTrabalho
7
SOMATÓRIO POR LINHAS DA MAT RIZ DE IMAGEM
O método adoptado para detecção das linhas consiste na análise do vector somatório das linhas da
matriz de imagem. O somatório toma valor mais baixo quando a imagem tem maior número de
elementos a preto. Como as linhas da pauta são horizontais, a associação com as linhas da matriz é
evidente. P odem ser necessárias correcções de orientação para que os resultados sejam rigorosos.
Esta orientaç ão é determinada pela análise dos valores mínimos do vector somatório como se ilustra
Σ
4
5
4
2
3
5
4
2
4
5
Pa
ix
ão
Σ
M
ar
tin
ho
na figura seguin te:
Pa
ul
o
Combase no raciocínio anteriormente explanado concluiu-se que após uma rotação da imagem de –
0.3º as linhas da pauta ficam horizontais e a sua localização é dada pelos valores mais baixos das
ao ficheiro VC2.M.
Jo
sé
componentes do somatório. Apresentam-se em seguida os resultados grá ficos obtidos com recurso
Este resultado obtido ao fim de 0.9 segundos comrecurso a 204270 bytes. Comparando coma
Transfor mada de Hough esta metodologia é 8 vezes mais rápida e ocupa 40 vezes menos me mória.
As melhorias são bastante significativas se tivermos em conta que estes valores são
reportados a um pequeno excerto da imagem (176 x 1151) , e que a imagem completa da pauta
musical tem a considerável dimensão de 1727 x 1251.
Visão Computacional – 2ªTrabalho
Visão Computacional – 2ªTrabalho
8
9
Os resultados obtidos para a imagem completa da pauta musical são apresentados no anexo A
neste relatório. Se o nível de detalhe da imagem for reduzido, a tomada de decisão poderá ficar
impossibilitada. Experimentalmente verificou-se que a partir da imagem base , pode ser aplicada
uma redução de 60%. Assim, a partir de uma imagem com dimensões (1727×1251 –
somatorio=400), obtém-se uma com dimensões (691x501 – somatorio=275) correspondentes ao
tamanho mínimo necessário para que todas as linhas da pauta musical sejam correctamente
detectadas. De notar que a variável somatório tem que ser calibrada em função das dimensões da
imagem em estudo.
M
ar
tin
ho
P ara realizar a correcta detecção das linhas da pauta musical, os elementos em questão serão:
-
Aquisição da imagem binarizada, atravé s de uma câ mara CCD linear
-
Placa digitalizadora para conversão do sinal do tipo analógico num sinal digital.
-
Iluminação orientada de modo a evitar projecção de sombras e com intensidade
Jo
sé
Pa
ul
o
Pa
ix
ão
suficiente para adquirir a imagem mas sem prejudicar a integridade dos documentos.
-
Fundo da imagem numa tonalidade escura para evitar interferência de páginas
sobrepostas.
DESCRIÇÃO DOS ALGORITMOS IMPLEMENTADOS
VC2.M:
Inicialização dos parâmetros de setup para rotação deimage m e valor do somatório.
Leitura do ficheiro com a imagem binarizada.
Ciclo derotação até o somatório ter um valor mínimo.
Marcaç ão de linhas a toda a largura dai magem com cores diferentes.
Apresentação de resultados gráficos.
VCHOUGH.M:
Alteraç ão de HOUGH.M para permitir a utilização de imagens rectangulares e/ou com dimensões
impares.
Visão Computacional – 2ªTrabalho
Visão Computacional – 2ªTrabalho
10
CONCLUSÕES E COMENTÁRIOS FINAIS
ANEXO A – RESULT ADOS FINAIS
P1VR50BW.BMP – (1727x1251)
A solução proposta para a resolução do problema, conduziu a resultados bastante satisfatórios,
tendo o software detectado correctamente todas as linhas da pauta musical.
Apesar da manipulação de imagens ser pesada computacionalmente, devido ao elevado
número de dados a processar, a metodologia implementada demonstra um rápido funcionamento,
comparativamenteà s outras metodologias abordadas neste trabalho.
Consoante a dimensão das imagens, o parâmetro de detecção associado à variável somatório
tem que ser calibrado. Esta calibração é feita com base nos resultados grá ficos apresentados pelo
M
ar
tin
ho
software após rotaç ão da image m.
BIBLIOGRAFIA
"Visão Computacional na Industria", J. Caldas Pinto, AEIST
Pa
ix
ão
"Visão Computacional – Livro", AEIST
"Image P rocessing Toolbox", The Mathworks Inc., 1993
http://www.csee.usf.edu/ieee-cs/look/sooda/
http://v2.math.tau.ac.il/matlab/hough.html
Jo
sé
http://www.doc.ic.ac.uk/~dfg/vision/
Pa
ul
o
http://www.cogs.susx.ac .uk/users/davidy/teachvision/
11
Visão Computacional – 2ªTrabalho
Visão Computacional – 2ªTrabalho
12
Linhas da Pauta M usical
Jo
sé
Pa
ul
o
Pa
ix
ão
M
ar
tin
ho
Rotação = -0.3º
13
Visão Computacional – 2ªTrabalho
14
Visão Computacional – 2ªTrabalho
15
VCHOUGH.M
VC2.M
% Alteração da função hough.m realizada para 2ºtrabalho Visão
Computacional 1999
% Permite imagens rectângulares e corrige dimensões impares
clc
clear all
tic
im=imread('pauta.bmp','bmp');
THETA_MAX=1;
[X,Y]=size(im);
if Y/2-fix(Y/2)
Y=Y-1;
end
if X/2-fix(X/2)
X=X-1;
end
titulo=['PAUTA.BMP - (' num2str(X) 'x' num2str(Y) ')'];
figure(1),imshow(im),title(titulo);
RHO_MAX=min([X,Y]);
d_rho=X/RHO_MAX;
d_theta=pi/THETA_MAX;
theta=0:d_theta:(pi-d_theta);
smat=sin(theta);
cmat=cos(theta);
fprintf('Finding feature points.\n');
[x,y]=find(im);
% translation by a pixel so that low left pixel has (0,0)
coordinates
x=x-1;
y=y-1;
fprintf('Translating so the origin is in the middle of the
image.\n');
fprintf('Doing the Hough Transform.\n');
h1=((y-Y/2) * smat + (x-X/2) * cmat )/d_rho;
h2=h1+RHO_MAX/2;
fprintf('Rounding.\n');
h3=round(h2);
fprintf('Summing the votes.\n');
[l,c_THETA]=size(theta);
res=zeros(RHO_MAX,c_THETA);
for j=0:RHO_MAX-1
temp=(h3==j);
res(j+1,:)=sum(temp);
end
figure(2),plot(res),axis tight,title('TRANSFORMADA DE HOUGH'),grid
on
toc
Pa
ix
ão
Pa
ul
o
Jo
sé
%VISÃO COMPUTACIONAL VC2.m - 2ºTrabalho Prático, Junho de 1999
%versão para MatLab 5.2
%Variáveis:
%
ang_ini,ang_inc,ang_ini - ângulo inicial,incremento do ângulo,ângulo final
%
somatorio - parâmetro para decisão da posição da linha
%
cor - vector de cinco cores para marcar as linhas
% ficheiro - nome do ficheiro com a imagem *.BMP
% foto,nova_foto,foto_cor - imagem original,rodáda,colorida
% titulo - título das imagens
%
linhas,colunas - dimensão da imagem
%
soma,nova_soma - somatório dos elementos da linha
%
minimo,novo_minimo - mínimo da soma
%
angulo,l - controlo de ciclos for
%
cont - contador da cor
%
troca_cor - flag para troca de cor da linha de marcação
clc
clear all
ang_ini=-0.1; %PARÂMETROS PARA SETUP
ang_inc=-0.1;
ang_fin=-1;
somatorio=400;
cor=[0 1 1;0 0 1;1 0 0.5;1 0 0;0 1 0];
%ficheiro ='P1VR50BW.BMP';
ficheiro ='PAUTA.BMP';
disp('Leitura da imagem no ficheiro *.BMP')
[foto,mapa]=imread(ficheiro,'BMP');
[linhas,colunas]=size(foto);
titulo=[ficheiro ' - (' num2str(linhas) 'x' num2str(colunas) ')'];
figure(1),imshow(foto),title(titulo);
disp('Cálculo do somatório das linhas da matriz')
soma=sum(foto,2);
minimo=min(soma);
figure(2),plot(soma),title('SOMATÓRIO'),ylabel('Linhas'),axis tight,grid on;
disp('Rotação para ter linhas da pauta horizontais')
for angulo=ang_ini:ang_inc:ang_fin
nova_foto=imrotate(foto,angulo,'crop');
nova_soma=sum(nova_foto,2);
novo_minimo=min(nova_soma);
if novo_minimo<=minimo
foto=nova_foto;
minimo=novo_minimo;
else
break %INTERROMPE ROTAÇÃO QUANDO ATINGE O MÍNIMO
end
end
titulo=['Rotação = ' num2str(angulo-ang_inc) 'º'];
figure(3),imshow(foto),title(titulo);
soma=sum(foto,2);
minimo=min(soma);
figure(4),plot(soma),title('SOMATÓRIO'),ylabel('Linhas'),axis tight,grid on;
disp('Marcação das linhas detectadas')
foto_cor=ind2rgb(foto,mapa);
cont=0;
troca_cor=1;
for l=1:1:linhas
if soma(l)<somatorio
if troca_cor
if cont<5
cont=cont+1;
else
cont=1;
end
troca_cor=0;
end
foto_cor(l,:,1)=cor(cont,1); %MARCA LINHAS A TODA A LARGURA DA IMAGEM
foto_cor(l,:,2)=cor(cont,2);
foto_cor(l,:,3)=cor(cont,3);
else
troca_cor=1;
end
end
figure(5),imshow(foto_cor),title('Linhas da Pauta Musical')
%foto_cor ocupa 4861824 bytes (PAUTA.BMP) ou 51851448 bytes (P1VR50BW.BMP)
%imwrite(foto_cor,mapa,'clinhas.tif','tif')
M
ar
tin
ho
ANEXO B - PROGRAMAS I MPLEMENTADOS
Visão Computacional – 2ªTrabalho
16
Jo
sé
Pa
ul
o
Pa
ix
ão
fu ncti on re s=ho ugh( im,R HO_M AX,T HETA _MAX )
% Name :
ho ugh( im,R HO_M AX,T HETA _MAX )
% Argu ment s:
%
im : is th e in put, bina ry, i mage . I f the im age i s n ot b inar y pix els
ha ving
%
no n- ze ro v alue s ar e co nsid ered .
%
RH O_MA X: i s an int eger num ber spec ifyi ng t he r ho q uant izat ion.
%
TH ETA_ MAX: is an i nteg er n umbe r s peci fyin g th e th eta quan tiza tio
% Exam ple:
v= houg h(im ,256 ,256 )
%
in put is t he i mage im, and the
%
qu anti zati on i s d_ rho= X/25 6 an d d_ thet a=pi /256
%
if the siz e of the ima ge i s 25 6 by 256 d_r ho=1 .
%
V is t he n umbe r of vot es i n th e
%
pa reme ter spac e. v (i,j ) is the num ber
%
of vot es f or t he s trip hav ing dist ance fro m
%
th e ce nter of the imag e eq ual to
%
(i-RH O_MA X/2) *d_r ho ( d_rh o=X/ RHO_ MAX, the
%
im age is X by X
pi xels ),an d it s no rmal has
%
an gle j*d_ thet a,(d _the ta=p i/TH ETA_ MAX)
%
Fo r a 256 by 2 56 i mage , th e ce nter of the
%
im age is t he c ente r of the pix el ( 128, 128)
%
i= 1 => rho =(i-1- 12 8)*d _rho =- 12 8*d_ rho
%
i= 256 => r ho=( i- 1-12 8)*d _rho =127 *d_r ho
%
th is e ssen tial ly m eans tha t:
%
't he i mage is not symm etri c ar ound its cen ter'
ti c
[X ,Y]= size (im) ;
if X~ =Y
fp rint f(1, 'I nput ima ge i s no t sq uare . Ex itin g!\n');
re turn ;
el seif re m(X, 2)== 1
fp rint f(1, 'I nput ima ge s ize has to b e ev en i n pi xels . Ex itin g!\n');
re turn
en d
d_ rho= X/RH O_MA X;
d_ thet a=pi /THE TA_M AX;
th eta= 0:d_ thet a:pi -d_ thet a;
sm at=s in(t heta );
cm at=c os(t heta );
fp rint f('F indi ng f eatu re p oint s.\ n');
[x ,y]= find (im) ;
% tran slat ion by a pix el s o th at l ow l eft pixe l ha s (0 ,0)
%c oord inat es
x= x-1;
y= y-1;
fp rint f('T rans lati ng s o th e or igin is in t he m iddl e of the ima ge. \n');
fp rint f('D oing the Hou gh T rans form .\n' );
h1 =((y -Y/ 2) * sma t + (x-X/ 2) * cma t )/ d_rh o;
h2 =h1+ RHO_ MAX/ 2;
cl ear h1
fp rint f('R ound ing. \n' );
h3 =rou nd(h 2);
cl ear h2
fp rint f('S ummi ng t he v otes .\n' );
re s=ze ros( RHO_ MAX, THET A_MA X);
fo r j= 0:RH O_MA X-1
te mp=( h3== j);
re s( j+1, :)=s um(t emp) ;
en d
to c
M
ar
tin
ho
HOUGH.M (forn ecido p elo p rof essor)