Mikä on ketjukoodi?

Tietokonegrafiikassa ja kuvankäsittelyssä ketjukoodi on algoritmi, jota käytetään objektin ääriviivojen koodaamiseen mustavalkoisena tai yksivärisenä. Tuloksena oleva koodisarja voi joko kuvata, kuinka piirtää kohteen ääriviivat suhteessa kuvaan, jossa se sijaitsee, tai se voi olla kokoelma ohjeita suhteessa sijaintiin ääriviivassa, josta algoritmi alkoi, ja tarjoaa pääasiassa vaiheita, jotka voidaan piirtää objekti uudelleen. Nämä koodit voidaan normalisoida kaavan mukaan ja verrata sitten toiseen ketjukoodiin sen määrittämiseksi, ovatko kaksi objektia identtiset. Ketjukoodia voidaan käyttää objektien eristämiseen tietokoneen visio -ohjelmassa tai kuvien segmentointiin kuvankäsittelyssä, vaikka sitä voidaan yleisemmin käyttää optisten merkkien tunnistusohjelmissa.

Vaikka ketjukoodille on useita vakiintuneita algoritmeja, peruskäsite on sama jokaisessa. Ensinnäkin kohteen reuna sijaitsee, yleensä siirtämällä pikseliä pikseliltä rasterikuvan läpi. Kun sijainti on löydetty, sijainti tallennetaan ja ympäröivät reunat tunnistetaan. Sen mukaan, liikkuuko tunnistusalgoritmi myötä- tai vastapäivään, nykyistä sijaintia siirretään suuntaan tai toiseen reunaa pitkin, kunnes se palaa alkuperäiseen asentoonsa.

Aina kun nykyinen sijainti liikkuu, ketjun koodiin tallennetaan numero. Tämä luku ilmaisee yleensä suunnan, jota liikuttiin kohteen reunaa pitkin. Jos esimerkiksi ketjukoodialgoritmi seuraa suoraa reunaa oikealta vasemmalle, niin aina kun reuna jäljitetään vasemmalle, vasemmanpuoleinen numeerinen koodi lisätään koodin loppuun. Tuloksena oleva koodi on numerojono, jossa, jos sekvenssiä seurataan mielivaltaisesta lähtökohdasta ja pikseli jokaiseen vaiheeseen, objektin ääriviivat piirretään uudelleen.

Kun koodin muodostava numerojono on valmis, siihen voidaan soveltaa useita erilaisia ​​algoritmeja, jotka auttavat vertaamaan muita ketjukoodisekvenssejä. Ensinnäkin numero normalisoidaan kiertämällä aloituslukua, kunnes pienin kokonaislukuarvo on määritetty. Tällä tavalla voidaan verrata kahta saman ääriviivan omaavaa objektia riippumatta siitä, mistä kunkin objektin koodaus alkoi.

On olemassa muita monimutkaisempia versioita ketjukoodialgoritmista. Näitä ovat vektoripohjainen koodaus, jossa objektin ääriviivat kuvataan linjoilla yhdistettyjen koordinaattien sekvenssillä, vaikka tämä menetelmä voi olla häviöllinen, kun sitä käytetään hienoissa yksityiskohdissa. On olemassa myös algoritmin versio, joka käyttää suorituspituista koodausta (RLE) pakatakseen edelleen poikkeuksellisen suurten tai monimutkaisten objektien koodeja, jotta ne voidaan tallentaa tehokkaammin.