ce of 
ond 
; the 
and- 
ly, we 
gular 
| and 
d ex- 
men- 
rown, 
parse 
orga- 
d un- 
amer 
lanar 
max- 
on in 
least- 
f the 
refine 
) find 
| and 
then 
only 
cribe 
rtain 
ks at 
on of 
from 
g the 
tion. 
mbi- 
scher 
stant 
neth- 
)Cess. 
| also 
ther. 
many 
also 
es to 
e The segmentation of edges performed individually in 
both images, does not necessarily produce correspond- 
ing breakpoints. Therefore, the identification of the 
same feature in both images becomes a nontrivial 
task. 
e Although straight lines in the object space are also 
straight lines in all projections, the converse does not 
hold. Circular arcs appear as elliptic arcs, which are 
more difficult to detect. 
To avoid these disadvantages we propose to segment the 
3-D curves in the object space. In the next section we 
present two methods for segmenting a 3-D curve into its 
basic primitives. 
2 METHODS 
Here we describe two methods suitable for segmenting 3-D 
curves. These methods are not necessarily the best curve 
segmentation methods known, rather they demonstrate the 
concept of segmentation in 3-D space. The first method is 
a 3-D version of a split-and-merge concept, based on the 
offset from a straight line. In this method, the curve is 
segmented into straight lines only. The second method is 
an extension of the % — s concept (see Li and Schenk, 1991 
for a 2-D description) into 3-D. With this method, straight 
lines and circular arcs are detected. 
The input for both methods are lists of densely spaced 
points of 3-D edges. It should be noted that the points 
are not evenly spaced. They are represented by real 3-D 
coordinates. We are presently investigating another repre- 
sentation, where the edge points are resampled into a 3-D 
discrete space (voxels). 
2.1 Split-and-merge method 
As the name indicates, the split-and-merge method consists 
of the two phases split and merge. In the split phase, the 
input data is segmented to assure that each segment fulfills 
a certain condition. In our case, the condition is that all 
the points contained in a segment are likely to correspond 
to a straight line. In the merge phase, redundant break- 
points that have been produced during the split phase are 
eliminated. 
The criterion for deciding whether a group of small line 
fragments can be represented as a longer straight line is 
the maximum offset. We have chosen the maximum offset 
and not a least-squares criterion as suggested in (Pavlidis 
and Horowitz, 1974). The reason is that the computational 
cost for applying the least-squares criterion is much higher 
than the one for the maximum offset, especially in the 3-D 
case. In addition, we only perform one split and one merge 
phase because the initial segmentation criterion is strong. A 
refinement of the breakpoints and a fitting of a straight line 
to a list of points can be performed once the segmentation 
has been achieved. In general, the offset criterion is superior 
to other criteria, since it is not very noise sensitive. Other 
criteria, such as the orientation of a line, are quite sensitive 
to noise, as we will see in the next section. 
Let us now define the maximum offset criterion. Con- 
sider a string of n small line fragments I; ...1, which are 
formed by a corresponding set of densely spaced points 
Do... Pa. This string of fragments can be considered as one 
longer straight line if the distance from each point p; . . . pn_1 
523 
  
  
  
Figure 1: Splitting a curve according to the maximum offset 
criterion 
to the straight line connecting po and p, does not exceed a 
predefined threshold value. 
The following pseudo code describes the split phase 
of the split-and-merge method. It processes an edge 
E=({pı...Pn} or a part of it. The input to the function 
in the first call is the indices 1 and n of the first and last 
points of the edge. The function works recursively, and in 
general its input is the indices of the first and last points 
of a sub-edge. The set s (which is a global parameter) is 
initialized to contain the numbers 1 and n. 
Split( f, 1) 
I. m= —1 
2. Vi, JS SES 
2.1 o := the offset of point p; from the line DP 
2.2 ifo » m then m :— o; t:— i 
3. if m > MAXOFFSET 
then s :— sU (t); Split(f, t); Split(t,1) 
Once the above algorithm terminates, s contains an 
unsorted list of indices of the potential breakpoints. The 
merge algorithm, as specified in the following pseudo code, 
attempts to merge two neighboring segments, according to 
the same maximum offset criterion described earlier. 
Merge() 
1. Sort the s list by ascending order 
2. k:= the number of breakpoints in s 
3. Vi, 2<1<k—1 
3.1 o := the offset of point p,; from the line 
Pafi-1]Psfi+1] 
3.2 if 0 > MAXOFFSET 
then s:=s— {s[i]}; k: =k — 1 
Figure 1 demonstrates a 2-D curve splitting. The 3-D 
case is similar, except for the calculation of the offsets. 
These are calculated in a 3-D coordinate system. 
Another aspect is the analysis of the segmented line. 
Although the split-and-merge method aims at segmenting 
straight lines, some lines cannot be classified, be it because 
of noise, short segments or simply because no straight line 
segments are present.