سلسله‌مراتب کانتورها (Contours Hierarchy)

هدف#

در این بخش، درباره سلسله‌مراتب کانتورها (Hierarchy of Contours)، یعنی رابطه والد-فرزند (Parent-Child Relationship) در کانتورها، یاد می‌گیریم.

تئوری#

در چند مقاله اخیر درباره کانتورها، با توابع مختلف مرتبط با کانتورها در OpenCV کار کرده‌ایم. اما هنگامی که کانتورها را در تصویر با استفاده از تابع cv.findContours() پیدا کردیم، یک آرگومان به نام حالت بازیابی کانتور (Contour Retrieval Mode) ارسال کردیم. معمولاً cv.RETR_LIST یا cv.RETR_TREE را ارسال می‌کنیم و کار به درستی انجام می‌شود. اما واقعاً معنای این‌ها چیست؟

همچنین در خروجی، سه آرایه دریافت کردیم: اول تصویر، دوم کانتورهای ما، و یکی دیگر که آن را hierarchy (سلسله‌مراتب) نام‌گذاری کردیم (لطفاً کدهای مقالات قبلی را بررسی کنید). اما هرگز از این سلسله‌مراتب در جایی استفاده نکردیم. پس این سلسله‌مراتب چیست و برای چه کاری است؟ چه رابطه‌ای با آرگومان تابع قبلاً ذکر شده دارد؟

این همان چیزی است که در این مقاله به آن می‌پردازیم.

سلسله‌مراتب چیست؟#

معمولاً از تابع cv.findContours() برای تشخیص اشیاء در تصویر استفاده می‌کنیم، درست است؟ گاهی اوقات اشیاء در مکان‌های مختلف قرار دارند. اما در برخی موارد، برخی اشکال داخل اشکال دیگری قرار می‌گیرند، درست مثل شکل‌های تودرتو. در این صورت، کانتور بیرونی را والد (Parent) و کانتور داخلی را فرزند (Child) می‌نامیم. به این ترتیب، کانتورها در یک تصویر با یکدیگر روابطی دارند و می‌توانیم مشخص کنیم که هر کانتور چگونه به دیگری متصل است؛ مثلاً آیا فرزند کانتور دیگری است یا خودش والد است. نمایش این رابطه را سلسله‌مراتب (Hierarchy) می‌نامیم.

یک تصویر نمونه زیر را در نظر بگیرید:

در این تصویر، چند شکل وجود دارد که از ۰ تا ۵ شماره‌گذاری شده‌اند. ۲ و ۲a به ترتیب کانتورهای بیرونی و داخلی جعبه بیرونی‌ترین را نشان می‌دهند.

در اینجا، کانتورهای ۰، ۱ و ۲ بیرونی یا بیرونی‌ترین هستند. می‌توانیم بگوییم آن‌ها در سطح سلسله‌مراتب ۰ یا به سادگی در همان سطح سلسله‌مراتب قرار دارند.

سپس کانتور ۲a می‌آید. می‌توان آن را فرزند کانتور ۲ در نظر گرفت (یا برعکس، کانتور ۲ والد کانتور ۲a است). پس آن را در سطح سلسله‌مراتب ۱ قرار می‌دهیم. به همین ترتیب، کانتور ۳ فرزند کانتور ۲a است و در سطح بعدی قرار می‌گیرد. در نهایت، کانتورهای ۴ و ۵ فرزندان کانتور ۳a هستند و در آخرین سطح سلسله‌مراتب قرار می‌گیرند. بر اساس روش شماره‌گذاری جعبه‌ها، می‌توان گفت کانتور ۴ اولین فرزند کانتور ۳a است (البته می‌تواند کانتور ۵ هم باشد).

این مطالب را ذکر کردم تا اصطلاحاتی مانند همان سطح سلسله‌مراتب، کانتور بیرونی، کانتور فرزند، کانتور والد، اولین فرزند و غیره را درک کنیم. حالا بیایید وارد OpenCV شویم.

نمایش سلسله‌مراتب در OpenCV#

هر کانتور اطلاعات خود را درباره سطح سلسله‌مراتب، فرزندان و والدش دارد. OpenCV آن را به صورت آرایه‌ای از چهار مقدار نشان می‌دهد: [Next, Previous, First_Child, Parent]

«Next نشان‌دهنده کانتور بعدی در همان سطح سلسله‌مراتب است.»

