Neural Networks for Matching in Computer Vision
Giansalvo Cirrincione1 and Maurizio Cirrincione2
Department of Electrical Engineering, Lab. CREA University of Picardie-Jules Verne 33, rue Saint Leu, 80039 Amiens - France exin@u-picardie.fr Universite de Technologie de Belfort-Montbeliard (UTBM) Rue Thierry MIEG, Belfort Cedex 90010, France maurizio.cirricione@utbm.fr
1

2

Abstract. A very important problem in computer vision is the matching of features extracted from pairs of images. At this proposal, a new neural network, the Double Asynchronous Competitor (DAC) is presented. It exploits the self-organization for solving the matching as a pattern recognition problem. As a consequence, a set of attributes is required for each image feature. The network is able to find the variety of the input space. DAC exploits two intercoupled neural networks and outputs the matches together with the occlusion maps of the pair of frames taken in consideration. DAC can also solve other matching problems.

1

Introduction

In computer vision, structure from motion (SFM) algorithms recover the motion and scene parameters by using a sequence of images (very often only a pair of images is needed). Several SFM techniques require the extraction of features (corners, lines and so on) from each frame. Then, it is necessary to find certain types of correspondences between images, i.e. to identify the image elements in different frames that correspond to the same element in the scene. This paper addresses this specific problem, also known as matching. The techniques for image matching can be continuous or discrete. The latter are feature-based methods (FBM) and treat the images as samples of the scene taken at discrete times. They allow accurate estimation of motion parameters and structure of the scene even under a relatively large motion, do not suffer much from the problem of varying image intensity and do not need intensity smoothness. However, they suffer from several problems, like occlusion, depth discontinuities, repetitive patterns in the scene. As a consequence, image matching belongs to the class of the so called inverse problems, which are known to be ill-posed. It can be converted to a well-posed problem by introducing constraints in the correspondence formulation. The commonly used constraints are the similarity (or compatibility) constraint (matching features must have similar attribute values), the uniqueness constraint (almost always, a given pixel or feature from one view can match no
B. Apolloni et al. (Eds.): KES 2007/WIRN 2007, Part I, LNAI 4692, pp. 688–695, 2007. c Springer-Verlag Berlin Heidelberg 2007

Neural Networks for Matching in Computer Vision

689

more than one pixel or feature from the other view), the epipolar constraint (for calibrated stereo rig), the continuity (or disparity) constraint (correspondences for neighboring points in one image must have similar disparities), the disparity gradient constraint (condition on the tangent to the object surface), the ordering constraint, the smooth motion constraint and several geometric and kinematic constraints (see [1] for reference). The formulation of the correspondence problem is well-suited to computation by a neural network. Indeed, it can be formulated as an optimization task where a cost function (energy equation), representing the constraints, is minimized. The minimization can be mapped into a Hopfield neural network [2] such that the energy function is the same as the Lyapunov function of the network, with the synaptic interconnection weights between the neurons representing the constraints imposed by the corresponding problem. These applications yield bad results for real images because of their dimensionality and high computational demand, suffer from the local minima and the possible improvements (e.g. simulated annealing) are too time consuming for real time applications. The most interesting applications are the Zhou and Chellappa neural network [3] for static stereo, the Sarigianidis and Pycock neural network [4] which uses a motion correspondence method and the Nasrabadi and Choo neural network [5] for stereo vision correspondence (the cost function is devised by implementing the continuity, uniqueness and 2D rigidity). Unlike the previous ones, the Bellando and Kothari neural network [6] uses topology preserving maps (see after), but works well only for toy problems. In the next section a novel neural network is proposed. It considers matching as a pattern recognition problem. Two examples of matching are then given, the first by using a pair of synthetic images, the second by using a road sequence.

2

The Double Asynchronous Competitor (DAC)

The Double Asynchronous competitor (DAC) exploits the features of the self organizing feature maps (SOFM, [7]) for solving the correspondence problem. The SOFM defines a topologically preserving mapping from a high-dimensional input data space into a low dimensional output space: the latter is usually a 2D lattice of neurons. The neurons are usually arranged on a rectangular grid and connected according to a given neighborhood relation. Each neuron possesses a weight vector whose dimensionality is the same of the input vector. The learning is unsupervised and its updating is winner-take-most : after presentation of the input vector x to the network, the neuron i whose weight wi is the nearest to the input, according to a predefined metric, is selected (winning neuron with index i∗ ). The winner-take-most approach updates both the winning neuron and its lattice neighbors according to: wi ←− wi + α(t)G( i, i∗ , t)(x − wi ) ∀i
∗

(1)

where α(t) is the learning rate, usully decreasing with time, and G( i, i , t) is a weighting function (neighborhood kernel ) depending on the grid distance around the winning neuron. The kernel can be Gaussian:

690

G. Cirrincione and M. Cirrincione

G( i, i∗ , t) = e

−

wi −wi∗ ρ2 (t)

2 2

(2)

where the Euclidean distance is used and ρ(t) (decreasing with time) is the neighborhood radius. The SOFM quantizes the input distribution and is able to capture the underlying variety of the input space. The vector quantization is constrained by the grid neighborhood structure of the neurons. These units project the input distribution toward the neuron grid by respecting locally the concept of proximity: in this sense, SOFM is topologically preserving. DAC works for sequences of images without need of epipolar constraints. It is able to solve the matching problem even in the case of several moving objects and mobile camera. It also yields an occlusion map for each image. The following description considers the two-view problem, but can be easily extended to multiple views. DAC is composed of two SOFMs (NN12 and NN21) which are coupled. Every SOFM has a particular lattice: the neurons are placed in one image (2D lattice) at the geometrical position of the feature points and the training set is composed of the attribute vectors of the other image. An advantage of this approach is the possibility of using as many attributes as desired, without any care of eventual correlations: in every case, the network is able to detect the unknown variety of the input space. The choice of the attributes depends on the kind of image sequence. In the simulations, the SUSAN corner detector [8] has been used. The advantage of this choice is given by the fact that no explicit image derivatives are needed and the feature extraction is very quick. According to the value of its scalar parameter t (brightness difference threshold), corners or edge points (edgels) can be extracted. A lot of attributes can be attached to these features, e.g., the intensity (gray value) of the feature point, the edgeness as defined in [9], the positive and the negative cornerness as defined in [9], the USAN area computed by the SUSAN detector and the USAN centre of gravity w.r.t. the feature point [8], the measure of interest of the Moravec operator (computed ad hoc for the feature point, [10]), the Laplacian using 3x3 or 5x5 masks for the second derivatives [11], the second derivative in the direction of the gradient and in the direction orthogonal to the gradient [11] and the coordinates of the feature points, weighted far less than the other attributes in the training set. NN12 has the first image (feature points) as grid (neurons), the attribute vectors of feature points of the second image as training set (TS) and the attribute vectors of feature points of the first image as initial weight vectors. NN21 is the opposite: the second image as grid, the first image attribute vectors as training set and the second image attribute vectors as initial weight vectors. This choice for the initial conditions helps implementing the search for the correspondence similarity by means of the SOFM quantization process. The choice for the grid implies the continuity and 2D rigidity constraints thanks to the topologically preserving behavior of the SOFM. Indeed, the network seeks to 2D project the one image attribute vectors in order to respect the relative other image feature point positions. In a certain sense, it is a way of implementing the 2D rigidity constraint without need of introducing an a priori shift parameter as in the existing matching techniques. The coupling between NN12 and NN21 implements

Neural Networks for Matching in Computer Vision

691

the uniqueness constraint. The SOFMs used in DAC have Gaussian neighborhood kernels. An important difference with the SOFM learning is the possibility for an input vector of not having a winning neuron. In fact, a neuron is accepted as winner only if its weight vector stays into a hypersphere (search window in the attribute/input space) centered at the input vector, whose radius is given by the threshold δ (t) which decreases with time for increasing resolution. The association input vector-winning neuron is considered as a possible match.

Fig. 1. 1D illustration of the determination of the occlusion maps. The images are one-dimensional. The displacement fields illustrate correspondences between two 1D images.

There are several possible architectures for DAC. The basic arrangement is made of the series of NN21 and NN12 and a feedback from NN12 to NN21. One DAC epoch is equal to the sum of one NN21 epoch (half DAC epoch) and one NN12 epoch (half DAC epoch). Every half DAC epoch, a test is done for the setting of the first and second image occlusion maps. Fig.1 shows the testing for 1D images. The first half epoch (presentation of the whole image 1 training set) is given by the NN21 learning (right side of fig.1). This learning is coupled to the other SOFM. At the end of the epoch, a first approximated disparity map 2 → 1 is given by the input data and associated winning neurons. This first matching does not use occlusion information. Hence, this matching may jam the occluded parts of the second image into parts of the first image. The objective of this first half DAC epoch is to compute the occlusion map 1 (first image). The jamming generally will not affect the computation of the occlusion map 1, since the occluded regions of image 1 to be detected may only occur on the opposite side across the jammed region [9]. Those regions (input data/features) in the first image that have not been matched are occluded in the second image and are marked as occluded: every neuron/input vector has a state variable which is set to zero in case of occlusion, i.e. when no neuron wins. If the input vector (feature) is not occluded, its state variable is set to the number of the winning neuron. Hence, a test is done on the input data state variables. If an input vector is occluded, it is excluded from the TS for the successive N21 learnings and the corresponding

692

G. Cirrincione and M. Cirrincione

(i.e. attached to the same feature point of image 1) neuron in NN12 is inactivated and does not enter the N12 learning. This is recorded by a state variable set to zero for the corresponding neuron. This inactivation is represented by the arrow from N21 (right) to N12 (left) in fig.1. Once this inactivation is done, NN12 learns for one half DAC epoch with the remaining neurons (presentation of the whole N12 training set). A first approximated disparity map 1 → 2 is output. The results of this learning determine occlusion map 2 analogously. The same test is done on the NN12 input data. As a consequence, the occluded data are ruled out the TS and the corresponding neurons in the N21 grid are inactivated. This inactivation is represented by the arrow from N12 (left) to N21 (right) in fig.1. This procedure is recursive. The coupling between NN12 and NN21 is given by the following procedure (the coupling between NN21 and NN12 is analogous): 1. 2. 3. 4. 5. Enter vector k of the image 2 TS into NN12. Neuron f 2 wins (its weight vector must also be in the δ-hypersphere). Neuron f 2 and its Gaussian neighborhood learn. Select the corresponding couple in NN21: neuron k and input vector f 2. Neuron k and its Gaussian neighborhood learn only if the k weight vector is in the δ-hypersphere centered at f 2.

As a consequence of this coupling, one half epoch in a SOFM induces learning in the other one before the corresponding half epoch. This coupling implements the uniqueness constraint as shown in fig.2. Indeed, the asymmetry of DAC (one feature has only one winning neuron, but one neuron may win for more than one feature) and the interchange of the function of neuron and feature between the SOFMs imply the uniqueness.

Fig. 2. DAC uniqueness coupling property

Resuming, the only DAC parameters are the neighborhood radius ρ(t), the learning rate α(t) and the threshold δ (t) for the acceptance of the winner. Experience has suggested the following heuristics for setting a constant value for δ: merge the two training sets and compute all the possible Euclidean distances D between couples of vectors; then, set σ to (1.1 ÷ 1.2) dmin , where dmin is equal ¯ ¯ to D − σD and D and σD are the average and standard deviation of the set of distances D.

Neural Networks for Matching in Computer Vision

693

After every DAC epoch, a control is done on the DAC results as a stop criterion: 1. Every non occluded input vector/feature point from image 1 has a nonzero state variable representing the number of the associated winning neuron for image 2. 2. The winning neuron represents also the input vector for the feature point in the same image (i.e. image 2). 3. If the state variable of this input vector (image 2) coincides with the state variable of the input vector of image 1 (first step), then the match is accepted. 4. If all matches are accepted, then DAC stops and outputs the list of the correspondences and the lists of the two occlusion maps.

3

Simulations

The first simulation deals with a pair of synthetic images. Given a world reference frame xyz, centered at the center of projection of the normalized camera (unit focal distance) and of z-axis parallel to the optical axis, a certain number of points Pi = (xi , yi , zi ), where xi , yi ∈ [−5, 5] and zi ∈ [3, 10], has been selected randomly. These points are then translated of the vector [2, 3, 1] and rotated around the axis [0, 0, 1] of 0.1 rad. Then, the initial and final points are projected (perspective projection) into an image plane whose coordinates are parallel to the x- and y-axes of the world reference frame and whose centre is the intersection with the optical axis. Hence, the correspondences are known a priori. A white Gaussian noise (μ = 0, σ = 1) is then added to all image points. A comparison is made between the network of Nasrabadi and Choo and DAC. In the first network, the vertical disparity is also implemented in the compatibility measure and the selected parameters (used for the comparison) are λ = 1 and ϑ = 10 (for an explanation of these terms, see [5]). In the second network, the input vectors are only composed of the coordinates of the image points. The learning rate α(t) is a decreasing function (inversely proportional to the iteration number) from 0.3 to 0.03; after reaching the minimum, the function remains constant. at 0.03. The same function is used both for the Gaussian standard deviation ρ(t) and for the hypersphere ray δ(t), with initial values, respectively, 1.5 and 3 and same final value 0.03. Tab.1 shows the results, averaged over five experiments for every choice of the number of points. DAC is more accurate, both for noiseless and, above all, for noisy images, even if only two attributes can be used. Furthermore, it is by far faster than the other network and does not suffer from the problem of local minima. In fact, only two DAC epochs are sufficient for all the experiments. The second simulation considered here is fully presented in [12]. Two image frames are extracted from a road sequence of 100 frames, given by the CSTV CNR Computer Vision Laboratory of Turin (Italy). It has been captured by a camera mounted on the roof of a van (mobile laboratory MOBLAB) which slowly turns to left. The frames have 256 grey levels and pixel dimension 720 × 280. In the camera model (frame XY Z) for the test road image pair, the Y -axis has the vertical direction and is oriented upward. A certain number of feature points

