GradientTop
PC
Vodeći IT časopis u Srbiji
PC #237 > Iz prakse
ARHIVA BROJEVA | O ČASOPISU | POSTANI SARADNIK | PRETRAGA
preview
Prepoznata loptica
Voja Antonić
Prepoznavanje oblika na bitmapi je jedan od najozbiljnijih programerskih problema. Objedinili smo nekoliko tehnika da bismo prepoznali broj na loptici za igru Bingo
- PC #237 (Novembar 2016)
- U prodaji po ceni od 200 din

broj

Prepoznata loptica

image

Sve je započelo kao komercijalni projekat, ali se pokazalo se da je problem prepoznavanja broja na loptici tako složen, da se ubrzo pretvorio u izazov kome nije lako odoleti. Zvuči prosto: treba samo pogledati lopticu i prepoznati broj. No, kada počnemo da pišemo program, nađemo se pred problemom. Odakle početi? Najpre je to bila neuronska mreža, ali se algoritam zasnovan na sumi kvadrata grešaka pokazao boljim i lakšim za „održavanje“, jer ne zahteva dugo i neizvesno treniranje mreže.

Odmah ćemo reći da je samo prepoznavanje znaka (u ovom slučaju to je jedna ili dve cifre) najmanji od svih problema. Mnogo teže od toga je locirati sve vidljive brojeve, odabrati onaj koji je najbolji za sigurno prepoznavanje i rotirati ga za potreban ugao. Onda treba razdvojiti dve cifre (ili ustanoviti da postoji samo jedna), skalirati ih na zadatu rezoluciju i tek tada porediti sa prethodno napravljenom bazom. Da bi stvar bila još složenija, sve to treba uraditi oslanjajući se na snagu običnog mikrokontrolera, koji sadrži vrlo ograničenu količinu memorije i radi mnogo sporije od savremenih računara. Uz sve to, ceo postupak snimanja i prepoznavanja treba da bude što kraći, jer je vreme ograničeno na 500 milisekundi.

Pre svega nabrojanog, treba rešiti još i to kako snimiti lopticu, koja je lakirana tako da je sjajna i savršeno reflektuje svaki izvor svetla, a da se ti refleksi ne vide. A izvora je mnogo, jer sfernu površinu treba ravnomerno osvetliti sa svih strana.

Eliminacija refleksa izvora svetla

Za snimanje smo koristili jeftinu crno-belu kameru sa kompozitnim video izlazom. Ovde se nećemo baviti šemom veze, jer je težište na softverskom postupku. Reći ćemo samo da je upotrebljen 16-bitni RISC mikrokontroler PIC24EP512GP806, koji ima 52 KB RAM-a i radi na taktu od 120 MHz, što mu daje brzinu od 60 MIPS. Analogni signal je digitalizuje brzim 8-bitnim A/D konvertorom, a postoji još i softverski generisani VGA izlaz. Ovaj signal se ne koristi u radu uređaja, nego samo tokom razvoja softvera i podešavanja kamere, kao i tokom servisa. Na slici na VGA monitoru se, osim semplovane slike, vide i stanja nekih radnih registara, kao i sadržina RAM-a. Sa serverom se komunicira preko RS-232 porta. Postoji mišljenje da je teško raditi sa sistemom koji vas prisiljava da krenete od nule, jer ne možete da se oslonite na gotove module koje je neko drugi napravio pre vas. Naprotiv, upravo takav sistem nudi potpunu slobodu i omogućava da bez ograničenja realizujete svaku ideju koju dobijete. To će u ovom projektu biti od koristi više puta, a posebno u tehnici snimanja, kojom se potpuno eliminiše svaki refleks.

Loptica je osvetljena sa 16 belih svetlećih dioda, koje su tačkasti izvori svetla. Po osam dioda je raspoređeno u dva kruga: u širokom bliskom krugu, i u daljem uskom krugu, tako da je čitava površina osvetljena ravnomerno. Kako se onda izboriti protiv refleksa? Treba najpre upaliti svaki drugi LED i napraviti prvu ekspoziciju, a onda napraviti istu ekspoziciju sa upaljenim preostalim LED-ovima. Iz ta dva naoko jednaka snimka treba napraviti zbirni, na kome su odabrani pikseli koji su tamniji. U praksi, to će biti „kriške“ loptice na kojima nema refleksa.

Ovim će se utrošiti vreme potrebno za dve ekspozicije, što, uz najnepovoljnije vreme čekanja na vertikalni sink, iznosi čak 200 milisekundi, ali će rezultat biti savršen. Mada je svaka loptica lakirana i polirana do visokog sjaja, na snimcima će biti bez najmanjeg refleksa.

