Increasing accuracy of discrete curve transform estimates for curve matching in higher dimensions

US 7,450,765 B2
Filed: 09/07/2007
Issued: 11/11/2008
Est. Priority Date: 04/10/2002
Status: Expired due to Term

First Claim

Patent Images

1. A computer-accessible memory medium that stores program instructions for estimating a rotational shift between a first discrete curve and a second discrete curve, wherein the program instructions are executable to perform:

receiving a first discrete curve and a second discrete curve, wherein the second discrete curve is a rotationally shifted version of the first discrete curve, wherein the first discrete curve and the second discrete curve each comprises a respective curve in at least three dimensions;

estimating a rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve, wherein said estimating the rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve comprises calculating;

$α = \frac{\begin{matrix} \sum_{n = 1}^{N} {(z_{n 1} - y_{n 1}) (y_{n + 11} - y_{n 1}) + (z_{n 2} - y_{n 2}) (y_{n + 12} - y_{n 2}) + \\ (z_{n 3} - y_{n 3}) (y_{n + 13} - y_{n 3})} \end{matrix}}{\sum_{n = 1}^{N} {{(y_{n + 11} - y_{n 1})}^{2} + {(y_{n + 12} - y_{n 2})}^{2} + {(y_{n + 13} - y_{n 3})}^{2}}}$ wherein y_nand z_nrefer to points in the first discrete curve and the second discrete curve, respectively;

updating a cumulative rotational shift based on the estimated rotational shift;

generating a rotationally shifted version of the second discrete curve based on the cumulative rotational shift;

performing said estimating, said updating, and said generating in an iterative manner using the respective rotationally shifted discrete curve for each iteration until a stopping condition occurs, thereby determining a final estimate of the rotational shift between the first discrete curve and the second discrete curve; and

storing the final estimate of the rotational shift, wherein the final estimate of the rotational shift is useable to perform discrete curve matching.

View all claims

5 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

System and method for estimating a rotational shift between a first discrete curve and a second discrete curve, where the second discrete curve is a rotationally shifted version of the first discrete curve. First and second discrete curves are received. A rotational shift between the first discrete curve and the second discrete curve is estimated based on the first discrete curve and the second discrete curve. A cumulative rotational shift is updated based on the estimated rotational shift. A rotationally shifted version of the second discrete curve is generated based on the cumulative rotational shift. The estimating, updating, and generating are performed in an iterative manner using the respective rotationally shifted discrete curve for each iteration until a stopping condition occurs, thereby determining a final estimate of the rotational shift between the first discrete curve and the second discrete curve. The final estimate may be used to perform curve matching.

19 Citations

View as Search Results

22 Claims

1. A computer-accessible memory medium that stores program instructions for estimating a rotational shift between a first discrete curve and a second discrete curve, wherein the program instructions are executable to perform:
- receiving a first discrete curve and a second discrete curve, wherein the second discrete curve is a rotationally shifted version of the first discrete curve, wherein the first discrete curve and the second discrete curve each comprises a respective curve in at least three dimensions;
  
  estimating a rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve, wherein said estimating the rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve comprises calculating;
  
  $α = \frac{\begin{matrix} \sum_{n = 1}^{N} {(z_{n 1} - y_{n 1}) (y_{n + 11} - y_{n 1}) + (z_{n 2} - y_{n 2}) (y_{n + 12} - y_{n 2}) + \\ (z_{n 3} - y_{n 3}) (y_{n + 13} - y_{n 3})} \end{matrix}}{\sum_{n = 1}^{N} {{(y_{n + 11} - y_{n 1})}^{2} + {(y_{n + 12} - y_{n 2})}^{2} + {(y_{n + 13} - y_{n 3})}^{2}}}$ wherein y_nand z_nrefer to points in the first discrete curve and the second discrete curve, respectively;
  
  updating a cumulative rotational shift based on the estimated rotational shift;
  
  generating a rotationally shifted version of the second discrete curve based on the cumulative rotational shift;
  
  performing said estimating, said updating, and said generating in an iterative manner using the respective rotationally shifted discrete curve for each iteration until a stopping condition occurs, thereby determining a final estimate of the rotational shift between the first discrete curve and the second discrete curve; and
  
  storing the final estimate of the rotational shift, wherein the final estimate of the rotational shift is useable to perform discrete curve matching.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
