WU Yi-quan(吳一全)，WU Jia-ming(吳加明)，ZHAN Bi-chao(占必超)

(1.School of Electronic and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，Jiangsu，China;2.Science and Technology on Electro-optic Control Laboratory，Institute of Electro-optic Equipment of AVIC，Luoyang 471009，Henan，China;3.State Key Laboratory of Novel Software Technology，Nanjing University，Nanjing 210093，Jiangsu，China)

Introduction

Threshold segmentation is an image segmentation technology which is universally used，effective in processing and simple to implement.It can select an appropriate threshold rapidly for accurate segmentation.The scholars at home and abroad have done extensive research on this issue［1－2］，and have put forward the various threshold selection methods based on maximum between-class variance(Otsu)［3］，maximum entropy［4］and Fisher criterion［5］.At first，the threshold was selected by the 1-D gray scale histogram of image.A satisfactory segmented result is difficult to obtain when the image is interfered with noise，though its processing speed is rapid.Thus the maximum entropy method，Otsu method and Fisher criterion method are extended to gray scale-average gray scale 2-D histogram by Abutaleb［6］，Brink［7］，LIU Jian-zhuang［8］，GONG Jian［9］，et al.The result is improved significantly，but at the same time the amount of computation increased exponentially.Consequently some fast algorithms of threshold selection based on 2-D histogram are proposed［10－12］，and the running speed is improved to different extent. However， the above-mentioned 2-D methods all divided the 2-D histogram into 4 rectangular areas(called as vertical segmentation).As a result，a certain approximation is introduced into the calculation，which may cause the segmented results inaccurate.Therefore，WU Yi-quan et al put forward a threshold segmentation method based on oblique segmentation of 2-D histogram［13－15］，which further reduces errors，greatly shortening the running time，and making the anti-noise performance more robust.

Image threshold segmentation is one of key steps in infrared target detection.In the imaging plane of infrared target detection，the proportion of object to background is usually very small，for example，less than 1%.Thus the threshold segmentation problem of small target image where the proportion of object to background is very small needs to be solved.The existing threshold selection methods almost fail under the circumstance and can not obtain the perfect results.When there is a larger difference between the sizes of object and background，a smaller intra-class variance or larger between-class variance is obtained if some part of background is divided into object.Therefore Otsu method and Fisher criterion method can not accurately segment the small target images，neither can maximum entropy method.

In view of the above-mentioned reasons，a kind of threshold selection method for small target image segmentation is proposed，which is based on the area difference between background and the object and intra-class variance.When the exact segmentation of image is considered，the gray inside object and background is uniform，the intra-class variance is very small，the large area difference between object and background can be used to construct the criterion function.On this basis，the threshold selection formulae based on 1-D histogram and 2-D histogram vertical segmentation are given，respectively.Then the threshold selection formulae based on 2-D histogram oblique segmentation and its fast recursive algorithm are derived.Finally，the segmented images and running time of the proposed method are given in experimental results.Otsu，maximum entropy and Fisher threshold selection methods based on 2-D histogram oblique segmentation are compared.

1 Threshold Selection Based on 1-D Histogram and 2-D Histogram Vertical Segmentation

1.1 Threshold Selection Based on 1-D Histogram

Otsu method selects the threshold according to maximum between-class variance or minimum intraclass variance，which is essentially derived based on the least square error criterion.This criterion has a latent problem of that less sum of squares of errors may be obtained if a large category is separated when the number of samples contained in different categories has larger difference.There is a larger difference between the sizes of object and background in a small target image，a smaller intra-class variance or larger betweenclass variance is obtained if part of background is divided into object.Therefore Otsu method can not accurately segment the small target images.

For the exact segmentation of image，the gray inside object and background is uniform，data points are compact and the intra-class variance is very small，and the area difference between object and background is large，criterion function of threshold selection can be constructed and the accuracy of threshold segmentation is expected to be enhanced.According to the above two characteristics，the criterion function of threshold selection is constructed based on the area difference between background and object and the intra-class variance in this paper，which can be used to segment the small target images effectively.

Assuming that the size of image isM×N，the gray scale is 0，1，…，L－1，andp(i)is the probability of the gray scalei.The thresholdtis used to divide the image into the object class and background class.Assuming that the bright(dark)pixel of image belongs to the object(background).The probabilities of the background and object areω0(t)andω1(t)，respectively.The means of gray scale areμ0(t)/ω0(t)andμ1(t)/ω1(t)，respectively.And the variances areσ20(t)andσ21(t)，respectively.Thus the criterion function based on 1-D histogram is as follows:

The optimal threshold is obtained when the criteri-on functionΦ(t)attains the maximum value.

1.2 Threshold Selection Based on 2-D Histogram Vertical Segmentation

Fig.1 2-D histogram and vertical segmentation

The optimal threshold is obtained when the criterion functionΦ(t，s)attains the maximum value，

As a result，the intra-class gray scale of segmented image is uniform，and the object and background are separated effectively.

2 Threshold Selection Formula Based on 2-D Histogram Oblique Segmentation and Its Fast Recursive Algorithm

2.1 Threshold Selection Formula Based on 2-D Histogram Oblique Segmentation

The 2-D histogram in Fig.1(b)shows that the pixel points are almost distributed near the main diagonal.In Fig.2 the histogram region is divided into an interior-point region，two border-point regions and two noise-point regions by four parallel oblique linesL1，L2，L3，L4，which are located in both sides of the main diagonal and paralleled with it.The region betweenL1 andL2 is considered as the interior-point region of object and background because the pixel gray scale is approximate to the average gray scale of neighborhood.The region betweenL1 andL3 and the region betweenL2 andL4 are regarded as the border-point regions or transitive regions between object and background because of the certain difference between the pixel gray scale and the average gray scale of neighborhood.The two regions outsideL3 andL4 are regarded as the noise-point regions because there is a large difference between the pixel gray scale and the average gray scale of neighborhood［14－15］.

Fig.2 2-D histogram oblique segmentation

In oblique segmentation，the oblique lineg= －f+2T(Tis the threshold，0≤T≤L－1)，which is vertical to the main diagonal(or at a 135°angle with gray scale axis)，is used to segment the image according to the average value of the gray scale and the average gray scale of neighborhood.The obtained binary imageb(m，n)is

Assuming that the total gray-scale means areμtiandμtj，and the total variances areand.Because the total variance equals the sum of the intraclass variance and the between-class variance for oblique segmentation，the criterion function in Eq.(5)can be rewritten as:

The optimal threshold is obtained when the criterion functionΦ(T)attains the maximum value.

2.2 Fast Recursive Algorithm

It can be seen from the above-mentioned algorithm formulae that calculation ofΦ(T)requires the calculation ofω0(T)，ω1(T)，μ0i(T)，μ0j(T)，μti，μtj，andare fixed for the specified image.For every thresholdT，if calculation ofΦ(T)requires the cumulative calculation ofω0(T)，μ0i(T)andμ0j(T)fromi=0 andj=0 again，it will be bound to cause lots of repetitive calculation and the computational complexity iso(L2).The total computational complexity comes too(L3)because the number of thresholdTisL－1.

For 0＜T≤L/2－1，the recursive formulae are derived as follows:

similarly，the recursive formulae forL/2≤T≤L－1 can be obtained.

The flowchart of the above-mentioned algorithm is shown in Fig.3.

Fig.3 Flowchart of algorithm

3 Experimental Result and Analysis

3.1 Comparison of the Methods Based on 1-D Histogram，2-D Histogram Vertical and Oblique Segmentation

A large number of experiments are made in this paper，and an example is illustrated.The threshold segmented results for the same ship image of the methods based on 1-D histogram，2-D histogram vertical and oblique segmentation are shown in Fig.4.Fig.4(a)shows the original ship image which size is 155×154.Fig.4(b)shows the segmented result based on 1-D histogram.Fig.4(c)shows the segmented result based on 2-D histogram vertical segmentation，and Fig.4(d)shows the segmented result based on 2-D histogram oblique segmentation.It can be seen from Fig.4 that the proposed method in this paper can extract the object accurately and the anti-noise performance of 2-D method is better，especially for the method based on 2-D histogram oblique segmentation.

Fig.4 Segmented results of different methods

3.2 Comparison with Other Methods

Over 200 small target images are used in the experiments.Five of those are chosen to be illustrated.All objects are aircrafts but their distances from the infrared imaging plane are different.The segmented results of the methods proposed in this paper and methods based on 2-D histogram oblique segmentation，such as Otsu method，maximum entropy method，F(xiàn)isher criterion method，are given below，respectively.As shown in Tab.1，image 1 to image 5 are given from top to bottom，and the original image，the 1-D histogram，the segmented results of Otsu method，maximum entropy method，F(xiàn)isher criterion method and the method proposed in this paper are given from left to right in each row in turn.The size of image 1 is 322×221 and the proportion of object to background is 6.8%.The anti-noise performance of the method proposed in this paper is better，though all four methods can extract the object.Image 2 and image 3 are 323×217 and 256×256 in size，respectively.the proportions of object to background are 4.2%and 3.9%，respectively.Otsu method and Fisher criterion method can not extract the object effectively.Although the maximum entropy method can extract the object，some noise still exists in the images.The size of image 4 is 104×90，and the proportion of object to background is 0.43%.Under the circumstances，Otsu method and Fisher criterion method almost fail.The segmented result of the maximum entropy method has larger noise and lower accuracy.While the method proposed in this paper not only can extract the small target accurately，but also has the minimum noise compared with other methods，which meets the requirement.The size of image 5 is 106×94，and the proportion of object to background is 0.18%.The segmented result is similar to image 4，which further proves the superiority of the method proposed in this paper in segmentation of small target images.

