Abstract
Intra-operative registration is a critical component of computer-assisted surgery, aligning pre-operative plans with real-time patient anatomy. This paper presents a novel graph-based approach for matching partial intra-operative surface scans to complete pre-operative models. By segmenting surfaces into regions and representing them as nodes in an attributed graph, the method leverages both local curvature descriptors and global topological context. Evaluation on clinical liver data demonstrates high accuracy and robustness to noise, even with small surface patches, significantly outperforming traditional discrete curvature classification methods.
Introduction
In computer-assisted surgery, registration aligns pre-operative data (CT/MRI) with the patient's intra-operative anatomy. Traditional landmark-based methods are often invasive or difficult to implement. While laser range scanners provide a non-invasive alternative, they typically capture only partial, noisy views of the organ surface in arbitrary orientations. Existing registration methods often rely on local point features, which lack the spatial context necessary to resolve ambiguities in partial matches. This paper introduces a graph-theoretic framework to capture the "context" of surface regions, enabling robust registration without manual initialization.
Methods
The proposed pipeline transforms raw geometric data into an abstract graph representation to facilitate matching:
- Mesh Segmentation: The surface is subdivided into regions using two curvature-based descriptors: shape index and curvedness. These descriptors are chosen for their invariance to rigid transformations.
- Graph Construction: Each segmented region is represented as a node in an attributed graph. Edges are established between adjacent regions, with directionality pointing from areas of lower to higher curvedness.
- Graph Matching: A similarity matrix is computed between nodes of the partial scan and the full model. This similarity integrates topological similarity (neighborhood structure) and region similarity (curvature values).
- Assignment and Refinement: The Munkres’ algorithm identifies the global assignment that maximizes total similarity. A final refinement step prunes false correspondences by verifying neighborhood consistency.
Results and Discussion
The method was evaluated using five clinical liver meshes. Researchers generated 500 random submeshes (1% to 50% surface area) and introduced up to 8mm of noise to simulate intra-operative conditions.
Performance and Robustness
On clean data, the algorithm achieved near-perfect matching for submeshes representing as little as 5% of the total surface area. Even at 1% coverage, the system maintained an 83.5% correct node assignment rate. Under noisy conditions (8mm displacement), the system remained reliable for submeshes larger than 30% of the total surface.
Continuous vs. Discrete Descriptors
A key finding is the superiority of continuous curvature measures over discrete "curvature classes." As shown in the performance comparison, binning curvature values into discrete categories leads to a significant loss of geometric detail, resulting in lower matching accuracy compared to the proposed continuous approach.
Conclusion
This graph-based approach offers a fast and robust solution for intra-operative registration, effectively utilizing spatial context to match partial surfaces. While the current segmentation method remains sensitive to extreme noise, the framework demonstrates significant potential for clinical application. Future work will focus on enhancing segmentation robustness and extending the method to handle non-rigid tissue deformations.
Summary updated