نمایش/عدم نمایش سایدبار
رفتن به بالای صفحه
أَللّهُمَّ ارْزُقْنی شَفاعَةَ الْحُسَیْنِ یَومَ الْوُرُودِ

آموزش ماژول Planar Subdivision در OpenCV

به نام خدا : ان شاء الله که مطلب کامل و مفیدی در این زمینه بنویسم؛ این ماژول، زیر مجموعه ای از ماژول Image Processing هستش؛ تو این مطلب اول درباره مثلث بندی دلونی و نمودار ورنوی صحبت میکنیم و بعد میریم سراغ توضیح توابع کلاس Subdiv2D، یه چندتا کد نمونه ساده هم قرار میدیم برا آشنایی بیشتر با کلاس فوق و نحوه کار با توابع.

آموزش ماژول Planar Subdivision در OpenCV

 

توضیح اصطلاحات استفاده شده در این مطلب

1) دایره محیطی چیست؟

دایره محیطی ( Circumscribed Circle و یا Circumcircle ) از یک چندضلعی، دایره ای است که از تمام رئوس آن چندضلعی میگذرد؛ مرکز این دایره را «مرکز دایره محیطی» ( Circumcenter ) و شعاعش را «شعاع دایره محیطی» ( Circumradius ) مینامند.

همه چندضلعی‌ها لزوماً دایره محیطی ندارند؛ چندضلعی که دایره محیطی داشته باشد را «چندضلعی محاطی» ( چون توسط یک دایره احاطه شده )، «چندضلعی دایره‌ای» ( Cyclic Polygon )، یا «چندضلعی هم‌دایره» ( Concyclic Polygon ) نیز مینامند، چرا که رئوس آن هم‌دایره اند؛ تمام مثلث‌ها، تمامی چندضلعی‌های ساده منتظم، تمام مستطیل‌ها، تمام ذوزنقه‌های متساوی الساقین، و همچنین تمام کایت‌های راست‌گوشه جزو چندضلعی‌های محاطی اند.

تصویر زیر : دایره محیطی C، و مرکز دایره محیطی O مربوط به یک چندجمله‌ای محاطی P :

Circumscribed Circle

 

مثلث بندی دلونی ( Delaunay Triangulation )

مثلث بندی دلونی ( Delaunay Triangulation )

یک مثلث بندی دلونی ( دیلانی ) برای یک مجموعه از نقاط به نام P در یک صفحه، یک مثلث بندی به نام (DT(P است به نحوی که هیچ یک از نقاط P درون هیچ یک از دایره های محیطی مثلثهای (DT(P نباشد؛ این مثلث بندی کمینه زاویه‌های مثلثها را به بیشترین مقدار ممکن می‌رساند و به این ترتیب از به وجود آمدن مثلث‌های باریک جلوگیری میکند؛ این مثلث بندی توسط Boris Delaunay در سال 1934 ابداع شد.

تصاویر زیر با فرمت SVG هستن، برای دیدن در اندازه بزرگتر، در صفحه جدید بازشون کنید! ( محدودیت zoom ندارند تصاویر SVG )

  • تصویر 1 : مثلث بندی دلونی با دوایر محیطی.
  • تصویر 2 : مرکز دوایر محیطی رسم شده.
  • تصویر 3 : با وصل کردن مراکز دوایر محیطی میتوان دیاگرام ورونی را تشکیل داد؛ فلذا : مثلث بندی Delaunay با خطوط سیاه و نمودار Voronoi با خطوط قرمز مشخص شده است!
تصویر 3 تصویر 2 تصویر 1
Delaunay Voronoi Delaunay Triangulation Delaunay Triangulation
نمودار ورنوی ( Voronoi diagram )

نمودار ورنوی ( Voronoi diagram )

نمودار ورنوی صفحه ( plane ) را به تعدادی ناحیه تقسیم میکند؛ به این نواحی، سلول‌های ورونوی ( Voronoi cell ) گفته میشود؛ برای هر نقطه از مجموعه نقاط، یک ناحیه تعریف میشود؛ تمام نقاط داخل هر ناحیه ای به نقطه تولیدکننده آن ناحیه نزدیکتر میباشد!؛ از کاربردهای این دیاگرام در مثلث بندی دلونی ( Delaunay triangulations ) میباشد.

نمودار ورنوی ( Voronoi diagram )

کاربردهای نمودار ورونوی ( Voronoi diagram applications )

کاربردهای نمودار ورونوی ( Voronoi diagram applications )

لیست تقریبا جامعی از این کاربرد ها رو میتونید در ویکی پدیا ( Voronoi diagram ) مشاهده کنید؛ چون کاربرهاش تخصصی و تو رشته های مختلف هستش، اینجا هم بنویسم کسی چیزی متوجه نمیشه همونطور که خودم هم کاربردهاشو متوجه نشدم! ( درک کاربردها تو حوزه های تخصصی با 1 خط توضیح.... )

این لینک هم کاربرد نمودار ورونوی تو حوضه هوش مصنوعی ( AI = Artificial Intelligence ) در بحث بازی سازی مثال زده : نمودار ورونی یا Voronoi Diagram چیست؟

 

توضیح توابع کلاس Subdiv2D

به کمک این کلاس میتونیم نقاطی به شیء ساخته شده از کلاس فوق بدیم تا برامون «مثلث بندی دلونی» و «نمودار Voronoi» رو محاسبه و ایجاد کنه و…

تقسیم‌بندی‌هایی که این کلاس انجام میده رو می‌توان برای تبدیل یک صفحه به تکه یی سه بعدی ( 3D piece-wise )، تغییر شکل ( morphing )، مکان‌یابی سریع نقاط روی صفحه، ساختن نمودارهای خاص ( مانند NNG و یا  RNG ) و… استفاده کرد.

1) سازنده Subdiv2D

1) سازنده Subdiv2D : ایجاد شیء از کلاس Subdiv2D؛ اگر از تعریف اول استفاده کنید، برای ایجاد یک Delaunay subdivision خالی، باید تابع initDelaunay رو هم فراخونی کنید :

توضیح پارامترها :

rect : مستطیلی که شامل تمام نقاط دو بعدی است که قرار است به subdivision اضافه شوند.

2) تابع initDelaunay

2) تابع initDelaunay : در قسمت سازنده ها، دربارش صحبت کردیم.

