loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Trace Inference, Curvature Consistency, and Curve Detection
August 1989 (vol. 11 no. 8)
pp. 823-839

An approach is described for curve inference that is based on curvature information. The inference procedure is divided into two stages: a trace inference stage, which is the subject of the present work, and a curve synthesis stage. It is shown that recovery of the trace of a curve requires estimating local models for the curve at the same time, and that tangent and curvature information are sufficient. These make it possible to specify powerful constraints between estimated tangents to a curve, in terms of a neighborhood relationship called cocircularity, and between curvature estimates, in terms of a curvature consistency relation. Because all curve information is quantized, special care must be taken to obtain accurate estimates of trace points, tangents, and curvatures. This issue is addressed specifically to the introduction of a smoothness constraint and a maximum curvature constraint. The procedure is applied to two types of images: artificial images designed to evaluate curvature and noise sensitivity, and natural images.

[1] F. Attneave,Applications of Information Theory to Psychology: A Summary of Basic Concepts, Methods, and Results. New York: Holt, Rinehart and Winston, 1959.[2] H. G. Barrow and J. M. Tenenbaum, "Interpreting line drawings as three-dimensional surfaces,"Artificial Intell., vol. 17, pp. 75-116, 1981.[3] T. O. Binford, "Inferring surfaces from images,"Artificial Intell., vol. 17, pp. 205-244, 1981.[4] M. Brady and H. Asada, "Smoothed local symmetries and their implementation,"Robot. Res., vol. pp. 37-61, 1984.[5] L. S. Davis and Freeman, "Corner detection in chain codes,"IEEE Trans. Pattern Anal. Machine Intell., 1977.[6] L. S. Davis and A. Rosenfeld, "Cooperating processes for low-level vision: A survey,"Artificial Intell., vol. 17, pp. 245-263, 1981.[7] M. P. do Carmo,Differential Geometry of Curves and Surfaces. Englewood Cliffs, NJ: Prentice-Hall, 1976.[8] O. Faugeras and M. Berthod, "Scene labeling, An optimization approach," inProc. IEEE Conf. Pattern Recognition Image Proc., Chicago, IL, 1979, pp. 318-326.[9] M. A. Fischler and R. C. Bolles, "Perceptual organization and curve partitioning," Proc. 1983 image Understanding Workshop, 1983.[10] S. Geman and D. Geman, "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, pp. 721-741, 1986.[11] R. Hartshorne,Algebraic Geometry. New York: Springer Verlag, 1972.[12] M. Hedlund, G. H. Granlund, and H. Knutsson, "A consistency operation for line and curve enhancement," inProc. Pattern Recognition Image Proc. Conf., 1982, pp. 93-96.[13] D. D. Hoffman and W. A. Richards, "Parts of recognition," inFrom Pixels to Predicates, A. Pentland, Ed. Norwood, NJ: Ablex, 1986.[14] D. Hubel and T. Wiesel, "Functional architecture of macaque monkey visual cortex,"Proc. Royal Soc.(London), vol. B198, pp. 1-59, 1977.[15] R. Hummel and S. W. Zucker, "On the foundations of relaxation labeling processes,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-5, pp. 267-287, 1983.[16] L. Iverson and S. W. Zucker, "Orientation selection to optical flow: A computational perspective,"Proc. IEEE Workshop Comput. Vision, Miami, FL, 1987.[17] J. Koenderink and A. Doom, "The shape of smooth objects and the way contours end,"Perception, vol. 11, pp. 129-137, 1982.[18] A. Martelli, "An application of heuristic search methods to edge and contour detection,"Commun. ACM, vol. 19, no. 2, pp. 73-83, Feb. 1976.[19] J. L. Mohammed, R. Hummel, and S. W. Zucker, "A gradient projection algorithm for relaxation methods,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-5, pp. 330-332, 1983.[20] U. Montanari, "On the optimal detection of curves in noisy pictures,"Comm. ACM, vol. 14, pp. 335-345, 1971.[21] A. Papoulis,Probability, Random Variables, and Stochastic Processes. New York: McGraw-Hill, 1965.[22] P. Parent and S. W. Zucker, "Radial projection: An efficient update rule for relaxation labeling," Comput. Vision Robotics Lab. Tech. Rep. TR-85-15R, McGill Univ., 1985.[23] P. Parent and S. W. Zucker, "Radial projection: An efficient update rule for relaxation labeling,"IEEE Trans. Pattern Anal. Machine Intell., to be published.[24] T. Pavlidis,Algorithms for Graphics and Image Processing. Rockville, MD: Computer Science Press, 1982.[25] S. Peleg and A. Rosenfeld, "Determining compatibility coefficients for curve enhancement relaxation processes,"IEEE Trans. Syst., Man, Cybern., vol. SMC-8, pp. 548-555, 1978.[26] A. Rosenfeld, R. Hummel, and S. W. Zucker, "Scene labeling by relaxation operations,"IEEE Trans. Syst., Man, Cybern., vol. SAC- 6, pp. 420-433, 1976.[27] A. Rosenfeld and A. Kak,Digital Picture Processing, New York: Academic, 1976.[28] P. Sander and S. W. Zucker, "Inferring differential structure from 3D images: Smooth cross sections of fiber bundles," McGill Res. Cent. Intell. Machines Tech. Rep. TR-CIM-88-6, McGill Univ., Montreal, P.Q., Canada, 1988.[29] D. Terzopoulos, "Integrating visual information from multiple sources," inFrom Pixels to Predicates, A. Pentland, Ed. Norwood, NJ: Ablex, 1986.[30] D. Waltz, "Understanding line drawings of scenes with shadows," inThe Psychology of Computer Vision, P. H. Winston, Ed. New York: McGraw-Hill, 1975, pp. 19-91.[31] A. P. Witkin, "Recovering surface shape and orientation from texture,"Artificial Intell., vol. 17, pp. 17-45, 1981.[32] S. W. Zucker, R. Hummel, and A. Rosenfeld, "An application of relaxation labeling to line and curve enhancement,"IEEE Trans. Comput., vol. 26, pp. 394-403, and pp. 92-929, 1977.[33] S. W. Zucker, "Early orientation selection and grouping: Evidence for type I and type II processes," Comput. Vision Robot. Lab. Tech. Rep. TR-82-SR, McGill Univ., 1982.[34] S. W. Zucker and P. Parent, "Multiple-size operators and optimal curve finding," inMultiresolution Image Processing and Analysis, A. Rosenfeld, Ed. New York: Springer-Verlag, 1984.[35] S. W. Zucker, "Early orientation selection: Tangent fields and the dimensionality of their support,"Comput. Vision, Graphics, Image Processing, 1985.[36] S. W. Zucker and R. Hummel, "Receptive fields and the representation of visual information,"Human Neurobiology, vol. 5, pp. 121- 128, 1986.[37] S.W. Zucker, C. David, L. Dobbins, and L. Iverson, "The organization of curve detection: Coarse tanget fields and fine spline coverings," inProc. 2nd ICCV, Tarpon Springs, FL, 1988, pp. 568-577.

Index Terms:
picture processing; pattern recognition; curvature consistency; curve detection; curve inference; curvature information; tangent; cocircularity; trace points; artificial images; natural images; inference mechanisms; pattern recognition; picture processing
Citation:
P. Parent, S.W. Zucker, "Trace Inference, Curvature Consistency, and Curve Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 8, pp. 823-839, Aug. 1989, doi:10.1109/34.31445
Usage of this product signifies your acceptance of the Terms of Use.