Sparse Data Interpolation Using the Geodesic Distance Affinity Space

Mikhail G. Mozerov, Fei Yang, Joost van de Weijer

TL;DR

The authors present a fast, edge-preserving method for filling in the gaps of sparse data (like motion vectors or depth maps) by leveraging the "geodesic distance" on the underlying image. By adapting a recursive filtering technique, they achieve higher accuracy and significantly faster processing speeds than popular methods like EpicFlow, making it a powerful tool for real-time computer vision pipelines.

What Problem Does This Paper Address?

In many computer vision tasks, we only have data for a fraction of the pixels in an image. For example, in optical flow (tracking movement) or stereo matching (calculating depth), we might only have high-confidence values for a few "feature points." The challenge is to interpolate these sparse points to create a dense, full-resolution map.

Traditional methods like bilinear interpolation or standard bilateral filters often fail here. They tend to blur across object boundaries or "leak" information between two similarly colored objects that are actually separated by a thin edge. This happens because standard filters look at the straight-line (Euclidean) distance between pixels. If a thin black line separates two white regions, a standard filter sees the white pixels as "close," even though they belong to different objects.

Methods

The researchers propose using geodesic distance—the shortest path between two pixels that follows the "topography" of the image's intensity/color. In this "affinity space," two pixels are only considered close if there is a path between them that doesn't cross high-contrast edges.

Key Technical Contributions: * Closed-Form Solution: They show that the interpolation problem can be solved as a ratio of two non-normalized bilateral filters. * Recursive Filtering: Instead of a "brute-force" calculation (which is computationally expensive), they use a fast recursive algorithm based on "calculation trees." * O(1) Complexity: Unlike many heuristic methods where the speed depends on how many sparse points you have, this method’s computational time depends only on the total image size. This makes it incredibly predictable and efficient for high-resolution data.

Datasets

The authors evaluated their method using several standard benchmarks:

  • Middlebury Stereo Dataset: Specifically the "Motorcycle" and "Art" images, used to test disparity (depth) interpolation.
  • MPI Sintel Dataset: A challenging benchmark for optical flow, used to compare the proposed method against the state-of-the-art EpicFlow algorithm.

Key Insights and Ideas

  • Geodesic vs. Euclidean: The "aha" moment is that geodesic distance is a much better proxy for object boundaries than simple spatial distance. By following the "valleys" of image intensity, the filter naturally respects edges without needing a complex edge-detection pre-processing step.
  • Efficiency is King: While the concept of geodesic distance isn't new, the implementation via recursive trees allows it to run in a fraction of the time of previous heuristic approaches (like those using Dijkstra’s algorithm).
  • Mathematical Elegance: By framing interpolation as a global mean squared error minimization problem, they derived a solution that fits perfectly into existing fast-filtering frameworks.

Key Results

  • Accuracy: In stereo disparity tests, the proposed method consistently achieved lower Root-Mean-Square Error (RMSE) than both Nadaraya-Watson estimation and standard bilateral kernels. For example, in one experiment, it achieved an RMSE of 3.31 compared to the bilateral filter's 3.77.
  • Speed: The most dramatic result was in the comparison with EpicFlow (EFI). On the MPI Sintel dataset, the proposed method took a constant 0.32 seconds per frame. In contrast, EFI's speed varied based on data density, often taking between 1.2 and 3.7 seconds per frame.
  • Visual Quality: Qualitatively, the method produces much sharper boundaries and fewer "bleeding" artifacts than traditional interpolation, especially in complex scenes with fine details.

Limitations and Future Work

The authors note one primary limitation: image edges are not always motion boundaries. If an object is moving but has the same color as the background, or if there is a texture edge that doesn't correspond to a physical boundary, the geodesic distance might lead to inaccuracies.

Future work could involve integrating more sophisticated "confidence" measures into the weights ($c_q$) to better handle regions where the underlying image and the sparse data are poorly correlated. Additionally, while the $O(1)$ complexity is great for CPUs, further optimization for GPU architectures could push this toward true real-time performance for 4K video.

Summary updated

Abstract

In this letter, we adapt the geodesic distance-based recursive filter to the sparse data interpolation problem. The proposed technique is general and can be easily applied to any kind of sparse data. We demonstrate its superiority over other interpolation techniques in three experiments for qualitative and quantitative evaluation. In addition, we compare our method with the popular interpolation algorithm presented in the paper on EpicFlow optical flow, which is intuitively motivated by a similar geodesic distance principle. The comparison shows that our algorithm is more accurate and considerably faster than the EpicFlow interpolation technique.
BibTeX
@article{mozerov2019sparse,
  author = {Mikhail G. Mozerov and Fei Yang and Joost van de Weijer},
  title = {{Sparse Data Interpolation Using the Geodesic Distance Affinity Space}},
  journal = {IEEE Signal Processing Letters},
  year = {2019},
  url = {https://openreview.net/forum?id=G806Yt3DzP},
}

Loading related content...

Figure