JPH0143352B2 - - Google Patents

Description

[Detailed Description of the Invention] (1) Technical Field of the Invention The present invention relates to a method for detecting the center position of an ellipse image, and in particular, to correctly detect the center position even when the outer ellipse is partially missing. Regarding the method.

(2) Technical Background and Problems In image processing, figures are often moved, rotated, and enlarged or reduced. Also, when performing pattern recognition, similar processing is performed to bring the figure to the correct position.

The outer shape is an ellipse (including a circle as a special case)
A figure whose outer shape is an ellipse and which contains various characters, symbols, etc. (for example, a seal, a seal, etc.)
In the case of an ellipse (hereinafter, these figures are simply referred to as ellipse images), if you know the center position, the lengths of the major and minor axes, and the inclination of the ellipse, you can move its position for image processing, pattern recognition, etc. , rotation, enlargement, reduction, etc. can be easily performed.

When the center position of the ellipse image is detected, the major axis length is detected from the length of the chord, that is, the length of the cut piece of the straight line passing through the center position cut by the outer ellipse of the ellipse image, and the minimum value of the chord is detected. Since the short axis length is detected by , and the inclination of the elliptical image is detected from the inclination of the long axis or the short axis, detection of the center position of the ellipse image is most problematic.

Conventional methods for determining the center position of an elliptical image include (a) simply finding a rectangular area PQRS that circumscribes the elliptical image E, and calculating the center position of the elliptical image E from that center position, for example, as shown in FIG. A method for detecting the center position C, (b) Several points on the outer ellipse of the elliptical image E that are separated by a certain distance or more, for example, 6 points A, B, D,
There was a method in which the center was found from F, G, and H, and the center position C of the elliptical image E was detected by taking the histogram.

Method (a) can correctly detect the center position if the outer ellipse is complete, but if a part of the ellipse image is printed or displayed faintly, or if a part of the outer ellipse is
When the MN part is missing, its circumscribed rectangle is
Since P′Q′RS, its center position is C′,
There was a drawback that the correct center position C of the ellipse image could not be detected.

The method (b) has the disadvantage that the procedure for determining the center position is complicated, takes time to calculate, and requires a large amount of storage capacity.

Also, if the six points of interest are all on an ellipse, as shown by the symbol H in Figure 1b, the coordinates of the center, which is close to the true position, can be found, for example, as shown by the symbol I in Figure 1b. If six points are selected, the coordinates of the center will be found at a position far away from the true center position.

Furthermore, in method (b), when the ellipse is missing,
The center may not be noticeably high on the histogram. Also, depending on the image drawn inside the ellipse, the center may be found at a different position. Since the frequency of the histogram is unknown, a large amount of memory for the histogram is required.

There are also various forms when an ellipse is missing. For example, in the case of A in Figure 1 c, the image shows l _nax
The center can be found by searching for , but in b and c of c above,
The problem was that it was not known whether the l _nax passing through the image would pass through the center of the ellipse, and the calculations were complicated and time-consuming.

(3) Purpose of the Invention The purpose of the present invention is to detect the center position of an ellipse in image processing or pattern recognition, even when a part of the ellipse is missing, when the target image is known to be an ellipse image. The object of the present invention is to provide a method for detecting the center position of an ellipse image, which can accurately detect the center position.

(4) Structure of the Invention In order to achieve this object, the ellipse image center position detection method of the present invention detects the center position of an ellipse image. a maximum rotation angle detecting means for detecting a maximum rotation angle that is projected onto a reference coordinate axis and at which the contact length of an ellipse image in a direction perpendicular to the projection at the end of the projection is the longest; The present invention is characterized by having a center position detecting means for detecting the center position of the longest chord when the length of the chord of the ellipse image in the direction is the longest.

(5) Embodiments of the Invention In the present invention, when a part of an ellipse in the outer shape of an ellipse image is missing, the length of the chord parallel to the chord of the missing part is sequentially determined, and the length of the chord is calculated. The center position of the ellipse image is detected from the center position of the longest chord.

