ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.379-385



ԭֵѡ㷨
ϣƽ
ժҪԭͼֵѡ÷֮һ.ܶоԭ˸о,һ㶼رԭжֵѡʱ̫.˽һICM(iterated conditional modes)㷨.ͨʵȽICM㷨H.D.Chengģ˻㷨,ʾICM㷨Ч.
ؼʡͼ,ֵ,,ģ˻,ICM㷨.
ͼšTP391
The ICM Algorithm for Multi-Level Threshold Selection by Maximum Entropy Criterion
LUO Xi-pingTIAN Jie
(Laboratory of Artificial IntelligenceInstitute of AutomationThe Chinese Academy of SciencesBeijing100080)
AbstractThe maximum entropy approach is one of the most important threshold selection methods in image processing.Many researchers avoid the problem of computationally prohibitive when the maximum entropy criterion is applied to multi-level threshold selection.This paper proposes to deal with this problem using ICM (iterated conditional modes) algorithm.Comparing the ICM algorithm with the simulated annealing algorithm proposed by H.D.Cheng et al,the experimental results show the effectiveness of ICM algorithm fully.
Key wordsImage processing,threshold,entropy,simulated annealing,ICM algorithm.
ֵѡ񷽷ͼҪҲõķ֮һ.ȥ,ΪͼҶֵԶѡ񸶳˾޴Ŭ,˺ܶ෽13.80ǰչֵѡ񷽷һϺõɲοף4.·Jui-Cheng Yen˵ԭѡֵķ5,A.Pikaz˵Ļͼȶ״̬ķ6,N.Papamarkos˵ʽϻҶֱͼ,øʽļСֵֵķ7,Liang-kai Huang˵ͨСͼĳģҶֵķ8,кܶķ911.
ԭѡֵǳõֵѡ񷽷֮һ,T.Punף12,13.ַĿڣͼĻҶֱͼֳɶ,ʹø.Ϣ۽Ƕ˵,ʹѡֵõϢ.ַĽһչɲοJ.N.KapurˡP.Sahoo˺A.D.Brink1416.Щͨһֵͼֳɱ.е߶ǵķֱƹ㵽ֵѡ,Ҳô.ֵ,һҶȼΪ256ͼ,ΪʹֵֻҪ255ֲͬѡ,Լ˵ֻǺСļ,㷨䵽ֵѡʱ,Ӷָ.,6ֵ,Ϊʹֵ,һ256ҶȼͼҪ255254253252251ֲֵͬ,Ŀǰõ΢վҲҪüСʱܵõ.Ȼǲʵõ.
Ϊ˽˸ֲͬķ,J.Gongˣ17һٵݹ㷨ټ㲻ֵͬµֵʱļ,ַûнҪǵ̫ࡢռ̫һ.H.D.Cheng˽һصģ˻㷨18,ģ˻㷨ͬмܴٶȺ,йͼеģ˻㷨ϸοף19.
ĲICM(iterated conditional modes)ᵽļ.ICMıȽ͸οJulian Besagģ20.ICMܺܿȶֵ,һ㲻ܱ֤ȫŽ,ҳʼֵICMȶҪӰ20.һʼ㷨,ͨʵǷ,ʹøóʼ㷨Ķʵ,ICM㷨ģ˻ٷһ̬(ϵͳȫŽ),ʵеһ,ICM㷨Ҳһ̬.
ĵ1ڶԭһ򵥽.2ڸICM㷨ϸ.3ڽICMĳʼ㷨.4ڸĲʵʵ,нȽICM㷨ģ˻㷨Ч.5ܽ.
1ԭ
жֲͬԭ,ǲодԵJ.N.Kapurˣ14ԭ۶ֵ.
ȿǵֵѡ,ͼһҶֳֵɱ.p0,p1,...,pnʾҶȼĸʷֲ,ֵڻҶȼs,ʷֲ,һ1sĻҶȼ,һs+1nĻҶȼ,ֲ£



ÿһֲصΪ

(1)

(2)


(3)
ֵsΪ

ֵѡԭֱƹ㵽ֵѡ,ʱ,ʽ(3)Ϊ

(4)
k,ֵ(s1,s2,...,sk)Ϊ

2ICM 㷨
ǰѾ۹,ԭжֵѡ,ʹٷʵ,ģ˻㷨ٶҲԽ.ǽһICM㷨.
minimaxiʾiĲ,iminimaxiлҶȼ,
min1=0,maxn=max-gray,κ2ni,maxi-1=mini,
n=classnumΪ,max-grayΪͼҶֵ.
㷨.
(1) ʹýڵ3ڽܵĳʼ㷨minimaxi(1in)ĳʼֵ.
(2) Դ1n-1ÿһi,ִ²
maxiֵminimaxi+1䶯,ȡmaxiֵΪ

Ц(max1,...,maxn-1)ʽ(4).
(3) ظ(2),ֱκθı.
(4) ֵΪmax1,...,maxn-1 .
Ȼ,༴ֵѡ,㷨ٷ,Ҫ.ICM㷨Ȼ,Ϊ״̬ռ޵,ÿһε,ǵ½,Ӷ޴εĵ,Ȼĳֲȶ״̬.ʵ,һ㷨35ε̬,Ҷȼ޹.,ʵĽǶȿ,ICM㷨ļ㸴ΪO(mn),m,nǻҶȼ,ɼICM㷨ֻжʽ,ٷָ.
3ʼ㷨
ʼǸʼֵ,ICM㷨һ½ֲСֵ,ϵͳĳʼ״̬״̬Ҫ,ϵͳĳʼ״̬ȫּСֵ״̬ȽϽ,ôʹICM㷨ͺܿȫּСֵ.µĳʼ㷨.
㷨.
1.ȡͼҶֱͼеоֲ;ֲСֵ,hist(i)ʾͼолҶiظ,ҶֱͼеһֲСֵĻҶȼi:
hist(i)hist(i+1)hist(i)hist(i-1).
ͬ,һֲֵĻҶȼi:
hist(i)hist(i+1)hist(i)hist(i-1).
ͼĻҶֱͼһɨͿɻеľֲ;ֲСֵ.loc-maxֲֵ,loc-minֲСֵ,ֵ
κi,
loc-mini-1ݣloc-maxiݣloc-mini,
ֲСֵ֮һֲֵ.ͬ,ֲֵ֮һֲСֵ.
ڵľֲСֵ֮ĻҶֵΪһ,һ,һֳҪö,ҪĳЩϲ.ǲﵽһĿ.
2.һкϲͼ1ʾ Nor  ״,Nε
hist(loc-min(i-1)hist(loc-min(i))hist(loc-max(i)hist(loc-max(i+1)).

Fig.1Form"N" in the left an "" in the right
ͼ1Ϊ"N",ұΪ""
ε.
ѡNεϲһ
hist(loc-max(i)-hist(loc-min(i))hist(loc-max(i+1)-hist(locmax(i))

loc-max(i+1)-loc-max(i)max-inter,
max-interԤȸֵ,ǵʵȡΪmax-hist/(2*classnum).ԡƵĺϲ.Ҳ˵,ǽϲҶֱͼ಻̫ԶֺܿճһС.һ̽УֱٺϲΪֹ.
3.2ϲõԱҪĶ,͵һĵ̣Ҫ.һ.
ÿһε֮,ҳС(һĸǸлҶֵĸ֮),ȻڵиʽСǸϲ.ҳֱͼͷֻһ,ϲ.
㷨ͼֵڻҶֱͼֲСֵʹûҶֱͼдĽṹܵõ,ڴ˻ϰѻҶֱͼֳɸʾĲ.ͼ2ʾһʹֳʼ㷨.ͼ2еĻҶֱͼóʼ㷨õֵs1,s2.


Fig.2 An example of the initial algorithm
ͼ2ʹóʼ㷨һ
4ʵ 
ǵʵ,ף18ܵģԭģ˻㷨,ԱǵICM㷨Ƚ.Ըģ˻㷨
(1) 2(classnum-1)ƶ¶ٳӦ(˻)ף18ƶһξͳԦ,classnumõ.
(2) Ͽ,ģ˻㷨˻ٶӦ൱(οף19),ܱ֤ϵͳ̬,ǲף18ʼ״̬ʼ˻,Ǵóʼ㷨õĳʼ״̬ʼ˻.
(3) ʹõĳʼ¶Ϊ1,˻Ϊ0.999 9.
ʵ鶼ڴ128MBڴPII300΢ɵ,ڴ˸ʵĽ.
ͼ3ʾһͷCTƬ,CTֵΧΪ04 095,ȡҶȼΪ4 096.öֵѸͼֳɱƤ֯͹4.1ʾ˷ֱICMģ˻㷨SA(simulated annealing)õֵͼʱ.ӱ1ǿԿ,ICM㷨˲1͵õ˽175,977,1502,SA12ŵõͬĽ.ͼ4ʹICM㷨õֵͷֳ4Ľ.


Fig.3 The CT slice of the head,it's histogram and initial threshold value
ͼ3 ͷCTƬҶֱͼʼֵ
Table 1 The threshold value and computational time of Fig.3(4 096 grey level)
1ͼ3ֵʱ(4 096Ҷȼ)

ThresholdComputational time
Initial value209,989,1162
ICM175,977,15021s
SA175,977,150212s

ֵ,ڼʱ,۳ʼֵ.


ٱ,ڱƤ,֯,ܹ.
Fig.4 The threshold value got by ICM and the 4 regions by threshold
ͼ4 ICM㷨õֵ佫ͷֳɵ4
ͼ5ʾһ256ҶȼĺͼƬҶֱͼ,аʹǵĳʼ㷨õĳʼֵ.öֳֵ6.2ʾ˷ֱICMģ˻㷨SAõֵͼʱ.ӱ1ǿԿ,ICM㷨˲1Ӿ͵õ˽67,107,140,173,206,SA47ŵõͬĽ.ͼ6ʹICM㷨õֵͼĽ,ÿһصĻҶֵΪصƽҶֵ.


Fig.5 An aerial picture,it's histogram and initial threshold value
ͼ5 ͼƬ,Ҷֱͼʼֵ
Table 2 The threshold value and computational time of Fig.4(256 grey level)
2ͼ4ֵʱ(256Ҷȼ)

ThresholdComputational time
Initial value111,141,170,202,250
ICM67,107,140,173,2061s
SA67,107,140,173,20647s

ֵ,ڼʱ,۳ʼֵ.


Fig.6 The result picture with threshold values got by ICM
ͼ6 ʹICM㷨õֵӦĽͼ
5 
ĽICMԭжֵѡʱռ̫¼̫һ.ʵǿԿICMʹܸŽ,Ҳҳ.Ҫ,㷨,ʱ伫.ʵ,256ҶȼͼҳĶֵʱԶС1.Ż㷨ģ˻㷨ʱܳ,һＸʮϰ,ʵӦʱ˽.ٷʱ,ںʱ.
нܵICM㷨ڻԭжֵѡ,ܴͬĶֵѡ񷽷.J.KittlerСֵѡ񷨣1,Jui-Cheng YenĻԭֵѡ񷨣5ݵȵ.ĿǰûЩӦʵ,ţICM㷨ЩͬܵõĽؼټ.
оõȻѧ(No.69843001)͹863߿ƼĿ(No.863- 306-ZT04-06-04).ϣƽ,1974,ʿҪо Ϊͼģʽʶ.,1960,ʿоԱʿʦ,Ҫ оΪģʽʶϵͳý.
ͨѶϵ:ݣ 100080йѧԺԶо˹ʵ
ߵλϣƽ(йѧԺԶо˹ʵҡ100080)
(йѧԺԶо˹ʵҡ100080)
ο
1Kittler J,Illingworthv I.Minimum error thresholding.Pattern Recognition,1986,19(1):4147
2Cho S,Haralick R,Yi S.Improvement of Kittler and Illingworth's minimum error thresholding.Pattern Recognition,1989,22(5):609617
3Ostu N.A threshold selection method from gray-level histogram.IEEE Transactions on System Man and Cybernet,1978,8(1):6266
4Sahoo P K,Soltani S,Wang A K C et al.A survey of thresholding techniques.Computer Vision,Graphics and Image Processing,1988,41(2):233260
5Yen Jui-cheng,Chang Fu-juay,Chang Sh-yang.A new criterion for automatic multilevel thresholding.IEEE Transactions on Image Processing,1995,4(3):370377
6Pikaz A,Averbuch A.Digital image thresholding based on topological stable state.Pattern Recognition,1996,29(5):829843
7Papamarkos N,Gatos B.A new approach for multilevel threshold selection.CVGIP: Graphic Models and Image Processing,1994,56(3):357370
8Huang Liang-kai,Mao-Jiun,Wang J.Image thresholding by minimizing the measure of fuzziness.Pattern Recognition,1995,28(1):4151
9Corneloup G,Moysan J,Maynin I E.BSCAN image segmentation by thresholding using cooccurrence matrix analysis.Pattern Recognition,1996,29(2):281296
10Li L,Gong J,Chen C.Grey-level image thresholding based on Fisher linear projection of two-dimensional histogram.Pattern Recognition,1997,30(5):743750
11Ramac L C,Varshney P K.Image thresholding based on Ali-Silvey distance measures.Pattern Recognition,1997,30(7):11611174
12Pun T.A new method for gray-level picture thresholding using the entropy of the histogram.Signal Processing,1980,2(2):233237
13Pun T.Entropic thresholding: a new approach.Computer Vision,Graphics and Image Processing,1981,16(2):210239
14Kapur J N,Wong A K C.A new method for gray-level picture thresholding using the entropy of the histogram.Computer Vision,Graphics and Image Processing,1985,29(2):273285
15Sahoo P,Wilkins C,Yeager J.Threshold selection using Renyi's entropy.Pattern Recognition,1997,30(1):7184
16Brink A D.Thresholding of digital images using two-dimensional entropies.Pattern Recognition,1992,25(8):803808
17Gong J,Li L,Chen W.Fast recursive algorithms for two dimensional thresholding.Pattern Recognition,1998,31(3):295300
18Cheng H C,Chen Jim-rong,Li Ji-guang.Threshold selection based on fuzzy c-partition entropy approach.Pattern Recognition,1998,31(7):857870
19Geman S,Geman D.Stochastic relaxation.Gibbs distributions,and the bayesian restoration of images.PAMI,1984,6(6):721741
20Besag J.On the statistical analysis of dirty pictures.Journal of Royal Statistic Society (B),1996,48(3):259302
1999-01-05յԭ,1999-04-12յ޸ĸ
