Aplicatii ale Transformatei Radon In Prelucarea Imaginilor

INTRODUCERE

În lucrarea de față este prezentată transformata Radon cu aplicațiile acesteia în prelucrarea imaginilor. Se utilizată în astronomie, microscopie și tomografie servind la reconstrucția imaginilor. Detectează particularitățile imaginilor. Transformata Radon este o cartare dintr-un domeniu al imaginii într-un domeniu parametric, aceștia din urmă caracterizând particularitățile de identificat. Atribuie o valoare numerică fiecărui membru al unei familii de linii.

Sunt explorate diferite metode de prezentare a detecțiilor de linii ce apar în sistemele ce folosesc transformata Radon. Există diverse moduri prin care poate fi descrisă o transformată Radon; aici sunt prezentate trei tipuri : Transformata Slant Stacking, Transformata Radon normală și Transformata Hough. În practică toate acestea, deși exclud atribute de performanță certe, sunt echivalente în esența lor. Este prezentat modul cum reacționează acești algoritmi în cazul detecției de linii, acesta fiind primul pas în recunoașterea de forme pentru procesarea de imagini. Bineînțeles, există numeroase moduri de percepție a transformatei Radon.

CAPITOLUL I

Transformata Slant Stacking (transformata -p)

Transformata Radon este cunoscută și utilizată în seismologie, sub numele de transformata Slant Stacking. De asemenea sunt prezentate și câteva dintre proprietățile transformatei Radon discrete. Sunt date câteva exemple, cele mai multe privind detectarea liniilor drepte din imaginile digitale.

La ce se folosește transformata Radon

Pentru început este prezentat un mic exemplu numai pentru a arăta că această transformată Radon este potrivită în extragerea parametrului de linie chiar și în prezența zgomotului. Figura 1.1 ilustrează o imagine ce conține trei linii dintre care două sunt apropiate, imaginii adăugându-i-se totodată și un zgomot uniform distribuit. Figura 1.2 prezintă transformata Radon discretă a imaginii, adică figura sugerează spațiul posibililor parametrii ai liniei. Se arăta că transformata Radon poate transforma fiecare linie în vârfuri poziționate corespunzător parametrilor liniilor. În acest fel , transformata Radon convertește o problemă dificilă de detecție globală din domeniul imaginii într-o problemă de detecție a vârfului (maximului) local, ușor rezolvabil în domeniul parametric, iar parametrii actuali pot fi recuperați, de exemplu, aducând la limită transformata Radon.

De remarcat este faptul că, în acest caz, alți algoritmi au dat greș. Ca alternativă ar putea fi folosit un algoritm de detecție local, de exemplu filtre de detecție a marginilor, urmat de o procedură de împreunare a pixelilor individuali, iar în cele din urmă utilizarea regresiei liniare pentru estimarea parametrilor. Algoritmi de acest fel au probleme la liniile care se intersectează, și dacă mai există și un nivel ridicat de zgomot, este dificilă stabilizarea filtrelor cu detecție de margine. Transformata Radon nu este limitată de aceste probleme.

Definirea transformatei Radon (p,)

Transformata Radon poate fi definită în diverse moduri. Definiția folosită, de exemplu, în seismologie este mai ușor de înțeles. Transformata Radon a unei funcții (continue) bidimensionale pentru g(x, y) este găsită prin constrângerea sau integrarea valorii lui g de-a lungul liniilor înclinate. Locul (locația) liniei este determinat cu ajutorul parametrilor liniilor: panta p și linia de decalaj .

(1.1)

Funcția delta Dirac (.) va fi mult folosită în cele ce urmează. Utilizarea funcției delta va face ca transformata “Slant Stacking” să poată fi scrisă astfel:

(1.2)

Valoarea lui este o funcție într-un spațiu bidimensional (p,), adică, spațiu Radon sau domeniu parametric. De regulă, cei doi parametrii nu au limite inferioare sau superioare, cu toate că, după cum se va vedea, implementarea discretă va folosi un număr limitat de eșantioane în ambele direcții.

Proprietățile fundamentale ale transformatei Radon (p,)

Pornind de la ecuațiile 1.1 si 1.2 se poate obține un set de proprietăți fundamentale. Este posibil să se găsească și analitic transformata Radon, pornind de la niște funcții matematice simple.

Liniaritatea

Pornind de la ecuația 1.1 se poate observa implicit că transformata Radon a unei sume ponderate de funcții este aceeași cu suma ponderată a transformatelor Radon de funcții luate individual. Această proprietate este foarte importantă.

(1.3)

1.3.2 Deplasarea

Următoarea proprietate este transformata Radon a unei funcții de deplasare.

unde

(1.4)

Astfel doar parametrul de decalaj este schimbat prin schimbarea funcției. Din punct de vedere geometric rezultatul este clar. Panta unei linii nu poate fi modificată de o translație, însă decalajul trebuie schimbat ca în ecuația 1.4.

Scalarea

Se presupune existența unei funcții de scalare:

unde și

unde

(1.5)

Rezultatul poate fi înțeles din parametrii linei. Este clar că o compresie pe direcția y trebuie urmată de o compresie de-a lungul liniei de decalaj τ. Nu este dificil de înțeles că orice pantă va fi scalată cu un raport între a și b, lucru ce va fi realizat și de transformata Radon.

Originea vârfului

Originea vârfului este modelată ca fiind un produs de două funcții delta. Inițial originea vârfului este poziționată în originea coordonatelor sistemului.

(1.6)

Originea vârfului poate fi cu ușurință plasat în orice poziție, iar ecuația 1.4 este folosită pentru a o face:

(1.7)

Acest rezultat este interesant deoarece orice funcție poate fi scrisă ca o integrală ponderată a originii vârfului.

(1.8)

(1.9)

Ecuația 1.7 și în special ecuația 1.9 demonstrează că orice punct al funcției va contribui de-a lungul unei linii infinit de lungă în domeniul parametric. Acest aspect este asociat cu transformata Hough , transformată ce va fi analizată în Capitolul 3.

În figura 1.3 rezultatul este arătat simbolic. Se remarcă faptul că figura ilustrază o funcție bidimensională prin folosirea culorilor, alb pentru a indica (aproximativ) valoarea zero iar negru este o valoare înaltă (în acest caz infinit). Acest tip de grafic va fi folosit de multe ori în cele ce urmează.

Linia

Această proprietate foarte importantă presupune o funcție care conține o anumită linie, aici modelată cu o funcție delta.

(1.10)

deci funcția are o valoare diferită de zero numai dacă se întinde de-a lungul liniei cu anumiți parametrii fixați. În acest caz transformata Radon este dată de:

(1.11)

Se observă că pentru p=p* și τ= τ* rezultatul este scris ca o funcție infinită integrată pe un interval infinit, deci rezultatul este infinit în acel punct. Dacă, pentru moment, termenii finiți sunt neglijați, rezultatul este acela că transformata Radon a unei linii produce un vârf (cu valoare infinită) în domeniul parametric și poziția vârfului corespunde parametrilor liniei. Această proprietate a fost baza multor algoritmi de detecție a parametrilor curbelor. În figura 1.4 rezultatul este arătat simbolic. Din nou, albul indică (aproximativ) valoarea zero iar negrul valoarea înaltă (infinită).

Când parametrii domeniului Radon corespund parametrilor liniei, un vârf este găsit poziționat la parametrii liniei din imagine. Termenii finiți din domeniul parametric sunt ignorați aici pentru a obține o claritate mai mare.

Se poate observa că, în modul cum este definită transformata Slant Staking aici, apare dualitatea dintre cele două domenii. Un punct dintr-un domeniu imagine, cum ar fi spațiul (x, y), este transformat într-o linie din domeniul Radon și, dacă termenii finiți sunt ignorați, o linie din domeniul imagine va fi transformată într-un punct din domeniu Radon. Această proprietate este o consecință directă a formei nucleului integrat în ecuația 1.2. Această proprietate arată de ce transformata Radon poate fi folosită pentru algoritmi de detecție a curbelor.

Transformata “Slant Stacking” discretă

Fiind dată o submulțime de funcții ce pot fi transformate Radon analitic, este foarte folositoare o aproximare discretă a transformatei Radon care transformă o imagine digitală. În funcție de scopul propus, de exemplu viteză, artefacte, sau simplitate, există tot atât de multe definiții a transformatei Radon discrete câți oameni lucrează cu ea. Cu toate acestea, o metodă mai simplă este de a eșantiona liniar cele patru variabile și de a lucra numai cu un set limitat de eșantioane.

(1.12)

Aici xmin este poziția primului eșantion, este distanța de eșantionare a lui x și m este un indice discret folosit pentru a număra eșantioanele M ale lui x.

Folosind ecuația 1.1, o abordare simplă și generală pentru a aproxima transformata Radon liniară constă în a folosi o aproximare a sumei :

(1.13)

Eșantionarea funcției g(x, y) dă o imagine digitală:

(1.14)

Un nou simbol ar putea fi atribuit imaginii digitale, deși pornind de la indici ar trebui să fie clar dacă este folosită o versiune discretă sau continuă. De asemenea transformata Radon va fi scrisă astfel:

(1.15)

Deci, transformata Radon discretă va putea și va fi prezentată ca o imagine digitală.

1.4.1 Interpolarea celui mai apropiat vecin

Fiind dată imaginea eșantionată digital g(m, n), se ivește o problemă fundamentală. Ecuația 1.13 necesită eșantionări ce nu se găsesc în imaginea digitală, deoarece eșantionarea liniară a tuturor variabilelor implică faptul că în general pkxm+τh niciodată nu coincide cu eșantioanele yn . Problema poate fi corectată, de exemplu, folosind o aproximare a celui mai apropiat vecin pe direcția y, deci transformata Radon poate fi aproximată printr-o transformată Radon discretă:

(1.16)

unde [.] are rolul de a rotunji argumentul până la cel mai apropiat întreg. Altă problemă este că punctul discret (m,n(m;k,h)) nu trebuie neapărat să se găsească în imaginea finită. Dacă punctul iese din imagine, valoarea dorită poate fi setată la zero, adică punctul nu aduce nici o contribuție transformatei Radon discrete.

Se observă că termenul constant poate fi neglijat. Acest termen nu poartă nici o informație și este necesar numai dacă transformata Radon discretă ar trebui să aproximeze cantitativ transformata Radon (continuă).

Poate fi demonstrat cu ușurință că transformata Radon discretă este o funcție liniară, deși celelalte proprietăți indicate pentru transformata Radon continuă pot fi folosite numai cu aproximare în cazul transformatei Radon discrete.

Înainte de a arăta o mică parte dintr-un algoritmul de calcul pentru transformata Radon discretă, pentru a reduce calculul ,expresia pentru n ar trebui rescrisă într-o formă liniară foarte simplă:

(1.17)

Următorul program este scris în pseudo-cod, unde toți indicii de ordine au pornit de la zero.

Algoritmul 1.1 : Transformata Slant Stacking discretă

for k = 0 to K-1 //pentru toate valorile lui p

for h = 0 to H-1 //pentru toate valorile lui τ

Alpha = p(k) * Delta_x/Delta_y //se calculează panta digitală

Beta=(p(k)*x_min+tau(h)-y_min)/Delta_y//se calculează decalajul digital

sum = 0 //se inițializează suma

For = m = 0 to M-1 //pentru toate valorile lui x

n=round (alpha*m+beta)//folosește aproximarea celui mai apropiat vecin

if n 0 și n < N //se verifică dacă pixeli se întind de-a lungul imaginii

sum = sum+g(m,n) //dacă da, atunci se incrementează suma

end

end

g_radon(k,h)=Delta_ finiți sunt neglijați, rezultatul este acela că transformata Radon a unei linii produce un vârf (cu valoare infinită) în domeniul parametric și poziția vârfului corespunde parametrilor liniei. Această proprietate a fost baza multor algoritmi de detecție a parametrilor curbelor. În figura 1.4 rezultatul este arătat simbolic. Din nou, albul indică (aproximativ) valoarea zero iar negrul valoarea înaltă (infinită).

Când parametrii domeniului Radon corespund parametrilor liniei, un vârf este găsit poziționat la parametrii liniei din imagine. Termenii finiți din domeniul parametric sunt ignorați aici pentru a obține o claritate mai mare.

Se poate observa că, în modul cum este definită transformata Slant Staking aici, apare dualitatea dintre cele două domenii. Un punct dintr-un domeniu imagine, cum ar fi spațiul (x, y), este transformat într-o linie din domeniul Radon și, dacă termenii finiți sunt ignorați, o linie din domeniul imagine va fi transformată într-un punct din domeniu Radon. Această proprietate este o consecință directă a formei nucleului integrat în ecuația 1.2. Această proprietate arată de ce transformata Radon poate fi folosită pentru algoritmi de detecție a curbelor.

Transformata “Slant Stacking” discretă

Fiind dată o submulțime de funcții ce pot fi transformate Radon analitic, este foarte folositoare o aproximare discretă a transformatei Radon care transformă o imagine digitală. În funcție de scopul propus, de exemplu viteză, artefacte, sau simplitate, există tot atât de multe definiții a transformatei Radon discrete câți oameni lucrează cu ea. Cu toate acestea, o metodă mai simplă este de a eșantiona liniar cele patru variabile și de a lucra numai cu un set limitat de eșantioane.

(1.12)

Aici xmin este poziția primului eșantion, este distanța de eșantionare a lui x și m este un indice discret folosit pentru a număra eșantioanele M ale lui x.

Folosind ecuația 1.1, o abordare simplă și generală pentru a aproxima transformata Radon liniară constă în a folosi o aproximare a sumei :

(1.13)

Eșantionarea funcției g(x, y) dă o imagine digitală:

(1.14)

Un nou simbol ar putea fi atribuit imaginii digitale, deși pornind de la indici ar trebui să fie clar dacă este folosită o versiune discretă sau continuă. De asemenea transformata Radon va fi scrisă astfel:

(1.15)

Deci, transformata Radon discretă va putea și va fi prezentată ca o imagine digitală.

1.4.1 Interpolarea celui mai apropiat vecin

Fiind dată imaginea eșantionată digital g(m, n), se ivește o problemă fundamentală. Ecuația 1.13 necesită eșantionări ce nu se găsesc în imaginea digitală, deoarece eșantionarea liniară a tuturor variabilelor implică faptul că în general pkxm+τh niciodată nu coincide cu eșantioanele yn . Problema poate fi corectată, de exemplu, folosind o aproximare a celui mai apropiat vecin pe direcția y, deci transformata Radon poate fi aproximată printr-o transformată Radon discretă:

(1.16)

unde [.] are rolul de a rotunji argumentul până la cel mai apropiat întreg. Altă problemă este că punctul discret (m,n(m;k,h)) nu trebuie neapărat să se găsească în imaginea finită. Dacă punctul iese din imagine, valoarea dorită poate fi setată la zero, adică punctul nu aduce nici o contribuție transformatei Radon discrete.

Se observă că termenul constant poate fi neglijat. Acest termen nu poartă nici o informație și este necesar numai dacă transformata Radon discretă ar trebui să aproximeze cantitativ transformata Radon (continuă).

Poate fi demonstrat cu ușurință că transformata Radon discretă este o funcție liniară, deși celelalte proprietăți indicate pentru transformata Radon continuă pot fi folosite numai cu aproximare în cazul transformatei Radon discrete.

Înainte de a arăta o mică parte dintr-un algoritmul de calcul pentru transformata Radon discretă, pentru a reduce calculul ,expresia pentru n ar trebui rescrisă într-o formă liniară foarte simplă:

(1.17)

Următorul program este scris în pseudo-cod, unde toți indicii de ordine au pornit de la zero.

Algoritmul 1.1 : Transformata Slant Stacking discretă

for k = 0 to K-1 //pentru toate valorile lui p

for h = 0 to H-1 //pentru toate valorile lui τ

Alpha = p(k) * Delta_x/Delta_y //se calculează panta digitală

Beta=(p(k)*x_min+tau(h)-y_min)/Delta_y//se calculează decalajul digital

sum = 0 //se inițializează suma

For = m = 0 to M-1 //pentru toate valorile lui x

n=round (alpha*m+beta)//folosește aproximarea celui mai apropiat vecin

if n 0 și n < N //se verifică dacă pixeli se întind de-a lungul imaginii

sum = sum+g(m,n) //dacă da, atunci se incrementează suma

end

end

g_radon(k,h)=Delta_x*sum

end

end

În acest algoritm pk a fost înlocuit cu p(k) și inițierea ordinii a fost scoasă pentru a reduce dimensiunea pseudocodului. Se va observa că acțiunile ce au fost efectuate asigură faptul că acel pixel ce intră în sumă de fapt se află în imagine. În partea de consum de timp a buclei, adică, în bucla m, optimizarea ar trebui realizată avându-se mare grijă de platforma folosită (computerul sau echipamentul digital similar) pentru a calcula transformata Radon discretă. Un truc care poate crește considerabil performanța pe cele mai multe platforme este calcularea directă a valorilor lui m care vor da pixeli în interiorul imaginii.

(1.18) (1.19)

unde rotunjesc spre cel mai apropiat întreg inferior și, respectiv superior. În loc să folosim întregul interval de m valori, pentru a evita consumul de timp folosit pentru testarea limitelor valide, ar trebui folosit doar m,de la mmin până la mmax.

O altă problemă a optimizării are în vedere expresia n=round(alpha*m+beta), expresie ce poate fi înlocuită inițial de nfloat=beta+m_min*alpha (dacă folosim schimbarea descrisă în ecuația 1.19) și apoi în cadrul buclei n=round(nfloat) și liniei nfloat=nfloat+alpha. Deci, multiplicarea poate fi evitată în cea mai importantă parte a programului. Acumularea suplimentară de zgomot va cauza probleme numai dacă folosim o reprezentare sumară a numerelor în virgulă mobilă sau vom folosi imagini exagerat de mari (nu este cazul). Această alterare poate da o viteză suplimentară, dar totuși depinde pe ce platformă lucrăm, adică, rata de acces la memorie și rata de multiplicare sau sumare a platformei.

