Method and system for lossless dealiasing in time-of-flight (TOF) systems

[0001] Priority is claimed to co-pending U.S. provisional patent application Ser. No. 60/848,832 filed 2 Oct. 2006 entitled Method and System for Lossless Dealiasing.

[0002] The invention relates generally to depth imaging systems, and more particularly to time-of-flight (TOF) imaging system that acquire depth images by comparing phase shift between emitted optical energy and reflected detected optical energy.

[0003] Modern time-of-flight (TOF) systems can ascertain depth distances to a target object by emitting modulated optical energy of a known phase, and examining phase-shift in the optical signal reflected from the target object. Exemplary such phase-type TOF systems are described in several U.S. patents assigned to Canesta, Inc., assignee herein, including U.S. Pat. Nos. 6,515,740 “Methods for CMOS-Compatible Three-Dimensional Imaging Sensing Using Quantum Efficiency Modulation”, 6,906,793 entitled Methods and Devices for Charge Management for Three Dimensional Sensing, 6,678,039 “Method and System to Enhance Dynamic Range Conversion Useable With CMOS Three-Dimensional Imaging”, 6,587,186 “CMOS-Compatible Three-Dimensional Image Sensing Using Reduced Peak Energy”, 6,580,496 “Systems for CMOS-Compatible Three-Dimensional Image Sensing Using Quantum Efficiency Modulation”.

[0004] As the present invention is used with such prior art phase-type TOF systems, it is useful at this juncture to review their operation. FIG. 1A is based upon the above-referenced patents, e.g. the '186 patent, and depicts an exemplary phase-type TOF system.

[0005] In FIG. 1A, exemplary phase-shift TOF depth imaging system 100 may be fabricated on an IC 110 that includes a two-dimensional array 130 of pixel detectors 140, which pixel detectors may be single-ended or differential in operation. Preferably each of the pixel detectors 140 has dedicated circuitry 150 for processing detection charge output by the associated detector. IC 110 preferably also includes a microprocessor or microcontroller unit 160, memory 170 (which preferably includes random access memory or RAM and read-only memory or ROM), a high speed distributable clock 180, and various computing and input/output (I/O) circuitry 190. Among other functions, controller unit 160 may perform distance to object and object velocity calculations.

[0006] Under control of microprocessor 160, optical energy source 120 is periodically energized by an exciter 115, and emits modulated optical energy toward an object target 20. Emitter 120 preferably is at least one LED or laser diode(s) emitting low power (e.g., perhaps 1 W) periodic waveform, producing optical energy emissions of known frequency (perhaps a few dozen MHz) for a time period known as the shutter time (perhaps 10 ms). Typically emitter 120 operates in the near IR, with a wavelength of perhaps 800 nm. A lens 125 is commonly used to focus the emitted optical energy.

[0007] Some of the emitted optical energy (denoted S_out) will be reflected (denoted S_in) off the surface of target object 20. This reflected optical energy S_in will pass through an aperture field stop and lens, collectively 135, and will fall upon two-dimensional array 130 of pixel or photodetectors 140. When reflected optical energy S_in impinges upon photodetectors 140 in array 130, photons within the photodetectors are released, and converted into tiny amounts of detection current. For ease of explanation, incoming optical energy may be modeled as S_in=A·cos(ωt+θ), where A is a brightness or intensity coefficient, ω·t represents the periodic modulation frequency, and θ is phase shift. As distance Z changes, phase shift θ changes, and FIGS. 1B and 1C depict a phase shift θ between emitted and detected signals. The phase shift θ data can be processed to yield desired Z depth information. Within array 130, pixel detection current can be integrated to accumulate a meaningful detection signal, used to form a depth image. In this fashion, TOF system 100 can capture and provide Z depth information at each pixel detector 140 in sensor array 130 for each frame of acquired data.

[0008] Signal detection within phase-type TOF systems such as system 100 is described more fully later herein with respect to FIG. 2B, but in brief, pixel detection information is captured at least two discrete phases, preferably 0° and 90°, and is processed to yield Z data.

[0009] System 100 yields a phase shift A at distance Z due to time-of-flight given by:
θ=2·ω·Z/C=2·(2·π·f)·Z/C  (1)

[0010] where C is the speed of light, 300,000 Km/sec. From equation (1) above it follows that distance Z is given by:
Z=θ·C/2·ω=θ·C/(2·2·f·π)  (2)
And when θ=2·π, the aliasing interval range associated with modulation frequency f is given as:
Z_AIR=C/(2·f)  (3)

[0011] In practice, changes in Z produce change in phase shift θ but eventually the phase shift begins to repeat, e.g., θ=θ+2·π, etc. Thus, distance Z is known modulo 2·π·C/2·ω)=C/2·f, where f is the modulation frequency. Thus there can be inherent ambiguity between detected values of phase shift θ and distance Z, and multi-frequency methods are employed to disambiguate or dealias the phase shift data. Thus, if system 100 reports a distance Z₁, in reality the actual distance may be any of Z_N=Z₁+N·C/2f, where N is an integer. The nature of this ambiguity may be better understood with reference to FIGS. 1D and 1E.

[0012] FIG. 1D is a mapping of detected phase θ versus distance Z for system 100. Assume that system 100 determines a phase angle θ′ for target object 20, where this phase information was acquired with a modulation frequency f₁ of say 50 MHz. As shown by FIG. 1D, there are several distances, e.g., z₁, z₂, z₄, z₅, etc. that could be represented by this particular phase angle . . . but which is the correct distance? In FIG. 1D, Z_AIR1 represents the Z distance aliasing interval range associated with z data acquired at frequency f₁, and is the distance from z₁ to z₂, or z₂ to z₄, or z₄ to z₅, etc. These various z₁, z₂, z₄, z₅, distances are ambiguous and require disambiguation or dealiasing to identify the correct distance value.

[0013] It is desired to dealias the z data by increasing magnitude of the aliasing interval range Z_AIR1. One prior art approach does this by increasing the ratio C/2f, which is to say, by decreasing the modulation frequency f, see equation (3). FIG. 1D also shows, in bold line, phase data acquired for a lower modulation frequency f₂. In FIG. 1D, f₂ is perhaps 20 MHz, in that the slope dθ/dz for the f₂ waveform is less than about half the slope for the f₁ waveform, where the slope dθ/dz is proportional to modulation frequency f_m. FIG. 1E is a polar representation in which a vector, depicted as a line rotating counter-clockwise, rotates with velocity ω=dθ/dt=2πf. In prior art system 100, data is captured from pixel detectors at least two discrete phases, e.g., 0° and 180°.

[0014] Thus in FIG. 1D, when the lower modulation frequency f₂ is employed, the candidate distance values represented by phase θ′ are z₃, z₆, etc. As seen in FIG. 1D, the aliasing interval range Z_AIR2 has advantageously increased from a short range Z_AIR1 (associated with faster modulation frequency f₁) to a greater range Z_AIR2. The ratio of the aliasing interval range increase will be the ratio f₂/f₁. But acquiring phase data with lower modulation frequency f₂ yields a Z value with less precision or resolution than if acquired with higher modulation frequency f₁. This imprecision occurs because the slope of the curve for frequency f₂ is about half the slope for modulation frequency f₁. Thus errors in the measurement of phase acquired at f₂ translate to greater errors in Z than errors in phase acquired at f₁. For the same signal/noise ratio, errors in phases acquired at f1 and at f2 will be the same, but the corresponding uncertainty errors in Z use phase acquired at the lower f₂ modulation frequency will be about twice as large for the representation of FIG. 1D. Thus, all things being equal, lowering the modulation frequency undesirably results in lower resolution (greater uncertainty) in accurately determining Z.

[0015] Thus while increasing the aliasing range interval is desired, doing so by decreasing the modulation frequency f is not desirable. This modulation frequency decrease approach to dealiasing is wasteful since lower modulation frequency means lower pixel sensor 140 accuracy per watt of illumination power from emitter 120 (see FIG. 1A). For example, a reduction of modulation frequency by a factor of 2.5, say from f=50 MHz to f=20 MHz, will advantageously increase the aliasing interval by the same factor, e.g., from 3 m to 7.5 m, but the penalty is a substantial (2.5)·(2.5)=6.25× increase in operating power to achieve similar uncertainty performance, assuming effects of ambient sunlight can be ignored. By way of further example, if modulation frequencies of 50 MHz and 10 MHz were used, the dealiasing range would increase from 3 m to 30 m, but at a 25× increase in operating power for the same level of uncertainty. Thus, in practice dealiasing a TOF system simply by lowering the modulation frequency is accompanied by a very substantial performance penalty.

[0016] What is needed for a phase-type TOF system is a method of dealiasing in a relatively lossless fashion, e.g., disambiguation of Z data results, but without the large performance penalty associated with prior art dealiasing approaches. Preferably such relatively lossless dealiasing should enable the TOF system to operate most of the time near its maximum modulation frequency, to help maintain system performance.

[0017] The present invention provides a method and system for dealiasing in phase-type TOF systems.

[0018] The present invention dealiases data acquired from a phase-type TOF range finding system that has a maximum operable modulation frequency f_m and determines Z distance to a target object by comparing differences in phase between emitted and received optical energy. The present invention uses at least first and second modulation frequencies f₁ and f₂ to acquire phase data, where frequency f₁ is perhaps within 40% of frequency f_m and preferably even closer to f_m, and where f₂<f₁ and is within about 35% of the frequency of f₁, and preferably closer to f₁.

[0019] TOF phase data acquired using modulation frequency f₁ and using modulation frequency f₂ is processed to produce a dealiasing frequency f_D that is preferably proportional to a function of (f₁ and f₂) such that f_D<<f_m. The TOF phase data is also processed to produce an effective operating frequency f_E that is preferably greater in frequency than f₂, and in some embodiments may be intermediate f₁ and f₂.

[0020] In one aspect of the present invention, the TOF system performs as though phase data were acquired at a relatively low modulation frequency f_D. As such, the TOF system advantageously produces an effective aliasing interval range of Z_DAIR that is commensurate with TOF system operation at f_D. Further, Z_DAIR is larger than the aliasing range interval that would be obtained using either f₁ or f₂ alone and thus facilitates rapidly learning an approximate value for Z.

[0021] In a second aspect of the present invention, the TOF system performs with enhanced precision as though phase data were acquired at the relatively high modulation frequency f_E. As such, resolution certainty of distance Z range values is that of a system with relatively high modulation frequency f_E and can approach the performance of the TOF system operating at all times at the highest modulation frequency f_m. As used herein, a high level of resolution certainty means that jitter or uncertainty in the acquired Z data due to noise and other errors is low.

[0022] Phase data acquired by the TOF system can be processed and combined in various sequence combinations, using different methodologies to produce virtual frequencies f_E and f_D Regardless of how frequencies f_E and f_D, are mathematically produced, the resultant TOF system exhibits a good aliasing interval range commensurate with a low modulation frequency f_D, and exhibits a low level of resolution uncertainty commensurate with high modulation frequency f_E operation, while preserving frame rate. Dealiasing according to several embodiments of the present invention is lossless in the sense that there is a very small performance penalty in carrying out the dealiasing process, namely additional digital readouts from detectors in the TOF system.

[0023] Other features and advantages of the invention will appear from the following description in which the preferred embodiments have been set forth in detail, in conjunction with their accompanying drawings.

[0036] FIG. 2A depicts a phase-type TOF system 200 similar to that described with respect to FIGS. 1A-1C, except that additional components 210 and software 220 are included to implement the present invention. As such, software 220 and 210 may be considered as a dealiasing subsystem for TOF system 200. Output DATA' may include information provided as DATA by TOF system 100 in FIG. 1A. A TOF system such as system 100 (FIG. 1A) or 200 (FIG. 2A) normally is operable at some maximum modulation frequency f_m, perhaps 100 MHz. This is not to say that the system cannot be operated at a modulation frequency greater than f_m, but it is realized that at such higher modulation frequencies, system performance ultimately degrades. Thus, it is understood that f_m denotes the highest modulation frequency at which the system is normally operable, and not the highest modulation frequency at which it can be operated.

[0037] Before describing dealiasing operation of system 200, it is useful to briefly describe multiphase detection with reference to FIG. 2B, which shows two of the many photodetectors PD in array 130, namely photodetectors 140-1, and 140-N, as well as some of their associated electronics, namely 150-1, 150-N. This particular embodiment employs quantum efficiency (QE) modulated differential photodetectors or pixels 140, whose pixel detection information is captured at least two discrete phases 0° and 90°, and more preferably four discrete phases 0° and 180°, and 90° and 270°. These discrete phase operations of the pixel detectors are not to be confused with the phase shift data θ that is sought to be detected. These discrete phases represent shift between modulator 115 and optical energy emitter 120, whereas the phase shift data θ that is sought to be detected is shift between emitted optical energy S_out from emitter 120, and pixel detectors 140 in array 130 (see FIG. 2A).

[0038] The detection phase data that is captured at the discrete phases is denoted herein as captures C⁰ and C¹⁸⁰, C⁹⁰ and C²⁷⁰ and is processed to implement dealiasing according to the present invention. Acquisition using four phases is preferred so as to remove so-called fixed pattern offset. The C⁰ acquisition yields data but may include an error offset from zero, e.g., the value C⁰ may not be zero when there is no signal to be detected. By the same token, the C¹⁸⁰ acquisition should have the same, but inverted, data and will have the same fixed pattern offset. Advantageously by subtracting (C⁰−C¹⁸⁰) and preferably also subtracting (C⁹⁰−C²⁷⁰) phase and Z data information is preserved but the fixed pattern offset is canceled out. However the present invention may be used to dealias multiphase TOF data that is obtained from single-ended phase detectors, as well as from detection systems that do not employ QE modulation detection.

[0039] Phase angle θ can be computed from captures C⁰, C⁹⁰, C¹⁸⁰, C²⁷⁰, as follows:
θ=α tan 2(C⁹⁰−C²⁷⁰,C⁰−C¹⁸⁰)  (4)
where a tan 2(X,Y) is the trigonometric function corresponding to a tan (Y/X)

[0040] The configuration and operation of what is shown in FIG. 2B is similar to what is described with respect to the fixed phase delay embodiment of FIG. 10 in earlier-referenced U.S. Pat. Nos. 6,580,496 and 7,906,793. In FIG. 2B, detection-generated photocurrent from each QE-modulated differential pixel detector, e.g., 140-1, is differentially detected (DIF. DETECT) and differentially amplified (AMP) to yield signals B·cos(θ), B·sin(θ), where B is a brightness coefficient, A fixed discrete 0° or 90° phase shift delay (DELAY), and more preferably a fixed 0° or 180 or 90° or 270° phase shift is switchably insertable responsive to a phase select control signal (PHASE SELECT) that can be commanded by clock unit 180′. Phase data, e.g., C⁰ and C¹⁸⁰, C⁹⁰ and C²⁷⁰, is acquired or captured from the pixel detectors at these discrete phases. A more detailed description of such phase detection may be found in the above-referenced patents, but without limitation, the fixed discrete phase shifts may be inserted by clock unit 180′, whose signal is used to drive detector array 130, or may be introduced by modulator 115; see FIG. 2B.

[0041] As will now be described, the present invention combines preferably close together modulation frequencies f₁ and f₂, each typically less than the system maximum modulation frequency f_m) and the resultant phase data acquired from each, denoted θ₁ and θ₂, to provide two goals: (1) obtaining the equivalent of a high modulation frequency measurement from system 200 that yields a low level of Z resolution uncertainty, and (2) obtaining the equivalent of a low modulation frequency measurement from system 200 that provides a long aliasing interval Z range. In this fashion the approximate Z range is determined from the long aliasing interval, while more precise determination of the Z value is determined from the high modulation frequency measurement.

[0042] Referring back to FIG. 2A, software 220 when executed by processor 160 can alter normal operation of clock circuit 180′ by virtue of components 210. More specifically, in embodiments of the present invention, system 200 is thus caused to operate using at least first and second frequencies f₁, f₂, where f₁>f₂, f₁ is close to f_m, preferably within about 40% or less of f_m, and f2 is within about 35% of f₁ and preferably closer. Thus f₁ may be said to lie in a range of about 60% to 100% of the frequency of f_m such that if f_m were say 100 MHz, then f₁ would have a frequency of about 60 MHz to as high as 100 MHz. Similarly the range of f₂ is about 65% to about 99% the frequency such that if f₁ was say 90 MHz, then f₂ would have a frequency of about 58.5 MHz to about 89.1 MHz.

[0043] According to the present invention, the use of modulation frequencies f₁ and f₂ will cause system 200 to behave with respect to dealiasing interval as though phase data were collected while system 200 was being operated at a very slow modulation frequency f_D that preferably is proportional to (f₁−f₂). For example, assume that operation of system 200 at modulation frequency f, provides an aliasing interval range Z_AIR1 and that operation of system 200 at modulation frequency f₂ provides an aliasing interval range Z_AIR2. Embodiments of the present invention process data acquired at modulation frequency f₁ and at modulation frequency f₂ to provide an effective aliasing interval range Z_AIRD>Z_AIR2Z_AIR1.

[0044] Further, according to the present invention, the use of preferably close together modulation frequencies f₁ and f₂ advantageously produces good resolution precision of Z measurements as though system 200 were collecting phase data operating with a high effective modulation frequency close to f_m, perhaps (f₁+f₂)/2 or other combination of f₁ and f₂. It is noted that the frequencies (f₁−f₂), (f₁+f₂)/2 and other combinations of these modulation frequencies are really mathematical constructs or virtual frequencies, and system 200 does not physically operate at those virtual frequencies. Of course it is understood that more than two modulation frequencies f₁, f₂ may be used, which different modulation frequencies preferably are close in frequency to each other and to f_m. However using multiple modulation frequencies according to embodiments of the present invention also results in Z resolution certainty or precision that is better than would be achieved if the TOF system processed data acquired solely while operating at modulation frequency f₁ and disregarded data acquired at modulation frequency f₂, or operated at modulation frequency f₂ and disregarded data acquired at modulation frequency f₁.

[0045] As will be appreciated from what is shown in FIG. 3, in contrast to prior art dealiasing wherein f_m is decreased with loss of system efficiency, the present invention operates system 200 at high frequency, preferably close to f_m, which maintains high operating system efficiency. Further, because modulation frequencies f₁ and f₂ preferably are close to each other and to f_m, phase information captured by pixel detectors 140 at one modulation frequency may be shared with data frames captured at the other modulation frequency (or frequencies, if more than two modulation frequencies are employed).

[0046] FIG. 3 is a plot of phase versus distance Z, according to the present invention. A waveform is shown for phase data acquired using first modulation frequency f₁, which data is denoted θ₁. For purposes of explanation, assume f₁ is about 50 MHz. FIG. 3 also shows a plot of phase data acquired using a slightly lower second modulation frequency f₂, data for which is denoted θ₂. For purposes of explanation, assume f₂ is about 31 MHz, and according its slope is less than that of the f₁ waveform, and its period (or aliasing interval range) is longer. For these exemplary values of f₁ and f₂, a typical value of f_m for system 200 might be 70 MHz. The f₂ waveform is drawn with a heavier line than the f₁ waveform to promote clarity in the figure. As was the case with the plot described in FIG. 1D, at phase multiples of 2π the data folds-over or wraps around. The wrap-around somewhat complicates the calculations of θ_E and θ_DS as noted later herein.

[0047] As noted, one aspect or goal of the present invention is provide a large aliasing interval range Z_AIR by making it appear as though system 200 acquire phased phase data using a relatively low modulation frequency. The following description will demonstrate that defining a difference frequency f_D that preferably is a function of f₁ and f₂ and defining a phase difference θ_D=(θ₁−θ₂) will achieve the goal of providing a low modulation frequency suitable for a large aliasing interval range. Without limitation, an exemplary function for f_p may be a difference function (a·f₁−b·f₂), where a and b may be weighting factors.

[0048] Mathematically, phase delay θ may be expressed in terms of absolute target distance Z as:

[0049] $\begin{array}{cc}\theta =2\pi \left(\frac{2\mathrm{fZ}}{C}+N\right)& \left(5\right)\end{array}$

[0050] Differentiating equation (5) yields:

[0051] $\begin{array}{cc}\mathrm{\delta \theta }=\frac{4\pi Z\delta f}{C}& \left(6\right)\end{array}$

[0052] Therefore the absolute (dealiased) distance Z_ABS is given by:

[0053] $\begin{array}{cc}{Z}_{\mathrm{ABS}}=Z=\frac{C}{4\pi }\frac{\mathrm{\delta \theta }}{\delta f}& \left(7\right)\end{array}$

[0054] In this instance, the differential in equation (7) can be replaced with small differences without loss of precision, to yield:

[0055] $\begin{array}{cc}Z=\frac{C}{4\pi }\frac{\mathrm{\Delta \theta }}{\Delta f}& \left(8\right)\end{array}$

[0056] Equation (8) shows that Z can be determined from Δθ, which is θ_D or (or θ₁−θ₂) and from Δf. Note that this is the same equation one would use to determine Z from a modulation frequency Δf=f_D=f₁−f₂ and phase Δθ=θ_D=θ₁−θ₂. Thus with knowledge of f₁, f₂, θ₁, θ₂, one can compute a measurement for distance Z that is akin to a calculation for Z where the actual modulation frequency was physically (f₁−f₂). This aspect of the present invention is thus the combination of modulation frequencies f₁ and f₂ that will yield a large aliasing interval range, as though system 200 were acquiring phase data while operating at a very low modulation frequency. Of course many other combinations of f₁ and f₂ could be used to achieve this goal, and one could employ more than two modulation frequencies, e.g., f₁, f₂, f₃, . . . . Preferably the highest of these modulation frequencies f₁ would be close to the system highest maximum modulation frequency f_m and at least within 40% of f_m. Preferably at least the closest together of the various modulation frequencies would be within about ±35% of each other, and preferably closer together than that.

[0057] Preferably maximum modulation frequency f_m is close to, the optimal operating point for TOF system 200. This means that f_m is near a maximum of operating efficiency, and therefore curve of system operating efficiency is relatively flat in the vicinity of f_m. Generally this maximum is quite flat and therefore operating frequencies f₁ and f₂ will also be close to the optimal operating conditions for system 200.

[0058] Design consideration in implementing a high effective (e.g., virtual) modulation frequency commensurate with a desired low level of Z resolution uncertainty will now be presented. In this aspect of the present invention, phase data obtained from system 200 operating at modulation frequencies f₁ and f₂ are combined to yield an effective (virtual) frequency measurement at frequency f_E. Rather than use data obtained from system 200 operating at modulation frequency f₁ alone, or at modulation frequency f₂ alone, the present invention advantageously combines data acquired at both modulation frequencies to further lower uncertainty in the Z data. (It is understood that if additional modulation frequencies are used, e.g., f₃, f₄, . . . phase data acquired while system 200 was operating at these modulation frequencies would also preferably be used).

[0059] Combining phase data from all modulation frequencies used (e.g., f₁ and f₂ in the example at hand) averages noise in the phase data measurements, and advantageously results in lower noise than would be obtained using data acquired solely from f₁ or f₂ alone. Furthermore, because modulation frequencies f₁ and f₂ are preferably relatively close to maximum modulation frequency f_m, each measurement is obtained with relatively high precision and lowered noise. In general for close together frequencies f₁ and f₂, system 200 performance will be somewhat similar. Advantageously, uncertainty obtained after combining data from frequency f₁ and f₂ will be about 0.7 times the uncertainty when phase data acquired using modulation frequency f₁ or modulation frequency f₂ was used alone.

[0060] Thus this second aspect of the present invention relates to combining phase data acquired by system 200 operating at different (but preferably close to each other) modulation frequencies so as to emulate system operation at a high modulation frequency that yields a low Z resolution uncertainty. While some specific methods of combining data will now be described, it is understood that many other combinations could also be used.

[0061] With respect to this second aspect or goal, one approach is to combine that raw data readings from pixel detectors 140 in array 130 (see FIGS. 2A and 2B) from captures (C′_o, C₁⁹⁰, C₁¹⁸⁰, C₁²⁷⁰) obtained at modulation frequency f₁ and add this raw data to data readings (C₂⁰, C₂⁰, C₂¹⁸⁰, C₂¹⁸⁰) obtained at a frequency f₂ to produce (C₁⁰+C₂⁰, C₁⁹⁰+C₂⁰, C₁¹⁸⁰+C₂¹⁸⁰, C₁²⁷⁰+C₂¹⁸⁰). This exemplary combination is equivalent to adding the respective phase vectors together in a polar representation and obtaining the phase angle for the sum vector.

[0062] Consider now a polar representation of the phase vector for a target object 20 at a given distance Z, acquired by system 200 operating at modulation frequency f₁ or at modulation frequency f₂. (FIG. 1E may be regarded as a polar representation for a single phase vector.) The phase vectors may be represented in polar form as V₁=(ρ, θ₁) and V₂=(ρ, θ₂) for captures at modulation frequencies f₁, f₂ respectively. For ease of explanation it will be assumed that the small change in modulation frequency does not affect modulation contrast, and hence both V₁ and V₂ have the same magnitude ρ. (The term “modulation contrast” denotes a measure of collection efficiency within pixel detectors 140, e.g., how well incoming photon energy from signal S_in is captured and converted into a detection signal. A high modulation contrast is desirable.)

[0063] Adding phase vectors V₁=(ρ, θ₁) and V₂=(ρ, θ₂) yields:
V₁+V₂=(2ρ·sin((θ₁−θ₂)/2),(θ₁+θ₂)/2)  (8)

