Abstract:
Navigation by interpretation of images of parallelogram corner points of a ground beacon array. A video camera senses images of the beacon array and a computer interprets the images to provide attitude and location of the platform, on which the camera is mounted, relative to the array.

Description:
FIELD OF THE INVENTION 
     The present invention pertains to navigation and particularly the air navigation by reference to land-based arrays. More particularly, the invention pertains to navigation by interpretation of images of beacons located at the corners of a ground array. 
     RELATED ART 
     Systems of the related art have included ranging relative to a fixed point, with the aid of an electro-optical sensor system and computer. Other systems disclose determination of attitude and distance between two bodies with reference to a plurality of points on the earth&#39;s surface. 
     SUMMARY OF THE INVENTION 
     The present invention is a method and apparatus utilizing an electro-optical sensor or a conventional video camera, having an addressable pixel-by-pixel output, and hardware for framing images and computing image centers of gravity. The latter hardware and respective functions define precise coordinates of the images. A microcomputer capable of processing the computations at a reasonable repetition rate is also used. Each set of microcomputer computations yields navigational information, comprising position and attitude of the sensor or camera relative to the ground array, and thus to an earth-fixed frame of reference. The sensor or camera may be typically mounted on a movable platform such as an aircraft or spacecraft. Hence, because of the defined positional and attitudinal relationship of the sensor or camera to the vehicle, etc., the resulting information serves to define the position and orientation of the vehicle relative to the array. The computer may be located on the platform or in a remote area. The ground array may consist of beacons or other emanating devices of visible light, infrared light, or other electromagnetic energy sensed by the sensor or camera. The array may also be located at sea or in space. The invention may be used day or night under various environmental conditions including foggy and cloudy conditions, under which the beacons may be emanating an appropriate electromagnetic energy, such as certain infrared wavelengths to be detected by the sensor or camera. 
    
    
     FIG. 1 illustrates an aircraft utilizing a sensing device relative to a ground array of emanating devices. 
     FIG. 2 shows the connection among the computer, sensing camera and interface. 
     FIG. 3 illustrates the relationship between the object and image planes. 
     FIG. 4 shows a horizon in the context of the object and image planes. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     FIG. 1 shows an application of the present invention with aircraft 8 embodying apparatus 10 (of FIG. 2) and navigating relative to ground array 17 of emanating devices 15. The method of the invention comprises navigation through calculations of sensed images from an array having a plurality of devices 15. 
     The specific embodiment of apparatus 10, as illustrated in FIG. 2, incorporates a Pulnix model TM 540 video camera 12, having a standard addressable pixel-by-pixel output, a Matrox model PIP 640B device 13 for data gathering, preprocessing, pixel addressing, and interfacing, and a microcomputer 6 of nominal computing power, as exemplified by that of any contemporary personal computer using, for instance, an Intel 8086 microprocessor chip, for computing, displaying, storing and comparing data in accordance with the method of the invention. This apparatus is easily assembled and programmed according to the method described below, by anyone skilled in the art. Camera 12 senses light of beacons 15 of array 17, as images focused on image plane 18 (of FIGS. 3 and 4) which is located within camera 12. The location of the beacon images on plane 18 are distinguished by specific pixels of the sensing screen which is integral with plane 18. The signals incorporating image locations of beacon 15 go from camera 12 to data gatherer and preprocessor 13 and on to computer 6, consistent with the method of the present invention. 
     The present specific embodiment of the invention involves sensing only four beacons 15, through more may be included, which are placed so as to define four corners of a parallelogram ABCD in an object plane 14 which is the earth&#39;s surface in the present description, through plane 14 may have other locations in places such as space. Beacons 15 are regarded as object point location vectors relative to video-camera 12, denoted by A, B, C and D which correspond to images (in video image plane 18) designated by location vectors a, b, c and d, respectively, as illustrated in FIGS. 3 and 4. A coordinate frame is used with an origin, O, at the &#34;pinhole point&#34; 16 of video-camera 12, and having axes aligned with the two principal directions in the video plane 18 (&#34;left-right&#34; and &#34;up-down&#34;) and with a perpendicular thereto. Object space coordinates are defined, as follows, in conformity with conventions used for aircraft axes and are depicted in FIG. 3 as solid lines emanating from point 16. Visualizing and looking through camera 12 from behind it, and positioning camera 12 in a conventional orientation, +x coordinates, and the +i unit vector, are forward; +y coordinates, and the +j unit vector, are to the right; +z coordinates, and the +k unit vector, are down. In order that image vectors be positive scalar multiples of the corresponding object vectors, the conventions for image coordinates, as depicted in FIG. 2 as dashed lines emanating from point 16, are as follows: +x and +i are backwards from O and through image plane 18; +y and +j are to the left; +z and +k are up. All points in camera image plane 18 lie at some common distance &#34;f&#34;, perpendicular to the image plane, from O, and thus all image points have the same x axis component of vector distance from the origin, namely, +f. 
     In FIG. 4, if the two lines through the image-point pairs a,b and c,d meet at the image point denoted by the vector u and the two lines through b,c and a,d meet at v, then the line through u and v constitutes the image of the line through the object points U and V, which are the meeting points of lines through the object point-pairs A,B and C,D for U, and B,C and A,D for V. However, since the object points A, B, C and D define a parallelogram, the points of intersection, U and V, are at infinity and not illustrated in the Figures of the present application. The line through U and V is the object space horizon for plane 14 containing A, B, C and D, and the line through u and v is the image of the horizon. Because U and its image u lie along a line through O, and likewise for V and v, it follows that the plane defined by the lines O-to-U and O-to-V is the same plane as that defined by the lines O-to-u and O-to-v. Also, because U and V are at infinity, the plane defined by O-to-U and O-to-V (and, in fact, any plane defined by Z-to-U and Z-to-V, where Z is any arbitrary point) is parallel to plane 14. So, u and v serve to define the orientation of the ABCD plane. Next one determines how far that plane is from O, and thence solves for A, B, C and D, and finally gets an expression for the range vector DP of some designated object plane 14 reference point P, and the orientation matrix of that object plane 14, relative to origin 16 of camera 12, and to the camera 12 coordinate axes. This determination yields the location and orientation of the camera 12 relative to the object plane 14, and thence the position and orientation of aircraft 8 in which the camera 12 is embedded. 
     The mathematical details of the method of determining the location and orientation of camera 12 relative to the plane are provided here. Having the coordinates of the images a, b, c, and d, one can solve for u and v by the ensuing method. The following vector quantities are defined: ##EQU1## Then, the fact that u lies along a,b and along c,d is expressed by the two relations: ##EQU2## where G and H are unknown scalars, to be solved for, and &#34;*&#34; means multiply. By subtraction, one gets from (2) the equation: ##EQU3## From (3), one gets, by vector-multiplying by d3 and by dl, respectively: ##EQU4## (v1×v2 denotes &#34;vector cross-product of vectors v1 and v2&#34;.) One converts (4) to two scalar equations, by scalar-multiplying by the unit x-axis vector, i: ##EQU5## v1.v2 means &#34;scalar product of v1 and v2&#34;, aka &#34;dot-product of v1 and v2&#34;. Hence, one has: ##EQU6## Since all the d&#39;s are in the y-z plane, the triple scalar products (denoted for short by a set of Q&#39;s) are fairly simple expressions: ##EQU7## where D1Y denotes y-component of d1, D1Z denotes z-component of d1, and analogously for d2, d3 and d4. So: ##EQU8## The simplest way of expressing u is to average the two formulations for u in (2): ##EQU9## In a similar fashion, one solves for the vector v, getting: ##EQU10## Having u and v, which are two vectors emanating from O to the video plane, one can describe the plane of u and v conveniently by defining the direction normal to the plane, which is represented by the vector u×v. This vector is: ##EQU11## In order to deal with singularities which would arise if two sides of the image plane quadrilateral were parallel (i.e., if u and/or v lie at or near infinity in the image plane), one multiplies the above expression for N by 4*Q31*Q42, to give the modified N formulation: 
     
         N=t1×t2-2*&lt;s&gt;×(Q42*t1-Q31*t2)                  (12) 
    
     One proceeds with the solution by exploiting the fact that all points in the object plane (including, in particular, the four object points A, B, C and D) are at some same perpendicular distance, DP, along N, from O. A, B, C and D are all scalar multiples of the image plane vectors a, b, c and d, respectively. Therefore, one has the set of equations connecting the object and image vectors: ##EQU12## where |N| is the magnitude of N. One can solve this for DP, by using the fact that one knows the magnitudes of the sides of the object quadrilateral, defined by A-B, B-C, C-D and D-A. Putting: ##EQU13## In principle, the two versions of DP should be of identical value. In practice, they will differ slightly, due to noise, etc. So, one gets a best estimate of DP by root mean squaring the two versions: ##EQU14## (&#34;SQRT&#34; signifies square root and &#34;**&#34; raises to a power) where: ##EQU15## The reference point (PREFR) of the target point quartet will have been specified as some linear blend of A, B, C and D (with unity sum of weights). For instance, one may specify the &#34;center-of gravity&#34;: 
     
         PREFR=(A+B+C+D)/4                                          (18) 
    
     This gives the target location expressed in video-camera coordinates, and in the video-camera reference frame. One needs to express PREFR in an earth-fixed reference frame, and to define the camera attitude relative thereto. To do this, one needs to compute the matrix of target array attitude, MTR, relative to the camera frame. To do so, one notes that the sides of the object array, defined by the vectors A-B, B-C, C-D and D-A, as seen in the camera frame, are matrix multiples of those same four sides, as expressed in the earth-fixed geographic frame: ##EQU16## and likewise for D2E, D3E, and D4E. 
     Since the object defines a parallelogram, D1=D3 and D2=D4; thus, in terms of usable information, (19) reduces to: ##EQU17## One can adjust (20) in a useful (i.e. non-trivial) way, by using an identity which derives from the properties of rotation matrices, that is, any given rotation of the vectorcross-product of any two given vectors produces a vector which is identical to the cross-product of the two vectors resulting from applying the said rotation to the two aforesaid vectors: 
     
         R*(U×V)=(R*U)×(R*V),                           (21) 
    
     where R is any rotation matrix, and U and V are any two vectors. Therefore, one can extend (20) to the triplet: ##EQU18## Now, (22) defines a matrix equation: 
     
         MD=MTR&#39;*MDE,                                               (23) 
    
     where MD denotes the 3-by-3 matrix whose three columns comprise the three vectors D1, D2 and D1×D2 respectively, and where MDE denotes the 3-by-3 matrix whose three columns comprise the three vectors D1E, D2E and D1E×D2E respectively. With this, one can solve for MTR: 
     
         MTR=MDE*(1/MD),                                            (24) 
    
     where 1/MD denotes the inverse of the matrix MD. 
     If there is no noise or errors, MTR as thus computed will, in fact, be a rotation matrix, as it is supposed to be. That is, the magnitudes of each of its three column vectors, and of each of its three row vectors, will be 1.0. Furthermore, the dot products of any two distinct column vectors, or of any two distinct row vectors will be zero. But, there will be noise, etc., and MTR won&#39;t be a perfect rotation matrix. So, one least-squares best-fits (BF) a rotation matrix to MTR. This is done by using an alternative definition of a rotation matrix as one whose transpose is equal to its inverse. This leads to the best-fit: ##EQU19## As one can easily confirm, (25) yields an MTRBF which is a perfect rotation matrix. Since, in fact, MTR*MTR&#39; will be fairly close to the identity matrix, I, one expresses it as equal to I+e, (where, of course, e=MTR*MTR&#39;-I), and then uses a Taylors series expansion: ##EQU20## This expansion also results in the selection of the correct one of two square roots, namely, that corresponds to MTR (approx)=+I, rather than -I. 
     For the present purposes, the first order expression suffices: ##EQU21## Therefore, (25) becomes: 
     
         MTRBF=(3*MTR-MTR&#39;*MTR)/2 (26) 
    
     Now one can obtain the camera attitude, MCAM, relative to the earth-fixed frame. This is simply the inverse, i.e., the transpose, of MTRBF: ##EQU22## Additionally, to get the vector distance (CRANGE) of the camera point O from the chosen object reference point, expressed in earth-fixed coordinates, one simply multiplies PREFR first by -1 (to convert camera-to-object range to object-to-camera range), and then by the camera attitude matrix: 
     CRANGE=-MCAM*PREFR