بخشی از مقاله
خلاصه -
در این مقاله، یک روش جدید براي توصیف تصاویر بر اساس مدل شبکههاي پیچیده ارائهمیشود. یک تصویر داراي نقاط کلیدي است و براساس آن یک نمودار ساخته میشود که میتواند به عنوان یک شبکه پیچیده جهان کوچک مدل شده و از ویژگیهاي شبکه پیچیده همانند ویژگیهاي توپولوژیک و پویا، یک گراف CNCRG1 به دستآید. بر اساس این خصوصیات، عملیات مقایسه بین تصاویر انجام میگیرد. نتایج مقاله نشانمیدهد که این روش براي رسیدن به عملکرد شناسایی شباهت ها و در نهایت خوشهبندي/ طبقهبندي مناسبتر است.
.1 مقدمه
نقاط کلیدي یکی از شاخصهاي مهم هر تصویر میباشد و الگوریتم هاي مختلفی براي شناسایی آنها طراحی شده است که برخی از آنها داراي اهمیت بیشتري بوده و یا بیشتر مورد استفاده قرار می گیرند. مثلا در الگوریتم Sift2 که از آن براي استخراج ویژگیهاي مشخص از تصاویر استفاده شده و در کارهایی چون تطبیق نماهاي مختلف یک جسم یا صحنه و شناسایی اجسام به کار میرود. در این الگوریتم ویژگیهاي بدست آمده نسبت به مقیاس تصویر و چرخش و نسبت به تغییر دیدگاه و تغییرات نورپردازي تا اندازهاي ثابت هستند.
الگوریتم مورد استفاده دیگر الگوریتم Surf3 است که از روش هاي آشکارساز ویژگی و توصیف می باشد و از آن میتوان براي انجام وظایفی از قبیل تشخیص شیء، ثبت تصویر، طبقه بندي و یا بازسازي سه بعدي استفاده نمود. نسخه استاندارد Surf چندین بار سریع تر از Sift است.
براي تشخیص نقاط مورد علاقه در surf از یک تقریب صحیح تعیین کننده آشکارساز استفاده می شود که می تواند با کمک تصویر انتگرال محاسبه شود. از Surf براي تشخیص اشیاء، افراد و یا چهره، براي بازسازي صحنه هاي سه بعدي براي پیگیري اشیاء و براي استخراج نقاط مورد علاقه استفاده شده است .
الگوریتم دیگر روش Shi-Tomasi است که در آن مقدار مینیمم مقادیر ویژه محاسبه می شود و بر اساس نظریه ماتریس ها از این مقادیر ویژه براي شناسایی لبه و نقاط کلیدي استفاده می شود.از جمله سایر الگوریتم ها روشی است که Harris نام دارد و توسط هریس و استفنز معرفی شد و بهبود روش آشکارساز گوشه Moravec است.
لذا همانگونه که بیان شد روش هاي متعددي براي شناسایی لبه ها و نقاط کلیدي وجود دارد. همانگونه که می دانیم از گراف ها براي تشخیص الگو و دید کامپیوتري استفاده میشود. یکی از موارد کلیدي براي تشخیص الگو بر مبناي گراف ، اندازه گیري میزان تشابه میان گراف هاي دو به دو است.
مشکلترین مسئله در تعیین تشابه گرافها، این است که گرافها بردارهاي طبیعی نیستند و نمیتوانند به راحتی به بردار تبدیل شوند. به علاوه، گرافهاي به کارگرفته در تشخیص الگو بسیار شلوغ هستند و شامل تعداد زیادي گره و یال میباشند. بنابراین، حتی اگر مرتب سازي بتواند انجام شود، امکان ارتباط با بردارها با طولهاي متفاوت همچنان ضروري است. راه هاي بسیاري براي اندازه گیري میزان تشابه گرافها وجود دارد.
کلاسهاي اصلی برمبناي فاصله ویرایش گراف [1-2] GED4، هسته گراف[10-12]، تطبیق گراف و روشهاي توصیف توپولوژیکی می باشد.[12] یکی از راه هاي سنتی استفاده از مفهوم فاصله ویرایش گراف - GED - میباشد که براي اولین بار توسط SANFELIU و FU معرفی شد
GED از طریق شمارش و برچسب گذاري مجدد همزمان یالها و گره با تعداد حذفها و اضافه کردن هاي یال و گره که براي انتقال یک گراف به گراف دیگر ضروري است بوجود می آید.
BUNKE نشان داد که GED و اندازه ي حداکثر زیر گراف مشترك، داراي محدودیت و هزینه ي ویرایش گره و یال می باشد. براساس این مشاهده HANCOCK,TORSELLO محاسبات تقریبی روي فاصله ي ویرایش با استفاده از برچسب گذاري جدید با استفاده از تئوري MOTZKIN-STRAUSS انجام دادند
BUAKE ارتباط میان GED و اندازهگیري حداکثر زیر گراف مشترك و نیز منحصر به فرد بودن توابع هزینه را منتشر کرد. معمولاً گرافها میتوانند به رشته تبدیل شوند وفاصله ویرایش براي مقایسه رشته ها بکار می رودHANCOCK
.[6] از فاصله LEVEN SHTEIN براي ارزیابی تشابه رشته هاي دو به دو استفاده می کند TANG .[8] گرافها را به رشته تبدیل کرد و بر اساس تئوري گراف CATCH و با استفاده از انحراف زمان پویا DTW1 تشابه رشتهها را محاسبهنمود
RALEO_KELLY و HANCOCK این مسئله را به منظور حداکثر کردن احتمال تراز بندي براي گرافهاي دو به دو با استفاده از سري ها، فرموله کردند GAD .[6] طرحی را بر مبناي هیستوگرام براي محاسبه GED براي دو گراف ارائه داد.
راه دیگر براي اندازهگیري تشابه گرافها ، محاسبه ي تشابه بین جفت گرافهاي مبتنی بر الگوهاي مشترك است که به اشتراك می گذارند. الگو ها میتوانند در محدوده ساده تا پیچیده قرار بگیرند. تحقیقات زیادي در تلاش براي توسعه توابع هسته ي گراف بطور موثرتر و کاراتر انجام شده است. این روشها بطور گسترده میتواند به روشهایی بر اساس گامهاي تصادفی [9] کوتاهترین مسیرها [10]، زیر درختها [11] و زیر گرافها [12] دسته بندي شود. در هسته هاي گام تصادفی ، تشابه دو گراف میتواند توسط شمارش گام هایی که بین هر دوي آنها مشترك است بدست آید.
این نوع هسته معمولاً بسیار پیچیده و متزلزل است. با جایگزین کردن گامها با مسیرها، BARGWARDT و KRIEGED کوتاه ترین هسته مسیر روي گرافها را معرفی کردند. در این هسته، تشابه دو گراف از طریق مقایسه ي تمام جفت طول هاي کوتاهترین مسیر تعیین می شود.[10] این نوع از هسته میتواند از تزلزل جلوگیري کرده و معمولا سریع تر از هسته هاي گام تصادفی است. RAMON و GARTNER هسته ي زیر درخت را بروي گرافها از طریق مقایسه الگوهاي مشابه زیر درخت در دو گراف معرفی کردند
در مقایسه با گام بر اساس هسته، این روش میتواند ساختار گراف ارزشمند تري را ارائه دهد. همچنین از یک روش آماري میتواند براي محاسبه تشابه گراف ها استفاده شود. WILSEN و HANCOCK یک روش براي اندازه گیري تشابه گرافها با استفاده از توزیع احتمالی پیشنهاد دادند که تعداد گرههاي مجدد برچسب گذاري شده و عملیات ویرایش گرافها را در مواردي که خطا هاي ساختاري وجود دارد مدل سازي می کند
از روشهاي فوقالذکر جهت اندازه گیري فاصله بین ساختارهاي گراف استفاده می شود ولی از آنها نمی توان براي مرتب سازي گرافهاي حاصل از تغییرات تصویر استفاده نمود. بنابراین، ما قادریم که مشکل سازماندهی گرافها را به فضاي الگو واگذار کنیم به نحوي که در آن ساختارهاي مشابه نزدیک به یکدیگر و ساختارهاي غیر مشابه از یکدیگر مجزا شدهاند. بطور ویژه، هدف این است که گرافها به فضاي برداري که در آن ابعاد مهم هستند مرتبط شوند.
علاوه بر این، اگر گراف بتواند در MUNIFOLD فضاي الگو جا سازي شود، آنگاه روشهاي گوناگون تصویر میتواند توسط پیمودن در روش MONIFOLD کاوش شود. فرآیند ساخت فضاي کم بعد - یا با بعد کم - یا MUNIFOLD و یا بکارگیري بردارهاي الگو، یک برنامه عادي و روزمره است.
تکنیک هاي گوناگون،از قبیل مقیاس گذاري چند بعدي MDS2 ، تحلیل اجزاي اصلی PCA3، تحلیل اجزاي مستقل و نگاشت لاپلاس براي رسیدن به همین هدف وجود دارد. هرچند ، برخی از متد هاي هم ارز وجود دارند که میتوانند براي ساخت فضاي الگو با بعد کم براي مجموعه اي از گرافها استفاده شوند. یک راه براي رسیدن به این هدف، نمایش گرافها از طریق بردارهاي الگو میباشد.
متدهاي توصیف گر توپولوژیکی می توانند براي حل این مشکل استفاده شوند.[15-16] این متدها ابتدا از طریق نگاشت هر گراف به طرح بردار و سپس به کارگیري فواصل و معیارهاي روي بردار، براي یادگیري گرافها کار میکنند. جهت توصیف توپولوژیکی گراف اقدامات زیادي صورت گرفته است مثلاً LUO,WILSON,HONCOCK ساختار یک گراف را از طریق تئوري گراف SPECTRAL به درون طرح برداري با طول ثابت نگاشت کردند.[15] از طریق بردارهاي طرح اختصاصی استخراج شده از گراف، آنها راهی براي اندازهگیري فواصل گرافها و تحلیل ساختارهاي گراف بر اساس متددهاي MDSو PCA فراهم می کنند.
Gao گرافی را با بردارهاي طرح هیستوگرام [16] مشابه با متد [15] LUO معرفی نمود. این متد از فرموله کردن تابع هزینه یا معیار - میزان - تشابه گره یالهاي مشابه در دو گراف جلوگیري میکند. هرچند مشخص کردن هر دوي این موارد دشوار است ولی اشکال اصلی این متد این است که ساختارهاي گراف مبتنی بر بردارهاي طرح هیستوگرام را کاوش نمی کند.
به منظور تحقیق بیشتر بر روي مشکلات نگاشت ساختار گراف به بردار با طول ثابت و اندازهگیري میزان تشابه گرافها، در این مقاله از متد نمایش شبکه هاي پیچیده استفاده می کنیم. شبکه هاي پیچیده میتواند به صورت ترکیب تئوري گراف و تئوري احتمال توصیف شود که بطور گسترده در علم کامپیوتر، ریاضی و فیزیک استفاده می شود [17-19] و علاقمندان زیادي در بسیاري از زمینه هاي علوم را جذب کرده است. محبوبیت شبکه هاي پیچیده، ناشی از انعطاف پذیري و معمولاً امکان نمایش و ساختار داده اي آن می باشد. سایر نکات جالب در رابطه با شبکه هاي پیچیده، تغییرات توپولوژي، اتصال ساختارها در طی فرآیند ارزیابی و اندازه گیري مشخصه هاي ساختارهاي شبکه است.
تلاشهاي اخیر، موجب بکارگرفتن شبکه هاي پیچیده در داده هاي دنیاي واقعی شده است که شامل نمایش مشکلات واقعی شبکه هاي پیچیده و تحلیل میزان رشد پویایی شبکه و تشخصیص ویژگی هاي توپولوژي شبکه پیچیده، براي مدلسازي متن ها، شالوده ي عکس و تصاویر است که در آنها بردارهاي طرح به منظور دستهبندي و تشخیص توسط اندازه گیري هاي توپولوژیکی شبکه، استخراج میشوند.
علاوه بر اینها روش هایی برمبناي مدل شبکه جهان کوچک مطرح شده اند که در آنها قالب شکل به منظور ارتباط با ساختار شبکه جهان کوچک در طی تمامی مراحل تکامل شبکهها نشان داده شده است. خصوصیات پویا و توپولوژیکی شبکه براي توصیف مرزها استفاده شده است. در این مقاله ،یک متد نمایش ساختارگراف برمبناي شبکه ي پیچیده مطرح شده است. در ابتدا ساختار گراف را به عنوان یک شبکه پیچیده مدل کرده وسپس به استخراج خصوصیات پویا وتوپولوژیکی شبکه ي پیچیده میپردازیم تا ساختار گراف را توصیف کنیم. با تصور ارتباطات خاص بین یالهاي گراف که عناصر اصلی در ساختار گراف هستند، شبکه پیچیدي ما با استفاده از گراف ها نمایش داده می شود.
.2 مفاهیم شبکه هاي پیچیده
همانطور که می دانیم شبکه هاي پیچیده گرافی است شامل مجموعه اي از رئوس که توسط یالهایی به هم متصل شده اند. با توجه به خصوصیات آنها شبکههاي پیچیده میتوانند به سه مدل اصلی -1شبکه هاي تصادفی -2شبکه هاي جهان-کوچک -3شبکه هاي مقیاس آزاد دسته بندي شوند. در مدل شبکههاي تصادفی که ساده ترین مدل است لبه ها به صورت تصادفی اضافه میشوند
در مدل شبکه جهان-کوچک که توسطwatts و strogatz مطرح شد[18]، خصوصیات جهان-کوچک مطرح میشود از قبیل اینکه تمامی رئوس از هر راس دیگري از طریق تعداد محدودي از یالها قابل دسترسی است و ضریب بالاي خوشه بندي وجود دارد. Barbasi و Albert یک شبکه از نظر مقیاس ثابت معرفی کردند که آن را شبکه ي مقیاس آزاد نامیدند
یالهاي شبکه ي پیچیده به عنوان یک گراف، میتواند دودویی، داراي وزن و جهت دار باشد. در این مقاله تنها حالت بدون جهت بررسی شده است. مدل شبکه ي پیچیده ي بدون جهت معمولا با ماتریسW نمایش داده می شود که w - i,j - وزن هایی است که گره i را به گره j وصل میکند. تشخیص خصوصیات توپولوژي و اتصال شبکه ي پیچیده می تواند با استفاده از اندازه گیري برگرفته از تئوري گراف و نیز تحقیقات مربوط به شبکههاي پیچیده صورت گیرد.
هر شبکه پیچیده داراي طرح توپولوژیکی خاص است که نحوه ي اتصال را مشخص می کند. بنابراین تغییر و تحلیل شبکه هاي پیچیده بستگی به استفاده از اندازه گیري ها دارد که منجر به استخراج طرح هاي توپولوژیکی مناسب و دستهبندي آن ها می شود. توزیع درجه یک خصوصیت مهم راس در گراف است. بر اساس درجات رئوس، می توان بسیاري اندازهگیريها را انجام داد که دو مورد از ساده ترین روش هاي اندازه گیري ها عبارتنداز:
ki درجه گره i می باشد. توزیع درجه اتصال نقش مهمی در بسیاري از خصوصیات شبکه هاي پویا و ساختاري ایفا میکند. معمول ترین رهیافت، در نظر گرفتن ارتباط بین دو راس متصل شده با یک یال است. می توانیم این ارتباط را توسط توزیع درجه ي اتصال p - k,k’ - نشان دهیم. یعنی احتمال اینکه یک یال به راسی با درجه k و راسی با درجه k’ متصل شود. در این مقاله، شرایطی را در نظر می گیریم که k=k’، یعنی احتمال اینکه یک یال، دو راس با درجه ي یکسان را به هم وصل کند. بر اساس احتمال درجه ي اتصال، اندازه گیري هاي متفاوتی می تواند بدست آید از قبیل:
الف - Entropy
ب - انرژي
ج - درجه ي اتصال میانگین
در اینجا از entropy و انرژي استفاده کردیم. Entropy مربوط به توزیع درجه ي اتصال، به صورت زیر تعریف می شود:
انرژي مربوط به توزیع درجه نرمال به شکل زیر تعریف می شود:
یک راه براي تشخیص وجود لوپ از طریق ضریب خوشه بندي است. مشابه با درجه، این ضریب نیز خصوصیت مهمی براي تحلیل شبکه است. دو ضریب خوشه بندي متفاوت اغلب استفاده می شود. اولی بر اساس تعریف زیر براي شبکه بدون جهت است
