Browse Prior Art Database

Original Publication Date: 1984-Aug-13
Included in the Prior Art Database: 2007-Mar-30
Document File: 48 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Kirkpatrick, David G.: AUTHOR [+3]


RJ 4397 (47785) 8/13/84 Computer Science A FRAMEMTC)R.K FOR CO>IP'L"TATIONAL 3IORPHOLOGY

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 48

RJ 4397 (47785) 8/13/84 Computer Science


David G. ~iric~atrick* IBM Research Laboratory San Jose, California 95193
John D. Radke
Department of Geography
Wilfred Laurier University
Waterloo, Canada N2L3C5

ABSTRACT: This paper, which will appear as a chapter in the forthcoming book entitled Compurational Geometry, G. T. Toussaifi, editor (North-Holland Publishing Company), outlines a neu- methodology for describing the "internal structure" (or "skeleton") of planar point sets. The methodology, which is based on parameterized measures of neiaborliness, gives rise to a spectrum of possible internal shapes. Applications to the analysis of both point set and network patterns are described.


On leave from the Computer Science Department, University of British Columbia, Vancouver, B.C., V6TlW5, Canada

[This page contains 1 picture or other non-text object]

Page 2 of 48

[This page contains 1 picture or other non-text object]

Page 3 of 48


    The relatively young field of computational geometry has had a significant and steadily increasing impact on the development and unification of techniques in pattern recognition. It has also made it possible to discuss with greater uniformity and precision the inherent complexity of many pattern recognition tasks. Toussaint [T3] surveys all but the most recent literature in computationaI geometry related to pattern recognition. He emphasizes the fundamental geometrical structures underlying a broad range of pattern reco,~tion applications along with the complexity issues that arise in the construction and manipulations of these structures.

    Toussaint is careful to point out that certain aspects of pattern recognition problems are not adequately captured by geometrical properties alone. In fact, he pays little attention to statistical attribute of patterns, even those that attempt to aggregate fundamental geometrical properties. We follow Toussaint in focusing our attention on the purely geometrical attributes of patterns. We assume that in practice these will be analyzed in various ways in an attempt to characterize the pattern at hand. It is understood that even the exact solution of the geometrical problems that arise in our discussions constitute only partial, approximate, or heuristic solutions of the associated pattern recognition problems.

Toussaint [T3] coins the term computational morphology to describe the situation where


 a computational geometrical structure is intended to extract-the form of the input." This paper can be viewed as a presentation of new tools for the development of computational

morphology. Ow results and techniques were developed originally in the context of geographical pattern recognition [R]. However, as we hope to make clear, they have somewhat broader application.

P 2

[This page contains 1 pic...