Abstract
Interpolating sparse data points into dense maps is a fundamental challenge in computer vision tasks such as optical flow and stereo matching. Traditional Euclidean-based filters often fail to respect object boundaries, leading to artifacts. This paper proposes a novel interpolation method leveraging geodesic distance—the shortest path following image intensity topography. By utilizing a recursive filtering framework, the method achieves $O(1)$ computational complexity relative to data density and provides superior edge preservation. Experimental results demonstrate significant improvements in both accuracy (RMSE) and processing speed compared to state-of-the-art techniques.
Introduction
Many computer vision algorithms produce sparse outputs, where high-confidence data is available only for a subset of pixels. Converting these sparse points into a dense, full-resolution map requires interpolation that respects the underlying image structure. Standard techniques, such as bilinear interpolation or bilateral filtering, rely on Euclidean distances. These methods often "leak" information across thin edges or blur distinct object boundaries because they do not account for the image's connectivity.
Methodology: Geodesic Affinity Space
The core contribution of this work is the use of geodesic distance as a proxy for pixel affinity. Unlike Euclidean distance, geodesic distance measures the shortest path between pixels while considering the "topography" of the image's color or intensity. This ensures that two pixels are only considered similar if a path exists between them that does not cross high-contrast edges.
The researchers derived a closed-form solution for the interpolation problem, framing it as a ratio of two non-normalized bilateral filters. To ensure efficiency, they implemented this using a fast recursive algorithm based on calculation trees. This approach results in $O(1)$ complexity, meaning the processing time depends solely on the image resolution rather than the number of sparse input points.
Experimental Results
The method was evaluated on standard benchmarks, including the Middlebury Stereo and MPI Sintel datasets.
Accuracy and Edge Preservation
In stereo disparity tests, the proposed geodesic method consistently outperformed standard bilateral kernels and Nadaraya-Watson estimation. As shown in the visual comparisons, the method produces significantly sharper boundaries and fewer bleeding artifacts.
Quantitatively, for the "Motorcycle" image, the proposed method achieved a Root-Mean-Square Error (RMSE) of 3.31, compared to 3.77 for the standard bilateral filter and 6.25 for other baseline methods.
Computational Efficiency
The most significant advantage is speed. When compared against EpicFlow (EFI) on the MPI Sintel dataset, the proposed method maintained a constant processing time of 0.32 seconds per frame. In contrast, EFI's performance varied with data density, typically ranging from 1.2 to 3.7 seconds. This predictability makes the geodesic approach ideal for real-time vision pipelines.
Conclusion
By leveraging geodesic distance within a recursive filtering framework, this method provides a highly efficient and accurate solution for sparse data interpolation. While it excels at edge preservation, its reliance on image intensity means it can occasionally be misled by texture edges that do not correspond to physical motion boundaries. Future work will focus on integrating more robust confidence measures to mitigate these effects and further optimizing the implementation for GPU architectures.
Summary updated