Multiple coordinated detectors for examination and ranging

Abstract

This invention focuses specifically on the use of epipolar lines and the use of matrix transformations to coordinate cameras. This invention organizes cameras in a manner which is intuitive and effective in perceiving perspectives which are not normally possible; to calculate range precisely; to allow redundancy; to corroborate feature recognition; and to allow perspectives from angles from which no cameras exist. By enabling remote scene reconstruction with a limited set of images, transmission bandwidth is greatly conserved.

Claims

1. A computer-implemented method of using a plurality of imaging devices, positioned in a spaced apart relationship with each other, to create a new image of an object from a new viewpoint where an imaging device is not positioned, said method comprising: capturing images of said object with each of said plurality of imaging devices; projecting epipoles from an image plane of said each of said plurality of imaging devices to infinity; positioning all image planes coplanar with each other; selecting a center position of a new viewpoint; linking, with baselines, said center position of said new viewpoint with centers of plurality of imaging devices; running epipolar lines, parallel to a respective baseline, from key features of a captured image by said plurality of imaging devices; intersecting epipolar lines from each respective key feature in said each of said plurality of imaging devices to define corresponding key features in said new viewpoint; and aligning, using matrix transformations, captured images from said plurality of imaging devices at corresponding respective key features in said new viewpoint to create said new image.

2. The method of claim 1, wherein said each of said plurality of imaging devices comprises a camera with a lens.

3. The method of claim 1, wherein said plurality of imaging devices comprises two imaging devices.

4. The method of claim 1, further comprising tracking said object with said captured images and said new image, said object being a moving object.

5. The method of claim 1, wherein said object comprises a plurality of objects and said method further comprises tracking said plurality of objects with said captured images and said new image, each of said plurality of objects being a moving object.

6. The method of claim 1, further comprising identifying said object with said captured images and said new image.

7. The method of claim 1, further comprising replacing an image from any failed imaging device from said plurality of imaging devices with said new image from said new viewpoint.

8. The method of claim 1, further comprising calculating distances to said object from any one of said plurality of imaging devices and said new viewpoint.

9. The method of claim 8, further comprising assigning one or more of said baselines based on said distance(s) to said object.

10. The method of claim 8, further comprising scaling a size of said new image in said new viewpoint.

11. The method of claim 8, further comprising stretching and compressing said new image based on a ratio between a distance to said object from said new viewpoint and a distance to said object from any one of said plurality of imaging devices.

12. The method of claim 8, further comprising normalizing said new image by inverting a ratio between a distance to said object from said new viewpoint and a distance to said object from any one of said plurality of imaging devices.

13. The method of claim 1, wherein said positioning of said all image planes coplanar with each comprises progressively aligning said each of said plurality of imaging devices by way of primary, secondary and fine alignments.

14. The method of claim 1, further comprising projecting a curved image field in front of a lens of said each of said plurality of imaging devices, if a single epipole is not convergent or parallel to other epipoles.

15. The method of claim 1, further comprising converting polar coordinates into orthogonal coordinates.

16. The method of claim 1, further comprising creating additional new images of said object from additional new viewpoints and generating a 3D image of said object.

17. A computer-implemented method for identifying a moving object with a plurality of imaging devices positioned in a spaced apart relationship with each other, said method comprising: capturing an image of said moving object with each of said plurality of imaging devices; projecting epipoles from an image plane of said each of said plurality imaging devices to infinity; positioning all image planes coplanar with each other; selecting a center position of at least one new viewpoint; linking, with baselines, said center position of said at least one new viewpoint with centers of plurality of imaging devices; running epipolar lines, parallel to a respective baseline, from key features of a captured image by said each of said plurality of imaging devices; intersecting epipolar lines from each respective key feature in said each of said plurality of imaging devices to define corresponding key features in said at least one new viewpoint; aligning, using matrix transformations, captured images from said plurality of imaging devices at corresponding respective key features in said at least one new viewpoint to create at least one new image of said object; and comparing a combination image comprising said at least one new image and said captured image with a template image.

18. The method of claim 17, further comprising tracking said moving object and deciding to accept said object as harmless or destroy said object with a weapon.

19. A system for at least identifying an object, comprising: a plurality of imaging devices positioned in a spaced apart relationship with each other in a polygon pattern, each capturing an image of said object; and a computer configured to: project epipoles from an image plane of said each of said plurality imaging devices to infinity; position all image planes coplanar with each other; select a center position of at least one new viewpoint; link, with baselines, said center position of said at least one new viewpoint with centers of plurality of imaging devices; run epipolar lines, parallel to a respective baseline, from key features of a captured image by said each of said plurality of imaging devices; intersect epipolar lines from each respective key feature in said each of said plurality of imaging devices to define corresponding key features in said at least one new viewpoint; align, using matrix transformations, captured images from said plurality of imaging devices at corresponding respective key features in said at least one new viewpoint to create at least one new image of said object; and compare a combination image comprising said at least one new image and said captured images with a template image.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a basic geometrical layout of two detectors for seeing or sensing an object 200, with the parameters of width and length of the object and the corresponding images shown for computation. The detectors, or cameras, are described as an image plane 10 with lens 1, and an adjacent and coplanar image plane 120 with lens 12. The notation is typical for triangulation.

(2) FIG. 2 shows a graphs 901 and 902 the results of using the parameters described in FIG. 1 for computations of length and width in the object 200.

(3) FIG. 3 shows a projection of the object 200 into 3D space, with the image planes 10 and 120 convergent towards object 200, showing images of the object on both planes, and with a baseline 304 connecting the camera centers 1 and 12. (Noted here is the theoretical convention in projection that the lenses 1 and 12 become now the camera centers 1 and 12 with the image planes 10 and 120 inverted towards the object 200, simplifying exegesis.) Where the baseline 304 intersects the image planes 10 and 120 are the epipoles e and e, important in what follows.

