موضوع مقاله: تبدیل هاف دایره‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تبدیل هاف دایره‌ای | مقدمه: مقدمه یک مشکل رایج در بینایی ماشین تعیین موقعیت، تعداد یا جهت اشیاء خاص در تصویر می‌باشد. | ## بخش 1: تبدیل هاف دایره‌ای | اغلب اشیاء مورد علاقه شکل‌هایی غیر از خط دارند مثل دایره، بیضی یا هر شکل دلخواه دیگر. با وجود اینکه پیچیدگی تبدیل هاف با افزایش تعداد پارامترهای مورد نیاز برای توصیف شکل مورد نظر افزایش می یابد، تبدیل عادی و عمومی هاف می‌تواند روی هر نوع شکلی استفاده شود. وبلاگ هوش مصنوعی نمایش پارامتری تبدیل هاف به عنوان تبدیل یک نقطه در صفحه x-y به فضای پارامتری توصیف می‌شود. یک خط راست که از نقاط (x1,y1) و (x2,y2) عبور می‌کند در صفحه x-y با معادله زیر تعریف می‌شود : این رابطه یک تساوی برای خط راست در یک سیستم مختصات کارتِزیَن است که a و b پارامترهای خط هستند. تبدیل هاف برای خط این رابطه را استفاده نمی‌کند زیرا خط عمود بر بردار x دارای مقدار a بینهایت است که سبب می‌شود فضای پارامتری a و b حجم بینهایت داشته باشد. به جای نمایش خط به صورت بالا، خط را در فضای پارامتری به صورت زیر نمایش می‌دهند : در این حالت فضای پارامتری شامل و است که حجم محدود خواهد داشت. دایره در مختصات کارتِزیَن به صورت زیر بیان می‌شود: در مقایسه با خط، دایره در فضای پارامتری راحت‌تر بیان می‌شود زیرا پارامترهای دایره مستقیم می‌تواند به فضای پارامتری ارسال شود. در رابطه بالا a و b مختصات مرکز دایره در راستای محورهای xوy است و r شعاع دایره می‌باشد. نمایش پارامتری رابطه بالا به صورت زیر است : کاملاً واضح است که فضای پارامتری مربوط به دایره بوده در حالیکه فضای پارامتری خط می‌باشد. چون با افزایش پارامترهای مورد نیاز برای تعریف شیء مورد نظر، ابعاد R فضای پارامتری افزایش می یابد، تبدیل هاف پیچیده تر خواهد شد. برای ساده‌سازی فضای پارامتری دایره، شعاع به صورت یک عدد ثابت در این فضا ثبت می‌شود. انباره پروسه یافتن دایره در یک تصویر به کمک تبدیل هاف به صورت زیر است : ابتدا تمام لبه‌ها در تصویر مشخص می‌شوند. | ## بخش 2: تبدیل هاف دایره‌ای | این بخش ارتباطی به تبدیل هاف ندارد و هر تکنیک تشخیص لبه دلخواه مثل سوبل یا کَنی یا هر عمل ریخت‌شناسی دیگر می‌تواند مورد استفاده قرار گیرد. سپس در هر نقطه لبه یک دایره به مرکزیت نقطه مورد نظر با شعاع دلخواه ترسیم می‌شود. این دایره در فضای پارامتری طوری ترسیم می‌شود که محور x مؤلفه a و محور y مؤلفه b و محور z شعاع دایره را مدل می‌کند. در مختصاتی که متعلق به محیط دایره ترسیم شده هستند، مقدار ماتریس انباره که اندازه‌ای برابر با فضای پارامترها دارد، افزایش داده می‌شود. بدین طریق تمامی نقاط لبه تصویر اصلی با ترسیم دایره‌ای به شعاع دلخواه و افزایش مقادیر در انباره، بررسی می‌شوند. پس از این، انباره شامل اعدادی است که بیانگر تعداد دایره‌های عبورکننده از یک مختصات منحصربه‌فرد می‌باشد. بنابراین اعداد بزرگتر که به صورت هوشمند با توجه به شعاع انتخاب می‌شوند، متناظر با مراکز دایره‌های در تصویر اصلی می‌باشند. الگوریتم الگوریتم تبدیل هاف دایره‌ای به صورت زیر خلاصه می‌شود : یافتن لبه ها برای هر نقطه لبه : // تبدیل هاف شروع می‌شود// یک دایره با مرکزیت نقطه لبه با شعاع r رسم می‌شود و در انباره تمام مختصاتی که محیط دایره از آن‌ها عبور می‌کند، افزایش می یابند. // تبدیل هاف تمام می‌شود// پارامترهای پیدا شده (r,a,b) مطابق با نقاط ماکزیمم پیدا شده روی تصویر اصلی مشخص می‌شوند. پیاده‌سازی با توجه به الگوریتم ارائه شده در قسمت 4 می‌توان به پیاده‌سازی الگوریتم اقدام کرد. آرایه انباره که سه بعدی است، در صورتی‌که شعاع ثابت در نظر گرفته نشده باشد، خیلی سریع می‌تواند از لحاظ اطلاعات ذخیره شده رشد پیدا کند. هزینه محاسباتی برای محاسبه کردن تمام دایره‌های مربوط به نقاط لبه با افزایش نقاط لبه افزایش می یابد که تعداد نقاط لبه معمولاً تابعی از اندازه تصویر می‌باشد. | ## بخش 3: تبدیل هاف دایره‌ای | زمان کلی محاسبات تبدیل هاف دایره‌ای در تصاویر بزرگ با نقاط لبه زیاد می‌تواند به سرعت به مقدار مهار نشدنی از زمان برسد. دایره در فضای گسسته با استفاده از رابطه (4) مستقیماً رسم می‌شود، اما یک مشکل وجود دارد. اما این کار سبب ترسیم بیش از یک بار پیکسل‌های لبه شده یا اگر شعاع خیلی بزرگ باشد سبب کمبود پیکسل‌ها می‌شود. برای اطمینان از ترسیم تمام پیکل‌ها، وضوح بایستی بسیار بالا باشد، اما این کار سبب افزایش یافتن هزینه محاسباتی می‌شود. یک روش که می‌تواند هزینه محاسبات را پایین بیاورد، محاسبه سریع مقادیر برای توابع sin و cos با استفاده از جدول مراجعه می‌باشد. به جای استفاده از رابطه (4)، الگوریتم بِرزِنهام را می‌توان برای رسم دایره استفاده کرد. این الگوریتم جهت ترسیم خط یا دایره برای مانیتورهای دیجیتالی بدون مشکل ترسیم بیش از یک بار پیکسل‌ها طراحی شده و برای تبدیل هاف دایره‌ای مناسب می‌باشد . یک ویژگی خوب در این الگوریتم اینست که می‌توان فهمید که تعداد دقیق پیکسل‌های مورد استقاده برای ترسیم دایره چقدر است و این اطلاعات زمانی می‌تواند مناسب باشد که مرکز دایره‌ها از داده‌های انباره پیدا می‌شوند. اگرچه این بحث مربوط به تبدیل هاف نیست ولی برای استخراج اطلاعات دایره‌ها از داده‌های انباره مفید است. اگر دربارهٔ تعداد دایره‌ها و شعاع‌های آن‌ها اطلاعاتی وجود ندارد، این پروسه خیلی دردسر ساز است. یک رویکرد آنست که قله‌های صفحه a و b هر یک متناظر با یک شعاع خاص هستند در انباره داده پیدا شود. اگر ارتفاع قله (ها) در مقایسه با تعداد پیکسل‌های لبه مربوط به دایره‌ای با شعاع خاص برابر باشد، مختصات قله (ها) شاید متناظر مرکز چنین دایره‌ای باشد. | ## جمع‌بندی | اما مثلاً در حالتی که دایره کامل نباشد یا یک شکل بیضی مانند داشته باشیم، مرکز دایره می‌تواند با ارتفاعی کمتر از تعداد پیکسل‌های لبه نمایش داده شود.