Evolutionary Search for Faces from Line Drawings
Authors:
- Jianzhuang LiuJLJianzhuang Liu
- Xiaoou TangXTXiaoou Tang
- 1 June 2005
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 27 (6) , 861-872
Abstract
Single 2D line drawing is a straightforward method to illustrate 3D objects. The faces of an object depicted by a line drawing give very useful information for the reconstruction of its 3D geometry. Two recently proposed methods for face identification from line drawings are based on two steps: finding a set of circuits that may be faces and searching for real faces from the set according to some criteria. The two steps, however, involve two combinatorial problems. The number of the circuits generated in the first step grows exponentially with the number of edges of a line drawing. These circuits are then used as the input to the second combinatorial search step. When dealing with objects having more faces, the combinatorial explosion prevents these methods from finding solutions within feasible time. This paper proposes a new method to tackle the face identification problem by a variable-length genetic algorithm with a novel heuristic and geometric constraints incorporated for local search. The hybrid GA solves the two combinatorial problems simultaneously. Experimental results show that our algorithm can find the faces of a line drawing having more than 30 faces much more efficiently. In addition, simulated annealing for solving the face identification problem is also implemented for comparison.Keywords
This publication has 23 references indexed in Scilit:
- Identifying faces in a 2D line drawing representing a manifold objectIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Graph-based method for face identification from a single 2D line drawingIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Sketching spaceComputers & Graphics, 2000
- Optimization-based reconstruction of a 3D object from a single freehand line drawingComputer-Aided Design, 1996
- Identification of faces in a 2D line drawing projection of a wireframe objectIEEE Transactions on Pattern Analysis and Machine Intelligence, 1996
- Interpretation of line drawings of complex objectsImage and Vision Computing, 1993
- Automatic construction of curvilinear solids from wireframe viewsComputer-Aided Design, 1988
- Efficiently identifying the faces of a solidComputers & Graphics, 1983
- Creating volume models from edge-vertex graphsACM SIGGRAPH Computer Graphics, 1982
- On seeing thingsArtificial Intelligence, 1971