Gyors Hough Transform

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. szeptember 6-án felülvizsgált verziótól ; az ellenőrzések 13 szerkesztést igényelnek .

A gyors Hough-transzformáció ( Fast Hough Transform , röv . FHT) a Hough-transzformáció olyan módosítása, amely lehetővé teszi vonalak (valamint további módosításokkal szegmensek és négyszögek ) paraméteres azonosítását a tény felhasználása miatt kisebb számítási bonyolultsággal. a figyelembe vett diszkrét vonalak önmetszéspontja.

Történelem

Az algoritmust először M. L. Brady javasolta 1992-ben, [1] később különböző szerzők többször is újra feltalálták. [2] [3]

Definíció

Adjunk meg egy méretű képet . Tekintsünk diádikus vonalakat (egyenes vonalakat), amelyek a képen egyenként pixelekből állnak (oszloponként egy pixel). $m\szer n$ $m^{2}$ $n$

Legyen a paraméterek által megadott diadikus egyeneshez tartozó th pixel intenzitása ; — Ennek a diadikus vonalnak a félképe. $I^{(s,t)}(i)$ $én$ $s,t$ ${\displaystyle S^{(s,t)))$

A diszkrét Hough-transzformáció képét a következő képlet határozza meg:

S^{(s,t)}=\sum _{i=0}^{n-1}(I^{(s,t)}(i))

Az összes érték közvetlen kiszámítása műveleteket igényel : a paraméterek különböző értékeinek felsorolása , , az egyes értékpárok felsorolása . ${\displaystyle S^{(s,t)))$ $O$ $\left(m^{2}n\right)$ $m$ $s$ $t$ $n$ $én$

Az FHT algoritmus viszont, amely a szegmensek egymás közötti metszéspontjainak figyelembevételén alapul, műveleteket igényel , műveletek szükségesek egy egyeneshez (négyzetes képekhez ). A T. M. Khanipov [4] által megfogalmazott tétel szerint lehetetlen aszimptotikusan kisebb számítási bonyolultságú diádikus sorokat összeadni. $\Theta$ $\left(mn\log m\right)$ $\Theta$ $\left({\frac {n\log m}{m}}\right)$ $\Theta$ $\left(\log n\right)$

Algoritmus

Az algoritmus az „ oszd meg és uralkodj ” elvén alapul. A probléma az, hogy megtaláljuk a pixelértékek összegét a kép „bal” és „jobb” szélét összekötő szegmensek mentén. A kép felére van osztva, minden részben önállóan oldják meg a problémát. Az egyes szegmensek végösszegének kiszámításához a „bal” és a „jobb” felén lévő válaszokat összeadjuk.

Az FHT algoritmusban tetszőleges vonalak képpontjait diszkréten diádikus vonalakkal közelítik. Az egyenes diádikus közelítésének képpontjai a képméretben legfeljebb képponttal távolodnak el az eredeti egyenestől. [5] $n\szer n$ $O$ $(\log n)$

A szegmenseket az összekapcsolt pixelek középpontja paraméterezi. Ezért egy szegmens részszegmensekre bontása csak megközelítőleg alkotja az eredeti szegmenst. A közelítési hiba rekurziós lépésekkel kumulatív, de legfeljebb pixel. [5] A szegmens így megszerkesztett képpontokká diszkretizálását diádikus közelítésnek nevezzük . $O$ $(\log n)$

Generatív diadikus minták

Továbbá a minta pixelek halmaza, amely a kép minden függőleges részén tartalmaz egy elemet. A minta eltérése lesz az érték , és a koordináta lesz az érték . A mintaváltást halmaznak nevezzük ${\displaystyle p=\{(x_{i},i)\}_{i=0}^{2^{k}-1))$ ${\displaystyle t(p)=x_{2^{k}-1}-x_{0))$ ${\displaystyle s(p)=x_{0))$

p ↗ ( a , b ) = { ( x én + a , y én + b ) | ( x én , y én ) ∈ p } {\displaystyle p\narrow (a,b)=\lkapcsos zárójel \left(x_{i}+a,y_{i}+b\right)\ |\ (x_{i},y_{i})\in p \rbrace }

p\narrow (a,b)=\lkapcsos zárójel \left(x_{i}+a,y_{i}+b\right)\ |\ (x_{i},y_{i})\in p \rbrace

A szélesség és lejtés generatív diadikus mintái rekurzív módon vannak definiálva. A esetén a minta egy pixelből áll, a esetén pedig -ben fejeződik ki .

2^k

{\displaystyle t<2^{k))

k=t=0

k>0

k-1

$P_{t}^{k}={\begin{cases}\{(0,0)\}&,k=0\\\ P_{t/2}^{k-1}\ \ \ \cup \ P_{t/2}^{k-1}\ \ \ \ \közel (t/2,2^{k})&,k>0,\ \ t\equiv 0\ (mod2)\\ P_{(t-1)/2}^{k-1}\pohár \ P_{(t-1)/2}^{k-1}\közel ((t+1)/2,2^{k })&,k>0,\ \t\equiv 1\ (mod2)\end{cases}}$

Diadikus vonalak

A túlnyomórészt vízszintes, felfelé irányuló, diadikus vonalak az összes függőlegesen eltolt generatív mintából származnak , amelyek a kép összes lehetséges koordinátájával épülnek fel . $P_{s,t}^{k}=P_{t}^{k}\narrow (s,0)$ $s\in \{0,...,2^{k}-1\},t\in \{0,...,2^{k}-1\}$

A Hough-transzformáció hozzávetőleges kiszámításához meg kell találni a kép összes diadikus vonalának összegét. Ebben a vonalak összegében minden egyes pont szerepel. A rekurzív átmenet miatt ez az összegzés a bal, külön a jobb felek külön-külön történő számlálására redukálódik, ami lehetővé teszi, hogy a számítást lecsökkentsük a pontok feletti összegek kiszámítására. $S_{s,t}=\sum _{(x,y)\in P_{s,t}^{k}}I_{x,y}$ ${\displaystyle 2^{k}\cdot 2^{k))$ $2^k$ $2\cdot 2^{k}\cdot 2^{k-1}$ $2^{k-1}$

Tekintsük a 0 és 1 számokból álló bináris szavakat. A diadikus szavak halmazát rekurzívan definiáljuk. diádikus szónak nevezzük, ha a vagy alakja van , ahol egy üres vagy diadikus szó. Minden háromnál nem hosszabb diádikus szó: 0, 1, 000, 010, 101, 111. $w$ $w$ $a0a$ $a1a$ $a$

Minden diadikus szóra a kumulatív összeget veszik figyelembe . Azt fogjuk mondani, hogy a pixelsorozat egy diadikus egyenes, amely összeköti a pixelek középpontját és . ${\displaystyle {\overline {b_{1}b_{2}...b_{n))))$ $\{a_{i}\}_{0}^{2^{k}-1},a_{i}=\sum _{0}^{i}b_{i}$ ${\displaystyle \{(a_{i},i)\}_{0}^{2^{k}-1))$ $(0,0)$ $(a_{2^{k}-1},2^{k}-1)$

Vannak pontosan diadikus hosszúságú vonalak . Minden és párhoz egy . $2^k$ $2^k$ $(0,0)$ ${\displaystyle (h,2^{k}-1),0\leqslant h<2^{k))$

Formai leírás

Az FHT algoritmus a következőképpen épül fel: [6]

A mátrix kezdeti állapota a méret eredeti képe . Ezután a számítás a -edik szinteken sorra történik, az elsőtől kezdve: a -edik szinten az aktuális állapotú mátrixot csoportokra osztják a második tengely koordinátájának egész részének egyenlőségének elve szerint. -vel való osztás után ; almátrixokat kapunk ; egyesítsd a szomszédosakat párokba (metszéspontok nélkül ez lehetséges, mivel a mátrix mérete kettő hatványa), és ebben a párban hívjuk az első almátrixot, amely a mátrix második koordinátája mentén kisebb koordinátákon található , és a másik - a második; minden párban az első helyett az összegét a megfelelő másodikkal írjuk, a második helyett pedig az első és a második összegét egy ciklikus eltolással balra. Így az ilyen vonalak Hough-képe olyannak tekinthető, hogy bármely pontpárra, amelynek koordinátái ebből az egyenesből származnak , teljesül a diádikus egyenesekkel történő közelítéssel. A többi sor képének kiszámításához elegendő a képet elforgatni, elvégezni ugyanazt a műveletet, majd hozzáadni az eredményeket. ${\displaystyle 2^{p}\times 2^{q))$ $q-1$ $én$ $2^i$ ${\displaystyle 2^{p}\times 2^{i))$ ${\megjelenítési stílus (x_{1},y_{1}),(x_{2},y_{2})}$ $(x_{1}\neq x_{2})\jobbra nyíl ((y_{1}\neq y_{2})\wedge (x_{1}<x_{2}\Leftrightarrow y_{1}<y_ {2}))$

Az így kapott mátrixok minden szinten az FHT piramis elemei. Az FHT-piramis formális leírása : Az FHT-piramis nulladik szintje az eredeti kép (nagyságú , az utolsó pedig a Hough-kép, amely hosszúságú diádikus egyenesek mentén összegeket tartalmaz . A piramis 0. szintjének leírása , az eredeti kép vízszintes csíkokra van felosztva , ahol a csík száma, Minden csíkhoz az FHT piramis th szintje tárolja az összes lehetséges csíkminta összegét hosszával és paramétereivel . Az ilyen minták száma egy csíknál : tehát a piramis edik szintje annyi memóriát foglal el, mint az eredeti kép. $m\szer n$ ${\displaystyle n=2^{p))$ $q$ $[0,n-1]\times [k\cdot 2^{q},(k+1)\cdot 2^{q}-1]$ $k$ $k\in [0.2^{pq}-1]$ $q$ ${\displaystyle 2^{q))$ $s\in [0,n-1],t\in [0,2^{q}-1]$ ${\displaystyle n\cdot 2^{q))$ $q$

Az elhasznált memória mennyiségének változatlansága és az, hogy az egyes szinteket az eredeti képpel azonos méretű mátrixban tárolhatjuk, az értelmezhetőség elvesztése nélkül, a következő tulajdonságot adják: lehetséges az FHT piramist egy formában tárolni. mátrix, amelynek mérete eggyel nagyobb, mint az eredeti kép mérete (egy tengely mentén - a szintek száma, ), a többinél - a kép mérete).

[7]

\log _{2}n

Szoftver implementációk

Egy példa megvalósítás a pythonban:

import numpy mint np W = 2 ** 5 H = 2 ** 5 img = np . véletlenszerű . véletlenszerű ([ H , W ]) def calc_sums ( img , xmin , xmax ): res = np . nullák ([ W , xmax - xmin ]) , ha xmax - xmin == 1 : res [:, 0 ] = img [:, xmin ] else : mid = ( xmin + xmax ) // 2 ans1 = calc_sums ( img , xmin , mid ) ans2 = calc_sums ( img , mid , xmax ) x esetén tartományban ( W ) : tartomány eltolásánál ( xmax - xmin ) : res [ x , shift ] = ans1 [ x , shift // 2 ] + ans2 [ _ ( x + shift // 2 + shift % 2 ) % W , shift // 2 ] return res res = calc_sums ( img , 0 , W )

Az algoritmus az opencv könyvtárban [8] van implementálva, és felhasználható például az eltűnési pont gyors megtalálására . [9]

Általánosítások a háromdimenziós esethez

FHT repülőgépekhez

A probléma megoldása egy algoritmus használatát jelenti a kétdimenziós esethez.

A síkok haf-képe is háromdimenziós lesz (a síkot a vektor rá merőleges három koordinátáján keresztül adjuk meg). Adjuk meg a paraméterezéssel , ahol a sík és a sugáron lévő képhatár metszéspontjának koordinátája , a metszéspont koordinátája a síkban lévő sugárral párhuzamos képhatárral , és a különbség a sík második és első metszéspontjának koordinátái a képhatárokkal. Az első pont a képhatárt tartalmazó síkok és a vele párhuzamos sík metszéspontjában van . A második pont a kép határát tartalmazó síkok metszéspontjában van, párhuzamosan és -vel . $s,t,t_{2}$ $s$ $x$ $Ökör$ $s+t$ $x$ $Ökör$ $xOz$ $t_{2}$ $x$ $xOz$ $xOy$ $xOy$ $xOz$

A koordinátatengelyre túlnyomóan merőleges síkot akkor fogunk nevezni, ha a vele való normális kisebb szöget zár be ezzel a tengellyel, mint a másik kettővel. Csak azokat a síkokat vesszük figyelembe, amelyek túlnyomórészt merőlegesek az y tengelyre. A 4. ábrán látható módon 4 lejtőtípusra vannak felosztva. Az általánosság elvesztése nélkül feltételezzük, hogy a vizsgált síkok I. típusúak.

A Hough-kép sík felsorolással történő felépítése aszimptotikus bonyolultságú (a síkok száma szorozva az egy síkot összegző műveletek számával), ahol m, n, k a kép méretei az egyes dimenziókban. $O$ $\left(mnk\cdot (mn+nk+mk)\right)$

A gyors Hough-transzformáció ebben az esetben a következő algoritmus lesz:

Minden olyan tengelyre merőleges síkra , amelynek e tengely mentén koordinátája van, kiszámítja a gyors Hough-transzformációt, és az eredményt a koordináták mentén háromdimenziós térbe helyezi . $Oz$ $z$ $s,t,z$
A kapott háromdimenziós térben a tengelyre merőleges minden síkra, amelynek koordinátája e tengely mentén van, kiszámítja a gyors Hough-transzformációt, és az eredményt a koordináták mentén egy kockába helyezi . $From$ $t$ $s,t,t_{2}$

Egy ilyen transzformáció bonyolultsága az első lépés összetettségének ( ) és a második lépés összetettségének ( ) összege , amelyeket a figyelembe vett síkok számának és a síkonkénti műveletek számának szorzataként számítunk ki. Összesen, , egy síkra vonatkoztatva . $\Theta$ $\left(k\cdot mn\log m\right)$ $\Theta$ $\left(n\cdot mk\log m\right)$ $\Theta$ $\left(mnk\log m\right)$ $\Theta$ $(\log m)$

FHT 3D vonalakhoz

Egy háromdimenziós vonal félképe négydimenziós lesz (két paraméter a vonal két pontjához). Adjuk meg paraméterezéssel . a síkon lévő pont x , y koordinátái , a síkkal párhuzamos egyenes képhatárának metszéspontjának x, y koordinátái . ${\displaystyle s,t,s_{2},t_{2))$ $s,s_{2}$ $xOy$ ${\displaystyle s+t,s_{2}+t_{2))$ $xOy$

A Hough-kép háromdimenziós vonalak felsorolásával történő felépítése aszimptotikus bonyolultságú (a sorok száma szorozva az egy sor összegzéséhez szükséges műveletek számával), ahol m, n, k a kép méretei az egyes dimenziókban. $O$ $\left((mn)^{2}\cdot k\right)$

A gyors Hough-transzformáció ilyen esetre a kétdimenziós esethez hasonlóan van megfogalmazva. A kétdimenziós esetben csak egy tengely mentén volt az eltolás lehetősége, most viszont egy tengely mentén, a második tengely mentén és két tengely mentén lesz az eltolás egyszerre.

A kettős hosszúságú minták megszámlálásához (összesíthető síkok csoportjainak száma) szorozva (összeadások összetettsége minden csoporthoz) műveletek szükségesek. A 4 hosszúságú számlálási minták műveleteket igényelnek. Mintahosszak — , ahol definíciója: , azaz a figyelembe vett mintahossz száma. A kifejezéseket (a vizsgált kép lehetséges mintahosszainak számát) a geometriai progresszió összegének képletével összegezve megkapjuk az algoritmus összetettségét és egy egyenesben a bonyolultságát . A komplexitás állandó lesz. ${\frac {k}{2))$ $4 perc$ ${\frac {k}{4}}\cdot 16mn$ $d$ ${\frac {k}{d}}\cdot d^{2}mn=mnkd=mnk\cdot 2^{i}$ $én$ $\log _{2}(d)$ $\log _{2}(k)$ $\Theta$ $\left(\sum _{i=1}^{\log _{2}k}mnk\cdot 2^{i}\right)\equiv$ $\Theta$ $\left({\frac {2mnk\cdot (2^{\log _{2}k}-1)}{2-1}}\right)\equiv$ $\Theta$ $\left(mnk^{2}\right)$ $\Theta$ $\left({\frac {k^{2}}{mn}}\right)$ $m=n=k$

A BPH és a négy orosz elv kombinációja

Annak ellenére, hogy az egy soronkénti műveletek száma minden dimenzióban azonos képméret esetén állandó, minden sorra költeni kell . De ha nincs szükség minden sorra, hanem csak egy részükre, akkor az első lépéseket [10] előre ki lehet számítani, eltárolni a memóriában, majd csak azokra a sorokra számítani az összegeket, amelyekre szükség van. ${\displaystyle n^{4))$ $x$

Ezt a koncepciót négy orosz módszere rögzítette. A módszert V. Arlazarov , M. Kronrod, E. Dinits, I. Faradzhev felfedezőkről nevezték el.

A háromdimenziós vonalak eredeti FHT-algoritmusában minden szinten számítást végeznek bizonyos hosszúságú vonalak esetén. Másrészt csak az első lépésekre végezhet előkalkulációt, majd a szükséges sorokra számíthat. $\log _{2}k$ $x$

Az előreszámítási lépések optimális számának meghatározásához meg kell oldani a következő egyenletet ( az a sorok száma, amelyet az algoritmusnak meg kell találnia): $a$

$\Theta \left(mnk2^{x}\right)=\Theta \left(a2^{\log _{2}kx}\right)$

A bal oldalon az előszámítás elvégzéséhez szükséges műveletek száma látható. A jobb oldalon a kért sorok mentén összegek kereséséhez szükséges műveletek száma látható. Ha az összes egyenest meg kell keresni , akkor az egyenlet megoldása lesz , és a bal és a jobb oldal egyenlő , ami kisebb, mint előszámítás nélkül. Mindazonáltal a műveletek számának csökkentése érdekében annyi memóriával kell fizetni, amennyit a Hough-kép elfoglal (az FHT algoritmus által a foglalt memória invarianciájának tulajdonsága minden számlálási szinten). $a=mnk$ $x={\frac {1}{2}}\log _{2}k=\log _{2}{\sqrt {k}}$ $\Theta \left(mnk{\sqrt {k}}\right)$ ${\sqrt {k))$

Egy kép szegmensének összegének kiszámítása

A számítási elv nemcsak az FHT piramis utolsó szintjének (vagyis magának a Hough-képnek), hanem az FHT piramis más szintjeinek az értékeinek használatán is alapul.

A feladat két részfeladatra oszlik:

Keress két megadott pixelen átmenő diadikus vonalat
Az ezen egyenes mentén lévő értékek összegéből válassza ki az összegnek azt a részét, amely a megadott pixelek közötti mintára vonatkozik

Két adott pixelen átmenő diadikus vonal keresése

Az általánosság elvesztése nélkül feltételezzük, hogy . Itt csak a túlnyomóan függőleges mintákat fogjuk figyelembe venni, amelyek jobbra dőlnek, azaz és . A -paraméterezés is használatos , és az érték egyenlő , ahol a kép mérete a tengely mentén . ${\displaystyle y_{2}\geq y_{1))$ $x_{2}\geq x_{1}$ ${\displaystyle y_{2}-y_{1}\geq x_{2}-x_{1))$ ${\megjelenítési stílus (s,t)}$ $p$ $\log _{2}n$ $n$ $y$

Nézzük a diádikus egyenes paraméter bináris kiterjesztését így: Ekkor a minta a következőképpen írható fel ( - kerekítés a legközelebbi egész számra): $t$ ${\displaystyle t=\sum _{i=0}^{p-1}t_{i}2^{i))$ $\left[\cdot \right]$

$x=s+\sum _{r=0}^{p-1}t_{r}\left[{\frac {s^{r}y}{2^{p}-1}}\right ]$

${\displaystyle \Delta x=x_{2}-x_{1))$ feladat adataiból számítjuk ki. a vizsgált minta eltolódásainak száma a sávban , amely szintén ismert. Így csak a biteket kell visszaállítani . $\delta _{r}^{y_{1},y_{2}}=\left(D_{r}(y_{2})-D_{r}(y_{1})\right)$ $(y_{1},y_{2})$ ${\displaystyle t_{0},t_{1},\ldots ,t_{p-1))$

Egy mohó algoritmust használnak a helyreállításhoz: Minden bit nulla először. Mivel ezért a felsorolás nagyobb számú eltolásról kisebbre, szintről 0 szintre történik. Ha , akkor az ennek a szintnek megfelelő bit 1-re áll, és -kal csökken . A lépést addig ismételjük, amíg 0-ra nem változik. $t_{r}$ $i>j\rightarrow \delta _{i}^{y_{1},y_{2}}\geq \delta _{j}^{y_{1},y_{2}}$ $p-1$ $\Delta y\geq \delta _{r}^{y_{1},y_{2}}$ $\Delta y$ $\delta _{r}^{y_{1},y_{2))$ $\Delta y$

A paraméter értékét a . Ezen a paraméteren keresztül a paraméter kiszámítása a következő képlet szerint történik: $t_{i}$ $t$ $s$

$s=D(y_{1},t)-\sum _{r=0}^{p-1}t_{r}D_{r}(y_{1})$

$\#\lbrace \delta _{r}^{y_{1},y_{2}}\rbrace =p=\log _{2}n$ , tehát az algoritmus összetettsége . [7] $\Theta$ $(\log n)$

Összeg keresése egy ismert diadikus egyenes szakasza mentén

1. módszer

Az ábrára hivatkozva látható, hogy egy tetszőleges szakaszt egy egyenesen úgy számítunk ki, hogy megkeressük azoknak a diadikus mintáknak a minimális számát, amelyek a sor elejétől az adott szakasz végéig tartó részeket tartalmaznak, és a minimális számú szakaszt. olyan minták, amelyek az egyenes elejétől az adott szegmens elejéig tartó szakaszt tartalmazzák, kivéve az eredeti szegmens első pixelét. Vagyis meg kell találni az összegeket két olyan szegmenshez, amelyeknek a kezdete a kép határán van, és a végkoordináták eltérőek. $n$

Az ilyen típusú hosszúságú szegmens összegének kiszámításához (bináris kiterjesztése ) , ahol az FHT=piramis -edik szintjének -edik sávjában lévő minta összege egy paraméterekkel rendelkező egyenesre . $l$ $\sum _{j=0}^{p}\left(l_{j}\cdot 2^{j}\right)$ $\sum _{q=0}^{p}\left[l_{q}\cdot H^{s,t}\left(q,\sum _{j=q+1}^{p} l_{j}\cdot 2^{jq}\right)\right]$ $H^{s,t}\left(q,k\right)$ ${\displaystyle 2^{q))$ $k$ $q$ ${\megjelenítési stílus (s,t)}$

A belső összeg nem igényel minden lépésben teljes számítást, mivel azt az előzőből kapjuk állandó időben. Így az algoritmus összetettsége arányos a külső összegben lévő tagok számával, azaz . Mivel az eredményt két ilyen típusú szegmensre számítjuk ki, az algoritmus eredő összetettsége is . Sőt, érdemes megjegyezni, hogy egy pixel lehet többcsatornás is. [7] $\Theta$ $(\log n)$ $\Theta$ $(\log n)$

2. módszer

A szegmens a szegmensen belüli minimális számú mintából állhat össze. Az ilyen minták kereséséhez meg kell nézni az FHT piramis szintjeit, kezdve az utolsókkal és az elsőkkel bezárólag. Azonnal kiszűrheti azokat a mintákat, amelyek nem szerepelnek a szegmensben. Ha olyan mintát találunk, amely teljesen a szegmensen belül van, akkor annak összege beleszámít a szükséges összegbe, és a következő szinteken lévő felosztásokat nem veszi figyelembe. Ez a módszer számításilag összetettebb, mint az első, mivel minden olyan mintát megkövetel, amely több mint . $n$

A kép négyszögének összegének kiszámítása

Hasonlóan a szegmens összegének kiszámításához a négyszögre vonatkozó összeg kiszámításához a Hough-kép síkokra vonatkozó közbenső számításaiból, más szóval az FHT-piramisból síkok esetén.

Feltételezve, hogy annak a síknak a paraméterei, amelyen az adott négyszög található, a kívánt összeget a befogadás-kizárás képlettel számítjuk ki úgy, hogy az összeget négy téglalapra vesszük, amelyek egyik csúcsa a diádikus sík sarokcsúcsa (mi jelölje a betűvel , az ezzel a csúcstal rendelkező szakaszokat pedig a sarokszegmensekkel ). Jelöljük az adott négyszög csúcsaihoz legközelebbi és legtávolabbi pontok koordinátáit ill. A megjelölt sarokszegmensek és csúcsú sarokszegmensek összegét pluszjellel , a és ponttal rendelkezők összegét mínuszjellel vesszük. ${\megjelenítési stílus (s,t,t_{2})}$ $E$ $E$ $(i_{1},j_{1})$ $(i_{2},j_{2})$ $(i_{1}-1,j_{1}-1)$ $(i_{2},j_{2})$ $(i_{1}-1,j_{2})$ $(i_{2},j_{1}-1)$

Egy tetszőleges szögszegmens összegének megtalálásához fel kell osztani az FHT piramisban lévő szegmensekre. Figyelembe kell venni a szegmens szélességének és magasságának bináris kiterjesztését. Az egydimenziós esethez hasonlóan a szegmens vízszintesen függőleges csíkokra, függőlegesen legfeljebb vízszintes csíkokra van felosztva. A metszéspontjuk nem ad többet, mint a háromdimenziós FPH piramis szegmensei. Így egy tetszőleges szegmensre vonatkozó összeg kiszámításának bonyolultsága műveleteknek felel meg. [7] $\log _{2}n$ $\log _{2}n$ $\log _{2}n$ $\Theta$ $(\log n)$

Az FHT algoritmus alkalmazásai

Bár van némi hiba az egyenes diádikus mintával való közelítésében, a kísérletek azonban azt mutatják, hogy ez a hiba elég kicsi ahhoz, hogy a problémamegoldás során a hagyományos Hough-transzformációs algoritmust ki lehessen cserélni az FHT-algoritmusra. [tizenegy]

Egy lineáris regressziós probléma robusztus megoldása M-becslések FHT-val történő kiszámításával

Az M-becslések lineáris regressziós feladatra történő alkalmazásával radiális bázisfüggvényeket kaphatunk . Ezek egy "folyamatos" képet alkotnak, amelyből viszont mintát vesznek egy 2D hisztogrammá.

Ezután a kép konvolúcióját a kiválasztott M-becslőnek megfelelő diszkretizált kernellel hajtjuk végre. A kapott Hough-kép alapján FHT segítségével számítjuk ki. A maximum koordinátája a paraméterek terén - és lesz a kívánt M-becslés. $K$

Gyors lineáris bináris klaszterezés

