تحديد الحدود

يمكن اعتبار تتبع الحدود ، المعروف أيضًا بتتبع المحيط ، لمنطقة رقمية ثنائية ، تقنية تجزئة تحدد وحدات البكسل الحدودية لتلك المنطقة. ويُعد تتبع الحدود خطوة أولى مهمة في تحليل تلك المنطقة.

في علم الطوبولوجيا ، يمكن تحديد الحدود بدقة نظرًا لطبيعة الفضاءات الطوبولوجية الدقيقة . مع ذلك، لا تخضع الصور الرقمية لنفس قواعد الفضاءات الطوبولوجية، وبالتالي فإن التعريف المناسب للحدود أقل وضوحًا. على سبيل المثال، تصف معظم المنشورات المتعلقة بتحديد حدود مجموعة جزئية S من صورة رقمية I خوارزمياتٍ تجد مجموعة من البكسلات التي تنتمي إلى S ولها في جوارها المباشر بكسلات تنتمي إلى كلٍّ من S ومكملتها I - S. وفقًا لهذا التعريف، فإن حدود المجموعة الجزئية S تختلف عن حدود مكملتها I - S، وهو أمرٌ مستحيل في الطوبولوجيا العادية.

لتحديد الحدود بدقة، من الضروري تعريف فضاء طوبولوجي يُطابق الصورة الرقمية المُعطاة. يمكن أن يكون هذا الفضاء مُركبًا خلويًا مُجردًا ثنائي الأبعاد. يحتوي هذا الفضاء على خلايا ثلاثية الأبعاد: خلايا ثنائية الأبعاد تُطابق بكسلات الصورة الرقمية، وخلايا أحادية البعد أو "شقوق" تُمثل خطوطًا قصيرة تقع بين بكسلين متجاورين، وخلايا صفرية الأبعاد أو "نقاط" تُطابق زوايا البكسلات. بالتالي، فإن حدود المجموعة الجزئية S هي سلسلة من الشقوق والنقاط، بينما تتقاطع جوارات هذه الشقوق والنقاط مع كل من المجموعة الجزئية S ومُكملتها I – S.

يتطابق الحد المُعرَّف بهذه الطريقة تمامًا مع التعريف الطوبولوجي، ويتطابق أيضًا مع تصورنا البديهي للحدود، لأن حدود المجموعة S لا ينبغي أن تحتوي على عناصر من S ولا من متممتها. بل ينبغي أن تحتوي فقط على العناصر الواقعة بين S ومتممتها. وهذه هي تحديدًا الشقوق والنقاط في المركب.

تم وصف هذه الطريقة المصححة لتتبع الحدود في كتاب من تأليف فلاديمير أ. كوفاليفسكي ^{[ 1 ]} وفي موقعه الإلكتروني ذي الصلة. ^{[ 2 ]}

خوارزمية تتبع المربع بسيطة وفعّالة في الوقت نفسه. يعتمد سلوكها كليًا على ما إذا كانت الخلية سوداء أم بيضاء (بافتراض أن الخلايا البيضاء جزء من الشكل). أولًا، يتم المسح من أعلى اليسار إلى اليمين صفًا تلو الآخر. عند دخول أول خلية بيضاء، يبدأ جوهر الخوارزمية. ويتكون أساسًا من قاعدتين:

• إذا كنت في زنزانة بيضاء، فاتجه يساراً.
• إذا كنت في زنزانة سوداء، فاتجه يميناً.

ضع في اعتبارك أن طريقة دخولك إلى الخلية الحالية مهمة، بحيث يمكن تحديد اليسار واليمين.

