آشکارساز لبه کنی
آشکارساز لبه کنی یک عملگر لبه یابی است که از یک الگوریتم چند مرحله ای برای یافتن دامنه وسیعی از لبه در تصویر استفاده میکند. این روش در سال ۱۹۸۶ توسط John F. Canny توسعه یافت. همچنین Canny یک تئوری محاسباتی لبه یابی ایجاد کرد که توضیح میدهد روش چگونه کار میکند.
توسعه الگوریتم Canny
آشکارکننده لبه Canny روشی است برای استخراج اطلاعات ساختاری مفید از اشیا بصری و به طرز چشمگیری میزان دادههایی که باید پردازش شوند را کاهش میدهد. این روش بهطور گسترده در سیستمهای بینایی کامپیوتر استفاده شدهاست. Canny دریافت که لازمههای اعمال آشکارسازی لبه روی سیستمهای بینایی گوناگون نسبتاً یکسان است. به این ترتیب، راهکار آشکارسازی لبه برای مشخص کردن این لازمهها میتواند در رنج وسیعی از وضعیتها پیادهسازی شود. معیارهای کلی برای لبه یابی شامل موارد زیر میشوند:
- آشکارسازی لبه با میزان خطای کم، بدین معنی که آشکارسازی باید تا جایی که ممکن است بیشترین لبههای نشان داده شده در تصویر را به درستی بدست آورد.
- نقطه لبهٔ آشکار شده توسط عملگر باید بهطور دقیق در مرکز لبه متمرکز شده باشد.
- لبه داده شده در تصویر باید یکبار مشخص شود و در صورت امکان، نویز تصویر نباید لبههای نادرست ایجاد کند.
برای تحقق این لازمهها Canny از حساب تغییرات – روشی که تابعی را برای بهینهسازی یک تابعی داده شده پیدا میکند – استفاده کرد. تابع بهینه در آشکارساز Canny به وسیله جمع ۴ مؤلفه نمایی توصیف میشود، اما میتواند با مشتق اول یک گاوسی تقریب زده شود.
در بین متدهای لبه یابی توسعه یافته تا کنون، الگوریتم آشکارساز لبه Canny یکی از روشهای تعریف شده بهطور دقیقی است که آشکارسازی خوب و قابل اعتمادی را فراهم میکند. به دلیل بهینه بودن آن برای تحقق ۳ معیار لبه یابی وسادگی فرایند پیادهسازی، این روش یکی از محبوبترین الگوریتمها برای آشکارسازی لبه است.
فرایند الگوریتم آشکارسازی لبه Canny
فرایند الگوریتم آشکارسازی لبه Canny میتواند در ۵ مرحله مختلف خلاصه شود:
- اعمال فیلتر گوسی برای هموار کردن تصویر جهت حذف نویز.
- یافتن گرادیان شدت روشنایی تصویر.
- اعمال سرکوب نقاط غیر بیشینه جهت خلاص شدن از پاسخ غلط به آشکارسازی لبه.
- اعمال آستانه دوگانه برای تشخیص لبههای بالقوه.
- دنبال کردن لبهها با استفاده از پسماند: نهایی کردن آشکارسازی لبه با سرکوب همه لبههای دیگری که ضعیف هستند و به لبههای قوی متصل نیستند.
فیلتر گوسی
از آنجائیکه همه نتایج آشکارسازی لبه به سادگی تحت تأثیر نویز در تصویر قرار میگیرند، برای جلوگیری از آشکارسازی غلط ناشی از نویز، فیلتر کردن نویزها ضروری است. برای هموار کردن تصویر، یک کرنل گوسی با تصویر پیچش داده میشود. این مرحله تصویر را اندکی هموار میکند تا آثار نویزهای واضح روی آشکارساز لبه کاهش یابد. معادله کرنل یک فیلتر گوسی به اندازه (2k+۱)×(2k+۱) در زیر آورده شدهاست.
این مثالی از یک فیلتر گوسی ۵×۵، که برای ایجاد تصویر مقابل استفاده شدهاست، با ۱٫۴ =
درک این امر که انتخاب اندازه کرنل گوسی روی عملکرد آشکارساز اثر میگذارد مهم است. هر چه اندازه بیشتر باشد، آشکارساز حساسیت کمتری نسبت به نویز دارد. به علاوه خطای محلی سازی برای آشکارکردن لبه با افزایش اندازه کرنل فیلتر گوسی اندکی افزایش پیدا میکند. اندازه ۵×۵ در بیشتر موارد مناسب است اما میتواند بسته به شرایط خاص متفاوت باشد.
یافتن گرادیان شدت روشنایی تصویر
لبه یک تصویر ممکن است در راستاهای مختلفی باشد، در نتیجه الگوریتم Canny از 4 فیلتر برای تشخیص لبههای افقی، عمودی و قطری در تصویر هموار شده استفاده میکند. عملگر لبه یاب (برای مثال Roberts, Prewitt یا Sobel)، مشتق اول در راستای افقی (Gx) و عمودی (Gy) بدست میدهد. با استفاده از آنها میتوان گرادیان و راستای لبه را مشخص کرد:
که G با استفاده از تابع hypot و atan2 که تابع عکس تانژات با دو آرگومان است حساب میشود. جهت لبه به ۴ راستای عمودی، افقی و قطری (۲ راستا) رند میشود (°۰، °۴۵، °۹۰ و °۱۳۵). زاویه مشخصی به جهت لبه در هر ناحیه رنگی نسبت داده میشود برای مثال برای θ در بازه [°۰, °۲۲٫۵] یا [°۱۵۷٫۵,°۱۸۰] به °۰ نگاشت میشود.
سرکوب غیر بیشینه
سرکوب غیر بیشینه یک روش نازک کننده لبه است.
سرکوب نقاط غیر بیشینه یک روش برای نازک کردن لبه است. سرکوب نقاط غیر بیشینه برای یافتن «بزرگترین لبه» استفاده میشود. پس از اعمال محاسبات گرادیان، لبه بدست آمده از مقدار گرادیان همچنان بهطور کامل تار است. با توجه به معیار ۳، تنها باید یک پاسخ دقیق به لبه وجود داشته باشد. به این ترتیب سرکوب نقاط غیر بیشینه میتواند به سرکوب همه مقادیر گرادیان (با صفر کردن آنها) به جز بیشینههای محلی که نشان دهنده مکانهایی با سریعترین تغییر در مقدار روشنایی هستند کمک کند. این الگوریتم برای هر پیکسل در تصویر گرادیان به شرح زیر است:
- مقایسه قدرت لبه پیکسل کنونی با قدرت لبه پیکسل در راستاهای مثبت و منفی گرادیان.
- اگر قدرت لبه پیکسل کنونی در مقایسه با دیگر پیکسلها که در یک راستا (برای مثال یک پیکسل که جهت آن در راستای y است با پیکسلهای بالا و پایین در محور عمودی مقایسه میشود) هستند بزرگترین باشد، مقدار نگه داشته میشود. در غیر اینصورت مقدار سرکوب میشود
در برخی از پیادهسازیها، الگوریتم جهتهای پیوسته گرادیان را به مجموعه ای از جهتهای گسسته دستهبندی میکند، و بعد یک فیلتر 3x3 را روی خروجی مرحله قبل (که قدرت لبه و جهت گرادیان است) حرکت میدهد. در هر پیکسل، این الگوریتم قدرت لبه پیکسل مرکزی را سرکوب میکند (با صفر کردن مقدار آن) اگر اندازه آن بزرگتر از اندازه دو همسایه آن در راستای گرادیان نباشد. برای مثال،
- اگر زاویه رند شده گرادیان صفر (یعنی لبه در راستای جنوبی-شمالی باشد) و اندازه گرادیان بزرگتر از اندازه پیکسلها در جهتهای شرق و غرب باشد به عنوان نقطه روی لبه در نظر گرفته میشود.
- اگر زاویه رند شده گرادیان °۹۰ (یعنی لبه در راستای شرقی-غربی باشد) و اندازه گرادیان بزرگتر از اندازه پیکسلها در جهتهای شمال و جنوب باشد به عنوان نقطه روی لبه در نظر گرفته میشود.
- اگر زاویه رند شده گرادیان °۱۳۵ (یعنی لبه در راستای شمال شرقی-جنوب غربی باشد) و اندازه گرادیان بزرگتر از اندازه پیکسلها در جهتهای شمال غرب و جنوب شرق باشد به عنوان نقطه روی لبه در نظر گرفته میشود.
- اگر زاویه رند شده گرادیان °۴۵ (یعنی لبه در راستای شمال غربی-جنوب شرقی باشد) و اندازه گرادیان بزرگتر از اندازه پیکسلها در جهتهای شمال شرق و جنوب غرب باشد به عنوان نقطه روی لبه در نظر گرفته میشود.
در پیادهسازیهای دقیقتر، از درون یابی خطی بین دو پیکسل همسایه که بین مسیر گرادیان قرار دارند استفاده میشود. برای مثال اگر زاویه گرادیان بین °۸۹ و °۱۸۰ باشد، درون یابی بین گرادیانها در پیکسلهای شمال و شمال شرق یک مقدار درون یابی شده و درون یابی بین پیکسلهای جنوب و جنوب غرب یک مقدار دیگر بدست میدهد (با استفاده از قواعد پاراگراف آخر). اندازه گرادیان در پیکسل مرکزی باید بزرگتر از هر دو پیکسل که به عنوان لبه در نظر گرفته شدهاند باشد.
دقت شود که علامت جهت اهمیتی ندارد، یعنی شمال-جنوب با جنوب-شمال و یه همین ترتیب برابر است.
آستانه گذاری دوگانه
پس از اعمال سرکوب غیر بیشینه، پیکسلهای لبه باقی مانده، ارائه دقیقتری از لبههای واقعی تصویر دارند. اگرچه بعضی از پیکسل لبهها به علت نویز و تغییرات رنگ باقی میمانند. برای در نظر گرفتن این پاسخهای غیر واقعی، فیلتر کردن پیکسلهای لبه با مقدار گرادیان ضعیف و نگه داشتن پیکسلهای لبه با مقدار گرادیان زیاد ضروری است. این کار با انتخاب آستانه کم و زیاد صورت میگیرد. اگر گرادیان یک پیکسل لبه بزرگتر از آستانه زیاد باشد پیکسل لبه قوی حساب میشود. اگر گرادیان یک پیکسل لبه کوچکتر از آستانه زیاد و بزرگتر از آستانه کم باشد پیکسل لبه ضعیف حساب میشود. این دو آستانه به صورت تجربی تعیین میشوند و تعریف آنها بستگی به محتوای تصویر ورودی داده شده دارد.
دنبال کردن لبه به وسیله پسماند
تا اینجا پیکسلهای لبه قوی قطعاً باید در تصویر لبه نهایی جای بگیرند، زیرا آنها از لبههای واقعی در تصویر بدست آمدهاند. اگر چه بحثهایی در مورد پیکسلهای لبه ضعیف وجود دارد، زیرا این پیکسلها میتواند هم از لبه واقعی و هم از تغییرات رنگ/نویز بدست آیند. برای رسیدن به نتیجه دقیق، لبههای ضعیف ناشی از تغییرات رنگ یا نویز باید حذف شوند. معمولاً یک پیکسل لبه ضعیف که ناشی از لبههای واقعی هستند به پیکسل لبه قوی متصل است در صورتی که پاسخهای نویز متصل نیستند. برای دنبال کردن اتصال لبه، آنالیز blob به وسیله نگاه کردن به پیکسل لبه قوی و پیکسلهای همسایگی ۸-اتصاله اعمال میشود. از آنجائیکه تنها یک پیکسل لبه قوی در blob نقش دارد، آن نقطه لبه ضعیف میتواند به عنوان نقطه ای که باید حفظ شود تشخیص داده شود.
بهبود در لبه یابی Canny
در حالیکه لبه یابی قدیمی Canny روشی نسبتاً ساده ولی دقیق برای مسئله لبه یابی فراهم میآورد، برای رسیدن به دقت و مقاومت بیشتر در تشخیص، الگوریتم قدیمی دیگر نمیتواند مسئله لبه یابی سخت را حل کند. معایب اصلی الگوریتم قدیمی به صورت زیر خلاصه میشود:
- فیلتر گوسی برای هموار کردن نویز استفاده میشود اما این فیلتر سبب هموار شدن لبهها نیز میشود که به عنوان ویژگیهای با فرکانس بالا در نظر گرفته میشوند. این سبب افزایش احتمال از دست دادن لبههای ضعیف و ظاهر شدن لبههای ایزوله شده در خروجی میشود.
- برای محاسبه اندازه گرادیان، روش قدیمی لبه یابی Canny از مرکز در یک پنجره همسایگی کوچک ۳×۳ برای محاسبه مقدار محدود میانگین تفاوت استفاده میکند تا اندازه گرادیان را بدست دهد. این روش حساس به نویز است و میتواند به راحتی لبههای غلط را تشخیص و لبههای واقعی را از دست دهد.
- در الگوریتم قدیمی لبه یابی Canny، دو آستانه ثابت سراسری برای فیلتر کردن لبههای غلط تصویر وجود دارد. اگر چه زمانی که تصویر پیچیده شود، نواحی محلی مختلف به آستانه بسیار متفاوتی برای پیدا کردن صحیح لبههای حقیقی نیاز دارند. به علاوه مقادیر آستانه سراسری در روش قدیمی به صورت دستی در طی آزمایشها مشخص میشوند که سبب پیچیدگی محاسبات، زمانی که با تعداد زیادی تصاویر سر و کار داریم میشود.
- نتیجه تشخیص قدیمی نمیتواند منجر به یک پاسخ منفرد رضایتبخش با دقت بالا برای هر لبه شود و پاسخهای چند نقطه ای ظاهر میشوند.
برای برطرف کردن این نواقص، بهبود الگوریتم لبه Canny در زیر آمدهاست.
جایگزین کردن فیلتر گوسی
از آنجائیکه لبه و نویز به عنوان سیگنال فرکانس بالا شناسایی میشوند، فیلتر گوسی ساده هر دو را هموار میکند. اگرچه برای رسیدن به تشخیص لبه واقعی با دقت بالا انتظار میرود که همواری بیشتر باید به نویز و همواری کمتر باید به لبه اعمال شود. Bing Wang و Shaosheng Fan از Changsha University of Science and Technology یک فیلتر وفقی توسعه دادند که ناپیوستگی بین مقادیر greyscale در هر پیکسل را ارزیابی میکند. هرچه ناپیوستگی بیشتر باشد، مقدار وزن کمتری برای فیلتر هموارکننده در آن نقطه در نظر گرفته میشود. متقابلاً هر چه ناپیوستگی بین مقادیر greyscale کمتر باشد، مقدار وزن بیشتری برای فیلتر در نظر گرفته میشود. فرایند پیادهسازی این فیلتر وفقی در ۵ مرحله میتواند خلاصه شود:
- k = ۱، تعداد تکرار n وضریب اندازه لبه h در نظر گرفته میشود.
- مقادیر گرادیان ومحاسبه شود.
- وزن بر اساس فرمول زیر محاسبه شود.
- ۴. رابطه فیلتر برای هموار کردن تصویر برابر است با:
برای هموار کردن تصویر که
- ۵. زمانی که k = n تکرار را متوقف کن در غیر اینصورت k = k+1، و به مرحله ۲ بازگرد.
بهبود در محاسبه جهت و اندازه گرادیان
اندازه و جهت گرادیان میتواند از طریق عملگرهای لبه یابی متفاوتی محاسبه شود و انتخاب عملگر بر کیفیت نتایج اثر میگذارد. بهطور رایج فیلتر 3x3 Sobel انتخاب میشود. اگر چه فیلترهای دیگر ممکن است بهتر باشد از جمله فیلتر 5x5 Sobel که نویز را کاهش میدهد یا فیلتر Scharr که تقارن چرخشی بهتری دارد. انتخابهای رایج دیگر Prewitt (استفاده شده توسط Zhou) و Roberts Cross هستند.
روش مقاوم برای تعیین مقدار آستانه دوگانه
برای برطرف کردن چالشهایی که در آن تشخیص آستانه دوگانه به صورت تجربی دشوار است، روش Otsu میتواند بر تصویر اندازه گرادیان که سرکوب غیر بیشینه شدهاست برای ایجاد آستانه زیاد اعمال شود. آستانه کم معمولاً نصف آستانه زیاد در این حالت تنظیم میشود. از آنجائیکه تصویر اندازه گرادیان مقادیر پیوسته بدون بیشینه مشخص دارد، روش Otsu باید برای استفاده از جفتهای مقدار/تعداد به جای کل هیستگرام وفق داده شود.
نازک کردن لبه
با اینکه لبه یابی قدیمی Canny خروجی تشخیص خوبی را با در نظرگرفتن دو معیار اول بدست میدهد، اما پاسخ منفرد برای هر لبه را بهطور دقیق برآورده نمیکند. ریختشناسی ریاضی برای باریک کردن لبه شناسایی شده توسط Mallat S و Zhong توسعه داده شد.
استفاده از Curvelets
به جای فیلتر گوسی و تخمین گرادیان از Curvelets برای محاسبه میدان برداری که جهتها و اندازههای آن جهت و قدرت لبهها در تصویر را تقریب میزند استفاده شدهاست که در مراحل ۳ تا ۵ الگوریتم Canny اعمال میشود. Curvelets سیگنالها را به مولفههای جداگانه مقیاسهای متفاوت تجزیه میکند و کاهش مؤلفههای مقیاسهای نرمتر میتواند نویز را کاهش دهد.
فرمول بندی هندسی تفاضلی لبه یاب Canny
روشی بهتر برای رسیدن به لبههای با دقت زیرپیکسل، استفاده از رویکرد لبه یابی تفاضلی است که سرکوب غیر بیشینه به صورت عبارات مشتق مرتبه دوم و سوم که از فضای مقیاس محاسبه میشوند فرمول بندی میشود (Lindeberg 1998). برای شرح با جزئیات مقاله لبه یابی دیده شود.
فرمول بندی تغییرپذیر آشکارساز لبه Haralick–Canny
شرحی تغییرپذیر برای مؤلفه اصلی آشکارساز لبه Canny که پیداکردن گذر از صفر مشتق دوم در طول مسیر گرادیان است، به عنوان نتیجه کمینه سازی تابع Kronrod–Minkowski و بیشینه سازی انتگرال روی تطبیق لبه با میدان گرادیان نشان داده شدهاست (Kimmel and Bruckstein 2003). برای شرح با جزئیات مقاله on regularized Laplacian zero crossings and other optimal edge integrators دیده شود.
پارامترها
الگوریتم Canny شامل چند پارامتر قابل تنظیم است که میتواند روی زمان محاسبه و کارایی الگوریتم اثر گذارد.
- اندازه فیلتر گوسی: فیلتر هموارسازی که در مرحله اول استفاده میشود مستقیماً روی نتایج الگوریتم Canny اثر میگذارد. فیلتر کوچکتر سبب تار شدن کمتر میشود و امکان آشکارسازی خطوط تیز و کوچک را فراهم میکند. فیلتر بزرگتر باعث تار شدن بیشتر میشود و مقدار یک پیکسل را در ناحیه بزرگی از تصویر پراکنده میکند. شعاعهای محوسازی بزرگتر برای آشکار ساختن لبههای نرمتر و بزرگتر کاربردی است – برای مثال لبههای یک رنگین کمان.
- آستانه: استفاده از دو آستانه با پسماند نسبت به رویکرد تک آستانه ای انعطافپذیری بیشتری دارد اما مشکلات عمومی رویکرد آستانه گذاری همچنان وجود دارند. آستانه بالا سبب از دست رفتن اطلاعات مهم میشود. از طرفی دیگر آستانه کم سبب تشخیص اطلاعات غلط و نامربوط (نظیر نویز) به عنوان اطلاعات مهم میشود. انتخاب آستانه عمومی که برای همه تصاویر نتیجه خوب بدست دهد دشوار است. همچنان هیج تلاش و رویکرد آزمایش شدهای برای این مسئله وجود ندارد.
جمعبندی
الگوریتم Canny در شرایط مختلف تطبیق پذیر است. پارامترهای آن این امکان را میدهد که این الگوریتم برای شناسایی لبههای با مشخصات متفاوت بسته به نیاز خاص مناسب باشد. در مقاله اصلی Canny، مشتق فیلتر بهینه سبب ایجاد یک فیلتر با پاسخ ضربه محدود میشود که محاسبه در حوزه مکان را اگر میزان هموارسازی مورد نیاز مهم باشد کند میکند (فیلتر در این حالت معادل مکانی بزرگی دارد). به همین علت، معمولاً استفاده از فرم پاسخ ضربه نامحدود Rachid Deriche فیلتر Canny پیشنهاد میشود (آشکارساز Canny-Deriche) که بازگشتی است و میتواند در زمان کوتاه و ثابت برای هر میزان از هموار سازی محاسبه شود. فرم دو برای پیادهسازیهای real time در FPGAها یا DSPها یا PCها تعبیه شده مناسب است. در این حالت اگرچه پیادهسازی عادی بازگشتی اپراتور Canny تقریب خوبی از تقارن چرخشی نمیدهد و در نتیجه در لبههای افقی و عمودی بایاس داریم.
جستارهای وابسته
منابع
- Canny, J. , A Computational Approach To Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986.
- R. Deriche, Using Canny's criteria to derive a recursively implemented optimal edge detector, Int. J. Computer Vision, Vol. 1, pp. 167–187, April 1987.
- Lindeberg, Tony "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, 30, 2, pp 117—154, 1998. (Includes the differential approach to non-maximum suppression.)
- Kimmel, Ron and Bruckstein, Alfred M. "On regularized Laplacian zero crossings and other optimal edge integrators", International Journal of Computer Vision, 53(3):225–243, 2003. (Includes the geometric variational interpretation for the Haralick–Canny edge detector.)
- Moeslund, T. (2009, March 23). Canny Edge Detection. Retrieved December 3, 2014
- Thomas B. Moeslund. Image and Video Processing. اوت ۲۰۰۸
- Green, B. (2002, January 1). Canny Edge Detection Tutorial. Retrieved December 3, 2014; archived here
- Li, Q. , Wang, B. , & Fan, S. (2009). Browse Conference Publications Computer Science and Engineer … Help Working with Abstracts An Improved CANNY Edge Detection Algorithm. In 2009 Second International Workshop on Computer Science and Engineering proceedings: WCSE 2009: 28–30 October 2009, Qingdao, China (pp. 497–500). Los Alamitos, CA: IEEE Computer Society
- Mallat S, Zhong S. Characterization of Signals from Multi scale Edges [J]. IEEE Trans on PAMI, 1992, 14 (7):710-732.
- Zhou, P. , Ye, W. , & Wang, Q. (2011). An Improved Canny Algorithm for Edge Detection. Journal of Computational Information Systems, 7(5), 1516-1523.
- Otsu N. A threshold selection method from gray-level histograms بایگانیشده در ۷ مارس ۲۰۱۹ توسط Wayback Machine. IEEE Trans Systems, Man and Cybernetics,9(1):62-66,1979.
- Gebäck1, T. & Koumoutsakos, P. "Edge detection in microscopy images using curvelets" BMC Bioinformatics, 10: 75, 2009.
پیوند به بیرون
- John Canny's home page
- Publication List of Rachid Deriche
- Journal Publications of Ron Kimmel
- Easy-to-follow MIT licensed c implementation
- Canny edge detection in c++ OpenCV
- Canny edge detection in Python OpenCV بایگانیشده در ۲۹ آوریل ۲۰۱۴ توسط Wayback Machine
- Free Java implementation of Canny edge detector
- Canny edge detector in Mathematica
- Edge detection in MATLAB
- Canny edge detector implementation in ActionScript for the Flash Platform
- On-line Canny edge detector
- Canny Edge World - example video