Feature Selection in Colour Images for Token Matching
Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Perception. Pages 749-750.
© 1987 International Joint Conferences on Artificial Intelligence
Abstract
We are currently developing an algorithm for knowledge-based correspondence analysis in dynamic stereo images. In this paper we describe the feature selection algorithms and the relational data structure used for matching. We also present a clustering algorithm that is used to group the tokens into sets of similar tokens. The matching algorithm uses this classification information to plan a matching strategy. The least ambiguous image features are matched first and are used as a 'handle' for constraint propagation. We present two algorithms for feature selection in colour images - a region grower and an interest operator, as well as experimental results for point classification and region classification.
- Bartsch et al. 86 : Merl.:mal1detel.:tion in Farbbildern al1 Grundlage zur Korre1pondenzanaly1e in Stereo-Bildfolgen, Thomas Bartsch, Leonie S. Dreschler-Fischer, and Carsten SchrOder, Proc. 8. DAGM-Symposium, Paderborn, West Germany , September 1986, G. Hartmann (Hrsg.), Informatilr Fachberichte 125, Springer Verlag Berlin Heidelberg New York Tokyo 1986, pp. 94-97.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
Leonie S. Dresehler-Fiseher and Frank Gnutzmann
Faehbereich Informatik, Universitat Hamburg BodenstedtstraBe 16, 2000 1f 'Uilburg 50, Federal Republic of �~rmany
ABSTRACT
We are currently developing an algorithm for knowledge-based corre spondence analysis in dynamic stereo images. In this paper we describe the feature selection algorithms and the relational data structure used for matching. We also present a clustering algorithm that is used to group the tokens into sets of similar tokens. The matching algorithm uses this classification information to plan a matching strategy. The least ambiguous image features are matched first and are used as a 'han dle' for constraint propagation. We present two algorithms for feature selection in colour images - a region grower and an interest opera tor, as well as experimental results for point classification and region classification.
I INTRODUCTION
We are currently implementing a knowledge-based vision system called SISSY (Stereo Image Sequences SYstem) for 3-D reconstruction from dynamic stereo images using a knowledge-based approach. The input are colour images, since colour provides additional features for match ing and also for the classification of boundaries. The system consists of the following modules:
- Modules to compute a rich . structural image de1cription based on regions, edges, straight linea, vertices, critical points, texture, and op tical flow fields [Bartsch et al. 86].
- A cla11i/ication module [Dre·clller-Filcller + Triendl 8~ J performing a clusterinl algorithm oil the features and grouping ambiguous features (according to some similarity criteron) into equinlence classes. The correspondence analysis starts with matching classes of features rather than features~ Classes with only few elements are matched first, since unique features may provide a starting point for constraint propaga tion.
- A mate/ling module for kno-rledge based correspondence analysis, implemented as a blackboard aystem with supervisor, scheduler, dis patcher, blackboard, attention list, and a procedur&l. knowledge base for geometric and kinetic re·oning.
- The fuzzy temporal geometric scene description reflecting the state of the geometrical reeonatruction &ecompliahed so far- object deaerip tiona, obaerver motion, moving an4 atationary objects, light sources - together with inbrmatioJl on numerical accuracy and confidence.
Thia paper describes the .feature selection part of the SISSY-system; fOr a diacu11ion of the correspondence analysis see Dre1clller-Fi1cller 86.
II FEATURE SELECTION
A.. Region Growing
There are two cluiical approaches to region growing - region growing via thresholding and regii>n growing via merging [Zucker 76]. Both approaches have advantages as well u drawbacks; region merging, gen erally, suft'ers from a lack of global knowledge, whereas thresholding is problematic because of neglecting the local context. Therefore, we sug gest a region growing algorithm by hierarchical clustering in 5-D feature space, that combines position information with colour features. Each pixel is represented by a feature vector consisting of the three colour features RGB and the two image coordinates. Thus, pixels have to be similar in colour and in position to form a duster in 5-D space. Since the dusters will be flat and of arbitrary shape, we chose a hierarchi cal clustering based on the minimal spanning tree (MST), which doea neither require a functional model of the data, nor a fixed number of classes [Zalln 71 ]. Graph-based clustering reveal· structure in the data and does not impo·e structure, like model-based classification. This is important, since we do not want to use scene-specific knowledge.
Generally, the computation of the MST for a large data set is com putationally expensive in storage and computation time reqqifements. These costs can be reduced considerably by the following obaervation: Typically, the nearest neighbor of a pixel in 5-D feature apace is one of its 4-eonnected neighbors in the image. Therefore, we reatriet the connections in the MST to those between 4-conneeted pixels.
A nice property of this clustering algorithm is that each subtree of the MST directly corresponds to a 4-eonneeted subregion of the image. Thus, segmentation is done by simply removing inconsistent edge· from the MST. The MST provides global as well as local information to de teet such inconsistent edges. Since there is no restriction on sise and shape of the regions, the MST-algorithm can detect . elongated, thin regions as well as compact regions.
Burr + Chien 76 used a MST-algorithm region grower for black-and white images and report similar good results. Burr and Chiens'a algo rithm divides the image into a set of elementary regiona and fits planes to those regions. The MST is then constructed from theae elememary regions. Contrary to Burr and Chien we compute the MST for single pixels, and thus achieve a finer spatial res91ution. This is pouible, be cause in colour images each pixel provides three intensity features, and thus we have a feature vector already on pixellcvel. .
Fig. 1 shows the segmentation result for the bouse scene from fig. 2. The image was recorded on a sunny day. The sky is entixely deep blue and the houses are painted in pastellshades, the left one is light brown and the right one is pink. The image has a resolution of 192*256 pix els. Please, note that big compact regions are detected as well u small, elongated regions.
B. Point. or Intereat
Points of interest are small local image features with aignificant varia tion ofthe image density function in more than one direction. Example· of points of interest are small dota, verticea, or endpoints of lines. Fea ture detectors for points of interest are usually called interest operators. Points of interest are important for 3-D reconstruction and correspon dence analysis, since they provide well defined points for meuurement . So far, interest operators have been developed only for black-and-white images.
Our main concern has been to verify the significance of colour infor mation for feature detection and correspondence analysis. Therefore, we decided to use the interest operator of Moravec 80 for .f\nt exper iments with colour. Moravec's operator is euy to implement and we used this operator previously for motion analysis .[Druclller + Nagel 8.1!]. We adapted Moravec's operator to colc:;ur images by c:hanging the computation of the directional variancea. Inatead of computing squared greyvalue dift'erences, the squared dift'erences of colour vectors are computed.
Figure 2 shows the results obtained with the interest operator. Most of the visually interesting points are detected - see BtJrtscll et al. 88
for a detailed discussion. These results have comfumed our assump tion that colour is a helpful cue for feature selection. At present we are developing an analytical interest operator for colour images, since ana,lytical interest operators are superior to heuristic operators with respect to the spatial resolution.
C. Classification
After feature selection the features are grouped into similarity classes according to a similarity function . The classification module performs a clustering algorithm on the features using the same similarity function that is us~d by the correspondence algorithm. The correspondence analysis starts with matching classes of features rather than features. Classes with only few elements are matched first, since unique features may provide a starting point for constraint propagation.
The classification module uses a "minimal-spanning-tree" -algorithm for clustering, for the same reasons as the region grower. The minimal spanning-tree is segmented by removing all edges longer than a thresh old that is computed from the mean edge length and the variance of the edge length in the minimal spanning tree.
Classification of points - Fig. 2 shows classification results for the points of interest. The set of all points of interest is indicated by white markers. In each of the figures a and b one class of points is marked by black markers. Fig. 2a shows a class of "all points looking like the horizontal end points of cross-bars" . Fig. 2b shows a class with only·two members. There are some classes with points unique in the image and thus, a promising starting point for matching, e.g. the two top corners of the chimney. Please note that many points do look alike locally on pixel level, even when they are globally quite different in structure. The similarity function used for classification was the normaliaed cross-correlation in a 5-by-5 neighborhood.
Claasifleation of regions - The classification of regions is based on a distance function computed from several features: area, mean RGB-values, compactness, and the principle moments of inertia. These features are sealed to sero mean and variance 1.0 to provide a uniform weight for all features.
Fig.3 shows results of the region classification. There is one big class of dark regions of more or less rectangular shape corresponding to the windows; A smaller class combines the five window regions that are darker than the others (fig. 3b).
There are some classes with only one member, e.g. the sky region. Those unique regions may serve as starting points for the matching algorithm.
In addition to guiding the matching process we want to exploit the classification as second-order-features. For example, a class of points of interest with many members is a cue to textured regions; classes of parallel lines are helpful to detect separate objets.
III IMPLEMENTATION AND CONCLUSIONS
So Car, we have implemented the modules for feature extraction from colour images that perform quite satisfactory (region growing, points of interest, edge detection) and a database for easy retrieval of struc tural image descriptions together with a versatile interactive graphical display facility [Sprengel 86), and there are promissing results for the classification of points of interest and regions. All algorithms presented here are programmed in Ada.
Acknowledgements - This work has been funded partially by a grant from the Deutsche Forschungsgemeinschaft (DFG). Th. Bartsch implemented the interest operator, C. SchrOder implemented the region grower, and Rainer Sprengel implemented the database. We thank I. Heer-Miick and H. Kruger for keeping the hardware running, and H. Faasch, and V. Haarslev for their ready help in case of system trouble.
Bartsch et al. 86 : Merl.:mal1detel.:tion in Farbbildern al1 Grundlage zur Korre1pondenzanaly1e in Stereo-Bildfolgen, Thomas Bartsch, Leonie S. Dreschler-Fischer, and Carsten SchrOder, Proc. 8. DAGM-Symposium, Paderborn, West Germany , September 1986, G. Hartmann (Hrsg.), Informatilr Fachberichte 125, Springer Verlag Berlin Heidelberg New York Tokyo 1986, pp. 94-97.
I Burr + Chien 76 : The minimal 1panning tree in vi1ual data legmentation, D.J . Burr and R.T. Chien, Proc. of the 3' 4 Int. Joint Conf. Pattern Recognition, Coronado, California, U.S.A., Novem ber 1976, pp. 519-523.
Dreschler + Nagel 82 : Volumetric Model and 3D-Trajectory of a Moving Car Derived from Monocular TV Frame Sequence· of a Street Scene, L. Dreschler and H.-H. Nagel, Computer Graphics and Image Processing 20, 199-228 (1982).
Dreschler-Fischer 86 : A Blackboard Syltem for Dynamic Stereo Matching, L.S. Dreschler-Fischer, Proc. 1' 1 Int. Conf. on Au tonomous Mobile Systems, Amsterdam, The Netherlands, Decem ber 1986, (in press) .
Dreschler-Fischer + Triendl 84 : The ASTERIX-Sy1tem: A Fea ture Ba&ed Approach to the Corre1pondence Problem, Leonie S. Dreschler-Fischer and Ernst E. Triendl, Proc. DARPA-Image Un derstanding Workshop, New Orleans/La, October 1984, pp. 300301.
Moravec 80 : Obltacle Avoidance and Navigation in the Real World by a Seeing Robot Rover, H.-P. Moravec, Ph.D. Thesis Dept. Comp. Science, Stanford University, Stanford/CA (1980) see also:
Report CMU-RI-TR-3 Robotics Institute, Carnegie-Mellon University, Pittsburgh/FA (September 1980) .
Sprengel 86 : DESIRE - Entwurf einer Datenltrul.:tur zur ·ymbol i~ehen Be1chreibung von Bildem, Rainer Sprengel, Technical Note FBI-HH-M142/86 Universitat Hamburg, Fachbereich In formatik, Hamburg, West Germany (November 1986).
Zahn 71 : Graph-Theoretical Method· for Detecting and De1cribing Ge1talt Clu1ter1, C.T. Zahn, IEEE llans. on Computers c~20, 68-86 (1971).
Zucker 76 : Region and Adole1cence, S.W. Zucker, Processing 5, 382-399 (1976) . Growing: Childhood Computer Graphics and Image The points marked by black crosses belong to the same equivalence class.







Fi~. 2: Classification results for Points of interest.
Fig. 3: Classification results for regions The regions marked by black or white contours are members of the same equivalence class.
@inproceedings{ijcai1987p151,
title = {Feature Selection in Colour Images for Token Matching},
author = {Dreschler-Fischer, Leonie S. and Gnutzmann, Frank},
booktitle = {Proceedings of the Tenth International Joint Conference on
Artificial Intelligence, {IJCAI-87}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John McDermott},
pages = {749--750},
year = {1987},
note = {Perception},
url = {https://ijcai.org/proceedings/1987/151},
}
TY - CPAPER TI - Feature Selection in Colour Images for Token Matching AU - Dreschler-Fischer, Leonie S. AU - Gnutzmann, Frank T2 - Proceedings of the Tenth International Joint Conference on Artificial Intelligence, IJCAI-87 PB - International Joint Conferences on Artificial Intelligence PY - 1987 SP - 749 EP - 750 UR - https://ijcai.org/proceedings/1987/151 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: