In: Paparoditis N., Pierrot-Deseilligny M., Mallet C., Tournaire O. (Eds), IAPRS, Vol. XXXVIII, Part 3A – Saint-Mandé, France, September 1-3, 2010

EFFECT OF SAMPLING IN CREATING A DIGITAL IMAGE
ON MEASUREMENT ACCURACY OF CENTER LOCATION OF A CIRCLE
R. Matsuoka a, b, *, M. Sone a, N. Sudo a, H. Yokotsuka a, N. Shirai baTokai University Research & Information Center, 2-28-4 Tomigaya, Shibuya-ku, Tokyo 151-0063, JAPAN(ryuji, sone3)@yoyogi.ycc.u-tokai.ac.jp, (sdo, yoko)@keyaki.cc.u-tokai.ac.jpb
Kokusai Kogyo Co., Ltd., 2-24-1 Harumi-cho, Fuchu, Tokyo 183-0057, JAPAN(ryuji_matsuoka, naoki_shirai) @kkc.co.jp
Commission III, WG III/1

KEY WORDS: Analysis, Sampling, Measurement, Accuracy, Digital
ABSTRACT:
Our previous paper reported an experiment conducted in order to evaluate measurement methods of the center location of a circle byusing simulated images of various sizes of circles. The variances of the measurement errors of the centroid methods in theexperiment appeared to oscillate on a one-pixel cycle in diameter. This paper reports an analysis of the dependence of themeasurement accuracy of the center location of a circle by the centroid methods on its diameter. Two centroid methods: intensityweighted centroid method (WCM) and unweighted centroid method using a binary image created by thresholding (BCM) areinvestigated. Since general expressions representing the measurement accuracy by both WCM and BCM are unable to be obtained
analytically, the variances of the measurement errors by both methods are obtained by numerical integration. From the results by
the numerical integration, we conclude that sampling in digitization would cause the measurement accuracy of the center location ofa circle by both WCM and BCM to oscillate on a one-pixel cycle in diameter. The results show that the variance of measurement
errors by WCM can be expressed by the combination of the inverse proportion to the cube of the diameter and the oscillation on a
one-pixel cycle in diameter. On the other hand, the variance of the measurement errors by BCM should approximate to the
combination of the inverse proportion to the diameter and the oscillation on a one-pixel cycle in diameter.
methods might be caused by sampling in creating a digital
image.

1. INTRODUCTION
Circular targets are often utilized in photogrammetry,particularly in close range photogrammetry. Since a circle isradially symmetrical, circular targets are well suited forphotogrammetric use such as camera calibration and 3D
measurement. It is said that determination of the center of acircular target by digital image processing techniques isrotation-invariant and scale-invariant over a wide range ofimage resolutions. The center of a circular target can be
estimated by centroid methods, by matching with a reference
pattern, or by analytical determination of the circle center(Luhmann et al., 2006).

Bose and Amir (1990) reported the investigation of the effect of
the shape and size of a square, a diamond, and a circle on themeasurement accuracy of its center location by the unweighted
centroid method using a binarized image. They conducted theanalysis of the measurement accuracy of the center location of asquare and showed the standard deviations of the measurement
errors of the center location of a square derived from thevariances of the measurement errors of the center location of aline segment. However, we confirmed that their study would beincomplete and the measurement accuracy of the center locationof a square from 2 to 22 pixels in side shown in their paper isthat when the side of a square is infinite. Moreover, they
executed the simulation on the measurement accuracy of thecenter location of a circle. In their simulation, 400 binarized
circles were placed at 0.05 pixel intervals covering a range of
one pixel in x and y direction, and the radius of a circle was
examined at merely 0.25 pixel intervals. Consequently, there
was no mention finding cyclic measurement errors of the center
location of a circle in their paper.

Our previous paper (Matsuoka et al., 2009) reported anexperiment conducted in order to evaluate measurement
methods of the center location of a circle by using simulated
images of various sizes of circles. We investigated two centroid
methods: intensity-weighted centroid method and unweighted
centroid method using a binary image created by thresholding,and least squares matching in the experiment. We made theexperiment by the Monte Carlo simulation using 1024
simulated images of which the centers were randomly
distributed in one pixel for each circle. The radius of a circle
was examined at 0.1 pixel intervals from 2 to 40 pixels. The
variances of measurement errors by both centroid methods inthe experiment appeared to oscillate on a 0.5 pixel cycle inradius, even though the formula to estimate the center of acircle by each centroid method does not seem to produce such
cyclic measurement errors.
We wondered whether theoscillation of the measurement accuracy by the centroid

This paper reports an analysis of the dependence of themeasurement accuracy of the center location of a circle bycentroid methods on its diameter. Two centroid methods:
intensity-weighted centroid method and unweighted centroid
method using a binary image created by thresholding were
investigated.

31

In: Paparoditis N., Pierrot-Deseilligny M., Mallet C., Tournaire O. (Eds), IAPRS, Vol. XXXVIII, Part 3A – Saint-Mandé, France, September 1-3, 2010

The difference between WCM and BCM is the difference of wij.
While wij = gij in WCM, wij = 1 if gij  gT and wij = 0 if gij < gT
in BCM using the threshold gT. We set gT at the most ordinary
value 1/2 in the analysis.

2. OUTLINE OF ANALYSIS
2.1 Process of Analysis
Since general expressions representing the measurement
accuracy of the center location of a circle by the investigatedcentroid methods are unable to be obtained analytically, thevariances of the measurement errors were obtained bynumerical integration. We guessed that it was difficult tounderstand the characteristics of the measurement accuracy ofthe center location of a circle only by the results obtained by thenumerical integration. Accordingly, we conducted the analysesof the measurement accuracy of the center location of a line
segment and a square as well. We show the results of theseanalyses in advance.

2.4 Numerical Integration
The variances of the measurement errors of the center locationof a circle by both WCM and BCM and a square by BCM,
which are unable to be obtained analytically, were obtained bynumerical integration. Since the measurement errors of thecenter location of a circle by WCM are continuous versus thelocation of a figure, the variances of the measurement errors by
WCM were obtained by the Simpson’s rule. On the contrary,since measurement errors by BCM are not continuous versus
the location of a figure, we obtained those variances by the
midpoint rule. The size of a figure (the side of a square, thediameter of a circle) was examined at 1/128 pixel intervals from
2 to 20 pixels in the numerical integration.

2.2 Assumed Digital Image
In order to investigate the effects of sampling on themeasurement accuracy of the center location of a figure, we
assumed that images were sampled but not quantized indigitization. The gray value gij of the pixel (i, j) of an assumed
digital image was the area of part of a figure inside the region{(x, y) | i  x  (i + 1), j  y  (j + 1)}. Therefore, 0  gij  1.
The image was assumed free of noise.

2.5 Evaluation of Measurement Accuracy
All the averages of errors (x, y) in estimation of the center
location of a line segment, a square, and a circle by WCM and
BCM, which were obtained analytically or numerically, proved
to be zero. The fact demonstrated that both WCM and BCM
can estimate the center location of the figure without bias.

2.3 Measurement Methods
Centroid methods are relatively simple and theoreticallyindependent of the image resolution. Furthermore, centroid
methods do not require a template dependent on the image
resolution. Accordingly, centroid methods are often utilized inmeasurement of the target location in photogrammetry.

The measurement accuracy of the center location of a figure
was measured by the variances (Vx, Vy) and V (= Vx + Vy) of (x,y). Vx = Vy, V = 2Vx, because both a square and a circle arepoint symmetry. We show a root mean squares of errors(RMSE) Vx of the center location of a line segment and V

We investigated two popular centroid methods. One was theintensity-weighted centroid method and is called WCM forshort from now on. The other was the unweighted centroid
method using a binary image created by thresholding and iscalled BCM for short from now on. While Hattori et al. (1999)
adopted WCM in camera calibration, Chikatsu and Anai (2001)
adopted BCM in camera calibration.

of the center location of a square and a circle in the figures as
well.
3. RESULTS AND DISCUSSION
3.1 Line Segment
It was assumed that a line segment with the length d was placedon the x-axis with its center on (s + d/2, 0) (0  s < 1).

