Lattice based dynamic programming classification system

• US 5,473,731 A
• Filed: 07/20/1993
• Issued: 12/05/1995
• Est. Priority Date: 07/20/1993
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Seligson, Daniel
• Primary Examiner(s): Davis, George B.
• Application Number:
  US08/094,468
• Time in Patent Office: 868 Days
• Field of Search: 395/27, 395/24, 395/23, 395/11, 395/22, 364/807
• US Class Current: 706/28
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

An integrated circuit lattice chip for computation of dynamic programming (DP) recursions uses identical nodal processor units arranged in regular lattice form. Interconnections between processor units on the chip are programmable using non-volatile EEPROM connections. The nodal processor units have computing element for generating a distance metric representative of the difference between the i^th and j^th elements of the unknown and prototype vectors that is combined with a maximum partial or minimum cumulative distance metric of preselected set of lower order nodal processors to produce an optimal (maximum or minimum) cumulative distance value for unknown and prototype vector elements with indices equal to or less than (i, j). A network is also provided for identifying the optimal path through the lattice for use in designing a DP classification system.

Claims

1. A lattice-based dynamic programming (DP) classification system that compares an unknown vector with a prescribed set of prototype vectors comprising:

a) a lattice controller for system control, for system configuration, for selecting a prescribed prototype vector for comparison with the unknown vector for storing of processed results of a DP lattice network, for determining an optimal lattice path, and for determining an optimal cumulative distance value corresponding to the optimal lattice path;

b) a DP lattice network controlled by the lattice controller for producing processed results by use of processing means operating on the prescribed prototype vector and the unknown vector, the processing means comprising means for computing a cumulative distance between the unknown vector and a prototype vector, means for providing optimal path information to the lattice controller, a first set of input terminals for accepting the unknown vector, a second set of input terminals for accepting a prototype vector, a set of processed data output terminals for outputting the processed results, and a set of control terminals connected to the lattice controller for transmitting controlled lattice path information;

c) a vector generator controlled by the lattice controller comprising means for generating at the vector generator output terminals a prototype vector selected from the prescribed set of prototype vectors, the output terminals connected to the second set of the DP lattice network input terminals; and

d) a vector quantizer (VQ) comprising a VQ code book of prescribed prototype vectors, with the VQ data input connected to the lattice controller for classifying the unknown vector based on the optimal lattice path by outputting a VQ code corresponding to a prescribed prototype vector that most closely corresponds to the unknown vector.

2. The system of claim 1, wherein the DP lattice network comprises a MXN array of nodal processors, a first set of M input terminals for accepting an unknown vector with M vector components, a second set of N input terminals for accepting a prescribed prototype vector with N vector components, each nodal processor of the MXN array of nodal processors is identified by coordinates (i,j), where 0≦

i≦

(M-1) is a row index and 0≦

j≦

(N-1) is a column index, wherein the nodal processor, identified by coordinate indices (i,j), for processing the i^th unknown vector component and the j^th prototype vector component further comprises;

a) an output terminal for outputting the nodal processor output of a cumulative distance value;

b) an input terminal for inputting the i^th component of the unknown vector from the first set of M input terminals;

c) an input terminal for receiving the j^th component of the prescribed prototype vector from the second set of N input terminals;

d) a local distance processor unit for calculating, and producing, at an output terminal, a distance metric representative of an absolute difference between the i^th unknown vector component and the j^th prescribed prototype vector component;

e) a comparator/selector unit having a multiplicity of input terminals, each input terminal connected to a distinct nodal processor output signal of a nodal processor identified by coordinate indices (i-1, j-l) for ≧

0, the comparator/selector unit for comparing the output signal of each nodal processor and selecting for output at an output terminal the input terminal with a nodal processor output signal satisfying an optimality criterion; and

f) an adder unit with an output, a first input connected to the output terminal of the local distance processor, and a second input connected to the output terminal of the comparator/selector unit, the adder unit output connected to the nodal processor output terminal for producing at the adder unit output a signal representative of a cumulative distance measure of the (i, j) nodal processor.

