Fast dominant circle detection through horizontal and vertical scanning
First Claim
Patent Images
1. A method for determining a circle in a region of interest comprising the steps of:
- extracting a first pair of edge points along an x-axis of the region of interest;
extracting a second pair of edge points along a y-axis of the region of interest;
determining an intersection of a first and second line extending perpendicular from a pair of midpoints of the first and second pair of edge points respectively;
determining a radius from the intersection to any edge point;
verifying a connectivity of the first and second pair of edge points in the presence of a foreign structure in the region of interest, wherein verifying comprises;
scanning the image along the x-axis of the region of interest, scanning the image along the v-axis of the region of interest, performing a horizontal gradient and a vertical gradient along the x and y-axis of the region of interest respectively, and determining whether a local maximum along the gradients match the coordinates for any edge point comprising;
determining a position, relative to the circle of the foreign structure, wherein if the foreign structure is inside, searching from each edge of the region of interest, inward, to determine the local maximum, if the foreign structure is outside, searching from the center of the region of interest, outward, to determine the local maximum, and if the foreign structure is both inside and outside the circle, randomly scan at a plurality of points each axis of the region of interest within ½
of the total axis length, conduct a gradient operation at each point scanned, determine a plurality of potential edge points, determine a coordinate for center of the circle, save the coordinate in an array, determine, based on the plurality of edge points a median value for each coordinate of the center of the circle; and
determining the circle upon verifying the connectivity of the first and second pair of edge points.
2 Assignments
0 Petitions
Accused Products
Abstract
A method for determining a circle in an image is disclosed. The method extracts a first pair of edge points along an x-axis of the image, extracts a second pair of edge points along a y-axis of the image, determines an intersection of a first and second line extending perpendicular from a pair of midpoints of the first and second pair of edge points respectively, and determines a radius from the intersection to any edge point.
48 Citations
15 Claims
-
1. A method for determining a circle in a region of interest comprising the steps of:
-
extracting a first pair of edge points along an x-axis of the region of interest;
extracting a second pair of edge points along a y-axis of the region of interest;
determining an intersection of a first and second line extending perpendicular from a pair of midpoints of the first and second pair of edge points respectively;
determining a radius from the intersection to any edge point;
verifying a connectivity of the first and second pair of edge points in the presence of a foreign structure in the region of interest, wherein verifying comprises;
scanning the image along the x-axis of the region of interest, scanning the image along the v-axis of the region of interest, performing a horizontal gradient and a vertical gradient along the x and y-axis of the region of interest respectively, and determining whether a local maximum along the gradients match the coordinates for any edge point comprising;
determining a position, relative to the circle of the foreign structure, wherein if the foreign structure is inside, searching from each edge of the region of interest, inward, to determine the local maximum, if the foreign structure is outside, searching from the center of the region of interest, outward, to determine the local maximum, and if the foreign structure is both inside and outside the circle, randomly scan at a plurality of points each axis of the region of interest within ½
of the total axis length, conduct a gradient operation at each point scanned, determine a plurality of potential edge points, determine a coordinate for center of the circle, save the coordinate in an array, determine, based on the plurality of edge points a median value for each coordinate of the center of the circle; and
determining the circle upon verifying the connectivity of the first and second pair of edge points. - View Dependent Claims (2, 3, 4, 5, 15)
-
-
6. A method for determining a circle in an image, comprising the steps of:
-
extracting a first pair of edge points along an x-axis of the image;
extracting a second pair of edge points along a y-axis of the image;
determining an intersection of a first and second line extending perpendicular from a pair of midpoints of the first and second pair of edge points respectively;
verifying each edge point by verifying a connectivity of adjacent edge points in a gradient array of the image in the presence of a foreign structure visible in the image, wherein verifying comprises;
scanning the image along the x-axis, scanning the image along the v-axis, performing a horizontal gradient and a vertical gradient along the x and y-axis respectively, and determining whether a local maximum along the gradients match the coordinates for any edge point, comprising;
determining a position, relative to the circle of the foreign structure, wherein if the foreign structure are inside, searching from each edge of the image, inward, to determine the local maximum, if the foreign structure are outside, searching from the center of the image, outward, to determine the local maximum, and if the foreign structure is both inside and outside the circle, randomly scan at a plurality of points each axis of the image within ½
of the total axis length, conduct a gradient operation at each point scanned, determine a plurality of potential edge points, calculate a coordinate for a center of the circle, save the coordinate in an array, determine, based on the plurality of edge points a median value for each coordinate of the center of the circle; and
determining the circle by comparing radiuses from at least two edge points to the intersection. - View Dependent Claims (7, 8, 9, 10, 13)
-
-
11. A computer program product comprising:
-
a computer usable medium having computer readable program code embodied therein for causing the computer to detect a circle within an image, the computer readable program code in the computer program product comprising;
computer readable program code for causing the computer to extract a first pair of edge points along an x-axis of the image;
computer readable program code for causing the computer to extract a second pair of edge points along a y-axis of the image;
computer readable program code for causing the computer to determine an intersection of a first line and a second line extending perpendicular from a midpoint of the first and second edge points respectively;
computer readable program code for causing the computer to determine a radius from the intersection to any edge point;
computer readable program code for causing the computer to determine the circle by verifying a connectivity of adjacent edge points in a gradient array of the image in the presence of a foreign structure visible in the image comprising;
computer readable program code for causing the computer to scan the image along an x-axis, computer readable program code for causing the computer to scan the image along a v-axis, computer readable program code for causing the computer to perform a horizontal gradient and a vertical gradient along the x and y-axis respectively wherein the x and y-axis intersect within the circle, and computer readable program code for causing the computer to determine whether a local maximum along the gradients match the coordinates for any edge point, comprising;
computer readable program code for causing the computer to determine the position, relative to the circle of the foreign structure, wherein if the foreign structures are inside, searching from each edge of the image, inward, to determine the local maximum, if the foreign structures are outside, searching from the center of the image, outward, to determine the local maximum, and if the foreign structure is both inside and outside the circle, randomly scan at a plurality of points each axis of the image within ½
of the total axis length, conduct a gradient operation at each point scanned, determine a plurality of potential edge points, calculate a coordinate for a center of the circle, save the coordinate in an array, determine, based on the plurality of edge points a median value for each coordinate of the center of the circle; and
computer readable program code for causing the computer to verify the circle by comparing radiuses from at least two edge points to the intersection. - View Dependent Claims (12, 14)
-
Specification