Although the standard deviation of the measurement errors by
WCM would be theoretically proportional to the magnitude ofimage noises (Maas et al., 1993), WCM would be expected toachieve the more accurate measurement for ordinary images.
On the contrary, although BCM is robust against image noises,
BCM would be unable to produce more accurate measurement
results for ordinary images.

The gray value gi of the line segment is shown in Table 1. Hereint(x) and fra(x) are the functions to return the integer andfractional parts of the value x respectively.
i
0
1  i  int(s + d)  1
int(s + d)

Both WCM and BCM estimate the center (xC, yC) of a figure byusing the following equation (1):wij  i

1

i
j

 xC 
2
w

ij

i
j

 wij  j 1
 yC  i j


2
wij


i
j

gi
(1  s)1fra(s + d)

Table 1. Grey value gi of line segment(1)

3.1.1 WCM: Equation (2) expresses the measurement error
x of the center location of the line segment by WCM derived
from gi shown in Table 1.

x 

where, wij is the weight of the pixel (i, j).

2  s  d   int  s  d   1 int  s  d   1d s  
2


32

2d

2

(2)

In: Paparoditis N., Pierrot-Deseilligny M., Mallet C., Tournaire O. (Eds), IAPRS, Vol. XXXVIII, Part 3A – Saint-Mandé, France, September 1-3, 2010

The variance Vx of x can be obtained analytically and be
expressed by Equation (3).
1  1   
d2
12
2

Vx 

2

(3)

where  is the fractional part of d, that is to say,  = fra(d).
Equation (3) indicates that Vx oscillates on a one-pixel cycle inlength and the local maxima of Vx in the one-pixel cycle areinversely proportional to the square of d. Moreover it showsthat Vx has the local minima 0 in the one-pixel cycle when  = 0.
Figure 1 shows the RMSE Vx from d = 2 to d = 20.

Figure 2. RMSE Vx of line segment by BCM
The result of the analysis demonstrates that sampling indigitization causes the measurement accuracy by BCM to
oscillate on a one-pixel cycle in length as well as by WCM.
3.2 Square

It was assumed that a square with the side d was placed as eachside was parallel to the x-axis or y-axis with its center on (s +d/2, t + d/2) (0  s < 1, 0  t < 1).
The gray value gij of the square is shown in Table 3. Hereint(x) and fra(x) are the functions to return the integer andfractional parts of the value x respectively.

Figure 1. RMSE Vx of line segment by WCM

i=0
i=S
gij
1  i  (S  1)
j=0
(1  s) (1  t)
(1  t)s′ (1  t)1s′
1  j  (T  1)
(1  s)
j=T
t′
s′ t′
(1  s) t′
S = int(s + d), T = int(t + d), s′ = fra(s + d), t′ = fra(t + d)

The result of the analysis demonstrates that sampling indigitization causes the measurement accuracy by WCM to
oscillate on a one-pixel cycle in length.
3.1.2 BCM: Table 2 shows the measurement error x of thecenter location of the line segment by BCM using the thresholdgT = 1/2 derived from gi shown in Table 1. Here  is thefractional part of d.

x

0 

1
2

1
  12

1
0  s    
2


1
1

    s 
2
2

1
3

 s    
2
2


3

    s 1
2


 
 s  2
1  s  2 
2

1  s  
2 
2




1  s  2Table 3. Grey value gij of square
3.2.1 WCM: Equation (5) expresses the measurement error(x, y) of the center location of the square by WCM derived
from gij shown in Table 3.
2  s  d   int  s  d   1 int  s  d   1
 x 
2d
2


d

  s  
2




2
t
  d   int  t  d   1 int  t  d   1
 y 
2d2 t  d 



 2

 
1  s  2
3  s  2 2
 = fra(d)The variances (Vx, Vy) and V of (x, y) can be obtained
analytically and be expressed by Equation (6).

Table 2. Measurement error x of line segment by WCM
The variance Vx of x can be obtained analytically and be
expressed by Equation (4).
Vx 

2
1 
1
1  1  3  1         
4 
2  12 
12

(5)

2
2

1  1   Vx  Vy 
2

12
d

2
2
1  1   

2
V
V
V
V




x
y
x

6
d2

(4)

where  is the fractional part of d.

