6.4.2 Basic Algorithms to Partition Curves

Hodes, L.,
Discrete Approximation of Continuous Convex Blobs,
SIAM_JAM(19), 1970, pp. 477-485. BibRef 7000

Cooper, D., and Yalabik, N.,
On the Computational Cost of Approximating and Recognizing Noise-Perturbed Straight Lines and Quadratic Arcs in the Plane,
TC(25), No. 10, October 1976, pp. 1020-1032. BibRef 7610

Davis, L.S., and Rosenfeld, A.,
Curve Segmentation by Relaxation Labeling,
TC(26), 1977, pp. 1053-1057. BibRef 7700

Yamaguchi, F.,
A New Curve Fitting Method Using a CRT Computer Display,
CGIP(7), No. 3, June 1978, pp. 425-437.
WWW Version. BibRef 7806

Pavlidis, T., and Ali, F.,
A Hierarchical Syntactic Shape Analyzer,
PAMI(1), No. 1, January 1979, pp. 2-9. BibRef 7901

Pavlidis, T.,
The Use of a Syntactic Shape Analyzer for Contour Matching,
PAMI(1), No. 3, July 1979, 307-310. BibRef 7907

Pavlidis, T.,
Hierarchies in Structural Pattern Recogniton,
PIEEE(67), 1979, pp. 737-744. BibRef 7900

Rutkowski, W.S., Peleg, S., and Rosenfeld, A.,
Shape Segmentation Using Relaxation,
PAMI(3), No. 4, July 1981, pp. 368-375. See also Thresholding Using Relaxation. BibRef 8107

Rutkowski, W.S.,
Shape Segmentation Using Arc/Chord Properties,
CGIP(17), No. 2, October 1981, pp. 114-129.
WWW Version. BibRef 8110

Slagle, J.R.[James R.], Dixon, J.K.[John K.],
Finding a good figure that approximately passes through given points,
PR(12), No. 5, 1980, pp. 319-326.
WWW Version. 0309 BibRef

Slagle, J.R., Dixon, J.K.,
Freedom descriptions: A way to find figures that approximate given points,
PR(17), No. 6, 1984, pp. 631-636.
WWW Version. 0309 BibRef

Elliott, H., Srinivasan, L.,
An Application of Dynamic Programming to Sequential Boundary Estimation,
CGIP(17), No. 4, December 1981, pp. 291-314.
WWW Version. BibRef 8112

Shlien, S.,
Segmentation of Digital Curves Using Linguistic Techniques,
CVGIP(22), No. 2, May 1983, pp. 277-286.
WWW Version. BibRef 8305

Pavlidis, T.,
Curve Fitting with Conic Splines,
TOG(2), No. 1, 1983, pp. 1-31. BibRef 8300

Badii, F., Peikari, B.,
Approximation of Multipath Planar Shapes in Pattern Analysis,
CIS(12), 1983, pp. 99-110. BibRef 8300

Fischler, M.A., and Bolles, R.C.,
Perceptual Organization and Curve Partitioning,
PAMI(8), No. 1, January 1986, pp. 100-105. Reprinted: BibRef 8601 RCV87(210-215). BibRef
Earlier: CVPR83(38-46). BibRef
And: DARPA83(224-232). Various ways to partition curves. BibRef

Fischler, M.A.,
Perceptual Organization and the Curve Partitioning Problem,
IJCAI83(1014-1018). BibRef 8300

Fischler, M.A., and Wolf, H.C.,
Locating Perceptually Salient Points on Planar Curves,
PAMI(16), No. 2, February 1994, pp. 113-129.
IEEE Abstract. IEEE Top Reference.
WWW Version. BibRef 9402
Earlier:
Saliency Detection and Partitioning Planar Curves,
DARPA93(917-931). Curve partioning using salient points, with an attempt to match human performance. Extension of the Fischler/Bolles paper above. BibRef

