Computer graphics processing and selective visual display system – Display peripheral interface input device
Reexamination Certificate
2001-11-19
2004-02-10
Lao, Lun-Yi (Department: 2673)
Computer graphics processing and selective visual display system
Display peripheral interface input device
C345S173000, C345S168000, C345S172000, C382S106000
Reexamination Certificate
active
06690354
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally systems that use an array of sensors to detect distances in at least two dimensions, and more specifically to enhancing performance of such system by reducing computational overhead, overcoming geometric error, elliptical error, and lens distortion.
BACKGROUND OF THE INVENTION
FIG. 1
depicts a generic three-dimensional sensing system
10
that includes a pulsed light source
20
some of whose emissions
30
strike a target object
40
and are reflected back as optical energy
50
. Some of the reflected energy
50
passes through a lens
60
and is collected by at least some three-dimensional sensors
70
i,j in a sensor array
80
, where i,j represent indices. An electronics system
90
coordinates operation of system
10
and carries out signal processing of sensor-received data. An exemplary such system is described in U.S. patent application Ser. No. 09/401,059 “CMOS-Compatible Three-dimensional Image Sensor IC”, now U.S. Pat. No. 6,323,942(2001).
Within array
80
, each imaging sensor
70
i,j
(and its associated electronics) calculates total time of flight (TOF) from when a light pulse left source
20
to when energy reflected from target object
40
is detected by sensor
80
. Surface regions of target
40
are typically identified in (x,y,z) coordinates. Different (x,y,z) regions of target object
40
will be imaged by different ones of the imaging sensors
70
ij
in array
80
. Data representing TOF and/or brightness of the returned optical energy is collected by each senor element (i,j) in the array, and may be referred to as the data at sensor pixel detector (i,j). Typically, for each pulse of optical energy emitted by source
20
, a frame of three-dimensional image data may be collected by system
10
.
FIG. 2
depicts one potential application for system
10
, in which system
10
attempts to detect the spatial location of interaction between a virtual input device
100
(here shown as a virtual keyboard) and a user-controlled object
110
(here shown as a user's hand). Virtual input device
100
may be simply an image of an input device, such as a keyboard. As the user
110
“types” on the image, system
10
attempts to discern in the (x,y,z) coordinate system which keys on an actual keyboard would have been typed upon by the user.
Typically an image representing the surface of virtual input device
110
will have been stored in (x,y,z) coordinates in memory within system
10
. For example in
FIG. 2
, the user's left forefinger is shown contacting (or typing upon) the region of the virtual input device where the “ALT” character would be located on an actual keyboard. In essence, regions of contact or at least near contact between user-controlled object
110
and the virtual input device
110
are determined using TOF information. Pixel detector information from sensor array
80
would then be translated to (x,y,z) coordinates, typically on a per-frame of data acquired basis. After then determining what region of device
110
was contacted, the resultant data (e.g., here the key scancode for the ALT key) would be output, if desired, as DATA to an accessory device, perhaps a small computer. An example of such an application as shown in
FIG. 2
may be found in co-pending U.S. patent application Ser. No. 09/502,499 entitled “CMOS-Compatible Three-dimensional Image Sensor IC”, assigned to assignee herein.
Unfortunately several error mechanisms are at work in the simplified system of FIG.
2
. For example, geometric error or distortion is present in the raw data acquired by the sensor array. Referring to
FIGS. 3A and 3B
, geometric or distortion error arises from use of distance measurement D at pixel (i,j) as the z-value at pixel (i,j). It is understood that the z-value is distance along the z-axis from the target object
40
or
110
to the optical plane of the imaging sensor array
80
. It is known in the art to try to compensate for geometric error, by transforming the raw data into (x,y,z) coordinates using a coordinate transformation that is carried out on a per-pixel basis. Such coordinate transformation is a transformation from one coordinate system into another coordinate system.
FIG. 3C
depicts another and potentially more serious geometric error, namely so-called elliptical error. Elliptical error results from approximating imaging regions of interest as lying on planes orthogonal to an optical axis of system
10
, rather than lying on surfaces of ellipsoids whose focal points are optical emitter
20
and optical sensor
80
. Elliptical error is depicted in
FIG. 3C
with reference to points A and point B, which are equal light travel distances from optical energy emitter
20
shown in FIG.
1
. Referring to
FIG. 3C
, optical source
20
and sensor array
80
are spaced-apart vertically (in the figure) a distance
2
c
. Further, points A and point B each have the same light traveling distance
2
d
, e.g., r
1
+r
2
=
2
d
, and r′
1
+r′
2
=
2
d
. In mapping distance values to planes in a three-dimensional grid, points A and B, which have the same distance value from the optical plane, may in fact map to different planes on the three-dimensional grid. Thus while points A and B both lie on the same elliptical curve Ec, point A lies on plane P
a
while point B lies on a parallel plane P
b
, a bit farther from the optical plane than is plane P
a
. Thus to properly determine (x,y,z) coordinate information for point A and point B requires a further correction.
Unfortunately, computational overhead or cost associated with various coordinate transformations and other corrections may be high. For example assume that array
80
includes 100 rows and 100 columns of pixel detectors
70
i,j
(e.g., 1≦i≦100, 1≦j≦100). Thus, a single frame of three-dimension data acquired for each pulse of energy from emitter
20
includes information from 10,000 pixels. In this example, correcting for geometric or distortion error requires performing 10,000 coordinate transformations for each frame of data acquired. If the frame rate is 30 frames per second, the computational requirement just for the coordinate transformations will be 300,000 coordinate transformations performed within each second.
In addition to the sheer number of transformations required to be calculated per second, coordinate transformation typically involves use of floating-point calculation and/or memory to store transformation tables. Thus, the necessity to perform a substantial number of coordinate transformations can be computationally intensive and can require substantial memory resources. However in applications where system
10
is embedded system, the available computational power and available memory may be quite low. But even if the overhead associated with increased computational power and memory is provided to carry-out coordinate transformation, correction to geometric error does not correct for distortion created by lens
60
.
Lens distortion is present on almost every optical lens, and is more evident on less expensive lens. Indeed, if system
10
is mass produced and lens
20
is not a high quality lens, the problem associated with lens distortion cannot generally be ignored.
FIG. 4A
depicts a cross-hatch image comprising parallel and vertical lines.
FIG. 4B
depicts the image of
FIG. 4A
as viewed through a lens having substantial barrel distortion, while
FIG. 4C
depicts the image of
FIG. 4A
as viewed through a lens having substantial pincushion distortion. Barrel distortion and pin cushion distortion are two common types of lens distortion. An additional type of lens distortion is fuzziness, e.g., imaged parallel lines may not necessary be distorted to bow out (
FIG. 4B
) or bow in (FIG.
4
C), yet the resultant image is not optically sharp but somewhat fuzzy.
It is known in the art to correct non-linear lens distortion such as barrel and pincushion lens distortion using non-linear numerical transformation methods that are carried out on a per-pixel basis. While such transformat
Canesta, Inc.
Dorsey & Whitney LLP
Lao Lun-Yi
LandOfFree
Method for enhancing performance in a system utilizing an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for enhancing performance in a system utilizing an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for enhancing performance in a system utilizing an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3331752