تصنيف الكائنات بناءً على التجزئة

يمكن تمثيل مجموعة النقاط في فضاء ميزات عشوائي كرسم بياني كامل غير موجه وموزون G = (V, E)، حيث تمثل عقد الرسم البياني النقاط الموجودة في فضاء الميزات. الوزن${\displaystyle w_{ij}}$من حافة${\displaystyle (i,j)\in E}$هي دالة للتشابه بين العقد${\displaystyle i}$و${\displaystyle j}$في هذا السياق، يمكننا صياغة مشكلة تجزئة الصور كمشكلة تقسيم الرسم البياني التي تطلب تقسيمًا${\displaystyle V_{1},\cdots ,V_{k}}$مجموعة الرؤوس${\displaystyle V}$، حيث، وفقًا لمقياس ما، الرؤوس في أي مجموعة${\displaystyle V_{i}}$تتمتع بتشابه كبير، والرؤوس في مجموعتين مختلفتين${\displaystyle V_{i},V_{j}}$تشابه منخفض.

ليكن G = ( V , E , w ) رسمًا بيانيًا مُثقَّلًا.${\displaystyle A}$و${\displaystyle B}$ليكن مجموعتين جزئيتين من الرؤوس.

يترك:

${\displaystyle w(A,B)=\sum \limits _{i\in A,j\in B}w_{ij}}$

${\displaystyle \operatorname {ncut} (A,B)={\frac {w(A,B)}{w(A,V)}}+{\frac {w(A,B)}{w(B,V)}}}$

${\displaystyle \operatorname {nassoc} (A,B)={\frac {w(A,A)}{w(A,V)}}+{\frac {w(B,B)}{w(B,V)}}}$

في نهج القطع المعياري، ^{[ 2 ]} لأي قطع${\displaystyle (S,{\overline {S}})}$في${\displaystyle G}$،${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$يقيس التشابه بين الأجزاء المختلفة، و${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$يقيس التشابه الكلي للرؤوس في نفس الجزء.

منذ${\displaystyle \operatorname {ncut} (S,{\overline {S}})=2-\operatorname {nassoc} (S,{\overline {S}})}$، قطع${\displaystyle (S^{*},{\overline {S}}^{*})}$ذلك يقلل${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$كما أنه يزيد من${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$.

حساب القطع${\displaystyle (S^{*},{\overline {S}}^{*})}$ذلك يقلل${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$هي مسألة صعبة من نوع NP-hard . ومع ذلك، يمكننا إيجاد قطع في وقت متعدد الحدود${\displaystyle (S,{\overline {S}})}$ذات وزن معياري صغير${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$باستخدام التقنيات الطيفية .

يترك:

${\displaystyle d(i)=\sum \limits _{j}w_{ij}}$

أيضًا، ليكن D${\displaystyle n\times n}$مصفوفة قطرية مع${\displaystyle d}$على القطر، ودع${\displaystyle W}$كن${\displaystyle n\times n}$مصفوفة متناظرة مع${\displaystyle w_{ij}=w_{ji}}$.

بعد بعض العمليات الجبرية، نحصل على:

${\displaystyle \min \limits _{(S,{\overline {S}})}\operatorname {ncut} (S,{\overline {S}})=\min \limits _{y}{\frac {y^{T}(DW)y}{y^{T}Dy}}}$

مع مراعاة القيود التالية:

• ${\displaystyle y_{i}\in \{1,-b\}}$، لبعض الثوابت${\displaystyle -b}$
• ${\displaystyle y^{t}D1=0}$

التقليل${\displaystyle {\frac {y^{T}(DW)y}{y^{T}Dy}}}$تخضع المسألة للقيود المذكورة أعلاه، وهي مسألة صعبة من نوع NP . ولجعل المسألة قابلة للحل، نخفف القيود المفروضة على${\displaystyle y}$، والسماح لها بأخذ قيم حقيقية. يمكن حل المسألة المُخففة عن طريق حل مسألة القيم الذاتية المعممة.${\displaystyle (D-W)y=\lambda Dy}$للحصول على ثاني أصغر قيمة ذاتية معممة.

خوارزمية التقسيم:

1. بناءً على مجموعة من الخصائص، قم بإنشاء رسم بياني مرجح${\displaystyle G=(V,E)}$، احسب وزن كل حافة، ولخص المعلومات في${\displaystyle D}$و${\displaystyle W}$.
2. يحل${\displaystyle (D-W)y=\lambda Dy}$بالنسبة للمتجهات الذاتية ذات القيم الذاتية الأصغر الثانية.
3. استخدم المتجه الذاتي ذو القيمة الذاتية الثانية الأصغر لتقسيم الرسم البياني إلى قسمين (على سبيل المثال، التجميع وفقًا للإشارة).
4. حدد ما إذا كان ينبغي تقسيم القسم الحالي إلى أقسام فرعية.
5. قم بتقسيم الأجزاء المجزأة بشكل متكرر، إذا لزم الأمر.

يستغرق حل مسألة القيم الذاتية القياسية لجميع المتجهات الذاتية (باستخدام خوارزمية QR ، على سبيل المثال)${\displaystyle O(n^{3})}$الوقت. هذا غير عملي لتطبيقات تجزئة الصور حيث${\displaystyle n}$يمثل عدد البكسلات في الصورة.

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

بالنسبة للصور عالية الدقة، غالبًا ما تكون القيمة الذاتية الثانية غير مستقرة ، مما يؤدي إلى بطء تقارب خوارزميات حل القيم الذاتية التكرارية، مثل خوارزمية لانكزوس . يُعدّ التكييف المسبق تقنية أساسية لتسريع التقارب، كما هو الحال في طريقة LOBPCG الخالية من المصفوفات . يستغرق حساب المتجه الذاتي باستخدام طريقة خالية من المصفوفات ومُكيّفة مسبقًا بشكل أمثل وقتًا.${\displaystyle O(n)}$الوقت، وهو التعقيد الأمثل، لأن المتجه الذاتي لديه${\displaystyle n}$عناصر.

تستخدم مكتبة scikit-learn ^{[ 3 ]} خوارزمية LOBPCG من SciPy مع التكييف المسبق متعدد الشبكات الجبرية لحل مشكلة القيم الذاتية لمصفوفة لابلاس للرسم البياني لإجراء تجزئة الصورة عبر تقسيم الرسم البياني الطيفي كما تم اقتراحه لأول مرة في ^{[ 4 ]} وتم اختباره فعليًا في ^{[ 5 ]} و ^{[ 6 ] .}

1. بالنظر إلى الصورة D، يتم اختيار فئة من فئات الكائنات، على سبيل المثال الأبقار أو الخيول.
2. يتم مطابقة نموذج LPS المقابل مع D للحصول على العينات${\displaystyle \Theta _{1},\cdots ,\Theta _{s}}$
3. يتم تحديد دالة الهدف المعطاة بالمعادلة (2) عن طريق حساب${\displaystyle E(m,\Theta _{i})}$وباستخدام${\displaystyle w_{i}=g(\Theta _{i}|Z)}$
4. يتم تقليل دالة الهدف باستخدام عملية MINCUT واحدة للحصول على التجزئة m .