Chain Code

In a black and white (bi-level) image, collections of connected black pixels can be considered foreground or objects, while white pixels act as the background. Each set of connected black pixels can be completely described by listing the positions of the pixels on its boundary in counterclockwise order, starting from any point on the boundary. This list of pixels can, in turn, be represented as the direction to the next pixel in the list. This sequence of directions is called the chain code of the object, and precisely describes the shape independently of its position.

There are $8$ possible directions from one pixel to an adjacent pixel, and although the assignment of these numbers is arbitrary, figure 1 shows the standard convention. The direction $0$ means "to the right", $2$ means "immediately above", and $1$ is at $45$ degrees, bisecting $0$ and $2$, and so on.

Two black pixels are considered adjacent if the square of the distance between them is less than or equal to $2$. This is based on a standard graphics coordinate system having a pixel at each integer coordinate. Two pixels are connected if a contiguous path of adjacent pixels can be traced between them. A connected region is a set of black pixels in which all members are connected to each other. A boundary pixel of a connected region (from now on referred to as a region) is a pixel within the region that has at least one neighbor (in the four compass directions) that is not black. For this problem, you may assume that there are no "holes" in the region, so that there is only one boundary.

The chain code of a region can start at any pixel on the boundary. It proceeds by finding the next adjacent pixel on the boundary in a counterclockwise direction, saving the direction ($0$-$7$) in an output buffer, and continuing the process from the new pixel. When the process returns to the starting pixel, the chain code is complete. The output buffer contains the sequence of directions that make up the chain code, from which the original set of pixels can be reconstructed starting from any position in an image.

As an example, the chain code for the region in figure 2 is $446567001232$. The chain code uniquely describes the shape of the region, although its position is unknown. Shape-related measures such as the perimeter and area (the number of pixels in the region) can be determined directly from the chain code alone. You are to write a program that calculates the area of a connected region given only the chain code.