Tracking pointing device motion using a single buffer for cross and auto correlation determination

• US 6,664,948 B2
• Filed: 07/30/2001
• Issued: 12/16/2003
• Est. Priority Date: 07/30/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hastings, Brian L., Crane, Randall T.
• Primary Examiner(s): Wu, Xiao
• Assistant Examiner(s): FATAHI YAR, MAHMOUD
• Application Number:
  US09/918,911
• Publication Number:
  US 20030058218A1
• Time in Patent Office: 869 Days
• Field of Search: 345/156, 345/157, 345/158, 345/159, 345/163, 345/169, 382/312, 382/313, 382/321
• US Class Current: 345/166
• CPC Class Codes: G06F 3/0317 in co-operation with a patterned surface, e.g. absolute position or relative movement detection for an optical mouse or pen positioned with respect to a coded surface

Abstract

Cross correlation between a reference image frame and a comparison image frame determine the direction of motion relative to x and y orthogonal axes for a pointing device that uses optical imaging to monitor movement relative to a surface. Pixel data for a portion of the surface are loaded into a buffer memory that shifts the data between successive positions in the buffer memory as each pixel of a comparison frame is processed to compute cross correlation. Auto correlation is determined for positions in the reference frame and used with the cross correlation results to determine a sub-pixel interpolation for the movement of the pointing device. A new reference frame is loaded using data for the comparison frame currently being processed if the pointing device is moved sufficiently so that the next comparison frame will not overlap the existing reference frame.

Claims

1. A pointing device that produces an output signal indicative of a relative movement between at least a portion of the pointing device and an adjacent surface, comprising:

(a) an imaging detector that produces a signal corresponding to an image of the adjacent surface;

(b) an electronic switch having a first input to receive the signal from the imaging detector, and a second input, said switch being operative to selectively couple one of the first input and the second input to an output;

(c) a sequential memory buffer having an input through which data are input for storage and an output through which data are transferred out of the sequential memory buffer, said input of the sequential memory buffer being coupled to the output of the electronic switch and said output of the sequential memory buffer being coupled to the second input of the electronic switch so that said input of the sequential memory buffer selectively receives data conveyed by either the signal from the imaging detector or the output of the sequential memory buffer, depending upon a state of the electronic switch; and

(d) a processing circuit that is coupled to the imaging detector to respond to the signal corresponding to the image, to the sequential memory buffer to selectively read data stored therein, and to the electronic switch, said processing circuit carrying out a logical process that;

(i) selectively controls a state of the electronic switch to selectively load the sequential memory buffer with data derived from the signal produced by the imaging detector in a first state and with data from the output of the sequential memory buffer in a second state;

(ii) uses the data in the sequential memory buffer for a reference frame and the signal from the imaging detector that comprises a comparison frame to calculate a cross correlation between the reference frame and the comparison frame; and

(iii) produces the output signal indicative of the relative movement between at least the portion of the pointing device and the adjacent surface as a function of the cross correlation.

2. The pointing device of claim 1, wherein the processing circuit further uses the data for the reference frame in the sequential memory buffer to calculate an auto correlation.

3. The pointing device of claim 2, wherein the processing circuit determines a sub-pixel interpolation for the relative movement between at least the portion of the pointing device and the adjacent surface as a function of the auto correlation.

4. The pointing device of claim 1, wherein the sequential memory buffer shifts data for pixels between successive storage locations contained in the sequential memory buffer as data from the output of the electronic switch are applied to the input of the sequential memory buffer.

5. The pointing device of claim 1, further comprising a high-pass filter that is applied to the signal produced by the imaging detector, an output of the high-pass filter being coupled to the first input of the electronic switch and to the processing circuit.

6. The pointing device of claim 1, wherein the electronic switch comprises a multiplexer that determines whether a new reference frame is loaded into the sequential memory buffer or whether the reference frame previously stored in the sequential memory buffer is reloaded therein.