Equation (4) indicates that Vx oscillates on a one-pixel cycle inlength and is independent of the integer part of d. Figure 2
shows the RMSE Vx from d = 2 to d = 5.

33

(6)

In: Paparoditis N., Pierrot-Deseilligny M., Mallet C., Tournaire O. (Eds), IAPRS, Vol. XXXVIII, Part 3A – Saint-Mandé, France, September 1-3, 2010

If  = 0, that is to say, d is an integer, V can be obtained
analytically and be expressed by Equation (7) The red broken
line in Figure 4 shows V calculated by using Equation (7).

Equation (6) indicates that V oscillates on a one-pixel cycle inside similarly to Vx of the line segment with the length d and the
local maxima of V in the one-pixel cycle are inversely
proportional to the square of d. Moreover, it shows that V has
the local minima 0 when  = 0 in the one-pixel cycle in thesame way as Vx of the line segment. Figure 3 shows the RMSE
V from d = 2 to d = 20.

 1
 1
V     log e 2 2 2  d  1

(7)

1
5
 1
   4 log e 2 

2
1
d

 6



When d  1, V becomes nearly independent of the integer partof d similarly to Vx of the line segment with the length d andcould be approximated to Equation (8).
V  Vx  Vy  2 Vx 1  3  1   
6(8)

The results by the numerical integration show that sampling indigitization would cause the measurement accuracy by BCM to
oscillate on a one-pixel cycle in side as well as by WCM.

Figure 3. RMSE V of square by WCM
The result of the analysis demonstrates that sampling indigitization causes the measurement accuracy by WCM to
oscillate on a one-pixel cycle in side.

3.3 Circle

It was assumed that a circle with the diameter d was placed as
its center was located on (s + d/2, t + d/2) (0  s < 1, 0  t < 1).

3.2.2 BCM: The region division of (s, t) according to thethresholding result of the pixel containing each vertex of thesquare is much complicated and it takes a large space to show
the formulae of the measurement error (x, y) of the center
location of the square by BCM using the threshold gT = 1/2.
Furthermore, the variances (Vx, Vy) and V of (x, y) are unable
to be obtained analytically. Therefore, we decided to omit
showing the formulae of (x, y) in this paper.

Table 4 shows the gray value gij of the circle when d = 2 and t =0. The general expression of gij is complicated with sine andinverse sine functions in the same way as Table 4 shows.
Consequently, the measurement error (x, y) by either WCM or
BCM is expressed by the combination of sine and inverse sinefunctions, and the variances (Vx, Vy) and V of (x, y) are unable
to be obtained analytically.

V were obtained by numerical integration and Figure 3 shows
the RMSE V from d = 2 to d = 20.

i
0
1
2

gij (j = 0, 1)
 1  1  1   sin 21
4 2  4
11
1   2    sin 21  sin 2 2 24
 1  1   2   sin 2 2
4 2  4
1 = sin1(s), 2 = sin1(1  s)

Table 4. Grey value gij of circle when d = 2 and t = 0
3.3.1 WCM:
The variances (Vx, Vy) and V of themeasurement errors (x, y) of the center location of the circle
by WCM were obtained by numerical integration. Figure 5
shows the RMSE V from d = 2 to d = 20.

Figure 4. RMSE V of square by BCM
The results by the numerical integration show that V oscillates
on a one-pixel cycle in side similarly to Vx of the line segment.
However, those show that the local maxima and local minima
of V in the one-pixel cycle increase as d increases in contrast to
the fact that Vx of the line segment is independent of the integer
part of the length d. The increases of the local maxima andlocal minima of V with an increase in d could be explained interms that the thresholding result of the pixel containing eachvertex of the square would make the measurement accuracy
higher and the influence of these four vertex pixels would
decrease as d increases.

Figure 5. RMSE V of circle by WCM

34

In: Paparoditis N., Pierrot-Deseilligny M., Mallet C., Tournaire O. (Eds), IAPRS, Vol. XXXVIII, Part 3A – Saint-Mandé, France, September 1-3, 2010

