Computational reconstruction of ancient artifacts

In this article, we discuss the development of automatic artifact reconstruction systems capable of coping with the realities of real-world geometric puzzles that anthropologists and archaeologists face on a daily basis. Such systems must do more than find matching fragments and subsequently align these matched fragments; these systems must be capable of simultaneously solving an unknown number of multiple puzzles where all of the puzzle pieces are mixed together in an unorganized pile and each puzzle may be missing an unknown number of its pieces. Discussion has cast the puzzle reconstruction problem into a generic terminology that is formalized appropriately for the 2-D and 3-D artifact reconstruction problems. Two leading approaches for 2-D tablet reconstruction and four leading approaches for 3-D object reconstruction have been discussed in detail, including partial or complete descriptions for the numerous algorithms upon which these systems rely. Several extensions to the geometric matching problem that use patterns apparent on the fragment outer surface were also discussed that generalize the problem beyond that of matching strictly geometry. The models needed for solving these problems are new and challenging, and most involve 3-D that is largely unexplored by the signal processing community. This work is highly relevant to the new 3-D signal processing that is looming on the horizon for tele-immersion.