Fast algorithm for 2D fragment assembly based on partial EMD

摘要

2D Fragment assembly is an important research topic in computer vision and pattern recognition, and has a wide range of applications such as relic restoration and remote sensing image processing. The key to this problem lies in utilizing contour features or visual cues to find the optimal partial matching. Considering that previous algorithms are weak in predicting the best matching configuration of two neighboring fragments, we suggest using the earth mover's distance, based on length/property correspondence, to measure the similarity, which potentially matches a point on the first contour to a desirable destination point on the second contour. We further propose a greedy algorithm for 2D fragment assembly by repeatedly assembling two neighboring fragments into a composite one. Experimental results on map-piece assembly and relic restoration show that our algorithm runs fast, is insensitive to noise, and provides a novel solution to the fragment assembly problem.