فهرست مطالب
پیشگفتار. 1
فصل اول: بررسی منابع.. 4
1-1 مقدمه. 5
1-2 مروری بر بینایی استریو. 5
1-3 هندسه‌ی بینایی استریو-بازسازی سه‌بعدی.. 7
1-4 پارامترهای یک سیستم استریو. 9
1-5 علائم راهنما 9
1-5-1 پاره‌خط‌ها 9
1-5-2 گوشه‌ها 10
1-5-3 نقاط ویژگی SIFT.. 11
1-5-3-1 تشخیص مکان ویژگی.. 12
1-5-3-2 حذف نقاط متعلق به لبه‌ها 15
1-5-3-3 تخصیص جهت.. 16
1-5-3-4 توصیف‌گر نقطه‌ی ویژگی.. 18
1-5-4 نقاط ویژگی SURF. 19
1-5-4-1 تشخیص نقاط ویژگی.. 19
1-5-4-1-1 تصاویر تجمعی.. 19
1-5-4-1-2 نقاط ویژگی مبتنی بر ماتریس هسین.. 20
1-5-4-1-3 نمایش فضای مقیاس… 22
1-5-4-1-4 تعیین مکان نقطه‌ی ویژگی.. 24
1-5-4-2 تعیین جهت غالب ویژگی.. 24
1-5-4-3 تشکیل بردار ویژگی.. 26
1-5-5 سایر نقاط ویژگی.. 27
1-5-6 بحث و جمع‌بندی.. 28
1-6 تطابق استریو. 28
1-6-1 الگوریتم‌های مبتنی بر اطلاعات نوری و پیکسل‌های تصویر. 28
1-6-2 الگوریتم‌های تطابق علائم راهنما در تصاویر استریو. 31
1-7 دنبال کردن علائم راهنما بین دو جفت تصویر استریو. 34
1-8 محاسبه‌ی جابجایی و تغییر جهت… 35
1-9 بررسی کاربردی.. 37
1-10 تعریف مسئله و اهداف پژوهش…. 37
فصل دوم: مواد و روش‌ها. 39
2-1 مقدمه. 40
2-2 دوربین استریو. 40
2-3 انتخاب نقاط علائم راهنما 42
2-4 الگوریتم‌های تطابق مبتنی بر نقاط ویژگی.. 43
2-4-1 الگوریتم مبتنی بر حد آستانه. 43
2-4-2 الگوریتم 2nd NN.. 45
2-4-3 الگوریتم‌های سراسری.. 46
2-4-3-1 مدل‌سازی مسئله. 46
2-4-3-2 تابع هدف و حل مسئله‌ی تطابق.. 48
2-4-4 دنبال کردن علائم راهنما بین دو جفت تصویر استریو. 51
2-4-5 تعیین موقعیت و جهت با استفاده از علائم راهنما 52
2-4-5-1 الگوریتم CTF. 52
2-4-5-1-1 استفاده از SVD برای محاسبه‌ی ماتریس‌های دوران و جابجایی.. 52
2-4-5-1-1-1 محاسبه‌ی چرخش… 53
2-4-5-1-1-2محاسبه‌ی جابجایی.. 53
2-4-5-1-1-3موارد خاص… 54
2-4-5-1-2 بهبود جواب.. 54
2-4-5-2 استفاده از الگوریتم ژنتیک برای محاسبه‌ی موقعیت وجهت.. 55
2-4-5-2-1 الگوریتم ژنتیک… 56
2-4-5-1-2 محاسبه‌ی موقعیت و جهت.. 61
2-4-5-2-3 محاسبه‌ی جابجایی و تغییرات زاویه نسبت به دستگاه اولیه. 64
فصل سوم: نتایج و بحث… 66
3-1 مقدمه. 67
3-2 استخراج نقاط ویژگی از تصاویر. 67
3-3 تطابق استریو. 69
3-4 دنبال کردن نقاط ویژگی بین دو وضعیت… 72
3-5 تعیین موقعیت و جهت… 74
نتیجه‌گیری.. 79
پیشنهادها. 80
منابع.. 81
فهرست شکل‌ها
شکل (1-1): در قسمت پایین شکل، دوربین استریوی بامبل‌بی2 قرار دارد. در قسمت بالای شکل، دو تصویر خروجی چپ و راست دوربین دیده می‌شود. نقاط نشان داده‌شده، نمونه‌ای از دو نقطه‌ی متناظر هستند. 6
شکل (1-2): بالا: دوربین استریو به همراه دستگاه مختصات دوربین چپ. پایین: نمایش هندسی سیستم استریو. 7
شکل (1-3): نحوه‌ی تشکیل فضای مقیاس. سمت چپ: تصاویر هموار شده با توابع گاوسین؛ سمت راست: تصاویر محاسبه‌شده از تفاضل تصاویر همواره‌شده. 14
شکل (1-4): اکسترمم محلی تابع DoG با مقایسه‌ی پیکسل نشان داده‌شده توسط ×، با 26 پیکسل همسایه در نواحی 3×3 (نقاط سبزرنگ) محاسبه می‌گردد. 15
شکل (1-5): نمونه‌ای از هیستوگرام تشکیل شده برای تعیین جهت غالب نقطه‌ی ویژگی. میله‌ی قرمز رنگ نشان‌دهنده‌ی بیشینه مقدار در هیستوگرام و در نتیجه جهت غالب نقطه‌ی ویژگی است. 17
شکل (1-6): برای تشکیل توصیف‌گر نقطه‌ی ویژگی ابتدا اندازه و جهت بردار گرادیان برای نقاط داخل پنجره‌ای حول نقطه‌ی ویژگی محاسبه می‌شود(شکل چپ). سپس مقادیر این نقاط برای نواحی 4×4 در هیستوگرام جهت وارد شده و برای 8 جهت محاسبه می‌گردد(شکل راست). 18
شکل (1-7): با استفاده از تصاویر تجمعی، می‌توان جمع مقادیر درون هر مستطیل دلخواه از تصویر را تنها با استفاده از 3 بار جمع و تفریق محاسبه کرد. 20
شکل (1-8): نیمه‌ی چپ: مشتق دوم گاوسین در راستای y ( ) و xy ( )؛ نیمه‌ی راست: تخمین همان مشتقات سمت چپ با استفاده از فیلترهای جعبه‌ای. قسمت‌های خاکستری در این فیلترها معادل صفر است. 21
شکل (1-9): سمت چپ: ابعاد فیلتر ثابت است، ابعاد تصویر به تدریج کاهش می‌یابد؛ سمت راست: ابعاد تصویر ثابت است، ابعاد فیلتر به تدریج افزایش می‌یابد. 22
شکل (1-10): فیلترهای (بالا) و (پایین) برای دو مقیاس متوالی(9×9 و 15×15). 23
شکل (1-11): فیلترهای ویولت هار که پاسخ را در جهت x(چپ) و y(راست) محاسبه می‌کنند. بخش‌های سفید معادل 1+ و بخش‌های سیاه‌رنگ، معادل 1- هستند. 25
شکل (1-13): تخصیص جهت نقطه‌ی ویژگی: پاسخ فیلتر ویولت وزنی‌دهی شده با گاوسین، برای نقاط درون ناحیه‌ای دایره‌شکل حول نقطه‌ی ویژگی محاسبه شده(بالا) و به همچون نقاطی در دستگاه مختصات کارتزین رسم می‌گردد؛ سپس با لغزاندن پنجره‌ای به پهنای در نمودار رسم شده، جهت غالب تعیین می‌شود(پایین). 25
شکل (1-14): نحوه‌ی تشکیل بردار ویژگی.. 26
شکل (1-15): توصیف‌گر ویژگی GLOH که از بردارهای گرادیان حوا نقطه‌ی ویژگی حاصل شده است… 27
شکل (1-16): نمونه‌ای از یک تصویر DSI و مسیر بهینه(نقاط سفیدرنگ). 29
شکل (1-17):مدل مسئله در الگوریتم برش گراف؛ x محور افقی، y محور قائم و d محور اختلاف مکان است. 30
شکل (2-1): بالا: دوربین استریوی مورد استفاده؛ پایین: نمایی از برنامه‌ی در حال اجرا برای تصویر برداری. 41
شکل (2-2): الگوریتم CTF. 55
شکل (2-3): نمودار ترتیبی عملکرد الگوریتم ژنتیک. 56
شکل (2-4): نمونه‌ای از یک چرخ رولت به همراه وزن‌های هر قطاع از آن. 58
شکل(2-5): جابجایی تک‌نقطه‌ای. 59
شکل (2-6) : نمونه‌ای از اعمال عملگر جهش بر روی یک کروموزوم. منظور از m، ژنی است که در اثر عملگر جهش در کروموزوم جایگزین شده است. 60
شکل (2-7): نحوه‌ی بیان متغیرهای مسئله به صورت کروموزوم برای استفاده در الگوریتم ژنتیک. 62
شکل (3-1): نقاط ویژگی استخراج شده از دو نمونه تصویر گرفته شده با استفاده از دوربین استریو. چپ: نقاط SURF؛ راست: نقاط SIFT. تصاویر مربوط به دوربین چپ دوربین استریو است. 67
شکل (3-2): نمونه‌ای از نقاط ویژگی دنبال شده در دو تصویر از دوموقعیت متفاوت. بالا سمت چپ: موقعیت اولیه؛ بالا سمت راست: موقعیت ثانویه. پایین: ترسیم نقاط دنبال شده(هر دو نقطه دسته نقاط، در یک تصویر نشان داده شده و دنبال شده‌اند). 72
فهرست جداول
جدول (2-1): مشخصات فنی دوربین بامبل‌بی2. 40
جدول (2-2):عملگرها و پارمترهای مورد استفاده در الگوریتم ژنتیک ارائه شده. 62
جدول (3-1): مقایسه‌ی تعداد نقاط ویژگی SIFT و SURF در تصاویر. 68
جدول (3-2): مقایسه‌ی دو الگوریتم تطابق مورد استفاده برای نقاط SURF. 69
جدول (3-3): نتایج بهبود الگوریتم‌های تطابق با استفاده از تطابق دوطرفه. 70
جدول (3-4): نتایج تطابق نقاط SIFT با استفاده از الگوریتم 2nd NN. 71
جدول (3-5): نتایج الگوریتم 2nd NN در دنبال کردن نقاط SURF. 73
جدول (3-6): نتایج الگوریتم 2nd NN در دنبال کردن نقاط SIFT. 73
جدول (3-7): نتایج محاسبه‌ی زوایای چرخش و تغییر مکان با استفاده از الگوریتم CTF برای نقاط SURF. 74
جدول (3-8): نتایج محاسبه‌ی زوایای چرخش و تغییر مکان با استفاده از الگوریتم CTF برای نقاط SIFT. 74
جدول (3-9): نتایج محاسبه‌ی زوایای چرخش و تغییر مکان با استفاده از الگوریتم GA برای نقاط SURF. 75
جدول (3-10): نتایج محاسبه‌ی زوایای چرخش و تغییر مکان با استفاده از الگوریتم GA برای نقاط SIFT. 75
جدول (3-11): قدر مطلق خطای CTF بر روی نقاط SURF(گردشده تا اولین رقم اعشار). 75
جدول (3-12): قدر مطلق خطای CTF بر روی نقاط SIFT (گردشده تا اولین رقم اعشار). 76
جدول (3-13): قدر مطلق خطای GA بر روی نقاط SURF (گردشده تا اولین رقم اعشار). 76
جدول (3-14): قدر مطلق خطای GA بر روی نقاط SIFT (گردشده تا اولین رقم اعشار). 76
جدول (3-15): مقایسه‌ی خطای زوایا برای دو الگوریتم و برای نقاط SIFT و SURF. 77
جدول (3-16): مقایسه‌ی خطای زوایا برای دو الگوریتم و برای نقاط SIFT و SURF. 77
لیست علائم اختصاری
Scale Invariant Feature Transform |
SIFT |
Speeded Up Robust Features |
SURF |
Coarse to Fine |
CTF |
Genetic Algorithm |
GA |
Difference of Gaussian |
DoG |
Laplacian of Gaussian |
LoG |
Smallest Univalue Segment Assimilating Nucleus |
SUSAN |
Disparity Image Space |
DSI |
Gradient Location and Orientation Histogram |
GLOH |
