JP3593885B2 - Image analysis apparatus and method - Google Patents

Description

仮中心算出ステップＳ２の出力値をＯ（Ｘ，Ｙ）とし、値９０に対して十分に小さい値Φをパラメータとして設定し（本実施例ではΦ＝ｓｉｎ^−１１／１０）、バッファ１に貯えられたエッジ画像座標値のうち角ＡＯＢが（９０−Φ）以上、（９０＋Φ）以下であるような座標の組（Ａ，Ｂ）をすべて決定する。これら決定した組に対して１／ＯＡ^２＋１／ＯＢ^２を計算し、その値の度数分布を求める。最も大きい度数を持つカテゴリをｐとすれば、これが１／ａ^２＋１／ｂ^２となっているはずである。次にａ，ｂに関するもう一つの関係式を用いる。楕円周上の任意の１点をＡとし、点Ａにおける楕円の接線の傾きと平行で楕円の中心Ｏを通る直線を引き、楕円周との交点を点Ｂ，点Ｃとすれば、
【００３１】
【数２】

なる関係式を持つ。デジタル画像の場合、点Ｂ，点Ｃが存在しない場合があるが、バッファ１に貯えられた座標の中で楕円の中心Ｏに関して互いに反対位置にあり、上記直線との距離が最短である２組の座標を算出し、それらエッジから直線に下した垂線の足を点Ｂ，点Ｃと定める。再びすべてのエッジ座標Ａに対して三角形ＡＢＣの面積を求め、その値の度数分布を求める。最も大きい度数を持つカテゴリをｑとすれば、これがａｂとなっているはずである。以上の二つの図形的性質を示す図を図１３（ａ）（ｂ）に示す。この時ａ，ｂはｔに関する二次方程式
【００３２】
【数３】

の２解となる。これを解いて、
【００３３】
【数４】

