Method and apparatus for using a neural network to extract an optimal number of data objects from an available class of data objects

• US 5,675,712 A
• Filed: 04/18/1995
• Issued: 10/07/1997
• Est. Priority Date: 05/02/1994
• Status: Expired due to Fees

• Current Assignee: Commissariat a L'Energie Atomique (French Alternative Energies and Atomic Energy Commission)
• Original Assignee: Commissariat a L'Energie Atomique (French Alternative Energies and Atomic Energy Commission)
• Inventors: Herault, Laurent
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): CHUNG, JI YONG DAVID
• Application Number:
  US08/424,011
• Time in Patent Office: 903 Days
• Field of Search: 395/22, 395/24, 395/21, 395/23
• US Class Current: 706/20
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology

Abstract

Method and apparatus for selecting an optimal number of trajectories from an available class of potential trajectories in a velocimetry application. In an exemplary method, a neural network is constructed wherein each neuron in the network represents a trajectory in the overall class. A binary output of each neuron indicates whether the trajectory represented by the neuron is to be selected. In the exemplary method, the neural network is initialized with a starting solution wherein the network is in an initially converged state. The network is then alternately excited and constrained so that it settles to additional converged states. During excitation, correction factors including a set-size maximizing term are applied to neuron input potentials. During constraint, the set-size maximizing terms are interrupted. Each time the network converges, the outputs of the neurons in the network are decoded to obtain a subset of trajectories which are to be selected. The excitation and constraint phases are then repeated in an attempt to obtain larger and larger subsets of trajectories to be selected. Once the excitation and constraint phases have been repeated a suitable number of times, the trajectories identified in the largest obtained subset of trajectories are selected.

Claims

1. A method for selecting an optimal number of trajectories in a velocimetry application, comprising the steps of:

receiving as input a class of potential trajectories and a matrix of pair-wise relations wherein each pair-wise relation indicates whether two potential trajectories in the received class are related to one another;

constructing a neural network including a plurality of neurons, wherein each neuron represents a potential trajectory in the received class, wherein a binary output of each neuron is based on an input potential of the neuron which is in turn based on outputs of neurons in the network, and wherein the output of each neuron indicates whether a represented potential trajectory is to be selected from the received class;

initializing the neural network with a valid initial solution, wherein the input potential and the output of each neuron in the network are stationary and the network is in an initially converged state;

exciting the network by applying correction factors to the input potentials of neurons in the network, wherein a correction factor applied to the input potential of a neuron includes a set-size maximizing term and is based in part on pair-wise relations associated with the neuron and on outputs of neurons in the network;

constraining the network by applying correction factors which do not include a set-size maximizing term to the input potentials of neurons in the network so that the network achieves a newly converged state, corresponding to an additional valid solution, wherein the input potential and the output of each neuron in the network are stationary;

decoding the outputs of the neurons in the network to establish a list of trajectories to be selected from the received class;

repeating said steps of exciting the network, constraining the network, and decoding the outputs of the network to establish a plurality of lists of trajectories to be selected from the received class; and

selecting the trajectories identified in a longest list of trajectories to be selected from the received class.

2. The method of claim 1, wherein said steps of exciting the network and constraining the network are accomplished by asynchronously scanning the network and updating input potentials and corresponding outputs of neurons in the network.

3. The method of claim 2, wherein a transition from said step of exciting the network to said step of constraining the network is accomplished by modifying the use of correction factors in updating input potentials based on a number of times the network has been excited since a last convergence of the network.

4. The method of claim 1, wherein said steps of exciting the network and constraining the network are carried out in an attempt to obtain a list of trajectories which is longer than a previously longest list of trajectories.

5. The method of claim 4, wherein said repeating step is carried out a fixed number of times which is set by a user of the method based on a particular velocimetry application.

6. The method of claim 1, wherein each pair-wise relation is a binary number indicating whether two neurons are related to one another, and wherein said steps of exciting the network and constraining the network are carried out in an attempt to select a maximum number of trajectories which are not related.

