Shaped-Based Recognition of 3D Objects from 

2D Projections 

by Philip David and Daniel DeMenthon 

ARL-TR-4006 December 2006 

Approved for public release; distribution unlimited. 
NOTICES 

Disclaimers 

The findings in this report are not to be construed as an official Department of the Army position unless 

so designated by other authorized documents. 

Citation of manufacturer’s or trade names does not constitute an official endorsement or approval of the 

use thereof. 

Destroy this report when it is no longer needed. Do not return it to the originator. 
Army Research Laboratory 

Adelphi, MD 20783-1197 

ARL-TR-4006 December 2006 

Shaped-Based Recognition of 3D Objects from 

2D Projections 

Philip David 

Computational and Information Sciences Directorate, ARL 

Daniel DeMenthon 

University of Maryland

Approved for public release; distribution unlimited. 
ii

REPORT DOCUMENTATION PAGE Form Approved 

OMB No. 0704-0188

Public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the 

data needed, and completing and reviewing the collection information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing the 

burden, to Department of Defense, Washington Headquarters Services, Directorate for Information Operations and Reports (0704-0188), 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202-4302. 

Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to any penalty for failing to comply with a collection of information if it does not display a currently 

valid OMB control number. 

PLEASE DO NOT RETURN YOUR FORM TO THE ABOVE ADDRESS. 

1. REPORT DATE (DD-MM-YYYY)

December 2006 

2. REPORT TYPE 

Summary 

3. DATES COVERED (From - To) 

January to July 2006 

5a. CONTRACT NUMBER 

5b. GRANT NUMBER 

4. TITLE AND SUBTITLE 

Shaped-Based Recognition of 3D Objects from 2D Projections 

5c. PROGRAM ELEMENT NUMBER 

5d. PROJECT NUMBER 

5e. TASK NUMBER 

6. AUTHOR(S) 

Philip David (ARL) and Daniel DeMenthon (University of Maryland) 

5f. WORK UNIT NUMBER 

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 

U.S. Army Research Laboratory 

ATTN: AMSRD-ARL-CI-CB 

2800 Powder Mill Road 

Adelphi, MD 20783-1197

8. PERFORMING ORGANIZATION 

 REPORT NUMBER 

ARL-TR-4006

9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR'S ACRONYM(S) 

U.S. Army Research Laboratory 

2800 Powder Mill Road 

Adelphi, MD 20783-1197 

11. SPONSOR/MONITOR'S REPORT 

 NUMBER(S) 

12. DISTRIBUTION/AVAILABILITY STATEMENT 

Approved for public release; distribution unlimited. 

13. SUPPLEMENTARY NOTES 

14. ABSTRACT 

We present an object recognition algorithm that uses model and image line features to locate complex objects in high clutter 

environments. Corresponding line features are determined by a three-stage process. The first stage generates a large number 

of approximate pose hypotheses from correspondence of one or two lines in the model and image. Next, pose hypotheses 

from the previous stage are quickly evaluated and ranked by a comparison of local image neighborhoods to the corresponding 

local model neighborhoods. Fast nearest neighbor and range search algorithms are used to implement a distance measure that 

is unaffected by clutter and partial occlusion. The ranking of pose hypotheses is invariant to changes in image scale, 

orientation, and partially invariant to affine distortion. Finally, a robust pose estimation algorithm is applied for refinement 

and verification, starting from the few best approximate poses produced by the previous stages. Experiments on real images 

demonstrate robost recognition of partially occluded objects in very high clutter environments. 

15. SUBJECT TERMS

Object recognition, soft posit, shape features 

16. SECURITY CLASSIFICATION OF:

19a. NAME OF RESPONSIBLE PERSON

Philip David 

a. REPORT 

Unclassified 

b. ABSTRACT 

Unclassified 

c. THIS PAGE 

Unclassified 

17. LIMITATION

OF 

ABSTRACT 

SAR 

18. NUMBER

OF 

PAGES 

40 

19b. TELEPHONE NUMBER (Include area code) 

301-394-5603 

Standard Form 298 (Rev. 8/98) 

Prescribed by ANSI Std. Z39.18 
Contents

1. Introduction 1

2. Related Work 3

3. Generating Pose Hypotheses 6

4. Similarity of Line Neighborhoods 9

5. Distance Between Lines 12

6. Graduated Assignment for Lines 14

7. Experiments 19

8. Conclusions 23

Appendices 25

A. Line Detection 25

B. Modifications of the Sinkhorn Algorithm 27

C. Solving for the Affine Transformation 29

References 30

Distribution 32

iii
List of Figures

1 Outline of the new object recognition algorithm. (The constant N is the number of pose refinements performed; as discussed in section 7, good performance

is obtained with N = 4) . . . . . . . . . . . . . . . . ............. 4

2 Recognizing books in a pile. (The two models were generated from frontal

images of the books) . ................. ............. 4

3 Geometry for calculation of the approximate affine transformation . . . . . . 9

4 Pose hypotheses generated for a correct correspondence of a real model and image line. (The model lines [dashed lines and thick solid line] are shown overlaid on the image lines [thin lines]. The one thick solid line in each image

shows the base correspondence: a model line perfectly aligned with an image line. The top row shows the two similarity transformations, one for each

possible alignment of the base lines. The bottom row shows the two affine

transformations, one for each possible corner correspondence of the base lines.

These are the complete set of transformations hypothesized for this base correspondence. Notice the better alignment in the images of the bottom row,

resulting from the use of corner angle correspondences, compared to the upper

left image) . . . . . . . . ...................... . . . . . . . 10

5 The neighborhood radius of line l, in the center of the image, is the minimum

distance r(l) for which both end points of Nnbr lines are within distance r(l)

of l. (Here, Nnbr = 5, but in actual experiments, we take Nnbr = 10) . . . . . 11