- - 2. The memory medium of claim 1, wherein the first discrete curve and the second discrete curve each comprises a respective spatial curve.
  - 3. The memory medium of claim 1, wherein each point of the respective spatial curves comprises:
    - three 3D spatial coordinates.
  - 4. The memory medium of claim 1, wherein each point of the respective spatial curves comprises:
    - two 2D spatial coordinates; and
      
      a gray-scale value;
      
      wherein the gray-scale value is interpreted as a third spatial coordinate.
  - 5. The memory medium of claim 1, wherein the first discrete curve and the second discrete curve each comprises a respective sequence of points, wherein each point comprises:
    - two spatial coordinates; and
      
      one additional coordinate, based on additional image data associated with the point, wherein the additional coordinate is interpreted as an additional spatial coordinate for the point.
  - 6. The memory medium of claim 1, wherein the stopping condition occurs when a magnitude of the estimated rotational shift is less than a specified threshold value.
  - 7. The memory medium of claim 1, wherein the stopping condition occurs when a specified number of iterations have elapsed.
  - 8. The memory medium of claim 1, wherein the first discrete curve and the second discrete curve each comprise a respective sequence of points in a complex space.
  - 9. The memory medium of claim 1, wherein the first discrete curve and the second discrete curve comprise substantially smooth discrete curves.
  - 10. The memory medium of claim 1, wherein the first discrete curve and the second discrete curve each comprises a respective closed curve.
  - 11. The memory medium of claim 1,wherein the first discrete curve and the second discrete curve each comprises the same number of points, wherein for each curve, each point corresponds to a value of an index;
    - and
12. The memory medium of claim 11,wherein an estimated a rotational shift value of 1 corresponds to a cyclic shift of one point in the second discrete curve.
13. The memory medium of claim 1, wherein the second discrete curve is rotationally shifted from the first discrete curve by less than a rotational distance between successive points in the second discrete curve.
14. The memory medium of claim 1, wherein the second discrete curve is rotationally shifted from the first discrete curve by less than or equal to 5 degrees.
15. The memory medium of claim 1, wherein the second discrete curve is rotationally shifted from the first discrete curve by less than or equal to 1 degree.
16. The memory medium of claim 1, wherein said rotational shifting the second discrete curve based on the estimated rotational shift to generate a respective rotationally shifted discrete curve further comprises:
- interpolating the second discrete curve.
17. The memory medium of claim 1, wherein the program instructions are further executable to perform:
- outputting the final estimate of the rotational shift between the first discrete curve and the second discrete curve.
18. The memory medium of claim 1, wherein the program instructions are further executable to perform:
- performing curve matching on the first discrete curve and the second discrete curve using the final estimate of the rotational shift, thereby generating results indicating a degree of match between the first discrete curve and the second discrete curve.

19. A method for estimating a rotational shift between a first discrete curve and a second discrete curve, the method comprising:
- receiving a first discrete curve and a second discrete curve, wherein the second discrete curve is a rotationally shifted version of the first discrete curve;
  
  estimating a rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve, wherein said estimating the rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve comprises calculating;
  
  $α = \frac{\begin{matrix} \sum_{n = 1}^{N} {(z_{n 1} - y_{n 1}) (y_{n + 11} - y_{n 1}) + (z_{n 2} - y_{n 2}) (y_{n + 12} - y_{n 2}) + \\ (z_{n 3} - y_{n 3}) (y_{n + 13} - y_{n 3})} \end{matrix}}{\sum_{n = 1}^{N} {{(y_{n + 11} - y_{n 1})}^{2} + {(y_{n + 12} - y_{n 2})}^{2} + {(y_{n + 13} - y_{n 3})}^{2}}}$ wherein y_nand z_nrefer to points in the first discrete curve and the second discrete curve, respectively;
  
  updating a cumulative rotational shift based on the estimated rotational shift;
  
  generating a rotationally shifted version of the second discrete curve based on the cumulative rotational shift; and
  
  performing said estimating, said updating, and said generating in an iterative manner using the respective rotationally shifted discrete curve for each iteration until a stopping condition occurs, thereby determining a final estimate of the rotational shift between the first discrete curve and the second discrete curve; and
  
  storing the final estimate of the rotational shift, wherein the final estimate of the rotational shift is useable to perform discrete curve matching.

20. A system for estimating a rotational shift between a first discrete curve and a second discrete curve, the system comprising:
- a processor;
  
  a memory medium coupled to the processor;
  
  an input coupled to the processor and the memory medium; and
  
  an output coupled to the processor and the memory medium;
  
  wherein the input is operable to receive a first discrete curve and a second discrete curve, wherein the second discrete curve is a rotationally shifted version of the first discrete curve, and wherein the first discrete curve and the second discrete curve each comprises a respective sequence of points in at least three dimensions;
  
  wherein the memory medium stores program instructions which are executable by the processor to;
  
  estimate a rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete, wherein said estimating the rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve comprises calculating;
  
  $α = \frac{\begin{matrix} \sum_{n = 1}^{N} {(z_{n 1} - y_{n 1}) (y_{n + 11} - y_{n 1}) + (z_{n 2} - y_{n 2}) (y_{n + 12} - y_{n 2}) + \\ (z_{n 3} - y_{n 3}) (y_{n + 13} - y_{n 3})} \end{matrix}}{\sum_{n = 1}^{N} {{(y_{n + 11} - y_{n 1})}^{2} + {(y_{n + 12} - y_{n 2})}^{2} + {(y_{n + 13} - y_{n 3})}^{2}}}$ wherein y_nand z_nrefer to points in the first discrete curve and the second discrete curve, respectively;
  
  update a cumulative rotational shift based on the estimated rotational shift;
  
  generate a rotationally shifted version of the second discrete curve based on the cumulative rotational shift; and
  
  perform said estimating, said updating, and said generating in an iterative manner using the respective rotationally shifted discrete curve for each iteration until a stopping condition occurs, thereby determining a final estimate of the rotational shift between the first discrete curve and the second discrete curve;
  
  wherein the output is operable to output the final estimate of the rotational shift between the first discrete curve and the second discrete curve, and wherein the final estimate of the rotational shift is useable to perform discrete curve matching.

21. A system for estimating a rotational shift between a first discrete curve and a second discrete curve, the system comprising:
- means for receiving a first discrete curve and a second discrete curve, wherein the second discrete curve is a rotationally shifted version of the first discrete curve, wherein the first discrete curve and the second discrete curve each comprises a respective curve in at least three dimensions;
  
  means for estimating a rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve, wherein said estimating the rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve comprises calculating;
  
  $α = \frac{\begin{matrix} \sum_{n = 1}^{N} {(z_{n 1} - y_{n 1}) (y_{n + 11} - y_{n 1}) + (z_{n 2} - y_{n 2}) (y_{n + 12} - y_{n 2}) + \\ (z_{n 3} - y_{n 3}) (y_{n + 13} - y_{n 3})} \end{matrix}}{\sum_{n = 1}^{N} {{(y_{n + 11} - y_{n 1})}^{2} + {(y_{n + 12} - y_{n 2})}^{2} + {(y_{n + 13} - y_{n 3})}^{2}}}$ wherein y_nand z_nrefer to points in the first discrete curve and the second discrete curve, respectively;
  
  means for updating a cumulative rotational shift based on the estimated rotational shift;
  
  means for generating a rotationally shifted version of the second discrete curve based on the cumulative rotational shift;
  
  means for performing said estimating, said updating, and said generating in an iterative manner using the respective rotationally shifted discrete curve for each iteration until a stopping condition occurs, thereby determining a final estimate of the rotational shift between the first discrete curve and the second discrete curve; and
  
  means for storing the final estimate of the rotational shift, wherein the final estimate of the rotational shift is useable to perform discrete curve matching.

22. A programmable hardware element configured for estimating a rotational shift between a first discrete curve and a second discrete curve, wherein the programmable hardware element is configured to perform:
- receiving a first discrete curve and a second discrete curve, wherein the second discrete curve is a rotationally shifted version of the first discrete curve, wherein the first discrete curve and the second discrete curve each comprises a respective curve in at least three dimensions;
  
  estimating a rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve, wherein said estimating the rotational shift between the first discrete curve and the second discrete curve based on the first discrete curve and the second discrete curve comprises calculating;
  
  $α = \frac{\begin{matrix} \sum_{n = 1}^{N} {(z_{n 1} - y_{n 1}) (y_{n + 11} - y_{n 1}) + (z_{n 2} - y_{n 2}) (y_{n + 12} - y_{n 2}) + \\ (z_{n 3} - y_{n 3}) (y_{n + 13} - y_{n 3})} \end{matrix}}{\sum_{n = 1}^{N} {{(y_{n + 11} - y_{n 1})}^{2} + {(y_{n + 12} - y_{n 2})}^{2} + {(y_{n + 13} - y_{n 3})}^{2}}}$ wherein y_nand z_nrefer to points in the first discrete curve and the second discrete curve, respectively;
  
  updating a cumulative rotational shift based on the estimated rotational shift;
  
  generating a rotationally shifted version of the second discrete curve based on the cumulative rotational shift;
  
  performing said estimating, said updating, and said generating in an iterative manner using the respective rotationally shifted discrete curve for each iteration until a stopping condition occurs, thereby determining a final estimate of the rotational shift between the first discrete curve and the second discrete curve; and
  
  storing the final estimate of the rotational shift, wherein the final estimate of the rotational shift is useable to perform discrete curve matching.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
National Instruments Corporation (Emerson Electric Company)
Original Assignee
National Instruments Corporation (Emerson Electric Company)
Inventors
Wenzel, Lothar
Primary Examiner(s)
Carter; Aaron W

Application Number

US11/851,477
Publication Number

US 20080031524A1
Time in Patent Office

431 Days
Field of Search

382/209, 382/289, 382/290, 382/296, 382/297
US Class Current

382/209
CPC Class Codes

G06V 10/32   Normalisation of the patter...

G06V 10/46   Descriptors for shape, cont...

G06V 10/471   using approximation functions

G06V 10/7515   Shifting the patterns to ac...

G06V 10/752   Contour matching

Increasing accuracy of discrete curve transform estimates for curve matching in higher dimensions

First Claim

5 Assignments

0 Petitions

Accused Products

Abstract

19 Citations

22 Claims

Specification

Solutions

Use Cases

Quick Links

Increasing accuracy of discrete curve transform estimates for curve matching in higher dimensions

First Claim

5 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

19 Citations

22 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links