A feladat a következőképpen fogalmazódik meg: meg kell találni egy hipersíkot, amely 2 osztályra osztja a képet. A kép normalizált kép hisztogramjaként jelenik meg . $P$

$L$ a kívánt hipersík, amely a képeket két osztályra osztja , a hisztogram összes elemének osztálya. $A_{L},B_{L}$ $\Omega$

Használt összeadó statisztika ( - -edik koordináta ): $X\subset \Omega$ $x_{i}$ $én$ $x$

$D^{0}(X)=\sum _{x\in X}P(x)$
$D_{i}^{1}(X)=\sum _{x\in X}x_{i}P(x)$
$D_{ij}^{2}(X)=\sum _{x\in X}x_{i}x_{j}P(x)$

A klaszterszétválasztási problémák megoldására számos, a priori ismert tulajdonságokkal rendelkező, ugyanakkor additív statisztika szempontjából kiszámítható funkcionális létezik. Érdemes még egyszer megemlíteni, hogy ezek a funkcionálisok általában nem konvexek, és optimális értékük meghatározásának egyetlen megbízható módja az elválasztó felületek paraméterterében a rácson történő kimerítő felsorolás.

Naiv algoritmus: A hisztogramot lineáris méretű diszkrét vonalak metszik . Mindegyiknél el kell végezni a súlyok, a kovarianciamátrixok és végül a kritériumértékek kiszámítására szolgáló műveleteket. Így a naiv algoritmus számítási bonyolultsága műveletek. Hasonlóképpen kimutatható, hogy háromdimenziós esetben az algoritmus számítási bonyolultsága . $O(n^{2})$ $n$ $O(n^{2})$ $O(n^{4})$ $O(n^{6})$

Ebben a szakaszban kumulatív összegzést alkalmazunk: a bemeneti kép összes rétegének megfelelő elemeinek összegét, amelynek indexe nem haladja meg, a kimeneti kép számát tartalmazó rétegelemre írjuk . $én$ $én$

A képpontértékek összege a kimeneti kép bármely sorában megegyezik az eredeti kép azon részének összegével, amely nem e sor alatt van. Ezenkívül a kimeneti kép bármely túlnyomórészt vízszintes egyenes vonala mentén az összeg megegyezik az eredeti képen általa határolt felső félsík összegével. A bal oldali félsíkok feletti összegek túlnyomóan függőleges egyenes vonalakon történő hasonló kifejezéséhez a függőleges helyett a kép vízszintes kumulatív összegét kell elvégezni.

Algoritmus:

számítson ki egy képkészletet, amely tartalmazza a szükséges additív statisztikák értékeit a bemeneti hisztogram ( ) egyes elemeihez (kétdimenziós esetben 6, háromdimenziós esetben 10) ${\displaystyle D^{0},D_{i}^{1},D_{ij}^{2))$
az egyes tengelyek mentén a kumulatív összeget kiszámítva egy sor képet kapunk. Ennek a sornak a dimenzióhoz kapcsolódó bármely képénél a hipersík összege, amely túlnyomórészt merőleges az indexű tengelyre , megegyezik a megfelelő additív statisztikával, amelyet a féltérre számítanak ki, beleértve az origót is, és amelyet a választott hipersík határol. Ismerve az additív statisztika értékét egy féltérre, könnyen megkaphatjuk ugyanazt a statisztikát a másodikra, ha a teljes képre számított statisztikából kivonjuk. $d$ $d$
Most, miután kiszámítottuk az additív statisztikát a hipersíkok összes szétválasztására, kiszámíthatjuk az optimális klaszterezés kiválasztásának kritériumának értékeit.

Ha egyszerűen összegezzük az összes hipersíkot, akkor kétdimenziós esetben a komplexitás , háromdimenziós esetben . ( dimenziós ) $O(mn^{3})$ $O(mn^{5})$ $k$ $O(mn^{2k-1})$

A hipersíkok feletti összegzés (egyenesek 2D-ben, síkok 3D-ben...) FHT segítségével végezhető el. Ez segít csökkenteni az egyes képek bonyolultságát. Vagyis most a komplexitás a kétdimenziós esetben van, a háromdimenziósban . $O(n^{2k-1})$ $O(n^{k}\log {\left(n\right)})$ $m$ $O(mn^{2}\log {\left(n\right)})$ $O(mn^{3}\log {\left(n\right)})$

Tehát a végső algoritmus:

kumulatív összegzés
Az additív statisztikák számlálása
BPH
A maximum megtalálása a Hough térben

Bonyolultság: idő , memória . $O(mn^{k}\log {\left(n\right)})$ $O(mn^{k})$

A kétdimenziós esetben részletesebben:

Összesített összegzés: $O(n^{2})$
Felkészülés az additív statisztikák kiszámítására: $O(n^{2})$
BPH: $O\left(n^{2}\log {\left(n\right)}\right)$
A maximum megtalálása a Hough térben: $O(n^{2})$

Végső nehézség: $O(n^{2}\log {\left(n\right)})$

3D-s esetben részletesebben:

Összesített összegzés: $O(n^{3})$
Felkészülés az additív statisztikák kiszámítására: $O(n^{3})$
BPH: $O\left(n^{3}\log {\left(n\right)}\right)$
A maximum megtalálása a Hough térben: $O(n^{3})$

Végső nehézség: $O(n^{3}\log {\left(n\right)})$

Egyéb felhasználások

Az alábbiakban csak néhány olyan probléma található, amelyek a Hough-transzformációval megoldhatók.

