Affordable Access

Publisher Website

Linear-time algorithms for testing the realisability of line drawings of curved objects

Authors
Journal
Artificial Intelligence
0004-3702
Publisher
Elsevier
Publication Date
Volume
108
Identifiers
DOI: 10.1016/s0004-3702(98)00118-0
Keywords
  • Line Drawing Labelling
  • Constraint Satisfaction Problem
  • Np-Completeness
Disciplines
  • Computer Science
  • Law
  • Linguistics

Abstract

Abstract This paper shows that the semantic labelling of line drawings of curved objects with piecewise C 3 surfaces is solvable in linear time. This result is robust to changes in the assumptions on object shape. When all vanishing points are known, a different linear-time algorithm exists to solve the labelling problem. Furthermore, in both cases, all legally labelled line drawings of curved objects are shown to be physically realisable. However, when some but not all of the vanishing points are known, when the drawing is an orthographic projection of a scene containing parallel lines or when we wish to minimise the number of phantom junctions, the labelling problem becomes NP-hard. The introduction of collinearity constraints also renders the labelling problem NP-complete, except in the case when all vanishing points are known.

There are no comments yet on this publication. Be the first to share your thoughts.