چکیده
در بینایی سه بعدی، اطلاعات عمق از طریق نگاشت اختلاف مکان، در تطبیق دو تصویر حاصل میشود. لذا تطبیق استریو مهمترین مسئله در بینایی سه بعدی به شمار میرود. در این مسئله هدف یافتن بهترین نگاشت اختلاف مکان است. بعضی از روشهای ارائه شده در این رابطه، نتایج با سرعت بالا ولی با دقت پایین تولید کردهاند. در این مقاله، اتوماتای سلولی دو بعدی جهت بهبود دقت نگاشت اختلاف مکان استفاده میشود. با توجه بر اینکه، همبستگی پیکسلها در دو بعد میباشد، لذا استفاده از اتوماتای سلولی دو بعدی، نگاشت بهتری در تطبیق دو تصویر نتیجه میدهد. نتایج حاصل شده، بر اساس معیارهای پیکسلهای غیر مسدود (nonocc)، همه پیکسلها (all) و پیکسلهایی که نزدیک به ناپیوستگی اختلاف مکان (disc) هستند، سنجیده میشود و در نهایت عملکرد الگوریتم بر مبنای رتبه میانگین ارزیابی میگردد. طی آزمایشات

انجام گرفته، الگوریتم پیشنهادی از نظر رتبه میانگین در جایگاه خوبی قراردارد، که بیانگر کارآمدی روش پیشنهادی است.
کلید واژه- اتوماتای سلولی، تطبیق استریو، نگاشت اختلاف مکان.

-۱ مقدمه

تطبیق استریو [۱]، یکی از وظـایف پیچیـده در بینـایی سـه بعدی است. استریو به معنی دو تصویر اکتسـابی از یـک صـحنه، بوسیله دو دوربین است، بطوریکه دوربینهـا از لحـاظ مختصـات افقی اندکی با یکدیگر فاصله داشـته باشـند. ایـن فاصـله موجـب ناهمخوانی در دو تصویر میشود، که امکـان تخمـین عمـق اشـیأ حاضر در صحنه را امکانپذیر میسازد. در مسئله تطبیق اسـتریو، هدف یافتن محتمل ترین پیکسل متناظر در هر دو تصویر اسـت. بعبارتی دیگر، نگاشتی بین پیکسلهای دو تصویر برقرار میکنـد، که از طریق اختلاف مکان، d، پیکسل در دو تصویر متناظر، عمق آن پیکسل حاصل میگردد. جستجو جهت یافتن پیکسل متناظر، فقط بصورت افقی و روی یک خط صورت میگیرد. نگاشـتی کـه فاصله افقی دو نقطه متناظر را بیـان مـیکنـد، نگاشـت اخـتلاف مکان نام دارد .[۲] به ازای هر مقدار جابجایی تصویر راست، یـک نگاشت اختلاف مکان دو بعدی وجود دارد. اجتماع کل نگاشتها، به ازای تمام مقادیر اختلاف مکان [dmin, dmax]، تصویری از عمـق اشیأ حاضر در صحنه را نتیجه میدهد.
این مسئله با استفاده از الگـوریتمهـای مبتنـی بـر ناحیـه و مبتنی بر ویژگی قابـل حـل اسـت. روشهـای مبتنـی بـر ناحیـه سریعتر هستند و بـرای اسـتخراج نگاشـت اخـتلاف مکـان انبـوه

استفاده میگردند. در مقابل روشهای مبتنی بر ویژگی اگرچـه از دقت بیشتری برخوردارند، اما معمولأ نگاشتهای اخـتلاف مکـان خلوت تولید میکنند و نیازمند درونیابی تصویر هستند. استخراج ویژگــی و درونیــابی تصــویر باعــث افــزایش هزینــه محاســباتی مــیشــوند. بنــابراین الگــوریتمهــای مبتنــی بــر ویژگــی ســرعت محاسباتی کمتری دارند.
اتوماتای سلولی توسط اولام و نیومن [۳] معرفی شد. آنها بطور گسترده از اتوماتای سلولی جهت مدلسازی حجم وسیعی از سیستمهای پویا در حوزههای کاربرد مختلف استفاده کردند. یک اتوماتای سلولی اساسأ یک الگوریتم کامپیوتری است که در زمان و مکان گسسته است و روی شبکهای از مکانها عمل میکند.
اخیرأ از اتوماتای سلولی در بسیاری از زمینـههـای پـردازش تصویر و بینایی کامپیوتر استفاده شـده اسـت .[۴] از کاربردهـای آن میتوان به شناسایی لبه، قطعـه بنـدی و نـویزبرداری تصـویر اشاره کرد. معمولا از اتوماتای سلولی در مسـئله تطبیـق اسـتریو، بصورتی استفاده شده است که بتوان آنرا بـر روی مـدارات پیـاده سازی کرد و در کاربردهای بلادرنگ از آن بهره گرفت. از کارهای انجام گرفته در این زمینه میتوان به ۷]،۶،[۵ اشـاره کـرد. نتـایج حاصل از این الگوریتمها، عمومأ حاوی مقادیر بالای نویز میباشد، زیرا در کاربردهای بلادرنگ زمان نسبت به دقـت ارجحیـت دارد، بنابراین هدف، تولید نگاشـت اخـتلاف مکـان در کمتـرین زمـان

۱

دومین کنفرانس بینالمللی بازشناسی الگو و تحلیل تصویر ایران، دانشگاه گیلان، اسفند ۱۳۹۳

ممکن است.
روش پیشنهادی متشکل از سه مرحله است: در مرحلـه اول، نگاشت اختلاف مکان با استفاده از روش مجموع اخـتلاف مطلـق ۹]،[۸، تولید میشود. نگاشت حاصل شده در ایـن مرحلـه شـامل نویز با سطح بالا است. در مرحله دوم، که مرحله بهینه سازی نـام دارد، نگاشت تولید شده، با استفاده از اتوماتای سـلولی دو بعـدی فیلتر میشود. نگاشت حاصله شامل حفرههـایی اسـت کـه بعلـت عدم دقت کافی الگوریتم مجموع اختلاف مطلق بوجود آمـدهانـد. سرانجام، در مرحله آخر، از عملگر ریخت شناسی پرسـازی [۱۰]، جهت همگن سازی نگاشت اختلاف مکان، استفاده میشود.

-۲ روش پیشنهادی

-۱-۲

تطبیق مبتنی بر همبستگی، عمومأ نگاشتهای عمـق انبـوه بوســیله محاســبه اخــتلاف، بــرای هــر پیکســل حاضــر در یــک همسایگی، تولید میکند. این کار بوسیله اتخاذ یک پنجره محلـی با ابعاد مشخص، حول پیکسل مورد نظر در تصویر مرجـع و پیـدا کردن پیکسل مشابه در همان پنجـره در تصـویر هـدف، صـورت میپذیرد، که در امتـداد خـط افقـی جسـتجوی متنـاظر، پنجـره جابجا میشود. هـدف یـافتن پیکسـل متنـاظر در یـک محـدوده اختلاف مکان مشخص، d، است، بطوریکـه تـابع هـدف کمینـه و شباهت بیشینه گردد.

تصاویر میتوانند بوسیله در نظر گرفتن تصویر چـپ بعنـوان مرجع (تطبیق چپ-به-راست، که تطبیق مستقیم نام دارد) و یـا در نظر گرفتن تصویر راست بعنوان مرجع (راست-بـه-چـپ، کـه تطبیق معکوس نام دارد)، تطبیق یابند.

در این مقاله از روش مجموع اختلاف مطلـق بـرای محاسـبه نگاشت اختلاف مکان استفاده شده اسـت. ایـن روش مبتنـی بـر ناحیه میباشد و نسـبت بـه روشهـایی ماننـد مجمـوع مربعـات اختلاف، همبستگی تقـاطع نرمالسـازی شـده، مجمـوع همینـگ فاصله، از دقت بیشـتری برخـوردار اسـت و نـویز کمتـری تولیـد میکند. در این روش، هدف، کمینه کردن تابع هدف تعریف شده در معادله (۱) است. یافتن مقدار کمینه این تابع به منزله یـافتن نگاشت اختلاف مکان با بیشترین دقت است. در این مقالـه ابعـاد پنجره همسایگی ۳ ۳ انتخاب شده است. انتخاب ابعاد بـالا بـرای پنجره همسایگی موجب حذف جزئیات و لبههای سطوح نگاشـت اختلاف مکان شده و تصویری مبهم حاصـل مـیشـود. در مقابـل انتخاب ابعاد پایین موجب میگردد تا نگاشت تولید شـده شـامل

مقدار بسیار زیادی نویز تصـادفی باشـد، و چـون نویزهـای تولیـد شده از تابع خاصی پیروی نمیکنند، حذف آنها مشـکل بـوده و یکی از چالشهای اساسی در تطبیق استریو به شمار میرود.

محدوده اختلاف مکان، d، با توجه به نحوه اکتساب تصـاویر، متفاوت است. این محدوده وابسته به میزان جابجایی دوربـین در محور افقی، در هنگام تصویر برداری اسـت. در دیتاسـت اسـتفاده شده برای این روش، هر یک از تصـاویر محـدوده اخـتلاف مکـان مشخصی دارند، که هنگام محاسبه نگاشت بایـد آنهـا را در نظـر گرفت.

Il w w
(1) v) , j (i SAD(i, j, d)

w v
w I r
v) d j , (i

Il و Ir به مقادیر سطوح خاکسـتری پیکسـل تصـویر چـپ و تصویر راست اشاره میکنند، d محدوده اخـتلاف مکـان اسـت، w ابعاد پنجره همسـایگی اسـت و i و j مختصـات (سـطر و سـتون) پیکســل مرکــزی هســتند، کــه بــرای آن انــدازه تشــابه محاســبه میشود. مجموع اختلاف مطلق برای همه پیکسلها و برای همـه مقادیر اختلاف مکان محاسبه میشود، و یک انباشتگر تشابه برای هر پیکسل ساخته خواهد شد، که بیانگر محتمـل تـرین اخـتلاف مکان است. بر طبق معادله (۲)، برای محاسـبه نگاشـت اخـتلاف مکان، برای هر پیکسل، جسـتجویی در مجمـوع اخـتلاف مطلـق برای همه مقادیر اختلاف مکان [dmin, dmax] صورت میپذیرد. در محدوده اختلاف مکان، [dmin, dmax]، جایی کـه مجمـوع اخـتلاف مطلق برای هر پیکسل کمینه اسـت، ایـن مقـدار بعنـوان مقـدار پیکسل متناظر برای نگاشت اختلاف مکان تعیین میشود: