Method and system for identifying an edge in an image

• US 8,971,637 B1
• Filed: 07/16/2012
• Issued: 03/03/2015
• Est. Priority Date: 07/16/2012
• Status: Active Grant

• Current Assignee: Matrox Electronic Systems Ltd.
• Original Assignee: Matrox Electronic Systems Ltd.
• Inventors: Rivard, Dominique
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US13/550,288
• Time in Patent Office: 960 Days
• Field of Search: 382/199, 382/266
• US Class Current: 382/199
• CPC Class Codes: G06T 7/13 Edge detection

Abstract

A method and system for identifying an edge in a portion of an image, the portion having an associated intensity variation. An edge candidate is detected at a local extremum of the intensity variation (i.e. at a position along the x-axis that corresponds to a peak or valley of the intensity variation). A local threshold associated with the edge candidate is computed on the basis of a slope tolerance and the slope value of the edge candidate, where this local threshold defines a boundary region for the edge candidate. If the edge candidate is determined to be a global extremum (i.e. the highest peak or lowest valley) within its respective boundary region, the edge candidate is verified as being an actual edge of the image portion. Identification of this verified edge may include determination of one or more of a plurality of characteristics of the edge.

Claims

1. A method for identifying with a computing unit an edge in a portion of an image, the portion of the image having an associated intensity variation, said method comprising:

a. identifying a position of an edge candidate and establishing a slope value from the intensity variation at said position;

b. if the slope value at said position is positive, calculating a local threshold associated with the edge candidate by subtracting a slope tolerance from the slope value at said position;

c. determining if the edge candidate corresponds to an actual edge by analysing the intensity variation within a boundary region extending on either side of the edge candidate'"'"'s position, said boundary region defined by the local threshold, wherein for a positive slope value at said position said determining includes identifying the edge candidate as an actual edge if each other position within the boundary region has a respective slope value that is smaller or equal to the slope value at said position;

d. if the edge candidate corresponds to an actual edge of the image portion, identifying the edge as located in the portion of the image.

2. A method as defined in claim 1, wherein if the slope value at said position is negative, said method comprises:

a. calculating the local threshold by adding the slope tolerance to the slope value at said position;

b. identifying the edge candidate as an actual edge if

each other position within the boundary region has a respective slope value that is greater or equal to the slope value at said position.

3. The method as defined in claim 1, further comprising identifying the edge candidate as an actual edge only if at least one position on either side of the edge candidate'"'"'s position is outside of the boundary region and has a slope value that is smaller than the local threshold.

4. The method as defined in claim 2, further comprising identifying the edge candidate as an edge only if at least one position on either side of the edge candidate'"'"'s position is outside of the boundary region and has a slope value that is greater than the local threshold.

5. The method as defined in claim 1, wherein if the edge candidate corresponds to an actual edge of the image portion, said method further comprises:

a. computing a second derivative of an intensity profile of the image portion;

b. identifying extrema of the second derivative and corresponding points of inflexion of the intensity variation;

c. applying an iteration of Newton'"'"'s method to the intensity variation from the points of inflexion, thereby identifying a start position and an end position of the actual edge within the portion of the image.

6. The method as defined in claim 1, wherein the slope tolerance used to compute the local threshold for each one of a plurality of different edge candidates is constant within the portion of the image.

7. The method as defined in claim 1, wherein said position is one at which the intensity variation is characterized by a local extremum.

8. The method as defined in claim 1, wherein said identifying a position of an edge candidate comprises comparing slope values at different positions of the intensity variation to a global threshold.

9. The method as defined in claim 1, wherein identifying the edge includes determining at least one characteristic of the edge.

10. The method as defined in claim 1, wherein the intensity variation is computed from an intensity profile associated with the portion of the image.

11. A non-transitory computer readable medium encoded with instructions that when executed by at least one processor implement a method for identifying an edge in a portion of an image, the portion of the image having an associated intensity variation, said method comprising:

a. identifying a position of an edge candidate and establishing a slope value from the intensity variation at said position;

b. if the slope value at said position is positive, calculating a local threshold for the edge candidate by subtracting a slope tolerance from the slope value at said position;

c. determining if the edge candidate corresponds to an actual edge of the image portion by analysing the intensity variation within a boundary region extending on either side of the edge candidate'"'"'s position, said boundary region defined by the local threshold, wherein for a positive slope value at said position said determining includes identifying the edge candidate as an actual edge if each other position within the boundary region has a respective slope value that is smaller or equal to the slope value at said position;

d. if the edge candidate corresponds to an actual edge of the image portion, identifying the edge as located in the portion of the image.

12. A method for identifying with a computing unit an edge in a portion of an image, the portion of the image having an associated intensity variation, said method comprising:

a. identifying a position of an edge candidate and establishing a slope value from the intensity variation at said position;

b. if the slope value at said position is negative, calculating a local threshold associated with the edge candidate by adding a slope tolerance to the slope value at said position;

c. determining if the edge candidate corresponds to an actual edge by analysing the intensity variation within a boundary region extending on either side of the edge candidate'"'"'s position, said boundary region defined by the local threshold, wherein for a negative slope value at said position said determining includes identifying the edge candidate as an actual edge if each other position within the boundary region has a respective slope value that is greater or equal to the slope value at said position;

d. if the edge candidate corresponds to an actual edge of the image portion, identifying the edge as located in the portion of the image.

13. A method as defined in claim 12, wherein if the slope value at said position is positive, said method comprises:

a. calculating the local threshold by subtracting the slope tolerance from the slope value at said position;

b. identifying the edge candidate as an actual edge if each other position within the boundary region has a respective slope value that is smaller or equal to the slope value at said position.

14. The method as defined in claim 13, further comprising identifying the edge candidate as an actual edge only if at least one position on either side of the edge candidate'"'"'s position is outside of the boundary region and has a slope value that is smaller than the local threshold.

15. The method as defined in claim 12, further comprising identifying the edge candidate as an edge only if at least one position on either side of the edge candidate'"'"'s position is outside of the boundary region and has a slope value that is greater than the local threshold.

16. The method as defined in claim 12, wherein if the edge candidate corresponds to an actual edge of the image portion, said method further comprises:

a. computing a second derivative of an intensity profile of the image portion;

b. identifying extrema of the second derivative and corresponding points of inflexion of the intensity variation;

c. applying an iteration of Newton'"'"'s method to the intensity variation from the points of inflexion, thereby identifying a start position and an end position of the actual edge within the portion of the image.

17. The method as defined in claim 12, wherein the slope tolerance used to compute the local threshold for each one of a plurality of different edge candidates is constant within the portion of the image.

18. The method as defined in claim 12, wherein said position is one at which the intensity variation is characterized by a local extremum.

19. The method as defined in claim 12, wherein said identifying a position of an edge candidate comprises comparing slope values at different positions of the intensity variation to a global threshold.

20. The method as defined in claim 12, wherein identifying the edge includes determining at least one characteristic of the edge.

21. The method as defined in claim 12, wherein the intensity variation is computed from an intensity profile associated with the portion of the image.

22. A method for identifying with a computing unit an edge in a portion of an image, the portion of the image having an associated intensity variation, said method comprising:

a. identifying a position of an edge candidate and determining a slope value from the intensity variation at said position;

b. calculating a local threshold associated with the edge candidate on a basis of a slope tolerance and from the slope value at said position;

c. determining if the edge candidate corresponds to an actual edge by analysing the intensity variation within a boundary region extending on either side of the edge candidate'"'"'s position, said boundary region defined by the local threshold;

d. if the edge candidate corresponds to an actual edge of the image portion;

i. identifying the edge as located in the portion of the image;

ii. computing a second derivative of an intensity profile of the image portion;

iii. identifying extrema of the second derivative and corresponding points of inflexion of the intensity variation;

iv. applying an iteration of Newton'"'"'s method to the intensity variation from the points of inflexion, thereby identifying a start position and an end position of the actual edge within the portion of the image.

23. The method as defined in claim 22, wherein the slope tolerance used to compute the local threshold for each one of a plurality of different edge candidates is constant within the portion of the image.

24. The method as defined in claim 22, wherein said position is one at which the intensity variation is characterized by a local extremum.

25. The method as defined in claim 22, wherein said identifying a position of an edge candidate comprises comparing slope values at different positions of the intensity variation to a global threshold.

26. The method as defined in claim 22, wherein identifying the edge includes determining at least one characteristic of the edge.

27. The method as defined in claim 22, wherein the intensity variation is computed from the intensity profile associated with the portion of the image.

28. A non-transitory computer readable medium encoded with instructions that when executed by at least one processor implement a method for identifying an edge in a portion of an image, the portion of the image having an associated intensity variation, said method comprising:

a. identifying a position of an edge candidate and establishing a slope value from the intensity variation at said position;

b. if the slope value at said position is negative, calculating a local threshold for the edge candidate by adding a slope tolerance to the slope value at said position;

c. determining if the edge candidate corresponds to an actual edge of the image portion by analysing the intensity variation within a boundary region extending on either side of the edge candidate'"'"'s position, said boundary region defined by the local threshold, wherein for a negative slope value at said position said determining includes identifying the edge candidate as an actual edge if each other position within the boundary region has a respective slope value that is greater or equal to the slope value at said position;

d. if the edge candidate corresponds to an actual edge of the image portion, identifying the edge as located in the portion of the image.

29. A non-transitory computer readable medium encoded with instructions that when executed by at least one processor implement a method for identifying an edge in a portion of an image, the portion of the image having an associated intensity variation, said method comprising:

a. identifying a position of an edge candidate and determining a slope value from the intensity variation at said position;

b. calculating a local threshold associated with the edge candidate on a basis of a slope tolerance and from the slope value at said position;

c. determining if the edge candidate corresponds to an actual edge of the image portion by analysing the intensity variation within a boundary region extending on either side of the edge candidate'"'"'s position, said boundary region defined by the local threshold;

d. if the edge candidate corresponds to an actual edge of the image portion;

i. identifying the edge as located in the portion of the image;

ii. computing a second derivative of an intensity profile of the image portion;

iii. identifying extrema of the second derivative and corresponding points of inflexion of the intensity variation;

iv. applying an iteration of Newton'"'"'s method to the intensity variation from the points of inflexion, thereby identifying a start position and an end position of the actual edge within the portion of the image.