Zobecněná Houghova transformace - Generalised Hough transform

The zobecněná Houghova transformace (GHT), představil Dana H. Ballard v roce 1981, je modifikace Hough transformace pomocí principu shoda šablony.^[1] Houghova transformace byla původně vyvinuta pro detekci analyticky definovaných tvarů (např. čára, kruh, elipsa atd.). V těchto případech máme znalosti o tvaru a snažíme se zjistit jeho umístění a orientaci v obraze. Tato modifikace umožňuje použít Houghovu transformaci k detekci libovolného objektu popsaného s jeho modelem.

Problém nalezení objektu (popsaného s modelem) v obraze lze vyřešit vyhledáním polohy modelu v obraze. S generalizovanou Houghovou transformací se problém s nalezením pozice modelu transformuje na problém s nalezením parametru transformace, který mapuje model do obrazu. Vzhledem k hodnotě parametru transformace lze určit polohu modelu v obraze.

Původní implementace GHT používala informace o hraně k definování mapování od orientace okrajového bodu k referenčnímu bodu tvaru. V případě a binární obraz kde pixely mohou být černé nebo bílé, každý černý pixel obrázku může být černý pixel požadovaného vzoru, čímž se vytvoří a místo referenčních bodů v Houghově prostoru. Každý pixel obrázku hlasuje pro odpovídající referenční body. Maximální body Houghova prostoru označují možné referenční body vzoru na obrázku. Toto maximum lze zjistit skenováním Houghova prostoru nebo řešením a uvolněná sada rovnic, z nichž každý odpovídá černému pixelu.^[2]

Dějiny

Merlin a Farber^[3] ukázal, jak použít Houghův algoritmus, když nebylo možné analyticky popsat požadované křivky. Byl to předchůdce Ballardova algoritmu, který byl omezen na překlad a nezohlednil otáčení a měřítko Změny.^[4]

Algoritmus Merlin-Farber je nepraktický pro skutečná obrazová data, jako v obraze s mnoha pixely na hraně, díky opakovaným uspořádáním pixelů najde mnoho falešných pozitiv.

Teorie zobecněné Houghovy transformace

Chcete-li zobecnit Houghův algoritmus na neanalytické křivky, definuje Ballard následující parametry pro zobecněný tvar: a = {y, s, θ} kde y je odkaz původ pro tvar, θ je jeho orientace a s = (s_X, s_y) popisuje dva ortogonální měřítkové faktory. Algoritmus může vypočítat nejlepší sadu parametrů pro daný tvar z dat okrajových pixelů. Tyto parametry nemají stejný status. Referenční místo původu, y, je popsán v pojmech tabulky šablon nazývané R tabulka možných orientací okrajových pixelů. Výpočet dalších parametrů s a θ je pak dosaženo přímými transformacemi do této tabulky. Klíčovým zobecněním pro libovolné tvary je použití směrových informací. Vzhledem k libovolnému tvaru a pevnému referenčnímu bodu na něm se místo parametrické křivky ukládají informace poskytované hraničními pixely ve formě tabulky R ve fázi transformace. U každého okrajového bodu na testovacím obrázku se vlastnosti bodu vyhledají na R-tabulce a načte se referenční bod a zvýší se příslušná buňka v matici zvaná matice Akumulátor. Buňka s maximálním počtem hlasů v matici akumulátoru může být možným bodem existence pevné reference na objekt v testovacím obrazu.

Sestavení R-stolu

Vyberte referenční bod y pro tvar (obvykle se volí uvnitř tvaru). Pro každý hraniční bod X, vypočítat ɸ (x), spád směr a r = y - x jak je znázorněno na obrázku. Obchod r jako funkce ɸ. Všimněte si, že každý index ɸ může mít mnoho hodnot r. Lze buď uložit rozdíly souřadnic mezi pevnou referencí a hranovým bodem ((X_C - X_ij), (r_C - y_ij)) nebo jako radiální vzdálenost a úhel mezi nimi (r_ij , α_ij) . Po provedení tohoto pro každý bod bude R-tabulka plně představovat objekt šablony. Protože je generační fáze invertibilní, můžeme ji použít k lokalizaci výskytů objektů na jiných místech v obraze.

Geometrie detekce tvaru pro zobecněnou Houghovu transformaci

