Circular Object Identification System

• US 20130259386A1
• Filed: 05/17/2012
• Published: 10/03/2013
• Est. Priority Date: 03/30/2012
• Status: Active Grant

• Current Assignee: LTIMindtree Ltd. (Larsen & Toubro Limited)
• Original Assignee: Mindtree Limited (Larsen & Toubro Limited)
• Inventors: Chandrashekar, Puneeth Bilagunda, Saha, Sharmila
• Granted Patent: US 8,811,675 B2
• Time in Patent Office: Days
• US Class Current: 382/203
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

A computer implemented method and system determines a center point of a circular object in an image. A circular object identification system identifies prospective center points of the circular object for each of multiple pixel points at a predetermined distance along a gradient direction determined for each of the pixel points, constructs an axis between the corresponding prospective center points and a corresponding pixel point, and locates prospective circumference points at predetermined angles from the constructed axis. The circular object identification system compares the gradient direction of each of the prospective circumference points with a direction defined by each of the prospective circumference points and a corresponding prospective center point to find a match, determines convergence of the gradient direction of each of the prospective circumference points to a corresponding prospective center point, and determines the center point based on resultant decision votes of each of the prospective center points.

Claims

1. A computer implemented method for determining a center point of a circular object in an image, said method employing a computer system comprising at least one processor communicatively coupled to a non-transitory computer readable storage medium that stores instructions executable by said at least one processor, said at least one processor configured to implement said method, said method comprising:

determining a gradient direction for each of a plurality of pixel points in said image, wherein said gradient direction defines an angular orientation related to a change in intensity at said each of said pixel points with respect to a reference axis;

identifying prospective center points of said circular object for said each of said pixel points at a predetermined distance along said gradient direction of said each of said pixel points, and constructing an axis that joins corresponding said prospective center points and a corresponding pixel point of said each of said pixel points;

locating prospective circumference points among said pixel points at predetermined angles from said constructed axis for said corresponding pixel point, wherein said prospective circumference points are at said predetermined distance from a corresponding one of said prospective center points;

comparing said gradient direction of each of said prospective circumference points with a direction defined by said each of said prospective circumference points and said corresponding one of said prospective center points, with respect to said reference axis to find a match;

determining convergence of said gradient direction of said each of said prospective circumference points to said corresponding one of said prospective center points on finding said match, for establishing that said each of said prospective circumference points lies on a circumference of said circular object;

assigning a decision vote to said corresponding one of said prospective center points based on said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points to said corresponding one of said prospective center points;

determining number of resultant decision votes assigned to each of said prospective center points identified for said each of said pixel points in said image by counting each said decision vote assigned to said each of said prospective center points; and

determining said center point of said circular object from said prospective center points identified for said pixel points in said image based on said determined number of said resultant decision votes assigned to said each of said prospective center points.

2. The computer implemented method of claim 1, wherein said determined center point of said circular object is one of said prospective center points with a highest said number of said resultant decision votes.

3. The computer implemented method of claim 1, wherein said determined center point of said circular object is one of said prospective center points when a weighted average of said resultant decision votes assigned to said one of said prospective center points is greater than a predetermined threshold.

4. The computer implemented method of claim 1, further comprising storing said each said decision vote assigned to said corresponding one of said prospective center points for said each of said pixel points in an accumulator array, wherein said storage of said each said decision vote assigned to said corresponding one of said prospective center points in said accumulator array comprises:

identifying a first local neighborhood of said pixel points around said each of said prospective center points;

identifying a second local neighborhood of said pixel points around said each of said prospective circumference points;

determining convergence of said gradient direction of said each of said prospective circumference points and each of said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points, by traversing said predetermined distance from said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to reach said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood;

assigning a local vote to said corresponding one of said prospective center points based on each said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points and said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood; and

adding said decision vote to said corresponding one of said prospective center points in said accumulator array when number of resultant local votes assigned to said corresponding one of said prospective center points determined by counting each said local vote assigned to said corresponding one of said prospective center points is greater than a predetermined vote count threshold.

5. The computer implemented method of claim 4, further comprising comparing said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with a direction defined by said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with said corresponding one of said prospective center points, with respect to said reference axis to find a match, wherein said convergence of said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points is determined on finding said match.

