التجزئة القائمة على الشجرة الممتدة الدنيا
تسعى تقنية تجزئة الصور إلى تقسيم الصورة الرقمية إلى مناطق من البكسلات ذات خصائص متشابهة، مثل التجانس. [ 1 ] يُسهّل تمثيل المنطقة على مستوى أعلى مهام تحليل الصور، مثل عدّ الكائنات أو اكتشاف التغييرات، لأن سمات المنطقة (مثل متوسط الشدة أو الشكل [ 2 ] ) يمكن مقارنتها بسهولة أكبر من البكسلات الخام.
دوافع استخدام الأساليب القائمة على الرسوم البيانية
لتحسين سرعة تجزئة الصور الكبيرة، يمكن تقسيم العمل بين عدة وحدات معالجة مركزية . إحدى طرق تحقيق ذلك هي تقسيم الصور إلى مربعات تُعالج بشكل مستقل. مع ذلك، قد تُجزأ المناطق الواقعة على حدود المربع أو تُفقد إذا لم تستوفِ الأجزاء متطلبات الحد الأدنى لحجم خوارزمية التجزئة. يتمثل أحد الحلول البسيطة في تداخل المربعات، أي السماح لكل معالج بمعالجة وحدات بكسل إضافية حول حدود مربعه. لسوء الحظ، يزيد هذا من الحمل الحسابي، لأن المعالجات على جانبي حدود المربع تُجري عملاً زائداً. أيضاً، لا يُضمن الحفاظ إلا على الكائنات الأصغر من منطقة تداخل المربع، مما يعني أن الكائنات الطويلة، مثل الأنهار في الصور الجوية، ستظل عرضة للتجزئة. في بعض الحالات، يمكن دمج نتائج المربعات المستقلة لتقريب النتائج الحقيقية. [ 3 ] يوجد بديل آخر يتمثل في طرق التجزئة القائمة على الرسوم البيانية. تسمح معلومات الاتصال المتأصلة في الرسوم البيانية بإجراء عمل مستقل على أجزاء من الصورة الأصلية، وإعادة ربطها للحصول على نتيجة دقيقة كما لو تمت المعالجة بشكل شامل.
من الصور إلى الرسوم البيانية
إن إمكانية دمج الصور الفرعية المستقلة تحفز إضافة معلومات الاتصال إلى البكسلات. يمكن تصور ذلك على أنه رسم بياني، حيث تمثل العقد البكسلات، وتمثل الحواف الروابط بينها. أحد أشكال هذا الرسم البياني البسيط والفعال من حيث المساحة هو الرسم البياني الشبكي ، حيث يرتبط كل بكسل بجيرانه في الاتجاهات الأصلية الأربعة . ولأن علاقة الجوار بين البكسلات متناظرة، فإن الرسم البياني الناتج يكون غير موجه ، ولا يلزم تخزين سوى نصف حوافه (مثل الجار الشرقي والجنوبي لكل بكسل). تتطلب الخطوة الأخيرة ترميز معلومات تشابه البكسلات في أوزان الحواف، بحيث لا تعود الصورة الأصلية ضرورية. في أبسط الحالات، تُحسب أوزان الحواف كفرق في شدة البكسلات.
خوارزميات تجزئة الشجرة الممتدة الدنيا
الشجرة الممتدة الدنيا (MST) هي مجموعة فرعية من حواف الرسم البياني ذات وزن أدنى وخالية من الدورات ، بحيث تكون جميع العقد متصلة. في عام 2004، قدم فيلزينزوالب طريقة تجزئة [ 4 ] تعتمد على خوارزمية كروسكال للشجرة الممتدة الدنيا . تُدرس الحواف بترتيب تصاعدي للوزن؛ وتُدمج وحدات البكسل الطرفية في منطقة إذا لم يُسبب ذلك دورة في الرسم البياني، وإذا كانت وحدات البكسل "مُشابهة" لوحدات البكسل في المناطق الموجودة. يُمكن اكتشاف الدورات في وقت شبه ثابت باستخدام بنية بيانات المجموعة المنفصلة [ 5 ] . يُحكم على تشابه البكسل بواسطة طريقة استدلالية، تُقارن الوزن بعتبة لكل جزء. تُخرج الخوارزمية عدة أشجار ممتدة دنيا منفصلة، أي غابة؛ كل شجرة تُقابل جزءًا. تعقيد الخوارزمية شبه خطي لأن فرز الحواف ممكن في وقت خطي عبر فرز العد .
في عام ٢٠٠٩، طوّر واسنبرغ وزملاؤه خوارزمية [ ٦ ] لحساب عدة غابات ممتدة دنيا مستقلة، ثم دمجها معًا. يُمكّن هذا من المعالجة المتوازية دون تقسيم الكائنات على حدود البلاطات. وبدلًا من عتبة وزن ثابتة، يُستخدم تصنيف أولي للمكونات المتصلة لتقدير حد أدنى للعتبة، مما يُقلل من التجزئة الزائدة والناقصة. تُظهر القياسات أن أداء هذه الخوارزمية يتفوق على خوارزمية فيلزينزوالب التسلسلية بعشرة أضعاف.
في عام 2017، استخدم ساغلام وبايكان التمثيل التسلسلي لشجرة الامتداد الأدنى لبريم، واقترحا معيارًا جديدًا للقطع في تجزئة الصور. [ 7 ] وقد بنيا شجرة الامتداد الأدنى باستخدام خوارزمية بريم لشجرة الامتداد الأدنى، وذلك بالاعتماد على بنية بيانات كومة فيبوناتشي. وقد حققت هذه الطريقة نجاحًا ملحوظًا على صور الاختبار، مع سرعة تنفيذ عالية.
مراجع
- ↑ هاراليك، روبرت م .؛ شابيرو، ليندا ج. (يناير 1985)، "تقنيات تجزئة الصور"، رؤية الحاسوب، والرسومات، ومعالجة الصور ، 29 (1): 100-132 ، doi : 10.1016/s0734-189x(85)90153-7
- ↑ إيفارينن، يوكا؛ بيورا، ماركوس؛ ساريلا، جاكو؛ فيزا، آري (1997)، "مقارنة واصفات الشكل المدمجة للأجسام غير المنتظمة" ، في كلارك، أدريان ف. (محرر)، وقائع المؤتمر البريطاني لرؤية الآلة 1997، BMVC 1997، جامعة إسكس، المملكة المتحدة، 1997 ، الجمعية البريطانية لرؤية الآلة
- ↑ تشين، مينغهوا؛ بافليديس، ثيودوسيوس (1990)، "دمج الصور للتجزئة على بنية متوازية"، معاملات IEEE في تحليل الأنماط والذكاء الآلي ، 12 (6): 588-594 ، doi : 10.1109/34.56195
- ↑ فيلزينزوالب، بيدرو ف .؛ هوتينلوشر، دانيال ب. (2004)، "تجزئة الصور الفعالة القائمة على الرسوم البيانية"، المجلة الدولية لرؤية الحاسوب ، 59 (2): 167-181 ، doi : 10.1023/B:VISI.0000022288.19776.77 ، S2CID 207663697
- ↑ هارفست، غريغوري سي؛ رينغولد، إدوارد إم (2000)، "تحليل مُستهلك قائم على الإمكانات لبنية بيانات الاتحاد والبحث"، أخبار SIGACT ، 31 (3): 86-95 ، doi : 10.1145/356458.356463 ، S2CID 14779624
- ↑ فاسنبرغ، يان؛ ميدلمان، فولفغانغ؛ ساندرز، بيتر (2009)، "خوارزمية متوازية فعالة لتجزئة الصور القائمة على الرسوم البيانية"، في جيانغ، شياوي؛ بيتكوف، نيكولاي (محرران)، التحليل الحاسوبي للصور والأنماط، المؤتمر الدولي الثالث عشر، CAIP 2009، مونستر، ألمانيا، 2-4 سبتمبر 2009، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 5702، سبرينغر، الصفحات 1003-1010 ، doi : 10.1007/978-3-642-03767-2_122 ، ISBN 978-3-642-03766-5
- ↑ ساغلام، علي؛ بايكان، نوردان أخان (2017)، "تجزئة الصور المتسلسلة بناءً على تمثيل الشجرة الممتدة الدنيا"، رسائل التعرف على الأنماط ، 87 : 155-162 ، Bibcode : 2017PaReL..87..155S ، doi : 10.1016/j.patrec.2016.06.001
روابط خارجية
- شجرة ممتدة
- تجزئة الصور