SEGMENTATION OF EDGES IN 3-D OBJECT SPACE 
Amnon Krupnik 
Toni Schenk 
Department of Geodetic Science and Surveying 
The Ohio State University, Columbus, Ohio 43210-1247 
Commission III 
ABSTRACT 
In our feature-based matching approach, zero-crossings are matched and represented in 3-D object space by a sequence of 
densely spaced points. These spatial curves form the basis for reconstructing the surface. Since edges are likely to correspond 
to object boundaries, the 3-D curves also serve as an important input for object recognition. In this paper we address the 
problem of segmenting the contours in straight lines and regular curves. We compare different methods, such as split-and- 
merge and a 3-D version of the y — S method. 
KEY WORDS: Edge Segmentation, Curve Decomposition, 3-D, Image Matching, Feature Extraction 
1 INTRODUCTION 
One of the goals of digital photogrammetry is to automat- 
ically recognize and extract man-made objects from aerial 
images. An essential step toward this goal is to extract 
features and to match them. We have adopted this ap- 
proach and described it in several papers, e.g., (Schenk, 
1989, Schenk et. al, 1991a, Zong et. al, 1991). A similar ap- 
proach is also accepted by the computer vision community 
(e.g., Grimson, 1985). 
The features detected in the images are discontinuities 
of gray values, or edges. In our current implementation, 
the images are convolved with the Laplacian of a Gaus- 
sian (LoG) operator (Marr and Hildreth, 1980). The re- 
sulting zero-crossings are the edges. In the automatic ori- 
entation module, which is the first stage of our system, the 
zero-crossings are matched for determining conjugate points 
(Schenk et. al, 1991b, Stefanidis et. al, 1991, Zong et. al, 
1991). Once the orientation parameters are established, 
the images are resampled to epipolar geometry (Cho et. al, 
1992). Now we begin to reconstruct surfaces where many 
edges are matched (Zong and Schenk, 1992), resulting lists 
of densely spaced points in object space (3-D edges) 
The feature-based matching approach offers two major 
advantages: 
e Surface discontinuities are most likely to show up as 
edges in the image. By detecting these edges, break- 
lines can be found and the surface reconstruction pro- 
cess (Schenk et. al, 1991a, Schenk and Toth, 1992) 
becomes more robust. 
e In many of the cases, edges correspond to object 
boundaries. Therefore, once the location of edges is 
known, they serve as building blocks for a symbolic 
description of the object space. Such descriptions can 
be matched with symbolic representations of “world” 
objects, stored in a library. 
In order to use the edges for the symbolic description of 
the object space, we must segment and group them. In this 
paper, we focus on the segmentation aspect. The goal is to 
decompose the 3-D curves into primitives which are more 
explicit than a list of densely spaced points. Specifically, we 
want to segment the 3-D curves into straight lines, regular 
curves (circular arcs in our current implementation) and 
natural lines. 
The curve segmentation problem has been addressed ex- 
tensively in computer vision literature. À popular segmen- 
tation method is the Hough transform (Ballard and Brown, 
1982). This method tries to find straight lines from a sparse 
set of points. In our application points are already orga- 
nized along edges; Thus, the Hough transform would un- 
necessarily increase the computational complexity. Ramer 
(1972) presents a simple algorithm to approximate planar 
curves by polygons. He based his approximation on a max- 
imum offset criterion. We have adopted this criterion in 
our approach. Pavlidis and Horowitz (1974) use a least- 
squares algorithm to fit straight lines to portions of the 
curve, and then iterate a split-merge procedure to refine 
the initial segmentation. Grimson and Pavlidis (1985) find 
the breakpoints of a curve by comparing the original and 
a smoothed version of the curve. Discontinuities are then 
easily detected, and regular curve fitting is performed only 
between discontinuities. Fischler and Bolles (1986) describe 
two methods, one of them passes a "stick" of a certain 
width and length over the curve, and the other looks at 
the curve from different “views” followed by a selection of 
breakpoints according to the maximum votes obtained from 
these views. Both methods are based on segmenting the 
curve over different scales, and on perceptual organization. 
Grimson (1989) suggests an approach which is a combi- 
nation of split-and-merge and y — s algorithms. Wuescher 
and Boyer (1991) describe an algorithm based on a constant 
curvature criterion. 
Except for the Hough transform, all the proposed meth- 
ods consider a plane curve as the input for the process. 
Grimson (1989) mentioned that the segmentation can also 
be performed in 3-D, but did not elaborate it any further. 
While curve segmentation in 2-D may be sufficient for many 
applications, it has some disadvantages: 
e Features which appear in one image only are also 
segmented, although they do not lend themselves to 
edges in the object space. 
522 
To ax 
3-D « 
prese 
basic 
Here - 
curve: 
segme 
conce 
a 3-D 
offset 
segme 
an ext 
for a : 
lines 2 
Tk 
points 
are nc 
coordi 
sentat 
discre! 
2.1 
As the 
of the 
input 
a cert: 
the po 
toas 
points 
elimin. 
Th 
fragme 
the m: 
and nc 
and Hc 
cost fo 
than t] 
case. I 
phase 1 
refinen 
to a lis 
has bee 
to othe 
criteria 
to nois: 
Let 
sider a 
formed 
Po..-P, 
longer :