Egyenletesen mozgó objektumok követése kockánkénti képkülönbség segítségével. Ezek a tárgyak kifejezett egyenes vonalakat hagynak a nyomukon. [12] [13]
Eltűnési pont észlelése a képen. Az eltűnési pont a képsík azon pontja, ahol a 3D jelenet párhuzamos vonalainak vetületei metszik egymást. [14] [15]
tomográfiás helyreállítás. Az elemzett objektum képének röntgensugárzással vetületei kialakításának eljárását általában a Hough és Radon transzformációk modellezik, és a vizsgált objektum háromdimenziós szerkezetének megszerzése gyakran az inverz Hough vagy Radon transzformáció megoldására redukálódik. [16]
Orvosi képek elemzése. [17]
A radiális torzítás vakkalibrálására szolgáló algoritmusok megvalósításában, feltéve, hogy egyenes vonalú objektumok találhatók a színpadon. A Hough-image új funkcionalitásának optimalizálásával a radiális torzítás kompenzáció paraméterei kerülnek kiválasztásra. [tizennyolc]
A kamera leütési fokának meghatározása. Az epipoláris mintázatból az FHT kiszámítása és egy olyan egyenes keresése alapján, amelyen a vizsgált vonalak pontjai az epipoláris mintázatban helyezkednek el.
Kézírás felismerés. [19]
A betűtípus dőlésszögének meghatározása. Abból a tényből kiindulva, hogy a betűtípus egy szögben elhelyezkedő, egyenes szegmensekből álló karaktereket tartalmaz, ilyen szög mentén a fél-kép nagyobb értéket képvisel. [húsz]
Vonalkód felismerés. [21] [22]
A formák hasonlóságának mértékének meghatározása. [23]
Háromdimenziós képek vektorizálása. [24]
Műholdnyomok észlelése hosszú expozíciós képekről. [25]
Radarcélok észlelése. [26] [27]
Földalatti szelvény deformáció elemzése. [28]
Mikroáramkörök topológiájának felépítésének elemzése fényképek alapján. [29]
A járműtengelyek számának megszámlálása az oldalról készített kamerával készített képek kerékérzékelő nyomaiból. [harminc]
Átlátszó ásványok lapos felületeinek 3D-s rekonstrukciója képkészletből. [31]
SAR-képek elemzése. [32]

Jegyzetek