6. The computer implemented method of claim 4, wherein said decision vote is added to each of said corresponding said prospective center points in said accumulator array, when said resultant local votes assigned to said each of said corresponding said prospective center points are equal.

7. The computer implemented method of claim 4, wherein said decision vote is added to one of said corresponding said prospective center points in said accumulator array, when said resultant local votes assigned to said one of said corresponding said prospective center points are greater than said resultant local votes assigned to another of said corresponding said prospective center points.

8. The computer implemented method of claim 1, wherein said predetermined distance for identifying said prospective center points of said circular object for said each of said pixel points is selected from a plurality of radius ranges defined for said circular object.

9. The computer implemented method of claim 1, further comprising setting a center threshold for a number of said resultant decision votes that qualifies one of said prospective center points as said center point of said circular object.

10. A computer implemented method for determining a center point of a circular object in an image, said method employing a computer system comprising at least one processor communicatively coupled to a non-transitory computer readable storage medium that stores instructions executable by said at least one processor, said at least one processor configured to implement said method, said method comprising:

determining a gradient direction for each of a plurality of pixel points in said image, wherein said gradient direction defines an angular orientation related to a change in intensity at said each of said pixel points with respect to a reference axis;

identifying prospective center points of said circular object for said each of said pixel points at a predetermined distance along said gradient direction of said each of said pixel points, and constructing an axis that joins corresponding said prospective center points and a corresponding pixel point of said each of said pixel points;

identifying a first local neighborhood of said pixel points around each of said prospective center points;

locating prospective circumference points among said pixel points at predetermined angles from said constructed axis for said corresponding pixel point, wherein said prospective circumference points are at said predetermined distance from a corresponding one of said prospective center points;

identifying a second local neighborhood of said pixel points around said each of said prospective circumference points;

determining convergence of said gradient direction of said each of said prospective circumference points and each of said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points, by traversing said predetermined distance from said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to reach said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood;

assigning a local vote to said corresponding one of said prospective center points based on each said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points and said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood;

adding a decision vote to said corresponding one of said prospective center points in an accumulator array when number of resultant local votes assigned to said corresponding one of said prospective center points determined by counting each said local vote assigned to said corresponding one of said prospective center points is greater than a predetermined vote count threshold;

determining number of resultant decision votes assigned to each of said prospective center points identified for said each of said pixel points in said image by counting each said decision vote assigned to said each of said prospective center points; and

determining said center point of said circular object from said prospective center points identified for said pixel points in said image based on said determined number of said resultant decision votes assigned to said each of said prospective center points.

11. The computer implemented method of claim 10, further comprising comparing said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with a direction defined by said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with said corresponding one of said prospective center points, with respect to said reference axis to find a match, wherein said convergence of said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points is determined on finding said match.

12. The computer implemented method of claim 10, wherein said determined center point of said circular object is one of said prospective center points with a highest said number of said resultant decision votes.

13. The computer implemented method of claim 10, wherein said determined center point of said circular object is one of said prospective center points when a weighted average of said resultant decision votes assigned to said one of said prospective center points is greater than a predetermined threshold.

14. The computer implemented method of claim 10, wherein said decision vote is added to each of said corresponding said prospective center points in said accumulator array, when said resultant local votes assigned to said each of said corresponding said prospective center points are equal.

15. The computer implemented method of claim 10, wherein said decision vote is added to one of said corresponding said prospective center points in said accumulator array, when said resultant local votes assigned to said one of said corresponding said prospective center points are greater than said resultant local votes assigned to another of said corresponding said prospective center points.

16. A computer implemented method for identifying a circular object in an image, said method employing a computer system comprising at least one processor communicatively coupled to a non-transitory computer readable storage medium that stores instructions executable by said at least one processor, said at least one processor configured to implement said method, said method comprising:

determining a gradient direction for each of a plurality of pixel points in said image, wherein said gradient direction defines an angular orientation related to a change in intensity at said each of said pixel points with respect to a reference axis;

identifying prospective center points of said circular object for said each of said pixel points at a predetermined distance along said gradient direction of said each of said pixel points, and constructing an axis that joins corresponding said prospective center points and a corresponding pixel point of said each of said pixel points;

locating prospective circumference points among said pixel points at predetermined angles from said constructed axis for said corresponding pixel point, wherein said prospective circumference points are at said predetermined distance from a corresponding one of said prospective center points;

comparing said gradient direction of each of said prospective circumference points with a direction defined by said each of said prospective circumference points and said corresponding one of said prospective center points, with respect to said reference axis to find a match;

determining convergence of said gradient direction of said each of said prospective circumference points to said corresponding one of said prospective center points on finding said match, for establishing that said each of said prospective circumference points lies on a circumference of said circular object;

assigning a decision vote to said corresponding one of said prospective center points based on said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points to said corresponding one of said prospective center points;

determining number of resultant decision votes assigned to each of said prospective center points identified for said each of said pixel points in said image by counting each said decision vote assigned to said each of said prospective center points;

determining said center point of said circular object from said prospective center points identified for said pixel points in said image based on said determined number of said resultant decision votes assigned to said each of said prospective center points;

identifying each of said pixel points at said predetermined distance from said determined center point, that contributes each said decision vote to said determined center point of said circular object;

determining an angle range that defines a curvature and a magnitude of said circular object by generating an angle histogram of said identified each of said pixel points; and

correlating said resultant decision votes assigned to said determined center point of said circular object with said angle range determined from said angle histogram for identifying said circular object in said image.

17. The computer implemented method of claim 16, further comprising storing said each said decision vote assigned to said corresponding one of said prospective center points for said each of said pixel points in an accumulator array, wherein said storage of said each said decision vote assigned to said corresponding one of said prospective center points in said accumulator array comprises:

identifying a first local neighborhood of said pixel points around said each of said prospective center points;

identifying a second local neighborhood of said pixel points around said each of said prospective circumference points;

determining convergence of said gradient direction of said each of said prospective circumference points and each of said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points, by traversing said predetermined distance from said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to reach said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood;

assigning a local vote to said corresponding one of said prospective center points based on each said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points and said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood; and

adding said decision vote to said corresponding one of said prospective center points in said accumulator array when number of resultant local votes assigned to said corresponding one of said prospective center points determined by counting each said local vote assigned to said corresponding one of said prospective center points is greater than a predetermined vote count threshold.

18. The computer implemented method of claim 17, further comprising comparing said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with a direction defined by said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with said corresponding one of said prospective center points, with respect to said reference axis to find a match, wherein said convergence of said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points is determined on finding said match.

19. The computer implemented method of claim 16, wherein said determination of said angle range comprises:

determining a number of local votes contributed by said identified each of said pixel points to said determined center point;

mapping said number of said local votes contributed by said identified each of said pixel points to a predetermined angle measure; and

determining said angle range using each said predetermined angle measure with a non-zero number of said local votes.

20. The computer implemented method of claim 19, further comprising comparing an average number of said local votes for said angle range with a predetermined angle threshold for validating said circular object in said image.

21. The computer implemented method of claim 16, wherein said curvature of said circular object determines a type of said circular object based on said angle range.

22. The computer implemented method of claim 16, further comprising determining a number of said pixel points associated with each of an upper surface and a lower surface of said circular object in said image and comparing said number of said pixel points associated with said upper surface of said circular object with said number of said pixel points associated with said lower surface of said circular object for identifying a type of said circular object.

23. The computer implemented method of claim 16, further comprising determining characteristics of a first said circular object and one or more second circular objects associated with said first said circular object to classify a device associated with said first said circular object and said one or more second circular objects in said image.

24. The computer implemented method of claim 23, wherein said characteristics of said first said circular object and said one or more second circular objects comprise one or more of a radius of each of said first said circular object and said one or more second circular objects, a number of said one or more second circular objects, and a distance between said first said circular object and each of said one or more second circular objects.

25. A computer implemented system for determining a center point of a circular object in an image, comprising:

at least one processor;

a non-transitory computer readable storage medium communicatively coupled to said at least one processor, said non-transitory computer readable storage medium storing modules of said computer implemented system that are executable by said at least one processor, said modules comprising;

a gradient direction determination module that determines a gradient direction for each of a plurality of pixel points in said image, wherein said gradient direction defines an angular orientation related to a change in intensity at said each of said pixel points with respect to a reference axis;

a point determination module that performs;

identifying prospective center points of said circular object for said each of said pixel points at a predetermined distance along said gradient direction of said each of said pixel points;

