Выделить слова: 

Патент США №

8208131

Автор(ы)

Schilling и др.

Дата выдачи

26 июня 2012 г.

Digital registration of 3D laser radar data based on manually selected fiducials



РЕФЕРАТ

A system and method for registering 3D data sets is disclosed based on manual fiducial selection. The technique is useful in imaging obscured targets with 3-D imaging laser radars. For such an exemplary method, which defines a three-dimensional linear shift vector for each data voxel, four fiducials are required to completely define the mapping for a 3D space. An exemplary registration algorithm as disclosed provides an approach to automatically make fine adjustments to the 3D data registration. The tedious technique of shifting data sets relative to each other, in many degrees of freedom, is eliminated. Instead, a fine adjust is applied to the digital mapping function, through fiducial perturbation.

Авторы:

Bradley W. Schilling (Fredericksburg, VA), Brian W. Thomas (Reston, VA), Dallas N. Barr (Woodbridge, VA), Charlie W. Trussell (Woodbridge, VA)

ID семейства патентов

45399295

Номер заявки:

12/828,318

Дата регистрации:

01 июля 2010 г.

Класс патентной классификации США:

356/5.01; 356/3.01; 356/5.04; 356/5.1

Класс международной патентной классификации (МПК):

G01C 3/08

Класс совместной патентной классификации:

G01S 17/89 (20130101)

Область поиска:

356/3.01-139.1

Использованные источники

[Referenced By]

Патентные документы США

6414746July 2002Stettner et al.
2002/0060784May 2002Pack et al.
2007/0052947March 2007Ludwig et al.
2008/0246943October 2008Kaufman et al.

Другие источники


B W. Schilling, D. N. Barr, G. C. Templeton, L. J. Mizerka, C. W. Trussell, "Multiple-return laser radar for three-dimensional imaging through obscurations" Appl. Opt. 41, 2791-2799 (2002). cited by other .
C. W. Trussell, "3D imaging for Army applications," in Laser Radar and Technology Applications VI, G. W. Kamerman, ed., Proc. SPIE 4377, 126-131 (2001). cited by other .
C. W. Trussell, D. N. Barr, B. W. Schilling, G. C. Templeton, L. J. Mizerka, C. Warner, R. Hummel and R. Hauge "Multi-aspect high-resolution ladar data collection", Proceedings SPIE 5086, pp. 104-111 (2003). cited by other .
D. Ludwig, et. al., "Identifying targets under trees: jigsaw 3D ladar test results," in Proceedings of SPIE vol. 5086 Laser Radar Technology and Applications VIII, edited by Gary W. Kamerman (SPIE. Bellingham, WA, 2003) pp. 16-26. cited by other .
A. Gelbart, C. Weber, S. Bybee-Driscoll, j. Freeman, G. J. Fetzer, T. Seales, K. A. McCarley, J. Wright, "FLASH Lidar data collections in terrestrial and ocean environments," in Proceedings of SPIE vol. 5086 Laser Radar Technology and Applications VIII, edited by Gary W. Kamerman (SPIE. Bellingham, WA, 2003) pp. 27-38. cited by other .
S. Hsu, S. Samarasekera and R. Kumar, "Automatic registration and visualization of occluded targets using ladar data," in Proceedings of SPIE vol. 5086 Laser Radar Technology and Applications VIII, edited by Gary W. Kamerman (SPIE. Bellingham, WA, 2003) 209-220. cited by other .
B. L. Stann, W. C. Ruff, Z. G. Sztankay, "Intensity-modulated diode laser radar using frequency-modulated/continuous-wave ranging techniques," Opt. Eng. 35(11) 3270-3278 (Nov. 1996). cited by other .
B. L. Stann, et. al., "Research progress on a focal plane array ladar system using chirped amplitude modulation," in Proceedings of SPIE vol. 5086 Laser Radar Technology and Applications VIII, edited by Gary W. Kamerman (SPIE. Bellingham, WA, 2003) pp. 47-57. cited by other .
M. A. Albota, et. al., "Three-dimensional imaging laser radar with a photon-counting avalanche photodiode array and microchip laser," Appl. Opt. 41, 7671-7678 (2002). cited by other.

Главный эксперт: Ratcliffe; Luke
Уполномоченный, доверенный или фирма: Kim; Richard J.

Интересы правительства



GOVERNMENT INTEREST

The invention described herein may be manufactured, used, sold, imported, and/or licensed by or for the Government of the United States of America.

ФОРМУЛА ИЗОБРЕТЕНИЯ



What is claimed is:

1. A registration algorithm to process 3D laser radar data sets using a computing device to map obscured objects based on fine adjustments to the 3D data registration, comprising: defining fiducials based on an imaged reference point identifiable in each data set; using the fiducials as anchor points to create a digital mapping relating two or more data sets; and defining a three-dimensional linear shift vector for each data voxel to allow fine adjustments to the 3D data registration and improve target-identification of an obscured target, wherein said fine adjustments to the 3D data registration are based on fiducial perturbation without having to shift data sets relative to each other with respect to various degrees of freedom.

2. The registration algorithm according to claim 1, wherein the fiducials are visually selected from each data set as an initial course alignment.

3. The registration algorithm according to claim 1, wherein four fiducials are used to define the mapping for a three-dimensional space.

