Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
2001-07-30
2004-11-23
Boudreau, Leo (Department: 2621)
Image analysis
Applications
Motion or velocity measuring
C345S156000
Reexamination Certificate
active
06823077
ABSTRACT:
BACKGROUND OF THE INVENTION
Modern optical navigation upon arbitrary surfaces produces motion signals indicative of relative movement along the directions of coordinate axes, and is becoming increasingly prevalent. It is used, for instance, in optical computer mice and fingertip tracking devices to replace conventional mice and trackballs for the position control of screen pointers in windowed user interfaces for computer systems. It has many advantages, among which are the lack of moving parts that accumulate dirt and suffer the mechanical wear and tear of use. Another advantage for newer types of optical mice is that they do not need a mouse pad, since they usually employ sophisticated techniques that are generally capable of navigating upon arbitrary surfaces, so long as those surfaces are not optically featureless.
Modern optical navigation operates by tracking the relative displacement of images. In a preferred embodiment, a two dimensional view of a portion of the surface is focused upon an array of photo detectors, whose outputs are digitized, and then perhaps spatially filtered to remove grain or other objectionable artifacts from the image. The resulting image is then stored as a reference image in a corresponding array of memory, which array may be referred to as a “reference frame.” A brief time later a sample image is also digitized, and perhaps also spatially filtered before being stored as a “sample frame.” If there has been no motion, then the sample image (i.e., the sample frame) and the reference image (reference frame) are identical (or very nearly so). What is meant, of course, is that the stored arrays appear to match up (i.e., they already “correlate”, without further manipulation). If, on the other hand, there has been some motion, then the sample image will appear to have shifted within its borders, and the digitized arrays will no longer match (that is, if their borders are also lined up). The matching process is termed “correlation” and may be performed in various ways, a conventional one of which is described in the incorporated Patents. Considered in isolation, correlation answers the narrow question “Are these two images aligned?” When the answer is “NO,” it could be because of intervening motion in any direction, in which case some additional mechanism is needed to find the direction and amount of displacement that will produce correlation results of “YES” or “ALMOST.” What is done is to perform correlations between one of the stored images (say, the sample image) and a collection of nine shifted trial versions of the other (reference) image. These nine shifted trial versions are: no shift; one over; one over and one up; one up; one over the other direction; etc., for eight actual shifts and one “null” shift. We would then expect that one of these nine correlations would be better than all the others, and its direction and amount of shift is taken as an indication of the intervening motion. (Either frame could, in principle, be the one that is trial shifted.)
On the other hand, an answer of “NO” could also occur because the two images are really quite different, either because the mouse velocity is really high, or because some other pernicious mischief is afoot. Whatever the reason, if this is the case then no trial shift will produce correlation, and we can't navigate using those images. The best we can do in such a circumstance is recognize it and respond in an appropriate and graceful manner.
Now, a navigation mechanism must avoid losing track of its changes in position, and if the above strategy were, by itself, the sole method of navigation, it would place quite a burden on the system through the imposition of a continuous high sample rate, even when there is no motion (which for a mouse is most of the time). Such high duty cycles can have consequences that increase the cost of a manufactured navigation mechanism, and for its power consumption during operation. The issue of power consumption bears particularly on the ability to provide a practical optical mouse that is “cordless” or “wireless,” since it is apt to be battery powered.
For those and other reasons, the navigation mechanism maintains velocity (speed and direction) information. When a new sample frame is to be correlated with the reference frame a predicted shift can be used as the starting point for the nine trial shifts. The predicted shift is obtained from the velocity in conjunction with the elapsed time between samples, and may be many pixels in length. With this arrangement the correlation results contribute to an updated velocity and either ratify or modify the motion just predicted. Prediction is used to cumulatively “pre-shift” the reference frame, until such time as the new sample frame fails to overlap a significant portion of the shifted reference frame. At that time a new reference frame is taken. Among the benefits of such prediction is an increased allowable mouse velocity and a lowered power consumption and frame rate during period of small or zero velocity.
Now, it is generally the case that the reference frame/sample frame misalignment is produced by an amount of intervening motion that does not correspond exactly to the pixel size of the optical navigation mechanism. It is in these (typical) cases that the correlation process indicates the “ALMOST” answer mentioned above. In fact, an interpolation mechanism allows the detection of motion with a resolution that is substantially better than the mere pixel size. Here is a simplified explanation of why this is possible.
Refer to
FIG. 1
, wherein is shown a depiction
1
of an array
2
of photo-sensitive sensors (e.g., photo-transistors). The photo sensors are arranged into a square array of seven rows (t through z) and seven columns (a through g). We have shown seven rows and seven columns as a simplification to make the drawing more manageable; a typical actual array would be sixteen by sixteen, or perhaps twenty-four by twenty-four. These forty-nine photo sensors receive an image reflected from the work surface being navigated upon (not shown), typically through the action of an illumination and lens system (also not shown). In the depiction
1
of
FIG. 1
a non-illuminated photo sensor, such as
5
, is denoted by an empty square, as indicated by the legend
3
. A filled in box, such as in legend
4
, denotes a photo sensor that is illuminated (e.g., the photo sensor
6
at position (d, w)).
In
FIG. 1
the photo sensors of array
2
are depicted as disjoint. This is in fact the case, although the active sensor area still accounts for about ninety percent of the foot print of the array. Some space between the sensors is needed to produce electrical isolation, and some is needed for inter-connecting conductors and buffer amplifiers, etc. In the explanations that follow, we shall ignore the spatial gaps between the sensors by treating those gaps as if they were of zero extent, although still expecting electrical isolation. This will be a convenient fiction that will do no actual harm, but that will provide a welcome simplification by avoiding a messy minor complication.
What is depicted in
FIG. 1
, then, is a highly contrived (but nevertheless useful) case where just one pixel
6
(at location (d, w)) is illuminated; all the others are dark. That is, we assume that the work surface being navigated upon (by an unshown optical mouse) has one reflective feature that is aligned to impinge upon the center of array
2
, and that the feature is of such a size that its image is projected exactly onto photo sensor
6
at (d, w) and onto no other photo sensor. Furthermore, the photo sensors are not mere switches, and produce variable outputs based upon the amount of light that reaches them. Let us assume that photo sensor
6
is sufficiently illuminated to produce a maximum output of one hundred on a scale of zero to one hundred, and that all the other sensors have outputs of zero. For now, let's just say that these values are expressed in some “photo units” related to the light within the image. Now let th
Dietz Zachary
Moore Charles E
Agilent Technologie,s Inc.
Boudreau Leo
Lu Tom Y
Miller Edward L.
LandOfFree
Simplified interpolation for an optical navigation system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Simplified interpolation for an optical navigation system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simplified interpolation for an optical navigation system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3346153