Hereinafter, one embodiment of the present invention will be described based on FIGS. 2 to 7.

First, the principle of the present invention will be explained with reference to FIGS. 2 to 6.

Figure 2 shows typical types of elliptical images that are the subject of the present invention, where a ₁ is a circle E _al , a ₂ is a partially missing circle E _a2 , and b ₁ is a circle with characters or symbols inside. , a circle image E _b1 containing an image W such as a figure, b ₂ is a circle image E _b2 with a part of the outer circle missing, c ₁ is an ellipse E _c1 , c ₂ is an ellipse with a part missing E _c2 , d ₁ is an ellipse image that image W contains inside
E _d1 and d ₂ are ellipse images E _d2 with a part of the outer ellipse missing
This is the case.

By the way, in the case of an ellipse (including a circle as a special case), consider an arbitrary straight line, and the chord parallel to the straight line becomes maximum when it passes through the center position C of the ellipse.
Therefore, by pulling a string in an arbitrary direction, the center position C of the ellipse can be determined from the coordinates of both ends of the string when the string reaches its maximum length.

However, when a part of the ellipse is missing, the maximum length of the string cannot be detected unless the direction of the string is in a specific direction. This situation will be explained with reference to FIG. 3. In the case of the string _G1 , one end is within the missing arc MN of the elliptical image E, so the maximum value cannot be detected clearly. In the case of string _G2 , when it passes through the position of string _G'2 on its way to center C, it enters the part of arc MN where one end of string _G2 is missing. Therefore, the maximum value of the length of the string in the direction of string _G2 cannot be detected. In the case of a string parallel to string MN, the string G ₃ with the maximum length is detected because the string does not pass through the missing part in the process of passing through the center C. Therefore, the coordinates of both ends of string G ₃ are A (X ₁ , Y ₅ ), B (X ₂ ,
Y ₂ ), the center position C can be detected as the average value of each X coordinate and Y coordinate.

Unless a string parallel to string MN is used, in the process of finding the maximum value of the string length, one end of the string will always end up in the missing part of arc MN, so the position where the arc length is maximum cannot be detected. Therefore, it is necessary to detect the string MN of the missing part.

Note that, as the coordinates of each chord, only the chord coordinates related to the outer ellipse of the elliptical image E are detected, so the presence or absence of the internal image W does not matter. Naturally, the type of image, whether or not there are missing parts in the image, etc. do not matter.

Therefore, although the following explanation will be made regarding an elliptical image having only an elliptical portion of the outer shape, the contents are directly applicable to a general elliptical image having an image inside.

The fourth method for detecting the missing string MN
This will be explained with reference to FIGS.

Figure 4 shows an elliptical image E with a missing part displayed on the display screen, where C is the center position of the ellipse image, P, Q, R, and S are the display screen, and Z is the display screen PQRS. Center, MN is the chord of the missing part, X, Y
indicates the respective coordinates. Q is the origin of the coordinates.

In this state, the elliptical image E is projected on the X coordinate, and the coordinates X _L1 and X _R1 at both ends of the projection are detected.

Next _, draw perpendicular lines NL, _{NR 1} to _{the X coordinate at the coordinates X L1 ,}
Find l _L1 and l _R1 . Since the actual ellipse image E is not a geometric ellipse, the contact lengths l _L1 and l _R1 are often close to zero, but are detected as having a certain length.

In the case of FIG. 4, l _L1 is a point and l _R1 is detected with a certain length, so l _R1 >l _L1 .

The contact lengths l _L1 and l _R1 are compared and the larger l _R1 is stored in memory. Next, as shown in Fig. 5, the elliptical image E is rotated by a fixed angle, for example, by one angle, about the center Z of the display screen PQRS, and at each rotation angle position, as in the case of Fig. 3, the elliptical image E is rotated about the center Z of the display screen PQRS. The perpendicular lines NL ₂ , NR 2 , NL ₃ , _{NR 3 , ... at the coordinates XL 2 , XR 2 , XL 3 , XR 3 ... at both ends} of the projection are the elliptical image E
The contact lengths l _L2 , l _R2 , l _L3 , l _{R3 .} . . are sequentially compared in size, and the larger one is stored in the memory.

