تبدیل هاف (Hough Transform) در پردازش تصویر – از صفر تا صد

۲۸۰۰ بازدید
آخرین به‌روزرسانی: ۲۳ اردیبهشت ۱۴۰۲
زمان مطالعه: ۱۰ دقیقه
دانلود PDF مقاله
تبدیل هاف (Hough Transform) در پردازش تصویر – از صفر تا صدتبدیل هاف (Hough Transform) در پردازش تصویر – از صفر تا صد

«تبدیل هاف» (Hough Transform) تکنیکی است که به وسیله آن می‌توان خطوط راست و حتی اشکال دایره‌ای را در یک تصویر تشخیص داد. در این مطلب قصد داریم به بیان نحوه تشخیص خطوط و دایره‌ها در یک تصویر با استفاده از تبدیل هاف بپردازیم و آن را با استفاده از کتابخانه OpenCV در زبان‌های پایتون و نیز ++C و نیز متلب پیاده‌سازی کنیم.

997696

تبدیل هاف چیست؟

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

به عنوان مثال، یک خط را می‌توان فقط به کمک دو پارامتر شیب و عرض از مبدا نشان داد. همچنین دایره با کمک ۳ پارامتر قابل نشان دادن است که عبارتند از مختصات X و Y و نیز شعاع R دایره. تبدیل هاف در یافتن این شکل‌ها در یک تصویر به صورت فوق‌العاده عمل می‌کند. یکی از مهم‌ترین مزایای تبدیل هاف در یافتن خط و دایره در تصویر این است که نسبت به همپوشانی حساس نیست. حال در ادامه قصد داریم به بررسی نحوه کار تبدیل هاف از طریق یک مثال بپردازیم.

تشخیص خط در تصویر با استفاده از تبدیل هاف

در تصویر زیر نمایی از یک خط راست در مختصات قطبی نشان داده شده است.

یک خط راست در مختصات قطبی
یک خط راست در مختصات قطبی

معادله یک خط در مختصات قطبی به صورت زیر نوشته می‌شود:

ρ=xcos(θ)+ysin(θ)\rho = x \cos ( \theta ) + y \sin ( \theta )

در این رابطه، ρ\rho برابر با فاصله عمودی خط از مبدا بر حسب پیکسل و θ\theta زاویه خط با مبدا است که بر حسب رادیان اندازه گرفته می‌شود. این موارد در تصویر فوق نیز به خوبی نشان داده شده است. ممکن است این سوال پیش بیاید که چرا از معادله خط در مختصات دکارتی که به صورت زیر است، استفاده نمی‌کنیم:

y=mx+cy = m x + c

دلیل عدم استفاده از مختصات دکارتی این است که مقدار شیب خط یا m، می‌تواند مقادیر بین - \infty تا \infty را به خود اختصاص دهد، در حالی که در تبدیل هاف مقادیر پارامترها باید محدود باشند. همچنین سوال دیگری که ممکن است در مورد تبدیل هاف پیش بیاید این است که در معادله مربوط به خط در مختصات قطبی، مقدار θ\theta محدود است، اما آیا پارامتر ρ\rho در بازه مقادیر بین 0 تا \infty نیست؟ در پاسخ باید گفت این مقادیر تنها از لحاظ تئوری درست هستند، اما در عمل پارامتر ρ\rho نیز محدود است؛ زیرا خود تصویر محدود است.

انباشتگر (Accumulator)

زمانی که می‌گوییم یک خط در فضای دو بعدی با دو پارامتر ρ\rho و θ\theta مشخص می‌شود، به این معنی است که اگر دو مقدار تصادفی برای پارامترهای ρ\rho و θ\theta انتخاب کنیم، در این صورت یک خط در فضای دو بعدی به دست می‌آید. یک آرایه دو بعدی را در نظر بگیرید که محور x دارای تمام مقادیر ممکن برای θ\theta و محور y دارای تمام مقادیر ممکن برای ρ\rho باشد. هر عضو این آرایه دو بعدی متناظر با یک خط در فضا است. به این آرایه دو بعدی انباشتگر می‌گویند. در تصویر زیر نمایی از این مفهوم نشان داده شده است.

