Transformada de Hough

La Transformada de Hough és un algorisme emprat en reconeixement de patrons en imatges que permet trobar certes formes dins d'una imatge. És una tècnica utilitzada per aïllar característiques de forma particular dins d'una imatge, per tant, és una eina útil pel processament digital d'imatges, en l'anàlisi d'imatges i per a la visió artificial.^[1] Es basa a transformar punts de la imatge en un espai de paràmetres amb la idea bàsica de trobar corbes que puguin ser parametritzades com a rectes, polinomis i circumferències. Aquest espai paramètric es representa per una estructura rectangular de cel·les, anomenada arranjament acumulador, on els seus elements són cel·les acumuladores A(ρi,θi), les quals són els rangs esperats de (ρ,θ). Aquestes cel·les acumuladores amb una magnitud superior a un cert llindar poden ser considerades com a línies possibles.

El propòsit de la transformada de Hough és fer front a un problema que sorgeix en l'anàlisi automatitzada d'imatges digitals. El fet de detectar les vores d'una imatge per a obtenir punts o píxels d'aquesta pot causar imperfeccions, ja que poden faltar punts o píxels, poden existir desviacions espacials entre la línia ideal i els punts d'avantatge sorollós, etc.^[2]

Algorisme

Existeixen diverses aplicacions de la transformada de Hough, tot i que l'aplicació més simple es correspon a la de rectes.^[3]

Detecció de cercles

La transformada de Hough, en principi, està pensada per a la detecció de rectes, però també és aplicable a qualsevol funció de la forma f(v,c) =0, on v és un vector de coordenades i c és un vector de coeficients. L'equació del cercle té tres paràmetres, que són les coordenades del centre de la circumferència (xo,yo) i el radi de la circumferència(r^2); per tant, l'espai de paràmetres és de dimensió tres. Això dificulta l'algorisme, ja que donarà lloc a un espai de paràmetres de tres dimensions, amb cel·les en forma de cub i acumuladors (que són subdivisions de l'espai paramètric - de la forma f(r,x,y)).

$\,r^{2}=(x-xo)^{2}+(y-yo)^{2}$

El procediment en aquest cas és per a cada punt del pla format pels eixos (x,y), per a cada xo i yo, calcular el valor del radi i actualitzar l'acumulador corresponent a (xo,yo,r). La complexitat de la transformada de Hough depèn de la mida de l'espai de paràmetres.

Per percebre de millor manera el concepte de transformada, en l'exemple de la figura es mostren dues imatges que tenen un conjunt de cercles. A la imatge de l'esquerra hi ha tres cercles amb tres radis diferents. En aquest exemple es passa el paràmetre radi a la transformada de Hough perquè busqui cercles de radi 35. A la imatge de la dreta s'observa que en el cercle 2 totes les corbes passen per un mateix punt indicant que el cercle 2 té un radi de 35 píxels.

Detecció de rectes

La transformada de Hough per a la detecció de rectes és una tècnica per a detectar segments rectes en imatges. Utilitza la descripció paramètrica de formes geomètriques, és a dir, la representació d'una recta en coordenades polars.^[4]

\,x\cos(\rho )+\,y\sin(\rho )=\phi

A l'espai de la imatge, la línia recta es pot descriure com:

\,y=mx+b

i pot ser gràficament representada per cada parell de punts d'imatge (x, y). La idea principal és tenir en compte les característiques de la línia recta i no com a punts d'una imatge (x1, y1), (x2, y2), etc. És a dir, en termes del paràmetre del pendent $m$ i la intersecció del paràmetre $b$ . Basant-se en aquest fet, la línia recta es pot representar com un punt $(b,m)$ en l'espai de paràmetres.

En el següent exemple gràfic s'observa com la transformada de Hough de la recta ρj (recta a distància de l'origen) i amb orientació θi es representa com un punt del pla (ρ,θ).

Exemple pràctic de la transformada de Hough per a rectes