1.4.2 Interpolarea liniară

Până acum a fost luată în calcul numai aproximarea celui mai apropiat vecin. Poate fi folosită de asemenea și interpolarea liniară a imaginii pe direcția y .

(1.20)

(1.21)

Se poate observa că ecuația 1.20 necesită suma a de două ori mai multe eșantioane decât ecuația 1.16. În general, o schemă de interpolare mai bună implică un efort de calcul mai mare. Această optimizare poate fi făcută prin eșantionarea proprietăților și timpul disponibil al algoritmului.

După cum este arătat în ecuația ce urmează, interpolarea liniară nu implică multe schimbări în strategia de optimizare a calculului intervalului în care poate lua valori m, valori corespunzătoare pixelilor din imagine.

(1.22)

(1.23)

De remarcat este faptul că ecuația (1.23) se folosește la îmbunătățirea performanței.

În algoritmul următor este arătat cum se calculează transformata Radon discretă folosind interpolarea liniară.

Algoritmul 1.2: Transformata Slant Stacking discretă folosind interpolarea liniară

for k = 0 to K-1 //pentru toate valorile lui p

alpha = p(k)*delta_x/delta_y //se calculează panta digitală

for h = 0 to H-1 //pentru toate valorile lui τ

beta=(p(k)*x_min+tau(h)-y_min)/delta_y//se calculează decalajul digital

set m_min si m_max folosind ecuația 1.23

sum = 0 //se inițializează suma

for m = m_min to m_max //pentru toate valorile lui x

nfloat = alpha*m+bet //se folosește aproximarea celui mai apropiat vecin

n = floor(nfloat) //se calculează indexul cel mai scăzut

w = nfloat-n //se calculează factorul pondere

sum = sum+g(m,n)*(1-w)+g(m,n+1)*w //se incrementează suma

end

g_radon(k,h) = sum*delta_x //se actualizează elementele matricei

end

end

În subcapitolele 1.5 și 1.6 exemplele vor fi date pe parcurs pentru a arăta diferențele dintre aproximarea celui mai apropiat vecin, dată de ecuația 1.16, aproximarea prin interpolare liniară și interpolarea sinc a transformatei Radon.

Interpolarea sinc

Presupunând că funcția g(x, y) a fost eșantionată folosind teorema de eșantionare Whittaker-Shannon, atunci funcția poate fi recuperată dintr-o imagine digitală g(m,n) prin convoluția cu o funcție sinc.

(1.24)

Funcția g(x, y) nu este recuperată chiar cu exactitate, deoarece însumarea ar fi, în principiu, infinită, însă acestor eșantioane li se atribuie valoarea zero.

În locul aproximării transformatei Radon cu o imagine digitală, este propusă o nouă metodă de analiză a transformatei Radon pentru o imagine digitală.

Ecuația 1.1 va fi aplicată ecuației 1.24 pentru a obține informații despre transformata Radon și pentru a deduce un criteriu de eșantionare pentru domeniul parametric.

(1.25)

(1.26)

(1.27)

Ultima integrală poate fi interpretată ca o convoluție. Folosind faptul că transformata Fourier a unei funcții sinc este un pătrat, iar un pătrat multiplicat cu un pătrat ne dă tot un pătrat, acest fapt arată că ultima integrală este o funcție sinc.

(1.28)

(1.29)

Rezultatul este o interpolare sinc a transformatei Radon discrete, dar pentru moment expresia va fi folosită pentru a analiza proprietățile de eșantionare ale transformatei Radon.

Proprietățile de eșantionare ale transformatei Radon discrete

Presupunând că panta absolută |p| este limitată (în paragraful 1.7 se va arăta că acest fapt este rezonabil), adică, ||<1, implică faptul că transformata Radon este determinată de funcția sin()/, care, ca o funcție de are o limitare superioară în frecvență la 1/2π, și dacă ar trebui eșantionată, acest fapt ar trebui să fie făcut cu o rată de eșantionare mai mare de

(1.30)

O variantă discretă a transformatei Radon necesită ca cei doi parametrii să fie eșantionați, iar ecuația 1.30 este folosită pentru fiecare din cei doi parametrii Radon, și anume, p și .

(1.31)

(1.32)

Se observă că o evaluare conservativă este folosită pentru a asigura că limita din ecuația 1.32 este validă pentru toate valorile lui xm. Ultima ecuație arată că distanța de eșantionare p trebuie să fie mică, dacă max|xm| este mare. În ceea ce privește eșantionarea lui p este optimă alegerea unor puncte de eșantionare simetrice cu x, prin urmare minimalizând max|xm|.

(1.33)

Chiar dacă xmin este fixat de formula de mai sus, micul artificiu poate fi folosit datorită proprietății de deplasare (shiftare) a transformatei Radon, prezentată în ecuația 1.4.

O altă metodă rezonabilă în definirea limitelor distanțelor de eșantionare din domeniul parametric, este aceea că schimbarea unuia din parametrii transformatei Radon cu intervalul său de eșantionare, nu poate duce la o diferență mai mare de un pixel în imagine, altfel unii dintre pixeli nu pot adăuga greutate domeniului parametric, și astfel informația este pierdută. Altfel spus :

(1.34)

(1.35)

deci, concluzia interesantă este aceea că cele două metode dau același rezultat.

Presupunând că scopul constă în a identifica parametrii liniei, atunci distanțele de eșantionare p și pot fi aflate cu ajutorul ecuațiilor 1.32 și respectiv 1.31. Cei doi parametrii min și H pot fi stabiliți printr-o cerință ca, de exemplu, jumătate din eșantioanele transformatei Radon discrete ar trebui să se afle în imagine. Dacă privim ecuația 1.33, se va găsi că H=N și min=ymin, adică, eșantionarea lui este urmată de eșantionarea lui y. Cei doi parametrii pmin și K trebuie să fie aleși pentru a acoperii intervalul pantelor propuse.

Concluzia este că pentru o imagine digitală dată, domeniul parametric trebuie să fie eșantionat suficient de des pentru a evita problemele nedorite. Limitările ce decurg din ecuațiile 1.32 și 1.31 vor fi acum testate cu implementări discrete ale transformatei Radon.

1.5 Transformata Radon discretă a unei linii discrete

O imagine digitală a fost generată cu eșantioane tip 101*101. Imaginea artificială conține două linii, așa cum se vede în figura 1.5. Eșantionarea parametrilor pentru acest exemplu poate fi găsită în tabelul 1.1. Aici p și sunt aleși ținându-se cont de ecuațiile 1.31 și 1.32.

Tabelul 1.1 : Parametrii de eșantionare

Figura 1.5 Figura 1.6

Imagine cu două linii Transformata Radon discretă corespunzătoare

Liniaritatea transformatei Radon implică faptul că două vârfuri ar trebui să apară în domeniul parametric discret, fapt arătat în figura 1.6. De pe pozițiile vârfurilor, este evident că parametrii liniei sunt (p1=0.5,1=50) și (p2=0.4 și 2 =20).

Acum sunt schimbați parametrii eșantionării din domeniul parametric, pentru a mări zona din jurul unui vârf. Parametrii de eșantionare sunt arătați în partea stângă a tabelului 1.2 iar transformata Radon este ilustrată în figura 1.7. Acum vârful este foarte întins (clar), ceea ce sugerează că eșantionarea domeniului parametric este inutil de densă. De asemenea se poate observa că a fost menținut domeniul discret al parametrilor, și deci costul de calcul este aproape la fel ca și în figura 1.6.

În figura 1.8 domeniul parametric a fost eșantionat foarte rar și se observă cum a dispărut vârful de sus. Parametrii de eșantionare p și sunt fixați aici pentru a întării eșantionarea domeniului parametric, adică, limitele găsite în ecuațiile 1.32 și 1.31 sunt puternic depășite. Acest exemplu arată cum ar trebui setați parametrii de eșantionare ai domeniului parametric. Dacă acest domeniu este eșantionat prea dens vom avea informație redundantă. Pe de altă parte eșantionarea domeniului parametric foarte rară ar putea duce la pierderea de informații importante. Aici este pierdută informația despre una dintre linii, dar sunt menținuți parametrii celeilalte linii.

Tabelul 1.2 : Parametrii de eșantionare

1.5.1 Comparație între diferite metode de interpolare

Eșantionarea domeniului parametric depinde de asemenea și de tipul de interpolare folosit, și de tipul imaginii. Dacă imaginea g(m, n) nu include margini foarte ascuțite cu multe componente cu frecvențe înalte, ar fi suficientă o aproximare a celui mai apropiat vecin, însă o imagine ce conține o linie, ca și cea din figura 1.9, implică faptul că metoda de interpolare afectează rezultatele din apropierea vârfului din domeniul discret al parametrilor.

În cele ce urmează domeniul discret al parametrilor este găsit prin folosirea a trei aproximări, și anume interpolare celui mai apropiat vecin în imagine (ecuația 1.16), interpolarea liniară (ecuația 1.20) și interpolarea sinc (ecuația 1.29). În toate aceste trei cazuri sunt găsiți parametrii liniari, corespunzători figurii 1.9.

Figura 1.9 : O imagine cu o linie

Figurile 1.10,1.12 și 1.14 folosesc aceeași scală de culoare pentru a arăta domeniile discrete ale parametrilor. Se poate observa că diferența este limitată dar valoarea din vârf este scăzută în ultimele două imaginii comparativ cu prima (cel mai apropiat vecin). În figurile 1.11, 1.13 și 1.15 sunt prezentate domeniile discrete ale parametrilor folosind o eșantionare densă a ariei vârfului. Imaginile au o scală de culori comună. Se poate observa că vârful din figura 1.11 este foarte limitat, cu toate că valoarea cea mai mare (aproximativ 101) este mult superioară în comparație cu figurile 1.13 și 1.15. Aceasta indică faptul că folosirea aproximării celui mai apropiat vecin, pentru a asigura găsirea vârful, necesită o eșantionare densă a domeniului parametric. Folosirea interpolării liniare implicǎ faptul cǎ valorile vârfului vor fi mai degrabă mici (≈ 78), dar clare. Acest lucru poate fi înțeles din figura 1.9, unde cel puțin una din douǎ imagini sunt nule (egale cu zero) pentru orice m, deci factorii pondere vor micșora rezultatele din vârf.

Ceea ce este important este că vârful generat în domeniul discret al parametrilor cu o dimensiune suficientă și o eșantionarea adecvată a domeniului parametric ar trebui comparată cu teoria din care provine. Pornind de la figura 1.15 este găsită o valoare de vârf oarecare (≈ 89) și mărimea efectivă a vârfului seamănă cu cea găsită cu ajutorul interpolării liniare. Pentru figurile 1.10,1.12, și 1.14 parametrii imaginii și parametrii domeniului pot fi găsiți în tabelul 1.1, și pentru figurile 1.11, 1.13, și 1.14 în tabelul 1.3. Observați forma specială a domeniului parametric în cazul celui mai apropiat vecin. Este un efect digital și va fi găsit când panta liniei poate fi scrisă ca o fracție de numere mici, de exemplu 1/2.,1/3 sau 3/4 .

De asemenea, foarte interesantă este și complexitatea calculului celor trei aproximări. Folosind simbolurile folosite în ecuația 1.12, acest calcul de implementare a transformatei Radon discrete este cu aproximație dată de :

(1.36)

unde este funcția de ordine; s-au neglijat unii dintre termenii de ordine inferiori. Presupunând că M este de ordin 100, atunci complexitatea de calcul a interpolării sinc este de 100 de ori mai mare decât în cazul celorlalte două metode.

Tabelul 1.3 : Parametrii de eșantionare pentru figurile 1.11,1.13 și 1.15

Se observă că aproximarea liniară este mai lentă decât cea a celui mai apropiat vecin, datorită însumării celor două eșantioane pentru fiecare m.

În tabelul 1.4 este arătat timpul necesar calculului domeniului discret al parametrilor corespunzător pentru trei aproximări diferite. Algoritmii au fost implementați în limbajul C. Așa cum se poate vedea, a fost câștigat un factor de viteză de aproximativ 3.5 prin optimizarea codului, descrisă mai sus. Timpul folosit pentru aproximarea liniară poate fi comparat cu timpul aproximării celui mai apropiat vecin (ne-optimizat) din 1.4, unde este găsită doar o mică diferență. Aproximarea sinc este foarte înceată după cum rezultă din ecuația 1.36, datorită faptului că acest algoritm trebuie să calculeze funcția sinc pentru fiecare (m,n,k,h).

Tabelul 1.4: Timpul necesar pentru a calcula transformata Radon discretă a trei tipuri de aproximări corespunzătoare figurilor 1.11, 1.13 și 1.15. (s-a folosit un procesor la 120 MHz)

O metodă de analiză a rezoluției transformatei Radon discrete constă în vizualizarea formei domeniului discret al parametrilor cu o valoare de prag corespunzătoare, de exemplu, cu jumătate din maximul de potențial al domeniului parametric, în acest caz 50. Aceasta este un fel de măsurătoare bandă întreagă la jumătate de maxim. Figurile 1.16, 1.17 și 1.18 prezintă un domeniu parametric folosind un nivel de prag de 50. Se poate vedea din figuri că o extindere a vârfului, extindere ce poate fi interpretată ca rezoluție a transformatei Radon discrete pe direcția , este foarte apropiată de distanța de eșantionare dedusă în ecuația 1.31, iar rezoluția pe direcția p este de aproximativ de trei ori mai mare ca cea dedusă în ecuația 1.32. Dar trebuie notat că acest fel de analiză depinde de nivelul de prag actual. Privind acest exemplu se trage concluzia că aproximările simple duc la rezultate bune și mult mai rapide decât cele folosind interpolarea sinc.

Transformata Radon discretă a punctelor

În acest subparagraf va fi analizată transformata Radon discretă a unor puncte individuale. Vor fi analizate imagini cu un număr crescând de puncte ce se întind de-a lungul unei linii pentru a vedea rezultatele paragrafului 1.5 dintr-un alt punct de vedere.

Figura 1.9 este generată din figura 1.5 (o imagine cu două linii) și imaginea are opt pixeli diferiți de zero, de-a lungul celor două linii. Valorile pixelilor acum sunt atenuate orizontal de-a lungul imaginii (valoarea pixelului cel mai de jos în partea dreaptă a imaginii). În figura 1.20 este arătată transformata Radon discretă corespunzătoare folosind interpolarea celui mai apropiat vecin. După cum se aștepta din ecuația 1.7 fiecare din cei opt pixeli sunt transformați într-o linie în domeniul parametric. Datorită valorilor diferite al pixelilor diferiți de zero din imagine este posibilă identificarea pixelului diferit de zero din imagine care corespunde unei anumite linii din domeniul parametric. Altă problemă importantă este aceea că liniile găsite în domeniului parametric, intersectează și amplificată în două puncte corespunzătoare parametrilor liniei. Parametrii de eșantionare pentru acest exemplu pot fi găsiți în tabelul 1.1

Figura 1.21 prezintă o imagine similară generată având zece puncte pe fiecare linie. Pornind de la transformata Radon discretă, ilustrată în figura 1.22, pot fi extrași parametrii de linie, datorită poziției vârfurilor marcată clar în domeniul parametric. Figura 1.23 ilustrează o imagine cu două linii complete, iar figura 1.24 arată domeniul corespunzător al parametrilor. Imaginile au fost scalate individual în funcție de valoarea pixelului maxim și minim, și astfel se poate vedea că valoarea de vârf, în ultimul caz, este mai mare comparativ cu celelalte două.

S-a demonstrat că fiecare punct din imagine este transformat într-o linie în domeniul discret al parametrilor, unde decalajul și panta variază în funcție de poziția pixelului din imagine. Acest fapt conduce la o problemă foarte importantă și anume că transformata Radon discretă a oricărui pixel nu poate fi reținută, deci trunchiată, în domeniul finit al parametrilor. În acest fel informația va fi pierdută folosind transformata discretă Slant Stacking.

S-a demonstrat că domeniul parametric trebuie să fie eșantionat suficient de des pentru a asigura ca aproximările discrete ale transformatei Radon să nu producă probleme de aliasing.

O altă problemă se ridică atunci când imaginile conțin linii cu o pantă foarte mare (aproape verticale). Pentru început presupunem o imagine ce conține două linii așa cum se arată în figura 1.25. O linie are panta 1/9 iar cealaltă 9. Transformata Radon discretă corespunzătoare este arătată în figura 1.26, unde parametrul p a fost limitat între –1 și 1. Parametrii primei linii sunt clar identificați dar datorită pantei abrupte și a domeniului parametric trunchiat cealaltă linie nu este detectată. Aceasta ilustrează faptul că poate fi identificată numai o linie cu parametrii ce se află în cadrul domeniului parametric. Există o proprietate generală a transformatei Radon discrete, care necesită un domeniul al parametrilor ce conține multe eșantioane, atunci când nu este dată nici o informație anterioară. Dacă, de exemplu, pantele liniilor sunt limitate între –0.1 și 0.1, atunci pentru a reduce calculul trebuie folosită această limitare și în domeniul discret al parametrilor.

O soluție care ar face posibilă detectarea ambelor linii pentru a obține pmax=p min + (K-1)p>9, ar fi creșterea lui K, de exemplu, numărul de eșantioane în direcția p. Acest fapt este posibil, însă costul de calcul este prea mare, datorită numărului mare de eșantioane din domeniul discret al parametrilor.

O altă problemă este aceea că valoarea de vârf din domeniul discret al parametrilor ar trebui să fie în jur de 100 (sau poate puțin mai scăzută după cum se vede în subparagraful 1.5), datorită faptului că fiecare linie este făcută din 101 eșantioane ce au valoarea 1. Presupunând că domeniul parametric a fost extins pentru a include o linie foarte abruptă, atunci valoarea la vârf a transformatei Radon discrete, ar trebui să fie în jurul valorii 10. Acest lucru este ilustrat în figura 1.27. Linia întreruptă este linia sub care se adună valorile. Dar mergând mai departe la m, numai în acest caz, 4 eșantioane contribuie la transformata Radon discretă, iar câteva eșantioane ce se află între cele patru sunt omise. În figura 1.25, doar în jur de 10 pixeli contribuie la transformata Radon discretă în regiunea parametrilor din a doua linie, deci valoarea de vârf va fi cu mult mai scăzută decât cea posibilă din imagine.