In this way, the magnitude of the contact length at each rotation angle is compared, and the rotation angle at which the contact length is maximum, that is, the maximum rotation angle θ _nax is detected.

It is clear from the figure that the contact length is at its maximum when the string MN reaches the position M'N' perpendicular to the X axis, but this point will be further explained using Figure 6. .

Figure 6 shows the position where the string MN is perpendicular to the X axis.
This shows the elliptical image E when reaching M'N'. If the part where the perpendicular lines NL _nax and NR _nax in the X coordinates X _Lnax and X _Rnax at both ends of the projection contact the elliptical image E, that is, the contact length is l _Lnax and l _Rnax , then l _Lnax ≒ 0,
l _nax = M′N′. Except for the case shown in Figure 5, l _L , l _R
<<M'N' is considered to be close to zero, so in the case of Fig. 6, the contact length becomes M'N' and takes the maximum value.

Therefore, from the condition where the contact length is maximum, the string
The position of M′N′ and the rotation angle at that time, that is, the maximum rotation angle θ _nax can be detected. If the position of the string M'N' and the maximum rotation angle θ _nax are known, the original position MN of the string can be found using a known coordinate transformation method.

Next, if we detect a string that is parallel to the chord M'N' and has the longest length, that is, the longest chord M _nax N _nax , the center position C' of the elliptical image E in FIG.
It can be found as the center position of M _nax N _nax .

If this center position C' is rotated counterclockwise by the maximum rotation angle θ _nax around the display screen Z using a known coordinate transformation method, the center position C at the position of the original elliptical image E can be determined.

The maximum rotation angle is 180 degrees, and the chord M'N', that is, the maximum rotation angle θ _nax and the longest chord M _nax N _nax , are always detected within the rotation angle of 0 to 180 degrees, and therefore the center of the ellipse image Position C can be detected.

The above settings were made using the case of projecting an elliptical image onto the X-axis as an example, but by simultaneously projecting onto the
It is clear that M'N', the maximum rotation angle θ, and the longest chord M _nax N _nax are detected, and therefore the center position C of the ellipse image can be detected.

Generally speaking, if you draw n coordinate axes at intervals of 180/n degrees and project onto them, 0 to 180°/n
Each of the above values including the center position of the ellipse image can be detected within the rotation angle of .

FIG. 7 shows one embodiment of the present invention. By projecting an elliptical image on the X-axis and Y-coordinates and rotating it between 0 and 90 degrees, the chord M'N' and the maximum rotation angle are This is an embodiment in which θ _nax , the longest chord M _nax N _nax , the center position C' of the elliptical image at the maximum rotation angle position, and the center position C at the original ellipse image position are detected.

