ERK'2021, Portorož, 329-332 329 Pregled 2D veriˇ znih kod Borut ˇ Zalik, Damjan Strnad, Krista Rizman ˇ Zalik, Andrej Nerat, Niko Lukaˇ c, Bogdan Lipuˇ s, David Podgorelec Univerza v Mariboru, Fakulteta za elektrotehniko, raˇ cunalniˇ stvo in informatiko E-poˇ sta: borut.zalik@um.si On 2D Chain Codes The Freeman chain code in eight directions is the old- est, the best known, and the most frequently used 2D chain code. However, there exist other chain codes, which are, together with their features, surveyed briefly in this paper. Beside Freeman chain code in eight directions, also Freeman chain code in four directions, derivations of Freeman’s chain codes, Vertex Chain Code, Three- OrThogonal Chain Code, Unsigned Manhattan Chain Co- de, and Mid-Crack Chain Code are presented and their features are exposed. 1 Uvod Od uvedbe rastrskih naprav je primerna predstavitev geo- metrijskih objektov v rastrskem prostoru ˇ se kako pomem- bna. V mnogih primerih je dovolj, ˇ ce opiˇ semo samo mejo objekta, za kar lahko uporabimo koordinate mejnih pi- kslov ali, kar je uˇ cinkoviteje, zaporedje preprostih uka- zov, ki nam povedo, kako se od podanega izhodiˇ sˇ cnega piksla premikati po obodu objekta. Temu zaporedju uka- zov pravimo veriˇ zna koda (angl. chain code). Veriˇ zne kode uporabljamo v raznih aplikacijah od razpoznavanja objektov [1] do stiskanja podatkov [2]. ˇ Clovek ne vidi in ne pomni vzorcev fotonov na mreˇ znici, ki jih mode- lira tradicionalna rastrska slika, ampak so moˇ zgani spo- sobni v delˇ cku sekunde segmentirati videno (sliko) v se- mantiˇ cne komponente in jih povezati s predhodnimi za- znavami objektov. Zato je pogosto smiselno tudi rastrsko sliko predstaviti v segmentirani obliki, pri ˇ cemer lahko posamezne segmente uˇ cinkovito predstavimo z veriˇ zno kodo, morebitne barvne informacije pa shranjujemo loˇ ce- no za vsak segment. Veriˇ zne kode ˇ ze same po sebi kompaktno predsta- vljajo rastrske objekte, saj potrebujejo do 3 bite na pik- sel, kar je obˇ cutno manj kot zapis piksla s koordinatami. Kljub temu pa veriˇ zne kode pogosto ˇ se dodatno stiskamo, pri ˇ cemer najveˇ ckrat uporabljamo prilagoditve poznanih metod stiskanja. Statistiˇ cno (Huffmanovo ali aritmetiˇ cno) kodiranje je logiˇ cna izbira, kadar so simboli abecede veriˇ z- ne kode izrazito neenakomerno porazdeljeni. Nadaljnje izboljˇ save rabe statistiˇ cnih metod so bile doseˇ zene z vpe- ljavo posebnih kod za pogoste pare simbolov [3, 4] ali z rabo veˇ c statistiˇ cnih modelov v t.i. kontekstnih pristopih [5]. Predlagane so bile tudi nestatistiˇ cne metode stiska- nja, temeljeˇ ce na transformacijah nizov [2, 6]. Stiskanje veriˇ znih kod je obiˇ cajno brezizgubno, poznamo pa tudi pristope z nadzorovanimi izgubami [4]. V tem prispevku bomo najpogostejˇ se veriˇ zne kode je- drnato opisali in jih podkrepili s primeri. 2 Predstavitev 2D veriˇ znih kod 2.1 8-smerna Freemanova veriˇ zna koda 0 1 2 3 4 5 6 7 (a) 0 1 2 3 (b) Slika 1: Ukazi veriˇ znih kod F8 in F4 8-smerna Freemanova veriˇ zna koda (angl. Freeman chain code in eight directions – F8) je najstarejˇ sa veriˇ zna koda [7]. Iz referenˇ cnega robnega piksla se lahko premak- nemo v enega izmed osmih sosednjih pikslov. Abeceda kode ima 8 simbolov: ( F 8) = f0; 1; 2; 3; 4; 5; 6; 7g (slika 1a). Postopek tvorbe veriˇ zne kode F8 je sestavljen iz naslednjih korakov: izberemo zaˇ cetni robni piksel in shranimo njegovi koordinati (x;y). Odloˇ cimo se za smer potovanja po robnih pikslih (sourna ali protiurna), nato pa skonstruiramo kodo tako, da poiˇ sˇ cemo sosednji robni pi- ksel in zapiˇ semo Freemanovo kodo premika. Kodi, ki se premika skozi srediˇ sˇ ca pikslov, pravimo srediˇ sˇ cna koda. Lastnosti veriˇ zne kode F8 so: • poloˇ zaj objekta je odvisen le od koordinat zaˇ cetne toˇ cke veriˇ zne kode (ta lastnost je dejansko skupna vsem veriˇ znim kodam), • poveˇ cevanje objekta za faktors,s2N, izvedemo tako, da vsak simbol F8 shranimos-krat. • zaporedje enakih vrednosti predstavlja zaporedje pikslov, ki si sledijo v ravni ˇ crti (vodoravni, navpiˇ cni ali pod kotom 45 o ), • ˇ ce vsakemu simbolu F8 v zaporedju priˇ stejemo vre- dnost naravnega ˇ stevilan po modulu 8, objekt za- vrtimo zan 45 o v smeri, nasprotni urinemu ka- zalcu, in obratno, ˇ ce vrednosti odˇ stejemo, objekt zavrtimo v sourni smeri. 330 2.2 4-smerna Freemanova veriˇ zna koda 4-smerna Freemanova veriˇ zna koda (angl. Freeman chain code in four directions – F4) dovoli premik iz trenutnega piksla v sosednje piksle samo preko skupnih robov. Abe- ceda kode ( F 4) =f0; 1; 2; 3g je zato manjˇ sa (slika 1b). Konstrukcija kode F4 je enaka kot pri F8, tudi lastnosti so enake, le da lahko objekt zavrtimo le za kote 90 o in 180 o . 0 0 0 0 0 5 5 6 4 2 3 3 0 0 0 0 0 2 2 2 2 2 3 3 1 1 0 0 0 0 0 0 2 2 1 1 2 1 1 (a) (b) 3 (c) 3 3 2 3 3 2 2 1 Slika 2: veriˇ zne kode (a) F8, (b) F4 in (c) lomna F4 Kodo F4 lahko uporabimo na dva naˇ cina. V prvem naˇ cinu potujemo skozi srediˇ sˇ ca pikslov tako kot pri F8, v drugem primeru pa po mejnih robovih pikslov. Takˇ sni kodi pravimo lomna veriˇ zna koda (angl. crack chain code). Primer objekta, opisanega z razliˇ cnimi Freemanovimi ve- riˇ znimi kodami, vidimo na sliki 2. 2.3 Izpeljanke Freemanove veriˇ zne kode 1. Freeman je predlagal tudi diferenˇ cno veriˇ zno kodo (angl. Chain-Difference Coding – CDC) [8]. Vsak mejni pikselp i (razen prvegap 0 in drugegap 1 ) za- kodiramo z relativno razliko kotov = \(p i p i 1 , p i 1 p i 2 ), relativne razlike pa zapiˇ semo s Freemanovo abecedo ( F 8). Izkaˇ ze se, da so statistiˇ cno najbolj verjetne razlike kotov 0 o , ki jim sledijo koti 45 o . To lastnost sta izkoristila Liu in ˇ Zalik [9], ki sta predlagala eno prvih metod za stiskanje veriˇ znih kod, temeljeˇ co na Huffmanovih kodah. 2. Bribiesca je predstavil izpeljanko veriˇ zne kode F8, ki jo imenujemo usmerjena 8-smerna Freemanova veriˇ zna koda (angl. Directional Freeman Chain Co- de of eight directions, DF8) [10]. Simbole F8 je obravnaval kot ˇ stevila, nato pa zaporedne vrednosti odˇ stel. ˇ Ce je vsota vrednosti pri sourni orientaciji 0, oz. pri protiurni -8, je veriˇ zna koda sklenjena. 3. Varianto veriˇ zne kode F4 je predstavil Nunes s so- delavci [11]. Predlagali so kodiranje relativne spre- membe obhoda, kodo pa poimenovali veriˇ zna koda razlik (angl. Differential Chain Code, DCC). Abe- ceda ( DCC) =fR;L;Sg, kjerR pomeni zasuk v desno,L, zasuk v levo inS nadaljuj v isti smeri. Koda DCC je lomna koda. 4. ˇ Zalik in Lukaˇ c sta s ciljem boljˇ sega stiskanja veriˇ zne kode F8 predstavila kodirno shemo NAD (angl. Nor- malised Angle-Difference code) [6]. Abeceda ima ˇ stiri simbole, ( NAD) =f0; 1; 2; 3g, kjer simbol 3 oznaˇ cuje, da je sprememba kota, ki sledi, veˇ cja od 45 o . Spremembe kotov so predstavljene s ko- dami NAD na naslednji naˇ cin: 0 o = 0, 45 o = 1, 45 o = 2, 90 o = 300, 90 o = 310, 135 o = 301, 135 o = 311, 180 o = 312. Avtorja sta pokazala, da je to kodiranje bolj stisljivo. 2.4 Ogliˇ sˇ cna veriˇ zna koda Leta 1999 je Bribiesca izumil zanimivo veriˇ zno kodo, ki jo imenujemo ogliˇ sˇ cna veriˇ zna koda (angl. vertex chain code – VCC) [12]. Koda VCC je definirana s ˇ stevilom robnih pikslov objekta v opazovanem ogliˇ sˇ cu, kot vidimo na sliki 3. Abeceda vozliˇ sˇ cne kode VCC sestoji iz treh simbolov, ( VCC) = f1; 2; 3g. VCC je lomna koda in se vedno sklene. Zaporedje simbolovh1; 1; 1; 1i opiˇ se objekt iz enega samega piksla, primer veˇ cjega objekta pa kaˇ ze slika 5a. Koda VCC je uporabna tudi, ko piksli niso 1 2 3 Slika 3: Simboli vozliˇ sˇ cne kode VCC ˇ stirikotniki, a v tem primeru se spremni tudi abeceda. Pri pikslih trikotne oblike je abecedaf1; 2; 3; 4; 5g, pri ˇ sestkotnih paf1; 2g. Veriˇ zna koda VCC ima naslednje lastnosti: • ravno (navpiˇ cno ali vodoravno) ˇ crto karakterizira zaporedje simbolov 2, • diagonalno ˇ crto pod kotom 45 o oznaˇ cuje izme- njujoˇ ce se zaporedje simbolov 1 in 3, • koda VCC je neobˇ cutljiva na vrtenje (za 90 o in 180 o ) in zrcaljenje, • kodo VCC lahko normaliziramo, kar nam olajˇ sa preverjanje, ali dve veriˇ zni kodi VCC opisujeta enak objekt. Zaporedje kod vrtimo tako dolgo, da zapo- redje simbolov predstavlja ˇ stevilo z najmanjˇ so vre- dnostjo, kot vidimo na naslednjem primeru: 1311232121321213113312; zasuk v desno 3112321213212131133121; zasuk v desno 1123212132121311331213; normalizirana koda • kodo VCC lahko enostavno stisnemo; ker je sta- tistiˇ cno najpogostejˇ si simbol 2, ga predstavimo z enim bitom, ostala dva simbola pa z dvema. 2.5 Tri-ortogonalna veriˇ zna koda Tri-ortogonalno veriˇ zno kodo (angl. Three OrThogonal chain code – 3OT) sta predstavila S´ achez-Cruz and Rodr´ ı- guez-Diaz [13]. Abeceda (3 OT ) =f0; 1; 2g sestoji iz treh simbolov, katerih pomen je naslednji (slika 4): • ˇ ce je smer premika enaka, kot je bila predhodna smer premika, je koda 0, • ˇ ce se smer premika spremeni tako, da je enaka smeri pred predhodno spremembo, potem je koda 1, • sicer je koda 2. 331 0 1 2 Slika 4: Simboli veriˇ zne kode 3OT 3OT je lomna koda, katere postopek konstrukcije je na- slednji: • izberemo ekstremno ogliˇ sˇ ce (na primer zgoraj levo), • izberemo smer obhoda, • prvi rob, ki ni vodoraven, dobi kodo 1, • preostale robove zakodiramo s pravili 3OT. Lastnosti kode 3OT so naslednje: • ravno (navpiˇ cno ali vodoravno) ˇ crto oznaˇ cuje za- poredje simbolov 0, • diagonalno ˇ crto pod kotom 45 o predstavlja zapo- redje simbolov 1, • koda 3OT je neobˇ cutljiva na vrtenje (za 90 o in 180 o ) in zrcaljenje. Slika 5b kaˇ ze objekt, predstavljen s 3OT. 1 1 2 2 2 2 2 2 1 1 1 1 2 2 3 3 3 3 3 3 a) b) 0 0 0 0 0 0 2 1 1 1 0 2 0 0 1 1 1 1 1 1 Slika 5: Geometrijski objekt, opisan z (a) VCC in (b) 3OT 2.6 Nepredznaˇ cena veriˇ zna koda Manhattan Nepredznaˇ cena veriˇ zna koda Manhattan (angl. Unsigned Manhattan Chain Code – UMCC) je predstavljena v [14]. Koda opisuje premikanje po robnih pikslih loˇ ceno v sme- reh x in y. ˇ Ce od koordinat x in y opazovanega piksla odˇ stejemo koordinatix iny njegovega predhodnika, do- bimo predznaˇ ceno veriˇ zno kodo Manhattan (angl. Man- hattan Chain Code – MCC). Abeceda veriˇ zne kode MCC je sestavljena iz treh simbolov, ( MCC) =f 1; 0; 1g. Na sliki 6a vidimo primer opisa meje geometrijskega ob- jekta z MCC, kode pa povzema tabela 1. Tabela 1: Veriˇ zna koda MCC za objekt iz slike 6 MCC x 1 1 1 1 1 -1 -1 0 -1 0 -1 -1 MCC y 0 0 0 0 0 -1 -1 -1 0 1 1 1 Ugotovimo, da nikoli ne moreta biti oba simbola veriˇ z- ne kode MCC po koordinatahx iny hkrati 0. Zato lahko x = 0 in y = 0 uporabimo za preklapljanje med pred- znaki, ki ji sledi par simbolov 0 ali 1, ki pove, v kateri smeri se je spremenil predznak. Na primer: 00 10 po- meni, da spremenimo predznak kodi x, 00 01 spremeni predznak kodi y, 00 11 pa obema kodama. Na ta naˇ cin dobimo nepredznaˇ ceno veriˇ zno kodo Manhattan z abe- cedo iz dveh simbolov, ( UMCC) =f0; 1g. Veriˇ zno kodo UMCC za objekt s slike 6 vidimo v tabeli 2, pri ˇ cemer predpostavimo, da je zaˇ cetni predznak v obeh sme- reh pozitiven. Poudarjeni elementi so elementi, s katerimi preklapljamo predznak. Tabela 2: Veriˇ zna koda UMCC za objekt iz slike 6 UMCC x 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 UMCC y 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 Kodo lahko ˇ se nekoliko zmanjˇ samo. Namreˇ c, v smeri, ki smo jo oznaˇ cili z 1 in pomeni spremembo predznaka, vemo, da bo naslednji simbol 1, zato ga pri zapisu lahko izpustimo. Rezultat vidimo v tabeli 3, kjer simbol ’ t ’ oznaˇ cuje mesto izpuˇ sˇ cenega simbola. Tabela 3: Reducirana veriˇ zna koda UMCC za objekt iz slike 6 UMCC x 1 1 1 1 1 0 1 t 1 0 1 0 0 0 1 1 UMCC y 0 0 0 0 0 0 1 t 1 1 0 0 1 t 1 1 UMCC ima naslednje lastnosti [14]: • Poveˇ cevanje objekta za faktors izvedemo tako, da vsak simbol, s katerim ne spreminjamo predznaka, shranimos-krat. • Kot smo omenili, predpostavimo, da je zaˇ cetna vre- dnost koordinatx iny pozitivna. Vrtenje za 180 o doseˇ zemo, ˇ ce priˇ cnemo obhod v smereh x in y, vrtenje za 90 o pa z zamenjavo vrednosti UMCC x in UMCC y . Za vrtenje za 270 o zamenjamo vre- dnosti UMCC x in UMCC y in priˇ cnemo z obhodom v smereh x in y. • Zrcaljenje glede na osY dobimo s spremembo smeri obhoda v smerix in, analogno, s spremembo smeri obhoda v smeriy objekt prezrcalimo preko osiX. • V odoravne in navpiˇ cne ˇ crte zaznamo kot zaporedje enakih simbolov v UMCC x , oziroma UMCC y . • Zaporedje simbolov 1 v UMCC x in UMCC y doloˇ ca diagonalne ˇ crte. • Normalizacijo veriˇ zne kode doseˇ zemo z naslednjim postopkom: – zaˇ casno odstranimo vse simbole za spremembo predznaka; – vrtimo simbole v UMCC x , dokler UMCC x ne predstavlja najmanjˇ se vrednosti, pri ˇ cemer oznaˇ cimo ˇ stevilo operacij vrtenja sk x ; – analogno poiˇ sˇ cemo vrednostk y za UMCCy; – doloˇ cimok =minfk x ;k y g; 332 – simbole v izvornih zaporedjih UMCC x in UM- CC x z odstranjenimi znaki za nadzor pred- znaka zavrtimok-krat; – nazadnje na ustrezna mesta vstavimo simbole za spremembo predznaka. • Pri veriˇ zni kodi UMCC enostavno doloˇ cimo tudi monotone dele geometrijskega objekta, in sicer, deli med simboli, ki nadzirajo predznak v UMCC x , so monotoni glede na os X, in analogno, deli, ki so med dvema simboloma za spremembo predznaka v UMCC y , so monotoni glede na osY . 10 10 10 10 10 -1-1 -1-1 0-1 -10 01 -11 -11 0 (a) 0 0 0 0 7 5 5 5 5 4 3 3 3 3 3 1 5 6 2 (b) Slika 6: Geometrijski objekt, opisan s (a) predznaˇ ceno veriˇ zno kodo Manhattan in (b) s srediˇ sˇ cno-lomno veriˇ zno kodo 2.7 Srediˇ sˇ cno-lomna veriˇ zna koda Srediˇ sˇ cno-lomno (angl. Mid-Crack - MC) veriˇ zno kodo sta predlagala Shih in Wong [15] s ciljem bolje oceniti la- stnosti izvornega nerasteriziranega objekta, kot sta obseg in ploˇ sˇ cina. MC kombinira srediˇ sˇ cno veriˇ zno kodo F8 z lomno kodo F4, pri tem pa povezuje srediˇ sˇ cne toˇ cke ro- bov pikslov. Abeceda ( MC) = ( F 8), pri ˇ cemer pri navpiˇ cnih robovih pikslov ne dovolimo simbolov 0 in 4 (slika 7a), pri vodoravnih pa ne 2 in 6 (slika 7b). Opis objekta z veriˇ zno kodo MC vidimo na sliki 6b. Lastnosti srediˇ sˇ cno-lomne veriˇ zne kode so enake kodi F8. (a) (b) 1 2 3 5 7 6 0 4 1 3 5 7 Slika 7: Simboli srediˇ sˇ cno-lomne veriˇ zne kode 3 Zakljuˇ cek Ker je obe Freemanovi veriˇ zni kodi (8-smerno in 4-smer- no) najlaˇ zje razumeti in implementirati, ju v praksi tudi najpogosteje sreˇ camo. F4 lahko uporabimo kot srediˇ sˇ cno ali lomno kodo. V tem ˇ clanku smo ˇ zeleli opozoriti, da ob- stajajo tudi druge veriˇ zne kode, katerih lastnosti bi lahko bile v dani situaciji primernejˇ se. Pri prav vseh veriˇ znih kodah lahko zaznamo ravne ˇ crte, med vodoravnimi in navpiˇ cnimi ˇ crtami pa ne moremo loˇ citi pri kodah VCC in 3OT. Diagonalno ˇ crto lahko zaznamo z vsemi veriˇ znimi kodami. Neobˇ cutljive na vrtenje in zrcaljenje so kode VCC, 3OT in UMCC, vrtenje vsaj za kote 90 o in 180 o omogoˇ cajo vse kode razen 3OT in VCC. Vse kode razen VCC in 3OT omogoˇ cajo skaliranje. Monotone dele geo- metrijskega objekta enostavno zazna koda UMCC, koda MC pa daje najboljˇ si pribliˇ zek dejanskega obsega in plo- ˇ sˇ cine izvornega geometrijskega objekta. ˇ Ce ˇ zelimo veriˇ zne kode dodatno stisniti, je najbolj stisljiva veriˇ zna koda 3OT [2]. Zahvala Projekt (Posploˇ sene simetrije in ekvivalence v geometrij- skih podatkih, ˇ st. N2-0181) je sofinancirala Javna agen- cija za raziskovalno dejavnost Republike Slovenije iz dr- ˇ zavnega proraˇ cuna. Literatura [1] N.B. Boodoo-Jahangeer, S. Baichoo, Face Recognition Using Chain Codes, Journal of Signal and Information Pro- cessing 4(3B), 2013, 154–157. [2] B. ˇ Zalik, D. Mongus, N. Lukaˇ c, K.R. ˇ Zalik, Efficient chain code compression with interpolative coding, Information Sciences 439–440, 2018, 39–49. [3] Y .-K. Liu, W. Wei, P.-J. Wang, B. ˇ Zalik, Compressed ver- tex chain codes. Pattern Recognition, 40(11), 2007, 2908– 2913. [4] Y .-K. Liu, B. ˇ Zalik, P.-J. Wang, D.Podgorelec, Directional difference chain codes with quasi-lossless compression and run-length encoding, Signal Processing: Image Communu- nication, 27(9), 2012, 973–984. [5] A. Akimov, A. Kolesnikov, P. Fr¨ anti, Lossless compression of map contours by context tree modeling of chain codes, Pattern Recognition, 40(3), 2007, 944–952. [6] B. ˇ Zalik, N. Lukaˇ c, Chain code lossless compression using move-to-front transform and adaptive run-length encoding, Signal Processing Image Communication 29(1), 2014, 96– 106. [7] H. Freeman, On the Encoding of Arbitrary Geometric Con- figurations, IRE Transactions on Electronic Computers, EC-12(2), 1961, 260–268. [8] H. Freeman, Computer processing of line drawing, ACM Computing Surveys, 6(1), 1974, 57–97. [9] Y .-K. Liu, B. ˇ Zalik, An efficient chain code with Huffman coding, Pattern Recognition, 38(4), 2005, 553–557. [10] E. Bribiesca, A geometric structure for two-dimensional and three-dimensional surfaces, Pattern Recognition, 25(5), 1992, 483–496. [11] P. Nunes, F. Pereira, F. Marqu´ es, Multi-grid chain coding of binary shapes, ICIP’97 Proceedings of the 1997 Interna- tional Conference on Image Processing, 3, 1997, 114–117. [12] E. Bribiesca, A new chain code, Pattern Recognition, 32(2), 1999, 235–251. [13] H. S´ achez-Cruz, R. M. Rodr´ ıguez-Diaz, Compressing bi- level images by means of a 3-bit chain code, SPIE Optical Engineering, 44(9), 2005, 1–8. [14] B. ˇ Zalik, D. Mongus, Y .-K. Liu, N. Lukaˇ c, Unsigned Man- hattan Chain Code, Journal of Visual Communication and Image Representation, 38(C) , 2016, 186–194. [15] F. Y . Shih, W.-T. Wong, A new single-pass algorithm for extracting the Mid-Crack Codes of Multiple Regions, Jo- urnal of Visual Communication and Image Representation, 3(3), 1992, 217-224.