Method and parallel processor computing apparatus for determining the three-dimensional coordinates of objects using data from two-dimensional sensors

• US 5,386,370 A
• Filed: 09/21/1993
• Issued: 01/31/1995
• Est. Priority Date: 07/19/1991
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Woo, Steven C.
• Primary Examiner(s): Voeltz, Emanuel T.
• Assistant Examiner(s): CHOI, KYLE JAEHUN
• Application Number:
  US08/124,416
• Time in Patent Office: 497 Days
• Field of Search: 364/516, 364/449, 364/458, 364/460, 235/400, 235/411, 342/126, 342/356, 342/363, 342/357, 342/463, 342/464, 342/465, 342/451
• US Class Current: 701/207
• CPC Class Codes: G01S 5/04 Position of source determined by a plurality of spaced direction-finders

Abstract

First and second passive sensors (14,16), which may be mounted on different earth orbiting satellites, provide relative azimuth and elevation coordinates to sensed objects (A,B,C) such as hostile missiles. Minimum and maximum possible ranges to the objects (A,B,C) along lines-of-sight (18a,18b,18c) from the first sensor (14) are predetermined, and used to calculate "range lines" (24,26,28) which are coincident with the lines-of-sight (18a,18b,18c) and extend from the respective minimum to maximum ranges respectively. The range lines (24,26,28) are transformed into the field of view of the second sensor (16), and matched to the azimuth and elevation coordinates of the respective objects (A,B,C) using a basic feasible solution (greedy) or global optimization algorithm. The approximate points of intersection of lines-of-sight (20a,20b,20c) from the second sensor (16) to the objects (A,B,C) and matched range lines (24,26,28) are calculated, and transformed into coordinates relative to a reference point (10) such as the center of the earth (12). The calculations for the individual objects (A,B,C) may be performed simultaneously using parallel processors (44a,44b,44c) in a single instruction stream--multiple data stream (SIMD) or similar computing arrangement (40).

Claims

1. A method for analyzing electromagnetic radiation from each of a plurality of objects to determine the positions of the objects relative to a predetermined reference point, comprising the steps of:

(a) sensing each object using a first sensor whose position relative to the predetermined reference point is known, the first sensor sensing electromagnetic radiation from each object and providing first angular data defining first lines-of-sight from the first sensor to the respective objects;

(b) sensing each object using a second sensor whose position relative to the predetermined reference point is known, the second sensor sensing electromagnetic radiation from each object and providing second angular data defining second lines-of-sight from the second sensor to the respective objects, said first and second sensors sensing objects over respective angular ranges that include locations at which the angle with respect to the first sensor is greater than the angle with respect to the second sensor, and locations at which the angle with respect to the first sensor is less than the angle with respect to the second sensor;

(c) determining, for each object, a distance range line along its respective first line-of-sight from a predetermined minimum range to a predetermined maximum range independent of the relative intensities of electromagnetic radiation sensed by each sensor from said object;

(d) converting the range line for each object relative to the first sensor to range line coordinates relative to the second sensor independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object;

(e) matching the respective second angular data for each object to said range line coordinates for the respective object independent of the relative intensities of electromagnetic radiation sensed by each sensor from each other;

(f) determining, for each object relative to the second sensor and independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object, a position point which corresponds to the closest approach of its respective second line-of-sight to its respective range line; and

(g) determining, for each object relative to the predetermined reference point and independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object, coordinates of its respective position point;

said coordinates of the respective position points relative to the predetermined reference point specifying said positions of the respective objects relative to the reference point.

2. A method as in claim 1, in which step (e) comprises matching the second angular data for each object to said range line coordinates for the respective object using a basic feasible solution algorithm.

3. A method as in claim 1, in which step (e) comprises the substeps, for each object, of:

(h) calculating a perpendicular distance from the respective second line-of-sight to each of the range lines; and

(i) matching the respective second angular data to the range line for which said calculated perpendicular distance is minimum.

4. A method as in claim 1, in which step (e) comprises matching said second angular data for each object to said range line coordinates for the respective object using a global optimization algorithm.

5. A method as in claim 4, in which the global optimization algorithm is the Munkres Assignment Problem Algorithm.

6. A method as in claim 1, in which step (f) comprises calculating, for each object, its respective position point as the intersection of its respective range line with a line which perpendicularly intersects its respective range line and its respective second line-of-sight.

7. A method for analyzing electromagnetic radiation from each of a plurality of objects to determine the three-dimensional coordinates of the object relative to a predetermined reference point, comprising the steps of:

(a) sensing each object using a first sensor whose three-dimensional coordinates relative to the predetermined reference point are known, the first sensor sensing electromagnetic radiation from each object and providing first azimuth and elevation coordinates defining first lines-of-sight from the first sensor to the respective objects;

(b) sensing each object using a second sensor whose three-dimensional coordinates relative to the predetermined reference point are known, the second sensor sensing electromagnetic radiation from each object and providing second azimuth and elevation coordinates defining second lines-of-sight from the second sensor to the respective objects, said first and second sensors sensing objects over respective elevation ranges that include locations at which the elevation with respect to the first sensor is greater than the elevation with respect to the second sensor, and locations at which the elevation with respect to the first sensor is less than the elevation with respect to the second sensor;

(c) determining for each object, as a predetermined function of the respective first azimuth and elevation coordinates and said three-dimensional coordinates of the first sensor relative to the predetermined reference point, first three-dimensional coordinates relative to the first sensor of minimum and maximum endpoints of a distance range line coincident with the respective first line-of-sight and independent of the relative intensities of electromagnetic radiation sensed by each sensor from said object, the minimum endpoint being a predetermined minimum range from the first sensor and the maximum endpoint being a predetermined maximum range from the first sensor;

(d) determining for each object, independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object and as a predetermined function of (1) said first three-dimensional coordinates of the minimum and maximum endpoints of the respective range line, (2) said three-dimensional coordinates of the first sensor relative to the predetermined reference point and (3) said three-dimensional coordinates of the second sensor relative to the predetermined reference point, second three-dimensional coordinates relative to the second sensor of the minimum and maximum endpoints of the respective range line;

(e) matching the respective second azimuth and elevation coordinates for each object to said second three-dimensional coordinates of the minimum and maximum endpoints of the range line for the respective object independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object;

(f) determining for each object, as a predetermined function of the respective second azimuth and elevation coordinates and said second three-dimensional coordinates of the minimum and maximum endpoints of the respective range line, and independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object, first three-dimensional coordinates relative to the second sensor of a position point which corresponds to the closest approach of its respective second line-of-sight to its respective range line; and

(g) determining for each object, as a predetermined function of said first three-dimensional coordinates of its respective position point and said three-dimensional coordinates of the second sensor relative to the predetermined reference point and independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object, second three-dimensional coordinates relative to the predetermined reference point of its respective position point;

said second three-dimensional coordinates of the respective position points specifying said positions of the respective objects relative to the predetermined reference point.

8. A method as in claim 7, in which step (e) comprises matching the respective second azimuth and elevation coordinates of each object to said second three-dimensional coordinates of the minimum and maximum endpoints of the respective range line using a basic feasible solution algorithm.

9. A method as in claim 7, in which step (e) comprises the substeps, for each object, of:

(h) calculating a perpendicular distance from the respective second line-of-sight to each of the range lines; and

(i) matching the respective second azimuth and elevation coordinates to the second three-dimensional coordinates of the minimum and maximum endpoints of the respective range line for which said calculated perpendicular distance is minimum.

10. A method as in claim 7, in which step (e) comprises matching the respective second azimuth and elevation coordinates of each object to said second three-dimensional coordinates of the minimum and maximum endpoints of the respective range line using a global optimization algorithm.

11. A method as in claim 10, in which the global optimization algorithm is the Munkres Assignment Problem Algorithm.

12. A method as in claim 7, in which step (f) comprises calculating, for each object, its respective position point as the intersection of its respective range line with a line which perpendicularly intersects its respective range line and its respective second line-of-sight.

13. An apparatus for analyzing electromagnetic radiation from each of a plurality of objects to determine the positions of the objects relative to a reference point, comprising:

a first sensor whose position relative to the predetermined reference point is known for sensing electromagnetic radiation from each of the objects and providing first angular data defining first lines-of-sight from the first sensor to each respective object;

a second sensor whose position relative to the predetermined reference point is known for sensing electromagnetic radiation from each of the objects and providing second angular data defining second lines-of-sight from the second sensor to each respective object, said first and second sensors sensing objects over respective angular ranges that include locations at which the angle with respect to the first sensor is greater than the angle with respect to the second sensor, and locations at which the angle with respect to the first sensor is less than the angle with respect to the second sensor;

first parallel processing means for simultaneously determining, for each object, a distance range line along its respective first line-of-sight from a predetermined minimum range to a predetermined maximum range independent of the relative intensities of electromagnetic radiation sensed by each sensor from said object;

second parallel processing means for simultaneously converting the range line for each object relative to the first sensor means to range line coordinates relative to the second sensor independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object;

third parallel processing means for simultaneously matching the respective second angular data for each object to said range line coordinates for the respective object independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object;

fourth parallel processing means for simultaneously determining, for each object relative to the second sensor and independent of the relative intensities of electromagnetic radiation sensed by each sensor from each object, a position point which corresponds to the closest approach of its respective second line-of-sight to its respective range line; and

fifth parallel processing means for simultaneously determining, for each object, coordinates relative to the predetermined reference point of its respective position point;

said coordinates of the respective position points relative to the predetermined reference point specifying said positions of the respective objects relative to the predetermined reference point.

14. An apparatus as in claim 13, in which the first to fifth parallel processing means are integral and comprise, in combination, a single instruction stream--multiple data stream (SIMD) computing means including an operating program temporarily stored in volatile memory.

15. An apparatus as in claim 13, in which the first to fifth parallel processing means are integral and comprise, in combination, a single instruction stream--multiple data stream (SIMD) computing means including an operating program permanently stored in non-volatile memory.

16. An apparatus as in claim 13, in which said first to fifth parallel processing means are integral and comprise, in combination, a single instruction stream--multiple data stream (SIMD) computing means including:

a main processing element including;

computing means;

main program storage means for storing main program data including instructions for simultaneous execution by the first to fifth parallel processing means; and

main data storage means for storing data including said positions of the first and second sensors relative to the predetermined reference point;

a plurality of parallel processing elements for processing data associated with the objects respectively; and

bus line means for interconnecting the main processing element with each of the parallel processing elements such that instructions generated by the main processing element are simultaneously executed by all of the parallel processing elements in parallel;

each parallel processing element including;

computing means for executing said instructions from the main processing means;

parallel program storage means for storing program data which implements the functions of said first to fifth parallel processing means; and

parallel data storage means for storing data associated with the respective object.

17. An apparatus as in claim 16, in which the parallel program storage means of each parallel processing element includes a non-volatile memory for permanently storing said program data.