4. A 3D laser radar system based on a laser transceiver sensor system, comprising: producing nominal pulses of laser from a microchip towards scanners, the scanners being computer controlled to scan a monostatic transceiver field of view directed towards a scene having an obscured target, wherein said scanning yields at least one data set relating to said obscured target acquired from one location during one time period, and another data set relating to said obscured target acquired from another location during another time period; reflecting a returning radiation from the scene by a polarization beam splitter for focusin on a preamplifier module, wherein a post-amplifier further amplifies the output of the preamplifier module; digitizing said amplified output for input t a computing device to acquire data from differing aspect angles; computer processing data. from one 3D imaging laser radar location at one aspect angle, wherein the target is obscured such that some amount of laser radiation passes through and scatter at the target; identifying the target by accumulating one data set acquired from said one 3D imaging laser radar location based on said laser radiation scattered at the target, resulting in a limited number of target-voxels; computer processing another data set from another 3D imaging laser radar location at another aspect angle, wherein the target obscuration from said another aspect angle is such that another amount of another laser radiation passes through another set of gaps and scatter differently at the target; identifying the target by accumulating said another data set acquired from said another 3D imaging laser radar location, resulting in a differing number of target-voxels in the another data set; and as target-voxels from different data acquisitions are registered and accumulated, constructing a complete 3D representation of the obscured target, wherein the 3D representation of the obscured target acquired from differing aspect angles improves identification of the obscured target.

5. The 3D laser radar system according to claim 4, comprising: a telescope having a filter at an entry aperture capable of blocking said nominal pulses of laser diode; a diverging lens and a primary lens, along with said polarization beam splitter, being disposed in an optical path of the telescope; and a quarter wave plate disposed at an output end of said telescope and in an optical path before towards said scanners.

6. The 3D laser radar system according to claim 4, wherein said obscured target is obscured by a foliage canopy or camouflage net.

7. The 3D laser radar system according to claim 4, wherein said another data set from said another aspect angle of said another 3D imaging laser radar obtains another pass through another set of holes in a foliage, resulting in another independent collection of target voxels.

8. The 3D laser radar system according to claim 4, wherein fiducials are selected from each data set based on physical data points that are easily recognizable in both data sets.

9. The 3D laser radar system according to claim 4, wherein a fine adjustment is applied to a digital mapping process based on fiducial perturbation.


ОПИСАНИЕ



FIELD OF THE DISCLOSURE

The disclosure relates to imaging obscured targets using three-dimensional (3D) imaging laser radar.


ИНФОРМАЦИЯ ОБ УРОВНЕ ТЕХНИКИ



In the past, numerous targeting scenarios have been investigated. Usually, laser radar data is recorded of a target or scene that is obscured by foliage, camouflage netting, or other obscurations. The data acquisition process is repeated for the same target, but from different locations, or view-points. A frequency-modulated ladar can be used to study the problem and record multi-aspect laser radar imagery.

One of the most straightforward techniques for registering 3D data is to calculate the actual physical location of the voxels in each data set. Other researchers have successfully "stitched together" multi-aspect laser radar data by this technique. A potential drawback of this straightforward method is the necessity for precise positioning information, such as the location of the laser radar transceiver at the time of acquisition, the location of some object clearly visible in the scene, and/or the precise pointing direction of the acquisition system. Precise and absolute positioning information may be difficult to acquire, require special equipment, or simply not be available in some cases. For this reason and others, purely databased registration techniques are being developed for three-dimensional data sets. Researchers from Sarnoff Corporation have successfully registered multi-aspect laser radar data sets of occluded objects with a technique that is data-driven and automatic.

A key aspect of the general concept is the capability to register and combine the three-dimensional data without the difficulties of using special equipment or not being able to acquire the data at all. Therefore, there is a need in the art to overcome these difficulties.


СУЩНОСТЬ



The disclosure relates to registering 3D data sets to map obscured objects based on scene fiducials, where a fiducial is defined as an easily identifiable physical reference point common to each data set. The fiducials are used as anchor points to create a digital mapping relating two or more data sets. An exemplary embodiment defines a three-dimensional linear shift vector for each data voxel, wherein four fiducials are used to completely define the mapping for a 3D space. Using an exemplary registration algorithm as disclosed provides a novel approach to automatically make fine adjustments to the 3D data registration. The tedious technique of shifting data sets relative to each other, in many degrees of freedom, is eliminated. Instead, a fine adjust is applied to the digital mapping function, through fiducial perturbation.

Accordingly, in one aspect, a digital registration of 3D laser radar data is disclosed for imaging processing based on selected fiducials using a laser radar system. Such a digital registration comprises: raster scanning by a scanner of the laser radar system a target from at least two different positions; using predetermined fiducials to create a digital mapping relating the raster scans from the at least two different positions to each other; defining a three-dimensional linear shift vector for data voxels from the digital mapping; and image mapping using the three-dimensional linear shift vector to improve target-identification of an obscured target.

In another aspect, a registration algorithm is disclosed to process 3D laser radar data sets using a computing device to map obscured objects based on fine adjustments to the 3D data registration. Such a registration algorithm comprises: defining fiducials based on an imaged reference point identifiable in each data set; using the fiducials as anchor points to create a digital mapping relating two or more data sets; and defining a three-dimensional linear shift vector for each data voxel to allow fine adjustments to the 3D data registration and improve target-identification of an obscured target.

