C
m à 7 23.
nethod
Te seg-
own in
egmen-
orthog-
results
ere de-
-preted
ged. À
; corre-
tures.
ed ac-
tion of
it-and-
ne fact
physi-
1 value
ble for
ire ac-
The
) We
iterval
row at
PY —s
a 3-D
r arcs)
can be
d cor-
jise ef-
x
>.
i into
in the
Figure 9: Results of applying the y — s method to the
synthetic data: straight segments are represented by dashed
lines, circular arcs by solid lines, and noise effects are not
presented. The breakpoints are represented by squares.
spatial domain. For example, the second arc in the syn-
thetic example was detected as two smaller arcs and a noise
segment. In the spatial domain, these shorter arcs can be
combined into a larger arc by applying a least-squares ad-
justment, and eliminating possible blunders. The noise ef-
fects near the breakpoints can be resolved as well. If we
eliminate any "short" phenomena, we can intersect neigh-
boring longer phenomena, and by that close the gaps pro-
duced by the elimination of the short segments.
Real data: Experiments with the — s method were
also performed with real data. We found that the limita-
tions of the j — s method, in terms of predefined thresholds,
are quite critical. The selection of the threshold values is
application dependent, i.e., the approximate size of features
should be known.
4 SUMMARY AND CONCLUSIONS
The paper describes curve segmentation in 3-D object space.
Although the two methods described for that purpose are
not necessarily the best available segmentation methods,
the results are encouraging and show that 3-D segmenta-
tion 1s possible.
The split-and-merge method segments the data into
straight lines only. Circular arcs are segmented into a list
of short straight line segments. The offset criterion used
reduces the sensitivity to noise. In other words, the split-
and-merge method is quite robust and detects line segments
even if they are very noisy.
The y — s method offers the advantage of representing
circular arcs as straight lines. This property allows detec-
tion of circular arcs by using the split-and-merge approach.
However, determining threshold values becomes a crucial
issue. Due to noise effects, it is dependent on the lengths of
lines to be classified. The noise is reduced significantly by a
proper filtering of the original data. However, filtering also
blurs the breakpoints. Current research focuses on a 3-D
Freeman code (Freeman, 1974) representation. That is, the
object space is discretized, thus reducing some of the noise
caused by the scanning process.
The experience gained leads to the following conclu-
sions:
1. Since the 3 — s method allows easy detection of cir-
cular arcs, it can be used for a rough segmentation
of the 3-D curve into straight lines and circular arcs.
Once such approximations exist, other methods can
be used to refine the segmentation.
527
2. Other segmentation methods should be investigated
and eventually extended to 3-D.
The segmentation of the 3-D curves is an important clue
for man-made features, which are usually composed of 3-D
straight lines and other regular curves that provide informa-
tion which is much more explicit than the original densely
spaced points resulting from stereo matching.
References
[1] Ballard, D. H. and C. M. Brown, 1987. Computer Vi-
sion. Prentice-Hall, Inc., Englewood, NJ.
[2] Cho, W., M. Madani, and T. Schenk, 1992. Resam-
pling digital imagery to epipolar geometry. In Interna-
tional Archives of Photogrammetry and Remote Sens-
Ing.
[3] Fischler, M. A. and R. C. Bolles, 1986. Perceptual
organization and curve partitioning. IEEE Transac-
tions on Pattern Analysis and Machine Intelligence,
8(1):100-105.
[4] Freeman, H., 1974. Computer processing of line-
drawing images. Computing Surveys, 6(1).
[5] Grimson, W. E. L., 1985. Computational experiments
with a feature-based stereo algorithm. IEEE Trans-
actions on Pattern Analysis and Machine Intelligence,
7(1):17-34.
[6] Grimson, W. E. L., 1989b. Object Recognition by Rom-
puter: The Role of Geometrical Constraints. MIT
Press, Cambridge, Massachusetts; London, England.
[7] Grimson, W. E. L., 1989a. On the recognition of curved
objects. IEEE Transactions on Pattern Analysis and
Machine Intelligence, 11(6):632-642.
[8] Grimson, W. E. L. and T. Pavlidis, 1985. Discontinuity
detection for visual surface reconstruction. Computer
Vision, Graphics and Image Processing, 30:316-330.
[9] Li, J. C. and T. Schenk, 1991. Stereo image
matching with sub-pixel accuracy. In Proceed-
ings, ACSM/ASPRS Annual Convention, Vol. 5:Pho-
togrammetry and Primary Data Acquisition, pp. 228-
236.
[10] Marr, D. and E. C. Hildreth, 1980. Theory of edge
detection. In Proceedings, Royal Society London, B
207, pp. 187-217.
[11
—À
Pavlidis, T. and S. L. Horowitz, 1974. Segmentation
of plane curves. IEEE Transactions on Computers,
23(8):860-870.
[12] Rabiner, L. R., J. H. McClellan, and T. W. Parks,
1975. FIR digital filter design techniques using
weighted Chebyshev approximations. In Proceedings,
IEEE 63, pp. 595-610.
[13] Ramer, U., 1972. An iterative procedure for the polyg-
onal approximation of plane curves. Computer Graph-
ics and Image Processing, 1:244-256.
