Transformare Hough rapidă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 septembrie 2022; verificările necesită 13 modificări .

Fast Hough Transform ( Fast Hough Transform , prescurtare FHT) este o modificare a transformării Hough care vă permite să identificați parametric linii (precum și, cu modificări suplimentare , segmente și patrulatere ) cu o complexitate de calcul mai mică datorită utilizării faptului de autointersectare a liniilor discrete considerate.

Istorie

Algoritmul a fost propus pentru prima dată de M. L. Brady în 1992, [1] a fost ulterior reinventat de mai multe ori de diverși autori. [2] [3]

Definiție

Să fie dată o imagine de dimensiune . Luați în considerare linii diadice (linii drepte de un tip special) constând din pixeli din imagine fiecare (un pixel pe coloană). $m\ori n$ $m^{2}$ $n$

Fie intensitatea celui de-al treilea pixel aparținând dreptei diadice dată de parametrii ; — Jumătatea imaginii acestei linii diadice. $I^{(s,t)}(i)$ $i$ $s,t$ ${\displaystyle S^{(s,t)))$

Imaginea transformării discrete Hough este definită prin următoarea formulă:

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

Calculul direct al tuturor valorilor necesită operații: enumerarea peste diferite valori ale parametrilor , , enumerarea pentru fiecare pereche de valori . ${\displaystyle S^{(s,t)))$ $O$ $\stanga(m^{2}n\dreapta)$ $m$ $s$ $t$ $n$ $i$

La rândul său, algoritmul FHT, bazat pe luarea în considerare a intersecțiilor segmentelor între ele, necesită acțiuni, operațiunile sunt necesare pentru o linie dreaptă (pentru imagini pătrate ). Conform teoremei formulate de T. M. Khanipov [4] , este imposibil să se adauge linii diadice cu complexitate computațională asimptotic mai mică. $\Theta$ $\stanga(mn\log m\dreapta)$ $\Theta$ $\left({\frac {n\log m}{m}}\right)$ $\Theta$ $\stanga(\log n\dreapta)$

Algoritm

Algoritmul se bazează pe principiul „ împărțiți și cuceriți ”. Problema este de a găsi sumele valorilor pixelilor de-a lungul segmentelor care conectează marginile „stânga” și „dreapta” ale imaginii. Imaginea este împărțită în jumătate, în fiecare parte problema este rezolvată independent. Pentru a obține suma finală pe fiecare dintre segmente, se adaugă răspunsurile din jumătățile „stânga” și „dreapta” ale acestuia.

În algoritmul FHT, pixelii liniilor arbitrare sunt aproximați discret prin linii diadice. Pixelii aproximării diadice a unei linii drepte din imaginea de dimensiune sunt eliminați din linia dreaptă inițială cu cel mult pixeli. [5] $n\ ori n$ $O$ $(\log n)$

Segmentele sunt parametrizate de centrele pixelilor conectați. Prin urmare, împărțirea unui segment în subsegmente alcătuiește doar aproximativ segmentul inițial. Eroarea de aproximare cu pași de recursivitate este cumulativă, dar nu mai mult de pixeli. [5] Discretizarea segmentului la pixeli astfel construiti se numeste aproximare diadica . $O$ $(\log n)$

Modele diadice generative

Mai mult , un model este un set de pixeli care conțin un element în fiecare verticală a imaginii. Abaterea modelului va fi valoarea , iar coordonata va fi valoarea . O schimbare de model va fi numită set ${\displaystyle p=\{(x_{i},i)\}_{i=0}^{2^{k}-1))$ $t(p)=x_{2^{k}-1}-x_{0)$ $s(p)=x_{0)$

p ↗ ( A , b ) = { ( X i + A , y i + b ) | ( X i , y i ) ∈ p } {\displaystyle p\narrow (a,b)=\lbrace \left(x_{i}+a,y_{i}+b\right)\ |\(x_{i},y_{i})\in p \rbrace }

p\narrow (a,b)=\lbrace \left(x_{i}+a,y_{i}+b\right)\ |\(x_{i},y_{i})\in p \rbrace

Modelele diadice generative de lățime și pantă sunt definite recursiv. Pentru , modelul este format dintr-un pixel, iar pentru , este exprimat în termeni de .

2^k

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}\ \ \ \ \narrow (t/2,2^{k})&,k>0,\ \ t\equiv 0\ (mod2)\\ P_{(t-1)/2}^{k-1}\cup \ P_{(t-1)/2}^{k-1}\narrow ((t+1)/2,2^{k })&,k>0,\ \t\equiv 1\ (mod2)\end{cases}}$

Linii diadice

Liniile diadice, predominant orizontale, în sus, sunt obținute din toate modelele generative deplasate vertical , construite cu toate coordonatele posibile din imagine . $P_{s,t}^{k}=P_{t}^{k}\îngust (s,0)$ $s\in \{0,...,2^{k}-1\},t\in \{0,...,2^{k}-1\)$

