Houghova transformace je technika extrakce příznaků používaná v analýze obrazu, počítačovém vidění a zpracování obrazu. 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“ („generalized Hough transform“) podle původního patentu Paula Hougha z roku 1962P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959. 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. náhled|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. náhled|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.
Odkazy
Reference
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
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/ – 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.
Kategorie:Zpracování obrazu