[0064] Thus if (θ₁−θ₂) is not a multiple of it, the phase of V₁+V₂ that would make the vector null will be the same phase (θ₁+θ₂)/2 as the phase vector for target object 20 measured at modulation frequency (f₁+f₂)/2. In practice, however, modulation contrast varies with frequency, which complicates implementation of this addition method. A further complication is variation in modulation contrast ratio with temperature, which makes the mathematics somewhat unwieldy.

[0065] In an alternate embodiment, actual phase angles from the two measurements θ₁ and θ₂ at modulation frequencies f₁ and f₂ are themselves combined to produce an effective phase angle θ_E. Typically the average (θ₁+θ₂)/2 of the phase angles is used, although other combinations of the actual phase angles are possible.

[0066] As noted above, values for θ_E and θ_D may be determined in a variety of ways, within the scope and spirit of the present invention. Regardless of the specific method used to obtain these values, preferably θ_E and θ_D are both used to determine distance Z, as shown by FIG. 3. FIG. 3 depicts phase angles θ₁, θ₂, θ_D=θ₁−θ₂ and θ_E=(θ₁+θ₂)/2 associated, respectively, with frequencies f₁, f₂, f_D=(f₁−f₂), and f_E=(f₁+f₂)/2. It is noted that θ₁ and θ₂ are normalized so as to be 0 for Z=0. FIG. 3 also depicts θ_DS, which may be derived from θ_D as θ_DS=θ_D·f_E/f_D. Angle θ_DS corresponds to the same frequency as θ_E and thus has the same slope as θ_E as shown in FIG. 3. However because angle θ_DS is mathematically derived from θ_D, it advantageously has the same large aliasing interval as θ_D, denoted Z_AIR.

[0067] Note that both θ_D and θ_E are adjusted to take account the foldover or wrap around repetitions of θ₁ and θ₂. For example, before the end of the first aliasing interval of θ_E, θ₁ wraps around. Simply computing θ_E=(θ₁+θ₂)/2 would not suffice because θ_E would decrease by π when θ₁ wraps around. However when θ₁<θ₂, it is known that θ1 must have wrapped around, and hence π must be added to θ_E. Such trigonometric corrections are well known in the art and are assumed to have been performed on the data.

[0068] Having thus appropriately trigonometrically corrected θ_E and θ_D, since θ_DS and θ_E have the same slope and differ only by their aliasing interval, in the absence of noise it follows that θ_DS=θ_E+K2π. K is an integer that represents the index of the aliasing interval of θ_E. In the presence of noise, θ_DS≅θ_E+K2π. Finding the correct aliasing interval involves selecting K so as to minimize the absolute value of (θ_DS−θ_E+K2π). θ_E+K2π then represents an accurate measure of Z, but with unknown aliasing interval. The expression θ_E+K2π represents the dealiased value of θ_E. It is of course assumed that the target object is at a distance less than the aliasing interval for f_D. It is understood that other equivalent mathematical approaches to determine suitable values for K may also be employed.

[0069] It is important to select an appropriate difference frequency f_D. If f_D is too big, the corresponding dealiasing interval for f_D may be too small. Conversely, if f_D is too small, then resolution certainty in Z measurements at f_D can become too large. Thus, difference frequency f_D should be as small as possible, subject to the noise constraints affecting resolution uncertainty. The aliasing interval index K should be determined with high certainty to ensure the proper dealiasing interval is selected.