constructing an axis joining corresponding said prospective center points and a corresponding pixel point of said each of said pixel points; and

locating prospective circumference points among said pixel points at predetermined angles from said constructed axis for said corresponding pixel point, wherein said prospective circumference points are at said predetermined distance from a corresponding one of said prospective center points;

a comparison module that compares said gradient direction of each of said prospective circumference points with a direction defined by said each of said prospective circumference points and said corresponding one of said prospective center points, with respect to said reference axis to find a match;

a convergence determination module that determines convergence of said gradient direction of said each of said prospective circumference points to said corresponding one of said prospective center points on finding said match, for establishing that said each of said prospective circumference points lies on a circumference of said circular object;

a vote assignment module that assigns a decision vote to said corresponding one of said prospective center points based on said determination of said convergence of said gradient direction of said each of one or more of said prospective circumference points to said corresponding one of said prospective center points;

said vote assignment module that determines number of resultant decision votes assigned to each of said prospective center points identified for said each of said pixel points in said image by counting each said decision vote assigned to said each of said prospective center points; and

said point determination module in communication with said vote assignment module that determines said center point of said circular object from said prospective center points identified for said pixel points in said image based on said determined number of said resultant decision votes assigned to said each of said prospective center points.

26. The computer implemented system of claim 25, wherein said vote assignment module, in communication with said point determination module and said convergence determination module, stores said each said decision vote assigned to said corresponding one of said prospective center points for said each of said pixel points in an accumulator array.

27. The computer implemented system of claim 25, wherein said point determination module identifies a first local neighborhood of said pixel points around said each of said prospective center points, and a second local neighborhood of said pixel points around said each of said prospective circumference points.

28. The computer implemented system of claim 27, wherein said convergence determination module, in communication with said point determination module, determines convergence of said gradient direction of said each of said prospective circumference points and each of said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points, by traversing said predetermined distance from said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to reach said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood.

29. The computer implemented system of claim 28, wherein said comparison module compares said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with a direction defined by said each of said prospective circumference points and said each of said pixel points in said second local neighborhood with said corresponding one of said prospective center points, with respect to said reference axis to find a match, and wherein said convergence determination module, in communication with said comparison module, determines said convergence of said gradient direction of said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points, on finding said match.

30. The computer implemented system of claim 28, wherein said vote assignment module, in communication with said convergence determination module, performs:

assigning a local vote to said corresponding one of said prospective center points based on each said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points and said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood; and

adding said decision vote to said corresponding one of said prospective center points in said accumulator array when number of resultant local votes assigned to said corresponding one of said prospective center points determined by counting each said local vote assigned to said corresponding one of said prospective center points is greater than a predetermined vote count threshold.

31. The computer implemented system of claim 30, wherein said vote assignment module adds said decision vote to each of said corresponding said prospective center points in said accumulator array, when said resultant local votes assigned to said each of said corresponding said prospective center points are equal.

32. The computer implemented system of claim 30, wherein said vote assignment module adds said decision vote to one of said corresponding said prospective center points in said accumulator array, when said resultant local votes assigned to said one of said corresponding said prospective center points are greater than said resultant local votes assigned to another of said corresponding said prospective center points.

33. The computer implemented system of claim 25, wherein said modules further comprises a threshold setting module that sets a center threshold for a number of said resultant decision votes that qualifies one of said prospective center points as said center point of said circular object.

34. The computer implemented system of claim 25, wherein said point determination module selects said predetermined distance for identifying said prospective center points of said circular object for said each of said pixel points from a plurality of radius ranges defined for said circular object.

35. The computer implemented system of claim 25, wherein said modules further comprise a circular object identification module, in communication with said vote assignment module, that performs:

determining an angle range that defines a curvature and a magnitude of said circular object by generating an angle histogram of each of said pixel points identified at said predetermined distance from said determined center point, that contributes each said decision vote to said determined center point of said circular object; and

correlating said resultant decision votes assigned to said determined center point of said circular object with said angle range determined from said angle histogram for identifying said circular object in said image.

36. The computer implemented system of claim 35, wherein said circular object identification module, in communication with said vote assignment module, performs:

determining a number of local votes contributed by said identified each of said pixel points to said determined center point;

mapping said number of said local votes contributed by said identified each of said pixel points to a predetermined angle measure;

