Apparatus, method and computer program for determining information about shape and/or location of an ellipse in a graphical image

• US 7,948,493 B2
• Filed: 04/03/2007
• Issued: 05/24/2011
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V., Technische Universitã¤T Ilmenau
• Original Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V., Technische Universitat Munchen
• Inventors: Katzmann, Johannes, Holland-Nell, Christian, Husar, Peter, Klefenz, Frank
• Primary Examiner(s): Amini; Javid A
• Application Number:
  US11/732,539
• Publication Number:
  US 20080012860A1
• Time in Patent Office: 1,512 Days
• Field of Search: 345/441
• US Class Current: 345/441
• CPC Class Codes: G06T 7/64 of convexity or concavity
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 40/193 Preprocessing; Feature extraction

Abstract

An apparatus for determining information about shape and location of an ellipse involves determining two coordinates of a first ellipse point representing a point of the ellipse located furthest in the first direction, and determining two coordinates of a second ellipse point representing a point of the ellipse located furthest in a direction opposite to the first direction. The apparatus determines parameters of bent line segments approximating the ellipse at ellipse points or in a surrounding of ellipse points, and determines the coordinates of ellipse points based on the parameters of the bent line segments. The apparatus involves calculating ellipse parameters of the ellipse based on the two coordinates of the first ellipse point and the two coordinates of the second ellipse point. The apparatus enables real-time-capable determination of parameters of an ellipse included in an image to be analyzed.

Claims

1. An apparatus for determining information about shape and/or location of an ellipse in a graphical image, the graphical image comprising a first given direction and a second given direction, comprising:

a coordinate determinator for determining two coordinates of a first ellipse point representing a point of the ellipse located furthest in the first given direction, and

for determining two coordinates of a second ellipse point representing a point of the ellipse located furthest in a direction opposite to the first given direction,

wherein the coordinate determinator is formed to determine at least one parameter of a first bent line segment approximating the ellipse at the first ellipse point or in a surrounding of the first ellipse point, and to determine the coordinates of the first ellipse point based on the at least one parameter of the first bent line segment, and

to determine at least one parameter of a second bent line segment approximating the ellipse at the second ellipse point or in a surrounding of the second ellipse point, and to determine the coordinates of the second ellipse point based on the at least one parameter of the second bent line segment; and

an ellipse calculator for calculating at least one ellipse parameter based on the two coordinates of the first ellipse point and the two coordinates of the second ellipse point,

wherein the at least one ellipse parameter represents the information about the shape and/or the location of the ellipse.

2. The apparatus according to claim 1,

wherein the coordinate determinator further is formed to determine at least one coordinate of a third ellipse point representing a point of the ellipse located furthest in the second direction,

wherein the coordinate determinator is formed to determine at least one parameter of a third bent line segment approximating the ellipse at the third ellipse point or in a surrounding of the third ellipse point, and

to determine at least one coordinate of the third ellipse point based on the at least one parameter of the third bent line segment,

wherein the ellipse calculator is formed to calculate at least one ellipse parameter based on the two coordinates of the first ellipse point, the two coordinates of the second ellipse point and the at least one coordinate of the third ellipse point.

3. The apparatus according to claim 1, wherein the graphical image is a raster image including a plurality of image points arranged in a plurality of raster rows and/or in a plurality of raster columns, wherein the ellipse is described by a plurality of image points forming ellipse points, and/or wherein the first bent line segment can be described by a plurality of adjacent image points, and/or wherein the second bent line segment can be described by a plurality of adjacent image points, and/or wherein the third bent line segment can be described by a plurality of adjacent image points.

4. The apparatus according to claim 3, wherein the coordinate determinator is formed to perform a pattern recognition, using the raster rows and/or the raster columns, in order to identify, in an image excerpt of the image to be identified, which is formed by a plurality of raster rows and/or raster columns, a curve course forming the first bent line segment, and to determine at least one parameter of the identified curve course as a parameter of the first bent line segment.

5. The apparatus according to claim 4, wherein the coordinate determinator is formed to perform a pattern recognition, using the raster rows and/or raster columns, in order to identify, in the image excerpt of the image to be identified, which is formed by the plurality of raster rows and/or raster columns, a curve course forming the first bent line segment, by checking if the image excerpt to be analyzed includes a curve course that is sufficiently similar to a reference curve course from a first set of possible reference curve courses with respect to a given similarity measure, wherein the first set of possible reference curve courses describes admissible courses of the first bent line segment for various parameters of the first bent line segment,

and/or to identify, in the image excerpt of the image to be analyzed, which is formed by the plurality of raster rows and/or raster columns, a curve course forming the second bent line segment, by checking if the image excerpt to be analyzed includes a curve course sufficiently similar to a reference curve course from a second set of possible reference curve courses with reference to a given similarity measure, wherein the second set of possible reference curve courses describes admissible courses of the second bent line segment for various parameters of the second bent line segment,

and/or to identify, in the image excerpt of the image to be analyzed, which is formed by the plurality of raster rows and/or raster columns, a curve course forming the third bent line segment, by checking if the image excerpt to be analyzed includes a curve course sufficiently similar to a reference curve course from a third set of possible reference curve courses with reference to a given similarity measure, wherein the third set of possible reference curve courses describes admissible courses of the third bent line segment for various parameters of the third bent line segment.

6. The apparatus according to claim 5, wherein the set of possible reference curve courses describes curve courses differing with reference to their location and/or shape, wherein at least one parameter characterizing the location and/or shape is associated with a curve course from the plurality of possible reference curve courses, and wherein the coordinate determinator is formed to derive the parameter of the first bent line segment approximating the ellipse at the first ellipse point, the parameter of the second bent line segment approximating the ellipse at the second ellipse point, or the parameter of the third bent line segment approximating the ellipse at the third ellipse point, from the fact as to which one of the curve courses from the plurality of possible reference curve courses is sufficiently similar to a curve course in the image excerpt with reference to the given similarity measure.

7. The apparatus according to claim 5, wherein the curve courses are chosen from the plurality of possible reference curve courses so that they approximate ellipses of different shape and/or location at the first ellipse point or at the second ellipse point or at the third ellipse point.

8. The apparatus according to claim 5, wherein the curve courses are selected from the plurality of possible reference curve courses so that they describe excerpts from circular curves of different location and/or different radius.

9. The apparatus according to claim 1, wherein the coordinate determinator is formed to apply a pattern recognition to a plurality of image excerpts of the image to be analyzed, in order to identify, in the plurality of image excerpts to be analyzed, a curve course forming the first bent line segment, and to determine a location parameter of the first bent line segment, based on in which one of the plurality of image excerpts of the image the first bent line segment is identified.

10. The apparatus according to claim 9, wherein the coordinate determinator is formed to apply the pattern recognition to the plurality of image excerpts of the image to be analyzed, wherein the image excerpts to be analyzed are chosen so that at least two image excerpts of the plurality of image excerpts to be analyzed overlap.

11. The apparatus according to claim 1, wherein the coordinate determinator is formed to determine at least a further coordinate of the third ellipse point as an additional coordinate, or at least one coordinate of a fourth ellipse point representing a point of the ellipse located furthest in a direction opposite to the second direction,

wherein the ellipse calculator is formed to calculate a first set of ellipse parameters including at least one ellipse parameter, based on the two coordinates of the first ellipse point, the two coordinates of the third ellipse point and the first coordinate of the third ellipse point, as well as to calculate a second set of ellipse parameters including at least one ellipse parameter, based on the two coordinates of the first ellipse point, the two coordinates of the second ellipse point and the additional coordinate, and to calculate a result set of ellipse parameters by averaging, using the first set of ellipse parameters and the second set of ellipse parameters.

12. The apparatus according to claim 1, wherein the coordinate calculator is formed to determine two coordinates of the third ellipse point representing a point of the ellipse located furthest in the second direction, and two coordinates of a fourth ellipse point representing a point of the ellipse located furthest in a direction opposite to the second direction, and further to select a plurality of different sets of three ellipse points from the first ellipse point, the second ellipse point, the third ellipse point and the fourth ellipse point, in order to determine associated sets of ellipse parameters for the sets of ellipse points, and to calculate an average set of ellipse parameters as information about the shape and/or the location of the ellipse by averaging of the sets of ellipse parameters belonging to the sets of ellipse points.

13. The apparatus according to claim 1, wherein the coordinate determinator is formed to determine two coordinates of the third ellipse point representing a point of the ellipse located furthest in the second direction, and

wherein the ellipse calculator is further formed to calculate center coordinates of the ellipse from the two coordinates of the first ellipse point and the two coordinates of the second ellipse point,

to perform a coordinate transform of the coordinates of the first ellipse point and of the third ellipse point, in order to obtain transformed coordinates of the first ellipse point and the third ellipse point, wherein the coordinate transform is formed to shift a center of the ellipse described by the center coordinates into a coordinate origin,

to calculate an estimated transformed second coordinate y_y,calc of the third ellipse point, using the determination equation

14. The apparatus according to claim 1,

wherein the ellipse calculator is formed to calculate a first center coordinate x_m of the ellipse, based on the first coordinate x₃ of the first ellipse point and the first coordinate x₁ of the second ellipse point, using the calculation rule

15. The apparatus according to claim 14, wherein the ellipse calculator is further formed to calculate a rotational angle α

of the ellipse, a length a of a first semiaxis of the ellipse and/or a length b of a second semiaxis of the ellipse, using the following determination equations;

16. The apparatus according to claim 1, wherein the coordinate determinator comprises a pattern recognizer, which is formed to receive a plurality of raster rows to be analyzed or of raster columns to be analyzed in form of a plurality of parallel time signals, and to forward the time signals at different speeds in parallel through a plurality of stages connected one behind the other,

wherein at least one predetermined stage includes a summer, which is formed to sum signals coming out of the predetermined stage, in order to form a column sum, and

wherein the pattern recognizer is further formed to evaluate the column sum, in order to determine information about a bent line segment included in the raster rows or raster columns received from the pattern recognizer,

wherein the information includes at least one parameter of the bent line segment included in the received raster rows or raster columns.

17. The apparatus according to claim 16, wherein the predetermined stage further comprises a threshold value recognizer, which is formed to receive and recognize the column sum if at least a predetermined number of signals at the output of the predetermined stage are active at the same time,

wherein the pattern recognizer is further formed to evaluate an output signal of the threshold value recognizer, in order to determine at least one parameter of a bent line segment included in the received raster rows or raster columns.

18. The apparatus according to claim 16, wherein the pattern recognizer is formed to distort a curved curve course, which is described by the signals received by the pattern recognizer, step by step when passing through the stages connected one behind the other, due to the differently fast propagation of the signals, in order to obtain a distorted description of the curved curve course, and to recognize if an approximately straight line represented by a plurality of concurrently active signals in a particular stage is described by the distorted description.

19. The apparatus according to claim 16, wherein the at least one stage of the pattern recognizer is formed to delay several signals in differently strong manner when forwarding same through the stage.

20. The apparatus according to claim 16, wherein the pattern recognizer, by establishing different delays when forwarding the signals through the stages, is formed so that a circularly bent line segment included in the raster rows or raster columns received by the pattern recognizer is deformed approximately to a straight line after passing through a number of stages,

wherein the pattern recognizer is formed to recognize presence of an approximately straight line and to determine after passing through how many stages the straight line is present, and

wherein the pattern recognizer is further formed to derive at least one parameter of the circularly bent line segment received by the pattern recognizer from the number of stages passed through until the presence of an approximately straight line.

21. The apparatus according to claim 10, wherein the pattern recognizer, by establishing different delays when forwarding the signals through the stages, is formed so that a circularly bent line segment included in the raster rows or raster columns received by the pattern recognizer is deformed approximately to a straight line after passing through a number of stages, wherein the pattern recognizer is formed to recognize presence of an approximately straight line and to derive at least one parameter of the circularly bent line segment received by the pattern recognizer, based on the time instant at which the approximately straight line is present.

22. The apparatus according to claim 10, wherein the coordinate determinator is formed to supply the image to the pattern recognizer twice in form of successively transmitted raster rows to be analyzed,

wherein the coordinate determinator is further formed to supply the image to the pattern recognizer for a determination of the two coordinates of the first ellipse point, beginning with a raster row of the image located at a first edge of the image, and to supply the image to the pattern recognizer for a determination of the two coordinates of the second ellipse point, beginning with a raster row of the image located at a second edge of the image, wherein the first edge of the image is opposite to the second edge of the image, and wherein the pattern recognizer is formed to recognize bent line segments with a given direction of curvature.

23. The apparatus according to claim 10, wherein the coordinate determinator includes a first pattern recognizer and a second pattern recognizer, wherein the first pattern recognizer is formed to recognize bent line segments with a first given direction of curvature, wherein the second pattern recognizer is formed to recognize bent line segments with a second direction of curvature opposite to the given first direction of curvature, and wherein the coordinate determinator is formed to supply the image to the first pattern recognizer for a determination of the two coordinates of the first ellipse point, beginning with a raster row located at a first edge of the image, and to provide the image to the second pattern recognizer for a determination of the two coordinates of the second ellipse point, beginning with a raster row located at the first edge of the image.

24. The apparatus according to claim 10, wherein the pattern recognizer is formed to process a first plurality of raster rows to be analyzed as well as a second plurality of raster rows to be analyzed, wherein the first plurality of raster rows to be analyzed and the second plurality of raster rows to be analyzed overlap, and

wherein the pattern recognizer is further formed to determine a location parameter of the curve course to be identified based on whether the curve course to be identified is identified in an analysis of the first plurality of raster rows to be analyzed or in an analysis of the second plurality of raster rows to be analyzed.

25. The apparatus according to claim 1, wherein the first direction is orthogonal to the second direction.

26. The apparatus according to claim 1, wherein the apparatus for determining information about the shape and/or the location of an ellipse is formed to receive a binary edge image as graphical image, wherein the binary edge image describes at least one edge by at least one line in form of active image points, whereas locations in the edge image at which no edge is present are described by non-active image points.

27. The apparatus according to claim 1, wherein the apparatus is further formed to derive the graphical image from video data from a video data source.

28. The apparatus according to claim 1, further comprising a data interface or a display device, which is formed to output the information about the shape and/or the location of the ellipse to an electrical processor or a human user.

29. The apparatus according to claim 1, wherein the apparatus for determining information about the shape and/or the location of an ellipse is formed to preprocess the graphical image by a threshold value binarization, in which a light value or a dark value is associated with each image point of the graphical image, depending on the result of a comparison of a color value and/or a brightness value with a threshold value, in order to obtain a binarized image,

and further to apply edge detection to the binarized image, wherein the edge detection is formed to generate an edge image from the binarized image, in which edge-shaped transitions from the light value to the dark value in the binarized image are characterized as a line-shaped edge,

wherein the coordinate determinator is further formed to process the edge image.

30. The apparatus according to claim 1, wherein the apparatus is further formed to obtain the graphical image from a video camera arranged to capture a pupil of a human eye,

and wherein the apparatus further includes a data interface formed to transmit the information about the shape and/or the location of the ellipse to an apparatus for calculating a viewing direction of the human eye.

31. A method for determining information about shape and/or location of an ellipse in a graphical image, the image comprising a first given direction and a second given direction, comprising:

determining, using a computer, two coordinates of a first ellipse point representing a point of the ellipse located furthest in the first given direction, determining, using a computer, two coordinates of a second ellipse point representing a point of the ellipse located furthest in a direction opposite to the first given direction, wherein determining the two coordinates of the first ellipse point includes determining at least one parameter of a first bent line segment approximating the ellipse at the first ellipse point or in a surrounding of the first ellipse point, as well as determining the coordinates of the first ellipse point, based on the at least one parameter of the first bent line segment, and wherein determining the two coordinates of the second ellipse point includes determining at least one parameter of a second bent line segment approximating the ellipse at the second ellipse point or in a surrounding of the second ellipse point, as well as determining the coordinates of the second ellipse point, based on the at least one parameter of the second bent line segment; and

