رقم المقالة : 202007088196 زيارة : 10050 الصفحة: 37 - 56

نوع المخطوط: المحکّمة

بخش‌بندي تصاوير رنگي بيروني به هدف تشخيص اشياء به كمك هيستوگرام با دقت دوگانه

الموضوعات :

جواد راستي ¹ , سید امیرحسن منجمی ² , عباس وفایی ³

1 - مهندسی پزشکی
2 - اصفهان
3 - دانشگاه اصفهان

تاريخ الإرسال : 20 الثلاثاء , شعبان, 1433 تاريخ التأكيد : 20 الثلاثاء , شعبان, 1433 تاريخ الإصدار : 28 الأحد , ربيع الثاني, 1434

الکلمات المفتاحية: تصاوير بيروني, خوشه‌بندي, بخش‌بندي رنگي, دقت تصوير.,

ملخص المقالة :

يكي از مسايل مهم در پردازش خودكار تصاوير بيروني، نحوه بخش‌بندي اين تصاوير به هدف تشخيص شيء در آنها مي‌باشد. مشخصات خاص اين تصاوير از جمله تنوع رنگ، اثرات نوري متفاوت، وجود سايه‌هاي رنگي، جزييات بافتي زياد و وجود اشياء كوچك و ناهمگن باعث مي‌شود مسأله بخش‌بندي تصاوير بيروني به ويژه بخش‌بندي رنگي با چالش‌هاي جدي مواجه شود. در تحقيقات قبليبراي خوشه‌بندي رنگي تصاوير بيروني به هدف بخش‌بندي ابتدايي، روشي مبتني بر الگوريتم خوشه‌بندي k-means در بستري با دقت چندگانه پيشنهاد شده بود.اين روش با استفاده از محو عمدي جزييات بافتي تصوير و حذف كلاسهاي محرز در تصاوير محو شده و سپس اضافه كردن كلاسها در تصاوير با دقت بالاتر، كارايي مناسبي براي بخش‌بندي ابتدايي اين تصاوير در مقايسه با روش k-means عادي نشان مي‌داد.در اين مقاله، يك روش تطبيق‌پذير با تصوير با استفاده از هيستوگرام حلقوي ته‌رنگ براي تشخيص كلاس‌هاي محرز در تصاوير محوشده در بستري با دقت دوگانه پيشنهاد گرديده است.كارايي اين الگوريتم به كمك يك روش ارزيابينظارت‌شده روي دو پايگاه داده از تصاوير بيروني بررسي شده كه حدود 20% كاهش خطاي پيكسلي در بخش‌بندي و نيز دقت و حدود 30% سرعت بيشتر در همگرايي الگوريتم خوشه‌بندي، نشانگر كيفيت بالاتر روش پيشنهادي نسبت به روش عادي است.

المصادر:

[1]. W. W. Mayol, "Wearable Visual Robots," Ph.D, Computer Science, University of Oxford, 2004.
[2]. M. Everingham, B. T. Thomas, and T. Troscianko, "Wearable mobility aid for low vision using scene classification in a Markov random field model framework," International Journal of Human Computer Interaction, special issue on mediated reality, vol. 15, pp. 231-244, 2003.
[3]. R. C. González and R. E. Woods, Digital Image Processing: Pearson/Prentice Hall, 2008.
[4]. R. Manduchi, "Learning Outdoor Color Classification," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1713-1723, 2006.
[5]. J. Batlle, A. Casals, J. Freixenet, and J. Martí, "A review on strategies for recognizing natural objects in colour images of outdoor scenes," Image and Vision Computing, vol. 18(6-7), pp. 515-530, 2000.
[6]. Y.-W. Tai, J. Jia, and C.-K. Tang, "Soft Color Segmentation and Its Applications," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, pp. 1520-1537, 2007.
[7]. H. D. Cheng, X. H. Jiang, Y. Sun, and J. Wang, "Color Image Segmentation: Advances & Prospects," Pattern Recognition, vol. 34, pp. 2259–2281, 2001.
[8]. H. B. M'hadheb, A. Douik, M. M. Fendri, and M. Annabi, "Reduction of color variability in color image segmentation," in IEEE International Conference on Electronics, Circuits and Systems, 2006.
[9]. I. Ashdown, "Octree color quantization," in Radiosity: A Programmer's Perspective, ed: Wiley New York 1994.
[10] P. Heckbert, "Color image quantization for frame buffer display," SIGGRAPH Comput. Graph., vol. 16, pp. 297-307, 1982.
[11]. S. J. Wan, P. Prusinkiewicz, and S. K. M. Wong, "Variance based color image quantization for frame buffer display," Color Res. Applicat, vol. 15(1), pp. 52-58, 1990.
[12]. P. Scheunders, "A comparison of clustering algorithms applied to color image quantization," Pattern Recognition Letters, vol. 18, pp. 1379-1384, 1997.
[13]. N. Vlajic and H. C. Card, "Vector quantization of images using modified adaptive resonance algorithm for hierarchical clustering," IEEE Transactions on Neural Networks, vol. 12, pp. 1147-1162, 2001.
[14]. B. Fritzke, "A Growing Neural Gas Network Learns Topologies," Advances in Neural Information Processing Systems, 1995.
[15]. A. Baraldi and P. Blonda, "A survey of fuzzy clustering algorithms for pattern recognition. II," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 29, pp. 786-801, 1999.
[16]. G .A.Carpenter , S. Grossberg, N. Markuzon, J. H. Reynolds, and D. B. Rosen, "Fuzzy ARTMAP: A neural network architecture for incremental supervised learning of analog multidimensional maps," IEEE Transactions on Neural Networks and Learning Systems, vol. 3, pp. 698-713, 1992.

[17]. N. Papamarkos, A. E. Atsalakis, and C. P. Strouthopoulos, "Adaptive color reduction," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 32, pp. 44-56, 2002.
[18]. G. Cheng, J. Yang, K. Wang, and X. Wang, "Image Color Reduction Based on Self-Organizing Maps and Growing Self-Organizing Neural Networks," in The Sixth International Conference on Hybrid Intelligent Systems, 2006, p. 24.
[19]. K. Zagoris, N. Papamarkos, and I. Koustoudis, "Color Reduction Using the Combination of the Kohonen Self-Organized Feature Map and the Gustafson-Kessel Fuzzy Algorithm," in The 5th international conference on Machine Learning and Data Mining in Pattern Recognition, Leipzig, Germany, 2007, pp. 703-715.
[20]. A. Atsalakis, N. Papamarkos, and I. Andreadis, "On estimation of the number of image principal colors and color reduction through self-organized neural networks," International Journal of Imaging Systems and Technology, vol. 12, pp. 117-127, 2002.
[21]. J. Rasti, A. Monadjemi, and A. Vafaei, "Color reduction using a multi-stage Kohonen Self-Organizing Map with redundant features," Expert Systems with Applications, vol. 38, pp. 13188-13197, 2011.
[22]. S. Kiranyaz, S. Uhlmann, and M. Gabbouj, "Dominant Color Extraction Based on Dynamic Clustering by Multi-dimensional Particle Swarm Optimization," in The Seventh International Workshop on Content-Based Multimedia Indexing, 2009, pp. 181-188.
[23]. R. O. Duda, P. E. Hart, and D. G. Stork, Pattern classification: Wiley, 2001.
[24]. J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms: Kluwer Academic Publishers, 1981.
[25]. M. Y. Choong, W. L. Khong, W. Y. Kow, L. Angeline, and K. T. K. Teo, "Graph-Based Image Segmentation Using K-Means Clustering and Normalised Cuts," in The Fourth International Conference on Computational Intelligence, Communication Systems and Networks, 2012, pp. 307-312.
[26]. Y. C. Hu and M. G. Lee, "K-means-based color palette design scheme with the use of stable flags," Journal of Electronic Imaging, vol. 16, pp. 033003-1 to 033003-11, 2007.
[27]. S. N. Sulaiman and N. A. M. Isa, "Adaptive fuzzy-K-means clustering algorithm for image segmentation," IEEE Transactions on Consumer Electronics, vol. 56, pp. 2661-2668, 2010.
[28]. P. Ng and C.-M. Pun, "Skin Color Segmentation by Texture Feature Extraction and K-mean Clustering," in The Third International Conference on Computational Intelligence, Communication Systems and Networks, 2011, pp. 213-218.
[29]. R. Figueiredo, L. Schnitman, and F. d. Souza, "Using Neural Network and K-means Clustering for Image Segmentation in Outdoor Scenes," in The 2nd International Congress on University-Industry Cooperation, Perugia, Italy, 2007.
[30]. R. Huang, N. Sang, D. Luo, and Q. Tang, "Image Segmentation via Coherent Clustering in Lab Color Space," Pattern Recognition Letters, vol. 32, pp. 891-902, 2011.
[31]. جواد راستي، سيد اميرحسن منجمي و عباس وفايي، «كاهش رنگ تصاوير بيروني به هدف بخش‌بندي ابتدايي با استفاده از خوشه‌بندي سلسله‌مراتبي با حذف تدريجي در هرم گوسي»، ششمين کنفرانس ماشين بينايي و پردازش تصوير، دانشگاه اصفهان، آبان 1389.
[32]. A. Roy, S. K. Parui, D. Nandi, and U. Roy, "Color image segmentation using a semi-wrapped gaussian mixture model," in The 4th international conference on Pattern recognition and machine intelligence, Moscow, Russia, 2011, pp. 148-153.
[33]. M. Recky and F. Leberl, "Windows Detection Using K-means in CIE-Lab Color Space," in The 20th International Conference on Pattern Recognition, 2010, pp. 356-359.
[34]. S. Haykin, Neural Networks: A Comprehensive Foundation: Prentice Hall PTR, 1994.
[35] H. J. Aantonisse, "Image segmentation in pyramids," Computer Graphics and Image Processing vol. 19, pp. 367–383, 1982.
[36]. R. Marfil, L. Molina-Tanco, A. Bandera, J. A. Rodriguez, and F. Sandoval, "Pyramid segmentation algorithms revisited," Pattern Recognition, vol. 39, pp. 1430-1451, 2006.
[37]. G. Ramella and G. S. Baja, "Color Quantization by Multiresolution Analysis," in The 13th International Conference on Computer Analysis of Images and Patterns, Germany, 2009, pp. 525-532.
[38]. A. Atsalakis and N. Papamarkos, "Color reduction and estimation of the number of dominant colors by using a self-growing and self-organized neural gas," Engineering Applications of Artificial Intelligence, vol. 19, pp. 769-786, 2006.
[39]. S. Makrogiannis, G. Economou, and S. Fotopoulos, "A region dissimilarity relation that combines feature-space and spatial information for color image segmentation," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 35, pp. 44-53, 2005.
[40]. Y. J. Zhang, Advances in Image And Video Segmentation: IRM Press, 2006.
[41]. J. Rasti, A. Monadjemi, and A. Vafaei, "A Graph-Based Vision System for Automatic Object Detection in Outdoor Scenes," in The 22nd International DAAAM Symposium, Vienna, Austria, 2011, pp. 0167-0168.
[42]. A. Bosch, X. Munoz, and J. Freixenet, "Segmentation and description of natural outdoor scenes," Image and Vision Computing, vol. 25, pp. 727-740, 2007.
[43]. H. Zhang, J. E. Fritts, and S. A. Goldman, "A Co-Evaluation Framework for Improving Segmentation Evaluation," in SPIE Defense and Security Symposium - Signal Processing, Sensor Fusion, and Target Recognition XIV, 2005, pp. 420-430.
[44]. A. Alonso-Betanzos, B. Arcay-Varela, and A. Castro-Martínez, "Analysis and evaluation of hard and fuzzy clustering segmentation techniques in burned patient images," Image and Vision Computing, vol. 18, pp. 1045-1054, 2000.
[45]. D. Collins, W. A. Wright, and P. Greenway, "The sowerby image database," presented at the The 7th IEEE International Conference of Image Processing and Its Applications, Manchester, England, 1999.
[46]. X. He, R. S. Zemel, and M. Carreira-Perpi, "Multiscale conditional random fields for image labeling," in IEEE computer society conference on Computer vision and pattern recognition, Washington, D.C., USA, 2004, pp. 695-703.
[47]. A. Likas, M. Vlassis, and J. Verbeek, "The global k-means clustering algorithm," Pattern Recognition vol. 36, pp. 451-461, 2003.
[48]. جواد راستي، «ارائه يك روش بخش‌بندي مبتني بر الگوريتم‌هاي هوشمند به منظور تشخيص اشياء در تصاوير بيروني»، پايان‌نامه دکترا، گروه مهندسي کامپيوتر، دانشگاه اصفهان، 1391.
[49]. F. Y. Shih and S. Cheng, "Automatic seeded region growing for color image segmentation," Image and Vision Computing, vol. 23, pp. 877-886, 2005.
[50]. R. Datta, D. Joshi, J. Li, and J. Z. Wang, "Image retrieval: Ideas, influences, and trends of the new age," ACM Computing Surveys, vol. 40, pp. 1-60

