Computation of level lines of 4-/8-connectedness

• A topdown algorithm is introduced to compute 4-/8-connected level line trees.
• The running time is linear to the input image size and the total level line length.
• The algorithm is an extension of an algorithm previously developed by the author.
• Mathematical techniques are developed to analyze 4-/8-connected level lines.

We present a topdown algorithm to compute level line trees of 4-/8-connectedness. As a boundary of a level set component, a level line of an image is a Jordan boundary of intensity value on instant interior greater/less than on instant exterior. The interior of a Jordan boundary assumes 4-connectedness and the exterior 8-connectedness, or the inverse. All level lines form a tree structure. The running time of the algorithm is O(n + t), where n is the size of the input image and t is the total length of all level lines. The efficiency of the algorithm is illustrated by experiments.