The International Arab Journal of Information Technology (IAJIT)

..............................
..............................
..............................


A Novel Fast Otsu Digital Image Segmentation

1,
#
  Digital image segmentation based on Otsu’s method i s one of the most widely used technique for threshold selection. With Otsu’s method, an optimum threshold is found by maximizing the between+class variance and the algorithm assumes that the image contains two classes of pixe ls or bi+modal histogram (e.g., foreground and back ground). It then calculates the optimal threshold value separating t hese two classes so that, their between class variance is maximal. The optimum threshold value is found by an exhaustive s earch among the full range of gray levels (e.g., 256 levels of intensity). The objective of this paper is to develop a fast algori thm for the Otsu method that reduces the number of search iterations. A new search technique is developed and compared with the original Otsu method. Experiments on several images show that the proposed Otsu+Checkpoints fast method give the same estimated threshold value with less number of iterations thus resulting in a much less computational complexity.


[1] Alsaeed D., Bouridane A., ElZaart A., and Sammouda R., Two Modified Otsu Image Segmentation Methods Based on Lognormal and Gamma Distribution Models, in Proceedings of International Conference on Information Technology and e+Services (ICITeS) , Sousse, pp. 1 5, 2012.

[2] Bazen B. and Gerez S., Segmentation of Fingerprint Images, available at: http://citeseerx.ist.psu.edu/viewdoc/download?do i=10.1.1.122.9683&rep=rep1&type=pdf, last visited 2001.

[3] Chen L., Guo L., and Du N., Multi Level Image Thresholding. Based on Histogram Voting., in Proceedings of the 2 nd International Congress on Image and Signal Processing , Tianjin, pp. 1 5, 2009.

[4] Chen Y. and Chen O., Image Segmentation Mehod Using Thresholds Automatically Determined From Picture Contents, EURASIP Journal on Image and Video Processing , vol. 2009, no. 1, pp. 1 15, 2009.

[5] Chung K. and Tsai C., Fast Incremental Algorithm For Speeding Up The Computation Of (33) 432 The International Arab Journal of Information Technology, Vol. 13, No. 4, July 2016 Binarization, Applied Mathematics and Computation , vol. 212, no. 2, pp. 396 408, 2009.

[6] Cormen T., Leiserson C., Rivest R., and Stein C., Introduction to Algorithms , MIT Press, 2009.

[7] Gonzalez R. and Woods R., Digital Image Processing , Prentice Hall, 2002.

[8] Li Z., Liu G., Cheng Y., Yang X., and Zhao C., A Novel Statistical Image Thresholding Method, AEU+International Journal of Electronics and Communications , vol. 64, no. 12, pp. 1137 1147, 2010.

[9] Mohideen F., Niraimathi M., and Seenivasagam V., Comparison Of Segmentation Algorithms By a Mathematical Model for Resolving Islands and Gulfs in Nuclei of Cervical Cell Images, The International Arab Journal of Information Technology , vol. 12, no. 5, pp. 424 430, 2015.

[10] Narayana C., Reddy E., and Prasad M., Article: Automatic Image Segmentation Using Ultra Fuzziness, International Journal of Computer Applications , vol. 49, no. 12, pp. 6 13, 2012.

[11] O Gorman L., Experimental Comparisons of Binarization and Multithresholding Methods on Document Images, in Proceedings of the 12 th IAPR International Conference on Pattern Recognition, Conference B : Computer Vision and Image Processing , Jerusalem, pp. 395 398, 1994.

[12] Otsu N., A Threshold Selection Method from Gray level Histograms, IEEE Transactions on Systems, Man and Cybernetics , vol. 9, no. 1, pp. 62 66, 1979.

[13] Pham D., Xu C., and Prince J., A Survey of Current Methods in Medical Image Segmentation, in Proceedings of Annual Review of Biomedical Engineering , pp. 318 338, 2000.

[14] Raut S., Raghuvanshi M., Dharaskar R., and Raut A., Image Segmentation A State Of Art Survey for Prediction, in Proceedings of International Conference on Advanced Computer Control , Singapore, pp. 420 424, 2009.

[15] Sezgin M. and Sankur B., Survey Over Image Thresholding Techniques and Quantitative Performance Evaluation, Journal of Electronic Imaging , vol. 13, no. 1, pp. 146 168, 2004.

[16] Wan Y., Wang J., Sun X., and Hao M., A Modified Otsu Image Segment Method Based On the Rayleigh Distribution, in Proceedings of the 3 rd IEEE International Conference on Computer Science and Information Technology , Chengdu, pp. 281 285, 2010.

[17] Xu L., Jackowski M., Goshtasby A., Roseman D., Bines S., Yu C., Dhawan A., and Huntley A., Segmentation of Skin Cancer Images, Image and Vision Computing , vol. 17, no. 1, pp. 65 74, 1999.