Un alt motiv serios de îngrijorare vine din analiza funcțiilor cu linii verticale. Transformata Radon discretă corespunzătoare poate fi găsită pr

(1.37)

unde se poate observa că transformata Radon nu depinde de poziția liniei x*. Aceasta înseamnă că informația nu este menținută în domeniul parametric, deci poziția liniilor verticale nu poate fi detectată folosind “Slant Stacking”.

Un mod de a rezolva problemele descrise constă în a calcula două domenii ale parametrilor. Primul are valori cuprinse în intervalul –plim pplim , iar celălalt este folosit pentru a manevra orientările liniilor rămase.

(1.38)

(1.39)

Cele două moduri de descriere a liniilor sunt relaționate astfel:

(1.40)

Astfel dacă –plim<pplim atunci celălalt parametru al pantei ar trebui sa fie mărginit astfel –1/ pli m 1/ plim. O valoare rezonabilă a pantei limitate este:

(1.41)

Această limită asigură că problema ilustrată în figura 1.27 este eliminată. Schimbarea pe direcția verticală când trecem la următorul m, în timpul transformării Radon discrete, va fi mai mică decât 1. Din ecuația 1.17, aceasta va putea fi interpretată ca o pantă digitală a liniei, și va avea valori între –1 și 1. Acest mod de alegere a lui plim îndeplinește totodată și presupunerea din ecuația 1.30 că || > 1.

Se poate observa că o implementare discretă a transformatei Radon definită în ecuația 1.39 nu necesită o programare suplimentară. Aplicând transformata Radon discretă pentru a transpune o imagine digitală, adică h(m,n)=g(n,m) și folosind ecuația 1.40 pentru a converti parametrii de eșantionare, atunci domeniul discret al parametrilor obținut estimează transformata Radon dorită.

Concluzii

Transformata Slant Stacking fost definită la fel cu termenul folosit în seismică. Transformata a fost analizată ca un caz special al transformatei Radon. Prin introducerea și analiza unei noi strategii de expansiune sinc s-au derivat aproximări discrete și au fost analizate proprietățile de eșantionare. S-a demonstrat, cu scopul detecției curbei, că este adecvată aproximarea celui mai apropiat vecin, dacă eșantionarea domeniului parametric este suficient de densă. De asemenea, s-a demonstrat că interpolarea liniară are ca rezultat cam același domeniu al parametrilor ca și cel găsit cu ajutorul interpolării sinc.

S-a demonstrat că transformata Slant Stacking detectează parametrii curbelor dacă panta liniei este sub o anumită limită ce ține cont de parametrii de eșantionare. Este de asemenea trecut în revistă și un remediu simplu pentru această limitare.

CAPITOLUL II

Transformata Radon normală

În acest capitol sunt trecute în revistă cele mai cunoscute forme ale transformatei Radon liniare. Sunt prezentate câteva moduri de definirea a transformatei Radon discrete și o analiză a relațiilor de eșantionare folosind aceleași tehnici prezentate în Capitolul 1. Sunt incluse și câteva exemple pentru a lămuri teoria.

2.1 Definirea transformatei Radon (,)

În Capitolul 1 a fost prezentată o formă a transformatei Radon liniare, numită transformata Slant Stacking. Aceasta este numai una din formele liniare, deoarece transformata Radon poate fi definită într-o formă mai generală, astfel :

(2.1)

În această formă, linia este descrisă (aparent) cu trei grade de libertate, fapt ce este doar un mod de a descrie o linie, astfel încât cei trei parametrii ar trebui să aibă o legătură, ceea ce ar elimina un grad de libertate. În literatură două forme sunt cele mai răspândite. Prima, Slant Stacking, are parametrii :

(2.2)

O altă definiție a transformatei Radon este folosită în multe domenii ale științei, de exemplu tomografie, astronomie și microscopie, unde funcția fundamentală g(x, y) nu are nici o orientare privilegiată. Acest fapt duce la descrierea liniei în forma sa normală :

(2.3)

adică, și la transformata Radon normală. Termenul de transformată Radon normală nu este în general acceptat, dar aici este un termen foarte practic și este folosit numai pentru a face distincția dintre Slant Stacking și forma prezentată aici în ecuația 2.4 care poate fi scrisă astfel:

(2.4)

Această definiție poate fi comparată cu ecuația 1.2, corespunzătoare transformatei Slant Stacking. Se observă că nu a fost atribuit nici un nou simbol pentru transformata Radon normală, iar argumentele sunt folosite pentru a arăta care definiție este folosită.

Este folosită mai des o altă formă echivalentă a ecuației 2.4 :

(2.5)

(2.6)

(2.7)

(2.8)

Ecuația 2.8 poate fi comparată cu ecuația 1.1.

Sensul de parametrii normali folosit pentru specificarea poziția liniei este prezentat în figura 2.1. Parametrul este distanța cea mai mică dintre originea sistemului de coordonate și linie, iar este unghiul corespunzător orientării liniei.

Primul lucru pe care îl observăm despre transformata Radon normală este că toate liniile pot fi descrise în intervalul 0 2 și 0, dar sunt folosite frecvent și alte limite. Dacă sunt introduse și valori negative ale lui atunci domeniul parametric are următoarele limite :

(2.9)

unde este pozitiv, și finit când este luată în considerare orice implementare discretă. Ambele limite ale domeniului parametric sunt valabile , ele fiind în legătură astfel :

(2.10)

fapt ce poate fi găsit pornind de la ecuația 2.4 folosind proprietatea funcției delta de a fi pară.

Transformata Radon normală și Slant Stacking sunt inter-relaționate, adică una poate fi exprimată din cealaltă. Pornind de la ecuația 2.6 se găsește că:

(2.11)

Relație este foarte simplă, iar legătura dintre cele două seturi de parametrii poate fi găsită direct din figurile 2.1 și 1.3. Este clar că ecuația 2.11 impune o problemă când este aproape zero, dar în acest caz poate fi făcută o legătură cu transformata Radon din ecuația 1.39,

(2.12)

Folosind ecuația 2.4 pot fi derivate câteva proprietăți. Cea mai importantă este aceea că transformata Radon normală este o funcție liniară.

2.1.1 Originea vârfului

Originea varfului este folosită iarăși pentru a obține informații despre comportamentul fundamental al transformatei Radon normale. Aici, originii varfului îi este atribuită o poziție arbitrară (x*,y*).

(2.13)

(2.14)

Pornind de la ecuația 2.14 se arată că pentru orice funcție g(x,y) transformata Radon este dată de :

(2.15) (2.16)

(2.17)

(2.18)

Acest rezultat este foarte interesant ținând cont de algoritmii numerici. Se arată că un punct este transformat într-o sinusoidă în domeniul parametric, iar transformata Radon a originii vârfului poate fi restrânsă într-un domeniu trunchiat al parametrilor.

(2.19)

formulă ce derivă direct din ecuația 2.17. Acest rezultat poate fi comparat cu ecuația 1.7, găsită pentru Slant Stacking.

2.1.2 Transformata Radon (,) a unei linii

Unul dintre avantajele majore ale transformatei Radon normale îl reprezintă detecția liniei. O linie cu parametrii (*,*), dacă o modelăm cu funcția delta, avem:

(2.20)

(2.21)

și dacă = * , adică sin( – *) = 0, rezultă că

(2.22)

Și nu este surprinzător că rezultatul arată formarea unui vârf în = * și = * (vor fi găsiți de asemenea și termeni finiți). Mai mult, se observă că nu există nici o limitare în ceea ce privește orientarea liniei, fapt ce constituia o problemă în ceea ce privea modul de definire a transformatei Slant Stacking.

2.2 Transformata Radon (,) discretă

O aproximare discretă a transformatei Slant Stacking continue se găsește în ecuațiile 1.12 și 1.13. Încă o dată toți parametrii sunt eșantionați liniar:

(2.23)

Aparent transformata are o mulțime de termeni liberi, dar în mod normal, numai câțiva dintre ei sunt fixați. Ecuația 2.19 implică faptul că, partea funcției g(x, y) care interesează, ar trebui deplasată înainte spre centrul sistemului de coordonate, pentru a obține cel mai mic număr de eșantioane pe direcția .

Se presupune că imaginea este un pătrat:

(2.24)

(2.25)

fapt ce face ca eșantionarea să fie simetrică într-un interval din jurul lui zero, adică,

(2.26)

(2.27)

(2.28)

Considerând eșantionarea unghiulară, punctul unghiular de început poate fi ales astfel:

(2.29)

În al doilea rând, intervalul de eșantionare a lui ar trebui setat cu deschiderea , adică:

(2.30)

Astfel, acest fapt lasă numai câțiva termeni liberi, și anume x, M, T, R și . Aceste limitări sunt deduse în cele ce urmează.

Un mod de a defini o transformata Radon discretă constă în a putea aproxima ecuația 2.8 la :

(2.31)

(2.32)

unde sj este o eșantionare liniară a variabilei s, dată în ecuația 2.23. Această metodă are anumite implicații. Cea mai importantă este aceea că pentru o valoare dată a lui j, punctele imagine găsite în ecuația 2.32, adică, nu coincid niciodată cu eșantioanele din imaginea (presupusă) g(m, n) = g (xm, yn), deci este nevoie de o interpolare pentru ambele variabile (x, y). Această interpolare bidimensională poate fi și trebuie evitată, datorită zgomotului suplimentar adăugat, comparativ cu o interpolare unidimensională. O altă problemă este cât de dens ar trebui eșantionat intervalul de parametrii s, adică, cum ar trebui ajustată s.

O altă metodă de aproximare a transformatei Radon normale și de a obține doar o interpolare unidimensională în imagine, este de a reformula ecuația 2.8 folosind definiția transformatei Slant Stacking, cum a fost dată în ecuațiile 2.11 și 2.12. Această soluție necesită numai o interpolare unidimensională. Ambele au fost implementate la fel (de repede) ca și aproximarea celui mai apropiat vecin, după cum se observă mai jos, sau de exemplu , ca o interpolare liniară.

(2.33)

(2.34)

(2.35)

(2.36)

(2.37)

(2.38)

unde s-a folosit faptul că x = y, M = N și xmin = ymin . Se observă că, pe lângă factorii (de proiecție) 1/|sin| și 1/|cos| din fața integralelor, modul de aproximare al celor două integrale, rezultă din paragraful 1.4 și în special din paragraful 1.7. Ideea este arătată în algoritmul 2.1

Algoritmul 2.1 : Transformata Radon normală discretă :

for t = 0 to T-1 //pentru toate valorile lui θ

costheta = cos(theta(t))

sintheta = sin(theta(t))

rhooffset = x_min*(costheta+sintheta) //factor comun

if sintheta > 1/sqrt(2) //proiecție pe axa x

alpha = – costheta/sintheta //este setată panta digitală

for r = 0 to R-1 //pentru toate valorile lui ρ

beta = (rho(r)-rooffset)/(delta_x*sintheta) //este setat decalajul

mmin și mmax sunt setate folosind ecuația 1.19 //expresie omisă

sum = 0 //se inițializează suma

for m=sum+g(m,round(alpha*m+beta)) //se incrementează suma

end

g_radon(r,t)=delta_x*sum/sintheta //se update-ază elementele matricei

end

else //proiecție pe axa y

alpha=-sintheta/costheta //este setată panta digitală

for r=0 to R-1 //pentru toate valorile lui ρ

beta=(rho(r)-rooffset)/(delta_x*costheta) //este setat decalajul

nmin și nmax sunt setate folosind ecuația 1.19 // expresie omisă

sum=0 //se inițializează suma

for n=nmin to nmax //pentru toate valorile normale ale lui x

sum=sum+g(round(alpha*n+beta),n) //se incrementează suma

end

