Abstract
The upper-weighted sets of a signal are the sets of points with weight above a given threshold. The components of the upper-weighted sets, thanks to the inclusion relation, can be organized in a tree structure, which is called the component tree. In this work, we present a linear time and space algorithm to compute the component tree of one-dimensional signals. From this algorithm we derive an efficient gray-level image multithresholding method, which is based on the hypothesis that objects which appear on an image can be represented by salient classes present in the histogram of this image. These classes are modelled as the most significative components of the histogram's component tree. We show results of the proposed method and compare it with classical methods.
Introduction
Component trees are fundamental hierarchical representations in mathematical morphology, widely applied in image filtering, segmentation, and compression. They capture the evolution and merging of connected components—regions of a signal exceeding a specific threshold—as that threshold is progressively lowered. While algorithms for N-dimensional signals typically achieve quasi-linear complexity (often involving the inverse Ackermann function), the simpler topology of 1D signals offers an opportunity for true linear optimization. In 1D, connected components are always simple intervals, allowing for a single-scan construction process that minimizes memory overhead.
Linear Component Tree Construction
The authors propose a stack-based, single-scan algorithm to process a Weighted Ordered Set (WOS), which serves as the formal model for a 1D signal. The algorithm iterates through the signal point-by-point, utilizing a stack to maintain the hierarchy of components.
By comparing a point's weight to its predecessor and the current "head" of the stack, the algorithm identifies whether a component is starting, ending, or continuing. This logic is governed by specific local configurations of three consecutive points ($q_h, r_h, p_h$), which dictate how the tree's parent-child relationships are updated in $O(n)$ time.
Simultaneously, the algorithm can compute various attributes for each node, such as height, surface (area), and volume. The volume attribute is particularly significant as it represents the statistical prominence of a grayscale range, combining both the range's width and the frequency of pixels within it.
Application to Image Multithresholding
The efficiency of the 1D component tree is leveraged for image multithresholding by treating the image histogram as a 1D signal. The process involves:
- Histogram Computation: Generating the 1D frequency distribution of the image.
- Tree Construction: Building the component tree of the histogram in linear time.
- Salient Node Selection: Identifying the $K$ most significant nodes based on the volume attribute.
- Threshold Determination: Using these nodes as markers for a watercourse transform (the dual of the watershed transform) to find optimal threshold boundaries.
Experimental Results
The method was evaluated using standard test images, including Lena, Goldhill, Fruits, Barbara (512x512), and Cameraman and House (256x256). The proposed algorithm was compared against established thresholding techniques: Kapur, Khotanzad, and Otsu.
Quantitatively, the method achieved Peak Signal to Noise Ratio (PSNR) values comparable to the industry-standard Otsu method. For the "House" image, the proposed method yielded a PSNR of 28.10, while Otsu achieved 29.33. Qualitatively, the method excelled at segmenting images into homogeneous regions, such as the sky in the "Cameraman" image, provided the underlying objects formed distinct peaks in the histogram.
Conclusion
The primary contribution of this work is a guaranteed $O(n)$ complexity algorithm for 1D component tree construction, making it highly suitable for real-time processing of large data streams. While the method struggles when histogram classes overlap significantly (as seen in the "Goldhill" and "Fruits" datasets), it provides a robust structural approach to statistical thresholding. Future work will focus on automating the selection of the number of classes ($K$) and extending the approach to multi-dimensional histograms for color image segmentation.
Summary updated