آشکارساز لبه کنی
آشکارساز لبه کنی یک عملگر لبه یابی است که از یک الگوریتم چند مرحله ای برای یافتن دامنه وسیعی از لبه در تصویر استفاده می‌کند. این روش در سال ۱۹۸۶ توسط توسعه یافت. همچنین Canny یک تئوری محاسباتی لبه یابی ایجاد کرد که توضیح می‌دهد روش چگونه کار می‌کند.
آشکارکننده لبه Canny روشی است برای استخراج اطلاعات ساختاری مفید از اشیا بصری و به طرز چشمگیری میزان داده‌هایی که باید پردازش شوند را کاهش می‌دهد. این روش به‌طور گسترده در سیستم‌های بینایی کامپیوتر استفاده شده‌است. Canny دریافت که لازمه‌های اعمال آشکارسازی لبه روی سیستم‌های بینایی گوناگون نسبتاً یکسان است. به این ترتیب، راهکار آشکارسازی لبه برای مشخص کردن این لازمه‌ها می‌تواند در رنج وسیعی از وضعیت‌ها پیاده‌سازی شود. معیارهای کلی برای لبه یابی شامل موارد زیر می‌شوند:
برای تحقق این لازمه‌ها Canny از حساب تغییرات – روشی که تابعی را برای بهینه‌سازی یک تابعی داده شده پیدا می‌کند – استفاده کرد. تابع بهینه در آشکارساز Canny به وسیله جمع ۴ مؤلفه نمایی توصیف می‌شود، اما می‌تواند با مشتق اول یک گاوسی تقریب زده شود.
در بین متدهای لبه یابی توسعه یافته تا کنون، الگوریتم آشکارساز لبه Canny یکی از روش‌های تعریف شده به‌طور دقیقی است که آشکارسازی خوب و قابل اعتمادی را فراهم می‌کند. به دلیل بهینه بودن آن برای تحقق ۳ معیار لبه یابی وسادگی فرایند پیاده‌سازی، این روش یکی از محبوبترین الگوریتم‌ها برای آشکارسازی لبه است.
فرایند الگوریتم آشکارسازی لبه Canny می‌تواند در ۵ مرحله مختلف خلاصه شود:
از آنجائیکه همه نتایج آشکارسازی لبه به سادگی تحت تأثیر نویز در تصویر قرار می‌گیرند، برای جلوگیری از آشکارسازی غلط ناشی از نویز، فیلتر کردن نویزها ضروری است. برای هموار کردن تصویر، یک کرنل گوسی با تصویر پیچش داده می‌شود. این مرحله تصویر را اندکی هموار می‌کند تا آثار نویزهای واضح روی آشکارساز لبه کاهش یابد. معادله کرنل یک فیلتر گوسی به اندازه (2k+۱)×(2k+۱) در زیر آورده شده‌است.
formula_1
این مثالی از یک فیلتر گوسی ۵×۵، که برای ایجاد تصویر مقابل استفاده شده‌است، با ۱٫۴ = formula_2 می‌باشد. (ستاره عملگر پیچش را نشان می‌دهد).
درک این امر که انتخاب اندازه کرنل گوسی روی عملکرد آشکارساز اثر می‌گذارد مهم است. هر چه اندازه بیشتر باشد، آشکارساز حساسیت کمتری نسبت به نویز دارد. به علاوه خطای محلی سازی برای آشکارکردن لبه با افزایش اندازه کرنل فیلتر گوسی اندکی افزایش پیدا می‌کند. اندازه ۵×۵ در بیشتر موارد مناسب است اما می‌تواند بسته به شرایط خاص متفاوت باشد.
لبه یک تصویر ممکن است در راستاهای مختلفی باشد، در نتیجه الگوریتم Canny از 4 فیلتر برای تشخیص لبه‌های افقی، عمودی و قطری در تصویر هموار شده استفاده می‌کند. عملگر لبه یاب (برای مثال , یا )، مشتق اول در راستای افقی (Gx) و عمودی (Gy) بدست می‌دهد. با استفاده از آن‌ها می‌توان گرادیان و راستای لبه را مشخص کرد:
که G با استفاده از تابع و atan2 که تابع عکس تانژات با دو آرگومان است حساب می‌شود. جهت لبه به ۴ راستای عمودی، افقی و قطری (۲ راستا) رند می‌شود (°۰، °۴۵، °۹۰ و °۱۳۵). زاویه مشخصی به جهت لبه در هر ناحیه رنگی نسبت داده می‌شود برای مثال برای θ در بازه [°۰, °۲۲٫۵] یا [°۱۵۷٫۵,°۱۸۰] به °۰ نگاشت می‌شود.
سرکوب غیر بیشینه یک روش نازک کننده لبه است.
سرکوب نقاط غیر بیشینه یک روش برای نازک کردن لبه است. سرکوب نقاط غیر بیشینه برای یافتن «بزرگترین لبه» استفاده می‌شود. پس از اعمال محاسبات گرادیان، لبه بدست آمده از مقدار گرادیان همچنان به‌طور کامل تار است. با توجه به معیار ۳، تنها باید یک پاسخ دقیق به لبه وجود داشته باشد. به این ترتیب سرکوب نقاط غیر بیشینه می‌تواند به سرکوب همه مقادیر گرادیان (با صفر کردن آن‌ها) به جز بیشینه‌های محلی که نشان دهنده مکان‌هایی با سریعترین تغییر در مقدار روشنایی هستند کمک کند. این الگوریتم برای هر پیکسل در تصویر گرادیان به شرح زیر است:
در برخی از پیاده‌سازی‌ها، الگوریتم جهت‌های پیوسته گرادیان را به مجموعه ای از جهت‌های گسسته دسته‌بندی می‌کند، و بعد یک فیلتر 3x3 را روی خروجی مرحله قبل (که قدرت لبه و جهت گرادیان است) حرکت می‌دهد. در هر پیکسل، این الگوریتم قدرت لبه پیکسل مرکزی را سرکوب می‌کند (با صفر کردن مقدار آن) اگر اندازه آن بزرگتر از اندازه دو همسایه آن در راستای گرادیان نباشد. برای مثال،
در پیاده‌سازی‌های دقیقتر، از درون یابی خطی بین دو پیکسل همسایه که بین مسیر گرادیان قرار دارند استفاده می‌شود. برای مثال اگر زاویه گرادیان بین °۸۹ و °۱۸۰ باشد، درون یابی بین گرادیان‌ها در پیکسل‌های شمال و شمال شرق یک مقدار درون یابی شده و درون یابی بین پیکسل‌های جنوب و جنوب غرب یک مقدار دیگر بدست می‌دهد (با استفاده از قواعد پاراگراف آخر). اندازه گرادیان در پیکسل مرکزی باید بزرگتر از هر دو پیکسل که به عنوان لبه در نظر گرفته شده‌اند باشد.
دقت شود که علامت جهت اهمیتی ندارد، یعنی شمال-جنوب با جنوب-شمال و یه همین ترتیب برابر است.
پس از اعمال سرکوب غیر بیشینه، پیکسل‌های لبه باقی مانده، ارائه دقیقتری از لبه‌های واقعی تصویر دارند. اگرچه بعضی از پیکسل لبه‌ها به علت نویز و تغییرات رنگ باقی می‌مانند. برای در نظر گرفتن این پاسخ‌های غیر واقعی، فیلتر کردن پیکسل‌های لبه با مقدار گرادیان ضعیف و نگه داشتن پیکسل‌های لبه با مقدار گرادیان زیاد ضروری است. این کار با انتخاب آستانه کم و زیاد صورت می‌گیرد. اگر گرادیان یک پیکسل لبه بزرگتر از آستانه زیاد باشد پیکسل لبه قوی حساب می‌شود. اگر گرادیان یک پیکسل لبه کوچکتر از آستانه زیاد و بزرگتر از آستانه کم باشد پیکسل لبه ضعیف حساب می‌شود. این دو آستانه به صورت تجربی تعیین می‌شوند و تعریف آن‌ها بستگی به محتوای تصویر ورودی داده شده دارد.
تا اینجا پیکسل‌های لبه قوی قطعاً باید در تصویر لبه نهایی جای بگیرند، زیرا آن‌ها از لبه‌های واقعی در تصویر بدست آمده‌اند. اگر چه بحث‌هایی در مورد پیکسل‌های لبه ضعیف وجود دارد، زیرا این پیکسل‌ها می‌تواند هم از لبه واقعی و هم از تغییرات رنگ/نویز بدست آیند. برای رسیدن به نتیجه دقیق، لبه‌های ضعیف ناشی از تغییرات رنگ یا نویز باید حذف شوند. معمولاً یک پیکسل لبه ضعیف که ناشی از لبه‌های واقعی هستند به پیکسل لبه قوی متصل است در صورتی که پاسخ‌های نویز متصل نیستند. برای دنبال کردن اتصال لبه، به وسیله نگاه کردن به پیکسل لبه قوی و پیکسل‌های همسایگی ۸-اتصاله اعمال می‌شود. از آنجائیکه تنها یک پیکسل لبه قوی در blob نقش دارد، آن نقطه لبه ضعیف می‌تواند به عنوان نقطه ای که باید حفظ شود تشخیص داده شود.
در حالیکه لبه یابی قدیمی Canny روشی نسبتاً ساده ولی دقیق برای مسئله لبه یابی فراهم می‌آورد، برای رسیدن به دقت و مقاومت بیشتر در تشخیص، الگوریتم قدیمی دیگر نمی‌تواند مسئله لبه یابی سخت را حل کند. معایب اصلی الگوریتم قدیمی به صورت زیر خلاصه می‌شود:
برای برطرف کردن این نواقص، بهبود الگوریتم لبه Canny در زیر آمده‌است.
از آنجائیکه لبه و نویز به عنوان سیگنال فرکانس بالا شناسایی می‌شوند، فیلتر گوسی ساده هر دو را هموار می‌کند. اگرچه برای رسیدن به تشخیص لبه واقعی با دقت بالا انتظار می‌رود که همواری بیشتر باید به نویز و همواری کمتر باید به لبه اعمال شود. Bing Wang و Shaosheng Fan از Changsha University of Science and Technology یک فیلتر وفقی توسعه دادند که ناپیوستگی بین مقادیر greyscale در هر پیکسل را ارزیابی می‌کند. هرچه ناپیوستگی بیشتر باشد، مقدار وزن کمتری برای فیلتر هموارکننده در آن نقطه در نظر گرفته می‌شود. متقابلاً هر چه ناپیوستگی بین مقادیر greyscale کمتر باشد، مقدار وزن بیشتری برای فیلتر در نظر گرفته می‌شود. فرایند پیاده‌سازی این فیلتر وفقی در ۵ مرحله می‌تواند خلاصه شود:
formula_8
formula_9
formula_10
برای هموار کردن تصویر که
formula_11
اندازه و جهت گرادیان می‌تواند از طریق عملگرهای لبه یابی متفاوتی محاسبه شود و انتخاب عملگر بر کیفیت نتایج اثر می‌گذارد. به‌طور رایج فیلتر 3x3 انتخاب می‌شود. اگر چه فیلترهای دیگر ممکن است بهتر باشد از جمله فیلتر 5x5 Sobel که نویز را کاهش می‌دهد یا فیلتر که تقارن چرخشی بهتری دارد. انتخاب‌های رایج دیگر (استفاده شده توسط Zhou) و هستند.
برای برطرف کردن چالش‌هایی که در آن تشخیص آستانه دوگانه به صورت تجربی دشوار است، می‌تواند بر تصویر اندازه گرادیان که سرکوب غیر بیشینه شده‌است برای ایجاد آستانه زیاد اعمال شود. آستانه کم معمولاً نصف آستانه زیاد در این حالت تنظیم می‌شود. از آنجائیکه تصویر اندازه گرادیان مقادیر پیوسته بدون بیشینه مشخص دارد، روش Otsu باید برای استفاده از جفت‌های مقدار/تعداد به جای کل هیستگرام وفق داده شود.
با اینکه لبه یابی قدیمی Canny خروجی تشخیص خوبی را با در نظرگرفتن دو معیار اول بدست می‌دهد، اما پاسخ منفرد برای هر لبه را به‌طور دقیق برآورده نمی‌کند. ریخت‌شناسی ریاضی برای باریک کردن لبه شناسایی شده توسط Mallat S و Zhong توسعه داده شد.
به جای فیلتر گوسی و تخمین گرادیان از Curvelets برای محاسبه میدان برداری که جهت‌ها و اندازه‌های آن جهت و قدرت لبه‌ها در تصویر را تقریب می‌زند استفاده شده‌است که در مراحل ۳ تا ۵ الگوریتم Canny اعمال می‌شود. Curvelets سیگنال‌ها را به مولفه‌های جداگانه مقیاس‌های متفاوت تجزیه می‌کند و کاهش مؤلفه‌های مقیاس‌های نرمتر می‌تواند نویز را کاهش دهد.
روشی بهتر برای رسیدن به لبه‌های با دقت زیرپیکسل، استفاده از رویکرد است که سرکوب غیر بیشینه به صورت عبارات مشتق مرتبه دوم و سوم که از محاسبه می‌شوند فرمول بندی می‌شود (Lindeberg 1998). برای شرح با جزئیات مقاله دیده شود.
شرحی تغییرپذیر برای مؤلفه اصلی آشکارساز لبه Canny که پیداکردن گذر از صفر مشتق دوم در طول مسیر گرادیان است، به عنوان نتیجه کمینه سازی تابع Kronrod–Minkowski و بیشینه سازی انتگرال روی تطبیق لبه با میدان گرادیان نشان داده شده‌است (Kimmel and Bruckstein 2003). برای شرح با جزئیات مقاله on regularized Laplacian zero crossings and other optimal edge integrators دیده شود.
الگوریتم Canny شامل چند پارامتر قابل تنظیم است که می‌تواند روی زمان محاسبه و کارایی الگوریتم اثر گذارد.
الگوریتم Canny در شرایط مختلف تطبیق پذیر است. پارامترهای آن این امکان را می‌دهد که این الگوریتم برای شناسایی لبه‌های با مشخصات متفاوت بسته به نیاز خاص مناسب باشد. در مقاله اصلی Canny، مشتق فیلتر بهینه سبب ایجاد یک فیلتر با می‌شود که محاسبه در حوزه مکان را اگر میزان هموارسازی مورد نیاز مهم باشد کند می‌کند (فیلتر در این حالت معادل مکانی بزرگی دارد). به همین علت، معمولاً استفاده از فرم Rachid Deriche فیلتر Canny پیشنهاد می‌شود () که بازگشتی است و می‌تواند در زمان کوتاه و ثابت برای هر میزان از هموار سازی محاسبه شود. فرم دو برای پیاده‌سازی‌های real time در FPGA‌ها یا DSP‌ها یا PCها تعبیه شده مناسب است. در این حالت اگرچه پیاده‌سازی عادی بازگشتی اپراتور Canny تقریب خوبی از تقارن چرخشی نمی‌دهد و در نتیجه در لبه‌های افقی و عمودی بایاس داریم.