i	ɸ_i	R_{ɸ_i}
1	0	(r₁₁, α₁₁) (r₁₂, α₁₂)… (R_1n, α_1n)
2	Δɸ	(r₂₁, α₂₁) (r₂₂, α₂₂)… (R_{2 m}, α_{2 m})
3	2Δɸ	(r₃₁, α₃₁) (r₃₂, α₃₂)… (R_3k, α_3k)
...	...	...

Lokalizace objektu

Pro každý hranový pixel X na obrázku najděte přechod ɸ a zvýšit všechny odpovídající body x + r v poli akumulátoru A (inicializováno na maximální velikost obrázku), kde r je záznam tabulky indexovaný pomocí ɸ, tj., r (ɸ). Tyto vstupní body nám dávají každou možnou pozici referenčního bodu. Přestože lze vypočítat některé falešné body, vzhledem k tomu, že objekt existuje v obraze, v referenčním bodě dojde k maximu. Maxima v A odpovídají možným instancím tvaru.

Zobecnění měřítka a orientace

Pro pevnou orientaci tvaru bylo pole akumulátoru dvourozměrné v souřadnicích referenčního bodu. Hledání tvarů libovolné orientace θ a měřítko s, tyto dva parametry jsou přidány do popisu tvaru. Pole akumulátoru se nyní skládá ze čtyř dimenzí odpovídajících parametrům (y, s, θ). R-tabulku lze také použít k zvětšení tohoto většího dimenzionálního prostoru, protože různé orientace a měřítka odpovídají snadno vypočítaným transformacím tabulky. Označte konkrétní R-stůl pro tvar S podle R (ɸ). Jednoduché transformace do této tabulky umožní detekovat zmenšené nebo otočené instance stejného tvaru. Například pokud je tvar zmenšen o s a tato transformace je označena T_s.pakT_s[R (ɸ)] = sR (ɸ) tj. všechny vektory jsou zmenšeny o s. Také pokud je objekt otočen o θ a tato transformace je označena T_θ, pakT_θ[R (ɸ)] = Rot {R [(ɸ-θ) mod2π], θ}tj. všechny indexy jsou zvýšeny o - θ modulo 2π, příslušné vektory r jsou nalezeny a poté jsou otočeny o θDalší vlastností, která bude užitečná při popisu složení zobecněných Houghových transformací, je změna referenčního bodu. Pokud chceme zvolit nový referenční bod ỹ takhle y-ỹ = z pak je modifikace R-tabulky dána R (ɸ) + z, tj. z se přidá ke každému vektoru v tabulce.

Alternativní způsob použití párů hran

Ke zmenšení prostoru parametrů lze použít dvojici okrajových pixelů. Pomocí tabulky R a vlastností popsaných výše definuje každý hranový pixel povrch v prostoru čtyřrozměrného akumulátoru a = (y, s, θ). Dva okrajové pixely v různých orientacích popisují stejnou plochu otočenou o stejné množství vzhledem k θ. Pokud se tyto dva povrchy protínají, body, kde se protínají, budou odpovídat možným parametrům A pro tvar. Je tedy teoreticky možné použít dva body v obrazovém prostoru ke zmenšení lokusu v parametrickém prostoru na jediný bod. Obtíže s hledáním průsečíků dvou ploch v prostoru parametrů však způsobí, že tento přístup bude ve většině případů neproveditelný.

Složené tvary

Pokud má tvar S složenou strukturu skládající se z dílčích částí S₁, S₂, .. S_N a referenční body pro tvary S, S₁, S₂, .. S_N jsou y, y₁, y₂, .. y_npoté pro faktor měřítka s a orientace θ, zobecněná Houghova transformace R_s(ɸ) darováno ${displaystyle R_ {phi} = T_ {s} vlevo {T_ {heta} vlevo [igcup _ {k = 1} ^ {N} R_ {s_ {k}} (phi) ight] ight}}$ . Obavy z této transformace spočívají v tom, že volba reference může výrazně ovlivnit přesnost. Abychom to překonali, navrhl Ballard vyhlazení výsledného akumulátoru pomocí kompozitní vyhlazovací šablony. Kompozitní vyhlazovací šablona H (y) je uveden jako složený konvoluce jednotlivých vyhlazovacích šablon dílčích tvarů. ${displaystyle H (y) = součet _ {i = 1} ^ {N} h_ {i} (y-y_ {i})}$ . Vylepšený akumulátor je pak dán A_s = A * H a maxima v A_s odpovídá možným instancím tvaru.

Prostorový rozklad

