As an Edge may be an interesting image feature to extract for robotic visual tasks such as the 3D modelization of the environment of robots by stereovision, we propose in this paper a methodology to implement edge segmentation, then we apply it to design a Temporally Optimized Edge Segmentation for Mobile Robotics Applications. Using our methodology, we show how it is possible to reduce the duration of an edge detection operator from 100.62ms for the slower case to 10.8ms for the faster one. This represents a gain of nearly 90ms for the processing time, so nearly a factor of 10 for the speed up.
Processing images involves large amount of both rich and complex information. Indeed, sets of localized pixels identify objects; however, the same pixels when contained on a larger set (the whole image for example), may also represent other types of information. They may have some semantics or represent a context and so on. Dealing with one type of information identifies problems particular to one grain level. At the low level are for example filtering problems. At the mid-level, one may consider segmentation techniques and at the high level, are interpretation problems. Independently of the algorithmic questions, a structure that allows capturing part or whole of the above granularity is of great interests. In this frame of mind, it is proposed here a structure based on the combinatorial maps' formalism. A combinatorial map is a topological representation, in term of darts, built to represent one object within the image. Permutations are then defined that operate on the darts. Their combinations allow exhaustive and easy circulations on the objects' edges. The combinations allow also representing relations among different objects; a feature one may use for complex (3D) objects' modeling. Furthermore, different information (texture, geometry...) may be attached to the maps. The proposed structure is demonstrated here at the mid-level, within a fusion scheme that combines edge and region segmentations. The first one is accurate in edges detection while the second detects regions which edges are less accurate. Combinatorial maps are then considered to highlight features mentioned above, but also to enhance region edges' representation.
Color Region may be an interesting image feature to extract for visual tasks in robotics, such as navigation and obstacle avoidance. But, whereas numerous methods are used for vision systems embedded on robots, only a few use this segmentation mainly because of the processing duration. In this paper, we propose a new real-time (ie. video rate) color region segmentation followed by a robust color classification and a merging of regions, dedicated to various applications such as RoboCup four-legged league or an industrial conveyor wheeled robot. Performances of this algorithm and confrontation with other methods, in terms of result quality and temporal performances are provided. For better quality results, the obtained speed up is between 2 and 4. For same quality results, the it is up to 10. We present also the outlines of the Dynamic Vision System of the CLEOPATRE Project - for which this segmentation has been developed - and the Clear Box Methodology which allowed us to create the new color region segmentation from the evaluation and the knowledge of other well known segmentations.
Our goal is to design and to achieve a multiple purpose vision system for various robotics applications : wheeled robots (like cars for autonomous driving), legged robots (six, four (SONY's AIBO) legged robots, and humanoid), flying robots (to inspect bridges for example) in various conditions : indoor or outdoor. Considering that the constraints depend on the application, we propose an edge segmentation implemented either in software, or in hardware using CPLDs (ASICs or FPGAs could be used too). After discussing the criteria of our choice, we propose a chain of image processing operators constituting an edge segmentation. Although this chain is quite simple and very fast to perform, results appear satisfactory. We proposed a software implementation of it. Its temporal optimization is based on : its implementation under the pixel data flow programming model, the gathering of local processing when it is possible, the simplification of computations, and the use of fast access data structures. Then, we describe a first dedicated hardware implementation of the first part, which requires 9CPLS in this low cost version. It is technically possible, but more expensive, to implement these algorithms using only a signle FPGA.
This paper addresses the problem of architecture optimization, when implementing an image matching primitive in reconfigurable circuits. Circuit spatial organization is optimized in terms of processing time, and circuit volume, in order to suit well for real time on board applications. This optimized adaptive spatial and scalable organization of the (mu) PD circuit dedicated to image matching reduces by one order the spatial and temporal performance, without altering the quality of matching. The (mu) PD circuit has been validated with the minimal 22 elementary cells architecture with Xilinx 4010 XL circuit working at 12 MHz and occupying 92 percent of the circuit CLB. It performs the pyramidal 256 X 256 image matching in less than 1 s.
This paper proposes a parallel systolic VLSI circuit which can support efficiently the implementation of a dynamic programming algorithm, a part of two aerial image matching procedure. A dynamic programming algorithm allows to estimate the dense field of local luminosity difference (distance) between images in O(N) steps (N X N being image size). The calculated field is a sampling of the projective transform which links two images. The transform parameter final values are obtained through pyramidal calculations (at different image resolutions) and least square approximations.
This paper addresses a method for implementation of some basic geometric transformation, namely rotation and scale, on 1D parallel SIMD computers. Solutions to solve many implementation details such as 2D image scanning with 1D machine, the floating point arithmetic simulation and an approximation of the transformed pixel spatial co-ordinates are proposed. The proposed approach tolerates up to +/- 15 degree(s) rotation and up to +/- 50% continue scale changes between images. Those transformations can be used for construction of robust matching primitives useful for robot applications. The evaluation of the proposed method, on SYMPATI2, a French 1D parallel computer (designed by CEA,LETI) is reported.
The recognition of moving 3D objects is one of the most important tasks of future vision systems. Several techniques have been proposed using a sequence of images. Image difference thresholding, optical flow, token tracker...are a few examples. The main inconvenience is the amount of calculation that cannot meet the real time constraints, even on parallel computers. The snakes approach, also called 'active edges' seems more suitable for 3D-object recognition and tracking. We used this concept as a basic tool in our model-based recognition method. The proposed approach uses an elementary geometric property: if the 2D projections of 3D objects are similar, then 3D objects can be identical. A conveniently defined series of 2D projections can allow us to find correct associations of the representative projections of known objects memorized in image database. The snakes are used as an efficient means for location/tracking of a given object in a sequence of images. The good results obtained with this technique on a SUN Sparc workstation allows us to expect similar satisfaction on dedicated computer under strong real-time conditions.
A parallel algorithm of O(N) complexity, N number of compared pixels, for image matching, based on the dynamic programming principle, is addressed. Its new correlation (cost) function evaluates images similarity very precisely. Running time of the proposed parallel algorithm on a bi-SPARC 20/60 workstation is provided.
A new image filtering algorithm useful for line detection and aerial image matching with multiple target occurrences is presented. The filtering algorithm is based upon concepts of similar pixels and a pixel significance. A matching method of the complexity of O(n2), n: number of potential candidates, is addressed. A temporal evaluation of the corresponding sequential algorithm on DEC ALPHA 4/166 is provided.
A parallel algorithm for affine matching of aerial images using the dynamic programming as a means for images comparison under real time constrains is addressed. It includes not only data flow approach in order to speed up its execution, but also a new cost function allowing for very precise evaluation of images resemblance. Temporal evaluations of the corresponding sequential algorithm, and of the proposed parallel algorithm on a bi-SPARC 20/60 workstation are provided.
The research presented here focuses on the general problem of finding tools and methods to compare and evaluate parallel architectures in this particular field: the computer vision. As there are several different parallel architectures proposed for machine vision, some means of comparison between them are necessary in order to employ the most suitable architecture for a given application. 'Benchmarks' are the most popular tools for machine speed comparison, but do not give any information on the most convenient hardware structures for implementation of a given vision problem. This paper tries to overcome this weakness by proposing a definition of the concept of a tool for the evaluation of parallel architecture (more general than a benchmark), and provides a characterization of the chosen algorithms. Taken into account different ways to process data, it is necessary to consider two different classes of machines: MISD and (MIMD, SPMD, SIMD) offering different programming models, thus leading to two classes of algorithms. Consequently, two algorithms, one for each class are proposed: 1) the extraction of connected components, and 2) a parallel region growing algorithm with data reorganization. The second algorithm tests the capabilities of the architecture to support the following: i) pyramidal data structures (initial region step), ii) a merge procedure between global and global information (adjacent regions to the growing region), and iii) a parallel merge procedure between local and global information (adjacent points to the growing region).
This paper focuses on the problem of the massively parallel implementation of image processing algorithms. In previous theoretical studies the parallel software requirements to implement image processing algorithms were pointed out. A test algorithm, which is representative enough of the requirements for edge and region segmentations was chosen. Our goal here is to detail its implementation. The proposed test algorithm was implemented with the data programming model, on the connection machine CM5 in C*, which is an extension of the C programming language. The crux points of the parallel implementation are underlined. Edge point detection requires only parallel operations, and regular communications. Conversely, region extraction and edge chaining require irregular communications, therefore for a better efficiency, in both cases, the original algorithms were modified. These studies are in relation with the problem of finding tools and methods to compare and to evaluate parallel architectures. One of the two proposed algorithms is deduced of this one.
This paper proposes an algorithm for approximate affine plane matching of aerial images. The concept of a projective transform associated with partial Hausdorff distance is used in order to reduce the computational burden, and meet the real-time constraints. Potential algorithm parallelization for the SPMD computers is proposed as well. The running time evaluation evaluation of a sequential algorithm is given.
The field of knowledge sharing designed from conceptual specifications-ontologies and the field of logical modeling of goal achievement have an impact on processing design by using image data explanations, from sensors to physics which deals with the real world. We report in this paper some illustratioons and preliminary models dealing with the enhancement of relations which exist between conceptualization and image processing (IP). In this framework, the paper focuses on elementary models which are in correspondence with categories of IP objects, functions, and properties. The aim of this approach is to formalize conceptual domains from conceptual specifications (ontologies) and use these conceptual models in order to guarantee the adequacy between domains, and to establish a taxinomy of each domain.
This paper focuses on the design of segmentation based on textural features extraction. This is an example of a transposition between biological and visual phenomena used in order to characterize natural image understanding. This is also an illustration of a more general appraoch to IP knowledge representation based on a methodology dedicated to the formalization of concrete and abstract models for image processing applications. It proposes an ontology which includes conceptual specifications borrowed from mathematics and physical and biological axiomatics which give concrete and more natural sense to our IP models. This provides a set of elementary definitions which can be used for the expression of concrete models such as image segmentation or pattern detection. In the case of texture we would like to formalize grey level behavior through processings based on multiple window analysis (spectral and morphological criteria: grey level and compacity). In this framework, the evolutionary models studied are issued from biological modeling of migration and mutation. Our illustration is relevant to multispectral segmentation where the homogeneity criterion has been modelized by a grey level evolution function based on exponentiation.
The paper focuses on the problem of the mulitspectral image segmentation. A multispectral image is composed by several monospectral images (black and white for example), constituted by different wavelength bands. Consequently, the complementarity and/or redundancy of data, through data fusion, makes reliable and robust military or individual systems. The parallelism of the algorithm is inherent: different monospectral images may be sometimes processed in parallel without information exchanges or synchronization, or different monospectral images may be processed in parallel, but with explicit information exchanges and synchronization. This method is a new approach of image data fusion. It does not enter the taxinomy of image data fusion methods, because its level of fusion is between two classical levels. The image data fusion is performed while segmenting together the different images. The image data fusion is treated as an extension of segmentation methods. The classical or monospectral image features edges and regions that have been extended to the multispectral framework. Their attributes gather the information coming from all spectral images.
A great number of parallel computer architectures have been proposed, whether they are SIMD machines (Single Instruction Multiple Data) with lots of quite simple processors, or MIMD machines (Multiple Instruction Multiple Data) containing few, but powerful processors. Each one claims to offer some kind of an optimality at the hardware level. But implementing parallel image processing algorithms to make them run in real time will remain a real challenge; it addresses rather the control of communication networks between processors (message passing, circuit switching..) or the computing model (e.g. data parallel model). In that respect, our goal here is to point out some algorithmic needs to distribute image processing operators. They will be translated first in terms of programming models, more general then image processing applications, and then as hardware properties of the processor network. In that way, we do not design yet another parallel machine dedicated to image processing, but a more general parallel architecture which one will be able to efficiently implement different kinds of programming models.
Proc. SPIE. 1771, Applications of Digital Image Processing XV
KEYWORDS: Digital image processing, Detection and tracking algorithms, Sensors, Image segmentation, Image processing, Computing systems, 3D modeling, Reconstruction algorithms, Systems modeling, 3D image processing
Image processing is progressively becoming a science, but it remains closer to techniques, than to theory. Hence one needs to define a common frame to settle general enough problems and to build systems for various purposes in vision: a systematic method for tackling applications in computer vision.
The tentative method here stems from three main principles:
- taking the operational framework into account, to get constraints,
- introducing specific knowledge related to the application as early as possible,
- extracting local and global image properties at both segmentation and matching steps.
As it will be shown along the paper, all principles ask for an explicit expertise on classical image processing techniques: application bounds and limits. They lead to less classical image procedures, to be especially developped as in the present case:
- cooperative segmentation,
- use of planarity constraints.
Two applications have been selected, they are different on both their operational framework and image processing problems they pose :
- target tracking in IR imagery,
- 3D scene reconstruction of classical mobile robot environments: indoor or outdoor urban scenes.
Both systems have been actually designed and built. It is impossible to prove any generality of a method based on two different applications only. But these have been selected to be generic enough and with sufficient change between them, so that our systematic method of applicative system designing be likely used with succes in many other image processing applications.
After explaining the systematic method outlines through the three basic principles, each principle is illustrated by examples derived from both abovementionned applications.
This paper describes a 3-D reconstruction method of polyhedric objects (planar faces) that uses planarity constraints. Not very often used on papers, because of its global nature, we propose a new global/local implementation of these constraints. It is detailed in the context of our edge region cooperative segmentation. Conceptually, the advantages of this method are its simplicity, a precise knowledge of its uncertainties, and at the operational level its rapidity and the preciseness of the obtained volumetric reconstruction.
This paper outlines a specific method of cooperative edge linking, where difference (edge points) and homogeneous (boundaries of regions) informations are simultaneously available. In only one scanning of the image, both classical steps of "edge closing (in a small distance)" and "edge linking" are gathered. Complete chains, corresponding to strong edges, are first extracted, knowing the local edge configuration around each edge point. Then, they are brocken, in order to find junction points. Such junctions are searched only at both ends of chains, on the edge image.
This paper describes the method and the last implemented modules within the frame of an ongoing study in the field of 3D indoor / outdoor scenes reconstruction, but in man-made environments. It deals more specifically with a cooperative segmentation methodology, very much application driven, and designed from a rough geometrical modelisation of such scenes, as sets of polyhedra.
First of all, principles of the segmentation methodology are given. Then, information transfers between both kinds of feature extractors: region (relating homogeneous properties), and edge (relating local difference properties) are pointed out. They allow an easy merge of the different types of data. Later, to conclude with the advantages of this method, compared to other classical ones are underlined.