[18] Zhang J. and Hu J., Image Segmentation Based On 2d Otsu Method with Histogram Analysis, in Proceedings of International Conference on Computer Science and Software Engineering , pp. 105 108, 2008. Duaa Alsaeed received a BCS degree in computer science in 1992 and an M.Phil. degree in computer science (image processing) in 2005; both degrees from the College of Computer and Informatio n Sciences (CCIS), King Saud University, Saudi Arabia . She is now studying for a PhD in computer science (image processing) in the Department of Computer Science and Digital Technologies at Northumbria University, UK. From 1993 to 2005, she worked as a teacher of computer courses for high school student s with hearing disabilities in the Ministry of Educat ion, Saudi Arabia. From 2005 2008 she worked as a general educational supervisor for special educatio n in the Ministry of Education, Saudi Arabia. In 2008, s he worked as a general technical and educational supervisor in the Technical and Vocational Training Corporation; in 2009, she joined King Saud Universi ty as a lecturer in the College of Computer and Information Sciences (CCIS), and her research interests are in image processing and imagesegmentation. Ahmed Bouridane received an Ingenieurd Etat degree in electronics from Ecole Nationale Polytechnique of Algiers (ENPA), Algeria, in 1982, an M.Phil. degree in electrical engineering (VLSI design for signal processing) from the University of Newcastle Upon Tyne, U.K., in 1988, and an Ph.D. degree in electrical engineering (computer vision) from the University of Nottingham , U.K., in 1992. From 1992 to 1994, he worked as a Research Developer in telesurveillance and access control applications. In 1994, he joined Queen s University Belfast, Belfast, U.K., initially as Lec turer in computer architecture and image processing and later on he was promoted to Reader in Computer Science. He is now a full Professor in Image Engineering and Security and leads the Computer and Electronic Security Systems Group at Northumbria University at Newcastle (UK), and his research interests are in imaging for forensics and security , biometrics, homeland security, image/video watermarking, cryptography and mobile and visual computing. He has authored and co authored more than 250 publications and one research book. he is a Senior Member of IEEE. A Novel Fast Otsu Digital Image Segmentation Method 433 Ali El-Zaart was a senior software developer at Department of Research and Development, Semiconductor Insight, Ottawa, Canada during 2000 2001. From 2001 to 2004, he was an assistant professor at the Department of Biomedical Technology, College of Applied Medical Sciences. From 2004 to April 2010, he was an assistant professor at the Department of Computer Science, College of computer and information Sciences. Since April 2010, he is an associate professor at the same department. Present ly he is an associate professor at the Beirut Arab University. He has published numerous articles and proceedings in the areas of image processing, remot e sensing, and computer vision. He received a BSc in computer science from the University of Lebanon; Beirut, Lebanon in 1990, M.Sc. degree in computer science from the University of Sherbrooke, Sherbrooke, Canada in 1996, and Ph.D. degree in computer science from the University of Sherbrooke, Sherbrooke, Canada in 2001. His research interests include image processing, pattern recognition, remo te sensing, and computer vision. 344 The International Arab Journal of Information Technology, Vol. 13, No. 4, July 2016 Appendix 1 Table 2. Estimated thresholds and evaluation for me thods: Otsu, proposed otsu checkpoints (part 1). Image Threshold Global Mean Checkpoints Selected Cp No. of Itrs % Itrred % Cmplxred Otsu Proposed Cp1 Cp2 Cp3 Chickenfilet with Bones 79 79 94 80 85 90 1 15 94.14 99.66 Einstein 90 90 109 87 89 91 3 15 94.14 99.66 MRI of Knee Univ Mich 121 121 142 121 122 123 2 25 90.23 99.05 MRI Spine1 Vandy 108 108 68 108 109 110 2 25 90.23 99.05 Skin Cancer 19 98 98 117 99 101 103 1 15 94.14 99.66 Skin Cancer 4 112 112 124 113 114 115 1 20 92.19 99.39 Skin Cancer 5 91 91 99 88 90 92 3 15 94.14 99.66 Skin Cancer 7 74 74 94 75 76 77 1 20 92.19 99.39 Skin Cancer 8 91 91 95 91 92 93 2 20 92.19 99.39 Skin Cancer 9 74 74 78 74 75 76 2 20 92.19 99.39 Washingtondc Band4 133 133 147 134 135 136 1 38 85.16 97.80 Bacteria 98 98 96 97 99 101 2 15 94.14 99.66 Blob Original 108 108 121 109 110 111 1 28 89.06 98.80 Blobs 170 170 119 170 171 172 2 25 90.23 99.05 Blobs In Circular Arrangement 142 142 156 143 145 147 1 20 92.19 99.39 Boats 105 105 141 104 105 106 3 20 92.19 99.39 Brain 46 46 49 43 45 47 3 15 94.14 99.66 Brain Tomur (1) 77 77 50 78 84 90 1 15 94.14 99.66 Brain Tomur (2) 69 69 50 70 72 74 1 20 92.19 99.39 Brain Tomur (3) 59 59 31 60 61 62 1 20 92.19 99.39 Brain Tomur (4) 81 81 30 74 78 82 3 15 94.14 99.66 Bubbles 174 174 140 175 181 187 1 15 94.14 99.66 Building Original 146 146 134 147 148 149 1 38 85.16 97.80 Cameraman 88 88 120 89 91 93 1 20 92.19 99.39 Chest Xray Vandy 103 103 143 100 102 104 3 20 92.19 99.39 Columbia 100 100 82 99 100 101 3 20 92.19 99.39 Crabpulsar Optical 131 131 104 132 133 134 1 33 87.11 98.34 Ctskull 256 117 117 130 118 119 120 1 28 89.06 98.80 Cygnusloop Xray Original 75 75 68 75 76 77 2 25 90.23 99.05 Dark Blobs on Light Background 142 142 155 142 143 144 2 25 90.23 99.05 Defective Weld 167 167 174 168 169 170 1 38 85.16 97.80 Dental Xray 146 146 168 146 147 148 2 20 92.19 99.39 Face 80 80 94 81 82 83 1 20 92.19 99.39 Fb1 132 132 137 133 134 135 1 33 87.11 98.34 Fb10 176 176 209 177 182 187 1 15 94.14 99.66 Fb11 181 181 216 180 181 182 3 20 92.19 99.39 Fb12 130 130 132 131 132 133 1 33 87.11 98.34 Fb13 148 148 175 149 150 151 1 38 85.16 97.80 Fb14 152 152 171 152 153 154 2 20 92.19 99.39 Fb15 150 150 183 149 151 153 2 20 92.19 99.39 Fb16 112 112 113 113 114 115 1 33 87.11 98.34 Fb17 110 110 99 111 113 115 1 20 92.19 99.39 Fb18 159 159 175 160 161 162 1 20 92.19 99.39 Fb19 125 125 141 125 126 127 2 25 90.23 99.05 Fb2 181 181 211 182 183 184 1 33 87.11 98.34 Fb20 153 153 144 153 154 155 2 20 92.19 99.39 Fb3 160 160 181 161 162 163 1 33 87.11 98.34 Fb4 149 149 165 150 151 152 1 38 85.16 97.80 Fb5 105 105 74 105 106 107 2 25 90.23 99.05 Fb6 147 147 166 146 147 148 3 20 92.19 99.39 Fb7 128 128 134 128 129 130 2 25 90.23 99.05 Fb8 142 142 160 143 144 145 1 33 87.11 98.34 Fb9 174 174 203 174 175 176 2 20 92.19 99.39 Headct Vandy 90 90 81 91 92 93 1 33 87.11 98.34 House 117 117 109 117 118 119 2 20 92.19 99.39 Contd. In Tabel 3 Table 3. Estimated thresholds and evaluation for me thods: Otsu, proposed otsu checkpoints (part 2). Image Threshold Global Mean Checkpoints Selected Cp No. of Itrs % ItrRed % Cmplxred Otsu Proposed Cp1 Cp2 Cp3 Kidney 127 127 116 128 129 130 1 33 87.11 98.34 Large Septagon 118 118 111 115 119 123 2 15 94.14 99.66 Left Hand Xray 79 79 52 79 80 81 2 20 92.19 99.39 Lena 101 101 107 101 102 103 2 20 92.19 99.39 Lung 85 85 81 86 88 90 1 20 92.19 99.39 Noisy Region 181 181 147 182 183 184 1 20 92.19 99.39 Ordered Matches 143 143 114 139 144 149 2 15 94.14 99.66 Orig Chest Xray 78 78 61 79 80 81 1 33 87.11 98.34 Polymersomes 181 181 171 181 182 183 2 25 90.23 99.05 Radar1 42 42 28 43 44 45 1 33 87.11 98.34 Radar2 65 65 47 56 66 76 2 10 96.09 99.85 Radar3 52 52 57 43 48 53 3 10 96.09 99.85 Random Matches 143 143 111 143 144 145 2 25 90.23 99.05 Rice Image with Intensity Gradient 134 134 117 134 135 136 2 20 92.19 99.39 Scalp 52 52 52 52 53 54 2 20 92.19 99.39 Skull 96 96 36 96 97 98 2 25 90.23 99.05 Small Blobs Original 120 120 131 121 122 123 1 33 87.11 98.34 Third from Top 111 111 114 112 113 114 1 28 89.06 98.80 Tooth 109 109 147 109 110 111 2 25 90.23 99.05 Tungsten Filament Shaded 75 75 94 68 72 76 3 15 94.14 99.66 Tungsten Original 99 99 129 88 94 100 3 15 94.14 99.66 Turbine Blade Black Dot 132 132 135 133 134 135 1 28 89.06 98.80 Weld Original 167 167 174 168 169 170 1 38 85.16 97.80 Wood Dowels 121 121 88 122 123 124 1 33 87.11 98.34 Yeast USC 42 42 34 42 43 44 2 20 92.19 99.39 Evaluation of Performance Among all Experiments (Ta bles 1, 2) For Proposed Method (Otsu-Checkpoints) Accuracy = 100% Percentage of Reduction in: 1. No. Of Checked Gray Values = 90.83% 2. Computational Complexity = 99.10%