The Viscous Watershed Transform

The watershed transform is the basic morphological tool for image segmentation. Watershed lines, also called divide lines, are a topographical concept: a drop of water falling on a topographical surface follows a steepest descent line until it stops when reaching a regional minimum. Falling on a divide line, the same drop of water may glide towards one or the other of both adjacent catchment basins. For segmenting an image, one takes as topographic surface the modulus of its gradient: the associated watershed lines will follow the contour lines in the initial image. The trajectory of a drop of water is disturbed if the relief is not smooth: it is undefined for instance on plateaus. On the other hand, each regional minimum of the gradient image is the attraction point of a catchment basin. As gradient images generally present many minima, the result is a strong oversegmentation. For these reasons a more robust scheme is used for the construction of the watershed based on flooding: a set of sources are defined, pouring water in such a way that the altitude of the water increases with constant speed. As the flooding proceeds, the boundaries of the lakes propagate in the direction of the steepest descent line of the gradient. The set of points where lakes created by two distinct sources meet are the contours. As the sources are far less numerous than the minima, there is no more oversegmentation. And on the plateaus the flooding also is well defined and propagates from the boundary towards the inside of the plateau. Used in conjunction with markers, the watershed is a powerful, fast and robust segmentation method. Powerful: it has been used with success in a variety of applications. Robust: it is insensitive to the precise placement or shape of the markers. Fast: efficient algorithms are able to mimic the progression of the flood. In some cases however the resulting segmentation will be poor: the contours always belong to the watershed lines of the gradient and these lines are poorly defined when the initial image is blurred or extremely noisy. In such cases, an additional regularization has to take place. Denoising and filtering the image before constructing the gradient is a widely used method. It is however not always sufficient. In some cases, one desires smoothing the contour, despite the chaotic fluctuations of the watershed lines. For this two options are possible. The first consists in using a viscous fluid for the flooding: a viscous fluid will not be able to follow all irregularities of the relief and produce lakes with smooth boundaries. Simulating a viscous fluid is however computationally intensive. For this reason we propose an alternative solution, in which the topographic surface is modified in such a way that flooding it with a non viscous fluid will produce the same lakes as flooding the original relief with a viscous fluid. On this new relief, the standard watershed algorithm can be used, which has been optimized for various architectures. Two types of viscous fluids will be presented, yielding two distinct regularization methods. We will illustrate the method on various examples.Corinne Vachier received an engineer degree from the Ecole Supérieure dElectricité, Paris and a Ph.D. in Mathematical Morphology from the Ecole des Mines de Paris, respectively in 1991 and 1995. From 1992 to 1995, she was research engineer in General Electric Medical Systems, Buc, France and phd student in the Centre de Morphologie Mathématique (CMM) of the Ecole des Mines de Paris. She became in 1996 an associate professor at the University Paris 12. She joined Jean-Michel Morels Team at the Centre de Mathématiques et Leurs Applications (CMLA) at the Ecole Nationale Supérieure de Cachan in 2001. Her research interests include mathematical morphology with emphasis on multiscale representations. Current applicative interests are focused on medical imaging.Fernand Meyer got an engineer degree from the Ecole des Mines de Paris in 1975. He works since 1975 at the Centre de Morphologie Mathématique (CMM) of the Ecole des Mines de Paris, where he is currently director. His first research area was Early and automatic detection of cervical cancer on cytological smears, subject of his PhD thesis, obtained in 1979. He participated actively to the development of mathematical morphology: particle reconstruction, top-hat transform, the morphological segmentation paradigm based on the watershed transform and markers, the theory of digital skeleton, the introduction of hierarchical queues for high speed watershed computations, morphological interpolations, the theory of levelings, multiscale segmentation.     

A Road-Matching Method for Precise Vehicle Localization Using Belief Theory and Kalman Filtering

This paper describes a novel road-matching method designed to support the real-time navigational function of cars for advanced systems applications in the area of driving assistance. This method provides an accurate estimation of position for a vehicle relative to a digital road map using Belief Theory and Kalman filtering. Firstly, an Extended Kalman Filter combines the DGPS and ABS sensor measurements to produce an approximation of the vehicle’s pose, which is then used to select the most likely segment from the database. The selection strategy merges several criteria based on distance, direction and velocity measurements using Belief Theory. A new observation is then built using the selected segment, and the approximate pose adjusted in a second Kalman filter estimation stage. The particular attention given to the modeling of the system showed that incrementing the state by the bias (also called absolute error) of the map significantly increases the performance of the method. Real experimental results show that this approach, if correctly initialized, is able to work over a substantial period without GPS.Maan El Badaoui El Najjar was born in Tripoli-Lebanon in 1975. He received his engineer diploma and his M.S. degree in control system and automation from the Institut National Polytechnique de Grenoble, France, in 1999 and 2000 respectively and his Ph.D. degree in control system from the Université de Technologie de Compiègne, France, in 2003. He is research and teaching associate at the Heudiasyc laboratory of the Université de Technologie de Compiègne. His current research interests include robot localization, map-aided navigation techniques, sensor fusion and Bayesian estimation techniques.Philippe Bonnifait graduated from the Ecole Superieure d’Electronique de l’Ouest, France, in 1992 and received the Ph.D. degree in automatic control and computer science from the Ecole Centrale de Nantes, France, in 1997. He joined the Institut de Recherche en Communications et Cybernétique de Nantes (IRCCyN UMR 6597), France, in 1993. Since September 1998, he is with Heudiasyc UMR 6599, France, and he is Assistant Professor at the Université de Technologie de Compiègne. His current research interests are in intelligent outdoor vehicles, with particular emphasis on applications to dynamic localisation.     

Geodesic Matching with Free Extremities

In this paper, we describe how to use geodesic energies defined on various sets of objects to solve several distance related problems. We first present the theory of metamorphoses and the geodesic distances it induces on a Riemannian manifold, followed by classical applications in landmark and image matching. We then explain how to use the geodesic distance for new issues, which can be embedded in a general framework of matching with free extremities. This is illustrated by results on image and shape averaging and unlabeled landmark matching. Laurent Garcin is a former student of the Ecole Polytechnique. He obtained his Ph.D. in 2004 at the Ecole Normale de Cachan, working on matching methods for landmarks and images. He is an engineer at the French National Geographic Institute. Laurent Younes is a former student of the Ecole Normale Superieure in Paris. He was awarded the Ph.D. from the University Paris Sud in 1989, and the thesis advisor certification from the same university in 1995. He works on the statistical analysis of images and shapes, and on modeling shape deformations and shape spaces. Laurent Younes entered CNRS, the French National Research Center in October 1991, in which he has been a “Directeur de Recherche" until 2003. He is now a professor at the Department of Applied Mathematics and Statistics Department and the Center for Imaging Science at Johns Hopkins University in July 2003.     

A database for linguists: Intelligent querying and increase of data

What do database (DB) querying and information retrieval imply for linguistics? What are data for the linguist? How can one envisage efficient access to data? I propose that DB querying in language sciences be designed linguistically and directly determined by linguistic data. Linguists from various backgrounds could then use a consensual query tool. An implemented data-directed DB querying system, which was developed for research on French interrogative structures, is presented in detail.Rachel Panckhurst teaches and researches in computational linguistics at the Université Paul Valéry-Montpellier III, France. Her research interests include natural language processing and information retrieval systems. She is currently devising a computer-assisted classification system for verbal subcategorization in French. She received her PhD (doctorat nouveau régime) in computational linguistics in December 1990 (Université Clermont II). Recent works include: Scatlex: une aide informatisée pour la construction d'entrées lexicales verbales, ICO Québec: Hiver 1993, pp. 61–67; Comment allier les besoins du linguiste et l'utilisation intelligente de bases de données? CIL '92 Proceedings, Québec, September 1993, pp 301–304.This article is a revised and extended English version of a paper in French, Comment allier les besoins du linguiste et l'utilisation intelligente de bases de données, Proceedings of the XVth International Congress of Linguists, Québec, August 1992, pp. 301–304, and was written during a post-doctoral fellowship (AUPELF-UREF) at the Centre d'ATO-CI, (Recherche et développement en linguistique computationnelle (RDLC)), Université du Québec à Montréal. The paper is adapted from part of Chapter 4 of a doctoral dissertation, Panckhurst, 1990. Many thanks are due to Jean-Marie Marandin who first encouraged me to write the paper and who read and gave constructive criticism on a previous version. I would also like to thank Sophie David and Claude Ricciardi Rigault (French version) and Fay Panckhurst (English version) for their helpful remarks. Finally, an anonymous reviewer provided constructive criticism, for which I am grateful. Any remaining errors are of course my own.     

Mapping dynamic programming onto modular linear systolic arrays

Summary In this paper we propose a novel way of deriving a family of fully-pipelined linear systolic algorithms for the computation of the solutions of a dynamic programming problem. In many instances, modularity is an important feature of these algorithms. One may simply add more processors to the array as the size of the problem increases. Each cell has a fixed amount of local storage and the time delay between two consecutive cells of the array is constant. The time complexity and the number of cells in our array tend ton ²+O(n) andn ²/ +O(n), respectively, as increases. This represents the best known performance for such an algorithm. Jean Frédéric Myoupo received his B.Sc in mathematics from the University of Yaounde, Cameroon, in 1980, and the M.S. and Ph.D. degrees both in applied mathematics from the Université Paul Sabatier de Toulouse, France in 1981 and 1983 respectively. From 1983 to 1985, he was lecturer at the Université de Sherbrooke, Québec, Canada. From 1985 to 1990, he was Assistant-Professor at the University of Yaounde, Cameroon. Since October 1990, he has been Associate-Professor in the department d'Informatique and Laboratoire de Recherche en Informatique (L.R.I.) of the Université de Paris-Sud, France. His current research interests include design of systolic algorithms and architectures, parallel and distributed processing.     

A new method for implementing moment functions in a CMOS retina