3. The system of claim 2 wherein the nodal processor further comprises a storage means at the adder unit output for storing the adder unit output signal representative of a cumulative distance and operating under control of the lattice controller.

4. The system of claim 2 wherein the nodal processor further comprises:

a) an encoder network for generating a binary coded signal identifying the nodal processor whose output was selected by the comparator/selector unit; and

b) a storage unit whose content is addressable by the lattice controller for temporarily storing the binary coded signal generated by the encoder network for use by the lattice controller in establishing the optimal lattice path.

5. The system of claim 4 wherein the storage unit is a parallel-in serial-out shift register.

6. The system of claim 2, wherein the nodal processor further comprises:

a) binary gain scaling means controlled by the lattice controller, the binary gain scaling means for scaling the output of the nodal processor;

b) saturation detection means coupled to the output terminal of the nodal processor, having a threshold value that is compared with the nodal processor output, the saturation detection means for producing a scaling request signal at the saturation detection means output if the threshold value is exceeded; and

c) a storage means for temporary storing the scaling request signal, the storage means being accessible for reading by the lattice controller.

7. The system of claim 2 wherein the prescribed optimality criterion selects the input terminal having a smallest nodal processor output signal.

8. The system of claim 2 wherein the prescribed optimality criterion selects the input terminal having a largest nodal processor output signal.

9. The system of claim 2 wherein the comparator/selector unit further comprises means for selecting a first or a second optimality criteria, the first optimality criteria for selecting the input terminal having a smallest nodal processor output signal, and the second optimality criteria for selecting the input terminal having a largest nodal processor output signal.

10. The system of claim 1, further comprising a lattice controller for controlling means, for scaling intermediate lattice network results and for expanding the dynamic range of the lattice network.

11. The system of claim 10 wherein the lattice controller applies binary scaling to the nodal processor output of each nodal processors connected to a prescribed prototype vector component with prototype index less than j, and applies binary scaling to the output of each adder unit in nodal processors connected to a prototype vector component with prototype index equal to and greater than j, whenever the lattice controller senses a scaling request indicator in any processor having a prototype index of j.

12. A modular chip large-scale integrated circuit, lattice-based dynamic programming nodal processor array for use in a vector classification system, the modular chip comprising:

a) a set of M-input terminals, indexed 1≦

i≦

M, for inputting an M-component unknown data vector;

b) a set of N-input terminals, indexed 1≦

j≦

N, for inputting an N-component prototype data vector;

c) a set of N-output terminals for outputting an N-component cumulative distance vector;

d) a set of lattice controller terminals for receiving control and configuration signals from a lattice controller and for sending status signals to a lattice controller;

e) a controller interface connected to the set of lattice controller terminals, the controller interface for formatting and sending status signals to a lattice controller, for generating and distributing control signals to on-chip nodal processors; and

f) a lattice network having MXN nodal processors, each nodal processor indexed by a two-dimensional coordinate index (i,j) where index 1≦

i≦

M corresponds to the i^th component of the M-component unknown data vector, and index 1≦

j≦

N corresponds to the j^th component of the N-component prototype data vector, the (i,j) nodal processor comprising;

i) an output terminal for outputting a cumulative distance output signal;

ii) a first input terminal connected to the i^th terminal of the set of M-input terminals;

iii) a second input terminal connected to the j^th terminal of the set of N-input terminals;

iv) a local distance processor connected to the first input terminal and to the second input terminal, the local distance processor for producing at an output terminal a distance metric representative of the distance between the i^th unknown vector component and the j^th prototype vector component;

v) a comparator/selector circuit having a multiplicity of input cumulative distance terminals connected to the output terminal of a set of lower-order nodal processors having an unknown vector component index of i-1 and prototype vector component indices equal to (j-l) for 0≦

l≦

L where L represents a prescribed limit of elasticity, and an output data terminal, the comparator/selector circuit for presenting at the output data terminal a lower-order input cumulative signal distance corresponding to a smallest value of the set of lower-order processor output signals;

vi) an adder circuit with a first input connected to the local distance processor output terminal, a second input connected to the output data terminal of the comparator/selector circuit for producing at the adder circuit output a sum signal combining a signal from the first input and a signal from the second input, the sum signal being the (i,j) nodal processor output cumulative distance signal; and

g) each (M,j) nodal processor adder circuit output connected to the j^th terminal of the set of N-output terminals.

13. The integrated circuit of claim 12 wherein each adder circuit further comprises means for indicating potential overflow by comparing the adder circuit output sum signal with a programmable threshold value and, if the threshold value is exceeded, generating a scaling request signal for use by an external controller.

14. The integrated circuit of claim 13 wherein each nodal processor further comprises:

a) a local distance processor binary scaling means connected to the local processor output terminal for binary scaling of the distance metric and connected to the lattice controller terminals for control by a lattice controller; and

b) a nodal processor output binary scaling means connected to the nodal processor output for binary scaling the (i j) cumulative distance signal, and connected to the lattice controller terminals for control by a lattice controller.

15. The integrated circuit of claim 14 further comprising temporary memory means for storing a scaling indicator signal indicating a binary scaling value of both the local distance processor and the nodal processor output, the temporary memory means connected to the set of lattice control terminals for read access by an external controller.

16. The integrated circuit of claim 15 wherein the temporary memory means is a parallel-in serial-out shift register.

17. The integrated circuit of claim 12 wherein the comparator/selector circuit further comprises means for identifying and encoding the input cumulative distance terminal of the multiplicity of cumulative distance terminals selected, and temporary storage means connected to the set of lattice control terminals for read access by an external controller for temporarily storing the encoded identification of the selected input terminal for use in establishing an optimal path through the lattice network.

18. The integrated circuit of claim 17 wherein the temporary storage means is a parallel-in serial-out register.

19. The integrated circuit of claim 12 further comprising a controller interface network for exchanging control information and signals with an external controller.

20. The integrated circuit of claim 19 wherein the controller interface further comprises means for generating and distributing, within the modular chip large-scale integrated circuit a switched-capacitor-resistor clock for binary gain control, the switched capacitor resistor clock from a clock signal provided by an external controller.

21. The integrated circuit of claim 12 further comprising externally controllable gates for opening and closing inter-nodal processor connections.

22. The integrated circuit of claim 21 wherein the externally controllable gates are field effect transistors.

23. The integrated circuit of claim 21 wherein the externally controllable gates are floating gate transistors with selectively pre-programmed stored charges for controlling the floating gate transistor drain to source conductance to act as an interconnection weight.

24. The integrated circuit of claim 12 further comprising means for converting the (i, j) nodal processor output cumulative distance signal into a conditional probability value representing a probability of the j^th prototype vector element given an i^th unknown vector element.

25. The modular chip of claim 12 with auxiliary input and output terminals for interconnecting similar modular chips into a P×

Q chip-array that can operate on an unknown vector with P·

M elements and a prototype vector with Q·

N elements, a prescribed elasticity limit of L prior nodal processor cumulative distance output signals, the modular chip further comprising;

(a) a first set of cumulative distance input terminals for each of M rows of nodal processors with L-(j-1) terminals connected to the input cumulative distance terminals of the j^th nodal processor, where 1≦

j≦

L, for each of M rows;

(b) a second set of (N+L-2) with cumulative distance input terminals, indexed k through k+L-1, connected to distinct input cumulative distance terminals of each nodal processor at coordinates (i,j)=(1,k+1); and

(c) a first set of L cumulative distance output terminals for each of M rows of nodal processors, each cumulative output terminal connected to a distinct nodal processor output located at coordinates (i,j)=(i,N-l) for 0≦

l≦

L-1.