determining said angle range using each said predetermined angle measure with a non-zero number of said local votes; and

comparing an average number of said local votes for said angle range with a predetermined angle threshold for validating said circular object in said image.

37. The computer implemented system of claim 25, wherein said point determination module determines a number of said pixel points associated with each of an upper surface and a lower surface of said circular object in said image and compares said number of said pixel points associated with said upper surface of said circular object with said number of said pixel points associated with said lower surface of said circular object for identifying a type of said circular object.

38. The computer implemented system of claim 25, wherein said modules further comprise a characteristics determination module that determines characteristics of a first said circular object and one or more second circular objects associated with said first said circular object to classify a device associated with said first said circular object and said one or more second circular objects in said image, wherein said characteristics of said first said circular object and said one or more second circular objects comprise one or more of a radius of each of said first said circular object and said one or more second circular objects, a number of said one or more second circular objects, and a distance between said first said circular object and each of said one or more second circular objects.

39. A computer program product comprising a non-transitory computer readable storage medium, said non-transitory computer readable storage medium storing computer program codes comprising instructions executable by at least one processor, said computer program codes comprising:

a first computer program code for determining a gradient direction for each of a plurality of pixel points in an image, wherein said gradient direction defines an angular orientation related to a change in intensity at said each of said pixel points with respect to a reference axis;

a second computer program code for identifying prospective center points of a circular object for said each of said pixel points at a predetermined distance along said gradient direction of said each of said pixel points;

a third computer program code for constructing an axis that joins corresponding said prospective center points and a corresponding pixel point of said each of said pixel points;

a fourth computer program code for locating prospective circumference points among said pixel points at predetermined angles from said constructed axis for said corresponding pixel point, wherein said prospective circumference points are at said predetermined distance from a corresponding one of said prospective center points;

a fifth computer program code for comparing said gradient direction of each of said prospective circumference points with a direction defined by said each of said prospective circumference points and said corresponding one of said prospective center points, with respect to said reference axis to find a match;

a sixth computer program code for determining convergence of said gradient direction of said each of said prospective circumference points to said corresponding one of said prospective center points on finding said match, for establishing that said each of said prospective circumference points lies on a circumference of said circular object;

a seventh computer program code for assigning a decision vote to said corresponding one of said prospective center points based on said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points to said corresponding one of said prospective center points;

an eighth computer program code for determining number of resultant decision votes assigned to each of said prospective center points identified for said each of said pixel points in said image by counting each said decision vote assigned to said each of said prospective center points; and

a ninth computer program code for determining said center point of said circular object from said prospective center points identified for said pixel points in said image based on said determined number of said resultant decision votes assigned to said each of said prospective center points.

40. The computer program product of claim 39, further comprising:

a tenth computer program code for identifying a first local neighborhood of said pixel points around said each of said prospective center points and a second local neighborhood of said pixel points around said each of said prospective circumference points;

an eleventh computer program code for determining convergence of said gradient direction of said each of said prospective circumference points and each of said pixel points in said second local neighborhood to one of a corresponding one of said prospective center points and any of said pixel points in said first local neighborhood around said corresponding one of said prospective center points, by traversing said predetermined distance from said each of said prospective circumference points and said each of said pixel points in said second local neighborhood to reach said one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood;

a twelfth computer program code for assigning a local vote to said corresponding one of said prospective center points based on each said determination of said convergence of said gradient direction of each of one or more of said prospective circumference points and said pixel points in said second local neighborhood to one of said corresponding one of said prospective center points and said any of said pixel points in said first local neighborhood; and

a thirteenth computer program code for adding said decision vote to said corresponding one of said prospective center points in said accumulator array when number of resultant local votes assigned to said corresponding one of said prospective center points determined by counting each said local vote assigned to said corresponding one of said prospective center points is greater than a predetermined vote count threshold.

41. The computer program product of claim 39, further comprising:

a fourteenth computer program code for identifying each of said pixel points at said predetermined distance from said determined center point, that contributes each said decision vote to said determined center point of said circular object;

a fifteenth computer program code for determining an angle range that defines a curvature and a magnitude of said circular object by generating an angle histogram of said identified each of said pixel points; and

a sixteenth computer program code for correlating said resultant decision votes assigned to said determined center point of said circular object with said angle range determined from said angle histogram for identifying said circular object in said image.