The present disclosure is based on identifying a target by accumulating data collected through the small gaps in the foliage canopy or camouflage net with a 3D imaging laser radar. Even for heavy (but not complete) obscuration, some amount of laser radiation will pass through gaps and scatter at the target, resulting in a limited number of target-voxels in any single data set. Subsequent laser radar data acquisitions of the same target area, but from varying positions, will each pass through a different set of holes in the foliage, resulting in an independent collection of target-voxels. As target-voxels from different data acquisitions are registered and accumulated, a complete 3D representation of the target may be constructed. Once the data is registered, 3D laser radar data acquired from differing aspect angles improves the target-identification capability of heavily obscured targets.

Accordingly, yet in one aspect, a 3D laser radar system is disclosed based on a laser transceiver sensor system. Such a 3D laser radar system comprises: producing nominal pulses of laser from a microchip towards scanners, the scanners being computer controlled to scan a monostatic transceiver field of view directed towards a scene having an obscured target, wherein said scanning yields at least one data set relating to said obscured target acquired from one location during one time period, and another data set relating to said obscured target acquired from another location during another time period; reflecting a returning radiation from the scene by a polarization beam splitter for focusing on a preamplifier module, wherein a post-amplifier further amplifies the output of the preamplifier module; digitizing said amplified output for input to a computing device to acquire data from differing aspect angles; computer processing data from one 3D imaging laser radar location at one aspect angle, wherein the target is obscured such that some amount of laser radiation passes through and scatter at the target; identifying the target by accumulating one data set acquired from said one 3D imaging laser radar location based on said laser radiation scattered at the target, resulting in a limited number of target-voxels; computer processing another data set from another 3D imaging laser radar location at another aspect angle, wherein the target obscuration from said another aspect angle is such that another amount of another laser radiation passes through another set of gaps and scatter differently at the target; identifying the target by accumulating said another data set acquired from said another 3D imaging laser radar location, resulting in a differing number of target-voxels in the another data set; and as target-voxels from different data acquisitions are registered and accumulated, constructing a complete 3D representation of the obscured target, wherein the 3D representation of the obscured target acquired from differing aspect angles improves identification of the obscured target.


КРАТКОЕ ОПИСАНИЕ РИСУНКОВ



These and other objects of the disclosure will become readily apparent in light of the Detailed Description and the attached drawings wherein:

FIG. 1a is an exemplary schematic illustration of the multiple aspect data collection of an obscured target by imaging laser radar.

FIG. 1b shows an exemplary optical layout of an laser transceiver sensor system for data collection of obscured target.

FIG. 2 shows an exemplary imaging laser radar records data in a regularly spaced 3D array wherein each data point, called a voxel, has a truncated pie shape.

FIG. 3 is a theoretical 2D illustration of an exemplary registration data taken from two different, widely displaced, aspect angles.

FIG. 4 is a graphical representation of an exemplary mapping function for the x-dimension in the 2D example. For any point in the 2D space that is data set A, the map gives the .delta..sub.x-shift to locate the companion pixel in data set B.

FIG. 5 is a graphical representation of an exemplary mapping function for the y-dimension in the 2D example. For any point in the 2D space that is data set A, the map gives the .delta..sub.y-shift to locate the companion pixel in data set B.

FIG. 6a shows an exemplary arrangement of items for experimental results from perspective A. The 1 by 4 board occludes a portion of the box.

FIG. 6b shows an exemplary occluded object from perspective B.

FIGS. 7a through d are exemplary laser radar data displayed as intensity mappings of the test objects, a) from perspective A, b) from perspective B, c) from perspective A with occluder gated out and d) from perspective B with occluder gated out.

FIGS. 8a and 8b are exemplary point cloud renderings rotated by computer of the laser radar data for a) perspective A, b) perspective B.

FIG. 9 shows an exemplary target wherein the fiducials used in the registration algorithm are indicated by circles.

FIG. 10 shows exemplary registered and combined 3D laser radar data displayed as a range-gated intensity map, consistent with the display parameters of FIG. 7d).

FIG. 11a is an exemplary point cloud representation of the scene with data from perspectives A and B registered and combined.

FIG. 11b is an exemplary point cloud representation of the target area recorded with the central board physically removed from the scene. Display parameters are identical to that of FIG. 8 b).

FIG. 12 shows exemplary graphical results of registration/combination using additional fiducials. The horizontal axis shows the number of fiducials used to calculate the mapping function. The vertical axis shows the number of discrepancy voxels between the combined data and the unobscured data, calculated by a logical NOR.


ПОДРОБНОЕ ОПИСАНИЕ



Laser Radar and 3D Data Collection

A short-pulsed, direct-detection, scanning laser radar is disclosed to record and process 3D data. Such a ladar system can be based on a single laser, single detector, common-aperture architecture. An exemplary ladar system (e.g., 100) employs a diode pumped, passively Q-switched, Nd:YAG, micro-chip laser (e.g., 110) capable of emitting short laser pulses (on the order of about .about.1.2 nanosecond) of high peak power (e.g., 5 kW). In one exemplary embodiment, two galvanometer-scanning mirrors (e.g., 150) direct the laser radiation (e.g., 101) to the area of interest, scanning the scene in a raster fashion. The laser radar return signals (e.g., 102)) are detected by a photodiode 160, e.g., an InGaAs avalanche photodiode, and then amplified, digitized and stored, e.g., in a computer 190 storage device. This data results in a regularly spaced 3D array representing the volume of interest, as shown in FIG. 2.