In FIG. 7, 1 is a counter that measures the rotation angle of the elliptical image E, 2 is an image memory in which the elliptical image E is stored, and 3 is a counter that reads out the contents of the image memory 2 and counters every time the contents of the counter 1 change. 1 is a rotation circuit that outputs ellipse image data rotated by the content; 4 is a rotation image memory that stores the rotated ellipse image; 5 is the coordinates of both ends of the ellipse image E projected on the X axis, X _L , an X-direction projection extraction circuit that detects _R ;
6 is the contact length l _L , l _R in the Y-axis direction at the coordinates X _L , X _R
7 is a Y-direction contact length register that stores the Y-direction contact length, and 9 is a Y-direction contact length register that stores the longest contact length in the Y direction.
Direction longest contact length register; 8 is a Y direction longest contact length comparator that compares the contact length of the Y direction contact register 7 with the contact length of the Y direction longest contact length register 9; 10 is the longest contact length in the Y direction at each rotation angle position; A Y-direction longest string coordinate detection circuit detects the maximum value and minimum value of the Y-coordinate of the Y-direction longest chord having a length of . A Y-direction longest string center position detection circuit detects the center position of the Y-direction longest chord at a rotation angle position, and 12 and 13 are first and second Y-direction longest string center position registers that store the coordinates of the center position of the Y-direction longest chord. , 14 is a first rotation angle register that stores the rotation angle. 15 to 24 are respective circuits when projected in the Y-axis direction, and correspond to the respective circuits when projected in the aforementioned X-axis direction. That is, 15 is a Y-direction projection extraction circuit that detects the coordinates Y _U , Y _D (not shown) of both ends of the elliptical image E projected on the Y axis, and 16 is a contact in the axial direction at Y coordinates Y _U , Y _D X-direction contact length comparison circuit that calculates the lengths l _U and l _D and outputs the larger one, 17
is the X-direction contact length register that stores the X-direction contact length, 19 is the X-direction longest contact register that stores the longest contact length in the X-direction, and 18 is the contact length of the X-direction contact length register 17 and the X-direction longest contact length register. 19
X-direction longest contact length comparator for comparing the contact lengths of 2
0 is an X-direction longest string coordinate detection circuit that detects the maximum and minimum values of the X coordinate of the X-direction longest chord having the longest length in the X-axis direction at each rotational angular position, 2
1 is an X-direction longest string center position detection circuit that detects the center position of the X-direction longest string at each rotation angle position;
22 and 23 are first and second X-direction longest chord center position registers that store the coordinates of the center position of the longest chord in the X direction, and 24 is a second rotation angle register that stores the rotation angle. 25 is the longest contact register 9 in the Y and X directions
and 19, comparing the longest contact lengths l _Ynax and l _Xnax ,
A comparator that outputs "0" when l _Ynax > l _Xnax and "1" when l _Ynax < l _Xnax , 26 receives the rotation angle data of the first and second rotation angle registers 14 and 24, and compares 27 is a rotation angle data selector which outputs the rotation angle data of the first rotation angle register when the output of the device 25 is "0", and outputs the rotation angle data of the second rotation angle register when the output is "1"; and the coordinate data of the second X-direction longest string center position registers 13 and 23 are received, and when the output of the comparator 25 is "0", the coordinate data of the second Y-direction longest string center position register 13 is received, and when it is "1", the coordinate data of the second Y-direction longest string center position register 13 is received. The longest string center position data selector 28 outputs the coordinate data of the second X-direction longest string center position register 23, and the longest string center position data from the rotation angle data selector 26 and the longest string center position data from the longest string center position data selector 27. 29 is a center position data register that stores the output of the center position detection circuit 28.

Next, the operation shown in FIG. 7 will be explained.

A reset pulse S _re is input through the signal line a, and the counter 1, 9, 13, 14, etc.
Resets registers 19, 23, and 24.

The counter 1 outputs the count contents to the data line c, and outputs ``0'' to the signal line b until the rotation angle reaches 90 degrees, and outputs ``1'' when the rotation angle exceeds 90 degrees.

The rotation circuit 3 receives the data of the ellipse image in the image memory 2 from the data line d every time the content of the counter 1 from the data line c changes, for example, every time "1" increases, and rotates it by the content of the counter 1. The resulting ellipse image data is output to the data line e and stored in the rotation image memory 4.

The X-direction projection extraction circuit 5 reads out the contents of the rotating image memory 4 via the data line f, and outputs the data of the X coordinates X _L and X _R at both ends of the projection of the elliptical image E in the X-axis direction to the data line g. do.

The Y-direction contact length comparison circuit 6 reads the contents of the rotating image memory 4 from the data line s based on the data of the X coordinates X _L and X _R of both ends of the projection obtained through the data line g, and The contact lengths l _L and l _R in the Y-axis direction at the rotational angle positions of the X coordinates X _L and X _R are determined and stored in the Y-direction contact length register 7 via the larger data line h.

