تبدیل هاف برای خطوط (Hough Line Transform)

هدف#

در این فصل،

• مفهوم تبدیل هاف (Hough Transform) را درک خواهیم کرد.
• خواهیم دید که چگونه از آن برای تشخیص خطوط در یک تصویر استفاده کنیم.
• توابع زیر را خواهیم دید: cv.HoughLines()، cv.HoughLinesP()

تئوری#

تبدیل هاف (Hough Transform) یک تکنیک محبوب برای تشخیص هر شکلی است، به شرطی که بتوانید آن شکل را به صورت ریاضی نمایش دهید. این روش می‌تواند شکل را حتی اگر کمی شکسته یا تغییر شکل داده باشد نیز تشخیص دهد. خواهیم دید که این روش برای خطوط چگونه کار می‌کند.

یک خط می‌تواند به صورت $y=mx+c$ یا در قالب پارامتری به صورت $\rho =x\cos \theta +y\sin \theta$ نمایش داده شود، که در آن $\rho$ فاصله عمودی از مبدأ مختصات تا خط است، و $\theta$ زاویه‌ای است که این خط عمودی با محور افقی می‌سازد و در جهت مخالف عقربه‌های ساعت اندازه‌گیری می‌شود (این جهت بسته به نحوه نمایش سیستم مختصات متفاوت است. این نمایش در OpenCV استفاده می‌شود). تصویر زیر را مشاهده کنید:

بنابراین اگر خط از پایین مبدأ مختصات عبور کند، rho مثبت و زاویه کمتر از ۱۸۰ درجه خواهد بود. اگر از بالای مبدأ عبور کند، به جای اینکه زاویه‌ای بیشتر از ۱۸۰ درجه داشته باشد، زاویه کمتر از ۱۸۰ درجه در نظر گرفته می‌شود و rho منفی خواهد بود. هر خط عمودی دارای زاویه ۰ درجه و خطوط افقی دارای زاویه ۹۰ درجه خواهند بود.

حال بیایید ببینیم تبدیل هاف برای خطوط چگونه کار می‌کند. هر خطی را می‌توان با این دو عبارت $(\rho ,\theta )$ نمایش داد. پس ابتدا یک آرایه دوبعدی یا جمع‌کننده (accumulator) ایجاد می‌کند (برای نگه داشتن مقادیر دو پارامتر) که در ابتدا روی ۰ تنظیم شده است. فرض کنید ردیف‌ها نشان‌دهنده $\rho$ و ستون‌ها نشان‌دهنده $\theta$ باشند. اندازه آرایه به دقت مورد نیاز بستگی دارد. فرض کنید دقت زوایا را ۱ درجه می‌خواهید، پس به ۱۸۰ ستون نیاز دارید. برای $\rho$، حداکثر فاصله ممکن طول قطر تصویر است. بنابراین با در نظر گرفتن دقت یک پیکسل، تعداد ردیف‌ها می‌تواند برابر طول قطر تصویر باشد.

یک تصویر ۱۰۰x۱۰۰ با یک خط افقی در وسط را در نظر بگیرید. اولین نقطه روی خط را بردارید. مقادیر (x,y) آن را می‌دانید. حال در معادله خط، مقادیر $\theta =0,1,2,....,180$ را قرار دهید و $\rho$ به دست آمده را بررسی کنید. برای هر جفت $(\rho ,\theta )$، مقدار جمع‌کننده در سلول متناظر $(\rho ,\theta )$ را یک واحد افزایش می‌دهیم. بنابراین اکنون در جمع‌کننده، سلول (50,90) = 1 به همراه برخی سلول‌های دیگر خواهیم داشت.

حال دومین نقطه روی خط را بردارید. همان کار بالا را انجام دهید. مقادیر سلول‌های متناظر با (rho, theta) به دست آمده را افزایش دهید. این بار، سلول (50,90) = 2. در واقع کاری که انجام می‌دهید رأی دادن (voting) به مقادیر $(\rho ,\theta )$ است. این فرآیند را برای هر نقطه روی خط ادامه می‌دهید. در هر نقطه، سلول (50,90) افزایش می‌یابد یا به آن رأی داده می‌شود، در حالی که سلول‌های دیگر ممکن است رأی بخورند یا نخورند. به این ترتیب، در پایان، سلول (50,90) بیشترین رأی را خواهد داشت. بنابراین اگر جمع‌کننده را برای حداکثر رأی جستجو کنید، مقدار (50,90) را به دست می‌آورید که نشان می‌دهد در این تصویر خطی به فاصله ۵۰ از مبدأ و با زاویه ۹۰ درجه وجود دارد. این موضوع در انیمیشن زیر به خوبی نمایش داده شده است (منبع تصویر: Amos Storkey )

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

