Pattern recognition

[0001] This application is based on and hereby claims priority to German Patent Application No. 19924009.4 filed on May 26, 1999, the contents of which are hereby incorporated by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates to a technically implementable method for searching for a reference pattern in a search field.

[0004] 2. Description of the Related Art

[0005] Pattern in the sense of the present description is understood as any two- or multidimensional representation of physical variables or general sensory information. A pattern in this sense can therefore be characterized by a two- or multidimensional matrix of predetermined parameters. A corresponding statement also holds for the search field which thereby constitutes a two- or multidimensional representation of physical variables or sensory information. The aim is to use the reference pattern in the search field by using the pattern searching method. In this case, in addition to the reference pattern it is also possible for other, partially very similar patterns, which are termed distracters, to be present in the search field.

[0006] It is known from the prior art to utilize findings from neurosciences (neuroinformatics, neurobiology) with regard to an efficient search operation, since biological neurosystems such as, for example, the human brain generally accomplish pattern searching tasks efficiently.

[0007] The following text states the prior art, which constitutes various approaches known from the neurosciences.

[0008] Two principle types of search or recognition are distinguished, specifically the attribute search and the conjunction search (compare A. Treisman and S. Sato, “conjunction search revisited”, Journal of Experimental Psychology; Human Perception and Performance, 16, 459–478). In the case of an attribute searching task, the target object is distinguished from the distracters by only one respectively identical attribute type (termed parameter below), for example only in shape. It is to be noted here that in the following description the term parameter characterizes, for example, the shape, color or size of a pattern, for example large and small for the size parameter, triangular, rectangular and round for the shape parameter etc., which represent values which the parameters can assume. These values are represented in a coded fashion in the case of a technical implementation, for example by logic signals.

[0009] In a conjunction searching task, the distracter objects are combined into various groups. The target pattern is distinguished from each distracter group by one parameter, but not from all distracter groups by the same parameter. It is possible, for example, to distinguish between a standard and a triple conjunction search. In a standard conjunction search, there are two distracter groups, which have two parameters in each case, and the target pattern has in each case a parameter value common to each distracter group. In a triple conjunction search, the target pattern can be distinguished from all distracter groups by one or more parameters.

[0010] A model has been proposed in which there is initiated after a first parallel search a competitive search which is terminated by the recognition of only a single pattern, specifically the target object (M. Usher and E. Niebur, “Modeling the temporal dynamics of IT neurons in visual search: A mechanism for top-down selective attention”, Journal of Cognitive Neuroscience, 8, 311–327). The model is based in this case of a neuro approach for object- orientated recognition, various visual stimulation values such as, for example, shape, color, size etc. being represented by mutually competing cell arrangements which are mutual inhibitory.

[0011] A disadvantage of the prior art set forth above is that available solutions for technical realization or implementation of the pattern searching operation do not play a role in this case. This problem exists in general when an appeal is made to non-technical fields such as neurobiology, when implementing technical systems.

[0012] It is therefore an object of the present invention to provide a technique for pattern searching which can be realized efficiently in technical terms. The efficiency of biological systems should be obtained overall as far as possible in this case.

[0013] A particular application of the method according to the invention is in automated searching of objects which are to be picked up by a robot, based on a reference pattern representing an object in this case. In this application, it is possible, for example, for objects which are to be picked up by the robot to pass by on a conveyor belt in the region of a robot arm.

[0014] Thus, a method is proposed for searching a reference pattern in a search field. The reference pattern is characterized in this case by predetermined parameters. At least one topographic map of the search field is generated per parameter. Levels at the respective positions of the topographic map are in this case a function of the value of the corresponding parameter at the corresponding position in the search field. The levels of the topographic map are varied as a function of the values of the parameters of the reference pattern. A dynamic variation of the topographic map therefore takes place. The respective levels of each position of the varied topographic maps are combined for the purpose of generating a combined topographic map. The reference pattern is then considered to be found at that position of the search field which corresponds to that position of the combined topographic map which has the highest level.

[0015] The method set forth above can be executed completely in a parallel or quasi-parallel fashion. The method advantageously has no sort of return loop, and this renders the technical realization less complicated. The dynamics of the method resides in the respective variation in the level of the topographic maps. This variation takes place separately for each parameter. This also is attended by advantages by comparison with a realization with the aid of a return loop, in which all the method steps must be run through again at each iteration step.

[0016] One group comprising a plurality of topographic maps of the search field can be generated per parameter. A topographic map is generated for each value which the corresponding parameter can assume.

[0017] The variation in the level of the topographic maps is a function of the values of the parameters of the reference pattern can be performed by mutual interaction of the topographic maps of a group in each case.

[0018] In the step of varying the levels of the topographic maps, the levels of the topographic maps can be varied as a function of their correspondence in each case with the actual values of the parameters of the reference pattern.

[0019] The generation of the topographic maps can be performed by a parallel or pseudo- parallel (quasi-parallel) processing of the information of the search field.

[0020] The levels of the combined topographic map can also be varied dynamically, levels which are above a predetermined limiting value being increased, and levels which are smaller than or equal to the predetermined limiting value being reduced. In a final stage, the levels of the combined topographic map can therefore converge to the effect that only one position still has a determined level.

[0021] A preferred application of the present invention is to be found in robotics. For example, objects which are to be picked up by a robot can be automatically searched for by the method in an automated fashion. In other words, the reference pattern constitutes an object to be picked up.

[0028] Reference will now be made in detail to the preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to like elements throughout.

[0029] A search field with a plurality of patterns is illustrated in FIG. 1, the intention being to find one of the patterns. The search field is split up, for example, into nine sections, each section being defined by a horizontal co-ordinate i (i=1, 2, 3) and a vertical coordinate j (j=1, 2, 3). Each section of the search field of the example shown in FIG. 1 maintains a pattern. Each pattern is characterized by K parameters, in the present example by the three parameters of shape, size and color. The first parameter (k=1) of color, can assume L=3 parameter values, specifically triangular, rectangular and round. The second parameter (k=2) of size can assume L=2 values, specifically large and small, and the third parameter (k=3) of color can assume L=2 values of white and black, the value of black being represented in FIG. 1 by hatching of the respective objects.

[0030] Thus, the pattern illustrated by the example in section (1=1, j=1) is characterized by the parameter values of rectangular, small and black, the pattern in section (i=3, j=2) is characterized by the parameter values of triangular, large and white, etc. The search for a reference pattern is illustrated diagrammatically in FIG. 2, the search field with nine sections shown in FIG. 1 being used as a basis by way of example. The search system comprises detection means 2 which detect the parameter values of the patterns in the search field, and output corresponding detection information to first processing means 3. In the example illustrated in FIG. 2, the search system comprises nine detection means 2, which are assigned in each case to a section(i, j) of the search field illustrated in FIG. 1. In the example illustrated, each detection means 2, which can, for example, be photodetector, an infrared detector or the like therefore detects the parameter values of the pattern arranged in the corresponding section of the search field. The detecting means 2 can thus simultaneously detect in each case the three parameters of shape, size and color. Alternatively each section of the detection region can be assigned a respective detecting means 2 for each parameter, such that in the example illustrated in FIG. 2, for example, each section (i, j) of the detection range can be scanned by three detection means 2 for the size, the shape and the color of the object, in each case. As a further alternative, it would be possible for each section of the search field to be assigned a multiplicity of detecting means.

[0031] The first processing means 3 processes the detection information from the detection means 2 in parallel or quasi-parallel and separately for each parameter, by making use of parameter information from the storage device 1. The parameter information in the storage device 1 includes the parameter values of the reference pattern, which is to be found in the search field. The processing, separate for each parameter, of the detection information by the first processing means 3 is illustrated in FIG. 2 by splitting up the first processing means 3 into three parameter networks (k=1, k=2 and k=3), each parameter network being subdivided in turn into parallel subnetworks 5 for each parameter value of the corresponding parameter. Each parameter network therefore constitutes a topographic map of the search field with reference to the corresponding parameter.

[0032] The first parameter network (k=1), which is assigned, for example, to the parameter value of size for the example shown in FIG. 1, therefore includes three parallel subnetworks 5, one for each of the three possible parameter values of rectangular, triangular and round. The other parameter networks (k=2, k=3) correspondingly likewise have two subnetworks 5.

[0033] It is to be noted that the terms of parameter network and subnetwork relate to their construction as neuronetwork, each first processing means of the subnetworks 5 being constructed in the manner of a collection of completely interconnected excitatory neurons. As may be seen from the scheme in FIG. 2, in this case each first processing means 3 or each collection of neurons is assigned to a corresponding section of the search field such that in the present example each subnetwork 9 has first processing means 3 which correspond in the corresponding sections (i, j) of search field.

[0034] The first processing means 3 or the respective collections of neurons within each subnetwork 5, and the subnetworks 5 within a respective parameter network are intercoupled in the manner of an inhibitory link 6, something which can be illustrated by a pool of inhibitory neurons. In this case, the links illustrated in the scheme of FIG. 2 with the aid of continuous lines are excitatory, and the links shown with the aid of dashed lines are inhibitory. Each parameter network therefore has an independent pool of inhibitory neurons, and this corresponds in a neurophysiological comparison to the fact that the response of neurons which are sensitive to a specific parameter is amplified, and the activity of the other neurons, which are sensitive to other parameters, is suppressed.

[0035] Each first processing means 3 in each subnetwork 5 is assigned to a corresponding section of the search field, that is to say the first processing means 3 in each subnetwork are topographically ordered or, in terms of a comparison, the receptive field of neurons which are assigned to a specific section are sensitive to the detection information detected at the corresponding section of the search field. It is to be noted here that each detection means 2 is connected to each first processing means 3. In the scheme illustrated in FIG. 2, this means that each first detection means 3 receives detection information from each of the nine detection means 2. Furthermore, each first processing means 3 receives the parameter information relating to the reference pattern from the storage device 1.

[0036] The second processing means 4 process the processing information from the first processing means 3 and output information which serves to determine the assumed position of the reference pattern in the search field. The second processing means 4 are likewise constructed in the manner of a neuron network, processing information from various sections of the search field being processed in a parallel or quasi-parallel fashion. In each case, a second processing means 4 is respectively assigned to a section of the search field and receives processing information respectively only from the first processing means 3, which are assigned to the same section, as may be seen from the scheme in FIG. 2.

[0037] In other words, this means that the second processing means 4, which is assigned to the section (i=3, j=3), receives processing information exdusively from the first processing means 3, which are likewise assigned to the section (i=3, j=3) of the search field. Like the first processing means 3, the second processing means 4 are respectively constructed, in terms of a comparison, in the manner of a collection of completely interconnected excitatory neurons which are intercoupled in the manner of an inhibitory link 6. The second processing means 4 constructed in such a way in the manner of a raster or a layer thus correspond to the model of IT (inferrotemporal) neurons which exhibit a position-specific increase in the activity by suppressing the responses of the collections assigned to other positions. A corresponding statement holds for the subnetworks 5 of the first processing means 3.

[0038] This configuration of the second processing means 4 corresponds to a dynamic construction of a focused attentiveness without the explicit assumption of a focusing mechanism. Top-down information in the form of parameter values, stored in the storage device 1, of the reference pattern are, as it were, fed by corresponding excitatory links between the storage device 1 and each first processing means 3. The detection information and parameter information are processed in this case by the first processing means 3 and the second processing means 4 for each section of the search field in a parallel or quasi-parallel fashion, a longer reaction time corresponding to a slower dynamic convergence on all layer planes, that is to say to the subnetworks 5 and the higher-order layer consisting of higher-order processing means 4.

[0039] Presented below is a set of differential equations by which the dynamic behavior of the search operation can be characterized. Assuming an ergodic response, use is made of the so-called mean-field approximation to derive a dynamic system of equations for the activity levels of the collections of neurons forming the first and second processing means 3 and 4 respectively. The basic idea consists in representing each arrangement of neurons by the respective activity x and an input current I which is characteristic of all the arrangements of neurons, in which case it holds that: $x=F\left(I\right)=\frac{1}{T_r-\tau \log \left(1-\frac{1}{\tau I}\right)},$

[0040] F(I) being the response function, which converts the input current I into discharging or activity rates for a neuron (integrate and fire spiking neuron) having a deterministic input, a time membrane constant τ and an absolute refractory time T_r.

[0041] The system of differential equations which describe the dynamic behavior of the subnetworks 5 is: $\tau \frac{\partial }{\partial t}{I}_{\mathrm{ijkl}}\left(t\right)=-I_{\mathrm{ijkl}}\left(t\right)+aF\left(I_{\mathrm{ijkl}}\left(t\right)\right)-bF\left(I_k^P\left(t\right)\right)+I_0+I_{\mathrm{ijkl}}^F+I_{\mathrm{kl}}^A+v,{\tau }_P\frac{\partial }{\partial t}{I}_k^P\left(t\right)=-I_k^P\left(t\right)+c\sum _{i=1}^S\sum _{j=1}^S\sum _{l=1}^{L\left(k\right)}F\left(I_{\mathrm{ijkl}}\left(t\right)\right)-dF\left(I_k^P\left(t\right)\right)$
I_ijkl(t) being the input current for the neuron collection with a receptive field in the case of section ij of the parameter network k, in which the parameter value I is analyzed, I^D_k(t) being the current in the inhibitory pool, which is coupled to the subnetworks 5 of the parameter k, and S representing the framework variable (size of the search field). I₀ is a diffuse spontaneous background input signal, I^f_ijkl is the sensory input, that is to say the detection information signal from the detection means 2 to the first processing means 3 in the parameter network k, which are sensitive to the parameter value I and have receptive fields in section ij of the search field, this input characterizing the presence of the corresponding parameter value on the corresponding section, and I^A_kj being the parameter information from the storage device 1. ν is the additive Gauss noise, τ the synaptic time constant for the excitatory links, and τ_P the synaptic time constant for the inhibitory links, a, b, c and d are the synaptic ratings. The following values were used in the case of the simulation results illustrated in FIGS. 3 to 6: ν=0.002, τ=5, τ^P=20, a=0.95, b=0.8, c=2.0, d=0.1, I₀=0.025. The value 0.05 was assumed for I^F_ijkl in the presence of the corresponding parameter value I, and the value 0 was assumed in the absence of the corresponding parameter value I. For the parameter information I^A_kj, a value of 0.005 was assumed for the subnetworks 5 which analyze the corresponding parameter values of the reference pattern, and a value of 0 was assumed for other subnetworks.

[0042] The following system of differential equations is used for the dynamic properties of the second processing means 4 in the higher-order processing layer: ${\tau }_H\frac{\partial }{\partial t}{I}^H\left(t\right)=-I_{\mathrm{ij}}\left(t\right)+\hat{a}F\left(I_{\mathrm{ij}}\left(t\right)\right)-\hat{b}F\left(I^{\mathrm{PH}}\left(t\right)\right)+I_0+\hat{w}\sum _{k=1}^K\sum _{l=1}^{L\left(k\right)}F\left(I_{\mathrm{ijkl}}\left(t\right)\right)+v,{\tau }_{\mathrm{PH}}\frac{\partial }{\partial t}{I}^{\mathrm{PH}}\left(t\right)=-I^{\mathrm{PH}}\left(t\right)+\hat{c}\sum _{i=1}^S\sum _{j=1}^{S}F\left(I_{\mathrm{ij}}^H\left(t\right)\right)-\hat{d}F\left(I^{\mathrm{PH}}\left(t\right)\right)$
I^H_ij(t) being the input current for the neuron collection with a receptive field in the case of section ij, I^PH being the corresponding current of the inhibitory pool, τ_H being the synaptic time constant for the excitatory links, τ_PH being the synaptic time constant for the inhibitory links, and â, {circumflex over (b)}, ŵ, ĉ and {circumflex over (d)} being the synaptic ratings. The following values were assumed for the simulation results of FIG. 3 and FIG. 7: τ_H=5, τ_PH=20, â=0.95, {circumflex over (b)}=0.8, ŵ=1,0, ĉ=1.0 and d=0.1.

[0043] The above system of differential equations was integrated numerically for the simulations shown in FIGS. 3 to 7, until a convergence criterion was reached. This convergence criterion consisted in the fact that the neurons in the second processing means 4 are the corresponding higher-order processing layer are polarized, something which corresponds to the following condition: $F\left(I^H{i}_{\max }{j}_{\max }\left(t\right)\right)-\frac{1}{\left(S-1\right)\left(S-1\right)}\sum _{i\ne i_{\max }}\sum _{j\ne j_{\max }}F\left(I_{\mathrm{ij}}^H\left(t\right)\right)>\theta ,$
the index i^maxj_max characterizing the neuron arrangement of the second processing means 4 of the higher-order layer with maximum activity, and the threshold value having been assumed as θ=0.1. The second term on the left-hand side of the above equation corresponds to the mean distracter activity.

