Vad är en kedjekod?

Vid datorgrafik och bildbehandling är en kedjekod en algoritm som används för att koda konturerna för ett objekt i en svartvit, eller monokrom bild. Den resulterande kodsekvensen kan antingen beskriva hur man drar konturen för objektet i förhållande till bilden där det är beläget, eller det kan vara en samling riktningar i förhållande till platsen på konturen där algoritmen startade, vilket väsentligen ger steg som kan följas för att rita om objektet. Dessa koder kan normaliseras enligt en formel och sedan jämföras med en annan kedjekod för att bestämma om två objekt är identiska. En kedjekod kan användas för att isolera objekt i ett datorsynsprogram eller bildsegmentering i bildbehandling, även om den oftare kan användas i optiska teckenigenkänningsprogram (OCR).

Även om det finns flera etablerade algoritmer för en kedjekod är grundkonceptet detsamma i var och en. Först är kanten på ett objekt, vanligtvis genom att flytta pixel för pixel genom en rasterbild. När den är placerad registreras positionen och de omgivande kanterna upptäcks. Beroende på om detekteringsalgoritmen kommer att röra sig medurs eller moturs flyttas den aktuella platsen i en eller annan riktning längs kanten tills den återgår till det ursprungliga läget.

Varje gång den aktuella positionen rör sig, registreras ett nummer i kedjekoden. Detta nummer indikerar i allmänhet riktningen som förflyttades längs objektets kant. Om till exempel en kedjekodalgoritm följer en rak kant från höger till vänster, läggs den numeriska koden för vänster till i slutet av koden varje gång kanten spåras till vänster. Den resulterande koden är en sträng med siffror där, om sekvensen följs från en godtycklig utgångspunkt och en pixel placerad vid varje steg, objektets kontur skulle ritas om.

När strängen med nummer som utgör koden är klar kan flera olika algoritmer tillämpas på den för att göra jämförelser mot andra kedjekodsekvenser. Först normaliseras antalet genom att rotera startnumret tills det lägsta heltalvärdet bestäms. På detta sätt kan två objekt som har samma kontur jämföras, oavsett var på varje objekt kodningen startade.

Andra, mer komplexa versioner av kedjekodalgoritmen finns. Dessa inkluderar vektorbaserad kodning i vilken konturen av ett objekt beskrivs av en sekvens av koordinater som är anslutna med linjer, även om denna metod kan vara förlorad när den används i fint detaljerade konturer. En version av algoritmen finns också som använder körlängdkodning (RLE) för att ytterligare komprimera koderna för exceptionellt stora eller komplexa objekt så att de kan lagras på ett mer effektivt sätt.