Hva er en kjedekode?

I datamaskingrafikk og bildebehandling er en kjedekode en algoritme som brukes til å kode konturene til et objekt i et svart-hvitt eller svart-hvitt bilde. Den resulterende kodesekvensen kan enten beskrive hvordan man tegner omrisset av objektet i forhold til bildet det befinner seg i, eller det kan være en samling veibeskrivelser i forhold til stedet på omrisset der algoritmen startet, og i det vesentlige gi trinn som kan følges for å tegne gjenstanden på nytt. Disse kodene kan normaliseres i henhold til en formel og deretter sammenlignes med en annen kjedekode for å bestemme om to objekter er identiske. En kjedekode kan brukes til å isolere objekter i et datavisjonsprogram eller bildesegmentering i bildebehandling, selv om den oftere kan brukes i OCR-programmer.

Selv om det er flere etablerte algoritmer for en kjedekode, er grunnkonseptet det samme i hver. Først er kanten til et objekt lokalisert, vanligvis ved å flytte piksel for piksel gjennom et rasterbilde. Når den er lokalisert, blir stillingen registrert og de omkringliggende kantene blir oppdaget. Avhengig av om deteksjonsalgoritmen vil bevege seg med klokken eller mot klokken, blir den gjeldende plasseringen flyttet i en eller annen retning langs kanten til den kommer tilbake til den opprinnelige posisjonen.

Hver gang den nåværende posisjonen beveger seg, registreres et nummer i kjedekoden. Dette tallet indikerer generelt retningen som ble beveget langs kanten av objektet. For eksempel, hvis en kjedekodealgoritme følger en rett kant fra høyre til venstre, legges den numeriske koden for venstre til hver på slutten av koden hver gang kanten spores til venstre. Den resulterende koden er en streng med tall der, hvis sekvensen følges fra et vilkårlig utgangspunkt og en piksel plassert ved hvert trinn, vil omrisset til objektet bli tegnet på nytt.

Når strengen med tall som utgjør koden er fullført, kan flere forskjellige algoritmer brukes på den for å gjøre sammenligninger med andre kjedekodesekvenser. Først normaliseres tallet ved å rotere startnummeret til den laveste heltallverdien er bestemt. På denne måten kan to objekter som har samme omriss sammenlignes, uavhengig av hvor på hvert objekt kodingen startet.

Andre, mer komplekse versjoner av kjedekodealgoritmen eksisterer. Disse inkluderer vektorbasert koding der omrisset til et objekt er beskrevet av en sekvens av koordinater som er forbundet med linjer, selv om denne metoden kan være tapt når den brukes på fint detaljerte konturer. Det finnes også en versjon av algoritmen som bruker kjørelengdekoding (RLE) for ytterligere å komprimere kodene for eksepsjonelt store eller komplekse objekter slik at de kan lagres på en mer effektiv måte.