Pozorování, že globální Houghovu transformaci lze získat součtem místních Houghových transformací disjunktní podoblasti, Heather a Yang^[5] navrhla metodu, která zahrnuje rekurzivní dělení obrazu do dílčích obrazů, z nichž každý má svůj vlastní prostor parametrů, a jsou uspořádány do a čtyřstrom struktura. Výsledkem je lepší efektivita při hledání koncových bodů segmentů řádků a lepší robustnost a spolehlivost při extrakci řádků v hlučných situacích při mírně zvýšené ceně paměti.

Implementace

Implementace používá následující rovnice:^[6]

${displaystyle x = x_ {c} + x 'nebo x_ {c} = x-x'}$

${displaystyle y = y_ {c} + y 'nebo y_ {c} = y-y'}$

${displaystyle cos (pi -alpha) = x '/ r {ext {or}} x' = rcos (pi -alpha) = - rcos (alfa)}$

${displaystyle sin (pi -alpha) = y '/ r {ext {or}} y' = rsin (pi -alpha) = rsin (alpha)}$

Kombinací výše uvedených rovnic máme:

${displaystyle x_ {c} = x + rcos (alfa)}$

${displaystyle y_ {c} = y + rsin (alfa)}$

Konstrukce R-tabulky

(0) Pomocí libovolného převeďte ukázkový obrazec tvaru na obraz hrany detekce hran jako algoritmus Hranatý detektor hran

(1) Vyberte referenční bod (např. (X_C, y_C))

(2) Nakreslete čáru od referenčního bodu k hranici

(3) Vypočítat ɸ

(4) Uložte referenční bod (X_C, y_C) jako funkce ɸ v R (ɸ) stůl.

Detekce:

(0) Převeďte ukázkový obrazec tvaru na obraz hrany pomocí libovolného algoritmu detekce hran Hranatý detektor hran.

(1) Inicializujte tabulku Akumulátor: Sekera_cmin. . . X_cmax] [r_cmin. . . y_cmax]

(2) Pro každý hranový bod (x, y)

(2.1) Použití úhlu přechodu ɸ, získat z R-tabulky vše (α, r) hodnoty indexované pod ɸ.

(2.2) Pro každého (α, r), vypočítat kandidátské referenční body:

X_C = x + r cos (α)

y_C = y + r sin (α)

(2.3) Zvýšení počtu (hlasování):

++ A ([[x_C]] [r_C])

(3) Možná umístění obrysu objektu jsou dána místními maximy v Sekera_C] [r_C].

Li Sekera_C] [r_C]> T, pak se obrys objektu nachází na (X_C, y_C)

Obecný případ:

Předpokládejme, že objekt prošel určitou rotací ϴ a jednotné měřítko s:

(x ‘, y’) -> (x ’’, y ’’)

x "= (x’cos (ϴ) - y’sin (ϴ)) s

y "= (x’sin (ϴ) + y’cos (ϴ)) s

Nahrazení x „x“ a y „y“:

X_C = x - x "nebo x_C = x - (x’cos (ϴ) - y’sin (ϴ)) s

y_C = y - y "nebo y_C = y - (x’sin (ϴ) + y’cos (ϴ)) s

(1) Inicializujte tabulku Akumulátor: Sekera_cmin. . . X_cmax] [r_cmin. . . y_cmax] [q_min . . .q_max] [s_min . . . s_max]

(2) Pro každý hranový bod (x, y)

(2.1) Použití jeho gradientního úhlu ɸ, získat všechny (α, r) hodnoty z R-tabulky

(2.2) Pro každého (α, r), vypočítat kandidátské referenční body:

x '= r cos (α)

y ’= r sin (α)

pro(ϴ = ϴ_min; ϴ ≤ ϴ_max; ϴ ++)

pro(s = s_min; s ≤ s_max; s ++)

X_C = x - (x’cos (ϴ) - y’sin (ϴ)) s

y_C = y - (x’sin (ϴ) + y’cos (ϴ)) s

++ (A [x_C] [r_C] [ϴ] [s])

(3) Možná umístění obrysu objektu jsou dána místními maximy v Sekera_C] [r_C] [ϴ] [s]

Li Sekera_C] [r_C] [ϴ] [s]> T, pak se obrys objektu nachází na (X_C, y_C), prošlo rotací ϴ, a byl změněn s.

Výhody a nevýhody

Výhody

