Concurrent Chain Code Extraction

Overview

A chain code is a way to represent shapes in a binary (black and white) image. While there are several ways to perform chain-coding, the basic idea is very simple. One spot on the outer boundary of a shape is selected as the starting point. We then move along the boundary of the shape and describe each movement with a directional code that describes the movement. We continue tracing the boundary of the shape in this fashion unil we return to the starting point.

Freeman

The Freeman code [1] encodes a movement as an integer number between 0 and 7. These codes are shown in Figure 1 where 0 represents a movement to the right and 2 represents a movement down.

Consider the binary image of Figure 2. There is a single shape in this image and it can be described by recording a starting point and then tracing the movements around the shape boundary. Figure 2 shows the movements around the shape boundary but gives no guidance on the starting point.

Since any of the boundary pixels can be used as the starting point, there are many different ways to represent a shape. Here is one way to describe the shape of Figure 1.

• starting point: (4, 2)
• chain-code: 334466660110

Here is another way to describe the same shape.

• starting point: (1, 4)
• chain-code: 466660110334

Scheffler and Greiner Algorithm

Extracting the chain codes of an arbitrarily complex binary image can be done in linear time by raster-scanning the image. Scheffler and Greiner [2] provide an efficient algorithm for chain code extraction which provides a representation of not only the outer contours of a shape, but also of inner holes within a shape. The output of their algorithm is a tree where any path through the tree alternates between outer-shape contours and holes.

Figure 3 illustrates how the algorithm of Scheffler and Greiner classifies shapes and holes and arranges them heirarchically. The binary image at the left of Figure 3 contains various shapes that are colored for illustration in the center image. White regions are considered to be 'holes' in shapes since they are entirely enclosed by some larger shape. The output of the Scheffler and Greiner algorithm is shown on the right where the larger blue rectangle encloses two holes (the two children) and each of the holes contains several triangles. One of the triangles itself contains a hole.

The Project : Parallelize Chain Code Extraction

Although the Scheffler-Greiener extraction algorithm is efficient, we would like to increase performance by parallelizing the algorithm. It seems likely that the algorithm can be broken into small tiles such that the outputs of each tile can be stitched together (something like a map-reduce) to generate a solution for the entire image. The output of this research project will be a paper describing a parallel approach to chain-code extraction together with an implementation of that algorithm that has been emperically characterized on one of the departments clusters.