public void GetBoundary ( byte [,] image ) { for ( int j = 0 ; j < image . GetLength ( 1 ); j ​​++ ) for ( int i = 0 ; i < image . GetLength ( 0 ); i ++ ) if ( image [ i , j ] == 255 ) // تم العثور على أول بكسل أبيض SquareTrace ( new Point ( i , j )); }public void SquareTrace ( Point start ) { HashSet < Point > boundaryPoints = new HashSet < Point > (); // استخدم HashSet لمنع التكرار // وجدنا نقطة واحدة على الأقل boundaryPoints . Add ( start );// أول بكسل تصادفه أبيض بحكم التعريف، لذا نتجه يسارًا. // في هذا المثال، وسيطات مُنشئ النقطة هي y و x على عكس الاصطلاح . // كان اتجاهنا الأولي من اليسار إلى اليمين، وبالتالي (1، 0). Point nextStep = GoLeft ( new Point ( 1 , 0 )); Point next = start + nextStep ; while ( next != start ) { // وجدنا خلية سوداء، لذا نتجه يمينًا ولا نضيف هذه الخلية إلى HashSet. if ( image [ next.x , next.y ] == 0 ) { next = next - nextStep ; nextStep = GoRight ( nextStep ); next = next + nextStep ; } // أو وجدنا خلية بيضاء ، فنضيفها إلى HashSet . else { boundaryPoints.Add ( next ) ; nextStep = GoLeft ( nextStep ) ; next = next + nextStep ; } } }private Point GoLeft ( Point p ) = > new Point ( p.y , -p.x ) ; private Point GoRight ( Point p ) = > new Point ( -p.y , p.x ) ;​​​​​​

تُقدّم خوارزمية المسح الشعاعي، التي تُناقش غالبًا في الأدبيات جنبًا إلى جنب مع نظيرتها الأكثر شيوعًا، وهي خوارزمية تتبع الجوار مور، نهجًا يبدو بسيطًا لتتبع المحيط في معالجة الصور . ورغم أن تسمية الخوارزمية قد توحي بالتعقيد، إلا أن مبدأها الأساسي يتوافق بشكل كبير مع تقنية تتبع الجوار مور المألوفة.

تعتمد خوارزمية تتبع الجوار لمور، وهي طريقة شائعة لتحديد الحدود داخل الصور الرقمية ، على التنقل في نطاق مور حول بكسل حدودي محدد في اتجاه معين، عادةً باتجاه عقارب الساعة. عند مصادفة بكسل أسود، يتم تحديد هذا البكسل كنقطة حدودية جديدة، ثم تستمر العملية بشكل متكرر.

ومع ذلك، فإن خوارزمية المسح الشعاعي، على الرغم من كونها مكافئة وظيفيًا لتتبع الجوار مور، تقدم منظورًا جديدًا لتحديد البكسل الأسود التالي داخل جوار مور لنقطة حدودية معينة.

يكمن ابتكار الخوارزمية في منهجها لتحديد بكسل الحدود التالي. فعند تحديد بكسل حدود جديد، يُرمز له بـ P، تُحدده الخوارزمية كنقطة الاهتمام الحالية. ثم ترسم قطعة مستقيمة وهمية تصل النقطة P ببكسل الحدود السابق. بعد ذلك، تُدير الخوارزمية هذه القطعة بشكل منهجي حول النقطة P في اتجاه عقارب الساعة حتى تتقاطع مع بكسل أسود ضمن جوار مور الخاص بـ P. ^{[ 10 ]} في الواقع، تُحاكي هذه الحركة الدورانية عملية فحص كل بكسل يُحيط بالنقطة P في جوار مور.

باستخدام هذه الطريقة، تُقدّم خوارزمية المسح الشعاعي استراتيجيةً مميزةً لاجتياز حدود البكسلات داخل الصور الرقمية. ورغم تشابهها الأساسي مع تتبع الجوار لمور، إلا أن تركيزها على الاستكشاف الدوراني يُقدّم منظورًا مثيرًا للاهتمام لتقنيات تتبع المحيط في تحليل الصور وتطبيقات رؤية الحاسوب .

خوارزمية ثيو بافليديس هي طريقة معروفة لتتبع حدود الصور الثنائية، مصممة للكشف المنهجي عن حدود المكونات ذات الصلة وتتبعها. تبدأ هذه التقنية بتحديد بكسل حدودي أولي، وهو عادةً أول بكسل أسود يُرى أثناء مسح الصورة من أعلى إلى أسفل ومن اليسار إلى اليمين. ثم تبدأ بفحص محيط البكسل الحالي لتحديد البكسل الحدودي التالي، وغالبًا ما يكون ذلك في اتجاه عقارب الساعة للعثور على البكسل الأسود التالي الذي يُشكل الحد. ^{[ 10 ]}

يتتبع البرنامج محيط العنصر بالانتقال من بكسل حدودي إلى آخر، مما يضمن زيارة كل بكسل حدودي مرة واحدة فقط. تُعزز هذه التقنية المنهجية كفاءة الحوسبة. تستمر عملية التتبع حتى يعود البرنامج إلى أول بكسل حدودي، مُكملاً بذلك محيط العنصر. يتميز هذا الأسلوب بسهولة تطبيقه، مما يجعله خيارًا شائعًا لمجموعة متنوعة من التطبيقات، مثل اكتشاف الأجسام ، وتحليل الأشكال، والتعرف على الأنماط في مهام رؤية الحاسوب ومعالجة الصور .

تشتهر خوارزمية ثيو بافليديس ببساطتها وكفاءتها ومرونتها. فهي قادرة على التعامل مع نطاق واسع من أشكال وأحجام الأجسام داخل الصور الثنائية، مما يجعلها مفيدة لمجموعة متنوعة من تطبيقات معالجة الصور.

• إيجاد المسار
• رسم المنحنيات
• رمز السلسلة
• اتصال البكسل
• مشكلة التحسين