We present in this paper a new method for implementing geometric moment functions in a CMOS retina. The principle is based on the similarity between geometric moment equations and the measurement of the correlation value between an image to analyze and a range of grey levels. The latter is approximated by a binary image called mask using a dithering algorithm in order to reduce hardware implementation cost. The correlation product between the mask and the image under analysis gives an approximated value of the geometric moment with an error less than 1% of the exact value. Finally, the results obtained by our approach have been applied to an object localization application and the localization error due to the approximated moment values reported. Olivier Aubreton was born in Vichy on August 31, 1973. He obtained the agrégation examination in June 2000 and received the D.E.A. degree (equivalent to a master degree) in image processing in June 2001. He is currently a lecturer working towards a Ph. D. degree at Laboratory LE2I in the IUT of Le Creusot in Burgundy. His research interests include the design, development implementation, and testing of silicon retinas for pattern matching and pattern recognition. Lew F.C. Lew Yan Voon received his Ph.D. degree in Computer Aided Design of VLSI circuits from Montpellier University, France, in March 1992. Since September 1993, he has been first assistant professor and then associate professor at the University of Burgundy. His research interests lie in the field of pattern recognition and in the design of silicon retinas in standard CMOS technology for real-time inspection by machine vision. Bernard Lamalle was born in Autun on May 1, 1946. He obtained the Ph.D. degree in 1973 from the Université de Bourgogne in Dijon. During 1980 to 2000 he has been Maître de conférences at the IUT of Le Creusot in Bourgogne. He joined the image processing team of laboratory Le2i in 1992. Since 2000, he has been appointed full professor of the University of Bourgogne. His field of interest is principally the study and design of silicon retinas dedicated to industrial control. He has in charge some industrial contracts in the field of quality control by artificial vision and he holds two patents in the field of image processing and smart sensors. Guy Cathébras was born in Uzès, France, in 1961. He received the French engineer degree from the Ecole Nationale Supérieure de l'Electronique et de ses Applications, Cergy, France, in 1984 and the Diplôme de Doctorat de l'Université de Montpellier, France, in 1990. Since 1992 he is an assistant professor of microelectronics at the Institut des Sciences de l'Ingénieur de Montpellier. His current research interests include the design of imagers and silicon retinas using standard CMOS technologies.     

Computability by finite automata and pisot bases

We prove that the function of normalization in base , which maps any -representation of a real number onto its -development, obtained by a greedy algorithm, is a function computable by a finite automaton over any alphabet if and only if is a Pisot number.Christiane Frougny was supported in part by the PRC Mathématiques et Informatique of the Ministère de la Recherche et de l'Espace.     

Image Decomposition into a Bounded Variation Component and an Oscillating Component

We construct an algorithm to split an image into a sum u + v of a bounded variation component and a component containing the textures and the noise. This decomposition is inspired from a recent work of Y. Meyer. We find this decomposition by minimizing a convex functional which depends on the two variables u and v, alternately in each variable. Each minimization is based on a projection algorithm to minimize the total variation. We carry out the mathematical study of our method. We present some numerical results. In particular, we show how the u component can be used in nontextured SAR image restoration.Jean-François Aujol graduated from 1 Ecole Normale Supérieure de Cachan in 2001. He was a PHD student in Mathematics at the University of Nice-Sophia-Antipolis (France). He was a member of the J.A. Dieudonné Laboratory at Nice, and also a member of the Ariana research group (CNRS/INRIA/UNSA) at Sophia-Antipolis (France). His research interests are calculus of variations, nonlinear partial differential equations, numerical analysis and mathematical image processing (and in particular classification, texture, decomposition model, restoration). He is Assistant Researcher at UCLA (Math Department).Gilles Aubert received the These dEtat es-sciences Mathematiques from the University of Paris 6, France, in 1986. He is currently professor of mathematics at the University of Nice-Sophia Antipolis and member of the J.A. Dieudonne Laboratory at Nice, France. His research interests are calculus of variations, nonlinear partial differential equations and numerical analysis; fields of applications including image processing and, in particular, restoration, segmentation, optical flow and reconstruction in medical imaging.Laure Blanc-Féraud received the Ph.D. degree in image restoration in 1989 and the Habilitation á Diriger des Recherches on inverse problems in image processing in 2000, from the University of Nice-Sophia Antipolis, France. She is currently director of research at CNRS in Sophia Antipolis. Her research interests are inverse problems in image processing by deterministic approach using calculus of variation and PDEs. She is also interested in stochastic models for parameter estimation and their relationship with the deterministic approach. She is currently working in the Ariana research group (I3S/INRIA) which is focussed on Earth observation.Antonin Chambolle studied mathematics and physics at the Ecole normale Supérieure in Paris and received the Ph.D. degree in applied mathematics from the Université de Paris-Dauphine in 1993. Since then he has been a CNRS researcher at the CEREMADE, Université de Paris-Dauphine, and, for a short period, a researcher at the SISSA, Trieste, Italy. His research interest include calculus of variations, with applications to shape optimization, mechanics and image processing.     

Using Ancillary Text to Index Web-based Multimedia Objects

