مسئله پوش محدب در OpenCV با پایتون و سی پلاس پلاس

نوامبر

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

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

یک Convex Hull یا پوش محدب چیست؟

بیایید عبارت را به دو بخش Convex و Hull بشکنیم.

یک شئ Convex یا محدب، هیچ زاویه داخلی بزرگتر از ۱۸۰ درجه ندارد. یک شکل که Convex نیست، را هم شئ Concave یا مقعر می نامیم. در شکل شماره ۱ مثال هایی از اشکال محدب و مقعر نشان داده شده است.

شکل ۱: مثال هایی از اشکال محدب و مقعر

کلمه Hull یا پوش هم به معنای دور و بیرون شکل یک شئ است.

بنابراین عبارت Convex Hull یک شئ یا گروهی از نقاط یک مرز چسبیده دور شکل و نقاط شکل است که تمام آن را می پوشاند و این پوشش محدب است.

پوش محدب یا Convex Hull اشیا درون شکل شماره ۱ در ادامه رسم شده است.

شکل 2: پوش محدب برای اشیا درون شکل شماره 1

شکل ۲: پوش محدب با رنگ قرمز برای اشیا درون شکل شماره ۱

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

الگوریتم های Gift Wrapping

با فرض داشتن یک مجموعه نقطه که شکلی را تعریف می کنند، چطور می توان پوش محدب آن را پیدا کرد؟ الگوریتم های پیدا کردن پوش محدب اغلب الگوریتم بسته بندی کادو یا Gift Wrapping خوانده می شوند. ویدیوی زیر چند الگوریتم را با ارائه یک پویانمایی عالی توضیح می دهد:

ویدیو را تماشا کردید؟ آسان بود! نه؟

بسیاری از مسائل در نگاه اول آسان به نظر می رسند اما هنگامی که یک سری محدودیت ها در مسئله اعمال می شوند، بسیار پیچیده خواهند شد. به طور مثال، الگوریتم Jarvis March که در ویدیو شرح داده شد، پیچیدگی زمانی برابر با O(nh) دارد که در آن n برابر با نقاط ورودی مسئله (نقاط تشکیل دهنده شکل) است و h هم تعداد نقاط نهایی در پوش محدب است. الگوریتم Chan هم پیچیدگی O(n log h) دارد.

اما آیا داشتن یک الگوریتم با درجه پیچیدگی O(n) ممکن است؟ پاسخ مثبت است، اما تاریخچه پیدا کردن یک الگوریتم با پیچیدگی خطی برای پوش محدب کمی آشفته است!

اولین الگوریتم O(n) توسط Sklansky و در سال ۱۹۷۲ میلادی منتشر شد. اما بعد ها ثابت شد که الگوریتم غلطی است. در میان سال های ۱۹۷۲ و ۱۹۸۹ ، تعداد ۱۶ الگوریتم خطی دیگر منتشر شد که ۷ تای آن ها بعداً غلط شناخته شدند. در این بازه Sklansky یک الگوریتم نادرست دیگر هم در سال ۱۹۸۲ منتشر کرد.

(نقل از نویسنده اصلی) این تاریخچه من را به یاد یک جوک می اندازد که در کالج شنیده ام: هر مسئله دشواری در ریاضیات یک راه حل اشتباه ساده و قابل درک دارد!

در اینجا حالا قضیه از این هم جالب تر می شود! باید بدانید که الگوریتمی که در کتابخانه OpenCV پیاده سازی شده است همانی است که توسط Sklansky (1982) معرفی شد! و پیش تر گفتیم که این الگوریتم هم همیشه و در همه حالات صحیح نیست پس غلط شناخته شد.

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

convexHull در کتابخانه OpenCV

تا به اینجا در مورد الگوریتم های Gift Wrapping برای پیدا کردن پوشه محدب روی یک مجموعه از نقاط صحبت کرده ایم.

اما چطور این الگوریتم های یافتن پوشه محدب را می توان روی تصاویر به کار برد؟

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

قدم اول: خواندن تصاویر ورودی

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

پایتون

src = cv2.imread("sample.jpg", 1) # read input image

سی پلاس پلاس

Mat src;
src = imread("sample.jpg", 1); // read input image

قدم دوم: باینری کردن تصاویر ورودی

همین قدم باینری کردن تصاویر ورودی خود سه مرحله زیر را دارد:

تبدیل فضای رنگ به خاکستری (grayscale)
مات کردن تصویر با افکت blur برای حذف نویزها
تعیین آستانه روی شدت روشنایی برای باینری کردن تصویر

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

