Přeskočit na obsah

Houghova transformace

Z Wikipedie, otevřené encyklopedie

Houghova transformace je technika extrakce příznaků používaná v analýze obrazu, počítačovém vidění a zpracování obrazu.[1] Cílem této metody je najít nedokonalé instance objektů v rámci určité třídy tvarů hlasováním. Toto hlasování se provádí v prostoru parametrů, ze kterého jsou kandidáti objektů získání jako lokální maxima v tzv. akumulačním prostoru, který je explicitně zkonstruován algoritmem při výpočtu Houghovy transformace.

Klasická Houghova transformace byla určena pro identifikaci přímek v obraze, ale později byla Houghova transformace rozšířena pro určení pozic libovolných tvarů, nejčastěji kruhů nebo elips. Podobu Houghovy transformace, jak se obecně používá dnes, vynalezli Richard Duda a Peter Hart v roce 1972 a nazvali ji „zobecněná Houghova transformace[2] („generalized Hough transform“) podle původního patentu Paula Hougha z roku 1962[3]. Transformace byla zpopularizována v komunitě počítačového vidění Danem H. Ballardem v roce 1981 v časopiseckém článku „Generalizing the Hough transform to detect arbitrary shapes“ (Zobecnění Houghovy transformace pro detekci libovolných tvarů).

Klasická Houghova transformace

[editovat | editovat zdroj]

Klasická Houghova transformace slouží pro detekci přímek v obraze. Používá se ve strojovém vidění; dlouho byla nejužívanější technikou pro detekci čar na silnici pro autonomní a částečně autonomní vozidla (v současné době se od této transformace upouští a používají se techniky rychlejší (LSD, EDlines)). Houghova transformace dokáže sama o sobě najít pouze přímky – pakliže je třeba najít úsečky, je potřeba aplikovat další kroky.

V běžných případech pracuje transformace nad černo-bílým (bez stupňů šedi, tj. binárním) obrázkem.

Prostor parametrů

Transformace je založená na skutečnosti, že každá přímka v rovině x, y lze jednoznačně popsat dvojicí parametrů (r,σ), tedy vzdáleností od středu souřadnicového systému a úhlem od osy x.

Rovnice přímky v takovém tvaru je

x cos(σ)+y sin(σ)=r

Rovině se souřadnicovým systémem vymezeným osami (r,σ) se říká prostor parametrů.

Protože je přímka jednoznačně určena dvojicí (r,σ), zobrazí se každá přímka v (x,y) do (r,σ) jako jeden bod (viz obrázek) a naopak – bod v (r,σ) lze zobrazit jako přímku v (x,y).

Pro každý bod v (x,y) lze jednoduše najít množinu přímek, které tímto bodem procházejí. Je to množina (r,σ), splňujících uvedenou rovnici (x cos(σ)+y sin(σ)=r), když za (x,y) dosadíme souřadnice zkoumaného bodu.

Je zřejmé, že takováto množina splňující uvedenou rovnici bude mít v (r,σ) tvar sinusovky.

Pro každý nalezený (bílý) bod v (x,y) zobrazíme množinu přímek, které jím mohou procházet jako sinusovku do (r,σ).

Předpokládejme dále, že v (x,y) existují body ležící na přímce. Výše uvedeným postupem dokážeme pro každý bod vykreslit v (r,σ) množinu přímek, které jím mohou procházet. Přímku, která prochází všemi, můžeme tedy logicky najít jako průnik těchto množin.

Průniky sinusovek (množin), značící nalezenou přímku.

Tento průnik odpovídá v (r,σ) jednomu bodu, který je přímo parametrickým vyjádřením odpovídající přímky.

V tomto článku byl použit překlad textu z článku Hough transform na anglické Wikipedii.

  1. STOCKMAN, George; SHAPIRO, Linda G. Computer Vision. 1. vyd. [s.l.]: Prentice Hall, 2001. Dostupné online. ISBN 0130307963. (anglicky) 
  2. DUDA, Richard O.; HART, Peter E. Use of the Hough transformation to detect lines and curves in pictures. Communications of the ACM. 1972-01, Volume 15, Issue 1, s. 11–15. Dostupné online. DOI 10.1145/361237.361242. (anglicky) 
  3. P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959

Literatura

[editovat | editovat zdroj]
  • Tarsha-Kurdi, F., Landes, T., Grussenmeyer, P., 2007a. Hough-transform and extended RANSAC algorithms for automatic detection of 3d building roof planes from Lidar data. ISPRS Proceedings. Workshop Laser scanning. Espoo, Finland, September 12–14, 2007.

Související články

[editovat | editovat zdroj]

Externí odkazy

[editovat | editovat zdroj]