An exemplary embodiment is shown as a laser transceiver system in FIG. 1b. Further, FIG. 1b shows an exemplary optical layout of such a laser transceiver sensor system 100 in which a Nd:YAG microchip laser (e.g., 110) produces nominal pulses, e.g., one nanosecond pulses at a rate of three kilohertz. A computer-controlled shutter 111 can remain closed, for safety, until the scanners (e.g., 150) are active. This results in an eye safe range, e.g., of about 35 meters. A filter (e.g., 121) at the entry aperture of a telescope (e.g., 120) can block diode laser pump radiation. A diverging lens (e.g., L1) serves as the telescope secondary optic and after passing through a polarization beam splitter (e.g., 130) the beam divergence is reduced to about 100 micro radians by the primary lens (e.g., L2). The linearly polarized radiation is converted to circular polarization by the quarter wave plate (140) that is the last element of the optical path before the scanners (e.g., 150). The galvo scanners (e.g., 150) can be computer (e.g., 190) controlled, e.g., via a D/A converter 191, to scan a monostatic transceiver field of view, e.g., in 0.5 milliradian steps. Returning radiation (e.g., 102) from the scene is reflected from the polarization beam splitter (e.g., 130) and focused on a preamplifier module 160 having, e.g., a 2.5 GHZ bandwidth (e.g., based on an InGaAs avalanche photodiode). The focal length of the primary lens (e.g., L2) can be nominally 100 millimeters and the detector (e.g., 160) can have a 30 micron diameter so the field of view of the receiver is about 300 micro radians. A post-amplifier (e.g., 170), e.g., that has a bandwidth of 500 MHz, can further amplify the output of a detector/preamplifier (e.g., 160). An RF splitter can divide the signal for delivery to an oscilloscope and an A/D converter 180 (e.g., an eight bit computer digitizer that samples at 2 Gs/s) for input to a computing device (e.g., 190). Such an input data can be processed by the computing device 190 to result in a regularly spaced 3D array representing the volume of interest, as shown in FIG. 2.

Accordingly, an exemplary 3D laser radar system can be based on such a laser transceiver sensor system. An exemplary 3D laser radar system comprises: producing nominal pulses of laser from a microchip towards scanners, the scanners being computer controlled to scan a monostatic transceiver field of view directed towards a scene having an obscured target, wherein said scanning yields at least one data set relating to said obscured target acquired from one location during one time period, and another data set relating to said obscured target acquired from another location during another time period; reflecting a returning radiation from the scene by a polarization beam splitter for focusing on a preamplifier module, wherein a post-amplifier further amplifies the output of the preamplifier module; digitizing said amplified output for input to a computing device to acquire data from differing aspect angles; computer processing data from one 3D imaging laser radar location at one aspect angle, wherein the target is obscured such that some amount of laser radiation passes through and scatter at the target; identifying the target by accumulating one data set acquired from said one 3D imaging laser radar location based on said laser radiation scattered at the target, resulting in a limited number of target-voxels; computer processing another data set from another 3D imaging laser radar location at another aspect angle, wherein the target obscuration from said another aspect angle is such that another amount of another laser radiation passes through another set of gaps and scatter differently at the target; identifying the target by accumulating said another data set acquired from said another 3D imaging laser radar location, resulting in a differing number of target-voxels in the another data set; and as target-voxels from different data acquisitions are registered and accumulated, constructing a complete 3D representation of the obscured target, wherein the 3D representation of the obscured target acquired from differing aspect angles improves identification of the obscured target.

Digital sampling (e.g., 180) and storage of the entire return signal over a time period of interest as disclosed yields an enhanced computer processing capability to detect objects in a target area behind or through partial obscurations as exemplified in FIG. 1a, which, in turn, results in a more completely filled 3D array of data as may be represented on a computing device 190. A typical laser radar data set as may be processed by a computing device 190 consists of a regularly spaced 3D array of truncated pie-shaped voxels containing 8-bit intensity values. The total physical volume interrogated by the laser radar is determined in .theta. and .phi. by the scanning voltages and in p by the digitization length of the avalanche photodiode signal. In the lateral dimensions, the sampling resolution is determined by the number of points stored for each line scan in .theta., and in .phi. by the number of lines scanned. The sampling resolution along the depth dimension is dependant on the digitization frequency (f.sub.d) of the return signal. Laser radar data can be displayed in a number of ways, including a 2D intensity image, a 2D range mapping, and a full 3D rendering of the entire volume of data. Somewhat inherent in the 3D nature of laser radar data is the ability to display multiple range bins to show a specific range-gated volume of interest. This range gating technique is often employed to avoid displaying obscurations and clutter that can be separated based on range information.

In one aspect, the following disclosure includes a digital registration of 3D laser radar data for imaging processing based on selected fiducials using a laser radar system (see, FIGS. 1a and 1b). Such a digital registration comprises: raster scanning by a scanner (e.g., 150 of FIG. 1b) of the laser radar system a target from at least two different positions (e.g., t.sub.1, t.sub.2, etc. of FIG. 1a); using predetermined fiducials to create a digital mapping relating the raster scans from the at least two different positions to each other; defining a three-dimensional linear shift vector for data voxels from the digital mapping; and image mapping using the three-dimensional linear shift vector to improve target-identification of an obscured target (e.g., target area of FIG. 1a).

