[1960s to 1994]

THE “CENTRE DE MORPHOLOGIE MATHEMATIQUE”:

AN OVERVIEW

(Welcoming Speech to the Second International Conference on Mathematical Morphology and its Applications to Image Processing, Fontainebleau, 5-9 September 1994)

JEAN SERRA

Ecole des Mines de Paris, Centre de Morphologie Mathematique, 35, rue Saint-Honore, F-77305 Fontainebleau Cedex, France Since the present workshop enables our gathering here at Fontainebleau, at the very place where mathematical morphology has expanded, let me introduce you briefly, in this welcoming speech, the “Centre de Morphologie Mathematique” and its history.

The Sixties

For a long time, Mathematical Morphology had seemed to confine itself to a small coterie. Was it because its first publication had been a patent, in 1965? or because it had originated outside from any academic context? Its birth took place thirty years ago exactly. G. Matheron supervised my PhD thesis, a work devoted to ore reserve estimation, for the iron deposit of Lorraine. The quality of ore was more related to its ability to be enriched, after appropriate milling than to the iron grade. Transposing the tools of geostatistics, I decided to compute variograms on ore thin sections, and in order to do so, to construct a digital device. Thanks to this first “Texture Analyser”, developed in cooperation with J .-C. Klein, I understood that such different operations as covariance, chord length distribution, perimeter mea- surement, or particle counting were particular cases of a unique concept, which I called Hit or Miss Transform (Serra, 19656; Serra, 1967; Haas, Matheron & Serra, 1967).

In the meantime, on a more theoretical level, G. Matheron had undertaken the study of permeability for porous media in relation with their geometry (or their ‘texture’). When we look, today, at the publication he made following this first work (Matheron, 1967), the morphological aspect clearly prevails over the hydro- dynamics part. For the first time, the notion of a morphological opening was in- troduced and associated with the convexity of the structuring element, leading to granulomet.ry. In parallel, a random approach was explored, via the Boolean and the semi-Markov models, which also appeared for the first time.

Three years after the publication of Elbnents pour une theorie des milieux poreux, we realized that our nonlinear approach was in line with Integral Geometry, and that G. Matheron had rediscovered Steiner formula and Minkowski functionals: the history of ideas is nonlinear either.

Finally, this first period yielded, besides a first set of result, a certain sketch for the future, namely:

– the wish to develop theory from actual (physical) issues,

– the primacy given to ‘hit or miss’ type relationships,

– the cross-fertilization between deterministic and random approaches,

– the symbiosis between method development and system design.

Also, one evening of winter 1966, in a pub of Nancy, following a full-day lecture on probabilities, and perhaps a few pints of beer, G. Matheron, Ph. Formery and I, decided to call “Mathematical Morphology” the foreseen method.

The seventies

An institutional basis was provided by the Ecole des Mines de Paris. They had received substantial funds from the government, in order to create centres of applied research, and the city of Fontainebleau had offered room for these scientific activities. Our application was accepted, and the Centre de Morphologie Mathematique was born in April 1968, in the building it still occupies today. We were ten people (including staff and the first, four PhD students), under the direction of G. Matheron. This was the anchoring point. Very soon, it turned out that the chaining of successive hit or miss transforms actually generated new operations such as particle reconstruction. This resulted in a second patent in 1970 (Serra, 1970), and in the Texture Analysis System of the German company Leitz. This system has probably been one of the most important ones in image processing, if we consider the turnover (30 to 50 million dollars), and surely a long life record (12 years).

On the theoretical level, the seventies were marked by G. Matheron’s work: topo- logical foundations, random sets, increasing mappings, convexity, several models of random sets, etc. Part of this material became the subject of a second book (Math- eron, 1975). On the level of operators, it can be said that the core of the mor- phological tool box was discovered during this period (except for morphological filtering). Based on iterative processing, binary thinning, skiz, ultimate erosion, conditional bisector and their geodesic framework were introduced. Meanwhile, the initial set-oriented approach was extended to numerical functions, giving birth to morphological gradient, top hat transform and watershed, in particular. The main actors of this development were S. Beucher, H. Digabel, D. Jeulin, J-C. Klein, Ch. Lantuejoul, F. Meyer and J. Serra (a list of the first papers covering each topic is given in the references).

Although, the centre was already known in the field of geometrical probability (see the proceedings of Buffon’s symposium (Serra, 1977)) our work was practically not known to the community of signal (or image) processing. This is perhaps because the Leitz-TAS, in spite of its success, reached mainly the world of users, and often of naturalists. A contrario, this demonstrates that the scientists who adopted mor-APPENDIX A 371 phology at the beginning of the seventies (G.S. Watson, R.M. Raralick, M. Coster, J.-L. Chermant, J.-C. Binet, among others) denoted a real independent mind.

The eighties

Four events marked this decade, namely

– the opening to the out.side world, and especially to the Unit.ed States,

– the setting up of Mathemat.ical Morphology in the convenient mathematical framework of lattices,

– algorithmic developments and

– the renewal of random processes.

The opening to the outside world was produced by both a book and a man. The first volume of Image Analysis and Mathematical Morphology reflected t.he state of the art in 1980 at Fontainebleau (40% of the book had not been published before, another 40% came from Fontainebleau school but was not well known, the rest came from other sources). The person was S.R. Sternberg. Re liked the way of thinking in Mathematical Morphology, adopted it, and organized a number of courses on the subject at Ann Arbor (1980-1985). I also co-organized three of t.hose courses with him, and participated in t.wo others ..

This sudden broadening came as new fields opened to apply Mathematical Mor- phology. The oil crisis had resulted in the development of aut.omated visual inspec- tion, and t.he method could obviously provide means to solve part of such tasks. At Fontainebleau, in 1984 and 1986, two opportunities to create companies occurred.

They led to launch MorphoSystems (finger print recognition, 200 people in 1994) and Noesis (image processing, 25 people in 1994). As another consequence of this broadening, about ten research centres were created in Europe, America and Aus- tralia. For the first time, subst.ant.ial developments in morphology stemmed from other sources than Fontainebleau.

The second typical feat.ure of the eighties was the setting of t.he method (at least of its det.erministic aspect) in the mathematical framework of complete lattices.

The variety of applications brought us back t.o theoretical reflect.ion. Although the initial operat.ors were set oriented and translation invariant. They were now trans- posed to other sit.uations and to other objects (graphs, numerical functions), where translation might influence the process (geodesy, edge condit.ions) or even not exist (graphs). Finally, the core of essential axioms could be reduced to the complete lattice structure.

In 1986, I worked out a new formulat.ion of Mathematical Morphology on this basis, and tried to figure the addit.ional assumptions necessary for some particu- lar notions. For example, the concept of a connectivity needed a lattice of P( E) type, but no additional requirement. It is this reorganization that led G. Math- eron and myself to the theory of morphological filt.ering. A contributed book (Serra ed., 1988) gathered these advances. interpreters to renew stochast.ic approaches ap- peared in the lat.e seventies through the works of D. Jeulin and J. Serra on Boolean functions. During the nineties, it continued on bot.h levels of theory and applica- tions (D. Schmitt, F. Pret.eux), while D. Jeulin explored new models, (conditional) simulation, and lattice gas approaches.

The third characteristic of the eighties concerned the emphasis put on algorith- mics. It has its root in the relative growth of morphological software packages, versus dedicated processors. They concerned elementary operations, such as binary dilation, or sophisticated ones such as watershed. The classical data flow was con- veniently replaced by edge tracking, (hierarchical) queues, arrow propagation and rewriting. At the Centre, this activity was mainly associated with the names of S. Beucher, F. Meyer, M. Schmitt and L. Vincent. They benefited from the extraor- dinary improvements in computation and processing speed, during the decade. But, paradoxically, this acceleration urged them to speed up even more.

The nineties

We do not have the required distance to step back and evaluate the present time. However, two major trends can be discerned at Fontainebleau Centre. First, the pre- dominant role devoted to motion analysis: it concerns both encoding and description of moving scenes. Second, the permanent symbiosis between algorithms and hard- ware architectures has continued (J-C. Klein, M. Bilodeau, R. Peyrard, Ch. Gratin), as well as the design of operators for numerical functions (M. Grimaud, L. Vincent, P. Soille).

Conclusion

The future of a theory and a praxis generally escapes their founders (fortunately so!). As a method for artificial vision, Mathematical Morphology will be, and already is, trapped by its inability to catch the universe of meanings and the symbolic representations of the human mind. If it turns out to be, sometimes, more efficient than other approaches in pattern recognition, this comes from a better hold on the geometry of the scenes under study, but nothing more.

On the other hand, physics, or biology, offer situations where the method may be fruitful. An example is given by the lattice gas, which combines morphological operators and digital substitutes for partial derivative equations in a very subtle way. Another example is given by the current trends to give diffel’ential expressions to Minkowski operations. More basically, there are so many natural phenomena that are managed by sup/inf type relationships (possibly combined with other laws) that one can hope Mathematical Morphology will continue to be useful.

Last word: although this overview has, on purpose, focused on the contributions of Fontainebleau School, and on the first appearances of the concepts, it is clear that Mathematical Morphology is not reduced, today, to this particular group. The amount of publications in the field, and the recent books from Dougherty (1993), Schmitt & Matioli (1994), or Heijmans (1994) attest it. But the proof of this dy- namism will be given during these three days: it is the workshop it,self.

References

Beucher, S. (1982), Watersheds of functions and picture segmentation, in ‘IEEE Int. Conf. on

Acoustics, Speech and Signal Processing’, Paris, pp. 1928-1931. [Examples, and use of water-

shed on gradients]. APPENDIX A 373

Beucher, S. (1990), Segmentation d’images et morphologie mathematique, PhD thesis, Ecole des

