Browse Prior Art Database

# A DESIGN METHOD FOR RELAXATION LABELING APPLICATIONS

IP.com Disclosure Number: IPCOM000128224D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 33K

## Publishing Venue

Software Patent Institute

## Related People

Robert A. Hummel: AUTHOR [+3]

## Abstract

In an earlier paper, a theory of consistency in ambiguous labelings of objec ts has been developed This theory allows the relaxation labeling algorithm to be interpreted as a method for finding consistent labelings and allows specific applications to be tailored in accordance with intended design goals. We begin by discussing the general class of problems to which this theory is applicable. We then outline the theory of consistency and the principal results implied by the relaxation labeling algorithm in conjunction with this theory. Finally, we discuss a design methodology for implementing applications.

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A DESIGN METHOD FOR RELAXATION LABELING APPLICATIONS

BY Robert A. Hummel

Technical Report No. 68 Robotics Report No. 11

March, 198:

1. Introduction

In an earlier paper, a theory of consistency in ambiguous labelings of objec ts has been developed This theory allows the relaxation labeling algorithm to be interpreted as a method for finding consistent labelings and allows specific applications to be tailored in accordance with intended design goals. We begin by discussing the general class of problems to which this theory is applicable. We then outline the theory of consistency and the principal results implied by the relaxation labeling algorithm in conjunction with this theory. Finally, we discuss a design methodology for implementing applications.

2. Labeling Problems

The discrete labeling problem occurs when each of a finite number of objects are to be assigned a label chosen from a finite label set. Let apa 210*',an denote the n distinct objects, and

(Equation Omitted)

the set of possible labels. An unambiguous labeling is then an assignment mapping objects to labels. For example, if object a i is labeled by X then the integer map 1 4 X, can be used to define'the labelingo

In practical systems, measurements are made t6 describe object ail' and a most probable label is assigned independent of the labels assigned to neighboring objects. However, these decisions may be in error because of the myopia of a purely local viewpointo Further, since the decision as to which label to assign to a particular object is fraught with uncertainty, information is discarded when we eliminate possible but improbable labels in favor of a single label at each object. Consequently, it is useful to extend the notion of labelings to weighted labeling assignments. In this model, a nonnegative weight pi(X) is assigned for each label in the label set, at every object. The weight Pi(X) denotes the confidence level that object ai should be labeled by label X These weights are normalized by the condition

(Equation Omitted)

The assignment pi(t) = I signifies that object ai is unambiguously labeled by label Xt, (see (21). (The distribution of values (pi(l),...,pi(m)) at object i makes the weights look very much like probabilities, but this viewpoint is unhelpful).

By coAcatenating assignment weights, we can form an assignment vector

New York University Page 1 Dec 31, 1983

Page 2 of 12

A DESIGN METHOD FOR RELAXATION LABELING APPLICATIONS

(Equation Omitted)

(Due tothe normalization condition, there can be-only one component with a value one at each object). We call the space of all possible assignment vectors T the assignment space IK. The set of unambiguous labelings can be viewed as a subset IK* IK, and is described by labelings in which all assignment components pi(x) are either Oor 1. It is not hard to show that IK is the convex hull of IK*

3. Support Functions

To apply the relaxation labeling...