Nekoliko riječi o prepoznavanju obrazaca. Rasterska slika kao dvodimenzionalni niz podataka Primjer digitalnog prepoznavanja trougla
Kada pogledamo dvodimenzionalnu sliku trodimenzionalnog prizora (na slici, fotografiji, ekranu monitora), čini nam se da su svi objekti koje bismo mogli vidjeti da smo direktno posmatrali istu scenu u životu direktno prisutni. tamo. U međuvremenu, sve što nam je zaista dato u dvodimenzionalnoj slici je vidljivo polje, što predstavlja samo neke funkcija raspodjele svjetline ili boje na dvodimenzionalnoj ravni: f(x, y) , Gdje x I y– Kartezijanske koordinate koje opisuju ravan slike.
Štaviše, ako se približite ekranu kompjuterskog monitora, možete videti da slika na ekranu zapravo nije glatka i neprekidna, već je diskretni „mozaik“ koji se sastoji od pojedinačnih obojenih pravougaonika raspoređenih u pravilnu pravougaonu matricu. Ovo je digitalna slika. Sa matematičke tačke gledišta digitalna slika je dvodimenzionalna matrica Im veličine (DimXDimY), gdje je x cijeli broj od 0 do DimX– 1, koji opisuje broj elementa u redu matrice, y je cijeli broj od 0 do DimY– 1, koji opisuje broj reda matrice u kojem se ovaj element nalazi. U ovom slučaju, element same digitalne slike (ćelija pravokutne matrice) naziva se piksela(piksel, element slike). U najjednostavnijem slučaju, svaki pixelIm ima skalarnu cjelobrojnu vrijednost proporcionalnu vrijednosti funkcije raspodjele svjetline f(x, y) u datoj tački u ravni.
Na sl. 1.1.1 lijevo je slika ženskog lica, predstavljena kao slika, a desno je uvećani fragment slike istog lica (desno oko), gdje je za svaki element slike odgovarajuća numerička vrijednost piksela naznačeno. Svetlosni elementi slike odgovaraju b O veće vrijednosti matrice, tamno – manje vrijednosti. Digitalna slika ne sadrži nikakve druge informacije.
@Rice. 1.1.1 Digitalna slika kao dvodimenzionalna matrica intenziteta
Kada počnete proučavati kompjuterski vid, morate jasno razumjeti da je samo i isključivo dvodimenzionalni niz brojeva jednog ili drugog formata pohranjen u kompjuteru kao digitalna slika. Sve druge podatke koje bismo željeli izdvojiti iz slike (oblike, linije, objekte, dimenzije, sadržaj prikazanog teksta itd. itd.) možemo dobiti samo kao rezultat primjene brojnih postupaka obrade i analize slike , koju moramo ili sami programirati ili koristiti gotove procedure dostupne u poznatim softverskim paketima za analizu slike. Istovremeno, za rješavanje jednostavnih problema kompjuterskog vida, gotovi alati će se najvjerovatnije naći u standardnim bibliotekama postupaka obrade slika za rješavanje složenijih problema, bit će potrebno kombinirati određene gotove procedure, a za mnogi sasvim “obični” zadaci koje ljudski “biološki” vid naizgled rješava lako i razigrano, kompjuterski vid još uvijek nema rješenja i još uvijek ih traži. Uostalom, koristeći svoju prirodnu viziju, osoba se može lako kretati u bilo kojem okruženju, prepoznavati objekte, birati put, voziti automobil i još mnogo, mnogo više. Zašto računar koji prima sliku sa video kamere ne može sve ovo? Možda je to struktura ljudskog oka?
U stvari, ljudsko oko, poput video kamere, samo formira "vidljivo polje" slično digitalnoj slici. U ovom slučaju, optički sistem, koji se sastoji od zenice i sočiva, projektuje dvodimenzionalnu sliku na mrežnjaču, gde fotosenzitivne ćelije („štapići” i „čušnici”) pretvaraju rezultujuću sliku u nervne impulse. I tek nakon toga složeni mehanizam za obradu primljenih informacija, koji funkcionira u odgovarajućem dijelu našeg mozga, tumači ove impulse kao sliku vidljivog prizora koji razumijemo. Dakle, kod ljudi funkciju "vida" ne obavlja samo oko, već i sistem "oko + mozak" ("senzor + kompjuter"). To su algoritmi za obradu informacija ugrađeni u mozak koji omogućavaju osobi da razumije ono što vidi. Uloga ovih ugrađenih algoritama može se objasniti korištenjem sljedećeg primjera.
Kada su sredinom 20. veka oftalmološki hirurzi naučili da rade operacije na očnom sočivu, mnogi ljudi koji su bili slepi od rođenja imali su tehničku sposobnost da vide. Odnosno, nakon takve operacije kod osobe koja je prethodno bila slijepa (svjetlost jednostavno nije prošla kroz sočivo), slika se počela formirati na mrežnici i odgovarajući signali su počeli ulaziti u mozak na potpuno isti način kao što se događa kod zdravih ljudi. Nažalost, u ovom slučaju, “vidjeti svjetlo” nije značilo “početi vidjeti”. Kao što je kasnija historija pokazala, većina "tehnički osvijetljenih" odraslih pacijenata nikada nije mogla postići značajnije rezultate u vidnom polju od prepoznavanja jednostavnih geometrijskih oblika - a čak je i to zahtijevalo ozbiljan svjestan napor s njihove strane. Prepoznavanje ljudi po licima i orijentacija u prostoru za njih su ostali nemogući zadaci. Činjenica je da oni ugrađeni mehanizmi “automatske” vizuelne analize koji se razvijaju kod ljudi u ranom djetinjstvu kod ovih pacijenata nisu na vrijeme razvijeni, te su se našli u poziciji kompjutera koji ima uređaj za unos slika. , ali nema potreban softver za svoju analizu.
Kako bismo se konačno uvjerili u složenost zadatka koji nam predstoji analize slike, a to je dvodimenzionalni niz numeričkih podataka, pokušajmo se postaviti na mjesto kompjuterskog programa koji se bavi apstraktnim brojevima. Da bismo to učinili, promijenimo mentalno modalitet percepcije slike - prebacimo je iz vizualnog u taktilno područje. Zamislimo dvodimenzionalni niz vrijednosti intenziteta kao šahovsku ploču, čija je veličina jednaka veličini slike (DimXDimY), a u centar svake ćelije umetnut je stupac čija je visina je proporcionalna vrijednosti odgovarajućeg piksela na slici. Drugim riječima, razmotrimo dvodimenzionalnu sliku kao neku vrstu uslovne trodimenzionalne površine. Na sl. 1.1.2 lijevo je fragment ženskog lica prikazan kao slika, a desno je prikazan kao pseudo-3D reljef.
@Rice. 1.1.2. Digitalna slika kao pseudo-3D reljef
Sada zamislite da morate, bez gledanja u sliku, osjetiti odgovarajući "reljef" i pokušati utvrditi šta tačno ovaj "reljef" prikazuje - kuću, psa ili ljudsko oko? Eksperimenti pokazuju da prosječna osoba nije u stanju da se nosi s takvim zadatkom. Čak i prepoznavanje najjednostavnijih geometrijskih figura u takvom "reljefnom" prikazu zahtijevat će značajan napor i zahtijevat će svjestan razvoj posebne vještine, strategije i algoritama senzora. Ovo je, uprkos prividnoj jednostavnosti objekta „digitalne slike“, prava složenost problema kompjuterskog i mašinskog vida.
Odavno sam želio napisati opći članak koji bi sadržavao same osnove prepoznavanja slika, svojevrsni vodič za osnovne metode, koji govori kada ih koristiti, koje probleme rješavaju, šta se može raditi uveče na koljenima i šta je bolje ne razmišljati o tome bez tima ljudi u 20.
Već duže vrijeme pišem neke članke o optičkom prepoznavanju, pa mi par puta mjesečno pišu razni ljudi s pitanjima na ovu temu. Ponekad imate osjećaj da živite s njima u različitim svjetovima. S jedne strane, razumijete da je osoba najvjerovatnije profesionalac u srodnoj temi, ali zna vrlo malo o metodama optičkog prepoznavanja. A najneugodnije je to što pokušava primijeniti metodu iz obližnje oblasti znanja, što je logično, ali ne funkcionira u potpunosti u prepoznavanju slika, ali to ne razumije i jako se uvrijedi ako mu počnete govoriti nešto iz same osnove. A s obzirom na to da pričanje iz osnova oduzima mnogo vremena, koje često nije dostupno, postaje još tužnije.
Ovaj članak je namijenjen da osoba koja nikada nije radila s metodama prepoznavanja slika može u roku od 10-15 minuta u svojoj glavi stvoriti određenu osnovnu sliku svijeta koja odgovara temi i shvatiti u kojem smjeru treba kopati. Mnoge od ovdje opisanih tehnika primjenjive su na radarsku i audio obradu.
Počeću s nekoliko principa koje uvijek počinjemo govoriti potencijalnom kupcu ili osobi koja želi početi raditi optičko prepoznavanje:
- Kada rješavate problem, uvijek idite od najjednostavnijeg. Mnogo je lakše staviti narandžastu oznaku na osobu nego pratiti osobu, ističući je u kaskadama. Mnogo je lakše uzeti kameru sa višom rezolucijom nego razviti algoritam super rezolucije.
- Stroga formulacija problema u metodama optičkog prepoznavanja je za redove veličine važnija nego u problemima sistemskog programiranja: jedna dodatna riječ u tehničkoj specifikaciji može dodati 50% posla.
- Ne postoje univerzalna rješenja za probleme prepoznavanja. Ne možete napraviti algoritam koji će jednostavno “prepoznati bilo koji natpis”. Znak na ulici i list teksta su suštinski različiti objekti. Vjerovatno je moguće kreirati opći algoritam (evo dobrog primjera iz Google-a), ali će zahtijevati puno rada velikog tima i sastojat će se od desetina različitih potprograma.
- OpenCV je biblija koja ima mnogo metoda i može riješiti 50% gotovo svakog problema, ali OpenCV je samo mali dio onoga što se zapravo može učiniti. U jednoj studiji napisani su zaključci: “Problem se ne može riješiti korištenjem OpenCV metoda, stoga je nerješiv.” Pokušajte to izbjeći, nemojte biti lijeni i svaki put trezveno procijenite trenutni zadatak ispočetka, bez korištenja OpenCV šablona.
Ovdje navedena lista metoda nije potpuna. Predlažem da u komentare dodate kritičke metode koje nisam napisao i da svakom pripišete 2-3 popratne riječi.
Dio 1. Filtracija
U ovu grupu sam stavio metode koje vam omogućavaju da odaberete područja od interesa na slikama bez njihove analize. Većina ovih metoda primjenjuje neku vrstu pojedinačne transformacije na sve točke na slici. Na nivou filtriranja ne vrši se analiza slike, ali se tačke koje se filtriraju mogu smatrati oblastima sa posebnim karakteristikama.Binarizacija po pragu, izbor područja histograma
Najjednostavnija transformacija je binarizacija slike po pragu. Za RGB i slike u sivim tonovima, prag je vrijednost boje. Postoje idealni problemi u kojima je takva transformacija dovoljna. Pretpostavimo da želite automatski odabrati objekte na bijelom listu papira:
Izbor praga na kojem dolazi do binarizacije u velikoj mjeri određuje sam proces binarizacije. U ovom slučaju, slika je binarizirana prosječnom bojom. Obično se binarizacija provodi pomoću algoritma koji adaptivno bira prag. Takav algoritam može biti izbor očekivanja ili moda. Ili možete odabrati najveći vrh u histogramu.
Binarizacija može dati vrlo zanimljive rezultate pri radu sa histogramima, uključujući i situaciju kada sliku ne razmatramo u RGB, već u HSV. Na primjer, segmentirajte boje od interesa. Na ovom principu možete napraviti i detektor oznaka i detektor ljudske kože.
Klasično filtriranje: Fourier, niskopropusni filter, visokopropusni filter
Klasično radarsko filtriranje i metode obrade signala mogu se uspješno primijeniti na različite zadatke prepoznavanja uzoraka. Tradicionalna metoda u radaru, koja se gotovo nikada ne koristi u čistoj formi slika, je Fourierova transformacija (tačnije, FFT). Jedan od rijetkih izuzetaka u kojima se koristi jednodimenzionalna Fourierova transformacija je kompresija slike. Za analizu slike, jednodimenzionalna transformacija obično nije dovoljna;
Malo ljudi to zapravo izračunava, mnogo je brže i lakše koristiti konvoluciju područja od interesa sa gotovim filterom, podešenim za visoke (HPF) ili niske (LPF) frekvencije. Ova metoda, naravno, ne dozvoljava analizu spektra, ali u konkretnom zadatku obrade video zapisa obično nije potrebna analiza, već rezultat.
Najjednostavniji primjeri filtera koji naglašavaju niske frekvencije (Gausov filter) i visoke frekvencije (Gaborov filter).
Za svaku tačku slike odabire se prozor i množi filter iste veličine. Rezultat takve konvolucije je nova bodovna vrijednost. Prilikom implementacije niskopropusnih i visokopropusnih filtera dobijaju se slike sljedećeg tipa:
Wavelets
Ali što ako koristimo neku proizvoljnu karakterističnu funkciju za konvoluciju sa signalom? Tada će se zvati "Wavelet transform". Ova definicija talasa nije tačna, ali tradicionalno, u mnogim timovima, talasna analiza je potraga za proizvoljnim uzorkom na slici pomoću konvolucije sa modelom ovog uzorka. Postoji skup klasičnih funkcija koje se koriste u talasnoj analizi. To uključuje Haar talas, Morlet talas, meksički šešir talas, itd. Haar primitivi, o kojima je bilo nekoliko mojih prethodnih članaka (,), odnose se na takve funkcije za dvodimenzionalni prostor.
Iznad su 4 primjera klasičnih talasa. 3-dimenzionalni Haar talas, 2-dimenzionalni Meyer talas, Meksički šešir talas, Daubechies talas. Dobar primjer korištenja proširene interpretacije talasa je problem pronalaženja odsjaja u oku, za koji je talas sam odsjaj:
Klasični talasi se obično koriste za kompresiju slike ili za klasifikaciju slike (opisati će se u nastavku).
Korelacija
Nakon ovako slobodnog tumačenja talasa s moje strane, vrijedi spomenuti stvarnu korelaciju koja je u njihovoj osnovi. Ovo je nezamjenjiv alat za filtriranje slika. Klasična aplikacija povezuje video tok kako bi se pronašle pomake ili optički tokovi. Najjednostavniji detektor pomaka je u izvesnom smislu i korelator razlike. Tamo gdje slike nisu bile u korelaciji, bilo je kretanja.
Funkcije filtriranja
Zanimljiva klasa filtera je filtriranje funkcija. Ovo su čisto matematički filteri koji vam omogućavaju da otkrijete jednostavnu matematičku funkciju na slici (prava, parabola, krug). Konstruiše se akumulirajuća slika u kojoj se za svaku tačku originalne slike iscrtava skup funkcija koje je generišu. Najklasičnija transformacija je Houghova transformacija za linije. U ovoj transformaciji, za svaku tačku (x;y), nacrtan je skup tačaka (a;b) prave linije y=ax+b za koje je tačna jednakost. Dobijate prelepe slike:
(prvi plus je onome ko prvi pronađe kvaku na slici i ovoj definiciji i objasni je, drugi plus je onome ko prvi kaže šta je ovdje prikazano)
Hough transformacija vam omogućava da pronađete bilo koju funkciju koja se može parametrirati. Na primjer krugovi. Postoji modificirana transformacija koja vam omogućava da tražite bilo koji oblik. Matematičari užasno vole ovu transformaciju. Ali prilikom obrade slika, nažalost, to ne funkcionira uvijek. Vrlo mala brzina rada, vrlo visoka osjetljivost na kvalitet binarizacije. Čak i u idealnim situacijama, radije sam se zadovoljio drugim metodama.
Analog Houghove transformacije za prave linije je Radon transformacija. Izračunava se putem FFT-a, što daje povećanje performansi u situaciji kada ima puno bodova. Osim toga, može se primijeniti na nebinariziranu sliku.
Filtriranje kontura
Posebna klasa filtera je filtriranje granica i kontura. Obrisi su veoma korisni kada želimo da pređemo sa rada sa slikom na rad sa objektima na toj slici. Kada je objekt prilično složen, ali se jasno razlikuje, često je jedini način rada s njim odabir njegovih kontura. Postoji niz algoritama koji rješavaju problem filtriranja kontura:Najčešće se koristi Canny, koji dobro radi i čija implementacija je u OpenCV-u (Sobel je također tu, ali lošije traži konture).
Ostali filteri
Iznad su filteri čije modifikacije pomažu u rješavanju 80-90% problema. Ali osim njih, postoje rjeđi filteri koji se koriste u lokalnim zadacima. Takvih filtera ima na desetine, neću ih sve nabrajati. Zanimljivi su iterativni filteri (na primjer, model aktivnog izgleda), kao i ridgelet i curvlet transformacije, koje su fuzija klasičnog talasnog filtriranja i analize u polju transformacije radona. Beamlet transformacija radi lijepo na granici wavelet transformacije i logičke analize, omogućavajući vam da istaknete konture:
Ali ove transformacije su vrlo specifične i prilagođene rijetkim zadacima.
Dio 2. Logička obrada rezultata filtriranja
Filtriranje pruža skup podataka pogodnih za obradu. Ali često ne možete jednostavno uzeti i koristiti ove podatke bez obrade. U ovom odeljku biće nekoliko klasičnih metoda koje vam omogućavaju da pređete sa slike na svojstva objekata ili na same objekte.Morfologija
Prijelaz sa filtriranja na logiku, po mom mišljenju, jesu metode matematičke morfologije (, ,). U suštini, ovo su najjednostavnije operacije rasta i erodiranja binarnih slika. Ove metode vam omogućavaju da uklonite šum iz binarne slike povećanjem ili smanjenjem postojećih elemenata. Postoje algoritmi za konturiranje zasnovani na matematičkoj morfologiji, ali se obično koriste neka vrsta hibridnih algoritama ili algoritama u kombinaciji.
Analiza kontura
Algoritmi za dobijanje granica su već pomenuti u odeljku o filtriranju. Rezultirajuće granice se jednostavno pretvaraju u konture. Za Canny algoritam to se dešava automatski za druge algoritme je potrebna dodatna binarizacija. Možete dobiti konturu za binarni algoritam, na primjer, koristeći algoritam buba.Kontura je jedinstvena karakteristika objekta. Ovo vam često omogućava da identifikujete objekat po njegovom obrisu. Postoji moćan matematički aparat koji vam to omogućava. Uređaj se zove analiza kontura (,).
Da budem iskren, nikada nisam bio u stanju da primenim analizu kontura u stvarnim problemima. Potrebni su previše idealni uslovi. Ili nema granica, ili je previše buke. Ali, ako trebate nešto prepoznati u idealnim uvjetima, onda je analiza kontura odlična opcija. Radi vrlo brzo, lijepa matematika i jasna logika.
Posebne tačke
Pojedinačne tačke su jedinstvene karakteristike objekta koje omogućavaju da se objekat poredi sam sa sobom ili sa sličnim klasama objekata. Postoji nekoliko desetina načina da se identifikuju takve tačke. Neke metode identificiraju posebne točke u susjednim okvirima, neke nakon dužeg vremenskog perioda i kada se osvjetljenje promijeni, neke vam omogućavaju da pronađete posebne točke koje ostaju takve čak i kada se objekt rotira. Počnimo s metodama koje nam omogućavaju da pronađemo posebne točke, koje nisu tako stabilne, ali se brzo izračunavaju, a zatim ćemo ići u sve većoj složenosti:Prvi razred. Posebne tačke koje su stabilne u periodu od nekoliko sekundi. Takve tačke se koriste za vođenje objekta između susednih video okvira ili za kombinovanje slika sa susednih kamera. Takve tačke uključuju lokalne maksimume slike, uglove na slici (najbolji detektor je možda Charis detektor), tačke u kojima se postiže maksimalna disperzija, određene gradijente itd.
Druga klasa. Posebne tačke koje su stabilne pri promenama osvetljenja i malim pokretima objekta. Takve tačke služe prvenstveno za obuku i kasniju klasifikaciju tipova objekata. Na primjer, pješački klasifikator ili klasifikator lica je proizvod sistema izgrađenog upravo na takvim tačkama. Neki od prethodno navedenih talasa mogu biti osnova za takve tačke. Na primjer, Haar primitivi, traženje istaknutih dijelova, traženje drugih specifičnih funkcija. Ove tačke uključuju one pronađene metodom histograma usmjerenih gradijenta (HOG).
Treća klasa. Stabilne tačke. Znam samo za dvije metode koje daju potpunu stabilnost i za njihove modifikacije. To su SURF i SIFT. Omogućuju vam da pronađete posebne tačke čak i kada rotirate sliku. Izračunavanje takvih bodova traje duže u odnosu na druge metode, ali je vrijeme prilično ograničeno. Nažalost, ove metode su patentirane. Iako je u Rusiji nemoguće patentirati algoritme, pa ga koristite za domaće tržište.
Dio 3. Obuka
Treći dio priče bit će posvećen metodama koje ne rade direktno sa slikom, ali koje vam omogućavaju da donosite odluke. To su uglavnom različite metode mašinskog učenja i donošenja odluka. Nedavno je Yandyx objavio kurs na ovu temu na Habru, tamo je jako dobar izbor. Evo ga u tekstualnoj verziji. Za ozbiljno proučavanje teme toplo preporučujem da ih pogledate. Ovdje ću pokušati opisati nekoliko glavnih metoda koje se koriste posebno u prepoznavanju obrazaca.U 80% situacija, suština učenja u zadatku prepoznavanja je sljedeća:
Postoji test uzorak koji sadrži nekoliko klasa objekata. Neka to bude prisustvo/odsustvo osobe na fotografiji. Za svaku sliku postoji skup karakteristika koje su istaknute nekom karakteristikom, bilo da je to Haar, HOG, SURF ili neki talas. Algoritam učenja mora izgraditi model tako da može analizirati novu sliku i odlučiti koji se objekt nalazi na slici.
Kako se to radi? Svaka od testnih slika je tačka u prostoru obeležja. Njegove koordinate su težina svake od karakteristika na slici. Neka naši znaci budu: „Prisustvo očiju“, „Prisustvo nosa“, „Prisustvo dve ruke“, „Prisustvo ušiju“ itd... Sve ove znakove ćemo istaći koristeći naše postojeće detektore koji su obučeni na dijelovi tijela slični ljudskim Za osobu u takvom prostoru, ispravna tačka bi bila . Za majmuna, tačka za konja. Klasifikator je obučen korištenjem uzorka primjera. Ali nisu na svim fotografijama bile ruke, druge nisu imale oči, a na trećoj je majmun imao ljudski nos zbog greške u klasifikatoru. Obučeni ljudski klasifikator automatski deli prostor obeležja na način da kaže: ako prva karakteristika leži u opsegu 0,5
Postoji mnogo klasifikatora. Svaki od njih bolje radi u nekom određenom zadatku. Zadatak odabira klasifikatora za određeni zadatak je u velikoj mjeri umjetnost. Evo nekoliko lijepih slika na ovu temu.
Jednostavno kućište, jednodimenzionalno razdvajanje
Pogledajmo primjer najjednostavnijeg slučaja klasifikacije, kada je prostor karakteristika jednodimenzionalan, a moramo odvojiti 2 klase. Situacija se događa češće nego što mislite: na primjer, kada trebate razlikovati dva signala ili uporediti uzorak s uzorkom. Dajte nam uzorak za obuku. Ovo proizvodi sliku gdje je X-osa mjera sličnosti, a Y-osa je broj događaja sa takvom mjerom. Kada je željeni objekat sličan samom sebi, dobije se lijevi Gaussian. Kad ne izgleda tako - ono pravo. Vrijednost X=0,4 razdvaja uzorke tako da pogrešna odluka minimizira vjerovatnoću donošenja bilo kakve pogrešne odluke. Potraga za takvim separatorom je zadatak klasifikacije.
Mala napomena. Kriterijum koji minimizira grešku neće uvijek biti optimalan. Sljedeći grafikon je graf stvarnog sistema za prepoznavanje šarenice. Za takav sistem kriterijum se bira tako da se minimizira verovatnoća lažnog ulaska neovlašćenog lica u objekat. Ova vjerovatnoća se naziva “greška tipa I”, “vjerovatnoća lažnog alarma”, “lažno pozitivno”. U literaturi na engleskom jeziku “False Access Rate”.
) AdaBusta je jedan od najčešćih klasifikatora. Na primjer, na njemu je izgrađena kaskada Haar. Obično se koristi kada je potrebna binarna klasifikacija, ali ništa ne sprečava obuku za veći broj klasa.
SVM ( , , , ) Jedan od najmoćnijih klasifikatora, koji ima mnogo implementacija. U osnovi, na zadacima učenja s kojima sam se susreo, radio je slično kao i Adabusta. Smatra se prilično brzim, ali je njegov trening teži od Adabustinog i zahtijeva odabir pravog jezgra.
Tu su i neuronske mreže i regresija. Ali da bismo ih ukratko klasifikovali i pokazali po čemu se razlikuju, potreban nam je članak mnogo duži od ovoga.
________________________________________________
Nadam se da sam uspeo da dam brzi pregled korišćenih metoda bez poniranja u matematiku i opis. Možda će ovo nekome pomoći. Iako je, naravno, članak nedorečen i nema ni riječi o radu sa stereo slikama, niti o LSM-u sa Kalman filterom, niti o adaptivnom Bayesovom pristupu.
Ako vam se sviđa članak, pokušat ću napraviti drugi dio s izborom primjera kako se rješavaju postojeći problemi ImageRecognition.
I na kraju
Šta čitati?1) Jednom mi se jako svidjela knjiga “Digitalna obrada slike” B. Yanea, koja je napisana jednostavno i jasno, ali je u isto vrijeme data skoro sva matematika. Dobro za upoznavanje sa postojećim metodama.
2) Klasik žanra je R. Gonzalez, R. Woods “Digital Image Processing”. Iz nekog razloga mi je bilo teže od prvog. Mnogo manje matematike, ali više metoda i slika.
3) “Obrada i analiza slike u problemima kompjuterskog vida” - napisano na osnovu predmeta koji se izvodi na jednom od odsjeka za fiziku i tehnologiju. Postoji mnogo metoda i njihovih detaljnih opisa. Ali po mom mišljenju, knjiga ima dva velika nedostatka: knjiga je snažno fokusirana na softverski paket koji dolazi sa njom u knjizi, prečesto se opis jednostavne metode pretvara u matematičku džunglu, iz koje je teško izaći; izvući strukturni dijagram metode. Ali autori su napravili zgodnu web stranicu na kojoj je predstavljen gotovo sav sadržaj - wiki.technicalvision.ru
4) Iz nekog razloga, čini mi se da je dobra knjiga koja strukturira i povezuje sliku svijeta koja nastaje proučavanjem prepoznavanja slika i mašinskog učenja “O inteligenciji” Jeffa Hawkinsa. Tu ne postoje direktne metode, ali postoji mnogo stvari koje treba razmisliti o tome odakle potiču metode direktne obrade slike. Kada ga pročitate, shvatite da ste već vidjeli metode ljudskog mozga, ali u zadacima obrade videa.
UDC 004932:621.396
T.M. VLASOVA, V.G. KALMYKOV
ALGORITAM I PROGRAM ZA PREPOZNAVANJE KONTURA SLIKE KAO SEKVENCA DIGITALNIH LINIJSKIH SEGMENTA
Sažetak: U datom radu razmatra se algoritam prepoznavanja digitalnog direktnog segmenta u konturama binarnih slika i softverska implementacija algoritma. Korišćenje ovog algoritma za obradu slika će rezultirati prirodnijim i ekonomičnijim opisom u poređenju sa poznatim načinima opisa slika. Razmatrani algoritam i softverska implementacija mogu se koristiti i za opis kontura pri obradi polutonskih i kolor slika.
Ključne riječi: slika, kontura, digitalni ravni segmenti, algoritam, program.
Apstrakt: Ovaj robot razvija algoritam za prepoznavanje segmenata digitalnih pravih linija u konturama binarnih slika, kao i softversku implementaciju algoritma. Odabrani algoritam za sastavljanje slike će dovesti do činjenice da će opis slike biti prirodniji i ekonomičniji, usklađen s poznatim metodama kodiranja slike. Registrirani algoritam i softverska implementacija mogu se kombinirati za kodiranje kontura prilikom obrade monotonih i kolor slika. Ključne riječi: slika, kontura, presjeci digitalnih linija, algoritam, program.
Sažetak: U radu se razmatra algoritam za prepoznavanje segmenata digitalnih linija u konturama binarnih slika i softverska implementacija algoritma. Upotreba ovog algoritma prilikom obrade slika će dovesti do prirodnijeg i ekonomičnijeg opisa slika u odnosu na poznate metode. Razmatrani algoritam i softverska implementacija mogu se koristiti i za opisivanje kontura pri obradi polutonskih i kolor slika. Ključne riječi: slika, kontura, segmenti digitalnih linija, algoritam, program.
1. Uvod
Strukturna analiza kontura slike kao nizova pravih segmenata i zakrivljenih lukova jedan je od glavnih zadataka u obradi slika u svrhu njihove interpretacije u sistemima umjetne inteligencije.
U većini slučajeva, slika se može smatrati dijelom ravnine, podijeljenom na područja sa konstantnim ili promjenjivim parametrima prema nekom zakonu, na primjer, optička gustoća, boja, tekstura, koji određuju pozadinu i objekte slike. Integralno svojstvo svakog od ovih područja je njegova granica, odnosno kontura - jednostavno povezan niz koji se sastoji od ravnih segmenata i zakrivljenih lukova. Prilikom obrade rasterske slike obično se naglašavaju obrisi objekata. Međutim, konture objekata, predstavljene kao kolekcija pojedinačnih, graničnih piksela, malo su korisne za dalju obradu, jer ne izražavaju dovoljno njegovu geometrijsku suštinu.
Prepoznavanje kontura slike u obliku niza ravnih segmenata može se smatrati jednim od glavnih zadataka u procesu obrade rasterske slike. Rješavanje problema predstavljanja konture kao niza pravih segmenata omogućava nam da dobijemo opis slike u kompaktnom obliku koji je prirodan za ljudsku percepciju, nepromjenjiv prema afinim transformacijama i pogodan, posebno, za obradu neuronskim mrežama. . Segmenti linija su glavni elementi konture. Luk krivulje se također često zamjenjuje isprekidanom linijom koja je upisana u njega, kako u osnovnim principima matematičke analize, tako i u velikom broju praktičnih primjena.
Poznate metode i algoritmi, posebno oni predloženi u radu, omogućavaju dobijanje približnog rješenja, što nije prihvatljivo za sve aplikacije.
Ovaj rad ispituje prepoznavanje konture binarne slike kao niza segmenata digitalnih pravih linija bez gubitka informacija.
2. Kontura kao niz segmenata digitalnih linija
U ovom dijelu se govori o strukturnoj analizi kontura slike kao niza segmenata digitalnih linija, koji su početni podaci za segmentiranje konture na lukove digitalnih krivulja i segmente digitalnih linija.
Ograničit ćemo se na razmatranje binarnih slika, čiji su objekti u potpunosti određeni konturama koje ih ograničavaju. Lukovi digitalnih krivulja, kao i segmenti digitalnih pravih linija, formiraju se uzorkovanjem slika koje sadrže konture formirane segmentima pravih linija i lukovima krivih.
Karakteristične karakteristike ravnih segmenata i zakrivljenih lukova se gube tokom procesa transformacije. Prilikom gledanja uzorkovane slike pri dovoljnom povećanju, često je teško prepoznati pojedinačne ravne segmente i zakrivljene lukove u nizu
vertikalni i horizontalni segmenti. Dodatne poteškoće nastaju prilikom obrade zbog činjenice da se konturne linije – matematičke linije bez debljine – prikazuju na ekranu monitora kao povezane sekvence piksela, odnosno vizuelne linije sa debljinom.
Da bismo otklonili probleme koji iz toga proizlaze, sliku dobijenu iz originala kao rezultat diskretizacije smatrat ćemo dvodimenzionalnim ćelijskim kompleksom. U ovom slučaju
pikseli su dvodimenzionalni elementi ovog ćelijskog kompleksa. Osim piksela, tu su i pukotine i tačke. Pukotine su
strane piksela koji su jednodimenzionalni elementi. Tačke su krajnje tačke pukotina i kutne tačke piksela. Tačke su nuldimenzionalni elementi. Dakle
Dakle, u slučaju koji se razmatra, kontura objekta je povezani zatvoreni niz konturnih pukotina koje se graniče između piksela objekta i pozadine. Kontura se može opisati kao niz cjelobrojnih koordinata tačaka,
ograničavanje konturnih pukotina. Kao što je prikazano na , predstavljajući ravan slike kao
ćelijski kompleks pruža mnoge prednosti. Konkretno, granica regije postaje tanka kriva sa nultom površinom.
Na sl. 1 prikazuje primjer originalne konture objekta formiranog od luka krivulje i segmenta prave linije, kao i njegov digitalni ekvivalent kao niz pukotina. Tačke koje pripadaju pukotinama različitih smjerova su numerisane. Kao iu radovima, pod L-elementom podrazumijevamo povezani niz pukotina istog smjera, koji izlaze iz određene točke i završavaju se pukotinom istog ili okomitog smjera. Na sl. Na slici 1 prikazana je jedna od mogućih podjela konture na b-elemente, koji su formirani pukotinama između tačaka: (0-2), (2-4), (4-6), (6-8), (8 -9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25 ), (25-27 ), (27-0). Svaki b-element karakterišu sledeći parametri: pravac u odnosu na njegovu početnu tačku g (prihvaćeno g = 0 - za pravac gore, 1 - desno, 2 - dole, 3 - levo); l - broj pukotina u pravcu g (! = 1,2,...); smjer zadnje pukotine q u odnosu na smjer g prethodnih pukotina (q = -1 - zadnja pukotina je usmjerena lijevo u odnosu na smjer g, +1 - desno, 0 - poklapa se sa smjerom g) . Broj pukotina l će se konvencionalno nazvati “dužinom” b-elementa (0-2) g =0, !=3, q =+1. Za b-element (27-0) g =3, =1, q =0.
Metoda za odabir segmenata digitalnih pravih linija u konturi koristi sljedeće svojstvo niza L-elemenata koji formiraju segment. Takav niz uključuje b-elemente sa istim vrijednostima g, q; njihove dužine uzimaju vrijednosti!, +1. Štaviše
alternacija b-elemenata dužine!, +1 određena je kontinuiranim razlomkom dobijenim dijeljenjem cijelih brojeva n = Ax = |x1 - x2| i m = Au = |u1 - u2\, gdje su (h1zu1), (h2, u2) koordinate početne
i krajnje tačke segmenta: ili
Pretpostavimo radi određenosti da n > m Kao što slijedi iz formule (1), l - cijeli dio podjele n sa m - odgovara u segmentu digitalne prave linije broju l uzastopnih pukotina iste. smjer. Zajedno sa susjednom okomitom pukotinom čine b-element dužine!. k1 uzastopnih b-elemenata dužine l i jednog b-elementa dužine!+1 (ili k1 uzastopnih b-elemenata dužine +1 i jednog b-elementa dužine!) čine K1-element “dužine” k1 (po analogija sa b-elementom "dužine". B-element koji se po dužini razlikuje za 1 od uzastopnih b-elemenata će se zvati modifikovani b-element datog K1-elementa. Slično, k2 uzastopnih K1-elemenata “dužine” k1 i jedan K1-element “dužine” k1 +1 (ili k2 uzastopnih K1-elemenata “dužine” k1 +1 i jedan K1-element “dužine” k1) formiraju K2- element “dužine” k1. Dakle
k + k 2 + k z +... + kg
dalje dok se članovi kontinuiranog razlomka ne iscrpe. K1 -element (uglavnom K-1 -element), koji se po dužini razlikuje za 1 od uzastopnih K1 -elemenata (Kg-1 -element), nazivat će se modificiranim K1 –elementom (Kg-1 –elementom) datog K2 -element (Kg -element). Dakle, svi
Digitalni segment linije odgovara kontinuiranom razlomku, čiji elementi određuju strukturu ovog segmenta.
U skici na sl. 1, mogu se razlikovati sljedeći segmenti digitalnih pravih linija: 0-3, 3-9, 910, 10-17, 17-0.
3. Odabir segmenata digitalne linije u konturi
Prilikom obrade kontura slike, posebno binarnih slika, u nizu pukotina koje formiraju konturu, potrebno je odabrati dijelove niza koji formiraju ravne segmente. Ovaj problem se može posmatrati kao problem određivanja elemenata kontinuiranog razlomka iz niza L-elemenata konture. Ovaj problem je inverzan problemu određivanja strukture pravolinijskog segmenta iz niza članova kontinuiranog razlomka, dobijenog kao omjer razlika u koordinatama početka i kraja segmenta.
Metoda odabira segmenata digitalne linije sastoji se od uzastopnog izvođenja sljedećih radnji.
1. Identifikacija redoslijeda b-elemenata u nizu pukotina. Ova akcija zadovoljava definiciju cijelog dijela! kontinuirani razlomak (1).
2. Izdvajanje niza Kr -elemenata sa r = 1 u nizu b -elemenata, a jedan od b -elemenata svakog K1 -elementa mora sadržavati 1 pukotinu više ili manje od ostalih. Ova radnja odgovara definiciji k1. elementa kontinuiranog razlomka (1). Nakon njegovog izvršenja, vrijednost r mora se povećati za 1.
3. Identifikacija niza Kr-elemenata u nizu Kr-1 elemenata,
Štaviše, jedan od Kr-1 elemenata svakog Kr elementa mora sadržavati jedan Kr-2 element više ili manje od ostalih. Ova akcija odgovara definiciji k(-og elementa kontinuiranog razlomka (1). Nakon njegovog izvršenja, vrijednost r mora se povećati za 1.
4. Tačka 3 se ponavlja sve dok još nije moguće
formiraju Km element.
5. Odrediti granične tačke između dva susjedna b-elementa koji nisu uključeni u isti Kr-element. Ove tačke su krajnje tačke digitalnih segmenata linija koje formiraju konturu.
Razmotrimo algoritam za odabir ravnih segmenata u nizu b-elemenata
Neka [b5(/5,gs,qs)); 5 = 0,1,...,£ - niz b-elemenata koji formiraju konturu; x5,y5 - koordinate početka b-elementa; [hu, y y); y = ; r = 0,1,...,!; !< £ - множество
tačke prekida konture. Prelomne tačke definišu krajnje tačke segmenata linija koje formiraju konturu. Pronalaženje tačaka prekida znači identifikovanje ravnih segmenata koji formiraju konturu.
Svaki segment koji se razmatra karakterizira Kg element, kao i lanac
frakcija. U početnom trenutku prepoznavanja pravolinijskog segmenta, elementi odgovarajućeg kontinuiranog razlomka su jednaki 0. Segment se može smatrati prepoznatim ako se prepoznaju parametri Kr elementa, uključujući njegov red r i vrijednosti od elementi odgovarajućeg kontinuiranog razlomka.
1. Početni uslovi.
Zadane sekvence [b5 (/5, gs, qs)) i (x5,y5) .
Potrebno je pronaći koordinate tačaka prekida |x;.,y,).
k0r:= 0, k1r:= 0, k2r:= 0,..., kr:= 0 - radne vrijednosti elemenata kontinuiranog razlomka.
Uzmimo tačku 5 =0 kao početnu tačku prvog segmenta; i =0; i =0.
2. Uzmite prvi b-element u nizu kao početak prvog ravnog segmenta. Njegova početna tačka je x5,y. Dužina /=/0 je također vrijednost prvog elementa kontinuiranog razlomka.
5:=5+1; k1p:=k1p+1.
3. Provjerite za sljedeći b-element da li zajedno sa prethodnim čine K0-element.
3.1. Ako je ((d3 == d3-1) && (d3 == 73-1)&& (4 == /3-1)), onda je nastavak Kg-elementa k0p:= k0p +1; 5:= 5 + 1; i nastavak pravolinijskog segmenta. Idite na korak 3.
3.2. Ako je ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /ê-1!>1)), onda je kraj pravog segmenta. Idite na korak 5.
3.3. Ako ((&== 9z+1) && (%== 7z+1)&& ((/z+1== /z+1)1! (/z - 1 == /3+1))), zatim završetak K0 -elementa; Í̈ = Í+1.
4. Provjera nastavka/dovršenja K(-elementa.
4.1. Ako je (k == 0), onda je k ^= k^; cr:= 0; k^1p:= k1+ 1p+1; 5:=5 +1; početak elementa Km.
Idite na korak 3.
4.2. Ako je ((k iF 0)&&(k == k^)), onda je k^1p:= k^1p+1; 5:= 5+1; nastavak Ki+1 elementa. Idite na korak 3.
4.3. Ako ((k (F 0)&&((k+1== k1p)11(k1-1 == k^))), onda Í := +1; kraj Km-elementa.
Idite na korak 4.
4.4. Ako je ((^f0)&&(|k - k1r|>1)), onda je kraj segmenta direktan prijelaz na korak 5.
5. Kraj segmenta.
X] = Xs; y = Uz; k1r:= 0, k2r:= 0,., kor:= 0; k:= 0, k2:= 0,., k:= 0.
Ako (s< S), то s:= s +1; переход к п. 2.
Inače, kraj niza L-elemenata. Kraj algoritma.
U suštini, predloženi algoritam pronalazi elemente kontinuiranog razlomka i za svaki dobijeni Kt -element i provjerava da li se kontinuirani razlomak novokonstruiranog Kt -elementa poklapa s već izgrađenim.
4. Program za odabir digitalnih linija
Kao što se može vidjeti iz opisa algoritma, on sadrži značajan broj uvjetnih prijelaza, čija je upotreba u suprotnosti s preporukama strukturiranog programiranja zbog poteškoća koje nastaju prilikom otklanjanja grešaka u programima. Osim toga, broj parametara Kt unaprijed
nemoguće je odrediti, jer varijabla t nije unaprijed ograničena. Granična vrijednost t
To znači unaprijed ograničiti veličinu slike. Implementacija softvera, posebno otklanjanje grešaka predloženog algoritma trivijalnim sredstvima, značajno je otežana iz gore navedenih razloga. Poteškoće u razvoju i otklanjanju grešaka u implementaciji softvera mogu se smanjiti ako koristite moderne objektno orijentisane alate za programiranje.
Predloženi algoritam je implementiran u obliku programa LINESEGM, koji je dio laboratorijskog softverskog paketa za obradu slika u Visual C++ okruženju.
Kao početne informacije, program LINESEGM koristi sekvence L-elemenata konstruisanih za svaku od kontura obrađene slike.
Rezultat programa je povezan niz segmenata digitalnih linija konstruiranih za svaku konturu, predstavljen koordinatama krajnjih tačaka segmenata.
Kao što se vidi iz algoritma, operacije konstruisanja Kt -elemenata iz Kt-l -elemenata
iste su za sve vrijednosti t. Imajte na umu da je početna vrijednost t = 0 i da se tokom rada algoritma svaki put povećava za 1. Posebna klasa CKForLn uključuje metode koje odgovaraju operacijama algoritma. Tokom rada programa koji implementira algoritam, sa svakim povećanjem t za 1, kreira se novi objekat koji sadrži funkcije koje izvršavaju operacije algoritma za svaku vrijednost t.
S obzirom da se na nultom nivou K0 -elementi ne formiraju od K -elemenata, već od L -
elemenata, za implementaciju algoritma na nultom nivou, kreirana je posebna modifikacija klase CKForLn - klasa Cmini.
Princip rada programa je da za svaku vrijednost t program implementira objekat klase CKForLn t-tog nivoa, koji sadrži funkcije koje definiraju parametre elementa Kt. Početni parametri Kt elementa su već parametri
završeni Kt-l element, čiji su parametri određeni objektom klase CKForLn t-1
Vau nivo.
Objekti klase CKForLn se implementiraju kako se stvore uslovi, odnosno: potreba za konstruisanjem K-elementa sledećeg nivoa, i akumuliraju se u posebnom dinamičkom nizu. Objekt nultog nivoa kreira se odmah na početku programa.
Implementacija objekata u dinamičkom nizu kako se t povećava omogućava vam da ne namećete ograničenja na veličinu slike. Ograničenja veličine slike određuju se samo resursima računara koji se koristi.
Prilikom opisa rada programa koristit će se koncept završenog Kt -
element. Svaki završeni Kt -element sadrži kt Kt-l -elemenata i jedan modificirani Kt-l -element, koji sadrži kt-l ±1 Kt-2 -elemenata, za razliku od nekompletnog Kt -elementa koji ne sadrži nekompletan Kt -element.
Klasa CKForLn uključuje sljedeće metode.
1. Metoda DK(), (definirajte K-element) - odredite K-element.
Odrediti Kt -element znači odrediti broj Kt-1 -elemenata koji formiraju dati Kt -element.
2. Metoda VK§, (verifikovati K-element) - proveriti identitet dotičnog K-elementa sa K-elementom istog nivoa, koji je prethodno određen funkcijom DK() metode.
3. Metoda DEO, (definisati kraj K-elementa) - odrediti kraj K-elementa, odnosno pri definisanju Kt-elementa pronaći njegov modifikovani Kt-1-element. Funkciju metode DE() nivoa t-1 poziva funkcija metode DK() nivoa t.
4. Metoda VE(), (provjeriti kraj K -elementa) - provjeriti identitet kraja razmatranog K -elementa sa modificiranim K -elementom, prethodno određen funkcijom DE() metode.
Klasa Cmini uključuje iste metode, koje se razlikuju od metoda klase CKForLn po tome što metode klase Cmini rade sa L -elementima i određuju ili provjeravaju K0 -elemente.
Metode Cmini klase
Metode klase Cmini koriste kao početne nizove podataka L -elemenata konstruisane za svaku od kontura obrađene slike, počevši od trenutnog broja L -elementa u trenutku kada je funkcija metode pozvana.
Funkcija metode DK() klase Cmini uspoređuje parametre svakog sljedećeg L -elementa sa parametrima početnog L -elementa dok se ne poklapaju. Ako se parametri ne podudaraju, funkcija DK() provjerava da li je element K0 potpun i završava
rad. K0 -element se smatra kompletnim ako se završava modifikovanim L -elementom, čija se dužina razlikuje od ostalih L -elemenata K0 -elementa za 1 (operacija 3.1 za početak segmenta - t = 0).
Funkcija metode VK() provjerava da li se parametri sljedećih k0 L -elemenata poklapaju s parametrima L -elemenata K0 -elementa prethodno definiranih funkcijom DK() metode
isti nivo. Ako se parametri trenutnog K0 elementa poklapaju sa prethodnim
definisana, funkcija VK() formira znak za nastavak segmenta i završava posao (operacija 3.1 za nastavak segmenta - t > 0).
Inače, funkcija VK() generira znak završetka segmenta i završava
Funkcija DE() metode uspoređuje parametre trenutnog elementa Kci s parametrima elementa K0 koji je prethodno definirana DK() funkcijom kako bi se utvrdilo da li je trenutni element K0 izmijenjen. Ako su ostali parametri jednaki, broj L -elemenata k0
modifikovani K0 -element u poređenju sa prethodno određenim K0 -elementom
funkcija DK(), mora se razlikovati za 1 (operacija 3.2, 3.3 za određivanje završetka
početni K0 element segmenta - t = 0). Rezultat - parametri modificiranog K0 elementa
se koriste u metodi VE() klase Cmini.
Funkcija metode VE() uspoređuje parametre trenutnog elementa K0 s parametrima promijenjenog elementa K0 koje je prethodno odredila funkcija DE() kako bi se utvrdilo
da li se poklapaju (operacija 3.2, 3.3 za nastavak segmenta - t > 0). Rezultat - znak podudaranja ili nepodudaranja - koristi se u metodi VK() klase CKForLn.
Metode klase CKForLn
Metode koriste parametre K-elemenata konstruisanih za najniži nivo kao početne podatke. Odnosno, za određivanje parametara Kt elementa, koriste se parametri
već izgrađeni Kt-l -elementi.
Funkcija metode DK() nivoa t klase CKForLn, prilikom definisanja parametara ^-elementa, poziva funkciju VK() nivoa t-1 klase CKForLn, koja provjerava da li je već definirani Kt-l element slijedi element Kt-l sa istim parametrima. Ako jeste, ponavlja se poziv funkcije VK(). U tom slučaju se broj ponavljanja, odnosno određuje se parametar kt.
Inače, funkcija nivoa t DK() poziva funkciju t-1 nivoa DE() da odredi modifikovani Kt-l element i izlazi. Na kraju rada, funkcija DK() nivoa t klase CKForLn određuje parametre i generiše znakove završenog ili nepotpunog Kt elementa (operacija 4.1, 4.2 na trenutnoj maksimalnoj vrijednosti t).
Funkcija VK() metode nivoa t klase CKForLn provjerava da li se parametri sljedećih kt Kt -elemenata poklapaju s parametrima prethodno definiranog Kt -elementa
funkcija DK() metode istog nivoa. Ako se parametri trenutnog Kt elementa poklapaju sa
unaprijed određeno funkcijom DK() Kt -element istog nivoa, funkcija VK()
generira znak za nastavak segmenta i završava posao.
Inače, funkcija VK() generiše znak završetka segmenta i završava posao (operacija 4.1,4.2 sa trenutnom vrednošću t manjom od maksimalne).
Kt -element Funkcija DE0 metode nivoa t klase CKForLn, prilikom određivanja parametara Kt -elementa, upoređuje parametre trenutnog Kt -elementa sa parametrima Kt -elementa koji je prethodno definiran pomoću DK() funkcija za određivanje da li je trenutni Kt -element modificiran. Ako su ostali parametri jednaki, njihove kt-1 vrijednosti moraju se razlikovati za 1. Ako je ovaj uvjet ispunjen, funkcija DE() generiše znak promijenjenog Kt -elementa i
završi posao (operacija 4.3, 4.4 na trenutnoj maksimalnoj vrijednosti t).
Funkcija VE() metode nivoa t klase CKForLn uspoređuje parametre trenutnog Kt elementa s parametrima modificiranog Kt elementa koje je prethodno dodijelila funkcija DE() kako bi se utvrdilo da li se vrijednosti njihovih parametara podudaraju .
Ako se vrijednosti parametara trenutnog Kt elementa poklapaju s prethodnim
definirana DK() funkcijom istog nivoa, funkcija VK() generira znak podudarnosti vrijednosti parametara i završava posao (operacija 4.3,4.4 sa trenutnom vrijednošću t manjom od maksimalne).
Vremenski dijagram (slika 2) ilustruje rad programa LINESEGM na primjeru prepoznavanja pravolinijskog segmenta. Donji dio slike prikazuje dio digitalne linije, koji se sastoji od L-elemenata istih glavnih i pomoćnih pravaca i različitih dužina.
U koraku 0 kreiran je objekt klase Stipi koji definira parametre elementa K0.
U koraku 10 završava se određivanje parametara elementa K0 i kreira se objekat 1 klase SKrogbn, koji koristi funkcije prethodno kreiranog objekta za određivanje parametara elementa K1. U koraku 19 završava se određivanje parametara elementa K1 i kreira se objekat 2 klase SKrogbn koji koristi funkcije prethodno kreiranih objekata za određivanje parametara elementa K2. U koraku 49 završava se određivanje parametara elementa K2 i kreira se objekat 3 klase SKrogbn, koji koristi funkcije prethodno kreiranih objekata za određivanje parametara elementa K3. Korak 79 se izvršava
uslov za završetak segmenta. Rad programa je detaljno opisan u dodatku.
U sekciji 0-6, dva b-elementa čine nepotpun K0-element. Očigledno je da b -
element 3-6 dužine 3 završava linijski segment, pošto b-element 6-7 dužine 1 ne može biti njegov nastavak. Dakle, b-element 6-7 je početak segmenta digitalne linije.
Na sl. Slika 3 pokazuje primjer kako program radi. Kontura binarne slike kovrčave strelice podijeljena je kvadratima na ravne segmente. Rezultat programa - niz pravih segmenata - korišten je za isticanje lukova digitalnih krivulja. Veliki kvadrati pokazuju granice lukova digitalnih krivulja.
Rad programa je testiran na značajnom broju (više od 2000) primjera i koristi se u proučavanju strukturne analize polutonskih slika.
5. Rad programa za prepoznavanje linija
Pogledajmo rad programa iYEBESM koristeći primjer na sl. 4. Donji dio slike prikazuje dio digitalne linije, koji se sastoji od b-elemenata istih glavnih i pomoćnih pravaca i različitih dužina. U odeljku 0-6, dva b-elementa čine nepotpun K0-
Rice. 3. Primjer rada programa za strukturnu analizu konture - segmentacija konture segmentima digitalnih linija
element. Očigledno, b-element 3-6 dužine 3 završava segment, pošto b-element 6-7 dužine 1 ne može biti njegov nastavak. Dakle, b-element 6-7 je početak segmenta digitalne linije.
Rad programa za određivanje sljedećeg pravocrtnog segmenta počinje sa funkcijom OK() nultog nivoa, koja određuje završeni K0 -element 6-10, koji se sastoji od b -elemenata
dužine 1,1,2; k0=2. Ovaj K0 element je početni element za K1 element. Program kreira objekt prve razine i prenosi kontrolu na funkciju OK() ovog objekta. Funkcija OK() na nivou 1 poziva funkciju VKQ na nivou 0. Funkcija VKQ upoređuje parametre b-elemenata K0-elementa 6-10 sa narednim b-elementima i potvrđuje prisustvo K0-elementa 10 -14,
identičan K0 -elementu 6-10. Nastavljajući svoj rad, funkcija VKQ otkriva da sljedeći b elementi ne čine isti element K0, izlazi i prenosi kontrolu na funkciju nivoa 1 OK() Funkcija nivoa 1. OE() poziva. Ovaj poslednji, počevši od b-elementa 6-7, određuje prisustvo modifikovanog K0-elementa 14-19, koji se sastoji od b-elemenata dužine 1,1,1,2; k0=3, završava rad i prenosi kontrolu na OK() funkciju nivoa 1. Ova funkcija određuje prisustvo završenog K1 elementa 6-19, koji se sastoji od dva K0 -
elementi 1,1,2, (k1=2) i jedan modifikovani 1,1,1,2 (k0=3). Program kreira objekt druge razine i prenosi kontrolu na funkciju OK() ovog objekta. Funkcija OK() nivoa 2 poziva VKQ funkciju nivoa 1, koja zauzvrat poziva funkciju VKQ nivoa 0. Funkcija VKQ upoređuje parametre b elemenata K0 elemenata 6-10 sa sledećim b -
elemenata i potvrđuje prisustvo K0 elemenata 19-23, 23-27, identičnih K0 elementu 6-10, odnosno isti broj takvih K0 elemenata sadržanih u K1 elementu 6-19. Zatim, funkcija VKQ nivoa 0 vraća kontrolu sa predznakom nastavka segmenta funkcije VKQ nivoa 1. Funkcija VKQ poziva funkciju VE0 nivoa 0, koja određuje prisustvo promenjenog K0 -
element 27-32, identičan K0 -elementu 14-19. Dakle, K1-element 19-32 je definisan,
identičan K1-elementu 6-19. Nadalje, funkcija VKQ nivoa 1 ne definira sljedeći K1-element, identičan K1-elementu 6-19, zbog činjenice da VE0 funkcija nivoa 0 ne određuje promijenjeni K1-element, identičan K1-element 6-19, počevši od b-elementa 40-41, i vraća kontrolu funkciji OK() nivoa 2. Funkcija OK() nivoa 2 poziva funkciju OE() nivoa 1, koja određuje prisustvo modifikovanog K1 elementa 32-49, koji se sastoji od K0 elemenata 32-36, 36-40,
40-44, 44-49. Zatim se određuje K2 element 6-49, formira se objekat nivoa 3 i određuje se modifikovani K2 element 49-79. Ova dva elementa K2 čine K3 element 6-79. Ovim se završava konstrukcija segmenta, budući da sljedeći b-elementi 79-81 i 81-83 ne čine K0-element,
identičan K0 -elementu 6-10, a funkcija VKQ nivoa 0 ne generiše znak nastavka
segment. U nizu L-elemenata istaknut je segment digitalne linije 6-79. Program počinje određivanje sljedećeg segmenta, počevši od b-elementa 80-82.
b. zaključci
1. Predložen je novi algoritam za identifikaciju segmenata linija u konturama slike i netrivijalna softverska implementacija algoritma, koji omogućavaju dobijanje tačnog rješenja problema prepoznavanja kontura slike kao nizova segmenata linija.
2. Softverska implementacija algoritma za odabir pravih segmenata u konturama slike napravljena je korištenjem savremenih objektno orijentisanih programskih alata, što je omogućilo da se ne nameću očigledna ograničenja na veličinu obrađene slike uz maksimalnu upotrebu resursa kompjuter koji se koristi.
3. Na osnovu predloženog algoritma i njegove softverske implementacije dobijeno je teorijsko rješenje i provedeni eksperimenti na prepoznavanju lukova digitalnih krivulja i segmentiranju konture binarnih slika na segmentu digitalnih pravih i lukova digitalnih krivulja.
BIBLIOGRAFIJA
1. Kovalevsky V.A. Primjena digitalnih ravnih segmenata na ekonomično kodiranje slike, u Zborniku radova 7. međunarodne radionice, DGCI"97, Montpellier. - Francuska, 1997. - 3-5. decembar. - P. 51-62.
2. Kalmykov V.G. Strukturna metoda opisa i prepoznavanja segmenata digitalnih linija u konturama binarnih slika // Piece intelligence. - 2002. - br. 4. - P. 450-457.
3. Kalmykov V.G., Vishnevsky V.V. Analiza kontura objekata u binarnim slikama // Matematičke mašine i sistemi. - 1997. - br. 2. - Str. 68 - 71.
4. Kalmikov V.G. Luk digitalne krivulje - vrednovan i stagniran // Obrada signala i prikaz i prepoznavanje obrazaca. Zbornik radova ove sveukrajinske međunarodne konferencije. - Kijev. - 2004. - 11 - 15 zhovten.
Formulacija problema određen ciljem i mogućnostima njegovog sprovođenja.
Target. Izraditi program za razvrstavanje pravokutnih dijelova na kvalitetne i neispravne.
Mogućnosti za realizaciju zadatka određeno mogućnostima računara. Računar je sposoban da obrađuje numeričke informacije u algoritamskom nizu. Da bi se ostvarile mogućnosti računara, potrebno je simulirati problem koji se rješava.
Modeliranje pomoću računara podrazumijeva prijelaz sa stvarnog objekta (svijeta) na kodirani opis njegovih svojstava koristeći podatke i operacije na njima. Takav prijelaz se obično provodi u nekoliko faza:
Apstrakcija– izbor najbitnijih karakteristika objekta sa stanovišta zadatka.
Potrebno je provesti istraživanje koje nam omogućava da pređemo sa objekta modeliranja na predmet modeliranja, odbacujući sve nepotrebno u skladu s ciljem zadatka.
Po čemu se pravougaonik razlikuje od ostalih četvorouglova?
- Jednakost suprotnih strana.
- Paralelizam suprotnih strana.
- Jednakost dijagonala.
- Svi uglovi su pravi.
Koje su minimalne karakteristike potrebne da bi se problem riješio nedvosmisleno?
- Jednakost 2 suprotne strane + jednakost dijagonala.
- Paralelizam 2 suprotne strane + jednakost dijagonala.
- Tri ugla su prava.
Dakle, zahvaljujući apstrakciji, dobili smo verbalni informacioni model. Ali to je kompjuteru i dalje nerazumljivo. Razumije matematički model predstavljen kao algoritam i implementiran u softver.
Metodologija realizacije zadatka.
Crtež kvalitetnog dela (pravougaonik) ili neispravnog dela (četvorougao) se pravi od segmenata (komanda LINE) u grafičkom sistemu AutoCAD i eksportuje u . Program kntrs.lsp() čita podatke o segmentima (koordinate vrhova) iz DXF datoteke i upisuje ih u tekstualnu datoteku vrtks.txt kružnim redoslijedom prelaska vrhova.
Tekstualni fajl vrtks.txt se može kreirati ručno uzimajući koordinate vrha direktno sa crteža.
Razvijeni program rct.lsp mora pročitati podatke iz datoteke vrtks.txt, analizirati ih i u rezultat.txt datoteci ispisati zapis o tome da li dio ispunjava zahtjeve (pravougaonik ili ne).
Formalizacija karakteristika
Jednakost dužina segmenata (stranica ili dijagonala): Dužina svakog segmenta je određena kao hipotenuza pravougaonog pravougaonika (prema Pitagorinoj teoremi) kroz razliku u koordinatama segmenata:
(setq DX12 (abs (- X1 X2))) (setq DY12 (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
Paralelizam pravih: K2= K1, Gdje TO– nagib prave linije K=(Y2-Y1)/(X2-X1)
Kako formalizirati koncept "pravog ugla"? U okviru zadatka, prisustvo "pravog ugla" može se odrediti okomitošću segmenata: K2= -1/K1, Gdje TO– nagib prave linije. K=(Y-Y0)/(X-X0).
Prikaz modela na računaru
Svaka informacija se na kraju prikazuje u kompjuteru koristeći binarne brojeve (kodove) u model unutar mašine. Ranije je kodiranje radio programer. Danas se većina programa kreira na algoritamskim jezicima.
