Fuzzy method and device for the recognition of geometric shapes in images

• US 5,870,495 A
• Filed: 01/11/1996
• Issued: 02/09/1999
• Est. Priority Date: 01/13/1995
• Status: Expired due to Term

• Current Assignee: SGS-Thomson Microelectronics, S.R.L. (STMicroelectronics NV)
• Original Assignee: SGS-Thomson Microelectronics, S.R.L. (STMicroelectronics NV)
• Inventors: Moretti, Paolo, Rizzotto, Gianguido, Mancuso, Massimo, Poluzzi, Rinaldo
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/584,529
• Time in Patent Office: 1,125 Days
• Field of Search: 382/199, 382/155, 382/160, 382/201, 382/203, 395/3, 395/142
• US Class Current: 382/199
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

A method for recognizing geometric shapes in an image using fuzzy logic. The method includes determining an edge in the image and a gradient of the edge. The gradient is corrected by virtue of a first fuzzy logic process, and the number of points that belong to the curve are determined by virtue of a second fuzzy logic process. A fuzzy device for the recognition of geometric shapes in images that implementing the method includes an edge detector, a fuzzy gradient corrector to correct the gradient, and a fuzzy vote attributor to determine the number of points that belong to the curve.

Claims

1. A method for recognizing geometric shapes in images comprising the steps of:

recognizing at least one edge of a curve of an image;

recognizing a gradient of the at least one edge;

correcting the gradient using a first fuzzy logic process to determine the curve;

calculating a radius that is related to the at least one edge after the step of correcting the gradient; and

determining a number of points belonging to the curve using a second fuzzy logic process;

wherein the step of determining the number of points includes steps of

incrementing a value at a main memory location corresponding to the corrected gradient and the calculated radius, the value at the main memory location representing the number of points, and

incrementing values at additional memory locations related to the main memory location, the step of incrementing the values at the additional memory locations including a step of assigning a respective weight by which each value is incremented for each of the additional memory locations.

2. The method of claim 1, further comprising a step of creating image portions prior to the step of recognizing at least one edge.

3. The method of claim 1, further comprising a step of selecting a portion of a gradient image generated by the step of recognizing the gradient, wherein the correcting and determining steps are applied to the selected portion.

4. The method of claim 1, further comprising a step of digitizing the image prior to the step of recognizing at least one edge.

5. The method of claim 1, wherein the step of correcting the gradient includes a step of differentiating a gradient between a central pixel of a gradient image portion and pixels surrounding the central pixel of the gradient image portion.

6. The method of claim 5, wherein the step of differentiating produces a difference and the step of correcting the gradient includes a step of processing the difference using the first fuzzy logic process to produce the corrected gradient.

7. The method of claim 1 wherein the number of points belonging to the curve is a final sum of the value at the main memory location and a sum of respective weights by which the value at the main memory location is incremented when the main memory location is one of the additional memory locations.

8. A device for recognizing geometric shapes in an image comprising:

an edge detector, which recognizes at least one edge of a line of the image and determines a gradient of the at least one edge;

a fuzzy gradient corrector receiving and correcting the gradient;

an arithmetic unit to calculate a radius of the line, the line being related to the corrected gradient; and

a fuzzy vote attributor receiving the corrected gradient and determining a number of points in the image that belong to the line, wherein the fuzzy vote attributor includes a memory, and an address generator to generate a main memory location in the memory that is related to the corrected gradient and to the radius of the line.

9. The device of claim 8, further comprising a first interface to create portions of the image, an output of the first interface being connected to an input of the edge detector to provide the portions of the image to the edge detector.

10. The device of claim 8, further comprising a second interface interposed between the edge detector and the fuzzy gradient corrector to select a portion of a gradient image that is generated by the edge detector and to provide the portion of the gradient image to the fuzzy gradient corrector as the gradient.

11. The device of claim 8, wherein the fuzzy gradient corrector includes a differential block to calculate a difference between a gradient of a central pixel of the portion of the gradient image and a gradient of pixels surrounding the central pixel.

12. The device of claim 11, wherein the fuzzy gradient corrector further includes first fuzzy logic means for processing the difference and generating the corrected gradient.

13. The device of claim 8, wherein the fuzzy vote attributor further includes an address expander to identify additional memory locations that contain points of other lines close to the line associated with the main memory location.

14. The device of claim 13, wherein the fuzzy vote attributor further includes second fuzzy logic means to assign a respective weight for each one of the additional memory locations, to add each respective weight to the content of the main memory location to produce a final sum, and to output the final sum as the number of points belonging to the line.

15. The device of claim 8, further comprising an A/D converter, coupled to the edge detector, to digitize the input image and output the digitized image to the edge detector.

16. A method for recognizing geometric shapes in an image comprising the steps of:

detecting points on an edge of the image;

applying fuzzy logic to the points to determine at least one line including the points on the edge; and

applying fuzzy logic to the at least one line and the points to determine a number of points belonging to the at least one line;

wherein the step of detecting points on an edge of the image includes a step of producing a plurality of sets of parameters, each set of parameters corresponding to a respective one of the points;