3) تابع insert

3) تابع insert : اضافه کردن نقطه/نقاط به مثلث بندی دلونی ( Delaunay Triangulation )؛ اگه نقطه تکراری به تابع بدید، نقطه فوق رو اضافه نمیکنه؛ تابع اولی، در خروجی، ID نقطه فوق رو برمیگردونه.

به کمک تابع اولی، نقاط رو دونه دونه وارد میکنید و در خروجی این تابع، شناسه راس ( vertex id ) هم return میشه، برای استفاده ازش به صورت زیر عمل کنید :

به کمک تابع دومی هم میتونید تمام نقاط رو یکجا وارد کنید که خب تو این تابع دیگه شناسه راس ( vertex id ) ها رو ارسال نمیکنه، برای استفاده ازش به صورت زیر عمل کنید :

4) تابع getTriangleList

4) تابع getTriangleList : دریافت لیست مثلث های Delaunay؛ این تابع برداری از نوع Vec6f به ما میده، که هر Vec6f، حاوی 6 مقدار هستش؛ که این 6 تا مقدار حاوی : 3 تا مقادر X و 3 تا مقدار Y، که میشن مختصات 3 تا نقطه!؛ فلذا هر Vec6f به ما مختصات 3 نقطه رو میده ( رئوس مثلث رو میده! )

برای رسم مثلث بندی دلونی ( Delaunay Triangulation ) از تابع زیر استفاده میکنیم :

5) تابع getVoronoiFacetList

5) تابع getVoronoiFacetList : دریافت لیست چند ظلعی ( facet ) های Voronoi؛

توضیح پارامترها :

  • idx : لیست رئوس ( نقاطی ) که میخواید برگشت داده بشه رو تعین کنید، که خب باید لیستی از ID نقاط مدنظر رو به این پارامتر بدید؛ اگه تمام رئوس رو میخواید، بردار خالی به این پارامتر بدید.
  • facetList : برداری حاوی چند ظلعی های ورونوی.
  • facetCenters : بردار خروجی نقاط مرکزی ورونوی ( این نقاط، همون نقاطی هستند که به کمک تابع insert به شیء مون اضافه کردیم ).

برای رسم نمودار ورنوی ( Voronoi diagram ) از تابع زیر استفاده میکنیم :

توابع اصلی رو در بالا گفتم، از اینجا به بعد توابع فرعی رو توضیح میدم…

6) تابع getEdgeList

6) تابع getEdgeList : تو نمودار Delaunay، یه سری مثلث داریم، که خب هر مثلثی از 3 ضلع تشکل شده، به این ضلع ها، لبه ( edge ) میگن؛ برای خوندن لیست این لبه ها، از این تابع استفاده میکنیم؛ که لیستی از Vec4f ها بهمون میده که هر Vec4f حاوی 4 تا مقدار هستش، 2 تا X و 2 تا Y، که میشن مختصات 2 تا نقطه، که مختصات رئوس لبه فوق هستند.