[0044] For each parameter, the fixed point of the dynamic behavior is given by the activity of the neuron arrangements in the sublayers with the same parameter value as the reference pattern, and in correspondence with distracter objects which have this parameter value. If, for example, the reference pattern is red, in a parameter network for color, the activity of the sublayer 5 assigned to the parameter value of green is suppressed and the neuron arrangements corresponding to red distracter objects are amplified. In the higher-order layer of the second processing means 4, the neuron arrangements, which correspond to sections ij, which undergo maximum activation in all parameter networks, while the others are suppressed. In other words, the second processing means, which corresponds to section ij and shows all the parameter values which are stimulated and required in accordance with the parameter information of the reference pattern, is activated more strongly, as a result of which the corresponding section ij of the search field is determined as that section in which the reference pattern is located.

[0045] Simulation results which were determined by using the above differential equations with the specified parameter values are illustrated in FIGS. 3 to 7. FIG. 3 shows the search time T as a function of the framework variable S for various types of search. The various types of search are characterized as m, n search by a pair of numbers m and n in each case, m being the number of parameters by which the distracter patterns differ from the reference pattern, and n being the number of parameters by which all the distracter groups differ simultaneously from the reference pattern. In other words, the search addressed above corresponds to a 1,1 search, a standard link search corresponds to a 2,1 search and a triple link search can be a 3,1 or 3,2 search depending on whether the reference pattern differs from all the distracter groups in one or two parameters.

[0046] In the case of the simulation results shown in FIGS. 3 to 7, it was assumed that the patterns in the search field are defined by three parameters, for example color, size and shape, each parameter being capable of assuming two parameter values. The experiment was repeated one hundred times for each search, in each case with different random generated distracters and referenced patterns. Illustrated in FIG. 3, as a result, is the mean value T of the hundred simulated reaction times in ms, as a function of the framework S for a 1,1 search, a 3,2 search, a 2,1 search and a 3,1 search. The gradient of the reaction time with respect to the framework variable is absolutely consistent with the existing experimental results. In accordance with the experimental results, the simulation result of FIG. 3 shows for the 1,1 search that the reference pattern is detected by a parallel processing in the overall search field. Furthermore, the simulation results shown in FIG. 3 show for the standard link search and the triple link search that the reaction time is a linear function of the size of the search field, the gradient of the triple link search for the 3,1 search being somewhat steeper, and that for the 3,2 search being substantially flatter than the 2,1 search or standard search.

[0047] The activity rates in the individual parameter networks which are given by the three branches of the first processing means 3 are illustrated in FIGS. 4 to 6, illustrated correspondingly in each of the figures three curves for the reference pattern activity and three curves for the distracters. FIG. 4 shows a simulation result for a 1,1 search, FIG. 5 shows the simulation result for a 2,2 search, and FIG. 6 shows the simulation result for a 3,1 search. It is to be seen that in the case of the 1,1 and 3,2 searches the convergence times appear to be very slight in all parameter networks, and these types of search therefore appear as searches with parallel processing. In the case of the 3,1 search, the delay in the dynamic response requires more time, and this type of search therefore appears as a search with serial processing, although the basic processing mechanism operates in a parallel fashion. In this case (FIG. 6), the competition present within each parameter network, that is to say for each parameter, delays the convergence of dynamic response for each parameter and, as a consequence of this, also in the higher-order network or the higher-order layer of the second processing means 4. Reference may be made to the slow suppression of the distracter activity in FIG. 6, which illustrates the fundamental competition. FIG. 7 shows the resulting activity rates plotted against time in the higher-order network or the higher-order layer of the second processing means 4 for the same simulation values, which also form the basis of FIGS. 3 to 6. The delayed attainment of the convergence criterion in the 3,1 search is clearly to be seen in FIG. 7.

[0048] The invention has been described in detail with particular reference to preferred embodiments thereof and examples, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention.