© The Institution of Engineering and Technology
Optimal reduction of the number of grey levels present in an image is a fundamental problem in segmentation, classification, lossy compression, quantisation, inspection and computer vision. We present a new algorithm based on dynamic programming and optimal partitioning of the image data space, or its histogram representation. The algorithm allows the reduction of the number of grey levels for an image in a fine to coarse fashion, starting with the original grey levels present in the image and all the way down to two grey levels that simply create a binarised version of the original image. The algorithm can also be used to find a reduced number of grey levels in a natural way without forcing a specific number ahead of time. Application of the algorithm is demonstrated in image segmentation, multi-level thresholding and binarisation, and is shown to give very good results compared to many of the existing methods.
References
-
-
1)
-
S. Reddi ,
S. Rudin ,
H. Keshavan
.
An optimal multiple threshold scheme for image segmentation.
IEEE Trans. Syst. Man Cybern.
,
661 -
665
-
2)
-
N. Papamarkos ,
A. Atsalakis
.
Gray-level reduction using local spatial features.
Comput. Vis. Image Underst.
,
336 -
350
-
3)
-
J.N. Kapur ,
P.K. Sahoo ,
A.K.C. Wong
.
A new method for gray-level picture thresholding using the entropy of the histogram.
Comput. Vis. Graph. Image Process.
,
3 ,
273 -
285
-
4)
-
J.-S. Chang
.
New automatic multi-level thresholding technique for segmentation of thermal images.
Image Vis. Comput.
,
23 -
34
-
5)
-
C.C. Chang ,
C.H. Chang ,
S.Y. Hwang
.
A connectionist approach for thresholding.
Proc. Int. Conf. Pattern Recognit.
,
522 -
525
-
6)
-
A. Brink
.
Minimum spatial entropy threshold selection.
IEE Proc., Vis. Image Signal Process.
,
3 ,
128 -
132
-
7)
-
N. Otsu
.
A thresholding selection method from gray-level histogram.
IEEE Trans. Syst. Man Cybern.
,
1 ,
62 -
66
-
8)
-
R. Vidal
.
(1993)
Optimal partition of an interval, Applied simulated annealing.
-
9)
-
L. Lam ,
S. Lee ,
C. Suen
.
Thinning methodologies—a comprehensive survey.
IEEE Trans. Pattern Anal. Mach. Intell.
,
869 -
885
-
10)
-
M. Sezgin ,
B. Sankur
.
Survey over image thresholding techniques and quantitative performance evaluation.
J. Electron. Imaging
,
1 ,
146 -
165
-
11)
-
S. Marchand-Maillet
.
(2000)
Binary digital image processing.
-
12)
-
A.S. Abutaleb
.
Automatic thresholding of gray-level pictures using two-dimensional entropy.
Comput. Vis. Graph Image Process.
,
22 -
32
-
13)
-
D.-M. Tsai
.
A fast thresholding selection procedure for multimodal and unimodal histograms.
Pattern Recognit. Lett.
,
6 ,
653 -
666
-
14)
-
J. Scargle
.
Studies in astronomical time series analysis. V. Bayesian blocks, a new method to analyze structure in photon counting data.
Astrophys. J.
,
405 -
418
-
15)
-
L. Cao ,
Z.K. Shi ,
E.K.W. Cheng
.
Fast automatic multilevel thresholding.
Electron. Lett.
,
868 -
870
-
16)
-
J. Kittler ,
J. Illingworth
.
Minimum error thresholding.
Pattern Recognit.
,
1 ,
41 -
47
-
17)
-
S.U. Lee ,
S.Y. Chung ,
R.H. Park
.
A comparative performance study of several global thresholding techniques for segmentation.
Comput. Vis. Graph. Image Process.
,
171 -
190
-
18)
-
N. Papamarkos ,
C. Strouthopoulos ,
I. Andreadis
.
Multithresholding of color and gray-level images through a neural network technique.
Image Vis. Comput.
,
213 -
222
-
19)
-
A.H. Dekker
.
Kohonen neural networks for optimal color quantisation network.
Comput. Neural Syst.
,
351 -
367
-
20)
-
R. Bellman
.
(1957)
Dynamic programming.
-
21)
-
N. Papamarkos ,
B. Gatos
.
A new approach for multithreshold selection.
Comput. Vis. Graph. Image Process. Graph. Models Image Process.
,
5 ,
357 -
370
-
22)
-
M. Sezgin ,
B. Sankur
.
Survey over image thresholding techniques and quantitative performance evaluation.
J. Electron. Imaging
,
146 -
168
-
23)
-
W.K. Leow ,
R. Li
.
Adaptive binning and dissimilarity measure for image retrieval and classification.
Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit. (CVPR)
,
234 -
239
-
24)
-
A. Brink
.
Using spatial information as an aid to maximum entropy image threshold selection.
Pattern Recognit. Lett.
,
1 ,
29 -
36
-
25)
-
Y. Chang ,
A. Fu ,
H. Yan ,
M. Zhao
.
Efficient two-level image thresholding method based on Bayesian formulation and the maximum entropy principle.
Opt. Eng.
,
10 ,
2487 -
2498
-
26)
-
B. Jackson ,
J. Scargle
.
An algorithm for optimal partitioning of data on an interval.
IEEE Signal Process. Lett.
,
105 -
108
-
27)
-
Alginahi, Y., Sid-Ahmed, M.A., Ahmadi, M.: `Local thresholding of composite documents using multi-layer preceptron neural network', Proc. 2004 IEEE Midwest Symp. on Circuits and Systems, July 2004, Hiroshima, Japan, p. 209–212.
-
28)
-
O.D. Trier ,
T. Taxt
.
Evaluation of binarization methods for document images.
IEEE Trans. Pattern Anal. Mach. Intell.
,
3 ,
312 -
315
-
29)
-
K.-L. Chung ,
W.-Y. Chen
.
Fast adaptive PNN-based thresholding algorithms.
Pattern Recognit.
,
2793 -
2804
-
30)
-
N.R. Pal ,
S.K. Pal
.
Object-background segmentation using new definitions of entropy.
IEE Proc., Comput. Digital Tech.
,
4 ,
284 -
295
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr_20050262
Related content
content/journals/10.1049/iet-ipr_20050262
pub_keyword,iet_inspecKeyword,pub_concept
6
6