A kinematic-geometric approach to spatial interpretation of line drawings

Abstract

This Thesis contributes with new algorithms for line drawing interpretation. A line drawing is a 2D diagram of vertices and straight edges aiming to depict a polyhedral 3D scene. Given one such drawing we usually want to first test whether it is a correct projection. If it is, then we wish to reconstruct all possible scenes it can depict. Otherwise, we attempt to correct the drawing so that it becomes reconstractable.<br/><br/>Traditionally, the Machine Vision approach to these problems has been mainly algebraic. Although computer scientists have discovered graphical techniques like the reciprocal diagrams, these have not been fully exploited or sometimes left apart, arguing that they only provide necessary conditions for realizability. However, a careful investigation of related areas of Geometry reveals the existence of complete and purely geometric tools that, using just pencil and straightedge, are able to decide the correctness of certain families of drawings. A first goal of this Thesis has been to select one such tool, the so-called cross-section diagram, and extend its validity to a broader class of drawings; namely, those of polyhedral surfaces generated by scenes of opaque polyhedra.<br/><br/>At present, however, no general realizability test using pencil and straightedge alone has been devised for general drawings so that relying on algebraic methods seems unavoidable. A second goal of the Thesis has been to exploit a known mapping between spatial polyhedra and the instantaneous motions of an articulated mechanism. Based on this mapping, we give a concise realizability test that outperforms the most popular algebraic approach known so far, due to Sugihara: it is faster, numerically stable, straightforwardly implementable in floating-point arithmetic and yields a linear parameterization of all possible reconstructions of the drawing. Additionally, this gives a model of the Necker reversal phenomenon and, in some cases, it allows obtaining all concavity/convexity patterns of the edges, neither resorting to consistent labelling techniques, nor consulting junction dictionaries.<br/><br/>A correction module is usually necessary, since drawings with a general geometry are seldom correct. In practice, for example, if a drawing is got from a hand-made sketch or by filtering a real image, the coordinates of its vertices will seldom lie in the right places, and reconstruction will not be possible. The third goal of the Thesis has been to efficiently solve this problem. To this end, we have devised the first algorithm for line drawing correction that allows the simultaneous movement of all the vertices. This yields better solutions than existing approaches, which only allowed the displacement of a subset of the vertices, or failed to correct some combinatorial structures. Moreover, we have provided a second correction strategy that keeps the vertices fixed but alters the combinatorial structure.<br/><br/>The developed techniques find applications in the design of new man-machine interfaces for solid modeling, since they allow the reconstruction of 3D shapes from rough hand-made sketches.