تبدیل هاف در OpenCV#

تمام توضیحات بالا در تابع cv.HoughLines() در OpenCV کپسوله شده است. این تابع به سادگی آرایه‌ای از مقادیر $(\rho ,\theta )$ را برمی‌گرداند. $\rho$ بر حسب پیکسل و $\theta$ بر حسب رادیان اندازه‌گیری می‌شود. پارامتر اول، تصویر ورودی باید یک تصویر باینری (Binary) باشد، بنابراین قبل از اعمال تبدیل هاف، آستانه‌گذاری کنید یا از تشخیص لبه Canny استفاده نمایید. پارامترهای دوم و سوم به ترتیب دقت‌های $\rho$ و $\theta$ هستند. آرگومان چهارم آستانه (threshold) است که حداقل رأی لازم برای در نظر گرفتن یک خط را مشخص می‌کند. به خاطر داشته باشید، تعداد رأی‌ها به تعداد نقاط روی خط بستگی دارد. پس این مقدار نشان‌دهنده حداقل طول خطی است که باید تشخیص داده شود.

import cv2 as cv
import numpy as np

img = cv.imread(cv.samples.findFile('sudoku.png'))
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
edges = cv.Canny(gray,50,150,apertureSize = 3)

lines = cv.HoughLines(edges,1,np.pi/180,200)
for rho, theta in lines.reshape(-1, 2):
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a*rho
    y0 = b*rho
    x1 = int(x0 + 1000*(-b))
    y1 = int(y0 + 1000*(a))
    x2 = int(x0 - 1000*(-b))
    y2 = int(y0 - 1000*(a))

    cv.line(img,(x1,y1),(x2,y2),(0,0,255),2)

cv.imwrite('houghlines3.jpg',img)

نتایج زیر را بررسی کنید:

تبدیل هاف احتمالاتی (Probabilistic Hough Transform)#

در تبدیل هاف، می‌بینید که حتی برای یک خط با دو آرگومان، محاسبات زیادی لازم است. تبدیل هاف احتمالاتی (Probabilistic Hough Transform) بهینه‌سازی تبدیل هاف است که دیدیم. این روش همه نقاط را در نظر نمی‌گیرد. در عوض، تنها یک زیرمجموعه تصادفی از نقاط را که برای تشخیص خط کافی است انتخاب می‌کند. فقط باید آستانه را کاهش دهیم. تصویر زیر را ببینید که تبدیل هاف و تبدیل هاف احتمالاتی را در فضای هاف مقایسه می‌کند. (منبع تصویر: Franck Bettinger's home page )

پیاده‌سازی OpenCV بر اساس مقاله Robust Detection of Lines Using the Progressive Probabilistic Hough Transform توسط Matas, J. و Galambos, C. و Kittler, J.V. است [Matas00.] تابع مورد استفاده cv.HoughLinesP() است. این تابع دو آرگومان جدید دارد:

• minLineLength - حداقل طول خط. قطعه‌خطوطی که از این مقدار کوتاه‌تر باشند رد می‌شوند.
• maxLineGap - حداکثر شکاف مجاز بین قطعه‌خطوط برای اینکه به عنوان یک خط واحد در نظر گرفته شوند.

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

import cv2 as cv
import numpy as np

img = cv.imread(cv.samples.findFile('sudoku.png'))
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
edges = cv.Canny(gray,50,150,apertureSize = 3)
lines = cv.HoughLinesP(edges,1,np.pi/180,100,minLineLength=100,maxLineGap=10)
num_lines, _ = lines.shape
for i in range(num_lines):
    x1, y1, x2, y2 = lines[i]
    cv.line(img,(x1,y1),(x2,y2),(0,255,0),2)

cv.imwrite('houghlines5.jpg',img)

نتایج زیر را ببینید:

منابع اضافی#

1. تبدیل هاف در ویکی‌پدیا