Keletas žodžių apie modelio atpažinimą. Rastrinio vaizdo vaizdas kaip dvimatis duomenų masyvas Skaitmeninio trikampio atpažinimo pavyzdys
Kai žiūrime į dvimatį trimatės scenos vaizdą (paveiksle, fotografijoje, monitoriaus ekrane), mums atrodo, kad visi objektai, kuriuos galėtume pamatyti, jei tiesiogiai stebėtume tą pačią gyvenimo sceną, yra tiesiogiai. ten. Tuo tarpu dvimačiame vaizde mums iš tikrųjų suteikiama viskas matomas laukas, kuris atstovauja tik kai kuriuos ryškumo paskirstymo funkcija arba spalvos dvimatėje plokštumoje: f(x, y) , Kur x Ir y– Dekarto koordinatės, apibūdinančios vaizdo plokštumą.
Be to, jei priartėsite prie kompiuterio monitoriaus ekrano, pamatysite, kad vaizdas ekrane iš tikrųjų nėra lygus ir ištisinis, o yra atskira „mozaika“, susidedanti iš atskirų spalvotų stačiakampių, išdėstytų įprastoje stačiakampėje matricoje. Tai skaitmeninis vaizdas. Matematikos požiūriu skaitmeninis vaizdas yra dvimatė matrica Im, kurios dydis yra (DimXDimY), kur x yra sveikas skaičius nuo 0 iki DimX–1, apibūdinantis elemento skaičių matricos eilutėje, y yra sveikas skaičius nuo 0 iki DimY–1, apibūdinantis matricos eilutės, kurioje yra šis elementas, numeris. Šiuo atveju vadinamas pats skaitmeninio vaizdo elementas (stačiakampės matricos ląstelė). pikselių(pikselis, vaizdo elementas). Paprasčiausiu atveju kiekvienas pixelIm turi skaliarinę sveikojo skaičiaus reikšmę, proporcingą ryškumo pasiskirstymo funkcijos reikšmei f(x, y) tam tikrame plokštumos taške.
Fig. 1.1.1 kairėje yra moters veido vaizdas, pavaizduotas kaip vaizdas, o dešinėje - padidintas to paties veido (dešinės akies) vaizdo fragmentas, kur kiekvienam vaizdo elementui yra atitinkama skaitinė pikselio reikšmė nurodytas. Šviesūs vaizdo elementai atitinka b O didesnės matricos reikšmės, tamsios – mažesnės reikšmės. Skaitmeniniame vaizde nėra jokios kitos informacijos.
@Ryžiai. 1.1.1 Skaitmeninis vaizdas kaip dvimatė intensyvumo matrica
Pradedant studijuoti kompiuterinį regėjimą, reikia aiškiai suprasti, kad kompiuteryje kaip skaitmeninis vaizdas yra saugomas tik ir išimtinai dvimatis vieno ar kito formato skaičių masyvas. Bet kokius kitus duomenis, kuriuos norėtume išgauti iš vaizdo (formos, linijos, objektai, matmenys, pavaizduoto teksto turinys ir kt. ir t. t.), galime gauti tik pritaikę daugybę vaizdo apdorojimo ir analizės procedūrų. , kurią turime arba patys suprogramuoti, arba naudoti paruoštas procedūras, prieinamas gerai žinomuose vaizdų analizės programinės įrangos paketuose. Tuo pačiu metu, norint išspręsti paprastas kompiuterinio matymo problemas, paruoštų įrankių greičiausiai bus galima rasti standartinėse vaizdo apdorojimo procedūrų bibliotekose; norint išspręsti sudėtingesnes problemas, reikės derinti tam tikras paruoštas procedūras ir daug gana „įprastų“ užduočių, kurias „biologinis“ žmogaus regėjimas, atrodytų, išsprendžia lengvai ir žaismingai, kompiuterinis matymas vis dar neturi sprendimų ir vis dar jų ieško. Juk naudodamasis savo natūraliu regėjimu žmogus gali lengvai orientuotis bet kokioje aplinkoje, atpažinti objektus, pasirinkti kelią, vairuoti automobilį ir daug daug daugiau. Kodėl kompiuteris, kuris gauna vaizdą iš vaizdo kameros, negali viso to padaryti? Gal tai žmogaus akies sandara?
Tiesą sakant, žmogaus akis, kaip ir vaizdo kamera, sudaro tik „matomą lauką“, panašų į skaitmeninį vaizdą. Šiuo atveju optinė sistema, susidedanti iš vyzdžio ir lęšio, į tinklainę projektuoja dvimatį vaizdą, kuriame šviesai jautrios ląstelės („stypeliai“ ir „kūgiai“) gautą vaizdą paverčia nerviniais impulsais. Ir tik po to sudėtingas gautos informacijos apdorojimo mechanizmas, veikiantis atitinkamoje mūsų smegenų dalyje, interpretuoja šiuos impulsus kaip mums suprantamos matomos scenos vaizdą. Taigi žmonėms "regėjimo" funkciją atlieka ne tik akis, bet ir "akis + smegenys" ("jutiklis + kompiuteris") sistema. Būtent smegenyse įmontuoti informacijos apdorojimo algoritmai leidžia žmogui suprasti, ką jis mato. Šių integruotų algoritmų vaidmenį galima paaiškinti naudojant šį pavyzdį.
Kai XX amžiaus viduryje oftalmologai išmoko atlikti akies lęšiuko operacijas, daugelis nuo gimimo aklų žmonių turėjo techninių galimybių matyti. Tai yra, po tokios operacijos žmogui, kuris anksčiau buvo aklas (šviesa tiesiog neprasiskverbė pro lęšį), tinklainėje pradėjo formuotis vaizdas ir atitinkami signalai į smegenis pradėjo patekti lygiai taip pat, kaip atsitinka. sveikiems žmonėms. Deja, šiuo atveju „matyti šviesą“ nereiškia „pradėti matyti“. Kaip parodė vėlesnė istorija, dauguma „techniškai apsišvietusių“ suaugusių pacientų niekada negalėjo pasiekti reikšmingesnių rezultatų regėjimo lauke nei atpažindami paprastas geometrines figūras – ir net tam reikėjo rimtų sąmoningų jų pastangų. Žmonių atpažinimas iš veidų ir orientavimasis erdvėje jiems liko neįmanomomis užduotimis. Faktas yra tai, kad tie įtaisyti „automatinės“ vizualinės analizės mechanizmai, kurie išsivysto žmonėms ankstyvoje vaikystėje, šiems pacientams nebuvo laiku sukurti ir jie atsidūrė kompiuterio, kuriame yra vaizdų įvedimo įrenginys. , bet neturi jo analizei reikalingos programinės įrangos.
Norėdami pagaliau įsitikinti mūsų laukiančios užduoties analizuoti vaizdą, kuris yra dvimatis skaitinių duomenų masyvas, sudėtingumu, pabandykime atsidurti kompiuterinės programos, kuri nagrinėja abstrakčius skaičius, vietą. Norėdami tai padaryti, mintyse pakeiskime vaizdo suvokimo modalumą – perkelkime jį iš regėjimo į lytėjimo sritį. Įsivaizduokime dvimatę intensyvumo reikšmių masyvą kaip šachmatų lentą, kurios dydis lygus paveikslėlio dydžiui (DimXDimY), o į kiekvieno langelio centrą įterpiamas stulpelis, kurio aukštis yra proporcinga atitinkamo vaizdo pikselio vertei. Kitaip tariant, dvimatį vaizdą laikykime tam tikru sąlyginiu trimačiu paviršiumi. Fig. 1.1.2 kairėje yra moters veido fragmentas, parodytas kaip vaizdas, o dešinėje - kaip pseudo-3D reljefas.
@Ryžiai. 1.1.2. Skaitmeninis vaizdas kaip pseudo-3D reljefas
Dabar įsivaizduokite, kad nežiūrėdami į atvaizdą turite pajusti atitinkamą „reljefą“ ir pabandyti nustatyti, ką tiksliai šis „reljefas“ vaizduoja - namą, šunį ar žmogaus akį? Eksperimentai rodo, kad paprastas žmogus nesugeba susidoroti su tokia užduotimi. Netgi paprasčiausių geometrinių figūrų atpažinimas tokiame „reljefiniame“ atvaizde pareikalaus didelių pastangų ir pareikalaus sąmoningo specialių įgūdžių, strategijos ir jutimo algoritmų ugdymo. Tai, nepaisant akivaizdaus „skaitmeninio vaizdo“ objekto paprastumo, yra tikrasis kompiuterių ir mašinų regėjimo problemų sudėtingumas.
Jau seniai norėjau parašyti bendrą straipsnį, kuriame būtų patys vaizdo atpažinimo pagrindai, savotiškas pagrindinių metodų vadovas, nurodantis, kada juos naudoti, kokias problemas jie išsprendžia, ką galima padaryti vakare atsiklaupus ir kas yra geriau negalvoti apie tai, kad neturite 20 žmonių komandos.
Kai kuriuos straipsnius optinio atpažinimo tema rašau jau seniai, todėl porą kartų per mėnesį man rašo įvairūs žmonės su klausimais šia tema. Kartais apima jausmas, kad gyveni su jais skirtinguose pasauliuose. Viena vertus, jūs suprantate, kad asmuo greičiausiai yra susijusios temos profesionalas, tačiau labai mažai žino apie optinio atpažinimo metodus. O labiausiai erzina tai, kad jis bando pritaikyti metodą iš šalia esančios žinių srities, kuris yra logiškas, bet ne iki galo veikia Vaizdo atpažinimo sistemoje, tačiau to nesupranta ir labai įsižeidžia, jei pradedi jam ką nors pasakoti iš. pačius pagrindus. O turint galvoje, kad pasakojimas nuo pagrindų atima daug laiko, kurio dažnai nėra, darosi dar liūdniau.
Šis straipsnis skirtas tam, kad vaizdų atpažinimo metodais niekada nedirbęs žmogus per 10-15 minučių savo galvoje susikurtų tam tikrą pagrindinį temą atitinkantį pasaulio vaizdą ir suprastų, kuria kryptimi reikia kapstytis. Daugelis čia aprašytų metodų yra taikomi radarui ir garso apdorojimui.
Pradėsiu nuo kelių principų, kuriuos visada pradedame pasakyti potencialiam klientui arba asmeniui, norinčiam pradėti optinio atpažinimo funkciją:
- Spręsdami problemą visada eikite nuo paprasčiausio. Žmogui daug lengviau uždėti oranžinę etiketę, nei sekti žmogų, išryškinant jį kaskadomis. Daug lengviau paimti fotoaparatą su didesne raiška, nei sukurti super raiškos algoritmą.
- Griežta problemos formuluotė optinio atpažinimo metoduose yra daug svarbesnė nei sistemos programavimo problemose: vienas papildomas žodis techninėje specifikacijoje gali papildyti 50% darbo.
- Universalių atpažinimo problemų sprendimų nėra. Negalite sukurti algoritmo, kuris tiesiog „atpažins bet kokį užrašą“. Ženklas gatvėje ir teksto lapas – iš esmės skirtingi objektai. Tikriausiai įmanoma sukurti bendrą algoritmą (čia geras pavyzdys iš Google), tačiau jis pareikalaus daug didelės komandos darbo ir susideda iš dešimčių skirtingų paprogramių.
- OpenCV yra Biblija, kuri turi daug metodų ir gali išspręsti 50% beveik bet kokios problemos, tačiau OpenCV yra tik maža dalis to, ką iš tikrųjų galima padaryti. Viename tyrime buvo parašytos išvados: „Problemos negalima išspręsti naudojant OpenCV metodus, todėl ji yra neišsprendžiama“. Stenkitės to išvengti, nepatingėkite ir kiekvieną kartą blaiviai įvertinkite esamą užduotį nuo nulio, nenaudodami OpenCV šablonų.
Čia pateiktas metodų sąrašas nėra išsamus. Siūlau komentaruose pridėti kritinius metodus, kurių neparašiau ir kiekvienam priskirti po 2-3 lydinčius žodžius.
1 dalis. Filtravimas
Šioje grupėje įdėjau metodus, kurie leidžia pasirinkti vaizdų dominančias sritis jų neanalizuojant. Dauguma šių metodų taiko tam tikrą vieną transformaciją visuose vaizdo taškuose. Filtravimo lygmenyje vaizdo analizė neatliekama, tačiau filtruojami taškai gali būti laikomi sritimis, turinčiomis specialių savybių.Binarizavimas pagal slenkstį, histogramos srities pasirinkimas
Paprasčiausias transformavimas yra vaizdo binarinimas pagal slenkstį. RGB ir pilkos spalvos vaizdams slenkstis yra spalvos reikšmė. Yra idealių problemų, kuriose tokios transformacijos pakanka. Tarkime, kad norite automatiškai pasirinkti objektus baltame popieriaus lape:
Binarizacijos slenksčio pasirinkimas iš esmės lemia patį binarizacijos procesą. Šiuo atveju vaizdas buvo dvejetainis pagal vidutinę spalvą. Paprastai dvejetainis nustatymas atliekamas naudojant algoritmą, kuris adaptyviai parenka slenkstį. Toks algoritmas gali būti lūkesčių arba režimo pasirinkimas. Arba galite pasirinkti didžiausią histogramos smailę.
Binarizacija gali duoti labai įdomių rezultatų dirbant su histogramomis, įskaitant situaciją, kai vaizdą laikome ne RGB, o HSV formatu. Pavyzdžiui, segmentuoti dominančias spalvas. Šiuo principu galite sukurti ir žymų detektorių, ir žmogaus odos detektorių.
Klasikinis filtravimas: Furjė, žemo dažnio filtras, aukšto dažnio filtras
Klasikiniai radaro filtravimo ir signalų apdorojimo metodai gali būti sėkmingai taikomi atliekant įvairias šablono atpažinimo užduotis. Tradicinis radaro metodas, kuris beveik niekada nenaudojamas grynos formos vaizduose, yra Furjė transformacija (konkrečiau, FFT). Viena iš nedaugelio išimčių, kai naudojama vienmatė Furjė transformacija, yra vaizdo glaudinimas. Vaizdo analizei vienmatės transformacijos paprastai neužtenka, reikia naudoti daug daugiau išteklių reikalaujančią dvimatę transformaciją.
Tik nedaugelis žmonių tai apskaičiuoja; paprastai daug greičiau ir lengviau naudoti dominančios srities konvoliuciją su paruoštu filtru, sureguliuotu aukštiems (HPF) arba žemiems (LPF) dažniams. Šis metodas, žinoma, neleidžia atlikti spektrinės analizės, tačiau atliekant konkrečią vaizdo apdorojimo užduotį dažniausiai reikia ne analizės, o rezultato.
Paprasčiausi filtrų, pabrėžiančių žemus dažnius (Gauso filtras) ir aukštus dažnius (Gaboro filtras), pavyzdžiai.
Kiekvienam vaizdo taškui parenkamas langas ir padauginamas su tokio pat dydžio filtru. Tokios konvoliucijos rezultatas yra nauja taško reikšmė. Diegiant žemų dažnių filtrus ir aukšto dažnio filtrus gaunami tokio tipo vaizdai:
Bangelės
Bet ką daryti, jei signalo konvoliucijai naudosime kokią nors savavališką charakteristikos funkciją? Tada jis vadinsis „Wavelet transform“. Šis bangelių apibrėžimas nėra teisingas, tačiau tradiciškai daugelyje komandų bangelių analizė yra savavališko modelio paieška vaizde naudojant konvoliuciją su šio modelio modeliu. Yra klasikinių funkcijų rinkinys, naudojamas bangelių analizėje. Tai apima Haar bangelę, Morlet bangelę, Meksikos skrybėlių bangelę ir kt. Haar primityvai, apie kuriuos buvo keli mano ankstesni straipsniai (,), yra susiję su tokiomis dvimatės erdvės funkcijomis.
Aukščiau yra 4 klasikinių bangelių pavyzdžiai. 3 dimensijos Haar bangelės, 2 dimensijos Meyer bangelės, Meksikos kepurės bangelės, Daubechies bangelės. Geras išplėstinio bangelių aiškinimo pavyzdys yra blyksnio akyje radimo problema, kuriai bangelė yra pats akinimas:
Klasikinės bangelės dažniausiai naudojamos vaizdų glaudinimui arba vaizdų klasifikavimui (bus aprašyta toliau).
Koreliacija
Po tokios laisvos bangelių interpretacijos iš mano pusės verta paminėti tikrąją koreliaciją, kuri yra jų pagrindas. Tai nepakeičiamas įrankis filtruojant vaizdus. Klasikinė programa koreliuoja vaizdo srautą, kad surastų poslinkius arba optinius srautus. Paprasčiausias poslinkio detektorius tam tikra prasme taip pat yra skirtumo koreliatorius. Ten, kur vaizdai nesiderino, buvo judėjimas.
Filtravimo funkcijos
Įdomi filtrų klasė yra funkcijų filtravimas. Tai yra grynai matematiniai filtrai, leidžiantys vaizde aptikti paprastą matematinę funkciją (liniją, parabolę, apskritimą). Konstruojamas kaupiamasis vaizdas, kuriame kiekvienam pradinio vaizdo taškui nubraižytas jį generuojančių funkcijų rinkinys. Klasikiškiausia transformacija yra Hough transformacija linijoms. Šioje transformacijoje kiekvienam taškui (x;y) nubrėžiama tiesės y=ax+b taškų (a;b), kurių lygybė yra teisinga, rinkinys. Gaunate gražių nuotraukų:
(pirmas pliusas yra tam, kuris pirmas randa laimikį paveikslėlyje ir šį apibrėžimą ir paaiškina, antrasis pliusas yra tam, kuris pirmas pasako, kas čia parodyta)
Hough transformacija leidžia rasti bet kokias parametrizuojamas funkcijas. Pavyzdžiui, ratai. Yra modifikuota transformacija, leidžianti ieškoti bet kokių formų. Matematikai siaubingai mėgsta šią transformaciją. Bet apdorojant vaizdus, deja, tai ne visada veikia. Labai lėtas veikimo greitis, labai didelis jautrumas binarizacijos kokybei. Net ir idealiose situacijose man labiau patiko tenkinti kitus metodus.
Tiesių linijų Hough transformacijos analogas yra Radono transformacija. Jis apskaičiuojamas naudojant FFT, kuris suteikia našumo padidėjimą situacijoje, kai yra daug taškų. Be to, jį galima pritaikyti nebinarizuotam vaizdui.
Kontūrų filtravimas
Atskira filtrų klasė yra kraštinių ir kontūrų filtravimas. Kontūrai yra labai naudingi, kai norime pereiti nuo darbo su vaizdu prie darbo su tame vaizde esančiais objektais. Kai objektas yra gana sudėtingas, bet aiškiai atskiriamas, dažnai vienintelis būdas su juo dirbti yra pasirinkti jo kontūrus. Yra keletas algoritmų, kurie išsprendžia kontūrų filtravimo problemą:Dažniausiai naudojamas Canny, kuris veikia gerai ir kurio įdiegimas yra OpenCV (yra ir Sobel, bet prasčiau ieško kontūrų).
Kiti filtrai
Aukščiau yra filtrai, kurių modifikacijos padeda išspręsti 80-90% problemų. Tačiau be jų yra ir retesnių filtrų, naudojamų atliekant vietines užduotis. Tokių filtrų yra dešimtys, visų neišvardinsiu. Įdomūs yra iteraciniai filtrai (pavyzdžiui, aktyvaus išvaizdos modelis), taip pat keteros ir kreivės transformacijos, kurios yra klasikinio bangelių filtravimo ir analizės radono transformacijos lauke sintezė. Beamleto transformacija puikiai veikia bangelės transformacijos ir loginės analizės ribose, leidžianti paryškinti kontūrus:
Tačiau šios transformacijos yra labai specifinės ir pritaikytos retoms užduotims.
2 dalis. Loginis filtravimo rezultatų apdorojimas
Filtruojant gaunamas duomenų rinkinys, tinkamas apdoroti. Tačiau dažnai negalite tiesiog paimti ir naudoti šių duomenų jų neapdoroję. Šiame skyriuje bus keletas klasikinių metodų, leidžiančių nuo vaizdo pereiti prie objektų savybių arba prie pačių objektų.Morfologija
Perėjimas nuo filtravimo prie logikos, mano nuomone, yra matematinės morfologijos metodai (, ,). Iš esmės tai yra paprasčiausios dvejetainių vaizdų auginimo ir ardymo operacijos. Šie metodai leidžia pašalinti triukšmą iš dvejetainio vaizdo padidinant arba sumažinant esamus elementus. Yra kontūravimo algoritmai, pagrįsti matematine morfologija, tačiau dažniausiai naudojami tam tikri hibridiniai algoritmai arba algoritmų derinys.
Kontūrų analizė
Filtravimo skyriuje jau buvo paminėti ribų gavimo algoritmai. Gautos ribos gana paprastai paverčiamos kontūrais. Canny algoritmui tai vyksta automatiškai; kitiems algoritmams reikalingas papildomas dvejetainis nustatymas. Galite gauti dvejetainio algoritmo kontūrą, pavyzdžiui, naudodami vabalo algoritmą.Kontūras yra unikali objekto savybė. Tai dažnai leidžia atpažinti objektą pagal jo kontūrą. Yra galingas matematinis aparatas, leidžiantis tai padaryti. Prietaisas vadinamas kontūrų analize (,).
Jei atvirai, aš niekada negalėjau pritaikyti kontūrų analizės tikroms problemoms. Reikalingos pernelyg idealios sąlygos. Arba nėra ribos, arba per daug triukšmo. Bet jei jums reikia ką nors atpažinti idealiomis sąlygomis, kontūrų analizė yra puikus pasirinkimas. Veikia labai greitai, graži matematika ir aiški logika.
Ypatingi taškai
Vienetiniai taškai yra unikalios objekto savybės, leidžiančios objektą palyginti su pačiu savimi arba su panašiomis objektų klasėmis. Yra kelios dešimtys tokių taškų nustatymo būdų. Kai kurie metodai nustato specialius taškus gretimuose kadruose, kai kurie po ilgo laiko ir pasikeitus apšvietimui, kai kurie leidžia rasti specialius taškus, kurie tokie išlieka net ir sukant objektą. Pradėkime nuo metodų, leidžiančių rasti specialius taškus, kurie nėra tokie stabilūs, bet greitai apskaičiuojami, o tada eisime vis sudėtingiau:Pirma klasė. Specialūs taškai, kurie yra stabilūs per kelias sekundes. Tokie taškai naudojami nukreipti objektą tarp gretimų vaizdo kadrų arba sujungti vaizdus iš gretimų kamerų. Tokie taškai yra vietiniai vaizdo maksimumai, vaizdo kampai (geriausias detektorius galbūt yra Chariso detektorius), taškai, kuriuose pasiekiama didžiausia sklaida, tam tikri gradientai ir kt.
Antra klasė. Specialūs taškai, kurie yra stabilūs keičiantis apšvietimui ir nedideliems objekto judesiams. Tokie taškai pirmiausia skirti mokymui ir vėlesniam objektų tipų klasifikavimui. Pavyzdžiui, pėsčiųjų klasifikatorius arba veido klasifikatorius yra sistemos, sukurtos būtent ant tokių taškų, produktas. Kai kurios iš anksčiau paminėtų bangelių gali būti tokių taškų pagrindas. Pavyzdžiui, Haar primityvai, ieškokite svarbiausių elementų, ieškokite kitų specifinių funkcijų. Šie taškai apima tuos, kurie rasti kryptinių gradientų histogramos (HOG) metodu.
Trečia klasė. Stabilūs taškai.Žinau tik apie du visišką stabilumą užtikrinančius metodus ir apie jų modifikacijas. Tai yra SURF ir SIFT. Jie leidžia rasti specialius taškus net sukant vaizdą. Tokių taškų skaičiavimas užtrunka ilgiau, palyginti su kitais metodais, tačiau laikas yra gana ribotas. Deja, šie metodai yra patentuoti. Nors Rusijoje neįmanoma patentuoti algoritmų, todėl naudokite jį vidaus rinkai.
3 dalis. Mokymai
Trečioji pasakojimo dalis bus skirta metodams, kurie tiesiogiai neveikia su įvaizdžiu, bet leidžia priimti sprendimus. Iš esmės tai įvairūs mašininio mokymosi ir sprendimų priėmimo metodai. Neseniai Yandyx paskelbė kursą šia tema Habr, ten yra labai geras pasirinkimas. Čia jis yra tekstinėje versijoje. Norint rimtai studijuoti temą, labai rekomenduoju juos pažiūrėti. Čia pabandysiu apibūdinti kelis pagrindinius metodus, naudojamus konkrečiai modelio atpažinimui.80% situacijų mokymosi atpažinimo užduotyje esmė yra tokia:
Yra bandomasis pavyzdys, kuriame yra keletas objektų klasių. Tebūnie tai žmogaus buvimas/nebuvimas nuotraukoje. Kiekvienam vaizdui yra aibė funkcijų, kurias paryškino kuri nors funkcija, ar tai būtų Haar, HOG, SURF ar kokia nors banga. Mokymosi algoritmas turi sukurti modelį, kad galėtų analizuoti naują vaizdą ir nuspręsti, kuris objektas yra vaizde.
Kaip tai daroma? Kiekvienas bandomasis vaizdas yra taškas funkcijų erdvėje. Jo koordinatės yra kiekvienos vaizdo ypatybės svoris. Tebūnie mūsų ženklai: „Akių buvimas“, „Nosies buvimas“, „Dviejų rankų buvimas“, „Ausų buvimas“ ir tt... Visus šiuos ženklus išryškinsime naudodami turimus detektorius, kurie yra išmokyti. kūno dalys, panašios į žmogaus Žmogui tokioje erdvėje teisingas taškas būtų . Beždžionei – taškas arkliui. Klasifikatorius mokomas naudojant pavyzdžių pavyzdį. Tačiau ne visose nuotraukose buvo matyti rankos, kitose nebuvo akių, o trečioje beždžionė dėl klasifikatoriaus klaidos turėjo žmogaus nosį. Išmokytas žmogaus klasifikatorius automatiškai padalina objektų erdvę taip, kad sakytų: jei pirmoji savybė yra diapazone 0,5
Yra daug klasifikatorių. Kiekvienas iš jų geriau atlieka tam tikrą užduotį. Klasifikatoriaus parinkimas konkrečiai užduočiai iš esmės yra menas. Štai keletas gražių nuotraukų šia tema.
Paprastas dėklas, vienmatis atskyrimas
Pažiūrėkime į paprasčiausio klasifikavimo atvejo pavyzdį, kai požymio erdvė yra vienmatė ir reikia atskirti 2 klases. Situacija pasitaiko dažniau, nei manote: pavyzdžiui, kai reikia atskirti du signalus arba palyginti modelį su pavyzdžiu. Pateikiame mokymo pavyzdį. Taip sukuriamas vaizdas, kuriame X ašis yra panašumo matas, o Y ašis – įvykių su tokiu matu skaičius. Kai norimas objektas yra panašus į save, gaunamas kairysis Gausas. Kai neatrodo, tai yra teisinga. X=0,4 reikšmė atskiria imtį taip, kad neteisingas sprendimas sumažintų tikimybę priimti bet kokį neteisingą sprendimą. Tokio separatoriaus paieška yra klasifikavimo užduotis.
Maža pastaba. Kriterijus, kuris sumažina klaidą, ne visada bus optimalus. Šis grafikas yra tikrosios rainelės atpažinimo sistemos grafikas. Tokiai sistemai kriterijus pasirenkamas siekiant sumažinti tikimybę, kad pašalinis asmuo klaidingai patektų į objektą. Ši tikimybė vadinama „I tipo klaida“, „klaidingo pavojaus tikimybe“, „klaidingai teigiama“. Literatūroje anglų kalba „False Access Rate“.
) AdaBusta yra vienas iš labiausiai paplitusių klasifikatorių. Pavyzdžiui, ant jo pastatyta Haar kaskada. Paprastai naudojamas, kai reikalinga dvejetainė klasifikacija, tačiau niekas netrukdo treniruotis didesniam klasių skaičiui.
SVM ( , , , ) Vienas iš galingiausių klasifikatorių, turintis daugybę įgyvendinimų. Iš esmės, atliekant mokymosi užduotis, su kuriomis susidūriau, jis veikė panašiai kaip Adabusta. Manoma, kad jis yra gana greitas, tačiau jo mokymas yra sunkesnis nei Adabusta ir reikalauja pasirinkti tinkamą branduolį.
Taip pat yra neuroniniai tinklai ir regresija. Tačiau norint juos trumpai klasifikuoti ir parodyti, kuo jie skiriasi, mums reikia daug ilgesnio straipsnio.
________________________________________________
Tikiuosi, kad man pavyko greitai apžvelgti naudojamus metodus, nesigilindamas į matematiką ir aprašymą. Gal kam nors tai padės. Nors, žinoma, straipsnis yra neišsamus ir nėra nė žodžio apie darbą su stereo vaizdais, nei apie LSM su Kalman filtru, nei apie adaptyvų Bayes požiūrį.
Jei jums patinka straipsnis, pabandysiu padaryti antrą dalį su pavyzdžiais, kaip sprendžiamos esamos ImageRecognition problemos.
Ir, galiausiai
Ką skaityti?1) Man kažkada labai patiko B. Yane knyga „Skaitmeninis vaizdo apdorojimas“, kuri parašyta paprastai ir aiškiai, bet tuo pat metu pateikta beveik visa matematika. Tinka susipažinti su esamais metodais.
2) Žanro klasika – R. Gonzalez, R. Woods „Skaitmeninis vaizdo apdorojimas“. Kažkodėl man buvo sunkiau nei pirmasis. Daug mažiau matematikos, bet daugiau metodų ir paveikslėlių.
3) „Vaizdo apdorojimas ir analizė kompiuterinio regėjimo problemomis“ – parašyta pagal kursą, dėstomą vienoje iš Fizikos ir technologijų katedrų. Metodų ir jų detalių aprašymų yra labai daug. Tačiau, mano nuomone, knyga turi du didelius minusus: knygoje labai daug dėmesio skiriama programinės įrangos paketui, kuris yra su ja, knygoje per dažnai paprasto metodo aprašymas virsta matematinėmis džiunglėmis, iš kurių sunku ištrūkti. išvesti metodo struktūrinę schemą. Tačiau autoriai sukūrė patogią svetainę, kurioje pateikiamas beveik visas turinys – wiki.technicalvision.ru
4) Kažkodėl man atrodo, kad gera knyga, kuri struktūrizuoja ir susieja pasaulio vaizdą, susidarantį studijuojant vaizdų atpažinimą ir mašininį mokymąsi, yra Jeffo Hawkinso „Apie intelektą“. Tiesioginių metodų ten nėra, tačiau reikia daug pagalvoti, iš kur atsiranda tiesioginio vaizdo apdorojimo metodai. Skaitydami supranti, kad jau matėte žmogaus smegenų metodus, bet vaizdo apdorojimo užduotis.
UDC 004932:621.396
T.M. VLASOVA, V.G. KALMYKOVAS
ALGORITMAS IR PROGRAMA VAIZDO KONTŪRŲ KAIP SKAITMENINIŲ LINIJŲ SEGMENTŲ SEKAI ATPAŽINTI
Anotacija: Pateiktame darbe nagrinėjamas skaitmeninės tiesioginės linijos segmento atpažinimo dvejetainių vaizdų kontūruose algoritmas ir programinis algoritmo įgyvendinimas. Naudojant šį algoritmą vaizdams apdoroti, aprašymas bus natūralesnis ir ekonomiškesnis, palyginti su žinomais vaizdų aprašymo būdais. Nagrinėjamas algoritmas ir programinė įranga gali būti panaudota ir kontūrų aprašymui apdorojant pustonius ir spalvotus vaizdus.
Raktažodžiai: vaizdas, kontūras, skaitmeniniai tiesūs segmentai, algoritmas, programa.
Anotacija: Šis robotas sukuria algoritmą skaitmeninių tiesių linijų segmentams dvejetainių vaizdų kontūruose atpažinti, taip pat programinį algoritmo įgyvendinimą. Pasirinktas vaizdo sudarymo algoritmas lems tai, kad vaizdo aprašymas bus natūralesnis ir ekonomiškesnis, suderintas su žinomais vaizdo kodavimo būdais. Užregistruotas algoritmas ir programinės įrangos įgyvendinimas gali būti derinami, kad būtų koduojami kontūrai apdorojant monotoniškus ir spalvotus vaizdus. Raktažodžiai: vaizdas, kontūras, skaitmeninių linijų atkarpos, algoritmas, programa.
Anotacija: Šiame darbe aptariamas skaitmeninių linijų segmentų atpažinimo dvejetainių vaizdų kontūruose algoritmas ir algoritmo įgyvendinimas programinėje įrangoje. Šio algoritmo naudojimas apdorojant vaizdus lems natūralesnį ir ekonomiškesnį vaizdų aprašymą, palyginti su žinomais metodais. Nagrinėjamas algoritmas ir programinė įranga taip pat gali būti naudojama kontūrams apibūdinti apdorojant pustonius ir spalvotus vaizdus. Raktiniai žodžiai: vaizdas, kontūras, skaitmeninių linijų atkarpos, algoritmas, programa.
1. Įvadas
Vaizdo kontūrų, kaip tiesių atkarpų ir lenktų lankų sekų, struktūrinė analizė yra viena iš pagrindinių užduočių apdorojant vaizdus, siekiant juos interpretuoti dirbtinio intelekto sistemose.
Daugeliu atvejų vaizdas gali būti laikomas plokštumos dalimi, suskirstyta į sritis su pastoviais arba kintančiomis parametrais pagal kokį nors dėsnį, pavyzdžiui, optinį tankį, spalvą, faktūrą, kurios lemia vaizdo foną ir objektus. Neatsiejama kiekvienos iš šių sričių savybė yra jos riba, tai yra kontūras - tiesiog sujungta seka, susidedanti iš tiesių segmentų ir lenktų lankų. Apdorojant rastrinį vaizdą dažniausiai paryškinami objektų kontūrai. Tačiau objektų kontūrai, pateikiami kaip atskirų ribinių pikselių rinkinys, yra mažai naudingi tolesniam apdorojimui, nes jie nepakankamai išreiškia geometrinę esmę.
Vaizdo kontūrų atpažinimas tiesių segmentų sekos forma gali būti laikomas viena iš pagrindinių užduočių rastrinio vaizdo apdorojimo procese. Kontūro vaizdavimo kaip tiesių linijų atkarpų sekos problemos sprendimas leidžia gauti kompaktiškos formos vaizdo aprašymą, kuris yra natūralus žmogaus suvokimui, nekintamas afininių transformacijų metu ir ypač patogus apdoroti neuroniniais tinklais. . Linijos segmentai yra pagrindiniai kontūro elementai. Kreivės lankas taip pat dažnai pakeičiamas į ją įrašyta laužta linija tiek pagrindiniuose matematinės analizės principuose, tiek daugelyje praktinių pritaikymų.
Gerai žinomi metodai ir algoritmai, ypač pasiūlyti darbe, leidžia gauti apytikslį sprendimą, kuris nėra priimtinas visoms programoms.
Šiame darbe nagrinėjamas dvejetainio vaizdo kontūro atpažinimas kaip skaitmeninių tiesių linijų segmentų seka neprarandant informacijos.
2. Kontūras kaip skaitmeninių linijų atkarpų seka
Šiame skyriuje aptariama vaizdo kontūrų struktūrinė analizė kaip skaitmeninių linijų segmentų seka, kuri yra pradiniai duomenys segmentuojant kontūrą į skaitmeninių kreivių lankus ir skaitmeninių linijų segmentus.
Apsiribosime dvejetainių vaizdų svarstymu, kurių objektus visiškai nulemia juos ribojantys kontūrai. Skaitmeninių kreivių lankai, kaip ir skaitmeninių tiesių linijų segmentai, sudaromi atimant vaizdus, kuriuose yra kontūrų, sudarytų iš tiesių linijų segmentų ir kreivių lankų.
Transformacijos proceso metu prarandamos būdingos tiesių segmentų ir lenktų lankų savybės. Žiūrint atrinktą vaizdą esant pakankamam padidinimui, dažnai sunku atpažinti atskirus tiesius segmentus ir lenktus lankus iš eilės.
vertikalūs ir horizontalūs segmentai. Apdorojant atsiranda papildomų sunkumų dėl to, kad kontūro linijos - matematinės linijos be storio - monitoriaus ekrane rodomos kaip sujungtos pikselių sekos, tai yra vaizdinės linijos su storiu.
Norėdami pašalinti iš to kylančias problemas, vaizdą, gautą iš originalo dėl diskretizacijos, laikysime dvimačiu ląstelių kompleksu. Tokiu atveju
pikseliai yra šio ląstelių komplekso dvimačiai elementai. Be pikselių, yra įtrūkimų ir taškų. Įtrūkimai yra
pikselių, kurie yra vienmačiai elementai, pusės. Taškai yra įtrūkimų galiniai taškai ir taškų kampiniai taškai. Taškai yra nulinio matmens elementai. Taigi
Taigi nagrinėjamu atveju objekto kontūras yra sujungta uždara kontūro plyšių seka, besiribojanti tarp objekto pikselių ir fono. Kontūras gali būti apibūdintas kaip taškų sveikųjų skaičių koordinačių seka,
ribojantys kontūro įtrūkimus. Kaip parodyta , vaizduojanti vaizdo plokštumą kaip
ląstelių kompleksas suteikia daug privalumų. Visų pirma, regiono riba tampa plona kreive, kurios plotas yra nulinis.
Fig. 1 parodytas originalaus objekto kontūro, sudaryto iš kreivės lanko ir tiesios linijos atkarpos, pavyzdys, taip pat jo skaitmeninis atitikmuo kaip įtrūkimų seka. Skirtingų krypčių plyšiams priklausantys taškai sunumeruoti. Kaip ir darbuose, L-elementu turime omenyje sujungtą tos pačios krypties plyšių seką, išeinančią iš tam tikro taško ir baigiančią tos pačios arba statmenos krypties plyšiu. Fig. 1 paveiksle pavaizduota viena iš galimų kontūro atskyrimų į b elementus, kurie susidaro dėl įtrūkimų tarp taškų: (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). Kiekvienas b elementas apibūdinamas šiais parametrais: kryptis, palyginti su pradiniu tašku g (priimta g = 0 - krypčiai aukštyn, 1 - į dešinę, 2 - žemyn, 3 - į kairę); l - plyšių skaičius g kryptimi (! = 1,2,...); paskutinio įtrūkimo q kryptis, palyginti su ankstesnių plyšių g kryptimi (q = -1 - paskutinis įtrūkimas nukreiptas į kairę g krypties atžvilgiu, +1 - į dešinę, 0 - sutampa su kryptimi g) . Įtrūkimų skaičius l sutartinai bus vadinamas b elemento „ilgiu“, b elementui (0-2) g =0, !=3, q =+1. B elementui (27-0) g =3, =1, q =0.
Skaitmeninių tiesių atkarpų kontūre parinkimo metodas naudoja sekančią atkarpą sudarančių L elementų sekos savybę. Tokia seka apima b elementus su tomis pačiomis g, q reikšmėmis; jų ilgiai įgauna reikšmes!, +1. Be to
ilgio b elementų kaita!, +1 nustatoma pagal tęstinę trupmeną, gautą padalijus sveikuosius skaičius n = Ax = |x1 - x2| ir m = Ау = |у1 - у2\, kur (х1зу1), (х2, у2) yra pradinės koordinatės
ir atkarpos galiniai taškai: arba
Tikslumui darykime prielaidą, kad n > m. Kaip matyti iš (1) formulės, l - sveikoji n dalijimosi iš m dalis - skaitmeninės tiesės atkarpoje atitinka l iš eilės einančių to paties plyšių skaičių. kryptis. Kartu su gretimu statmenu plyšiu jie sudaro ilgio b elementą!. k1 iš eilės einantys l ilgio b elementai ir vienas ilgio b elementas!+1 (arba k1 iš eilės +1 ilgio b elementas ir vienas ilgio b elementas!) sudaro K1 „ilgio“ k1 elementą (pagal analogija su „ilgio“ b elementu). B elementas, kurio ilgis 1 skiriasi nuo iš eilės einančių b elementų, bus vadinamas modifikuotu tam tikro K1 elemento b elementu. Panašiai susidaro k2 iš eilės einančių K1 elementų, kurių „ilgis“ k1, ir vienas K1 elementas, kurio „ilgis“ k1 +1 (arba k2 iš eilės K1 elemento „ilgis“ k1 +1 ir vienas K1 elementas „ilgis“ k1). K2- „ilgio“ elementas k1. Taigi
k + k 2 + k z +... + kg
toliau, kol baigsis tęstinės frakcijos nariai. K1 elementas (paprastai K-1 elementas), kurio ilgis 1 skiriasi nuo iš eilės einančių K1 elementų (Kg-1 -elementas), bus vadinamas modifikuotu tam tikro K1 elementu (Kg-1 -elementas). K2 -elementas (Kg -elementas). Taigi, visi
Skaitmeninė linijos atkarpa atitinka tęstinę trupmeną, kurios elementai lemia šios atkarpos struktūrą.
Konspekte pav. 1, galima išskirti šiuos skaitmeninių tiesių segmentus: 0-3, 3-9, 910, 10-17, 17-0.
3. Skaitmeninės linijos atkarpų pasirinkimas kontūre
Apdorojant vaizdo kontūrus, ypač dvejetainius vaizdus, įtrūkimų sekoje, sudarančioje kontūrą, būtina pasirinkti sekos dalis, kurios sudaro tiesius segmentus. Ši problema gali būti laikoma tęstinės trupmenos elementų nustatymo iš kontūro L elementų sekos problema. Šis uždavinys yra atvirkštinis uždaviniui nustatyti tiesios linijos atkarpos struktūrą iš tęstinės trupmenos terminų sekos, gautos kaip atkarpos pradžios ir pabaigos koordinačių skirtumų santykis.
Skaitmeninės linijos segmentų pasirinkimo metodas susideda iš nuoseklaus šių veiksmų atlikimo.
1. B elementų sekos įtrūkimų sekoje identifikavimas. Šis veiksmas atitinka visos dalies apibrėžimą! tęstinė frakcija (1).
2. Kr -elementų sekos, kurios r = 1, išskyrimas b -elementų sekoje, o viename iš kiekvieno K1 -elemento b -elementų turi būti 1 plyšys daugiau ar mažiau nei kituose. Šis veiksmas atitinka tęstinės trupmenos (1) k1-ojo elemento apibrėžimą. Po jo vykdymo r reikšmė turi būti padidinta 1.
3. Kr-elementų sekos identifikavimas Kr-1 elementų sekoje,
Be to, vienas iš kiekvieno Kr elemento Kr-1 elementų turi turėti vieną Kr-2 elementą daugiau ar mažiau nei kiti. Šis veiksmas atitinka k(-ojo tęstinės trupmenos (1) elemento apibrėžimą. Jį įvykdžius r reikšmė turi būti padidinta 1.
4. 3 punktas kartojamas tol, kol dar įmanoma
sudaro Km elementą.
5. Nustatykite ribos taškus tarp dviejų gretimų b elementų, kurie nėra įtraukti į tą patį Kr elementą. Šie taškai yra skaitmeninių linijos atkarpų, sudarančių kontūrą, galiniai taškai.
Panagrinėkime b elementų sekos linijos atkarpų pasirinkimo algoritmą
Tegu [b5(/5,gs,qs)); 5 = 0,1,...,£ - kontūrą formuojančių b elementų seka; x5,y5 - b-elemento pradžios koordinatės; [hu, y y); y = ; r = 0,1,...,!; !< £ - множество
kontūro lūžio taškai. Lūžio taškai apibrėžia linijos atkarpų, sudarančių kontūrą, galinius taškus. Rasti lūžio taškus reiškia tiesių segmentų, sudarančių kontūrą, nustatymą.
Kiekvienam nagrinėjamam segmentui būdingas Kg elementas, taip pat grandinė
trupmena Pradiniu tiesios linijos atkarpos atpažinimo momentu atitinkamos tęstinės trupmenos elementai yra lygūs 0. Segmentas gali būti laikomas pripažintu, jei atpažįstami Kr elemento parametrai, įskaitant jo eilę r ir reikšmes atitinkamos tęstinės trupmenos elementai.
1. Pradinės sąlygos.
Duotos sekos [b5 (/5, gs, qs)) ir (x5,y5) .
Reikia rasti lūžio taškų koordinates |x;.,y,).
k0р:= 0, к1р:= 0, к2р:= 0,..., кр:= 0 - tęstinės trupmenos elementų darbinės vertės.
Pirmosios atkarpos pradžios tašku laikykime tašką 5 =0; i = 0; i = 0.
2. Paimkite pirmąjį sekos b elementą kaip pirmosios tiesios atkarpos pradžią. Jo pradžios taškas yra x5,y. Ilgis /=/0 taip pat yra tęstinės trupmenos pirmojo elemento reikšmė.
5:=5+1; k1p:=k1p+1.
3. Patikrinkite, ar nėra kito b elemento, ar jie kartu su ankstesniais sudaro K0 elementą.
3.1. Jei ((d3 == d3-1) && (d3 == 73-1)&& (4 == /3-1)), tai Kg elemento tęsinys k0p:= k0p +1; 5:= 5 + 1; ir tiesios atkarpos tęsinys. Eikite į 3 veiksmą.
3.2. Jei ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1)), tai tiesios atkarpos pabaiga. Eikite į 5 veiksmą.
3.3. Jei ((&== 9з+1) && (%== 7з+1)&& ((/з+1== /з+1)1! (/з - 1 == /3+1))), tada K0 -elemento užbaigimas; Ї = Ї+1.
4. K(-elemento) tęsinio/užbaigimo tikrinimas.
4.1. Jei (k == 0), tai k ^= k^; cr:= 0; k^1p:= k1+ 1p+1; 5:=5 +1; Km elemento pradžia.
Eikite į 3 veiksmą.
4.2. Jei ((k iФ 0)&&(k == k^)), tai k^1p:= k^1p+1; 5:= 5+1; Ki+1 elemento tęsinys. Eikite į 3 veiksmą.
4.3. Jei ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^))), tada Ї := +1; Km elemento pabaiga.
Eikite į 4 veiksmą.
4.4. Jei ((^ф0)&&(|к - к1р|>1)), tada atkarpos pabaiga yra tiesioginis perėjimas į 5 veiksmą.
5. Segmento pabaiga.
X] = Xs; y = Uz; k1р:= 0, к2р:= 0,., кір:= 0; k:= 0, k2:= 0,., k:= 0.
Jei (s< S), то s:= s +1; переход к п. 2.
Priešingu atveju L elementų sekos pabaiga. Algoritmo pabaiga.
Iš esmės siūlomas algoritmas suranda tęstinės trupmenos elementus ir kiekvienam gautam Kt elementui ir patikrina, ar naujai sukurto Kt elemento tęstinė trupmena sutampa su jau sudaryta.
4. Skaitmeninių linijų atkarpų parinkimo programa
Kaip matyti iš algoritmo aprašymo, jame yra nemažai sąlyginių perėjimų, kurių naudojimas prieštarauja struktūrinio programavimo rekomendacijoms dėl sunkumų, kylančių derinant programas. Be to, parametrų skaičius Kt iš anksto
neįmanoma nustatyti, nes kintamasis t nėra iš anksto ribojamas. Ribinė t reikšmė
Tai reiškia iš anksto apriboti vaizdo dydžius. Programinės įrangos diegimas, ypač siūlomo algoritmo derinimas naudojant nereikšmingas priemones, yra labai sunkus dėl aukščiau išvardytų priežasčių. Programinės įrangos diegimo kūrimo ir derinimo sunkumai gali būti sumažinti, jei naudojate modernius objektinio programavimo įrankius.
Siūlomas algoritmas realizuotas LINESEGM programos forma, kuri yra laboratorinio programinio paketo, skirto vaizdo apdorojimui Visual C++ aplinkoje, dalis.
Kaip pradinę informaciją, LINESEGM programa naudoja L elementų sekas, sudarytas kiekvienam apdoroto vaizdo kontūrui.
Programos rezultatas yra sujungta skaitmeninių linijų segmentų seka, sudaryta kiekvienam kontūrui, vaizduojama atkarpų galinių taškų koordinatėmis.
Kaip matyti iš algoritmo, Kt -elementų konstravimo iš Kt-l -elementų operacijos
yra vienodi visoms t reikšmėms. Atkreipkite dėmesį, kad pradinė reikšmė t = 0 ir algoritmo veikimo metu kaskart didėja 1. Specialioji klasė CKForLn apima metodus, atitinkančius algoritmo operacijas. Veikiant programai, kuri įgyvendina algoritmą, kiekvienam t padidinimui 1 sukuriamas naujas objektas, kuriame yra funkcijos, atliekančios algoritmo operacijas kiekvienai t reikšmei.
Atsižvelgiant į tai, kad nuliniame lygyje K0 elementai susidaro ne iš K elementų, o iš L -
elementų, algoritmui įgyvendinti nuliniame lygyje buvo sukurta speciali CKForLn klasės modifikacija - Cmini klasė.
Programos veikimo principas yra tas, kad kiekvienai t reikšmei programa realizuoja t-ojo lygio CKForLn klasės objektą, kuriame yra funkcijos, kurios nustato Kt elemento parametrus. Pradiniai Kt elemento parametrai jau yra parametrai
užbaigtas Kt-l elementas, kurio parametrus nulėmė CKForLn t-1 klasės objektas
Oho lygis.
CKForLn klasės objektai realizuojami susidarius sąlygoms, būtent: poreikiui sukonstruoti kito lygio K elementą, ir kaupiami specialiame dinaminiame masyve. Nulinio lygio objektas sukuriamas iškart programos pradžioje.
Įdiegę objektus dinaminiame masyve, kai t didėja, galite neriboti vaizdo dydžio. Vaizdo dydžio apribojimus lemia tik naudojamo kompiuterio ištekliai.
Apibūdinant programos veikimą, bus vartojama užbaigto Kt sąvoka -
elementas. Kiekviename užpildytame Kt elemente yra kt Kt-l elementų ir vienas modifikuotas Kt-l elementas, kuriame yra kt-l ±1 Kt-2 elementų, priešingai nei nepilname Kt elemente, kuriame nėra nepilno Kt. - elementas.
CKForLn klasė apima šiuos metodus.
1. Metodas DK(), (apibrėžti K elementą) – nustatyti K elementą.
Nustatyti Kt elementą reiškia nustatyti Kt-1 elementų, kurie sudaro tam tikrą Kt elementą, skaičių.
2. Metodas VK§, (patikrinti K elementą) - patikrinkite nagrinėjamo K elemento tapatumą su to paties lygio K elementu, anksčiau nustatytu DK() metodo funkcija.
3. Metodas DEO, (nurodykite K elemento pabaigą) - nustatykite K elemento galą, tai yra apibrėždami Kt elementą, raskite jo modifikuotą Kt-1 elementą. t-1 lygio metodo funkcija DE() vadinama t lygio metodo DK() funkcija.
4. Metodas VE(), (patikrinti K -elemento pabaigą) - patikrinkite svarstomo K -elemento pabaigos tapatumą su modifikuotu K -elementu, anksčiau nustatytu DE() metodo funkcija.
Cmini klasė apima tuos pačius metodus, skiriasi nuo CKForLn klasės metodų tuo, kad Cmini klasės metodai veikia su L -elementais ir nustato arba tikrina K0 -elementus.
Cmini klasės metodai
Cmini klasės metodai kaip pradinius duomenis naudoja L elementų sekos, sudarytas kiekvienam apdoroto vaizdo kontūrui, pradedant nuo dabartinio L elemento skaičiaus tuo metu, kai iškviečiama metodo funkcija.
Cmini klasės metodo funkcija DK() lygina kiekvieno sekančio L elemento parametrus su pradinio L elemento parametrais, kol jie sutampa. Jei parametrai nesutampa, funkcija DK() patikrina, ar K0 elementas yra baigtas, ir baigiasi
dirbti. K0 -elementas laikomas baigtu, jei jis baigiasi modifikuotu L -elementu, kurio ilgis nuo kitų K0 -elemento L -elementų skiriasi 1 (operacija 3.1 atkarpos pradžiai - t = 0).
Metodo funkcija VK() patikrina, ar sekančių k0 L -elementų parametrai atitinka K0 -elemento L -elementų parametrus, anksčiau apibrėžtus DK() metodo funkcija.
to paties lygio. Jei dabartinio K0 elemento parametrai sutampa su ankstesniais
apibrėžta, funkcija VK() suformuoja atkarpos tęsinio ženklą ir užbaigia darbą (operacija 3.1 atkarpos tęsimui - t > 0).
Kitu atveju funkcija VK() generuoja segmento užbaigimo ženklą ir užbaigia
DE() metodo funkcija lygina dabartinio Kci elemento parametrus su K0 elemento parametrais, anksčiau apibrėžtais DK() funkcija, kad nustatytų, ar dabartinis K0 elementas yra modifikuotas. Jei kiti parametrai lygūs, L -elementų skaičius k0
modifikuotas K0 -elementas, palyginti su anksčiau nustatytu K0 -elementu
funkcija DK(), turi skirtis 1 (operacija 3.2, 3.3, norint nustatyti užbaigimą
pradinis atkarpos K0 elementas – t = 0). Rezultatas – modifikuoto K0 elemento parametrai
yra naudojami Cmini klasės VE() metodu.
VE() metodo funkcija lygina esamo K0 elemento parametrus su pakeisto K0 elemento parametrais, anksčiau nustatytais DE() funkcija, kad nustatytų.
ar jie sutampa (operacija 3.2, 3.3 atkarpai tęsti – t > 0). Rezultatas – atitikimo arba neatitikimo ženklas – naudojamas CKForLn klasės metodu VК().
CKForLn klasės metodai
Metoduose kaip pradiniai duomenys naudojami žemiausiam lygiui sukonstruotų K elementų parametrai. Tai yra, norint nustatyti Kt elemento parametrus, naudojami parametrai
jau sukonstruoti Kt-l -elementai.
CKForLn klasės t lygio metodo funkcija DK(), apibrėždama ^-elemento parametrus, iškviečia CKForLn klasės t-1 lygio funkciją VK(), kuri patikrina, ar jau apibrėžtas Kt-l elementas. po jo seka Kt-l elementas su tais pačiais parametrais. Jei taip, VK() funkcijos iškvietimas kartojamas. Šiuo atveju skaičiuojamas pakartojimų skaičius, tai yra, nustatomas parametras kt.
Kitu atveju t-1 lygio funkcija DK() iškviečia t-1 lygio DE() funkciją, kad nustatytų pakeistą Kt-l elementą ir išeina. Darbo pabaigoje CKForLn klasės t lygio funkcija DK() nustato parametrus ir generuoja užbaigto ar neužbaigto Kt elemento ženklus (operacija 4.1, 4.2 esant esamai didžiausiai t reikšmei).
CKForLn klasės t lygio metodo VK() funkcija patikrina, ar sekančių kt Kt elementų parametrai atitinka anksčiau apibrėžto Kt elemento parametrus.
to paties lygio metodo DK() funkcija. Jei dabartinio Kt elemento parametrai sutampa su
iš anksto nustatyta funkcija DK() Kt -to paties lygio elementas, funkcija VK()
sugeneruoja segmento tęsinio ženklą ir užbaigia darbą.
Kitu atveju funkcija VK() generuoja atkarpos užbaigimo ženklą ir užbaigia darbą (operacija 4.1, 4.2, kai dabartinė t reikšmė yra mažesnė už didžiausią).
Kt -elementKlasės CKForLn t lygio DE0 metodo funkcija, nustatydama Kt -elemento parametrus, lygina esamo Kt -elemento parametrus su Kt -elemento parametrais, anksčiau apibrėžtais DK() funkcija nustatyti, ar esamas Kt elementas yra pakeistas. Jei kiti parametrai yra vienodi, jų kt-1 reikšmės turi skirtis 1. Jei ši sąlyga įvykdoma, funkcija DE() generuoja pasikeitusio Kt elemento ženklą ir
baigia darbus (operacija 4.3, 4.4 esant esamai maksimaliai t vertei).
CKForLn klasės t lygio metodo VE() funkcija lygina esamo Kt elemento parametrus su modifikuoto Kt elemento parametrais, anksčiau priskirtais DE() funkcija, kad nustatytų, ar jų parametrų reikšmės sutampa. .
Jei dabartinio Kt elemento parametrų reikšmės sutampa su ankstesnėmis
apibrėžiama to paties lygio funkcija DK(), funkcija VK() sukuria parametrų reikšmių sutapimo ženklą ir užbaigia darbą (operacija 4.3, 4.4, kai dabartinė t vertė yra mažesnė už maksimalią).
Laiko diagrama (2 pav.) iliustruoja LINESEGM programos veikimą naudojant tiesios atkarpos atpažinimo pavyzdį. Apatinėje paveikslo dalyje pavaizduota skaitmeninės linijos dalis, susidedanti iš tos pačios pagrindinės ir pagalbinės krypčių ir skirtingo ilgio L elementų.
0 žingsnyje buvo sukurtas Stipi klasės objektas, kuris apibrėžia K0 elemento parametrus.
10 žingsnyje baigiamas K0 elemento parametrų nustatymas ir sukuriamas SKrogbn klasės 1 objektas, kuris naudoja anksčiau sukurto objekto funkcijas K1 elemento parametrams nustatyti. 19 žingsnyje baigiamas K1 elemento parametrų nustatymas ir sukuriamas SKrogbn klasės 2 objektas, kuris naudoja anksčiau sukurtų objektų funkcijas, kad nustatytų K2 elemento parametrus. 49 žingsnyje baigiamas K2 elemento parametrų nustatymas ir sukuriamas SKrogbn klasės 3 objektas, kuris naudoja anksčiau sukurtų objektų funkcijas, kad nustatytų K3 elemento parametrus. 79 veiksmas vykdomas
segmento pabaigos sąlyga. Programos veikimas detaliai aprašytas priede.
Skyriuje 0-6 du b elementai sudaro nepilną K0 elementą. Akivaizdu, kad b-
3 ilgio elementas 3-6 užbaigia linijos atkarpą, nes 1 ilgio b elementas 6-7 negali būti jo tęsinys. Taigi b elementas 6-7 yra skaitmeninės linijos segmento pradžia.
Fig. 3 paveiksle parodytas programos veikimo pavyzdys. Garbanotos rodyklės dvejetainio vaizdo kontūras kvadratais padalintas į tiesius segmentus. Skaitmeninių kreivių lankams išryškinti buvo panaudotas programos rezultatas – tiesių linijų atkarpų seka. Dideli kvadratai rodo skaitmeninių kreivių lankų ribas.
Programos darbas buvo išbandytas daugybe (daugiau nei 2000) pavyzdžių ir naudojamas tiriant pustonių vaizdų struktūrinę analizę.
5. Linijos atkarpų atpažinimo programos veikimas
Pažiūrėkime į iYEBESM programos veikimą pagal pav. 4. Apatinėje paveikslo dalyje pavaizduota skaitmeninės linijos dalis, susidedanti iš tos pačios pagrindinės ir pagalbinės krypčių ir skirtingo ilgio b elementų. 0-6 skyriuje du b elementai sudaro nepilną K0-
Ryžiai. 3. Kontūro struktūrinės analizės programos darbo pavyzdys - kontūro segmentavimas skaitmeninių linijų atkarpomis
elementas. Akivaizdu, kad 3 ilgio b elementas 3-6 užbaigia linijos atkarpą, nes 1 ilgio b elementas 6-7 negali būti jo tęsinys. Taigi b elementas 6-7 yra skaitmeninės linijos segmento pradžia.
Programos, skirtos nustatyti kitą tiesės atkarpą, darbas prasideda nulinio lygio OK() funkcija, kuri nustato užbaigtą K0 elementą 6-10, susidedantį iš b elementų.
ilgiai 1,1,2; k0=2. Šis K0 elementas yra K1 elemento pradinis elementas. Programa sukuria pirmojo lygio objektą ir perduoda valdymą šio objekto funkcijai OK(). 1 lygio funkcija OK() iškviečia 0 lygio VKQ funkciją. Funkcija VKQ lygina K0 elemento 6-10 b elementų parametrus su vėlesniais b elementais ir patvirtina K0 elemento 10 buvimą. -14,
identiškas K0 -elementui 6-10. Tęsdama savo darbą, funkcija VKQ nustato, kad kiti b elementai nesudaro to paties K0 elemento, išeina ir perkelia valdymą į 1 lygio OK() funkciją.1 lygio OK() funkcija iškviečia 0 lygio OE() funkciją. Šis paskutinis elementas, pradedant b-elementu 6-7, nustato modifikuoto K0 elemento 14-19, sudaryto iš 1,1,1,2 ilgio b elementų, buvimą; k0=3, užbaigia darbą ir perkelia valdymą į 1 lygio funkciją OK(). Ši funkcija nustato užbaigto K1 elemento 6-19 buvimą, susidedantį iš dviejų K0 -
elementai 1,1,2, (k1=2) ir vienas modifikuotas 1,1,1,2 (k0=3). Programa sukuria antrojo lygio objektą ir perduoda valdymą šio objekto funkcijai OK(). 2 lygio funkcija OK() iškviečia 1 lygio VKQ funkciją, kuri, savo ruožtu, iškviečia 0 lygio VKQ funkciją. Funkcija VKQ lygina 6-10 K0 elementų b elementų parametrus su vėlesniais b -
elementus ir patvirtina, kad yra K0 elementų 19-23, 23-27, identiškų K0 elementui 6-10, tai yra tiek pat tokių K0 elementų, esančių K1 elemente 6-19. Toliau 0 lygio funkcija VKQ grąžina valdymą su 1 lygio VKQ funkcijos segmento tęsimo ženklu. VKQ funkcija iškviečia 0 lygio VE0 funkciją, kuri nustato pakeisto K0 buvimą -
elementas 27-32, identiškas K0 -elementui 14-19. Taigi apibrėžiamas K1 elementas 19-32,
identiškas K1 elementui 6-19. Be to, 1 lygio funkcija VKQ neapibrėžia kito K1 elemento, identiško K1 elementui 6-19, dėl to, kad 0 lygio funkcija VE0 neapibrėžia pakeisto K1 elemento, identiško K1 elementas 6-19, pradedant b elementu 40-41, ir grąžina valdymą 2 lygio funkcijai OK(). 2 lygio funkcija OK() iškviečia 1 lygio OE() funkciją, kuri nustato modifikuoto K1 elemento 32-49, sudaryto iš K0 elementų 32-36, 36-40, buvimas,
40-44, 44-49. Toliau nustatomas K2 elementas 6-49, formuojamas 3 lygio objektas ir nustatomas modifikuotas K2 elementas 49-79. Šie du K2 elementai sudaro K3 elementą 6-79. Tai užbaigia atkarpos konstravimą, nes kiti b elementai 79-81 ir 81-83 nesudaro K0 elemento,
identiškas K0 elementui 6-10, o 0 lygio VKQ funkcija negeneruoja tęsinio ženklo
segmentas. L elementų sekoje paryškinamas skaitmeninės linijos 6-79 segmentas. Programa pradeda nustatyti kitą segmentą, pradedant nuo b elemento 80-82.
b. išvadas
1. Pasiūlytas naujas linijų atkarpų identifikavimo vaizdo kontūruose algoritmas ir netrivialus algoritmo įgyvendinimas programinėje įrangoje, leidžiantis gauti tikslų vaizdo kontūrų atpažinimo kaip linijų atkarpų sekomis problemos sprendimą.
2. Tiesių atkarpų atrankos vaizdo kontūruose algoritmo programinis įgyvendinimas atliktas naudojant šiuolaikinius objektinio programavimo įrankius, kurie leido nenustatyti akivaizdžių apdorojamo vaizdo dydžio apribojimų, maksimaliai išnaudojant vaizdo kontūrų išteklius. naudoto kompiuterio.
3. Remiantis pasiūlytu algoritmu ir jo programiniu įgyvendinimu, gautas teorinis sprendimas ir atlikti eksperimentai atpažįstant skaitmeninių kreivių lankus ir segmentuojant dvejetainių vaizdų kontūrą skaitmeninių tiesių segmente ir skaitmeninių kreivių lankais.
BIBLIOGRAFIJA
1. Kovalevskis V.A. Skaitmeninių tiesių segmentų taikymas ekonomiškam vaizdo kodavimui, 7-ojo tarptautinio seminaro darbuose, DGCI"97, Monpeljė. - Prancūzija, 1997. - Gruodžio 3-5. - P. 51-62.
2. Kalmykovas V.G. Skaitmeninių linijų segmentų aprašymo ir atpažinimo dvejetainių vaizdų kontūruose struktūrinis metodas // Pjesės intelektas. - 2002. - Nr. 4. - P. 450-457.
3. Kalmykovas V.G., Višnevskis V.V. Objektų kontūrų analizė dvejetainiuose vaizduose // Matematinės mašinos ir sistemos. - 1997. - Nr.2. - P. 68 - 71.
4. Kalmikovas V.G. Skaitmeninės kreivės lankas – vertinamas ir sustingęs // Signalų apdorojimas ir raštų rodymas bei atpažinimas. Šios visos Ukrainos tarptautinės konferencijos medžiaga. - Kijevas. - 2004. - 11 - 15 zhovten.
Problemos formulavimas lemia tikslas ir jo įgyvendinimo galimybės.
Tikslas. Sukurkite stačiakampių dalių klasifikavimo į kokybiškas ir brokuotas programas.
Užduoties įgyvendinimo galimybės lemia kompiuterio galimybės. Kompiuteris gali apdoroti skaitmeninę informaciją algoritmine seka. Norint realizuoti kompiuterio galimybes, būtina imituoti sprendžiamą problemą.
Modeliavimas naudojant kompiuterį reiškia perėjimą nuo realaus objekto (pasaulio) prie koduoto jo savybių aprašymo, naudojant duomenis ir su jais atliekamas operacijas. Toks perėjimas paprastai atliekamas keliais etapais:
Abstrakcija– svarbiausių objekto savybių parinkimas užduoties požiūriu.
Būtina atlikti tyrimą, leidžiantį pereiti nuo modeliavimo objekto prie modeliavimo objekto, atsisakant visko, kas nereikalinga pagal užduoties tikslą
Kuo stačiakampis skiriasi nuo kitų keturkampių?
- Priešingų pusių lygybė.
- Priešingų pusių lygiagretumas.
- Įstrižainių lygybė.
- Visi kampai teisingi.
Kokių minimalių savybių reikia norint vienareikšmiškai išspręsti problemą?
- 2 priešingų kraštinių lygybė + įstrižainių lygybė.
- 2 priešingų kraštinių lygiagretumas + įstrižainių lygybė.
- Trys kampai yra teisingi.
Taigi abstrakcijos dėka gavome žodinį informacijos modelį. Bet kompiuteriui tai vis tiek nesuprantama. Jis supranta matematinį modelį, pavaizduotą kaip algoritmą ir įdiegtą programinėje įrangoje.
Užduoties įgyvendinimo metodika.
Kokybiškos dalies (stačiakampio) arba brokuotos dalies (keturkampio) brėžinys iš segmentų (komandos LINE) sudaromas AutoCAD grafinėje sistemoje ir eksportuojamas į . Programa kntrs.lsp() nuskaito duomenis apie segmentus (viršūnių koordinates) iš DXF failo ir įrašo juos į tekstinį failą vrtks.txt apskritimo tvarka, eidama viršūnes.
Tekstinį failą vrtks.txt galima sukurti rankiniu būdu, paimant viršūnių koordinates tiesiai iš brėžinio.
Sukurta rct.lsp programa turi nuskaityti duomenis iš vrtks.txt failo, juos išanalizuoti ir faile result.txt išvesti įrašą apie tai, ar dalis atitinka reikalavimus (stačiakampis ar ne).
Požymių formalizavimas
Atkarpų (kraštinių arba įstrižainių) ilgių lygybė: kiekvieno atkarpos ilgis nustatomas kaip stačiakampio stačiakampio hipotenuzė (pagal Pitagoro teoremą) per atkarpų koordinačių skirtumą:
(setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
Linijų lygiagretumas: K2= K1, Kur KAM– tiesės nuolydis K=(Y2-Y1)/(X2-X1)
Kaip įforminti „stačiojo kampo“ sąvoką? Vykdant užduotį „stačiojo kampo“ buvimą galima nustatyti pagal segmentų statmenumą: K2= -1/K1, Kur KAM– tiesės nuolydis. K=(Y-Y0)/(X-X0).
Modelio rodymas kompiuteryje
Bet kokia informacija galiausiai rodoma kompiuteryje naudojant dvejetainius skaičius (kodus) į mašinos modelį. Anksčiau kodavimą atlikdavo programuotojas. Šiais laikais didžioji dalis programų yra kuriamos algoritminėmis kalbomis.
