چکیده

مراحل اولیه بسیاری از الگوریتم های بینایی کامپیوتری استخراج و تطبیق نقطه کلیدی است. در مجموعه‌های بزرگ تصویر ، تطبیق دوتایی توصیفگرهای نقطه کلیدی بین تصاویر، یک گلوگاه مهم است. برای هر توصیفگر در یک تصویر، نزدیکترین همسایه (تقریبی) در تصویر دیگر باید پیدا شود و با نزدیکترین همسایه دوم بررسی شود تا اطمینان حاصل شود که مطابقت بدون ابهام است. در اینجا، ما این سوال را مطرح کردیم که چگونه می‌توان لیست نقاط کلیدی را بدون از دست دادن تطابق ها کاهش داد، یعنی می‌خواهیم با فیلتر کردن نقاطی که در مرحله تطابق حذف می شوند، تطابق را سرعت بخشیم. به نظر می رسد که بهترین معیار فیلتر، پاسخ آشکارساز نقطه کلیدی نیست، که در واقع تعجب آور نیست: هدف تشخیص، نقاط تکرارپذیر و به خوبی محلی سازی شده است، در حالی که هدف از انتخاب، نقاطی هستند که توصیف کننده های آنها می توانند با موفقیت مطابقت داده شوند. ما نشان می‌دهیم که در واقع می‌توان پیش‌بینی این که کدام توصیفگرها قابل تطبیق هستند را یاد گرفت و بنابراین تعداد نقاط کلیدی را بدون از دست دادن تعداد زیادی از تطبیق ها به میزان قابل توجهی کاهش داد. ما نشان می‌دهیم که این استراتژی، به همان اندازه که ساده است، موفقیت تطبیق را با همان تعداد نقاط در هر تصویر بسیار بهبود می‌بخشد.

معرفی

تطبیق نقاط کلیدی بین تصاویر مختلف یک عملیات اساسی بینایی کامپیوتر است. تطابقات – یعنی نگاشت های (محتمل) یک نقطه به شبیه های خودش- اساس روش‌های قبلی برای ثبت تصویر [12]، ساختار از حرکت (SfM) [15، 9] و ردیابی مبتنی بر ویژگی [ 24] است ، و برای تأیید هندسی در هنگام تشخیص شی و بازیابی تصویر استفاده می شود [26، 21].

بلوک‌های اولیه محاسباتی برای یافتن نقاط تطبیق در دو تصویر ساده هستند: پس از یافتن نقاط متمایز در هر دو تصویربه صورت مجزا با یک آشکارساز نقطه کلیدی (به عنوان مثال هریس، تفاضل گوسی)، نقاط شناسایی شده با توصیفگرهایی بر اساس همسایگی خود کدگذاری می‌شوند. (به عنوان مثال روشنایی خام، SIFT، SURF، و غیره).

سپس، برای هر نقطه از تصویر مبدأ، بهترین تطابق را در بین نقاط تصویر هدف جستجو می‌کنیم، یعنی نزدیک‌ترین همسایه را در فضای توصیفگر (معمولاً با ابعاد بالا). در نهایت، مجموعه تناظرهای احتمالی که بدین ترتیب یافت می‌شوند، با برازش قوی یک تبدیل هندسی مناسب، معمولاً با روش‌های نمونه‌برداری از نوع RANSAC، و کنار گذاشتن خارج از خط ها، تأیید می‌شوند.

استراتژی از دو مشکل اساسی رنج می برد. از یک طرف، در عمل، بخش بزرگی از نقاط علاقه شناسایی شده در تصاویر را نمی توان به طور قابل اعتماد مطابقت داد، زیرا چندین نامزد با فواصل قابل مقایسه وجود دارد. بنابراین، فرد فقط بین رد کردن همه موارد مبهم یا حفظ همه آنها می تواند انتخاب کند. یک روش که توسط Lowe [21] مطرح می‌شود، بیشتر مورد استفاده قرار می‌گیرد: نه تنها بهترین کاندید منطبق، بلکه بهترین گزینه دوم را نیز می‌یابیم، و هر زمان که دو توصیفگر به خوبی مطابقت داشته باشند (یعنی نسبت دو فاصله برابر و نزدیک 1 است)) کاندید رد می شود. یک رویکرد جایگزین سعی می‌کند نزدیک‌ترین همسایه‌های متقابل را بیابد، که محاسبات را دو برابر می‌کند، اما از نظر تجربی تطابق را تا حد زیادی بهبود نمی‌بخشد .