نص كامل:

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال چهارم، شماره‌هاي 13 و 14، پاییز و زمستان 1391

صص: 37- 56

$E:\E Drive\logo\iicta Logo0.JPG$

بخش‌بندي تصاوير رنگي بيروني به هدف تشخيص اشياء به كمك هيستوگرام با دقت دوگانه

جواد راستي*1 سيد اميرحسن منجمي** عباس وفایی***

* استادیار، دانشکده مهندسی پزشکی، دانشگاه اصفهان، اصفهان

** دانشیار، دانشکده مهندسی کامپیوتر، دانشگاه اصفهان، اصفهان

*** استادیار، دانشکده مهندسی کامپیوتر، دانشگاه اصفهان، اصفهان

تاريخ دريافت: 20/04/1391 تاريخ پذيرش: 30/11/1391

چکيده

كليد واژگان: تصاوير بيروني، خوشه‌بندي، بخش‌بندي رنگي، دقت تصوير.

1. مقدمه

پردازش خودكار تصاوير بيروني يكي از زمينه‌هاي مهم بينايي ماشين است كه از جمله كاربردهاي آن مي‌توان به ساخت روبات‌هاي هوشمند براي ايفاي نقش در محيطهاي خارجي [1] و طراحي كامپيوترهاي پوشيدني[2]اشاره كرد. بخش‌بندي يكي از مهمترين گامهاي ابتدايي پردازش خودكار تصاوير است كه موفقيت در تحليل تصوير تا حد زيادي به آن وابسته است [3]. بخش‌بندي، تصوير را به اجزاء سازنده آن تقسيم مي‌كند تا به كمك روندهاي تشخيص شيء بتوان اين اجزاء را شناسايي نمود. اين تشخيص در زمينه‌هاي زيادي از بينايي ماشين مانند تحليل صحنه و رديابي اشياء كاربرد خواهد داشت.

مشخصات خاص تصاوير بيروني از جمله تغييرات نوري، وجود جزييات بافتي زياد و وجود اشياء كوچك و زياد و ناهمگن، باعث مي‌شود مسأله بخش‌بندي تصاوير بيروني با چالش‌هاي جدي مواجه شود[4, 5]. به همين دليل استفاده از رويه‌هاي پيش‌پردازش كه بتواند ابعاد فضاي اطلاعاتي تصوير را كاهش دهد،براي بخش‌بندي اين تصاوير معمولاً ضروري است.

رنگ يكي از مهمترين ويژگي‌هاي هر شكل است كه با تكيه بر آن مي‌توان تا حد زيادي به موفقيت بخش‌بندي اميدوار بود[6, 7]. اما تنوع رنگي تصوير كه در سيستم‌هاي ديجيتال امروزي به صورت معمول چند ميليون رنگ را دربرمي‌گيرد، مانعي جدي در اين راه به شمار مي‌رود. يكي از ابزارهاي معمول پيش‌پردازش براي عمليات بخش‌بندي استفاده از روش‌هاي كاهش و دسته‌بندي رنگهاست. روندهاي كاهش رنگ، تصوير را از يك فضاي اطلاعاتي با ابعاد چند ميليون رنگ به يك فضاي دسته‌بندي شده محدود با ابعاد چند رنگ مهم تبديل مي‌كنند. تحليل ماشيني اين فضاي محدود كاري ساده‌تر و طبعاً كاراتر است كه مي‌تواند به عنوان گامي ابتدايي در بخش‌بندي تصوير به كار رود[8].

هدف از كاهش تعداد رنگهاي يك تصوير، تركيب رنگهاي نزديك و ايجاد تصويري جديد با تعدادي محدود رنگ است كه بتواند رنگ‌هايتصوير اصلي (الگوها يا اشياء) را به نمايش درآورد. اين فرآيند مي‌تواند براي تقسيم تصوير به عناصر اصلي سازنده‌اش مفيد باشد.

دسته‌اي از روشهاي كاهش رنگ بر مبناي تقسيم متوالي مكعب سه‌بعدي RGB عمل مي‌كنندكه از جمله آنها مي‌توان به روشهاي Octree[9]، برش ميانه[10]، و الگوريتم‌هاي مبتني بر پراش [11] اشاره كرد. دسته‌ي‌ ديگر الگوريتمهاي كاهش رنگ، بر مبناي خوشه‌بنديرنگها عمل مي‌كنند[12]. اين الگوريتم‌ها براي پيدا كردن رنگ‌هاي مهم تصوير از روشهاي خوشه‌بندي مانند كوانتيزاسيون برداري [13]، GNG[14]، FOSART [15]، Fuzzy ART [16]، ACR[17] استفاده مي‌کنند. شبکه‌هاي عصبي نيز براي خوشه‌بندي اطلاعات رنگي مورد استفاده قرار مي‌گيرند. به عنوان مثال، شبکه عصبي خودسامانده کوهونن براي کاهش رنگ محبوبيت فراواني دارد که از جمله پژوهش‌هاي مرتبط با آن مي‌توان از [18-20] نام برد. پيش‌تر، با افزايش تعداد ويژگي‌هاي رنگي به صورت افزونه و در نظر گرفتن پيکسل‌ها در فضاهاي رنگي مختلف، در [21] روشي مبتني بر شبکه عصبي خودسامانده پيشنهاد کرديم که به دسته‌بندي بهتر رنگ‌ها مي‌انجامد.

در روش‌هاي مزبور، پيكسل‌هاي تصوير مانند يك بردار با مؤلفه‌هاي ويژگيهاي رنگي (مثلاً درصد مشاركت رنگهاي اصلي قرمز و سبز و آبي در ساخت آن) در نظر گرفته مي‌شوند كه بايد با هم تركيب شوند و بردارهايي بسازند كه نمايندگان خوبي از رنگهاي تصوير باشند. به بيان ديگر بهكاهش رنگمي‌توان به عنوان يك تبديل از فضاي برداري وسيع به فضاي برداري محدود نگريست. اين فضاي برداري محدود همان رنگ‌هاي مهم تصوير است كه دسته‌بندي اشياء تصوير به كمك آنها مي‌تواند قدم مهمي در بخش‌بندي ابتدايي تصوير باشد[20, 22].

يكي از راه‌حل‌هاي ساده،سريع،و كارا براي مسأله خوشه‌بندي استفاده از الگوريتمk-means است[23] كه به همراه نسخه فازي آن به نام Fuzzy c-means يا FCM [24]،پركاربردترين الگوريتم‌هاي خوشه‌بندي در كاربردهاي صنعتي پردازش تصوير و يادگيري ماشين به شمار مي‌روند که از جمله پژوهش‌هاي اخير مي‌توان به الگوريتم‌هاي پيشنهاد شده در [25-28] اشاره کرد.هرچند با استفاده از اين الگوريتم مانند آنچه پيش‌تر در [21] پيشنهاد کرديم، مي‌توان با حفظ كيفيت بصري تصوير، پهناي باند لازم براي انتقال و نيز فضاي مورد نياز براي ذخيره‌سازي تصوير را به نحو مطلوبي كاهش داد، اما به لحاظ تنوع رنگ و جزييات بافتي تصاوير بيروني، روش k-means استاندارد (مانند ديگر روش‌هاي خوشه‌بندي رنگي) معمولاً كارايي مناسبي در كاهش رنگ اين تصاوير به هدف بخش‌بندي ابتدايي (كه در آن شكل كلي اشياء اهميت بيشتري دارد) از خود نشان نمي‌دهدو عموماً منجر به بخش‌بندي نادرست مي‌شود[29, 30]. به منظور بهبود روش k-means براي بخش‌بندي رنگي تصاوير بيروني، در [31]روشي مبتني بر خوشه‌بندي سلسله‌مراتبي با حذف تدريجي خوشه‌ها با استفاده از هرم گوسي با دقت چندگانه پيشنهاد كرديم كه در مقايسه با روش k-means عادي، كارايي بهتري در بخش‌بندي تصاوير بيروني و ايجاد شكل كلي اشياء از خود نشان مي‌داد. در اين مقاله، روش فوق به صورت تطبيق‌پذير با تصوير گسترش داده مي‌شود تا به كمك تجمع آماري رنگ‌هاي تصوير كه از روي هيستوگرام توزيع رنگ به دست مي‌آيند، بتواند نسبت به شرايط نوري و بافتي متنوع تصاوير بيروني مقاوم باشد. كارايي اين الگوريتم نسبت به روش k-means استاندارد و نسخه بهبود يافته آن، به كمك يك روش ارزيابي نظارت‌شده روي دو مجموعه تصوير استاندارد در بستري با دقت دوگانه بررسي خواهد شد.

در بخش 2 به معرفي روش k-means و عملكرد آن در كاهش رنگ تصاوير بيروني خواهيم پرداخت. بخش 3 اين تحقيق به تشريح الگوريتم k-means بهبود يافته و نسخه گسترش يافته آن اختصاص دارد. روش و نتايج ارزيابي الگوريتم در بخش 4، تحليل نتايج در بخش 5 و جمع‌بندي نهايي و پيشنهادهايي براي بهبود روش مورد تحقيق در بخش 6 آورده شده است.

2. روش k-means براي كاهش رنگ

روش k-means استاندارد، يك الگوريتم خوشه‌بندي است كه مي‌تواند براي دسته‌بندي رنگهاي يك تصوير به كار رود. اگر هر پيكسل تصوير رنگي را برداريمتشكل از ويژگي‌هاي رنگيآن پيكسل در نظر بگيريم، روش k-means بايد اين بردارهاي رنگي را از رويشباهتشان به هم به kخوشه تقسيم كند. هرچند ساده‌ترين ويژگي‌هاي رنگي مورد استفاده، ويژگي‌هاي فضاي RGB يا مانند [32] ويژگي‌هاي فضايHSV است، اما تحقيقات انجام شده در[33] نشان مي‌دهد فضاي رنگي CIE-Lab به لحاظ ادراكي بودن، بيشترين بازده را در مسأله خوشه‌بندي رنگي دارد. به‌علاوه چون فاصله اقليدسي دو رنگ در اين فضا متناسب با تفاوت بصري آنهاست، خوشه‌بندي رنگي با تكيه بر فاصله اقليدسي در اين فضا كاراتر ميشود. به همين لحاظ در اين تحقيق از ويژگي‌هاي رنگي پيكسل‌ها درفضاي CIE-Labاستفاده شده است.