برای مثال، کانتور ۰ را در تصویر ما در نظر بگیرید. کانتور بعدی در همان سطح آن کیست؟ کانتور ۱ است. پس به سادگی Next = 1 می‌گذاریم. به همین ترتیب برای کانتور ۱، کانتور بعدی کانتور ۲ است، پس Next = 2.

کانتور ۲ چطور؟ هیچ کانتور بعدی در همان سطح وجود ندارد. پس به سادگی Next = -1 می‌گذاریم. کانتور ۴ چطور؟ در همان سطح با کانتور ۵ قرار دارد. پس کانتور بعدی آن کانتور ۵ است و Next = 5.

«Previous نشان‌دهنده کانتور قبلی در همان سطح سلسله‌مراتب است.»

مانند موارد بالا است. کانتور قبلی کانتور ۱ در همان سطح، کانتور ۰ است. به همین ترتیب برای کانتور ۲، کانتور ۱ است. و برای کانتور ۰، هیچ کانتور قبلی وجود ندارد، پس ‎-1 می‌گذاریم.

«First_Child نشان‌دهنده اولین کانتور فرزند آن است.»

نیازی به توضیح ندارد. برای کانتور ۲، فرزند کانتور ۲a است. پس مقدار اندیس متناظر کانتور ۲a را می‌گیرد. کانتور ۳a چطور؟ دو فرزند دارد. اما فقط اولین فرزند را می‌گیریم که کانتور ۴ است. پس First_Child = 4 برای کانتور ۳a.

«Parent نشان‌دهنده اندیس کانتور والد آن است.»

دقیقاً برعکس First_Child است. هم برای کانتور ۴ و هم برای کانتور ۵، کانتور والد، کانتور ۳a است. برای کانتور ۳a، کانتور ۳ است و به همین ترتیب ادامه می‌یابد.

اکنون که از سبک سلسله‌مراتب مورد استفاده در OpenCV آگاه شدیم، می‌توانیم حالت‌های بازیابی کانتور (Contour Retrieval Modes) را در OpenCV با کمک همان تصویر بالا بررسی کنیم؛ یعنی پرچم‌هایی مانند cv.RETR_LIST، cv.RETR_TREE، cv.RETR_CCOMP، cv.RETR_EXTERNAL و غیره چه معنایی دارند؟

حالت بازیابی کانتور#

۱. RETR_LIST#

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

بنابراین در اینجا، جمله سوم و چهارم در آرایه سلسله‌مراتب همیشه ‎-1 هستند. اما طبیعتاً، جمله‌های Next و Previous مقادیر متناظر خود را خواهند داشت. خودتان آن را بررسی و تأیید کنید.

در زیر نتیجه‌ای است که به دست آوردم؛ هر سطر جزئیات سلسله‌مراتب کانتور متناظر است. برای مثال، سطر اول به کانتور ۰ مربوط است. کانتور بعدی، کانتور ۱ است. پس Next = 1. هیچ کانتور قبلی وجود ندارد، پس Previous = -1. و دو مورد باقیمانده، همانطور که گفته شد، ‎-1 هستند.

>>> hierarchy
array([[[ 1, -1, -1, -1],
        [ 2,  0, -1, -1],
        [ 3,  1, -1, -1],
        [ 4,  2, -1, -1],
        [ 5,  3, -1, -1],
        [ 6,  4, -1, -1],
        [ 7,  5, -1, -1],
        [-1,  6, -1, -1]]])

این گزینه مناسبی است که در کد خود استفاده کنید، اگر از ویژگی‌های سلسله‌مراتب استفاده نمی‌کنید.

۲. RETR_EXTERNAL#

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

بنابراین در تصویر ما، چند کانتور کاملاً بیرونی وجود دارد؟ یعنی در سطح سلسله‌مراتب ۰؟ فقط ۳ تا هستند، یعنی کانتورهای ۰، ۱ و ۲، درست است؟ حالا سعی کنید کانتورها را با استفاده از این پرچم پیدا کنید. در اینجا نیز مقادیر داده شده به هر عنصر مانند بالا است. آن را با نتیجه بالا مقایسه کنید. در زیر چیزی است که به دست آوردم:

>>> hierarchy
array([[[ 1, -1, -1, -1],
        [ 2,  0, -1, -1],
        [-1,  1, -1, -1]]])

می‌توانید از این پرچم استفاده کنید اگر فقط می‌خواهید کانتورهای بیرونی را استخراج کنید. در برخی موارد مفید است.

۳. RETR_CCOMP#

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

