Document Type : Research Article
Authors
Department of electrical engineering, Faculty of Engineering, Shahid Bahonar university of Kerman, Kerman, Iran
Abstract
Keywords
بازیابی تصویر مبتنی بر محتوا (CBIR) یکی از چالشهای مهم در بحث بازشناسی الگو و بینایی ماشین است که کاربردهای متنوعی در زمینههای سیستمهای چند رسانهای، پزشکی، جرم شناسی، هنر و سایر زمینهها دارد. تحقیقات در این زمینه از اوایل دهه 90 آغاز شده [1] و تا کنون، روشها و سیستمهای متفاوتی برای بازیابی تصویر بر اساس محتوا ارائه شده است.[i] CBIR شامل مجموعهای از روشها برای پردازش یک تصویر پرسوجو به منظور پیدا کردن تصاویر مشابه آن در یک پایگاه تصویر است. در این سامانه، ویژگیهای دیداری همچون رنگ، شکل و بافت نمایه سازی میشوند [2-4].
اساس کار غالب سامانههای بازیابی تصویر بر این است که تصاویر بر پایه مجموعهای از ویژگیهای دیداری سطح پایین3 آنها مثل شکل، بافت، رنگ و چیدمان رنگ4 ارائه و نمایهسازی شده و بازیابی تصاویر با مقایسه ویژگیهای تصویر پرس و جو با نمایههای تصاویر پایگاه و تعیین نزدیکترین تصاویر انجام میشود. از آنجا که تصاویر نزدیک در فضای ویژگی در نظر گرفته میشوند، بنابراین کیفیت ویژگیهای استخراجی نقش بسیار مهمی در دقت سامانه بازیابی ایفا میکند. تحقیقات نشان داده است که در یک سامانه عمومی بازیابی تصویر، استفاده تنها از یک نوع ویژگی کافی نیست و کارآیی ویژگیهای به کار رفته به حجم پایگاه تصویر و نوع تصاویر آن بستگی دارد [5].
موضوع مهم دیگر این است که عموماً کاربران هنگام پرس و جوی تصویر به ویژگیهای سطح پایین تصویر فکر نکرده و به دنبال ویژگیهای سطح بالا5 یا همان ویژگیهای معنایی6 هستند. در این موارد اغلب سامانههای بازیابی تصویر، عملکرد ضعیفی دارند. این ضعف به خاطر فاصلهای است که بین ویژگیهای دیداری سطح پایین و ویژگیهای معنایی سطح بالا وجود دارد و به شکاف معنایی7 مشهور است [4]. برای رفع این مشکل، محققان از روشهای متفاوتی استفاده میکنند. دستهای از این روشها در ارتباط با ویژگیهای سطح پایین عمل کرده و از روشهایی چون ترکیب ویژگیها، بهبود ویژگیها، انتخاب ویژگی و سایر روشها برای هر چه نزدیکتر شدن ویژگیهای دیداری به ویژگیهای معنایی استفاده میکنند.
بهبود ویژگی تاکنون به روشهای مختلف در سامانههای بازیابی تصویر به کار گرفته شده است [6-10] خصوصا بهبود ویژگی رنگ به راحتی قابل انجام است، اما بهبود ویژگی بافت مسالهای است که کمتر به آن پرداخته شده است. در تحقیق حاضر تطبیق موجک مادر به عنوان رویکردی جدید در بهبود استخراج ویژگی بافت معرفی شده است. در غالب تحقیقاتی که تاکنون گزارش شده، موجک مادر همواره ثابت در نظر گرفته میشود، چرا که تغییر آن به دلیل خواص ویژهای که باید همواره برقرار باشد (نظیر متعامد بودن) به راحتی امکان پذیر نیست. برای غلبه بر این مساله، در این تحقیق برای استخراج ویژگی بافت از موجک مادر پارامتری [11] استفاده شده است. استفاده از این موجک تاکنون در تصاویر گزارش نشده است. علاوه بر این، رویکرد جدید دیگر این تحقیق این است که دو موجک متفاوت به ردیفها و ستونهای تصاویر اعمال شده است که ضرایب مربوط به هر کدام از آنها با استفاده از الگوریتم گرانشی بهینهسازی شدهاند.
ما بر این باوریم که برای هر پایگاه داده، با توجه به گروههای معنایی که شامل میشود، باید ویژگیهای دیداری استخراج شده بهینه شوند. هم اکنون قریب به اتفاق سامانههای بازیابی تصویر، ویژگیها را با پارامترهای ثابت و از پیش تعیین شده استخراج میکنند، در حالی که چنانچه پارامترهای مربوط به روشهای استخراج ویژگی به صورت وفقی تنظیم شود، میتوان شکاف معنایی را تا حدی کاهش داد. بنابراین، در این مقاله از بهبود ویژگیهای بافت و رنگ برای افزایش دقت استفاده شده است. بهبود ویژگی رنگ با تنظیم بازههای چندی سازی و بهبود ویژگی بافت با تطبیق تبدیل موجک انجام گرفته است.
در این تحقیق برای تنظیم پارامترهای استخراج ویژگی بافت و رنگ، از الگوریتم جستجوی گرانشی استفاده شده است [12]. این الگوریتم از الگوریتمهای ابتکاری است که با الهام از قانون گرانش نیوتن ایجاد شده و در زمینههای مختلفی کاربرد پیدا کرده است، مانند طراحی فیلتر [13]، تعیین پارامترهای توربین هیدرولیکی [14]، انتخاب ویژگی [15- 16]، بهینهساز چند هدفه [17] و طبقهبندی [18]. در این مقاله از این الگوریتم برای تعیین پارامترهای سامانه بازیابی تصویر استفاده شده است.
ادامه این مقاله بدین نحو سازماندهی شده است: در بخش دوم، ارتقای ویژگی در سامانههای بازیابی تصویر توصیف میشود. بخش سوم به توصیف ویژگیهای دیداری استفاده شده در این تحقیق میپردازد. در بخش چهارم الگوریتم جستجوی گرانشی و در بخش پنجم روش پیشنهادی برای استخراج تطبیقی ویژگیها به کمک الگوریتم جستجوی گرانشی آورده شده است. نتایج آزمایشها و ارزیابی در بخش ششم آورده شده است. در بخش آخر جمعبندی مقاله ارائه شده است.
ساختار کلی سامانه بازیابی تصویر در شکل (1) به تصویر کشیده شده است. به طور کلی، سامانههای بازیابی تصویر در دو مرحله عمل میکنند. در مرحله اول، ویژگیهای دیداری تصاویر پایگاه به صورت خودکار استخراج شده، تصاویر با آنها نمایهسازی میشوند. در مرحله دوم پایگاه ویژگیهای دیداری برای یافتن نزدیکترین تصاویر به پرس و جو، جستجو میشود. در یک سامانه بازیابی تصویر، به یک زیر سامانه برای پردازش تصویر پرسوجو و استخراج ویژگیهای سطح پایین آن نیاز است.
پایگاه تصویر، شامل تصاویری است که بازیابی از میان آنها انجام میشود. ویژگیهای دیداری (یا سطح پایین) از تصاویر استخراج و در پایگاه ویژگیهای دیداری نگهداری میشوند. این سامانه شامل یک رابط گرافیکی یا واسط پرسوجوست که با استفاده از آن با کاربر ارتباط برقرار کرده و با او در تعامل است. زیر سامانه پردازش پرسوجو، ویژگیهای مناسب را از تصویر پرسوجو استخراج میکند. زیر سامانه اندازهگیری شباهت، شباهت بین بردار ویژگی تصویر پرسوجو و بردارهای ویژگی تصاویر پایگاه را محاسبه و سامانه نزدیکترین تصاویر به تصویر پرسوجو را پیدا میکند. این تصاویر از طریق رابط گرافیکی به کاربر ارائه میشوند. با توجه به ساختار و عملکرد سامانه بازیابی، مشخص است که کارایی آن به شدت تحت تاثیر ویژگیهای استخراجی از تصاویر است. در نتیجه، میتوان با استفاده از روشهای متدوال در بهبود کارایی ویژگیها، بهبود درخور توجهی در نتایج بازیابی حاصل کرد.
ویژگی |
استخراج |
نتایج بازیابی |
ویژگیهای دیداری
|
پایگاه تصویر |
پردازش پرسوجو |
کاربر |
واسط کاربر |
اندازهگیری شباهت |
شکل (1): ساختار سامانه بازیابی تصویر [5]
در سالهای اخیر برای ایجاد روشهایی کارآمد در بازیابی تصویر بر پایه محتویات آن تلاشهای زیادی شده است؛ خصوصا موضوع ارتقای کارایی ویژگیها که در سامانههای بازیابی تصویر به صورتهای مختلف انجام شده است. روشهای متدوال در بهبود کارایی ویژگیها شامل تطبیق ویژگیها [7]، بهبود ویژگیها [6] و گسسته سازی [10] آنهاست. این روشها تاکنون در مقالات متعدد استفاده شدهاند. در [9]، ویژگیها بافت و رنگ برای بازیابی تصویر به صورت تطبیقی وزندهی شدهاند و پس از وزندهی ویژگیها در بازخورد ربط، ویژگیهای دارای وزن کم حذف و ویژگیهای دارای وزن زیاد با جزییات بیشتری آورده شده است. در مرجع [7] ویژگی رنگ برای بهبود نتایج بازیابی تصاویر عام تطبیق داده شده است. برای چندی سازی ویژگی رنگ، از یک روش آستانه زنی با توجه به توزیع رنگ در تصویر استفاده شده است.
در [8] از الگوریتم وراثتی برای یافتن تبدیل موجک بهینه برای بهبود نتایج بازیابی تصاویر پزشکی استفاده شده و تپهای موجک مادر به دست آمده است. در روش پیشنهادی این مرجع، موجک مادر با پایگاههای داده خاص در تصاویر پزشکی، قابل تطبیق است، بدون اینکه مشخصات عمود بودن و سایر خواص تبدیل موجک خدشهدار شود. علاوه بر این، در تبدیل موجک، گشتاورهای نهایی[ii] با هر مقدار مورد نظر قابل دستیابی است. در [10] هیستوگرام دو بعدی فیلترهای گابور برای استخراج ویژگی استفاده و بهبود داده شده است؛ به این صورت که الگوریتم وراثتی برای جایگزینی ویژگیهای عددی در هیستوگرام با ویژگیهای ترتیبی به کار گرفته شده است.
تطبیق ویژگیها از رویکردهای مهم و پرکاربرد در بحث بهبود ویژگی است. در مساله تطبیق ویژگی، پارامترهای زیرسامانه استخراج ویژگی برای حداکثر کردن دقت بازیابی تنظیم میشود. بنابراین، مسایلی از این دسته را میتوان به صورت یک مساله بهینهسازی در نظر گرفت. یکی از روشهای مناسب برای حل مسایل بهینهسازی پیچیده در یک زمان قابل قبول، استفاده از الگوریتمهای ابتکاری است. در سامانههای بازیابی تصویر نیز تنظیم پارامترها در ارتباط با حجم زیاد تصاویر ، پیچیده و زمانبر است. به همین علت، دیده میشود که در بعضی از تحقیقات انجام شده، از الگوریتمهای ابتکاری برای تنظیم تطبیقی پارامترها در ارتباط با تصاویر پایگاه تصویر استفاده میشود [10]. در این مقاله، الگوریتم جستجوی گرانشی که یکی از الگوریتمهای ابتکاری کارامد و جدید است، برای بهبود ویژگی به خدمت گرفته شده است. الگوریتم جستجوی گرانشی، پارامترهای زیرسامانه استخراج ویژگی را با هدف حداکثر کردن دقت و کارایی سامانه در بازیابی تصاویر آموزشی به صورت تطبیقی تنظیم میکند. جزییات مربوط به ویژگیهای پیشنهاد شده در ادامه آورده شده است.
دو نوع ویژگی مهم که از تصاویر استخراج میشوند ویژگیهای حوزه مکان و حوزه فرکانس هستند. از ویژگیهای متداول حوزه مکان، ویژگی رنگ است. ویژگیهای حوزه فرکانس نیز، در استخراج ویژگی بافت کاربرد زیادی دارند. یکی از ابزارهای متداول برای استخراج ویژگیهای فرکانسی، تبدیل موجک است که در سامانههای بازیابی تصویر به وفور استفاده میشود [8، 19-22] خصوصا موجک دوبچی که از موجکهای متداول در بحث بازشناسی الگوست و در سامانههای مختلف بازیابی برای استخراج ویژگی به کار گرفته شده است. برای مثال، در سامانه SIMPLIcity[23] از موجک دوبچی برای استخراج ویژگیهای بافت استفاده شده است. همچنین، در مرجع [24] از موجک دوبچی برای محاسبه هیستوگرام در هر کدام از زیر باندها و استخراج ویژگی بافت استفاده شده است.
در کلیه سامانههای بازیابی تصویر که تاکنون از موجک مادر در استخراج ویژگی بافت استفاده کردهاند، یک موجک مادر ثابت به کار گرفته شده است، اما در این تحقیق، در یک رویکرد جدید، پارامترهای موجک مادر برای افزایش دقت سامانه بازیابی بهینهسازی شدهاند. طبق آخرین اطلاعات ما، تطبیق موجک مادر در سامانههای بازیابی تصویر تنها در [8] گزارش شده است؛ با این تفاوت که در [8] تپهای موجک مادر تطبیق داده شدهاند، در حالی که در این تحقیق از تبدیل موجک پارامتری استفاده شده است. استفاده از تبدیل موجک پارامتری برای استخراج ویژگی بافت تصاویر تاکنون در هیچ مرجعی گزارش نشده است. در این مقاله از دو نوع ویژگی برای نمایه سازی تصویر استفاده شده است. ویژگیهای پیاده سازی شده عبارتند از: هیستوگرام رنگ به نمایندگی از ویژگی رنگ و تبدیل موجک به نمایندگی از ویژگی بافت. شرح هر کدام در ادامه آورده شده است.
3-1- هیستوگرام رنگ
رنگ ویژگیای است که اغلب محققان در بازیابی تصویر از آن استفاده کردهاند و در موارد متعدد هیستوگرام رنگ به عنوان اصلیترین ویژگی در بازیابی مورد توجه بوده است. فوایدی همچون پایداری، مؤثر بودن، سادگی پیاده سازی، سادگی محاسباتی و حجم پایین بردار حاصل برای نمایه سازی، استفاده از هیستوگرام رنگ را توجیه میکند[52-26].
فضای رنگ RGB1 با سیستم بینایی انسان و روشی که انسان تصویر را درک میکند، همخوانی ندارد و برای نمایش تصویر توسط مانیتور و تلویزیون مناسب است. در این فضا تفاوت دو نقطه با توجه به مختصاتشان، متناسب با درک انسان نیست و فاصله اقلیدسی، تفاوت بین دو رنگ را به شکلی که برای انسان معنادار باشد، بیان نمی کند. در این تحقیق از فضای رنگ HSV استفاده شده است. از این فضای رنگ در تحقیقات مشابه به دفعات استفاده شده است [5، 25-26]. در این تحقیق، برای تشکیل هیستوگرام رنگ، فضای HSV به طور خطی کوانتیزه میشود. در این فضا بنا بر اهمیتی که مؤلفه H نسبت به سایر مؤلفهها دارد، این مؤلفه به هشت بازه و دو مؤلفه دیگر هر کدام به چهار بازه کوانتیزه میشوند. بنابراین، فضای رنگ به 8×4×4=128 بازه چندی میشود. بعد از چندی کردن رنگ نقاط یک تصویر، هیستوگرام رنگ آن با شمردن نقاطی که در هر بازه قرار میگیرند محاسبه میشود. برای حل مسأله تفاوت اندازه تصاویر، هیستوگرام رنگ به تعداد کل نقاط آن تصویر نرمالیزه میشود. بردار حاصل از نمایه سازی هر تصویر با استفاده از ویژگی رنگ، 128 بعدی است.
سطوح چندی سازی از مواردی است که در هیستوگرام رنگ نیاز به تنظیم آن وجود دارد. چندی کردن میتواند به صورت یکنواخت صورت بگیرد، اما با تنظیم مناسب سطوح چندی سازی، ویژگی هیستوگرام رنگ دقت بیشتری خواهد داشت. علت این امر این است که هر بازه از مؤلفههای رنگ دارای حساسیت و اهمیت متفاوتی است و این نکته در چندی کردن غیر یکنواخت، با تخصیص بازههای کوچکتر به محلهای با اهمیت تر، در نظر گرفته میشود؛ ضمنا از آنجا که اهمیت هر کدام از بازهها در هر نمونه از تصاویر متفاوت است، با تنظیم تطبیقی این بازهها با توجه به تصاویر موجود در سامانه، دقت ویژگی رنگ بیشتر میشود.
3-2- تبدیل چند دقتی
از ابزارهای کارآمد برای تحلیل اطلاعات محتوای تصویر نمایش برای دقتی است، خصوصا تبدیل موجک به وفور برای پرداش چند دقتی تصاویر استفاده میشود. تبدیل موجک گسسته سیگنال x با عبور دادن آن از مجموعهای از فیلترهای پایین گذر و بالا گذر ، به دست میآید [27-29]. در مورد موجکهای ارتوگونال، فیلتر با رابطه ، از فیلتر قابل استخراج است. تحلیل چند دقتی توسط فیلترهای فوق با توابع مقیاس و موجک متناظر است. در تحلیل چند دقتی،[iii] MRA، فیلترهای و با توابع مقیاس و موجک به صورت روابط 1 و 2 مرتبط هستند [27-29].
(1) |
|
(2) |
بنابراین، با توجه به این روابط، تبدیل موجک گسسته به طور کامل توسط فیلتر توصیف می شود. این فیلتر باید ویژگیهای معین مربوط به موجک متعامد را دارا باشد [27-29]. یک موجک متعامد مجموعهای از خانواده توابع است که با مقیاس[iv] و حرکت[v] دادن تابع به دست می آید. تجزیه سیگنال با استفاده از تبدیل چند دقتی متعامد را نمایش موجک سیگنال می نامند [27].
در سیگنالهای دو بعدی، تبدیل موجک دو بعدی به ستونها و ردیفهای سیگنال به صورت جداگانه اعمال میشود. ضرایب تجزیه تصویر با الگوریتم مالت با استفاده از فیلترهای و مطابق شکل 2 محاسبه میشود [28]. در تبدیل دو بعدی، فیلترهای آنالیز ابتدا به ستونها و سپس به ردیفها اعمال میشود. در این تحقیق، دو فیلتر جداگانه به ستونها و ردیفها اعمال میشوند، به این صورت که فیلترهای و به ستونها و فیلترهای و به ردیفها اعمال میشوند.
Columns |
|
|
Rows |
|
|
Rows |
|
|
Image |
شکل (2): تبدیل موجک دو بعدی
ویژگیهای متداولی که از هر کدام از زیرباندهای تبدیل موجک استخراج میشوند، میانگین، انحراف معیار، انرژی و آنتروپی هستند که به ترتیب با استفاده از روابط 3 تا 6 محاسبه می شوند. در این روابط، ضرایب موجک و و بعد هر کدام از زیرباندها هستند.
(3) |
|
(4) |
|
(5) |
|
(6) |
- موجک پارامتری
تبدیل موجک گسسته، سیگنال را به مجموعهای از توابع پایه تصویر میکند. این توابع نسخه های مقیاس شده و انتقال یافته از موجک مادر هستند. تعدادی از موجک های مادر معروف، موجک های هاآر و دوبچی هستند. موجکهای مادر دقتهای مختلفی در استخراج جزییات سیگنال دارند. بنابراین، کارایی مختلفی در تجزیه و استخراج اطلاعات فرکانسی سیگنالهای مختلف دارند. انتخاب موجک مادر با توجه به مشخصات سیگنال میتواند کارایی تبدیل چند دقتی را بالا ببرد.
در این تحقیق، یک موجک مادر پارامتری برای بهبود کارایی سامانه بازیابی تصویر به کار گرفته شده است. غالب موجکهای پرکاربرد درای ضرایب ثابتی از هستند، در حالی که ضرایب این موجک پارامتری و قابل تنظیم هستند [11، 30]. موجک مادر پارامتری برای مواردی مثل دستهبندی سیگنالها [30-31]، فشردهسازی سیگنال [32] و جداسازی کور سیگنال [33] استفاده شده است. در فیلترهای پارامتری به طول ، به میزان پارامتر آزاد وجود دارد که تغییر آنها تعامد موجک را خدشهدار نمیکند. با افزایش ، دقت تبدیل چند دقتی بهبود مییابد، اما در ازای آن، حجم محاسبات زیاد میشود. در این تحقیق، برابر با شش و با دو پارامتر آزاد و انتخاب شدهاند. فیلتر در روابط (7) تا (9) داده شده است [30].
(7) |
|
(8) |
|
(9) |
استفاده از این موجک تا کنون در تصاویر گزارش نشده است. در این تحقیق از این موجک برای استخراج ویژگی بافت تصاویر استفاده شده است. علاوه بر این، رویکرد جدید دیگر این تحقیق این است که دو موجک متفاوت به ردیفها و ستونهای تصاویر اعمال شده است که ضرایب مربوط به هر کدام از آنها با استفاده از الگوریتم گرانشی بهینهسازی شدهاند. در بخش بعد این الگوریتم مرور شده است.
در الگوریتم جستجوی گرانشی یا GSA [vi] [12]، بهینهیابی به کمک طرح قوانین گرانشی و حرکت در یک سیستم مصنوعی با زمان گسسته انجام ﻣﯽشود. این الگوریتم تا کنون در مسایل مختلف بهینه سازی استفاده شده است [35-37]. در GSA، محیط شامل یک دستگاه مختصات چند بعدی در فضای تعریف مسأله است. طبق قانون گرانش، هر جسم، محل و وضعیت سایر اجرام را از طریق قانون جاذبه گرانشی درک ﻣﯽکند. هر نقطه از فضا یک جواب مسأله است. عاملهای جستجو کننده مجموعهای از اجسام دارای جرم هستند و هر جسم چهار مشخصه دارد: الف- موقعیت جسم؛ ب- جرم گرانشی فعال؛ ج- جرم گرانشی غیر فعال و د- جرم اینرسی. مقدار اجرام گرانشی و اینرسی، با توجه به برازندگی هر جسم تعیین ﻣﯽشوند.
در این سیستم قانون گرانش و قوانین حرکت حاکمند. در این محیط، طبق قانون گرانش هر جسم در سیستم مصنوعی، تمام اجسام دیگر را به سمت خود جذب ﻣﯽکند. مقدار این نیرو متناسب است با حاصلضرب جرم گرانشی فعال آن جسم در جرم گرانشی غیر فعال جسم مقابل و عکس فاصله آن دو جسم. طبق قوانین حرکت نیز، سرعت فعلی هر جسم برابر است با مجموع ضریبی از سرعت قبلی و تغییر سرعت آن و تغییر سرعت یا شتاب هر جسم برابر است با نیروی وارد بر آن تقسیم بر جرم اینرسی.
سیستم به صورت مجموعهای از جسم تعریف میشود. موقعیت هر جسم، نقطهای از فضاست که جوابی از مسأله است. موقعیت بعد از جسم با نشان داده شده است (رابطه (6)). برای مکان یابی اجسام، فرض ﻣﯽشود که در فضای جستجو، تمام ابعاد دارای گستردگی یکسانی هستند. در صورتی که شرط فوق برقرار نباشد، با مقیاس کردن[vii] شرط فوق برقرار ﻣﯽشود.
(10) |
در این سیستم، در زمان به جرم از سوی جرم در برای بعد نیرویی به اندازه وارد ﻣﯽشود. مقدار این نیرو به صورت رابطه (11) محاسبه ﻣﯽشود. و به ترتیب جرم گرانشی فعال جسم و جرم گرانشی غیر فعال جسم هستند، ثابت گرانش در زمان و فاصله بین دو جسم و هستند. برای تعیین فاصله بین اجسام مطابق رابطه (12) از فاصله اقلیدسی (نرم 2) استفاده شده است. یک عدد بسیار کوچک است و برابر یک در نظر گرفته شده است [12].
(11) |
|
(12) |
نیروی وارد بر جسم در برای بعد در زمان ( )، مطابق رابطه (13) برابر مجموع ضریبهای تصادفی نیروهایی است که جسم برتر بر آن وارد ﻣﯽکنند. در این رابطه یک عدد تصادفی با توزیع یکنواخت در بازه [1-0] است. در این رابطه برای بهبود دادن قدرت کشف الگوریتم، تنها به مجموعه شامل عضو برتر، اجازه تاثیرگذاری بر سایر اعضا داده میشود. مقدار به صورت متغیر با زمان تعریف ﻣﯽشود. به این صورت که در زمان شروع تمام اجسام روی یکدیگر تاثیر ﻣﯽگذارند و با گذشت زمان از تعداد اعضا تاثیر گذار بر جمعیت، به صورت یک نسبت خطی کم ﻣﯽشود تا اینکه در انتها تنها 2 درصد از بهترینهای جمعیت بر سایر اعضا نیرو وارد ﻣﯽکنند [12].
(13) |
طبق قانون دوم نیوتن، هر جسم در برای بعد ام شتابی ﻣﯽگیرد که متناسب است با نیروی وارد بر آن جسم در برای ام، بخش بر جرم اینرسی آن که در رابطه (14) بیان شده است. شتاب جسم در برای بعد در زمان با و جرم اینرسی جسم با نشان داده شده است [12].
(14) |
سرعت بعدی هر جسم برابر مجموع ضریبی از سرعت فعلی جسم و شتاب جسم تعریف ﻣﯽشود (رابطه (15)). موقعیت جدید بعد از جسم طی رابطه (16) محاسبه ﻣﯽشود. سرعت بعد جسم در زمان است. در این روابط یک عدد تصادفی با توزیع یکنواخت در بازه [1-0] است که برای حفظ خصوصیت تصادفی بودن جستجو استفاده شدهاست [12].
(15) |
|
(16) |
برای تنظیم ثابت گرانش، از یک مقدار اولیه شروع کرده، با گذشت زمان مقدار آن کاهش داده ﻣﯽشود. ثابت گرانش طبق رابطه (17)، تابعی از ثابت گرانش اولیه و زمان است. این موضوع در دنیای واقعی نیز صدق ﻣﯽکند و ثابت گرانش با آهنگ بسیار کندی در طول زمان کوچک ﻣﯽشود.
(17) |
در این الگوریتم، اجرام گرانشی و اینرسی مطابق رابطه (18)، برابر در نظر گرفته شده، برای تنظیم آنها، از مقدار تابع هدف اجسام با استفاده از رابطه (19) استفاده ﻣﯽشود. در این روابط، بیانگر میزان برازندگی جسم و بدترین جواب در زمان است و به اجسام با شایستگی بهتر، جرم بیشتری نسبت داده شود [12].
(18) |
|
(19) |
در ابتدای تشکیل سیستم، هر جسم به صورت تصادفی در یک نقطه از فضا قرار ﻣﯽگیرد که جوابی از مسأله است. در هر لحظه از زمان، اجسام ارزیابی شده، تغییر مکان هر جسم پس از محاسبه روابط (11) الی (16) محاسبه شده، در زمان بعد جسم در آن موقعیت قرار ﻣﯽگیرد. جرمهای گرانشی، جرم اینرسی و ثابت گرانش نیوتن در هر مرحله طبق روابط (18) و (19) بهروز رسانی ﻣﯽشوند. شرط توقف میتواند پس از تعداد تکرارهای مشخص تعیین شود. شبه کد الگوریتم در شکل (3) آورده شده است [12].
1- تعیین محیط سیستم و مقدار دهی اولیه. 2- جایابی اولیه اجسام. 3- ارزیابی اجسام. 4- به روز رسانی مقادیر ، ، 5 - محاسبه جرم هر عامل ( ). 6- محاسبه نیروی وارد بر هر جسم. 7- محاسبه شتاب و سرعت هر جسم. 8- به روز رسانی موقعیت اجسام. 9- در صورتی که شرط توقف برآورده نشده، به مرحله سوم بر ﻣﯽگردیم. در غیر این صورت بهترین جواب دیده شده تاکنون به خروجی داده شده و الگوریتم متوقف ﻣﯽشود. |
شکل (3): شبه کد مربوط به الگوریتم جستجوی گرانشی
در این تحقیق، الگوریتم جستجوی گرانشی که یکی از الگوریتمهای ابتکاری کارامد و جدید است، برای بهبود ویژگی به خدمت گرفته شده است. برای این کار، تنظیم پارامترهای استخراج ویژگی به صورت یک مساله بهینهسازی شبیهسازی و تابع هدف متناسب با دقت بازیابی در نظر گرفته شده است. این تابع به کمک الگوریتم گرانشی حداکثر میشود. روش کار در شکل (4) آورده شده است. با توجه به شکل (4)، الگوریتم جستجوی گرانشی، پارامترهای زیرسامانه استخراج ویژگی را با هدف حداکثر کردن دقت و کارایی سامانه در بازیابی تصاویر آموزشی به صورت تطبیقی تنظیم میکند. به این صورت که در هر بار ارزیابی، پارامترهای بخش استخراج ویژگی توسط عاملهای هوشمند الگوریتم تنظیم و بازیابی به کمک ویژگیهای استخراجی انجام میشود. دقت بازیابی برای ارزیابی به الگوریتم برگردانده و این کار در چند مرحله تکرار میشود. پارامترهای استخراج ویژگی شامل تعدادی پارامتر مربوط به استخراج ویژگی بافت و تعدادی پارامتر مربوط به ویژگی رنگ هستند. تابع هدف در این الگوریتم به گونهای تعریف شده است که با حداکثر کردن آن، دقت سامانه بازیابی بالا برود. پارامترهای مربوط به ویژگیهای رنگ و بافت و تابع هدف تعریف شده، در ادامه توضیح داده شدهاند.
تصاویر آموزشی |
استخراج ویژگی |
سامانه بازیابی تصویر |
الگوریتم جستجوی گرانشی
|
دقت بازیابی |
شکل (4): بهبود پارامترهای بخش استخراج ویژگی به کمک الگوریتم ابتکاری برای افزایش دقت بازیابی در یک سامانه بازیابی تصویر
پارامترهای ویژگی بافت:
در بخش استخراج ویژگی بافت، موجک مادر برای حداکثر کردن دقت بازیابی بهینه شده است. در ساختن موجک مادر از فیلترهای پارامتری متعامد قابل تنظیم استفاده شده است. پارامترها به کمک الگوریتم جستجوی گرانشی با هدف افزایش دقت بازیابی بهینه شدهاند. فیلترهای و در ستونها و فیلترهای و در ردیفهای تصویر استفاده شدهاند. این فیلترها، پارامتری بوده و با سیگنالها تطبیق داده شدهاند. تعداد تپ های فیلتر ( ) برابر 6 در نظر گرفته شده است. لذا هر فیلتر دارای دو پارامتر قابل تنظیم است. پس در کل 4 پارامتر قابل تنظیم وجود دارد. فیلترهای با استفاده از فیلترهای محاسبه میشوند. در تبدیل موجک دو بعدی شکل 3، دو پارامتر ، مر بوط به فیلتر و دو پارامتر ، مربوط به فیلتر با استفاده از الگوریتم جستجوی گرانشی بهینه شدهاند.
پارامترهای ویژگی رنگ:
برای استخراج ویژگی رنگ، از هیستوگرام رنگ در فضای رنگ HSV استفاده شده است. برای محاسبه هیستوگرام، فضای رنگ به بینهایی چندی سازی شده است. در این تحقیق هر کدام از ابعاد H، S و V به ترتیب به 8، 4 و 4 سطح چندی شدهاند. بنابراین 128 سطح در فضای رنگ ایجاد میشود. نمادهای Sh1، Sh2، … و Sh8 برای نمایش سطوح H، نمادهای Ss1، Ss2، Ss3 و Ss4 برای نمایش سطوح S و نمادهای Sv1، Sv2، Sv3 و Sv4 برای نمایش سطوح V استفاده شده اند. سطوح چندیسازی دارای مقادیری بین صفر و یک هستند و به صورت تطبیقی به کمک الگوریتم جستجوی گرانشی تعیین شدهاند. در هر بعد، مقدار سطوح چندیسازی با تقسیم بر مجموع آنها نرمالیزه شدهاند.
نمایش اجسام در الگوریتم گرانشی:
هر جسم شامل تعدادی پارامتر مربوط به استخراج ویژگی است. با چهار پارامتر بافت و 16 پارامتر رنگ، در مجموع هر جسم دارای 20 بعد است. نمایش هر جسم در شکل (5) آورده شده است. برای ارزیابی هر عضو جمعیت، پارامترهای پیشنهادی مربوط به آن در بخش استخراج ویژگی تنظیم شده، دقت سامانه بازیابی با استفاده از ویژگیهای استخراجی محاسبه میشود. عضو دارای دقت بازیابی بالاتر، تابع شایستگی بالاتری داشته جرم بیشتری به آن نسبت داده میشود. در نتیجه سایر اجسام را بیشتر به سمت خود دعوت میکند.
Sh1 |
Sh2 |
… |
Sh8 |
||||
Ss1 |
Ss2 |
Ss3 |
Ss4 |
Sv1 |
Sv2 |
Sv3 |
Sv4 |
شکل (5): نمایش اجسام
معیار ارزیابی و تابع هدف:
برای ارزیابی کارایی روش پیشنهادی از معیار دقت استفاده شده است. معیار دقت از رایجترین معیارهای ارزیابی در بازیابی تصویر است که با استفاده از رابطه (20) به صورت نسبت تعداد تصاویر مرتبط به تعداد تصاویر بازیابی شده محاسبه میشود [4]. معیار دقت کارایی سامانه بازیابی را به خوبی نشان میدهد، در نتیجه، میتوان از آن برای تعریف یک تابع هدف مناسب استفاده کرد.
(20) |
در این تحقیق، تابع هدف در الگوریتم جستجوی گرانشی، با استفاده از معیار دقت به صورت رابطه (21) محاسبه شده است. در این رابطه تعداد تصاویر مرتبط با نمایش داده شده است و برابر است با دقت بازیابی وقتی تعداد تصاویر برگردانده شده برابر است. طبق این تعریف، هر جسم که میانگین دقت بازیابی بالاتری به دست بدهد، تابع شایستگی بیشتر و در نتیجه جرم بیشتری به آن تخصیص داده میشود و در تکرار بعدی الگوریتم، روی سایر اجسام تاثیر بیشتری میگذارد.
(21) |
برای ارزیابی روش پیشنهادی، تطبیق ویژگی بافت و رنگ در تصاویر و تاثیر آن در افزایش دقت بازیابی سنجیده شده است. در کلیه آزمایشها، در پیاده سازی الگوریتم جستجوی گرانشی تعداد اجرام برابر 50 و تعداد تکرارها برابر 20 در نظر گرفته شده است. برای ثابت گرانش از رابطه 22 استفاده شده است. در این رابطه، ثابت گرانش اولیه برابر یک، برابر 20 و کل تکرارهای الگوریتم و برابر با 20 است.
(22) |
به منظور ارزیابی، روش پیشنهادی در بخش پنجم برای تنظیم تطبیقی پارامترها به کار گرفته شده و نتایج با سامانه متداول در بازیابی مقایسه شده است. سامانه مطابق شکل (1) در نظر گرفته شده است. در بخش اندازه گیری شباهت شکل (1)، به منظور اندازهگیری شباهت بین دو بردار ویژگی از تابع شباهت رابطه (23) که به معیار معروف است، استفاده شده است. در رابطه (23)، بیانگر طول بردار ویژگی و و به ترتیب بیانگر بردار ویژگی تصویر ام و ام هستند. بیانگر مولفه ام از بردار ویژگی است.
(23) |
تابع هدف در الگوریتم جستجوی گرانشی، با استفاده از معیار دقت به صورت رابطه (21) محاسبه شده است.
6-1- معیار ارزیابی
برای ارزیابی کارایی روش پیشنهادی از معیار دقت مطابق رابطه (20) استفاده شده است. معیارهای دقت و فراخوانی[viii]از رایجترین معیارهای ارزیابی در بازیابی تصویر هستند. در این تحقیق، از آنجا که تعداد تصاویر برگردانده شده و تعداد تصاویر در هر گروه برابر است، مقادیر دقت و فراخوانی یکسان هستند. لذا در آزمایشها تنها نمودار دقت ارائه شده است. برای تشکیل گراف دقت برای هر یک از فواصل، به این نحو عمل میشود که به نوبت هر یک از تصاویر پایگاه به عنوان تصویر پرس و جو انتخاب شده و بازیابی تصویر از بین سایر تصاویر انجام میشود. در هر عمل بازیابی، برای تصاویر بازیابی شده رتبه تعیین میشوند و معیار دقت محاسبه میشود. در نهایت میانگین این معیارها برای تمام تصویر پرس و جو محاسبه شده و به عنوان معیار نهایی برای مقایسه در نظر گرفته میشود.
6-2- پایگاه تصویر
در این آزمون، از یک پایگاه شامل 1000 تصویر استفاده شده است. فرض شده است که گروه معنایی هر تصویر در پایگاه تصویر مشخص و از پیش تعیین شدهاند. این پایگاه از 10 گروه هر کدام با 100 تصویر تشکیل شده است. تمام تصاویر متعلق به یک گروه معنایی دارای ویژگی معنایی واحد هستند، اگرچه ممکن است ویژگیهای سطح پایین آنها متفاوت باشند. انتخاب گروهها بر اساس ویژگی معنایی آنهاست. تصاویر این پایگاه در ابعاد 256×384 یا 384×256 و به فرمت JPEG هستند. این تصاویر از پایگاه تصویر کورلو از مرجع [23] انتخاب شدهاند. گروههای معنایی استفاده شده عبارتند از: مردم، شیرها، ساختمانها، اتوبوسها، داخل خانه، فیلها، گلها، اسبها، کوهستان و غذاها. گروههای مردم، ساختمانها، کوهستان و غذاها دارای تنوع بسیار در ویژگیهای سطح پایین هستند، در حالی که گروههای شیرها، فیلها و اسبها ویژگیهای سطح پایین نزدیک به هم دارند.
6-3- آزمایشها
در این قسمت تاثیر تنظیم تطبیقی پارامترهای بخش استخراج ویژگی ارزیابی شده است. ویژگی هیستوگرام رنگ با 128 رنگ استخراج شده است. برای استخراج ویژگی بافت نیز تصویر با استفاده از تبدیل موجک به چهار سطح فیلتر شده و پس از استخراج چهار ویژگی (روابط (3) تا (6)) از هر زیرباند، شانزده ویژگی بافت به دست آمده است. لذا مجموعا 144 ویژگی در دست است.
سه آزمایش مجزا بررسی شده است: الف) بهینهسازی پارامترهای ویژگی رنگ شامل سطوح چندیسازی؛ ب) بهینهسازی پارامترهای ویژگی بافت شامل پارامترهای موجک مادر در تبدیل موجک پارامتری و ج) بهینهسازی پارامترهای هر دو ویژگی رنگ و بافت به صورت همزمان با یکدیگر. برای مقایسه، از سامانه متداول CBIR با ویژگی هیستوگرام رنگ 128 بعدی با سطوح چندیسازی یکنواخت و ویژگی بافت با استخراج 16 ویژگی از تبدیل موجک با موجک مادر دوبچی استفاده شده است. آموزش الگوریتم با تعداد 20 درصد از تصاویر پایگاه انجام شده است که به صورت تصادفی انتخاب شدهاند.
پس از آموزش الگوریتم، نتایج گراف دقت روی کل تصاویر پایگاه با استفاده از پارامترهای تنظیم شده محاسبه و در شکل (6) به تصویر کشیده شده است. مقایسه گرافها نشان میدهد که با تنظیم پارامترها، دقت بیشتری نسبت به سامانه متداول بازیابی تصویر به دست میآید. همچنین مشخص است که بهینهسازی ویژگی رنگ مؤثرتر از بهینهسازی ویژگی بافت است، در حالی که بهینهسازی توام هر دو آنها نتایج بهتری به دست میدهد.
در روش پیشنهادی، ویژگیهای بافت و رنگ با سیگنال تطبیق داده شدهاند. در نتیجه نتایج بهتری حاصل شده است. علت این بهبود این است که به خصوصیات سیگنال دو بعدی تصاویر توجه شده است؛ خصوصا که در ویژگی بافت، خصوصیات فرکانسی در ستونها و ردیفهای تصویر به صورت جداگانه لحاظ شده است. تطبیق بازه های کوانتیزه در ویژگی رنگ به خصوصیات سیگنالهای موجود در پایگاه، دقت بازیابی را بالا می برد، چرا که در یک پایگاه خاص، ممکن است یک بازه رنگی از اهمیت بیشتری برخوردار باشد. این در حالی است که در روشهای متداول استخراج ویژگی، ویژگیها بدون توجه به خصوصیات تصاویر استخراج میشوند.
علاوه بر این، علت اینکه تنظیم ویژگی رنگ اثربخش تر از ویژگی بافت بوده این است که به طور کلی ویژگی رنگ تاثیر بیشتری در نتایج بازیابی دارد، چرا که معنای تصویر بیشتر از رنگ تصویر قابل دریافت است تا بافت آن. بنابراین، تنظیم تطبیقی آن با توجه به خصوصیات تصویر اثربخش تر از استخراج تطبیقی ویژگی بافت است.
در شکل (7)، نتایج بازیابی تصاویر برای یک تصویر نمونه آورده شده و نتایج سامانه متداول بازیابی تصویر با سامانه پیشنهادی پس از تنظیم تطبیقی ویژگی بافت و رنگ آورده شده است. این شکل، بهبود قابل توجه تصاویر بازیابی شده در روش پیشنهادی را نشان میدهد؛ به طوری که تعداد تصاویر مرتبط بازیابی شده در روش پیشنهادی نسبت به روش متداول بیشتر است.
شکل (6): گراف دقت پس از بهینهسازی ویژگی رنگ، بهینهسازی ویژگی بافت، و بهینهسازی ویژگی رنگ و بافت در مقایسه با گراف دقت سامانه متداول بازیابی تصویر
(الف)
(ب)
(ج)
شکل (7): تصاویر مرتبط در 50 رتبه اول. تصاویر بر حسب رتبه از چپ به راست و از بالا به پایین چیده شدهاند. الف) تصویر پرس و جو، ب) نتایج سامانه متداول بازیابی تصویر (34 تصویر مرتبط)، ج) نتایج با سامانه پیشنهادی پس از تنظیم تطبیقی ویژگی بافت و رنگ (37 تصویر مرتبط)
نمایهسازی و بازیابی تصویر یکی از زمینههای مهم و فعال تحقیقاتی در بینایی ماشینی است. در سیستمهای بازیابی بر اساس محتوا، عموما پرس و جوی کاربر بر پایه ویژگیهای معنایی انجام میشود. این در حالی است که نمایه سازی معنایی تصاویر با استفاده از ویژگیهای سطح پایین کار دشواری است. در این مقاله، ترکیب دو نوع ویژگی متفاوت هیستوگرام رنگ و تبدیل موجک و بهینهسازی آنها در بازیابی بررسی شد. برای استخراج ویژگی بافت از تبدیل موجک با استفاده از موجک پارامتری استفاده شده است. ویژگی رنگ به صورت هیستوگرام رنگ در فضای رنگ HSV در نظر گرفته شده است. پارامترهای موجک مادر و سطوح چندیسازی با استفاده از الگوریتم جستجوی گرانشی برای حداکثر کردن دقت بازیابی بهینه سازی شدهاند. نتایج در یک سامانه با 1000 تصویر و ده گروه معنایی با استفاده از محاسبه گراف دقت ارزیابی شده است. مقایسه روشها با یک سامانه متداول بازیابی تصویر، بهبود نتایج را نشان میدهد.