第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
A Threshold selection method from grey-level histograms.pdf
62
7*
2EEE TRANSACTIONS ON SYSTREMS, MAN, AND CYBERNETICS, VOL. SMC-9, NO. 1, JANUARY 1979
ments," Proc. ofthe 3rd Sym. on Nonlinear Estimation Theory and its Applications,
San Diego, CA, Sept. 1972.
[4] P. Smith and G. Buechler, "A branching algorithm for discrimination and track-
ing multiple objects," IEEE Trans. Automat. Contr., vol. AC-20, pp. 101-104,
1975.
[5] D. L. Alspach, 'A Gaussian sum approach to the multitarget-tracking problem,"
Automatica, vol. 11, pp. 285-296,1975.
[6] C. L. Morefield, Application of 0-1 Integer Programming to a Track Assembly
Problem, TR-0075(5085-10II, Aerospace Corp. El Segundo, CA, Apr. 1975.
[7] D. B. Reid, A Multiple Hypothesis Filter for Tracking Multiple Targets in a
Cluttered Environment, LMSC-D560254, Lockheed Palo Alto Research Labora-
tories, Palo Alto, CA, Sept. 1977.
[8] P. L. Smith, "Reduction of sea surveillance data using binary matrices," IEEE
Trans. Syst., Man, Cybern., vol. SMC-6 (8), pp. 531-538, Aug. 1976.
Fig. 6.
ID plot of ship 10001 after the second round of operator-imposed assign-
ment constraints.
LONGITUDE
t
LONGITUDE
Fig. 7.
Actual ship movements.
of the two last sighted locations. The true trajectories are shown in
Fig. 7 where it can be seen that ship 10001 did, in fact, turn toward
the coast.
IV. CONCLUDING REMARKS
The procedure of ship identification from DF sightings has
been oversimplified in this discussion. Often DF sightings are not
completely identified but, instead, contain only ship class informa-
tion. The interactive technique still applies, but additional
identification and display flexibility must be provided.
Any additional information contained in the sightings can be
used to discriminate among radar and DF sightings. Factors such
as measured heading and visual ID will permit further automatic
reduction of the P and Q matrices.
It is also possible to automate some of the more routine manual
functions. However, experience has shown that better results are
obtained by having a human operator resolve ambiguous situa-
tions arising from sparse data.
REFERENCES
[I] R. W. Sittler, "An optimal data association problem in surveillance theory,"
[2] M. S. White, "Finding events in a sea of bubbles," IEEE Trans. Comput., voL
IEEE Trans. Mil. Elect., vol. MIL-8, pp. 125-139, 1964.
C-20 (9) pp. 988-1006, 1971.
[3} A. G. Jaffer and Y. Bar-Shalom. "On optimal tracking in multiple-target environ-
A Tlreshold Selection Method
from Gray-Level Histograms
NOBUYUKI OTSU
Abstract-A nonparametric and unsupervised method of automa-
tic threshold selection for picture segmentation is presented. An
optimal threshold is selected by the discriminant criterion, namely,
so as to maximize the separability of the resultant classes in gray
levels. The procedure is very simple, utilizing only the zeroth- and the
first-order cumulative moments of the gray-level histogram. It is
straightforward to extend the method to multithreshold problems.
Several experimental results are also presented to support the
validity of the method.
I. INTRODUCTION
It is important in picture processing to select an adequate thre-
shold of gray level for extracting objects from their background. A
variety of techniques have been proposed in this regard. In an
ideal case, the histogram has a deep and sharp valley between two
peaks representing objects and background, respectively, so that
the threshold can be chosen at the bottom of this valley [1].
However, for most real pictures, it is often difficult to detect the
valley bottom precisely, especially in such cases as when the valley
is flat and broad, imbued with noise, or when the two peaks are
extremely unequal in height, often producing no traceable valley.
There have been some techniques proposed in order to overcome
these difficulties. They are, for example, the valley sharpening
technique [2], which restricts the histogram to the pixels with
large absolute values of derivative (Laplacian or gradient), and
the difference histogram method [3], which selects the threshold at
the gray level with the maximal amount of difference. These utilize
information concerning neighboring pixels (or edges) in the ori-
ginal picture to modify the histogram so as to make it useful for
thresholding. Another class of methods deals directly with the
gray-level histogram by parametric techniques. For example, the
histogram is approximated in the least square sense by a sum of
Gaussian distributions, and statistical decision procedures are
applied [4]. However, such a method requires considerably ted-
ious and sometimes unstable calculations. Moreover, in many
cases, the Gaussian distributions turn out to be a meager approxi-
mation of the real modes.
In any event, no "goodness" of threshold has been evaluated in
Manuscript received October 13, 1977;revised April 17,1978 and August 31, 1978.
The author is with the Mathematical Engineering Section, Information Science
Division, Electrotechnical Laboratory, Chiyoda-ku, Tokyo 100, Japan.
0018-9472/79/0100-0062$00.75 (D 1979 IEEE
Authorized licensed use limited to: INSTITUTE OF AUTOMATION CAS. Downloaded on February 24, 2009 at 19:01 from IEEE Xplore. Restrictions apply.
CORRESPONDENCE
63
II. FORMULATION
(due to (9)) and
most of the methods so far proposed. This would imply that it
could be the right way of deriving an optimal thresholding method
to establish an appropriate criterion for evaluating the "goodness"
of threshold from a more general standpoint.
In this correspondence, our discussion will be confined to the
elementary case of threshold selection where only the gray-level
histogram suffices without other a priori knowledge. It is not only
important as a standard technique in picture processing, but also
essential for unsupervised decision problems in pattern recogni-
tion. A new method is proposed from the viewpoint of discrimin-
ant analysis; it directly approaches the feasibility of evaluating the
"goodness" of threshold and automatically selecting an optimal
threshold.
Let the pixels of a given picture be represented in L gray levels
,L]. The number of pixels at level i is denoted by ni and
[1, 2,
the total number of pixels by N = n1 + n2 +
+ nL* In order to
simplify the discussion, the gray-level histogram is normalized
and regarded as a probability distribution:
pi = nilN,
L
pi >0, Z Pi-1
(1)
Now suppose that we dichotomize the pixels into two classes
CO and C 1 (background and objects, or vice versa) by a threshold
at level k; CO denotes pixels with levels [1,
, k], and C1 denotes
, L]. Then the probabilities of class
pixels with levels [k + 1,
occurrence and the class mean levels, respectively, are given by
wo = Pr (Co)= E Pi=
(k)
w01 = Pr (Ci)= E pi = 1-@(k)
k
i=1
L
i =k+ I
and
where
and
i Pr (i Co)- E ipiIo = p(k)/w(k)
k
Po =
k
L
i=k+lk=k+I
L
ItT P(k)
co(k)
o(k)
k
=
pi
p(k)= I ipi
i=1
(2)
i-,
t9"
(4)
(5)
6
(6)
(7)
These require second-order cumulative moments (statistics).
In order to evaluate the "goodness" of the threshold (at level k),
we shall introduce the following discriminant criterion measures
(or measures of class separability) used in the discriminant
analysis [5]:
A = a22
K = (T2/a2WK
==/2/a2
where
2 2
2
UW = 6oJoU + 0J1ff1
2 = o(po
PT) + 1G(i1
PT)
= iOO(Y1 -PTo)T
JT = E (i -p2p
2
)p
L
i=1
are the within-class variance, the between-class variance, and the
total variance of levels, respectively. Then our problem is reduced
to an optimization problem to search for a threshold k that maxi-
mizes one of the object functions (the criterion measures) in (12).
This standpoint is motivated by a conjecture that well-
thresholded classes would be separated in gray levels, and con-
versely, a threshold giving the best separation of classes in gray
levels would be the best threshold.
The discriminant criteria maximizing A, K, and q, respectively,
for k are, however, equivalent to one another; e.g., K = i + 1 and
= )/(2 + 1) in terms of 2, because the following basic relation
always holds:
a2 + a2 = 52
1w + TB
(16)
It is noticed that U2 and U2 are functions of threshold level k, but
CT is independent of k. It is also noted that cr2
is based on the
second-order statistics (class variances), while (T2 is based on the
first-order statistics (class means). Therefore, q is the simplest
measure with respect to k. Thus we adopt q as the criterion meas-
ure to evaluate the "goodness" (or separability) of the threshold at
level k.
The optimal threshold k* that maximizes t, or equivalently
maximizes a2 is selected in the following sequential search by
using the simple cumulative quantities (6) and (7), or explicitly
using (2)-(5):
(12)
(13)
(14)
(15)
(17)
(18)
(19)
l(k) = us(k)l/T
a2k =[p7(k) -(k)]2
(k)[1 - w)(k)]-
cB(k =
are the zeroth- and the first-order cumulative moments of the
histogram up to the kth level, respectively, and
and the optimal threshold k* is
L
PT P- (L) = Z ipi
i =1
(8)
2(k* ) = max o2(k).
1 0,
or 0 < o(k) < 1}.
OP00 +O+IU1=P T,
The class variances are given by
k
L
2
E (i - P0)2 Pr (i C0)= Z (i - po)2pi/o
ii=
i=
(10)
k
I2 = E (i _ pl)2 Pr (i IC,) =
i=k+ I
L
i k+ I
(i - p)2p Wi,
(11)
We shall call it the effective range of the gray-level histogram.
From the definition in (14), the criterion measure i' (or q) takes a
minimum value of zero for such k as k e S - S* = {k; (o(k) = 0 or
1} (i.e., making all pixels either Cl or CO, which is, of course, not
our concern) and takes a positive and bounded value for k e S*. It
is, therefore, obvious that the maximum always exists.
Authorized licensed use limited to: INSTITUTE OF AUTOMATION CAS. Downloaded on February 24, 2009 at 19:01 from IEEE Xplore. Restrictions apply.
64
IEEE TRANSACnONS ON SYSTEMS, MAN, AND CYBERNEnCS, VOL SMC-9, NO. 1, JANUARY 1979
Ill. DISCUSSiON AND REMARKS
A. Analysis offurther important aspects
The method proposed in the foregoing affords further means to
optimal
selecting
important
aspects
other
than
analyze
thresholds.
For the selected threshold k*, the class probabilities (2) and (3),
respectively, indicate the portions of the areas occupied by the
classes in the picture so thresholded. The class means (4) and (5)
serve as estimates of the mean levels of the classes in the original
gray-level picture.
The maximum value ti(k*), denoted simply by 1*, can be used as
a measure to evaluate the separability of classes (or ease of thre-
sholding) for the original picture or the bimodality of the histo-
gram. This is a significant measure, for it is invariant under affine
transformations of the gray-level scale (i.e., for any shift and dila-
tation, g' = agj + b) It is uniquely determined within the range
0 < q < 1.
The lower bound (zero) is attainable by, and only by, pictures
having a single constant gray level, and the upper bound (unity) is
attainable by, and only by, two-valued pictures.
B. Extension to Multithresholding
The extension of the method to multihresholding problems is
straightforward by virtue of the discriminant criterion. For exam-
ple, in the case of three-thresholding, we assume two thresholds:
for separating three classes, CO for [1, * * *, kl], C,
1 < k1 < k2 <
, k2], and C2 for [k2 + 1, --, L]. The criterion
for [k1 + 1,
(also q) is then a function of two variables k, and k2,
measure or
and an optimal set of thresholds kt and kt is selected by maximiz-
ing r7:
a2(ki,, kt) =
o2(kI, k2)-
max
1!kl
CORRESPONDENCE
65
(a)
(a)
(c)
EL|
..11
II
() .
....:..
(b)
=T 34.4
l=418 033
K = 33
7 = 0.887
w,= 0.478
w, = 0.522
P&= 14.2
JJ1= 52.8
(d)
(e)
(f)
T 38.3
a2= 143982
_I......
IIIIIIIIIIIII
=
IK
32
7 = 0.767
7
wo= 0.266
wI =0. 734
0e 20.8
P,=44.6
(h)
..::
.........
..........
.................
i,t,,~~~~~~~~~~. ............
(a)
(b)
pT 7.3
2Cr2= 23.347
K;= 7
K2=15
'= 0.873
w, = 0.633
W, = 0.296
w2 = 0.071
hP= 4.3
10.5=05
z2=20.2
(d)
'' iliE,,,l , , , i~...........
I
*1'.
-. .t
(f)--
PT 80.7
K:=61
CT 3043.561
K2=136 7=0.893
w0=0.395
w, z 0.456
W2=0.1t49
PJO=.24.1
Pi= 99.2
PZ=174.0
(h)
111111111,-......
I
(c)
(e)
(g)
(g)
Fig. 2.
Application to textures.
Fig. 3.
Application to cells. Critenon measures f(kt, k2) are omitted in (c) and (g)
by reason of illustration.
Authorized licensed use limited to: INSTITUTE OF AUTOMATION CAS. Downloaded on February 24, 2009 at 19:01 from IEEE Xplore. Restrictions apply.
66
IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS, VOL. SMC-9, No. 1, JANI'ARY 1979
and another with an old one (e), respectively. In Fig. 2, the results
are shown for textures, where the histograms typically show the
difficult cases of a broad and flat valley (c) and a unimodal peak
In order to appropriately illustrate the case of three-
(g).
thresholding, the method has also been applied to cell images with
successful results, shown in Fig. 3, where CO stands for the back-
ground, C1 for the cytoplasm, and C2 for the nucleus. They are
indicated in (b) and (f) by (
), (=), and (*), respectively.
A number of experimental results so far obtained for various
examples indicate that the present method derived theoretically is
of satisfactory practical use.
D. Unimodality of the object function
The object function 52(k), or equivalently, the criterion measure
1(k), is always smooth and unimodal, as can be seen in the exper-
imental results in Figs. 1-2. It may attest to an advantage of the
suggested criterion and may also imply the stability of the
method. The rigorous proof of the unimodality has not yet been
obtained. However, it can be dispensed with from our standpoint
concerning only the maximum.
IV. CONCLUSION
A method to select a threshold automatically from a gray level
histogram has been derived from the viewpoint of discriminant
analysis. This directly deals with the problem of evaluating the
goodness of thresholds. An optimal threshold (or set of thre-
sholds) is selected by the discriminant criterion; namely, by maxi-
mizing the discriminant measure q (or the measure of separability
of the resultant classes in gray levels).
The proposed method is characterized by its nonparametric
and unsupervised nature of threshold selection and has the follow-
ing desirable advantages.
1) The procedure is very simple; only the zeroth and the first
order cumulative moments of the gray-level histogram are
utilized.
2) A straightforward extension to multithresholding problems
is feasible by virtue of the criterion on which the method is based.
3) An optimal threshold (or set of thresholds) is selected auto-
matically and stably, not based on the differentiation (i.e.. a local
property such as valley), but on the integration (i.e., a global
property) of the histogram.
4) Further important aspects can also be analyzed (e.g., estima-
tion of class mean levels, evaluation of class separability, etc.).
5) The method is quite general: it covers a wide scope of un-
supervised decision procedure.
The range of its applications is not restricted only to the thre-
sholding of the gray-level picture, such as specifically described in
the foregoing, but it may also cover other cases of unsupervised
classification in which a histogram of some characteristic (or feat-
ure) discriminative for classifying the objects is available.
Taking into account these points, the method suggested in this
correspondence may be recommended as the most simple anid
standard one for automatic threshold selection that can be
applied to various practical problenms,
AcK NOWLEDGMENT
The author wishes to thank Dr. H. Nishino, Head of the Infor-
mation Science Division, for his hospitality and encouragement.
Thanks are also due to Dr. S. Mori, Chief of the Picture Proces-
sing Section, for the data of characters and textures and valuable
discussions, and to Dr. Y. Nogucli for cell data. The author is also
very grateful to Professor S. Amari of the University of Tokyo for
his cordial and helpful suggestions for revising the presentation of
the manuscript.
REFERENCIES
[1] J. M. S. Prewitt and M. L. Mendelsolhn, "The analysis of cell images,"
[2] J. S. Weszka, R. N. Nagel, and A. Rosenfeld, "A threshold selection technique."
Acad. Sci., vol. 128, pp. 1035-1053, 1966
nn.
IEEE Trans. Comput., vol. C-23, pp. 1322 -1326, 1974
[3] S. Watanabe and CYBEST Group. "An automated apparatus for cancer
prescreening: CYBEST," Comp. Graph. Imiage Process. vol. 3. pp. 350--358, 1974.
[4] C. K. Chow and T. Kaneko, "Automatic boundary detection of the left ventricle
from cineangiograms," Comput. Biomed. Res., vol. 5, pp. 388- 410, 1972.
[5] K, Fukunage, Introduction to Statisticul Pattern Recogniition. New York:
Academic, 1972, pp. 260-267.
Book Reviews
Orthogonal Transforms for Digital Signal Processing---N. Ahmed and K.
R. Rao (New York: Springer-Verlag, 1975, 263 pp.). Reviewed by Lokenatlh
Debnath, Departments of Mathematics and Physics, East Carolina Unit er-
sity, Greenville, NC 27834.
With the advent of high-speed digital computers and the rapid advances
in digital technology, orthogonal transforms have received considerable
attention in recent years, especially in the area of digital signal processing.
This book presents the theory and applications of discrete orthogonal
transforms. With some elementary knowledge of Fourier series trans-
forms, differential equations, and matrix algebra as prerequisites, this
book is written as a graduate level text for electrical and computer engi-
neering students.
The first two chapters are essentially tutorial and cover signal represen-
tation using orthogonal functions. Fourier methods of representating sig-
nals. relation between the Fourier series and the Fourier transform, and
some aspects of cross correlation. autocorrelation. and consolution. Thlese
chapters provide a systematic transition from the Fourier represenitation
of analog signals to that of digital sigials.
The third chapter is concerned with the F'ourier representation of
discrete and digital signals througlh the discrete Fourier tranisfornm (D)[ I).
Some important properties of the DFT including thc conv olution anld
correlation theorems are discussed in some detail, The concept of ampli-
tude, power. and phase spectra is introduced. It is shown that the 1)1F
is
directly related to the Fourier transform series representation ol data sc-
quences tX(rn)). The two-dimensional DlFT anid its possible extensioni to
higher dimensions are insestigated. and the chapter closes "it}h
;omc
discussion on time-varying power andt phase spectra.
Authorized licensed use limited to: INSTITUTE OF AUTOMATION CAS. Downloaded on February 24, 2009 at 19:01 from IEEE Xplore. Restrictions apply.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