The results by the numerical integration show that V would
oscillate on a one-pixel cycle in diameter similarly to V of thesquare with the side d. Those also show that V has the local
maxima and local minima at   3/4 and 1/4 in the one-pixel
cycle respectively. Furthermore, those demonstrate that boththe local maxima and local minima of V in the one-pixel cycle
would be inversely proportional to the cube of d in contrast to
the fact that the local maxima of V of the square with the side d
are inversely proportional to the square of d. On the other hand,those indicate that V has the nonzero local minima in the onepixel cycle contrary to V of the square with the side d.

Figure 6. RMSE V of circle by BCM

Here x when d = 2 and t = 0 can be obtained analytically andbe expressed by Equation (9).

x 

The results by the numerical integration show that V would
oscillate on a one-pixel cycle in diameter similarly to V of thesquare with the side d. Those also show that V has the local
maxima and local minima at   1/4 and 3/4 in the one-pixel
cycle respectively. Additionally those demonstrate that boththe local maxima and local minima of V in the one-pixel cycle
might be inversely proportional to d differently from V of thesquare with the side d.

1 
 1

  sin 21  sin 2 2    s (9)     1 2 2  2
where 1 = sin1(s) and 2 = sin1(1  s). The fact that x  0when s  0 and s  1/2 in Equation (9) suggests that V has thenonzero local minima in the one-pixel cycle.

While V of the square with the side d by BCM and V of thecircle with the diameter d by WCM are smooth in the one-pixel
cycle of d, V of the circle with the diameter d by BCM has
small irregularities in the one-pixel cycle of d. As we guessedthat the irregularities would be caused by the discontinuity of(x, y), we studied distributions of (x, y) at several values of d.
Figure 7 shows the distributions of    x2   y2 at d = 3 +It is assumed that V can be expressed in the similar formula toEquations (3) and (6) with the denominator of the cube of d.
The approximation formula obtained by the least squares
method using 2305 sets of (d, V) at 1/128 pixel intervals from 2
to 20 pixels in d is as follows:
VApp. 0.008898  0.1388 124 1  1 4 
d3

2

(10)

75/128 and d = 3 + 88/128 where V has large irregularities in
the one-pixel cycle of 3  d  4. In order to compare with the
distributions of  of the circle show in Figure 7, Figure 8 shows
the distributions of  of the square with the side d at the samevalues of d as Figure 7. The larger (i, j) is, the brighter (i, j) isin Figures 7 and 8.

where 1/4 is the fractional part of ( + 1/4), that is to say, 1/4 =fra( + 1/4).
The blue, red, and green lines in Figure 5 show V by thenumerical integration, VApp. by the approximation, and theapproximation errors

V

App.

 V

 respectively. We studied

the validity of the approximation formula (10) at 1/128 pixel
intervals from 2 to 100 pixels in d. The maximum absolute
approximation error was 0.00203 pixel ( V = 0.00536,
An absolute
VApp. .= 0.00739) at d = 2 + 23/128.
approximation error by Equation (10) is less than 0.0004 pixel
when d  5. Therefore, it can be concluded that theapproximation formula (10) would be extremely effective.

(a) d = 3 + 75/128 pixels

The results by the numerical integration show that sampling indigitization would cause the measurement accuracy by WCM to
oscillate on a one-pixel cycle in diameter.

(b) d = 3 + 88/128 pixels

Figure 7. Measurement errors  of circle by BCM

3.3.2 BCM:
The variances (Vx, Vy) and V of themeasurement errors (x, y) of the center location of the circle
by BCM using the threshold gT = 1/2 were obtained bynumerical integration. Figure 6 shows the RMSE V from d =2 to d = 20.

(a) d = 3 + 75/128 pixels(b) d = 3 + 88/128 pixels

Figure 8. Measurement errors  of square by BCM

35

In: Paparoditis N., Pierrot-Deseilligny M., Mallet C., Tournaire O. (Eds), IAPRS, Vol. XXXVIII, Part 3A – Saint-Mandé, France, September 1-3, 2010

The distributions of  of the circle shown in Figure 7 are more
complicated than those of  of the square shown in Figure 8.
Furthermore, although the difference of d between two
distributions of  of the circle shown in Figure 7 (a) and (b) ismerely 13/128 pixel, two distributions would have a great
difference in contrast to two distributions of  of the square
shown in Figure 8 (a) and (b). We concluded that the wide
variation of the distribution of (x, y) according to d would
bring V having small irregularities of in the one-pixel cycle of d.