The Y-direction longest contact length comparator 8 reads the contents of the Y-direction contact length register 7 through the data line i and the contents of the Y-direction longest contact length register 9 through the data line j, and when the former is larger, outputs a control pulse to signal line k.

When the Y-direction longest contact length register 9 receives a control pulse from the signal line k, the Y-direction longest contact length register 9 receives the Y-direction longest contact length through the data line l.
The contents of the direction contact length register 7 are stored. That is, the Y-direction longest contact length register 9 stores and holds the longest contact length within the rotation angle up to that point. Therefore, at the end of the rotation up to 90 degrees, the longest contact length l _Ynax in the Y direction is stored and held.

The Y-direction longest chord coordinate detection circuit 10 detects, when the X-coordinate is changed, the position where the difference between the maximum value and the minimum value of the Y-coordinate of the spheroidal image having the X-coordinate is maximum;
That is, the maximum and minimum values of the Y coordinate of the longest chord in the Y direction having the longest length in the Y axis direction at that rotation angle position are detected and output to the data line m.

Note that when one end of the string falls over the missing part of the elliptical image E, the maximum or minimum value of the Y coordinate of the string cannot be detected. But in such a case,
Certain threshold values may be set for the maximum value and minimum value in the Y direction based on the ellipse image, and when the maximum value or minimum value of the chord corresponds to those threshold values, that data may not be used. This also applies to the X-direction longest string coordinate detection circuit 20.

The Y-direction longest string center position detection circuit 11 detects the center position of the Y-direction longest string at its rotation angle position by the arithmetic average of the maximum value and minimum value of the Y coordinate of the Y-direction longest string sent from the data line m. 1st Y
The direction is stored in the longest chord center position register 12.

The second Y-direction longest string center position register 13 stores and updates the contents of the first Y-direction longest string center position register 12 via the data line o only when receiving a control pulse from the signal line k. That is, the second Y-direction longest chord center position register 13 stores the center position of the longest chord at the rotation angle where the Y-direction contact length is the largest within the rotation angles up to that point. Therefore, as explained earlier, even if one end of the string hits the missing part MN of the ellipse image midway through, the maximum or minimum value of the Y coordinate becomes extremely large or small. , they are eventually updated, and when the final rotation reaches 90 degrees, the second Y-direction longest chord center position register 13 contains the Y-direction longest chord M _nax N _nax at the maximum rotation angle θ _nax where the Y-direction contact length is the longest. The center position of will be stored. This is the 2nd
The same applies to the direction longest chord center position register 23.

The first rotation angle register 14 stores the contents of the counter 1 via the data line c only when receiving a control pulse from the signal line k. That is, the first rotation angle register 14 stores and holds the rotation angle at which the Y-direction contact length is the longest among the rotation angles up to that point. Therefore, at the end when the rotation is completed to 90 degrees, the first rotation angle register 14 stores and holds the maximum rotation angle θ _nax at which the Y-direction contact length is the longest.

The processing related to projection in the Y-axis direction performed by the circuits 15 to 24, registers, etc. is also similar to the processing related to projection in the X-axis direction described above, so the corresponding data lines are The explanation will be omitted.

When the rotation up to 90° is completed, the longest contact length in the X-axis direction l _Xnax is stored in the X-direction longest contact length register 19, and the Y-direction contact length is stored in the second The center position of the longest chord in the Y direction is stored when the length becomes the longest, that is, at the maximum rotation angle θ _nax , and the second
The rotation angle register 24 stores the rotation angle when the X-direction contact length is the longest, that is, the maximum rotation angle θ _nax
is stored.

The comparator 25 is the longest contact length register 9 in the Y and X directions.
and 19 longest contact lengths l _Ynax and l _Xnax ,
When l _Ynax > l _Xnax , set "0" to the signal line t, and when l _Ynax <
l When _Xnax, output "1" to signal line t.