L'avantatge d'aquest mètode és que evita singulars, com ara rectes de pendent infinita. Si es representa $\phi$ i $\rho$ en un pla cartesià, una recta queda determinada mitjançant un punt amb coordenades (phi (recta), ro (recta)), mentre que un punt es representa com una funció sinusoidal. Si per 'exemple' tenim dos punts, tindrem dues senoides desfasades alfa graus depenent de les coordenades dels punts. Aquestes senoides s'aniran creuant cada 180°. La interpretació geomètrica d'aquest fet és que, si cada punt de la funció representa les infinites rectes que passen per cada punt, quan dos punts comparteixen la mateixa recta (les seves representacions sinusoidals es creuen) s'obté un punt. Cada vegada que es fa mitja volta ( $\rho$ = 180°) es torna a repetir la mateixa recta, de manera que tornem a obtenir un altre punt, que de fet és la mateixa recta.

Implementació

En el cas discret, el domini de Hough és un array bidimensional que representa valors discrets de θ i ρ. Abans d'aplicar la transformada és necessari seleccionar una resolució del domini de Hough. Quan es treballa amb una imatge binaria es segueixen els següents pasos:

Inicialitzem la matriu acumuladora a zeros
Per a cada pixel de la imatge amb nivell diferent de zero:
- Es determina el valor de ρ per a cada valor de θ
- S'incrementa la posició (θ,ρ) de la matriu en 1
En finalitzar, cada cel·la indicarà el nombre de píxels que formen una recta en aquests paràmetres

Matriu acumuladora: Quantificació del pla de paràmetres en cel·les acumuladores. En la transformada de Hough d'una imatge binaria cada cel·la indica el nombre de pixels que componen el segment recte; però si la imatge no és binària, el recompte de píxels s'ha de ponderar pel nivell d'intensitat.

La precisió en la linealitat d'aquests punts s'estableix pel nombre de subdivisions en el pla (θ,ρ). Si es subdivideix l'eix en k parts, llavors per a cada punt (xo,yo) s'obté k valors de θ que corresponen als k possibles valors de ρ.

Problema

El problema que ens trobem per representar una línia amb l'equació de la recta és que la pendent i l'ordenada a l'origen poden arribar a ser infinit. Una forma de resoldre aquest problema consisteix a utilitzar la representació normal de la recta. Així, ara a cada punt del pla xy correspon una sinusoïde al pla ρθ en lloc d'una recta.

La següent imatge és un exemple que mostra els resultats d'una transformada de Hough en una imatge de mapa de bits que conté dues línies gruixudes.

Exemple de la transformada de Hough amb línies gruixudes

Detecció de punts

La transformada de Hough per a la detecció de punts consisteix que per a cada punt (xk,yl) es correspon amb una corba al pla (ρj,θi). Per tant, calculant les corbes per a molts punts, els punts de creuament defineixen les rectes que els uneixen. Totes les corbes corresponents a les components colineals intersequen en el mateix punt (θ,ρ), on θ i ρ especifiquen els paràmetres de la línia. S'ha de tenir en compte que una recta horitzontal correspon a un valor θ=0° i un valor de ρ és igual a l'ordenada a l'origen, mentre que una recta vertical correspon a un valor de θ=90° i un valor de ρ és igual a l'abcissa a l'origen.

La següent imatge mostra com quatre punts corresponents a les cantonades d'un quadrat donen lloc a quatre sinusoïdes a l'espai ρθ. Les quatre sinusoïdes es tallen per sis punts, tot i que el resultat final són vuit punts, ja que cal recordar que els dos punts per a θ=90° són els mateixos que els punts per a θ=-90°.

Exemple pràctic de la transformada de Hough per a punts

(a) Imatge amb quatre punts (b) Transformada de Hough mostrant sis punts de tall corresponents a les sis rectes que poden passar pels quatre punts

Exemples

La primera imatge mostra el primer pas de la transformada de Hough, de tres punts i 6 grups d'angles possibles.

Les línies de diferents angles es tracen, tot va a través del primer punt. Aquestes es mostren com a línies contínues.
Per a cada línia contínua, la perpendicular que divideix l'origen també es troba. Aquestes es mostren com a línies discontínues.
La longitud i l'angle de la línia de punts després es troben.
Els valors es mostren a la taula de continuació de cada diagrama.
Això es repeteix per a cada un dels tres punts que es vol transformar.
Els resultats es representen en un gràfic

