تشخیص گوشه
تشخیص گوشه روشی است که در سیستم‌های بینایی کامپیوتر برای استخراج انواع خاصی از ویژگی‌ها و محتویات یک تصویر استفاده می‌شود. تشخیص گوشه اغلب در تشخیص حرکت، انطباق تصویر، ردیابی ویدئو، موزاییک تصویر، دوخت پانوراما، مدل‌سازی سه‌بعدی و تشخیص شی مورد استفاده قرار می‌گیرد. تشخیص گوشه و موضوع تشخیص نقطه برای رسیدن به هدف مشترک هم‌پوشانی دارد.
گوشه را می‌توان به عنوان تقاطع دولبه تعریف کرد، همچنین می‌توان نقطه‌ای تعریف کرد که در همسایگی‌اش دو جهت لبهٔ متفاوت و غالب وجود دارد.
نقطهٔ مطلوب در تشخیص گوشه، نقطه ای است که موقعیتش به خوبی تعریف و شناسایی می‌شود. این به این معنی است که نقطهٔ مطلوب شناسایی شده می‌تواند به عنوان گوشه شناسایی شود، اما ممکن است یک نقطهٔ مجزایی باشد که شدت روشنایی‌اش نسبت به همسایگی اطرافش مقدار ماکزیمم یا مینیمم باشد، پایان یک خط باشد یا اینکه نقطه ای از یک منحنی باشد که در آن نقطه انحنای منحنی بیشترین مقدار می‌باشد.
در عمل، بیشتر روش‌های تشخیص گوشه به‌طور کلی نقاط مطلوب را تشخیص می‌دهند و در واقع، اصطلاح «گوشه» و «نقطهٔ مطلوب» در ادبیات‌های مختلف بیشتر یا کمتر تغییر می‌کند. در نتیجه، اگر فقط بخواهیم گوشه شناسایی شود، برای تشخیص نقاط گوشه‌های واقعی، لازم است تجزیه و تحلیل‌های محلی بر روی نقاط مطلوب انجام گیرد. نمونه‌هایی از تشخیص لبه که در پیش‌پردازش برای شناسایی گوشه به کار می‌رود، اپراتور کیرش و مجموعه ماسک فری-چن می‌باشد.
«گوشه» و «نقطهٔ مطلوب» و «ویژگی» به جای یکدیگر استفاده می‌شود. به‌طور خاص چند شناساگر لکه وجود دارد که به «اپراتورهای تشخیص نقطهٔ مطلوب» اشاره می‌کند اما گاهی اوقات به اشتباه به «آشکارسازهای گوشه» اشاره می‌کند. علاوه بر این، برای دستیابی به مرز اشیا یک مفهوم شناسایی مرز (ridge detection) وجود دارد.
آشکارسازهای گوشه معمولاً به اندازهٔ کافی قوی نیستند و اغلب برای جلوگیری از اثر خطاهای فردی ناشی از تشخیص نیازمند ریداندانت است.
یک راه تشخیص میزان کیفیت یک آشکارساز گوشه توانایی تشخیص گوشه‌های مشابه در تصاویر مشابه، در شرایط روشنایی مختلف، انتقال، چرخش و سایر تغییرات است.
یک رویکرد ساده برای تشخیص گوشه در تصاویر، از همبستگی استفاده می‌کند، اما دارای محاسبات زیادی می‌باشد. یک رویکرد جایگزین که اغلب استفاده می‌شود براساس یک روش پیشنهادی توسط هریس و استفنز است که به نوبه خود بهبود روش مراوک می‌باشد.
یکی از اولین الگوریتم‌های تشخیص گوشه است. این الگوریتم برای هر پیکسل در تصویر بررسی می‌کند که آیا گوشه است یا اینکه نیست؛ که این کار با بررسی اینکه پیکسل مرکزی پنجره با پیکسل‌های اطرافش به چه میزان شباهت دارد صورت می‌گیرد. میزان شباهت با محاسبهٔ مجموع اختلاف مربعات بین پیکسل مرکزی و پیکسل‌های اطراف آن و موجود در پنجره به‌دست می‌آید. هر چقدر مقدار عدد به‌دست آمده کمتر باشد، میزان شباهت بیشتر است.
اگر پیکسل در یک منطقه از شدت یکنواخت باشد، سپس پیکسل‌های مجاور دارای شدت یکسانی می‌باشد و مشابه با پیکسل مورد بررسی به نظر می‌رسد، اگر پیکسل بر روی یک لبه باشد، شدت روشنایی پیکسل‌های اطراف در جهت عمود بر لبه‌ها کاملاً متفاوت خواهد بود، اما در شدت روشنایی پیکسل‌های مجاور در جهت موازی با لبه، تنها یک تغییر کوچک رخ می‌دهد.
قدرت گوشه به کمک کمترین مقدار مجموع مربعات اختلاف بین پیکسل مورد بررسی و همسایگان آن در یک پنجره تعریف می‌شود. دلیل این امر این است که اگر این مقدار زیاد باشد، تغییرات در طول تمام شیفت‌های پنجره یا برابر با آن یا بزرگتر از آن است، بدین ترتیب که همه پیکسل‌های اطراف متفاوت به نظر می‌رسند.
اگر مقدار قدرت گوشه برای همهٔ پیکسل‌ها محاسبه شود و برای یک پیکسل بیشترین مقدار باشد و به عبارت دیگر بیشتر از حد آستانه باشد، آن پیکسل نقطهٔ کلیدی برای تشخیص گوشه تعیین می‌شود.
همان‌طور که توسط مراوک اشاره شده‌است، یکی از مشکلات عمده این اپراتور این است که آن را ایزوتروپیک نمی‌کند: یعنی اگر یک لبه وجود داشته باشد که در جهت همسایگان (افقی، عمودی یا مورب) نباشد، سپس مقدار کوچکترین SSD بزرگ خواهد بود و به صورت نادرست لبه به عنوان نقطه مورد نظر انتخاب می‌شود.
هریس و استفنز، آشکارساز گوشهٔ مراوک را با در نظر گرفتن دیفرانسیل گوشه با توجه به جهت‌های مستقیم، به جای استفاده از پنجره‌های شیفت‌یافته توسعه دادند. در این الگوریتم از اتوکورولیشن استفاده می‌شود همچنین در محاسبات ریاضی آن مشاهده می‌شود که مجموع مربعات اختلافات استفاده شده‌است.
در این روش تصویری که در نظر می‌گیریم یک تصویر دو بعدی خاکستری است؛ که مقدار شدت روشنایی هر پیکسل را با I نمایش می‌دهیم که مختصات پیکسل را با (u,v) در نظر می‌گیریم و مقدار جابجایی صورت گرفته را با (x,y) نمایش می‌دهیم. در فرمول زیر S وزن مجموع مربعات اختلافات بین دو پچ می‌باشد.
(I(u+x,v+y با بسط تیلور تخمین زده می‌شود و همان‌طور که در رابطهٔ زیر نشان داده می‌شود در این تخمین مشتق جزئی I استفاده می‌گردد.
که تقریب زیر را تولید می‌کند.
که می‌تواند به فرم ماتریس نوشته شود.
که A تنسور ساختار (structure tensor) است.
این ماتریس، ماتریس هریس است و براکت زاویه میانگین را مشخص می‌کند و (w(u,v نشانگر نوع پنجره ای است که بر روی تصویر حرکت می‌کند. اگر فیلتر استفاده شده یک فیلتر پالسی باشد پاسخ ما غیرایزوتروپیک است یعنی ممکن است لبه را به عنوان گوشه مشخص کند، اما اگر فیلتر گوشی باشد پاسخ ما ایزوتروپیک است.
یک گوشه با محاسبهٔ S در همهٔ جهات بردار (x,y) مشخص می‌شود. با محاسبهٔ مقادیر ویژهٔ A شاخص به صورت زیر بیان می‌شود:ماتریس A برای نقاط مطلوب مشکوک به گوشه دو مقدار ویژهٔ بزرگ دارد. بر اساس اندازهٔ مقادیر خاص، می‌توان نتیجه‌گیری‌های زیر را انجام داد:
هریس و استفنز یادآوری می‌کنند که محاسبه دقیق مقادیر ویژه محاسبه گرانی است زیرا نیاز به محاسبه یک ریشه مربع square root دارد و به جای آن تابع formula_11 formula_12 :
در این الگوریتم نیاز نیست که مقادیر ویژه ماتریس A محاسبه شود کافیست مقدار دترمینان و مجموع عناصر روی قطرش را محاسبه کنیم.
آشکارساز شی-توماس به صورت مستقیم مقدار میانگین مقادیر ویژه را محاسبه می‌کند چون به کمک فرضیه‌های خاص گوشه‌های تعیین شده پایدارترند، این روش برخی مواقع به اسم kanade-Tomasi شناخته می‌شود.
مقدار formula_12 معمولاً به صورت تجربی به دست می‌آید و در رنج ۰٫۰۴ تا ۰٫۱۵ می‌باشد.
با استفاده از تعریف نوبل می‌توان از محاسبهٔ مقدار formula_12 صرف نظر کرد و formula_16 را اندازه‌گیری نمود، که به میانگین همساز مقادیر خاص مربوط می‌شود.
formula_18 یک مقدار کوچک مثبت می‌باشد.
"اگر "formula_19 موقعیت گوشه تفسیر شود، آنگاه formula_20.
مجموع مقادیر ویژهٔ formula_20 formula_16 مربوط است:
در بعضی موارد، ممکن است بخواهید مکان یک گوشه را با دقت زیر پیکسل محاسبه کنید. برای رسیدن به یک راه حل تقریبی، الگوریتم Förstner نقطه ای که به تمام خطوط مماس گوشه در یک پنجره معین نزدیک‌تر است را به کمک راه حل حداقل مربعات تعیین می‌شود. الگوریتم به این واقعیت اعتقاد دارد که برای یک گوشه ایده‌آل خطوط مماسی در یک نقطه برخورد می‌کنند.
معادلهٔ خطوط مماس formula_25 در پیکسل formula_26به صورت زیر به دست می‌آید:
که formula_28 بردار گرادیان تصویر formula_29 در formula_26.
نقطهٔ formula_31 نزدیک‌ترین نقطه به همهٔ خطوط مماس در پنجرهٔ formula_32برابر است یا:
فاصله بین formula_31 و خطوط مماس formula_35
نحوهٔ محاسبهٔ formula_31:
formula_38 به صورت زیر تعریف می‌شود:
محاسبهٔ حداقل با با مشتق‌گیری ز معادلهٔ فوق برحسب x و برابر صفر قرار دادن آن معادله به دست می‌آید:
توجه داشته باشید که formula_41 یک تنسور ساختاری است، برای اینکه معادلهٔ فوق دارای جواب باشد A باید معکوس‌پذیر باشد، در نتیجه A باید مرتبهٔ کامل باشد، در نتیجه راه‌حل به صورت زیر است:
تنها زمانی معادلهٔ فوق جواب دارد که گوشه در داخل پنجرهٔ formula_32
یک روش برای انجام انتخاب مقیاس اتوماتیک برای این روش محلی سازی گوشه توسط لیندبرگ با به حداقل رساندن مانده نرمال شده ارائه شده‌است:
به این ترتیب، این روش توانایی به صورت خودکار سطح مقیاس را به سطح نویز در داده‌های تصویری برای محاسبه گرادیان تصویر تطبیق دهد، که این کار به کمک انتخاب مقادیر مقیاس بزرگتر برای داده‌های تصویر دارای نویز و مقیاس‌های دقیق‌تر برای ساختارهای نزدیک به شکل ایده‌آل گوشه صورت می‌گیرد.
نکات:
محاسبهٔ ماتریس ممان دوم (برخی مواقع به تنسور ساختاری اشاره می‌کند). در اپراتور هریس A به محاسبهٔ مشتقات جزئیformula_47 در تصویر برای محاسبهٔ ترکیب‌های غیر خطی این مشتقات در همسایگی‌ها نیاز دارد. از آنجا که محاسبه مشتقات معمولاً شامل یک مرحله از مقیاس فضا است، تعریف عملیاتی از اپراتور هریس نیاز به دو پارامتر مقیاس دارد:۱) تعیین یک مقیاس محلی برای نرم کردن قبل از محاسبهٔ مشتقات تصویر۲) تعیین یک مقیاس یکپارچه برای جمع‌آوری عملیات غیر خطی بر روی اپراتورهای مشتق
با توجه به اینکه I شدت روشنایی تصویر اصلی را نشان می‌دهد، L مقیاس فضایی مربوط به I به دست آمده با کانولوشن با گوسی-کرنل را نشان می‌دهد.
با پارامتر مقیاس محلی formula_49:
سپس ما می‌توانیم مقادیر ویژهٔ formula_52 را همانند مقادیر ویژهٔ formula_19
ارتباط انتخاب پارامتر مقیاس محلی formula_49 و پارامتر مقیاس formula_56 formula_57 مرتبط می‌شوند، که ارتباط آن‌ها به صورت formula_58 formula_57 مقداری در بازهٔ formula_60 formula_61 تنها وابسته به پارامتر formula_49 محاسبه کنیم.
درعمل این آشکارساز گوشهٔ چندگانه با اپراتور لاپلاسین تکمیل شده‌است.
در هر مقیاس در مقیاس فضایی و مقیاس نقاط گوشه با انتخاب اتوماتیک مقیاس ("اپراتور هریس لاپلاس") محاسبه شده‌است.یک رویکرد پیشین به تشخیص گوشه، تشخیص نقاطی است که انحنای سطح منحنی و گرادیان به‌طور همزمان بالا است. یک روش دیفرانسیل برای تشخیص چنین نقاط، محاسبه انحنای سطح منحنی است:
"بهترین روش این است که سطح انحنای منحنی به صورت زیر محاسبه شود:"
با مقدار formula_70
به این ترتیب، مقادیر مقیاس بزرگتر با گوشه‌های گرد از وسعت فضایی بزرگ همراه خواهد بود در حالی که مقادیر مقیاس کوچکتر با گوشه‌های تیز با وسعت کم فضایی همراه است. این روش اولین آشکارساز گوشه با انتخاب مقیاس خودکار (قبل از «اپراتور هریس-لاپلاس») است و برای ردیابی گوشه‌ها در مقیاس‌های بزرگ در حوزه تصویر استفاده شده‌است و برای تطبیق پاسخ‌های گوشه به لبه‌ها برای محاسبه ویژگی‌های ساختاری تصویر استفاده می‌شود.
مخفف لاپلاسین گوسی LoG و مخفف دیفرانسیل گوسیDoG و مخفف دترمینان هسین DoH می‌باشد.
این آشکارسازها در تشخیص لکه بیشتر توضیح داده شده‌است.
این اپراتورها ممکن است به پاسخ‌های نزدیک به لبه‌ها منجر شوند. به منظور بهبود توانایی تشخیص گوشه در الگوریتم DoG، آشکارساز ویژگی در سیستم SIFT استفاده شده‌است. از یک مرحله پس پردازش اضافی استفاده می‌کند که در آن مقادیر ویژهٔ هسین تصویر در مقیاس تشخیص به روش مشابه موجود در اپراتور هریس مورد بررسی قرار می‌گیرد. اگر نسبت مقادیر ویژه بسیار بالا باشد، پس تصویر محلی به نظر می‌رسد که بسیار شبیه به لبه است، بنابراین این ویژگی رد می‌شود.
دترمینان هسین یک بیان دیفرانسیل کواریانت است و دارای خواص انتخابی مقیاس بهتر در تحولات تصویر افقی نسبت به اپراتور لاپلاسین است. نقاط به‌دست آمده از دترمینان هسین نسبت به لاپلاسین قابلیت تکرارش همچنین راندمان و دقت عملکردی بهتری دارد.
نقاط مطلوب از اپراتور هریس مقیاس چندگانه به دست می‌آید. تصاویری که ورودی به یک سیستم بینایی کامپیوتری را تشکیل می‌دهند، منجر به تحریف چشم‌انداز می‌شوند. برای به دست آوردن اپراتور نقطه ای که نسبت به تحولات چشم‌انداز قوی‌تر است، رویکرد طبیعی این است که یک شناسه ویژگی ایجاد کند که به تحولات وابسته نباشد.
ونگ و بردلی آشکارساز تصویر را یک سطح می‌داند و مکان‌هایی را پیدا می‌کند که انحنای بزرگ در امتداد یک لبه تصویر وجود دارد. به عبارت دیگر، الگوریتم مکان‌هایی را پیدا می‌کند که لبه سرعت آن را تغییر می‌دهد. نمره گوشه، C، توسط
جایی که c مشخص می‌کند لبهٔ آشکارساز چگونه است. نویسندگان به این نکته اشاره می‌کنند که برای کاهش نویز به یک فیلتر ترجیحاً گوسی نیاز است، اولین نوع C لاپلاسین می‌باشد.
SUSAN مخفف کوچک‌ترین هستهٔ جذب نشده‌است.
برای آشکارسازی ویژگی، الگوریتم سوسن یک ماسک دیسک بر روی پیکسل تحت آزمایش قرار می‌دهد، ناحیهٔ ماسک M می‌باشد و پیکسل‌های داخل ماسک به صورتm نشان داده می‌شود. مرکز در m0 قرار دارد. همهٔ پیکسل‌ها به کمک تابع زیر با پیکسل مرکزی مقایسه می‌شود:
که در رابطهٔ فوق t آستانه اختلاف روشنایی است. I میزان شدت روشنایی پیکسل است. ناحیهٔ سوسن مطابق با رابطهٔ زیر محاسبه می‌شود:
اگر c تابع مستطیل باشد، آنگاه n تعداد پیکسل داخل ماسک است که اختلاف شدتش با شدت روشنایی هسته کمتر از حد آستانهٔ t است. پاسخ اپراتور سوسن از رابطهٔ یر به دست می‌آید:
که g نام آستانهٔ هندسی است. به عبارت دیگر اینکه اپراتور سوسن مقدار کوچکی داشته باشد امتیاز مثبت آن تعریف می‌شود.
مقدار t اختلاف شدت روشنایی نقاط نسبت به هسته را مشخص می‌کند قبل از اینکه به عنوان یک بخش خالی مشخص شوند. مقدار g حداقل اندازهٔ بخش خالی را مشخص می‌کند، که اگر g به اندازهٔ کافی بزرگ باشد، آشکارساز لبه می‌شود.
برای شناساگر گوشه، دو مرحله استفاده می‌شود. در مرحلهٔ اول مرکز سوسن مشخص می‌شود، یک گوشهٔ مطلوب مرکزش از هستهٔ الگوریتم سوسن دور می‌باشد. مرحلهٔ دوم این است که همهٔ نقاط روی خط از هسته حول مرکز به خارج لبهٔ ماسک در سوسن هستن
به شیوه‌ای مشابه سوسن، این آشکارساز به‌طور مستقیم تست می‌کند که آیا پچ پیکسل با خواندن پیکسل‌های اطراف، مشابه خود است. formula_79 پیکسل مورد نظر است و formula_80 یک نقطه در دایره است و formula_81formula_79. نقطه‌یformula_83 نقطهٔ مخالف نقطهٔ formula_84 در راستای قطر می‌باشد.
تابع پاسخ به صورت زیر تعریف می‌شود:
این زمانی بزرگ خواهد بود که هیچ مسیری وجود نداشته باشد که در آن پیکسل مرکز مشابه دو پیکسل نزدیک در طول قطر باشد.P یک دایرهٔ برنسهام است که درون‌یابی برای دستیابی به پاسخ‌های ایزوتروپیک استفاده می‌شود.
AST مخفف تست بخش تسریع شده می‌باشد. این تست یک نوع از شناساگر گوشهٔ سوسن است. به جای ارزیابی دیسک دایره ای تنها پیکسل‌هایی در شعاع دایره ای از برسنهام اطراف نقطه کاندید ارزیابی می‌شود. اگر n پیکسل پیوسته حداقل به میزان t از پیکسل مرکزی روشن‌تر باشد یا به میزان t از پیکسل مرکزی تیره‌تر باشد، سپس پیکسل زیر هسته به عنوان یک ویژگی شناخته می‌شود. این تست ویژگی‌های پایدار را گزارش می‌دهد.
اولین الگوریتم شناسایی گوشه مبتنی بر AST به نام FAST می‌باشد، اگرچه که شعاع دایرهٔ برسنهام می‌تواند هر مقداری داشته باشد، اما در الگوریتم FAST مقدار این شعاع ۳ می‌باشد (دایره‌ای با ۱۶ پیکسل) و آزمایش نشان می‌دهد که بهترین نتیجه وقتی به دست می‌آید که n برابر ۹ باشد. این مقدار n کمترین مقداریست که به ازای آن لبه شناسایی نمی‌شود.
Trujillo and Olague یک روشی را معرفی کردند که در آن براساس یک برنامهٔ ژنتیکی اپراتورهای تصویر که می‌توانند نقاط مطلوب را شناسایی کنند را به صورت اتوماتیک سنتز می‌کند. مجموعه‌های ترمینال و تابع شامل عملیات اولیه است که در بسیاری از طرح‌های پیشنهادی که قبلاً پیشنهاد شده‌است رایج است. تابع فیتنس(fitness) میزان پایداری هر اپراتور را از طریق میزان تکرارپذیری‌اش اندازه‌گیری می‌کند و توزیع یکنواخت نقاط شناسایی‌شده در تصویر را افزایش می‌دهد. عملکرد اپراتورهای تکامل یافته به‌طور تجربی با استفاده از آموزش و تست تصاویر پشت سر هم تأیید شده‌است. از این‌رو الگوریتم GP به عنوان الگوریتمی که با عملکرد انسان برای تشخیص نقاط مطلوب در رقابت است، تصور می‌شود.
اپراتور هریس توسط لیندبرگ و لپتیو دراری بعد چهارم شد و formula_52 ماتریس نقطه دوم زمانی را مشخص می‌کند که به صورت زیر تعریف می‌شود:
دترمینان اپراتور هسین به وسیله Willems et al و Lindeberg به فضا-زمان مشترک گسترش یافته‌است، که منجر به معادله دیفرانسیل نرمال شده زیر می‌شود:
Willems et al در اظهار نظرش در رابطهٔ فوق مقدار formula_90 و formula_91را به کار برد اما Lindeberg نشان داد که formula_92 و formula_93 مستلزم خواص انتخاب مقیاس بهتر است به این معنی که سطوح مقیاس انتخاب شده از یک حباب فضایی-زمانی گوسی با محدودهٔ مشخص بهترین تطبیق را ایجاد کند.
اپراتور لاپلاسین به داده‌های ویدیویی فضایی-زمانی توسط Lindeberg افزوده شده و به دو اپراتور فضایی-زمانی زیر می‌افزاید که همچنین مدل‌هایی از زمینه‌های پذیرفته شده نورون‌های غیرقابل انفجار در عقب LGN را تشکیل می‌دهد:
که در اپراتور اول مقادیر پارامترها به صورت formula_90 و formula_97 formula_90 و formula_99.
این قسمت لینک‌های خارجی مراجع برخی از آشکارسازهای توضیح داده شده در بالا را ارائه می‌دهد. این مراجع توسط نویسندگان مقاله ارائه شده‌است که در آن آشکارساز برای اولین بار توصیف شده‌است. این‌ها ممکن است حاوی اطلاعاتی باشد که در مقاله‌های توصیف ویژگی‌ها وجود ندارد یا به‌طور صریح گفته نشده‌است.