(4) FIG. 4 shows that by projecting the epipoles e and e to infinity we make the image planes 10 and 120 coplanar, and the lines 301, 302 and 303 joining similar salient features in the two images, such as image corners 15 and 121, are made parallel to the baselines.

(5) In FIG. 5 this concept is extended to multiple camera centers 1 . . . 12 (described later as nodes) which for the sake of illustration (and simplicity) we here create as a symmetrical dodecagon 1000. It will be shown later that it can be any shape at all, both planar and non-planar, and that we can derive special relationships from the parallelism of lines on the epipolar pencils.

(6) In FIG. 6 is shown how missing cameras affect imaging. We have eliminated cameras at alternating nodes (such as 1, 3 and 5) leaving a hexagon of even numbered nodes (such as 2, 4, 6). Note here that an image 20 constructed with a reduced camera set (6) for node 2 is exactly the same as it is for a full camera set (12). This is to indicate how working with a skeleton can be effective. Later we will show that skeletons can be of any shape.

(7) FIG. 7 shows how an imaginary camera 13, located randomly, can be made to perform as a real camera within a skeleton (a polygon) formed by other camera centers.

(8) FIG. 8 shows the parameters of a polar coordinate system. This is to show how polar geometry can relate to outlying cameras which fall off our usual definition of coplanar.

(9) In FIG. 9 illustrates how a point X can project onto two different coordinate systems, but whose images can still be related through various coordinate transformations

(10) In FIG. 10 shows a visual range horopter 501 of all the coordinated detectors 500 in a detector bundle, as will be described below.

(11) FIG. 11 shows a possible way of processing the data gathered by cameras 1, 2, 3 . . . n. For redundancy (in case any lose function) a parallel configuration of cameras is preferred. When an object (such as an aircraft) is recognized by the computer, a select few cameras as in 1, 2, 3 . . . etc. can be chosen to track it, depending on the object's range.

(12) In the discussion which follows the imaging devices will be referred to as cameras, detectors, or nodes, as apt in context. Detectors is a more general term, referring to any device capable of perceiving images within the electromagnetic spectrum or sonar range.

DETAILED DESCRIPTION OF THE DRAWINGS

(13) This invention, with its further advantages described below, may be best understood by relating the descriptions below to the drawings appended, wherein like reference numerals identify like elements, and where:

(14) FIG. 1 illustrates how the geometrical parameters of an object, including depth, can be measured using two imaging devices. A first imaging device 401 is defined by a lens 1 and an image plane 10. A second imaging device 412 is defined by a lens 12 and an image plane 120. In the configuration shown the image planes 10 and 120 are coplanar in the x-y plane and lie centered on the x-axis.

(15) In FIG. 1 the imaging devices 401 and 412 are looking at an object, or feature, 200 in 3D space from two different perspectives. In our illustration the feature 200 is shown as a flat object such as a kite (for flying) or a sail (on a boat). The corners 201, 202 and 203 of feature 200 are imaged onto image plane 10 through lens 1 as points 15, 16 and 17. The corners 201, 202 and 203 of feature 200 are imaged onto image plane 120 through lens 12 as points 121, 122 and 123.

(16) In FIG. 1, given f as the focal length of the imaging devices, or cameras, and +h and h as the distances of the lenses from the z-axis, we can compute the pixel offsets q.sub.1 and q.sub.2 corresponding to the distances d.sub.1 and d.sub.2 to the feature corners 201 and 202, which in this scenario happen to lie along the z-axis. Geometrically
q.sub.1d.sub.1=q.sub.2d.sub.2=hf
or simply hf=qd
where, with the cameras secured and h and f both constant, the variables q and d describe a hyperbolic curve 901 as shown in FIG. 2.

(17) As an example from this curve 901 suppose that f is 35 mm, h is one meter, the detector pixels are 2, and there is an image offset q on the image plane of 50 pixels. Then
d=3510.sup.31/50210.sup.6=350 meters
Here d could exemplify the distance from the lenses 1 and 12 along the z-axis to feature corner 202. Correspondingly if on the image the value of q were increased by 8 more pixels then d would become 300 meters, making image 200 larger and bringing feature corner 201 50 meters closer to the detectors.

(18) FIG. 1 also shows offsets from the x-z plane of point p (14) in the +y direction corresponding to a offset l in the y direction of the feature corner 203. At a specific distance d along the z-axis this creates a linear relationship 902 as shown in FIG. 2
p=fl/d

(19) As a calculation from this line 902 in FIG. 1 suppose that f is 35 mm, d is a thousand meters, the detector pixels are 2, and there is a feature offset of 50 pixels. Then
l=50210.sup.61000/3510.sup.3=30 meters
This shows that the calculation of offsets from the z-axis is linear. It is a lot more sensitive than the calculation of distance along the z-axis, especially as distances increase.

(20) A series of lenses in the following discussion (such as 1, 2, 3, . . . 12, etc.) will be referred to as camera centers. It is useful (and conventional) to put the image plane in front of the lenses since, instead of being inverted, the images can be seen to more closely correspond to the objects being studied. For reasons which follow the camera centers will also be abbreviated in the discussion as nodes.

(21) In FIG. 3 is shown a projection of the image planes 10 and 120 into 3D space where the lenses 1 and 12 become the camera centers and the points 210, 202 lie on a plane 415. In this figure the image planes 10 and 120 are shown tipped inwards, or convergent, towards the points 201, 202 and 203.

(22) In FIG. 4 we project the epipoles e and e to infinity, thereby making the image planes 10 and 120 in this imaging system coplanar. This projection has the property of making all lines joining similar features parallel to the baseline 304, which is the line joining their two cameras centers 1 and 12. For example the corner 201 of object 200 will project onto detectors 10 and 120 as points 15 and 121 (denoted as x and x) on a line 301. The diagram shows this line parallel to the baseline 304.

(23) In FIG. 5 we extend this concept to multiple camera centers (or nodes) 1, 2, 3 . . . 10, 11, 12, etc. For the sake of illustration (and simplicity) we may make this shape a symmetrical dodecagon. It will be shown later that it can be any shape at all, and can be extended to non-coplanar detectors.

(24) In FIG. 6 we show how missing cameras affect imaging. We have eliminated cameras at alternate nodes 1, 3, 5, 7, 9 and 11six in all, leaving a hexagon of 2, 4, 6, 8, 10, 12 nodes as the remainder. By connecting new baselines such as 324 between nodes 12 and 2, all similar features 21 and 121, 22 and 122, etc. are connected by parallel lines 321 and 322, etc. since the epipoles of image planes 20 and 120 (and others) are all at infinity.

(25) This has the property that no matter how the baselines are connected between any pair of nodes, the images created on those image planes by any set of lines parallel to the baselines are identical. In other words, the image formed by the corners 121, 122, 123 on image plane 120 permutes identically to itself no matter how that image plane is connected to other coordinated image planes on the field.

(26) A missing or unusable imaging device make no difference for imaging in remaining real (or imaginary) imaging devices since using epipolar lines these can be linked seamlessly to alternate imaging devices in the field.

(27) This property has huge ramifications in terms of redundancy. The number of apexes which can be connected in pairs in any field of n coordinated detectors is n (n1)/2. This means that 12 detectors (as in FIG. 5) can be connected together 66 different ways. Losing half these detectors by mishap or sabotage (as in FIG. 6), thereby reducing the number to 6, still allows 15 different combinations, which is statistically significant, and in fact adequate, for many purposes.

(28) In FIG. 7 is shown the ability to place artificial cameras 13 and 14 in places where none existed before, and have them function like normal cameras. We will cover this later.

(29) Anticipating FIG. 10, we show a field of coordinated detectors 500. This field may contain many detectorsperhaps a thousand or more for missile tracking, aircraft navigation, drones, etc. The possible number of different pair combinations for 1,000 detectors is n (n1)/2 which equals 499,500nearly half a million. This implies that any select fewperhaps a dozen detectors, may be chosen for progressive tracking at one time. The tracking of multiple targets can overlap and proceed simultaneously. With massively parallel architecture and instantaneous fault detection should any detector fail (or get blown up in wartime) the system has multiple redundant detectors and resilience to spare. It can be programmed to continue seamlessly.

(30) Issues remain: (i) The epipoles are prescribed as being at infinity, but how must the cameras (or detectors) be coordinated? (iii) how does one go beyond infinity with the epipoles if the cameras are neither convergent nor coplanar?

(31) We first address issue (i): How do we coordinate cameras? and why ? (i) We coordinate cameras to reduce computation. Part of this can be achievedthough shown later as not strictly necessaryby acquiring a single model camera from a given manufacturer. (ii) When the cameras are coplanar and coordinated failure of any particular camera is not an issue; the computer can sense failure in microseconds; massive redundancy permits object detection to be switched to other selected cameras.

(32) To get cameras coplanar with their epipoles projected at infinity we need (progressively) primary, secondary and fine alignment.

(33) For camera pairs we can enumerate certain physical degrees of freedomfocal length, aperture, zoom, x, y and z, and pitch, roll and yaw. All degrees of freedom must then be adjusted together so that cameras as pairs and en masse match each other as closely as possible. As examples, the pose of the cameras, i.e. their axes, should be parallel; apertures also should be adjusted to give matching light intensity on the detectors, etc.

(34) Primary. Assuming cameras are facing skywards and connected in parallel (as they should be), they may be trained on a distant object (a star overhead), and aligned one by one so that their images coincide (as precisely as possible by eye) on a computer screen nearby. This will make them parallel but will not fix image size and rotation, which follows.

(35) Secondary. A simple recipe for bringing the images from each pair of cameras into close parallel, rotation and size correspondence can be performed in Matlab. It depends on accurately choosing (at least two) matching features in distant images. This could be pinpoints such as two well-separated and well-known stars. The median (estimated) pixel positions must be delivered to the program below into the two functions ginput2( ) by the user.

(36) The matching algorithms below we use the local coordinates of the detectors (rather than the global coordinates discussed later for image mapping). That is, that when our alignments are carried out to a sufficient degree point (x.sub.i, y.sub.i), of image plane 10 will correspond (almost) exactly to point (x.sub.i, y.sub.i) of image plane 120. alignment.m % load input images l1=double(imread(left.jpg)); [h1 w1 d1]=size(l1); l2=double(imread(right.jpg)); [h2 w2 d2]=size(l2); % show input images and prompt for correspondences figure; subplot(1,2,1); image(l1/255); axis image; hold on; title(first input image); [X1 Y1]=ginput2(2); % get two points from the user subplot(1,2,2); image(l2/255); axis image; hold on; title(second input image); [X2 Y2]=ginput2(2); % get two points from the user % estimate parameter vector (t) Z=[X2 Y2; Y2 X2; 1 1 0 0; 0 0 1 1]; xp=[X1; Y1]; t=Z\xp; % solve the linear system a=t(1); %=s cos(alpha) b=t(2); %=s sin(alpha) tx=t(3); ty=t(4); % construct transformation matrix (T) T=[a b tx; b a ty; 0 0 1]; % warp incoming corners to determine the size of the output image (in to out) cp=T*[1 1 w2 w2; 1 h2 1 h2; 1 1 1 1]; Xpr=min([cp(1,:)0]):max([cp(1,:)w1]); % min x:max x Ypr=min([cp(2,:)0]):max([cp(2,:)h1]); % min y:max y [Xp,Yp]=ndgrid(Xpr,Ypr); [wp hp]=size(Xp); %=size(Yp) % do backwards transform (from out to in) X=T\[Xp(:) Yp(:) ones(wp*hp,1)]; % warp % re-sample pixel values with bilinear interpolation clear Ip; xl=reshape(X(1,:),wp,hp); yl=reshape(X(2,:),wp,hp); lp(:,:,1)=interp2(l2(:,:,1), xl, yl, *bilinear); % red lp(:,:,2)=interp2(l2(:,:,2), xl, yl, *bilinear); % green lp(:,:,3)=interp2(l2(:,:,3), xl, yl, *bilinear); % blue % offset and copy original image into the warped image offset=round([min([cp(1,:)0])min([cp(2,:)0])]); lp(1+offset(2):h1+offset(2),1+offset(1):w1+offset(1),:)=double(l1(1:h1,1:w1,:)); % show the results figure; image(lp/255); axis image; title(aligned images);

(37) We can write a more general program in Matlab to bring multiple images within a few pixels of alignment, and consequently make multiple image planes parallel simultaneously.

(38) Fine alignment. To get accurate alignment in a terrestrial environment we must delve into a feature-based approach. In general, for feature selection, any of a number of edge detection algorithms can be used, such as: J. Canny, A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-8, No. 6, 1986, pp. 679-698). We can apply this to features we have already chosen, using the local coordinates of image planes 10 and 120.

(39) Using a notation common in imaging (See Richard Szeliski, December 2006), we may utilize the minimum of the sum of squares function ESSD(u) for our step-wise correlation of similar features on image planes 10, 20, 30 . . . 120, etc.:
ESSD(u)=.sub.i[I.sub.1(x.sub.i+u)I.sub.0(x.sub.i)].sup.2=.sub.i(ei).sup.2
Where u=(u, v) is the feature displacement on orthogonal axes (using local coordinates) and ei=I.sub.1(x.sub.i+u)I.sub.0(x.sub.i) is the error function or feature displacement offset within the feature areas (I.sub.0 being the reference feature on image plane 10 and I.sub.1 a similar feature on image plane 20, etc.)

(40) That is, we reduce all the errors ei to an acceptable minimum, realizing that because the images are taken from different perspectives, the errors ei will never be completely zero.

(41) The sum of squared differences function ESSD(u) above can also be written as a Fourier transform:
F{ESSD(u)}=F{.sub.i[I.sub.1(xi+u)I.sub.0(xi)].sup.2}=.sub.(f).sub.i[I.sub.1.sup.2(xi)+I.sub.0.sup.2(xi)]2I.sub.0(f)I.sub.1*(f)
The right-hand expression shows how ESSD(u) can be computed by subtracting twice the correlation function (the last term) from the sum of the energies of the two images (the first term). We can use the discrete cosine transform, DCT-2, if we want to correlate larger pixel areas.

(42) For really fine correlation we can use a partial differential equation to compare the image gradients at the light-to-dark edges of our chosen features on image planes 10 and 120. We can treat the least squares function ESSD(u) above as an energy function with a hypothetical displacement u
ESSD(u+u)=.sub.i[I.sub.1(x.sub.i+u+u)I.sub.0(x.sub.i)].sup.2=.sub.i[J.sub.1(x.sub.i+u)u+(ei)].sup.2
where the Jacobian J.sub.1(x.sub.i+u)=I.sub.1(x.sub.i+u)=(I.sub.1/x,I.sub.1/y)(x.sub.i+u)
is the image gradient at (x.sub.i+u) and ei=I.sub.1(x.sub.i+u)I.sub.0(x.sub.i) is the intensity error (as above).

(43) This is a soluble least squares problem in which sub-pixel resolution can be achieved when the Jacobians of the profiles of the two features 141 and 142 are approximately equal
J.sub.1(x.sub.i+u)J.sub.0(x)
since near the correct alignment the appearance of light-to-dark edges should be the same.

(44) This alignment of x and y coordinates will bring the two image planes 10 and 120 onto almost identical points (x.sub.i, y.sub.i) on their local x-y planes, differing only by their global offsets +h and h from the z-axis, as in FIG. 1. This alignment will apply sequentially to all image planes 10, 20, 30 . . . up to 120 and beyond.

(45) With the cameras aligned and secured in their locations we can estimate with fair precision variations in the geometry, recognition and motion of distant objects.

(46) Of interest to us is that the distance h from baseline to detectors could be quite largesay a hundred metersmaking the range accurate at 35,000 meters. In addition the separation of pixels could be accurately gauged at 1 (or less), making the accuracy for 100 meter detector separation 50 times greater again, at 1.7 million meters. More then will depend on camera resolution.

(47) A reflection is prompted about the resolution by an observation satellite of asteroid trajectories near earth, especially if there is an effort to divert an asteroid on collision course. Free from gravity and atmospheric turbulence, cameras could be deployed far from the satellite. From the calculations above, the range of such cameras 1 km apart would be 170,000 kilometers, giving ten hours warning for an asteroid approaching at 17, 000 km per hour.

(48) A sum of such images and measurements taken with many cameras will provide a many faceted picture of an object, as may be seen in the shaded areas of FIG. 5. With increasing facets the ability for software to recognize the unique character of an object will steadily improve. Bayesian probabilities will adduce certainty to recognition.

(49) We have not mentioned the additional parameters of color, hue, saturation, light, dark etc., in objects as a means of recognition. This will come later.

(50) FIG. 5 shows an array of coplanar detectors 1 to 12 arranged symmetrically around an object 200 lying along a central z-axis between detectors 1 to 12. For ease of visualization we make the z-axis look into the paper. The object 200 in FIG. 5 is the same object 200 as in FIG. 1, where the central corners 201 and 202 lie on the z-axis, and the corner 203 lies to one side on the y-axis.

(51) In FIG. 5 the construction lines 211 and 212 connect camera center 1 with the corners 201, 202 and 203. The line 211 is shown as single as points 201 and 202 lie coincident on the z-axis.

(52) Referring back to FIG. 1, we can transfer the same parameters of length d and pixel offsets q, etc. to the more general FIG. 5. On image plane 10 the pixel distance q.sub.1 from camera center 1 is plotted as point 15. Similarly the pixel distance q.sub.2 is plotted as point 16, and the pixel distance q.sub.3 and offset p on the y-axis is plotted as point 17. We proceed in a similar manner for all detectors 1 to 12.

(53) Because we have arranged it so that epipoles of all these detectors are at infinity, the corners of all these plots form in aggregate nested dodecagons 1000 (baselines), 1001 (points similar to 15), 1002 (points similar to 16) and 1003 (points similar to 17). These lines together form nested sets with parallel sides as shown in FIG. 5.

(54) We can observe from FIG. 1 that the object point 202 furthest away from camera center 1 creates the smallest pixel shift q.sub.2 on image plane 10, at point 16. Therefore the aggregate of images of point 202 on all image planes 10, 20, . . . up to 120, at points 16, 22 . . . up to 122, form the smallest dodecagon 1002 in FIG. 5.

(55) Similarly from FIG. 1 the object point 201 nearest from camera center 1 creates the largest pixel shift q.sub.1 on image plane 10, at point 15. Therefore the aggregate of images of point 201 on all image planes 10, 20 . . . up to 120, at points 16, 22 . . . up to 122, form the larger dodecagon 1001 in FIG. 5.

(56) Again in FIG. 1, the object point 203 intermediate from camera center 1 creates an intermediate pixel shift q.sub.3, and an additional pixel offset p in the y-direction, on image plane 10, at point 17. Therefore the aggregate of images of point 203 on all image planes 10, 20 . . . up to 120, at points 17, 23 . . . up to 123, form an intermediate dodecagon, offset by an amount corresponding to this pixel offset p, as dodecagon 1003 in FIG. 5.

(57) We note that the size of these dodecagons obey the hyperbolic curve 901 in FIG. 2. While an object feature 202 (the nose of a missile) is far away from detectors 1 . . . 12 a dodecagon will appear small (as dodecagon 1002). While object feature 201 (the nose the same missile) is closer to detectors 1 . . . 12 a dodecagon will appear larger (as dodecagon 1001).

(58) We also note the effect of an object feature 203 (the nose of our approaching missile) going off course on the y-axis. This is shown as dodecagon 1003, which is now eccentric. The size of this dodecagon will still obey the hyperbolic curve 901 in FIG. 2. But in eccentricity the dodecagon will obey the linear curve 902 in FIG. 2. The missile (as we have named object 200), will in fact track as a dodecagon in a manner combining curves 901 and 902 from FIG. 2.

(59) Because curve 901 in FIG. 2 is hyperbolic, should a missile actually hit the detectors the size of the tracking dodecagon would become infinite.

(60) The usefulness of this constructionof which we have given just one examplemay now be made apparent.

(61) The first is visualization. Through multiple views and with n(n1)/2 comparisons, Bayesian probabilities can rapidly help confirm an identity. This is important, since images can become indistinct, go behind clouds, etc.

(62) Another is velocity. Suppose point 202 represents the nose of our missile coming directly up the z-axis centerline towards the cameras. At moment t.sub.1 it could be at 202. At moment t.sub.2 it could be at 201. As prior calculations show the separation (as resolved by the detectors) could be 50 meters. Given an approach velocity of 600 km/hr. the time difference t.sub.2t.sub.1 would be 3 seconds. At 350 meters away in the calculations above, this would give a reaction time of just 21 seconds.

(63) To gain time we may propose a change in length of the baseline h between cameras. If h is changed from one meter to ten, the reaction time will become 210 secondsthree and a half minutes. If h is changed from one meter to one hundred, the reaction time will become 2,100 secondsthirty-five minutes. Multiple coordinated high resolution cameras with broader baselines will allow greater warning time for reaction.

(64) The addition of many viewpoints beyond 2D not only replicates the vision of the human eye to perceive depth from diverse points of view, but adds valuable information for the inspection of diverse objects. These objects can be instantaneously compared and sorted against three-dimensional templates which may reflect the ideal for that particular object. With advanced object recognition software, inspection and ranging can be done at high speed and with great accuracy.

(65) We now address issue (ii): An epipole of a camera imaging on a flat plane must make its z-axis either parallel to, or convergent with, all others, else its epipole will either be imaginary or beyond infinity.

(66) A solution to this dilemma is to project a curved image field in front of the lens to simulate a fish-eye lens or a human eyeball. The epipole will then fall on a spherical surface, real or imagined, surrounding the camera center.

(67) This solution is shown in FIG. 9, where a line 406 joining camera centers 401 and 402 has epipoles e passing through a flat plane 410 and e passing through a sphere 412. The pose of this camera with center 402 is on the z-axis. The spherical configuration here makes the pose immaterial, since within a sphere there is always one radius which will fall parallel to the z-axes of all other detectors. The sphere can be partial or otherwise, so long as the shape in general is curved. Having z-axes parallel for all cameras is not only necessary but desirable for simplifying calculations.