برای خوندن لیست این لبه ها، و نمایششون از کد زیر میتونید استفاده کنید ( در کد زیر، یه عکس از ورودی گرفتم، یه سری نقاط تصادفی ایجاد کردم، شیء از کلاس Subdiv2D ایجاد کردم، نقاطی که ایجاد کردم رو با رنگ قرمز رسم کردم، بعد لبه های نمودار Delaunay رو خوندم و بعد با رنگ آبی رسمشون کردم، تمام! ) :

7) تابع findNearest

7) تابع findNearest : به کمک این تابع میتونید نزدیک ترین نقطه ( نقاطی که قبلا به کمک تابع insert وارد شیء cv::Subdiv2D کرده بودید ) به نقطه مدنظرتون ( که به تابع میدید ) رو پیدا کنید.

توضیح پارامترها و خروجی :

  • pt : نقطه ورودی. ( پارامتر ورودی )
  • nearestPt : نزدیک ترین نطقه به pt. ( پارامتر خروجی )
  • خروجی تابع : vertex ID

برای درک هرچه بهتر این تابع، کد زیر رو بررسی و تست کنید :

نتیجه کد بالا : 

آموزش ماژول Planar Subdivision در OpenCV

8) تابع locate

8) تابع locate : مکان یک نقطه در یک مثلث دلونی را برمی‌گرداند؛ پارامتر pt، نقطه مدنظر ما هستش، پارامتر های خروجی edge و vertex هم اختیاری هستن.

خروجی تابع فوق رو به کمک enum زیر میخونیم :

مثلا : cv::Subdiv2D::PTLOC_VERTEX

توضح آیتم ها :

  • PTLOC_ERROR : خطای مکان نقطه!؛ هرکاری کردم نتونستم این خطا رو ایجاد کنم! نمیدونم تحت چه شراطی ایجاد میشه.
  • PTLOC_OUTSIDE_RECT : زمانی که نطقه ما خارج از 4 ظلعی subdivision bounding باشه ( این 4 ظلعی رو موقع ایجاد شیء به عنوان پارامتر ورودی به شیء میدید، یا به تابع initDelaunay مدید )
  • PTLOC_INSIDE : زمانی که نقطه ما روی facet های نمودار Voronoi قرار بگیره.
  • PTLOC_VERTEX : زمانی که نطقه ما روی یکی از نقاط subdivision vertices ( نقاطی که به کمک تابع insert وارد کردید ) قرار بگیره.
  • PTLOC_ON_EDGE : زمانی که نطقه ما روی لبه ( edge ) های مثلث بندی دلونی قرار بگیره.

 

برای مثال، این کد رو تست کنید :

چیزی که در خروجی چاپ میشه :

اینم از تصاویر خروجی :

مثلث بندی دلونی ( Delaunay Triangulation ) نمودار ورونوی ( Voronoi diagram )
9) getVertex

9) getVertex : خوندن موقعیت یک راس ( vertex ) به کمک شناسه اش ( vertex ID )؛ با پارامتر اختیاری firstEdge ( که خروجی هستش ) فعلا کاری نداریم ( تو مثالی که در ادامه قرار میدم )

حالا شاید سوال کنید که شناسه راس ( vertex ID ) ها رو از کجا گیر بیاریم؟ به قسمت توضیحات "تابع insert" مراجعه کنید؛ برا دیدن نحوه استفاده از این تابع، کد زیر رو ببینید :

نتیجه کد بالا :

آموزش ماژول Planar Subdivision در OpenCV

10) بقیه توابع

10) بقیه توابع : این توابع مربوط به edge ها هستند که خب حوصلم نشد دربارشون مطالعه کنم!

در تابع getEdge، از enum زیر استفاده میکنیم :

و اینم عکس راهنمای این تابع و enum بالا :

آموزش ماژول Planar Subdivision در OpenCV

 

نمونه کدهایی از کلاس Subdiv2D :

کد نمونه 1

کد نمونه 1 : خب یه کد خیلی ساده، که یه عکس رو میخونیم، بعد یه سری نقاط تصادفی ایجاد میکنیم، بعد نمودار های delaunay و voronoi رو ایجاد میکنیم.

نتیجه کد بالا :

آموزش ماژول Planar Subdivision در OpenCV

کد نمونه 2

کد نمونه 2 : کاری به کاربرد های این کلاس ندارم و این که کدهایی که میزنیم کاربردی دارن یا نه، فعلا میخوام یکم با توابع بازی میکنیم تا کار باهاشو یاد بگیرید؛ خب نظر موافقتون چیه که تصویر ورودی رو بیام نقاط کلیدی شو پیدا کنم و بعد به کمک این نقاط کلیدی، نمودارهای فوق رو ایجاد کنم؟ و مثلا تو نمودار voronoi بیام به جای این که از رنگ تصادفی استفاده کنم، از رنگ معادل تصویر ورودی در اون محیط استفاده کنم؟

برا بحث پیدا کردن نقاط کلیدی به این مطلب مراجعه کنید : آموزش ماژول 2D Features Framework در OpenCV

اگه میخواید تصویر خروجی، دقتش بره بالا و بیشتر شبیه تصویر ورودی بشه، از الگوریتم FastFeatureDetector استفاده کنید که تعداد KeyPoint های بیشتری میده.

نتیجه کد بالا : 

آموزش ماژول Planar Subdivision در OpenCV

کد نمونه 3

کد نمونه 3 : خب بریم سراغ یه کد دیگه، تو این کد ابتدا به وبکم وصل میشیم، به کمک الگوریتم landmark، چهره ها رو شناسایی میکنیم ( فعلا مطلبو نزاشتم تو سایت، هر وقت گزاشتم، لینک آموزششو قرار میدم )، اگه کلید ESC رو فشار بدیم، عکس گرفته میشه ( عکس 1 )، بعد به کمک الگوریتم Subdiv2D، نمودار مثلث بندی Delaunay رو رسم میکنیم ( عکس 2 ) و در آخر هم طرح Voronoi رو رسم میکنیم ( عکس 3 )؛ این کد ساده شده و اصلا شده کدی هستش که ته مطلب به عنوان مرجع ذکر کردم.

2 کد زیر رو در جایی که میخواید پروژه بالا اجرا بشه، قرار بدید ( فراخونی توابع اصلی پروژه بالا! ) :

نتیجه کد بالا : 

آموزش ماژول Planar Subdivision در OpenCV

 

فایل های مورد نیاز این پروژه :

1) فایل lbfmodel.yaml در مسیر زیر قرار داره ( چون حجم فایل 54 میگ هستش، بهتره فایل متنی زیر رو دانلود کنید! و بازش نکنید تو مرورگر! ):

https://raw.githubusercontent.com/kurnianggoro/GSOC2017/master/data/lbfmodel.yaml

2) فایل haarcascade_frontalface_alt2 در مسیر زیر قرار داره ( مسیری که opencv رو build کردید! ) :

[opencv]/data/haarcascades/haarcascade_frontalface_alt2.xml

اگه پیدا نکردید، از مسیر زیر میتونید دانلود کنید :

https://github.com/opencv/opencv/blob/master/data/haarcascades/haarcascade_frontalface_alt2.xml

 

دانلود کدهای پروژه + فایل های bfmodel.yaml و haarcascade_frontalface_alt2.xml مورد نیازدر پروژه 3 + تصویر خام شهید بزرگوار که تو پروژه ها استفاده کردم ( کلا هرچیزی که مربوطه به این پروژه رو داخل فایل زیر قرار دادم تا جایی که یادمه! ) :

 

منابع : 

 

عکسی که تو این مطلب ( پروژه 1 و 2 ) استفاده کردم مربوطه به شهید محمد هادی ذوالفقاری، که وقتی مطبی از یکی از سایت ها رو میخوندم با ایشون آشنا شدیم ( البته قبلا دیده بودم عکس این شهید بزرگوار رو و کلیپی ازش ولی خب اطلاعات دیگه ای دربارشون نداشتم )، برای مطالعه درباره این شهید به لینک های زیر برید :

قسمت 1؛ قسمت 2؛ قسمت 3؛ قسمت 4، قسمت 5 ( و پایانی )

برای شادی روح تمام شهدا، مخصوصا این شهید بزرگوار و امام شهدا، صلواتی بفرستید ( اگه حسش بود فاتحه، نبود همون صلوات ^_^ )؛ تا مطلب بعد یا علی.

 

برچسب ها : برچسب/تگ یی پیدا نشد!
تعداد مطالب : 358 تا
جنگ ما فتح قدس را به همراه خواهد داشت. [ امام خمینی (ره) ]
بقیه جلسات : آموزش OpenCV
ارسال دیدگاه

1) نظرات غیر فارسی به صورت خودکار حذف میشوند ( حداقل 5 حرف فارسی وارد کنید ).

2) پسورد فایل های سایت : www.dmf313.ir

3) نظرات حاوی کد برنامه نویسی تایید نمیشوند ( قالب سایت بهم میریزه )