الگوريتم k-means براي خوشه‌بندي فوق به شرح زير است:

1) در آغاز k پيكسل تصادفي از تصويربه عنوان نمايندگان ابتداييkخوشه رنگي (در فضاي CIE-Lab) انتخاب مي‌شوند كه بايد در ادامه اصلاح شوند.

2) يكي از پيكسل‌هاي تصوير به صورت تصادفي انتخاب و به بردارهاي نماينده عرضه مي‌شود. شباهت بردار ورودي با هركدام از بردارهاي نماينده كه بيشتر باشد، بردار ورودي جذب آن شده و در عين حال آن بردار نماينده را به خود شبيه مي‌كند. براي اين هدف، مقدار جديد بردار نماينده «برنده» برابر ميانگين مقدار قبلي و بردار ورودي جذب شده خواهد بود (رابطه 1). معيار شباهت مي‌تواند فاصله اقليدسي، حاصلضرب داخلي، يا معيارهاي ديگر باشد.

(1) (پيكسل جديد ، بردار نماينده قديم)ƒ = بردار نماينده جديد

كه تابع ƒ در الگوريتم k-means تابع ميانگين مي‌باشد.

3) گام 2 با ارائه بقيه پيكسلهاي تصوير به بردارهاي نماينده و تكرار اين روند تا جايي ادامه مي‌يابد كه بردارهاي نماينده در جاي صحيح خود قرار گيرند. معيار اين صحّت، كمينه شدن حاصل‌جمع خطاها، S، در رابطه 2 است:

S = Σi=all clustersΣj=all pixels in the i-th cluster d(ci,pj)(2)

كه در آن d(ci,pj) فاصله اقليدسي مركز خوشه iام تا پيكسل jام آن خوشه است.

انتساب بردارهاي ورودي براي تصحيح مقادير بردارهاي نماينده حتماً بايد تصادفي باشد؛ در غير اين صورت بردارهاي نماينده در فضاي برداري به خوبي پخش نخواهند شد و مشكل فراموشي پيش خواهد آمد[34].

4) پس از پايان فرآيند آموزش، بردارهاي نماينده در محل صحيح خود قرار گرفته‌اند. اكنون با ارائه پيكسلهاي تصوير به اين بردارها و نظير كردن هر پيكسل به شبيه‌ترين بردار نماينده، مي‌توان به خوشه‌بندي صحيحي رسيد.

روش فوق به عنوان يكي از متداول‌ترين شيوه‌هاي خوشه‌بندي و كاهش رنگ تصاوير به كار مي‌رود؛ اما همانطور كه در بخش ارزيابي نتايج نشان داده خواهد شد، روش k-means استاندارد كارايي مناسبي در كاهش رنگ اين تصاوير به هدف بخش‌بندي ابتدايي از خود نشان نمي‌دهد[29][30]. شكل 1 اين مطلب را به خوبي نشان مي‌دهد.

$Description: F:\Scientific\University\PhD\Thesis\Color Reduction\ادامه\Journal Paper\Fig1.tif$ Main

شكل 1 – تصوير اصلي (راست) و تصوير كاهش رنگ داده شده به كمك الگوريتم k-means (چپ)

همانطور كه مشاهده مي‌شود، الگوريتم k-meansمي‌تواند رنگهاي تصوير را با حفظ كيفيت بصري تركيب كند. اما تصوير حاصل از آن براي بخش‌بندي به هدف تشخيص شيء مناسب نيست. مثلاً در شكل بالا ديده مي‌شود كه آسمان و چمن با وجود اينكه يك شيء واحد هستند، به دليل وجود جزييات بافتي و سايه‌هاي رنگي مختلف، به چند بخش مختلف كم‌اهميت تقسيم شده‌اند. به علاوه، بعضي اشياء كوچك به اشتباه با كلاس‌هاي بزرگتر تركيب شده‌اند؛ مثلاً برج وسط تصوير با جاده يا ساختمان‌هاي بالا سمت چپ با سبزه و شاخ و برگ درختان تلفيق شده‌اند.

اهمّ دلايل عدم كارايي الگوريتم k-means ‌استاندارد براي بخش‌بندي به هدف تشخيص اشياء در تصاوير بيروني به شرح زير است:

جزييات بافتي،تعداد زيادي بخش كوچك و جدا از هم توليد مي‌كند كه براي روندهاي تشخيص اشياء مشكل‌ساز مي‌باشند (چمن در شكل 1).

تعدادي از اشياء كوچك در بخش‌هاي بزرگتر ادغام مي‌شوند (برج وسط تصوير در شكل 1)

سايه‌هاي رنگي متعلق به يك شيء تعدادي بخش بي‌مورد توليد مي‌كنند (چمن و آسمان در شكل 1).

جزييات بافتي زياد و نيز اشياء كوچك و ناهمگن در تصاوير بيروني باعث ايجاد نويز زيادي مي‌شوند كه سرعت و نيز دقت همگرايي را كاهش مي‌دهد و يك خطاي مانا در رابطه (2) ايجاد مي‌كند.

شكل 2 يك نماي دوبعدي از مشكلات الگوريتم k-meansدر بخش‌بندي را نشان مي‌دهد.

$F:\Scientific\University\PhD\Thesis\Papers\Customizing the k-mean method towards color segmentation of outdoor images\Figures\2-b.tif$	$F:\Scientific\University\PhD\Thesis\Papers\Customizing the k-mean method towards color segmentation of outdoor images\Figures\2-a.tif$
الف) يك فضاي دوبعدي نوعي	ب) خوشه‌بندي ايده‌آل
$F:\Scientific\University\PhD\Thesis\Papers\Customizing the k-mean method towards color segmentation of outdoor images\Figures\2-d.tif$	$F:\Scientific\University\PhD\Thesis\Papers\Customizing the k-mean method towards color segmentation of outdoor images\Figures\2-c.tif$
ج) خوشه‌بندي به كمك الگوريتم k-means عادي	د) خوشه‌بندي به كمك الگوريتم پيشنهادي

شكل 2) كارايي الگوريتم k-means در خوشه‌بندي

در شكل 2-الف تعدادي نقطه را در يك فضاي دوبعدي مي‌بينيد كه بايد دسته‌بندي شوند. يك خوشه‌بندي ايده‌آل بايد اين نقاط را به شش دسته (سه دسته بزرگتر و سه دسته كوچكتر) تقسيم كند (شكل 2-ب). اما تعداد زياد نقاط در دسته‌هاي بزرگتر سبب مي‌شود تمركز الگوريتم خوشه‌بندي k-means بر اين دسته‌ها بيشتر شود. در نتيجه همانطور كه در شكل 2-ج ديده مي‌شود، خوشه‌هاي بزرگتر به چند دسته كوچكتر تقسيم مي‌شوند و خوشه‌هاي كوچكتر ناديده گرفته مي‌شوند. شكل 2-د خوشه‌بندي به كمك الگوريتمي كه در بخش بعد تشريح مي‌شود را نشان مي‌دهد.

3. بهبود الگوريتم k-means به كمك هرم تصاوير چند دقتي

حتماً تاكنون صحنه‌اي را كه شخصي كه تازه به هوش مي‌آيد در مقابل خود مشاهده مي‌كند، ديده‌ايد؛ اشياء ابتدا كاملاً محو هستند و تنها رنگ چند شيء اصلي مشخص است. رفته‌رفته اشياء مشخص‌تر مي‌شوند و حتي اشياء جديد كه قبلاً ديده نمي‌شده‌اند اضافه مي‌شوند. اين موضوع مي‌تواند براي بخش‌بندي ابتدايي تصاوير بيروني يك ايده مناسب باشد؛ چون چشم انسان نيز در وهله اول براي تشخيص اشياء مختلف به رنگ آنها بيشتر از جزييات بافتي توجه مي‌كند.

اگر يك فيلتر ملايم‌كننده (مانند فيلتر ميانگير يا گوسي) را پي‌درپي روي يك تصوير اعمال كنيم، تعدادي تصوير محوشده با دقت‌هاي متفاوت به دست مي‌آيند. اين تصاوير در بسياري از كاربردهاي پردازش تصوير از جمله بخش‌بندي و دسته‌بندي تصاوير مفيد هستند[35-37]. چون با هربار اعمال فيلتر ملايم‌كننده روي تصوير، حجم اطلاعات کمتر مي‌شود، مي‌توان با کاهش ترکيبي نمونه‌ها اندازه تصوير را نيز کاهش داد. بنابراين مجموعه تصاوير چنددقتي مي‌توانند يك هرم تشكيل دهند كه تصوير اصلي در قاعده آن و تصاوير محوتر (و البته كوچكتر) در طبقات بالاتر قرار مي‌گيرند. شكل 3 يك هرم تصاوير چنددقتي را نشان مي‌دهد.

اولين كاربرد هرم تصاوير چنددقتي در بخش‌بندي تصاوير به كمك ايجاد پيوندهايي بين پيكسلهاي نظير در طبقات مختلف هرم در [35] مطرح شد. در سالهاي اخير بخش‌بندي تصاوير با استفاده از ويژگي‌هايي كه از طبقات مختلف اين هرم استخراج مي‌شوند، موضوع تحقيقات زيادي بوده است كه نمونه‌هايي از آنها در [36] فهرست شده‌اند. همچنين در [37] روشي براي خوشه‌بندي رنگي بر اساس تحليل قله‌هاي هيستوگرام در طبقات مختلف هرم فوق مطرح شده است.

شكل 3) هرم تصاوير چنددقتي براي يك تصوير بيروني

3.1. الگوريتم بهبوديافته

در طبقات بالاي هرم چنددقتي، جزييات بافتي و اشياء كوچك محو شده و رنگ مهمترين ويژگي شيء براي بخش‌بندي خواهد بود.به علاوه سايه‌هاي مربوط به يك رنگ تا حد زيادي با هم تركيب مي‌شوند. اين دو ويژگي يك بستر مناسب براي كاهش رنگ تصاوير بيروني را فراهم مي‌كند. در[31]براي ايجاد تصاوير 6 رنگ و 9 رنگ يك روشكاهش رنگ بر اساس الگوريتم k-meansپيشنهاد كرديم كه در هر طبقه هرم تصاوير چنددقتي به كمك خوشه‌بندي رنگي اشياء مهم را تشخيص داده و در طبقه زيرينآنها را حذف مي‌كند تا بخش‌‌بندي در ادامه فقط روي اشياء باقي‌مانده متمركز شود. استفاده از اين روش نسبت به خوشه‌‌بندي كامل و يك‌مرحله‌اي تصوير در طبقات مختلف هرم فوق كارايي بهتري از خود نشان داده است؛ چون از تأثير خوشه‌هاي بزرگ در خوشه‌بندي رنگي در طبقات پايين هرم جلوگيري مي‌كند.

مراحلاين روش (كه از اين پس الگوريتم حذف تدريجي ناميده مي‌شود) براي ايجاد يك تصوير 6 رنگ به كمك دو طبقه از هرم چنددقتي به شرح ذيل مي‌باشد:

1) يك فيلتر ملايم‌كننده 3×3 ميانگيررا 5 بار و 10 بار روي تصوير اصلي اعمال مي‌كنيم تا دو نسخه محو شده از تصوير (كه به ترتيب B1 وB2 ناميده مي‌شوند) به دست آيند.شكل 4 اين تصاوير محو شده را نشان مي‌دهد.


الف	ب	ج

شكل 4- الف) تصوير اصلي ب) تصوير B1 ج) تصوير B2

اين كار باعث مي‌شود تا نقاط مزاحم، اشياء بسيار كوچك و به ويژه جزييات بافتي كه در تصاوير بيروني بسيار ديده مي‌شود و كار بخش‌بندي را با مشكل مواجه مي‌كند از بين بروند و با تركيب سايه‌هاي رنگي مشابه، تنها دسته‌هاي رنگي مهم باقي بمانند.

2) به كمك روش k-means تصوير B2 (محوترين نسخه تصوير) را به سه خوشه رنگي تقسيم مي‌كنيم. شكل 5-الف يك تصوير بيروني و شكل 5-ب، نسخه سه‌رنگي آن را نشان مي‌دهد.اين سه خوشه از رنگهاي بسيار مهم تصوير با چگالي پيكسلي بالا هستند. نكته مهمي كه بايد در اينجا مورد توجه قرار بگيرد اين است كه تعدادي از پيكسلهاي تصوير واقعاً به اين سه كلاس شباهت دارند و در خوشه رنگي آنها قرار مي‌گيرند؛ اما نقاطي ديگر هم در تصوير وجود دارند كه مربوط به اشياء ديگر هستند و رنگهاي آنها شباهتي به اين سه خوشه رنگي ندارد؛ اما به ناچار در اين خوشه‌ها قرار گرفته‌اند. در گام بعدي اين نقاط به صورت مجزا خوشه‌بندي خواهند شد. مقايسه شكل‌هاي 5-ب و5-ج نشان مي‌دهد حتي اين كاهش رنگ سه‌خوشه‌اي به كمك تصاوير محوشده، به خاطر حذف جزييات بافتي از ديد بخش‌بندي بهتر از كاهش رنگ در فضاي معمولي عمل مي‌كند (هرچند كيفيت بصري پايين‌تري دارد).

3) اكنون فاصله اقليدسي نقاط تصوير B1(نسخه واضح‌تر تصوير) را تا سه نماينده به دست آمده از مرحله قبل محاسبه مي‌كنيم. نقاطي كه فاصله اقليدسي‌شان از هر سه نماينده بيش از حد آستانه th1 باشد، در هيچكدام از خوشه‌هاي رنگي جا نمي‌گيرند و بايد مجدداً خوشه‌بندي شوند. روش تعيين حد آستانه مزبور را در ادامه خواهيم ديد.اين نقاط را (كه نقاط يتيم ناميده مي‌شوند) در شكل 5-د مي‌بينيد (قسمت سفيدرنگ اين تصوير حاوي پيكسل‌هاي غيريتيم است كه در خوشه‌بندي مرحله اول نمايندگان مناسب خود را يافته‌اند).

4) اكنون به روشي مشابه گام 2، نقاط يتيم را به سه خوشه جديد تقسيم مي‌كنيم تا مجموعاً شش خوشه رنگي در تصوير به دست آوريم.تصوير 6 كلاسه كه به اين روش به دست آمده (شكل 5-هـ) براي بخش‌بندي مناسب است؛ به ويژه وقتي آن را با زماني مقايسه كنيم كه از ابتدا تصوير را به 6 كلاس تقسيم كرده باشيم (شكل 5-و). براي مقايسه بهتر از يك جعبه رنگ متفاوت و درخشان استفاده شده است.


الف	ب	ج
	$F:\Users\Administrator\Desktop\Fig.5.d.jpg$
د	هـ	و

شكل 5) الف) تصوير اصلي ب) تصوير B2 سه‌رنگي شده ج) تصوير اصلي سه‌رنگي شده د) نقاطي كه در 3 خوشه رنگي جا نگرفته‌اند هـ) تصوير شش رنگ به كمك k-means در هرم تصاوير چنددقتي و) تصوير شش رنگ به كمك k-means عادي

اين كيفيت بهتر ناشي از اين است كه در مرحله مياني، سه خوشه‌اي كه از مرحله اول به دست آمده‌اند حذف مي‌شوند و در مرحله آخر سه خوشه جديد فقط با تمركز بر بقيه تصوير به دست مي‌آيند؛ در حالي كه وقتي از ابتدا تصوير را به 6 خوشه تقسيم كنيم، نقش خوشه‌هايي با چگالي بالا پررنگ‌تر مي‌شود.به بيان ديگر، اين روش با حذف خوشه‌هاي رنگي مهم كه از طبقه بالا‌تر به دست آمده‌اند، از نسخه واضح‌تر تصوير براي يافتن اشياء جديد استفاده مي‌كند و با جلوگيري از تمركز خوشه‌هاي رنگي در رنگهاي مهم با چگالي پيكسلي بالا، به خوشه‌هاي رنگي كوچكتر (اشياء كوچكتر) ميدان بروز مي‌دهد (شكل 2 را مجدداً ببينيد).


الف	ب
$D:\Scientific\University\own\PhD\Thesis\Final Thesis\Report\CH3\kmeans6-Pyramid.tif$
ج	د

شكل 6- الف) تصوير اصلي ب) تصوير 3 رنگ شده ج) تصوير 6 رنگ شده با روش حذف تدريجي د) تصوير 6 رنگ شده با k-meansعادي

شكل 6 اثر اجراي اين الگوريتم روي تصويري ديگر را نشان مي‌دهد.

3.2. تعيين تطبيقي تعداد خوشه‌ها

همان‌طور که پیش‌تر اشاره شد، هدف از به‌کارگيري خوشه‌بندي در اين تحقيق، ايجاد پيش‌الگوهاي مناسب براي بخش‌بندي و تشخيص اشياء در تصاوير بيروني است. يکي از مسايل مهم در خوشه‌بندي رنگي، تشخيص تعداد صحيح رنگ‌های تصوير است[20, 38]. ايجاد پيش‌الگوهاي زياد (در نظر گرفتن تعداد زياد رنگ نهايي در فرآيند کاهش رنگ مانند آنچه در[39]پيشنهاد شده است) مي‌تواند باعث سنگين شدن فرآيند بخش‌بندي و نهايتاً منجر به فرابخش‌بندي شود. از سوي ديگر تعداد کم پيش‌الگوها هم باعث از دست رفتن تعدادي از بخش‌ها و بخش‌بندي نادرست خواهد شد[40]. در اين تحقيق، مطابق با آنچه در[41]پيشنهاد کرديم، براي تخمين تعداد خوشه‌هاي رنگي مهم در هر مرحله خوشه‌بندي به صورت زير عمل مي‌کنيم:

1) به کمک الگوريتم تقسيم تطبيقي مکعب RGB تعدادي تجمع پيکسلي در فضاي رنگي مي‌يابيم؛ به گونه‌اي که اين تعداد، از تعداد رنگي که معمولاً در يک تصوير بيروني يافته مي‌شود بيشتر باشد.

2) يک گراف وزن‌دار کاملاً متصل که هر گره آن، ويژگي رنگي ميانگين در يک خوشه در فضاي رنگي CIE-Lab و وزن هر يال آن فاصله اقليدسي بين رنگ دو گره دو سر آن (که در فضاي مزبور متناظر با تفاوت بصري آن‌ها است) باشد، ايجاد مي‌کنيم.

3) يالي که کمترين وزن را دارد، کمترين فاصله اقليدسي (معادل با کمترين تفاوت بصري) موجود بين دو رنگ را نشان مي‌دهد. اگر وزن اين يال از يک حد آستانه کمتر باشد، نشان مي‌دهد که گره‌هاي (رنگ‌هاي) دو سر اين يال به دليل تشابه رنگي زياد نامزد ترکيب شدن با يکديگر هستند. بنابراين دو رنگ مزبور را با هم ترکيب کرده و يک رنگ ايجاد مي‌کنيم؛ به علاوه در ساختار گراف، دو گره معادل اين دو رنگ را ترکيب کرده و رنگ ميانگين را به عنوان ويژگي رنگي گره جديد ثبت کرده و وزن يال‌هايي که به يکي از دو گره قبلي مرتبط بوده‌اند را به‌روز مي‌کنيم. به کمک ايده هرس گراف که در[41] نمونه‌اي از آن را مطرح کرديم، اين کار را تا جايي ادامه مي‌دهيم که کمترين وزن يال موجود در گراف (کمترين تفاوت بصري بين دو خوشه رنگي) از يک حد آستانه بيشتر شود (يعني دو رنگ خيلي شبيه به هم نداشته باشيم). تعداد گره‌هاي باقيمانده نشان‌دهنده تعداد خوشه‌هاي رنگي مهم تصوير هستند.

حد آستانه را درصدي از فاصله اقليدسي بيشينه در فضاي رنگي CIE-Lab در نظر مي‌گيريم. هرچه اين درصد بالاتر باشد، به رنگ‌ها بيشتر اجازه ترکيب شدن داده مي‌شود؛ يعني تعداد خوشه‌هاي رنگي در هر مرحله کمتر مي‌شود و پيش‌الگوهاي کلي‌تري خواهيم داشت. براي دست‌يابي به بخش‌بندي جزيي‌تر، بايد اين درصد کمتر شود. در اين تحقيق بهترين پاسخ‌ها با 5% ديده شده است. اين تعداد خوشه‌ها به الگوريتم خوشه‌بندي با حذف تدريجي داده مي‌شوند تا خوشه‌هاي مناسب پيش‌الگوهاي بخش‌بندي را ايجاد کند.

3.3. تعيين سطوح آستانه شباهت

همانطور كه پيشتر گفته شد، در روش حذف تدريجي در مرحله اول تصوير به سه رنگ اصلي خوشه‌بندي مي‌شود و در مرحله دوم، نقاطي كه به نمايندگان سه رنگ اصلي شبيه نيستند (پيكسل‌هاي يتيم)، مجدداً خوشه‌بندي مي‌شوند. معيار خوشه‌بندي مجدد يك پيكسل اين است كه فاصله اقليدسي آن پيكسل تا نماينده دسته‌اش از سطح آستانه th1بيشتر باشد.شكل 7 نمودار هيستوگرام تعداد پيكسل‌ها برحسب فاصله تا نماينده دسته در يك خوشه نوعي را نشان مي‌دهد.

شكل 7- نمودار تعداد پيكسل‌ها برحسب فاصله اقليدسي تا نماينده دسته در يك خوشه نوعي

همانطور كه در اين شكل مي‌بينيد، نمودار دو قله‌اي است؛ قله اول مربوط به تجمع پيكسل‌هايي است كه به نماينده دسته شبيه هستند و قله دوم، پيكسل‌هايي را نشان مي‌دهد كه به نماينده خوشه شبيه نيستند (احتمالاً مربوط به يك شيء جديد). بديهي است آستانه th1 بايد جايي بين اين دو قله باشد.

تعيين صحيح حد آستانه شباهت، يك عامل تعيين‌كننده در كيفيت الگوريتم فوق است. به همين لحاظ روشي بايد تدوين شود كه اين حد آستانه را از روي مشخصات آماري تصوير به صورتي تعيين كند كه در مقابل تغييرات ويژگي‌هاي خاص تصاوير بيروني از جمله تغييرات بافتي و رنگي و نوري مقاوم باشد.

3.3.1. سطح آستانه ثابت

مي‌توان سطح آستانه شباهت هر خوشه را مانند روشي كه در[31]پيشنهاد داده‌ايم، يك مقدار ثابت (مثلاً 90% بيشينه فاصله اقليدسيبين پيكسلهاي آن خوشه با مركز آن) در نظر گرفت؛ رابطه 3جزييات اين روش را نشان مي‌دهد:

thi= Max(di) × 90% (3)

thi سطح آستانه خوشه iام و di مجموعه فاصله اقليدسي پيكسلهاي خوشه iام با مركز آن است.

اين روش در بسياري از موارد بهبود خوبي نسبت به روش k-means عادي از نظر دقت بخش‌بندي ايجاد مي‌كند؛ اما در بعضي از موارد نيز موفق عمل نمي‌كند؛ دليل اين عدم موفقيت را مي‌توان در عدم توجه كافي رابطه 3 به توزيع رنگهاي درون يك خوشه جستجو كرد. به بيان ديگر تعيين يك درصد ثابت براي تمام خوشه‌ها در تمام تصاوير (به ويژه در مورد تصاوير بيروني كه داراي تنوع رنگ و نور هستند) نمي‌تواند انتخاب مناسبي باشد.به عنوان مثال، حتي چند پيكسل محدود كه دور از مركز يك خوشه قرار گرفته باشند (مثلاً در اثر نويز)، باعث زياد شدن سطح آستانه مي‌شوند. در شكل 8دو خوشه نوعي دوبعدي با سطح آستانه ثابت 50% با هم مقايسه شده‌اند:

Fig8-a Fig8-b

شكل 8- مقايسه حد آستانه شباهت دو خوشه تقريباً مشابه

در شكل بالا دو خوشه با توزيع تقريباً مشابه را مي‌بينيد كه حد آستانه شباهت آنها (كه با يك دايره نشان داده شده است) اصولاً بايد شبيه هم باشند؛ اما چند پيكسل دور از مركز در خوشه سمت چپ باعث افزايش قابل ملاحظه سطح آستانه شباهت اين خوشه شده است. هرچند احتمالاً مي‌توان براي يك مجموعه ثابت از تصاوير يك سطح آستانه شباهت مناسب از راه سعي و خطا به دست آورد؛ اما اين حد آستانه بهمجموعه ديگري از تصاوير قابل تعميم نيست. به بيان ديگر الگوريتم فوق در برابر تغييرات شرايط نوري و بافتي مقاوم نيست؛ به همين لحاظ بهتر است حد آستانه شباهت هر خوشه با توجه به توزيع آماري رنگ‌ها در آن خوشه تعيين شود.

3.3.2. تعيين سطح آستانه به كمك هيستوگرام رنگ

همانطور كه گفته شد، الگوريتم خوشه‌بندي در مرحله اول تعدادي از رنگهاي تصوير را در يك دسته قرار مي‌دهد. تعدادي از رنگ‌هاي هم‌دسته واقعاً به هم شبيه هستند (احتمالاً مربوط به يك شيء)؛ اما در هر دسته چند رنگ (چند شيء) وجود دارند كه شباهتي به رنگهاي ديگر آن دسته ندارند و به ناچار در آن دسته قرار گرفته‌اند. اين رنگ‌ها بايد از اين دسته تفكيك و مجدداً خوشه‌بندي شوند تا بتوانند اشياء ديگر تصوير را مشخص كنند.مطابق آنچه در [42] پيشنهاد شده است، مي‌توان توزيع رنگ‌هاي داخل يك خوشه را (مانند ديگر پديده‌هاي طبيعي)،توزيع نرمال تجمعي حول رنگ ميانگين آن دسته فرض كرد. شكل 9 نمودار يك توزيع نرمال را نشان مي‌دهد.

شكل 9- نمودار تجمع داده‌ها در يك توزيع نرمال

همانطور كه در اين نمودار ديده مي‌شود، حدود 68% انرژي توزيع نرمال در فاصله «انحراف معيار±ميانگين» و حدود 95% انرژي آن در فاصله «انحراف معيار×2 ± ميانگين» قرار دارد. بنابراين براي به دست آوردن پيكسل‌هاي يتيم مي‌توان حد آستانه شباهت را مثلاً در فاصله اقليدسي2σ(دوبرابر انحراف معيار) از ميانگين خوشه در نظر گرفت. البته براي مسأله مورد نظر ما در اين تحقيق، «ميانگين خوشه رنگي» پارامتر برآورد تجمع رنگها در يك خوشه نيست؛ چون مي‌تواند توسط رنگ‌هاي دور از مركز دسته تحت تأثير سوء قرار گيرد. شاخص تجمع در اين مسأله «تكرار رنگها» و به عبارت ديگر «مد» توزيع آماري رنگ‌ها در يك خوشه است؛ به بيان ديگر رنگ‌هاي كه دور از رنگ‌هاي پرتكرار خوشه‌شان قرار مي‌گيرند، بايد به عنوان «يتيم» در نظر گرفته شده و مجدداً خوشه‌بندي شوند. بنابراين هرچند در مورد توزيع نرمال ميانگين و مد با هم برابرند، اما در ادامه شاخص مد را به عنوان معيار تجمع در نظر مي‌گيريم.

$F:\Users\Administrator\Desktop\Fig-10-2.tif$

$F:\Users\Administrator\Desktop\Fig-10-1.tif$

$F:\Users\Administrator\Desktop\Fig-10-3.tif$

شكل 10–هيستوگرام ته‌رنگ (Hue) در سه خوشه رنگي مربوط به شكل 5

توزيع رنگ‌هاي يك تصوير بيروني در خوشه‌هاي رنگي، كمي با توزيع نرمال متفاوت است (هرچند اين توزيع‌ها را نمي‌توان به توزيعي بهتر از نرمال نظير كرد). شكل 10 نمونه توزيع هيستوگرام ته‌رنگ (پارامتر H در فضاي رنگي HSV[32]) در سه خوشه شكل 5 را نشان مي‌دهد. اين هيستوگرام‌ها حالت حلقوي دارند؛ به عبارت ديگر پيكسلهايي كه در انتهاي نمودار (با مقدار 1) قرار دارند، با پيكسل‌هاي ابتداي نمودار (با مقدار صفر) هم‌رنگ مي‌باشند. شكل 11 اين موضوع را نشان مي‌دهد.

hue

0 1

شكل 11– نمودار تغييرات ته‌رنگ (Hue)

نمودارهاي شكل 10 نشان مي‌دهند كه توزيع رنگ‌ها در يك خوشه رنگي حالت شبه‌نرمال داشته و نيز در خوشه‌هاي مختلف شكلي متفاوت دارد؛ بنابراين فاصله اقليدسي 2σاز «مد» رنگ‌ها در همه تصاوير انتخاب مناسبي نيست. به علاوه گاهي با توزيع‌هاي نرمال چندقله‌اي مواجه هستيم كه تكيه بر مشخصات توزيع نرمال تك‌قله‌اي را ناموجه مي‌سازد (هيستوگرام خوشه اول در شكل 10 را ببينيد).

براي رفع اين مشكل، در اين تحقيق از شيوه‌اي ديگر براي تعيين رنگ‌هاي يتيمدر يك خوشه استفاده مي‌كنيم. مراحل اين روش به شرح ذيل است:

بلندترين قله هيستوگرام رنگ يك خوشه را انتخاب مي‌كنيم (µ). اين رنگ، پرتكرارترين رنگ در اين خوشه و به عبارتي «مد» اين توزيع آماري است.

از سمت راست µ به سمت انتهاي هيستوگرام حركت مي‌كنيم تا به رنگي برسيم كه تعداد پيكسلهاي آن كمتر از 5% پيكسل‌هاي به رنگ µ باشد. اين رنگ را U مي‌ناميم. اگر در اين حركت به انتهاي هيستوگرام برخورديم و هنوز به رنگ U نرسيده باشيم، به دليل حلقوي بودن هيستوگرام ته‌رنگ «چرخ زده» و جستجو را از ابتداي هيستوگرام پيگيري مي‌كنيم.

از سمت چپ µ به سمت ابتداي هيستوگرام حركت مي‌كنيم تا به رنگي برسيم كه تعداد پيكسلهاي آن كمتر از 5% پيكسل‌هاي به رنگ µ باشد. اين رنگ را L مي‌ناميم. اگر در اين حركت به ابتداي هيستوگرام برخورديم و هنوز به رنگ L نرسيده باشيم، به دليل حلقوي بودن هيستوگرام ته‌رنگ «چرخ زده» و جستجو را از انتهاي هيستوگرام پيگيري مي‌كنيم.

به كمك رابطه 4، رنگ‌هايي كه پيكسل‌هاي آن رنگ يتيم هستند را تعيين مي‌كنيم:

(4)

شكل 12رنگ‌هاي مزبور(داخل مستطيل قرمز رنگ) در مورد سه خوشه رنگي را نشان مي‌دهد. پيكسل‌هايي به اين رنگ‌ها يتيم هستند و مجدداً خوشه‌بندي مي‌شوند تا رنگ‌هاي جديدي (مربوط به اشياء جديد) را معرفي كنند. توجه كنيد كه در خوشه اول شكل 12 شرط L < U و در خوشه‌هاي دوم وسوم شرط U < L صادق است.

4. ارزيابي روشها

همانطور كه در شكلهاي 5 و 6 ديديم، روش حذف تدريجي از نظر بصري نسبت به روش عادي نتايج مناسبتري براي بخش‌بندي توليد مي‌كند. اما ارزيابي بصري نمي‌تواند ملاكي مناسب براي ارزيابي كيفيت يك روش بخش‌بندي باشد. به همين لحاظ، براي ارزيابي كارايي الگوريتم بهتر است از يك روش كمّي نيز استفاده شود.

روش‌هاي كمّي ارزيابي الگوريتم‌هاي بخش‌بندي به سه دسته عمده تقسيم مي‌شوند[43]:

الف) روش‌هاي تحليلي كه بر ويژگي‌هاي يك الگوريتم بخش‌بندي مانند پيچيدگي و بهره‌وري زماني و نوع پردازش، فارغ از خروجي آن تمركز مي‌كنند. اين روش‌ها براي مقايسه كارايي الگوريتم‌هاي بخش‌بندي در تشخيص شيء چندان مناسب نيستند.

ب) روش‌هاي تجربي نظارت شده كه كيفيت يك الگوريتم بخش‌بندي را بر اساس اختلاف خروجي آن با بخش‌بندي دستي توسط ناظر مي‌سنجند.

ج) روش‌هاي تجربي نظارت‌نشده كه بر اساس پارامترهاي ديد انساني نسبت به كيفيت يك الگوريتم بخش‌بندي اظهار نظر مي‌كنند.

بهترين و معمول‌ترين شيوه ارزيابي كمّي الگوريتم‌هاي بخش‌بندي كه در اين تحقيق نيز از آن استفاده شده است، روش نظارت شده مي‌باشد كه بيشترين دقت در ارزيابي الگوريتم‌ها را داراست [43]. بنابراين بايد تعدادي تصوير بيروني را توسط ناظر انساني به 6 رنگ بخش‌بندي كنيم و سپس تصاوير خوشه‌بندي شده به كمك روش k-means استاندارد و روش‌هاي حذف تدريجي پيشنهاد شده را با تصاوير مرجع مقايسه كنيم. هر روشي كه تصوير حاصل از آن اختلاف كمتري در برچسب پيکسل‌ها با تصوير مرجع داشته باشد روش بهتري است.

$F:\Users\Administrator\Desktop\Fig-12-1.tif$

$F:\Users\Administrator\Desktop\Fig-12-2.tif$

$F:\Users\Administrator\Desktop\Fig-12-3.tif$

شكل 12–رنگ‌هاي يتيم در سه خوشه متفاوت (داخل كادر قرمزرنگ)