(68) In FIG. 9 we can choose a z-axis (north, polar) 407 as corresponding to the pose of all other cameras. Using FIG. 8, we convert spherical (polar) coordinates of point 404 (, , ) into (x, y, z) coordinates. This makes images consistent with those from all other cameras. Our new coordinates are: (x, y, z)=(sin cos , sin sin , cos )
where (rho) is the radius of sphere 412. may also be used as a scaling factor.

(69) In FIG. 9 any image on a sphere will have barrel distortion and this must be corrected from image 404 so that it will correspond point by point to flat image 403. The following factors will make correspondence easier by virtually eliminating this distortion, producing new coordinates x.sup.a and y.sup.a:
x.sup.a=x(1+k.sub.1r.sup.2+k.sub.2r.sup.4)
y.sup.a=y(1+k.sub.1r.sup.2+k.sub.2r.sup.4)
where k.sub.1 and k.sub.2 are radial distortion parameters and r.sup.2=x.sup.2+y.sup.2. r is a variable radius diminishing according to its distance up the z-axis as in FIG. 8. Higher order parameters (e.g. k.sub.3 r.sup.6) may be necessary for even more matching towards the poles.

(70) For both Cartesian and Polar coordinate systems we need a way to relate images between planes 10, 20, 30, . . . n, between spheres such as 412, and between the two imaging systems. We need to compare a matrix M describing an array of pixels x.sub.1 . . . x.sub.n, y.sub.1 . . . y.sub.n to a matrix M describing a similar array of pixels x.sub.1 . . . x.sub.n, y.sub.1 . . . y.sub.n. In other words we need a transformation matrix T where M=M.T

(71) Using homogeneous coordinates relating images on flat surfaces this appears as:

(72) $\left(\begin{array}{c}{x}^{}\\ y^{}\\ 1\end{array}\right)=\left(\begin{array}{ccccc}x& y& 1& 0& 0\\ y& -x& 0& 1& 0\\ 0& 0& 0& 0& 1\end{array}\right).Math.\left(\begin{array}{c}s\cos \\ s\sin \\ t_x\\ t_y\\ 1\end{array}\right)$
where s is a scaling factor to exactly match image sizes, t.sub.x and t.sub.y the pixel displacement for precisely corresponding images on their local image planes, and x and y are the local pixel arrays for the newly coordinated images. is the angle of rotation, programmed in radians, normally zero if detectors are properly coordinated.

(73) A similar expression will occur above when the x and y pixel arrays above are replaced with their corresponding polar (spherical) coordinates as in FIG. 8 and are properly scaled.

(74) Possibilities arise for a field of cameras where all cameras are spherical, all have their z-axes parallel, and all are scaled through their radii p to match each other. In this case all images would be similar and would be coordinated closely as spherical images.

(75) We note that cameras which are not strictly coplanar, or fall out of line with others, can be re-aligned with others through projective transformations, as may be occasionally needed.

(76) An essential point in the present invention is that a planar structure, as in FIG. 5, appears as a practical means for coordinating and making operative a multitude of detectors. The transformations for new points of view require no rotation or projection, only affine transformations, which make for a simple and robust way to achieve high-speed performance for recognition and tracking.

(77) An important ramification of this invention is that with a supporting structure as in FIG. 6 images can be constructed where none existed before. Cameras can be posited usefully in imaginary places and pictures can be created as though the cameras are actually there. This is shown in the dotted lines of FIG. 7 where an image is created based on parallel epipolar lines from adjacent images. In fact whole scenes can be constructed given a handful of nearby camera images.

(78) In FIG. 7 we posit an imaginary camera with center 13 as shown. From center 13 we run lines to adjacent camera centersline 334 to center 8, line 344 to center 10, and line 354 to center 12. Precisely parallel to these lines we run lines 351, 352 and 353 from the corners of image 120; we run lines 341, 342 and 343 from the corners of image 100; and we run lines 331, 332 and 333 from the corners of image 80. These lines intersect precisely on lines 211 and 212 to form the corners 131, 132 and 133 of a new image 130. This is now a perspective view of object 200 from a camera with center 13.

(79) To create a 3D view of object 200 from the same distance we can posit another imaginary camera with adjacent center 14, subtend an angle suitable for 3D at object 200, and iterate a series of lines as above. This will give us an image (not shown) precisely cognate with image 130 for a full 3D perspective view of object 200.

(80) An explanation is at hand. It lies (i) in our ability to line cameras up precisely, as described above (the practical difference between precise and not precise to image quality is like daylight to night) and (ii) on the transformation M=TM where T is an affine transformation on the x-y plane. The image 130 will be stretched along the line 211 by the ratio R/R of the distances from the object 200 to the camera centers 13 and 12. The image 130 will be compressed against line 212 by tan , where is the angle subtended by the object 200 between lines 211 and 212. The stretching and compression is automatic from the geometry. There is no rotation since all the cameras will have been rotated precisely prior to adding nodes 13 and 14.

(81) To explain further: In FIG. 5, FIG. 6 and FIG. 7, R represents how far a typical image plane 80 (containing the aggregate pixels M) is from a common center line, a z-axis, of a group of image planes 10 . . . 120. R represents how far the image plane 130 (containing the aggregate pixels M) may be from this z-axis. By changing the ratio R/R we can make the image 130 zoom larger or smaller, creating far and near perspectives at will.

(82) This can be done by a computer with an imaginary camera 130 with no physical change to other cameras. Better yet, a pair of cameras 130 and 140 can create real 3D perspectives with real images borrowed from real cameras with transformations like M=TM above.

(83) The images 130 and 140, as in all images, can be normalized with others by inverting the ratio R/R, to bring all images into conformity of scale.

