Virtual multi-fracture craniofacial reconstruction using computer vision and graph matching

The problem of computer vision-guided reconstruction of a fractured human mandible from a computed tomography (CT) image sequence exhibiting multiple broken fragments is addressed. The problem resembles 3D jigsaw puzzle assembly and hence is of general interest for a variety of applications dealing with automated reconstruction or assembly. The specific problem of automated multi-fracture craniofacial reconstruction is particularly challenging since the identification of opposable fracture surfaces followed by their pairwise registration needs to be performed expeditiously in order to minimize the operative trauma to the patient and also limit the operating costs. A polynomial time solution using graph matching is proposed. In the first phase of the proposed solution, the opposable fracture surfaces are identified using the Maximum Weight Graph Matching algorithm. The pairs of opposable fracture surfaces, identified in the first stage, are registered in the second phase using the Iterative Closest Point (ICP) algorithm. Correspondence for a given pair of fracture surfaces, needed for the Closest Set computation in the ICP algorithm, is established using the Maximum Cardinality Minimum Weight bipartite graph matching algorithm. The correctness of the reconstruction is constantly monitored by using constraints derived from a volumetric matching procedure guided by the computation of the Tanimoto Coefficient. (C) 2009 Elsevier Ltd. All rights reserved.