خوارزميات الكشف عن مخطط تفصيلي للصورة

يقدم المقال خوارزميات اكتشاف الحلقة الأربعة الأكثر شيوعًا.

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

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



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

ما هو الاتصال؟

في الصور الرقمية ذات القيم الثنائية ، يمكن أن تحتوي البيكسل على إحدى القيم التالية: 1 - عندما تكون جزءًا من النموذج ، أو 0 - عندما تكون جزءًا من الخلفية ، أي لا تدرج الرمادي. (سنفترض أن البيكسلات بقيمة 1 سوداء ، وبقيمة 0 بيضاء).

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

في الحالة العامة ، يكون المكون المتصل عبارة عن مجموعة من وحدات البكسل السوداء P ، بحيث يكون لكل زوج من وحدات البكسل p _i و p _j في P سلسلة من البكسلات p _i و ... و p _j بحيث:

أ) جميع البيكسلات في التسلسل موجودة في المجموعة P ، أي أسود ، و

ب) كل 2 بكسل في التسلسل بجانب بعضها البعض هي "الجيران".

يطرح سؤال مهم: متى يمكننا أن نقول أن 2 بكسل "الجيران"؟ نظرًا لأننا نستخدم بكسلات مربعة ، فإن إجابة السؤال السابق ليست تافهة للسبب التالي: في التغطية بالفسيفساء المربعة ، يكون للبكسلات حافة مشتركة أو قمة ، أو لا يوجد شيء مشترك بينهما. كل بكسل لديه 8 بكسل مشتركة معها ؛ مثل هذه بكسل تشكل "حي مور" من هذا بكسل. هل يجب أن نعتبر بكسلات "الجيران" ذات قمة شائعة واحدة فقط؟ أو لكي يتم اعتبارهم "جيرانًا" ، يجب أن يكون للبيكسلتين ميزة مشتركة؟

لذلك هناك نوعان من الاتصال ، وهما: 4 اتصال و 8 اتصال.

4-الاتصال

متى يمكن أن نقول أن مجموعة معينة من البكسلات السوداء مرتبطة بـ 4؟ أولاً ، تحتاج إلى تحديد مفهوم الجار 4 (يُسمى أيضًا الجار المباشر ):

تعريف الجوار 4 : البيكسل Q هو الجار 4 بيكسل معين P إذا كان Q و P لهما حافة مشتركة. يظهر الشكل 2 أدناه الجيران الأربعة للبكسل P (المعينة بـ P2 و P4 و P6 و P8 ).


تعريف مكون متصل بـ 4 : مجموعة البكسلات السوداء P هي مكون متصل بـ 4 إذا كان لكل زوج من البكسلات p _i و p _j في P يوجد تسلسل من البيكسلات p _i و ... و p _j بحيث:

أ) جميع البيكسلات في التسلسل موجودة في المجموعة P ، أي أسود ، و

ب) كل اثنين من البكسل المتاخمة في التسلسل هي 4 جارات

أمثلة على الأنماط المرتبطة 4

توضح الرسوم البيانية أدناه أمثلة للأنماط ذات الصلة بـ 4:

8-الاتصال

متى يمكنني أن أقول أن مجموعة معينة من البكسلات السوداء متصلة بـ 8 ؟ أولاً ، نحتاج إلى تعريف مفهوم الجار 8 (يُسمى أيضًا الجار غير المباشر ):

تعريف 8 الجوار : بكسل Q هو 8 جوار (أو مجرد جوار ) من بكسل معين P إذا كان Q و P له حافة مشتركة أو قمة. يشكل الجوار 8 لبكسل P معين حي مور لهذا البيكسل.

تعريف مكون متصل بـ 8 : مجموعة البكسلات السوداء P هي مكون متصل بـ 8 (أو مجرد مكون متصل ) إذا كان لكل زوج من وحدات البكسل p _i و p _j في P يوجد تسلسل من وحدات البكسل p _i و ... و p _j بحيث :

أ) جميع البيكسلات في التسلسل موجودة في المجموعة P ، أي أسود ، و

ب) كل 2 بكسل المتاخمة في هذا التسلسل هي 8 الجيران

ملاحظة : جميع الأنماط المتصلة 4 متصلة 8 ، أي 4 - الأنماط المرتبطة هي مجموعة فرعية من العديد من الأنماط المتصلة 8. من ناحية أخرى ، قد لا يكون النمط المتصل بـ 8 متصلاً بـ 4.

مثال 8 نمط المرتبطة

يُظهر الرسم التوضيحي أدناه نمطًا متصل بـ 8 ولكن ليس متصلاً بـ 4:

مثال على نمط غير متصل بـ 8:

يُظهر الرسم التوضيحي أدناه مثالًا لنمط غير متصل بـ 8 ، أي يتكون من أكثر من مكون متصل (يعرض الرسم التخطيطي ثلاثة مكونات متصلة):

مربع تتبع خوارزمية

فكرة

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

لفهم كيف يعمل ، تحتاج إلى القليل من الخيال ...

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

الآن تخيل أنك الخنفساء تقف على بكسل البداية ، كما هو مبين في الشكل 1 أدناه. للحصول على الخطوط العريضة لنمط ما ، عليك القيام بما يلي:

, , ,

, , ,

.

ستكون البيكسلات السوداء التي تدور حولها هي الخطوط العريضة للنمط.


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

خوارزمية

فيما يلي وصف رسمي لخوارزمية التتبع التربيعي:

المدخلات: التغطية بالفسيفساء مربعة ، T ، التي تحتوي على عنصر متصل P من الخلايا السوداء.

الإخراج: الصف B (ب ₁ ، ب ₂ ، ... ، ب _ك ) من بكسل الحدود ، أي الدائرة.

بداية

• حدد B كمجموعة فارغة.
• قم بمسح الخلايا T من الأسفل إلى الأعلى ومن اليسار إلى اليمين حتى يتم العثور على بكسل أسود من P.
• تضاف s في B.
• اجعل البيكسل الحالي هو البيكسل الأولي.
• انعطف يسارًا ، أي انتقل إلى بكسل المجاورة إلى يسار ص .
• التحديث ص ، أي يصبح بكسل الحالي.
• بينما p لا تساوي s ، نفذ
  
  إذا كان بكسل الحالي ع سوداء
  
  • أدخل p في B وانتقل إلى اليسار (انتقل إلى البكسل المجاور إلى يسار p ).
  • التحديث ص ، أي يصبح بكسل الحالي.
  
  وإلا
  
  • الاتجاه يمينًا (انتقل إلى البكسل التالي إلى يمين p ).
  • التحديث ص ، أي يصبح بكسل الحالي.
  
  نهاية دورة "وداعا"

النهاية

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

مظاهرة

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

تحليل

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

ويرجع ذلك أساسًا إلى أن التدوير الأيمن والأيسر لا يأخذ في الاعتبار البيكسلات الموجودة "على طول
الأقطار "من بكسل الحالي.

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

وقف المعيار

واحدة من نقاط الضعف في الخوارزمية هو اختيار معيار التوقف. بمعنى آخر ، متى تتوقف الخوارزمية عن التنفيذ؟

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

فيما يلي عرض توضيحي متحرك يشرح كيف أن الخوارزمية غير قادرة على اكتشاف المحيط الدقيق للنمط بسبب اختيار معيار الإيقاف السيئ:


كما ترون ، يمكن أن يكون تحسين معيار الإيقاف بداية جيدة لتحسين الأداء الكلي للخوارزمية. يوجد بديلان فعالان لمعيار الإغلاق الحالي:

أ) توقف فقط عن طريق زيارة بداية بكسل n مرات ، حيث n على الأقل 2 ، أو

ب) توقف بعد ضرب بكسل البداية للمرة الثانية ، تمامًا مثل ضربناها في البداية.

تم اقتراح هذا المعيار بواسطة Jacob Eliosoff ، لذلك سوف نسميه المعيار لإيقاف Jacob .

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

لا تستطيع خوارزمية التتبع المربّع اكتشاف محيط مجموعة من الأنماط باتصال 8 ليس به اتصال 4.

فيما يلي عرض توضيحي متحرك لكيفية فشل خوارزمية التتبع التربيعي (مع معيار توقف Jacob) في اكتشاف المخطط التفصيلي الصحيح لنمط مع اتصال 8 دون اتصال 4:

هل هذه الخوارزمية عديمة الفائدة تمامًا؟

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