を得る。
【００３４】
つぎに、長径・短径算出ステップＳ３の詳細を説明する。長径・短径算出ステップＳ３は、さらにステップＳ３１、Ｓ３２、Ｓ３３に分けることができる。ステップＳ３１は上述のｐ＝１／ａ^２＋１／ｂ^２を求めるものである。ステップＳ３２は、上述のｑ＝ａｂを求めるものである。ステップＳ３３は、ｐおよびｑから長径ａおよび短径ｂを求め、さらにエッジ画像が円か楕円かを判定するものである。ステップＳ３１、Ｓ３２およびＳ３３の処理の流れをそれぞれ図１０、図１１および図１２に示す。これらは並列に処理しても直列に処理してもよい。
【００３５】
図１０のステップ３１の処理は以下のとおりである。
［ステップＳ３１１］ インデックスｉ，ｊを１に初期設定する。
［ステップＳ３１２］ バッファ１のｉ個目の座標Ａｉを抽出する。
［ステップＳ３１３］ バッファ１のｊ個目の座標Ｂｊを抽出する。
［ステップＳ３１４］ 角ＡｉＯＢｊが（９０−Φ）度以上、（９０＋Φ）度以下かどうかを判別する。そうであれば考慮対象であるのでステップＳ３１５に進み、そうでなければ考慮対象外であるのでステップＳ３１６に進む。
［ステップＳ３１５］ ヒストグラムに（ＯＡｉ）^−２＋（ＯＢｊ）^−２の値を蓄える。
［ステップＳ３１６］ インデックスｊを１だけ増分する。
［ステップＳ３１７］ バッファ１のｊ個目のデータが空かどうかを判別する。
空でなければステップＳ３１３に戻り処理を繰り返す。空であればステップＳ３１８に進む。
［ステップＳ３１８］ ｉ＝ｉ＋１、ｊ＝１に設定する。
［ステップＳ３１９］ バッファ１のｉ個目のデータが空かどうか判別する。空でなければ、ステップＳ３１２に戻り処理を繰り返す。空であればステップＳ３２０に進む。
［ステップＳ３２０］ 最大度数のカテゴリをｐに代入する。
【００３６】
図１１のステップ３２の処理は以下のとおりである。
［ステップＳ３２１］ インデックスをｉ＝ｊ＝ｋ＝ｌ＝０に初期設定する
［ステップＳ３２２］ バッファ１のｉ個目の座標Ａｉを抽出する。
［ステップＳ３２３］ 座標Ａｉにおけるエッジの傾きを計算する。
［ステップＳ３２４］ ＯＡｉを通る直線ｌ_１：ｆ（ｘ，ｙ）＝０を算出する。
［ステップＳ３２５］ 座標Ｏを通り、傾きＳの直線ｌ_２：ｇ（ｘ，ｙ）＝０を算出する。
［ステップＳ３２６］ バッファ１のｊ個目の座標Ｂｊを抽出する。
［ステップＳ３２７］ 直線ｌ_２と座標Ｂｊの距離Ｌ_ｊおよび座標Ｂ_ｊから下ろした垂線の足Ｂ’_ｊを算出する。
［ステップＳ３２８］ ｆ（Ｂ’_ｊ）＞＝０かどうか判別する。そうであればステップＳ３２９に進む。そうでなければ、ステップＳ３３４へ進む。
［ステップＳ３２９］ ｋ＝０かどうかを判別する。そうであればステップＳ３３０へ進む。そうでなければ、ステップＳ３３２へ進む。
［ステップＳ３３０］ Ｌ_ｂ＝Ｌ_ｊ、Ｂ＝Ｂ’_ｊとする。
［ステップＳ３３１］ ｋ＝１とする。
［ステップＳ３３２］ Ｌ_ｂ＞Ｌ_ｊを判別する。そうであればステップＳ３３３へ進む。そうでなければステップＳ３３４へ進む。
［ステップＳ３３３］ Ｌ_ｂ＝Ｌ_ｊ、Ｂ＝Ｂ’_ｊとする。
［ステップＳ３３４］ ｌ＝０かどうかを判別する。そうであればステップＳ３３５へ進む。そうでなければステップＳ３３７へ進む。
［ステップＳ３３５］ Ｌ_ｃ＝Ｌ_ｊ、Ｃ＝Ｂ’_ｊとする。
［ステップＳ３３６］ ｌ＝１とする。
［ステップＳ３３７］ Ｌ_ｃ＞Ｌ_ｊを判別する。そうであればステップＳ３３８へ進む。そうでなければステップＳ３３９へ進む。
［ステップＳ３３８］ Ｌ_ｃ＝Ｌ_ｊ、Ｃ＝Ｂ’_ｊとする。
［ステップＳ３３９］ ｊ＝ｊ＋１とする。
［ステップＳ３４０］ バッファ１のｊ個目のデータが空かどうか判別する。空でなければステップＳ３２６に戻り処理を繰り返す。空であればステップＳ３４１へ進む。
［ステップＳ３４１］ 三角形ＡｉＢＣの面積を求め、ヒストグラム２に蓄える。
［ステップＳ３４２］ ｊ＝１、ｉ＝ｉ＋１とする。
［ステップＳ３４３］ バッファ１のｉ個目のデータが空かどうか判別する。空でなければステップＳ３２２に戻り処理を繰り返す。空であればステップＳ３４４へ進む。
［ステップＳ３４４］ 最大度数のカテゴリをｑに代入する。
【００３７】
以上の長径ａおよび短径ｂを求めるために必要なｐおよびｑが求まった。そして図１２のステップＳ３３で長径ａおよび短径ｂを求め、さらに円／楕円の判別を行なう。すなわち、ａとｂとの比の値が閾値（本実施例では１．０５）以下の場合、与えられたエッジ画像を中心がＯ（Ｘ，Ｙ），半径がａまたはｂの円と判定し、補正ステップに渡す。この補正ステップではステップＳ３３の出力値を初期値とする最小２乗法などで、より適合度の高いパラメータを算出する。もちろん初期値のまま出力してもよい。一方、ステップＳ３３においてエッジ画像を楕円と判定した場合、残りの１つのパラメータである傾きを決定するために傾き算出ステップＳ４に移行する。
【００３８】
なお、図１２のステップＳ３３の処理は以下のとおりである。
［ステップＳ３４５］ ｐ、ｑから長径ａおよび短径ｂを求める。
［ステップＳ３４６］ ａ／ｂ＜＝Ｔかどうかを判別する。そうであればステップＳ３４７へ進む。そうでなければステップＳ３４８へ進む。
［ステップＳ３４７］ エッジ画像を円と判断し所望の補正ステップへ進む。
［ステップＳ３４８］ エッジ画像を楕円と判断しステップＳ４へ進む。
【００３９】
つぎに、傾き算出ステップＳ４の処理について説明する。図１４は傾き算出ステップＳ４での処理の流れを示す。まず中心がＯ、長径がａで短径がｂのＸ軸Ｙ軸に平行な軸を持つ楕円Ｕを描く（ステップＳ４０１）。この楕円とエッジ画像との交点を図１５に示すように点Ａ，点Ｂ，点Ｃ，点Ｄとすれば、線分ＡＣと線分ＢＤは直交し、その交点は楕円の中心と一致する。エッジ画像上の点Ｐに対して、直線ＯＰと楕円Ｕの交点をＰ’とし、線分ＰＰ’の長さを持って楕円とエッジ画像上の画素との距離と定義する。今座標平面を以下の４つの領域に分ける（ステップＳ４０２）。それらを領域１（ｘ＞＝Ｘかつｙ＞Ｙ）、領域２（ｘ＜Ｘかつｙ＞＝Ｙ）、領域３（ｘ＜＝Ｘかつｙ＜Ｙ）、領域４（ｘ＞Ｘかつｙ＜＝Ｙ）とする。各領域内において楕円Ｕの外部にあって楕円Ｕとの距離が最小であるエッジ上の画素と、楕円Ｕの内部にあって楕円Ｕとの距離が最小であるエッジ上の画素とを選択し、それらを結ぶ線分と楕円Ｕとの交点を算出し、順に点Ａ，点Ｂ，点Ｃ，点Ｄとする（ステップＳ４０３）。この時点Ｏと４つの交点のうちいずれか（本実施例では点Ａ）を結ぶ直線の傾きをθとすれば、２θが求める楕円の傾きである（ステップＳ４０４）。こうしてこの時点で楕円の５つのパラメータがすべて算出できる。
【００４０】
線分ＡＣと線分ＢＤとの交点をとれば、これは理想的には楕円の中心座標と一致するはずであるが、実際には一致していない。そこで評価ステップＳ５が満足しないパラメータを傾き算出ステップＳ４が算出した場合、この新たに求めた中心を仮中心算出ステップＳ２の出力値とし、再び長径・短径算出ステップＳ３に戻す処理を行う。この操作を評価ステップＳ５が満足するまで繰り返す。評価ステップＳ５では線分ＡＣと線分ＢＤの角度が基準値内であるという条件にしてもよいし、線分ＡＣと線分ＢＤの交点と、直前に算出された楕円の中心座標との距離が基準値以内であるとしてもよいし、線分ＡＣと線分ＢＤの中点の距離が基準値以内であるとしてもよいし、線分ＡＣまたは線分ＢＤの中点が一方の線分の上にどの程度乗っているかを基準にしてもよい。また必要回数だけ評価ステップＳ５から長径・短径算出ステップＳ３に戻すループを回し、必要回数ループを回した後に得られるパラメータを評価ステップＳ５の出力としてもよい。ただしこのようなループを回すためにはエッジ画像と楕円Ｕとの間に最低でも対応する１組の交点（例えば点Ａと点Ｃ）が求まっている必要がある。この場合線分ＡＣの中点を新たな中心座標と置換することが可能である。対応する１組の交点が求まっていない場合は、求められた交点の一つと中心座標とを結んでできる直線の傾きをもってθとし、ループは回さない。また交点を１点も求めることができない場合は、本手法によっては傾きを算出することができず、最小２乗法などの手段により傾きを求める。ただし、本実施例で用いた画像では交点が１点も求めることができない程のノイズを持つものは存在しなかった。
【００４１】
【発明の効果】
本発明によれば、円を含む楕円の５つのパラメータを複雑な計算をすることなしに算出することが可能となる。またエッジ画像にノイズが含まれていたり、切れ目が生じている場合でもパラメータの算出が可能である。
【図面の簡単な説明】
【図１】本発明を説明するためのブロック図である。
【図２】本発明の実施例を全体的に示すフローチャートである。
【図３】図２のステップＳ１の詳細なアルゴリズムを示す図である。
【図４】図２におけるステップＳ２の詳細なアルゴリズムを示す図である。
【図５】図４におけるステップＳ２０１を説明する図である。
【図６】図４における中点算出手法を説明する図である。
【図７】図４においてエッジ画像と直線との交点が１点のみである具体例を示す図である。
【図８】図４においてエッジ画像と直線との交点が３点以上ある場合の具体例を示す図である。
【図９】図４におけるステップＳ２１９の詳細なアルゴリズムを示すフローチャートである。
【図１０】図２におけるステップＳ３の一部（ステップＳ３１）の詳細なアルゴリズムを示すフローチャートである。
【図１１】図２におけるステップＳ３の一部（ステップＳ３２）の詳細なアルゴリズムを示すフローチャートである。
【図１２】図２におけるステップＳ３の一部（ステップＳ３３）の詳細なアルゴリズムを示すフローチャートである。
【図１３】楕円の図形的性質を示す図である。
【図１４】図２におけるステップＳ４の詳細なアルゴリズムを示すフローチャートである。
【図１５】図１４における傾き算出手法を説明する図である。
【符号の説明】
１１ 前処理部
１２ 仮中心算出部
１３ 長径・短径算出部
１４ 傾き算出部
１５ 評価部
Ｓ１ 前処理ステップ
Ｓ２ 仮中心算出ステップ
Ｓ３ 長径・短径算出ステップ
Ｓ４ 傾き算出ステップ
Ｓ５ 評価ステップ[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a technique for extracting three parameters of a circle or five parameters of an ellipse from a digital image. As one of the application examples, an utterance recognition system for non-contact measurement of a subtle movement of a human articulator, a three-dimensional shape measurement device, and the like are considered.
[0002]
[Prior art]
There is a least-squares method as a method of obtaining a straight line that best fits a given pixel group. In this method, three unknown parameters can be easily determined by solving a ternary simultaneous linear equation. However, it is not easy to apply the least squares method to a circle or an ellipse. In the case of a circle, the three parameters to be determined are a total of the center coordinates and the radius. However, when these are determined by the least square method, a non-linear simultaneous equation is obtained, and optimization calculation such as Gauss-Newton method is performed in order to obtain a solution. It must be done and becomes complicated. Further, if the shape is an ellipse other than a circle, the parameters to be determined are five, that is, the center coordinate, the major axis, the radius, and the inclination, which is further complicated.
In order to solve this, in the case of a circle, a method of inverting a pixel group with respect to a specific point to replace the method with a straight line least squares method (IEICE, J75-DII, 1338-1345, 1992) has been proposed. Was. However, this is not easy in the case of an ellipse. This is because in the case of an ellipse, two more unknown parameters must be determined more than a circle. In order to cut out an ellipse efficiently and quickly, it is necessary to reduce the number of parameter dimensions.
The conventional ellipse extraction technique employs a method of calculating center coordinates, and then calculating a major axis, a minor axis, and an inclination. For example, Tsuji et al. Calculated the slope of each edge from an edge image by a simple gradient operator, and calculated the center of the ellipse using the property that the midpoint of the edge having the same slope is the center of the ellipse (IEEE Trans. Comp. , 27, 777-781, 1978). Further, Nair et al. Increased the speed by using the Hough transform (Pattern Recognition Let., 17, 777-784, 1996). Although the method of Tsuji et al. Eventually settles in a two-parameter least squares method, a non-linear shape remains at the end. These methods are effective when the image does not contain noise, but cannot extract the ellipse correctly when the image has noise and the calculation of the center coordinates fails.
[0003]
As another center calculation method, there is JP-A-8-210811. In this method, the scanning line is moved in a certain direction, the midpoint of the intersection between the scanning line and the image is calculated, and the distance between those intersections is used as the voting value, so that the one that obtains the largest voting value is an ellipse. The center of.
[0004]
Also, Japanese Patent Application Laid-Open No. 7-311847 has proposed a method in which an area extraction frame is provided and five parameters of an ellipse including a center coordinate are obtained from coordinates of a contact point with an image.
[0005]
However, even with these methods, it is difficult to extract correctly if the ellipse has a cut or noise. In JP-A-59-123981, the image is rotated so that the cut is parallel to the vertical or horizontal axis of the image, the scanning line is moved in parallel with the cut, and the length of the scanning line that cuts the image is the maximum. A method centered on the midpoint was proposed. However, it cannot be applied when there are multiple breaks.
[0006]
[Problems to be solved by the invention]
SUMMARY OF THE INVENTION It is an object of the present invention to provide an image analysis technique capable of calculating a parameter of a circle or an ellipse by using a graphic property of a circle or an ellipse even if the image includes noise or a break.
[0007]
[Means for Solving the Problems]
First, one aspect of the present invention will be described with reference to FIG. As shown in FIG. 1, the image analysis device of the present invention includes a preprocessing unit 11, a provisional center calculation unit 12, a long diameter / short diameter calculation unit 13, an inclination calculation unit 14, and an evaluation unit 15. In FIG. 1, a preprocessing unit 11 generates an edge image by performing thinning and the like. The temporary center calculation unit 12 selects and applies various calculation methods according to noise. When the processing first passes through the major axis / minor axis calculation unit 13, if the extraction target is a circle, a total of three parameters of a radius, a center X coordinate, and a Y coordinate can be calculated. On the other hand, when the extraction target is an ellipse, four parameters of a major axis, a minor axis, a center X coordinate, and a Y coordinate are calculated. Further, in the case of an ellipse, the inclination is calculated by the following inclination calculation unit 14, and the subsequent evaluation unit 15 newly determines a center coordinate value different from the center coordinates determined by the temporary center calculation unit 12. This is because in the process of extracting a circle or an ellipse from an image containing noise, the accuracy of the center coordinates greatly affects the calculation of other parameters. This is because there is a possibility of separation. By returning the result to the major axis / minor axis calculating unit 13 again, the lengths of the major axis and the minor axis can be newly calculated. By repeatedly performing the calculation of these parameters until the condition that the evaluation unit 15 satisfies is satisfied, it is possible to calculate the parameters with high accuracy.
[0008]
In the above configuration, the center can be calculated by dividing the case depending on the state, whether the edge image includes noise or a break. In addition, the length of the major axis and the minor axis can be calculated in the form of a quadratic equation by using the graphic properties of the ellipse. Further, the edge image can be sorted into a circle and other ellipses based on the value of the ratio of the major axis to the minor axis calculated here.
[0009]
When it is determined that the ellipse is an ellipse, the center of the edge image can be newly calculated from the graphic feature at the same time when the inclination is obtained. According to the present invention, the inclination of the ellipse can be calculated without depending on the state of the edge image, and the center coordinates can be newly calculated. Therefore, even if the accuracy of the center coordinates obtained by the temporary center calculation unit 12 is poor, by repeating these operations, a more accurate parameter can be calculated later.
[0010]
Further, the present invention will be described.
[0011]
According to the present invention, in order to achieve the above-described object, a central coordinate calculating means for calculating central coordinates from the analyzed image is provided to an image analyzing apparatus for analyzing a circle and an ellipse included in the digitized analyzed image. And, provided with a diameter calculating means for calculating the radius of the circle or the major axis and the minor axis of the ellipse based on the center coordinates, the diameter calculating means, (1) Let the center of the ellipse be point O, and So that the angle AOB is 90 degrees Taking the points A and B, the property that the sum of the reciprocals of the squares of the lengths of the line segments OA and OB is constant, and (2) If the point A is set on the circumference of the ellipse and the intersection of the ellipse with a straight line passing through the center O and parallel to the tangent of the ellipse at the point A is point B and point C, the property that the area of the triangle ABC is constant is used. Then, the radius of the circle or the major axis and the minor axis of the ellipse are calculated.
[0012]
In this configuration, the length of the major axis and the minor axis can be calculated in the form of a quadratic equation by using the graphic properties of the ellipse. Further, the edge image can be sorted into a circle and other ellipses based on the value of the ratio of the major axis to the minor axis calculated here.
[0013]
In this configuration, it is possible to determine whether the analyzed image is a circle or an ellipse by comparing the value of the ratio between the major axis and the minor axis to a predetermined threshold value. For example, when the value of the ratio between the major axis and the minor axis is equal to or greater than the threshold, the analyzed image is determined to be an ellipse. Alternatively, when the value of the ratio between the major axis and the minor axis is equal to or less than the threshold, the analyzed image is determined to be a circle.
[0014]
Further, when the analyzed image is determined to be a circle, the major axis may be output as the radius of the circle. Further, the minor axis may be output as the radius of the circle.
[0015]
Further, when the analyzed image is determined to be a circle, the calculated center coordinates and radius may be corrected so as to be more suitable for the analyzed image. For example, the correction is performed by the least square method.
[0016]
Further, the center coordinates of the ellipse calculated by the center coordinate calculation means and the diameter calculation means, having a major axis and a minor axis as parameters, the intersection of the ellipse having an axis parallel to the coordinate axis and the edge image of the target image. An inclination calculating means for calculating and calculating the inclination of the analyzed image based on these intersections may be further provided. For example, the intersection of the ellipse having the axis, the major axis, and the minor axis of the calculated ellipse as parameters, and having an axis parallel to the coordinate axis, and the original edge image are defined in the order of points A, B, and C in a counterclockwise direction. , Point D, the slope of the original analyzed image is twice the slope of the straight line AC or the straight line BD.
[0017]
The inclination calculating means may calculate an inclination of the analyzed image based on the intersection and the center coordinates. For example, when obtaining the inclination of the ellipse, the inclination of the ellipse is twice the inclination of the straight line connecting the center O of the ellipse and the four intersections A, B, C, and D.
[0018]
Further, a new center coordinate may be calculated based on the intersection. For example, the midpoint of the line segment AC or the line segment BD is set as the center coordinate of the new analyzed image. Alternatively, the intersection of the straight line AC and the straight line BD is set as the center coordinate of the new analyzed image. Alternatively, the foot of the perpendicular drawn from the point B or D to the straight line AC and from the point A or C to the straight line BD is set as the center coordinate of the new analyzed image. Alternatively, the intersection of the least-squares straight line for points A, O, and C and the least-squares straight line for points B, O, and D is set as the center coordinate of the new analyzed image.
[0019]
The operation of calculating the five parameters of the ellipse based on the new center coordinates may be repeated a specified number of times.
[0020]
The operation of calculating the five parameters of the ellipse based on the new center coordinates may be repeated until the amount of change of the parameter becomes equal to or less than a predetermined value.
[0021]
Furthermore, the present invention can be realized in the form of a method or computer software.
[0022]
DESCRIPTION OF THE PREFERRED EMBODIMENTS
Hereinafter, embodiments of the present invention will be described with reference to FIGS. In this embodiment, for example, the image analysis of the present invention is performed on an image using a computer system. The computer system itself is well known and will not be described. In the description related to this embodiment, the operation steps are indicated by blocks, but one or more of the blocks are collectively or one step is constituted by a plurality of hardware elements. However, it is needless to say that it may be implemented in the form of hardware.
[0023]
FIG. 2 shows an outline of the parameter extracting operation of the present embodiment. This is the central part of the present invention. In FIG. 2, the analyzed still image is preprocessed in a preprocessing step S1, and then processed in a provisional center calculation step S2, a major axis / minor axis calculation step S3, an inclination calculation step S4, and an evaluation step S5. The pre-processing step S1 is to remove or reduce factors that may cause erroneous recognition in the future, such as thinning an image or removing noise. The provisional center calculation step S2 is for calculating the center coordinates in various modes according to the quality of the image. The major axis / minor axis calculation step S3 calculates the major axis and the minor axis using a plurality of properties of the ellipse. In the inclination calculation step S4, the inclination of the image is calculated from the calculated center coordinates, major axis, minor axis, and the like. The evaluation step S5 evaluates the obtained parameters (three circles and five ellipses). If the evaluation is negative, the center coordinates are reset and the parameters are calculated again. The same routine is repeated until the evaluation becomes positive.
[0024]
Next, the above-described steps S1 to S5 will be described in detail. FIG. 3 shows details of the preprocessing step S1. First, the image to be analyzed is determined in step S11 as a black-and-white image or a full-color image. If it is a monochrome image, it is determined in step S12 whether or not it is a 1-bit image. If either is “No” in the determination at step S11 or S12, binarization is performed by filter processing including threshold processing at step S13. Therefore, the analyzed image A passed to the next step S14 is a black and white binary analyzed image B. In step S14, an edge portion is extracted by a local operator including Laplacian. Further, in step S15, an appropriate threshold value is set for the edge strength calculated in step S14, and the binarized analyzed edge image C is again set. The coordinate values of the edge image are stored in a buffer 1 (not shown). Image C is sent to provisional center calculation step S2.
[0025]
FIG. 4 shows details of the provisional center calculation step S2. In FIG. 4, the method of calculating the center coordinates is changed depending on the state of the edge image. First, when the edge image includes a straight line component having a certain length or more as shown in FIG. 5, this is removed in step S201. Next, as shown in FIG. 6, the scanning lines are moved in parallel with the X-axis and the Y-axis of the image, and only when the edge image cuts out these scanning lines, that is, two of the intersections with the edge image that do not adjoin are two. Only when there are pairs, the midpoints are stored in buffers 2 and 3 (not shown) (steps S205 and S213). If the number of intersections is one or less, or if there are three or more, no midpoint is calculated. For example, there are cases where the edge image is blurred as shown in FIG. 7 and there is only one set of intersections, or where there is noise and there are three or more sets of intersections as shown in FIG. When the scanning line is moved in parallel with respect to both axes, and the number of midpoints stored in the buffers 2 and 3 is both equal to or greater than a threshold value (5 in this embodiment), the equation of a straight line passing through each midpoint is minimized. It is calculated by the square method (steps S209 and S217), the intersection of these two straight lines is obtained in step S218, and this is used as the output of the temporary center calculation step S2. On the other hand, if any of the middle points stored in the buffers 2 and 3 is less than the threshold, the process proceeds to step S219. FIG. 9 shows the flow of the process in step S219. This part is the same as the method by Tsuji et al. The details of the processing itself are clear from the description of FIG. If the center cannot be determined even in step S219, the center is determined by the center of gravity of the edge pixel, or the five parameters of the ellipse are determined by the non-linear least square method or the like.
[0026]
The details of the operation in FIG. 4 are as follows.
[Step S200] It is determined whether there is a line segment having a certain length or more in the edge image. Such line segments are noise. If there is such a line segment, the process proceeds to step S201. If not, the process proceeds to step S202.
[Step S201] Line segments are removed from the edge image.
[Step S202] An index i for drawing a vertical straight line is initialized to 0.
[Step S203] A straight line X = i is drawn.
[Step S204] It is determined whether there are two sets of intersections that are not adjacent to the edge image. If so, the process proceeds to step S205 because the data is valid. Otherwise, the process proceeds to step 206.
[Step S205] The midpoint of the intersection is calculated and stored in the buffer 2. Thereafter, the process proceeds to step S206.
[Step S206] Increment the index i by one.
[Step S207] It is determined whether or not the index is smaller than a predetermined value w.
w is the horizontal width of the target area. If it is smaller, the process returns to step 203 and the process is repeated. If not, the process proceeds to step S208.
[Step S208] If the number of middle points in the buffer 2 is equal to or larger than the threshold, the process proceeds to step S209 to obtain a straight line for center calculation. If it is less than the threshold value, it is difficult to calculate a straight line accurately, so the process proceeds to step 219 (FIG. 9).
[Step S209] A midline is calculated from the midpoint by the least squares method.
[Step S210] An index j for drawing a horizontal straight line is initialized to 0.
[Step S211] A straight line Y = j is drawn.
[Step S212] It is determined whether there are two sets of intersections that are not adjacent to the edge image. If so, the process proceeds to step S213 because the data is valid. Otherwise, the process proceeds to step 214.
[Step S213] The midpoint of the intersection is calculated and stored in the buffer 3.
[Step S214] The index j is incremented by one.
[Step S215] It is determined whether or not the index is smaller than a predetermined value h.
h is the vertical height of the target area. If it is smaller, the process returns to step 211 and the process is repeated. If not, the process proceeds to step S216.
[Step S216] If the number of middle points in the buffer 2 is equal to or larger than the threshold, the process proceeds to step S217 to obtain a straight line for center calculation. If it is less than the threshold value, it is difficult to calculate a straight line accurately, so the process proceeds to step 219 (FIG. 9).
[Step S217] A midline is calculated from the midpoint by the least squares method.
[Step S218] The intersection of the two middle lines is obtained and output.
[Step S219] The center is determined from the midpoint of the edge having the same inclination (FIG. 9).
[0027]
The above processing is performed in the provisional center calculation step S2, and the process proceeds to the major axis / minor axis calculation step S3.
[0028]
Here, before describing the detailed procedure of the major axis / minor axis calculation step S3, the base of the major axis / minor axis calculation will be described first. That is, a method of calculating the lengths of the major axis and the minor axis using the graphic properties of the ellipse in the major axis / minor axis calculation step S3 will be described.
[0029]
The output value of the provisional center calculation step S2 is used as the coordinate value of the provisional center O of the ellipse image, and the points A and B are defined on the circumference of the ellipse so that the angle AOB becomes 90 degrees. . Here, a and b are the length of the major axis and the minor axis of the ellipse.
[0030]
(Equation 1)

The output value of the provisional center calculation step S2 is O (X, Y), and a value Φ sufficiently smaller than the value 90 is set as a parameter (in this embodiment, Φ = sin ^-1 1/10), and determines all coordinate sets (A, B) such that the angle AOB is not less than (90−Φ) and not more than (90 + Φ) among the edge image coordinate values stored in the buffer 1. 1 / OA for these determined sets ² + 1 / OB ² Is calculated, and a frequency distribution of the value is obtained. If the category having the highest frequency is p, this is 1 / a ² + 1 / b ² It should be. Next, another relational expression relating to a and b is used. If an arbitrary point on the circumference of the ellipse is A, a straight line that passes through the center O of the ellipse in parallel with the inclination of the tangent of the ellipse at the point A is drawn, and the intersection points with the circumference of the ellipse are points B and C,
[0031]
(Equation 2)

Has the relational expression In the case of a digital image, the points B and C may not exist, but two sets of coordinates stored in the buffer 1 which are located opposite to each other with respect to the center O of the ellipse and whose distance from the straight line is the shortest. Are calculated, and the legs of the perpendicular drawn straight down from the edges are defined as points B and C. Again, the area of the triangle ABC is obtained for all the edge coordinates A, and the frequency distribution of the value is obtained. If the category having the highest frequency is q, this should be ab. FIGS. 13A and 13B show the above two graphic properties. At this time, a and b are quadratic equations related to t.
[0032]
(Equation 3)

It becomes two solutions of. Solve this,
[0033]
(Equation 4)

Get.
[0034]
Next, details of the major axis / minor axis calculation step S3 will be described. The major axis / minor axis calculation step S3 can be further divided into steps S31, S32, and S33. Step S31 is the above-mentioned p = 1 / a ² + 1 / b ² Is what you want. Step S32 is for obtaining the above-mentioned q = ab. In step S33, the major axis a and the minor axis b are obtained from p and q, and further, it is determined whether the edge image is a circle or an ellipse. FIGS. 10, 11, and 12 show the flow of the processes in steps S31, S32, and S33, respectively. These may be processed in parallel or in series.
[0035]
The process of step 31 in FIG. 10 is as follows.
[Step S311] The index i, j is initialized to 1.
[Step S312] The i-th coordinate Ai of the buffer 1 is extracted.
[Step S313] The j-th coordinate Bj of the buffer 1 is extracted.
[Step S314] It is determined whether or not the angle AiOBj is equal to or more than (90−Φ) degrees and equal to or less than (90 + Φ) degrees. If so, the process proceeds to step S315 because it is not considered, and if not, the process proceeds to step S316.
[Step S315] (OAi) is added to the histogram. ^-2 + (OBj) ^-2 Store the value of.
[Step S316] Increment the index j by one.
[Step S317] It is determined whether the j-th data in the buffer 1 is empty.
If not empty, the process returns to step S313 to repeat the processing. If empty, the process proceeds to step S318.
[Step S318] i = i + 1 and j = 1 are set.
[Step S319] It is determined whether the i-th data in the buffer 1 is empty. If not empty, the process returns to step S312 to repeat the process. If empty, the process proceeds to step S320.
[Step S320] The category of the maximum frequency is substituted for p.
[0036]
The processing in step 32 in FIG. 11 is as follows.
[Step S321] Initialize an index to i = j = k = 1 / = 0.
[Step S322] The i-th coordinate Ai of the buffer 1 is extracted.
[Step S323] The inclination of the edge at the coordinates Ai is calculated.
[Step S324] Straight line 1 passing through OAi ₁ : F (x, y) = 0 is calculated.
[Step S325] A straight line l passing through the coordinates O and having a slope S ₂ : G (x, y) = 0 is calculated.
[Step S326] The j-th coordinate Bj of the buffer 1 is extracted.
[Step S327] Straight line l ₂ And the distance L between the coordinates Bj _j And coordinates B _j Foot B ' _j Is calculated.
[Step S328] f (B ′ _j )> = 0. If so, the process proceeds to step S329. Otherwise, the process proceeds to step S334.
[Step S329] It is determined whether or not k = 0. If so, the process proceeds to step S330. If not, the process proceeds to step S332.
[Step S330] L _b = L _j , B = B ' _j And
[Step S331] Let k = 1.
[Step S332] L _b > L _j Is determined. If so, the process proceeds to step S333. Otherwise, the process proceeds to step S334.
[Step S333] L _b = L _j , B = B ' _j And
[Step S334] It is determined whether l = 0. If so, the process proceeds to step S335. Otherwise, the process proceeds to step S337.
[Step S335] L _c = L _j , C = B ' _j And
[Step S336] Let l = 1.
[Step S337] L _c > L _j Is determined. If so, the process proceeds to step S338. Otherwise, the process proceeds to step S339.
[Step S338] L _c = L _j , C = B ' _j And
[Step S339] j = j + 1 is set.
[Step S340] It is determined whether the j-th data in the buffer 1 is empty. If not empty, the process returns to step S326 to repeat the processing. If empty, the process proceeds to step S341.
[Step S341] The area of the triangle AiBC is obtained and stored in the histogram 2.
[Step S342] j = 1 and i = i + 1.
[Step S343] It is determined whether the i-th data in the buffer 1 is empty. If not empty, the process returns to step S322 to repeat the processing. If empty, the process proceeds to step S344.
[Step S344] The category of the maximum frequency is substituted for q.
[0037]
P and q necessary for obtaining the major axis a and the minor axis b were determined. Then, in step S33 of FIG. 12, the major axis a and the minor axis b are obtained, and a circle / ellipse discrimination is performed. That is, when the value of the ratio between a and b is equal to or less than the threshold value (1.05 in this embodiment), it is determined that the given edge image is a circle whose center is O (X, Y) and whose radius is a or b. Pass to the correction step. In this correction step, a parameter having a higher degree of conformity is calculated by a least square method or the like using the output value of step S33 as an initial value. Of course, the output may be performed with the initial value. On the other hand, if it is determined in step S33 that the edge image is an ellipse, the process proceeds to a tilt calculation step S4 to determine the remaining one parameter, the tilt.
[0038]
The processing in step S33 in FIG. 12 is as follows.
[Step S345] The major axis a and the minor axis b are obtained from p and q.
[Step S346] It is determined whether a / b <= T. If so, the process proceeds to step S347. Otherwise, the process proceeds to step S348.
[Step S347] The edge image is determined to be a circle, and the process proceeds to a desired correction step.
[Step S348] The edge image is determined to be an ellipse, and the flow advances to step S4.
[0039]
Next, the processing of the inclination calculation step S4 will be described. FIG. 14 shows the flow of the process in the inclination calculation step S4. First, an ellipse U having an axis parallel to the X-axis and Y-axis having a center O, a major axis a, and a minor axis b is drawn (step S401). If the intersection of the ellipse and the edge image is point A, point B, point C, and point D as shown in FIG. 15, the line segment AC and the line segment BD are orthogonal, and the intersection point coincides with the center of the ellipse. . The point of intersection of the straight line OP and the ellipse U with respect to the point P on the edge image is defined as P ′, and the length of the line segment PP ′ is defined as the distance between the ellipse and the pixel on the edge image. Now, the coordinate plane is divided into the following four areas (step S402). These are defined as area 1 (x> = X and y> Y), area 2 (x <X and y> = Y), area 3 (x <= X and y <Y), and area 4 (x> X and y < = Y). In each area, a pixel on the edge outside the ellipse U and having the minimum distance to the ellipse U and a pixel on the edge inside the ellipse U and the minimum distance to the ellipse U are selected. Then, the intersection of the line segment connecting them and the ellipse U is calculated, and the points are set to point A, point B, point C, and point D in order (step S403). Assuming that the inclination of the straight line connecting the time point O and any one of the four intersections (point A in the present embodiment) is θ, 2θ is the inclination of the ellipse to be obtained (step S404). Thus, at this point, all five parameters of the ellipse can be calculated.
[0040]
If the intersection between the line segment AC and the line segment BD is taken, this should ideally coincide with the center coordinate of the ellipse, but does not actually coincide. Therefore, when the inclination calculation step S4 calculates a parameter that is not satisfied by the evaluation step S5, the newly calculated center is used as the output value of the temporary center calculation step S2, and the process returns to the major axis / minor axis calculation step S3 again. This operation is repeated until the evaluation step S5 is satisfied. In the evaluation step S5, the condition may be such that the angle between the line segment AC and the line segment BD is within the reference value, or the distance between the intersection of the line segment AC and the line segment BD and the center coordinate of the ellipse calculated immediately before. May be within the reference value, the distance between the line segment AC and the midpoint of the line segment BD may be within the reference value, or the midpoint of the line segment AC or the line segment BD may be one of the line segments. The degree of riding on the top may be used as a reference. Alternatively, a loop that returns from the evaluation step S5 to the major axis / minor axis calculation step S3 by the required number of times may be rotated, and a parameter obtained after the required number of loops may be used as the output of the evaluation step S5. However, in order to rotate such a loop, it is necessary that at least one set of intersection points (for example, point A and point C) corresponding between the edge image and the ellipse U has been obtained. In this case, it is possible to replace the midpoint of the line segment AC with the new center coordinates. If a corresponding set of intersections has not been determined, the inclination of a straight line connecting one of the determined intersections and the center coordinates is defined as θ, and the loop is not performed. If no intersection can be obtained, the inclination cannot be calculated by this method, and the inclination is obtained by means such as the least square method. However, none of the images used in this example had such noise that no intersection could be found.
[0041]
【The invention's effect】
According to the present invention, it is possible to calculate five parameters of an ellipse including a circle without performing complicated calculations. Also, parameters can be calculated even when the edge image contains noise or a break occurs.
[Brief description of the drawings]
FIG. 1 is a block diagram for explaining the present invention.
FIG. 2 is a flowchart generally showing an embodiment of the present invention.
FIG. 3 is a diagram showing a detailed algorithm of step S1 in FIG. 2;
FIG. 4 is a diagram showing a detailed algorithm of step S2 in FIG. 2;
FIG. 5 is a diagram illustrating step S201 in FIG.
FIG. 6 is a diagram illustrating a midpoint calculation method in FIG.
FIG. 7 is a diagram showing a specific example in which the intersection between an edge image and a straight line is only one point in FIG.
FIG. 8 is a diagram showing a specific example in a case where there are three or more intersections between an edge image and a straight line in FIG.
FIG. 9 is a flowchart showing a detailed algorithm of step S219 in FIG. 4;
FIG. 10 is a flowchart showing a detailed algorithm of a part of step S3 (step S31) in FIG. 2;
FIG. 11 is a flowchart showing a detailed algorithm of part of step S3 (step S32) in FIG. 2;
FIG. 12 is a flowchart showing a detailed algorithm of a part of step S3 (step S33) in FIG. 2;
FIG. 13 is a diagram showing the graphic properties of an ellipse.
FIG. 14 is a flowchart showing a detailed algorithm of step S4 in FIG. 2;
FIG. 15 is a diagram illustrating a slope calculation method in FIG.
[Explanation of symbols]
11 Preprocessing unit
12 Temporary center calculation unit
13 Long and short diameter calculator
14 Slope calculation unit
15 Evaluation section
S1 Pre-processing step
S2 Temporary center calculation step
S3 major axis / minor axis calculation step
S4 Slope calculation step
S5 Evaluation step

Claims (12)

In an image analysis device that analyzes a circle and an ellipse included in a numerically analyzed image,
Center coordinate calculating means for calculating center coordinates from the analyzed image;
Diameter calculating means for calculating the radius of the circle or the major axis and the minor axis of the ellipse based on the center coordinates,
The diameter calculating means is:
(1) If the center of the ellipse is point O and points A and B are set on the circumference so that the angle AOB is 90 degrees, the sum of the reciprocals of the squares of the lengths of the line segments OA and OB is obtained. (2) Take point A on the circumference of the ellipse, and if the intersection of the ellipse with a straight line passing through the center O and parallel to the tangent to the ellipse at point A is point B and point C, the area of triangle ABC is An image analyzing apparatus for calculating a radius of a circle or a major axis and a minor axis of an ellipse using the property of being constant. 2. The image analysis apparatus according to claim 1, wherein the value of the ratio between the major axis and the minor axis is compared with a predetermined threshold to determine whether the analyzed image is a circle or an ellipse. 3. The image analysis device according to claim 2, wherein when the analyzed image is determined to be a circle, one of the major axis and the minor axis is determined as the radius of the circle. The image analysis device according to claim 3, wherein when the analyzed image is determined to be a circle, the calculated center coordinates and radius are corrected so as to be more suitable for the analyzed image. The center coordinates of the ellipse calculated by the center coordinate calculating means and the diameter calculating means, the major axis and the minor axis are used as parameters, and the intersection of the ellipse having an axis parallel to the coordinate axis and the edge image of the target image is calculated. 2. The image analyzing apparatus according to claim 1, further comprising a tilt calculating unit that calculates a tilt of the analyzed image based on the intersections. 6. The image analysis device according to claim 5, wherein the inclination calculating means calculates an inclination of the analyzed image based on the intersection and the center coordinates. The image analysis device according to claim 5, wherein a new center coordinate is calculated based on the intersection. The image analysis device according to claim 7, wherein the operation of calculating the five parameters of the ellipse based on the new center coordinates is repeated a specified number of times. The image analysis apparatus according to claim 7, wherein the operation of calculating the five parameters of the ellipse based on the new center coordinates is repeated until the amount of change of the parameter becomes equal to or less than a predetermined value. In an image analysis method for analyzing a circle and an ellipse included in a numerically analyzed image,
A center coordinate calculation step of calculating center coordinates from the analyzed image;
A diameter calculation step of calculating a radius of a circle or a major axis and a minor axis of an ellipse based on the center coordinates,
The diameter calculating step includes:
(1) If the center of the ellipse is point O and points A and B are set on the circumference so that the angle AOB is 90 degrees, the sum of the reciprocals of the squares of the lengths of the line segments OA and OB is obtained. (2) Take point A on the circumference of the ellipse, and if the intersection of the ellipse with a straight line passing through the center O and parallel to the tangent to the ellipse at point A is point B and point C, the area of triangle ABC is An image analysis method comprising calculating a radius of a circle or a major axis and a minor axis of an ellipse using the property of being constant. The image analysis method according to claim 10, wherein the center coordinate calculation step changes a center coordinate calculation method according to a state of the edge image. The center coordinate calculation method includes a method based on an intersection of a series of parallel lines and an edge image of an ellipse analyzed image, a method based on a center of gravity of the edge image, and a method of applying a nonlinear least squares method to the edge image. The image analysis method according to claim 11, further comprising :

Images