پایتون

gray = cv2.cvtColor(src, cv2.COLOR_BGR2GRAY) # convert to grayscale
blur = cv2.blur(gray, (3, 3)) # blur the image
ret, thresh = cv2.threshold(blur, 50, 255, cv2.THRESH_BINARY)

سی پلاس پلاس

Mat gray, blur_image, threshold_output;
cvtColor(src, gray, COLOR_BGR2GRAY); // convert to grayscale
blur(gray, blur_image, Size(3, 3)); // apply blur to grayscaled image
threshold(blur_image, threshold_output, 50, 255, THRESH_BINARY); // apply binary thresholding

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

شکل 3: خروجی اجرای سه مرحله باینری سازی تصویر ورودی

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

قدم سوم: استفاده از findContour برای یافتن خطوط کانتور

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

در اینجا شاید این سوال برای شما پیش آمده باشد که چرا ما صرفاً از روش Edge detection برای پیدا کردن لبه های درون تصویر استفاده نکردیم. می توان جواب را به این صورت بیان کرد که به دلیل علاقمندی ما به نحوه تشکیل این لبه ها توسط نقاط، از تابع findContour بهره می بریم تا در یک لیست نقاط دور این لبه ها را برگرداند.

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

پایتون

# Finding contours for the thresholded image
im2, contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

سی پلاس پلاس

vector< vector<Point> > contours; // list of contour points
vector<Vec4i> hierarchy;
// find contours
findContours(threshold_output, contours, hierarchy, RETR_TREE, CHAIN_APPROX_SIMPLE, Point(0, 0));

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

شکل 4: خطوط کانتور روی لبه های داخل تصویر

شکل ۴: خطوط کانتور روی لبه های داخل تصویر باینری شده

قدم چهارم: یافتن پوش محدب دور کانتورها با convexHull

از آنجا که ما کانتورها را پیدا کرده ایم، حالا می توانیم پوش محدب برای هر لیست مجموعه نقطه از کانتورها را بیابیم. این کار را با تابع convexHull انجام می دهیم.

پایتون

# create hull array for convex hull points
hull = []

# calculate points for each contour
for i in range(len(contours)):
    # creating convex hull object for each contour
    hull.append(cv2.convexHull(contours[i], False))

سی پلاس پلاس

// create hull array for convex hull points
vector< vector<Point> > hull(contours.size());
for(int i = 0; i < contours.size(); i++)
    convexHull(Mat(contours[i]), hull[i], False);

قدم پنجم: ترسیم پوشه محدب

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

پایتون

# create an empty black image
drawing = np.zeros((thresh.shape[0], thresh.shape[1], 3), np.uint8)

# draw contours and hull points
for i in range(len(contours)):
    color_contours = (0, 255, 0) # green - color for contours
    color = (255, 0, 0) # blue - color for convex hull
    # draw ith contour
    cv2.drawContours(drawing, contours, i, color_contours, 1, 8, hierarchy)
    # draw ith convex hull object
    cv2.drawContours(drawing, hull, i, color, 1, 8)

سی پلاس پلاس

// create a blank image (black image)
Mat drawing = Mat::zeros(threshold_output.size(), CV_8UC3); 

for(int i = 0; i < contours.size(); i++) [
    Scalar color_contours = Scalar(0, 255, 0); // green - color for contours
    Scalar color = Scalar(255, 0, 0); // blue - color for convex hull
    // draw ith contour
    drawContours(drawing, contours, i, color_contours, 1, 8, vector<Vec4i>(), 0, Point());
    // draw ith convex hull
    drawContours(drawing, hull, i, color, 1, 8, vector<Vec4i>(), 0, Point());
}

شکل 5: پوشه محدب (سفید) و کانتورها (سبز)

شکل ۵: پوشه محدب (سفید) و کانتورها (سبز)

کاربردهای پوشه محدب

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

مرز مجموعه ای از نقاط یک شئ

تصور کنید که نقاط facial landmarks یا نقاط نشانه ای چهره را دارید، با پیدا کردن دور آنها شما مرز ناحیه اصلی صورت (میان دو گوش، چشم ها و بینی و دهان) را می توانید با یافتن پوشه محدب نقاط landmark بیابید و یک برنامه تعویض صورت روی تصویر بسازید!

شکل 6: پوشه محدب برای نقاط Facial landmarks

شکل ۶: پوشه محدب برای نقاط Facial landmarks

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

جلوگیری از تصادف و برخورد

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

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