اجعل P هو مجموعة البكسلات السوداء مع إمكانية الاتصال 4 على الشبكة. دع البيكسلات البيضاء للشبكة ، أي تتمتع بيكسلات الخلفية W أيضًا باتصال 4. يتضح أنه في ظل هذه الظروف من النموذج وخلفيته ، يمكن إثبات أن خوارزمية التتبع التربيعي (مع معيار Jacob stop) ستتعامل دائمًا بنجاح مع تحديد المحيط.

يوجد أدناه دليل على أنه في حالة توصيل كل من البيكسلات الخلفية والخلفية 4 ، ستحدد خوارزمية التتبع التربيعي الكفاف بشكل صحيح عند استخدام معيار Jacob stop.

دليل
المعطاة : يكون النمط P بحيث تتمتع جميع وحدات البكسل الخاصة بالنمط (أي الأسود) وبكسلات الخلفية (أي البيضاء) باتصال 4.

الملاحظة الأولى

نظرًا لأن مجموعة البيكسلات البيضاء لديها اتصال 4 ، فإن هذا يعني أنه لا يمكن أن يكون هناك أي " فتحات " في النموذج (بعبارات غير رسمية ، " الثقوب " نعني مجموعات من البيكسلات البيضاء محاطة تمامًا بالبكسلات السوداء للنمط).

سيؤدي وجود أي " ثقب " في النموذج إلى فصل مجموعة البيكسلات البيضاء عن البيكسلات البيضاء المتبقية ؛ ومع ذلك ، العديد من وحدات البكسل البيضاء تفقد الاتصال 4.

يوضح الشكل 2 والشكل 3 أدناه نوعين من " الثقوب " التي يمكن أن تحدث في نمط مع اتصال 4:



الملاحظة الثانية

يجب أن يكون لدى أي بكسلين أسود من نمط جانب واحد مشترك.

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


من المفيد تمثيل هذه الأنماط على النحو التالي:

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

يمكن اعتبار حواف الحدود هذه حواف مضلع. في الصورة
5 أدناه ، تتضح هذه الفكرة من خلال مثال المضلع المقابل للنمط من الشكل 4 أعلاه:


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

يمكن أن تكون وحدات البكسل الحدودية مضاعفات لهذه الحالات أو الترتيبات الأخرى ، على سبيل المثال التحولات والانعطافات لهاتين الحالتين. يتم وضع علامة على الأضلاع الحدودية باللون الأزرق مثل E1 و E2 و E3 و E4 .


الملاحظة الثالثة

في حالة الحالتين المذكورتين أعلاه ، وبغض النظر عن البيكسل الأولي الذي نختاره ، وفي أي اتجاه يقع فيه ، لن "تتراجع" خوارزمية التتبع التربيعي (التراجع) ، ولن "تمر" عبر الحافة الحدودية مرتين ( فقط إذا كان لا تتبع الحدود مرة أخرى) ولا تفوت على الحافة الحدودية . التحقق من ذلك!

يحتاج مفهومان إلى توضيح هنا:

أ) الخوارزمية "تعود" ، عندما قبل تتبع الحدود بأكملها تعود إلى زيارة بكسل زار بالفعل ، و

ب) لكل ضلع حدود ، هناك طريقتان "للمرور عبره" ، وهما "الداخل" و "الخارج" (حيث يشير "الداخل" إلى الحركة داخل المضلع المقابل ، و "الخارج" - الخارج من المضلع).

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

الملاحظة الأخيرة

يحتوي كل نمط على عدد زوجي من الحواف الحدودية .

إذا نظرت إلى المضلع من الشكل 5 ، يمكنك أن ترى ما يلي:

إذا كنا نريد أن نبدأ من قمة S التي تم تمييزها في الرسم البياني واتبع حواف الحدود حتى نصل إلى S مرة أخرى ، فإننا نلاحظ أننا في هذه العملية نعبر عدد زوجي من حواف الحدود. يمكننا اعتبار كل حافة حدود بمثابة "خطوة" في اتجاه منفصل. ثم لكل "خطوة" إلى اليمين يجب أن يكون هناك "خطوة" مقابلة إلى اليسار ، إذا كنا نريد العودة إلى وضع البداية. الأمر نفسه ينطبق على "الخطوات" العمودية لذلك ، يجب أن تحتوي "الخطوات" على أزواج مقابلة ، وهذا ما يفسر لماذا سيكون لكل من هذه الأنماط عدد زوجي من الحواف الحدودية.

