Clustering and associate processor

• US 5,404,561 A
• Filed: 07/06/1993
• Issued: 04/04/1995
• Est. Priority Date: 04/19/1989
• Status: Expired due to Term

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Castelaz, Patrick E.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/088,634
• Time in Patent Office: 637 Days
• Field of Search: 395/650, 395/700, 395/800
• US Class Current: 712/17
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06N 3/02 Neural networks
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51

Abstract

A clustering and assignment processor (40) for correlating set (12) of two-dimensional data points (14). Clustering is performed by treating each data point (14) as a mass subject to gravitational attraction by other data points (14). The data points (14) are permitted to move in data space until all data points (14) in particular regions (16) of the data set (12) fall into a single point, or centroid (18). Individual data points (14) and correlated regions (16) of successive data sets (12) are then correlated by means of a resonant descent technique, which determines the distance and direction of individual data points (14) from a chosen data point (108). The processor (40) then matches a pair of two data points (12) with the chosen data point (108) which are equidistant and collinear with the chosen data point (108).

Claims

1. A system for processing a series of successive arrays of two dimensional data points in a predetermined area of two-dimensional data space comprising:

means for receiving said data points,

a plurality of interconnected processing cells, said processing cells having addresses that represent each possible two-dimensional data point in said predetermined area, said processing cells each having a

means for storing the original address of all the data points said processing cells contain;

means for interconnecting selected pairs of processing cells containing data points;

means for calculating a movement vector for each data point, the movement vector being a function of the vector sum of vectors indicating the direction and distance of surrounding data points, said movement vector establishing a direction of movement for said data point;

means for transferring each data point in a processing cell to a neighboring processing cell in a direction determined by said movement vector, wherein said movement is repeated for each data point until all data points within a given region of said array occupy a single processing cell, whereby all data points from a given region of each of said successive arrays can be associated with said single processing cell, said processing cells having a means for reflecting received pulses; and

means for correlating individual data points in one of said regions of said arrays with individual data points in corresponding regions in previous and subsequent arrays in said series of successive arrays, wherein said means for correlating further comprises a means for transmitting a pulse from a chosen processing cell in said one region to processing cells in corresponding regions in the previous and subsequent cells, said transmitted pulse being reflected by said previous and said subsequent cells, means for sensing when said chosen processing cell receives reflected pulses substantially simultaneously from processing cells lying along a linear path with said chosen processing cell, and means for determining the address of the processing cell which reflected said simultaneous pulses, whereby said processing cells reflecting simultaneous pulses are correlated with each other and with said chosen processing cell.

2. The system of claim 1 wherein said two-dimensional data points represent object reports originating from sensors.

3. The system of claim 1 wherein said means for interconnecting comprises a data bus architecture capable of connecting each processing cell to every other processing cell.

4. The system of claim 1 wherein said processing cells are arranged in a two dimensional spray.

5. The system of claim 1 wherein said means for calculating a movement vector further comprises, a thresholding means for disregarding surrounding data points when the distance of the surrounding data point from said data point is greater than a predetermined threshold.

6. The system of claim 1 wherein said processing cells include a means for reflecting received pulses, and wherein the system further comprises:

means for correlating individual data points in one of said regions of said arrays with individual data points in corresponding regions in previous and subsequent arrays in said series of successive arrays, wherein said means for correlating further comprises a means for transmitting a pulse from a chosen processing cell in said one region to processing cells in corresponding regions in the previous and subsequent arrays, said transmitted pulse being reflected by said previous and said subsequent cells, means for sensing when said chosen processing cell receives reflected pulses substantially simultaneously from processing cells lying along a linear path with said chosen processing cell, and means for determining the address of the processing cells which reflected said simultaneous pulses, whereby said processing cells reflecting simultaneous pulses are correlated with each other and with said chosen processing cell.

7. The system of claim 6 wherein said means for transmitting a pulse includes means for directing said pulses in discrete angular directions 180 degrees apart.

8. The system of claim 6 wherein said means for sensing when pulses are received substantially simultaneously further comprises means for comparing the difference in the time said signals are received, with a predetermined threshold, and means for amplifying the transmission of said pulse when said threshold is exceeded.

9. The system of claim 6 wherein said pulse is transmitted along a conductor.

10. The system of claim 6 wherein said pulse is transmitted by means of electromagnetic or acoustic radiation.

11. The system of claim 6 wherein said pulse is transmitted through a data bus structure to selected processing cells.

12. The system of claim 1 further comprising means for measuring the distance of the original location of each data point from said single processing cell, wherein said distances for each data point in a region creates a characteristic histogram, whereby corresponding regions in said successive arrays can be correlated.

13. A method for processing a series of successive arrays of two-dimensional data points in said predetermined area of two dimensional data space, said method comprising:

receiving data points in a plurality of interconnected processing cells, said processing cells having addresses that represent each possible two-dimensional data point in said predetermined area, said processing cells each having a means for storing the original address of all the data points it contains;

interconnecting selected pairs of processing cells containing data points;

calculating a movement vector for each data point, the movement vector being a function of the vector sum of vectors indicating the direction and distance of surrounding data points, said movement vector establishing a direction of movement for said data point; and

transferring each data point in a processing cell to a neighboring processing cell in a direction determined by said movement vector, wherein said transfer is repeated for each data point until all data points within a given region of said array occupy a single processing cell, whereby all data points from a given region of each of said successive arrays can be associated with said single processing cell.

14. The method of claim 13 further comprising:

correlating individual data points in one of said regions of said arrays with individual data points in corresponding regions in previous and subsequent arrays in said series of successive arrays, wherein said step of correlating further comprises the steps of transmitting a pulse from a chosen processing cell in said one region to processing cells in corresponding regions in the previous and subsequent cells, reflecting said transmitted pulse by said previous and subsequent cells, sensing when said chosen processing cell receives reflected pulses substantially simultaneously from processing cells lying along a linear path with said chosen processing cells, and determining the address of the processing cell which reflected said simultaneous pulses, whereby said processing cells reflecting simultaneous pulses are correlated with each other and with said chosen processing cell.

15. A system for correlating a multiplicity of two-dimensional data points in a series of successive arrays of said two dimensional data points representing locations of moving targets in a predetermined area of two-dimensional data space for comprising:

means for receiving said data points,

a plurality of interconnected processing cells, said processing cells having addresses that each represent one of the possible two-dimensional data points,

means for interconnecting selected pairs of processing cells containing data points;

means for repetitively calculating a movement vector for each data point in a processing cell and transferring said data point to a neighboring processing cell located in a direction determined by the movement vector until all data points within a given region of said array occupy a single processing cell, said movement vector based on a gravitational-type rule in which the data points are assumed to have an attractive force related to the distance in the data space between the data points, the movement vector for each data point being a function of the vector sum of the attractive forces of all data points within a predetermined distance in the data space from said data point, and

means for correlating individual data points in one of said regions of said arrays with individual data points in corresponding regions in previous and subsequent arrays in said series of successive arrays, wherein said means for correlating further comprises a means for transmitting a pulse from a chosen processing cell in said one region to processing cells in corresponding regions in the previous and subsequent cells, said transmitted pulse being reflected by said previous and said subsequent cells, means for sensing when said chosen processing cell receives reflected pulses substantially simultaneously from processing cells lying along a linear path with said chosen processing cell, and means for determining the address of the processing cell which reflected said simultaneous pulses, whereby said processing cells reflecting simultaneous pulses are correlated with each other and with said chosen processing cell.