7. The method of claim 6, wherein a correction factor includes an inhibiting term and an activating term, wherein the inhibiting term tends to inhibit a neuron when the neuron is activated and related to at least one other neuron which is activated, and wherein the activating term tends to activate a neuron when the neuron is inhibited and not related to other neurons which are activated.

8. The method of claim 1, wherein each pair-wise relation is a binary number indicating whether two neurons are related to one another, and wherein said steps of exciting the network and constraining the network are carried out in an attempt to select a maximum number of trajectories which are related.

9. The method of claim 8, wherein a correction factor includes an inhibiting term and an activating term, wherein the inhibiting term tends to inhibit a neuron when the neuron is activated and not related to other neurons which are activated, and wherein the activating term tends to activate a neuron when the neuron is inhibited and related to other neurons which are activated.

10. A device for selecting an optimal number of trajectories in a velocimetry application, comprising:

means for receiving as input a class of potential trajectories and a matrix of pair-wise relations wherein each pair-wise relation indicates whether two potential trajectories in the received class are related to one another;

a neural network including a plurality of neurons, wherein each neuron represents a potential trajectory in the received class, wherein a binary output of each neuron is based on an input potential of the neuron which is in turn based on outputs of neurons in the network, and wherein the output of each neuron indicates whether a represented object is to be selected from the received class;

means for initializing the neural network with a valid initial solution, wherein the input potential and the output of each neuron in the network are stationary and the network is in an initially converged state;

means for exciting the network by applying correction factors to the input potentials of neurons in the network, wherein a correction factor applied to the input potential of a neuron includes a set-size maximizing term and is based in part on pair-wise relations associated with the neuron and on outputs of neurons in the network;

means for constraining the network by applying correction factors which do not include a set-size maximizing term to the input potentials of neurons in the network so that the network achieves a newly converged state, corresponding to an additional valid solution, wherein the input potential and the output of each neuron in the network are stationary;

means for decoding the outputs of the neurons in the network to establish a list of trajectories to be selected from the received class;

means for storing the list of trajectories;

means for repeatedly exciting the network and constraining the network in order to decode, establish, and store a plurality of lists of trajectories to be selected from the received class; and

means for comparing the plurality of lists to one another and for choosing a longest list of trajectories to be selected.

11. A device for selecting an optimal number of data objects from a class of available data objects, comprising:

a first memory storing input potentials corresponding to neurons in a neural network, wherein each neuron represents an object in the available class;

a second memory storing binary outputs corresponding to the neurons, wherein each output indicates whether a represented object is to be selected;

a third memory storing pair-wise relations, wherein each pair-wise relation indicates whether two neurons in the neural network, and therefore two objects in the available class, are related to one another;

a number generating circuit generating a number which corresponds to a neuron in the neural network;

an inhibiting circuit connected to said number generating circuit, said second memory, and said third memory computing, for a neuron specified by the number generating circuit, an inhibiting factor based on the outputs stored in said second memory and based on the pair-wise relations stored in the third memory;

an activating circuit connected to said number generating circuit, said second memory, and said third memory computing, for a neuron specified by the number generating circuit, an activating factor based on the outputs stored in said second memory and based on the pair-wise relations stored in the third memory;

an interruption device generating an interruption factor based on a number of times neurons in the neural network have been updated;

combining means connected to said inhibiting circuit, said activating circuit, and said interruption device for combining the inhibiting factor, the activating factor, and the interruption factor to create an input potential correction factor for a neuron specified by the number generating circuit;

updating means for applying the input potential correction factor to update a stored input potential of a neuron specified by the number generating circuit and for updating a stored output of the neuron specified by the number generating circuit based on the updated stored input potential;

controlling means for varying the number generated by the number generating circuit to update multiple neurons in the network and to maximize a number of stored outputs indicating that a represented object is to be selected.

12. A method for extracting a subset of trajectories from a class of potential trajectories in a velocimetry application using a neural network, comprising the steps of:

receiving as input the class of potential trajectories;

constructing a recursive neural network from potential trajectories and relations between potential trajectories by associating with each trajectory i a binary output p_i (t) of a formal neuron at a time t, wherein p_i (t)=1 indicates that a trajectory i belongs to a prevailing subset of trajectories at time t and p_i (t)=0 indicates that a trajectory i does not belong to a prevailing subset of trajectories at time t;

initializing the output p_i (t) and a potential u_i (t) of each neuron i such that, for each neuron i, p_i (t=0)=1 when u_i (t=0)≧

0 and p_i (t=0)=0 when u_i (t=0)≦

0;

using a recursive dynamic operation of the neural network to update outputs of neurons in the network;

using an interruption process to control the recursive dynamic operation of the neural network in order to obtain maximized subsets of trajectories in pairs, wherein trajectories in a pair are one of a) related to one another and b) not related to one another, wherein an obtained maximized subset cannot be included in an obtainable subset having a size which is larger than the obtained maximized subset, and wherein maximized subsets are obtained by repeatedly attempting to increase a size of a prevailing subset; and

choosing a largest maximized subset from a list of maximized subsets obtained as a result of said steps of using a recursive dynamic operation of the neural network and using an interruption process.

13. A method according to claim 12, wherein said steps of using a recursive dynamic operation of the neural network and using an interruption process comprise the additional steps of:

asynchronously updating, in one of i) a random fashion and ii) a sequential fashion, the neurons of the network by scanning the neurons in succession and applying to the potential of each scanned neuron a previously calculated correction factor which is dependent on the values of the outputs of other neurons in the network and on relations between potential trajectories; and

decoding the outputs of the neurons in the network to obtain a list of subsets of trajectories in pairs, wherein trajectories in a pair are one of

     1) related to one another and

     2) not related to one another, and wherein each subset of trajectories in the list is maximized so that it cannot be included in an obtainable subset of trajectories having a size larger than the subset in the list.

14. A device for extracting a subset of trajectories from a class of potential trajectories in a velocimetry application using a neural network, wherein said neural network comprises:

a selection circuit for selecting and providing an output corresponding to an integer in a range 1 to N;

a first table memory of outputs p_i of neurons in the neural network, wherein said first table memory receives the output of said selection circuit;

a second memory of relations between trajectories;

a third table memory of potentials of neurons, wherein said third table memory receives the output of said selection circuit;

a fourth table memory, coupled to the output of said selection circuit, of last variations of potentials of neurons;

a first computing circuit, coupled to outputs of said first and second memories and receiving the output of said selection circuit, computing a value A·

p_i ·

T({p_j }), wherein A is a positive real number and wherein T is a function of outputs p_j (t) of network neurons at a time t which correspond to trajectories which are one of a) related to a neuron i and b) not related to a neuron i;

a second computing circuit, coupled to outputs of said first and second memories and receiving the output of said selection circuit, computing a value B·

(1-p_i)·

S({p_j }), wherein B is a positive real number and wherein S is a function of outputs p_j (t) of network neurons at a time t which correspond to objects which are one of

     1) related to a neuron i and

     2) not related to a neuron i;

a third computing circuit, coupled to outputs of said first and second memories and receiving the output of said selection circuit, computing a value C·

R({p_j }), wherein C is a positive real number and wherein R is a function indicating a size of a subset of potential trajectories at a last convergence of the neural network;

an interruption device connected to an output of said third computing circuit and to outputs of said fourth memory;

a first adder receiving outputs of said first and second computing circuits and said interruption device and having an output connected to an input of said fourth memory;

a second adder receiving outputs of said third memory and said first adder and having an output connected to an input of said third memory; and

a thresholding function circuit receiving an output of said second adder and having a binary output connected to an input of said first memory.