PériCulture is the name of a research project at theUniversité de Montréal which is part of a largerproject based at the Université de Sherbrooke. The parentproject aimed to form a research network for managing Canadiandigital cultural content. The general research objective ofPériCulture was to study indexing methods for web-basednon-textual cultural content, specifically still images. Theresearch results reported here build on work in image indexingand automatic (text) indexing by studying properties of textassociated with images in a networked environment to try togain some understanding of how the ancillary text associatedwith images on web pages can be exploited to index the correspondingimages. We studied this question in the context of selectedweb sites, i.e. that contained multimedia objects, that hadtext associated with these objects (broader than file namesand captions), that were bilingual (English and French), andthat housed Canadian digital cultural content. We identifiedkeywords that were useful in indexing and studied their proximityto the object described. Potential indexing terms were identifiedin various HTML tags and full text (each considered a differentsource of ancillary text). Our study found that a large numberof useful indexing terms are available in the ancillary textof many web sites with cultural content, and that ancillarytext of different sources have variable usefulness in retrieval.Our results suggest that these terms can be manipulated in anumber of ways in automated retrieval systems to improve searchresults.     

Comparison of musical sequences

Concepts from the theory of sequence comparison are adapted to measure the overall similarity or dissimilarity between two musical scores. A key element is the notion of consolidation and fragmentation, different both from the deletions and insertions familiar in sequence comparison, and from the compressions and expansions of time warping in automatic speech recognition. The measure of comparison is defined so as to detect similarities in melodic line despite gross differences in key, mode or tempo. A dynamic programming algorithm is presented for calculating the measure, and is programmed and applied to a set of variations on a theme by Mozart. Cluster analysis and spatial representation of the results confirm subjective impressions of the patterns of similarities among the variations. A generalization of the algorithm is presented for detecting locally similar portions in two scores, and is then applied.Marcel Mongeau obtained his B.Sc. and M.Sc. degrees at the Université de Montréal and is currently completing his doctorate at the University of Waterloo.David Sankoff (Ph.D., McGill) is a Professor in the Département de mathématiques et statistique and is also attached to the Centre de recherches mathématiques at the Université de Montréal. His research intersts include sociolinguistics — specifically the quantitative approach inherent in linguistic variation theory — statistical classification theory, biomathematics and computational biology — particularly algorithms for macromolecular sequence analysis and the reconstruction of phylogenetic trees.     

Multi-Modal Locomotion Robotic Platform Using Leg-Track-Wheel Articulations

Other than from its sensing and processing capabilities, a mobile robotic platform can be limited in its use by its ability to move in the environment. Legs, tracks and wheels are all efficient means of ground locomotion that are most suitable in different situations. Legs allow to climb over obstacles and change the height of the robot, modifying its viewpoint of the world. Tracks are efficient on uneven terrains or on soft surfaces (snow, mud, etc.), while wheels are optimal on flat surfaces. Our objective is to work on a new concept capable of combining different locomotion mechanisms to increase the locomotion capabilities of the robotic platform. The design we came up with, called AZIMUT, is symmetrical and is made of four independent leg-track-wheel articulations. It can move with its articulations up, down or straight, allowing the robot to deal with three-dimensional environments. AZIMUT is also capable of moving sideways without changing its orientation, making it omnidirectional. By putting sensors on these articulations, the robot can also actively perceive its environment by changing the orientation of its articulations. Designing a robot with such capabilities requires addressing difficult design compromises, with measurable impacts seen only after integrating all of the components together. Modularity at the structural, hardware and embedded software levels, all considered concurrently in an iterative design process, reveals to be key in the design of sophisticated mobile robotic platforms.This research is supported financially by the Canada Research Chair (CRC) program, the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canadian Foundation for Innovation (CFI) and the Faculty of Engineering of the Université de Sherbrooke. Patent pending.François Michaud is the Canada Research Chairholder in Autonomous Mobile Robots and Intelligent Systems, and an Associate Professor at the Department of Electrical Engineering and Computer Engineering of the Université de Sherbrooke. He is the principal investigator of LABORIUS, a research laboratory working on applying AI methodologies in the design of intelligent autonomous systems that can assist humans in everyday lives. His research interests are architectural methodologies for intelligent decision making, autonomous mobile robotics, social robotics, robot learning and intelligent systems. He received his bachelors degree, Masters degree and Ph.D. degree in Electrical Engineering from the Université de Sherbrooke. He is a member of IEEE, AAAI and OIQ (Ordre des ingénieurs du Québec).Dominic Létourneau has a Bachelor degree in Computer Engineering and a Masters degree in Electrical Engineering from the Université de Sherbrooke. Since 2001, he is a research engineer at the LABORIUS Mobile Robotics and Intelligent Systems Laboratory. His research interests cover combination of systems and intelligent capabilities to increase the usability of autonomous mobile robots in the real world. His expertise lies in artificial vision, mobile robotics, robot programming and integrated design. He is a member of OIQ (Ordre des ingénieurs du Québec).Martin Arsenault has a Bachelor degree in Mechanical Engineering and from the Université de Sherbrooke. For AZIMUT, he developed the Direction subsystem.Yann Bergeron is a Mechanical Junior Engineer working in a consulting engineering firm, Groupe HBA. His field of activity is most oriented in industrial projects and construction. He received his bachelors degree in Mechanical Engineering from the University de Sherbrooke. For AZIMUT, he worked on the Track-Wheel subsystem. He is a member of OIQ (Ordre des ingénieurs du Québec) and JECQ (Jeunes entrepreneurs du Centre-du-Québec).Richard Cadrin has a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke. For AZIMUT, he worked on the Propulstion subsystem.Frédéric Gagnon has a Bachelor degree in Mechanical Engineering and from the Université de Sherbrooke. For AZIMUT, he designed the chassis and worked on the integration of the articulations, the bodywork and the hardware. He is currently a research engineer at LABORIUS, working on AZIMUTs second prototype and other robotic projects. He also contributes in a mobile robotic.Marc-Antoine Legault has a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke, and is currently pursuing a Masters degree at LABORIUS on serial-elastic actuators. He worked on AZIMUTs Propulsion subsystem. He also works on the design of other mobile robotic platforms. He is a member of OIQ (Ordre des ingénieurs du Québec).Mathieu Millette has a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke. For AZIMUT, he developed the Tensor subsystem and he designed and integrated the battery support inside the chassis. He is now working as a junior mechanical engineer in process and technical development in a third sector mill.Jean-François Paré graduated in Mechanical Engineering from the Université de Sherbrooke. He is also trained as a professional coach from R.I.C.K. (Réseau International de Coaching Kokopelli). He launched is own business in individual coaching, team coaching, team building and coaching workshops. For businesses and individuals, he assists people in reaching their well-being and efficiency and to manifest their leadership.Marie-Christine Tremblay has obtained a Bachelor degree in Mechanical Engineering from the Université de Sherbrooke. As a part of the AZIMUTõs team, she contributed the Track-Wheel subsystem and developed a new track with high adherence and wear resistance to climb stairs. She is working in the Engineering Department at Hydra-Fab Industriel, a company conceiving electro-hydraulic systems for high speed trains.Pierre Lepage has a Computer Engineering degree from the Université de Sherbrooke. For AZIMUT, he designed the user interface to control the robot and the propulsion system. He is currently a research engineer at LABORIUS, working on AZIMUTs second prototype and other robotic projects. He is involved in research projects on coordinated behavior of a group of mobile robots. He is also actively involved in a mobile robotic startup.Yan Morin has an Electrical Engineering degree from the Université de Sherbrooke. For AZIMUT, he designed the electrical interface to control the motors of the robot. He is currently a research engineer at LABORIUS, working on AZIMUTs second prototype and other robotic projects. He is also actively involved in a mobile robotic startup.Jonathan Bisson has a Bachelor degree in Computer Engineering and a Masters degree in Electrical Engineering from the Université de Sherbrooke. His contribution to AZIMUT was on the modular distributed computing architecture. His expertise lies in electronics, motor control, embedded systems and ultrasonic transducers.Serge Caron is technician in computer systems at the Department of Electrical Engineering and Computer Engineering of the Universit de Sherbrooke. His interests are in designing mobile robotic platforms, from four-legged to wheeled robots. He is also a writer for hobbyist robotic journals.     

