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.