A kinematic-geometric approach to spatial interpretation of line drawings

Author

Ros, Lluís

Director

Thomas, Federico

Tutor

Riera, Jordi (Riera Colomer)

Date of defense

2000-11-14

ISBN

8469957511

Legal Deposit

B.37626-2001



Department/Institute

Universitat Politècnica de Catalunya. Institut d'Organització i Control de Sistemes Industrials

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.

Keywords

dibuix; interpretació; espai; algorismes

Subjects

51 - Mathematics

Knowledge Area

120703. Cibernética - 1204. Geometria - 12030. Inteligencia artificial

Documents

thesis.pdf

4.470Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)