calculating, using a hardware, at least one ellipse parameter of the ellipse, based on the two coordinates of the first ellipse point and the two coordinates of the second ellipse point, wherein the at least one ellipse parameter represents information about the shape and/or the location of the ellipse.

32. A method for determining information about shape and/or location of an ellipse in a graphical image, the image comprising a first given direction and a second given direction, comprising:

determining, using a computer, two coordinates of a first ellipse point representing a point of the ellipse located furthest in the first given direction, determining, using a computer, two coordinates of a second ellipse point representing a point of the ellipse located furthest in a direction opposite to the first given direction, wherein determining the two coordinates of the first ellipse point includes identifying a first bent line segment approximating the ellipse at the first ellipse point or in a surrounding of the first ellipse point, determining at least one parameter of the identified first bent line segment, as well as determining the coordinates of the first ellipse point, based on the at least one parameter of the identified first bent line segment, and wherein determining the two coordinates of the second ellipse point includes identifying a second bent line segment approximating the ellipse at the second ellipse point or in a surrounding of the second ellipse point, determining at least one parameter of the identified second bent line segment, as well as determining the coordinates of the second ellipse point, based on the at least one parameter of the identified second bent line segment, and calculating, using a computer, at least one ellipse parameter of the ellipse, based on the two coordinates of the first ellipse point and the two coordinates of the second ellipse point, wherein the at least one ellipse parameter represents information about the shape and/or the location of the ellipse.

33. A computer program for performing, when the computer program is executed on a computer, a method for determining information about shape and/or location of an ellipse in a graphical image, the image comprising a first direction and a second direction, the method comprising:

determining two coordinates of a first ellipse point representing a point of the ellipse located furthest in the first direction,

determining two coordinates of a second ellipse point representing a point of the ellipse located furthest in a direction opposite to the first direction,

wherein determining the two coordinates of the first ellipse point includes determining at least one parameter of a first bent line segment approximating the ellipse at the first ellipse point or in a surrounding of the first ellipse point, as well as determining the coordinates of the first ellipse point, based on the at least one parameter of the first bent line segment, and

wherein determining the two coordinates of the second ellipse point includes determining at least one parameter of a second bent line segment approximating the ellipse at the second ellipse point or in a surrounding of the second ellipse point, as well as determining the coordinates of the second ellipse point, based on the at least one parameter of the second bent line segment; and

calculating at least one ellipse parameter of the ellipse, based on the two coordinates of the first ellipse point and the two coordinates of the second ellipse point,

wherein the at least one ellipse parameter represents information about the shape and/or the location of the ellipse.

34. A computer program for performing, when the computer program is executed on a computer, a method for determining information about shape and/or location of an ellipse in a graphical image, the image comprising a first direction and a second direction, the method comprising:

determining two coordinates of a first ellipse point representing a point of the ellipse located furthest in the first direction,

determining two coordinates of a second ellipse point representing a point of the ellipse located furthest in a direction opposite to the first direction,

wherein determining the two coordinates of the first ellipse point includes identifying a first bent line segment approximating the ellipse at the first ellipse point or in a surrounding of the first ellipse point, determining at least one parameter of the identified first bent line segment, as well as determining the coordinates of the first ellipse point, based on the at least one parameter of the identified first bent line segment, and

wherein determining the two coordinates of the second ellipse point includes identifying a second bent line segment approximating the ellipse at the second ellipse point or in a surrounding of the second ellipse point, determining at least one parameter of the identified second bent line segment, as well as determining the coordinates of the second ellipse point, based on the at least one parameter of the identified second bent line segment, and

calculating at least one ellipse parameter of the ellipse, based on the two coordinates of the first ellipse point and the two coordinates of the second ellipse point,

wherein the at least one ellipse parameter represents information about the shape and/or the location of the ellipse.