لذلك ، عندما تدخل خوارزمية تتبع المربعات عبر الحافة الحدودية الأولية (للبكسل الأولي) للمرة الثانية ، فستقوم بذلك في نفس الاتجاه مثل المرة الأولى.

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

استنتاج

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

تتبع محيط مور

فكرة

الفكرة وراء تتبع مور الجوار بسيطة ؛ ولكن قبل شرحه ، نحتاج إلى شرح مفهوم مهم: حي مور في بكسل.

حي مور

حي Moore في بكسل P هو مجموعة مكونة من 8 بكسل لها رأس أو حافة مشتركة مع هذا البكسل. يتم عرض وحدات البكسل هذه ، وهي P1 و P2 و P3 و P4 و P5 و P6 و P7 و P8 ، في الشكل 1 .

حي مور (يُسمى أيضًا 8 جيران أو جيران غير مباشرين ) مفهوم مهم غالبًا ما يشار إليه في الأدب.


الآن نحن على استعداد للتعرف على الفكرة الكامنة وراء تتبع محيط مور.

فليكن هناك نمط رقمي ، أي مجموعة من وحدات البكسل السوداء ، على خلفية وحدات البكسل البيضاء ، أي على الشبكة ابحث عن البيكسل الأسود وأعلن أنه البيكسل " الأولي ". (هناك عدة طرق للعثور على البكسل " الأولي " ، لكننا ، كما سبق ، سوف نبدأ من الركن الأيسر السفلي ونقوم بمسح جميع أعمدة البكسل بالترتيب ، حتى نعثر على البيكسل الأسود الأول ، الذي سنعلن أنه " أولي ".)

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

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

ستكون وحدات البكسل السوداء التي زارتها الخوارزمية هي الخطوط العريضة للنمط.

خوارزمية

فيما يلي وصف رسمي لخوارزمية تتبع حي مور:

المدخلات: التغطية بالفسيفساء مربعة T التي تحتوي على عنصر P متصل من الخلايا السوداء.

الإخراج: الصف B (b ₁ ، b ₂ ، ... ، b _k ) من وحدات البكسل الحدودية ، أي الدائرة.

يدل عليها M (أ) حي مور من بكسل أ .

دع p يكون بكسل الحدود الحالي.

دع c هو البيكسل الحالي قيد الدراسة ، أي ج في م (ع) .

بداية

• حدد B كمجموعة فارغة.
• من أسفل إلى أعلى ومن اليسار إلى اليمين ، قم بمسح الخلايا T حتى نعثر على بكسل أسود من P.
• تضاف s في B.
• لقد حددنا النقطة s كنقطة الحدود الحالية p ، أي ع = ق
• دعنا نعود ، أي دعنا ننتقل إلى البكسل الذي أتينا منه.
• دع c يكون بكسل التالي في اتجاه عقارب الساعة في M (p) .
• بينما c لا تساوي s ، نفذ
  
  
  • إذا كان ج أسود
    
    • أدخل c في b
    • وضعنا ع = ج
    • العودة (نقل بكسل الحالي ج إلى بكسل الذي وصلنا إلى ع )
    
    وإلا
    
    • انقل البيكسل الحالي c إلى البيكسل التالي في اتجاه عقارب الساعة في M (p)
    
    نهاية دورة وداعا

النهاية

مظاهرة

فيما يلي عرض متحرك لكيفية إجراء تتبع حي مور لكشف مخطط الخطوط العريضة. (قررنا تتبع المخطط في اتجاه عقارب الساعة.)

تحليل

يكمن الضعف الرئيسي في تتبع محيط مور في اختيار معايير التوقف.

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

فيما يلي عرض توضيحي متحرك يوضح لماذا لا تستطيع الخوارزمية العثور على المخطط الدقيق للنمط نظرًا لاختيار معيار الإيقاف السيئ:


كما ترون ، يمكن أن يكون تحسين معيار الإيقاف بداية جيدة لتحسين الأداء الكلي للتتبع. يوجد بديلان فعالان لمعيار الإغلاق ، يشبهان معيار الإغلاق Jacob.

يؤدي استخدام معيار Jacob إلى تحسين فعالية تتبع محيط مور بشكل كبير ، مما يجعله أفضل خوارزمية لتحديد محيط أي نمط ، بصرف النظر عن إمكانية الاتصال به.

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

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