La imatge següent correspon a fer la transformada de Hough per a punts al·lineats, on la brillantor de la transformada és proporcional al nombre de punts que la contribueixen.

Història

La Transformada de Hough va ser inventada inicialment per a l'anàlisi de la Càmera de bombolles(Hough, 1959).

Hough,^[5] el 1962, va inventar la transformació per a una aplicació en la detecció de les rutes de partícules subatòmiques passant per un camp de visió. Aquesta fou patentada dels Estats Units d'Amèrica (EUA) el 1962 i assignada a la Comissió d'Energia Atòmica dels EUA amb el nom de "Mètode i mitjans pel reconeixement de patrons complexos". Aquesta patent utilitza una parametrització pendent-intersecció de línies rectes, quelcom condueix a un espai transformat no fitat, ja que el pendent pot anar fins a l'infinit.

La transformada original de Hough va ser dissenyada per detectar línies rectes i corbes, aquest mètode s'utilitza només si es coneixen les equacions analítiques de les línies o corbes de vores de l'objecte. Més tard, es va descriure la transformada generalitzada de Hough (Generalised Hough Transform) que pot trobar objectes encara que no es conegui l'equació analítica de la vora.

La parametrització de la rho-theta universal que s'utilitza en l'actualitat va ser descrita per primera vegada a:

Duda, R.O. i Hart P.E.,"^[6] Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972), encara que ja era estàndard per a la transformació de radó com a mínim des de 1930.^[7]

La variació O'Gorman i Clowes es descriu a:

Frank O'Gorman, MB Clowes: Finding Picture Edges Through Collinearity of Feature Points. IEEE Trans. Computers 25(4): 449-456 (1976)

La història de com la forma moderna de la transformada de Hough va ser inventada es dona a:

Hart, P. E., "How the Hough Transform was Invented", IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 - 22 (November, 2009).

Codi Matlab

El següent codi matlab correspon en realitzar la transformada de Hough per a la imatge de la dreta.

RGB = imread('gantrycrane.png');
 I = rgb2gray(RGB); % convert to intensity
 BW = edge(I,'canny'); % extract edges
 [H,T,R] = hough(BW,'RhoResolution',0.5,'Theta',-90:0.5:89.5);

 % display the original image
 subplot(2,1,1);
 imshow(RGB);
 title('gantrycrane.png');

 % display the hough matrix
 subplot(2,1,2);
 imshow(imadjust(mat2gray(H)),'XData',T,'YData',R,...
 'InitialMagnification','fit');
 title('Hough transform of gantrycrane.png');
 xlabel('\theta'), ylabel('\rho');
 axis on, axis normal, hold on;
 colormap(hot);

Vegeu també

Referències

↑ Shapiro, Linda and Stockman, George. "Computer Vision", Prentice-Hall, Inc. 2001
↑ GONZÁLES Rafael C. y WOODS Richard E.,Tratamiento digital de Imágenes, Addison-Wesley,1992
↑ CiteSeerX — A short introduction to the Radon and Hough transforms and how they relate to each other
↑ «Hough Transform». Arxivat de l'original el 2011-12-07. [Consulta: 24 gener 2012].
↑ P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959
↑ «Use of the Hough Transformation to Detect Lines and Curves in Pictures».
↑ Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972)

Enllaços externs

[1] Shapiro, Linda and Stockman, George. "Computer Vision", Prentice-Hall, Inc. 2001

[2] GONZÁLES Rafael C. y WOODS Richard E.,Tratamiento digital de Imágenes, Addison-Wesley,1992

[3] CiteSeerX — A short introduction to the Radon and Hough transforms and how they relate to each other

[4] «Hough Transform». Arxivat de l'original el 2011-12-07. [Consulta: 24 gener 2012].

[5] P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959

[6] «Use of the Hough Transformation to Detect Lines and Curves in Pictures».

[7] Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972)

[1]

[2]

[3]

[4]

[5]

[6]

[7]