g_radon(r,t)=delta_x*sum/abs(costheta //se update-ază elementele matricei

end

end

end

După cum se poate vedea în algoritmul de mai sus, programul este împărțit în două părți, corespunzătoare axelor pe care integrala liniei a fost proiectată. Fiecare parte a fost optimizată în modul descris și în algoritmul 1.1. Expresiile pentru mmin și mmax sunt date în ecuația 1.19, iar expresiile pentru nmin și nmax pot fi deduse din aceeași ecuație doar cu câteva schimbări minore ale variabilelor.

2.2.1 Proprietățile de eșantionare ale transformatei Radon (,)

Pentru a câștiga informații despre legăturile dintre eșantionări, este folosită procedura „sinc-expansion”, prezentată în sub-paragraful 1.4.3. Dar, pentru a obține rezultatul, în loc să integrăm, ecuația 1.24, sunt cuplate rezultatul interpolării sinc de la transformata Slant Stacking și relația dintre transformata Radon normală și Slant Stacking, ecuația 2.11. Aceasta arată o metodă importantă pentru a obține mai multe informații despre transformata Radon. Unele rezultate sunt mai bine înțelese și pot fi deduse, de pildă, cu transformata Slant Stacking, dar poate fi ușor translatată transformatei Radon normale (și invers).

(2.39)

(2.40)

(2.41)

(2.42)

(2.43)

Folosind tehnica prezentată în sub-paragraful 1.4.3, proprietățile de eșantionare ale transformatei Radon normale sunt determinate de . Fiind în funcție de , funcția are valori cuprinse între 1 și . Folosind maximul din , intervalul de eșantionare al lui ar trebui să nu fie mai mare decât . Folosind această limită pentru ambii parametrii, avem:

(2.44)

(2.45)

De remarcat că sunt făcute câteva presupuneri ample, pentru a obține expresiile valide pentru toate valorile lui (xm, yn). Rezultatul arată că, pentru o imagine dată, există o limită inferioară a intervalelor de eșantionare din domeniul parametric. Depășirea acestor limite poate duce la apariția unor probleme în domeniu parametric. Se poate arăta că ecuațiile 2.44 și 2.45 corespund unei necesități, și anume când schimbăm ori ori cu intervalele lor de eșantionare respective, schimbarea poziției liniei ar trebui să fie sub un eșantion.

Pentru o imagine dată g(m ,n) și o distanță de eșantionare x, distanța de eșantionare unghiulară poate fi fixată folosind ecuația 2.45, deci parametrii de eșantionare unghiulari pot fi aleși astfel:

(2.46)

unde s-a folosit că . Când folosim ecuațiile 2.44 și 2.28, singurul parametru ce rămâne de determinat este R (sau min =-max), care poate fi determinat atribuind conform ecuației 2.44 și introducând ecuațiile 2.26-2.28 în ecuația 2.19. Astfel avem:

(2.47)

(2.48)

2.2.2 Transformata Radon (,) discretă a diverse linii

Figura 2.3 arată o imagine cu 101*101 pixeli, unde pot fi găsite 7 linii cu diferite orientări și amplitudini (valoare pixelului de pe o linie) după cum arată tabelul 2.1.

Figura 2.4 arată domeniul discret al parametrilor folosind algoritmul 2.1, adică aproximarea celui mai apropiat vecin. Sunt găsite șapte vârfuri, iar valorile vârfurilor corespund curbei de amplitudine . După cum se vede în tabelul 2.2, parametrii eșantionării au fost aleși potrivit ecuațiilor 2.44 și 2.45. Se observă că în domeniul parametric este necesar un număr mare de eșantioane comparativ cu imaginea originală.

Tabelul 2.1 : Parametrii liniei corespunzând figurii 2.3

Tabelul 2.2 : Parametrii de eșantionare corespunzând figurilor 2.3 și 2.4

Acum sunt schimbați parametrii de eșantionare. În primul rând, parametrii de eșantionare corespunzători domeniului discret al parametrilor, prezentat în figura 2.5, nu respectă ecuațiile 2.44 și 2.45. Aici a dispărut vârful corespunzător liniei numărul trei. În al doilea rând, în figura 2.6 este ilustrat un domeniu discret al parametrilor, unde parametrii de eșantionare sunt setați pentru a mări aria parametrilor linie numărul cinci.

În continuare domeniul discret al parametrilor, care folosește interpolarea liniară și interpolarea sinc, este expus în zona liniei cinci. Din figura 2.6 se poate observa că aproximarea celui mai apropiat vecin, conduce, de fapt, la formarea unui vârf, deși este de o formă oarecum diferită comparativ cu vârfurile găsite în figurile 2.7 și 2.8, care se aseamănă. Încă o dată, pentru acest exemplu, s-a găsit că valoarea vârfului este mai scăzută când se folosește interpolarea liniară.

Evaluarea rezultatului ar trebui să conțină și timpul folosit pentru a calcula domeniile celor trei parametrii, ca în tabelul 2.4. Complexitatea acestor trei aproximări sunt date astfel :

(2.49)

și arată la fel cu cele din ecuația 1.36. Din nou se poate observa că interpolarea liniară este puțin mai lentă decât interpolarea celui mai apropiat vecin.

Toate programele au fost implementate în C, și pentru primii doi algoritmi, codul a fost optimizat și implementat cum s-a descris mai jos algoritmul 1.1. Diferența majoră găsită în tabelul 2.4, din primii doi algoritmi până la 1500 secunde folosită cu interpolarea sinc, apare din două motive. În primul rând, aproximarea sinc necesită o funcție sinc, care trebuie să fie calculată o dată pe iterație. În al doilea rând, primi doi algoritmi au, conform ecuației 1.36, un cost de calcul mai scăzut, în comparație cu strategia interpolării sinc, după cum arată ecuația 2.49.

Tabelul 2.4 : Timpul necesar pentru calcularea transformatei Radon discrete pentru trei tipuri de aproximări , corespunzător figurilor 2.6,2.7 și 2.8. Toți timpii sunt măsurați pe un procesor la 120 MHz.

Pentru a vizualiza rezoluția transformatei Radon discrete, figurile 2.9 (cel mai apropiat vecin), 2.10 (interpolarea liniară) și 2.11 (interpolarea sinc) prezintă domeniul parametric într-o arie de vârfuri folosind un nivel prag de 50.

Se poate observa că toate cele trei implementări dau cu aproximație cam aceeași rezoluție, iar rezoluția de pe direcția este puțin peste cea dedusă din ecuația 2.44. Rezoluția pe direcția este aproximativ de cinci ori mai mare decât cea derivată în ecuația 2.45, dar trebuie observat că această limită a fost dedusă folosind mai degrabă presupuneri ample.

În figura 2.12, este prezentat domeniul discret al parametrilor în aria liniei trei, din tabelul 2.1, folosind aproximarea celui mai apropiat vecin, iar în figura 2.13 domeniul parametric a fost trunchiat la valoarea de –50 (se observă că linia trei are amplitudinea –1, și deci valoarea de vârf este de aproximativ -63). Se vede că aici rezoluția este sub valoarea dedusă în ecuația 2.44, pe direcția , ceea ce indică din nou că limitarea schimbă rezultatul acestui fel de analize. De asemenea în figura 2.14 se arată aceeași parte a domeniului parametric găsit folosind interpolarea liniară. În figura 2.15 domeniul parametric a fost calculat folosind interpolarea liniară și apoi limitarea la –50 . Este găsită o regiune mică semnificativă, care se așteaptă a fi cel mai înalt nivel de limitare.

2.2.3 Transformata Radon discretă (,) a punctelor

Figura 2.16 arată o imagine cu numai 14 pixeli ce au o valoare diferită de zero. Valoarea întrerupe liniaritatea în partea dreaptă a imaginii. Cei 14 pixeli se întind pe două linii care au aceeași orientare unghiulară, iar în figura 2.17 este ilustrat domeniul discret al parametrilor corespunzător, folosind o aproximare a celui mai apropiat vecin. Parametrii de eșantionare pot fi găsiți în tabelul 2.2. Fiecare din cele 14 puncte sunt reprezentate clar printr-o sinusoidă, și se observă cum liniaritatea transformatei Radon face ca sinusoidele să se intersecteze și vârfurile să fie poziționate corespunzător parametrilor celor două linii suport.

Figurile 2.18 și 2.19 ilustrează domeniul discret al parametrilor găsit folosind interpolarea liniară și respectiv interpolarea sinc. Figura 2.18 prezintă aproximativ același rezultat ca figura 2.17, dar cu sinusoide mult mai netede. O examinare mai atentă a figurii 2.19 arată că fiecare sinusoidă are efecte inelare, rezultând astfel valori nedorite diferite de zero în domeniul parametric cât și de asemenea în ariile unde nu avem sinusoide.

Timpii transformărilor corespunzătoare celor trei aproximări sunt date în tabelul 2.5.

În figura 2.20 este prezentat domeniul discret eșantionat rar folosind aproximarea celui mai apropiat vecin. Parametrii de eșantionare sunt prezentați în partea stângă a tabelului 2.3. Ar trebui observat că vârful superior are o valoare foarte scăzută. Acesta se datorează încălcării criteriului de eșantionare. Se poate vedea de asemenea, că sinusoidele sunt acum întrerupte în anumite unghiuri. Folosirea numai a interpolării liniare, în figura 2.21, impune curbelor să nu se întrerupă, și se remarcă din nou valoarea cea mai scăzută a vârfului superior.

Tabelul 2.5 : Timpul necesar pentru calcularea transformatei Radon discretă pentru cele trei aproximări, corespunzător figurilor 2.17,2.18 și 2.19. Timpi au fost măsurați pe un procesor la 120 MHz.

2.3 Concluzii

A fost definită transformata Radon de forma (,), iar formele discrete au derivat de aici. Au fost analizate ambele forme, și proprietățile de eșantionare au fost deduse și analizate folosind o strategia “sinc expansion”, la fel cu cea din Capitolul 1.

S-a demonstrat, cu scopul de detecție a curbelor, că aproximarea celui mai apropiat vecin este adecvată dacă eșantionarea domeniului parametric este suficient de densă. De asemenea s-a demonstrat că interpolarea liniară ne dă aproximativ același domeniu al parametrilor ca și cel obținut prin interpolarea sinc.

S-a demonstrat că transformata Radon discretă poate detecta linii cu orientare arbitrară, fapt ce nu a putut fi făcut cu transformata Slant Stacking. Acest capitol a fost concentrat pe imagini pătrate și pe orientări ale liniei arbitrare, iar aceasta este o diferență majoră față de rezultatele obținute în Capitolul 1.

CAPITOLUL III

Transformata Hough

Până acum transformata Radon a fost privită ca o aplicație pentru detecția de linii. Două metode diferite de selectarea a parametrilor au dat în mare parte același tip de transformate discrete, și anume, pentru fiecare poziție din domeniul parametric, însumarea valorilor pixelilor de-a lungul liniei din imagine și stocarea rezultatului sumei la o scală adecvată pentru acea poziție.

Dacă imaginea este împrăștiată, de exemplu, o imagine binară cu câțiva pixeli diferiți de zero, cel mai mult timp de calcul se pierde însumându-se zerouri, fapt ce nu contribuie la domeniul parametric. În una din cele mai citate paragrafe din literatura de procesare de imagini, Hough propune o metodă de a încorpora în transmisie cunoștințele anterioare, pentru a reduce costul de calcul. Ideea a fost inițial formulată pentru linii descrise prin pantă și parametru de decalaj (ca și Slant Stacking), dar mulți autori au translatat ideea într-un domeniu de parametrii liniari normali (,). Trebuie menționat că aici apar câteva confuzii în literatură privind legăturile dintre transformata Radon și Hough. Este o problemă de definiție. O opinie comună , care va fi folosită aici pentru a defini transformata Hough, este aceea că transformata Hough întocmește harta pixelilor individuali din domeniul imaginii într-o formă în domeniul parametric, iar transformata Radon transformă o formă din domeniul imaginii într-un singur pixel în domeniul parametric. Ideea principală constă în a transforma fiecare pixel din imagine individual în domeniului parametric.

Din punct de vedere istoric nu este clar ce motivează transformata Hough. Este ca și cum ar fi o idee nouă dar nu este motivată de rezultate ca și cele obținute în paragraful 1.6. Mai târziu s-a observat că transformata Radon și Hough sunt foarte asemănătoare.

3.1. Transformata Hough (p,)

Transformata Hough poate fi obținută din transformata Radon . În ecuația 1.9 s-a obținut că

Ecuația 3.1 exprimă de fapt ceea ce a vrut Hough. Pentru fiecare punct din imaginea g(x*,y*), trasează o linie în planul transformatei, adică, în domeniul parametric. Linia este găsită prin fixarea argumentului ultimei funcții delta la zero:

Ecuația 3.1 enunță că surplusul de încărcătură cu care este actualizat domeniul parametric să fie proporțional cu valoarea funcției g(x*,y*). Aceasta este o alegere naturală, și astfel transformata Hough pe o formă continuă poate fi văzută , conform ecuației 3.1, ca un caz special al transformatei Radon. Dar aceasta este adevărată numai în cazurile continue, și se va demonstra că cele două transformate nu sunt în general identice pentru formele discrete. Se observă că transformata Hough obișnuită este folosită sub o formă discretă.

Ecuația 3.1 motivează o nouă schemă de estimare a domeniului parametric. Din nou pentru a obține reducerea dimensiunii algoritmului y(n), se presupune a fi fixat la yn și asa mai departe. Se observă că sunt folosiți din nou parametrii eșantionării definiți în ecuația 1.12.

Algoritmul 3.1 : Transformata Hough

Set g_hough(k,h)=0 for all (k,h) // se inițializează spațiul Hough

for m=0 to M-1 //pentru toate valorile lui x

for n=0 to N-1 //pentru toate valorile lui y

gvalue=g(m,n) //se stochează în variabile simple

if gvalue0 //considerăm numai pixeli diferiți de zero

for k=0 to K-1 //pentru toate valorile lui p

tau=y(n)-p(k)*x(m) //se calculează

h=round ((tau-tau_min)/delta_tau) //se găsește valoarea corectă

if h0 și h<H //se verifică dacă eșantionul este valid

g_hough(k,h)=g_hough(k,h)+gvalue//se reîmprospătează domeniul parametric

end

end

end

end

end

Algoritmul 3.1 descrie esența transformatei Hough, deși ar trebui observat că cei ce lucrează cu transformata Hough folosesc forma (,). Punctul cheie este acela că pentru pixelii din imagine diferiți de zero și pentru fiecare valoare a lui pk este calculată valoarea , valoare ce este rotunjită cu ajutorul aproximării celui mai apropiat vecin. În cele ce urmează implicațiile acestei strategii vor fi analizate și comparate cu transformata Radon.

Prima problemă constă în compararea complexității de calcul. Presupunând că numai unii dintre pixelii imaginii au valori diferite de zero, atunci complexitatea de calcula a transformatei Hough este dată de ecuația 3.4. Pentru o mai ușoară comparație este repetată prima linie a ecuației 1.36 în ecuația 3.3, ecuație corespunzătoare transformatei Radon discretă folosind cel mai apropiat vecin.

unde indicele r este folosit pentru a indica că trebuie transformat un număr mic de pixeli. Dacă imaginea conține numai pixeli diferiți de zero atunci (M,N)r=1 , iar transformata Hough va fi cea mai rapidă dintre cele două transformate, dar o valoare mai realistică a lui (M,N)r se află între M și MN, fapt ce depinde de structura imaginii. Aceasta indică faptul că majoritatea transformatelor Hough sunt folosite pentru imagini binare, deseori mai puțin dense (multe zerouri și câțiva de unu).

Din nou procedeul descris chiar după algoritmul 1.1 este aplicat pentru a reduce costul de calcul, adică, punerea sub formă continuă a ecuațiilor este rescrisă folosind parametrii discreți.

Dacă aproximarea celui mai apropiat vecin este aplicată, atunci ecuația 1.19 poate fi folosită pentru a determina valoarea lui h, care corespunde parametrilor ce se întind în domeniul parametric discret trunchiat, adică

În algoritmul 3.2 este prezentată o implementare a transformării Hough folosind parametrii (p,) și o aproximare a celui mai apropiat vecin în domeniul parametric, iar pentru optimizare este folosită ecuația 3.8 pentru a se asigura că pixelii sunt în domeniul parametric discret.

Algoritmul 3.2 : Transformata Hough optimizată

set g_hough(k,h)=0 for alll (k,h) //se inițializează spațiul Hough

for m=0 to M-1 //pentru toate valorile lui x

for n=0 to N-1 //pentru toate valorile lui y

gvalue=g(m,n) //se stochează în variabile simple

if gvalue 0 //se consideră numai pixelii ne-nuli

kappa = -x(m)*delta_p/delta_tau //se calculează panta digitală

zeta=(y(n)-x(m)*p_min – tau_min)/delta_tau //se calculează decalajul digital

Se calculează k_min și k_max din ecuația 3.8

For k=k_min to k_max //pentru toate valorile lui p

h=round(kappa*k+zeta) //se găsește valoarea necesară (corectă)

g_hough(k,h)=g_hough(k,h)+gvalue //se reactualizează domeniul parametric

end

end

end

end

În algoritm este folosit faptul că sunt transformați numai pixeli imagine ce au valori diferite de zero. Pentru imagini ne-binare (valori în virgulă mobilă) poate fi aplicată o limitare, dar nivelul de limitare depinde foarte mult de natura imaginii.

3.1.1. Detecția de linie folosind transformata Hough

În figura 3.1 este prezentată o altă imagine artificială ce conține 6 bucăți de linie, iar parametrii linie pot fi găsiți în tabelul 3.1. Figura 3.2 arată domeniul parametric discret corespunzător folosind transformata Slant Stacking discretă. Parametrii eșantionării pot fi găsiți în tabelul 3.2. Pot fi găsite în domeniul parametric discret șase poziții de vârfuri clare marcate la parametrii corecți ai liniei, chiar și așa, unde există disponibile numai segmente de linii. Punctele de început și de final ale segmentelor de linie nu pot fi găsite direct în domeniul parametric, dar o descoperire mult mai interesantă este aceea că acest domeniul găsit folosind transformata Hough, este în acest caz identic cu cel găsit cu transformata Radon discretă. Acest fapt se datorează alegerii parametrilor eșantionării și modului cum calculează cei doi algoritmi indicii discreți.

În ecuația 1.17 se va găsi că

Dacă parametrii eșantionării s-au ales ca fiind =y și min=ymin după cum se sugerase în subparagraful 1.4.4, atunci ecuația 3.9, corespunzătoare transformatei Radon discretă, devine foarte simplă

iar pentru transformata Hough cu aceleași condiții =y și min=ymin, înfățișarea funcției este dată de ecuația 3.6:

rezultat ce este exact cu cel din ecuația 3.10. Deci concluzia interesantă este aceea că folosind parametrii pantă și decalaj, și aproximarea celui mai apropiat vecin, cei doi algoritmi ne dau exact același domeniu al parametrului discret, când alegem =y și min=ymin. Se poate observa că transformata Hough are nevoie de un factor general de multiplicare al lui x pentru a obține aceeași scalare ca și cea a transformatei Radon.

O mare diferență între cei doi algoritmi vine din timpul necesar pentru calculul domeniului parametric discret. Folosind transformata Radon discretă optimizată sunt necesare 0.42 secunde , iar transformata Hough optimizată necesită numai 0.026 secunde, adică, un factor de 16 este în favoarea transformatei Hough. În acest caz numai 3.34% din pixeli sunt diferiți de zero. Ambii timpi sunt măsurați pe un procesor de 120MHz.

Tabelul 3.1 : Parametrii liniei corespunzători figurii 3.1 sunt dați pornind cu punctul de start xstart și terminând cu punctul de final xsfârșit.

Acum parametrii de eșantionare ai domeniului discret sunt schimbați pentru a se focaliza pe două vârfuri. Parametrii de eșantionare sunt prezentați în partea stângă a tabelului 3.3. În figura 3.3 domeniul parametric discret este prezentat folosind transformata Radon discretă, și de asemenea în figura 3.4 folosind transformata Hough.

Se poate observa că folosind transformata Radon discretă sunt găsite clar două vârfuri, exact cum se prevedea în capitolul anterior. Din figura 3.4 se poate observa că transformata Hough nu dă rezultate bune. În primul rând se observă că nivelele sunt foarte reduse. În al doilea rând regiunile parametrilor de linie așteptați sunt slab marcate, deci domeniul parametric este inutil.

În ceea ce urmează se utilizează o eșantionare rară a domeniului parametric în figurile 3.5 și 3.6 corespunzător părții drepte ale tabelului 3.3. Se observă că transformata Radon discretă nu funcționează corespunzător și numai două vârfuri sunt clar marcate. Aceasta este datorită sub-eșantionării domeniului parametric. În contrast cu figura 3.5, figura 3.6 arată cum transformata Hough funcționează corespunzător. Pot fi găsite șase vârfuri, dar de remarcat că rezoluția este scăzută.

3.1.2 Alegerea parametrilor de eșantionare folosind

transformata Hough (p,)

Motivul pentru care transformata Hough nu funcționează când domeniul parametric este eșantionat prea dens, și aparent funcționează bine pe un domeniul parametric eșantionat prost, poate fi investigat pornind de la procedura de cartare folosind aproximarea celui mai apropiat vecin. Din ecuația 3.6 se va vedea că o bandă a punctelor imaginii sunt cartate în același vector parametru.

Rezultatul important este acela că modul de definire a transformata Hough face ca toți pixelii ce se află în jurul liniei (digitale) n=m+ într-o bandă de lățimea , măsurată în pixeli pe direcția n, vor fi cartați în același punct, (k,h), în domeniul parametric discret. Aceasta explică rezultatele din figurile 3.4 și 3.6. Folosirea unui domeniu parametric eșantionat des, cu, de exemplu , implică faptul ca lărgimea de bandă din domeniul imagine semnifică numai 1/10 dintr-un eșantion, deci dintr-un punct de vedere statistic, numai fiecare al zecelea pixel de-a lungul liniei digitale contribuie la domeniul parametric discret, și un domeniu parametric discret eșantionat rar, cu, de exemplu , implică faptul că pentru un punct dat din domeniul parametric, și o anumită valoare xm. vor contribui cinci pixeli la aceeași poziție în domeniul parametric, dacă valoarea lor este diferită de zero. Dacă nu este cunoscută nici o informație apriori a imaginii, concluzia este că o valoare rezonabilă a distanței de eșantionare a lui este .

Folosind transformata Hough cu un domeniul parametric eșantionat grosolan poate face ca pixelii să nu aibă nevoie de o linie perfectă, și totuși rezultatul să fie un vârf în domeniul parametric. Pentru transformata Radon implicațiile ulterioare și limitările vor fi discutate mai târziu.

S-a arătat mai sus că transformata Hough necesită ca să nu fie foarte mic. Parametrul p poate fi ales folosind diferite criterii. Un criteriu este cel prin care panta (digitală) absolută a liniei din ecuația 3.6 nu depășește 1, pentru a evita ca un pixel din imagine să fie cartat într-o linie discontinuă din domeniul parametric discret, după cum arată figurile 3.7 și 3.8. Această problemă de perforare poate face ca vârful să nu fie găsit în domeniul parametric discret.

Se observă că dacă alegem , această limitare se potrivește ecuației 1.32 derivate pentru transformata Radon (p,) discretă

.

3.2 Transformata Hough (,)

Transformata Hough poate fi definită folosind parametrii normali (,) iar ecuația 2.16 poate explica definiția transformatei Hough

și astfel sensul transformatei Hough este că fiecare punct din imagine este transformat într-o sinusoidă în domeniul parametric discret, și în algoritmul 3.3 este prezentată transformata Hough folosind parametrii (,). Cea mai simplă implementare distribuie valoarea pixelului pentru fiecare valoare a lui t . În cele ce urmează imaginea este presupusă patrulateră, conform ecuațiilor 2.24 și 2.25, și sunt folosiți parametrii de eșantionare definiți conform ecuației 2.23.

Algoritmul 3.3 : Transformata Hough (,)

set g_hough(r,t)=0 for all (r,t) //se inițializează spațiul Hough

for m=0 to M-1 //pentru toate valorile lui x

for n=0 to N-1 //pentru toate valorile lui y

gvalue=g(m,n) //se stochează valoarea într-o variabilă simplă

if gvalue0 //se iau în calcul numai pixelii nenuli

for t=0 to T-1 //pentru toate valorile lui θ

rho=x(m)*cos(theta(t))+y(n)*sin(theta(t)) //se calculează ρ

r=round((rho-rho_min)/delta_rho) //se găsește eșantionul corect

if ro and r<R //se verifică dacă eșantionul este valid

g_hough(r,t)=g_hough(r,t)+gvalue //se update-ează domeniul parametric

end

end

end

end

end

Acest algoritm este valid, dar totuși necesită o mulțime de verificări a părții din interiorul buclei, unde este un calcul suplimentar, și deci pentru a fi eficient ar trebui optimizate câteva părți. Acest fapt este arătat în subparagraful 3.2.2.

3.2.1 Alegerea parametrilor de eșantionare folosind

transformata Hough (,)

Urmărind procedura prezentată în subparagraful 3.1.2, este găsită o expresie similară pentru cartarea celui mai apropiat vecin

fapt ce arată că transformata Hough cartează toți pixelii din imaginea care se întind pe o lățime de bandă de în același punct din domeniul parametric discret. Banda este măsurată în pixeli perpendiculari pe linie. Aceasta arată faptul că a fost ales suficient de larg, dar nu sub x, adică,

În legătură cu alegerea lui , ar trebui evitat ca un pixel din imagine să fie cartat într-un sinusoidă întreruptă. Folosind o aproximare de prim ordin rezultă:

În figura 3.9 este prezentată o imagine cu cinci pixeli diferiți de zero, iar în figura 3.10 transformata Hough corespunzătoare. Parametrii de eșantionare au fost setați din ecuația 3.21 folosind numai T=50, ceea ce implică ca în ecuațiile 3.22 și 2.30 să avem T=142.

Se poate observa că transformatele discrete Hough și Radon dau aceleași rezultate în cazul (p,), dar în cazul (,) rezultatele vor fi întotdeauna diferite. Acest fapt reiese evident din modul de eșantionare al domeniului parametric discret ce trebuie ales.

3.3 Concluzii

S-a arătat că transformata Hough (p,) poate fi definită într-un mod care ne dă exact același domeniu discret al parametrului găsit cu aproximarea celui mai apropiat vecin cu ajutorul transformatei Radon discrete. Transformata Hough (,) nu are aceleași proprietăți.

De asemenea se observă că transformata Hough se comportă diferit când schimbăm intervalele de eșantionare din domeniul discret al parametrului, în comparație cu transformata Radon discretă.

CAPITOLUL IV

Algoritmul FCE (de estimare rapidă a curbei)

O problemă recurentă în procesarea imaginii pe calculator, este identificarea curbelor cu forme specifice. După cum s-a arătat în capitolele anterioare, transformata Radon este o aplicație dintr-un domeniu al imaginii într-un domeniu parametric, parametrii ce caracterizează curbele de identificat.

Transformata Radon generalizată convertește o problemă dificilă de detecție globală din domeniul imaginii, într-o problemă mult mai ușoară de detecție a vârfurilor locale în domeniul parametric.

În ultimii ani, s-au făcut progrese în a înțelege și în a mări viteza transformării Radon generalizate. Investigațiile privind atât transformata Radon tradițională cât și cea generalizată mai recent pentru schemele de identificare a curbei, subliniază două probleme cu atenție la costul de calcul. În primul rând, schemele de estimare nu pot exploata punctele din imagine cu valoare zero, și în al doilea rând, estimarea este scumpă din punctul de vedere al calculului. Baza pentru estimarea parametrilor curbei este o imagine binară. Aceasta poate fi generată în mai multe moduri, cum ar fi filtrarea marginii, deconvoluția, sau refacerea câmpului median. În acest capitol se va prezenta algoritmul de estimare a curbei, numit FCE. Ideea cheie a acestui algoritm este de a pre-condiționa domeniul parametric, creând zone neregulate corespunzătoare regiunilor parametrilor de interes. Mai mult, acest algoritm face ca pixelii cu valoare zero să genereze harta de pre-condiție. Inițial, algoritmul FCE identifică zonele domeniului parametric care conțin vârfuri reprezentând curbe în imagine. Ulterior acest algoritm estimează o transformată Radon generalizată în interiorul acestor regiuni.

4.1 Transformata Radon generalizată

Fie g(x, y) un semnal continuu, cu x și y variabile continue, și fie un vector de dimensiune , definit astfel:

= (1, 2, …, ) (4.1)

4.1.1 Transformata Radon generalizată continuă

Transformata Radon generalizată poate fi definită în mai multe moduri. O formă generală este:

(4.2)

Folosind definiția dată de ecuația (4.2), pot fi detectate forme exprimate prin . Fie transformata Radon generalizată continuă a funcției g(x, y), definită aici astfel:

(4.3)

unde reprezintă curba de transformare. Transformata Radon generalizată este integrarea lui g(x, y) de-a lungul curbei de transformare.

Ecuația 4.3 poate fi interpretată ca o generalizare a tehnicii „Slant Stacking” descrisă în capitolul 1. De remarcat la această ecuație este faptul că permite curbelor să aibă doar o singură valoare y pentru fiecare x și parametru . Deci se exclud curbele închise cum sunt cercurile.

Curba de detectat este acum modelată utilizând o funcție delta urmând forma curbei.

(4.4)

deci transformata Radon generalizată este dată de:

(4.5)

(4.6)

(4.7)
Ecuația 4.7 arată că transformata Radon generalizată va da un vârf infinit când =*, iar domeniul parametric va conține câteva valori diferite de zero, în funcție de valoarea lui I și de funcția actuală . Ecuația arată, de asemenea, că transformarea eșuează când panta curbei este infinită. În concluzie, ecuația 4.3 este completă pentru curbe ca parabole, hiperbole, și alte curbe parametrizate cu pantă limitată.

4.1.2 Transformata Radon generalizată discretă

Fie j vectorul parametrului discret de dimensiune , definit astfel:

j = (j1, …, ji, …j ) (4.8)

Corespondența dintre vectorul j și versiunea eșantionată a vectorului parametrului, notată j, poate fi scrisă:
= j = θ (j), unde j = θi(ji) (4.9)

unde θi(ji) este o funcție de eșantionare a parametrului.

Dacă se alege o eșantionare uniformă a domeniului parametric, atunci funcția θi poate fi scrisă:
j = θi(ji) = i,min + ji i, ji = 0,…, Ji – 1 (4.10)

unde i,min reprezintă limita inferioară, iar i intervalul de eșantionare al lui i.

Eșantionarea domeniului parametric și a domeniului imaginii se presupune a fi uniformă, ca în ecuația 1.12, adică:

(4.11)

(4.12)

Substituția ecuațiilor 4.9, 4.11 și 4.12 în curba de transformare dă:

(4.13)

Utilizând o aproximare a celui mai apropiat vecin în ecuația 4.13, curba de transformare discretă a indexului (m;j) poate fi exprimată astfel:

(4.14)

Fie g(m, n) versiunea discretizată a semnalului g(x, y), adică g(m, n)= g(x, y), și fie transformata Radon generalizată discretă (GRT) a lui g(m, n), definită ca:

(4.15)

Se observă că termenul dx a fost omis în cadrul transformatei Radon generalizate discrete, deoarece este o constantă datorită eșantionării uniforme a lui x. Dacă transformata Radon generalizată discretă aproximează cantitativ ecuația 4.3, atunci ecuația 4.15 trebuie multiplicată cu .

Folosirea rotunjirii în locul interpolării liniare, de pildă, nu are efecte problematice când se folosește o eșantionare eficientă a domeniului parametric, iar schemele de interpolare pot fi ușor incluse în ecuațiile 4.14 și 4.15.

4.2 Maparea punctului imaginii (IPM)

Prima parte a ecuație 4.3 poate fi folosită la definirea unui alt mod de estimare al domeniului discret al parametrilor.

(4.16)

unde reprezintă funcția delta Kronecker.

Ecuația 4.16 arată că fiecare punct al imaginii (m, n) este transformat într-o curbă unde . Astfel, maparea punctelor cu valoare zero este inutilă atât timp cât nu contribuie la . Schema de estimare a transformatei Radon propusă, lămurește faptul că valorile nule ale imaginii nu contribuie și nu sunt incluse în suma din ecuația 4.16. Aceasta are posibilitatea de a reduce considerabil costul calculului.

Presupunând că este inversabilă, avem:
(4.17)

Mai mult, presupunând că funcția de eșantionare θ este inversabilă, avem:

(4.18)

Ecuațiile 4.16 și 4.18 sunt baza pentru schema de estimare a transformatei Radon generalizate. Pașii cheie pentru maparea punctului imaginii (IPM) sunt:

a) , oricare ar fi j

