Cartesian to polar coordinate transformation

• US 6,064,388 A
• Filed: 11/10/1997
• Issued: 05/16/2000
• Est. Priority Date: 11/10/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Reyzin, Igor
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US08/967,683
• Time in Patent Office: 918 Days
• Field of Search: 345/418, 345/419, 345/428
• US Class Current: 345/418
• CPC Class Codes: G06F 7/548 Trigonometric functions; Co-ordinate transformations

Abstract

In an improved Cartesian to polar coordinate transformation, a Cartesian system of discrete data elements is converted to a polar system of discrete data elements. Each Cartesian element is divided into subelements and one of the subelements is designated as the polar system origin. A polar system comprising an intersecting plurality of radial sector lines and a plurality of confocal arcs formed of the subelements is defined about the origin. The lines and arcs define boundaries of polar data elements. The subelements lying within the polar element boundaries are identified and their respective data values are derived from the data values of corresponding Cartesian elements. Polar element data values are calculated based on the data values of the subelements contributing to the polar element. The present transformation technique offers the advantage of few floating point operations and provides a computationally efficient conversion system readily adaptive to changes in system parameters.

Claims

1. A method for converting a Cartesian system of discrete data elements to a polar system of discrete data elements, each Cartesian element having a corresponding data value, comprising:

dividing each Cartesian element into subelements;

designating one of the subelements as a polar system origin;

defining a polar system about said origin comprising an intersecting plurality of radial sector lines and a plurality of confocal arcs formed of said subelements, said sector lines and arcs defining boundaries of polar elements;

for each subelement within the boundaries of a polar element, determining a subelement data value derived from the data value of the Cartesian element from which the subelement was divided; and

calculating a data value for each polar element based on the data values of the subelements within the boundaries of the polar element.

2. The method of claim 1 wherein dividing comprises dividing each element into 2²ⁿ subelements, where n represents subelement resolution.

3. The method of claim 2 where n is a positive integer selected from the set of positive integers consisting of { 0, 1, 2, 3, . . . }.

4. The method of claim 1 wherein dividing comprises dividing the Cartesian elements into 2²ⁿ Cartesian subelements, and wherein designating a polar system origin comprises designating a Cartesian element having coordinates (2^n-, 2^n-1) in subelement space as the polar system origin.

5. The method of claim 1 wherein each polar element is defined by inner and outer arc boundaries and first and second sector line boundaries, and wherein the subelements within the boundaries of the polar element include the subelements corresponding to one of the inner and outer arc boundaries and one of the first and second sector line boundaries.

6. The method of claim 5 wherein the subelements within the boundaries of the polar element correspond to the outer arc and the furthest counter-clockwise sector line.

7. The method of claim 1 wherein determining a subelement data value for each subelement within the boundaries of each polar element comprises:

converting the Cartesian coordinates of each subelement to the coordinates of the element from which the subelement was divided; and

determining the data value of the element.

8. The method of claim 1 further comprising:

dividing the polar system into symmetrical radial segments;

designating one of the polar system segments as a working segment; and

defining the polar system arcs in the working segment.

9. The method of claim 8, further comprising:

mapping each sector line not within the working segment from an original segment into the working segment, said arcs and mapped sector lines defining boundaries of a mapped polar element;

for each subelement within the boundaries of a mapped polar element, mapping the subelements to the original segment and determining a subelement data value derived from the data value of the Cartesian element in the original segment from which the subelement was divided.

10. The method of claim 8 wherein the symmetrical radial segments comprise octants.

11. The method of claim 1 further comprising determining the number of sector lines and polar arcs from the resolution of the polar system.

12. The method of claim 1 wherein the elements comprise image pixels.

13. An image-processing system for converting a Cartesian system of discrete data elements to a polar system of discrete data elements comprising:

an input that receives a source array of discrete data elements indexed by Cartesian coordinates, each Cartesian element having a corresponding data value; and

a processing subsystem comprising a processor and a memory, the processor operating under the control of a program stored in the memory to;

divide each Cartesian element into subelements, each subelement indexed by its own Cartesian coordinates;

designate one of the subelements as a polar system origin;

define a polar system about said origin including an intersecting plurality of radial sector lines and a plurality of confocal arcs formed of said subelements, said sector lines and arcs defining boundaries of polar elements;

for each subelement within the boundaries of a polar element, determine a subelement data value derived from the data value of the Cartesian element from which the subelement was divided;

calculate a data value for each polar element based on the data values of the subelements within the boundaries of the polar element; and

store each polar element data value in memory.

14. The system of claim 13 wherein the processing subsystem further divides each element into 2²ⁿ subelements, where n represents the resolution of the conversion.

15. The system of claim 14 where n is a positive integer selected from the set of positive integers consisting of {0, 1, 2, 3, . . . }.

16. The system of claim 13 wherein the Cartesian elements are divided into 2ⁿ Cartesian subelements and wherein the processing subsystem further designates a Cartesian element having coordinates (2^n-1, 2^n-1) in subelement space as the polar system origin.

17. The system of claim 13 wherein each polar element is defined by inner and outer arc boundaries and first and second sector line boundaries, and wherein the subelements within the boundaries of the polar element include the subelements corresponding to one of the inner and outer arc boundaries and one of the first and second sector line boundaries.

18. The system of claim 17 wherein the subelements within the boundaries of the polar element correspond to the outer arc and the furthest counter-clockwise sector line.

19. The system of claim 13 wherein the processing subsystem determines a subelement data value for each subelement within the boundaries of each polar element by:

converting the Cartesian coordinates of each subelement to the coordinates of the element from which the subelement was divided; and

determining the data value of the element.

20. The system of claim 13 wherein the processing subsystem further:

divides the polar system into symmetrical radial segments;

designates one of the polar system segments as a working segment; and

defines the polar system arcs in the working segment.

21. The system of claim 20 wherein the processing subsystem further:

maps each sector line not within the working segment from an original segment into the working segment, said arcs and mapped sector lines defining boundaries of a mapped polar element; and

for each subelement within the boundaries of a mapped polar element, maps the subelements to the original segment and determines a subelement data value derived from the data value of the Cartesian element in the original segment from which the subelement was divided.

22. The system of claim 20 wherein the symmetrical radial segments comprise octants.

23. A method for converting a pixel image array arranged as a Cartesian system of discrete data elements to an image array arranged as a polar system of discrete data elements, each Cartesian element having a corresponding data value, comprising:

sensing an image at a sensor comprising an array of pixels;

storing said image in a memory as an array of discrete data elements indexed by Cartesian coordinates;

dividing each Cartesian element into subelements;

designating one of the subelements as a polar system origin;

defining a polar system about said origin comprising an intersecting plurality of radial sector lines and a plurality of confocal arcs formed of said subelements, said sector lines and arcs defining boundaries of polar elements;

for each subelement within the boundaries of a polar element, determining a subelement data value derived from the data value of the Cartesian element from which the subelement was divided;

calculating a data value for each polar element based on the data values of the subelements within the boundaries of the polar element; and

storing the polar element data values in memory.