6 Sampling the position of model and image lines. (Image line l is represented

by its midpoint [xmid, ymid] and its orientation θ. Projected model line l

0 is represented by the points {[ ̄xi, y ̄i], i = 1,...,Npts} and its orientation θ0

. When

the pose of a model is accurate and a model line and image line correspond,

the midpoint of that image line will be close to some sample point on the

projected model line, and the orientation of the two lines will be similar. This

is true even when the image line is fragmented. In this example, [xmid, ymid]

is closest to [ ̄x7, y ̄7]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

iv
7 Comparison of the two objective functions for a typical minimization by the

graduated assignment algorithm. (The solid line is E, which uses the Euclidean distances to the nearest neighbor, and the dotted line is E0

, which uses

the sum of the distances of the image line endpoints to the infinitely extended

model lines. The values of E and E0 generally decrease during the optimization process, but they can also rise because of changes in the assignment

variables Mjk)...................... . . . . . . . . . . . . . 18

8 The pose refinement algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 19

9 Pose refinement using the graduated assignment algorithm: initial pose (left)

and final pose after applying the algorithm (right). . . . . . . . . . . . . . . 19

10 Five books, some partially occluded, are recognized in a cluttered environment 20

11 Image of a table of books taken by a camera tilted 50 degrees from vertical . 21

12 Pθ (k) is the probability that one of the first k sorted pose hypotheses for a

model leads to a correct recognition for that model. (θ is the difference in

viewpoint elevation between the model and the object. For θ ≤ 40◦, one of

the four highest ranked pose hypotheses always leads to correct recognition.

The curves for θ = 0 through 40 degrees are superposed for k ≥ 4) . . . . . . 22

13 Recognition of 3-D objects from viewpoint-dependent 2-D models: computer

monitor (top row), stapler (middle row), and hole punch (bottom row). (Shown

in each row, from left to right, is the 2-D object model, original image, image

lines, and model of recognized object overlaid on the original image. The

modeled view of each object differs from the test view by 20 to 30 degrees) . 22

A.1 The accuracy of our line detector is depicted in this graph, which plots the

relative error versus the fraction of the model lines detected with relative error

no greater than that amount . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

B.1 The new Sinkhorn algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

v
vi 

INTENTIONALLY LEFT BLANK. 
1. Introduction

Object recognition in cluttered environments is a difficult problem with widespread

applications. Most approaches to object recognition, including the one presented here, rely

on the algorithm first finding correspondences between model features and image features,

then computing a hypothesized model pose, and finally searching for additional image

features that support this pose. The most challenging part of this process is the

identification of corresponding features when the images are affected by clutter, partial

object occlusion, changes in illumination, and changes in viewpoint. In fact, once the

feature correspondence problem is solved, object recognition becomes almost trivial. A

wide variety of features has been employed by object recognition systems, including points,

edges, and textured regions. There are advantages and disadvantages to each type of

feature, and each is suitable for different applications.

The surfaces of many objects consist of regions of uniform color or texture. Most of the

information available for object recognition is at the boundaries (edges) of these regions; a

line drawing representation of these objects provides a nearly complete description of these

objects. Approaches to object recognition that rely on variations in texture inside these

regions are likely to perform poorly. Furthermore, objects such as bicycles, chairs, and

ladders, that are composed of thin, stick-like components are especially difficult for

texture-based approaches because background clutter will be present within a few pixels of

any object pixel, thus corrupting local texture templates (4 ). Methods that rely on the

boundary shapes are better suited to these types of objects. This report presents a simple,

effective, and fast method for recognizing partially occluded 2D (two-dimensional) objects

in cluttered environments, where the object models and their images are each described by

sets of line segments. A fair amount of perspective distortion is tolerated by the algorithm,

so the algorithm is also applicable to 3D (three-dimensional) objects that are represented

by sets of viewpoint-dependent 2D models. Because of the close ties between object

recognition and feature correspondence, this report is about a new feature correspondence

algorithm as much as it is about a new object recognition algorithm.

Our approach assumes that at least one model line is detected as an unfragmented line in

the image. By unfragmented, we mean that the corresponding image line is extracted from

the image as a single continuous segment between the two end points of the projected

model line. This necessarily requires that at least one model line be unoccluded.

Additional model lines must be present in the image for verification, but these may be

partially occluded or fragmented. A potential difficulty with this approach is that line

detection algorithms often fragment lines because of difficulties in parameter selection, and

they usually do not extract lines completely at the intersections with other lines. The issue

of fragmentation resulting from poor parameter selection can be ameliorated through

1
post-processing steps that combine nearby collinear lines. However, this has not been

necessary in any of our experiments. The issue of line detection algorithms being unable to

accurately locate the end points of lines at the intersections with other lines do not cause a

problem because a few missing pixels at the ends of a line does not significantly affect the

computed model transformations (except in the case when the object’s image is so small as

to make recognition difficult, regardless of how well the object’s edges are detected). We

show that our line detector is able to detect a large number of object lines with very little

relative error in their length when compared to the corresponding projected model lines.

A three-stage process is used to locate objects. In the first stage, a list of approximate

model pose hypotheses is generated. Every pairing of a model line to an image line first

contributes a pose hypothesis consisting of a similarity transformation. When both the

model line and the corresponding image line form corner-like structures with other nearby

lines and the angles of the corners are similar (within 45 degrees), a pose hypothesis

consisting of an affine transformation is added to the hypothesis list, one for each such

compatible corner correspondence. Typically, each model-to-image line correspondence

contributes a small number of poses (one to six) to the hypothesis list.

We employ information inherent in a single line correspondence (position, orientation, and

scale) to reduce the number of correspondences that must be examined in order to find an

approximately correct pose. For m model lines and n image lines, we generate O(mn)

approximate pose hypotheses. Compare this to traditional algorithms that generate precise

poses from three pairs of correspondences, where there are as many as O(m3n3) pose

hypotheses. An approach such as random sample consensus (RANSAC) (9 ), which

examines a very small fraction of these hypotheses, still has to examine O(n3) poses to

ensure with probability 0.99 that a correct precise pose will be found (6 ). By starting with

an approximate pose instead of a precise pose, we are able to greatly reduce the number of

poses that need to be examined and ultimately find a correct precise pose.

Most of the pose hypotheses will be inaccurate because most of the generating

correspondences are incorrect. The second stage of our approach ranks each pose

hypothesis based on the similarity of the corresponding local neighborhoods of lines in the

model and image. The new similarity measure is largely unaffected by image clutter,

partial occlusion, and fragmentation of lines. Nearest neighbor search is used in order to

compute the similarity measure quickly for many pose hypotheses. Because this similarity

measure is computed as a function of approximate pose, the ranking of the pose hypotheses

is invariant to image translation, scaling, rotation, and partially invariant to affine

distortion of the image. By combining the process of pose hypothesis generation from

assumed unfragmented image lines with the neighborhood similarity measure, we are able

to quickly generate a ranked list of approximate model poses which is likely to include a

number of highly ranked poses that are close to the correct model pose.

2
The final stage of the approach applies a more time-consuming but also more accurate pose

refinement and verification algorithm to a few of the most highly ranked approximate

poses. Gold’s graduated assignment algorithm (10,11 ), modified for line correspondences,

is used for this purpose because it is efficient, tolerant of clutter and occlusion, and does

not make binary correspondence decisions until an optimal pose is found.

Our three-stage approach allows CPU resources to be quickly focused on the highest payoff

pose hypotheses, which in turn results in a large reduction in the amount of time needed to

perform object recognition. An outline of the algorithm is shown in figure 1. In the

following sections, we first describe related work and then describe each step of our

algorithm in more detail. Although any line detection algorithm may be used, appendix A

briefly discusses the line detection algorithm that we use and presents an evaluation of its

ability to extract unfragmented lines from an image. Section 3 then shows how approximate

pose hypotheses are generated from a minimal number of line correspondences. Next, in

sections 4 and 5, we present our method for efficiently comparing local neighborhoods of

model lines to local neighborhoods of image lines. Section 6 describes the pose refinement

and verification algorithm that we use. Experiments with real imagery containing high

levels of clutter and occlusion (see figure 2, for example) are discussed in section 7 and

demonstrate the effectiveness of the algorithm; this section also gives the run-time

complexity of the algorithm. We see that our algorithm is faster and able to handle greater

amounts of clutter than previous approaches that use line features. The approach is able to

recognize planar objects that are rotated by as much as 60 degrees away from their

modeled viewpoint and recognize 3-D objects from 2-D models that are rotated by as much

as 30 degrees from their modeled viewpoint. The report ends with conclusions in section 8.

2. Related Work

Automatic registration of models to images is a fundamental and open problem in

computer vision. Applications include object recognition, object tracking, site inspection

and updating, and autonomous navigation when scene models are available. It is a difficult

problem because it comprises two coupled problems, the correspondence problem and the

pose problem, each easy to solve only if the other has been solved first.

A wide variety of approaches to object recognition has been proposed since Robert’s

ground-breaking work on recognizing 3-D polyhedral objects from 2-D perspective images

(19 ). Among the pioneering contributions are Fischler and Bolles’ RANSAC method (9 ),

Baird’s tree-pruning method (2 ), and Ullman’s alignment method (22 ). These approaches,

which hypothesize poses from small sets of correspondences and reject or accept those

poses based on the presence of supporting correspondences, become intractable when the

3
Create a data structure for nearest neighbor and range searches of

image lines.

Using a range search, identify corners in each model and in the image.

for each model do

H = . // Initialize hypothesis list to empty.

for each pair of model line l and image line l

0

, do

C = Pose hypotheses generated from l, l

0

, and nearby corners.

H = H ∪ C.

Evaluate the similarity of model and image neighborhoods for poses

C.

end for

P = Sort H based on neighborhood similarity measure.

for i = 1 to N do

Apply the graduated assignment algorithm starting from pose

P (i).

if a sufficient number of line correspondences are found then

An object has been recognized.

end if

end for

end for

Figure 1. Outline of the new object recognition algorithm. (The constant N is the number of pose

refinements performed; as discussed in section 7, good performance is obtained with N = 4.)

(a) Models (b) Test image

(d) Recognized books (c) 519 detected lines

Figure 2. Recognizing books in a pile. (The two models were generated from frontal images of the

books.)

4
number of model and image features becomes large, especially when the image contains

significant clutter.

More recently, the use of rich feature descriptors has become popular as a way of reducing

the number of feature correspondences that must be examined. The Harris corner detector

(13 ) has seen widespread use for this purpose; however, it is not stable to changes in image

scale, so it performs poorly when models and images of different scales are matched.

Schmid and Mohr (20 ) have developed a rotationally invariant feature descriptor using the

Harris corner detector. Lowe (16 ) extended this work to scale invariant and partially affine

invariant features with his scale invariant feature transformation (SIFT) approach, which

uses scale-space methods to determine the location, scale, and orientation of features, and

then, relative to these parameters, a gradient orientation histogram describing the local

texture. Excellent results have been obtained by approaches with these rich features when

objects have significant distinctive texture. However, there are many common objects that

possess too little distinctive texture for these methods to be successful. Examples include

thin objects such as bicycles and ladders where background clutter will be present near all

object boundaries and uniformly textured objects such as upholstered furniture. In these

cases, only the relations between geometric features (such as points and edges) can be used

for matching and object recognition. Edges are sometimes preferred to points because they

are easy to locate and are stable features on textured and nontextured objects.

Our approach has some similarities to Ayache and Faugeras’s hypotheses predicted and

evaluated recursively (HYPER) system (1 ). They use a tree-pruning algorithm to

determine 2-D similarity transformations that best align 2-D object models with images,

where both the models and images are represented by sets of line segments. The ten

longest lines in the model are identified as “privileged” segments, which are used for initial

hypothesis generation because there are fewer of them (so fewer hypotheses have to be

generated) and because the use of long segments results in more accurate pose estimates.

The authors point out that the probability of having all privileged segments simultaneously

occluded is very small, and only one privileged segment needs to be visible for us to identify

a model. Although this is true, we believe that long model lines are just as likely as short

model lines to be fragmented in an image, and therefore, we treat all model lines identically

and do not identify any as privileged. In the HYPER system, 2-D pose hypotheses are

generated by matching each privileged model line is matched to every compatible image

line, where compatibility is defined in terms of the difference in the angles of corners

formed with neighbors, and the difference in scale from an a priori scale. The hypotheses

are ranked based on the degree of compatibility of the matched segments, and then the

best hypotheses are refined with a tree search to locate additional matching model and

image segments that are compatible with the initial pose estimate. During this tree search,

a pose hypothesis is augmented with additional matches when the difference in orientation

of the two segments, the Euclidean distance between their midpoints, and the relative

5
difference between their lengths, is small. In contrast, our pose hypotheses are based on

affine transformations instead of similarity transformations; we use a dissimilarity measure

(see section 5) to rank hypotheses, which is less affected by line fragmentation because it

does not depend on the lengths of lines nor on unique reference points on the lines, and we

use the more robust and efficient graduated assignment algorithm (10 ) for pose refinement.

A number of more recent works (18,4 ) have also used edges for object recognition of poorly

textured objects. Mikolajczyk et al. (18 ) generalize Lowe’s SIFT descriptors to edge

images, where the position and orientation of edges are used to create local shape

descriptors that are orientation and scale invariant. Carmichael’s approach (4 ) uses a

cascade of classifiers of increasing aperture size, trained to recognize local edge

configurations, to discriminate between object edges and clutter edges; this method

requires many training images to learn object shapes, and it is not invariant to changes in

image rotation or scale.

Gold and Rangarajan (11 ) simultaneously compute pose and 2D-to-2D or 3D-to-3D point

correspondences using deterministic annealing to minimize a global objective function. We

previously used this method (5 ) for matching 3-D model lines to 2-D image lines, and we

use it here for the pose refinement stage of our algorithm. Beveridge (3 ) matches points and

lines using a random start local search algorithm. Whitley et al. (23 ) present an algorithm

for 2-D pose estimation that uses a spatial heuristic similar to our corner correspondences

to initialize a messy genetic algorithm and then uses Beveridge’s local search algorithm

to refine individuals in the population. Denton and Beveridge (7 ) extended Beveridge’s

original work by replacing random starts with a heuristic that is used to select which initial

correspondence sets to apply the local search algorithm. Although we use line features

instead of point features, Denton’s approach is conceptually similar to ours in a number of

ways. Both approaches first hypothesize poses using small sets of local correspondences,

then sort the hypotheses based on a local match error, and finally apply a pose refinement

and verification algorithm to a small number of the best hypotheses. Significant differences

between the two approaches are that our approach uses lines instead of points, and zero or

one neighboring features instead of four to generate pose hypotheses; thus, our approach

will have many fewer hypotheses to consider, and each hypothesis is much less likely to be

corrupted by spurious features (clutter).

3. Generating Pose Hypotheses

We wish to generate a small set of approximate poses that, with high certainty, includes at

least one pose that is close to the true pose of the object. The smaller the number of

correspondences used in estimating a pose, the less likely the estimated pose will be

6
corrupted by spurious correspondences. At the same time, however, using fewer

correspondences will produce a less accurate pose when all correspondences used by the

estimation are correct. From a single correspondence of a model line to an image line,

where the image line may be fragmented (only partially detected because of partial

occlusion or faulty line detection), we can compute the 2-D orientation of the model as well

as a one-dimensional constraint on its position, but the scale and translation of the model

cannot be determined; this does not provide sufficient geometric constraints to evaluate the

similarity of a local region of the model with a local region of the image.

On the other hand, if we assume that a particular image line is unfragmented, then from a

single correspondence of a model line to this image line, we can compute a 2-D similarity

transformation of the model. This is possible because the two end points of the

unfragmented image line must correspond to the two end points of the model line, and two

corresponding points are sufficient to compute a similarity transformation. A similarity

transformation will be accurate when the viewing direction used to generate the 2-D model

is close to the viewing direction of the object. However, even when there is some

perspective distortion present, approximate similarity transformations from correct

correspondences are often highly ranked by the next stage of our approach. Generating

hypothesized poses that are highly ranked in the next stage is the main goal of this first

stage since the pose refinement algorithm used in the final stage has a fairly large region of

convergence.

Because we do not know which end point of the model line corresponds to which end point

of the image line, we consider both possibilities and generate a similarity transformation

for each. For p1 and p2 model line end points corresponding to image line end points q1

and q2, respectively, the similarity transformation mapping the model to the image is

qi = Api + t where A = sR and s, R, and t are the scaling, rotation, and translation,

respectively, defined by

s = kq1 − q2k / kp1 − p2k ,

R =

∙ cos θ − sin θ

sin θ cos θ

 ̧

,

t = q1 − Ap1,

and where θ is the rotation angle (in the range −π to π, clockwise being positive) from

p1 − p2 to q1 − q2.

We can obtain more accurate approximate poses with little additional work when the

model line and the unfragmented image line (called the base lines) form corner-like

structures with other lines: corners in the model should correspond to corners in the image.

Corners in the model are formed by pairs of model lines that terminate at a common point,

while corners in the image are formed by pairs of image lines that terminate within a few

pixels of each other. By looking at corners, we expand our search to correspondences of

7
two line pairs. However, because we restrict the search for corner structures in the image to

lines that terminate within a few pixels of an end point of a base image line, the number of

corners examined for any base image line is usually quite small. As before, we assume only

that the base image line is unfragmented; other image lines may be fragmented. If a base

model line forms a corner with another model line, which is usually the case for objects

described by straight edges, and if the base image line is unfragmented, then all model lines

that share an end point with the base model line should be unoccluded around that end

point in the image, and therefore, there is a good chance that these other models lines will

appear in the image near the corresponding end point of the base image line. Thus, looking

at corners formed with the base image lines provides a way of finding additional line

correspondences with a low outlier rate.

The model and image lines that participate in corner structures are efficiently located with

a range search algorithm (17 ). The end points of all image lines are first inserted into a

search tree data structure. Then, for each end point of each image line, a range search is

performed to locate nearby end points and their associated lines. A similar process is

performed for the model lines. This pre-processing step is done once for each model and

image. To generate pose hypotheses for a particular base correspondence, the angles of

corners formed with the base model line are compared to the angles of corners formed with

the base image line. An affine pose hypothesis is generated for any pair of corner angles

that are within 45 degrees. As before, this is repeated for each of the two ways that the

base model line can correspond to the base image line. Note that these affine pose

hypotheses are generated in addition to the similarity pose hypotheses described before.

The similarity pose hypotheses are kept even though they may be less accurate because the

affine pose hypotheses are more susceptible to being corrupted by spurious correspondences.

An affine pose hypothesis is generated as follows. Let p1 and p2 be the end points of the

base model line and q1 and q2 be the corresponding end points of the base image line (see

figure 3). Assume that a pair of corners is formed with the base lines by model line p and

image line q that terminate near end points p1 and q1 and have angles θp and θq,

respectively. We have two pairs of corresponding points and one pair of corresponding

angles. Since a 2-D affine transformation has 6 degrees of freedom but we have only five

constraints (two for each point correspondence and one for the angle correspondence), we

impose the additional constraint that the affine transformation must scale the length of line

p in the same way as it does the length of the base model line p1p2. This, defines a third

pair of corresponding points p3 and q3, on p and q, respectively, as shown in figure 3. p3 is

the second end point of p, and q3 is the point collinear with q so that

kp2 − p1k

kq2 − q1k = kp3 − p1kkq3 − q1k

.

8
Image Corner

Model Corner

q

p

Figure 3. Geometry for calculation of the approximate affine transformation.

q3 is found to be

q1 + kp3 − p1k kq2 − q1k

kp2 − p1k2

∙ cos θq − sin θq

sin θq cos θq

 ̧

(p2 − p1).

The affine transformation mapping a model point pi = £ pix piy

¤T to the image point

qi = £ qix qiy

¤T is

∙ qix

qiy

 ̧

=

∙ a1 a2

a3 a4

 ̧ ∙ pix

piy

 ̧

+

∙ tx

ty

 ̧

. (1)

For each correspondence pi ↔ qi we have two linear equations in the six unknowns a1, a2,

a3, a4, tx, and ty. From the three corresponding points, we can solve for the parameters of

the affine transformation. Figure 4 shows the pose hypotheses generated for a particular

correct base correspondence.

4. Similarity of Line Neighborhoods

The second stage of the recognition algorithm ranks all hypothesized approximate model

poses in the order that the pose refinement and verification algorithm should examine

them; the goal is to rank highly those poses that are most likely to lead the refinement and

verification algorithm to a correct precise pose. This way, the final stage can examine the

smallest number of approximate poses needed to ensure that a correct pose will be found if

an object is present. For this purpose, a geometric measure of the similarity between the

model (transformed by an approximate pose) and the image is computed. To ensure that

this similarity measure can be computed quickly, for any base model line generating a

9
Figure 4. Pose hypotheses generated for a correct correspondence of a real model and image line.

(The model lines [dashed lines and thick solid line] are shown overlaid on the image lines

[thin lines]. The one thick solid line in each image shows the base correspondence: a model

line perfectly aligned with an image line. The top row shows the two similarity transformations, one for each possible alignment of the base lines. The bottom row shows the two

affine transformations, one for each possible corner correspondence of the base lines. These

are the complete set of transformations hypothesized for this base correspondence. Notice

the better alignment in the images of the bottom row, resulting from the use of corner angle

correspondences, compared to the upper left image.)

10
hypothesized pose, only a local region of model lines surrounding the base line (called the

base model line’s neighborhood) is compared to the image lines. Let M be the set of lines

for a single model and I be the set of image lines. We define the neighborhood radius of a

line l to be the smallest distance, denoted r(l), so that the two end points of at least Nnbr

lines (excluding l) are within distance r(l) of l. In all our experiments, the value of Nnbr is

fixed at 10 lines (Nnbr ≤ |M|). The neighborhood of a model line l is the set of Nnbr model

lines, N (l), whose end points are within distance r (l) of l. Figure 5 illustrates a line and

its neighbors.

r(l)

l

Figure 5. The neighborhood radius of line l, in the center of the image, is the minimum distance r(l)

for which both end points of Nnbr lines are within distance r(l) of l. (Here, Nnbr = 5, but

in actual experiments, we take Nnbr = 10.)

For a hypothesized approximate model pose {A, t} generated for a base model line l, let

T (N (l), A, t) denote the neighbors of l transformed by the pose {A, t}, and let d (l

0

, l00)

denote the distance (defined in section 5) between two lines l

0 and l00 in the image. Then,

the geometric similarity between a model neighborhood N transformed by the pose {A, t}

and the set of image lines I is

S (N , I, A, t) = X

l0∈T (N ,A,t)

min 1⁄2Smax, min

l00∈I

d (l

0

, l00)

3⁄4

. (2)

The smaller the value of S (N , I, A, t), the more “similar” a model neighborhood N is to

the image I under the transformation {A, t}. The parameter Smax ensures that “good”

poses are not penalized too severely when a line in the model is fully occluded in the image.

11
This parameter is easily set if we observe the values of S (N , I, A, t) that are generated for

poor poses (that should be avoided) and then set Smax to this value divided by Nnbr.

As explained in section 5, the distance between a single model neighbor and the closest image

line can be found in time O (log n) when there are n image lines. Since |N | = Nnbr, the time

to compute S (N , I, A, t) is O (log n).

5. Distance Between Lines

For any image line l

0 (which is typically a transformed model line), we wish to efficiently

find the line l

00 ∈ I that minimizes d (l0

, l00) in equation 2 that expresses the similarity

between a model and image neighborhood. This search can be performed efficiently when

each line is represented by a point in an N -dimensional space and the distance between two

lines is the Euclidean distance between the corresponding points in this N -dimensional

space. Assuming that we have a suitable line representation, a tree data structure storing

these N -dimensional points can be created in time O (n log n) and the closest image line

can be found in time O (log n). This tree structure need only be created once for each

image and is independent of the model lines.

Thus, we want to represent each line as a point in an N -dimensional space so that the

Euclidean distance between two lines is small when the two lines are superposed. We would

also like the distance function to be invariant to partial occlusion and fragmentation of

lines. Representing a line by its 2-D midpoint is insufficient because two lines can have an

identical midpoint but different orientations. We could use the midpoint and orientation of

a line, but a short line superposed on a longer line (think of the short line as a partially

occluded version of the longer line) could be assigned a large distance because their

midpoints may be far. Further, there is problem associated with line orientation because a

line with an orientation of θ should produce the same distance as when its orientation is

given as θ ± 2kπ for k = 1, 2,.... For example, two lines with identical midpoints but

orientations 179 and −179 degrees should produce the same distance as if the orientations

of the two lines were 1 and −1 degree. It is not possible with a Euclidean distance function

to map both of these pairs of angles to the same distance. A solution to these occlusion

and orientation problems is to generate multiple representations of each line.

Let l be a line with orientation θ (relative to the horizontal, 0 ≤ θ ≤ π) and end points

[x1, y1] and [x2, y2]. When l is a line in the image (l ∈ I), l is represented by the two 3-D

points

∙ θ

rθ

,

xmid

rm

,

ymid

rm

 ̧

and ∙

θ − π

rθ

,

xmid

rm

,

ymid

rm

 ̧

(3)

12
where [xmid, ymid]=[x1 + x2, y1 + y2] /2 is the midpoint of the line and rθ and rm are

constant scale factors (described below); these are the 3-D points used to create the data

structure that is used in the nearest neighbor searches.

When l is a transformed model line (as in l

0 above), l is represented by the set of 3-D points

1⁄2∙ θ

rθ

,

x ̄i

rm

, y ̄i

rm

 ̧

,

∙

θ − π

rθ

,

x ̄i

rm

, y ̄i

rm

 ̧

, i = 1, 2,...,Npts3⁄4(4)

where

Npts =

»

k[x2 − x1, y2 − y1]k

w

1⁄4

+ 1, (5)

∆ = [x2 − x1, y2 − y1]

Npts − 1 ,

[ ̄xi, y ̄i]=[x1, y1]+(i − 1) ∆.

In words, two orientations are used for each transformed model line, but the position of the

line is represented by a series of Npts points that uniformly sample the length of the line at

an interval w. The reason why multiple sample points are required to represent the

position of transformed model lines but not the image lines is that when {A, t} is a correct

pose for the model, the image line, which may be partially occluded or otherwise

fragmented, will generally be shorter than the transformed model line. In this case, the

midpoint of the image line will lie somewhere along the transformed model line, but the

midpoint of the transformed model line may lie off the image line. The occlusion problem

of the representation is only truly eliminated by a uniform distribution of sample points

along transformed model lines when there is a sample point [ ̄xi, y ̄i] for every pixel on a

transformed model line. However, we have found that placing a sample point at

approximately every 10th pixel (w = 10 in equation 5) along each transformed model line

is sufficient to solve this problem. Then, when a transformed model line l

0 is correctly

aligned with a possibly partially occluded image line l

00, we will have d (l0

, l00) ≤ w/rm.

Figure 6 illustrates how model and image lines are sampled in the process of generating the

points in equations 3 and 4.

The scale factors rθ and rm are chosen to normalize the contribution of the orientation and

position components to the distance measure. Given a model line l with neighborhood

radius r (l) that is mapped to an image line l

0

, the radius around l

0 in which lines

corresponding to neighbors of l are expected to be found is defined to be

r0 (l,l0)=(kl

0

k r (l)) / klk, which is just the neighborhood radius of l scaled by the same

amount that l is itself scaled by the mapping. Assume that a transformed model line and

an image line are represented by the points [θ1, x1, y1] and [θ2, x2, y2], respectively, as

described by equations 3 and 4. When the orientation of the lines differ by π/2 radians, we

want |θ1 − θ2| = 1; when the horizontal distance between the sample points equals the

neighborhood radius of the image line, we want |x1 − x2| = 1; when the vertical distance

13
Figure 6. Sampling the position of model and image lines. (Image line l is represented by its midpoint [xmid, ymid] and its orientation θ. Projected model line l

0 is represented by the points

{[ ̄xi, y ̄i], i = 1,...,Npts} and its orientation θ0

. When the pose of a model is accurate and

a model line and image line correspond, the midpoint of that image line will be close to

some sample point on the projected model line, and the orientation of the two lines will be

similar. This is true even when the image line is fragmented. In this example, [xmid, ymid]

is closest to [ ̄x7, y ̄7].)

between the sample points equals the neighborhood radius of the image line, we want

|y1 − y2| = 1. The value rθ = π/2 satisfies the first normalization constraint. However,

because image lines will have different neighborhood radii, depending on which model line

they correspond to, the later normalization constraints can not be satisfied by a constant

scale factor, but they are satisfied for model and image lines of average length by

rm =

¡P

l∈I klk

¢ ¡P

l∈M r (l)

¢

|I|P

l∈M klk . (6)

The terms in equation 6 that sum over model lines represent sums over all lines in all

models. This value for rm has worked well in practice.

Finally, for any transformed model line l

0

, to find the image line l

00 that minimizes d (l0

, l00) we

simply query the nearest neighbor data structure (generated with points from equation 3)

with all the points listed in equation 4 and then use the distance of the closest one. Because

the complexity of the nearest neighbor search is O (log n), the use of multiple points to

represent lines does not significantly slow down the algorithm.

6. Graduated Assignment for Lines

The final stage of the object recognition algorithm is to apply a pose refinement and

verification algorithm to the few “best” approximate poses. We use the graduated

assignment algorithm (11 ) for this purpose because it is efficient (O [mn] complexity for m

14
model lines and n image lines), robust to occlusion and clutter, and does not make binary

correspondence decisions until a locally optimal pose is found.

Given an approximate initial pose T0 = {A0, t0}, we wish to find a 2-D affine

transformation T = {A, t} that maximizes the number of matches between model and

image lines so that the distance between matched lines does not exceed a threshold δfinal.

For a transformation T and a line l, let us denote by T (l) the transformation of l by T. We

assume that our initial pose T0 is accurate enough so that the pose refinement algorithm

does not have to consider all possible correspondences between model lines l and image

lines l

0 but only those correspondences where d (T (l), l0

) ≤ δ0; here, d () is the distance

function defined in section 5 and δ0 is an initial distance threshold that allows any

reasonably close correspondence. Limiting the correspondences in this way results in a

significant increase in the speed of this step without affecting the final outcome. Let

I0 = {l

0 ∈ I | ∃l ∈ M ∧ d (T0 (l), l0

) ≤ δ0} be the subset of image lines that are initially

reasonably close to any transformed model line.

Given m model lines M = {lj , j = 1,...,m}, n image lines I0 = {l

0

k, k = 1,...,n}, and an

approximate model pose T0 = {A0, t0}, we wish to find the 2-D affine transformation T and

the (m + 1) × (n + 1) match matrix M that minimizes the objective function

E = Xm

j=1

Xn

k=1

Mjk 3

d (T (lj ), l0

k)

2 − δ2

 ́

. (7)

M defines the correspondences between model lines and image lines; it has one row for

each of the m model lines and one column for each of the n image lines. This matrix must

satisfy the constraint that each model line match at most one image line and vice versa.

By adding an extra row and column to M, slack row m + 1 and slack column n + 1, these

constraints can be expressed as Mjk ∈ {0, 1} for 1 ≤ j ≤ m + 1 and 1 ≤ k ≤ n + 1,

Pn+1

i=1 Mji = 1 for 1 ≤ j ≤ m, and Pm+1i=1 Mik = 1 for 1 ≤ k ≤ n. A value of 1 in the slack

column n + 1 at row j indicates that the jth model line does not match any image line. A

value of 1 in the slack row m + 1 at column k indicates that the kth image line does not

match any model line. The objective function E in equation 7 is minimized by maximizing

the number of correspondences lj ↔ l

0

k where d (T (lj ), l0k) < δfinal.

Optimizing the objective function in equation 7 as a function of M and T is difficult

because it requires a minimization subject to the constraint that the match matrix be a

zero-one matrix whose rows and columns each sum to one. A typical nonlinear constrained

optimization problem minimizes an objective function on a feasible region that is defined

by equality and inequality constraints. The zero-one constraint on the match matrix is

impossible to express with equality and inequality constraints. The graduated assignment

algorithm developed by Gold and Rangarajan (10,11 ) can efficiently optimize our objective

function subject to these constraints. This algorithm uses deterministic annealing to

15
convert a discrete problem (for a binary match matrix) into a continuous one that is

indexed by the control parameter β. The parameter β (β > 0) determines the uncertainty

of the match matrix, and thus the amount of smoothing implicitly applied to the objective

function. The match matrix minimizing the objective function is tracked as this control

parameter is slowly adjusted to force the continuous match matrix closer and closer to a

binary match matrix. This has two advantages. First, it allows solutions to the simpler

continuous problem to slowly transform into a solution to the discrete problem. Secondly,

many local minima are avoided if an objective function is minimized which is highly

smoothed during the early phases of the optimization but gradually transforms into the

original objective function and constraints at the end of the optimization.

We minimize the objective function by first computing the variables Mjk that minimize E,

assuming that the transformation T is fixed, and then computing the transformation T

that minimizes E, assuming that the Mjk are fixed. This process is repeated until these

estimates converge. For a fixed transformation T, the continuous match matrix M is

initialized by

M0

jk =

1⁄2 1 if j = m + 1 or k = n + 1

exp ¡−β

¡

d (T (lj ), l0

k)

2 − δ2

¢¢ otherwise, (8)

where δ varies between δ0 at the start of the optimization and δfinal at the end. Note that δ

determines how distant two lines can be before the correspondence becomes undesirable:

M0

jk < 1 when d (T (lj ), l0k)

2 > δ2,

M0

jk = 1 when d (T (lj ), l0k)

2 = δ2,

M0

jk > 1 when d (T (lj ), l0k)

2 < δ2.

So, for example, when d (T (lj ), l0

k)

2 > δ2, M0

jk will be given a value less than the initial

slack values of 1 for row j and column k, thus initially making assignment to slack

preferred over the assignment of model line j to image line k. Next, we enforce the match

constraints by applying to M0 the Sinkhorn algorithm (21 ) of repeated row and column

normalizations:

repeat

Mi+1

jk = Mi

jk/Σn+1

s=1Mi

js, 1 ≤ j ≤ m, 1 ≤ k ≤ n + 1.

Mi+1

jk = Mi+1jk /Σm+1

s=1 Mi

sk, 1 ≤ j ≤ m + 1, 1 ≤ k ≤ n.

until °

°Mi+1 − Mi

°

° small

Sinkhorn showed that when each row and column of a square matrix is normalized several

times by the sum of the elements of that row or column, respectively (alternating between

row and column normalizations), the resulting matrix converges to one that has positive

16
elements with all rows and columns summing to 1, in other words, a probability

distribution. However, this is only approximate for a non-square matrix such as ours: the

rows or the columns will sum to one, but both will not. When β is small, all elements of

M0 will be close to the neutral value of 1; this represents a high degree of uncertainty in

the correspondences. As β increases (and presumably the accuracy of the pose as well), the

uncertainty in the correspondences decreases and the elements of M0 move toward the

values of 0 or ∞. Thus, the match matrix approximates a continuous probability

distribution when β is small, and ends as a binary correspondence matrix when β is large.

Appendix B describes changes that we have made in the Sinkhorn algorithm that often

result in improved convergence of the graduated assignment algorithm to the local optima.

We also need to compute the affine transformation T that minimizes the objective function

E, assuming that the continuous valued match matrix M is held constant. This is difficult

to do directly because of the complex nonlinear relation between T and the nearest

neighbor distance function d. Instead, we replace d with a new distance, d0

, whose square is

the sum of the squared distances of the end points of an image line to the infinitely

extended model line. For a model line lj and an image line l

0

k, the new squared distance

between T (lj ) and l

0

k is

d0(T (lj ), l0

k)

2 =

h

T (nj )

T (p0

k1 − T (pj1))i2

+

h

T (nj )

T (p0

k2 − T (pj1))i2

where p0

k1 and p0k2 are the two end points of l

0

k and where T (nj ) , T (pj1), and T (pj2)

denote the normal and two end points of T (lj ), respectively. The new objective function is

E0 = Xm

j=1

Xn

k=1

Mjk 3

d0

(T (lj ), l0

k)

2 − δ2

 ́

.

In general, the transformation T that minimizes E0 is not guaranteed to minimize E. In

practice, however, because three line correspondences define a 2-D affine transformation,

one would expect E and E0 to have approximately the same minimizers whenever the

model has three or more lines in a non-degenerate configuration. Since the expression for

d0 (T (lj ), l0

k)

2 involves rotating a vector and transforming a point, it is actually easier to

reverse the roles of lj and l

0

k and minimize E0 by computing the inverse transformation

T0 = {A0

, t0} that maps image lines into the frame of reference of the model. This way, the

model normal vectors are constants and T0 is applied only to image points. Then, T is

computed as the inverse of T0

. The objective function that is minimized to determine T0 is

E00 = Xm

j=1

Xn

k=1

MjkX

2

i=1

3¡

nT

j (A0

p0

ki + t0 − pj1)

¢2 − δ2

 ́

(9)

17
where nj = £

xnj , ynj

¤

is the unit normal vector of model line lj , pj1 = [xj1, yj1] is one end

point of model line lj , and p0

ki = [x0ki, y0ki] is the ith end point (i = 1, 2) of image line l

0

k. We

can find the transformation

T0 = {A0

, t0} =

1⁄2∙ a0 b0

c0 d0

 ̧

,

∙ t

0

x

t

0

y

 ̧3⁄4

that minimizes equation 9 by solving the system of six equations

∂E00/∂a0 = 0, ∂E00/∂b0 = 0, ∂E00/∂c0 = 0,

∂E00/∂d0 = 0, ∂E00/∂t

0

x = 0, ∂E00/∂t

0

y = 0 (10)

for a0

, b0, c0, d0, t

0

x, and t

0

y. The solution to this system of equations is given in appendix C.

Figure 7 compares the values of E and E0 over a typical application of the graduated

assignment algorithm. Pseudocode for the pose refinement and verification algorithm is

shown in figure 8. Figure 9 shows an example of how graduated assignment transforms an

initial approximate pose into a more accurate pose.

0 5 10 15 20 25 30

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Step number

E

Figure 7. Comparison of the two objective functions for a typical minimization by the graduated

assignment algorithm. (The solid line is E, which uses the Euclidean distances to the

nearest neighbor, and the dotted line is E0

, which uses the sum of the distances of the image

line endpoints to the infinitely extended model lines. The values of E and E0 generally

decrease during the optimization process, but they can also rise because of changes in the

assignment variables Mjk.)

18
initialize: T = T0, β = β0, δ = δ0, 2 = ∞, k = 0, maxsteps

= 30.

while k ¡ maxsteps and 2>2halt, do

Initialize M0 according to Equation 8.

Apply Sinkhorn’s algorithm to M0 to produce M.

Compute T0

k via Equation 10.

Compute Tk as the inverse of T0

k.

2 = max |Tk − Tk−1|.

k = k + 1.

δ = δ − (δfinal − δ0) /maxsteps.

β = βupdate × β.

end while

Figure 8. The pose refinement algorithm.

Figure 9. Pose refinement using the graduated assignment algorithm: initial pose (left) and final pose

after applying the algorithm (right).

7. Experiments

To validate our approach, we recognized partially occluded 2-D and 3-D objects in

cluttered environments under a wide variety of viewpoints. All images were acquired at a

resolution of 800 × 600 pixels; 400 to 800 lines were typically detected in an image, and

each model had between 20 and 80 lines. First, we used books to test the recognition of

planar objects. Figure 10 illustrates recognition results when our algorithm is applied to an

image of a pile of books. For all but one of the five recognized books, the pose hypothesis

leading to correct recognition was found in the top 10 hypotheses of the sorted hypothesis

list. One book (“Linux,” shown in the lower right of figure 10a) was not found until the

24th pose hypothesis. This book might be more difficult for our approach to recognize

because a large part of its cover depicts a horse with curved borders, for which detected

lines were inconsistent in images acquired from different viewpoints.

19
(a) Models of books (b) Test image

(c) 731 detected lines (d) Recognized books

Figure 10. Five books, some partially occluded, are recognized in a cluttered environment.

The performance of our algorithm depends on how reliably it can move those pose

hypotheses associated with correct correspondences to the top of the sorted hypothesis list.

To evaluate this, we estimate Pθ (k), the probability that one of the first k sorted pose

hypotheses for a model leads to a correct recognition when the viewpoint of the recognized

object and the viewpoint used to generate its model differ by an angle of θ, assuming that

an instance of the model does appear in the image. Knowing Pθ (k) allows one to

determine how many pose hypotheses should be examined by the pose refinement process

before restarting with a new model, either of a new object or of the same object but from a

different viewpoint. Because Pθ (k) is highly dependent on the amount and type of clutter

and occlusion in an image and because the level of clutter and occlusion present in our test

was held fixed, Pθ (k) should be interpreted loosely. The six books shown in figure 10a were

used to perform this experiment. All six books were placed flat on a table along with a

number of other objects for clutter. Each book in turn was moved to the center of the

table and then rotated on the plane of the table to eight different orientations, where each

orientation was separated by approximately 45 degrees. For each of these orientations, the

camera was positioned at angles 0, 10, 20, 30, 40, 50, 60, and 70 degrees relative to the

normal of the table (0 degree is directly overhead) and at a fixed distance from the center

book, and then an image was acquired. The center books were unoccluded in these

experiments. A separate image was also acquired of each book in an arbitrary orientation

with the camera in the 0-degree position; these latter images were used to generate the

book models. Figure 11 shows an image of the books on this table for the camera in the

20
Figure 11. Image of a table of books taken by a camera tilted 50 degrees from vertical.

50-degree position. We then applied our algorithm to each model and image pair and

determined the position in the sorted hypothesis list of the first hypothesis that allowed the

object to be recognized. As many as 100 hypotheses were examined for each model and

image pair. The estimated values of Pθ (k) are shown in figure 12. From this we see that

for planar objects whose orientations differ by as much as 60 degrees from the modeled

orientation, a probability of correct recognition of 0.8 can be achieved if we examine the

first 30 pose hypotheses. By examining just the top four pose hypotheses, we can achieve a

probability of correct recognition of 1.0 for objects whose orientations differ by as much as

40 degrees from the modeled orientations. Thus, a good strategy would be to apply the

algorithm with a set of models for each object generated for every 40-degree change in

viewpoint; in this case, it would be sufficient to represent planar objects by five models in

order to recognize all orientations of up to 80 degrees from the normal.

Finally, we applied our algorithm to three 3-D objects. We acquired 17 images of each

object, where the objects were rotated by 2.5 degrees between successive images. The first

image of each object was used to represent the object, and from this, we generated a 2-D

model by identifying the object edges in that image. With only the top 10 sorted pose

hypotheses examined, all three objects were successfully recognized from all viewpoints

that differed by as much as 25 degrees from the modeled viewpoint. Two of the objects

(the monitor and hole punch) were also recognized at 30 degrees away from the modeled

viewpoints. Figure 13 shows the object models, the images, the detected lines, and the

final poses of the recognized objects for the most distant viewpoints from which each was

21
20 40 60 80 100

0.4

0.5

0.6

0.7

0.8

0.9

1

k

Pθ (k)

θ = 60°

θ = 50°

θ = 0°, 10°, 20°, 30°, 40°

Figure 12. Pθ (k) is the probability that one of the first k sorted pose hypotheses for a model leads to

a correct recognition for that model. (θ is the difference in viewpoint elevation between the

model and the object. For θ ≤ 40◦, one of the four highest ranked pose hypotheses always

leads to correct recognition. The curves for θ = 0 through 40 degrees are superposed for

k ≥ 4.)

Figure 13. Recognition of 3-D objects from viewpoint-dependent 2-D models: computer monitor (top

row), stapler (middle row), and hole punch (bottom row). (Shown in each row, from left to

right, is the 2-D object model, original image, image lines, and model of recognized object

overlaid on the original image. The modeled view of each object differs from the test view

by 20 to 30 degrees.)

22
recognized. The range of recognizable object orientations could have been be extended

somewhat if more pose hypotheses has been examined, but at some point, it becomes more

cost effective to add a new model for a different viewpoint.

The minimum number of 2-D models needed to represent a 2-D or 3-D object can be

determined from the maximum difference between the object’s orientation and a modeled

orientation that still allows the object to be recognized from that 2-D model. Let this

maximum difference between object and model orientation be denoted by Θ. To be

conservative, based on results described , we take Θ = 40 degrees for 2-D objects, and Θ =

20 degrees for 3-D objects. We then determine the minimum number of 2-D models needed

to represent an object by counting the number of identical right-circular cones of angle Θ

that are needed to fully enclose the upper hemisphere (for the case of 2-D objects) or the

entire sphere (for the case of 3-D objects) when the vertices of the cones are placed at the

sphere’s center. (The angle of a right circular cone is the angle around the vertex of the

cone between the cone’s axis and the conic surface.) One can determine that six cones of

angle 40 degrees fully enclose the upper hemisphere while 44 cones of angle 20 degrees fully

enclose the entire sphere. Thus, recognizing 2-D objects from any viewpoint above the

plane of the object requires at most six 2-D models, while recognizing 3-D objects from any

viewpoint (above or below the ground plane) requires at most 44 2-D models.

From these experiments, it is apparent that only a small number of pose hypotheses need

to be examined by the pose refinement algorithm in order to reliably recognize objects. We

use this to determine the overall run time complexity of our algorithm. Assume that we

have q models, each containing m lines, and that the image contains n lines. Initialization

of the nearest neighbor data structure and identification of corners can be performed in

O (n log n) time. For each model, we generate O (mn) pose hypotheses. The neighborhood

similarity of each of these can be evaluated in O (log n) time. The pose hypotheses can be

sorted in time O (mn log (mn)). The pose refinement algorithm requires O (mn) time.

Thus, the overall run time complexity of our algorithm is O (qmn log (mn)).

8. Conclusions

We have presented an efficient approach to recognizing partially occluded objects in

cluttered environments. Our approach improves on previous approaches by employing

information available in one or two line correspondences to compute approximate object

poses. Only a few model lines need to be unfragmented in an image in order for our

approach to be successful; this condition is easily satisfied in most environments. The use

of one or two line correspondences to compute an objects pose allows for a large reduction

in the dimensionality of the space that must be searched in order to find a correct pose. We

23
then developed an efficiently computed measure of the similarity of two line neighborhoods

that is largely unaffected by clutter and occlusion. This provides a way to sort the

approximate model poses so that only a small number need to be examined by more

time-consuming algorithms. Experiments show that a single view of an object is sufficient

to build a model that will allow recognition of that object over a wide range of viewpoints.

24
A. Line Detection

Line segments in models are matched to line segments in images. Each line segment in a

model or image is represented by its two end points. Generation of model lines may be

performed manually by the user or automatically by the application of image processing to

images of the objects to be recognized. We currently use publicly available software (14 ) to

automatically locate model and image lines. Briefly, this software operates as follows. The

Canny edge detector is first applied. Next, contiguous edge pixels are linked together into

contours and very short contours are discarded. Each contour into line segments by

breaking the contour at edge pixels until no edge pixel is more than a specified distance

from the line connecting the two end points of its subcontour; this is done by finding the

longest subcontour (starting at the first edge point) whose maximum distance from the line

connecting the end points of the subcontour is less than a threshold. This subcontour is

replaced by the line segment, and then the process is repeated for the remainder of the

contour.

In our experience, for images with dense edges, this approach to line detection performs

better than the Hough Transform approach (8 ). The high connectivity of the edges

produced by the Canny edge detector greatly simplifies the process of fitting lines to those

contours when the contour partitioning approach is used. Line fitting with the Hough

Transform, on the other hand, is easily confounded by spurious peaks generated by

coincidental alignment of physically separated edge points (12 ).

A requirement of our approach, as stated in section 1, is to detect at least one

unfragmented image line segment. An evaluation of the accuracy of our line detector shows

that this requirement is easily satisfied for the types of scenes described in this report.

Using six different images of books and office objects (as typified by images shown

throughout this paper), we manually measured the length of 250 projected model lines and

the lengths of the corresponding automatically detected line segments. All model edges

that were partially or fully visible were measured. If a visible model edge was not detected

by our software, then the “corresponding line segment” was assigned a length of zero. For

each model edge, the relative error in the length of the corresponding detected line segment

is calculated as |(lm − li) /lm| where lm is the length of the projected model line and li is

the length of the detected line segment. Figure A.1 shows a plot of the relative error versus

the fraction of the 250 model lines that are detected with relative error no greater than

that amount. One can see that 11% of all partially and fully visible model lines are

detected in the images with less than one pixel error in the positions of their end points.

Furthermore, 35% of all model lines are detected as image segments where the sum of the

errors in the endpoint positions is no more than 5% of the length of the corresponding

projected model lines; that is, 35% of the visible model lines are detected with relative

25
error in length that is less than 5%. We find that 5% relative error is small enough to

obtain a good coarse pose hypothesis, and that with 35% of the model lines having relative

errors no larger than this, there will be many such good hypotheses that will allow the pose

refinement stage of the algorithm to recognize an object.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Maximum Relative Error

Fraction of Lines

Figure A.1. The accuracy of our line detector is depicted in this graph, which plots the relative error

versus the fraction of the model lines detected with relative error no greater than that

amount.

26
B. Modifications of the Sinkhorn Algorithm

Sinkhorn’s original algorithm (21 ) treats all rows and columns identically. The modified

Sinkhorn algorithm discussed in section 6 must treat the slack row and column differently

from other rows and columns: the slack values are not normalized with respect to other

slack values, only with respect to the nonslack values. This is necessary in order to allow

multiple image lines to be identified as clutter and to allow multiple model lines to be

identified as occluded. A problem with this modified algorithm is the following. Suppose

that a nonslack value is a maximum in both its row and column. After that row is

normalized, it is possible that this previously maximal value is now less than the slack

value for that column. The same sort of thing can happen when columns are normalized.

Intuitively, this behavior is undesirable: nonslack values that begin maximal in both their

row and column should remain maximal in their row and column throughout the Sinkhorn

iteration. The purpose of Sinkhorn normalization is not to shift assignment weights around

but only to normalize the assignments so that they approximate a probability distribution.

A secondary problem with the Sinkhorn algorithm is that the order of normalization (row

first or column first) can have a significant effect on the final normalization, especially

when there is potential for “weight shifting” as describe before.

To minimize weight shifting, after performing row normalizations we set, the values in the

slack row so that their ratio to the nonslack value in each column, which was previously

maximum, is the same as this ratio before row normalization. A similar thing is done after

column normalizations. In addition, to eliminate the effect of normalization order, rows

and columns are normalized independently on each step of the iteration and then the two

normalized matrices are combined into one. The pseudocode for this new Sinkhorn

algorithm is shown in figure B.1.

27
i = 0

R =

n3r, c,

M0

r,n+1

M0

rc

,

M0

m+1,c

M0

rc  ́

| M0

rc > M0jc and M0rc > M0

rk for all j 6= r and k 6= c

o

repeat

M0

jk = Mijk/Σn+1

s=1Mi

js, 1 ≤ j ≤ m, 1 ≤ k ≤ n + 1. // Normalize rows

for each (r, c, λ, μ) ∈ R // Adjust slack row

M0

m+1,c = μM0rc

end for

M00

jk = Mijk/Σm+1

s=1 Mi

sk, 1 ≤ j ≤ m + 1, 1 ≤ k ≤ n. // Normalize columns

for each (r, c, λ, μ) ∈ R // Adjust slack column

M00

r,n+1 = λM00rc

end for

i = i + 1

Mi

jk =

3

M0

jk + M00jk ́

/2, 1 ≤ j ≤ m + 1, 1 ≤ k ≤ n + 1

until °

°Mi − Mi−1

°

° small

Figure B.1. The new Sinkhorn algorithm.

28
C. Solving for the Affine Transformation

We obtain the affine transformation that minimizes equation 9 by solving the system given

in equation 10. Expanding equation 10, we obtain the linear system Ax = b where

x = ¡a0 b0 c0 d0 t

0

x t

0

y

¢T

, A is the 6 × 6 symmetric matrix

A = Xm

j=1

Xn

k=1

Mjk

⎛

⎜⎜⎜⎜⎜⎜⎜⎝

x2

nj (x02

k1 + x02k2) x2

nj (x0

k1y0k1 + x0k2y0k2) xnj ynj (x02k1 + x02k2)

x2

nj (x0

k1y0k1 + x0k2y0k2) x2

nj (y02

k1 + y02k2) xnj ynj (x0k1y0k1 + x0k2y0k2)

xnj ynj (x02

k1 + x02k2) xnj ynj (x0k1y0k1 + x0k2y0k2) y2

nj (x02

k1 + x02k2)

xnj ynj (x0

k1y0k1 + x0k2y0k2) xnj ynj (y02k1 + y02k2) y2

nj (x0

k1y0k1 + x0k2y0k2)

x2

nj (x0

k1 + x0k2) x2

nj (y0

k1 + y0k2) xnj ynj (x0k1 + x0k2)

xnj ynj (x0

k1 + x0k2) xnj ynj (y0k1 + y0k2) y2

nj (x0

k1 + x0k2)

···

xnj ynj (x0

k1y0k1 + x0k2y0k2) x2

nj (x0

k1 + x0k2) xnj ynj (x0k1 + x0k2)

xnj ynj (y02

k1 + y02k2) x2

nj (y0

k1 + y0k2) xnj ynj (y0k1 + y0k2)

y2

nj (x0

k1y0k1 + x0k2y0k2) xnj ynj (x0k1 + x0k2) y2

nj (x0

k1 + x0k2)

y2

nj (y02

k1 + y02k2) xnj ynj (y0k1 + y0k2) y2

nj (y0

k1 + y0k2)

xnj ynj (y0

k1 + y0k2) 2x02

nj

2x0

nj y0nj

y2

nj (y0

k1 + y0k2) 2x0

nj y0nj

2y02

nj

⎞

⎟⎟⎟⎟⎟⎟⎟⎠

,

and b is the column 6-vector given by

b = Xm

j=1

Xn

k=1

Mjk ¡xnjxj1 + ynj yj1

¢

⎛

⎜⎜⎜⎜⎜⎜⎝

xnj (x0

k1 + x0k2)

xnj (y0

k1 + y0k2)

ynj (x0

k1 + x0k2)

ynj (y0

k1 + y0k2)

2xnj

2ynj

⎞

⎟⎟⎟⎟⎟⎟⎠

.

The unknown x is easily found via standard linear methods.

29
References

[1] Ayache, N.; Faugeras, O. D. HYPER: A New Approach for the Recognition and

Positioning of Two-Dimensional Objects. IEEE Trans. on Pattern Analysis and

Machine Intelligence January 1986, 8 (1), 44—54.

[2] Baird, H. S. Model-Based Image Matching Using Location; MIT Press: Cambridge,

MA, 1985.

[3] Beveridge, J. R.; Riseman, E. M. Optimal Geometric Model Matching Under Full 3D

Perspective. Computer Vision and Image Understanding May 1995, 61 (3), 351—364.

[4] Carmichael, O.; Hebert, M. Shape-Based Recognition of Wiry Objects. IEEE Trans.

on Pattern Analysis and Machine Intelligence December 2004, 26 (12), 1537—1552.

[5] David, P.; DeMenthon, D.; Duraiswami, R.; Samet, H. Simultaneous Pose and

Correspondence Determination using Line Features. Proc. IEEE Conf. on Computer

Vision and Pattern Recognition June 2003, 2, II-424—II-431.

[6] David, P.; DeMenthon, D.; Duraiswami, R.; Samet, H. SoftPOSIT: Simultaneous Pose

and Correspondence Determination. Int. Journal of Computer Vision 2004, 49 (3),

259—284.

[7] Denton, J.; Beveridge, J. R. Two Dimensional Projective Point Matching. 5th IEEE

Southwest Symposium on Image Analysis and Interpretation April 2002, 77—81.

[8] Duda, R. O.; Hart, P. E. Use of the Hough Transform To Detect Lines and Curves in

Pictures. Communications of the ACM 1972, 15 (1), 11—15.

[9] Fischler, M. A.; Bolles, R. C. Random Sample Consensus: A Paradigm for Model

Fitting with Applications to Image Analysis and Automated Cartography. Comm.

Association for Computing Machinery June 1981, 24 (6), 381—395.

[10] Gold, S.; Rangarajan, A. A Graduated Assignment Algorithm for Graph Matching.

IEEE Trans. on Pattern Analysis and Machine Intelligence 1996, 18 (4), 377—388.

[11] Gold, S.; Rangarajan, A.; Lu, C. P.; Pappu, S.; Mjolsness, E. New Algorithms for 2D

and 3D Point Matching: Pose Estimation and Correspondence. Pattern Recognition

August 1998, 31 (8), 1019—1031.

[12] Grimson, W.E.L.; Huttenlocher, D. P. On the Sensitivity of the Hough Transform for

Object Recognition. IEEE Trans. on Pattern Analysis and Machine Intelligence 1990,

12 (3), 255—274.

30
[13] Harris, C. G.; Stephens, M. J. A Combined Corner and Edge Detector. Proc. Fourth

Harris Alvey Vision Conference, Manchester, 147—151, 1988.

[14] Kovesi, P. D. MATLAB Functions for Computer Vision and Image Analysis. School of

Computer Science & Software Engineering, The University of Western Australia.

Available from: ¡http://www.csse.uwa.edu.au/ ̃pk/research/matlabfns/¿.

[15] Lamdan, Y.; Wolfson, H. J. Geometric Hashing: A General And Efficient Model-Based

Recognition Scheme. Proc. 2nd Intl. Conf. on Computer Vision, 238—249, 1988.

[16] Lowe, D. G. Distinctive Image Features from Scale-Invariant Keypoints. Int. Journal

of Computer Vision 2004, 60 (2), 91—110.

[17] Merkwirth, C.; Parlitz, U.; Wedekind, I.; Lauterborn, W. TSTOOL User Manual.

University of Gttingen, http://www.physik3.gwdg.de/tstool/index.html.

[18] Mikolajczyk, K.; Zisserman, A.; Schmid, C. Shape Recognition with Edge-Based

Features. Proc. British Machine Vision Conference, September 2003.

[19] Roberts, L. Machine Perception of Three-Dimensional Solids. Optical and

Electrooptical Information Processing, J. T. Tipett, Ed., M.I.T. Press, Cambridge,

MA, 159—197, 1965.

[20] Schmid, C.; Mohr, R. Local Grayvalue Invariants for Image Retrieval. IEEE Trans. on

Pattern Analysis and Machine Intelligence May 1997, 19 (5), 530—535.

[21] Sinkhorn, R. A Relationship between Arbitrary Positive Matrices and Doubly

Stochastic Matrices. Annals Mathematical Statistics 1964, 35 (2), 876—879.

[22] Ullman, S. Aligning Pictorial Descriptions: An Approach to Object Recognition.

Cognition 1989, 32 (3), 193—254.

[23] Whitley, D.; Beveridge, J. R.; Guerra-Salcedo, C.; Graves, C. Messy Genetic

Algorithms for Subset Feature Selection. Proc. of the Seventh Intl. Conf. on Genetic

Algorithms, 1997.

31
32 

Distribution List

ADMNSTR 

DEFNS TECHL INFO CTR 

ATTN DTIC-OCP (ELECTRONIC COPY) 

8725 JOHN J KINGMAN RD STE 0944 

FT BELVOIR VA 22060-6218 

DARPA 

ATTN IXO S WELBY 

3701 N FAIRFAX DR 

ARLINGTON VA 22203-1714 

OFC OF THE SECY OF DEFNS 

ATTN ODDRE (R&AT) 

THE PENTAGON 

WASHINGTON DC 20301-3080 

US ARMY RSRCH DEV AND ENGRG CMND 

ARMAMENT RSRCH DEV AND ENGRG 

CNTR 

ARMAMENT ENGRG AND TECHNLTY CTR 

ATTN AMSRD-AAR-AEF-T J MATTS 

BLDG 305 

ABERDEEN PROVING GROUND MD 21005-

5001 

US ARMY TRADOC 

BATTLE LAB INTEGRATION & TECHL 

DIRCTRT 

ATTN ATCD-B 

10 WHISTLER LANE 

FT MONROE VA 23651-5850 

PM TIMS, PROFILER (MMS-P) AN/TMQ-52 

ATTN B GRIFFIES 

BUILDING 563 

FT MONMOUTH NJ 07703 

SMC/GPA 

2420 VELA WAY STE 1866 

EL SEGUNDO CA 90245-4659 

COMMANDING GENERAL 

US ARMY AVN & MIS CMND 

ATTN AMSAM-RD W C MCCORKLE 

REDSTONE ARSENAL AL 35898-5000 

US ARMY INFO SYS ENGRG CMND 

ATTN AMSEL-IE-TD F JENIA 

FT HUACHUCA AZ 85613-5300 

US ARMY SIMULATION TRAIN & 

INSTRMNTN CMND 

ATTN AMSTI-CG M MACEDONIA 

12350 RESEARCH PARKWAY 

ORLANDO FL 32826-3726 

US GOVERNMENT PRINT OFF 

DEPOSITORY RECEIVING SECTION 

ATTN MAIL STOP IDAD J TATE 

732 NORTH CAPITOL ST., NW 

WASHINGTON DC 20402 

UNIVERSITY OF MARYLAND INSTITUTE 

FOR ADVANCED COMPUTER STUDIES 

ATTN D DEMENTHON (5 COPIES) 

A V WILLIAMS BLDG 

COLLEGE PARK MD 20742-3275 

US ARMY RSRCH LAB 

ATTN AMSRD-ARL-CI-OK-TP 

 TECHL LIB T LANDFRIED (2 COPIES) 

BLDG 4600 

ABERDEEN PROVING GROUND MD 21005-

5066 

DIRECTOR 

US ARMY RSRCH LAB 

ATTN AMSRD-ARL-RO-EV W D BACH 

PO BOX 12211 

RESEARCH TRIANGLE PARK NC 27709 

US ARMY RSRCH LAB 

ATTN AMSRD-ARL-D J M MILLER 

ATTN AMSRD-ARL-CI-CB 

 P DAVID (5 COPIES) 

ATTN AMSRD-ARL-CI-OK-T 

 TECHL PUB (2 COPIES) 

ATTN AMSRD-ARL-CI-OK-TL 

 TECHL LIB (2 COPIES) 

ATTN IMNE-ALC-IMS 

 MAIL & RECORDS MGMT 

ADELPHI MD 20783-1197