مسح شعاعي

خوارزمية Radial Sweep عبارة عن خوارزمية لكشف الكفاف تمت مناقشتها في بعض الكتب. على الرغم من الاسم المعقد ، فإن الفكرة الأساسية بسيطة للغاية. في الواقع ، اتضح أن خوارزمية الكتل الشعاعية مطابقة لتتبع محيط مور. قد يتساءل المرء: "لماذا نذكره على الإطلاق؟"

تتبع محيط Moore يبحث في محيط Moore عن بكسلات الحدود الحالية في اتجاه معين (اخترنا اتجاه عقارب الساعة) حتى يعثر على بكسل أسود. ثم تعلن أن البكسل هو بكسل الحد الحالي ويستمر.

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

تعتمد الطريقة على الفكرة التالية:

في كل مرة نجد فيها بكسلًا جديدًا للحدود ، نجعله بكسلًا حاليًا P ، وارسم مقطع خط وهمي يربط P بالبكسل الحدودي السابق . بعد ذلك ، نقوم بتدوير المقطع بالنسبة لـ P في اتجاه عقارب الساعة حتى يتم عرضه على بكسل أسود في حي Moore في بكسل P. إن دوران الخط مطابق لفحص كل بكسل في المنطقة المجاورة لـ Moore P.

لقد أنشأنا عرضًا متحركًا لكيفية عمل خوارزمية الفحص الشعاعي وكيف يبدو البحث عن محيط مور.


ومتى تتوقف خوارزمية الاجتياح الشعاعي؟

لنشرح سلوك الخوارزمية باستخدام معايير التوقف التالية ...

وقف المعيار 1

دع خوارزمية الفحص الشعاعي مكتملة عندما تزور البكسل الأولي مرة ثانية.

يوجد أدناه عرض توضيحي متحرك ، يتضح من خلاله سبب تغيير معيار الاستراحة بشكل صحيح.


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

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

معيار إيقاف جاكوب أن تتوقف الخوارزمية عن التنفيذ عندما تزور بكسل البداية للمرة الثانية في نفس الاتجاه مثل المرة الأولى.

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

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

وقف معيار 2

افترض أنه في كل مرة تكتشف فيها الخوارزمية بيكسل حدود جديد P _i ، يتم إدراجه في سلسلة من وحدات البكسل الحدودية: P ₁ ، P ₂ ، P ₃ ، ... ، P _i ؛ وأعلن أنه بكسل الحدود الحالية. ( ف ₁ سننظر في بكسل الأولي ). هذا يعني أننا نعرف بكسل الحدود السابقة P _i-1 لكل بكسل حد حالي P _i . (بالنسبة لبداية البكسل ، سنفترض أن P ₀هو بكسل وهمي لا يضاهي أيًا من البكسلات على الشبكة التي تواجه البكسل الأولي في صف البكسلات الحدودية).

وبالنظر إلى الافتراضات المذكورة أعلاه، يمكننا تحديد معايير توقف على النحو التالي:

الخوارزمية ينهي التنفيذ في الحالات التالية:

أ) الحالية الحدود بكسل P _ط قد سبق واجتمع كما بكسل P _ي (حيث ي <ط ) في سلسلة من بكسل الحدود، و

ب) P _{ط- 1} = P _j-1 .

بمعنى آخر ، تكمل الخوارزمية التنفيذ عندما تزور بكسل الحدود P في الثانيةالأوقات إذا كانت بكسل الحدود قبل P (في صف البكسلات الحدودية) للمرة الثانية هي نفس البكسل التي كانت موجودة قبل P عندما تمت زيارة P لأول مرة.

إذا تم استيفاء حالة معيار الإيقاف ولم يتم إيقاف الخوارزمية ، فستستمر خوارزمية الفحص الشعاعي في الكشف عن نفس الحدود مرة أخرى.

يتشابه أداء خوارزمية المسح الشعاعي مع معيار التوقف هذا مع أداء تتبع حي مور مع معيار توقف يعقوب.

ثيو بافليديس خوارزمية

فكرة