آرایه دو بعدی انباشتگر
آرایه دو بعدی انباشتگر

از مقادیر موجود در آرایه دو بعدی انباشتگر برای جمع‌آوری اطلاعات درباره این امر استفاده می‌کنیم که کدام خطوط در تصویر وجود دارند. سلول بالا سمت چپ، متناظر با (R,0)(- R , 0 ) و سلول پایین سمت راست متناظر با (R,π)( R , \pi ) است. هر چقدر مدارک بیشتری درباره حضور یک خط با پارامتر ρ\rho و θ\theta جمع‌آوری شود، خواهیم دید که  مقادیر درون سلول‌های این آرایه دو بعدی کم کم  (ρ,θ)( \rho , \theta ) افزایش خواهند یافت. برای تشخیص یک خط در تصویر باید گام‌های زیر را انجام دهیم.

گام اول: مقداردهی اولیه (Initialize) آرایه دو بعدی

ابتدا لازم است که یک آرایه انباشتگر بسازیم. تعداد سلول‌هایی که در شبکه حضور دارند، یک پارامتر طراحی است که باید آن را مشخص کرد. حال فرض کنید یک شبکه انباشتگر ۱۰ در ۱۰ در انتخاب کرده‌ایم. این امر بدین معنی است که ρ\rho فقط ۱۰ مقدار متمایز می‌تواند بگیرد، همچنین θ\theta نیز فقط ۱۰ مقدار متفاوت را می‌تواند به خود اختصاص دهد. بنابراین در حالت کلی ما قادر به تشخیص ۱۰۰ خط متفاوت هستیم. البته اندازه انباشتگر که انتخاب می‌کنیم به رزولوشن تصویر نیز بستگی دارد. اما در اینجا و به عنوان شروع یادگیری لازم نیست زیاد راجع به تنظیم صحیح این پارامتر نگران باشید. ابتدا یک مقدار مانند ۲۰ در ۲۰ را انتخاب کنید و نتیجه را با این فرض مشاهده کنید.

گام دوم: تشخیص لبه (Edge Detection)

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

[(x1,y1),(x2,y2)...(xn,yn)][ ( x _ 1 , y _ 1 ), ( x _ 2 , y _ 2 ) . . . (x _ n , y _ n ) ]

گام سوم: انتخاب پیکسل‌های لبه

برای هر پیکسل لبه (x,y)( x , y ) در آرایه فوق، مقدار θ\theta را در بازه ۰ تا π\pi تغییر می‌دهیم و آن را در معادله خط در مختصات قطبی جایگزین می‌کنیم تا یک مقدار برای ρ\rho به دست آید. در تصویر زیر مقادیر θ\theta را در این بازه برای سه پیکسل تغییر داده‌ایم و مقادیر ρ\rho را با استفاده از معادله خط به دست آورده‌ایم. این سه پیکسل توسط سه منحنی رنگی نشان داده شده‌اند.

تغییر مقدار <span class=θ\theta برای سه پیکسل" width="476" height="384">
تغییر مقدار θ\theta برای سه پیکسل

همان طور که در تصویر بالا دیده می‌شود، منحنی‌ها در یک نقطه با همه برخورد می‌کنند که نشان دهنده این است که یک خط با پارامترهای θ=1\theta = 1 و ρ=0.95\rho = 0 . 9 5 از آن نقطه عبور می‌کند. معمولا در یک تصویر صدها پیکسل مربوط به لبه داریم و از انباشتگر برای یافتن تقاطع تمام منحنی‌های ایجاد شده توسط پیکسل‌های لبه استفاده می‌کنیم. در ادامه به بررسی نحوه انجام این کار می‌پردازیم.

فرض کنید که انباشتگر سایز ۲۰ در ۲۰ داشته باشد. بنابراین ۲۰ مقدار متمایز برای θ\theta وجود دارد و در نتیجه برای هر پیکسل لبه (x,y)( x , y ) نیز ۲۰ جفت (ρ,θ)( \rho , \theta ) را با استفاده از معادله قطبی خط خواهیم داشت. مقادیر سلول‌های انباشتگر متناظر با این ۲۰ مقدار (ρ,θ)( \rho , \theta ) به تدریج افزایش می‌یابند. برای هر پیکسل لبه این محاسبات را انجام می‌دهیم و در نتیجه یک انباشتگر خواهیم داشت که دارای اطلاعات کافی درباره تمام خطوط موجود در تصویر است.

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

تشخیص خطوط با تبدیل هاف در OpenCV

در کتابخانه OpenCV تشخیص خط با استفاده از تبدیل هاف را می‌توان با دو تابع HoughLines یا HoughLinesP پیاده‌سازی کرد. HoughLinesP مربوط به نوع دیگری از تبدیل هاف است که «تبدیل هاف احتمالاتی» (Probabilistic Hough Transform) نام دارد. این تابع آرگومان‌های زیر را به عنوان ورودی دریافت می‌کند.

  • edges: خروجی آشکارساز لبه.
  • lines: یک بردار برای ذخیره‌سازی مختصات شروع و پایان خطوط.
  • theta: پارامتر رزولوشن ρ\rho در پیکسل‌ها.
  • threshold: تعداد کمینه نقاط تقاطع برا تشخیص یک خط.

کدهای مربوط به پیاده‌سازی تبدیل هاف در زبان پایتون در ادامه قرار داده شده‌اند:

همچنین برای پیاده‌سازی تبدیل هاف روی یک تصویر به زبان ++C باید به طریق زیر عمل کنیم:

نتایج تشخیص خط با تبدیل هاف

در ادامه تصاویری از نتیجه اعمال تبدیل هاف برای تشخیص خطوط در تصویر نشان داده شده‌اند.

نتایج تشخیص خط با تبدیل هاف
نتایج تشخیص خط با تبدیل هاف

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

تشخیص دایره در تصویر با استفاده از تبدیل هاف

در مورد تشخیص خط با تبدیل هاف، به دو پارامتر (ρ,θ)( \rho , \theta ) نیاز داریم، اما برای تشخیص یک دایره به سه پارامتر نیاز داریم که به صورت زیر هستند:

  • (X,Y)( X , Y ): مختصات موقعیت مرکز دایره
  • r: شعاع دایره

در نتیجه برای تشخیص دایره با تبدیل هاف به سه انباشتگر نیاز داریم که هر بعد انباشتگر متعلق به یکی از پارامترها است. معادله یک دایره را می‌توان به صورت زیر بیان کرد:

(xx0)2+(yy0)2=r2( x - x _0 ) ^ 2 + ( y - y _ 0 ) ^ 2 = r ^ 2

برای تشخیص دایره در یک تصویر گام‌های زیر لازم هستند:

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

در OpenCV از تابع HoughCircles برای تشخیص دایره در تصویر استفاده می‌شود. این تابع پارامترهای زیر را به عنوان ورودی دریافت می‌کند:

  • image: تصویر ورودی
  • method: روش تشخیص
  • mindst: کمینه فاصله بین مراکز دایره‌های تشخیص داده شده.
  • param_1 و param_2: متدهای مخصوص مربوط به روش.
  • min_Radius: کمینه شعاع دایره‌‌هایی که باید تشخیص داده شوند.
  • max_Radius: بیشینه شعاع دایره‌‌هایی که باید تشخیص داده شوند.

حال کدهای مربوط به یافتن دایره در یک تصویر با کمک تبدیل هاف را با زبان پایتون به صورت زیر می‌نویسیم:

همچنین کد یافتن دایره در یک تصویر با کمک تبدیل هاف به زبان ++C به صورت زیر است:

توجه به این نکته ضروری است که تابع HoughCircles الگوریتم تشخیص لبه Canny را به صورت توکار در خود دارد. بنابراین لازم نیست لبه‌ها را به صورت جداگانه تشخیص دهیم.

نتایج تشخیص دایره با تبدیل هاف

در تصاویر زیر نتیجه تشخیص دایره با کمک تبدیل هاف نشان داده شده است.

نتایج تشخیص دایره با تبدیل هاف
نتایج تشخیص دایره با تبدیل هاف

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

