Houghova transformace
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
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.
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.
Tento průnik odpovídá v (r,σ) jednomu bodu, který je přímo parametrickým vyjádřením odpovídající přímky.
Odkazy
Reference
V tomto článku byl použit překlad textu z článku Hough transform na anglické Wikipedii.
- ↑ STOCKMAN, George; SHAPIRO, Linda G. Computer Vision. 1. vyd. [s.l.]: Prentice Hall, 2001. Dostupné online. ISBN 0130307963. (anglicky)
- ↑ 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)
- ↑ P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959
Literatura
- 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
- Zobecněná Houghova transformace
- Randomizovaná Houghova transformace
- Radonova transformace
- Fourierova transformace
Externí odkazy
Obrázky, zvuky či videa k tématu Houghova transformace na Wikimedia Commons - hough_transform.cpp – C++ code – example of CImg library (open source library, C++ source code, Grayscale images)
- https://web.archive.org/web/20070827233423/http://www.rob.cs.tu-bs.de/content/04-teaching/06-interactive/Hough.html – Java Applet + Source for learning the Hough transformation in slope-intercept form
- https://web.archive.org/web/20070827191440/http://www.rob.cs.tu-bs.de/content/04-teaching/06-interactive/HNF.html – Java Applet + Source for learning the Hough-Transformation in normal form
- http://www.sydlogan.com/deskew.html – Deskew images using Hough transform (Grayscale images, C++ source code)
- https://web.archive.org/web/20070922090216/http://imaging.gmse.net/articledeskew.html – Deskew images using Hough transform (Visual Basic source code)
- http://blog.une.edu.au/roland/deskew/[nedostupný zdroj] – Deskew images using Hough transform (Java source code)
- http://www.mitov.com/html/visionlab.html – Delphi, C++ and .NET free for educational purposes library containing Line, Circle and Line segment Hough transform components.