هذه الخوارزمية هي واحدة من أحدث خوارزميات الكشف عن الحلقة التي اقترحها ثيو بافليديس . استشهد بها في كتابه 1982 خوارزميات للرسومات ومعالجة الصور (الفصل 7 ، القسم 5). الأمر ليس بهذه السهولة مثل الخوارزمية الخاصة بتتبع المربعات أو تتبع المناطق المحيطة بـ Moore ، ولكنها ليست معقدة للغاية (هذا نموذجي لمعظم خوارزميات اكتشاف الحافة).

لن نوضح هذه الخوارزمية بنفس الطريقة التي تم بها في كتابه. أسلوبنا أسهل في الفهم ويعطي فكرة عن الفكرة العامة التي تقوم عليها الخوارزمية.

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

الآن دعنا ننتقل إلى الفكرة ...

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

للعثور على الأوليبكسل لاستخدام هذه الطريقة اختياري. بدلاً من ذلك ، سنختار بكسل بدء يفي بالقيود التالية التي تفرضها خوارزمية Pavlidis لتحديد بكسل بدء التشغيل:

أحد القيود المهمة على الاتجاه الذي ندخل فيه بكسل البداية.

في الواقع ، يمكنك اختيار أي بكسل حد أسود في البداية ، إذا كنت تقف في البداية. على ذلك ، بكسل اليسار المجاورة ليست سوداء. بمعنى آخر ، تحتاج إلى إدخال بكسل البدء في اتجاه بحيث يكون البيكسل المجاور الأيسر أبيض (يتم أخذ "اليسار" هنا نسبة إلى الاتجاه الذي ندخل فيه بكسل البدء ).

الآن تخيل أنك الخنفساء تقف علىبدء بكسل ، كما هو مبين في الشكل 1 أدناه. أثناء تنفيذ الخوارزمية ، سنهتم بثلاث بكسل فقط أمامك ، أي P1 ، P2 و P3 هو مبين في الشكل 1 . (نحن للدلالة به P2 بكسل قبل لكم، وP1 - هو بكسل إلى اليسار من P2 ، و على P3 - حق بكسل P2 ).


كما هو الحال مع خوارزمية التتبع التربيعي ، فإن أهم شيء في خوارزمية Pavlidis هو "الشعور بالاتجاه". يتحول اليسار واليمين إلى الموضع الحالي ، والذي يعتمد على كيفية إدخال البكسل الحالي. لذلك ، من أجل القيام بالتحركات الصحيحة ، من المهم تتبع اتجاهك الحالي. ولكن بغض النظر عن مكان وجودك ، يتم تحديد وحدات البكسل P1 و P2 و P3 كما هو موضح أعلاه.

مع هذه المعلومات، ونحن مستعدون لشرح خوارزمية ...

في كل مرة كنت تقف على بكسل الحدود الحالي (والذي هو أول الأولي بكسل)، قم بما يلي:

أولا ، تحقق من بكسل وP1 . إذا كانت P1 سوداء ، فأعلن P1البيكسل الحد الحالي وحرك خطوة للأمام ، ثم اتخذ خطوة إلى اليسار لتكون في P1 ( ترتيب الحركات مهم جدًا).

في الشكل 2 يوضح أدناه هذه الحالة. يظهر الطريق للوصول إلى P1 باللون الأزرق.


وفقط إذا كانت P1 بيضاء ، فانتقل إلى P2 ...

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


فقط إذا كان كل من P1 و P2 باللون الأبيض ، انتقل إلى التحقق من P3 ...

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


هذا كل شئ! ثلاث قواعد بسيطة لثلاث حالات بسيطة. كما ترون ، من المهم تتبع اتجاهك خلال المنعطفات ، لأن كل الحركات تتم وفقًا للاتجاه الحالي. لكن يبدو أننا نسينا شيئاً ما؟ ماذا لو كانت البيكسلات الثلاثة بيضاء أمامنا؟ بعد ذلك ندير (نقف عند بكسل الحالي) 90 درجة في اتجاه عقارب الساعة لرؤية مجموعة جديدة من ثلاثة بكسل أمامنا. ثم نقوم بنفس التحقق من هذه البكسلات الجديدة. ربما لا يزال لديك سؤال: ماذا لو كانت كل هذه البكسلات الثلاثة بيضاء؟! ثم مرة أخرى ندير 90 درجة في اتجاه عقارب الساعة ، والوقوف على نفس بكسل. قبل أن تتحقق من حي بيكسل مور بأكمله ، يمكنك تدوير ثلاث مرات (في كل مرة 90 درجة في اتجاه عقارب الساعة).