Sferne deformacije

image
Prva dva snimka su sa prvom i drugom grupom LED-ova, a treći je zbirni snimak. Pošto se refleksi nigde ne preklapaju, zbirni snimak je bez refleksa

Centriranje loptice na snimku se obavlja tako što se najpre izračuna težište svih belih piksela, zbog čega je poželjno da okolina bude crna. Posle toga, ostaje samo da se koordinate koriguju prema podacima o težištu i da se bitmapa u memoriji pomeri za potreban broj piksela.

Sferne deformacije je nemoguće ispraviti u potpunosti, što dobro znaju kartografi koji bi rado prikazali površinu Zemlje na dvodimenzionalnoj slici. Pošto u ovom slučaju nemamo obavezu da zadržimo konstantne proporcije, nego samo da brojeve učinimo što manje deformisanim, možemo da načinimo neke ispravke na bitmapi snimljene loptice. Softver će to učiniti tako što će piksele koji se nalaze na udaljenosti većoj od pola poluprečnika od centra razvući još dalje, kao da je slika od gume. Rezultat je vidljiv ako se uporede prikazane faze 2 i 3 u digitalnoj obradi bitmape. Sve sledeće korake je moguće pratiti na priloženim snimcima. Najpre se snimak ujednačava tehnikom sličnom filteru Unsharp Mask u Photoshop-u, čime se popravlja i oštrina, a onda se crne površine obeležavaju i pretvaraju u binarnu sliku.

Rezolucija slike je 220×220 piksela, što znači da frame buffer zauzima skoro čitavu memoriju, pa nema mesta za drugi bafer. Svaki piksel je 6-bitni (bitovi 0-5), pa ostaju samo po dva bita za manipulaciju tokom obrade. Neke faze u programu (kao što je na primer selekcija povezanih komponenata) zahtevaju binarnu sliku, pa je takva slika napravljena setovanjem bita 6, a kod specijalno selektovanih površina se selektuje bit 7. Srećna je okolnost da su hardver i softver za podršku VGA signala napravljeni tako da se bitovi 6 i 7 vide kao plava i crvena boja, što olakšava rad i značajno štedi vreme softverske obrade signala, jer su sve površine od interesa automatski obeležene na ekranu VGA monitora, bez posebnih potprograma.

Dalje se eliminišu razne nečistoće, kao što su zrna prašine i ogrebotine na lopticama, tako što se usamljeni pikseli ujednačavaju sa svojom okolinom. Crne površine se najpre smanjuju, pa potom proširuju za po jedan piksel, čime se ispravljaju neravne granične linije, bez gubitka oštrine.

Manipulacija komponentama snimka

Važan korak u obradi je ono što se u teoriji zove selekcija povezanih komponenata. Treba selektovati (setovanjem bita 6) jednu po jednu površinu u kojoj se svi pikseli međusobno dodiruju, a nepovezana „ostrva“ odvojiti međusobno. Pritom se na svakoj od komponenata registruju gabariti (maksimalne i minimalne X i Y koordinate), što će pomoći da se razlikuju krugovi oko brojeva od samih cifara, kao i da se eliminišu premale površine, koje nikako ne bi mogle da budu cifre.

Sada se već ulazi u „više sfere“ obrade, jer se ne operiše sa pikselima, nego sa komponentama i njihovim koordinatama. Podaci o svim komponentama koje bi (sudeći po gabaritima) mogle da budu cifre, stavljaju se u zasebnu tabelu, a međusobna rastojanja njihovih težišta se koriste za uparivanje cifara. Kad se težišta parova uporede sa težištima komponenata velikih gabarita (koji su verovatno krugovi oko brojeva), zaključuje se koje od tih grupa su ispravno zaokružene celine. Sada je lako odabrati celinu koja je najbliža centru, pa se sva dalja pažnja poklanja samo njoj.

Svaki od brojeva je na loptici podvučen tankim linijama, što se koristi za merenje ugla pod kojim se broj nalazi. Testira se specifična grupa piksela koja čini slovo „T“, zapravo oblik ispod broja. Ova grupa piksela se posle svakog testa rotira za po jedan stepen, pa se time proskenira ceo krug i registruje se ugao sa najboljim rezultatom. To je ugao pod kojim se nalazi broj, pa ga samo treba rotirati za inverzan ugao. Posle toga je lakše – ako je broj dvocifren, cifre se obeležavaju različitim bojama i malo se rastave za svaki slučaj, pa se svaka od cifara skalira na jednaku rezoluciju. Sve je spremno za prepoznavanje.

