Pointing device and displacement estimation method

• US 20050151724A1
• Filed: 06/24/2004
• Published: 07/14/2005
• Est. Priority Date: 12/29/2003
• Status: Active Grant

• Current Assignee: PixArt Imaging Incorporated
• Original Assignee: PixArt Imaging Incorporated
• Inventors: Lan, Jeng-Feng, Lin, Chun-Huang
• Granted Patent: US 7,417,623 B2
• Time in Patent Office: Days
• 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
• CPC Class Codes: G06T 7/238 using non-full search, e.g. three-step search

Abstract

A method of estimating image displacement by block matching for a pointing device used in a computer system. The method provided in the present invention comprises capturing digital images sequentially using a photo capture device, obtaining a template frame and a current frame, estimating a predicted velocity vector, and computing the displacement of the image. The efficiency and reliability of block match searching are improved by reducing the search range according to the calculated displacement. The template block can be defined anywhere on the template frame according to the predicted velocity to extend the lifetime of the template frame, and the displacement vector between the template block and the center of the template frame is proportional to the predicted velocity.

Claims

1. A pointing device for a computer system, comprising:

a photo capture device, capturing images sequentially to produce a first frame and a second frame; and

a displacement detection circuit, predicting a velocity of the pointing device, and comparing the first frame and the second frame according to the predicted velocity to obtain a displacement of the pointing device.

2. The pointing device according to claim 1, wherein the photo capture device comprises a photosensing array with a plurality of photo detectors.

3. The pointing device according to claim 2, wherein an area of each photo detector in the photosensing array is between 20 μ

m*20 μ

m to 40 μ

m*40 μ

m.

4. The pointing device according to claim 1, wherein the predicted velocity is derived from at least two previous velocities of the pointing device.

5. The pointing device according to claim 1, wherein the predicted velocity is estimated as:

$\stackrel{\to <br><br>}{V}<br><br>p=\frac{\text{\hspace{1em}<br><br>}<br><br>\stackrel{\rightharpoonup <br><br>}{V}<br><br>\text{\hspace{1em}<br><br>}<br><br>m<br><br>\text{\hspace{1em}<br><br>}+\text{\hspace{1em}<br><br>}<br><br>\stackrel{\rightharpoonup <br><br>}{V}<br><br>n}{\text{\hspace{1em}<br><br>}<br><br>2}+\left(\stackrel{\rightharpoonup <br><br>}{V}<br><br>m-\stackrel{\rightharpoonup <br><br>}{V}<br><br>n\right)$

where {overscore (V)}m and {overscore (V)}n comprise average velocities by accumulating m and n instantaneous velocities respectively and m>

n.

6. The pointing device according to claim 1, wherein the displacement detection circuit computes the predicted velocity according to an acceleration of the pointing device.

7. The pointing device according to claim 1, wherein the displacement detection circuit defines a template block in the first frame, defines a searching range in the second frame that is smaller than the second frame according to the predicted velocity, and outputs the displacement by searching a matched block in the search range, wherein the matched block is the block with the greatest correlation to the template block in the search range.

8. The pointing device according to claim 1, wherein the displacement detection circuit defines a template block in the first frame according to the predicted velocity, and searches a matched block with the greatest correlation to the template block in the second frame.

9. A displacement estimation method for a pointing device, the pointing device comprises a photo capture device for capturing images sequentially to produce corresponding frames, the method comprising the following steps:

estimating a predicted velocity of the pointing device; and

comparing a first frame and a second frame produced by the photo capture device according to the predicted velocity to obtain a displacement of the pointing device.

10. The displacement estimation method according to claim 9, wherein the predicted velocity is estimated according to at least two previous velocities.

11. The displacement estimation method according to claim 9, wherein the step of estimating the predicted velocity further comprises estimating the predicted velocity according to an estimated acceleration of the pointing device and at least one of the previous velocities.

12. The displacement estimation method according to claim 9, wherein the step of comparing the first frame and the second frame further comprises:

defining a template block in the first frame;

defining a search range in the second frame according to the predicted velocity; and

searching a matched block in the searching range in order to output the displacement, wherein the matched block is the block with the greatest correlation to the template block.

13. The displacement estimation method according to claim 12, wherein the step of defining the searching range further comprises the following steps:

computing an predicted block according to the predicted velocity, wherein the predicted block is the same size as the template block, and is the most probable location in the second frame for the template block according to the predicted velocity of the pointing device; and

extending the predicted block to set the search range.

14. The displacement estimation method according to claim 12, further comprising:

changing a location of the template block when the predicted velocity exceeds a first velocity; and

setting the search range based on an acceleration of the photo capture device.

15. The displacement estimation method according to claim 13, wherein each frame comprises X pixels*Y pixels, and the predicted block is extended symmetrically by at least one pixel to form search range.

16. The displacement estimation method according to claim 13, wherein the predicted block is extended asymmetrically to form the search range.

17. The displacement estimation method according to claim 9, wherein the step of comparing the first frame and the second frame further comprises:

defining a template block in the first frame according to the predicted velocity; and

searching a matched block in the second frame, wherein the matched block is the block with the greatest correlation to the template block.

18. The displacement estimation method according to claim 9, wherein the photo capture device comprises a photosensing array with a plurality of photo detectors.

19. The displacement estimation method according to claim 18, wherein an area of each photo detector in the photosensing array is between 20 μ

m*20 μ

m to 40 μ

m*40 μ

m.

20. A pointing device for a computer system, comprising.

a photo capture device, capturing images sequentially to produce a first frame and a second frame;

and

a displacement detection circuit, predicting a velocity of the pointing device according to an acceleration of the pointing device and comparing the first frame and the second frame according to the predicted velocity to obtain a displacement of the pointing device.