wherein the step of determining the number of points belonging to the at least one line includes a step of determining a number of points having similar sets of parameters;

wherein each set of parameters corresponding to a respective one of the points defines a location on the edge of the image, each set of parameters also defining a curve that is coincident to the unique location an intersection of a first curve and a second curve determining the at least one line; and

wherein the step of applying fuzzy logic to the points includes a step of determining a number of curves that nearly intersect at the location.

17. The method of claim 16, further comprising, prior to the step of detecting, separating the image into a plurality of image portions.

18. The method of claim 16, wherein the step of detecting points on the edge of the image includes:

determining at least one gradient of the points on the edge of the image; and

correcting the at least one gradient using fuzzy logic.

19. The method of claim 18, wherein the step of determining includes:

determining a potential gradient for each point on the edge of the image; and

generating the at least one gradient based upon a comparison of the potential gradient of each point to at least one threshold value.

20. The method of claim 19, wherein the generating step includes:

generating the potential gradient as the at least one gradient when the potential gradient is greater than an upper threshold value;

discarding the potential gradient when the potential gradient is lower than a lower threshold value; and

generating the potential gradient as the at least one gradient when the potential gradient is lower than the upper threshold value and greater than the lower threshold value, and a potential gradient of a neighboring point is greater than the upper threshold value.

21. The method of claim 18, wherein the step of correcting the at least one gradient using fuzzy logic includes a step of adjusting a value of a gradient of a selected point based upon a gradient value of points that are aligned with the selected point.

22. The method of claim 18, further comprising a step of determining a radius corresponding to the at least one gradient.

23. The method of claim 16, wherein the step of determining the number of points having similar sets of parameters includes:

generating a memory location corresponding to each of the points based upon the corresponding set of parameters; and

incrementing a value at the memory location; and

wherein the step of determining the number of points belonging to the at least one line includes the step of outputting a value at the memory location as the number of points belonging to the at least one line.

24. The method of claim 23, wherein the step of incrementing the value at the memory location includes:

incrementing the value at the memory location by a predetermined amount when the memory location is generated; and

incrementing the value at the memory location by a weighted amount when the memory location has a corresponding set of parameters that is approximately equal to a set of parameters corresponding to the memory location.

25. A method for recognizing geometric shapes in an image comprising the steps of:

detecting points on an edge of the image;

applying fuzzy logic to the points to determine at least one line including the points on the edge; and

applying fuzzy logic to the at least one line and the points to determine a number of points belonging to the at least one line;

wherein the step of detecting points on an edge of the image includes a step of producing a plurality of sets of parameters, each set of parameters corresponding to a respective one of the points;

wherein the step of determining the number of points belonging to the at least one line includes a step of determining a number of points having similar sets of parameters;

wherein each set of parameters corresponds to a parameter curve representing a respective one of the points on the edge; and

wherein the step of determining the number of points having similar sets of parameters includes a step of applying fuzzy logic to determine a number of parameter curves intersecting at a substantially one location.

26. A device for recognizing geometric shapes in an image comprising:

an edge detector that determines points on an edge of the image and gradients of the points;

a fuzzy gradient corrector coupled to the edge detector to receive and to correct the gradients; and

a fuzzy vote attributor, coupled to the fuzzy gradient corrector to receive the corrected gradients, to determine a line representing the edge and to determine a number of points that belong to the edge, the fuzzy vote attributor including

a memory,

an address generator generating a memory address based upon a first of the corrected gradients and a radius associated with the first corrected gradient, the unique memory address describing a point on the edge, and

an address expander, the address expander receiving the first corrected gradient and the associated radius and generating additional memory addresses that are proximate to the memory address.

27. The device of claim 26, further comprising a first interface, the first interface receiving the image and splitting the image to create image portions that are provided to the edge detector for determining points on the edge.

28. The device of claim 26, further comprising a second interface coupled between the edge detector and the fuzzy gradient detector, the second interface receiving the gradients and selecting a gradient portion to provide to the fuzzy gradient corrector to be corrected.

29. The device of claim 26, wherein the fuzzy gradient corrector includes a differentiator that determines differences between a gradient of a central point and gradients of points surrounding the central point.

30. The device of claim 29, wherein the fuzzy gradient corrector further includes a first fuzzy logic device that performs fuzzy logic reasoning on the differences to produce the corrected gradient of the central point.

31. The device of claim 26, further comprising an arithmetic unit to determine radii corresponding to the gradients.

32. The device of claim 26, wherein the fuzzy vote attributor further includes a second fuzzy logic device that performs fuzzy logic reasoning on the additional memory addresses to produce a respective weight to be added to a content of each of the additional memory addresses.

33. The device of claim 32, wherein the fuzzy vote attributor further includes:

a first adder that increments a content of the memory address each time the memory address is generated; and

a second adder that adds the respective weight to the content of each of the additional memory addresses, the number of points that belong to the edge being a sum of the content of the memory address and the respective weight added to the content of the memory address when the memory address is an additional memory address.