نتایج تشخیص دایره با تبدیل هاف
نتایج تشخیص دایره با تبدیل هاف

تبدیل هاف در متلب

در ادامه قصد داریم به بررسی کدهای تبدیل هاف در متلب نیز بپردازیم. برای این کار ابتدا باید تصویر مورد نظر را با دستور زیر بارگذاری کنیم.

توجه کنید که تصویر چرخش داده شده است.

سپس با استفاده از دستور زیر می‌توانیم لبه‌ها را در تصویر پیدا کنیم.

نتیجه به صورت زیر خواهد بود.

نتایج تشخیص لبه
نتایج تشخیص لبه

حال می‌توانیم با دستورات زیر ابتدا تبدیل هاف را روی تصویر انجام دهیم و سپس مقادیر به دست آمده در خروجی تابع را ترسیم کنیم.

تبدیل هاف به صورت زیر خواهد بود.

تبدیل هافِ تصویر
تبدیل هافِ تصویر

حال مقادیر پیک را در ماتریس H تبدیل هاف مشخص می‌کنیم و با دستورات زیر آن ها را رسم می‌کنیم.

نتیجه در تصویر زیر نمایش داده شده است.

محل برخورد خطوط در تبدیل هاف
محل برخورد خطوط در تبدیل هاف

در نهایت با استفاده از تابع houghlines می‌توانیم خطوط به دست آمده با استفاده از تبدیل هاف را ترسیم کنیم.

خطوط تصویر به درستی و با دقت بالایی مشخص می‌شوند.

خطوط در تصویر
خطوط در تصویر

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱۴ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
learnopencvmathworks
دانلود PDF مقاله
۷ دیدگاه برای «تبدیل هاف (Hough Transform) در پردازش تصویر – از صفر تا صد»

درود بر شما و ممنون به خاطر این مطلب مفید
چندتا سوال داشتم
در خروجی هاف دیدیم که تعداد خطوط با توجه به نقاط تقاطع خط های رسم شده در محیط هاف قابل فهم هستند .
چطور تعداد خط ها یا اضلاع را بشماریم
یعنی بگوییم چندتا خط ( ضلع) در تصویر مثلا مربع وجود داشت؟
و آیا دایره ضلع دارد ؟
تبدیل هاف چطور برای شکل دایره ضلع در نظر میگیرد؟!!
میخواهم برنامه ای بنویسم که بتواند مثلث و دایره و مربع را از روی اضلاع تشخیص دهد.


با سلام و احترام؛

با استفاده از قطعه کد زیر می‌توان تعداد خطوط موجود در عکس را پیدا کرد.
import cv2 import numpy as np # خواندن تصویر image = cv2.imread('a.jpg') gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) # لبه‌یابی edges = cv2.Canny(gray, 50, 150, apertureSize=3) # تبدیل هاف lines = cv2.HoughLines(edges, 1, np.pi / 180, 80) # شمارش تعداد خطوط num_lines = len(lines) if lines is not None else 0 print(f"تعداد خطوط: {num_lines}")

مطالعه مطلب «پیدا کردن خط عبور با روش های بینایی کامپیوتر — راهنمای کاربردی» نیز می‌تواند در این مورد برای شما سودمند باشد.

در رابطه با الگوریتم تبدیل هاف برای تشخیص دایره هم می‌توان گفت که به‌دنبال پیدا کردن مراکز و شعاع دایره هستیم.

از همراهی شما با مجله فرادرس سپاس‌گزاریم.

دستور اصلی تبدیل هاف توی متلب رو داخل کد ننوشتین

فقط اشاره ای به این نشده که این الگوریتم به چه میزان و به چه طریقی عملیات چرخش رو روی تصویر اعمال می‌کند.
ممنون

سلام. کد بازبینی و اصلاح شد.
از همراهی و بازخوردتان سپاسگزاریم.

سلام
ممنون از توضیحاتتون
یک سوال در کد متلب
imadjust(rescale(H)) منظورتون از H چیست؟

سلام.
منظور از H تبدیل هاف استاندارد است.
از همراهی شما با مجله فرادرس خوشحالیم.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *