Boundary adjacency tracing and its application to data base compression

Based on a well-segmented image, a series of methods leading to the compression of the boundary adjacency data base without any additional distortion is presented. The size of the compressed version for a regular image is 1/12 to 1/3 the original data base.

A well-segmented image has two-dimensional pixels clustered into regions. An easy method for extracting the singular boundary pixels, which requires special attention due to aspects of sequencing the boundary pixels, is discussed. In addition, a convenient way for identifying these boundary pixels is presented.

The storage structure of the boundary adjacency data base is a three-level hierarchical structure based on index and SRA (Stored Record Address) concept. A simple way to trace the adjacency relationships of a region to other regions and extract the boundary pixels of each adjacent edge of this region at the same time is presented.

The sequencing of the boundary pixels of the adjacent edges of a region provides a way to compress the boundary adjacency data base. Using a circular-linked list structure, the entire set of boundary pixels of a region is sequenced clockwise, with the singular boundary pixels being sequenced recurrently. Then, with reference to the sequenced boundary, a method that orders (in a clockwise sequence) the boundary pixels of each adjacent edge in the adjacency data base is developed. The possibility that the adjacent edge of a region would be cut into several separable sections is considered. Finally, three ways using a direction vector code to compress the boundary adjacency data base effectively are presented, compared, and discussed.

The sequencing of the boundary, the detecting of the boundary adjacency, and the coding of the adjacent edge might be directed toward such further studies as relationship analysis of the scene content, vertex locating, reconstruction of the scene, and the shape description.