Stable methods for recognizing acronym-expansion pairs: from rule sets to hidden Markov models

A significant portion of currently available documents exist in the form of images, for instance, as scanned documents. Electronic documents produced by scanning and OCR software contain recognition errors. This paper uses an automatic approach to examine the selection and the effectiveness of searching techniques for possible erroneous terms for query expansion. The proposed method consists of two basic steps. In the first step, confused characters in erroneous words are located and editing operations are applied to create a collection of erroneous error-grams in the basic unit of the model. The second step uses query terms and error-grams to generate additional query terms, identify appropriate matching terms, and determine the degree of relevance of retrieved document images to the user's query, based on a vector space IR model. The proposed approach has been trained on 979 document images to construct about 2,822 error-grams and tested on 100 scanned Web pages, 200 advertisements and manuals, and 700 degraded images. The performance of our method is evaluated experimentally by determining retrieval effectiveness with respect to recall and precision. The results obtained show its effectiveness and indicate an improvement over standard methods such as vectorial systems without expanded query and 3-gram overlapping. Youssef Fataicha received his B.Sc. degree from Université de Rennes1, Rennes, France, in 1982. In 1984 he obtained his M.Sc. in computer science from Université de Rennes1, France. Between 1984 and 1986 he was a lecturer at the Université de Rennes1, France. He then served as engineer, from 1987 to 2000, at {Office de l'eau potable et de l'électricité} in Morocco. Since 2001 has been a Ph.D. student at the {école de Technologie Supérieure de l'Université du Québec} in Montreal, Québec, Canada. His research interests include pattern recognition, information retrieval, and image analysis. Mohamed Cheriet received his B.Eng. in computer science from {Université des Sciences et de Technologie d'Alger} (Bab Ezouar, Algiers) in 1984 and his M.Sc. and Ph.D., also in computer science, from the University of Pierre et Marie Curie (Paris VI) in 1985 and 1988, respectively. Dr. Cheriet was appointed assistant professor in 1992, associate professor in 1995, and full professor in 1998 in the Department of Automation Engineering, {école de Technologie Supérieure} of the University of Québec, Montreal. Currently he is the director of LIVIA, the Laboratory for Imagery, Vision and Artificial Intelligence at ETS, and an active member of CENPARMI, the Centre for Pattern Recognition and Machine Intelligence. Professor Cheriet's research focuses on mathematical modeling for signal and image processing (scale-space, PDEs, and variational methods), pattern recognition, character recognition, text processing, document analysis and recognition, and perception. He has published more than 100 technical papers in these fields. He was the co-chair of the 11th and the 13th Vision Interface Conferences held respectively in Vancouver in 1998 and in Montreal in 2000. He was also the general co-chair of the 8th International Workshop on Frontiers on Handwriting Recognition held in Niagara-on-the-Lake in 2002. He has served as associate editor of the International Journal of Pattern Recognition and Artificial Intelligence (IJPRAI) since 2000. Dr. Cheriet is a senior member of IEEE. Jian Yun Nie is a professor in the computer science department (DIRO), Université de Montreal, Québec, Canada. His research focuses on problems related to information retrieval, including multilingual and multimedia information retrieval, as well as natural language processing. Ching Y. Suen received his M.Sc. (Eng.) from the University of Hong Kong and Ph.D. from the University of British Columbia, Canada. In 1972 he joined the Department of Computer Science of Concordia University, where he became professor in 1979 and served as chairman from 1980 to 1984 and as associate dean for research of the Faculty of Engineering and Computer Science from 1993 to 1997. He has guided/hosted 65 visiting scientists and professors and supervised 60 doctoral and master's graduates. Currently he holds the distinguished Concordia Research Chair in Artificial Intelligence and Pattern Recognition and is the Director of CENPARMI, the Centre for Pattern Recognition and Machine Intelligence.Professor Suen is the author/editor of 11 books and more than 400 papers on subjects ranging from computer vision and handwriting recognition to expert systems and computational linguistics. A Google search on “Ching Y. Suen” will show some of his publications. He is the founder of the International Journal of Computer Processing of Oriental Languages and served as its first editor-in-chief for 10 years. Presently he is an associate editor of several journals related to pattern recognition.A fellow of the IEEE, IAPR, and the Academy of Sciences of the Royal Society of Canada, he has served several professional societies as president, vice-president, or governor. He is also the founder and chair of several conference series including ICDAR, IWFHR, and VI. He has been the general chair of numerous international conferences, including the International Conference on Computer Processing of Chinese and Oriental Languages in August 1988 held in Toronto, International Conference on Document Analysis and Recognition held in Montreal in August 1995, and the International Conference on Pattern Recognition held in Québec City in August 2002.Dr. Suen has given 150 seminars at major computer companies and various government and academic institutions around the world. He has been the principal investigator of 25 industrial/government research contracts and is a grant holder and recipient of prestigious awards, including the ITAC/NSERC award from the Information Technology Association of Canada and the Natural Sciences and Engineering Research Council of Canada in 1992 and the Concordia “Research Fellow” award in 1998.     

The lexical unit in the metal® MT system

This paper tackles some of the problems encountered while developing the French-English version of the Siemens-Nixdorf METAL^® computer-assisted translation system. The first part deals with the general problem of delimiting lexical units and the second part describes a few concrete translation problems and the solutions that have been adopted in this experimental transfer-based system. The role and importance of the lexicons is stressed, focussing more specifically on the possibility the lexicographer is given to manipulate complex structures and to control the translation process directly.This paper is a slightly revised adaptation of a French version which appears under the title L'unité lexicale dans le système de traduction assistée par ordinateur METAL, in Bouillon & Clas (eds)La Traductique, Les Presses de l'Université de Montréal, AUPELF/UREF, Collection Universités Francophones, pp. 364–376. We gratefully acknowledge the editors' permission to use this material here.     

Detecting feature interaction in CPL

This article addresses the problem of detecting feature interactions in the area of telephony systems design. The proposed approach consists of two phases: filtering and testing. The filtering phase detects possible interactions by identifying incoherencies in a logic specification of the main elements of the features, consisting of preconditions, triggers, results and constraints. If incoherencies are identified, then an interaction is suspected, test cases corresponding to the suspected interaction are generated and testing is applied to see if the interaction actually exists. Two case studies, carried out on established benchmarks, show that this approach gives good results in practice. Nicolas Gorse received a Master of Computer Science from the University of Ottawa, School of Information Technology and Engineering in 2001.He is currently a Ph.D. candidate in the Département d'Informatique et Recherche Opérationnelle of the Université de Montréal. His research interests relate to formal methods and their application in the design and verification of complex electronic systems at high levels of abstraction. Luigi Logrippo received a degree in law from the University of Rome (Italy) in 1961, and in the same year he started a career in computing. He worked for several computer companies and in 1969 he obtained a Master of Computer Science from the University of Manitoba, followed by a Ph.D. of Computer Science from the University of Waterloo in 1974.He was with the University of Ottawa for 29 years, where he was Chair of the Computer Science Department for 7 years. In 2002 he moved to the Université du Québec en Outaouais, Département d'Informatique et Ingénierie, while remaining associated with the University of Ottawa as an Adjunct Professor.His interest area is formal and logic-based methods and their applications in the design of communications systems. For a number of years he worked on the development of tools and methods for the language LOTOS. Current research deals with the formal analysis of advanced communications services made possible by internet telephony, of the policies that govern them, and of their interactions, in application areas such as presence features and e-commerce contracts. Jacques Sincennes is a research programmer/systems analyst at the University of Ottawa, School of Information Technology and Engineering. He has held this position for the past 17 years. He is coauthor of a number of papers and a patent application.An erratum to this article is available at .     

Combining Seminorms in Adaptive Lifting Schemes and Applications to Image Analysis and Compression

In this paper, we present some adaptive wavelet decompositions that can capture the directional nature of images. Our method exploits the properties of seminorms to build lifting structures able to choose between different update filters, the choice being triggered by the local gradient-type features of the input. In order to deal with the variety and wealth of images, one has to be able to use multiple criteria, giving rise to multiple choice of update filters. We establish the conditions under these decisions can be recovered at synthesis, without the need for transmitting overhead information. Thus, we are able to design invertible and non-redundant schemes that discriminate between different geometrical information to efficiently represent images for lossless compression methods. The work of Piella is supported by a Marie-Curie Intra-European Fellowships within the 6th European Community Framework Programme. Gemma Piella received the M.S. degree in electrical engineering from the Polytechnical University of Catalonia (UPC), Barcelona, Spain, and the Ph.D. degree from the University of Amsterdam, The Netherlands, in 2003. From 2003 to 2004, she was at UPC as a visiting professor. She then stayed at the Ecole Nationale des Telecommunications, Paris, as a Post-doctoral Fellow. Since September 2005 she is at the Technology Department in the Pompeu Fabra University. Her main research interests include wavelets, geometrical image processing, image fusion and various other aspects of digital image and video processing. Beatrice Pesquet-Popescu received the engineering degree in telecommunications from the “Politehnica” Institute in Bucharest in 1995 and the Ph.D. thesis from the Ecole Normale Supérieure de Cachan in 1998. In 1998 she was a Research and Teaching Assistant at Université Paris XI and in 1999 she joined Philips Research France, where she worked for two years as a research scientist, then project leader, in scalable video coding. Since Oct. 2000 she is an Associate Professor in multimedia at the Ecole Nationale Supérieure des Télécommunications (ENST). Her current research interests are in scalable and robust video coding, adaptive wavelets and multimedia applications. EURASIP gave her a “Best Student Paper Award” in the IEEE Signal Processing Workshop on Higher-Order Statistics in 1997, and in 1998 she received a “Young Investigator Award” granted by the French Physical Society. She is a member of IEEE SPS Multimedia Signal Processing (MMSP) Technical Committee and a Senior Member IEEE. She holds 20 patents in wavelet-based video coding and has authored more than 80 book chapters, journal and conference papers in the field. Henk Heijmans received his masters degree in mathematics from the Technical University in Eindhoven and his PhD degree from the University of Amsterdam in 1985. Since then he has been in the Centre for Mathematics and Computer Science, Amsterdam, where he had been directing the “signals and images” research theme. His research interest are focused towards mathematical techniques for image and signal processing, with an emphasis on mathematical morphology and wavelet analysis. Grégoire Pau was born in Toulouse, France in 1977 and received the M.S. degree in Signal Processing in 2000 from Ecole Centrale de Nantes. From 2000 to 2002, he worked as a Research Engineer at Expway where he actively contributed to the standardization of the MPEG-7 binary format. He is currently a PhD candidate in the Signal and Image Processing Departement of ENST-Telecom Paris. His research interests include subband video coding, motion compensated temporal filtering and adaptive non-linear wavelet transforms.     

Exact and approximation algorithms for sorting by reversals,with application to genome rearrangement

Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and areversal takes an arbitrary substring of elements, and reverses their order.For this problem, we develop two algorithms: a greedy approximation algorithm, that finds a solution provably close to optimal inO(n ²) time and0(n) space forn-element permutations, and a branch- and-bound exact algorithm, that finds an optimal solution in0(mL(n, n)) time and0(n ²) space, wherem is the size of the branch- and-bound search tree, andL(n, n) is the time to solve a linear program ofn variables andn constraints. The greedy algorithm is the first to come within a constant factor of the optimum; it guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch- and-bound algorithm are a novel application of maximum-weight matchings, shortest paths, and linear programming.In a series of experiments, we study the performance of an implementation on random permutations, and permutations generated by random reversals. For permutations differing byk random reversals, we find that the average upper bound on reversal distance estimatesk to within one reversal fork<1/2n andn<100. For the difficult case of random permutations, we find that the average difference between the upper and lower bounds is less than three reversals forn<50. Due to the tightness of these bounds, we can solve, to optimality, problems on 30 elements in a few minutes of computer time. This approaches the scale of mitochondrial genomes.This research was supported by a postdoctoral fellowship from the Program in Mathematics and Molecular Biology of the University of California at Berkeley under National Science Foundation Grant DMS-8720208, and by a fellowship from the Centre de recherches mathématiques of the Université de Montréal.This research was supported by grants from the Natural Sciences and Engineering Research Council of Canada, and the Fonds pour la formation de chercheurs et l'aide à la recherche (Québec). The author is a fellow of the Canadian Institute for Advanced Research.     

Quasi-Linear Algorithms for the Topological Watershed

The watershed transformation is an efficient tool for segmenting grayscale images. An original approach to the watershed (Bertrand, Journal of Mathematical Imaging and Vision, Vol. 22, Nos. 2/3, pp. 217–230, 2005.; Couprie and Bertrand, Proc. SPIE Vision Geometry VI, Vol. 3168, pp. 136–146, 1997.) consists in modifying the original image by lowering some points while preserving some topological properties, namely, the connectivity of each lower cross-section. Such a transformation (and its result) is called a W-thinning, a topological watershed being an ultimate W-thinning. In this paper, we study algorithms to compute topological watersheds. We propose and prove a characterization of the points that can be lowered during a W-thinning, which may be checked locally and efficiently implemented thanks to a data structure called component tree. We introduce the notion of M-watershed of an image F, which is a W-thinning of F in which the minima cannot be extended anymore without changing the connectivity of the lower cross-sections. The set of points in an M-watershed of F which do not belong to any regional minimum corresponds to a binary watershed of F. We propose quasi-linear algorithms for computing M-watersheds and topological watersheds. These algorithms are proved to give correct results with respect to the definitions, and their time complexity is analyzed.Michel Couprie received his Ingénieurs degree from the École Supérieure dIngénieurs en Électrotechnique et Électronique (Paris, France) in 1985 and the Ph.D. degree from the Pierre et Marie Curie University (Paris, France) in 1988. Since 1988 he has been working in ESIEE where he is an Associate Professor. He is a member of the Laboratoire Algorithmique et Architecture des Systémes Informatiques, ESIEE, Paris, and of the Institut Gaspard Monge, Universit é de Marne-la-Vallée. His current research interests include image analysis and discrete mathematics.Laurent Najman received his Ph.D. of applied mathematics from Paris-Dauphine university and an Ingénieurs degree from the Ecole des Mines de Paris. After earning his Ingénieurs degree, he worked in the research laboratories of Thomson-CSF for three years, before joining Animation Science in 1995, as director of research and development. In 1998, he joined OcÉ Print Logic Technolgies, as senior scientist. Since 2002, he is associate professor with the A2SI laboratory of ESIEE, Paris. His current research interest is discrete mathematical morphology.Gilles Bertrand received his Ingénieurs degree from the École Centrale des Arts et Manufactures in 1976. Until 1983 he was with the Thomson-CSF company, where he designed image processing systems for aeronautical applications. He received his Ph. from the École Centrale in 1986. He is currently teaching and doing research with the Laboratoire Algorithmique et Architecture des Systémes Informatiques, ESIEE, Paris, and with the Institut Gaspard Monge, Université de Marne-la-Vallée. His research interests are image analysis, pattern recognition, mathematical morphology and digital topology.     

Toward a narra-topography: A pilot study applied to Marguerite Duras' novelModerato Cantabile

Although lexical frequencies are familiar measures of stylistic and thematic analysis, only recently have some stylostatisticians been tempted to investigate the relationship between the frequency and topography of repeated lexical items. In the present paper the authors have turned to the study of the four focal types of discursive narratology, using Marguerite Duras'Moderato Cantabile. Their intent is to uncover aspects of narratological performance which further elucidate the communicative strategies in the story. Part 1 summarizes the problematic between frequency and topography. It describes how a topographical index can be computed for any repeated item and how a Global Topography Index (GTI) can summarize the major topographical characteristics of any text sequence. Part 2 presents a four-cell typology of narrational mode: a segmentation of the verbal chain into narrating and narrated speech acts, with each text sequence tagged according to its discursive function: overt sender intervention for story coherence or comment on the focal level of a narrating present; representation of discrete or unlocalized events on the focal level of a mimeticized past. In Part 3 the focal encodings are displayed in numerical and graphic form, first according to the eight surface chapter divisions and then according to twenty-six subsets of approximately equal length. The fluctuations of the topography indices are reviewed, with particular attention being paid to the manifestation of cluster effects. Although sender interventions predominate, the relativized behavior of each focal type contributes to a climactic unraveling of the intrigue in the final chapters. In conclusion, the authors stress the dichotomy between the calm surface of the chapters and the agitated tensions of the twenty-six subsets.Richard Frautschi, Professor of French at Penn State University, is co-authoring a bibliography of French prose fiction, 1700–1800, and is preparing a book on the theory and practise of quantified discourse focalization.Philippe Thoiron, Professor and Director of the Centre de Recherche en Terminologie et Traduction at the Université de Lyon-2, specializes in quantitative studies of vocabulary (lexical richness and topography of repeated items). He is also engaged in research on languages for specific purposes and terminology.     

Performance considerations in the parallel execution of numerical algorithms on two processors

Summary Loosely coupled multiprocessor systems seem to offer an interesting alternative to the solution of large numerical problems. It is in the context of such an investigation that we treat here a special parallel-processing case concerning the solution of a numerical problem on two independent processors including simultaneous input-output operations. We present a short discussion of the underlying numerical algorithm, a modelling approach to the parallel computing system and a comparison of the theoretically obtained results with simulation and experimental results. The experimental setting is the XANTHOS multi-microprocessor system implemented at the Laboratoire de Recherche en Informatique, Université de Paris-Sud.This work was supported by a DGRST Research Scholarship at Université Paris-Sud