[0070] If it assumed that f_D<<f_E, then error(θ_DS)>>error(θ_E) and one can generally neglect error from θ_E. Let K_s=((θ_DS−θ_E)/2π. Then K is the closest integer to K_s. To find the correct K, the error on K_s must be <<0.5, which means the error on θ_DS/2πT=θ_D·f_E/f_D/2π must also be substantially less than 0.5.

[0071] The following section will now describe exemplary approaches to identifying good capture sequences for modulation frequencies f₁ and f₂. Many different capture sequences may be used to generate dealiased frames. A frame represents a complete Z image acquired by sensor array 130, which is to say that each pixel detector 140 in the array is associated with a corresponding Z value from target object 20. Assume first that pixel detectors 140 in system 200 can only achieve one capture at a time. Under this assumption, some exemplary sequences are as follows.

[0072] A first case is depicted in FIG. 4A, where it is assumed that the same pixel detector is sequenced though eight different captures to acquire the desired phase shift data θ₁, θ₂. Thus as shown in FIG. 4A, with system 200 operating at modulation frequency f₁ a sequence of captures C₁⁰, C₁⁹⁰, C₁¹⁸⁰, C₁²⁷⁰ is acquired over time. Next, with system 200 operating at modulation frequency f₂, a sequence of captures C₂⁰, C₂⁹⁰, C₂¹⁸⁰, C₂²⁷⁰ is acquired, after which the system is returned to operating at modulation frequency f₁ and a sequence of captures C₁⁰, C₁⁹⁰, C₁¹⁸⁰, C₁²⁷⁰ is made, and so on. Thus in FIG. 4A (as well as in FIGS. 4B-4D), the phase information displayed beneath the relevant sequence of captures is the phase data acquired by system 200 operating at the associated modulation frequency. Thus it is understood that subscript 1 denotes captures associated with modulation frequency f₁ and subscript 2 denotes captures associated with modulation frequency f₂. The frame information displayed beneath the phase information shows how frames are preferably constructed, according to the sequence shown. Once θ₁ and θ₂ have been determined, θ_E can be calculated from (θ₁+θ₂)/2.

[0073] FIG. 4B depicts another sequencing example, in which four adjacent pixel detectors, shown as a block, in the pixel array are used to acquire all four phases in a single capture.

[0074] Whereas the eight capture sequence of FIG. 4A is susceptible to motion blur due to the length of time to acquire all eight captures, the sequence shown in FIG. 4B should inherently exhibit lower motion blur. But in FIG. 4B, the C⁰−C¹⁸⁰ offset cancellation is done with data from different pixels and performance can suffer in that offsets are not fully cancelled. As before, θ_E is calculated from (θ₁+θ₂)/2.

[0075] FIG. 4C depicts yet another sequencing example, one in which captures for each phase are cancelled with respect to C⁰−C¹⁸⁰ offset with the same pixel detector, shown as a block. In this configuration, performance is quite good, and motion blur is acceptable. As before, θ_E is calculated from (θ₁+θ₂)/2.

[0076] FIG. 4D depicts an alternative embodiment in which phase θ₁ and phase θ₂ are not C⁰−C¹⁸⁰ offset corrected. As a result, data quality is somewhat poor, but advantageously θ_E is computed directly from the captures C₁⁰−C₂¹⁸⁰ and C₁⁹⁰−C₂²⁷⁰. The method is as described previously, where C₂¹⁸⁰ is substituted for C₂⁰ and where C₂²⁷⁰ is substituted for C₂⁹⁰. Advantageously, data quality for θ_E is good but θ_D=θ₁−θ₂ is of poor quality and as a result the dealiasing interval decision quality suffers.

[0077] An alternative embodiment, not depicted explicitly, is similar to that of FIG. 4D, but wherein θ_E is calculated from (θ₁+θ₂)/2. As noted earlier, acquired phase angles preferably are normalized to start at zero for Z=0. In the alternative embodiment at hand, if pre-normalization differences between θ₁ and θ₂ are small, then offset induced errors in θ₁ and θ₂ will be opposite of each other and will advantageously partially cancel out in θ_E=(θ₁+θ₂)/2. If O is the assumed small offset, then from equation (4), θ₁=atan2(C₁⁰+O, C₁⁹⁰+O), and θ₂=atan2(−C₂¹⁸⁰+O, −C₂²⁷⁰+O). If modulation contrast is similar for both modulation frequencies f₁ and f₂, and θ₁≈θ₂, then C₁⁰≦C₂¹⁸⁰ and C₁⁹⁰≈C₂²⁷⁰. Thus, θ₁≈atan2(C₁⁰+O, C₁⁹⁰+O) and θ₂≈atan2(C₁⁰−O, C₁⁹⁰−O)+π. As such, phases θ₁ and θ₂ move in opposite directions in roughly equal amounts with respect to offset O. Thus, advantageously the effect of offset O will be partially cancelled in the sum θ_E=(θ₁+θ₂)/2. In some advanced TOF systems, the time of flight pixels can acquire more than one phase or modulation frequency at each capture. For example such multiphase-capture pixels effectively function as through they simultaneously capture C₁⁰ and C₁⁹⁰. Such effective functionality may be implanted, for example, by rapidly time-slicing or time-multiplexing between different modulation frequencies and/or phases, or by using multiple detectors operating at different modulation frequencies and/or phases. Using such pixels, the time to assemble sequences for a dealiased frame is considerably shortened. The basic methodology described earlier herein remains the same.

[0078] Thus far, the various described dealiasing embodiments have been lossless, e.g., dealiasing was carried out with a very small TOF system performance penalty. A lossy so-called least common multiple (LCM) dealiasing embodiment will now be described reference to FIGS. 5A and 5B. In FIGS. 5A and 5B, two distance measurements are made using two modulation frequencies f₁ and f₂, for which frequencies Z_AIR1 and Z_AIR2 represent the associated maximum unambiguous aliasing interval ranges. In FIG. 5A, f₁ is 25 MHz, and Z_AIR1 is 3 M, while in FIG. 5B, f₂ is a lower 18.75 MHz, and Z_AIR2 is a longer 4 M. Assume a target object is present 7 m from the TOF sensor array. If a single modulation frequency f₁=of 25 MHz is used to acquire data, one can infer that the Z distance of the object is either 1 m, 4 m, 7 m, or 12 m as suggested by the cross-hatched rectangular regions in FIG. 5A. On the other hand, if a single modulation frequency f₂=18.75 MHz is used, one can infer the target object is at 3 m, 7 m, or 11 m, as suggested by the cross-hatched rectangular regions in FIG. 5B.

[0079] According to the LCM embodiment, the above-two results are combined, leading to the conclusion that the target object must be at a distance of 7 m. The target object is drawn in FIGS. 5A and 5B with heavy bold lines to distinguish from phantom locations, which are drawn in phantom. The true location of the target object could still be confused with another location at 19 M, but compared to the one-modulation frequency case, the use of two modulation frequencies has extended the unambiguous interval range substantially. According to the present invention, if two modulation frequencies are used, the effective unambiguous interval range is increased according to the LCM least common multiple of Z_AIR1 and Z_AIR2. One strategy in selecting modulation frequencies is to maximize the LCM of the corresponding unambiguous interval ranges by choosing two frequencies close to each other.

[0080] Another embodiment of the present invention provides a lossy so-called branch and bound hierarchical approach to dealiasing. According to this embodiment, a relatively very low modulation frequency may be used to determine whether a target object is within a first or a second Z range or bin, e.g., perhaps between a 0 m to 50 m range, or perhaps between a 50 m to 100 m range. If TOF system 200 determines that the target object is within say 0 m to 50 m, then software 200 can cause clock 180′ to double the modulation frequency to determine whether the target object lies within a 0 m to 25 m sub-range (or narrower bin), or within a 25 m to 50 m sub-range (or narrow bin). A similar analysis and modulation frequency change is performed should the object initially have been found to lie with a 50 m to 100 m range. This method of estimating distance range for the target object and then changing modulation frequency to better ascertain the distance range is repeated preferably until the range is determined with a desired range granularity. Again this method is preferably carried out automatically under command of software 220. Of course while this example assumed the various alternate ranges or bins were 2× apart, other ratios may be used.

[0081] During a branch and bound hierarchical dealiasing process it is not necessary to obtain full certainty (e.g., best granularity) at each modulation frequency. For lower modulation frequencies it can suffice to obtain lower resolution. For example to decide between the 0 m to 50 m, and 50 m to 100 m ranges or bins, a fairly coarse level of resolution is sufficient. For example, if a highest quality depth image acquired by system 200 uses say ten bits, a fairly coarse level of resolution may only require three to four bits of resolution. Advantageously therefore captures at low modulation frequency may have short shutter times to reflect these relaxed requirements. In general for a hierarchical sweep of modulation frequencies, e.g., 1 MHz, 10 MHz, 100 MHz, the shutter will be short for all but the highest swept frequency, here 100 MHz. So doing advantageously reduces the amount of integration time the sensor array is operated at low modulation frequencies, which further boosts effective performance.

[0082] Understandably, using branch and bound hierarchical dealiasing, it may be desirable to minimize the number of bins for each relatively low modulation frequency. In turn, the hierarchical modulation frequency sweep process tends to maximize the effective system TOF modulation frequency by keeping the resolution requirement at each lower modulation frequency as small as feasible. If desired, a branch and bound embodiment may be combined with lossless dealiasing embodiment at one or more steps in the hierarchical process.

[0083] The above description was directed to lossy hierarchical type dealiasing embodiments. A lossless hierarchical dealiasing embodiment will now be described. Earlier herein it was shown that θ_D·f_E/f_D/2π should be substantially less than 0.5. In an embodiment where a very long aliasing interval is desired, use of relatively high modulation frequencies f₁ and f₂ yield an f_E/f_p ratio that becomes very large, making it difficult to keep θ_D*f_E/f_D/2π<<0.5. For such applications, a lossless dealiasing method may also be applied hierarchically. In this fashion, at each step in the hierarchical process, as governed by noise consideration and as controlled by software 220, the ratio f_E/f_D is kept relatively small.

[0084] Consider the following example, in which modulation frequencies f_a=100 MHz, f_b=110 MHz, f_c=111 MHz are used, and wherein there are defined difference frequencies D₁=f_b−f_a=10 MHz, D₂=f_c−f_a=11 MHz., and hierarchically applied difference frequency E₁=D₂−D₁=1 MHz.

[0085] In a so-called top-down sweep, initially frequency E₁ is used to dealias acquired phase data for D₁ and for D₂. In this initial step, f₁=D₁, f₂=D₂ and f_p=E₁. The ratio f_E/f_D advantageously is not too large, here approximately 10. Thus, in this example, dealiased Z values may be found for an effective frequency θ_E=(θ₁+θ₂)/2.

[0086] Going down one step in the hierarchical process, the above found and dealiased value of θ_E will now be used in the current step as dealiasing phase θ_D for effective frequency 0.33(f_a+f_b+f_c) and effective phase θ_E=0.33(θ_a+θ_b+θ_c). Advantageously, it is noted that the ratio f_E/f_D remains relatively small, here approximately 10. In this fashion, as the bottom of the hierarchy, θ_E is 0.33(100 MHz+110+111 MHz), i.e., close to 100 MHz, yet is has been dealiased as though its frequency were E₁=1 MHz, with Z_AIR of about 150 M.

[0087] In addition, it is noted that TOF system 200 is not necessarily physically acquiring phase data with a modulation frequency f_c=111 MHz. Frequency f_c may be computed mathematically, for example as f_c=(110 MHz+100 MHz/100), e.g., f_b+(f_a)/100. Thus only frequencies f_a and f_b need to be physically measured by the TOF system.

[0088] In summary, dealiasing according to several embodiments of the present invention is lossless, and advantageously provides a relatively large aliasing interval range commensurate with a low modulation frequency, while also providing high precision certainty with respect to a given Z value, commensurate with a modulation frequency close to the highest modulation frequency f_m. According to the present invention, dealiasing may be carried out relatively losslessly, or in other embodiments, with loss.

[0089] Modifications and variations may be made to the disclosed embodiments without departing from the subject and spirit of the invention as defined by the following claims.