Abstract
Rigid transformations are involved in a wide variety of image processing applications, including image registration. In this context, we recently proposed to deal with the associated optimization problem from a purely discrete point of view, using the notion of discrete rigid transformation (DRT) graph. In particular, a local search scheme within the DRT graph to compute a locally optimal solution without any numerical approximation was formerly proposed. In this article, we extend this study, with the purpose to reduce the algorithmic complexity of the proposed optimization scheme. To this end, we propose a novel algorithmic framework for just-in-time computation of sub-graphs of interest within the DRT graph. Experimental results illustrate the potential usefulness of our approach for image registration.
Introduction
In standard image processing, rotating or translating an image involves floating-point math and interpolation (like bilinear or bicubic), which inevitably introduces numerical noise or blurring. Discrete Rigid Transformations (DRTs) aim to avoid this by treating the image as a grid of integers and finding the exact mapping from one grid to another.
However, the space of all possible discrete rotations and translations is complex. As a rotation angle changes slightly, the digitized result remains constant until a pixel center crosses a grid boundary, known as a tipping surface. Previously, the authors modeled this as a DRT graph, where each vertex represents a unique discrete transformation. The primary challenge was the computational cost: exploring a neighborhood of depth $k$ had an exponential complexity of $O(m^k N^2)$, making deep searches impractical for real-world image sizes.
Methods
The authors propose a novel just-in-time computation framework to explore the DRT graph. Instead of building the entire graph (which has a space complexity of $O(N^9)$), they only compute the sub-graph relevant to the current local search.
Key technical components include:
- Tipping Surfaces: Analytical definitions of 2D surfaces in the 3D parameter space $(a_1, a_2, heta)$ where the discrete mapping changes.
- Topological Sweeping Plane: A sweeping plane algorithm moves through the 3D parameter space along the rotation axis ($ heta$). As it intersects tipping surfaces, it updates the graph structure dynamically.
- Depth-Limited Construction: By using the sweeping plane to find the $(k+1)$ closest tipping surfaces in every direction, the algorithm bounds the search area strictly to a neighborhood of depth $k$.
A critical insight of this work is that the $k$-depth neighborhood can be computed in $O(kN^2)$ time rather than $O(m^k N^2)$. This is achieved by treating the neighborhood as a geometric volume in the parameter space rather than just a set of abstract graph nodes. Furthermore, the authors demonstrate that the average degree ($m$) of a vertex in a DRT graph is a small constant (typically 3–4 for 2D projections), preventing search explosion.
Results
The algorithm was evaluated using synthetic binary images, such as $53 \times 53$ pixel hand shapes. By testing reference and target image pairs related by known rigid transformations, the study demonstrated:
- Complexity Reduction: The time complexity of neighborhood computing was successfully reduced to linear with respect to the search depth $k$.
- Improved Local Optima: Increasing the neighborhood depth $k$ (from 1 to 15) allowed the algorithm to find significantly better local optima with lower matching distances. A larger $k$ enables the search to "jump" over small local traps in the energy landscape.
- Exactness: Because the search navigates the DRT graph directly, the registration is exact, avoiding interpolation artifacts and rounding errors.
Conclusion
This framework provides a foundation for exact, interpolation-free image registration. While the $O(kN^2)$ complexity is a significant improvement, the $N^2$ factor suggests that very large images may still require further optimization, perhaps by focusing on object boundaries. Future research will aim to extend this approach to 3D volumes ($\mathbb{Z}^3$), which involves navigating a significantly higher-dimensional parameter space.
Summary updated