(84) The ability of creating 3D as with nodes 13 and 14 opens up many possibilities. For example, a whole family of 3D perspectives with imaginary cameras can be created around a few actual key viewpoints. Also, a pair of nodes such as 13 and 14 can be moved around in virtually real time to obtain almost any perspective. Again, the separation of nodes 13 and 14 can be enlarged and reduced; enlarging increases the discrimination of objects in 3D.

(85) Transmission speeds (as in the MPEG-4, -5 and -6 series for video) will be increased by orders of magnitude through our ability to construct whole scenes from a few camera images. In this scenario cameras are only windows: the real visual processing will be done by powerful computers at the receiving end. Pan, tilt, zoomseeing scenes from different perspectiveswill be done remotely in virtually real-time by the recipient.

(86) Finally, using a stabilizing program (described elsewhere by this inventor and others, and using Newton's laws of motion) the persistence of a scene can be continued as though actually happening for some time (i.e. seconds, or perhaps half a minute) after all cameras are blown up. Even a destroyed scene itself could be constructed to continue hypothetically for a similar period.

(87) To a large degree certain transformations have already fixed the parameters of shape at hypothetical camera locations. What needs discussing are the additional parameters of color, hue, saturation, light, dark, etc. In hypothetical locations these can be inferredfor example, green should continue as green in saturation and hue, though it may be darkened by shadow.

(88) The parameters above may be inferred as a weighted average from the corresponding local images. From two adjacent images having corresponding pixels with different shades of green, a new color image could be created by summing and averaging, creating a shade in the middle. Largely, this may be adequate.

(89) For a projection system requiring multiple viewpoints, as exist for immersive 3D viewing, the conversion of a handful of coordinated cameras views, such as twelve, into multiple authentic viewpoints, such as two hundred, could be most valuable. This would be useful for both large and small glasses-free 3D screens.

(90) An opportunity exists to create real reality, as opposed to augmented reality, for popular items such as Oculus Rift and Google Cardboard. This can be done in very nearly real-time with simple transformations using the power of a modern cell-phone snapped into a slot behind the viewer. Football games could be watched on these devices in 3D in real-time in detail.

(91) In many scenarios time is limited, so the need for recognition with high probability is critical. Multiple offset cameras with many viewpoints, as in this invention, can increase probability; the computer can continuously cross-correlate information from several cameras, to verify details; the use of image stabilization, continuity and priors corroborates probabilities and aids identification.

(92) The possibilities described above could be of great value to forensic work.

(93) To summarize: What we have shown is a method using epipolar lines and matrix transformations to create viewpoints for which no imaging devices exist with these following steps: (i) precisely aligning multiple imaging devices; (ii) making imaging devices coplanar by projecting imaging device epipoles to infinity; (iii) positing coplanar imaginary imaging devices as and where needed; (iv) linking camera centers of imaginary imaging devices to camera centers of existing imaging devices with baselines; (v) running epipolar lines precisely parallel to baselines from key features of existing imaging devices to precisely intersect at hypothetical key features of imaginary imaging devices; (vi) using matrix transformations to bring real images from imaging devices to precisely align at hypothetical key features of imaginary imaging devices.

(94) What we have shown in this invention is that an efficient and exactand therefore fastway of creating wholly new real images from adjacent real images, which allows us to solve real-world imaging problems by creating as many nearby viewpoints as necessary chosen at will.

(95) FIG. 10 shows a field 500 of multiple coordinated detectors (nodes) 1, 2, 3 . . . n. There can be any number of nodes in such a field. A number of nodes (conveniently 12) can be assembled temporarily as irregular polygons which we call tracking skeletonsbecause out of a field of many detectors they might represent a bare bones minimum for effective tracking Examples given here are (i) a skeleton 505 consisting of nodes 1, 3, 4, 5 and 7 for tracking a missile 503, which skeleton could mutate rapidly upstream to higher numbered nodes such as 11, 12, etc. depending on the velocity of the missile; (ii) skeleton 506 consisting of nodes 6, 7, 9, 10, 11 for tracking an aircraft 502; (iii) another skeleton (unnumbered) for tracking a drone 504, expecting the last skeleton to mutate slowly for a slow drone.

(96) In FIG. 10 the volume 501 also describes an ellipsoid horopter, loosely enveloping the limits of visual perception of a system of detectorsor of our eyes. This horopter may be loosely defined as a curve of the limits of visual acuity, or further defined as a limit to the ability of any two detectors to see an object in 3D. We may pick an anglesay 1for that limit, selected (arbitrarily) because smaller than that we cannot easily distinguish objects in 3D. This limit is defined as the angle subtended by an object at a particular height between two ranging detectors. For a human being this would be 12.5 feet. Distinguishing objects at 60 miles would take a pair of detectors separated by a mile.

(97) The horopter 501 would also have its limits defined by the size of its base 500 (which is nodes), the maximum limit of 3D discrimination, and the distance apart of its detectors for effective tracking There could be multiple fields like 500 for long-distance tracking, for example twenty-five across the width of the United States, each accounting for a hundred-mile extent.

(98) The size of the horopter 501 would depend on the objects being tracked and their altitude. For drones 504 flying at five hundred feet the horopter envelope could be a few hundred feet high, using detectors ten feet apart. For aircraft 502 cruising at 60,000 feet the horopter envelope could be twelve miles high, with detectors 1000 feet apart. Detection of both planes and drones could be combined in the same field, a rough diameter of the skeletons for each being commensurate with their targets' altitudes.

(99) The extent of the horopter would also depend critically on an anticipated threat. In one scenario a missile might be approaching at 600 miles an hour. Detectors a mile apart would recognize it 6 minutes away. It might be better to allow double the minutes for response with detectors twice the distance apart, implying a horopter twice as large.

(100) FIG. 11 illustrates a system 700 for collecting and processing signals from a field 500 of detectors 1, 2, 3, . . . n, as in FIG. 10. When motion is picked up by these skyward-facing detectors, the signals are fed in parallel to a computer 702. Altitude and trajectory can be swiftly calculated, as already noted. A nearby database 701 can be consulted for eidetic correspondences. With correspondence and trajectory confirmed (703) a decision can be made (704) whether to accept the object (502, 503, or 504) as harmless or to destroy it (705) with a lethal weapon (520).

(101) As shown in Iron Dome with a similar configuration, the recent availability of ultra-high-speed processors allows the computation of highly complex data in speeds approaching real-time. With fast image recognition algorithms and high-speed software, 3D ranging can be done in milliseconds. This allows equally fast (and automated) response to incoming missiles threatening major institutions in cities like New York or Washingtonall the while the missiles being unaware that they being tracked and therefore less capable of taking evasive or jamming action.

(102) Iron Dome uses radar, it is active. The system 500-700 is passive, with massively parallel redundant architecture, spread over large areas with inexpensive optics, capable of using a computer the size of a cell-phone, capable of multiple replication, and much harder to incapacitate.

(103) The system portion 700 can also transmit data through the net, via satellite or on dedicated underground fiber-optics for immediate display or for storage.

(104) The computer 702 in FIG. 11 processes select combinations of detectors 1, 2, 3 . . . , and 10, 11, 12 . . . in small groups chosen by the computer in a predetermined order of significance. For example, the missile 503 may be determined the greatest threat and therefore allocated the prime detectors and computing resources. The computed trajectories of recognized objects such as 502, 503 and 504 (a plane, a missile and a drone) may be made available for transmission as plots and statistics for others, even though decisions, such as shooting down the missile 503 with rockets 520 will have been predetermined by the computer and performed in milliseconds.

(105) For recognition we can adapt training algorithms, such as those described by C. M. Bishop in Pattern Recognition and Machine Learning (2006). These can be simplified knowing the anticipated shape, size, color, markings etc. of the aircraft, missiles, rockets, drones, etc. expected in the area. These can be stored in the templates section 701 of the computer 702. Into the algorithms will be built the expectation that certain flying objects will recur regularly, intact and moving on appropriate trajectories. The computer 702 will also be smart enough to detect anomalies in size, speed and identification of all objects and be made to react accordingly.

(106) Data in an abbreviated form may be transmitted over the Internet (which has many redundant channels), through cellular communications channels such as 3G or LTE, or using Immarsat Global Xpress, all of whom provide high-bandwidth connections. If critical the system can use underground fiber-optics 712 (with vast bandwidth) to remote bunkers. By whichever transmission method the data can be decompressed and shown on remote display 710, and can be sent to storage in a remote unit 711.

(107) In more detail: In FIG. 11 the incoming data to computer 702 is tagged with its instantaneous coordinates from a Global Positioning System. This input is fed into a processor (a section of computer 702) which has internal DSP functions to create the enhanced image stabilization as necessary for images from distant objects. For transmission across the Internet another internal processor provides dual stream H.264 encoding, handles data compression, MJPEG encoding, and an output to a Physical Layer chip 707 for transmission over the Internet cloud 708 for remote 3D viewing. The processor 702 also has an output to a wireless connection which uses 802.11n for 4G communication speeds. Other local channels provided are an RS-485/RS-232 output to local storage, an HDMI output for 3D viewing on a local display 706.

(108) At the receiving end a decoder 709 has the capacity to capture 500 MegaPixels per second and process full 3DHD of 1080p60 for a remote display 710. The rate at which scenes can unfold on this display is limited only by the vagaries of the Internet and of the wireless channels.

(109) In this Codec description we are following MPEG-4, which is a collection of methods defining compression of audio and visual (AV) digital data beginning in 1998. It was at that time designated a standard for a group of audio and video coding formats and related technology agreed upon by the ISO/IEC Moving Picture Experts Group (MPEG) under the formal standard ISO/IEC 14496. In July 2008, the ATSC standards were amended to include H.264/MPEG-4 AVC compression and 1080p at 50, 59.94, and 60 frames per second (1080p50 and 1080p60)the last of which is used here. These frame rates require H.264/AVC High Profile Level 4.2, while standard HDTV frame rates only require Level 4.0. Uses of MPEG-4 include compression of AV data for web (streaming media) and CD distribution voice (telephone, videophone) and broadcast television applications). We could equally use any other protocol (or combination of protocols) suitable for transferring high-speed data over airwaves or land-lines.

(110) This invention relates to the remote, passive ranging of objects which are of interest to military observers and others. The addition of a dimension beyond 2D replicates the vision of the human eye and contributes the perception of depth, and adding valuable information for the inspection of diverse (in this case flying) objects. These can be instantaneously compared and sorted against three-dimensional (3D) templates which may reflect the ideal for that particular object. With advanced object recognition software inspection can be done at high speed and with great accuracy. The images can also be compressed in real time for high-speed transmission for remote display or analysis, or sent for compact storage. The techniques of this invention are applicable in the visible, infra-red, microwave and ultra-violet portions of the spectrum, and may apply also to sonar or ultrasound.

(111) While the invention has been described and illustrated in general as a method for recognizing, tracking and evaluating three dimensional objects such as aircraft and missiles, in fact to those skilled in the art, the techniques of this invention can be understood and used as means for creating and perfecting three-dimensional recognition, inspection and measurement tools for various subjects throughout the electro-magnetic spectrum and beyond.

(112) The techniques of this invention may be applied whether detectors are moving relative to fixed objects, or objects are moving relative to fixed detectors.

(113) It may be understood by those skilled in the art that although specific terms may be employed in this invention, they are used in a generic and descriptive sense and must not be construed as limiting. The scope of this invention is set out in the appended claims.