The rotation angle data select 26 sends the data of the first rotation angle register 14 to the data line u when the signal line t is "0", and sends the data of the second rotation angle register 24 to the data line u when the signal line t is "1". Output. That is, when the chord M'N' of the missing part of the elliptical image E is parallel to the Y-axis as shown in FIG. 6, the maximum rotation angle θ _nax of the first rotation angle register 14 is parallel to the X-axis. The maximum rotation angle θ _nax of the second rotation angle register 24 (not shown) is output to the data line u.

The longest string center position data selector 27 transfers the contents of the second Y-direction longest string center position register 13 to the data line v when the signal line t is "0", and transfers the contents of the second Y-direction longest string center position register 13 to the data line v when the signal line t is "1". The contents of the string center position register 23 are output. That is, as shown in FIG. 6, when the chord M'N' is parallel to the Y-axis, the contents of the second Y-direction longest string center position register 13 are the contents, and when it is parallel to the X-axis, the contents are the contents of the second X-direction longest string center position register 23. The contents are output to data line v.

The center position detection circuit 28 detects the coordinates obtained by rotating the coordinate data read by the data line v in the opposite direction by the maximum rotation angle θ _nax read by the data line u, that is, the center position C at the position of the original ellipse image. Find the coordinates of and output them to the data line w.

The center position data register 29 detects the center position detection circuit 28 from the data line w when the signal line b is "1", that is, when the rotation up to 90 degrees is completed.
In other words, the data of the center position C of the elliptical image E is stored.

Note that the data processing and calculations in steps 25 to 28 are actually performed at each rotational angle position.
At the end of the 90° rotation, each data processing result at the maximum rotation angle θ _nax is held.

(6) Effects of the Invention According to the present invention, when the target image is known in advance to be an ellipse image, even if a part of the ellipse is missing, the true center position of the image can be accurately and accurately determined. Can be detected quickly.

[Brief explanation of drawings]

Fig. 1 is an explanatory diagram of a conventional method for detecting the center position of an ellipse image, Fig. 2 is an explanatory diagram of an ellipse image that is the subject of the present invention, and Figs. 3 to 6 are illustrations of the center position detection method of an ellipse image according to the present invention. A diagram explaining the principle of the system, FIG. 7 is a block diagram of one embodiment of the present invention. In the figure, 1 is a counter, 2 is an image memory, 3 is a rotation circuit, 4 is a rotation image memory, 5 is an X-direction projection extraction circuit, 6 is a Y-direction contact length comparison circuit, 7 is a Y-direction contact length register, and 8 is a Y direction longest contact length comparator,
9 is the Y direction longest contact length register, 10 is the Y direction longest string coordinate detection circuit, 11 is the Y direction longest string center position detection circuit, 12 is the first Y direction longest string center position register, 13 is the second Y direction longest string center position register,
14 is a first rotation angle register, 15 is a Y direction projection extraction circuit, 16 is an X direction contact length comparison circuit, and 17 is an X
Direction contact length register, 18 is the Y direction longest contact length comparator, 19 is the X direction longest contact length register, 20 is the X direction longest string coordinate detection circuit, 21 is the X direction longest string center position detection circuit, 22 is the first X direction Longest string center position register, 23 is second X-direction longest string center position register, 24 is second rotation angle register, 25 is a comparator, 26 is rotation angle data selector, 27 is longest string center position data selector, 28 is center position Detection circuit and 29 indicate center position data registers, respectively.

Claims (1)

[Claims] 1 In a center position detection method that detects the center position of an ellipse image, the ellipse image is sequentially rotated and projected onto at least one reference coordinate axis, and the contact length between the projection and the ellipse image in the perpendicular direction at the end of the projection is the longest. a maximum rotation angle detection means for detecting a maximum rotation angle at which the maximum rotation angle is, and a center for detecting the center position of the longest chord when the length of the chord of the elliptical image in the direction perpendicular to the reference coordinate axis is the longest at this maximum rotation angle position. A method for detecting the center position of an elliptical image, comprising a position detecting means.