Optical flow-based manipulation of graphical objects

• US 7,535,463 B2
• Filed: 06/15/2005
• Issued: 05/19/2009
• Est. Priority Date: 06/15/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wilson, Andrew D.
• Primary Examiner(s): Nguyen; Chanh
• Assistant Examiner(s): Snyder; Adam J
• Application Number:
  US11/154,495
• Publication Number:
  US 20060284874A1
• Time in Patent Office: 1,434 Days
• Field of Search: 345156-184, 353/122
• US Class Current: 345/175
• CPC Class Codes: G06F 3/0421 by interrupting or reflecting a light beam, e.g. optical touch-screen
• CPC Class Codes: G06T 7/269 using gradient-based methods

Abstract

Motion of one or more physical objects relative to a display surface of a display system is detected and an optical flow determined from the motion is used to manipulate a graphical object presented on the display surface. The one or more physical objects are detected in response to light reflected from the object(s) and received by a video camera. The optical flow is determined from the video camera image by identifying flow vectors for points in one or more patches included in the image that correspond to the physical objects. A proximity of a physical object to the display surface can be determined based on an intensity of light reflected from the physical object(s), or using a touch sensor such as a capacitance, pressure, or electromagnetic sensor or the like. Based on the optical flow, the graphical object can be translated, rotated, and/or scaled in size.

Claims

1. A method of manipulating a graphical object presented on a display surface in response to a movement of one or more physical objects that are adjacent to the display surface, comprising the steps of:

(a) creating a first image of the display surface in which one or more patches are included that represent one or more portions of the physical object at a first time index, and wherein the one or more patches include a plurality of points that intersect points in the graphical object at the first time index;

(b) creating a second image of the display surface in which the one or more patches are included and which represent the one or more portions of the physical object at a second time index occurring after the first time index;

(c) determining flow vectors describing two-dimensional, in x and y directions, motion for at least some of the plurality of points that intersect points in the graphical object in the one or more patches at the first time index and the second time index, the optical flow vectors defining one or more vector fields that define an optical flow for the one or more portions of the one or more physical objects wherein determining flow vectors describing a two-dimensional, in x and y directions, motion for at least some of the plurality of points that intersect points in the graphical object comprises comparing patches by computing the sum of pixel wise absolute differences such that for a given patch in an image, (dx, dy) is selected to minimize

$\underset{x,y\in <br><br>\mathrm{patch}}{\sum <br><br>}<br><br><br><br><br><br>I_{t-1}<br><br>\left(x,y\right)-I_t<br><br>\left(x+\mathrm{dx},y+\mathrm{dy}\right)<br><br>;<br><br>\mathrm{and}$

(d) manipulating the graphical object by applying the optical flow to the graphical object presented on the display surface.

2. The method of claim 1, wherein the step of creating the first image comprises the step of processing at least one of a raw image of the display surface, or a normalized image produced from the raw image, wherein the raw image is made at the first time index in response to light reflected from the one or more physical objects and received by a light sensor.

3. The method of claim 1, wherein the step of creating the second image comprises the step of processing at least one of a raw image of the display surface, or a normalized image produced from the raw image, wherein the raw image is made at the second time index in response to light reflected from the one or more physical objects and received by a light sensor.

4. The method of claim 2, further comprising the step of:

(a) determining whether at least some points in the first image intersect with points within the graphical object; and

(b) only manipulating the graphical object by applying the optical flow to the graphical object if the optical flow is determined for the at least some points in the first image that intersect with points within the graphical object.

5. The method of claim 2, further comprising the steps of:

(a) determining that only a single graphical object that can be manipulated is presented on the display surface; and

(b) manipulating the graphical object image by applying the optical flow without regard to whether any points in the first image intersect with points within the graphical object.

6. The method of claim 1, wherein the optical flow vectors describing the two-dimensional motion of the at least some points are determined based on at least one of:

a block-matching algorithm, a Lucas-Kanade algorithm, or Horn and Schunck.

7. The method of claim 1, wherein the manipulation of the graphical object comprises at least one of the steps of:

(a) translating the graphical object to a different disposition on the display surface;

(b) rotating the graphical object to a different orientation on the displays surface;

or

(c) scaling the graphical object to change at least one of its size or its shape.

8. The method of claim 1, wherein the optical flow is repetitively determined at successive times to continuously manipulate the graphical object while the at least one the physical object is being moved.

9. A memory medium on which are stored machine executable instructions for carrying out the steps of claim 1.

10. Apparatus for detecting, applying, and displaying manipulation of a graphical object in response to movement of a physical object, comprising:

(a) a display surface adjacent to which the physical object can be positioned and moved and on which the graphical image is presented;

(b) a light source that emits light for illuminating a physical object disposed adjacent to the display surface;

(c) a light sensor disposed so as to sense light reflected back from the physical object, through the display surface;

(d) a processor in communication with the light sensor; and

(e) a memory in communication with the processor, the memory storing data and machine instructions that when executed by the processor cause a plurality of functions to be carried out, including;

(i) using the light sensor, creating a first image of the display surface in which one or more patches are included that represent one or more portions of the physical object at a first time index, and wherein the one or more patches include a plurality of points that intersect points in the graphical object at the first time index;

(ii) using the light sensor, creating a second image of the display surface in which the one or more patches are included and which represent the one or more portions of the physical object at a second time index occurring after the first time index;

(iii) determining flow vectors describing two-dimensional, in x and y directions, motion for at least some points in the one or more patches at the first time index and the second time index, the optical flow vectors defining an optical flow for the one or more portions of the one or more physical objects wherein determining flow vectors describing a two-dimensional, in x and y directions, motion for at least some of the plurality of points that intersect points in the graphical object comprises determining a merit of a computed (dx, dy) at a patch, by comparing a match score corresponding to (dx, dy) =0 against a best score for any (dx, dy) and discarding the flow information at this patch if the best score is not significantly better than that corresponding to (dx, dy) =0 so as to avoid spurious flow vectors computed on regions of an image without adequate texture; and

(iv) manipulating the graphical object by applying the optical flow to the graphical object presented on the display surface.

11. The apparatus of claim 10, wherein the machine language instructions further cause the processor to process at least one of a raw image of the display surface, or a normalized image produced from the raw image, wherein the raw image is made at the first time index in response to a light reflected from the one or more physical objects and received by the light sensor.

12. The apparatus of claim 10, wherein the machine language instructions further cause the processor to process at least one of a raw image of the display surface, or a normalized image produced from the raw image, wherein the raw image is made at the second time index in response to light reflected from the one or more physical objects and received by the light sensor.

13. The apparatus of claim 12, wherein the machine instructions further cause the processor to:

(a) determine whether at least some points in the first image intersect with points within the graphical object; and

(b) only manipulate the graphical object by applying the optical flow to the graphical object if the optical flow is determined for the at least some points in the first image that intersect with points within the graphical object.

14. The apparatus of claim 12, wherein the machine instructions further cause the processor to:

(a) determine that only a single graphical object that can be manipulated is presented on the display surface; and

(b) manipulate the graphical object image by applying the optical flow without regard to whether any points in the first image intersect with points within the graphical object.

15. The apparatus of claim 10, wherein the machine language instructions further cause the processor to manipulate the graphical object by at least one of:

(a) translating the graphical object to a different disposition on the display surface;

(b) rotating the graphical object to a different orientation on the displays surface;

or

(c) scaling the graphical object to change at least one of its size or its shape.

16. The apparatus of claim 10, wherein the optical flow describing a two-dimensional motion of at least a portion of the physical object is determined based on at least one of:

a block-matching algorithm, a Lucas-Kanade algorithm, or Horn and Schunck.