What Is a Chain Code?

In computer graphics and image processing, a chain code is an algorithm used to encode the contours of an object in a black and white, or monochrome, image. The resulting sequence of codes can either describe how to draw the outline of the object relative to the image in which it is located, or it can be a collection of directions relative to the location on the outline where the algorithm started, essentially providing steps that can be followed to redraw the object. These codes can be normalized according to a formula and then compared to another chain code to determine if two objects are identical. A chain code can be used for isolating objects in a computer vision program or image segmentation in image processing, though it more commonly may be used in optical character recognition (OCR) programs.

Although there are several established algorithms for a chain code, the basic concept is the same in each. First, the edge of an object is located, usually by moving pixel by pixel through a raster image. Once located, the position is recorded and the surrounding edges are detected. Depending on whether the detection algorithm will move clockwise or counterclockwise, the current location is moved in one direction or another along the edge until it returns to the original position.

Each time the current position moves, a number is recorded in the chain code. This number generally indicates the direction that was moved along the edge of the object. For example, if a chain code algorithm is following a straight edge from right to left, then each time the edge is traced to the left, the numerical code for left is added to the end of the code. The resulting code is a string of numbers in which, if the sequence is followed from an arbitrary starting point and a pixel placed at each step, the outline of the object would be redrawn.

Once the string of numbers that make up the code is completed, several different algorithms can be applied to it to help make comparisons against other chain code sequences. First, the number is normalized by rotating the starting number until the lowest integer value is determined. In this way, two objects that have the same outline can be compared, regardless of where on each object the encoding started.

Other, more complex versions of the chain code algorithm exist. These include vector-based encoding in which the outline of an object is described by a sequence of coordinates that are connected by lines, although this method can be lossy when used on finely detailed outlines. A version of the algorithm also exists that uses run-length encoding (RLE) to further compress the codes for exceptionally large or complex objects so they can be stored in a more efficient manner.