JPH0365605A - Measuring method of edge length in digital image - Google Patents

Abstract

PURPOSE:To enable precise measurement of an edge length in a digital image by taking edge gradient directions at two sample points and the relative positional relationship thereof into consideration. CONSTITUTION:First, in respect to sample points Pi and Pj of two pixels containing edges inside, a point Oc of intersection of two straight lines drawn in edge gradient directions thetai and thetaj at the sample points of the two pixels and a triangle OcPiPj set by these three points Pi, Pj and Oc, the radiuses of curvature of the two pixels are determined from a segment OcPi or OcPj or an average value of the two segments. Moreover, lengths obtained by cutting off the products of a difference in the edge gradient direction between the two pixels and the radiuses of curvature by two normals drawn from the two pixels to the edges are taken as the lengths of the edges. By determining the lengths of arcs in relation to the central angle obtained as differences in the edge gradient directions by using the relative positional relationship of the pixels and the edge gradient directions at the sample points Pi and Pj thereof, in other words, edge lengths in a digital image can be measured with high precision.

Description

DETAILED DESCRIPTION OF THE INVENTION (Technical field to which the invention pertains) The present invention is directed to sampling an analog image signal into a plurality of pixels using an A/D converter, and quantizing it to a certain gradation among a plurality of gradations. The present invention relates to a method for measuring edge lengths with high accuracy in digital images obtained by inputting them into a memory.

Specifically, the present invention is used for measuring edge curvature and measuring the circumference of an object used in object recognition processing using a digital image.

(Prior Art) First, a method of expressing edges in a digital image and a conventional method of measuring edge length will be explained, and then the accuracy and problems of the conventional technique will be described using specific examples.

(a) Conventional Edge Length Measuring Method A method for expressing edges in a digital image will be explained using FIGS. 2 and 3.

FIG. 2 is an image before digitization, and shows that object 1 and object 2 overlap with edge 3 as a boundary. In this case, edge 3 has continuous coordinates (u,
v), for example, expressed as V=f (u). Here, f is a continuous function indicating the boundary of edge 3.

FIG. 3 is a digitized version of FIG. 2. Through digitization, an image is expressed as a set of discrete pixel sample points P+ indicated by black circles in FIG. As a result, the edge is expressed as a series of pixels in which the edge resides, as shown by diagonal lines within the square in FIG. That is, the sampled coordinates P+(11+t v
i) will be expressed as a point sequence.

This edge-internal pixel is found as follows. Since the density change of the image is large in the edge portion, the density gradient Δg (u + t v t ) /ΔU.

Find Δg(uit vi)/ΔV as, for example, ΔgCut+vi)/ΔU...(1) Δg(uty vi)/ΔV...(2), and calculate its size (Δg(uit vi) )/Δu )” +(Δg(ui
A pixel where t vi )/Δv )2 is larger than a threshold value is detected as an edge-internal pixel. Here, Δg(uty
V+) is the density of the pixel whose coordinates of the sample point P+ are (u+*'V+), and the threshold value is determined to be an appropriate value through preliminary experiments or the like.

For such digital images, conventional technology
Sample point P + (u It vt)t P j (U rt
The edge length ΔSl,J corresponding to VJ) is the line segment P,
P, that is, ΔS1. J= (uJu+)”+(”/l V+)
” --(3).

(a) Problems with the prior art We will actually measure the edge lengths corresponding to two sample points in a digital image using the prior art, and discuss its accuracy and problems.

Here, as an example of the measurement target, a circle with a radius of 5 pixels and a center of 0° (1/4.-1/4) as shown in FIG. 4 is used. The result of determining the edge length corresponding to 2II11 points using the conventional method for FIG. 4 is shown in FIG. 5 (A). ,i
The th coordinate corresponds to sample point P+. The circle mark in the square in the figure is 2IllI main point P,,P,ya, (j =
i + 1) length PIPI+1 is the true arc length (vertical axis), that is, the arc corresponding to the central angle formed by the line segment ocp,,OcP, connecting the center Oc of the circle and the point P i pp This shows the result of dividing by the length of .

As a result of measuring this example, the edge lengths varied by 0.96 to 1.31 times the true values, and P2□
It was found that the maximum error of about 30% occurred in P and s. The average of the measured values is 1.081. m
M standard deviation is 0.090.

We will also investigate the case of a straight edge as shown in FIG. In the conventional technology, the lengths of edges corresponding to two sample points are all measured as l except for v'T of P and P. However, in reality, everything is 1.02 (= 1 /co
s(115)), and a measurement error has occurred.

As described above, the conventional method has a problem in that it is not possible to accurately measure edge lengths in digital images. The reason is 211 to calculate the edge length.
This method does not take into account the relative positional relationship of one point or the edge gradient direction at each sample point. More specifically, the central angle Δθ @ created by the line segment Oc P ly Oc P J, that is, obtained as the difference in the edge gradient direction
, s (= l P t Oc P s ) can be simply expressed as the lengths of the two sample points P, P,
As ΔS1. The reason lies in the fact that j is determined using equation (3). As a result, ΔS1. The measurement accuracy of J was poor.

However, the edge gradient direction refers to the normal direction of the edge at the sample point PL, as shown in FIG. The edge gradient direction θ1 at this sample point P L (u I y '/I) is the ratio of the concentration gradient at the sample point p, that is, -1Δg(utt 'i'+)/ΔV θ' = ""mm""" Calculated by (4). The method of detecting edge-internal pixels described in (a) above and the method of calculating edge gradient direction described above are just examples, and are described in Morio Onoue, 'Image Processing Handbook', Shokodo ( (1986)
Other methods are also described.

(Objective of the Invention) The object of the present invention is to accurately obtain the length of the arc with respect to the central angle obtained as the difference in the edge gradient direction using the relative positional relationship of pixels and the edge gradient direction at each sample point. The object of this invention is to measure edge lengths in digital images with high precision.

(Structure of the Invention) (Characteristics of the Invention and Differences from the Prior Art) The present invention provides digital images as the length of an edge cut by two straight lines passing through the center of the arc and the 2I11 points, that is, the length of the arc. The main feature is to measure the edge length at .

In the conventional technology, the distance is calculated as the distance between two sample points of the arc. On the other hand, the present invention differs from the prior art in that the edge length is accurately determined using the positional relationship between two sample points of the arc and the edge gradient direction.

(Example) First, the present invention will be described in detail for a case where two pixels are adjacent in vertical, horizontal, and diagonal directions, and then for a general case including these. After this, a case where the present invention is applied to measurement of edge curvature and perimeter length will be explained.

First, the present invention is implemented on a digital image in a zero-order manner, in which a pixel within an edge is detected and an edge gradient direction of the pixel is calculated. However, conventional techniques are used to detect pixels within edges and calculate edge gradient directions. The present invention will be explained in detail below.

(i) When edge-internal pixels are vertically adjacent to each other The edge-internal pixels are vertically adjacent to each other by comparing the center Oc of the 0 circle and the sample points of the edge-internal pixels shown in Figure 1(a). Let C□ and C8 be the intersections of the connected line segments 0°p, ocp or their extensions and the circle.

As is clear from FIG.
\ What is obtained is the arc length C, C, below Δθ,, = θj
It is expressed as −〇.

By increasing the precision of this arc length measurement, edge lengths corresponding to two sample points in the digital image are determined with high precision. However, regarding a circle, C3 is approximated by the average length of an arc whose radius is ocp, , oep.

If we apply the law of sine to ΔOcP,P, we get...
(5) holds, and on the other hand, from the geometrical relationship of Δ0ePiPo, Dikoha = 1. Zo6P□P, = θ1+π/2゜10
cP z P > ”-θ2+π/2 ・'-(6)
Because it is.

Manfu town = Chokoku sin (-θ8+π/2)/5in(
θj−01)=cosθ,/sinΔθx,−””・
・(7), again.

o, p, == Cogθ1/sinΔθx,z”
``''(s). Therefore, the length of the arc ΔS1,2 is obtained by further modifying equation (9).
・(10) Therefore, in cases where edge-internal pixels are adjacent, Δθ□, 3 is small, so formula (10) can be transformed into % formula % (
11) Note that the edge gradient direction is positive in the counterclockwise direction from the U-axis pressure direction.

Also, θ1. J=(θ, 10J)/2 ・・・・・・(12
).

(it) When edge-included pixels are adjacent in the horizontal direction Figure 1(b) shows how edge-included pixels are adjacent in the horizontal direction.Similar to the case (i) above, /''\ The arc length C3C4 is approximated by the average value of the length of an arc whose radius is ocp, ocp4.If the law of sine is applied to Δocp, p4, (13) holds.On the other hand.

p, p, = i, 1ocp, p, = θat Zocp4
p, = π-θ.

・・・・・・(14) Since ・・・・・・(15) Or ΔS, 4=cos(e, 4−π/2) −=(
16) is required.

(Group) When pixels within an edge are adjacent to each other in a diagonal direction Figure 1(c) shows how pixels within an edge are adjacent to each other in a diagonal direction.Let the arc lengths C, C, be ocp.

It is approximated by the average value of the length of an arc whose radius is oep.

ps ps =fΣ, 1Ocps pg =θ, +π/
Since 4゜1ocp, p, = -θ, + 3 x / 4, if we think in the same way as before, ΔS,,, = ...... (17) ...... (18) Or ΔS,,,=IIcos(8,,,-π/4) −
・(19) is required.

(Soup) General case When the contrast of the object is low.

FIG. 1(d) shows the general positional relationship of the edge-internal pixels, which are not necessarily adjacent to each other and are often separated.

It is approximated by the average value of the length of an arc whose radius is OcP.

By the way, the slope γ of the line segments P and P from the V axis is 'I =
Calculate as tan-'``工''i----(20)j-VJ. However, counterclockwise direction is positive, and O≦γ
If we take γ in this way, then θ5. at the two sample points PlyP. The geometric relationship between θj and γ is as shown in FIG. 1(e). Therefore, the angle of each vertex of ΔOcP, P is as shown in FIG. 1(f). As before, Δ
Applying the law of sine to ocp, p, the two radii of curvature are respectively
・・・・・・(21) Hyakufu-cho = Chofu-cho eos (
θ, -γ)/sinΔθ1. J・・・・・・(2
2). therefore.

......(23) Or ΔS (, 1= P (P 3 cos(θt, ty
) --(24) is obtained.

In addition, in the case of (i), (ti), and (aim) above, formula (23) is used.

%formula% Also, γ is O, x/2. This is the case of Fable/4.

(v) Accuracy The accuracy of the edge length measurement method corresponding to two sample points of the present invention will be investigated using the data shown in FIG.

The edge length ΔSiJ obtained by equation (24) is divided by the true edge length, and the result is the curve (B) shown in FIG. 5 with a black square. The 0 values measured in the range of 0.95 to 1.06 times the true value match well and the variation is small.In fact, the average measured value is 1,004. The standard deviation is 0.033.

This result will be compared with that obtained using the conventional method ((A) in FIG. 5). In the conventional method, the average of the measured values is 1
．． 081, the accuracy of the present invention is approximately 20 times that of the conventional method (=(1,081-engine)/(1,0O
4-1)) Improved.

Next, let's examine the linear edge shown in FIG. In FIG. 1(d), θ and θj are equal. That is, as the edges become straighter.

The length of the arc, that is, the edge corresponding to the two sample points PIyPJ approaches the vertical length subtracted from PI or PJ to o, p, or 0cPJ, and they match at θ1=θ. In this case, equation (23) becomes equation (24).

In Figure 6, the gradient direction of the edge at all points is 1.768 (= tan-”(-5)), so
The edge lengths P and P, which correspond to the two sample points, are 1-c.
os (1,768-yc/2) =0.981
．． P, P, is sr"j-cos (1,768-3
g/4) = 1.177. These values are the true edge lengths between each point.

(1) Application examples of the present invention The present invention can be applied to measuring the perimeter and edge curvature of an object. The zero perimeter and edge curvature are important information about an object that can be measured from a digital image. Used for recognition processing.

Conventionally, the perimeter length 2 has been determined by measuring the length of 2s points for adjacent pixels using equation (1) and summing the lengths. That is, α= Σ P I P l*x (2
5) -0. Here, n is the number of the end point.

In the conventional method, if they are adjacent in the horizontal and vertical directions, 1. If they are adjacent in the diagonal direction, there is one, and no other value could be taken. As a result, the perimeter could not be measured with high accuracy.The present invention can accurately measure the edge length corresponding to two sample points, so by applying the present invention to perimeter measurement, this measurement accuracy can be improved. can be improved.

On the other hand, the edge curvature PI, J in the digital image is 2
Difference Δθ1 in the edge gradient direction of 111 points P I t P J. J and its length ΔS1. Using j, PI, J=
lΔθ1. J/ΔS1. It is defined as Jl. Therefore, the measurement accuracy of p, , and ΔS1. There is a one-to-one correspondence with the measurement accuracy of J.

According to the present invention, ΔS1. By improving the measurement accuracy of J, the measurement accuracy of Pl and j can be improved.

(Effects of the Invention) As described above, the present invention has an advantage in that the edge length in a digital image can be measured with high accuracy by considering the edge gradient direction and relative positional relationship of two sample points. In this example, it was confirmed that the accuracy was improved by about 20 times.

[Brief explanation of drawings]

Fig. 1 is a diagram for explaining the method of measuring edge length in a digital image according to the present invention, Fig. 2 is a diagram for explaining edges in the image before digitization, and Fig. 3 is a diagram for explaining the edge length in the digital image. Figure 4 is a diagram to explain the edges in the later image, Figure 4 is a diagram showing circles on the digital image, Figure 5 is a diagram to explain the edges in the image.
The figure shows the result of dividing the edge length corresponding to two sample points by the true edge length, Figure 6 shows a straight edge on a digital image, and Figure 7 explains the edge gradient direction. This is a diagram for 1.2...object, 3...edge. ■ Fig. (0) (b) (d) Fig. Fig. (e) Dentistry Center (f) Fig. 5 Art and Crafts, Nonouchi-mura I, Jitsuro Pi Fig. ■ V,, = 1/) LJIJ+1 Figure A

Claims (2)

[Claims] (1) In the edge length measurement method in a digital image, two pixel sample points P_i, P_j that include an edge inside,
Edge gradient directions θ_i, θ_ at the sample points of the two pixels
The intersection point of the two straight lines drawn at j is O_c, and these P_i, P
Triangle O_cP_i defined by three points _j, O_c
For P_j, line segment @O_cP_i@ or @O_c
P_j@ or the average value of both to find the radius of curvature of the two pixels, and then subtract the product of the difference in the edge gradient direction between the two pixels and the radius of curvature from the two pixels to the edge. A method for measuring an edge length in a digital image, characterized in that the length cut by a line is taken as the edge length. (2) In the edge length measurement method in a digital image, two pixel sample points P_i, P_j that include an edge inside,
From the edge gradient force directions θ_i and θ_j of the sample points of the two pixels, @P_iP_j@cos(θ_i-γ)+cos(θ_
j-γ)/2sin(θ_i-θ_j) However, γ is @
The radius of curvature of the two pixels is determined by the angle between P_iP_j@ and the positive direction of the v-axis, and the product of the difference in the edge gradient direction between the two pixels and the radius of curvature is calculated @P_iP_
j@cos(θ_i-γ)+cos(θ_j-γ)/2
sin(θ_j-θ_i)(θ_j-θ_i) or @P_iP_j@cos(θi-γ)+cos(θ_j
-γ)/2 Furthermore, @P_iP_j@cos(θ_i-γ) or @P_j replaced with either θ_i or θ_j
A method for measuring edge length in a digital image, characterized in that iP_j@cos(θ_j−γ) is defined as the length of the edge by two normal lines drawn from the two pixels to the edge.