Dobbins, A., Zucker, S.W., Cyander, M.S.,
Endstopped Neurons in the Visual Cortex as a Substrate for Calculating Curvature,
Nature(329), No. 6138, 1987, pp. 438-441. BibRef 8700

Wuescher, D.M., and Boyer, K.L.,
Robust Contour Decomposition Using a Constant Curvature Criterion,
PAMI(13), No. 1, January 1991, pp. 41-51.
IEEE Abstract. IEEE Top Reference.
WWW Version. Arcs and lines both. This produces more stable results than local maxima type decompositions. BibRef 9101

Ventura, J.A.[Jose A.], Chen, J.M.[Jen-Ming],
Segmentation of two-dimensional curve contours,
PR(25), No. 10, October 1992, pp. 1129-1140.
WWW Version. BibRef 9210

Roberge, J.,
A Data Reduction Algorithm for Planar Curves,
CVGIP(29), No. 2, February 1985, pp. 168-195.
WWW Version. Fastest algorithm according to See also Optimum Uniform Piecewise Linear Approximation of Planar Curves. BibRef 8502

Phillips, T.Y., Rosenfeld, A.,
A Method of Curve Partitioning Using Arc-Chord Distance,
PRL(5), 1987, pp. 285-288. BibRef 8700

Meer, P., Baugher, E.S., Rosenfeld, A.,
Extraction of Trend Lines and Extrema from Multiscale Curves,
PR(21), No. 3, 1988, pp. 217-226.
WWW Version. BibRef 8800

Yamada, K.[Keiichi],
Method and system for determining connection states of straight short vectors representing figure in curve fitting,
US_Patent5,231,697, July 27, 1993.
WWW Version. BibRef 9307

Cox, I.J., Rehg, J.M., and Hingorani, S.,
A Bayesian Multiple-Hypothesis Approach to Edge Grouping and Contour Segmentation,
IJCV(11), No. 1, August 1993, pp. 5-24.
Springer DOI Reference BibRef 9308
A Bayesian Multiple-Hypothesis Approach to Contour Grouping,
ECCV92(72-77).
Springer DOI Reference BibRef

Chang, C.H., Hwang, S.Y.,
2-D Curve Partitioning by Kohonen Feature Maps,
JVCIR(5), 1994, pp. 148-155. BibRef 9400

Katzir, N., Lindenbaum, M., Porat, M.,
Curve Segmentation under Partial Occlusion,
PAMI(16), No. 5, May 1994, pp. 513-519.
IEEE Abstract. IEEE Top Reference.
WWW Version. BibRef 9405
Earlier:
Planar curve segmentation for recognition of partially occluded shapes,
ICPR90(I: 842-846).
IEEE DOI Reference 9006 BibRef

West, G.A.W., and Rosin, P.L.,
Techniques for Segmenting Image Curves into Meaningful Descriptions,
PR(24), No. 7, 1991, pp. 643-652.
WWW Version. (Check A2, A1?). BibRef 9100

Rosin, P.L., and West, G.A.W.,
Segmentation of Edges into Lines and Arcs,
IVC(7), No. 2, May 1989, pp. 109-114.
WWW Version. BibRef 8905

Rosin, P.L., West, G.A.W.,
Curve Segmentation and Representation by Superellipses,
VISP(142), No. 5, October 1995, pp. 280-288. BibRef 9510
Earlier:
Segmenting Curves into Elliptic Arcs and Straight Lines,
ICCV90(75-78).
IEEE DOI Reference BibRef

Rosin, P.L.,
Augmenting Corner Descriptors,
GMIP(58), No. 3, May 1996, pp. 286-294. 9606 BibRef

Rosin, P.L., West, G.A.W.,
Salience Distance Transforms,
GMIP(57), No. 6, November 1995, pp. 483-521. BibRef 9511
Earlier:
Multi-scale Salience Distance Transforms,
BMVC93(579-588).
PDF Version. Curtin Univ, Australia. BibRef

