Axioms and fundamental equations of image processing. (English) Zbl 0788.68153

Alvarez, Luis; Guichard, Frédéric; Lions, Pierre-Louis; Morel, Jean- Michel

Arch. Ration. Mech. Anal. 123, No. 3, 199-257 (1993).

The (nearly 60 pages) paper under review gives a full axiomatic base for the multiscale analysis of a picture in image analysis. The authors define a multiscale analysis as a family of transforms \((T_ t)_{t \geq 0}\) defined on a class of functions on \(\mathbb{R}^ n\), which gives rise to a family of pictures \((T_ tf)_{t \geq 0}\) for a given original picture \(f\); the parameter \(t\) defines the size of the neighbourhood; the operators \(T_ t\) are not necessarily linear. Besides the so-called comparison principle \((T_ t(f) \leq T_ t(g)\) for all \(t \geq 0\) and for \(f \leq g)\), two classes of axioms are distinguished. It is shown that, under these axioms, there exists a continuous function \(F\) such that, when for a given picture \(f\) we put \(u(t,x)=(T_ tf)(x)\), \(u(x,t)\) satisfies a partial differential equation of the form \({\partial u \over \partial t}=F(D^ 2u,Du)\). The already existing classical models of multiscale analysis (such as the Marr and Hildreth theory) are shown to be special cases of the developed general theory. The same methodology is applied to the analysis of movies.

Reviewer: G.Crombez (Gent)

MSC:

68U10

Computing methodologies for image processing

Keywords:

architectural axioms; morphological axioms; image analysis; multiscale analysis

References:

[1]	M. Allmen & C. R. Dyer. Computing spatiotemporal surface flow. Conference on Computer Vision, IEEE Computer Society Press. 303-309, 1991.
[2]	L. Alvarez, P. L. Lions & J. M. Morel. Image selective smoothing and edge detection by nonlinear diffusion (II). SIAM J. Num. Anal, 29, 845-866, 1992. · Zbl 0766.65117
[3]	H. Asada & M. Brady. The curvature primal sketch. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8, 2-14, 1986.
[4]	E. B. Barret, P. M. Payton, N. N. Haag & M. H. Brill. General methods for determining projective invariants in imagery. Computer Vision Graphics Image Proc., 1991.
[5]	G. Barles & P. E. Souganidis. Convergence of approximation schemes for fully nonlinear second order equation, Asymp. Anal, to appear. · Zbl 0729.65077
[6]	H. Brezis. Analyse Fonctionelle, Théorie et Applications. Masson, Paris, 1987.
[7]	M. Campani & A. Verri. Computing optical flow from an overconstrained system of linear algebraic equations. Conference on Computer Vision 1991. IEEE Computer Society Press. · Zbl 0780.68132
[8]	J. Canny. Finding edges and lines in images. Technical Report 720, MIT, Artificial Intelligence Laboratory, 1983.
[9]	F. Catté, T. Coll, P. L. Lions & J. M. Morel. Image selective smoothing and edge detection by nonlinear diffusion. Preprint, CEREMADE 1990. To appear in SIAM J. Num. Anal. · Zbl 0746.65091
[10]	Y -G. Chen, Y. Giga & S. Goto. Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations, Preprint, Hokkaido University, 1989. · Zbl 0735.35082
[11]	Y -G. Chen, Y. Giga, T. Hitaka & M. Honma. Numerical analysis for motion of a surface by its mean curvature. Preprint, Hokkaido University. · Zbl 0939.65545
[12]	M. G. Crandall, H. Ishii & P. L. Lions. User’s guide to viscosity solution of second order partial differential equation. Preprint, CEREMADE, 1990. · Zbl 0755.35015
[13]	J. I. Diaz. A nonlinear parabolic equation arising in image processing. Extracta Matematicae, Universidad de Extremadura 1990.
[14]	G. Dubek & J. Tsotsos. Recognising planar curves using curvature-tuned smoothing. Third Conference on Computer Vision 1990. IEEE Computer Society Press.
[15]	G. Dubek & J. Tsotsos. Shape representation and recognition from curvature. Third Conference on Computer Vision 1990. IEEE Computer Society Press.
[16]	L. C. Evans & J. Spruck. Motion of level sets by mean curvature, I. Preprint. · Zbl 0726.53029
[17]	S. V. Fogel. A nonlinear approach to the motion correspondance problem. Second Conference on Computer Vision 1988, IEEE Computer Society Press. 619-628.
[18]	D. Forsyth, J. L. Mundy, A. Zisserman, C. Coelho, A. Heller & C. Rothwell. Invariant descriptors for 3-D object recognition and pose. IEEE Transaction of Pattern Analysis and Machine Intelligence, 13, 971-991, 1991. · Zbl 05112509
[19]	Y. Giga & S. Goto. Motion of hypersurfaces and geometric equations. J. Math. Soc. Japan, 44, 1992. · Zbl 0739.53005
[20]	Y. Giga, S. Goto, H. Ishii & M. -H. Sato. Comparison principle and convexity preserving properties for singular degenerate parabolic equation on unbounded domains. Preprint, Hokkaido University, 1990. · Zbl 0836.35009
[21]	R. E. Graham. Snow removal: A noise-stripping process for TV signals, IRE Trans. Information Theory IT-9, 129-144, 1962.
[22]	G. H. Granlukd, H. Knutsson & R. Wilson. Anisotropic non-stationary image and its applications. Picture Processing Laboratory, Linkoeping University, lS-581 83 Linkoeping, Sweden.
[23]	N. M. Grzywacz & A. L. Yuille. The motion coherence theory. Second Conference on Computer Vision 1988, IEEE Computer Society Press. 344-353.
[24]	R. Hartshorne. Foundations of Projective Geometry. Benjamin, 1967. · Zbl 0152.38702
[25]	D. J. Heeger. Optical flow from spatiotemporal filters. Int. J. Computer Vision, 1, 279-302, 1988.
[26]	E. Hildreth. The measurement of visual motion. Cambridge, MIT Press 1984. · Zbl 0543.68074
[27]	K. Hollig & J. A. Nohel. A diffusion equation with a nonmonotone constitutive function. System of Nonlinear Partial Differential Equations, J. Ball, ed., Reidel, 409-422, 1983.
[28]	M. Kass, A. Witkin & D. Terzopoulos. Snakes: active contour models. First Conference on Computer Vision, 1987. IEEE Computer Society Press. 259-268.
[29]	G. Kanizsa. Grammatica del vedere. Tl Mulino, Bologna 1980.
[30]	J. J. Koenderink. The structure of images, Biol. Cybern. 50, 363-370, 1984. · Zbl 0537.92011
[31]	O. A. Lady?enskaja, V. A. Solonnikov & N. N. Ural’tseva. Linear and Quasilinear Equations of Parabolic Type. Amer. Math. Soc., Providence, 1968.
[32]	Y. Lamdan, J. T. Schwartz & H. J. Wolfson. Object recognition by affine invariant matching. In Proc. Computer Version and Pattern Recognition 88, 1988.
[33]	D. Lee, A. Papageorgiou & G. W. Wasilkowski. Computational aspects of determining optical flow. Second Conference on Computer Vision 1988, IEEE Computer Society Press, 612-618.
[34]	P. L. Lions. Generalized Solutions of Hamilton-]acobi Equations. Research Notes in Mathematics, 69, Pitman, Boston, 1982. · Zbl 0497.35001
[35]	H-C. Liu & M. D. Srinath. Partial shape classification using contour matching in distance transformation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12, 1072-1079, 1990. · Zbl 05112696
[36]	A. Mackworth & F. Mokhtarian. Scale-Based description and recognition of planar curves and two-dimensional shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8, 34-43, 1986.
[37]	S. Mallat & S. Zhong. Complete signal representation with multiscale edges. Technical report n? 483, Robotics Report n? 219, Courant Institute, Computer Science Division. · Zbl 0804.68158
[38]	P. Maragos. Tutorial on advances in morphological image processing and analysis. Optical Engineering, 26, 623-632, 1987.
[39]	D. Marr. Vision. Freeman, 1982.
[40]	D. Marr & E. Hildreth. Theory of edge detection. Proc. Ray. Soc. Land., B207, 187-217, 1980.
[41]	J. M. Morel & S. Solimini. Segmentation of images by variational methods: a constructive approach. Revista Matematica de la Universidad Complutense de Madrid, 1, 169-182, 1988. · Zbl 0679.68205
[42]	D. Mumford & J. Shah. Boundary detection by minimizing functionals, IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, 1985.
[43]	M. Nitzberg & Takahiro Shiota. Nonlinear Image Smoothing with Edge and Corner Enhancement. Technical Report n? 90-2, Division of Applied Sciences, Harvard University, Cambridge, 1990.
[44]	K. N. Nordstrom. Biased anisotropic diffusion ? A unified Approach to Edge Detection. Preprint. Dept. of Electrical Engineering and Computer Sciences, University of California, Berkeley.
[45]	S. Osher & L. Rudin. Feature-oriented image enhancement using shock filters. SIAM J. on Numerical Analysis, 27, 919-940, 1990. · Zbl 0714.65096
[46]	S. Osher & J. Sethian. Fronts propagating with curvature dependent speed: algorithms based on the Hamilton-Jacobi formulation. J. Comp. Physics, 79, 12-49, 1988. · Zbl 0659.65132
[47]	P. Perona & J. Malik. Scale space and edge detection using anisotropic diffusion. Proc. IEEE Computer Soc. Workshop on Computer Vision, 1987.
[48]	A. Rattarangsi & R. T. Chin. Scale-Based Detection of Corners of Planer Curves. Third Conference on Computer Vision 1990. IEEE Computer Society Press.
[49]	T.Richardson. Ph.D.Dissertation, MIT 1990.
[50]	A. Rosenfeld & M. Thurston. Edge and curve detection for visual scene analysis. IEEE Trans. on Computers, C-20, 562-569, May 1971.
[51]	L. Rudin & S. Osher. Total variation based restoration of noisy, blurred images, submitted to SIAM J. Num. Analysis, 1992.
[52]	L. Rudin, S. Osher & E. Fatemi. Nonlinear total variation based noise removal algorithms, Physica D., Proceedings of 11th Conf. on Experimental Mathematics, 1992. · Zbl 0780.49028
[53]	P. Saint-Marc, J.-S. Chen & G. Medioni. Adaptative smoothing: A general tool for early vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13, 514-529, 1991. · Zbl 05111646
[54]	J. Serra. Image Analysis and mathematical Morphology, Vol1. Academic Press, 1982. · Zbl 0565.92001
[55]	A. Singh. An estimation-theoretic framework for image-flow computation. Third Conference on Computer Vision 1990. IEEE Computer Society Press.
[56]	D. Sinha & C. R. Giardina. Discrete black and white object Recognition via morphological functions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12, 275-293, 1990. · Zbl 05110927
[57]	M. A. Snyder. On the mathematical foundations of smoothness constrains for the determination of the optical flow and for surface reconstruction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13, 1105-1114, 1991. · Zbl 05112705
[58]	M. Soner. Motion of a set by the curvature of its mean boundary. Preprint. · Zbl 0769.35070
[59]	A. Verri & T. Poggio. Against quantitative optical flow. Conference on Computer Vision 1987. IEEE Computer Society Press, 171-180.
[60]	I. Weiss. Projective invariants of shapes. In Proc. DARPA IU Workshop, 1125-1134, 1989.
[61]	A. P. Witkin. Scale-space filtering. Proc. of IJCAI, Karlsruhe, 1019-1021, 1983.
[62]	A. Yuille & T. Poggio. Scaling theorems for zero crossings. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8, 15-25, 1986. · Zbl 0575.94001
[63]	L. Alvarez, F. Guichard, P.-L. Lions & J.-M. Morel. Axiomatisation et nouveaux opérateurs de la morphologie mathématique. C. R. Acad. Sci. Paris, 315, Sér. I, 265-268, 1992. · Zbl 0805.68134
[64]	L. Alvarez, F. Guichard, P.-L. Lions & J.-M. Morel. Axiomes et équations fundamentales du traitement d’images (Analyse multiéchelle et E.D.P.). C. R. Acad. Sci. Paris, 315, Sér. I, 135-138, 1992. · Zbl 0792.68196
[65]	L. Alvarez, F. Guichard, P.-L. Lions & J.-M. Morel. Analyse multiéchelle des films. C. R. Acad. Sci. Paris, 315, Sér. I, 1145-1148, 1992. · Zbl 0824.68119
[66]	S. Angenant. Parabolic equations for curves on surfaces I, II. University of Wisconsin-Madison, Technical Summary Reports, 89-19, 89-24, 1989.
[67]	G. Barles. Remarks on a flame propagation model. Technical Report 464, INRIA Rapports de Recherche, December 1985.
[68]	G. Barles & C. Georgelin. A simple proof of convergence for an approximation scheme for computing motions by mean curvature. Preprint 1992. · Zbl 0831.65138
[69]	M. Gage & R. S. Hamilton. The heat equation shrinking convex plane curves. J. Diff. Geom., 23, 69-96, 1986. · Zbl 0621.53001
[70]	M. Grayson. The heat equation shrinks embedded plane curves to round points. J. Diff. Geom., 26, 285-314, 1987. · Zbl 0667.53001
[71]	R. Hummel. Representations based on zero-crossings in scale-space. Proc. IEEE Computer Vision and Pattern Recognition Conf., 204-209, 1986.
[72]	B. B. Kimia. Toward a computational theory of shape. Ph. D. Dissertation, Department of Electrical Engineering, McGill University, Montreal, Canada, August 1990.
[73]	J. J. Koenderink & A. J. Van Doorn. Dynamic shape. Biol. Cyber., 53, 383-396, 1986. · Zbl 0586.92022
[74]	B. B. Kimia, A. Tannenbaum & S. W. Zucker. On the evolution of curves via a function of curvature, 1: the classical case. To appear in J. Math. Anal. Appl. · Zbl 0771.53003
[75]	C. Lopez & J. M. Morel. Axiomatisation of shape analysis and application to texture hyperdiscrimination. Proceedings of the Trento Conference on Motion by Mean Curvature and Related Models. Springer, 1992.
[76]	A. Mackworth & F. Mokhtarian. A theory of multiscale, curvaturebased shape representation for planar curves. IEEE Trans. Pattern Anal. Machine Intell. 14, 789-805, 1992. · Zbl 05112081
[77]	P. Maragos. Pattern spectrum and multiscale shape representation. IEEE Trans. Pattern Anal. Machine Intell., 11, 701-716, 1989. · Zbl 0676.68050
[78]	B. Merriman, J. Bence & S. Osher. Diffusion generated motion by mean curvature. April 1992. CAM Report 92-18. Dept. Mathematics. University of California, Los Angeles.
[79]	G. Sapiro & A. Tannenbaum. On affine plane curve evolution. Dept. Electrical Engineering. Technion, Israel Institute of Technology, Haifa, Israel. Preprint, February 1992. · Zbl 0801.53008
[80]	G. Sapiro & A. Tannenbaum. Affine shortening of non-convex plane curves. Dept. of Electrical Engineering. Technion, Israel Institute of Technology, Haifa, Israel. Preprint, February 1992.