Pentru un calcul aproximativ al transformării Hough, este necesar să se găsească sumele peste toate liniile diadice din imagine. În această sumă de linii, există puncte fiecare. Datorită tranziției recursive, această însumare se reduce la numărarea separată a jumătăților stângi, separat a jumătăților drepte, ceea ce ne permite să reducem calculul la calculul sumelor peste puncte fiecare. $S_{s,t}=\sum _{(x,y)\in P_{s,t}^{k}}I_{x,y}$ $2^{k}\cdot 2^{k)$ $2^k$ $2\cdot 2^{k}\cdot 2^{k-1}$ $2^{k-1}$

Luați în considerare cuvintele binare formate din numerele 0 și 1. Mulțimea cuvintelor diadice este definită recursiv. va fi numit cuvânt diadic dacă are forma sau , unde este un cuvânt gol sau diadic. Toate cuvintele diadice cu lungimea nu mai mare de trei: 0, 1, 000, 010, 101, 111. $w$ $w$ $a0a$ $a1a$ $A$

Pentru fiecare cuvânt diadic se consideră suma cumulativă . Vom spune că succesiunea de pixeli este o linie dreaptă diadică care leagă centrele pixelilor și . ${\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)$

Există exact linii diadice de lungime . Unul pentru fiecare pereche de și . $2^k$ $2^k$ $(0,0)$ ${\displaystyle (h,2^{k}-1),0\leqslant h<2^{k))$

Descriere formală

Algoritmul FHT este structurat după cum urmează: [6]

Starea inițială a matricei este imaginea originală a dimensiunii . Apoi, calculul are loc la rândul său la --lea nivel, pornind de la primul: la --lea nivel, matricea în starea curentă este împărțită în grupuri conform principiului egalității părții întregi a coordonatei celei de-a doua axe. după împărțire prin ; se obțin submatrice ; uniți-le pe cele adiacente în perechi (fără intersecții, acest lucru este posibil, deoarece dimensiunea matricei este o putere de două) și în această pereche numim prima submatrice care este situată pe coordonate mai mici de-a lungul celei de-a doua coordonate din matrice , iar celălalt - al doilea; în loc de primul din fiecare pereche, suma sa este scrisă cu secunda corespunzătoare, iar în loc de a doua - suma primei și secunde cu o deplasare ciclică cu unu la stânga. Astfel, imaginea Hough a unor astfel de linii este considerată astfel încât pentru orice pereche de puncte cu coordonate din această dreaptă, , este satisfăcută folosind aproximarea prin linii diadice. Pentru a calcula imaginea pentru restul liniilor, este suficient să rotiți imaginea și să efectuați aceeași operație și să adăugați rezultatele. $2^{p}\times 2^{q)$ $q-1$ $i$ $2^i$ $2^{p}\times 2^{i)$ $(x_{1},y_{1}),(x_{2},y_{2})$ $(x_{1}\neq x_{2})\rightarrow ((y_{1}\neq y_{2})\wedge (x_{1}<x_{2}\Leftrightarrow y_{1}<y_ {2}))$

Matricele astfel obtinute la fiecare nivel sunt elemente ale piramidei FHT. Descrierea formală a piramidei FHT : Nivelul zero al piramidei FHT este imaginea originală (de dimensiune , iar ultima este imaginea Hough care conține sume de-a lungul liniilor drepte diadice de lungime . Pentru a descrie al treilea nivel al piramidei , imaginea originală este împărțită în dungi orizontale , unde este numărul dungii, . Pentru fiecare dungă, al treilea nivel al piramidei FHT stochează sume peste toate modelele de dungi posibile cu lungime și parametri .Numărul de astfel de modele pentru o dungă este , deci al treilea nivel al piramidei ocupă la fel de multă memorie ca imaginea originală. $m\ori n$ $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$ $2^{q)$ $s\in [0,n-1],t\in [0,2^{q}-1]$ $n\cdot 2^{q)$ $q$

Invarianța cantității de memorie cheltuită și capacitatea de a stoca fiecare nivel într-o matrice de aceeași dimensiune ca imaginea originală, fără pierderea interpretabilității, dă următoarea proprietate: este posibilă stocarea piramidei FHT sub forma unei matrice cu o dimensiune cu una mai mare decât dimensiunea imaginii originale (de-a lungul unei axe - numărul de niveluri, ), pentru restul - dimensiunea imaginii). [7] $\log _{2}n$

Implementări software

Un exemplu de implementare în python:

import numpy ca np W = 2 ** 5 H = 2 ** 5 img = np . aleatoriu . aleatoriu ([ H , W ]) def calc_sums ( img , xmin , xmax ): res = np . zerouri ([ W , xmax - xmin ]) dacă xmax - xmin == 1 : res [:, 0 ] = img [:, xmin ] else : mid = ( xmin + xmax ) // 2 ans1 = calc_sums ( img , xmin ) , mid ) ans2 = calc_sums ( img , mid , xmax ) for x in range ( W ): for shift in range ( 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 )

Algoritmul este implementat în biblioteca opencv [8] și poate fi folosit, de exemplu, pentru a găsi rapid punctul de fugă . [9]

Generalizări la cazul tridimensional

FHT pentru avioane

Rezolvarea acestei probleme presupune utilizarea unui algoritm pentru cazul bidimensional.

Imaginea haf a planurilor va fi, de asemenea, tridimensională (planul este specificat prin trei coordonate ale vectorului perpendicular pe acesta). Fie dat de parametrizare , unde este coordonata intersecției planului cu limita imaginii pe rază , este coordonata punctului de intersecție cu limita imaginii paralelă cu raza din plan și este diferența dintre coordonatele celui de-al doilea și primul punct de intersecție a planului cu limitele imaginii. Primul punct se află la intersecția planurilor care conțin limita imaginii și planul paralel cu . Al doilea punct se află la intersecția planurilor care conțin limita imaginii, paralel cu și . $s,t,t_{2}$ $s$ $X$ $Bou$ $s+t$ $X$ $Bou$ $xOz$ $t_{2}$ $X$ $xOz$ $xOy$ $xOy$ $xOz$

Vom numi un plan predominant perpendicular pe axa de coordonate dacă normala la acesta formează un unghi mai mic cu această axă decât cu celelalte două. Vom lua în considerare doar planele care sunt predominant perpendiculare pe axa y. Acestea sunt împărțite în 4 tipuri de pante, așa cum se arată în Figura 4. Fără pierderea generalității, vom presupune că planurile considerate sunt de tip I.

Construirea unei imagini Hough după enumerarea plană are complexitate asimptotică (numărul de planuri înmulțit cu numărul de operații pentru a însuma un plan), unde m, n, k sunt dimensiunile imaginii din fiecare dimensiune. $O$ $\stanga(mnk\cdot (mn+nk+mk)\dreapta)$

Transformarea Hough rapidă în acest caz va fi următorul algoritm:

Pentru fiecare plan perpendicular pe axa cu o coordonată de-a lungul acestei axe, se calculează transformarea Hough rapidă, iar rezultatul este plasat în spațiu tridimensional de-a lungul coordonatelor . $Oz$ $z$ $s,t,z$
Pentru fiecare plan din spațiul tridimensional rezultat perpendicular pe axa cu o coordonată de-a lungul acestei axe, se calculează transformarea Hough rapidă, iar rezultatul este plasat într-un cub de-a lungul coordonatelor . $De la$ $t$ $s,t,t_{2}$

Complexitatea unei astfel de transformări este suma complexității primului pas ( ) și a complexității celui de-al doilea pas ( ), care sunt calculate ca produsul dintre numărul de planuri considerate și numărul de operații pe plan. Total, , în termeni de un avion . $\Theta$ $\stanga(k\cdot mn\log m\dreapta)$ $\Theta$ $\stanga(n\cdot mk\log m\dreapta)$ $\Theta$ $\stanga(mnk\log m\dreapta)$ $\Theta$ $(\log m)$

FHT pentru linii 3D

Imaginea haf a unei linii tridimensionale va fi de patru dimensiuni (doi parametri pentru fiecare dintre cele două puncte de pe linie). Fie dat prin parametrizare . sunt coordonatele x, y ale punctului din plan , sunt coordonatele x, y ale punctului de intersecție al dreptei cu limita imaginii paralelă cu planul . $s,t,s_{2},t_{2)$ $s,s_{2)$ $xOy$ $s+t,s_{2}+t_{2)$ $xOy$

Construcția imaginii-Hough prin enumerarea liniilor tridimensionale are complexitate asimptotică (numărul de linii înmulțit cu numărul de operații pentru însumarea unei linii), unde m, n, k sunt dimensiunile imaginii în fiecare dimensiune. $O$ $\left((mn)^{2}\cdot k\right)$

Transformarea Hough rapidă pentru un astfel de caz este formulată în mod similar cu definiția pentru cazul bidimensional. În cazul bidimensional, posibilitatea deplasării a fost doar de-a lungul unei axe, dar acum deplasarea va fi de-a lungul unei axe, de-a lungul celei de-a doua axe și de-a lungul a două axe în același timp.

Numărarea modelelor de lungime doi necesită (numărul de grupuri de planuri însumabile) înmulțit cu (complexitatea adunărilor pentru fiecare grup) operații. Numărarea modelelor de lungime 4 necesită operații. Lungimile modelului — , unde este definită ca , adică numărul lungimii modelului considerat. Însumând termenii (numărul de lungimi de model posibil pentru imaginea luată în considerare) folosind formula pentru suma unei progresii geometrice, obținem complexitatea algoritmului și complexitatea într-o linie dreaptă . Pentru , complexitatea va fi constantă. ${\frac {k}{2)}$ $4mn$ ${\frac {k}{4}}\cdot 16mn$ $d$ ${\frac {k}{d}}\cdot d^{2}mn=mnkd=mnk\cdot 2^{i}$ $i$ $\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}}\dreapta)\equiv$ $\Theta$ $\left(mnk^{2}\right)$ $\Theta$ $\left({\frac {k^{2}}{mn}}\right)$ $m=n=k$

Combinația dintre BPH și principiul a patru ruși

În ciuda faptului că numărul de operații pe o linie este constant pentru aceeași dimensiune a imaginii în fiecare dimensiune, pentru toate liniile este necesar să se cheltuiască . Dar dacă nu sunt necesare toate liniile, ci este nevoie doar de o parte din ele, atunci se pot precalcula primii pași [10] , îi pot stoca în memorie și apoi se calculează sumele numai pentru acele linii care sunt necesare. $n^{4)$ $X$

Acest concept a fost consacrat în metoda a patru ruși. Metoda este numită după descoperitorii V. Arlazarov , M. Kronrod, E. Dinits, I. Faradzhev.

În algoritmul original FHT pentru linii tridimensionale, se efectuează un calcul la fiecare nivel pentru linii de o anumită lungime. Pe de altă parte, puteți face un precalcul numai pentru primii pași, apoi puteți calcula pentru liniile necesare. $\log _{2}k$ $X$

Pentru a determina numărul optim de pași de precalcul, este necesar să se rezolve următoarea ecuație ( este numărul de linii pe care algoritmul trebuie să le găsească): $A$

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

În stânga este numărul de operații pentru a efectua precalculul. În dreapta este numărul de operații pentru a găsi sume de-a lungul liniilor solicitate. Fie necesar să se găsească toate liniile, apoi , atunci soluția ecuației va fi , iar laturile stângă și dreaptă sunt egale , ceea ce este mai mic decât fără precalcular. Cu toate acestea, pentru reducerea numărului de operații, este necesar să se plătească cu memorie în aceeași cantitate pe care o ocupă imaginea Hough (proprietatea de invarianță a memoriei ocupate la fiecare nivel de numărare prin algoritmul FHT). $a=mnk$ $x={\frac {1}{2}}\log _{2}k=\log _{2}{\sqrt {k}}$ $\Theta \left(mnk {\sqrt {k}}\right)$ ${\sqrt {k)}$

Calcularea sumei unui segment dintr-o imagine

Principiul de calcul se bazează pe utilizarea valorilor nu numai ale ultimului nivel al piramidei FHT (adică imaginea Hough în sine), ci și ale altor niveluri ale piramidei FHT.

Sarcina este împărțită în două subsarcini:

Găsiți o linie diadică care trece prin doi pixeli dați
Din suma valorilor de-a lungul acestei linii drepte, selectați partea sumei care se referă la modelul dintre pixelii dați

Găsirea unei linii diadice care trece prin doi pixeli dați

Presupunem fără pierderi de generalitate că . Aici vom lua în considerare doar modele predominant verticale cu o înclinare spre dreapta, adică și . Se folosește și parametrizarea și valoarea este egală cu , unde este dimensiunea imaginii de-a lungul axei . $y_{2}\geq y_{1)$ $x_{2}\geq x_{1}$ $y_{2}-y_{1}\geq x_{2}-x_{1}$ $(s,t)$ $p$ $\log _{2}n$ $n$ $y$

Lăsați expansiunea binară a parametrului liniei drepte diadice să arate ca Apoi modelul poate fi scris după cum urmează ( - rotunjirea la cel mai apropiat număr întreg.): $t$ $t=\sum _{i=0}^{p-1}t_{i}2^{i)$ $\stânga[\cdot \right]$

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

$\Delta x=x_{2}-x_{1)$ calculate din datele sarcinii. este numărul de deplasări ale modelului considerat în banda , care este de asemenea cunoscută. Astfel, este necesar doar să restaurați biții . $\delta _{r}^{y_{1},y_{2}}=\left(D_{r}(y_{2})-D_{r}(y_{1})\right)$ $(y_{1},y_{2})$ $t_{0},t_{1},\ldots,t_{p-1)$

Pentru recuperare este folosit un algoritm lacom: toți biții sunt mai întâi zero. Din moment ce , prin urmare, enumerarea se realizează de la un număr mai mare de deplasări la unul mai mic, de la nivel la nivelul 0. Dacă , atunci bitul corespunzător acestui nivel este setat la 1 și scade cu . Pasul se repetă până când ajunge la 0. $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$

Valoarea parametrului se calculează prin . Prin acest parametru, parametrul se calculează după următoarea formulă: $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$ , deci complexitatea algoritmului . [7] $\Theta$ $(\log n)$

Găsirea unei sume de-a lungul unui segment pe o linie diadică cunoscută

Metoda 1

Referindu-ne la figură, se poate observa că un segment arbitrar pe o linie dreaptă se calculează prin găsirea numărului minim de modele diadice care conțin părți de la începutul liniei până la sfârșitul segmentului dat, inclusiv, și numărul minim de modele care conțin segmentul de la începutul liniei drepte până la începutul segmentului dat, excluzând primul pixel al segmentului original. Adică, trebuie să găsiți sumele pentru două segmente cu începutul la marginea imaginii și coordonate diferite de sfârșit. $n$

Pentru a calcula suma peste acest tip de segment de lungime (expansiunea sa binară ) , unde este suma peste modelul din banda --lea a --lea nivel al FHT=piramidă pentru o linie dreaptă cu parametri . $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}\dreapta)\dreapta]$ $H^{s,t}\stanga(q,k\dreapta)$ $2^{q)$ $k$ $q$ $(s,t)$

Suma interioară nu necesită un calcul complet la fiecare pas, deoarece se obține din precedentul în timp constant. Astfel, complexitatea algoritmului este proporțională cu numărul de termeni din suma externă, adică este . Deoarece rezultatul este calculat pentru două segmente de acest tip, complexitatea rezultată a algoritmului este de asemenea . Mai mult, este de remarcat faptul că un pixel poate fi multicanal. [7] $\Theta$ $(\log n)$ $\Theta$ $(\log n)$

Metoda 2

Segmentul poate fi compus din numărul minim de modele din cadrul segmentului. Pentru a căuta astfel de modele, trebuie să te uiți la nivelurile piramidei FHT, începând cu ultimele și terminând cu primele. Puteți filtra imediat acele modele care nu sunt incluse în segment. Dacă se găsește un model care se află complet în interiorul segmentului, atunci suma acestuia este inclusă în suma necesară, iar diviziunile sale la nivelurile următoare nu sunt luate în considerare. Această metodă este mai complexă din punct de vedere computațional decât prima, deoarece necesită enumerarea tuturor tiparelor care sunt mai mari de . $n$

Calcularea sumei peste un patrulater dintr-o imagine

Similar cu calculul sumei peste un segment pentru calcularea sumei peste un patrulater din calculele intermediare ale imaginii Hough pentru avioane, cu alte cuvinte, piramida FHT pentru cazul avioanelor.

Presupunând că sunt cunoscuți parametrii planului pe care se află patrulaterul dat, suma dorită se calculează prin formula de includere-excludere luând suma peste patru dreptunghiuri, dintre care un vârf este vârful colțului planului diadic (noi notează-l cu litera , iar segmentele cu acest vârf prin segmentele de colț ). Să notăm coordonatele punctelor cele mai apropiate și cele mai îndepărtate de vârfurile patrulaterului dat prin și respectiv. Sumele segmentelor de colț marcate cu vârfuri la și sunt luate cu semnul plus, iar sumele celor cu vârfuri la și sunt luate cu semnul minus. $(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)$

Pentru a găsi suma peste un segment unghiular arbitrar, este necesar să o împărțiți în segmente care sunt prezente în piramida FHT. Este necesar să se ia în considerare expansiunile binare ale lățimii și înălțimii segmentului. Similar cu cazul unidimensional, segmentul este împărțit orizontal în dungi verticale și vertical în nu mai mult decât dungi orizontale. Intersecția lor nu va da mai mult decât segmentele prezente într-o piramidă FPH tridimensională. Astfel, complexitatea calculării sumei pe un segment arbitrar echivalează cu operații. [7] $\log _{2}n$ $\log _{2}n$ $\log _{2}n$ $\Theta$ $(\log n)$

Aplicații ale algoritmului FHT

Deși există o anumită eroare în aproximarea unei linii drepte printr-un model diadic, totuși, experimentele arată că această eroare este suficient de mică încât în rezolvarea problemelor este posibil să se înlocuiască algoritmul tradițional de transformare Hough cu algoritmul FHT. [unsprezece]

Soluție robustă a unei probleme de regresie liniară prin calculul estimărilor M folosind FHT

Aplicând M-estimări problemei de regresie liniară , se pot obține funcții de bază radială . Ele formează o imagine „continuă”, care, la rândul ei, este eșantionată într-o histogramă 2D.

În continuare, convoluția imaginii este efectuată cu un nucleu discretizat corespunzător estimatorului M selectat. Pe baza imaginii primite Hough este calculată folosind FHT. Coordonata maximului în spațiul parametrilor - și va fi M-estimarea dorită. $K$

Grupare binară liniară rapidă

Sarcina este formulată astfel: este necesar să se găsească un hiperplan care să împartă imaginea în 2 clase. Imaginea este reprezentată ca o histogramă de imagine normalizată . $P$

$L$ este hiperplanul dorit care împarte imaginile în două clase , este clasa tuturor elementelor histogramei. $A_{L}, B_{L}$ $\Omega$

Statistici aditive utilizate ( --a coordonată ): $X\subset \Omega$ $x_{i}$ $i$ $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)$