براي اين كار، يك پايگاه داده به نام UIDSتوسط «گروه پژوهشي پردازش کاربردي تصوير و سيگنال دانشگاه اصفهان» فراهم آورده شده است که شامل 50 تصوير بيروني با اندازه‌هاي 480×640 و 640×640 مي‌باشد و توسط يك ناظر،بر اساس شباهت‌هاي رنگي بين پيكسل‌ها بخش‌بندي شده تا تصاوير مرجع 6 رنگ(كه به اصطلاح استاندارد طلايي يا Ground Truthناميده مي‌شوند) ايجاد شوند. تصاوير اين پايگاه داده از محيط‌هاي طبيعي و در شرايط نوري، رنگي و بافتي متنوع و بدون نرماليزه شدن تهيه شده است.نقطه ضعف روش نظارت‌شده، امكان عدم دقت ناظر يا اعمال سليقه شخصي وي هنگام بخش‌بندي است؛ براي به حداقل رساندن اين مشكل، تنها رنگ‌هاي اصلي توسط ناظر انتخاب مي‌شود و يافتن رنگ‌هاي مشابه رنگ اصلي در تصوير (پيكسل‌هايي كه در يك خوشه رنگي قرار مي‌گيرند) توسط نرم‌افزار فوتوشاپ و بدون هيچگونه اعمال نظر از سوي ناظر انجام مي‌پذيرد. شكل 13 چند نمونه از تصاويري كه به اين روش بخش‌بندي شده‌اند را نشان مي‌دهد.

a13 100_3330 a12 $F:\Users\Administrator\Documents\MATLAB\MVIPTest\Test-DB\a36.jpg$

100_3330-6 a12-6

شكل 13– تصاوير مرجع ايجاد شده به كمك ناظر انساني و نرم‌افزار فوتوشاپ

اكنون بايد تصاوير ايجاد شده توسط روش k-means‌ استاندارد و دو روش حذف تدريجي(كه در 3-3-1 و 3-3-2 پيشنهاد شده‌اند) را با تصوير مرجع مقايسه كنيم تا مشخص شود كدام روش كيفيت بهتري دارد.

در شكل 14بخش‌هاي ايجاد شده در تصوير مرجع، تصوير ايجاد شده به كمك روش عادي و تصوير ايجاد شده به كمك روش حذف تدريجي را مي‌بينيد.بخش‌هاي مشابه به روشي خودكار و با توجه به بيشينه شباهت بين دو بخش تعيين مي‌شوند.

براي ارزيابي هر الگوريتم مطابق با روشي كه در[44] پيشنهاد شده به شيوه زير عمل مي‌كنيم:

الف) تفاضل بين بخش‌هاي به دست آمده از آن الگوريتم و بخش‌هاي به دست آمده از تصوير مرجع (تعداد پيكسل‌هاي مورد اختلاف بين دو بخش متناظر) را مي‌يابيم.

ب) تفاضل‌هاي فوق (كه تعداد آنها بيانگر ضعف الگوريتم در بخش‌بندي صحيح است) را به ازاي تمام بخش‌ها با هم جمع مي‌كنيم.

ج) تعداد پيكسل‌هايي كه به اشتباه بخش‌بندي شده‌اند را بر تعداد كل پيكسل‌هاي تصوير تقسيم مي‌كنيم تا درصد خطاي بخش‌بندي به دست آيد. بديهي است هرچه اين درصد خطا كمتر باشد، الگوريتم قوي‌تر است.

د) متوسط درصد خطا را به ازاي تمام تصاوير پايگاه داده مورد بررسي به دست مي‌آوريم. رابطه 5 نحوه محاسبه متوسط خطاي بخش‌بندي (كه به اختصار ASE‌ ناميده مي‌شود) را نشان مي‌دهد.

(5)

در اين رابطه K تعداد تصاوير در پايگاه داده مورد بررسي (در اينجا 53)، M تعداد بخش‌هاي تصوير مرجع (در اينجا 6)، Ni تعداد پيكسل‌هاي تصوير iام و تعداد پيكسل‌هاي به اشتباه بخش‌بندي شده در بخش jام تصوير iام است.

جدول 1 درصد متوسط خطا در پايگاه داده تهيه شده را در مورد روش k-means عادي و دو نسخه روش حذف تدريجي را نشان مي‌دهد.

جدول 1 – مقايسه كيفيت روش‌هاي خوشه‌بندي براي بخش‌بندي تصاوير به 6 رنگ

الگوريتم	kmeans عادي	روش حذف تدريجي 1 (بخش 3-3-1)	روش حذف تدريجي 2 (بخش 3-3-2)
درصد متوسط خطا (ASE)	21/40%	82/36%	16/29%

$F:\Scientific\University\PhD\Thesis\Color Reduction\cnt\Journal Paper\Fig 11\Main.tif$	$F:\Scientific\University\PhD\Thesis\Color Reduction\cnt\Journal Paper\Fig 11\6.tif$
الف	ب	ج	د

هـ

شكل 14- الف) تصوير اصلي ب) تصوير مرجع ج) تصوير 6 رنگ شده به كمك روش k-means عادي د) تصوير 6 رنگ شده به كمك روش حذف تدريجي هـ) بخش‌هاي به دست آمده از تصوير مرجع و) بخش‌هاي به دست آمده از تصوير 6 رنگ شده به روش حذف تدريجي ز) بخش‌هاي به دست آمده از تصوير 6 رنگ شده به روشk-means عادي

مقادير ذكر شده در جدول 1 نشان‌دهنده كاهش قابل ملاحظه درصد متوسط خطا به كمك روش حذف تدريجي است.

علاوه بر پايگاه داده ذكر شده، روش مورد بررسي اين تحقيق به كمك پايگاه داده استاندارد Sowerby Image Data-base (SID) كه در [45]معرفي شده نيز مورد ارزيابي قرار گرفت. اين مجموعه شامل 104 تصوير بيروني است كه توسط ناظر انساني بر اساس اشياء موجود در تصاوير به 5 تا 7 بخش تقسيم شده‌اند. از اين پايگاه داده براي ارزيابي تحقيقات ديگري از جمله [46] نيز استفاده شده است. جدول 2 كيفيت روش‌هاي مورد بحث در اين مقاله را در مورد اين پايگاه داده نشان مي‌دهد.براي آزمايش روش پيشنهادي در يك بستر با دقت دوگانه روي تصويري از اين پايگاه داده كه به N‌ بخش تقسيم شدهباشد، ابتدا تصوير به سه خوشه و سپس پيكسل‌هاي يتيم به N-3 خوشه تقسيم مي‌شوند.

جدول 2– مقايسه كيفيت روش‌هاي خوشه‌بندي براي بخش‌بندي تصاوير به كمك پايگاه داده SID

الگوريتم	kmeans عادي	روش حذف تدريجي (بخش 3-2-1)	روش حذف تدريجي (بخش 3-2-2)
درصد متوسط خطا (ASE)	12/46%	8/44%	7/26%

همانطور كه در جدول 2 مي‌بينيد، روش حذف تدريجي با آستانه شباهت ثابت براي پايگاه داده SIDبه كيفيت مناسبي نرسيده است. اين در حال است كه با تغيير درصد حذف پيكسل‌هاي يتيم در رابطه 3 با سعي و خطا، درصد خطاي كمتري به دست خواهد آمد(مثلاً به ازاي 50% در رابطه 3 به درصد متوسط خطاي 83/24% مي‌رسيم). مزيت روش پيشنهادي در اين مقاله براي تعيين حد آستانه شباهت، تعيين اين آستانه از روي ويژگي‌هاي آماري رنگي تصوير است كه آن را نسبت به تغييرات شرايط نوري و رنگي و بافتي تصاوير بيروني مقاوم مي‌كند و كاربر را از تنظيم الگوريتم به ازاي شرايط مختلف تصاوير بي‌نياز مي‌نمايد.

5. تحليل نتايج

تصاوير به دست آمده نشان مي‌دهد كيفيت روش پيشنهادي براي بخش‌بندي ابتدايي تصاوير مناسب است.به‌عنوان نمونه، در شكل 15 تصوير بخش‌بندي شده به كمك روش پيشنهادي بيشتر از تصوير بخش‌بندي شده به كمك روش عادي، به تصوير مرجع شبيه است.

الف

ب ج د

شكل 15) مقايسه الگوريتم‌هاي بخش‌بندي به روش k-means الف) تصوير اصلي ب) تصوير مرجع ج) تصوير حاصل از روش k-meansعادي د) تصوير حاصل از روش حذف تدريجي

يك ويژگي جالب توجه روش پيشنهادي در شكلهاي 5 و 6 ديده مي‌شود؛ در روش عادي، تعداد پيكسل‌ها روي نماينده‌ها تأثير مي‌گذارد. به همين دليل اگر در تصوير چند سايه مربوط به يك رنگ با تعداد پيكسل زياد موجود باشد (مثلاً بخش‌هاي مختلف آسمان يا چمن)، اين سايه‌ها به عنوان اشياء مختلف در نظر گرفته مي‌شوند. مثلاً در هر دو شكل 4 و 5 مي‌بينيد كه آسمان به بيش از يك بخش تقسيم شده است؛ در حالي كه انتظار داريم كل آسمان يك بخش در نظر گرفته شود. اين موضوع نه تنها باعث اشتباه در بخش‌بندي اشياء بزرگتر مي‌شود، بلكه به دليل تأثيرپذيري از تعداد پيكسل‌ها، گاهي باعث مي‌شود اشياء كوچك هم در تصوير بخش‌بندي شده نهايي حضور نداشته باشند. اين مشكل يكي از نقاط ضعف عمده روش k-meansبراي كاهش رنگ به عنوان پيش‌گام بخش‌بندي است؛ به ويژه وقتي تصاوير مورد بررسي از تصاوير بيروني باشند كه از نور محيط تأثير بسيار مي‌پذيرند و گاه يك شيء واحد را در قالب چند رنگ نزديك به هم نشان مي‌دهند.

در روش پيشنهادي، در هر مرحله اشيائي كه تعداد پيكسل‌هاي زياد (و حتي چند سايه رنگي) دارند به عنوان يك شيء واحد درنظر گرفته شده و حذف مي‌شوند و خوشه‌بندي مرحله بعد تنها بر پيكسل‌هاي باقيمانده متمركز مي‌شود؛ به همين دليل نه تنها سايه‌هاي يك رنگ به عنوان يك شيء واحد در نظر گرفته مي‌شوند، بلكه بخش‌هايي كه در روش عادي از بين مي‌روند (مانند اشياء كوچك)، در روش پيشنهادي خود را نشان مي‌دهند.

البته اين ويژگي روش پيشنهادي در مواردي باعث بروز خطا نيز مي‌شود. مثلاً در شكل 16 مي‌بينيد كه بخشي از ساختمان كه روي آن سايه افتاده است، رنگي نزديك به آسمان دارد. اين موضوع باعث بروز خطا در روش پيشنهادي نسبت به روش عادي شده است.


الف	ب	ج

شكل 16) الف) تصوير اصلي ب) روش عادي ج) روش پيشنهادي

