Browse Prior Art Database

ADJACENCY IN DIGITAL PICTURES

IP.com Disclosure Number: IPCOM000128500D
Original Publication Date: 1972-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 9 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

Azriel Rosenfeld: AUTHOR [+3]

Abstract

CONDENSED REPORT CONTENTS: Let S be a subset of a digital picture, and let ~ be the complement of S. It is well known that the connected components of S and 9, under the relation "is adjacent to", form a tree and algorithms for constructing this tree have been devised. The main purpose of this paper is to prove that the components do form a tree, and in the pro-cess, to provide a basis for proving the validity of the tree-constructing algorithms.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ADJACENCY IN DIGITAL PICTURES

Azriel Rosenfeld

The support of the Office of Naval Research, under Contract N00014-67-A-0239-0062, is gratefully acknowledged. The author is also indebted to Anupam N. Shah for several help-ful discussions, and to Mrs. Eleanor B. Waters for her help in preparing the manuscript.

RESEARCH PROGRESS REPORT

TITLE: Adjacency in digital pictures, Azriel Rosenfeld, University of Maryland Computer Science Center Technical Report TR-203, October, 1972; Contract N00014-67-A-0239-0062.

BACKGROUND: The Computer Science Center of the University of Maryland is investigating the theory of image processing by computer.

CONDENSED REPORT CONTENTS: Let S be a subset of a digital picture, and let ~ be the complement of S. It is well known that the connected components of S and 9, under the relation "is adjacent to", form a tree and algorithms for constructing this tree have been devised. The main purpose of this paper is to prove that the components do form a tree, and in the pro-cess, to provide a basis for proving the validity of the tree-constructing algorithms.

FOR FURTHER INFORMATION: The complete report is available in the major Navy technical libraries and can be ob- tained from the Defense Documentation Center. A few copies are available for distribution by the author.

1. Basic concepts

Let I x I be the set of pairs of integers, and let

(Equation Omitted)

be in I x I. The four pairs (i l,j) and (i,j l) are called the 4-neighbors of x, and are said to be 4- adjacent to x. These same pairs, together with the four pairs (i l,j l), are called the 8-neighbors of x (8-adjacent to x). More generally, if S,T are subsets of I x I, we say that S is (4- or 8-) adjacent to T if some x E S is (4- or 8-) adjacent to some y E T. From now on, elements of I x I will be called points.

A path from x to y is a sequence of distinct points

(Equation Omitted)

such that x i is adjacent to n. There are two versions of this defini- x i-11 I :!g i f. tion, "4-path" and "8-path", depending on which type of adjacency is used. Similarly, there are two versions of most of the definitions which follow.

University of Maryland Page 1 Dec 31, 1972

Page 2 of 9

ADJACENCY IN DIGITAL PICTURES

If x,y E S 9 1 x I, we say that x is connected to y in S if there is a path from x to y consisting entirely of points of S. Readily, "is connected to" is an equiv-alence relation; the equivalence classes under this re-lation are called the connected components of S. If S has only one component, it is called connected.

Proposition 1. If S contains T, every component of T is contained in a unique component of S. Let be the complement of S. If S is finite, all points of that are sufficiently far from the origin are evidently connected in 9. It follows that exactly one component of ~ is infinite; we call this component the background of S. All other components of S, if any, are called holes in S. If S is...