↑ Martin L. Brady, Whanki Yong. Fast Parallel Discrete Approximation Algorithms for the Radon Transform // Proceedings of the Fourth Annual Annual ACM Symposium on Parallel Algorithms and Architectures. - New York, NY, USA: ACM, 1992. - S. 91-99 . — ISBN 9780897914833 . - doi : 10.1145/140901.140911 .
↑ JE Vuillemin. Gyors lineáris Hough transzformáció // Alkalmazás-specifikus rendszerek, architektúrák és processzorok nemzetközi konferenciája, Proceedings. - IEEE, 1994. - ISBN 0-8186-6517-3 . — ISSN 1063-6862 . - doi : 10.1109/ASAP.1994.331821 .
↑ S.M. Karpenko, D.P. Nikolaev, P.P. Nikolaev, V.V. Posztnyikov. Gyors átalakítás ellenőrzött robusztussággal // Mesterséges intelligens rendszerek és intelligens CAD. Az IEEE AIS "04 és CAD-2004. - Fizmatlit, 2004. - V. 2. , 2. szám - S. 303-309 . nemzetközi konferencia anyaga .
↑ Timur M. Hanipov. Bizonyos diszkrét Radon transzformációs közelítések számítási bonyolultsági alsó határai . — 2018-01-03. Az eredetiből archiválva : 2020. július 15.
↑ 1 2 S. M. Karpenko, E. I. Ershov. Fast Hough Transzformációs és közelítési tulajdonságai diadikus minták . — 2017-12-15. Archiválva : 2019. május 9.
↑ E. I. Ershov, A. P. Terekhin, D. P. Nikolaev. A gyors Hough-transzformáció általánosítása háromdimenziós képekhez // Journal of Communication Technology and Electronics. — 2018-06-01. — Vol. 63 , iss. 6 . — P. 626–636 . — ISSN 1555-6557 . - doi : 10.1134/S1064226918060074 .
↑ 1 2 3 4 K.V. Soshin, DP Nikolaev, SA Gladilin, EI Ershov. Acceleration of Summation Over Segments Using the Fast Hough Transformation Pyramid // South Ural State University Matematikai modellezés, programozás és számítógépes szoftver : Alevtina V. Keller, Natalia A. Manakova, Georgy A. Svirdyuk, Vladimir I. Zalyapin, Alena A. Zamyshlyaeva. - Cseljabinszk: Dél-Urali Állami Egyetem, 2020. - 13. évf. , no. 1 . - S. 129-140 . - doi : 10.14529/mmp200110 .
↑ OpenCV: opencv2/ximgproc/fast_hough_transform.hpp Fájlreferencia . docs.opencv.org. Letöltve: 2019. május 9. Az eredetiből archiválva : 2019. május 9. (határozatlan)
↑ Alekszandr Krotov. OpenCV Fast Hough Transform példa . — 2017-09-05. Archiválva az eredetiből 2021. július 9-én.
↑ Bulatov KB, Chukalina MV, Nikolaev DP Gyors röntgenösszeg számítási algoritmus számítógépes tomográfiához (angol) // SUSU MMP Bulletin. - 2020. - T. 13 , sz. 1 . - S. 95-106 . - doi : 10.14529/mmp200107 .
↑ E.I. Ershov. A Fast Hough Transform, mint eszköz a 2D és 3D képek elemzéséhez a vonalkeresésben és a lineáris klaszterezési problémákban . — 2018. (Orosz)
↑ A.E. Cowart, W.E. Snyder, W.H. Ruedger. A feloldatlan célok észlelése a Hough-transzformációval // Computer Vision, Graphics and Image Processing. - 1983. - T. 21 , sz. 2 . - S. 222-238 . (Orosz)
↑ A. Mitiche, P. Bouthemy. A képmozgás számítása és elemzése: A jelenlegi problémák és módszerek összefoglalója (angol) // International Journal of Computer vision. - 1996. - 1. évf. 19 , iss. 1 . - P. 29-55 .
↑ E. Lutton, H. Maitre, J. Lopez-Krahe. Hozzájárulás az eltűnési pontok meghatározásához Hough-transzformációval // IEEE-tranzakciókkal a mintaelemzés és a gépi intelligencia terén. - 1994. - 1. évf. 16 , iss. 4 . - P. 430-438 .
↑ D. Nikolaev et al. Hough transform: underestimated tool in the computer vision field // Proceedings of the 22th European Conference on Modeling and Simulation. - 2008. - P. 238-246 .
↑ V. Prun et al. Hatékony szabályosított algebrai rekonstrukciós technika a számítógépes tomográfiához // Crystallography Reports. - 2013. - Kt. 58 , iss. 7 . - P. 1063-1066 .
↑ Z.-H. Cho, JP Jones, M. Singh. Az orvosi képalkotás alapjai . - Wiley New York, 1993. (Orosz)
↑ IA Kunina, SA Gladilin, DP Nikolaev. A radiális torzítás vak kompenzációja egyetlen képen gyors Hough-transzformációval // Számítógép-optika. - 2016. - Kt. 40 , iss. 3 . - P. 395-403 .
↑ A. Mozgovoj. Hough-transzformáció az automatikus kézírás-felismerési problémákban . - 2012. - Kiadás. 9 . - S. 62-64 . (Orosz)
↑ E. Limonova, P. Bezmaternyk, D. Nikolaev, V. Arlazarov. Slant Rectiﬁction in Russian Passport OCR System Using Fast HoughTransform (angol) // 9th International Conference on Machine Vision, ICMV 2016. - SPIE, 2017. - P. 103410P . - doi : 10.1117/12.2268725 .
↑ V. A. Fursov, S. A. Bibikov, P. Yu. Jakimov. Objektumkontúrok lokalizálása képeken léptékváltozatokkal a Hough-transzformáció segítségével // Computer Optics. - 2013. - T. 37 , sz. 4 . (Orosz)
↑ R. Muniz, L. Junco, A. Otero. Robusztus szoftveres vonalkód-olvasó a Hough-transzformációval // International Conference on Information Intelligence and Systems, 1999. Proceedings.. - IEEE, 1999. - P. 313-319 .
↑ A. Rubis et al. Morfológiai összehasonlítás pontminták és kontúrképek formájában a Hough-transzformáció és annak módosításai alapján // Bulletin of Computer and Information Technologies. - 2011. - Kiadás. 7 . - S. 9-16 . (Orosz)
↑ M. Kudrina [et al.] Raszteres képek vektorizálása Hough-transzformációval // Proceedings of the International Symposium "Reliability and Quality". - 2013. - T. 1 . (Orosz)
↑ B. Vandame. Gyors Hough transzformáció a műholdnyomok robusztus észleléséhez // Mining the Sky. - Springer, 2001. - P. 595-597 .
↑ A. Semenov. Radarcélok észlelése a Hough-transzformáció segítségével // Tudomány és oktatás: a Moszkvai Állami Műszaki Egyetem tudományos kiadása. NE Bauman. - 2014. - Kiadás. 12 . (Orosz)
↑ B. Carlson, E. Evans, S. Wilson. Keresés radarérzékelésben és nyomon követésben a Hough transzformációval. III. Észlelési teljesítmény bináris integrációval (angol) // IEEE-tranzakciók repülési és elektronikus rendszereken. - 1994. - 1. évf. 30 , iss. 1 . - 116-125 . o .
↑ A. Dolgy, A. Khatlamadzhiyan. Hibrid modell az alakváltozások értelmezésére ballasztprizmában és a fő aljzatterületen a cél Hough-transzformáció és a Kohonen neurális hálózat alapján // Bulletin of the Southern Federal University. Műszaki tudomány. - 2007. - T. 77 , sz. 2 . (Orosz)
↑ A. Dudkin, D. Vershok, A. Szelikhanovics. Kontúrok elkülönítése integrált áramkörök topológiai rétegeinek szürkeárnyalatos képén // Mesterséges intelligencia. - 2004. - Kiadás. 3 . - S. 453-458 . (Orosz)
↑ A. Grigorjev, T. Hanipov, D. Nyikolajev. Egy jármű tengelyszámának meghatározása az átjáró videósorozatából // A Moszkvai Fizikai és Technológiai Intézet 54. tudományos konferenciája. - 2011. - T. 10 . - S. 31 . (Orosz)
↑ V. Gaganov, A. Ignatenko, M. Lomonoszov. Átlátszó ásványok lapos felületeinek háromdimenziós rekonstrukciója mikroszkópos képkészletből // A Graphon konferencia anyaga. - 2008. - S. 227-233 . (Orosz)
↑ J. Skinley, A. Rye. A SAR-képekre alkalmazott Hough-transzformáció vékony vonalérzékeléshez // Mintafelismerő levelek. - 1987. - 1. évf. 6 , iss. 1 . — P. 61–67 .