TL;DR
This paper introduces a novel, faster algorithm for constructing area Voronoi diagrams of connected components in digital images. By representing object contours with Freeman chain codes and expanding them directly in this code space, the method avoids computationally expensive pixel-level operations, leading to significant speed improvements for applications like document image analysis.
What Problem Does This Paper Address?
Defining proximity and relationships between objects in digital images is crucial for many analysis tasks. While point Voronoi diagrams are common, they often oversimplify complex shapes by representing objects as single points (e.g., centroids). This is particularly problematic for document images with varied character sizes and spacing. Area Voronoi diagrams offer a more accurate representation by considering the entire shape of objects, but existing methods for constructing them are often too slow for practical use, especially with images containing thousands of connected components. The paper aims to bridge this gap by developing a computationally efficient algorithm for generating area Voronoi diagrams.
Methods
The core of the proposed method lies in its efficient contour expansion and intersection detection. Instead of operating on pixels, the algorithm leverages Freeman chain coding to represent the boundaries of connected components, which are first approximated by closed convex polygons.
Here's a breakdown of the key steps:
- Connected Component Labeling: Standard algorithms are used to identify individual objects in the image.
- Convex Polygon Approximation: Each connected component is bounded by a convex polygon. This provides a more accurate representation than simple bounding boxes, especially for irregularly shaped objects.
- Freeman Chain Coding: The contour of each convex polygon is converted into a Freeman chain code. This code represents the contour as a sequence of direction vectors between adjacent pixels.
- Direct Contour Expansion: The crucial innovation is the ability to compute the Freeman chain code of an expanded contour directly from the original contour's chain code. This is achieved through a lookup table (Table 1) that maps pairs of direction codes to new sequences of direction codes representing the expanded contour. This process effectively simulates expanding the contour outwards by one pixel without explicit pixel manipulation.
- Voronoi Edge Detection: As contours expand iteratively, their intersections are detected. When an expanded contour from one component collides with the expanded contour of another component, the colliding pixels are identified as Voronoi edge pixels.
This approach bypasses the need for pixel-wise dilation or propagation, which are the bottlenecks in traditional methods.
Datasets
The paper evaluates its approach using 2,158 document images of varying sizes and resolutions (from 884x730 to 2592x3300 pixels, 200-600 DPI). These images contain hundreds to thousands of connected components. The authors mention preprocessing to remove small components considered noise. No new datasets were introduced.
Key Insights and Ideas
- Freeman Chain Codes as a Computational Domain: The most significant insight is the realization that contour expansion and intersection can be performed efficiently in the domain of Freeman chain codes, rather than on pixels. This abstraction dramatically reduces computational complexity.
- Direct Expansion via Code Transformation: The development of a method to directly compute the expanded contour's Freeman chain code from the original one, using a lookup table, is a key algorithmic contribution. This avoids iterative pixel-level expansion.
- Convex Polygon Approximation: While not entirely novel, the paper emphasizes the advantage of using convex polygons over rectangular bounding boxes for better shape representation, which is crucial for accurate Voronoi diagram construction in document images.
- Speedup through Abstraction: The core idea is that by moving the computation from the pixel domain to a higher-level representation (Freeman codes), significant speedups are achievable, making area Voronoi diagrams practical for large-scale image analysis.
Key Results
The paper demonstrates a significant improvement in the speed of constructing area Voronoi diagrams.
- Speed Comparison: Table 2 shows a comparison of the proposed method against Okabe's Method and Vliet's propagation method. For the tested document images, the proposed method consistently outperforms the others in terms of processing time (in milliseconds). For example, for image
im1, the proposed method takes 76ms, while Okabe's takes 259ms and Vliet's takes 169ms. For larger images likeim5, the proposed method takes 973ms, compared to 3162ms for Okabe's and 1103ms for Vliet's. - Qualitative Results: Figure 5 illustrates the contour expansion process, showing how Voronoi edges are formed by the intersections of expanding contours. Figure 6 provides examples of generated Voronoi diagrams for document images, showcasing their application in word grouping.
Limitations and Future Work
- Approximation: The method relies on approximating connected components with closed convex polygons. While better than bounding boxes, this is still an approximation, and the accuracy of the Voronoi diagram depends on the quality of this approximation.
- Generalization: While the paper focuses on document images, the authors suggest the underlying concepts are generalized and applicable to other digital images. However, they acknowledge that using convex polygons might not always be necessary or optimal for all object contours, and direct representation of object contours by Freeman codes could be an alternative in some cases.
- Future Work: The paper doesn't explicitly detail future work, but the success in speeding up area Voronoi diagram construction suggests potential for broader applications in image analysis and computer vision where accurate spatial relationships are important. The authors imply that the method is "amenable to other digital images."
Summary updated