In another aspect, the following disclosure includes a registration algorithm to process 3D laser radar data sets using a computing device (e.g., 190) to map obscured objects based on fine adjustments to the 3D data registration. Such a registration algorithm comprises: defining fiducials based on an imaged reference point identifiable in each data set; using the fiducials as anchor points to create a digital mapping relating two or more data sets; and defining a three-dimensional linear shift vector for each data voxel to allow fine adjustments to the 3D data registration and improve target-identification of an obscured target (e.g., target area of FIG. 1a).

Three Dimensional Data Registration Algorithm

A. Heuristic Description

The data registration algorithm of the present disclosure can be implemented as a computer program for processing by a computing device (e.g., 190) to operate on two or more three-dimensional data sets, e.g., data sets A and B. As shown in FIG. 1a, a plurality of laser radar data sets represent the same target area but have been acquired from different transceiver locations. For instance, with regard to FIG. 1a, data set A may be acquired at time t.sub.1, while data set B is acquired from a different location and time, say t.sub.2. Next, consider a specific voxel from data collection A, referenced (only) to data set A, designated (X.sub.A, Y.sub.A, Z.sub.4), after conversion to Cartesian coordinates. Since the data in B represent the same physical location in space, there will be a corresponding voxel in data set B, referenced to data set B, as (X.sub.B, Y.sub.B, Z.sub.B), that designates the same physical location in space. Physical data points that are easily recognizable in both data sets are considered reference points, and are referred to as fiducials. The voxel representing a fiducial, F.sub.1, from data set A can therefore be related to the voxel corresponding to F.sub.1 in data set B through a mapping or shift vector, (.delta..sub.x1, .delta..sub.y1, .delta..sub.z1) where .delta..sub.x1=X.sub.B-X.sub.A, .delta..sub.y1=y.sub.B-y.sub.A, .delta..sub.z1=Z.sub.B-Z.sub.A.

This correspondence can be made even though (x.sub.A, y.sub.A, z.sub.A) and (x.sub.B, y.sub.B, z.sub.B) exist in different reference frames and different coordinate systems. The corresponding voxels from each data set are defined to represent the same physical location to be companion voxels. It follows that for any voxel in data set A, there is a companion voxel in data set B that can be accessed by applying some shift (.delta..sub.xn, .delta..sub.yn, .delta..sub.zn), (except near the edges of the data sets, where physical overlap may not take place).

The identification of a second fiducial in each data set defines not only the shift vector associating companion voxels for the two fiducials, but through linear interpolation, the set of shift vectors for any voxel that lies on a line connecting the two fiducials. Likewise, add a third noncolinear fiducial to the set of anchor points, and a mapping can be defined that relates the voxels which lie in a plane created by the three fiducials. The complete, three-dimensional data set that defines the linear shifts relating each voxel in data set A to its companion voxel in data set B (or mapping data A into data B) is itself a 3-D array, each element being a 3-D shift vector, and is completely defined by four fiducials. These shifts in separate dimensions are linear and separable, allowing the mapping function to be treated as three separate three-dimensional arrays, each element consisting of the linear shift in the appropriate dimension, x, y, or z. Once the complete mapping function is defined, based on four fiducials, the data sets are registered: for any voxel in data set A the corresponding mapping vector, (.delta..sub.xn, .delta..sub.yn, .delta..sub.zn), is applied to accesses the companion voxel in data set B, and the two voxels are compared.

B. Analytical Formalism

In order to treat the mapping function of each spatial dimension separately, let .alpha.=x, y, or z. Again, for any voxel, (X.sub.A, Y.sub.A, Z.sub.A) in data set A, there is an .alpha.-map that relates that voxel to its companion in data set B. It is possible to define an .alpha.-mapping for every point in the 3D space that is data set A based on four fiducials, (which do not lie in a plane). Specifically, four fiducial-voxels in data set A are selected: F.sub.A1=(x.sub.A1,y.sub.A1,z.sub.A1) F.sub.A2=(x.sub.A2,y.sub.A2,z.sub.A2) F.sub.A3=(x.sub.A3,y.sub.A3,z.sub.A3), and F.sub.A4=(x.sub.A4,y.sub.A4,z.sub.A4) (1) The companion voxels are identified in data set B: F.sub.B1=(x.sub.B1,y.sub.B1,z.sub.B1) F.sub.B2=(x.sub.B2,y.sub.B2,z.sub.B2) F.sub.B3=(x.sub.B3,y.sub.B3,z.sub.B3), and F.sub.B4=(x.sub.B4,y.sub.B4,z.sub.B4) (2) With these four fiducials, the set of shifts are defined: .delta..sub.x1=x.sub.B1-x.sub.A1 .delta..sub.y1=y.sub.B1-y.sub.A1 .delta..sub.z1=z.sub.B1-z.sub.A1 .delta..sub.x2=x.sub.B2=x.sub.A2 .delta..sub.y2=y.sub.B2=y.sub.A2 .delta..sub.z2=z.sub.B2=z.sub.A2 .delta..sub.x3=x.sub.B3.times.x.sub.A3 .delta..sub.y3=y.sub.B3.times.y.sub.A3 .delta..sub.z3=z.sub.B3.times.z.sub.A3 .delta..sub.x4=x.sub.B4/x.sub.A4 .delta..sub.y4=y.sub.B4/y.sub.A4 .delta..sub.z4=z.sub.B4/z.sub.A4 (3) The definitions of (1), (2), and (3) allow us to map any voxel in data set A, (X.sub.An, Y.sub.An, Z.sub.An), to its companion in data set B, by solving the following equation for .delta..sub.an. A.sub..alpha.x.sub.An+B.sub..alpha.y.sub.An+C.sub..alpha.Z.sub.An+D.sub..- alpha..delta..sub..alpha.n+E.sub..alpha.=0 for .alpha.=x, y, or z (4) Where A.sub..alpha., B.sub..alpha., C.sub..alpha., D.sub..alpha., and E.sub..alpha. are the following determinants:

.alpha..times..times..times..times..delta..alpha..times..times..times..ti- mes..times..times..delta..alpha..times..times..times..times..times..times.- .delta..alpha..times..times..times..times..times..times..delta..alpha..tim- es..times..alpha..times..times..times..times..times..delta..alpha..times..- times..times..times..times..times..delta..alpha..times..times..times..time- s..times..times..delta..alpha..times..times..times..times..times..times..d- elta..alpha..times..times..times..alpha..times..times..times..times..delta- ..alpha..times..times..times..times..times..times..delta..alpha..times..ti- mes..times..times..times..times..delta..alpha..times..times..times..times.- .times..times..delta..alpha..times..times..alpha..times..times..times..tim- es..times..times..times..times..times..times..times..times..times..times..- times..times..times..times..times..times..times..times..times..times..time- s. ##EQU00001## .alpha..times..times..times..times..times..times..delta..alpha..times..ti- mes..times..times..times..times..times..times..delta..alpha..times..times.- .times..times..times..times..times..times..delta..alpha..times..times..tim- es..times..times..times..times..times..delta..alpha..times..times..times. ##EQU00001.2## Equation (4) is an extension of the expression for a plane based on three known points, but extended to another dimension.

C. Numerical Analysis in Two Dimensions

Now consider a simple example of the mapping technique in two dimensions. FIG. 3 shows four points arranged in a square, as seen from two different viewing angles, separated by 45.degree.. The mapping function(s) will be treated as two two-dimensional arrays, one for each spatial dimension. The set of a-shifts, where .alpha.=x, y, lie in a plane and can be completely determined by three (noncolinear) points, or fiducials. Specifically, three fiducial pixels are selected for data set A: F.sub.A1=(X.sub.A1,y.sub.A1)=(0,0), F.sub.A2=(X.sub.A2,y.sub.A2)=(0,1), and F.sub.A3=(X.sub.A3,y.sub.A3)=(1,1). (5) The companion pixels are identified in data set B:

.times..times..times..times..times..times..times..times..times..times..ti- mes..times..times..times..times..times..times..times..times..times..times. ##EQU00002## With these three fiducials, the set of shifts are defined as follows:

.delta..times..times..times..times..times..times..times..delta..times..ti- mes..times..times..times..times..times..delta..times..times..times..times.- .times..times..times..delta..times..times..times..times..times..times..tim- es..delta..times..times..times..times..times..times..times..delta..times..- times..times..times..times..times. ##EQU00003## The key to understanding the registration algorithm of the present disclosure is to realize that for a single dimension (a=x, y), the shifts defined in (7) lie on a plane in the coordinate system of (x.sub.A, y.sub.A, .delta..sub.x). That plane is defined by three points, hence the need for three fiducials. The plane is defined, from definitions (5), (6), and (7) by A.sub..alpha.x.sub.An+B.sub..alpha.y.sub.An+C.sub..alpha..delta..sub.an+D- .sub..alpha.=0 for .alpha.=x,y, (8) where A.sub..alpha., B.sub..alpha., C.sub..alpha., and D.sub..alpha. are the following determinants:

.alpha..times..times..delta..alpha..times..times..times..times..delta..al- pha..times..times..times..times..delta..alpha..times..times..alpha..times.- .times..delta..alpha..times..times..times..times..delta..alpha..times..tim- es..times..times..delta..alpha..times..times..times..times..times..times..- times..times..times..times..times..times..times..times..times..times..time- s..times..times..times..times..delta..alpha..times..times..times..times..t- imes..times..delta..alpha..times..times..times..times..times..times..delta- ..alpha..times..times. ##EQU00004##

This plane, or mapping function, can be used to map any pixel in data set A, (X.sub.An, y.sub.An), to its companion in data set B, by solving equation (8) for .delta..sub..alpha.n. Substitution of (5), (6) and (7) into (8) yields

.times..times..delta. ##EQU00005## Similarly, for the y-shift, substitution into (8) yields

.times..times..delta. ##EQU00006## Equation (9) and (10), shown graphically in FIGS. 4 and 5, completely describe the mapping between the two data sets. To demonstrate, consider (x.sub.A, yA)=(1, 0). The companion pixel location in data set B is determined by calculating the shift vector using (9) and (10), or

.delta..delta. ##EQU00007## The companion pixel location is therefore,

