Houghova transformace
Použití směru gradientu ke snížení počtu hlasůEdit
Vylepšení navržené O’Gormanem a Clowesem lze použít k detekci čar, pokud vezmeme v úvahu, že lokální gradient intenzity obrazu bude nutně ortogonální k hraně. Protože detekce hran obecně zahrnuje výpočet velikosti gradientu intenzity, směr gradientu se často zjišťuje jako vedlejší efekt. Pokud se daný bod o souřadnicích (x,y) skutečně nachází na přímce, pak lokální směr gradientu udává parametr θ odpovídající zmíněné přímce a parametr r je pak okamžitě získán. (Shapiro a Stockman, 305) Směr gradientu lze odhadnout s přesností 20°, což zkrátí stopu sinusoidy z plných 180° na zhruba 45°. To zkracuje dobu výpočtu a má zajímavý efekt v podobě snížení počtu zbytečných hlasů, čímž se zvyšuje viditelnost hrotů odpovídajících skutečným liniím v obraze.
Houghova transformace založená na jádře (KHT)Edit
Fernandes a Oliveira navrhli vylepšené schéma hlasování pro Houghovu transformaci, které umožňuje softwarové implementaci dosáhnout výkonu v reálném čase i na relativně velkých obrazech (např. 1280×960). Houghova transformace založená na jádře používá stejný ( r , θ ) {\displaystyle (r,\theta )}
parametrizaci navrženou Dudou a Hartem, ale pracuje se shluky přibližně kolineárních pixelů. Pro každý shluk se hlasuje pomocí orientovaného elipticko-gaussovského jádra, které modeluje nejistotu spojenou s nejlépe vyhovující linií vzhledem k příslušnému shluku. Tento přístup nejenže výrazně zlepšuje výkonnost hlasovacího schématu, ale také vytváří mnohem čistší akumulátor a činí transformaci odolnější vůči detekci falešných linií.
3-D Houghova transformace založená na jádru pro detekci rovin (3DKHT)Edit
Limberger a Oliveira navrhli deterministickou techniku pro detekci rovin v neorganizovaných mračnech bodů, jejíž náklady jsou n log ( n ) {\displaystyle n\log(n)}.
v počtu vzorků, přičemž dosahuje výkonu v reálném čase pro relativně velké soubory dat (až 10 5 {\displaystyle 10^{5}}.
bodů na procesoru 3,4 GHz). Je založen na rychlé hlasovací strategii Houghovy transformace pro rovinné oblasti, inspirované Houghovou transformací založenou na jádře (KHT). Tato 3D Houghova transformace založená na jádru (3DKHT) používá rychlý a robustní algoritmus pro segmentaci shluků přibližně spolurovinných vzorků a hlasuje pro jednotlivé shluky (místo pro jednotlivé vzorky) na ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }.
) sférického akumulátoru s použitím trojrozměrného Gaussova jádra. Tento přístup je o několik řádů rychlejší než stávající (nedeterministické) techniky pro detekci rovin v mračnech bodů, jako jsou RHT a RANSAC, a lépe se škáluje s velikostí souborů dat. Lze jej použít v jakékoli aplikaci, která vyžaduje rychlou detekci rovinných prvků na velkých souborech dat.
Houghova transformace křivek a její zobecnění pro analytické a neanalytické tvaryUpravit
Ačkoli výše popsaná verze transformace platí pouze pro vyhledávání přímek, podobnou transformaci lze použít pro vyhledávání jakéhokoli tvaru, který lze reprezentovat sadou parametrů. Například kruh lze transformovat na sadu tří parametrů, které představují jeho střed a poloměr, takže Houghův prostor se stane trojrozměrným. Tímto způsobem lze nalézt také libovolné elipsy a křivky, stejně jako jakýkoli tvar snadno vyjádřitelný jako množina parametrů.
Zobecnění Houghovy transformace pro detekci analytických tvarů v prostorech s libovolnou dimenzionalitou navrhli Fernandes a Oliveira. Na rozdíl od jiných přístupů založených na Houghově transformaci pro analytické tvary nezávisí Fernandesova technika na tvaru, který chceme detekovat, ani na typu vstupních dat. Detekci lze řídit podle typu analytického tvaru změnou předpokládaného modelu geometrie, v němž byla data zakódována (např. euklidovský prostor, projektivní prostor, konformní geometrie atd.), přičemž navržená formulace zůstává beze změny. Rovněž zaručuje, že zamýšlené tvary jsou reprezentovány s nejmenším možným počtem parametrů, a umožňuje souběžnou detekci různých druhů tvarů, které nejlépe odpovídají vstupní množině záznamů s různými rozměry a různými geometrickými definicemi (např. souběžná detekce rovin a koulí, které nejlépe odpovídají množině bodů, přímek a kružnic).
Pro složitější tvary v rovině (tzn, tvary, které nelze analyticky reprezentovat v nějakém 2D prostoru), se používá zobecněná Houghova transformace, která umožňuje volit funkci pro určitou polohu, orientaci a/nebo měřítko tvaru pomocí předem definované vyhledávací tabulky.Houghova transformace kumuluje příspěvky od všech pixelů v detekované hraně.
Proces detekce kružniceUpravit
- Nejprve vytvoříme akumulační prostor, který je tvořen buňkou pro každý pixel. Zpočátku je každá buňka nastavena na 0.
- Pro každý okrajový bod (i, j) v obraze inkrementujeme všechny buňky, které podle rovnice kruhu ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}.
by mohl být střed kružnice. Tyto buňky jsou v rovnici reprezentovány písmenem a {\displaystyle a}
.
- Pro každou možnou hodnotu a {\displaystyle a}
nalezenou v předchozím kroku najděte všechny možné hodnoty b {\displaystyle b}
, které splňují rovnici.
- V prostoru akumulátoru hledejte lokální maxima. Tato políčka představují kružnice, které byly algoritmem detekovány.
Pokud předem neznáme poloměr kružnice, kterou se snažíme lokalizovat, můžeme k hledání kružnic s libovolným poloměrem použít trojrozměrný akumulační prostor. To je samozřejmě výpočetně náročnější.
Tato metoda může také detekovat kružnice, které jsou částečně mimo akumulační prostor, pokud se v něm stále nachází dostatečná plocha kružnice.
Detekce 3D objektů (roviny a válce)Upravit
Houghovu transformaci lze také použít pro detekci 3D objektů v datech o rozsahu nebo 3D mračnech bodů. Rozšíření klasické Houghovy transformace pro detekci rovin je poměrně přímočaré. Rovina je reprezentována explicitní rovnicí z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}.
, pro který můžeme použít 3D Houghův prostor odpovídající a x {\displaystyle a_{x}}.
, a y {\displaystyle a_{y}}
a d {\displaystyle d}
. Toto rozšíření trpí stejnými problémy jako jeho 2D protějšek, tj. lze spolehlivě detekovat blízké vodorovné roviny, zatímco výkonnost se zhoršuje, jakmile se směr roviny stává svislým (velké hodnoty a x {\displaystyle a_{x}}.
a a y {\displaystyle a_{y}}.
zesilují šum v datech). Tato formulace roviny byla použita pro detekci rovin v mračnech bodů získaných z leteckého laserového skenování a funguje velmi dobře, protože v této oblasti jsou všechny roviny téměř vodorovné.
Pro zobecněnou detekci roviny pomocí Houghovy transformace lze rovinu parametrizovat jejím normálovým vektorem n {\displaystyle n}.
(při použití sférických souřadnic) a její vzdálenosti od počátku ρ {\displaystyle \rho }
a výsledkem je trojrozměrný Houghův prostor. Výsledkem je, že každý bod ve vstupních datech hlasuje pro sinusový povrch v Houghově prostoru. Průsečík těchto sinusových ploch označuje přítomnost roviny. Obecnější přístup pro více než tři rozměry vyžaduje vyhledávací heuristiku, aby zůstal proveditelný.
Houghova transformace byla také použita k nalezení válcových objektů v mračnech bodů pomocí dvoukrokového přístupu. V prvním kroku je nalezena orientace válce a ve druhém kroku je nalezena poloha a poloměr.
Použití vážených rysůUpravit
Jeden z běžných detailů varianty. To znamená, že nalezení binů s nejvyšším počtem v jedné fázi lze použít k omezení rozsahu hodnot hledaných v další fázi.
Pečlivě zvolený prostor parametrůEdit
Vysoký prostor parametrů pro Houghovu transformaci je nejen pomalý, ale při nepromyšlené implementaci může snadno zahltit dostupnou paměť. I když programovací prostředí umožňuje alokaci pole většího, než je dostupný paměťový prostor prostřednictvím virtuální paměti, počet výměn stránek, které jsou k tomu zapotřebí, bude velmi náročný, protože pole akumulátoru se používá náhodně a zřídkakdy se zastaví v souvislé paměti, protože přeskakuje z indexu na index.
Připomeňme si úlohu hledání elipsy v obrázku 800×600. Za předpokladu, že poloměry elips jsou orientovány podél hlavních os, je prostor parametrů čtyřrozměrný. (x,y) definuje střed elipsy a a a b označují dva poloměry. Připustíme-li, že střed může být kdekoli v obraze, přidáme omezení 0<x<800 a 0<y<600. Pokud poloměry dostanou stejné hodnoty jako omezení, zůstane řídce zaplněné pole akumulátorů o více než 230 miliardách hodnot.
Takto koncipovaný program pravděpodobně nebude mít možnost alokovat dostatek paměti. To neznamená, že problém nelze vyřešit, ale pouze to, že je třeba najít nové způsoby omezení velikosti pole akumulátorů, díky nimž je to proveditelné. Například:
- Pokud je rozumné předpokládat, že každá elipsa je celá obsažena v obraze, lze rozsah poloměrů zmenšit. Největší poloměry mohou být, pokud je střed elipsy ve středu obrazu, což umožňuje, aby se okraje elipsy roztáhly až k okrajům. V tomto extrémním případě může být každý z poloměrů pouze poloviční velikosti obrazu orientovaného stejným směrem. Zmenšení rozsahu a a b tímto způsobem redukuje pole akumulátorů na 57 miliard hodnot.
- Výměna přesnosti za prostor při odhadu Houghovy transformace akumuluje příspěvky ze všech pixelů v detekovaném okraji. Houghova transformace akumuluje příspěvky od všech pixelů v detekované hraně. he center: Pokud je střed předpovězen s odchylkou 3 na ose x i y, zmenší se tím velikost pole akumulátorů na přibližně 6 miliard hodnot.
- Přesnost výměny za prostor při odhadu poloměrů: Pokud se poloměry odhadnou každý o 5, dojde k dalšímu zmenšení velikosti pole akumulátorů, a to přibližně o 256 milionů hodnot.
- Oříznutí obrazu na oblasti zájmu. To je závislé na obrázku, a proto nepředvídatelné, ale představte si případ, kdy se všechny hrany zájmu v obrázku nacházejí v levém horním kvadrantu tohoto obrázku. V tomto případě lze pole akumulátorů ještě více zmenšit omezením všech 4 parametrů o faktor 2, takže celkový faktor zmenšení je 16.
Při použití pouze prvních tří z těchto omezení na příklad, o kterém byla řeč, se velikost pole akumulátorů zmenší téměř 1000krát, čímž se sníží na velikost, která se s mnohem větší pravděpodobností vejde do paměti moderního počítače.
Efektivní algoritmus detekce elipsyEdit
Yonghong Xie a Qiang Ji uvádějí efektivní způsob implementace Houghovy transformace pro detekci elipsy překonáním problémů s pamětí. Jak je uvedeno v algoritmu (na straně 2 článku), tento přístup používá k detekci elipsy v obraze pouze jednorozměrný akumulátor (pro vedlejší osu). Složitost je O(N3) v počtu nenulových bodů v obraze
.
Leave a Reply