Prepoznavanje

image
Ovo su sve faze postupka lociranja i prepoznavanja brojeva. Snimci su napravljeni fotoaparatom, jer ceo sistem čini samo jedan mikrokontroler, koji nema opciju screenshot

Najpre se prave histogrami za površine na kojima se očekuju linije kojima su napisani brojevi. Leva linija, desna, gornja, donja i srednja horizontalna. Dodaje se još i kosa rastuća linija, jer je ona od koristi za prepoznavanje brojeva 2 i 7, pošto oni sadrže baš takvu liniju. Onda se ti histogrami porede sa snimljenim histogramima za referentne loptice, po obrascu Mean Square Error. Za svaku cifru se utvrđuje zbir kvadrata grešaka u poređenju, pa se cifra koja je generisala najmanju zbirnu grešku usvaja kao prepoznata. Taj algoritam se u teoriji prepoznavanja oblika zove „glasanje“. Time je prepoznavanje skoro završeno, jer je preostalo samo još da se utvrdi ocena kvaliteta prepoznavanja, koja će pomoći da procenimo koliko je prepoznavanje bilo sigurno. Zbir grešaka „pobednika“ (prepoznatog broja) se uporedi sa „drugoplasiranim“. Što je ova razlika veća, prepoznavanje je uspešnije. Ako je broj dvocifren, za ukupnu ocenu prepoznavanja se uzima lošija od dve ocene.

Čemu služi ova ocena? Tome da se, ako je suviše loša, čitav postupak odbaci, loptica se repozicionira (malo okrene) i sve se ponovi od početka, uključujući i snimanje. Ovo se u praksi događa otprilike sa svakom desetom lopticom, ali čini čitanje brojeva veoma sigurnim.

Postoji još sigurniji sistem, koji zahteva više od 500 milisekundi, ali garantuje praktično stoprocentnu sigurnost. Svaka loptica se čita dva puta (sa repozicioniranjem između), pa se prepoznati brojevi uporede. Ako su jednaki, onda ne treba više sumnjati u tačnost čitanja.

Tačnost čitanja

Nakon završetka izrade softvera i prvih podešavanja, u jednoj beogradskoj firmi, koja se bavi proizvodnjom kazino opereme, izvršen je opsežan test. Postavljen je mehanizam koji meša loptice i posle svakog ciklusa postavi jednu od loptica pred kameru. Sve je automatizovano, a posebna kamera je snimala čitav sklop, zajedno sa lopticom i displejem koji prikazuje rezultat prepoznavanja. Snimci su pakovani u fajlove kojima je dat naziv koji započinje prepoznatim brojem, pa su fajlovi sortirani i izvršena je ručna provera svih snimaka.

Posle 115.000 ciklusa, što je trajalo oko deset dana po 24 sata dnevno, pokazalo se da je u samo jednom slučaju loptica bila pogrešno pročitana. To je obavljeno u single modu (nije bilo dvostrukog čitanja, koje bi trajalo duže), ali se može pretpostaviti da bi u slučaju dvostrukog čitanja loptica sve prošlo bez greške.

Zaključak

Uređaj je ispunio sva očekivanja, a neka čak i prevazišao. Čitanje je, uz nešto manju sigurnost i češće ponavljanje, moguće i kod starih i oštećenih loptica, jer sistem često „vidi“ dovoljno za uspešno poređenje čak i ako cifre nisu kompletne.

Pre optičkog prepoznavanja, u upotrebi su bili sistemi sa bar-kodom na lopticama, a zatim i sa RFID tagovima. Prvi sistem je bio nepouzdan u radu, a drugi je davao solidne rezultate, ali su specijalne loptice teže i skuplje od običnih, a treba ih često menjati, jer se lome tokom rada. Sistem koji je ovde opisan objedinjuje najbolje osobine svih prethodnih sistema i usvojen je kao najpouzdaniji.

I na kraju, najvažniji zaključak: pravo je zadovoljstvo razvijati ovako napredne, „pametne“ sisteme. Posao je obiman, ali na kraju ništa ne može da se uporedi sa osećanjem da ste napravili ovako dobro zaokružen i stabilan uređaj.

SLEDEĆI TEKST U PC #237
preview
ELKO iNELS pametne kuće
Dejan Ristanović


.

PC
Twitter Facebook Feed Newsletter