7. The pointing device of claim 1, wherein the data stored in the sequential memory buffer are at least partly selectively addressable and accessible by the processing circuit on a pixel-by-pixel basis.

8. The pointing device of claim 7, wherein as the processing circuit selectively controls the electronic switch to store each pixel of a comparison frame in the sequential memory buffer as a new reference frame, the data for each pixel of said comparison frame are also employed by the processing circuit in calculating a portion of the cross correlation using the data stored in the sequential memory buffer for a previous reference frame.

9. The pointing device of claim 8, wherein the processing circuit employs data for a pixel of the reference frame in calculating a portion of the cross correlation and then transfers the data either out of the sequential memory buffer so that the data are no longer used, or transfers the data back into the input of the sequential memory buffer through the electronic switch, depending, upon the state of the electronic switch.

10. The pointing device of claim 1, wherein the reference frame stored in the sequential memory buffer is replaced with a new reference frame comprising a current comparison frame as a function of a relative velocity between the pointing device and the adjacent surface, said velocity be determinative of whether a meaningful cross correlation can be determined from successive comparison frames.

11. The pointing device of claim 10, wherein the reference frame stored in the sequential memory buffer is replaced before relative movement between the pointing device and the adjacent surface is sufficient to eliminate an overlap between the reference frame that was stored in the sequential memory buffer and a current comparison frame being input from the imaging detector, the overlap being necessary to determine the cross correlation between the reference frame stored in the sequential memory buffer and the comparison frame currently being input to the processing circuit.

12. The pointing device of claim 1, wherein a data storage capacity of the sequential memory buffer is substantially less than that required to store both the reference frame and the comparison frame.

13. A method for producing a signal indicative of a relative movement between at least a portion of a pointing device and an adjacent surface, comprising the steps of:

(a) imaging the adjacent surface to produce image data;

(b) sequentially storing the image data in a memory buffer, the image data stored in the memory buffer corresponding to a reference frame;

(c) acquiring successive pixels of a comparison frame by imaging the adjacent surface, as the relative movement occurs between at least the portion of the pointing device and the adjacent surface, so that it is unnecessary to store said comparison frame in a separate memory buffer;

(d) determining a cross correlation between the reference frame stored in the memory buffer and the successive pixels of the comparison frame; and

(e) as a function of the cross correlation, producing a signal indicative of the extent of the relative movement between at least the portion of the pointing device and the adjacent surface.

14. The method of claim 13, further comprising the step of determining an auto correlation using the image data for the reference frame stored in the memory buffer.

15. The method of claim 14, further comprising the step of determining a sub-pixel interpolation of the relative movement as a function of the auto correlation.

16. The method of claim 14, wherein the step of determining the auto correlation is carried out in parallel with the step of determining the cross correlation, for each successive pixel of the comparison frame.

17. The method of claim 13, further comprising the step of selectively reloading the buffer memory with image data for the reference frame.

18. The method of claim 13, further comprising the step of selectively loading the buffer memory with image data for a new reference frame, using the image data for the comparison frame.

19. The method of claim 18, further comprising the step of determining a velocity of the relative movement between at least the portion of the pointing device and the surface.

20. The method of claim 19, further comprising the step of determining whether to load the new reference frame into the buffer memory as a function of the velocity of the relative movement, said velocity being determinative of whether a meaningful cross correlation can be determined with successive comparison frames.

21. The method of claim 19, further comprising the step of loading the new reference frame into the buffer memory before the relative movement between at least the portion of the pointing device and the surface is sufficient to cause a subsequent comparison frame to no longer overlap the reference frame previously stored in the buffer memory.

22. The method of claim 13, further comprising the step of filtering the image data before determining the cross correlation.

23. The method of claim 13, wherein the image data for the reference frame are shifted through the buffer memory a pixel at a time, as the cross correlation is determined using each successive pixel of the comparison frame.