مزيت ديگر اين روش دقت همگرايي و سرعت بيشتر آن نسبت به روش عادي است. همانگونه كه پيشتر گفته شد، تكرار الگوريتم خوشه‌بندي k-means تا جايي ادامه مي‌يابد كهحاصل‌جمع «مجموع فواصل نقاط هر دسته تا نماينده آن دسته»كمينه شود (رابطه 2 را ببينيد). اگر انتخاب مكان اوليه بردارهاي نماينده به درستي صورت نگيرد (كه در انتخاب تصادفي تنها به اقبال شما بستگي دارد)، حاصل‌جمع فوق يا به كمينه‌اي همگرا نمي‌شود يا به يك كمينه محلي همگرا خواهد شد كه طبعاً نتيجه مناسبي نخواهد داشت[47]. اين مشكل هنگام زياد بودن تعداد خوشه‌ها، بيشتر بروز مي‌كند؛ چون تعداد نماينده‌ها و به تبع آن احتمال واقع شدن تعدادي از نماينده‌ها در كمينه‌هاي محلي بيشتر مي‌شود. به همين لحاظ الگوريتمي كه از ابتدا تصوير را به 6 يا 9 رنگ تقسيم كند، در بسياري از مواقع به كمينه عمومي همگرا نخواهد شد (در پايگاه داده ما، در بيش از70% موارد اين مشكل ايجاد مي‌شود). به علاوه تكرارهاي زياد الگوريتم براي همگرا شدن به يك كمينه عمومي، زمان اجراي آن را بالا مي‌برد. در مقابل، روش پيشنهادي در هر مرحله تنها با سه بردار نماينده سروكار دارد؛ به همين لحاظ احتمال درگير شدن با كمينه‌هاي محلي و طولاني شدن زمان همگرايي آن ناچيز خواهد بود.در برآورد زماني کارايي الگوريتم که به کمک کامپيوتري با پردازنده پنتيوم Core i5 با فرکانس 2 گيگاهرتز و RAM چهار گيگابايتي روي پايگاه داده UIDS انجام شد، الگوريتم پيشنهادي در کمتر از 17 دقيقه خوشه‌هاي رنگي مناسب را در تصاوير ايجاد مي‌کند. اين در حالي است که در روش k-means در کمتر از 30% موارد همگرايي به کمينه عمومي در مرتبه اول اجراي الگوريتم به دست خواهد آمد و با احتساب تکرارهاي لازم براي همگرايي همه تصاوير، اين زمان بيش از 50 دقيقه خواهد بود. البته بايد اذعان داشت که در مواردي که روش k-means به کمينه عمومي همگرا مي‌شود، سرعت آن از روش پيشنهادي بيشتر است؛ چون ساختار مرحله به مرحله آن را ندارد. اما همانطور که ذکر شد، دقت الگوريتم پيشنهادي در تشخيص رنگ‌هاي صحيح از روش k-means بالاتر است.

نكته ديگري كه بايد در مورد روش پيشنهادي مدنظر قرار گيرد اين است كه اگر سه رنگ ابتدايي (در واقع محل تصادفي اوليه سه بردار نماينده) به اشتباه انتخاب شود، كل الگوريتم با شكست مواجه مي‌شود. البته اين يك اشكال ذاتي الگوريتم k-means است و در نسخه استاندارد اين روش نيز ديده مي‌شود.

استفاده از هرم تصاوير چنددقتي باعث بهبود قابل توجهي در نتايج مي‌شود؛ به گونه‌اي كه بدون استفاده از طبقات اين هرم خطاي بخش‌بندي پيكسلي حدود 6% افزايش مي‌يابد. شكل 17 نشان مي‌دهد با استفاده از هرم فوق، تغييرات نمودار هيستوگرام فاصله پيكسل‌هاي يك دسته از مركز آن دسته ملايم‌تر مي‌شود.به بيان ديگر با استفاده از اين هرم، رنگهاي نزديك با هم تركيب مي‌شوند و باعث يكنواخت شدن توزيع پيسكل‌هاي هم‌رنگ در يك دسته مي‌شوند. اين موضوع به نوبه خود سبب كاهش اشتباه الگوريتم بخش‌بندي در مواجهه با سايه‌هاي هم‌رنگ و نيز بافتهاي تصاوير بيروني خواهد شد. البته بايد به اين نكته توجه داشت كه با وجود اينكه محو كردن تصاوير با از بين بردن جزييات بافتي و تركيب سايه‌هاي رنگي به بخش‌بندي كمك مي‌كند، اما نكته كليدي الگوريتم پيشنهادي، محو كردن تصاوير نيست؛ چون در كنار مزاياي آن، اشياء كوچك در محوسازي از بين مي‌روند. استفاده از هرم تصاوير چنددقتي باعث به‌كارگيري همزمان تصاوير محوشده و تصاوير با وضوح بالا مي‌شود تا در كنار توجه به اشياء كوچك و جزييات بافتي در موقعيت مناسب، از مزاياي تصاوير محو شده نيز استفاده كند.

Compare2

شكل 17- مقايسه نمودار هيستوگرام فاصله‌هاي پيكسل‌هاي يك دسته تا مركز دسته در هرم تصاوير چنددقتي (تصوير بالا) و بدون استفاده از هرم تصاوير چنددقتي (تصوير پايين)

در پايان بايد به اين نکته توجه داشت که در [48] از آمارگان‌هاي مرتبه بالاتر نيز براي تشخيص پيکسل‌ها يتيم بهره برديم. اما روش تحليل هيستوگرام که شکل توزيع رنگ‌ها در خوشه‌ها را در نظر مي‌گيرد به مراتب ساده‌تر و کيفيت آن بالاتر است.

6. نتيجه‌گيري و پیشنهادات

در اين مقاله، مشكلات الگوريتم k-means براي كاهش رنگ تصاوير بيروني به هدف بخش‌بندي ابتدايي و تشخيص شيء در آنها بررسي و روشي براي حل اين مشكل پيشنهاد شد. در اين روش كه بر مبناي بستري متشكل از دو دقت متفاوت تصوير عمل مي‌كند، با حذف تدريجي خوشه‌هاي اشياء مهم در هر طبقه هرم، تمركز روش خوشه‌بندي بر بقيه اشياء افزايش مي‌يابد. در اين تحقيق، روشي براي تعيين حدود رنگ‌هاي مهم در هر مرحله پيشنهاد شد كه با استفاده از ويژگي‌هاي آماري خوشه‌هاي رنگي، وابستگي الگوريتم به شرايط تصاوير بيروني را به حداقل مي‌رساند.كارايي اين الگوريتم به كمك يك روش ارزيابي نظارت‌شده روي دو پايگاه داده از تصاوير بيروني بررسي شد. نتايج به‌دست آمده نشان مي‌دهد اين روش براي كاهش رنگ تصاوير بيروني به هدف بخش‌بندي ابتدايي از الگوريتمk-means عادي بهتر عمل مي‌كند.

با انجام اصلاحاتي روي روش پيشنهادي، مي‌توان به كيفيت بهتري دست يافت. مثلاًيكي از اشكالات به كارگيري هرم تصاوير چنددقتي اين است كه با اعمال فيلتر ملايم‌كننده روي تصوير، لبه‌هاي تصوير تغيير شكل و نيز تغيير رنگ مي‌دهند كه اين موضوع باعث مي‌شود لبه‌هاي تصوير به عنوان يك دسته رنگي جديد در نظر گرفته شوند. در شكلهاي 18-الف و 18-ب، يك تصوير بيروني و نسخه محو شده آن و در شكل 18-ج لبه‌هاي تغيير رنگ داده مشاهده مي‌شوند.

الف ب ج

شكل 18– الف) تصوير اصلي ب) تصوير محو شده ج) لبه‌هاي تغيير رنگ داده شده در اثر محو شدن

براي رفع اين مشكل، مي‌توان ابتدا لبه‌هاي تصوير را به دست آورد و از در نظر گرفتن پيكسل‌هاي نزديك به لبه‌ها به عنوان پيكسل يتيم اجتناب نمود؛ چون احتمالاً اين پيكسل‌ها همرنگ با زمينه هستند و به دليل استفاده از فيلترهاي ملايم‌كننده تغيير رنگ داده‌اند. ميزان نزديكي به لبه در روش بالا مي‌تواند با توجه به قوت لبه تعيين شود.

براي بهبود دقت بخش‌هاي ايجاد شده، بعد از به كار بردن روش مزبور يك مرحله ادغام نيز مي‌تواند انجام بپذيرد تا كلاسهاي ايجاد شده را در صورت لزوم بر حسب شباهتهاي رنگي و بافتي و شكلي و نيز پيوستگي پيكسلها ادغام كند و يا اشيائي كه تعداد پيكسلهاي آنها كم است (اشياء كوچك يا كم اهميت) را حذف كند. ايده‌هايي براي ادغام در[49] مطرح شده است.

نكته ديگر در مورد درصد استفاده شده در مراحل 2 و 3 الگوريتم پيشنهاد شده در اين تحقيق براي تعيين رنگ‌هايL و U (در اينجا 5%) است. واضح است هرچه اين درصد بزرگتر باشد، تعداد پيكسل‌هايي كه به مرحله بعد راه مي‌يابند بيشتر خواهد بود و اين موضوع احتمال تقسيم يك شيء واحد به چند بخش (over-segmentation) را افزايش مي‌دهد؛ اين در حالي است كه اگر درصد فوق خيلي كوچك باشد، رنگ‌هاي كمي به مرحله بعد راه مي‌يابند و احتمال از نظر دور ماندن بخش‌هاي كوچك (under-segmentation) بيشتر مي‌شود[40]. حتي اگر درصد فوق خيلي كوچك (مثلاً 1%) باشد، گاهي با بررسي هيستوگرام ته‌رنگ موفق به يافتن رنگ‌هاي U و L نمي‌شويم. به بيان ديگر، در هيستوگرام ته‌رنگ نمي‌توان رنگي يافت كه تعداد پيكسلهاي آن كمتر از 1% پيكسل‌هاي به رنگ µ باشد. نمونه‌اي از اين هيستوگرام را در شكل 19 مي‌بينيد.

$F:\Users\Administrator\Desktop\Fig-19.tif$

شكل 19–يك هيستوگرام ته‌رنگ «تخت»

چنين مي‌نمايد كه در اين خوشه تمام رنگ‌ها وجود دارند! در حالي كه اين طور نيست؛ در چنين خوشه‌اي پارامترهاي اشباع و روشنايي (S و V در فضاي HSV) مقاديري دارند كه تغيير ته‌رنگ در رنگ‌هاي آن خوشه تأثيري ندارد و به همين لحاظ در هيستوگرام ته‌رنگ تمام رنگ‌ها ديده مي‌شوند. مثلاً اگر روشنايي صفر باشد، پارامترهاي H‌ و S هر مقداري داشته باشند تفاوتي ندارد و آن رنگ، سياه ديده مي‌شود (نوار بالايي شكل 11 را ببينيد). بنابراين اگر هيستوگرام ته‌رنگ يك خوشه تخت باشد (رنگي كه شرايط رنگ‌هاي U و L را ارضا كند وجود نداشته باشد)، رنگ‌هاي آن خوشه همگي به يك رنگ ديده مي‌شوند و به همين لحاظ هيچ‌يك از آنها به عنوان رنگ يتيم در نظر گرفته نمي‌شوند. درهرحال تعيين بهينه مقدار درصد مذكور با توجه به شرايط تصوير مي‌تواند به كيفيت الگوريتم پيشنهادي كمك كند.

نكته ديگر اينكه همزمان با شفاف‌سازي تصوير (عبور به طبقات پاييني هرم تصاوير چنددقتي) ويژگي‌هاي بافتي خود را بهتر نشان مي‌دهند كه مي‌توان آنها را نيز براي بخش‌بندي ابتدايي تصوير مورد استفاده قرار داد. در واقع طول بردارهاي مربوط به ويژگي‌هاي پيكسل‌ها مي‌تواند با عبور به طبقات پايين هرم تصاوير چنددقتي افزايش يابد و شامل ويژگي‌هاي بافتي نيز شود.