b) pentru toate punctele imaginii g(m,n) cu valori diferite de zero

Se observă că algoritmul IPM este o transformare Hough generalizată, care a fost extinsă pentru a cuprinde un set mai larg de curbe de transformare neliniare. Ca și la transformata Hough, obiectivul pentru algoritmul IPM este identificare parametrului, transformând fiecare pixel al imaginii într-un domeniu parametric.

Una din diferențele fundamentale dintre transformata Radon generalizată și IPM, este aceea că transformata Radon generalizată necesită rotunjire în domeniul imaginii, pe când IPM rotunjește în domeniul parametric, după cum se vede și în figurile de mai jos:

Domeniul imaginii g(m,n) Domeniul parametric

Figura 4.1. a): Rotunjirea făcută de transformata Radon generalizată în domeniul imaginii corespunzând unui punct din domeniul parametric

Domeniul imaginii g(m,n) Domeniul parametric

Figura 4.1. b): Rotunjirea făcută de algoritmul IPM în domeniul parametric corespunzând unui punct din domeniul imaginii

Complexitatea calculului în cele două cazuri:
(4.19)

unde (MN)r indică faptul că sunt transformate doar un număr redus de puncte nenule. În ecuația 4.19 costul testării valorilor nenule este considerat neglijabil. Avantajul major al algoritmului IPM este capacitatea de a nu ține seama de punctele imaginii cu valori nule.

4.3 Eșantionarea domeniului parametric

Pentru o imagine dată g(m, n), în general nu este posibilă o determinare exactă a lui , i,min și Ji . Totuși pot fi stabilite câteva linii de ghid. Mai întâi, o parte din parametrii vor fi mărginiți de fizica fundamentală. Apoi domeniul parametric poate fi limitat cerând ca măcar o fracție din punctele imaginii să se afle în imagine, adică:

(4.21)

unde este egala cu 1 când expresia logică este adevărată, și 0 în rest.

În ceea ce privește utilizarea transformatei Radon generalizate, intervalul de eșantionare poate fi ales solicitând ca

(4.22)

Unde i este un vector de dimensiune ce conține zerouri la toate intrările, cu excepția intrării i care este .

Ecuația 4.22 arată că doi vectori adiacenți dă valori ce nu pot fi separate de mai mult de un eșantion în direcția y. Acest criteriu de proiectare nu este optim atât timp cât conduce la o eșantionare densă inutilă a anumitor părți din domeniul imaginii, deși poate fi folosit ca o limită superioară a ratei de eșantionare. Mărind rata de eșantionare a domeniului parametric peste o anumită limită, nu va îmbunătăți rezoluția obținută de transformata Radon generalizată atât timp cât vectorii adiacenți j vor rezulta în aceeași curbă . Pentru transformata Radon generalizată, o eșantionare de proastă calitate nu garantează că se va detecta o curbă dorită, datorită faptului că nici o curbă de transformare (m; j) nu poate garanta urmărirea perfectă a curbei imaginii.

4.4 Algoritmul de estimare rapidă a curbei (FCE)

Se consideră o imagine în care valorile sale sunt reprezentate prin valori continue. Această imagine poate fi mapată într-o imagine binară g(m, n), de exemplu prin filtrarea marginilor, prin deconvoluție sau prin normalizarea câmpului median. Algoritmul propus estimează parametrii curbelor din imaginea binară g(m, n).

Este bine știut că utilizarea directă a transformatei Radon generalizate este costisitoare din punctul de vedere al calculului. În lumina caracteristicilor transformatei Radon generalizate, se propune un algoritm de estimare rapidă a parametrilor curbei, și anume algoritmul FCE, care estimează simultan toți parametrii curbelor cu o formă specifică, cum ar fi liniile sau hiperbolele.

Acest algoritm presupune:
a) proiectarea domeniului discret al parametrului, adică alegerea lui i,min, Ji și

b) proiectarea unui domeniu redus al parametrului pentru algoritmul IPM, alegând

(4.26)

Unde rotunjește la cel mai apropiat întreg superior, iar vi este un întreg raportat la reeșantionare. Apoi se utilizează algoritmul IPM pentru a estima :

(4.27)

c) utilizarea funcției de prag T:
(4.28)

Funcția de prag T este menită să îndepărteze toate combinațiile nesemnificative ale parametrilor, iar o alegre potrivită poate fi:
(4.29)

unde M reprezintă numărul liniilor din imagine, 1 este o fracție care definește nivelul important, iar este funcția treaptă Hamilton.

d) reeșantionarea domeniului parametric pentru a obține . Procesul de reeșantionare poate fi scris astfel:
(4.30)

Acesta completează repede întregul domeniu parametric unde zonele de interes au valoare 1, în timp ce restul au valoare 0.

e) utilizarea transformatei Radon generalizate în zonele domeniului parametric unde .

(4.31)

f) utilizarea funcției de prag cu un nivel nou 2 pentru a justifica folosirea transformatei Radon generalizate. După aplicarea funcției de prag, toate punctele din domeniul parametric cu valori nenule reprezintă parametrii curbei.

g) gruparea parametrilor identificați în curbe ale imaginii comune.

Procesul de reeșantionare ia fiecare punct al parametrului corespunzător intervalului de eșantionare , și îl extinde câtorva puncte corespunzătoare intervalului de eșantionare , .

Nivelele importante 1 și 2 trebuie să fie alese astfel încât să reflecte valorile domeniului parametric, șipot fi acceptate ca vârfuri corespunzătoare curbelor din imagine.

4.5 Concluzii

A fost prezentat un nou algoritm de estimare rapidă a parametrilor curbei, numit FCE. Acest algoritm identifică parametrii curbei operând pe o imagine binară obținută, de exemplu prin filtrarea marginii, deconvoluție sau refacerea câmpului median.

Ideea fundamentală a algoritmului este folosirea pre-condiționării pentru a reducere costul calculului transformatei Radon generalizate tradiționale. Planul de pre-condiționare stabilește zonele domeniului parametric care conține vârfuri, iar transformata Radon generalizată este aplicată doar în aceste regiuni. Dacă dimensiunile zonelor sunt mai mici decât întregul domeniu parametric, atunci harta de pre-condiționare reduce costul calculului când se aplică transformata Radon generalizată. Pentru o generare mai rapidă a hărții de pre-condiționare, s-a dezvoltat o generalizare a transformatei Hough numită maparea punctului imaginii (IPM). Maparea punctului imaginii este eficientă din punctul de vedere al calculului, luând în considerare punctele cu valoare nulă.

Algoritmul FCE (de estimare rapidă a curbei) a fost aplicat cu succes în identificarea hiperbolelor din imaginile seismice.

CAPITOLUL V

Estimarea parametrilor de linie

în imagini afectate de zgomot

Până acum s-a presupus că liniile sunt drepte, în interiorul rezoluției digitale din imagini. Un semn de întrebare apare privitor la situația în care liniile sunt șerpuite. În subcapitolul 5.1 se analizează dacă transformata Radon liniară discretă încă poate fi folosită la detectarea parametrilor liniei. Sunt date expresii analitice pentru a cuantifica teoria.

În subcapitolul 5.2 se arată faptul că liniile șerpuite pot fi integrate în transformata Radon, și se mai arată de asemenea, că modificarea poate fi transformată înapoi în imaginea originală, ca un filtru neliniar simplu.

În final, în subcapitolul 5.3 sunt analizate implicațiile zgomotului aditiv în imagine, cu atenție la detectarea parametrilor liniei. Aici este presupusă o formă foarte amplă a transformatei Radon generalizate, iar teoria este ilustrată în cazul transformatei Radon liniare. Sunt obținute formule simple, cuantificând dacă o curbă poate fi detectată sau nu, în cazul unei imagini afectate de zgomot.

5.1 Linii șerpuite

Se presupune că linia digitală din imagine poate fi modelată de :

(5.1)

unde δ(.) este funcția delta Kronecker, și [.] se învârte în jurul celui mai apropiat întreg.

Termenul zgomotului λ, distribuit Gaussian, determină schimbarea în poziție a liniei, în direcția y, și se presupune că acești termeni λ ai zgomotului nu sunt corelați, în funcție de m. Constantele α* și β* corespund valorilor pantei actuale și decalajului ca în relațiile: , .

Interesant acum este găsirea valorii și formei vârfului în domeniul discret al parametrilor, ca o funcție a zgomotului deviat σ. Probabilitatea eșantionului g(m, n) este 1, este dată de:

(5.2)

(5.3)

(5.4)

Presupunând că punctul de eșantionare (m, n) este dat de cartarea celui mai apropriat vecin în transformarea Radon discretă, n=[αm+β], funcția de rotunjire este modelată ca un termen de zgomot aditiv ω.

(5.5)

(5.6)

,unde (5.7)

(5.8)

unde Φ(.) este funcția de probabilitate Gaussiană, și ζ este o deplasare între parametrii liniei reale (α*, β*), și parametrii (α, β) la o poziție m dată.

Datorită multelor valori ale lui m utilizate în transformata Radon discretă, o aproximare rezonabilă este de a modela ω ca o variabilă uniform distribuită între limitele –1/2 și 1/2 , adică ωmU(-1/2 , 1/2). Din ecuația 5.8 rezultă că, contribuția medie a pixelului g(m, n) la transformarea Radon discretă, este dată de :

(5.9)

(5.10)

Cu scopul de a obține o expresie analitică pentru , funcția de probabilitate Gaussiană este aproximată astfel:

, unde (5.11)

adică, integrală din Φ(.) poate fi aproximată de

(5.12)

Dacă ecuația 5.12 este inserată în ecuația 5.10, și se face o rearanjare a expresiilor, se găsește că :

(5.13)

În figura 5.1 ponderea medie a transformatei Radon discrete este prezentată ca fiind o funcție de σ și ζ.

(5.14)

În figura 5.2 ponderea medie a transformatei Radon discrete este prezentată ca fiind o funcție de σ, unde deplasamentul este presupus neglijabil. Se poate observa că funcția se potrivește bine cu rezultatul simulat ilustrat în figura 5.3, lucru găsit generând 10000 de imagini cu amplitudinea σ a zgomotului corectă, și estimând transformata Radon discretă doar pentru setul de parametrii care se potrivesc cu parametrii reali.

Figura 5.1: Ponderarea medie a transformatei Radon discrete ca o funcție de derivare a zgomotului σ pe prima axă, și deplasare ζ

Figura 5.2 sau ecuația 5.14 poate fi folosită să prevadă dacă parametrii liniei pot fi estimați, liniile fiind șerpuite. În figura 5.4 este ilustrată o imagine cu o linie fără zgomot, iar în figura 5.5 este prezentat domeniul discret al parametrilor în zona vârfului. Folosind aceeași parametrii de eșantionare, figura 5.6 arată o imagine unde σ=0.25, iar figura 5.7 ilustrează domeniul discret al parametrilor corespunzător. Imaginile sunt scalate individual în concordanță cu valorile minime și maxime, și se poate observa că valoarea maximă aici este în jurul lui 80, iar forma este aproximativ la fel ca cea din figura 5.5. Apoi, σ=0.5 dă o imagine ca cea prezentată în figura 5.8, și se poate vedea că nivelul zgomotului este ridicat. În figura 5.9 se observă domeniul discret al parametrilor, și se poate observa că aici, vârful acoperă o parte mare a câmpului vizual, și este cumva împrăștiat.

Ecuația 5.13 poate fi analizată și în cazul când σ=0, cu scopul de a ne concentra atenția la importanța deplasamentului.

(5.15)

unde (p*, *) sunt parametrii liniei corespunzători lui (α*, β*), iar (pk, h) corespund lui (α, β).

Presupunând p*=pk, se poate analiza deplasamentul în direcția τ. Din figura 5.2 se vede că corespunde lui , adică valoarea vârfului a scăzut cu aproximativ 50% față de valoarea maximă posibilă. Acest lucru se poate folosi pentru a restrânge intervalul de eșantionare Δτ , datorită cuantizării lui h:

(5.16)

Acest rezultat este în concordanță cu ecuația 1.31, însă aici rezultatul vine cu o informație importantă: utilizarea ecuației 1.31 poate duce la reducerea valorii vârfului cu 50 % față de maximul posibil. Astfel se ajunge la un compromis între numărul eșantioanelor domeniului discret al parametrilor, adică intervalele de eșantionare, și timpul necesar pentru calculul domeniului discret al parametrilor.

Trebuie menționat că poate fi propus un model simplu și intuitiv de analiză în cazul ζ=0, dar rezultatele nu sunt la fel de bune ca cele obținute de modelul descris anterior. Transformata Radon discretă va corespunde rotunjirii având o fereastră în direcția n, cum este arătat în figura 5.12, cu lungime 1. Deci, presupunând că decalajul ω este neglijabil, atunci probabilitatea detectării unui 1 este dată de :

(5.17)

care poate fi interpretată ca un factor de reducție a vârfului. Probabilitatea este arătată ca fiind o funcție de σ în figura 5.13.

Concluzia acestui subcapitol este aceea că un vârf este generat în domeniul discret al parametrilor corespunzător fiecărei linii din imagine, și valoarea vârfului va fi micșorată corespunzător nivelului de zgomot, care în acest caz se datorează șerpuirii.

5.2 Transformata Radon a unei imagini neclare

În locul utilizării pozițiilor pixelului desemnate de transformata Radon discretă, poate fi folosită o strategie de căutare, pentru a integra linii șerpuite în algoritmul de detecție a curbei. Presupunând că liniile sunt șerpuite ca în figura 5.1, o strategie pentru a integra informația precedentă, poate permite transformatei Radon discrete să caute valoarea maximă a imaginii într-o fereastră dată.

Strategia este demonstrată pentru transformata Slant Stacking discretă, dar poate fi adaptată, de pildă la transformata Radon normală sau la transformata Radon generalizată discretă. Presupunând că amplitudinea curbei este pozitivă și zgomotul aditiv deformează imaginea, figura 5.14 arată cum este folosită o fereastră de căutare cu 5 pixeli, pentru fiecare valoare m pe axa orizontală. În fereastră o strategie aparentă este folosită pentru a reactualiza suma din transformata Radon discretă prin maximul celor 5 pixeli.

Pe lângă asta, această strategie implică o creștere mare a timpului de procesare în comparație cu utilizarea transformatei Slant Stacking discrete, și nu este optim datorită faptului că, această strategie este identică cu filtrarea imaginii de început cu un filtru median pentru fiecare valoare a lui m. Filtrul ar trebui să returneze maximul pixelilor din fereastră, deci strategia este echivalentă cu o filtrare a domeniului inițial al imaginii și apoi a transformatei Slant Stacking discrete. Aceasta arată că modificarea nu ar trebui să fie folosită, ci doar filtrarea locală, dacă filtrul maxim poate selecta pixelul corect din fereastră.

Următoarele 6 figuri ilustrează problema strategiei. Figura 5.15 este o imagine cu zgomot, conținând 2 linii care se intersectează, iar figura 5.16 prezintă transformata Radon discretă corespunzătoare. Sunt foarte clar marcate două vârfuri. Apoi figura 5.17 arată imaginea, unde, pentru fiecare valoare a lui m, a fost folosit un filtru maxim cu lățimea ferestrei de 3 pixeli. Figura 5.18 prezintă transformata Radon discretă corespunzătoare, și se poate observa că vârfurile sunt totuși detectabile, dar rezoluția s-a înrăutățit. În final, figurile 5.19 și 5.20 folosesc o fereastră de filtrare de lungime 5, și rezultatul este mai neclar în ceea ce privește vârfurile, și de aceea nivelul fundalului în domeniul discret al parametrilor s-a mărit.

5.3 Detecția curbelor în imaginile afectate de zgomot

O extindere naturală a transformatei Radon este transformata Radon generalizată (GRT). Un avantaj major al GRT este acela că, curbele se pot intersecta. Alt avantaj major care va fi prezentat în cele ce urmează, este acela că GRT este foarte robust la zgomot.

În acest subcapitol, este utilizată o aproximare probabilistică pentru a arăta că GRT poate fi folosită pentru detecția curbei, dacă zgomotul din imagine este sub un anumit nivel comparat cu valorile semnalului pe curbe. Este dată o expresie analitică cuantificând limitele folosirii GRT pentru detecția curbei, în special la imaginile cu mult zgomot. Dacă zgomotul este adăugat unei imagini ce conține curbe, problema este că vârfurile din domeniul parametric pot corespunde sau nu parametrilor actuali ai curbei. Este derivat și aplicat un nivel de prag, bazat pe nivelul zgomotului, pentru separarea zgomotului de informațiile privitoare la curbă în domeniul parametric.

5.3.1 Transformata Radon Generalizată

Transformata Radon Generalizată a unei imagini digitale poate fi definită în mai multe feluri:

(5.18)

unde reprezintă transformata Radon generalizată a imaginii g(m, n), iar j este un vector multidimensional care conține parametrii curbei. Cele două funcții ale curbei Φm(l,j) și Φn(l,j) definesc tipul curbei și sunt, în general, arbitrare, și este presupusă implicit o schemă de interpolare, de exemplu prin rotunjirea funcțiilor Φm(l,j) și Φn(l,j) la cel mai apropiat punct eșantionare. O binecunoscută alegere sunt funcțiile liniare ale curbei; de exemplu parametrii normali j = (p, θ). O altă alegere frecventă sunt parametrii (τ, p), unde Φm(l,τ,p) = l și Φn(l,τ,p) = pl + τ.

Cu toate că GRT poate fi aplicată la orice imagine dată, trăsătura principală a GRT este aceea că o imagine care conține o curbă discretă care se potrivește cu funcțiile curbei la un parametru j implică faptul că domeniul parametric (j) va prezenta un vârf la un vector specific al parametrului j = j. Liniaritatea transformatei GRT implică faptul că fiecare curbă din imagine va fi transformată într-un vârf. Inițial vor fi considerate doar două valori ale transformatei GRT. Prima, , corespunde unei curbe din imagine. Cealaltă, , corespunde unui vector al parametrului. Se presupune că, este suma valorilor medii ale semnalului pentru toate eșantioanele L, iar nu acoperă eșantioanele din imagine. Ambele valori ale lui sunt afectate de zgomot, fapt cauzat de zgomotul din imagine.

5.3.2 Detecția curbei folosind transformata Radon generalizată

Un algoritm clasic de detecție a curbei, este de a determina vectorii parametrului din pozițiile vârfurilor din spațiul parametrilor.

(5.19)

Datorită liniarității, ğ este constituit dintr-o curbă și zgomot. Dacă L>>1, suma termenilor zgomotului ğnoise va fi distribuită aproximativ Gaussian cu media zero și varianța Lσ, conform Teoremei limitei centrale. Aceasta implică că cele 2 valori considerate pentru transformata GRT, sunt distribuite ca și .

Un rezultat important este probabilitatea detectări vectorului corect al parametrului ale celor două considerente

(5.20)

Se presupun două variabile necorelate :

și (5.21)

de aici avem funcția de distribuție a probabilității care este dată de:

(5.22)

Probabilitatea va fi găsită prin rotirea coordonatelor sistemului și . În noile coordonate funcția densitate de probabilitate este dată de :

(5.23)

(5.24)

Cele două integrale pot fi separate, și se găsește că :

(5.25) unde err(x) este funcția eroare.

Intersectând μA= μL, μB=0 și înlocuind σ cu σ avem :

și (5.26)

Aflăm că în acest caz P, prezentat în figura 5.21, depinde doar de λ. Dacă obținem o detecție aproape sigură. Apoi rezultă că σ0 sau μ.

Când folosim GRT pentru a detecta curbe, domeniul discret al parametrilor va avea nu doar 2, ci chiar I vectori diferiți, unde I este numărul eșantioanelor din domeniul parametric. Se presupune că toate sursele ce produc zgomot în domeniul parametric sunt independente, fiind analizată detecția unei singure curbe. Selectând poziția celui mai înalt vârf din domeniul parametric, probabilitatea de a selecta un vector corect, se poate aproxima cu :

(5.27)

Ultima aproximare simplă este bună dacă probabilitatea de detecție este aproape 1 cum putem observa în figura 5.22. Dacă se cere o probabilitate mare a detecției P, atunci ecuația 5.27 și figura 5.22 demonstrează că I ar trebui să fie mic, adică să reducă numărul de eșantioane din domeniul parametric la minim.

Ecuația 5.27 poate fi folosită și pentru a detecta nivelul mediu absolut al semnalului μ pentru curbele de detectat. Având o probabilitate de detecție P mai mare decât P implică faptul că μ = σ/(λ), unde λ poate fi găsit din ecuația 5.27 cu o probabilitate de detecție dată, lungimea sumei L, numărul de eșantioane din domeniul parametric I, și deviația standard σ. Orice mai mic decât nivelul pragului μ, poate fi considerat zgomot.

5.3.3 Un exemplu de detecție a unei linii dintr-o imagine afectată de zgomot

Se creează o imagine fără zgomot care conține 8 linii cu pantă limitată. Imaginea din figura 5.23, are 101*101 eșantioane. Funcțiile curbei de eșantionare sunt alese la :

Φm=l-50, Φn=p(l-50)+τ și L este setat la 101. Decalajul este făcut pentru a micșora cerințele eșantionării în domeniul parametric. Distanțele de eșantionare din domeniul parametric sunt Δτ=1 și Δp=0.01.

Parametrii liniei sunt afișați în tabelul 5.1 :

Tabelul 5.1: Parametrii liniei – p este panta, este decalajul și este amplitudinea curbei

Pentru a vedea potențialul transformatei Radon generalizate, se generează o imagine afectată de foarte mult zgomot, prin adăugarea zgomotului Gaussian la imaginea fără zgomot de medie nulă și abatere σ=1. Putem observa din figura 5.24 că liniile sunt greu de identificat. Alegând P=0.95, din ecuația 5.27 rezultă Lμ=65.7, adică numai liniile cu sunt detectabile. Deci numai linia numărul opt nu este detectabilă. În figura 5.25 este ilustrată valoarea absolută a domeniului parametric obținută prin aplicarea transformatei Radon generalizate imaginii afectate de zgomot.

Atât timp cât imaginea afectată de zgomot conține câteva linii cu amplitudine absolută , cu același ordin de mărime ca și σ și cu media aproximativ zero, σ a fost estimat din imagine folosind estimatorul normal central de varianță, ce dă . Setând Pdet all la 0.95, din ecuația 5.27 rezultă L*=65.7. Acesta este folosită pentru pragul domeniului parametric, cum este arătat în figura 5.26. Șapte din cei 8 parametrii ai liniei sunt găsiți în ciuda raportului semnal zgomot mic din imagine. De remarcat că unele dintre linii vor fi reprezentate de câțiva vectori vecini ai parametrilor, ce pot fi corectate prin gruparea vectorilor parametrilor din apropiere. Eroarea este cauzată de eșantionarea domeniului parametric și mărimii finite a imaginii.

Teoria a prezis că doar 7 linii pot fi detectate. Cea de-a 8-a linie poate fi detectată dacă poate fi mărită lungimea curbei sau dacă poate fi redusă varianța zgomotului. Dacă teoria e folosită cu P foarte mic, Lμ se micșorează și vârfurile zgomotului vor apărea în domeniul parametric împreună cu parametrii celei de-a 8-a linie. În figura 5.27 a fost redus nivel pragului la 0.7L μ=46. După cum se poate observa, zgomotul va da vectorii parametrilor care nu reprezintă o curbă. În figura 5.28 se poate remarca o reducere în plus a nivelului pragului la 0.5L μ= 32.9, care ilustrează domeniul parametric, unde sunt prezente toate cele 8 linii. Din cauza nivelului de zgomot pot fi observați mulți vectori falși ai parametrilor.

5.4 Concluzii

Acest capitol demonstrează posibilitățile și limitările folosirii transformatei Radon discrete cu privire la zgomot. În subcapitolul 5.1 s-a analizat detecția liniilor șerpuite și au fost derivate expresii analitice ce modelează comportarea transformatei Radon discrete cu privire la liniile șerpuite. În subcapitolul 5.2 s-a arătat că simpla integrare a liniilor șerpuite poate fi înțeleasă ca un filtru de maxim utilizat în domeniul imaginii.

În final, subcapitolul 5.3 prezintă o analiza statistică a transformatei Radon generalizate, bazată pe zgomot. Analiza a fost folosită pentru a obține un nivel de prag, cu scopul de a separa informațiile despre curbă de datele despre zgomot, în domeniul parametric. Pentru a demonstra teoria, a fost ilustrat un exemplu numeric.

CAPITOLUL VI

Transformata Radon inversă

6.1 Teorema Fourier pe cadre

Reconstituirea imaginilor se face cu ajutorul transformatei Radon inverse. Inversarea poate fi făcută în mai multe moduri. Un algoritm standard este bazat pe teorema Fourier, cunoscută și sub numele de teorema Centrală Fourier pe cadre. Transformata Radon trebuie inversată și adusă la forma g(x, y), inversare ce se bazează pe transformata Fourier.

Mai întâi este necesară transformata Fourier 2D a lui g(x, y).

(6.1)

iar transformata inversă este dată de:

(6.2)

Se introduc parametrii polari ai frecvenței:

(6.3)

Introducând ecuația 6.3 în 6.1, obținem:

(6.4)

În acest fel, spectrul este dat de o transformată Fourier unidimensională, care, ulterior, dă g(x, y) conform ecuației 6.2. Teorema Fourier pe cadre poate fi rezumată astfel:

(6.5)

(6.6)

Această teoremă face posibilă inversarea transformatei Radon utilizând transformatele Fourier 1D și 2D. Se observă că teorema poate fi folosită și în sens opus, de calculare a transformatei Radon, dacă se dă semnalul g(x, y).

6.2 Proiecția inversă filtrată

O altă schemă renumită de inversare este proiecția inversă filtrată. Este derivată din ecuația 6.2, introducând coordonatele polare.

(6.7)

Ecuația 6.7 este scrisă de obicei în două părți: o parte de filtrare și una de integrare:

(6.8)

(6.9)

(6.10)

(6.11)

Operația prezentată în ecuația 6.10 se numește proiecție inversă. Partea de filtrare din ecuația 6.8 este o transformare înainte Fourier pentru fiecare unghi. În domeniul Fourier, semnalul este filtrat cu filtrul trece sus . În final se utilizează o transformare Fourier 1D inversă, pentru a obține domeniul Radon filtrat . Partea de proiecție inversă este în întregime o integrare de-a lungul unei curbe sinuoase în domeniul Radon filtrat.

Proiecția inversă filtrată poate fi formulată și fără filtrare în domeniul frecvențelor. Filtrul este exprimat ca un produs:
(6.12)

(6.13)

Unde „*” reprezintă o convoluție a parametrului ρ. De remarcat este faptul că nu îndeplinește cerințele normale de a avea o transformată Fourier inversă, dar s-a folosit valoarea Cauchy principală în integrala Fourier inversă. Mai departe, este introdusă transformata Hilbert a unei funcții.

(6.14)

Ca urmare, proiecția inversă filtrată poate fi scrisă într-o formă foarte compactă, asemănătoare cu cea folosită de Radon:

(6.15)

Implementarea directă din ecuația 6.15 este cumva problematică, din cauza transformatei Hilbert. Transformata Hilbert nu poate fi implementată ușor fără folosirea transformatei Fourier.

6.3 Filtrarea după proiecția inversă

Este posibilă și conjugarea transformatei Radon înainte de filtrare. În cazul acesta se folosește un alt filtru. Rescriind g(x, y) utilizând funcția delta, conform ecuației 2.16, avem:

(6.16)

(6.17)

Ecuația 6.17 arată că fiecare punct este transformat într-un sinus în domeniul Radon. Transformata Radon a lui g(x, y) este suma integrală a tuturor curbelor din domeniul Radon. În cele ce urmează sunt omise integrările peste x* și y*. Acest lucru este posibil deoarece sunt folosite doar transformările liniare.

Presupunem că se dă originea unui punct, și se aplică transformata Radon conjugată înaintea filtrării.
(6.18)

(6.19)

(6.20)

(6.21)

(6.22)

(6.23)

Poate fi recunoscută o convoluție bidimensională.

, unde (6.24)

Utilizând tehnica prezentată în ecuația 6.17, se poate vedea că ecuația 6.24 este validă pentru orice funcție g(x, y) dată, astfel că ecuația 6.24 îngăduie altă schemă de inversare. Transformata Radon bidimensională a ecuației 6.24 dă:

(6.25)

(6.26)

Din tabelul standard al transformatei Fourier 2D se poate găsi că:
(6.27)

De unde rezultă că g(x, y) poate fi:
(6.28)

(6.29)

(6.30)

Metoda de reconstrucție prezentată mai sus se numește filtrare după proiecție inversă, și utilizează o integrare urmată de o filtrare bidimensională trece sus.

6.3.1 Problema frecvenței nule

În paragrafele anterioare a fost presupusă o inversare perfectă, însă algoritmii proiecției inverse nu pot inversa la perfecție, din cauza filtrelor utilizate. Folosind proiecția inversă filtrată s-a constata că spectrul polar la frecvență nulă (υ=0), este multiplicat cu zero. Acest lucru implică faptul că o valoare medie nenulă, în sinogramă, este fixată la zero în toate cazurile, deci valoarea medie a imaginii reconstruite trebuie să fie corectată. Utilizând proiecția inversă după filtrare, este evident că valoarea nulă a frecvenței imaginii inversate g(x, y), trebuie să devină zero. Această problemă este prezentată și de teorema Fourier, când se consideră implementarea discretă.

6.4 Inversarea transformatei Radon (p,)

În acest paragraf sunt derivate formule pentru transformata „Slant Stacking”. Sunt forme echivalente ale uneia derivate pentru transformata Radon (ρ,θ). Funcția de bază este g(x, y). În cadrul literaturii seismice, funcția căutată depinde de parametrul distanței x și de timpul t, iar transformata Fourier 2D are ca interpretare fizică un plan extins al undei.

Transformata Radon cu parametrii (p,):
(6.31)

6.4.1 Teorema Fourier pe cadre

Derivarea formulei de inversare este bazată pe transformata Fourier bidimensională a lui g(x, y)

(6.32)

(6.33)

Se introduc doi parametrii noi: p, care reprezintă raportul negativ între frecvențele kx și ky, și decalajul , date de:

(6.34)

(6.35)

Dacă inserăm acești doi parametrii în ecuația 6.32, avem:
(6.36)

(6.37)

(6.38)

În ultima ecuație poate fi recunoscută transformata Fourier 1D a transformatei Radon, iar combinând ecuațiile 6.38 și 6.33, este găsită o formulă de inversare:

(6.39)

Această teoremă Fourier arată că funcția g(x, y) poate fi reconstruită prin maparea transformatei Fourier 1D a transformatei Radon, în spectrul Fourier 2D a lui g(x, y). Dacă transformata Radon este dată doar într-un anumit interval, de exemplu între -1 și 1, atunci doar o parte din domeniul Fourier 2D poate fi prevăzută din transformata Fourier 1D a transformatei Radon, situație ilustrată în figura 6.1.

Figura 6.1: Din transformata Radon doar o parte a domeniului Fourier 2D

poate fi acoperită

6.4.2. Proiecția inversă filtrată

Ecuația 6.39 poate fi combinată cu ecuația 6.35 cu scopul de a obține o formulă de inversare pentru transformata „Slant Stacking”

(6.40)

(6.41)

(6.42)

Pentru claritate, ecuația 6.42 se scrie în două părți: o parte de filtrare și una de proiecție inversă:

(6.43)

(6.44)

Această formulă de calcul a transformatei Radon inverse, arată că domeniul parametric este filtrat cu frecvența absolută în direcția y pentru toate valorile ale lui x, iar apoi, partea de proiecție inversă integrează de-a lungul unei linii. De remarcat că, expresia liniară din integrala proiecției inverse este ca cea găsită pentru originea punctului, adică, originea punctului a fost transpusă în domeniul parametric de transformata Radon, și prin partea de proiecție inversă, domeniul parametric filtrat este iarăși colectat.

6.5 Concluzii

În acest capitol au fost derivate câteva formule de calcul ale transformatei Radon inverse. S-a văzut că acestea pot fi bazate pe tehnici Fourier și transformări ale integralei. Au fost făcute câteva remarci privitor la faptul că transformata Radon inversă nu poate recupera corect valoarea medie.

CAPITOLUL VII

Implementare

7.1 Implementarea transformatei Radon

Program: proiect.c

#include <IM.h>

#define ROUND(r)((r)>=0.0)?((int)(r+0.5)):((int)(r-0.5))

/* Variabilele globale */

FLOAT_TYPE **Data1;

FLOAT_TYPE **Data2;

int X, Y, Z;

int Debug = FALSE;

int Fast = FALSE;

int NumBuckets;

int NumărProiecții = 200;

double sin();

double cos();

/* Se execută proiecții paralele */

void Proiect()

{

int x, y, a, b, Xjum, Yjum, StângaImag, DreaptaImag;

float val, Poziție, Astânga, Adreapta, *TabelaSin, *TabelaCos;

/* Se inițializează tabelele sin și cos */

TabelaSin = (float *) malloc((unsigned) sizeof(float) * NumărProiecții);

TabelaCos = (float *) malloc((unsigned) sizeof(float) * NumărProiecții);

for (a = 0; a < NumărProiecții; a++)

{

TabelaSin[a] = (float) sin((double) (a * M_PI / NumărProiecții));

TabelaCos[a] = (float) cos((double) (a * M_PI / NumărProiecții));

}

/* Se inițializează proiecțiile cu zero */

for (a = 0; a < NumărProiecții; a++)

for (b = 0; b < NumBuckets; b++)

Data2[a][b] = 0.0;

/* Se proiectează fiecare pixel în imagine */

Xjum = X / 2;

Yjum = Y / 2;

for (y = -Yjum; y < Yjum; y++)

for (x = -Xjum; x < Xjum; x++)

{

val = Data1[y + Yjum][x + Xjum];

for (a = 0; a < NumărProiecții; a++)

{

/* Proiecție rapidă inexactă */

Poziție = x * TabelaCos[a] + y * TabelaSin[a];

if (Fast == TRUE)

{

/* Se calculează coordonatele celei mai apropiate variabile bucket */

b = ROUND(Poziție);

if (b < 0)

b += NumBuckets;

Data2[a][b] += val;

}

/* Proiecție lentă, dar mai precisă */

else

{

/* Se calculează coordonatele pixelilor din stânga și din dreapta*/

if (Poziție >= 0.0)

{

StângaImag = (int) Poziție;

DreaptaImag = StângaImag + 1;

}

else

{

DreaptaImag = (int) Poziție;

StângaImag = DreaptaImag – 1;

}

/* Se calculează contribuția pixelilor din dreapta și din stânga */

Astânga = DreaptaImag – Poziție;

Adreapta = Poziție – StângaImag;

if (StângaImag < 0)

StângaImag += NumBuckets;

if (DreaptaImag < 0)

DreaptaImag += NumBuckets;

Data2[a][StângaImag] += (val * Astânga);

Data2[a][DreaptaImag] += (val * Adreapta);

}

}

}

/* Se aleg 45 și 135 de proiecții pentru metoda rapidă */

if (Fast == TRUE)

for (b = 0; b < NumBuckets; b++)

{

Data2[NumărProiecții / 4][b] = Data2[1 + NumărProiecții / 4][b];

Data2[3 * NumărProiecții / 4][b] = Data2[1 + 3 * NumărProiecții / 4][b];

}

}

/* Programul principal */

int main(int argc, char *argv[])

{

/* Variabilele imaginii */

char Nume1[50];

char Nume2[50];

IM_TYPE *Imaginea1;

IM_TYPE *Imaginea2;

int PixType, DimCnt;

/* Variabilele programului */

int i = 0;

/* Opțiunile programului */

printf("Programul proiectului\n\n");

while ((++i < argc) && (argv[i][0] == '-'))

switch (argv[i][1])

{

case 'p':

if (sscanf(argv[++i], "%d", &NumărProiecții) == 0)

Error("Nu s-a putut obține NumărProiecții ");

break;

case 'd':

Debug = TRUE;

break;

case 'f':

Fast = TRUE;

break;

default:

Error("Opțiune invalidă");

break;

}

/* Se iau numele fișierelor din listă */

if (sscanf(argv[i++], "%s", Nume1) == 0)

Error("Nu s-a obținut numele fișierului de intrare");

if (sscanf(argv[i++], "%s", Nume2) == 0)

Error("Nu s-a obținut numele fișierului de ieșire");

/* Se citește Imagineaa care se analizează */

Imaginea1 = im_open(Nume1, &PixType, &X, &Y, &Z, &DimCnt);

if (DimCnt != 2)

Error("Nu poate procesa imaginile 1D sau 2D");

Data1 = (FLOAT_TYPE **) im_alloc2D(Imaginea1, FLOAT);

im_read(Imaginea1, FLOAT, (char *) &(Data1[0][0]));

/* Se creează Imagineaa rezultată */

NumBuckets = X * 2;

Imaginea2 = im_create(Nume2, FLOAT, NumBuckets, NumărProiecții, 1);

Data2 = (FLOAT_TYPE **) im_alloc2D(Imaginea2, FLOAT);

/* Se iau datele imaginii de intrare */

Proiect();

/* Se scrie informația în imaginea rezultată */

im_write(Imaginea2, FLOAT, (char *) &(Data2[0][0]));

im_free2D((char **) Data1);

im_free2D((char **) Data2);

return (0);

}

7.2 Implementarea transformatei Radon inverse

Program: inv_radon.c

Scop: Acest program calculează transformata Radon inversă a unei proiecții, astfel:

se aplică transformata Fourier inversă 1D la fiecare linie a proiecției

se aplică interpolarea celui mai apropiat vecin lui F(r,t) și se obține F(u,v)

se aplică transformata Fourier inversă 2D lui F(u,v)

se transpune f(x,y) în centru și se aranjează imaginea rezultată

#include <IM.h>

/* Acesta este programul principal.*/

int main(int argc, char *argv[])

{

/* Variabilele imaginii */

char Nume1[50];

char Nume2[50];

IM_TYPE *Imaginea1;

IM_TYPE *Imaginea2;

IM_TYPE *Imaginea3;

COMPLEX_TYPE **Data1;

COMPLEX_TYPE **Data2;

FLOAT_TYPE **Data3;

int PixType, R, T, X, Y, Z, DimCnt;

/* Variabilele programului */

int Debug = FALSE;

int i = 0, t, r, x, y, x1, y1;

int Xjum, Yjum;

/* Opțiunile de interpretare ale programului */

printf("Programul transformatei Radon inverse\n\n");

while ((++i < argc) && (argv[i][0] == '-'))

switch (argv[i][1])

{

case 'd':

Debug = TRUE;

break;

default:

Error("Opțiune invalidă");

break;

}

/* Se ia numele fișierelor imaginii din listă */

if (sscanf(argv[i++], "%s", Nume1) == 0)

Error("Nu s-a găsit numele fișierului de intrare");

if (sscanf(argv[i++], "%s", Nume2) == 0)

Error("Nu s-a găsit numele fișierului de ieșire");

/* Se citește imaginea care trebuie prelucrată */

Imaginea1 = im_open(Nume1, &PixType, &R, &T, &Z, &DimCnt);

if (DimCnt != 2)

Error("Nu se pot procesa imaginile 1D sau 2D");

Data1 = (COMPLEX_TYPE **) im_alloc2D(Imaginea1, COMPLEX);

im_read(Imaginea1, COMPLEX, (char *) &(Data1[0][0]));

/* Se creează imaginea temporară */

X = Y = R;

Imaginea2 = im_create("/dev/null", COMPLEX, X, Y, Z);

Data2 = (COMPLEX_TYPE **) im_alloc2D(Imaginea2, COMPLEX);

/* Se creează imaginea rezultată */

Imaginea3 = im_create(Nume2, FLOAT, X / 2, Y / 2, Z);

Data3 = (FLOAT_TYPE **) im_alloc2D(Imaginea3, FLOAT);

/* Se calculează transformata Fourier 1D */

for (t = 0; t < T; t++)

fft_1d(&(Data1[t][0]), R, -1);

/* Se generează imaginea rezultată */

Xjum = X / 2;

Yjum = Y / 2;

for (y = 0; y < Y; y++)

for (x = 0; x < X; x++)

{

/* Se grupează în jurul coordonatelor x,y */

if (y < Yjum)

y1 = y;

else

y1 = y – Y;

if (x < Xjum)

x1 = x;

else

x1 = x – X;

/* Se calculează coordonatele r și t */

if (x1 == 0 && y1 == 0)

r = t = 0;

else

{

r = (int) (sqrt((double) x1 * x1 + y1 * y1) + 0.5);

t = (int) (atan2((double) y1, (double) x1) * T / M_PI + 0.5);

if (t < 0)

{

t = T + t;

r = R – r;

}

}

/* Se copiază informații în imaginea F(u,v) */

if ((t >= 0) && (t < T) && (r >= 0) && (r < R))

{

Data2[y][x].im = Data1[t][r].im;

Data2[y][x].re = Data1[t][r].re;

}

else

{

Data2[y][x].im = 0;

Data2[y][x].re = 0;

}

}

/* Se apică transformata Fourier inversă 2D */

fft_2d((char *) &(Data2[0][0]), X, Y, 1);

/* Se deplasează originea imaginii rezultate */

for (y = 0; y < Yjum; y++)

for (x = 0; x < Xjum; x++)

Data3[y][x] = Data2[(y + Yjum + Yjum / 2) % Y][(x + Xjum + Xjum / 2) % X].re;

/* Se scrie informația în imaginea rezultată */

im_write(Imaginea3, FLOAT, (char *) &(Data3[0][0]));

im_free2D((char **) Data1);

im_free2D((char **) Data2);

im_free2D((char **) Data3);

return (0);

}

7.3 Rezultate obținute

Reprezentări ale transformatei Radon și ale transformatei Radon inverse pentru câteva imagini simple:

CAPITOLUL VIII

Aplicații ale transformatei radon

în prelucrări de imagini

8.1 Algoritmul de transformare

Transformata Radon a unei imagini este suma transformatelor Radon ale fiecărui pixel în parte (principiul superpoziției). Algoritmul de transformare mai întâi divide pixelii imaginii în patru părți și proiectează separat fiecare subdiviziune, cum este ilustrat în figura următoare:

Fiecare contribuție a pixelului este împărțit proporțional în două intervale binare apropiate. Dacă proiecția atinge centrul intervalului binar, atunci 25% din ponderea pixelului o ia intervalul binar al axelor. Dacă proiecția atinge marginea dintre două intervale binare, atunci cele două intervale binare împart pe jumătate cele 25%.

Funcția Radon calculează proiecțiile unei matrici a imaginii de-a lungul unor direcții impuse. Proiecția unei funcții bidimensionale f(x, y) este un set de integrale linie. Funcția Radon calculează integralele linie ale mai multor surse, pe căi sau raze paralele, într-o anumită direcție. Razele sunt distanțate printr-un pixel. Pentru a reprezenta o imagine, funcția Radon necesită multiple proiecții ale imaginii din unghiuri diferite, rotând sursa în jurul centrului imaginii. Figura următoare prezintă o singură proiecție într-un unghi de rotație specificat θ:

De exemplu, integrală din f(x,y) pe direcție verticală, este proiecția lui f(x,y) pe axa X; integrala pe direcție orizontală este proiecția lui f(x,y) pe axa Y. Următoarea figură ilustrează proiecțiile orizontală și verticală pentru a funcție simplă bidimensională:

Proiecțiile orizontală și verticală ale unei funcții simple bidimensionale

Proiecțiile pot fi calculate pentru orice unghi θ. În general, transformata Radon a lui f(x,y) este integrala acesteia paralel cu axa Y:

, unde

Geometria transformatei Radon este ilustrată în figura de mai jos:

8.2 Imagini reconstruite din proiecții

Exemple de imagini reconstruite cu număr diferit de proiecții inverse filtrate:

Indiferent de numărul proiecțiilor, partea din exteriorul elipsei nu se netezește perfect niciodată. Pentru o imagine f(x, y) pe care dorim să o reconstruim, q(, s) este proiecția inversă filtrată, algoritmul folosit este următorul:

Initialize f(x,y)

For each p do

For each (x,y) do