از سوی دیگر، تطبیق از نظر محاسباتی سنگین است: مقایسات برای n نقطه کلیدی در هر تصویر، با یک پیاده سازی دقیق نیاز O(n2) دارد. و حتی راه‌حل‌های غیر دقیق مبتنی بر جستجوی تقریبی نزدیک‌ترین همسایه (ANN) در درخت‌های تقسیم‌بندی مکانی [3] یا بر اساس تکنیک‌های درهم‌سازی حساس به محل [11] همیشه دارای پیچیدگی فوق‌خطی هستند.در کاربردهای مقیاس بزرگ مانند SfM نامرتب یا بازیابی، بنابراین دو گزینه مکمل باقی می‌ماند: یا تعداد m تصاویری که به صورت زوجی تطبیق داده شده‌اند را کاهش دهید [1، 16، 10]، به قیمت از دست دادن کامل برخی از جفت‌های تصویر قابل تطبیق. ; یا تعداد n نقطه کلیدی را که باید در هر تصویر مطابقت داده شود، به قیمت از دست دادن برخی از منطبقات صحیح کاهش دهید.

در کار حاضر به گزینه دوم می پردازیم. سؤالی که می‌پرسیم این است که آیا می‌توانیم پیش‌بینی کنیم که کدام توصیفگرها قبل از مرحله تطبیق قابل تطبیق هستند، در نتیجه تعداد نقاط کلیدی را بدون آسیب رساندن به مراحل بعدی کاهش دهیم؟

نقطه شروع مشاهده این است که در مرحله تشخیص نقطه کلیدی، نقاطی را هدف می گیریم که به خوبی محلی سازی شده و قابل تکرار هستند، اما تشخیص نقطه کلیدی به طور صریح نقاطی را جستجو نمی کند که بعداً بتوان با موفقیت مطابقت کرد. در واقع، از تجربه مشخص شده است که بعضی نقاط کلیدی مستحکم (مثلاً آنهایی که روی پوشش گیاهی، یا روی سطح جاده هستند) به ندرت موفقیتی در مطابقت دارند، به شکل 1 مراجعه کنید.

بنابراین پیشنهاد می‌کنیم طبقه‌بندی‌کننده‌ای را بیاموزیم که پیش‌بینی می‌کند کدام توصیفگر شانس بالایی برای یافتن یک تطابق خواهد داشت و تعداد نقاط را به گونه‌ای کاهش می‌دهد که عمدتاً نقاط بی‌فایده دور ریخته می‌شوند و میزان موفقیت تطبیق بهبود می‌یابد. توجه داشته باشید که هزینه محاسباتی پیش‌بینی پیشنهادی از نظر تعداد نقاط کلیدی, خطی و در مقایسه با ساخت واقعی بردارهای توصیفگر ناچیز است و از این رو می‌تواند زمان محاسبات را به میزان قابل توجهی کاهش دهد.

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

نقاط قابل تطبیق در ساختار-از-حرکت

سناریوی کاربردی ما محاسبه ساختار از حرکت از مجموعه‌های تصویر نامرتب است. در حالی که چارچوب پیشنهادی عمومی است و می تواند با سایر وظایف بینایی کامپیوتری سازگار شود، SfM شاید واضح ترین مثال باشد. در SfM نامرتب کلاسیک، همانطور که به عنوان مثال توسط باندلر [28] نشان داده شده است. ، تطبیق تصویر دوتایی بر زمان محاسبه غالب است و گلوگاه اصلی است، زیرا تعداد جفت‌های تصویری که باید مطابقت داده شوند با توجه به مجموعه تصویر ورودی به صورت درجه دوم افزایش می‌یابد.