.delta..delta. ##EQU00008##

The algorithm demonstrated in this 2D example is readily expandable to the third dimension, although the mapping functions become more difficult to visualize. Equation (4) is used to gain access to a voxel's companion in the second data set, the voxels are compared and the appropriate action taken.

For analytical data, such as in this 2D example, the mapping created using equation (4) can be shown to be an exact mapping, however, the same cannot be said of experimental data. Measurement uncertainty associated with processed laser radar data introduces error in the mapping, both in object location and fiducial selection. With the exemplary embodiments as disclosed the impact of this measurement error on the final registration is minimized through the inclusion of additional fiducials into the registration process and by application of an automatic fine adjustment algorithm after manual fiducial selection is complete.

D. Incorporating Additional Fiducials for Registration of 3D Experimental Data

The mapping function is calculated by estimating a "surface" in three dimensions based on four, experimentally obtained points. Just as with the estimation of any curve with experimental data, the process is subject to error from measurement uncertainty. To try to improve the situation, additional experimental data can be incorporated and a curve estimated through some technique such as least squares approximation. In the same way, measurement uncertainty associated with the laser radar data introduces error into the mapping function. Unfortunately, additional error is inserted into the process during the fiducial selection process, since even small physical structures may span several voxels of data. For some experimental conditions, the inventors have observed that relatively small errors in manual fiducial location selection can significantly degrade the registration, particularly for regions far from the selected fiducials.

To address this issue, means of incorporating additional fiducials are included into the mapping calculation. One way of doing this is to assume that all point pairs are equally valid, and to compute a set of space maps based on each possible combination of four point pairs. The space maps are then averaged together to produce a composite map, i.e.,

.delta..fwdarw..function..delta..fwdarw..function..delta..fwdarw..functio- n..delta..fwdarw..function. ##EQU00009## where N is the total number of combinations of four point pairs and the superscript refers to the individual combinations.

This method quickly becomes computationally intensive as fiducial point pairs are added. However, much of the computation can be avoided by recognizing that the space maps can be combined before the .delta. vector for each point in the 3-D space is calculated. Solving equation (4) for .delta. yields:

.delta..alpha..function..alpha..times..alpha..times..alpha..times..alpha.- .alpha. ##EQU00010## Equation (13) holds for any given combination of four fiducial point pairs. Combinations of four point pairs and the resulting constants A, B, C, D, and E will be designated using a superscripted integer I where I=1 to .sub.nC.sub.4, and n is the total number of fiducial point pairs. Therefore,

.delta..alpha..function..alpha..times..alpha..times..alpha..times..alpha.- .alpha. ##EQU00011## The equation can then be restated in the form,

.delta..alpha..function..alpha..alpha..times..alpha..alpha..times..alpha.- .alpha..times..alpha..alpha. ##EQU00012## which allows the average components of .delta. to be computed by:

.times..times..delta..alpha..function..function..times..alpha..alpha..tim- es..times..alpha..alpha..times..times..alpha..alpha..times..times..alpha..- alpha. ##EQU00013## where N=.sub.nC.sub.4. This method allows the analytic equation for the map to be computed for any number of point pairs with a relatively low computational overhead.

E. Fine Adjust

As with many 3D data registration techniques, a multi-step process is employed to calculate a final 3D data registration, or a course alignment and a fine adjustment. For this technique, consider the process of manually selecting fiducials in each data set as the initial course alignment. It is then possible to proceed through the software to an automatic fine-adjustment stage, which tweaks the registration/combination based on some metric. It has been found through the development of the fine adjustment algorithm that the technique lends itself to a simple and efficient algorithm for fine adjustment based on fiducial perturbation. This is an improvement over other methods of digital registration, in which automatic adjustment is often computationally intensive, involving processes such as exhaustive correlation or surface matching. The simplicity of the fine adjust algorithm employed relies on the fact that for a given set of fiducial point pairs, the best possible mapping, and therefore registration, will occur from the most correctly chosen fiducial points. The technique is computationally efficient because the mapping function is altered through fiducial perturbation, as opposed to shifting the data sets with respect to each other. A one-dimensional fiducial perturbation may result in some combination of multi-dimensional translation and rotation between the data sets.

Consider the fiducial sets given in equations (1) and (2). The fine adjust technique involves perturbing each fiducial point in data set B one pixel in each direction. After each perturbation, the data sets are registered in accordance with the resulting mapping function, and a metric of registration effectiveness is calculated. The perturbation having the greatest positive effect on the registration is executed and the process is repeated. The efficiency of the algorithm is greatly enhanced by applying individual limits to the extent of perturbation for a given fiducial. For instance, the operator can include a confidence rating upon fiducial selection, prohibiting the algorithm from perturbing a fiducial point beyond some bound. Similarly, the program can initiate perturbation on fiducials points with lower confidence levels. Choosing a quantitative measure of the effectiveness of registration is not trivial, but it has been found effective to minimize logically NORed data sets for local areas of interest.

Experimental Results

