Back to search

University of British Columbia

Using discrimination graphs to represent visual knowledge

Abstract

dc:description

This dissertation is concerned with the representation of visual knowledge. Image features often have many different local interpretations. As a result, visual interpretations are often ambiguous and hypothetical. In many model-based vision systems the problem of representing ambiguous and hypothetical interpretations is not very specifically addressed. Generally, specialization hierarchies are used to suppress a potential explosion in local interpretations. Such a solution has problems, as many local interpretations cannot be represented by a single hierarchy. As well, ambiguous and hypothetical interpretations tend to be represented along more than one knowledge representation dimension limiting modularity in representation and control. In this dissertation a better solution is proposed. Classes of objects which have local features with similar appearance in the image are represented by discrimination graphs. Such graphs are directed and acyclic. Their leaves represent classes of elementary objects. All other nodes represent abstract (and sometimes unnatural) classes of objects, which intensionally represent the set of elementary object classes that descend from them. Rather than interpreting each image feature as an elementary object, we use the abstract class that represents the complete set of possible (elementary) objects. Following the principle of least commitment, the interpretation of each image feature is repeatedly forced into more restrictive classes as the context for the image feature is expanded, until the image no longer provides subclassification information. This approach is called discrimination vision, and it has several attractive features. First, hypothetical and ambiguous interpretations can be represented along one knowledge representation dimension. Second, the number of hypotheses represented for a single image feature can be kept small. Third, in an interpretation graph competing hypotheses can be represented in the domain of a single variable. This often eliminates the need for restructuring the graph when a hypothesis is invalidated. Fourth, the problem of resolving ambiguity can be treated as a constraint satisfaction problem which is a well researched problem in Computational Vision. Our system has been implemented as Mapsee-3, a program for interpreting sketch maps. A hierarchical arc consistency algorithm has been used to deal with the inherently hierarchical discrimination graphs. Experimental data show that, for the domain implemented, this algorithm is more efficient than standard arc consistency algorithms.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1985

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mulder, Jan A.

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/25943

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Mulder, Jan A.. Using discrimination graphs to represent visual knowledge. doctoral thesis, University of British Columbia, 1985. http://hdl.handle.net/2429/25943