A problem in image processing is the reconstruction of a region given its boundary. The algorithm presented in this paper uses quadtree properties to reconstruct a region in a 2n × 2n image by filling increasingly larger quadrants with “black” nodes. The algorithm, a connectivity filling procedure, prevents spillover, handles regions with holes, and executes in n steps or iterations.
The input data is a set of border pixels, together with their directions, that are produced by traversing the boundaries of the region. The set of border pixels is defined by one of two mutually exclusive definitions:
(1) 4-connected: A black pixel that is horizontally or vertically adjacent to a white pixel, or on the image’s edge, or both.
(2) 8-connected: A black pixel that is diagonally adjacent to a white pixel, or on the image’s edge, or both.
For the same region, the set of border pixels produced by the 4-connected definition may not be identical to the set produced by the 8-connected definition. But the algorithm can reconstruct the original region from either set of border pixels. Each border pixel has four directions (North, East, South, West) associated with it, and each direction’s state is either blocked or unblocked. A direction is unblocked (or 0) if a black pixel is adjacent in that direction; otherwise the direction is blocked (or 1). The border pixels are sorted in ascending order by their quadtree identifiers. They are then grouped into quadrants (or nodes). At each successive iteration, the resulting quadrants/nodes are grouped into larger quadrants or nodes, until the entire image is grouped into a single quadrant.
At each iteration, the color of missing nodes in each quadrant are determined. Adjacent missing nodes in unblocked directions are black and are filled with black pixels; otherwise, the missing nodes are white.
Each quadrant has a set of directions (North, East, South, West) associated with it. The state of each quadrant’s direction is obtained by ORing together the states of the corresponding direction for each of the quadrant’s four component nodes; e.g., the blocked or unblocked state of the quadrant’s North direction is the result of ORing together the state of each node’s North direction.
The authors state that it is “fairly simple” to adapt the algorithm to three dimensions, but no hints or details are provided beyond the statement that “octal codes are used instead of quaternary integers” and the directions must be expanded to six (6).
The algorithm may be extended to color images by designating the color of the region being reconstructed as “black” and all the other colors as “white.” When the region is completed, repeat for the next color until all of the colored regions have been reconstructed. It may be necessary to fill the image with a “background” color before the “black” border pixels are colored.
The authors present two examples for the algorithm. The simpler example is worked for every pass (iteration). The second example has holes and is worked for only the last two passes, skipping the first two passes. The set of border pixels is provided for each example, but it is up to the reader to determine the direction states for the second example’s set.
The core of the algorithm is presented as a procedure in the Appendix. However, the procedures referenced by the algorithm are not presented, but are very briefly described. An example is “OR-B, that ORs bits.” There are two errors in the algorithm and one misleading description of a referenced procedure.
The definition of the procedure ROTATION is given as “ROTATION, which performs a circular right shift on the BLOCK-PR bits.” (The BLOCK-PR bits correspond to the directions associated with a node or quadrant.) ROTATION also rotates the quadrant’s nodes; i.e., the NW node becomes the NE node, which becomes the SE node, which becomes the SW node, which becomes the NW node. This missing piece of information cleared up rampant confusion about the evaluations performed by the algorithm.
In the algorithm’s Case 2, the references to “BLOCK” should be to “BLOCK-PR.” This error caused confusion because there is also a “NEW-BLOCK.” In the algorithm’s Case 3, the call to the procedure ROTATION is missing. Insert “ROTATION (PRESENT, BLOCK-PR, ROT-ANGLE);” just before the comment about eliminating “opposite internal directions.” This error caused the algorithm to produce incorrect results for certain situations.