The exemplary registration algorithm as disclosed was experimentally verified through a computer acquisition of laser radar data of a simple situation involving an occluded object from two different acquisition positions, again as depicted graphically in FIG. 1a. The object of this experiment is a cardboard box, approximately 66 cm wide, 93 cm tall and 61 cm deep, shown from the two acquisition perspectives in FIGS. 6a and b. The distance from the laser radar to the box is about 15.8 meters. An unpainted wooden 1 by 4 board, measuring approximately 8.6 cm wide and 93 cm in height is placed approximately 80 cm in front of the target to act as an occluder. Small black `x`s have been placed on the box and board to offer convenient fiducials for registration. Several other items with fiducial marks have been placed in the field of view, offering an array of choices for fiducial points. Horizontal and vertical scan voltages corresponding to a full-angle scan of approximately 112 mrad and scan step sizes of 437 jarad were used for this data acquisition. The return signal was digitized at 2 GS/s, offering a sampling resolution corresponding to about 7.5 cm. The measured multiple-pulse range resolution for the system is closer to 15 cm. Two laser radar data collections were conducted of this scene from positions separated by approximately 205 cm (260 mrad). The laser radar data from each perspective was displayed as a two-dimensional intensity map in FIGS. 7a and b. FIGS. 7c and d show range-gated versions of the 3D data where the 1 by 4 board was gated out of the intensity mapping. As expected, the occlusion leaves a shadow on the target in each data collection. The relative positions of the objects in the scene, along with their respective shadows, are easier to see with a 3D point cloud rendering, as shown in FIGS. 8a and b. These point cloud representation have been rotated by computer to emphasize the portions of the scene in which data is missing, i.e. the shadow left by the occlusion on the front surface of the box. Note that the box itself, (as well as the other stakes), creates its own shadow occluding some of the ground information.

As FIGS. 7c and 8a clearly indicate, data pertaining to the obscured portion of the surface of the box is not present in the laser radar data from the first perspective. However, that information is present in the data collection taken from perspective B. Likewise, data missing from aspect B is present in laser radar data A. Through 3-D data registration and combination, a full representation of the front surface of the box is possible. Following the mathematical procedure outlined in this specification, four fiducial point pairs are manually selected in each data set. These fiducials are indicated on FIG. 9 with circles. The data sets are registered and the fine adjust algorithm is applied. For this application, (combining multiple-aspect laser radar data), data voxels are accumulated after registration through companion voxel intensity comparison. The voxel with the maximum intensity is saved into a solution data set.

The results of this registration and combination, based on the technique, are given in FIGS. 10 and 11. The identical display parameters are used in FIG. 10 as in 7d, for comparison. Nearly all of the missing data, lying in the shadow in FIG. 7d, have been accumulated in the registration/combination processing and are displayed in the new data set. Similarly, a point cloud rendering of the combined data is shown in FIG. 11a, using display parameters consistent with FIG. 8b. For comparison purposes, the central occluding board (see FIG. 6) was physically removed and a laser radar data acquisition of the target area from position B was conducted. This data is shown in FIG. 11b. It is interesting to note that not only is the surface of the box reconstructed in FIG. 11a, the registered and combined image, but some data lying in the shadow behind the box has been filled in as well in the processed image.

Next, the effectiveness of incorporating additional fiducial pairs into the mapping for experimental cases was investigated where the accuracy of one or more fiducial pairs is questionable. The strategy was to replace one of the four fiducials in the above example with a haphazardly chosen fiducial point pair, and calculate a metric of registration effectiveness. As mentioned previously, selecting a metric for registration effectiveness is not trivial, and can be data dependant. For this experiment, it was thought that a reasonable metric might involve comparing the box face for registered/combined data (such as that shown in FIG. 11a) with the unobscured case, shown in FIG. 11b. Specifically, for this experiment the processed data and the unobscured data on a voxel-by-voxel basis, for a 12 bin (90 cm) range gate centered on the face of the box was logically NORed. This process essentially counts the discrepancies between the data sets, so a lower count represents a better registration.

A significant number of discrepancies will exist in the data due solely to the measurement uncertainty (primarily range uncertainty) inherent in the laser radar data. To baseline this effect, two experimental laser radar data acquisitions of identical scenes were taken and applied to the metric. This operation resulted in a discrepancy voxel count of 5,977'. This number is meaningless by itself, but is used as a baseline for the data to follow. Starting with three well-chosen and one haphazardly-chosen fiducial point pairs, fiducial pairs were added one at a time. The registration/combination algorithm was applied and metric calculated with each additional fiducial. The results of incorporating additional fiducials to a four fiducial pair mapping with known error are shown in FIG. 12. For example, FIG. 12 shows exemplary results of registration/combination using additional fiducials. The horizontal axis shows the number of fiducials used to calculate the mapping function. The vertical axis shows a factor corresponding to the efficacy of the registration. A value of 1 represents nearly perfect registration, while completely unregistered data will rank about 2.5. The baseline value of near 6,000 counts is used as the lowest value on the vertical scale. One can see from the graph that in almost every case, the registration was enhanced with the addition of a fiducial point pair. Finally, the fine adjust routine was applied to the eight-point mapping, automatically correcting the erroneously chosen fiducial point pair. The resulting discrepancy voxel count is shown on the bar graph as a dashed line at 10,344.

The invention has been described in an illustrative manner. It is to be understood that the terminology which has been used is intended to be in the nature of words of description rather than limitation. Many modifications and variations of the invention are possible in light of the above teachings. Therefore, within the scope of the appended claims, the invention may be practiced other than as specifically described.

* * * * *