سياق الشكل

سياق الشكل هو وصف للميزات يستخدم في التعرف على الأشياء . وقد اقترح سيرج بيلونجي وجيتندرا مالك هذا المصطلح في ورقتهم البحثية "المطابقة باستخدام سياقات الشكل" في عام 2000. [ 1 ]

نظرية

يهدف سياق الشكل إلى أن يكون طريقة لوصف الأشكال تسمح بقياس تشابهها واستعادة نقاط التطابق. [ 1 ] الفكرة الأساسية هي اختيار n نقطة على محيط الشكل. لكل نقطة pᵢ على الشكل، يتم النظر في n - 1 متجهًا ناتجة عن توصيل pᵢ بجميع النقاط الأخرى. تمثل مجموعة هذه المتجهات وصفًا غنيًا للشكل عند تلك النقطة ، ولكنه مفصل للغاية. تكمن الفكرة الرئيسية في أن التوزيع على المواضع النسبية هو وصف قوي ومختصر وذو قدرة تمييز عالية. لذا، بالنسبة للنقطة pᵢ ، فإن المدرج التكراري التقريبي للإحداثيات النسبية للنقاط المتبقية n -    

حأنا(ك)=8{qصأنا:(q-صأنا)سلة المهملات(ك)}{\displaystyle h_{i}(k)=\#\{q\neq p_{i}:(q-p_{i})\in {\mbox{bin}}(k)\}}

يُعرَّف بأنه سياق الشكل لـصأنا{\displaystyle p_{i}}تُعتبر الفئات عادةً متجانسة في الفضاء اللوغاريتمي القطبي. ويمكن ملاحظة أن سياق الشكل يُعدّ وصفًا غنيًا ومميزًا في الشكل أدناه، حيث يظهر سياقا شكل نسختين مختلفتين من الحرف "A".

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

لكي يكون وصف الميزة مفيدًا، يجب أن يتمتع ببعض الثوابت. على وجه الخصوص، يجب أن يكون ثابتًا في حالة الإزاحة، وتغيير الحجم، والاضطرابات الطفيفة، والدوران، وذلك حسب التطبيق. تأتي خاصية الثبات الإزاحي بشكل طبيعي في سياق الشكل. أما خاصية الثبات في حالة تغيير الحجم فتتحقق بتطبيع جميع المسافات القطرية بقسمتها على متوسط ​​المسافة.α{\displaystyle \alpha }بين جميع أزواج النقاط في الشكل [ 2 ] [ 3 على الرغم من إمكانية استخدام المسافة المتوسطة أيضًا. [ 1 ] [ 4 ] وقد ثبت تجريبيًا أن سياقات الشكل تتمتع بمتانة في مواجهة التشوهات والضوضاء والقيم الشاذة [ 4 ] باستخدام تجارب مطابقة مجموعات النقاط الاصطناعية. [ 5 ]

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

يُستخدم في مطابقة الأشكال

يتكون النظام الكامل الذي يستخدم سياقات الشكل لمطابقة الأشكال من الخطوات التالية (والتي سيتم تناولها بمزيد من التفصيل في قسم تفاصيل التنفيذ ):

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

تفاصيل التنفيذ

الخطوة 1: إيجاد قائمة بالنقاط على حواف الشكل

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

الخطوة الثانية: حساب سياق الشكل

تم شرح هذه الخطوة بالتفصيل في قسم النظرية .

الخطوة 3: حساب مصفوفة التكلفة

لنفترض وجود نقطتين p و q لهما مدرجات تكرارية معيارية ذات K خانة (أي سياقات شكلية) g ( k ) و h ( k ). بما أن السياقات الشكلية هي توزيعات ممثلة كمدرجات تكرارية، فمن الطبيعي استخدام إحصائية اختبار χ² كـ "تكلفة السياق الشكلي" لمطابقة النقطتين.

جS=12ك=1ك[ز(ك)-ح(ك)]2ز(ك)+ح(ك){\displaystyle C_{S}={\frac {1}{2}}\sum _{k=1}^{K}{\frac {[g(k)-h(k)]^{2}}{g(k)+h(k)}}}

تتراوح قيم هذا المتغير بين 0 و1. [ 1 ] بالإضافة إلى تكلفة سياق الشكل، يمكن إضافة تكلفة إضافية بناءً على المظهر. على سبيل المثال، يمكن أن تكون هذه التكلفة مقياسًا لاختلاف زاوية المماس (وهو أمر مفيد بشكل خاص في التعرف على الأرقام).

جأ=12(كوس(θ1)الخطيئة(θ1))-(كوس(θ2)الخطيئة(θ2)){\displaystyle C_{A}={\frac {1}{2}}{\begin{Vmatrix}{\dbinom {\cos(\theta _{1})}{\sin(\theta _{1})}}-{\dbinom {\cos(\theta _{2})}{\sin(\theta _{2})}}\end{Vmatrix}}}

هذا نصف طول الوتر في دائرة الوحدة بين متجهات الوحدة ذات الزواياθ1{\displaystyle \theta _{1}}وθ2{\displaystyle \theta _{2}}وتتراوح قيمها أيضًا من 0 إلى 1. الآن، يمكن أن تكون التكلفة الإجمالية لمطابقة النقطتين عبارة عن مجموع مرجح للتكلفتين:

ج=(1-β)جS+βجأ{\displaystyle C=(1-\beta )C_{S}+\beta C_{A}\!\,}

الآن، لكل نقطة p i على الشكل الأول ونقطة q j على الشكل الثاني، احسب التكلفة كما هو موضح وسمها C i , j . هذه هي مصفوفة التكلفة.

الخطوة الرابعة: إيجاد المطابقة التي تقلل التكلفة الإجمالية

نتائج المطابقة

الآن، مطابقة فرديةπ(أنا){\displaystyle \pi (i)}الذي يطابق كل نقطة p i على الشكل 1 و q j على الشكل 2 والذي يقلل من التكلفة الإجمالية للمطابقة،

ح(π)=أناج(صأنا،qπ(أنا)){\displaystyle H(\pi )=\sum _{i}C\left(p_{i},q_{\pi (i)}\right)}

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

الخطوة 5: نمذجة التحويل

بالنظر إلى مجموعة التطابقات بين مجموعة محدودة من النقاط على الشكلين، فإن التحويلتي:R2R2{\displaystyle T:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}يمكن تقدير إمكانية تحويل أي نقطة من شكل إلى آخر. توجد عدة خيارات لهذا التحويل، موضحة أدناه.

أفين

يُعد النموذج الأفيني خيارًا قياسيًا:تي(ص)=أص+o{\displaystyle T(p)=Ap+o\!}حل المربعات الصغرى للمصفوفةأ{\displaystyle A}ويتم الحصول على متجه الإزاحة الانتقالية o من خلال:

o=1نأنا=1ن(صأنا-qπ(أنا))،أ=(سؤال+P)ت{\displaystyle o={\frac {1}{n}}\sum _{i=1}^{n}\left(p_{i}-q_{\pi (i)}\right),A=(Q^{+}P)^{t}}

أينP=(1ص11ص121صن1صن2){\displaystyle P={\begin{pmatrix}1&p_{11}&p_{12}\\\vdots &\vdots &\vdots \\1&p_{n1}&p_{n2}\end{pmatrix}}}بتعبير مماثل لـسؤال{\displaystyle Q\!}.سؤال+{\displaystyle Q^{+}\!}هو المعكوس الزائف لـسؤال{\displaystyle Q\!}.

شريحة رقيقة

يُعد نموذج الشرائح الرقيقة (TPS) النموذج الأكثر استخدامًا للتحويلات عند التعامل مع سياقات الأشكال. ويمكن تقسيم التحويل ثنائي الأبعاد إلى دالتين من دوال TPS لنمذجة تحويل الإحداثيات:

تي(x،y)=(وx(x،y)،وy(x،y)){\displaystyle T(x,y)=\left(f_{x}(x,y),f_{y}(x,y)\right)}

حيث يكون لكل من ƒ x و ƒ y الشكل التالي:

و(x،y)=أ1+أxx+أyy+أنا=1نωأنايو((xأنا،yأنا)-(x،y))،{\displaystyle f(x,y)=a_{1}+a_{x}x+a_{y}y+\sum _{i=1}^{n}\omega _{i}U\left({\begin{Vmatrix}(x_{i},y_{i})-(x,y)\end{Vmatrix}}\right),}

ووظيفة النواةيو(ر){\displaystyle U(r)\!}يتم تعريفها بواسطةيو(ر)=ر2سجلر2{\displaystyle U(r)=r^{2}\log r^{2}\!}يمكن الاطلاع على التفاصيل الدقيقة لكيفية حساب المعاملات في مصادر أخرى [ 7 ] [ 8 ] ، ولكنها تتضمن أساسًا حل نظام معادلات خطية . كما يمكن الحصول بسهولة على طاقة الانحناء (وهي مقياس لمقدار التحويل اللازم لمحاذاة النقاط).

نظام TPS منتظم

تتطلب صيغة TPS المذكورة أعلاه مطابقة تامة لأزواج النقاط على الشكلين. بالنسبة للبيانات المشوشة، من الأفضل تخفيف هذا الشرط. إذا تركناvأنا{\displaystyle v_{i}}تشير إلى قيم دالة الهدف في المواقع المقابلةصأنا=(xأنا،yأنا){\displaystyle p_{i}=(x_{i},y_{i})}(لاحظ ذلك لـ)وx{\displaystyle f_{x}}،vأنا{\displaystyle v_{i}}كانx{\displaystyle x'}الإحداثي السيني للنقطة المقابلة لـصأنا{\displaystyle p_{i}}ولـوy{\displaystyle f_{y}}سيكون ذلك إحداثي y،y{\displaystyle y'}إن تخفيف هذا الشرط يعني تقليله إلى الحد الأدنى.

ح[و]=أنا=1ن(vأنا-و(xأنا،yأنا))2+λأناو{\displaystyle H[f]=\sum _{i=1}^{n}(v_{i}-f(x_{i},y_{i}))^{2}+\lambda I_{f}}

أينأناو{\displaystyle I_{f}\!}هي طاقة الانحناء وλ{\displaystyle \lambda \!}يُطلق عليه اسم مُعامل التنظيم. ويمكن إيجاد قيمة ƒ التي تُقلل H [ ƒ ] بطريقة مباشرة إلى حد ما. [ 9 ] إذا استخدمنا إحداثيات مُعَيَّرة لـ(xأنا،yأنا) و (xأنا،yأنا){\displaystyle (x_{i},y_{i}){\mbox{ و }}(x'_{i},y'_{i})}عندئذٍ، يتم الحفاظ على ثبات المقياس. مع ذلك، إذا تم استخدام الإحداثيات الأصلية غير المُعَيَّرة، فيجب معايرة مُعامل التنظيم.

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

الخطوة 6: حساب مسافة الشكل

الآن، مسافة الشكل بين شكلينP{\displaystyle P\!}وسؤال{\displaystyle Q\!}ستكون هذه المسافة عبارة عن مجموع مرجح لثلاثة حدود محتملة:

مسافة سياق الشكل : وهي المجموع المتناظر لتكاليف مطابقة سياق الشكل على أفضل نقاط المطابقة:

دsج(P،سؤال)=1نصPargمينqسؤالج(ص،تي(q))+1مqسؤالargمينصPج(ص،تي(q)){\displaystyle D_{sc}(P,Q)={\frac {1}{n}}\sum _{p\in P}\arg {\underset {q\in Q}{\min }}C(p,T(q))+{\frac {1}{m}}\sum _{q\in Q}\arg {\underset {p\in P}{\min }}C(p,T(q))}

حيث T (·) هو تحويل TPS المقدر الذي يربط النقاط في Q بتلك الموجودة في P.

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

دأج(P،سؤال)=1نأنا=1نΔZ2جي(Δ)[أناP(صأنا+Δ)-أناسؤال(تي(qπ(أنا))+Δ)]2{\displaystyle D_{ac}(P,Q)={\frac {1}{n}}\sum _{i=1}^{n}\sum _{\Delta \in Z^{2}}G(\Delta )\left[I_{P}(p_{i}+\Delta )-I_{Q}(T(q_{\pi (i)})+\Delta )\right]^{2}}

أينأناP{\displaystyle I_{P}\!}وأناسؤال{\displaystyle I_{Q}\!}هل هي صور ذات تدرج رمادي (أناسؤال{\displaystyle I_{Q}\!}(هي الصورة بعد التشويه) وجي{\displaystyle G\!}هي دالة نافذة غاوسية.

تكلفة التحويل : التكلفة النهائيةدبهـ(P،سؤال){\displaystyle D_{be}(P,Q)\!\,}يقيس هذا المقياس مقدار التحويل اللازم لمحاذاة الصورتين. وفي حالة نظام TPS، يُحدد هذا المقياس بطاقة الانحناء.

الآن وقد أصبح لدينا طريقة لحساب المسافة بين شكلين، يمكننا استخدام مصنف أقرب جار (k-NN) حيث تُعرَّف المسافة بأنها المسافة بين الشكلين المحسوبة هنا. ترد نتائج تطبيق هذه الطريقة على حالات مختلفة في القسم التالي.

نتائج

التعرف على الأرقام

اختبر المؤلفان سيرج بيلونجي وجيتندرا مالك منهجهما على قاعدة بيانات MNIST . وقد تم اختبار أكثر من 50 خوارزمية على هذه القاعدة. تحتوي قاعدة البيانات على مجموعة تدريب تضم 60,000 مثال، ومجموعة اختبار تضم 10,000 مثال. بلغ معدل الخطأ لهذا المنهج 0.63% باستخدام 20,000 مثال تدريبي وخوارزمية أقرب ثلاثة جيران (3-NN). وكان هذا المعدل الأدنى وقت النشر، بينما يبلغ حاليًا أدنى معدل خطأ 0.18%. [ 10 ]

الاسترجاع القائم على تشابه الصور الظلية

أجرى الباحثون تجربةً على قاعدة بيانات صور الظلية لأشكال MPEG-7، ضمن التجربة الأساسية CE-Shape-1 الجزء ب، والتي تقيس أداء الاسترجاع القائم على التشابه. [ 11 ] تحتوي قاعدة البيانات على 70 فئة شكلية، و20 صورة لكل فئة. تم اختبار أداء نظام الاسترجاع باستخدام كل صورة كاستعلام، وحساب عدد الصور الصحيحة ضمن أفضل 40 تطابقًا. في هذه التجربة، زاد الباحثون عدد النقاط المأخوذة من كل شكل. ونظرًا لأن الأشكال في قاعدة البيانات كانت تُدار أو تُقلب أحيانًا، فقد حدد الباحثون المسافة بين الشكل المرجعي والشكل المطلوب بأنها أقصر مسافة بين الشكل المطلوب والشكل المرجعي الأصلي، أو الشكل المقلوب رأسيًا، أو الشكل المرجعي المقلوب أفقيًا. [ 1 ] [ 2 ] [ 3 ] [ 4 ] مع هذه التغييرات، حصلوا على معدل استرجاع بلغ 76.45%، وهو أفضل معدل في عام 2002.

التعرف على الأجسام ثلاثية الأبعاد

تضمنت التجربة التالية التي أُجريت على سياقات الشكل استخدام 20 غرضًا منزليًا شائعًا من مكتبة صور كولومبيا للأشياء (COIL-20) . يحتوي كل غرض على 72 صورة في قاعدة البيانات. في هذه التجربة، تم تدريب الطريقة على عدد من الصور المتباعدة بالتساوي لكل غرض، واستُخدمت الصور المتبقية للاختبار. استُخدم مُصنِّف أقرب جار واحد (1-NN). كما طوّر الباحثون خوارزمية تحرير تعتمد على تشابه سياق الشكل وتجميع k-medoids ، مما حسّن من أدائها. [ 4 ]

استعادة العلامات التجارية

استُخدمت سياقات الشكل لاسترجاع أقرب العلامات التجارية المطابقة من قاعدة البيانات لعلامة تجارية مُستعلم عنها (مفيد في الكشف عن انتهاك العلامات التجارية ). لم تُغفل الخوارزمية أي علامة تجارية مشابهة بصريًا (تم التحقق من ذلك يدويًا من قِبل المؤلفين). [ 2 ]

مراجع

  1. 1 2 3 4 5 إس. بيلونجي وج. مالك (2000). "المطابقة مع سياقات الشكل". ورشة عمل IEEE حول الوصول القائم على المحتوى لمكتبات الصور والفيديو (CBAIVL-2000) . doi : 10.1109/IVL.2000.853834 .
  2. ١ ٢ ٣ ٤ س. بيلونجي؛ ج. مالك وج. بوزيتشا (أبريل ٢٠٠٢). "مطابقة الأشكال والتعرف على الأشياء باستخدام سياقات الأشكال" (ملف PDF) . معاملات IEEE في تحليل الأنماط والذكاء الآلي . ٢٤ (٤): ٥٠٩-٥٢١ . doi : 10.1109/34.993558 . S2CID ١٢٩٤٦٨ . 
  3. 1 2 إس. بيلونجي؛ ج. مالك وج. بوزيتشا (يوليو 2001). "مطابقة الأشكال" (ملف PDF) . المؤتمر الدولي الثامن لمعهد مهندسي الكهرباء والإلكترونيات حول رؤية الحاسوب (يوليو 2001) .
  4. 1 2 3 4 إس. بيلونجي؛ ج. مالك وج. بوزيتشا (2000). "سياق الشكل: واصف جديد لمطابقة الأشكال والتعرف على الأشياء" (ملف PDF) . NIPS 2000 .
  5. هـ. تشوي وأ. رانجاراجان (يونيو 2000). "خوارزمية جديدة لمطابقة النقاط غير الصلبة". مؤتمر رؤية الحاسوب وأنماط التعرف . المجلد 2. الصفحات 44-51 . doi : 10.1109/CVPR.2000.854733 .  
  6. ر. جونكر وأ. فولجينانت (1987). "خوارزمية أقصر مسار مُعزز لمسائل التخصيص الخطي الكثيفة والمتفرقة". الحوسبة . 38 (4): 325-340 . doi : 10.1007/BF02278710 . S2CID 7806079 . 
  7. إم جيه دي باول (1995). "طريقة الصفائح الرقيقة لرسم المنحنيات في منحنيات ثنائية الأبعاد". التقنيات والتطبيقات الحسابية (CTAC '95) . doi : 10.1142/9789814530651 .
  8. ج. دوشون (1977). "الدوال التكعيبية التي تُقلل من أنصاف المعايير الثابتة تحت الدوران في فضاءات سوبوليف". النظرية البنائية للدوال ذات المتغيرات المتعددة . سلسلة محاضرات في الرياضيات. المجلد 571. الصفحات 85-100 . doi : 10.1007/BFb0086566 . ISBN   978-3-540-08069-5.
  9. جي. وهبة (1990). نماذج الدوال التكعيبية للبيانات الرصدية . جمعية الرياضيات الصناعية والتطبيقية. ISBN 9780898712445.
  10. كوثرى، كامران؛ حيدري صفا، مجتبى؛ براون، دونالد إي.؛ ميماندي، كيانا جعفري؛ بارنز، لورا إي. (2018-05-03). "RMDL: التعلم العميق متعدد النماذج العشوائي للتصنيف". وقائع المؤتمر الدولي الثاني لنظم المعلومات واستخراج البيانات . ص 19-28 . arXiv : 1805.01890 . Bibcode : 2018arXiv180501890K . doi : 10.1145/3206098.3206111 . ISBN  9781450363549. S2CID 19208611 . 
  11. إس. جينين وم. بوبر (مارس 1999). "وصف التجارب الأساسية لحركة/شكل MPEG-7. التقرير الفني ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690، MPEG-7، سيول".{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=