A Theoretical Framework for Relaxation Processes in Pattern Recognition: Application to Robust Nonparametric Contour Generalization
|
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
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb