التوسيم التقريبي عبر قطع الرسم بناءً على البرمجة الخطية

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