Research Areas : General
javad rasti
1
monadjemi monadjemi
2
abbas vafaei
3
Keywords:
Abstract :
[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 |
|
بخشبندي تصاوير رنگي بيروني به هدف تشخيص اشياء به كمك هيستوگرام با دقت دوگانه
جواد راستي*1 سيد اميرحسن منجمي** عباس وفایی***
* استادیار، دانشکده مهندسی پزشکی، دانشگاه اصفهان، اصفهان
** دانشیار، دانشکده مهندسی کامپیوتر، دانشگاه اصفهان، اصفهان
*** استادیار، دانشکده مهندسی کامپیوتر، دانشگاه اصفهان، اصفهان
تاريخ دريافت: 20/04/1391 تاريخ پذيرش: 30/11/1391
چکيده
يكي از مسايل مهم در پردازش خودكار تصاوير بيروني، نحوه بخشبندي اين تصاوير به هدف تشخيص شيء در آنها ميباشد. مشخصات خاص اين تصاوير از جمله تنوع رنگ، اثرات نوري متفاوت، وجود سايههاي رنگي، جزييات بافتي زياد و وجود اشياء كوچك و ناهمگن باعث ميشود مسأله بخشبندي تصاوير بيروني به ويژه بخشبندي رنگي با چالشهاي جدي مواجه شود. در تحقيقات قبليبراي خوشهبندي رنگي تصاوير بيروني به هدف بخشبندي ابتدايي، روشي مبتني بر الگوريتم خوشهبندي k-means در بستري با دقت چندگانه پيشنهاد شده بود.اين روش با استفاده از محو عمدي جزييات بافتي تصوير و حذف كلاسهاي محرز در تصاوير محو شده و سپس اضافه كردن كلاسها در تصاوير با دقت بالاتر، كارايي مناسبي براي بخشبندي ابتدايي اين تصاوير در مقايسه با روش k-means عادي نشان ميداد.در اين مقاله، يك روش تطبيقپذير با تصوير با استفاده از هيستوگرام حلقوي تهرنگ براي تشخيص كلاسهاي محرز در تصاوير محوشده در بستري با دقت دوگانه پيشنهاد گرديده است.كارايي اين الگوريتم به كمك يك روش ارزيابينظارتشده روي دو پايگاه داده از تصاوير بيروني بررسي شده كه حدود 20% كاهش خطاي پيكسلي در بخشبندي و نيز دقت و حدود 30% سرعت بيشتر در همگرايي الگوريتم خوشهبندي، نشانگر كيفيت بالاتر روش پيشنهادي نسبت به روش عادي است.
كليد واژگان: تصاوير بيروني، خوشهبندي، بخشبندي رنگي، دقت تصوير.
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 اين مطلب را به خوبي نشان ميدهد.
