A search-and-validate method for face identification from single line drawings

Several studies have been made in finding the faces of an object depicted in a line drawing, but the problem has not been completely solved. Although existing methods can find the correct faces in most cases, there is no mechanism to ascertain that they are indeed correct, leaving the human user to do so. This paper uses a two-stage approach--find potential faces, then validate their correctness--to ensure that only correct faces are delivered ultimately. The face finding itself uses a double breadth-first search algorithm, which yields the shortest path, to find the potential faces. The basic premise is that the smallest faces found are more likely the correct ones. They serve as the "seed" potential faces, from which the algorithm proceeds to search for more faces. If the potential faces found satisfy the validation rules, then they are accepted as correct. Otherwise, the wrong potential faces are identified and removed, and new ones found in their place. The validation process is then repeated. The algorithm is fast and reliable, can deal with planar-faced manifold and nonmanifold objects, and can deliver the different results when a drawing has multiple interpretations. Our extensive tests show that the method can deal with most cases efficiently, including those that previous methods cannot solve.