You are here

Affine Puzzle

Lifetime from: 
Lifetime to: 
Short description: 
A novel solution for reassembling a broken object from its parts without established correspondences, where each part is subject to a linear deformation.

The affine puzzle problem can be formulated as follows: Given a binary image of an object (the template) and another binary image (the observation) containing the fragments of the template, we want to establish the geometric correspondence between these images which reconstructs the complete template object from its parts. The overall distortion is a global nonlinear transformation with the following constraint:

  • the object parts are distinct (i.e. either disconnected or separated by segmentation),
  • all fragments of the template are available, but
  • each of them is subject to a different affine deformation.

The basic idea of the proposed solution is to construct and solve a polynomial system of equations which provides the unknown parameters of the alignment. We have quantitatively evaluated the proposed algorithm on a large synthetic dataset containing 2D and 3D images. The results show that the method performs well and robust against segmentation errors. The method has been validated on 2D real images as well as on volumetric medical images applied to surgical planning.


Solution of the Tangram puzzle. TOP: observed tiles, MIDDLE: template silhouettes, BOTTOM: Realigned tiles.


Bone fracture reduction. The CPU time of our Matlab implementation was 15 sec. for these 1 megavoxel CT volumes.
Template (mirrored intact bone)
Fractured bone (observation)
Realigned bone fracture


Domokos C, Kato Z. Affine puzzle: Realigning deformed object fragments without correspondences. In: Daniilidis K, Maragos P, Paragios N, editors. European Conference on Computer Vision (ECCV). Crete, Greece: Springer; 2010. 7. p. 777-790p. (Lecture Notes in Computer Science).
Medical Applications