694

G. Cirrincione and M. Cirrincione Table 1. Correct match percentages for the synthetic pair DAC noiseless noisy 100 % 100 % 100 % 100 % 100 % 98.3 % 100 % 96.9 % Nasrabadi & Choo noiseless noisy 98.2 % 96.4 % 95.2 % 90.6 % 92.1 % 87.5 % 89.1 % 77.2 %

points 10 30 70 100

Fig. 3. DAC results (arrows) for the test road image sequence, superimposed on the first frame. The black arrows are excluded by the CASEDEL EXIN neural network.

(corners) are extracted by the SUSAN corner finder. The image matching has been performed by using DAC, which uses all the attributes described before. In fact DAC is able to automatically capture the variety of the input space. The learning rate α(t) is constant and equal to 0.01; the Gaussian standard deviation ρ(t) is a decreasing function (inversely proportional to the iteration number) with initial value 150; the hypersphere ray δ(t) is constant and equal to 1. DAC converges after only two epochs and finds 31 correspondences. These correspondences are visualized as superimposed on the first frame in fig.3. In the neural SFM module presented in [12], the neural network called CASEDEL EXIN is able to characterize the cluster of black arrows in the upper left of fig.3 as cluster of mismatches (outliers) and so it refines the DAC matching. The presence of this group of black arrows is explained by the absence of detected corners for the advertising poster in the first frame [12]. Despite the claims of Stephen Smith, SUSAN does not show a good stability in this image sequence. This explains the inaccuracy of some matches.

4

Conclusion

This paper has presented a novel kind of neural network, DAC, which exploits the self-organization for solving the matching problem in SFM as a pattern

Neural Networks for Matching in Computer Vision

695

recognition problem. As a consequence, a set of attributes is required for each feature point. The network is able to find the variety of the input space. DAC is faster and more accurate than the Hopfield based neural techniques and is by far better than the BPN based neural techniques which would require nearly unlimited training sets. DAC is an open architecture in the sense that different schemas are possible and other self-organizing learning laws can be chosen. In [12] DAC is integrated with the EXIN SNN neural network, which is able to segment the image and has a similar learning law. Hence, it can be implemented directly in the DAC learning law and can refine the matching. Future work will deal firstly with the choice of other feature detectors, better if neural, which must be less unstable than SUSAN. A more detailed analysis of the limits and the convergence properties of DAC is still needed. Its coupling and temporal scheduling must be further investigated. Furthermore, the DAC matching technique can be extended to other problems as the template matching, the range point matching and the graph matching. The parallelization of the DAC architecture must be still analysed.

References
1. Faugeras, O.: Three-Dimensional Computer Vision: a Geometric Viewpoint. MIT Press, Cambridge, Massachusetts (USA) (1993) 2. Hopfield, J.: Neural networks and physical systems with emergent collective computational abilities. Proc. Nat. Acad. Sci. 79, 2554–2558 (1982) 3. Zhou, Y., Chellappa, R.: Artificial Neural Networks for Computer Vision. Research Notes in Neural Computing, vol. 5. Springer, Heidelberg (1992) 4. Sarigianidis, G., Pycock, D.: Motion correspondence using a neural network. British Machine Vision Conference, 649–658 (1993) 5. Nasrabadi, N., Choo, C.: Hopfield network for stereo vision correspondence. IEEE Trans. on Neural Networks 3(1), 5–12 (1992) 6. Bellando, J., Kothari, R.: On image correspondence using topology preserving mappings. In: Proc. Int. Conf. On Neural Networks, Washington, D.C (USA), pp. 1784–1789 (June 1996) 7. Kohonen, T.: Self-Organization and Associative Memory. Springer, Berlin (1989) 8. Smith, S., Brady, J.: Susan-a new approach to low level image processing. International Journal of Computer Vision 23(1), 45–78 (1997) 9. Weng, J., Huang, T., Ahuja, N.: Motion and Structure from Image Sequences. Springer Series in Information Sciences. Springer, Heidelberg (1993) 10. Moravec, H.: Visual mapping by a robot rover. In: Proc. Of the 6th Int. Joint Conf. On Artificial Intelligence, pp. 598–600 (1979) 11. Beaudet, P.: Rotational invariant image operators. In: Proc. Of the Int. Conf. On Pattern Recognition, pp. 579–583 (1978) 12. Cirrincione, G.: A Neural Approach to the Structure from Motion Problem. PhD thesis, LIS INPG Grenoble (December, 1998)