Abstract
Topology is a fundamental property of shapes in pictures. Since the input for any image analysis algorithm is a digital image, which does not need to have the same topological characteristics as the imaged real world, it is important to know which shapes can be digitized without topological changes. Most existing approaches do not take into account the unavoidable blurring in real image acquisition systems or use extremely simplified and thus unrealistic models of digitization with blurring. In case of the mostly used square grids, we show which binary images can be digitized topologically correctly after blurring with an arbitrary non-negative radially symmetric point spread function, which is an important step forward to real digitization.
Introduction
In computer vision and image analysis, a common underlying assumption is that a digital image is a faithful representation of the continuous world. However, the process of capturing an image involves two inherently destructive steps: blurring and sampling. Real optical systems blur the image before it reaches the sensor, and each pixel integrates light over a small area, acting as a secondary blur. Subsequently, the continuous world is reduced to a discrete grid of pixels.
If the blurring is too significant or the sampling grid is too coarse, the topology of a shape can change—objects might merge, holes might disappear, or mathematical ambiguities like "checkerboard" patterns may arise. While previous research established sampling theorems for ideal, non-blurred images or simplified blur models, this paper addresses the gap of realistic blurring using arbitrary, non-negative, radially symmetric point spread functions (PSFs).
Theoretical Framework
The authors employ a rigorous mathematical framework based on digital topology to define the conditions under which a shape's structure is preserved. A central concept is $r$-regularity. A shape is considered $r$-regular if its boundary is smooth enough that a disc of radius $r$ can be rolled along both the inside and outside of the boundary without getting stuck or crossing it. This geometric constraint effectively excludes shapes with sharp corners or thin "necks" that would be lost during digitization.
To compare the original shape and its digital version, the paper uses the criterion of weak $r$-similarity. This requires both topological equivalence (the existence of a homeomorphism between the sets) and a bounded Hausdorff distance, ensuring that the boundaries of the digitized shape do not shift significantly from the original.
Modeling Blurring and Sampling
The camera's blur is modeled as a convolution with a $p$-PSF—a function that is non-negative, radially symmetric, and has a maximum radius of effect (support) denoted by $p$. The most significant insight of this work is that the exact shape of the blur does not need to be known to guarantee topological correctness, provided it meets these symmetry and non-negativity requirements.
Following the blur, the image is sampled on a standard square grid (an $r'$-grid) and converted back to a binary image via thresholding. The proof involves showing that the resulting digitization will be "well-composed," avoiding problematic 2x2 pixel configurations where connectivity is mathematically ambiguous.
Main Results
The primary contribution of the paper is Theorem 3, which establishes a clear geometric boundary for successful digitization. Given an $r$-regular shape $A$, a square grid with density $r'$, and a blur function with radius $p$, the digital reconstruction is topologically identical to $A$ if:
- The blur radius is smaller than the sampling density ($p < r'$).
- The shape's feature size is large enough to accommodate both sampling and blur ($r > r' + p$).
In essence, the "smoothness" of the shape ($r$) must be greater than the sum of the sampling distance ($r'$) and the blur radius ($p$). This allows engineers to predict the reliability of image analysis algorithms using realistic camera parameters.
Conclusion
This work provides a significant step toward understanding real-world digitization. However, some limitations remain. The requirement that the blur radius be smaller than the sampling density ($p < r'$) is strict and may not be met in all optical systems. The authors conjecture that the theorem might hold for any $p$ as long as the total error budget $r > r' + p$ is respected, but a formal proof remains for future work. Additionally, extending these results to hexagonal or irregular sampling grids is a promising avenue for further research.
Summary updated