Algorithms for the recovery of 3D objects from 2D line drawings

Reconstructing the 3D object depicted in a line drawing consistent with human perception is an interesting and important topic in computer vision. Normally, the reconstruction process requires two main steps: topological analysis and 3D recovery. This thesis makes three novel contributions in the three steps: (1) Decomposition of the line drawing of a complex object into a collection of drawings of simple manifolds; (2) Finding the faces of the object in the drawing; (3) Reconstruction of the object in both parallel and perspective projections. The work here is restricted to drawings of planar polyhedra. The decomposition of a complex line drawing into drawings of simpler manifolds occurs at (1) non-manifold vertices, (2) along non-manifold edges and (3) across internal faces. The algorithms for the first two are simple. The decomposition across an internal face has two stages: basic decomposition and the subsequent repair. Our results show that the algorithm can deal with objects with planar faces. Reconstructing of the 3D object is much easier and much more efficient from a simpler drawing than a complex one. Knowing the faces of the object in a drawing is essential to the 3D reconstruction of the object. A new face finding algorithm much more efficient than the existing ones is presented here. This algorithm also contains two stages: decomposition and face forming. In the first stage, a line drawing is decomposed into sub-loops, which are connected but usually open sequence of edges that must belong to the same face. Faces are formed from the sub-loops in the next stage. The method has the capability to differentiate an internal face from a real one once it is formed. After obtaining the faces, the next step is to reconstruct the 3D model. Here, we present a novel, simple and direct method, the cubic corner method (CCM). A cubic corner is a trihedral vertex where the three incident edges are mutually perpendicular. The 3D coordinates of the three end vertices relative to the given vertex can be obtained analytically given the 2D coordinates of the four vertices in the drawing. The algorithm starts with a user-identified cubic corner in the drawing and uses the face information obtained previously to recover the geometry of the entire object. It works for both parallel and perspective drawings; the only difference is that, for perspective, the method needs to find the focal length first, to establish the linear relationship between a vertex on the image plane and its corresponding point on the object. The method generates accurate results for accurate drawings. For inaccurate drawings, it generates plausible results which may not be good enough. A novel hybrid method, combining CCM and the well-known optimization-based method (OBM), overcomes the problem. The optimization process in OBM requires an initial guess to the 3D object; a guess close to the final solution could improve the result of OBM significantly. In the hybrid method, CCM supplies this initial guess to OBM, which then produces a result better than either method on its own. This thesis also presents an alternative efficient method that recovers 3D objects from perspective drawings by reversing the process one uses for drawing a perspective drawing manually. The method does not require the focal length and, depending on the topology of the drawing itself, may not need the faces of the object. This is a significant advantage as face identification is not a trivial task. Future work is required to resolve some of the shortcomings in the algorithms presented in the thesis. Besides, there is a need to overcome the geometric restriction of planar polyhedra only, and extend the geometric coverage to objects that contain both planar and curved faces. Also, the ability to recover line drawings accurately opens the possibility of recovering objects in photographs, if we can extract edges accurately from photographs. This brings forth the need for a stitching algorithm that merges reconstructed results together to form the whole object as the complete view of an object normally requires multiple photographs. This can then lead to some useful applications such as the reconstruction of engineering objects accurately, without using the expensive 3D laser scanner. Much work remains before we can arrive at that.DOCTOR OF PHILOSOPHY (MAE