| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Theoretical Framework for Relaxation Processes in Pattern Recognition: Application to Robust Nonparametric Contour Generalization
August 2003 (vol. 25 no. 8)
pp. 1021-1027
Abstract—While various approaches are suggested in the literature to describe and generalize relaxation processes concerning to several objectives, the wider problem addressed here is to find the best-suited relaxation process for a given assignment problem, or better still, to construct a task-dependent relaxation process. For this, we develop a general framework for the theoretical foundations of relaxation processes in pattern recognition. The resulting structure enables 1) a description of all known relaxation processes in general terms and 2) the design of task-dependent relaxation processes. We show that the well-known standard relaxation formulas verify our approach. Referring to the common problem of generating a generalized description of a contour we demonstrate the applicability of the suggested generalization in detail. Important characteristics of the constructed task-dependent relaxation process are: 1) the independency of the segmentation from any parameters, 2) the invariance to geometric transformations, 3) the simplicity, and 4) efficiency.
[1] 1021 D.H. Ballard and C.M. Brown, Computer Vision, Prentice Hall, Upper Saddle River, N.J., 1982.[2] N. Bonnet and J. Cutrona, Improvement of Unsupervised Multi-Component Image Segmentation through Fuzzy Relaxation Proc. Int'l Conf. Visualization, Imaging, and Image Processing, pp. 477-482, 2001.[3] H. Borotschnig, A. Pinz, and I. Bloch, Fuzzy Relaxation Labeling Reconsidered Proc. Sixth Int'l Conf. Fuzzy Systems, pp. 1417-1422, 1998.[4] H.J. Caufield, Fuzzy Syntactical Pattern Recognition Applied Optics, vol. 29, no. 17, pp. 2600-2602, 1990.[5] W.J. Christmas, J.V. Kittler, and M. Petrou, Labelling 2-D Geometric Primitives Using Probabilistic Relaxation: Reducing the Computational Requirements Electronic Letters, vol. 32, no. 4, pp. 312-314, 1996.[6] G.R. Cross and A.K. Jain, Markov Random Field Texture Models IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 5, no. 1, pp. 25-39, 1983.[7] L.S. Davis and A. Rosenfeld, Cooperating Processes for Low-Level Vision: A Survey Artificial Intelligence, vol. 17, pp. 245-263, 1981.[8] D.H. Douglas and T.K. Peuker, Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature The Canadian Cartographer, vol. 10, no. 2, pp. 112-122, 1973.[9] R.O. Duda and P.E. Hart, Pattern Classification and Scene Analysis. New York: John Wiley and Sons, 1973.[10] P. Faber, A General Framework for Relaxation Processes. Technical Report EDI-INF-RR-0057, Univ. of Edinburgh, 2001.[11] S. Geman and D. Geman, Stochastic Relaxation, Gibbs Distribution, and the Bayesian Restoration of Images IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, no. 6, pp. 721-741, 1984.[12] J.W. Guan and D.A. Bell, Generalization of the Dempster-Shafer Theory Proc. 13th Int'l Joint Conf. Artificial Intelligence, pp. 592-597, 1993.[13] E.R. Hancock and J. Kittler, "Discrete Relaxation," Pattern Recognition, no. 23, pp. 711-733, 1990.[14] E.R. Hancock and R.C. Wilson, A Bayesian Framework for Hierarchical Relaxation Proc. 12th Int'l Conf. Pattern Recognition, pp. 7-12, 1994.[15] R.M. Haralick, Decision Making in Context IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 5, no. 4, pp. 417-428, 1983.[16] R.M. Haralick, J.L. Mohammed, and S.W. Zucker, Compatibilities and the Fixed Points of Arithmetic Relaxation Processes Proc. Int'l Conf. Color in Graphics and Image Processing, vol. 13, pp. 242-256, 1980.[17] R.M. Haralick, An Interpretation for Probabilistic Relaxation Proc. Conf. Computer Vision, Graphics, and Image Processing, vol. 22, no. 3, pp. 388-395, June 1983.[18] T.C. Henderson, A Note on Discrete Relaxation Proc. Conf. Computer Vision, Graphics, and Image Processing, vol. 28, no. 5, pp. 384-388, 1984.[19] R.A. Hummel and S.W. Zucker, On the Foundations of Relaxation Labeling Processes IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 5, no. 3, pp. 267-286, 1983.[20] R.L. Kirby, A Product Rule Relaxation Method Technical Report 772, Univ. Maryland, 1979.[21] J. Kittler, W.J. Christmas, and M. Petrou, Probabilistic Relaxation for Matching Problems in Computer Vision Proc. Fourth Int'l Conf. Computer Vision, pp. 666-673, 1993.[22] J. Kittler and J. Illingworth, "Relaxation Labeling Algorithms—A Review," Image and Vision Computers, vol. 3, no. 4, pp. 206-216, 1985.[23] G. Lohmann, An Evidential Reasoning Approach to the Classification of Satellite Images Technical Report DLR-FB 91-29, Deutsche Forschungsanstalt für Luft- und Raumfahrt, 1991.[24] D.G. Lowe, Perceptual Organization and Visual Recognition. Boston: Kluwer Academic, 1985.[25] D.G. Lowe, “Three-Dimensional Object Recognition from Single Two-Dimensional Images,” Artificial Intelligence, vol. 31, pp. 355-395, 1987.[26] H. Ogawa, A Fuzzy Relaxation Technique for Partial Shape Matching Pattern Recognition Letters, vol. 15, no. 6, pp. 349-355, 1994.[27] K.E. Price, Relaxation Matching Techniques A Comparison IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, no. 5, pp. 617-623, 1985.[28] A. Rosenfeld, R.A. Hummel, and S.W. Zucker, Scene Labeling by Relaxation Operations IEEE Trans. Systems, Man, and Cybernetics, vol. 6, no. 6, pp. 420-433, 1976.[29] P.L. Rosin and G.A.W. West, “Nonparametric Segmentation of Curves into Various Representations,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, pp. 1,140-1,153, 1995.[30] G. Shafer, A Mathematical Theory of Evidence. Princeton Univ. Press, 1976.[31] G. Shafer, Perspectives on the Theory and Practice of Belief Functions Int'l J. Approximate Reasoning, vol. 4, pp. 323-362, 1990.[32] P. Smets, The Combination of Evidence in the Transferable Belief Model IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12. no. 5, pp. 447-458, May 1990.[33] V.W. Soo and K. Huang, On Evidential Relaxation Labeling A Scheme Toward Knowledge-Based Vision J. Information Science and Eng., vol. 9, no. 2, pp. 153-175, 1993.[34] R.V. Southwell, Stress-Calculation in Frameworks by the Method of Systematic Relaxation of Constraints, I and II Proc. Royal Soc. Edinburgh, vol. 151, no. 872, pp. 56-95, 1935.[35] A.J. Stoddart, M. Petrou, and J.V. Kittler, On the Foundations of Probabilistic Relaxation with Product Support J. Math. Imaging and Vision, vol. 9, no. 1, pp. 29-48, July 1998.[36] G. Temple, The General Theory of Relaxation Methods Applied to Linear Systems Proc. Royal Soc. Edinburgh, vol. 169, no. 939, pp. 476-500, 1939.[37] P.H.S. Torr, Geometric Motion Segmentation and Model Selection Phil. Trans. Royal Soc. A, pp. 1321-1340, 1998.[38] G. Vosselman, Relational Matching.Berlin: Springer-Verlag, 1992.[39] Z. Wang and G. Klir, Fuzzy Measure Theory. Plenum Press, 1992.[40] G. Winkler, Image Analysis, Random Fields, and Dynamic Monte Carlo Methods. Berlin-Heidelberg-New York: Springer, 1995.[41] Q.X. Wu, A Correlation-Relaxation-Labeling Framework for Computing Optical Flow-Template Matching from a New Perspective IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 9, pp. 843-853, Sept. 1995.[42] D.M. Wuescher and K.L. Boyer,“Robust contour decomposition using a constant curvature criterion,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 1, pp. 41-51, 1991.[43] L.A Zadeh, "Fuzzy Logic = Computing with Words," IEEE Trans. on Fuzzy Systems, vol. 4, no. 2, 1996.[44] S.W. Zucker, E.V. Krishnamurthy, and R.L. Haar, Relaxation Processes for Scene Labeling: Convergence, Speed, and Stability IEEE Trans. Systems, Man, and Cybernetics, vol. 8, no. 1, pp. 41-48, 1978.[45] S.W. Zucker, Y.G. Leclerc, and J.L. Mohammed, Continuous Relaxation and Local Maxima Selection: Conditions for Equivalence IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 3, no. 2, pp. 117-127, 1981.
Index Terms:
Generalization, compatibility function, support function, relaxation operator, significance measure, information theoretic model selection.
Citation:
Petko Faber, "A Theoretical Framework for Relaxation Processes in Pattern Recognition: Application to Robust Nonparametric Contour Generalization," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 8, pp. 1021-1027, Aug. 2003, doi:10.1109/TPAMI.2003.1217606