إذا قمنا بالتناوب ثلاث مرات دون العثور على بكسلات سوداء ، فهذا يعني أننا نقف على بكسل معزول ، غير متصل بأي بكسل أسود آخر. هذا هو السبب في أن الخوارزمية تسمح لك بالتدوير ثلاث مرات ، ثم إكمال تنفيذها.

جانب آخر: متى تنتهي الخوارزمية من التنفيذ؟

تنتهي الخوارزمية في حالتين:

أ) كما ذكر أعلاه. تسمح لك الخوارزمية بالتدوير ثلاث مرات (90 درجة في اتجاه عقارب الساعة في كل مرة) ، بعد أن تكمل التنفيذ وتعلن البيكسل معزولة أو

ب) عندما يكون البيكسل الحد الحالي هو البيكسل الأولي ، تستكمل الخوارزمية التنفيذ عن طريق "إعلان" اكتشافها لمخطط المخطط.

خوارزمية

فيما يلي وصف رسمي لخوارزمية Pavlidis:

الإدخال: التغطية بالفسيفساء مربعة T التي تحتوي على مكون P متصل بالخلايا السوداء.

الإخراج: الصف B (b ₁ ، b ₂ ، ... ، b _k ) من وحدات البكسل الحدودية ، أي الدائرة.

تعريفات:

• يُشار إليه بواسطة p بكسل الحالي ، أي بكسل الذي نقف عليه.
• حدد P1 و P2 و P3 على النحو التالي: (انظر أيضًا الشكل 1 أعلاه)
• P2 هي البيكسل أمامك ، المتاخمة للكاميرا التي تقف عليها ، أي مع بكسل ص .
• P1 — , P2 .
• P3 — , P2 .
• «» .

بداية

• B .
• T , s P (. , )
• s B .
• p s .
• :
  P1
  
  • P1 B
  • p=P1
  • ,
  
  P2
  
  • P2 B
  • p=P2
  • (. 3)
  
  P3
  
  • P3 B
  • p=P3
  • , (. 4)
  
  90 , p
  
  • إنهاء البرنامج وتعلن ع بكسل معزولة
  
  وإلا
  
  • تدوير 90 درجة في اتجاه عقارب الساعة ، والوقوف عند بكسل الحالي ص
  
  حتى الآن p = s (إنهاء حلقة التكرار)

النهاية

مظاهرة

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

تحليل

إذا كنت تعتقد أن خوارزمية Pavlidis مثالية للكشف عن الخطوط العريضة للنماذج ، فعليك تغيير رأيك ...

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

الخوارزمية تعمل بشكل جيد للغاية على الأنماط المرتبطة 4. تحدث مشكلتها عند تتبع بعض الأنماط المتصلة 8 التي ليست مرتبطة 4. فيما يلي عرض توضيحي متحرك لكيفية فشل خوارزمية Pavlidis في الكشف عن الخطوط العريضة الصحيحة لنمط متصل بـ 8 (غير متصل بأربعة أنماط) - يتخطى معظم الحدود.


هناك طريقتان بسيطتان لتعديل خوارزمية لتحسين أدائها بشكل ملحوظ.

أ) استبدال معيار الإيقاف

بدلاً من إكمال الخوارزمية عندما تزور بكسل البداية للمرة الثانية ، يمكنك إنهائها عندما تزور بكسل البداية للمرة الثالثة أو حتى الرابعة. سيؤدي ذلك إلى تحسين الأداء الكلي للخوارزمية.

أو

ب) انتقل إلى مصدر المشكلة ، أي قبل تحديد بكسل البداية ،

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

لا نخاطر بفقد البكسل المجاور الأيسر فقط من البيكسل الأولي ، ولكن أيضًا البيكسل تحته مباشرةً (كما هو موضح في التحليل). بالإضافة إلى ذلك ، في بعض الأنماط ، سيتم تخطي بكسل يقابل البكسل R في الشكل 5 أدناه. لذلك ، نفترض أن بيكسل البداية يجب أن يتم ضربه في هذا الاتجاه بحيث تكون البيكسلات المقابلة للبكسلات L و W و R الموضحة في الشكل 5 أدناه بيضاء.


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