24. The method of claim 18, further comprising the step of providing additional temporary storage in the buffer memory for a last portion of the image data of a previous reference frame, so that the last portion of the image data of the previous reference frame remain available for use in determining the cross correlation as the new reference frame is loaded into the buffer memory.

25. The method of claim 24, further comprising the step of discarding successive pixel image data for the previous reference frame as the new reference frame is loaded into the buffer memory.

26. A machine readable medium that stores a plurality of machine instructions for performing the steps of claim 13.

27. A machine readable medium that stores a plurality of machine instructions for performing the steps of claim 14.

28. A user input device that is movable and which produces an output signal indicative of a movement of the user input device, for input to a computing device, comprising:

(a) a housing that is movable relative to a surface;

(b) an image sensor disposed in the housing and oriented so as to detect an image of the surface, producing a signal corresponding to pixel data for the image of the surface;

(c) a buffer memory in which pixel data for a reference frame are stored, pixel data for said reference frame being sequentially shifted through the buffer memory; and

(d) a processing circuit that is coupled to the image sensor and the buffer memory, said processing circuit implementing a plurality of functions, including;

(i) selectively loading the pixel data for the reference frame into the buffer memory;

(ii) determining a cross correlation between the reference frame and pixel data received from the image sensor as the user input device is moved over the surface, so that it is unnecessary to store the pixel data in a buffer memory prior to determining the cross correlation; and

(iii) based upon the cross correlation, determining the movement of the user input device over the surface, producing a corresponding output signal indicative of said movement.

29. The user input device of claim 28, wherein the processing circuit further determines an auto correlation for the reference frame and modifies the output signal as a function of the auto correlation to include a sub-pixel interpolation for the movement of the user input device relative to the surface.

30. The user input device of claim 28, further comprising a light source disposed in the housing and oriented to illuminate the surface to enable the image sensor to detect the image of the surface.

31. The user input device of claim 28, further comprising a multiplexer that is coupled to the processing circuit, said multiplexer including an output coupled to an input of the buffer memory, a first input coupled to the image sensor, and a second input coupled to an output of the buffer memory, said multiplexer being controlled by the processing circuit to selectively determine whether the reference frame in the buffer memory is reloaded into the buffer memory, or that the comparison frame is loaded into the buffer memory as a new reference frame.

32. The user input device of claim 31, wherein the processing circuit causes the multiplexer to load the new reference frame if the movement of the user input device relative to the surface is about to result in a successive comparison frame no longer overlapping the reference frame that is currently stored in the buffer memory.

33. The user input device of claim 32, wherein the processing circuit determines a velocity with which the user input device is moving relative to the surface to determine when to cause the multiplexer to load the new reference frame into the buffer memory.

34. The user input device of claim 31, wherein the buffer memory is unable to store all of the pixel data for the reference frame and the comparison frame, at the same time.

35. The user input device of claim 28, further comprising a memory in which components of the cross correlation are stored while the cross correlation is being determined for the comparison frame.

36. The user input device of claim 28, wherein only pixel data within a correlation window are used in determining the cross correlation.

37. A motion sensing circuit for detecting movement relative to a surface, comprising:

(a) an image sensor that produces a signal corresponding to pixel data for an image of the surface;

(b) a shift memory in which the pixel data are selectively loaded;

(c) a processing circuit that controls loading of pixel data into the shift memory and determines a cross correlation between the data previously loaded into the shift memory and pixel data for a subsequent image of the surface without first loading the pixel data for the subsequent image into a memory, the pixel data for successive pixels of the subsequent image being used to determine the cross correlation as the pixel data in the shift memory are sequentially moved through the shift memory, the relative movement being determined based upon the cross correlation thus determined.

38. The motion sensing circuit of claim 37, wherein the processing circuit reloads the shift memory with the pixel data previously loaded therein unless sufficient movement has occurred to require that new pixel data be loaded into the shift memory from the image sensor for use in subsequently determining the cross correlation.

39. The motion sensing circuit of claim 37, wherein the processing circuit also determines an auto correlation for the pixel data loaded into the shift memory.

40. The motion sensing circuit of claim 39, wherein the processing circuit further determines a sub-pixel interpolation for the relative movement as a function of the auto correlation.

41. The motion sensing circuit of claim 38, further comprising a switching device that is coupled to the shift memory and controlled by the processing circuit to either reload the pixel data that were previously loaded into the shift memory, or to load the new pixel data into the shift memory.

42. The motion sensing circuit of claim 41, wherein the processing circuit determines a velocity for the relative movement as a basis for determining when to load the new pixel data into the shift memory, said velocity being determinative of whether a meaningful cross correlation can be determined with successive comparison frames.

43. The motion sensing circuit of claim 38, wherein the shift memory is of sufficient size to store one frame of pixel data and a portion of the frame of pixel data, said portion being used to temporarily store a portion of the pixel data previously loaded into the shift memory for use with the new pixel data being loaded into the shift memory for determining the cross correlation.

44. The motion sensing circuit of claim 37, further comprising an electronic filter that is coupled to the image sensor for electronically filtering the pixel data from the image sensor.

45. A method for determining a sub-pixel interpolation component for relative movement between an object and an adjacent surface, comprising the steps of:

(a) producing a signal corresponding to a pixelated image of the surface;

(b) storing a reference frame for the surface that includes data for each of a plurality of pixels of the pixelated image, said reference frame being stored in a memory buffer that enables the data to be shifted through the memory buffer a pixel at a time;

(c) as relative movement occurs between the object and the adjacent surface, producing a comparison frame that includes data for a plurality of pixels in a new pixelated image;

(d) determining a cross correlation between the data for the reference frame and the data for the comparison frame as successive pixels of the data for the comparison frame are read from the pixilated image corresponding to the comparison frame as said data for the reference frame are shifted through the memory buffer;

(e) determining an auto correlation of the data for the reference frame; and

(f) determining the sub-pixel interpolation component for the relative movement as a function of both the cross correlation and the auto correlation.

46. The method of claim 45, further comprising the step of determining a pixel component of the relative motion as a function of the cross correlation.

47. The method of claim 46, further comprising the step of selecting one of a plurality of different predefined mathematical functions to use in determining the sub-pixel interpolation component, based upon a direction in which the relative movement has occurred, where each of the plurality of different predefined mathematical functions corresponds to a different direction of the relative movement.

48. A machine readable medium that stores a plurality of machine instructions for performing the steps of claim 45.

49. A machine readable medium that stores a plurality of machine instructions for performing the steps of claim 47.

50. A user controlled object that determines a sub-pixel interpolation component for relative movement between said object and an adjacent surface, comprising:

(a) a pixelated image sensor that produces a signal corresponding to pixels of an image of a surface;

(b) a memory in which data corresponding to the pixels of the image are stored, said data comprising a reference frame and being shifted through the memory;

(c) a processing circuit that is coupled to the memory and to the pixelated image sensor, said processing circuit implementing a plurality of functions, including;

(i) determining a cross correlation between the data for the reference frame stored in the memory and data for successive pixels of a comparison frame that corresponds to new data for the image of the surface, as the relative movement between the surface and the object occurs, said cross correlation being determined as successive pixels of the comparison frame are read from the pixelated image sensor and as pixels of the data for the reference frame are shifted through the memory;

(ii) determining an auto correlation using the data for the reference frame that is stored in the memory; and

(iii) determining the sub-pixel interpolation component for the relative movement as a function of both the cross correlation and the auto correlation.

51. The system of claim 50, wherein the processing circuit further determines a pixel component of the relative motion as a function of the cross correlation.

52. The system of claim 50, wherein the processing circuit further selects one of a plurality of different predefined mathematical functions to use in determining the sub-pixel interpolation component, based upon a direction in which the relative movement has occurred, where each of the plurality of different predefined mathematical functions corresponds to a different direction of the relative movement.