Moreover, we suggested that the variance of measurement
errors by WCM is expressed by the combination of the inverse
proportion to the cube of the diameter and the oscillation on a
one-pixel cycle in diameter. On the other hand, the variance ofmeasurement errors by BCM should approximate to the
combination of the inverse proportion to the diameter and theoscillation on a one-pixel cycle in diameter.
We are planning to investigate the effect of quantization increating a digital image on the measurement accuracy of thecenter location of a circle by both WCM and BCM.
Furthermore, the influence of image noises on the measurement
accuracy will be studied.

It is assumed that V can be expressed in the similar formula toEquation (4) with the denominator of d. The approximation
formula obtained by the least squares method using 2305 sets of(d, V) at 1/128 pixel intervals from 2 to 20 pixels in d is asfollows:
VApp. 0.15697  0.3706  3 4 1   3 4 

REFERENCES

Bose, C.B., Amir, I., 1990. Design of Fiducials for Accurate
Registration Using Machine Vision, IEEE Transactions on
Pattern Analysis and Machine Intelligence, 12(12), pp. 11961200.

(11)

d

where 3/4 is the fractional part of ( + 3/4), that is to say, 3/4 =fra( + 3/4).

Chikatsu, H., Anai, T., 2001. Development of Hybrid Video
Theodolite System and Application to Image Sensing, Journalof the Japan Society of Photogrammetry and Remote Sensing,40(1), pp. 31-42.

The blue, red, and green lines in Figure 6 show V by thenumerical integration, VApp. by the approximation, and theapproximation errors

V

App.

 V

 respectively. We studied

Hattori, S., Akimoto, K., Okamoto, A., Hasegawa, H., Imoto,H., 1999. CCD Camera Calibration without Control Points by
Multi-Photograpy of a Target Field, IEICE Transactions on
Information and Systems, J82-D-II(9), pp. 1391-1400.

the validity of the approximation formula (11) at 1/128 pixel
intervals from 2 to 100 pixels in d. The maximum absolute
approximation error was 0.03312 pixel ( V = 0.24281,
An absolute
VApp. .= 0.20969) at d = 2 + 53/128.

Luhmann, T., Robson, S., Kyle, S., Harley, I., 2006. Close
Range Photogrammetry, Whittles Publishing, Caithness, pp.
183-190.

approximation error by Equation (11) is less than 0.025 pixel
when d  5 and less than 0.018 pixel when d  10. The
accuracy of the approximation (11) of V by BCM is obviously
lower than that of the approximation (10) of V by WCM. The
low accuracy of the approximation (11) would be caused by thewide variation of the distribution of (x, y) according to d as
mentioned previously. Nevertheless, we recognized that theapproximation formula (11) is effective for ordinary use.

Maas, H.-G., Gruen, A., Papantoniou, D. A., 1993. Particle
Tracking in three dimensional flows - Part I: Photogrammetricdetermination of particle coordinates, Experiments in Fluids, 15,
pp. 133-146.
Matsuoka, R., Sone, M., Sudo, N., Yokotsuka, H., Shirai, N.,
2009. Comparison of Measuring Methods of Circular Target
Location, Journal of the Japan Society of Photogrammetry andRemote Sensing, 48(3), pp. 154-170.

The results by the numerical integration show that sampling indigitization should cause the measurement accuracy by BCM to
oscillate on a one-pixel cycle in diameter as well as by WCM.
4. CONCLUSIONS

Although general expressions representing the measurement
accuracy of the center location of a circle by the two centroid
methods WCM and BCM are unable to be obtained analytically,
we succeeded in obtaining the variances of measurement errors
by numerical integration and the effective approximation
formulae of those. Additionally we conducted the analyses on
the measurement accuracy of the center location of a line
segment and a square by WCM and BCM.
From the results of these analyses, we concluded that samplingin creating a digital image would cause the measurement
accuracy of the center location of a circle by both WCM andBCM to oscillate on a one-pixel cycle in diameter.

36