This chapter presents an algorithm for identifying complementary site of objects broken into two parts. For a given 3D scanned image of broken objects, the algorithm identifies the rough sites of the broken object, transforms the object to a suitable alignment, registers it with its complementary part which belongs to the same object, and finds the local correspondence among the fragmented parts. The presented algorithm uses multiple granularity descriptors and edge extraction to detect the exact location of multiple cleavage sites in the object. It greatly reduces the amount of information to be matched and also helps in identification of the parts; as a result it reduces the computational time in the processing. It is also applicable to all triangulated surface data even in the presence of noise.
TopIntroduction
Recent advances in the field of computer vision, image processing and pattern recognition have led to substantial research in object identification and feature extraction from 2D images for different applications. In order to design efficient methods for solving problems in the field of 2D image processing, it is essential to have the good quality of image which is dependent on the image acquisition system and the environment. Generally, 2D methods are found to be efficient under controlled environment where the input images are acquired in almost fixed orientation, distance, camera calibration, illumination, fixed atmospheric condition etc. However, in reality it is expected that the acquired images which are to be processed do not possess good quality and fixed environment. Further, information available in 2D images may not be sufficient to generate needful result for a given application. This has motivated people to explore the possibility of analyzing 3D images. The most obvious difference between a 3D image and a 2D image of a particular object is its depth information. The 2D image provides only monocular depth information while a 3D image consists of both monocular and binocular depth information. This binocular depth information should also be considered for the study on images. Moreover, a 2D image is very sensitive to changes due to illumination or lighting conditions and change in orientation of image being captured. Since any 3D image considers the overall geometry of the image being captured, therefore, it is insensitive to the above mentioned changes. However, there are many challenges associated with 3D images; out of which handling large volume of data, high computational cost to process these data, inconvenient 3D acquisition systems and the digital archiving of 3D image data (Terry, 1995) are most important. There exists a large number of 3D scanners (Boehler, & Marbs, 2002) that can be used to scan any type of objects - from a small-sized object to a life-sized artifact (Levoy, 2000). Features are extracted from this scanned data for further processing.
This chapter deals with the problem of detecting the complementary part and to reassemble the broken 3D fragments. It has many applications in the fields like archeology where multiple broken fragments are obtained from the sites and parts belonging to the same object are to be identified. Along with this, automatic reassembly is required in art restoration, forensics, computer-aided design, chemistry, medicine etc. (Barequet, & Sharir, 1997). Generally, the reconstruction of arbitrary objects from their fragments may have many constraints. Some of these are mentioned below.
- •
Arbitrary shapes of parts (fragments)
- •
Unknown shape and number of the final objects
- •
Arbitrary number of fractured faces per fragment
- •
Missing fragments
- •
Probably flawed or weathered surfaces
- •
Non-existence of strict assemblage rules
Solutions to any assembly problem should be able to handle above mentioned challenges. The problem considered in this chapter can be formally defined as follows: Consider a 3D image consisting of multiple objects scanned using a 3D laser scanner and each object is broken into two pieces. The problem is to detect the complement of a broken part of a given object. Detection of complementary parts in the multiple broken objects is an important phase during the reassembly. Here, the rough site/ cleavage site in any fragment is identified and then an attempt is made to detect its complementary rough site in the other fragment. The detected complementary parts are aligned for reassembly. For example Figure 1 shows the multiple broken fragments. Fragment A and A’ belong to one object. This chapter presents an algorithm for the detection of A and A’ which are the complementary parts of same object. The result of detection is shown in Figure 2 (a) and (b) respectively.
Figure 1. Multiple broken fragments
Figure 2. (a) Fragment A (b) Fragment A’ [Complementary of A]