خوارزمية المشي العشوائي

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

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

نُشرت الخوارزمية في البداية بواسطة ليو جرادي كبحث في مؤتمر ^{[ 4 ]} ولاحقًا كبحث في مجلة علمية. ^{[ 1 ]}

على الرغم من وصف الخوارزمية من حيث المسارات العشوائية ، إلا أنه يمكن حساب احتمال إرسال كل عقدة لمسار عشوائي إلى البذور تحليليًا عن طريق حل نظام معادلات خطية متفرقة وموجبة التحديد مع مصفوفة لابلاس للرسم البياني ، والتي يمكننا تمثيلها بالمتغير${\displaystyle L}$. لقد تم إثبات أن الخوارزمية قابلة للتطبيق على عدد عشوائي من التصنيفات (الكائنات)، ولكن العرض هنا يتم من حيث تصنيفين (لتبسيط العرض).

افترض أن الصورة ممثلة برسم بياني ، مع كل عقدة${\displaystyle v_{i}}$مرتبط بالبكسل وكل حافة${\displaystyle e_{ij}}$ربط البكسلات المتجاورة${\displaystyle v_{i}}$و${\displaystyle v_{j}}$تُستخدم أوزان الحواف لترميز تشابه العقد، والذي يمكن استخلاصه من الاختلافات في شدة الصورة أو اللون أو الملمس أو أي ميزات أخرى ذات دلالة. على سبيل المثال، باستخدام شدة الصورة${\displaystyle g_{i}}$عند العقدة${\displaystyle v_{i}}$من الشائع استخدام دالة ترجيح الحواف

${\displaystyle w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.}$

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

تعمل خوارزمية المشي العشوائي على تحسين الطاقة

${\displaystyle Q(x)=x^{T}Lx=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}}$

أين${\displaystyle x_{i}}$يمثل متغيرًا حقيقي القيمة مرتبطًا بكل عقدة في الرسم البياني، وتخضع عملية التحسين لقيود معينة.${\displaystyle x_{i}=1}$ل${\displaystyle v_{i}\in F}$و${\displaystyle x_{i}=0}$ل${\displaystyle v_{i}\in B}$، أين${\displaystyle F}$و${\displaystyle B}$تمثل هذه المجموعات بذور المقدمة والخلفية، على التوالي. إذا افترضنا${\displaystyle S}$تمثل مجموعة العقد التي تم تهيئتها (أي،${\displaystyle S=F\cup B}$) و${\displaystyle {\overline {S}}}$تمثل مجموعة العقد غير المُهيأة (أي،${\displaystyle S\cup {\overline {S}}=V}$أين${\displaystyle V}$إذا كانت هي مجموعة جميع العقد)، فإن الحل الأمثل لمسألة تقليل الطاقة يُعطى بواسطة حل المعادلة التالية:

${\displaystyle L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},}$

حيث تُستخدم الرموز السفلية للإشارة إلى جزء من مصفوفة لابلاس للرسم البياني${\displaystyle L}$مفهرسة حسب المجموعات المعنية.

ولإدراج حدود الاحتمالية (الأحادية) في الخوارزمية، تم توضيح في ^{[ 3 ]} أنه يمكن تحسين الطاقة

${\displaystyle Q(x)=x^{T}Lx+\gamma \left((1-x)^{T}F(1-x)+x^{T}Bx\right)=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}+\gamma \left(\sum _{v_{i}}f_{i}(1-x_{i})^{2}+\sum _{v_{i}}b_{i}x_{i}^{2}\right),}$

للمصفوفات الموجبة والقطرية${\displaystyle F}$و${\displaystyle B}$يؤدي تحسين هذه الطاقة إلى نظام المعادلات الخطية

${\displaystyle \left(L_{{\overline {S}},{\overline {S}}}+\gamma F_{{\overline {S}},{\overline {S}}}+\gamma B_{{\overline {S}},{\overline {S}}}\right)x_{\overline {S}}=-L_{{\overline {S}}،S} x_ {S} -\gamma F_ {{\overline {S}}،{\overline {S}}}.}$

مجموعة العقد الأولية،${\displaystyle S}$قد يكون فارغًا في هذه الحالة (أي،${\displaystyle {\overline {S}}=V}$), ولكن وجود المصفوفات القطرية الموجبة يسمح بإيجاد حل فريد لهذا النظام الخطي.

على سبيل المثال، إذا تم استخدام حدود الاحتمالية/الأحادية لإدراج نموذج لوني للكائن، فإن${\displaystyle f_{i}}$سيمثل ذلك الثقة بأن اللون عند العقدة${\displaystyle v_{i}}$سينتمي إلى الكائن (أي قيمة أكبر من${\displaystyle f_{i}}$يشير ذلك إلى ثقة أكبر بأن${\displaystyle v_{i}}$(ينتمي إلى تسمية الكائن) و${\displaystyle b_{i}}$سيمثل ذلك الثقة بأن اللون عند العقدة${\displaystyle v_{i}}$ينتمي إلى الخلفية.

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

تم توسيع خوارزمية المشي العشوائي التقليدية الموضحة أعلاه بعدة طرق:

• المشي العشوائي مع إعادة التشغيل ^{[ 6 ]}
• تحديد ألفا ^{[ 7 ]}
• اختيار العتبة ^{[ 8 ]}
• المدخلات اللينة ^{[ 9 ]}
• تشغيل على صورة مجزأة مسبقًا ^{[ 10 ]}
• المشي العشوائي في فضاء المقياس ^{[ 11 ]}
• خوارزمية المشي العشوائي السريع باستخدام الحساب المسبق غير المتصل بالإنترنت ^{[ 12 ] [ 13 ]}
• المشي العشوائي المعمم الذي يسمح بوظائف توافق مرنة ^{[ 14 ]}
• خوارزمية تقسيم المياه الموحدة للرسوم البيانية، والمتجول العشوائي، وأقصر مسار ^{[ 15 ]}
• مستجمعات المياه العشوائية ^{[ 16 ]}
• حقل عشوائي شرطي غاوسي متعدد المتغيرات ^{[ 17 ]}

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

• تلوين الصور ^{[ 18 ]}
• تقنية التدوير التفاعلي ^{[ 19 ]}
• تجزئة الصور الطبية ^{[ 20 ] [ 21 ] [ 22 ]}
• دمج عمليات التجزئة المتعددة ^{[ 23 ]}
• تجزئة الشبكة ^{[ 24 ] [ 25 ]}
• إزالة التشويش الشبكي ^{[ 26 ]}
• تحرير التجزئة ^{[ 27 ]}
• إزالة الظلال ^{[ 28 ]}
• المطابقة المجسمة (أي تسجيل الصور أحادي البعد ) ^{[ 29 ]}
• دمج الصور ^{[ 14 ] [ 17 ]}

• كود Matlab الذي ينفذ خوارزمية المشي العشوائي الأصلية
• كود Matlab الذي ينفذ خوارزمية المشي العشوائي مع الحساب المسبق
• تطبيق بايثون لخوارزمية المشي العشوائي الأصلية. مؤرشف بتاريخ ١٤ أكتوبر ٢٠١٢ في أرشيف الإنترنت (Wayback Machine) ضمن مجموعة أدوات معالجة الصور scikit-image.