Automated assembly of shredded pieces from multiple photos

Abstract

In this paper, we investigate the problem of automated assembly of shredded pieces from multiple photos, which has a board usage in many multimedia applications. Both shape and appearance information along the boundaries are utilized and extracted for each pieces, and then the candidate matchings between pieces are established based on these features. A weighted graph, called matching graph, whose vertices represent shredded pieces and edges represent candidate matchings is then constructed, and divided into separate subgraphs, with each subgraph corresponding to a desired photo. The assembly results are finally obtained by searching for a valid spanning tree for each subgraph. This proposed method can deal with cases in which materials are lost and/or pieces belonging to multiple photos coexist. And the experimental results well demonstrate the effectiveness and efficiency of our proposed method. © 2006 IEEE.