Je robustní až částečné nebo mírně deformované tvary (tj. Robustní k rozpoznání pod okluzí).
Je robustní vůči přítomnosti dalších struktur v obraze.
Je tolerantní k hluku.
Může najít více výskytů tvaru během stejného zpracování.

Nevýhody

Má značné výpočetní a paměťové požadavky, které se stávají akutními, když je třeba vzít v úvahu orientaci a měřítko objektu.

Související práce

Ballard navrhl použít informace o orientaci okraje, což by snížilo náklady na výpočet. Bylo navrženo mnoho účinných technik GHT, jako je SC-GHT (Použití sklonu a zakřivení jako místních vlastností).^[7]Davis a Yam^[8] také navrhl rozšíření Merlinovy práce pro orientaci a škálování invariantního párování, které doplňuje Ballardovu práci, ale nezahrnuje Ballardovo využití informací o sklonu hrany a kompozitních struktur

Viz také

Reference

^ D.H. Ballard, „Zobecnění Houghovy transformace k detekci libovolných tvarů“, rozpoznávání vzorů, sv. 13, č. 2, s. 11-122, 1981
^ Jaulin, L .; Bazeille, S. (2013). Extrakce tvaru obrazu pomocí intervalových metod (PDF). In Proceedings of Sysid 2009, Saint-Malo, France.
^ Merlin, P. M .; Farber, D. J. (leden 1975). "Paralelní mechanismus pro detekci křivek v obrazech". Transakce IEEE na počítačích. C-24 (1): 96–98. doi:10.1109 / t-c.1975.224087. ISSN 0018-9340.
^ L. Davis, „Hierarchické generalizované Houghovy transformace a liniové segmentové generalizované Houghovy transformace“ „University of Texas Computer Sciences, listopad 1980
^ J.A. Heather, Xue Dong Yang, „Prostorový rozklad Houghovy transformace“, 2. kanadská konference o počítačové a robotické vizi, 2005.
^ Ballard a Brown, oddíl 4.3.4, Sonka et al., oddíl 5.2.6
^ A. A. Kassim, T. Tan, K. H. Tan, „Srovnávací studie efektivních generalizovaných technik Houghovy transformace“, Image and Vision Computing, svazek 17, číslo 10, strany 737-748, srpen 1999
^ L. Davis a S. Yam, „Zobecněná houghová transformace pro rozpoznávání tvarů“. University of Texas Computer Sciences, TR-134, únor 1980.

externí odkazy

Implementace OpenCV zobecněné Houghovy transformace http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html
Výukový program a implementace zobecněných Houghových transformací http://www.itriacasa.it/generalized-hough-transform/default.html
Praktická implementace generalizované Houghovy transformace http://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html
Implementace FPGA zobecněných Houghových transformací, IEEE Digital Library http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5382047&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5382047
Implementace MATLAB zobecněné Houghovy transformace http://www.mathworks.com/matlabcentral/fileexchange/44166-general-hough-transform

[1] D.H. Ballard, „Zobecnění Houghovy transformace k detekci libovolných tvarů“, rozpoznávání vzorů, sv. 13, č. 2, s. 11-122, 1981

[2] Jaulin, L .; Bazeille, S. (2013). Extrakce tvaru obrazu pomocí intervalových metod (PDF). In Proceedings of Sysid 2009, Saint-Malo, France.

[3] Merlin, P. M .; Farber, D. J. (leden 1975). "Paralelní mechanismus pro detekci křivek v obrazech". Transakce IEEE na počítačích. C-24 (1): 96–98. doi:10.1109 / t-c.1975.224087. ISSN 0018-9340.

[4] L. Davis, „Hierarchické generalizované Houghovy transformace a liniové segmentové generalizované Houghovy transformace“ „University of Texas Computer Sciences, listopad 1980

[5] J.A. Heather, Xue Dong Yang, „Prostorový rozklad Houghovy transformace“, 2. kanadská konference o počítačové a robotické vizi, 2005.

[6] Ballard a Brown, oddíl 4.3.4, Sonka et al., oddíl 5.2.6

[7] A. A. Kassim, T. Tan, K. H. Tan, „Srovnávací studie efektivních generalizovaných technik Houghovy transformace“, Image and Vision Computing, svazek 17, číslo 10, strany 737-748, srpen 1999

[8] L. Davis a S. Yam, „Zobecněná houghová transformace pro rozpoznávání tvarů“. University of Texas Computer Sciences, TR-134, únor 1980.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]