Mines de Paris. [First apparition of the combination of connected operators and watersheds, in

a hierarchical way, constitutes a compendium of watershed performances and applications].

Beucher, S. & Bilodeau, M. (1992), ‘Road tracking, lane segmentation and obstacles recognition

by mathematical morphology’, Proc. oj Intelligent Vehicles ’92, IEEE.

Beucher, S. & Lantuejoul, C. (1979), Use of watershed in contour detection, Rennes, France. [First

publication of the watershed for numerical functions].

Bilodeau, M. (1992), Architecture logicielle pour processeur de morphologie mathematique, PhD

thesis, Ecole des Mines de Paris.

Digabel, H. & Lantuejoul, C. (1978), Iterative algorithms, in J.-L. Chermant, ed., ‘Sonderbande

der Praktischen Metallographie’, Dr. Riederer-Verlag GmbH, Stuttgart, pp. 85-99. [First pub-

lication of the Skiz and of the watershed, the later presented as a set oriented notion].

Dougherty, E., ed. (1993), Mathema.tical morphology in image processing, Marcel Dekker.

Gratin, C. (1993), De la representation des images au traitement morphologique des images tridi-

mensionnelles, PhD thesis, Ecole des Mines de Paris.

Grimaud, M. (1992), New measure of cont.rast: dynamics, in P. Gader, E. Dougherty & J. Serra,

eds, ‘Image algebra and morphological image processing III’, Vol. SPIE-1769, pp. 292-305.

[First publication, in English, of the notion of the dynamics].

Haas, A., Matheron, G. & Serra, J. (1967), ‘Morphologie mathematique et granulometries en place’,

Annales des Mines 11 and 12, 736-753 and 768-782. [First publication of the connectivity

numbers and of linear opening].

Heijmans, H. (1994), Morphological image operators, Advances in Electronics and Electron Physics,

Academic Press.

Jeulin, D. (1989), ‘Morphological modelling of images by sequential random functions’, Signal

Processing 16, 401-431. [First publication in English of sequential random functions].

Jeulin, D., Vincent, L. & Serpe, G. (1992), ‘Propagation algorithms on graphs for physical appli-

cations’, Journal oj Visual Communication and Image Representation 3(2), 161-181.

Klein, J. C. (1976), Conception et realisation d’une unite logique pour l’analyse quantitative

d’images, PhD thesis, Universite de Nancy. [First publication of geodesic methods].

Lantuejoul, C. (1978), La squelettisation et son application aux mesures topologiques des mosaiques

polycristallines, PhD thesis, Ecole des Mines de Paris. [First theory of the Skiz].

Lantuejoul, C. & Beucher, S. (1981), ‘On the use of the geodesic metric in image analysis’, Journal

oj Microscopy 121, 39-49. [First theory of the geodesy].

Matheron, G. (1967), Elements pour une theorie des milieux poreux, Masson, Paris.

Matheron, G. (1975), Random sets and integml geometry, Wiley.

Meyer, F. (1978), Contrast feature extraction, in J.-L. Chermant, ed., ‘Sonderbande der Praktischen

Metallographie’, Vol. 8, Dr. Riederer-Verlag GmbH, Stuttgart, pp. 374-380. [First publication

of the top hat transform and of gradient by erosion].

Meyer, F. (1979), Cytologie quantitative et morphologie mathematique, PhD thesis, Ecole des

Mines de Paris. [Various notions applied to cytology, first publication of conditional bisector].

Meyer, F. & Beucher, S. (1990), ‘Morphological segmentation’, Journal oj lIisual Communication

and Ima.ge Representation 1 (1), 21-46.

Meyer, F. & Serra, J. (1989), ‘Contrasts and activity lattice’, Signal Processing 16, 303-317. [First

publication of idempotent contrast operators].

Preteux, F. (1987), Description et interpretation des images par la morphologie mathemathique.

Application a l’imagerie medicale, PhD thesis, Universite de Paris 6.

Salembier, P. & Serra, J. (1992), Morphological multiscale image segmentation, in ‘SPIE Visual

Communications and Image Processing 92′, Boston, USA, pp. 620-631. [First apparition of the

combination of connected operators and watersheds, in a hierarchical approach].

Schmitt, M. (1989), Des algorithmes morphologiques a l’intelligence artificielle, PhD thesis, Ecole

des Mines de Paris. [First publication of the chain and loop algorithms for binary dilation and

for artificial intelligence in mathematical morphology].

Schmitt, M. & Matioli, J. (1994), Morphologie mathematique, Masson, Paris.

Serra, J. (1965a), ‘Automatic scanning device for analyzing textures’. [Inventor, granted to IRSID.

Priority date: July 2, 1965, France. Patented in: Belgium, Canada, Great-Britain, Japan,

Sweden, USA].

Serra, J. (1965b), L’analyse des textures par la geometrie aleatoire, Technical report, Comptes-

rendus du Comite Scientifique de I’IRSID.