فقط تصویر یک «صفر سفید بزرگ» روی زمینه سیاه را در نظر بگیرید. دایره بیرونی صفر به اولین سطح سلسله‌مراتب و دایره داخلی صفر به سطح دوم تعلق دارد.

می‌توانیم آن را با یک تصویر ساده توضیح دهیم. در اینجا ترتیب کانتورها را با رنگ قرمز و سطح سلسله‌مراتبی که به آن تعلق دارند را با رنگ سبز (یا ۱ یا ۲) مشخص کرده‌ام. ترتیب همان ترتیبی است که OpenCV کانتورها را تشخیص می‌دهد.

پس اولین کانتور، یعنی کانتور ۰، را در نظر بگیرید. در سطح سلسله‌مراتب ۱ است. دو حفره دارد، کانتورهای ۱ و ۲، که به سطح سلسله‌مراتب ۲ تعلق دارند. پس برای کانتور ۰، کانتور بعدی در همان سطح سلسله‌مراتب کانتور ۳ است. و هیچ کانتور قبلی وجود ندارد. اولین فرزند آن کانتور ۱ در سطح سلسله‌مراتب ۲ است. هیچ والدی ندارد زیرا در سطح سلسله‌مراتب ۱ است. پس آرایه سلسله‌مراتب آن [3,-1,1,-1] است.

حالا کانتور ۱ را در نظر بگیرید. در سطح سلسله‌مراتب ۲ است. کانتور بعدی در همان سطح (زیر والدیت کانتور ۰) کانتور ۲ است. هیچ کانتور قبلی وجود ندارد. هیچ فرزندی ندارد، اما والد آن کانتور ۰ است. پس آرایه [2,-1,-1,0] است.

به همین ترتیب کانتور ۲: در سطح سلسله‌مراتب ۲ است. هیچ کانتور بعدی در همان سطح زیر کانتور ۰ وجود ندارد. پس Next وجود ندارد. قبلی کانتور ۱ است. هیچ فرزندی ندارد، والد کانتور ۰ است. پس آرایه [-1,1,-1,0] است.

کانتور ۳: کانتور بعدی در سطح سلسله‌مراتب ۱ کانتور ۵ است. قبلی کانتور ۰ است. فرزند کانتور ۴ است و هیچ والدی ندارد. پس آرایه [5,0,4,-1] است.

کانتور ۴: در سطح سلسله‌مراتب ۲ زیر کانتور ۳ است و هیچ خواهر و برادری ندارد. پس نه Next، نه Previous، نه فرزندی وجود دارد؛ والد کانتور ۳ است. پس آرایه [-1,-1,-1,3] است.

بقیه را خودتان پر کنید. این پاسخ نهایی است که به دست آوردم:

>>> hierarchy
array([[[ 3, -1,  1, -1],
        [ 2, -1, -1,  0],
        [-1,  1, -1,  0],
        [ 5,  0,  4, -1],
        [-1, -1, -1,  3],
        [ 7,  3,  6, -1],
        [-1, -1, -1,  5],
        [ 8,  5, -1, -1],
        [-1,  7, -1, -1]]])

۴. RETR_TREE#

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

برای مثال، تصویر بالا را گرفتم، کد را برای cv.RETR_TREE بازنویسی کردم، کانتورها را بر اساس نتیجه ارائه‌شده توسط OpenCV مرتب کردم و آن را تحلیل نمودم. دوباره، حروف قرمز شماره کانتور و حروف سبز ترتیب سلسله‌مراتب را نشان می‌دهند.

کانتور ۰ را در نظر بگیرید: در سطح سلسله‌مراتب ۰ است. کانتور بعدی در همان سطح کانتور ۷ است. هیچ کانتور قبلی وجود ندارد. فرزند کانتور ۱ است. و هیچ والدی ندارد. پس آرایه [7,-1,1,-1] است.

کانتور ۲ را در نظر بگیرید: در سطح سلسله‌مراتب ۱ است. هیچ کانتوری در همان سطح وجود ندارد. هیچ کانتور قبلی وجود ندارد. فرزند کانتور ۳ است. والد کانتور ۱ است. پس آرایه [-1,-1,3,1] است.

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

>>> hierarchy
array([[[ 7, -1,  1, -1],
        [-1, -1,  2,  0],
        [-1, -1,  3,  1],
        [-1, -1,  4,  2],
        [-1, -1,  5,  3],
        [ 6, -1, -1,  4],
        [-1,  5, -1,  4],
        [ 8,  0, -1, -1],
        [-1,  7, -1, -1]]])