Razpoznavanje Daljic
Seminarska naloga 4.21
RPK

1. Uvod
2. Definicija naloge
3. Resevanje naloge
4. Izvorna koda
5. Zakljucek

1. Uvod

Pri predmetu Racunalnisko Podprto Konstruiranje sem se odlocil za seminarko nalogo pod stevilko 4.21 Razpoznavanje daljic. Nalogo sem reseval v programskem paketu Delphi 3, ki ima izvorno kodo Pascal. Program je v exe obliki in se ga lahko dobi na danem serverju ozirom ga lahko dobite ce kliknete - Program.exe.

2. Definicija naloge

Za podano rastersko datoteko (*.bmp) na kateri je narisano vec daljic, je potrebno razpoznati dolzino in orientacijo daljic in jih zapisati v vektorski obliki (zacetek in konec). Izbira algoritma je poljubna.Naloga je zastavljena tako, da mora imeti rasterska slika samo crne daljice z debelino 1 piksel (pika).

3. Resevanje naloge

Nalogo sem reseval po naslednjem algoritmu -podan pri definiciji naloge:

(x/y) v (a/b) transformacija:
Imejmo tocke v ravnini podane s koordinatami x in y. Ce izberemo poljubni dve tocki (x1 , y1 ) in (x2 , y2 ) lahko med njima potegnemo daljico. Tako lahko napisemo enacbo premice:
y1= a x1 + b
y2= a x2 + b
Iz zgornje enacbe lahko izracunamo parametra a in b. Ce postopek ponovimo za vse mozne kombinacije tock dobimo tako mnozico parov (a , b). Parameter a predstavlja tanges kota daljice ali naklon, b pa zacetek crte. Ce na parametru a izvedemo operacijo alfa = arctang (a) , dobimo znan razpon kotov alfa ' [-p, p]. Tako imamo za oba parametra alfa in b znan razpon, Tako lahko vsak par (alfa , b) zapisemo v matriko pogostosti, ter s tem dobimo polja, ki so najbolj pogosta. Tako lahko narisemo premice, ki najbolje popisujejo tocke.

Algoritem programa:

• Preberemo vse crne piksle (pike) po vrsti na raterski sliki in jih zapisemo
• Nato gremo od vsake tocke do tocke in zapisemo enacbo premice ter zapisemo koeficiente a in b v tabelo.Koordinatni sistem je obrnjen tako, da je izhodisce v zgornjem desnem kotu, pri tem so pozitivne vrednosti b - ja (odmik) nanizane na vertikali, negativne pa na horizontali.
• Naredimo pogostostno tabelo, ki je dvo-dimenzionalna - eden stolpec so koti drugi odmiki V pogostostni tabeli so zapisane vrednosti, ki nam povejo, kolikokrat se pojavi dolocena kombinacija koeficientov a in b.
• Nato poiscemo maksimume kotov in nato se maksimume odmikov pri kotih - dobim tocke in te tocke nam oznacujejo premico.
• Nato vse vrednosti povprecimo - dobimo povprecno vrednost a in b
• Ker poznamo koeficienta a in b - kot in odmik lahko dolocimo dano premico
• Ko imamo enkrat dano premico se sprehodimo po njej in ko naletim na zacetek daljice, ki je druge barve zapisemo koordinate te tocke in nadaljujem naprej, dokler spet ne preidemo na barvo podlage - tam zapisemo koncno tocko daljice.

Tako imamo podane zacetne in koncne koordinate tock.

Izgled programa:

Odpri: Izberemo sliko, ki jo bomo obravnavali
Osvezi: Osvezi sliko
Razpoznaj: Dolocimo koeficiente a in b ter dolocimo zacetne in koncne tocke premic.
Shrani: Shrani rezultat pod datoteki a-b.txt in koordinate.txt.
Stevilo tock: Stevilo tock, ki jih program prebere iz rasterske slike - stevilo crnih pikslov (pik)
St. kombinacij: Stevilo vseh kombinacij, ki jih dobimo pri zapisu premic med tockami.
Faktor kot [%]: Faktor, ki doloca koliko procentov vrednosti kotov pri pogostostni tabeli vzamemo
Faktor odmik [%]: Faktor, ki doloca koliko procentov vrednosti odmikov pri pogostostni tabeli vzamemo
Toleranca kot: Doloca nam razliko med maksimumom in drugimi vrednostmi za kot, ki jih vzamemo za povprecenje
Toleranca odmik: Doloca nam razliko med maksimumom in drugimi vrednostmi za odmik, ki jih vzamemo za povprecenje
Sirina iskanja: Dolocimo sirino iskalnega polja,ki je v obliki kvadrata
Toleranca dolzine: Dolocimo namanjso dolzino daljice, ki jo ne upostevamo
Prvo okno: Izpise nam vrednosti koeficientov a [^o] in b za vsako premico posebej
Drugo okno: Izpis nam zacetne in koncne tocke daljic
Slika: Predstavlja rastersko sliko, ki jo pretvorimo v vektorsko obliko s tem, da dolocimo koordinate tock daljic.

4. Izvorna koda

Izvorna koda je napisana v programu Delphi 3.

5. Zakljucek

Naloga je bila precej zahtevna, predvsem zaradi algoritma, ki pa mi ga je na sreco za v sami nalogi predlagal mentor Leon Kos. Najvecji problem je bil pri povprecenju dobljenih vrednosti, ki pa sem ga resil z dodatkom za sirino iskanja ter toleranco kot in toleranco odmik. Toleranca za kot in odmik nam v bistvu povesta v koliksnem obsegu nam dane vrednosti zdruzi v eno vrednost.

Program deluje tako, da nam potem, ko prebere pike pobarva ozadje rdece medtem, ko premico pobarva rumeno. Nato nam za dolocene premice narise modre daljice, ki nam kazejo odklon od prave vrednosti, vendar ta odklon popravimo pri sirini iskanja, ki nam tocno doloci koordinate zacetne in koncne tocke premice.

Marko Obid, Univerzitetni studij, KGS - RPK 98/99 - Fakulteta za Strojnistvo v Ljubljani