s = xsin(phi) – ycos(phi)

f(x,y) = f(x,y) + q(phi,s);

end

end

8.3 Analiza formelor globulelor roșii utilizând transformata Radon

8.3.1 Introducere

Forma unei globule roșii normale este o discocită biconcavă, ce manifestă o stare de echilibru între două forme extrem-opuse, echinocite și stomatocite. Mecanismul prin care globulele roșii ale unui adult își schimbă forma în condiții fiziologice și patologice, este determinantul prim al modului de circulație al sângelui. Sunt prezentate în detaliu, utilizând transformata Radon, schimbări morfologice asociate cu formele globulelor roșii. Imaginile discocitelor și stomatocitelor obținute sunt expuse tehnicilor de procesare a imaginilor, și sunt evaluate profilurile intensității lor. Funcția răspuns obținută prin aplicarea transformatei Radon imaginilor, definește clar formele globulelor roșii. Această abordare explică descrierile formei cu privire la variațiile de intensitate ale imaginii, și poate fi folosită mai departe în investigațiile variatelor stări patologice.

Globulele roșii cu diametrul mediu de 6 microni suferă deformări și schimbări de formă pentru a trece prin capilare de 2 microni la capilare de 3 microni, pentru a oxigena întreg țesutul. În condiții de repaus, globulele roșii normale au o formă de disc biconcav, reprezentând starea de echilibru. Sunt presupuse două forme extrem-opuse ale globulelor roșii, și anume echinocitele și stomatocitele. Deformarea acestora este o consecință mai degrabă a solicitării continue decât a tensiunii elastice. Această deformabilitate permite reducerea vâscozității în vasele largi și este factorul prim în supraviețuirea globulelor în microcirculație pentru 120 de zile. Globulele roșii suferă astfel de transformări în vitro sub influența anumitor agenți, însă aceste schimbări sunt reversibile prin îndepărtarea agenților cauzativi.

În ultimii ani, în analiza imaginii, o atenție considerabilă a promit-o transformata Radon. Aceasta este capabilă să transforme imaginile bidimensionale cu linii, într-un domeniu al parametrilor de linie posibili. Aplicând transformata Radon, curbele din imagine devin puncte. Poziția unui punct corespunde parametrilor formei și amplitudinea corespunde tuturor formelor. Fiecare punct din planul imaginii este transformat în domeniul Radon, unde fiecare punct din domeniul real corespunde întregii distribuții în tot domeniul Radon.

8.3.2 Exemple și metodologie

Probele de sânge pentru acest studiu au fost obținute de la voluntari adulți sănătoși. Sunt separate celulele de plasmă prin centrifugă. Discocitele normale iau formă de cupă prin tratare cu Triton X-100. Formele normale și modificate ale globulelor sunt confirmate de microscop, și sunt fotografiate la extindere uniformă.

Imaginile obținute sunt procesate utilizând practici obișnuite de procesare a imaginilor. Acestea sunt redimensionate pentru a acoperi întreaga clasă, și apoi sunt segmentate pentru a detecta schimbările. Imaginilor redimensionate li se identifică marginile utilizând un operator deștept cu un punct de placare ales de 0,4 și o deviație lipsă standard de 1. Apoi, imaginii ce conțin marginile se aplică transformata Radon.

Transformata Radon poate fi definită de:

unde p este panta liniei și este întreruperea ei.

Este obținut un vector x’, ce conține coordonatele radiale corespunzătoare fiecărui rând din imagine. Aceste coordonate radiale sunt valorile de-a lungul axei x’ care este orientată la θ grade în sensul opus acelor de ceasornic față de axa x. Originea ambelor axe este pixelul din centrul imaginii I, definit astfel:

Floor ((size (I) +1)/2)

iar numărul punctelor proiecției din care este compusă I, este dat de:
2*ceil (norm (size (I)-floor ((size (I)-1)/2)-1)) +3

8.3.3 Rezultate și discuții

Â

Profilul intensității unei discocite are mai puține variații ale amplitudinilor coordonatelor transformatei Radon calculate în punctele proiecției. Însă stomatocitele au tranziții rapide și neașteptate ale valorilor intensității. Imaginea ce conține marginea stomatocitei prezintă variații în intensitate datorită formei sale de cupă, iar imaginea scalată corespunzătoare are un număr mare de linii luminoase, comparativ cu discocitele. Discocitele au o margine clară de disc biconcav ce corespunde puținelor pete luminoase din figurile 2.d și 3.d. Imaginile stomatocitelor cu formă de cupă prezintă ceva mai multe linii luminoase în figurile 4.d și 5.d, comparativ cu discocitele. Numărul liniilor luminoase din imaginile scalate indică, așadar, natura globulelor.

8.3.4 Concluzii

Globulele roșii normale suferă schimbări de formă pentru a exista în microcirculație 120 de zile iar aceasta este responsabilă de fluiditatea sângelui atât în macrovase cât și în microvase. Orice descreștere a deformabilității poate rezulta din incapacitatea de a-și schimba forma în funcție de condițiile cursului sângelui. Deci, deformabilitatea și schimbările formei sunt indici semnificativi în aprecierea circulației sângelui atât în vasele micro cât și în cele macro. De aceea este o necesitate analiza completă a schimbărilor de formă. Funcția răspuns a parametrului obținută prin aplicarea transformatei Radon, este găsită capabilă să distingă formele globulelor, potrivit schimbărilor de amplitudine ale intensității. Poziția unui vârf corespunde parametrilor formei, iar amplitudinea corespunde întregii evidențe a formei. Fiecare punct din planul imaginii este transformat în domeniul Radon unde fiecare punct din domeniul real corespunde întregii distribuții din tot domeniul Radon, prin aceasta dând o idee completă a formei imaginii.

8.4 Utilizarea transformatei Radon în investigarea

anizotropiei semnalului atmosferic

Transformata Radon este, de asemenea, un mijloc de a investiga anizotropia imaginilor în care variația sistematică a intensității într-o anumită direcție este în mod semnificativ vizibilă. Aici transformata Radon realizează o cartare din două dimensiuni într-una singură, unde intensitățile imaginii se strâng într-un contur. Transformata Radon este dată de:

(8.4.1)

unde f(x, y) este intensitatea imaginii, θ este orientarea conturului (în sensul opus acelor de ceasornic), iar δ este funcția Delta Dirac.

Aplicată unei imagini discrete, transformata Radon devine:

(8.4.2)

unde este imaginea originală rotită în sensul acelor de ceasornic cu un unghi θ, iar N este a l-a coloană a imaginii rotite.

Pentru a examina sistematic anizotropia semnalului atmosferic, se calculează transformata Radon a fiecărei interferograme. Se utilizează varianta normalizată a transformatei Radon:

(8.4.3)

Se obțin valorile medii ale efectelor atmosferice de-a lungul liniilor perpendiculare pe orientarea conturului.

Transformatele Radon ale celor trei regiuni de studiu prezintă anizotropii variabile. În prima transformare, unde întreaga imagine prezintă o aproape simetrie față de centrul conturului, orientările sunt vizibile în cele două părți, unde unghiul variază de la 00 la 900. Acest lucru implică acele arii mici ale semnalelor atmosferice pozitive și negative localizate în colțurile din sud-vest și nord-est ale imaginii originale din figura 8.4.1.a. Și transformata a doua (figura 8.4.2.b) prezintă anizotropie importantă cu orientare puternică cam pe la 1350. Cea de-a treia transformată (figura 8.4.3.b) prezintă modele foarte interesante. De la 00 la 900, valorile se schimbă lent de la extreme pozitive la extreme negative, în timp ce de la 910 la 1800 valorile se schimbă brusc. Acest lucru sugerează faptul că în toate cele patru colțuri sunt concentrații de fază pozitive sau negative. Câmpul atmosferic original (figura 8.4.3a) confirmă faptul că în colțurile din nord-est și sud-est este o cantitate mică a concentrației de faze negative, în timp ce în celelalte colțuri, nord-vest și sud-vest, sunt concentrații de fază pozitive. Din cele trei transformări, ce-a de-a treia prezintă variațiile cele mai complicate. Acest lucru poate fi cauzat de faptului că regiunile Shanghai și New South Wales sunt relativ întinse, pe când în Hong Kong sunt câțiva munți cu altitudinea cea mai mare de 1km. În zonele muntoase complicația poate fi dată de: 1) efectul stratificării pe verticală sau efectul „static” al troposferei; 2) efectul munților asupra condițiilor meteo locale (acestea pot fi diferite în cele două părți ale muntelui).

8.5 Aplicații ale transformatei Radon în ajustarea imaginii din tomografia computerizată

Metoda de ajustare a imaginii este una din algoritmii fundamentali de procesare a imaginii, și este o tehnică de estimare a similitudinii între diferite imagini. Este fundamentală în analiza imaginii și recunoașterea formelor, și are o varietate largă de aplicații, cum ar fi detectarea modificărilor într-o scenă, estimarea mișcării obiectelor, localizarea țintelor, identificarea obiectelor, reunirea informațiilor din diferite tipuri de imagini, etc. Printre aceste aplicații, cel mai frecvent considerate transformate geometric, sunt translația, scalarea uniformă și rotațiile. Interesul manifestat timpuriu în această problemă vine din perspectiva calculatorului, care necesită transformarea dintr-o coordonată spațială în alta. Un alt câmp al aplicației practice este recunoașterea țintei într-un plan îndepărtat. În ultimul timp, odată cu apariția imaginilor în diagnosticul medical, această problemă devine din ce în ce mai importantă în studii și implementări.

Operația fundamentală din ajustarea imaginii este de a compara corelații variate cu nume și aspecte diferite, în funcție de implementările specifice. În mod fundamental sunt trei categorii de algoritmi în literatura existentă:

tehnici bazate pe intensitățile imaginii, cum sunt momentele, corelațiile, tehnica integralei Kernel și metode Fourier;

metode bazate pe trăsături;

Metode bazate pe modelul elastic.

Au apărut multe metode combinate în aplicațiile recente din diagnosticul medical și planificarea tratamentului terapeutic. Totuși, metodele convenționale de ajustare a imaginii nu pot satisface nevoia unei detecții on-line, din cauza vitezei mici de recunoaștere. Se încearcă utilizarea directă a transformatei Radon pentru a soluționa parametrii de ajustare. Deformarea generală geometrică, doar cea rigidă, cum este translația, rotația și scalarea uniformă, este problema cheie a ajustării imaginii, și de aceea ne focalizăm în rezolvarea parametrilor geometrici de deformare cu ajutorul transformatei Radon.

În tomografia computerizată, când un fascicul de raze X trece printr-un obiect, atenuările depind de conținutul obiectului, distanța, direcția sau unghiul aceste proiecții. Aceste set de proiecții este numit transformata Radon.

Fie f(x,y) o imagine 2D, având transformata Radon o funcție 2D de două variabile reale t și θ, definită de:

£ (1)

Figura 1. Transformata Radon

Din punct de vedere geometric, după cum se vede în figura 1, (t,θ) este egală cu integrala funcției pe linia dreaptă L, ce trece prin t și este ortogonală pe θ. L este dat de :

(2)

Pentru un θ dat, setul de valori ale transformatei Radon care corespunde integralelor funcției pe linii paralele, este cunoscut ca o proiecție în tomografie. Proiecția pe direcția θ este:

(3)

Expresiile matematice pentru transformata Radon conduc la câteva proprietăți foarte importante. În cele ce urmează sunt prezentate proprietățile de invarianță ale transformatei Radon în cazul rotației, scalării și translației.

1) Teorema Fourier și conservarea energiei: proprietatea de bază în aplicațiile tomografice este teorema Fourier. Aceasta demonstrază că transformata Fourier a unei proiecții în direcția θ este egală cu o parte din transformata Fourier 2D a unei imagini de-a lungul direcției θ. Se poate scrie:

(4)

Această teoremă arată corespondența informației conținute în imagine și transformata Radon a acesteia. Bazându-ne pe teorema Fourier, putem considera că există o conservare a energiei în transformarea Radon, exprimată astfel:
(5)

2) Translația: efectul translației unei imagini este o deformare a transformatei Radon, care poate fi descrisă astfel: variabila spațială a transformatei Radon este translatată de o mărime ce depinde de vectorul de translație al imaginii și de variabilă unghiulară. Dacă imaginea f(x,y) este deplasată cu și , atunci transformata Radon este următoarea:
(6)

3) Rotația: dacă imaginea f(x,y) este rotată cu , atunci f(x,y) devine:
(7)

Atât timp cât integrala ecuației 1 poate fi exprimată cu ajutorul unei matrici de rotație, transformata radon a imaginii rotate devine:

(8)

4) Scalarea uniformă: dacă imaginea f(x,y) este scalată cu un factor k, k>0, atunci transformata Radon este:

(9)

Figura 2: a) Tomografia Shepp-Logan; b) sinograma figurii a); c) sinograma rotită cu £; d) sinograma translatată cu și ; e) sinograma scalată cu patru cincimi; f) sinograma scalată cu patru cincimi și translatată cu și

Figurile 2.c, 2.d, 2.e, 2.f ilustrează proprietățile de rotație, translație și respectiv de scalare ale transformatei Radon.

Recunoașterea parametrilor: după ce sunt obținute proiecțiile tomografiei computerizate, se trece la soluționarea relațiilor dintre imaginea originală (sau imaginea de referință) și imaginea test; cu alte cuvinte, se trece la recunoașterea parametrilor k, , , . Din ecuațiile 5 și 9 se obține ușor scalarea uniformă.

Figura 3: a) conturul figurilor 2.b și 2.e (θ=600);

b) conturul figurilor 2.b și 2.c (t=0)

Pentru o poziție spațială t dată, după cum se vede în figura 3.b, unghiul de rotație θ poate fi unic determinat printr-un minim local al celor două contururi ale obiectelor.

Mai departe ne concentrăm atenția asupra determinării vectorului de translație , iar procedurile de recunoaștere pot fi rezumate astfel:
a) calcularea transformatelor Fourier ale funcțiilor f(x,y) și respectiv

b) pentru un unghi θ1 fixat, fie , din ecuația 6 avem:

(10)

unde a și b sunt două constante ce depind de vectorul de translație . Deci translația poate fi determinată de

(11)

În acest fel deformarea geometrică rigidă este complet obținută.

Figura 4: Imagini test :a) Shepp-Logan translatată cu (10, 30) și cu zgomot;

b) Shepp-Logan translatată cu (10, 30) neclară

8.6 Reconstrucția formelor 3D bazată pe transformata Radon cu aplicații în măsurarea volumului

Reconstrucția formelor 3D este esențială în multe aplicații cum ar fi navigarea automată, verificarea aparaturii, recunoașterea obiectelor 3D, măsurarea distanței și a deplasamentului, controlul nivelului, ș.a.m.d. Transformata Radon reconstruiește imaginile din proiecții. Se fac o serie de fotografii la diferite unghiuri în jurul obiectului ce servesc la reconstrucția secțiunii imaginii. Din totalitatea secțiunilor reconstruite se obțin datele despre volum. Cu ajutorul acestora se reface partea exterioară. Avantajul acestei tehnici este acela că necesită doar o cameră digitală sau o cameră normală cu scanner, și nu necesită scanare mecanică cu problematica unei concordanțe laborioase.

O chestiune importantă în procesarea imaginii este reconstrucția unei secțiuni a obiectului din câteva imagini ale proiecțiilor sale trans-axiale. Se utilizează proiecția inversă filtrată în care reconstrucția este executată în domeniul Fourier multiplicând răspunsul în frecvență al unui filtru uni-dimensional cu transformata Fourier a proiecțiilor înainte de proiecția înapoi a transformatei inverse a rezultatului.

unde este proiecția inversă, F este transformata Fourier uni-dimensională.

Lumina reflectată din obiect servește drept sursă a procesului tomografic. O serie de profiluri ale imaginii obținute la anumite unghiuri în jurul obiectului pot fi utilizate în reconstrucția secțiunii obiectului. Informațiile despre volum sunt apoi obținute dintr-o serie de secțiuni realizate pe o linie orizontală. Și astfel se reconstituie obiectul.

Figura 8.6.1: Configurația sistemului

Sistemul constă în principal dintr-o platformă care se rotește și o cameră digitală. Obiectul testat este așezat pe acea platformă care se rotește cu 1 grad/pas, iar camera digitală fotografiază.

Figura 8.6.2: a) Manechinul original; b) Suprafața refăcută a manechinului

Pentru a minimiza efectul de perspectivă se utilizează o distanță focală mare. După fiecare expunere, platforma se rotește o dată pentru fiecare unghi de atac. Reconstrucția tomografică a primului cadru se realizează utilizând primul profil de intensitate al fiecărei imagini digitale. Reconstrucția este repetată pentru toate cele 480 de profiluri. Apoi imaginile 2D reconstruite sunt stivuite pentru a forma volumul. Suprafața exterioară este realizată cu ajutorul algoritmului cubului, și i se adaugă lumină și umbră utilizând modelul Phong și Gouraud de iluminare și umbrire.

Figura 8.6.3: a) O ceașcă de cafea; b) un model 3D a ceștii de cafea utilizând 72 de proiecții și 60 de straturi

Măsurarea volumului este esențială în mai multe aplicații, cum ar fi calculul procentajului de grăsime în corpul uman. Pentru a estima volumul obiectului se extrag coordonatele x-y ale secțiunii imaginii reconstruite. Conturul secționat este obținut din procesul de detecție a marginilor din secțiunea imaginii urmat de o simplă localizare a pixelilor ce constituie marginea detectată. Coordonatele 2D ale tuturor contururilor secționate sunt stocate în funcție de pozițiile lor în direcția z, și astfel sunt obținute coordonatele 3D.

Figura 8.6.4: Coordonatele 3D ale manechinului

Pentru calibrarea axelor x și y se măsoară lungimea și lățimea obiectului și se corelează cu numărul pixelilor.

Pentru a calcula volumul obiectului, mai întâi se calculează aria mărginită de conturul secționat.