International Journal of Pattern Recognition and Artificial Intelligence

Please refer to full tex.

The digital representation of an image requires a very large number of bits. The goal of image coding is to reduce this number, as much as possible, and to reconstruct a faithful duplicate of the original picture. Early efforts in image coding, solely guided by information theory, led to a plethora of methods. The compression ratio reached a plateau around 10: 1 a couple of years ago. Recent progress in the study of the brain mechanism of vision and scene analysis has opened new vistas in picture coding. Directional sensitivity of the neurones in the visual pathway combined with the separate processing of contours and textures has led to a new class of coding methods capable of achieving compression ratios as high as 100: 1. This paper presents recent progress on some of the main avenues of object-based methods. These second generation techniques make use of contour-texture modeling, new results in neurophysiology and psychophisics and scene analysis.

Three architectures of current interest—the pyramid, the linear array and the n-cube—are examined in relation to their ability to perform iconic and symbolic image processing. For each architecture an appropriate problem is identified and a matching implementation selected. An assessment of the characteristics of each implementation is given, together with an estimation of the performance on a number of fundamental operations. The relative merits of the designs are discussed but it is concluded that the success of a particular architecture depends crucially upon the type of application which is addressed, and that therefore no universally applicable ranking can be derived in the absence of a comprehensive benchmarking exercise.

The goal of high level vision is to identify a set of regions in a given image. This has been called by various names: the scene labeling problem’, the consistent labeling problem², the constraint satisfaction problem³, Waltz filtering⁴, the satisfying assignment problem⁵, etc.

There are several approaches to solve this problem, including backtracking, graph matching and relaxation. A new method called split-level relaxation, which is based on discrete relaxation was proposed in Ref. 6. It takes care of multiple semantic constraints by considering each of them independently. The problem is known to be NP-complete, so it takes a long time to solve. With the advent of multiprocessors, it is now imperative to see if the problem can be solved faster in the average case.

In this paper we give a framework for solving the scene analysis problem in a parallel processing environment, using split-level relaxation. Experiments done on a multiprocessor show that it is indeed advantageous to use multiprocessors to solve this problem.

Orientation selection is the inference of orientation information out of images. It is one of the foundations on which other visual structures are built, since it must precede the formation of contours out of pointillist data and surfaces out of surface markings. We take a differential geometric view in defining orientation selection and develop algorithms for actually doing it. The goal of these algorithms is formulated in mathematical terms as the inference of a vector field of tangents (to the contours), and the algorithms are studied in both abstract and computational forms. They are formulated as matching problems, and algorithms for solving them are reduced to biologically plausible terms. We show that two different matching problems are necessary, the first for 1-dimensional contours (which we refer to as Type I processes) and the second for 2-dimensional flows (or Type II processes).

Many investigations of image sequences can be understood on the basis of a few concepts for which computational approaches become increasingly available. The estimation of optical flow fields is discussed, exhibiting a common foundation for feature-based and differential approaches. The interpretation of optical flow fields is mostly concerned so far with approaches which infer the 3-D structure of a rigid point configuration in 3-D space and its relative motion with respect to the image sensor from an image sequence. The combination of stereo and motion provides additional incentives to evaluate image sequences, especially for the control of robots and autonomous vehicles. Advances in all these areas lead to the desire to describe the spatio-temporal development recorded by an image sequence not only at the level of geometry, but also at higher conceptual levels, for example by natural language descriptions.

We show in this article that when the environment is piecewise linear, it provides a powerful constraint on the kind of matches that exist between two images of the scene when the camera motion is unknown. For points and lines located in the same plane, the correspondence between the two cameras is a collineation. We show that the unknowns (the camera motion and the plane equation) can be recovered, in general, from an estimate of the matrix of this collineation. The two-fold ambiguity that remains can be removed by looking at a second plane, by taking a third view of the same plane, or by using a priori knowledge about the geometry of the plane being looked at. We then show how to combine the estimation of the matrix of collineation and the obtaining of point and line matches between the two images, by a strategy of Hypothesis Prediction and Testing guided by a Kalman filter. We finally show how our approach can be used to calibrate a system of cameras.

We are interested in the semantic interpretation of 3-D data obtained by a stereovision algorithm, in the context of indoor scenes. This paper presents a high level process built to find the main plane structures of the scene and to label them with a semantic description. This process is made up of three stages: first, the sorting and enhancement of the input data (3-D segments), second, the generation of affine planes from the sorted 3-D segments and finally, the semantic description of these planes by a classification expert system using the interpreter CLASSIC. This process has been tested on various stereo images and the quality of the results, in robustness and accuracy, are quite good. The advantages of using a knowledge based system are discussed.

A generalization of subgraph isomorphism for the fault-tolerant interpretation of disturbed line images has been achieved. Object recognition is effected by optimal matching of a reference graph to the graph of a distorted image. This optimization is based on the solution of linear and quadratic assignment problems. The efficiency of the procedures developed for this objective has been proved in practical applications. NP-complete problems such as subgraph recognition need exhaustive computation if exact (branch-and-bound) algorithms are used. In contrast to this, heuristics are very fast and sufficiently reliable for less complex relational structures of the kind investigated in the first part of this paper. Constrained continuous optimization techniques, such as relaxation labeling and neural network strategies, solve recognition problems within a reasonable time, even in rather complex relational structures where heuristics can fail. They are also well suited to parallelism. The second part of this paper is devoted exclusively to them.

This paper describes a new visual sensor system for the recognition of touching and overlapping workpieces, designed to meet the requirements of real applications in the factory. The system analyses the grey scale image and comprises two stages: a feature-extraction stage, which is designed mainly in special-purpose hardware, and a model-based analysis stage. The system works with edge-based geometrical primitives and surface features. The model comprises topographical and procedural information in order to control the image-analysis, which is based on the “heuristic-search” technique. The hardware and software design is modular. The system is working well in a wide range of environmental conditions and with different kinds of workpieces. A prototype version is completed and has proved its reliability and performance in several applications in the factory.

Two control strategies are presented as working on a hierarchical knowledge structure based on a semantic network. The control algorithms cover strict top-down control and a bidirectional control which is a mixture of top-down (model driven) and bottom-up (data driven) analysis. The knowledge used by the algorithm is represented in a semantic network. Besides the network some other knowledge sources may be generated automatically to direct the analysis and limit the search space. The approach was used successfully in image and speech understanding.

In the framework of man-machine communication, oral dialogue has a particular place since human speech presents several advantages when used either alone or in multimedia interfaces. The last decade has witnessed a proliferation of research into speech recognition and understanding, but few systems have been defined with a view to managing and understanding an actual man-machine dialogue.

The PARTNER system that we describe in this paper proposes a solution in the case of task oriented dialogue with the use of artificial languages. A description of the essential characteristics of dialogue systems is followed by a presentation of the architecture and the principles of the PARTNER system. Finally, we present the most recent results obtained in the oral management of electronic mail in French and German.