Există o serie de funcționale potrivite pentru problemele de separare a clusterelor cu diferite proprietăți cunoscute a priori și, în același timp, calculabile în termeni de statistici aditive. Merită menționat încă o dată că aceste funcționale nu sunt în general convexe și singura modalitate sigură de a le găsi valoarea optimă este enumerarea exhaustivă pe grilă în spațiul parametrilor suprafețelor de separare.

Algoritm naiv: Există linii discrete care intersectează histograma cu dimensiune liniară . Pentru fiecare dintre ele este necesar să se efectueze operații de calcul a ponderilor, matricelor de covarianță și, în final, a valorilor criteriului. Astfel, complexitatea computațională a algoritmului naiv este operațiile. În mod similar, se poate demonstra că pentru cazul tridimensional, complexitatea de calcul a algoritmului va fi . $O(n^{2})$ $n$ $O(n^{2})$ $O(n^{4})$ $O(n^{6})$

În această etapă, se aplică suma cumulativă: suma elementelor corespunzătoare ale tuturor straturilor imaginii de intrare cu un indice care nu depășește este scrisă în elementul strat cu numărul imaginii de ieșire . $i$ $i$

Suma valorilor pixelilor pentru orice linie a imaginii de ieșire este egală cu suma pentru acea parte a imaginii originale care nu se află sub această linie. În plus, suma de-a lungul oricărei linii drepte predominant orizontale din imaginea de ieșire este egală cu suma de-a lungul semiplanului superior delimitat de aceasta în imaginea originală. Pentru o exprimare similară a sumelor peste semiplanurile stângi prin linii drepte predominant verticale, în locul celei verticale, este necesară efectuarea sumei cumulate orizontale a imaginii.

Algoritm:

calculați un set de imagini care conțin valorile statisticilor aditive necesare pentru fiecare element al histogramei de intrare ( ) (6 în cazul bidimensional, 10 în cazul tridimensional) $D^{0},D_{i}^{1},D_{ij}^{2}$
calculând suma cumulativă de-a lungul fiecărei axe, obținem un tuplu de imagini. Pentru orice imagine a acestui tuplu legată de dimensiunea , suma peste orice hiperplan, predominant perpendicular pe axa cu indice , este egală cu statistica aditivă corespunzătoare calculată pe semi-spațiu, inclusiv originea și mărginită de hiperplanul ales. Cunoscând valoarea statisticii aditive pentru o jumătate de spațiu, este ușor să obțineți valoarea aceleiași statistici pentru al doilea scăzând din statistica calculată pe întreaga imagine. $d$ $d$
Acum, după ce am calculat statisticile aditive pentru toate separările hiperplanurilor, putem calcula valorile criteriului de alegere a grupării optime.

Dacă pur și simplu însumăm toate hiperplanurile, atunci în cazul bidimensional complexitatea este , în cazul tridimensional . (In -dimensional ) $O(mn^{3})$ $O(mn^{5})$ $k$ $O(mn^{2k-1})$

Însumarea peste hiperplanuri (linii drepte în 2D, planuri în 3D...) se poate face folosind FHT. Acest lucru ajută la reducerea complexității de la la pentru fiecare dintre imagini. Adică acum complexitatea este în cazul bidimensional , în cel tridimensional . $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)})$

Deci algoritmul final este:

Însumarea cumulativă
Numărarea statisticilor aditive
HBP
Găsirea maximului în spațiul Hough

Complexitate: timp , memorie . $O(mn^{k}\log {\left(n\right)})$ $O(mn^{k})$

În cazul bidimensional, mai detaliat:

Însumarea cumulativă: $O(n^{2})$
Pregătirea pentru calcularea statisticilor aditive: $O(n^{2})$
HBP: $O\left(n^{2}\log {\left(n\right)}\right)$
Găsirea maximului în spațiul Hough: $O(n^{2})$

Dificultatea finală: $O(n^{2}\log {\left(n\right)})$

În cazul 3D mai detaliat:

Însumarea cumulativă: $O(n^{3})$
Pregătirea pentru calcularea statisticilor aditive: $O(n^{3})$
HBP: $O\left(n^{3}\log {\left(n\right)}\right)$
Găsirea maximului în spațiul Hough: $O(n^{3})$

Dificultatea finală: $O(n^{3}\log {\left(n\right)})$

Alte utilizări

Următoarele sunt doar câteva dintre problemele care pot fi rezolvate folosind transformarea Hough.

