High-performance closed-form single-scan calculation of oblong-shape rotation angles from image data of arbitrary size and location using running sums

• US 8,639,037 B2
• Filed: 03/18/2013
• Issued: 01/28/2014
• Est. Priority Date: 03/14/2009
• Status: Expired due to Fees

• Current Assignee: NRI R&D Patent Licensing, LLC (Advanced Touchscreen and Gesture Technologies, LLC)
• Original Assignee: Lester F. Ludwig
• Inventors: Ludwig, Lester F.
• Primary Examiner(s): Rahmjoo, Mike
• Application Number:
  US13/846,830
• Publication Number:
  US 20130208011A1
• Time in Patent Office: 316 Days
• Field of Search: 382/203, 382/162, 382/167, 382/165, 382/169, 382/170, 382/220, 382/218
• US Class Current: 382/203
• CPC Class Codes: G06F 3/042 by opto-electronic means
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 10/435 Computation of moments
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis
• CPC Class Codes: G06V 40/107 Static hand or arm
• CPC Class Codes: G06V 40/12 Fingerprints or palmprints
• CPC Class Codes: G09G 5/34 for rolling or scrolling

Abstract

A method and system for calculating oblong-shape rotation angles from image data of arbitrary size using running sums is described without the need of eigenvector routines and storage of the image data. The oblong shape may be of arbitrary size and location and need not be precisely elliptical. A few running sums are calculated and stored throughout each scan, and the results are obtained in closed form by simple post-scan computation. An algorithmic embodiment can execute on one or more hardware processors with limited or otherwise constrained computation power, available instruction cycles, available memory, etc. Hardware processors may CPUs found in desktops, laptops, tablets, or handheld computing devices. The resulting arrangement may be used for touch or optical user interfaces, real-time image recognition, real-time machine vision, and other purposes.

Claims

1. A computer-implemented method for computing an orientation angle of an image of an oblong shape using a processor, the image of the oblong shape comprising thresholded pixels within image data, wherein each thresholded pixel is a scalar measurement comprising a numerical value exceeding a threshold, the method comprising:

determining a cumulative sum of the square of row indices of thresholded pixels, wherein an thresholded pixel is defined as a measurement data element within the binary-valued image data having a specified binary numerical value;

determining a cumulative sum of the square of column indices of thresholded pixels;

determining a cumulative sum of the product of row and column indices of thresholded pixels;

determining a value according to a closed form algebraic formula comprising the cumulative sum of the square of row indices, the cumulative sum of the square of column indices, and the cumulative sum of the product of row and column indices;

determining the computed orientation angle of the oblong shape of binary-valued image data according to the value using an inverse trigonometric function operation; and

providing the computed orientation angle as an output.

2. The method of claim 1 wherein the additional software provides a user interface function.

3. The method of claim 2 wherein the computed orientation angle is used as a user interface quantity for controlling at least one aspect of a computer application.

4. The method of claim 1 wherein the image data is produced from measurement data provided by a tactile sensor array.

5. The method of claim 4 wherein the tactile sensor array comprises a tactile proximity sensor.

6. The method of claim 4 wherein the tactile sensor array comprises a tactile pressure sensor.

7. The method of claim 4 wherein the image data is produced at least in part responsive to contact of a human hand with the tactile sensor array.

8. The method of claim 4 wherein the image data is produced by an optical sensing system.

9. The method of claim 1 wherein the inverse trigonometric function operation comprises an inverse cotangent function.

10. The method of claim 1 wherein the processor comprises an embedded controller.

11. A computer implemented data processing system comprising:

a memory that stores image data; and

a processor in communication with the memory that;

receives the image data, the image data comprising an array of pixels having rows and columns wherein each row and column has a unique associated index value, and each pixel having has a unique row index value and column index value wherein each pixel further comprises a scalar measurement, the image data comprising a subset of pixels having values above a threshold value that are arranged in an oblong shape within the image data;

perform threshold operations on each pixel of the image data to produce binary image data to generate the oblong shape;

computes the geometric center of the oblong shape, the geometric center comprising a row center value and a column center value;

defines a corresponding centered row index value by subtracting the row center value from the row index value for each row index value;

defines a corresponding centered column index value by subtracting the column center value from the column index value for each column index value;

computes a first cumulative sum of the square of centered row index values of the subset of pixels having values above the threshold value, second cumulative sum of the square of centered column index values of the subset of pixels having values above the threshold value, and a third cumulative sum of the product of centered row index values and centered column index values of the subset of pixels having values above the threshold value;

computes one or more numerical quantities within a closed form algebraic formula for a ratio of two terms of an inertial matrix defined by the binary-valued image data using each of first, second, and third cumulative sums;

transforms the ratio into a calculated numerical angle value using an inverse trigonometric function operation; and

provides the calculated numerical angle value as an output.

12. The system of claim 11 wherein the additional software provides a user interface function.

13. The system of claim 12 wherein the calculated numerical angle value is used as a user interface quantity for controlling at least one aspect of a computer application.

14. The system of claim 11 wherein the image data is produced from measurement data provided by a tactile sensor array.

15. The system of claim 14 wherein the tactile sensor array comprises a tactile proximity sensor.

16. The system of claim 14 wherein the tactile sensor array comprises a tactile pressure sensor.

17. The system of claim 14 wherein the image data is produced at least in part responsive to contact of a human hand with said tactile sensor array.

18. The system of claim 14 wherein the image data is produced by an optical sensing system.

19. The system of claim 11 wherein the inverse trigonometric function operation comprises an inverse cotangent function.

20. The system of claim 11 wherein the processor comprises an embedded controller.