Tab.1 Segmented results of four methods

The above experimental conditions are Intel Pentium 4，CPU 2.80 GHz，512 MB memory，and Matlab 7.1.The segmentation threshold and running time of four methods in Tab.1 are listed in Tab.2 and the percentages in Tab.2 are the size proportions of object to background.

Tab.2 Segmentation threshold and running time of four methods

It can be seen from Tab.2 that Otsu method requires the shortest running time but has the worst segmented result for small target images.The segmented result of maximum entropy method is superior to that of Otsu method while the running time is the longest because of the logarithm operations.The segmented result of Fisher criterion method is slightly better than Otsu method but still undesirable and its running time is longer.The method proposed in this paper has the best segmented result and can segment the small target images accurately.Its running time is shorter than Fisher criterion method and maximum entropy method while slightly longer than Otsu method.

4 Conclusions

The proposed threshold selection method for image segmentation based on the area difference between background and object and the intra-class variance can effectively segment the small target image which size proportion of object to background is very small.A large number of experimental results show that the method can make the interior of object and background region in the segmented images uniform and the boundary shape accurate.The anti-noise performance of the method based on 2-D histogram oblique segmentation is better than that of the method based on 1-D histogram and 2-D histogram vertical segmentation.The fast recursive algorithm based on 2-D histogram oblique segmentation reduces the search cost in 2-D space and improves the running speed greatly.Compared to the current fast algorithms of threshold selection for image seg-mentation，such as Otsu method，maximum entropy method and Fisher criterion method，based on 2-D histogram oblique segmentation，the method proposed in this paper has significant superiority in segmentation of small target images.

［1］WU Yi-quan，ZHU Zhao-da.30 years(1962—1992)of the developments in the threshold selection methods in image processing(I)［J］.Journal of Data Acquisition ＆Processing，1993，8(3):193－201.(in Chinese)

［2］WU Yi-Quan，ZHU Zhao-da.30 years(1962—1992)of the developments in the threshold selection methods in image processing(II)［J］.Journal of Data Acquisition ＆Processing，1993，8(4):268－282.(in Chinese)

［3］Otsu N.A threshold selection method from gray-level histogram［J］.IEEE Transactions System Man and Cybernetics，1979，9(1):62 －66.

［4］Kapur J N，Sahoo P K，Wong A K C.A new method for grey-level picture thresholding using the entropy of the histogram［J］.Computer Vision，Graphics and Image Processing，1985，29(1):273－285.

［5］CHEN Guo.The Fisher criterion function method of image thresholding［J］.Chinese Journal of Scientific Instrument，2003，24(6):564－567.(in Chinese)

［6］Abutaleb A S.Automatic thresholding of gray-level picture using two-dimensional entropies［J］.Pattern Recognition，1989，47(1):22－32.

［7］Brink A D.Thresholding of digital image using two-dimensional entropies［J］.Pattern Recognition，1992，25(8):803－808.

［8］LIU Jian-zhuang，LI Wen-qing.Automatic thresholding using the Otsu algorithm based on the two-dimensional gray image［J］.Acta Automatica Sinica，1993，19(1):101－105.(in Chinese)

［9］GONG Jian，LI Li-yuan，CHEN Wei-nan.The gray-level thresholding method based on Fisher linear discriminant of two-dimensional histogram［J］.Pattern Recognition and Artificial Intelligence，1997，10(1):1 －8.(in Chinese)

［10］Gong J，Li L Y，Chen W N.Fast recursive algorithms for two-dimensional thresholding［J］.Pattern Recognition，1998，31(3):295－300.

［11］JING Xiao-jun，CAI An-ni，SUN Jing-ao.Image segmentation based on 2D maximum between-cluster variance［J］.Journal of China Institute of Communications，2001，22(4):71－76.(in Chinese)

［12］WANG Hai-yang，PAN De-lu，XIA De-shen.A fast algorithm for two-dimensional Otsu adaptive threshold algorithm［J］.Acta Automatica Sinica，2007，33(9):968－971.(in Chinese)

［13］FAN Jiu-lun，ZHAO Feng.Two-dimensional Otsu curve thresholding segmentation method for gray-level images［J］.Acta Automatica Sinica，2007，35(4):751 －755.(in Chinese)

［14］WU Yi-quan，PAN Zhe，WU Wen-yi.Image thresholding based on two-dimensional histogram oblique segmentation and its fast recurring algorithm［J］.Journal of China Institute of Communications，2008，29(4):77－83.(in Chinese)

［15］WU Yi-quan，PAN Zhe，WU Wen-yi.Maximum entropy thresholding algorithm based on two-dimensional histogram oblique segmentation［J］.Pattern Recognition and Artificial Intelligence，2009，22(1):162 － 168.(in Chinese)