هرچند در اين مقاله به هدف بخش‌بندي تصاوير بيروني الگوريتم خوشه‌بندي k-means سفارشي شد، اما روش پيشنهادي در اين مقاله مي‌تواند براي بهبود نتايج الگوريتم‌هاي ديگر خوشه‌بندي مانند [15, 21]نيز مورد استفاده قرار گيرد.

پس از بخش‌بندي ابتدايي بايد به كمك تكنيك‌هاي بازيابي تصاوير، ماهيت بخش‌ها تشخيص داده شود كه بخش تكميل‌كننده اين تحقيق خواهد بود [42, 50].

از نتايج اين پژوهش مي‌توان در بخش‌بندي و تشخيص صحيح اشياء در تصاوير بيروني و در کاربردهاي مختلفي از جمله طراحي روبات‌هاي خودکار، کنترل ترافيک، کاربردهاي امنيتي و نيز طراحي كامپيوترهاي پوشيدني براي كمك به افراد نابينا و كم‌بينا در مسيريابي بيرون منزل و کمک به آن‌ها در مواجهه با چالش‌هايي نظير عبور از خيابان و چهارراه بهره برد.

مراجع

[1]. W. W. Mayol, "Wearable Visual Robots," Ph.D, Computer Science, University of Oxford, 2004.

[2]. M. Everingham, B. T. Thomas, and T. Troscianko, "Wearable mobility aid for low vision using scene classification in a Markov random field model framework," International Journal of Human Computer Interaction, special issue on mediated reality, vol. 15, pp. 231-244, 2003.

[3]. R. C. González and R. E. Woods, Digital Image Processing: Pearson/Prentice Hall, 2008.

[4]. R. Manduchi, "Learning Outdoor Color Classification," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1713-1723, 2006.

[5]. J. Batlle, A. Casals, J. Freixenet, and J. Martí, "A review on strategies for recognizing natural objects in colour images of outdoor scenes," Image and Vision Computing, vol. 18(6-7), pp. 515-530, 2000.

[6]. Y.-W. Tai, J. Jia, and C.-K. Tang, "Soft Color Segmentation and Its Applications," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, pp. 1520-1537, 2007.

[7]. H. D. Cheng, X. H. Jiang, Y. Sun, and J. Wang, "Color Image Segmentation: Advances & Prospects," Pattern Recognition, vol. 34, pp. 2259–2281, 2001.

[8]. H. B. M'hadheb, A. Douik, M. M. Fendri, and M. Annabi, "Reduction of color variability in color image segmentation," in IEEE International Conference on Electronics, Circuits and Systems, 2006.

[9]. I. Ashdown, "Octree color quantization," in Radiosity: A Programmer's Perspective, ed: Wiley New York 1994.

[10] P. Heckbert, "Color image quantization for frame buffer display," SIGGRAPH Comput. Graph., vol. 16, pp. 297-307, 1982.

[11]. S. J. Wan, P. Prusinkiewicz, and S. K. M. Wong, "Variance based color image quantization for frame buffer display," Color Res. Applicat, vol. 15(1), pp. 52-58, 1990.

[12]. P. Scheunders, "A comparison of clustering algorithms applied to color image quantization," Pattern Recognition Letters, vol. 18, pp. 1379-1384, 1997.

[13]. N. Vlajic and H. C. Card, "Vector quantization of images using modified adaptive resonance algorithm for hierarchical clustering," IEEE Transactions on Neural Networks, vol. 12, pp. 1147-1162, 2001.

[14]. B. Fritzke, "A Growing Neural Gas Network Learns Topologies," Advances in Neural Information Processing Systems, 1995.

[15]. A. Baraldi and P. Blonda, "A survey of fuzzy clustering algorithms for pattern recognition. II," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 29, pp. 786-801, 1999.

[16]. G .A.Carpenter , S. Grossberg, N. Markuzon, J. H. Reynolds, and D. B. Rosen, "Fuzzy ARTMAP: A neural network architecture for incremental supervised learning of analog multidimensional maps," IEEE Transactions on Neural Networks and Learning Systems, vol. 3, pp. 698-713, 1992.

[17]. N. Papamarkos, A. E. Atsalakis, and C. P. Strouthopoulos, "Adaptive color reduction," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 32, pp. 44-56, 2002.

[18]. G. Cheng, J. Yang, K. Wang, and X. Wang, "Image Color Reduction Based on Self-Organizing Maps and Growing Self-Organizing Neural Networks," in The Sixth International Conference on Hybrid Intelligent Systems, 2006, p. 24.

[19]. K. Zagoris, N. Papamarkos, and I. Koustoudis, "Color Reduction Using the Combination of the Kohonen Self-Organized Feature Map and the Gustafson-Kessel Fuzzy Algorithm," in The 5th international conference on Machine Learning and Data Mining in Pattern Recognition, Leipzig, Germany, 2007, pp. 703-715.

[20]. A. Atsalakis, N. Papamarkos, and I. Andreadis, "On estimation of the number of image principal colors and color reduction through self-organized neural networks," International Journal of Imaging Systems and Technology, vol. 12, pp. 117-127, 2002.

[21]. J. Rasti, A. Monadjemi, and A. Vafaei, "Color reduction using a multi-stage Kohonen Self-Organizing Map with redundant features," Expert Systems with Applications, vol. 38, pp. 13188-13197, 2011.

[22]. S. Kiranyaz, S. Uhlmann, and M. Gabbouj, "Dominant Color Extraction Based on Dynamic Clustering by Multi-dimensional Particle Swarm Optimization," in The Seventh International Workshop on Content-Based Multimedia Indexing, 2009, pp. 181-188.

[23]. R. O. Duda, P. E. Hart, and D. G. Stork, Pattern classification: Wiley, 2001.

[24]. J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms: Kluwer Academic Publishers, 1981.

[25]. M. Y. Choong, W. L. Khong, W. Y. Kow, L. Angeline, and K. T. K. Teo, "Graph-Based Image Segmentation Using K-Means Clustering and Normalised Cuts," in The Fourth International Conference on Computational Intelligence, Communication Systems and Networks, 2012, pp. 307-312.

[26]. Y. C. Hu and M. G. Lee, "K-means-based color palette design scheme with the use of stable flags," Journal of Electronic Imaging, vol. 16, pp. 033003-1 to 033003-11, 2007.

[27]. S. N. Sulaiman and N. A. M. Isa, "Adaptive fuzzy-K-means clustering algorithm for image segmentation," IEEE Transactions on Consumer Electronics, vol. 56, pp. 2661-2668, 2010.

[28]. P. Ng and C.-M. Pun, "Skin Color Segmentation by Texture Feature Extraction and K-mean Clustering," in The Third International Conference on Computational Intelligence, Communication Systems and Networks, 2011, pp. 213-218.

[29]. R. Figueiredo, L. Schnitman, and F. d. Souza, "Using Neural Network and K-means Clustering for Image Segmentation in Outdoor Scenes," in The 2nd International Congress on University-Industry Cooperation, Perugia, Italy, 2007.

[30]. R. Huang, N. Sang, D. Luo, and Q. Tang, "Image Segmentation via Coherent Clustering in Lab Color Space," Pattern Recognition Letters, vol. 32, pp. 891-902, 2011.

[31]. جواد راستي، سيد اميرحسن منجمي و عباس وفايي، «كاهش رنگ تصاوير بيروني به هدف بخش‌بندي ابتدايي با استفاده از خوشه‌بندي سلسله‌مراتبي با حذف تدريجي در هرم گوسي»، ششمين کنفرانس ماشين بينايي و پردازش تصوير، دانشگاه اصفهان، آبان 1389.

[32]. A. Roy, S. K. Parui, D. Nandi, and U. Roy, "Color image segmentation using a semi-wrapped gaussian mixture model," in The 4th international conference on Pattern recognition and machine intelligence, Moscow, Russia, 2011, pp. 148-153.

[33]. M. Recky and F. Leberl, "Windows Detection Using K-means in CIE-Lab Color Space," in The 20th International Conference on Pattern Recognition, 2010, pp. 356-359.

[34]. S. Haykin, Neural Networks: A Comprehensive Foundation: Prentice Hall PTR, 1994.

[35] H. J. Aantonisse, "Image segmentation in pyramids," Computer Graphics and Image Processing vol. 19, pp. 367–383, 1982.

[36]. R. Marfil, L. Molina-Tanco, A. Bandera, J. A. Rodriguez, and F. Sandoval, "Pyramid segmentation algorithms revisited," Pattern Recognition, vol. 39, pp. 1430-1451, 2006.

[37]. G. Ramella and G. S. Baja, "Color Quantization by Multiresolution Analysis," in The 13th International Conference on Computer Analysis of Images and Patterns, Germany, 2009, pp. 525-532.

[38]. A. Atsalakis and N. Papamarkos, "Color reduction and estimation of the number of dominant colors by using a self-growing and self-organized neural gas," Engineering Applications of Artificial Intelligence, vol. 19, pp. 769-786, 2006.

[39]. S. Makrogiannis, G. Economou, and S. Fotopoulos, "A region dissimilarity relation that combines feature-space and spatial information for color image segmentation," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 35, pp. 44-53, 2005.

[40]. Y. J. Zhang, Advances in Image And Video Segmentation: IRM Press, 2006.

[41]. J. Rasti, A. Monadjemi, and A. Vafaei, "A Graph-Based Vision System for Automatic Object Detection in Outdoor Scenes," in The 22nd International DAAAM Symposium, Vienna, Austria, 2011, pp. 0167-0168.

[42]. A. Bosch, X. Munoz, and J. Freixenet, "Segmentation and description of natural outdoor scenes," Image and Vision Computing, vol. 25, pp. 727-740, 2007.

[43]. H. Zhang, J. E. Fritts, and S. A. Goldman, "A Co-Evaluation Framework for Improving Segmentation Evaluation," in SPIE Defense and Security Symposium - Signal Processing, Sensor Fusion, and Target Recognition XIV, 2005, pp. 420-430.

[44]. A. Alonso-Betanzos, B. Arcay-Varela, and A. Castro-Martínez, "Analysis and evaluation of hard and fuzzy clustering segmentation techniques in burned patient images," Image and Vision Computing, vol. 18, pp. 1045-1054, 2000.

[45]. D. Collins, W. A. Wright, and P. Greenway, "The sowerby image database," presented at the The 7th IEEE International Conference of Image Processing and Its Applications, Manchester, England, 1999.

[46]. X. He, R. S. Zemel, and M. Carreira-Perpi, "Multiscale conditional random fields for image labeling," in IEEE computer society conference on Computer vision and pattern recognition, Washington, D.C., USA, 2004, pp. 695-703.

[47]. A. Likas, M. Vlassis, and J. Verbeek, "The global k-means clustering algorithm," Pattern Recognition vol. 36, pp. 451-461, 2003.

[48]. جواد راستي، «ارائه يك روش بخش‌بندي مبتني بر الگوريتم‌هاي هوشمند به منظور تشخيص اشياء در تصاوير بيروني»، پايان‌نامه دکترا، گروه مهندسي کامپيوتر، دانشگاه اصفهان، 1391.

[49]. F. Y. Shih and S. Cheng, "Automatic seeded region growing for color image segmentation," Image and Vision Computing, vol. 23, pp. 877-886, 2005.

[50]. R. Datta, D. Joshi, J. Li, and J. Z. Wang, "Image retrieval: Ideas, influences, and trends of the new age," ACM Computing Surveys, vol. 40, pp. 1-60, 2008.

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية

شارک

عنوان URL للمقالة

بخش‌بندي تصاوير رنگي بيروني به هدف تشخيص اشياء به كمك هيستوگرام با دقت دوگانه

رایمگ