Urmărirea obiectelor în mișcare uniformă folosind diferența de imagine cadru cu cadru. Aceste obiecte lasă linii drepte pronunțate pe urme. [12] [13]
Detectarea punctului de fuga într-o imagine. Un punct de fugă este un punct din planul imaginii în care proiecțiile liniilor paralele dintr-o scenă 3D se intersectează. [14] [15]
restaurare tomografică. Procedura de formare a proiecțiilor imaginii obiectului analizat cu ajutorul razelor X este de obicei modelată prin transformările Hough și Radon, iar obținerea structurii tridimensionale a obiectului studiat se reduce adesea la rezolvarea transformării inverse Hough sau Radon. [16]
Analiza imaginilor medicale. [17]
În implementarea algoritmilor de calibrare oarbă a distorsiunii radiale, cu condiția ca pe scenă să se găsească obiecte rectilinii. Prin optimizarea noii funcționalități a imaginii Hough sunt selectați parametrii de compensare a distorsiunii radiale. [optsprezece]
Determinarea gradului de deprimare a camerei. Pe baza calculului FHT din modelul epipolar și căutarea unei linii drepte pe care punctele liniilor de interes se află în modelul epipolar.
Scris de mana recunoscut. [19]
Determinarea înclinării fontului. Pe baza faptului că fontul are caractere formate din segmente drepte situate la un unghi, de-a lungul unui astfel de unghi imaginea haf va avea o valoare mai mare. [douăzeci]
Recunoașterea codurilor de bare. [21] [22]
Determinarea gradului de asemănare a formelor. [23]
Vectorizarea imaginilor tridimensionale. [24]
Detectarea pistelor de satelit din imagini cu expunere lungă. [25]
Detectarea țintelor radar. [26] [27]
Analiza deformarii profilului subteran. [28]
Analiza structurii topologiei microcircuitelor din fotografii. [29]
Numărarea numărului de osii ale vehiculului de pe urmele detectorului de roți ale imaginilor luate de la o cameră luată din lateral. [treizeci]
Reconstituirea 3D a fețelor plate de minerale transparente dintr-un set de imagini. [31]
Analiza imaginilor SAR. [32]

Note