Rosin, P.L.[Paul L.], West, G.A.W.[Geoff A.W.],
Nonparametric Segmentation of Curves into Various Representations,
PAMI(17), No. 12, December 1995, pp. 1140-1153.
IEEE Abstract. IEEE Top Reference.
WWW Version. Code, Curve Segmentation. (Code is available:
WWW Version. BibRef 9512
Detection of Circular Arcs in Images,
Alvey88(259-263). BibRef
Earlier: A2, A1:
Multi-stage Combined Ellipse and Line Detection,
BMVC92(197-206).
PDF Version. 9209Segments into various components, lines, arcs (circular, elliptical, etc.). A fairly general complete algorithm. An extensive bibliography of earlier curve partitioning work. BibRef

Kanatani, K.,
Nonparametric Segmentation of Curves into Various Representations: Comment,
PAMI(19), No. 12, December 1997, pp. 1391-1394.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9712 BibRef

Rosin, P.L., West, G.A.W.,
Nonparametric Segmentation of Curves into Various Representations: Response,
PAMI(19), No. 12, December 1997, pp. 1393-1394.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9712 BibRef

Rosin, P.L.,
Non-Parametric Multi-Scale Curve Smoothing,
PRAI(8), 1994, pp. 1381-1406. BibRef 9400
Earlier: SPIE(1964), April 1993, pp. 66-77 Code, Curve Smoothing. Code is available:
WWW Version. BibRef

Sheu, H.T., Yang, H.Z.,
Open Curve Segmentation Via a 2-Phase Scheme,
PR(26), No. 12, December 1993, pp. 1839-1844.
WWW Version. BibRef 9312

Ichoku, C., Deffontaines, B., Chorowicz, J.,
Segmentation of Digital Plane-Curves: A Dynamic Focusing Approach,
PRL(17), No. 7, June 10 1996, pp. 741-750. 9607 BibRef

Arcelli, C., Ramella, G.,
Finding Contour-Based Abstractions of Planar Patterns,
PR(26), No. 10, October 1993, pp. 1563-1577.
WWW Version. BibRef 9310

Sharaiha, Y.M., Garat, P.,
A Compact Chord Property for Digital Arcs,
PR(26), No. 5, May 1993, pp. 799-803.
WWW Version. BibRef 9305

Debled-Rennesson, I.[Isabelle], and Reveilles, J.P.,
A Linear Algorithm for Segmentation of Digital Curves,
PRAI(9), 1995, pp. 635-662. See also Multiorder polygonal approximation of digital curves. BibRef 9500

Reveillès, J.P.[Jean-Pierre],
Weak Rational Computing for Digital Geometry,
DGCI08(xx-yy).
Springer DOI Reference 0804 BibRef

Debled-Rennesson, I.[Isabelle], Rémy, J.L.[Jean-Luc], Rouyer-Degli, J.[Jocelyne],
Segmentation of Discrete Curves into Fuzzy Segments,
INRIARR-4989, 2003.
HTML Version. BibRef 0300

de la Blanca, N.P.[N. Perez], Fdez Valdivia, J., Garcia, J.A.,
Characterizing Planar Outlines,
PRL(14), 1993, pp. 489-497. BibRef 9300

Chaudhuri, B.B., Dutta, S.,
Interactive Curve Drawing by Segmented Bezier Approximation with a Control Parameter,
PRL(4), 1986, pp. 171-176. BibRef 8600

Leite, J.A.F., Hancock, E.R.,
Iterative Curve Organization with the EM Algorithm,
PRL(18), No. 2, February 1997, pp. 143-155. 9704 BibRef
Earlier:
Iterative Spline Relaxation with the EM Algorithm,
ICPR96(II: 161-165).
IEEE DOI Reference 9608(Univ. of York, UK) BibRef

Lindeberg, T., Li, M.X.,
Segmentation and Classification of Edges Using Minimum Description Length Approximation and Complementary Junction Cues,
CVIU(67), No. 1, July 1997, pp. 88-98. 9707
WWW Version. BibRef

Lindeberg, T., and Li, M.,
Automatic Generation of Break Points for MDL Based Curve Classification,
SCIA95(767-776). BibRef 9500
And: ISRN KTH/NA/P-94/28-SE, September 1994.
HTML Version. BibRef

Li, M.,
Minimum Description Length Based 2-D Shape Description,
ICCV93(512-517).
IEEE DOI Reference BibRef 9300
And: ISRN KTH/NA/P-92/34-SE, November 1992.
HTML Version. And Postscript:
Postscript Version. BibRef

Ozugur, T., Denizhan, Y., Panayirci, E.,
Feature-Extraction in Shape-Recognition Using Segmentation of the Boundary Curve,
PRL(18), No. 10, October 1997, pp. 1049-1056. 9802 BibRef

Pham, T.D., Yan, H.,
An Effective Algorithm for the Segmentation of Digital Plane Curves: The Isoparametric Formulation,
PRL(19), No. 2, February 1998, pp. 171-176. 9808 BibRef

Zunic, J.[Jovisa], Acketa, D.M.[Dragan M.],
A General Coding Scheme for Families of Digital Curve Segments,
GMIP(60), No. 6, November 1998, pp. 437-460. BibRef 9811

Sheu, H.T., Hu, W.C.,
Multiprimitive Segmentation of Planar Curves: A Two-Level Breakpoint Classification and Tuning Approach,
PAMI(21), No. 8, August 1999, pp. 791-797.
IEEE Abstract. IEEE Top Reference.
WWW Version. BibRef 9908

Rosin, P.L.[Paul L.],
Shape Partitioning by Convexity,
SMC-A(30), No. 2, March 2000, pp. 202-210.
IEEE Top Reference. 0004 BibRef
Earlier: BMVC99(633-64).
PDF Version.
PDF Version. BibRef

Rosin, P.L.[Paul L.],
Straightening and Partitioning Shapes,
VF01(440 ff.).
HTML Version. 0209 BibRef

Chung, J.W.[Jae-Won], Lee, J.H.[Jin-Hak], Moon, J.H.[Joo-Hee], Kim, J.K.[Jae-Kyoon],
A new vertex-based binary shape coder for high coding efficiency,
SP:IC(15), No. 7-8, May 2000, pp. 665-684.
WWW Version. 0005 BibRef

Meier, F.W.[Fabian W.], Schuster, G.M.[Guido M.], Katsaggelos, A.K.[Aggelos K.],
A mathematical model for shape coding with B-splines,
SP:IC(15), No. 7-8, May 2000, pp. 685-701.
WWW Version. 0005 BibRef

Meribout, M., Ogura, T., Nakanishi, M.,
On Using the CAM Concept for Parametric Curve Extraction,
IP(9), No. 12, December 2000, pp. 2126-2130.
IEEE DOI Reference 0011 BibRef

Yan, H.[Hong],
Fuzzy curve-tracing algorithm,
SMC-B(31), No. 5, October 2001, pp. 768-780.
IEEE Top Reference. 0111 BibRef
Earlier:
Detection of curved text path based on the fuzzy curve-tracing (FCT) algorithm,
ICDAR01(266-270).
IEEE DOI Reference 0109 BibRef

Lam, B.S.Y., Yan, H.[Hong],
Complex curve tracing based on a minimum spanning tree model and regularized fuzzy clustering,
ICIP04(III: 2091-2094).
IEEE DOI Reference 0505 BibRef

Wang, D.P.[Der Perng],
A new algorithm for fitting a rectilinear x-monotone curve to a set of points in the plane,
PRL(23), No. 1-3, January 2002, pp. 329-334.
HTML Version. 0201 BibRef

Cronin, T.M.[Terence M.],
Visualizing concave and convex partitioning of 2D contours,
PRL(24), No. 1-3, January 2003, pp. 429-443.
HTML Version. 0211 BibRef

Sarkar, B.[Biswajit], Singh, L.K.[Lokendra K.], Sarkar, D.[Debranjan],
Approximation of digital curves with line segments and circular arcs using genetic algorithms,
PRL(24), No. 15, November 2003, pp. 2585-2595.
WWW Version. 0308 BibRef

Sarkar, B.[Biswajit], Roy, S.[Sanghamitra], Sarkar, D.[Debranjan],
Hierarchical representation of digitized curves through dominant point detection,
PRL(24), No. 15, November 2003, pp. 2869-2882.
WWW Version. 0308 BibRef

Faber, P.[Petko],
A Theoretical Framework for Relaxation Processes in Pattern Recognition: Application to Robust Nonparametric Contour Generalization,
PAMI(25), No. 8, August 2003, pp. 1021-1027.
IEEE Abstract. IEEE Top Reference. 0308Task is to find an application specific relaxation process. Apply to curve descriptions. BibRef

Wei, W.[Wei], Wang, Q.[Qi], Wang, H.[Hua], Zhang, H.G.[Hong Guang],
The feature extraction of nonparametric curves based on niche genetic algorithms and multi-population competition,
PRL(26), No. 10, 15 July 2005, pp. 1483-1497.
WWW Version. 0506 BibRef

Mayster, Y.[Yan], Lopez, M.A.[Mario A.],
Approximating a set of points by a step function,
JVCIR(17), No. 6, December 2006, pp. 1178-1189.
WWW Version. 0711Combinatorial optimization; Visual data reduction; Curve fitting; Approximation algorithms BibRef

Sarfraz, M.[Muhammad],
Some Algorithms for Curve Design and Automatic Outline Capturing of Images,
IJIG(4), No. 2, April 2004, pp. 301-324. 0404 BibRef

Sarfraz, M.,
Interactive Curve Modeling With Applications to Computer Graphics, Vision and Image Processing,
Springer2008, ISBN: 978-1-84628-870-8.
WWW Version. Tools for curves, splines, etc. BibRef 0800

He, Z.[Zhiyu], Kuester, F.[Falko],
GPU-Based Active Contour Segmentation Using Gradient Vector Flow,
ISVC06(I: 191-201).
Springer DOI Reference 0611 BibRef

Locteau, H.[Herve], Raveaux, R.[Romain], Adam, S.[Sébastien], Lecourtier, Y.[Yves], Héroux, P.[Pierre], Trupin, E.[Eric],
Approximation of Digital Curves using a Multi-Objective Genetic Algorithm,
ICPR06(II: 716-719).
WWW Version. 0609 BibRef

Trupin, E., Lecourtier, Y.,
A modified contour following algorithm applied to document segmentation,
ICPR92(II:525-528).
IEEE DOI Reference 9208 BibRef

Makkapati, V.[Vishnu], Mahapatra, P.[Pravas],
Contour Encoding Based on Extraction of Key Points Using Wavelet Transform,
ICPR06(II: 1177-1180).
WWW Version. 0609 BibRef

Marji, M.[Majed], Klette, R.[Reinhard], Siy, P.[Pepe],
Corner Detection and Curve Partitioning Using Arc-Chord Distance,
IWCIA04(512-521).
WWW Version. 0505 BibRef

Weitzenberg, J., Posch, S., Rost, M.,
Analysis of Amperometric Biosensor Curves Using Hidden-Markov-Models,
DAGM02(182 ff.).
HTML Version. 0303 BibRef

Sezgin, T.M.[Tevfik Metin], Davis, R.[Randall],
Early Sketch Processing with Application in HMM Based Sketch Recognition,
MIT AIM-2004-016, July 28, 2004.
WWW Version. 0501 BibRef

Sezgin, T.M.[Tevfik Metin],
Feature Point Detection and Curve Approximation for Early Processing of Free-Hand Sketches,
MIT AI-TR-2001-009, May 2001.
WWW Version. 0205 BibRef

Ho, P.S.[Pong-Sik], and Kim, M.H.[Min-Hwan],
A Hierarchical Scheme for Representing Curves without Self-Intersections,
CVPR01(II:498-503).
IEEE Abstract. IEEE Top Reference. 0110Applying iterative endpoint fit for complex curves results in self-intersection. Hierarchical approach to eliminate that problem. See also Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. BibRef

Stricker, M.[Markus], Leonardis, A.[Aleš],
ExSel++: A general framework to extract parametric models,
CAIP95(90-97).
Springer DOI Reference 9509 BibRef
And:
From Edgels to Parametric Curves,
SCIA95(xx).
WWW Version. BibRef

Stewart, C.V.[Charles V.], Bubna, K.[Kishore], Perera, A.[Amitha],
Estimating Model Parameters and Boundaries By Minimizing a Joint, Robust Objective Function,
CVPR99(II: 387-393).
IEEE Abstract. IEEE Top Reference.
WWW Version. Not really curves, but estimation of parameters. BibRef 9900

Robl, C., Farber, G.,
Contour Tracer for a Fast and Precise Edge-line Extraction,
MVA98(xx-yy). BibRef 9800

Sluzek, A.[Andrzej],
Multi-Level Contour Segmentation Using Multiple Segmentation Primitives,
ICPR98(Vol I: 741-743).
IEEE DOI Reference 9808 BibRef

Mokhtari, M., and Bergevin, R.,
Multiscale Segmentation and Approximation for Significant Description of 2D Contours,
ICIP97(I: 212-215).
IEEE DOI Reference BibRef 9700

Weitzel, L., Kopecz, K., Spengler, C., Eckhorn, R., Reitboeck, H.J.,
Contour segmentation with recurrent neural networks of pulse-coding neurons,
CAIP97(337-344).
WWW Version. 9709 BibRef

Sloboda, F.[Fridrich], Zat'ko, B.[Bedrich],
Analysis situs and image processing,
CIAP97(I: 190-197).
WWW Version. 9709Approximation of planar curves and arcs. BibRef

Sloboda, F.[Fridrich], Zat'ko, B.[Bedrich],
On boundary approximation,
CAIP95(488-495).
Springer DOI Reference 9509 BibRef

Orrite, C., Lopez, J.E., Alcolea, A.,
Curve segmentation by continuous smoothing at multiple scales,
ICIP96(III: 579-582).
IEEE DOI Reference 9610 BibRef

Caglioti, V.[Vincenzo],
Decomposing contours into curves of different families,
CIAP95(399-404).
Springer DOI Reference 9509 BibRef

Delingette, H.,
Intrinsic Stabilizers of Planar Curves,
ECCV94(B:427-436).
Springer DOI Reference BibRef 9400

Waku, J., Chassery, J.M.,
Specification of a wavelet for multiscale analysis of discrete boundary,
ICPR92(III:680-683).
IEEE DOI Reference 9208 BibRef

Wu, L.D., Luo, X.Y.,
Fast Piecewise Non-Linear Approximation,
ICPR84(330-332). BibRef 8400

Otsu, N.,
Karhunen-Loeve Line Fitting And A Linearity Measure,
ICPR84(486-489). BibRef 8400

Gutfinger, D., Nishimura, R., Doi, H., and Sklansky, J.,
Robust Curve Detection by Temporal Geodesics,
ICCV90(752-756).
IEEE DOI Reference BibRef 9000

Zhou, Y.T.,
Fitting smooth curves,
ICPR90(I: 455-459).
IEEE DOI Reference 9006 BibRef

Cai, L.D., Porrill, J., Pollard, S.B., Mayhew, J.E.W., Frisby, J.P.,
Segmentation of planar curves using local and global behaviour analysis,
BMVC90(xx-yy).
PDF Version. 9009 BibRef

Chapter on Edge Detection and Analysis, Lines, Segments, Curves, Corners, Hough Transform continues in
Piece-Wise Linear Representations from Curves .