↑ Martin L. Brady, Whanki Yong. Algoritmi de aproximare discretă paralelă rapidă pentru transformarea radonului // Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures. - New York, NY, SUA: ACM, 1992. - S. 91-99 . — ISBN 9780897914833 . - doi : 10.1145/140901.140911 .
↑ JE Vuillemin. Transformare Hough liniară rapidă // Conferință internațională privind sistemele, arhitecturi și procesoare specifice aplicației, lucrări. - 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. Postnikov. Transformare Hough rapidă cu robustețe controlată // Sisteme inteligente artificiale și CAD inteligent. Proceedings of the international Conference IEEE AIS "04 and CAD-2004. - Fizmatlit, 2004. - V. 2 , issue 2. - S. 303-309 .
↑ Timur M. Khanipov. Limitele inferioare ale complexității computaționale ale anumitor aproximări discrete ale transformării radonului . — 03-01-2018. Arhivat din original pe 15 iulie 2020.
↑ 1 2 S. M. Karpenko, E. I. Ershov. Transformarea Hough rapidă și proprietățile de aproximare ale modelelor diadice . — 15-12-2017. Arhivat 9 mai 2019.
↑ E.I. Ershov, A.P. Terekhin, D.P. Nikolaev. Generalizarea transformării rapide Hough pentru imagini tridimensionale // Journal of Communications 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. Accelerarea însumării peste segmente utilizând piramida de transformare rapidă Hough // South Ural State University Modelare matematică, programare și software de calculator : Alevtina V. Keller, Natalia A. Manakova, Georgy A. Svirdyuk, Vladimir I. Zalyapin, Alena A. Zamyshlyaeva. - Chelyabinsk: Universitatea de Stat Ural de Sud, 2020. - Vol. 13 , nr. 1 . - S. 129-140 . - doi : 10.14529/mmp200110 .
↑ OpenCV: opencv2/ximgproc/fast_hough_transform.hpp File Reference . docs.opencv.org. Preluat la 9 mai 2019. Arhivat din original pe 9 mai 2019. (nedefinit)
↑ Alexander Krotov. Exemplu OpenCV Fast Hough Transform . — 05-09-2017. Arhivat din original pe 9 iulie 2021.
↑ Bulatov KB, Chukalina MV, Nikolaev DP Algoritm rapid de calcul al sumei cu raze X pentru tomografie computerizată (engleză) // SUSU MMP Bulletin. - 2020. - T. 13 , nr. 1 . - S. 95-106 . - doi : 10.14529/mmp200107 .
↑ E.I. Ershov. Transformare rapidă Hough ca instrument pentru analiza imaginilor 2D și 3D în problemele de căutare linie și de grupare liniară . — 2018. (Rusă)
↑ A.E. Cowart, W.E. Snyder, W.H. Ruedger. Detectarea țintelor nerezolvate folosind transformarea Hough // Computer Vision, Graphics, and Image Processing. - 1983. - T. 21 , nr. 2 . - S. 222-238 . (Rusă)
↑ A. Mitiche, P. Bouthemy. Calcularea și analiza mișcării imaginii: un rezumat al problemelor și metodelor actuale (engleză) // Jurnal internațional de viziune pe computer. - 1996. - Vol. 19 , iss. 1 . - P. 29-55 .
↑ E. Lutton, H. Maitre, J. Lopez-Krahe. Contribuție la determinarea punctelor de fugă folosind transformarea Hough // tranzacții IEEE privind analiza modelelor și inteligența mașinii. - 1994. - Vol. 16 , iss. 4 . - P. 430-438 .
↑ D. Nikolaev și colab. Hough transform: instrument subestimat în domeniul vederii computerizate // Proceedings of the 22th European Conference on Modeling and Simulation. - 2008. - P. 238-246 .
↑ V. Prun și colab. Tehnica eficientă de reconstrucție algebrică regularizată pentru tomografia computerizată // Crystallography Reports. - 2013. - Vol. 58 , iss. 7 . - P. 1063-1066 .
↑ Z.-H. Cho, JP Jones, M. Singh. Bazele imagisticii medicale . - Wiley New York, 1993. (Rusă)
↑ IA Kunina, SA Gladilin, DP Nikolaev. Compensare oarbă a distorsiunii radiale într-o singură imagine folosind transformarea Hough rapidă // Computer Optics. - 2016. - Vol. 40 , iss. 3 . - P. 395-403 .
↑ A. Mozgovoi. Hough Transformarea în probleme de recunoaștere automată a scrisului de mână . - 2012. - Emisiune. 9 . - S. 62-64 . (Rusă)
↑ E. Limonova, P. Bezmaternykh, D. Nikolaev, V. Arlazarov. Slant Rectiﬁcation in Russian Passport OCR System Using Fast HoughTransform (engleză) // A 9-a Conferință Internațională privind Viziunea Mașină, ICMV 2016. - SPIE, 2017. - P. 103410P . - doi : 10.1117/12.2268725 .
↑ V. A. Fursov, S. A. Bibikov, P. Yu. Yakimov. Localizarea contururilor obiectelor în imagini cu variații de scară folosind transformarea Hough // Computer Optics. - 2013. - T. 37 , nr. 4 . (Rusă)
↑ R. Muniz, L. Junco, A. Otero. Un cititor software robust de coduri de bare care folosește transformarea Hough // Conferința internațională privind informațiile și sistemele informaționale, 1999. Proceedings.. - IEEE, 1999. - P. 313-319 .
↑ A. Rubis și colab. , Comparație morfologică sub formă de modele de puncte și imagini de contur bazate pe transformarea Hough și modificările acesteia // Bulletin of Computer and Information Technologies. - 2011. - Emisiune. 7 . - S. 9-16 . (Rusă)
↑ M. Kudrina [et al.] Vectorization of raster images using the Hough transform // Proceedings of the International Symposium "Reliability and Quality". - 2013. - T. 1 . (Rusă)
↑ B. Vandame. Transformare Hough rapidă pentru detectarea robustă a pistelor de satelit // Mining the Sky. - Springer, 2001. - P. 595-597 .
↑ A. Semenov. Detectarea țintelor radar folosind transformarea Hough // Știință și educație: ediția științifică a Universității Tehnice de Stat din Moscova. NE Bauman. - 2014. - Emisiune. 12 . (Rusă)
↑ B. Carlson, E. Evans, S. Wilson. Căutați detectarea radarului și urmăriți cu transformarea Hough. III. Performanță de detectare cu integrare binară (engleză) // Tranzacții IEEE pe sisteme aerospațiale și electronice. - 1994. - Vol. 30 , iss. 1 . - P. 116-125 .
↑ A. Dolgy, A. Khatlamadzhiyan. Un model hibrid pentru interpretarea deformațiilor într-o prismă de balast și zona principală a subsolului bazat pe transformarea Hough țintă și rețeaua neuronală Kohonen // Buletinul Universității Federale de Sud. Știința tehnică. - 2007. - T. 77 , nr. 2 . (Rusă)
↑ A. Dudkin, D. Vershok, A. Selikhanovich. Izolarea contururilor pe imagini în tonuri de gri ale straturilor topologice ale circuitelor integrate // Inteligența artificială. - 2004. - Emisiune. 3 . - S. 453-458 . (Rusă)
↑ A. Grigoriev, T. Khanipov, D. Nikolaev. Determinarea numărului de osii ale unui vehicul din secvența video a pasajului // A 54-a Conferință științifică a Institutului de Fizică și Tehnologie din Moscova. - 2011. - T. 10 . - S. 31 . (Rusă)
↑ V. Gaganov, A. Ignatenko, M. Lomonosov. Reconstituirea tridimensională a fețelor plate de minerale transparente dintr-un set de imagini de la un microscop // Proceedings of the Conference Graphon. - 2008. - S. 227-233 . (Rusă)
↑ J. Skinley, A. Rye. Transformarea Hough aplicată imaginilor SAR pentru detectarea liniilor subțiri // Litere de recunoaștere a modelelor. - 1987. - Vol. 6 , iss. 1 . — P. 61–67 .