تحويل صفة صورة غير مرتبط بمقياس

تحويل صفة صورة غير مرتبط بمقياس أو Scale-invariant feature transform, SIFT هي خوارزمية في مجال الرؤية الحاسوبية طورها البروفيسور الكندي ديفيد لو في عام 1999. وتعتبر من أهم الخوارزميات المستخدمة لأغراض التعرف على الاجسام والبحث عن الصور ضمن خدمة الجوجل. كما تستعمل لربط مجموعة من الصور المتداخلة لتكوين صورة بانوراما من خلال تحديد نقاط في الصور المراد مقارنتها. كل نقطة توصف بشعاع مؤلف من 128 مركبة، ويتم حساب التشابه بين نقطتين بواسطة المسافة الاقليدية بين شعاعيهما. تتسم هذه الميزات بانها غير مرتبطة بالتحويلات الهندسية Geometry Transformations للصورة كالدوران Rotation والتدرج Scaling (التصغير والتكبير) والتي تنجم عن دوران آلة التصوير أو تغير نقطة التقاط الصورة viewpoint، كما أنها غير مرتبطة بشكل جزئي بالتحويلات الضوئية Photogrammetry Transformations كتغير التمايز Contrast أو السطوع Brightness والتي تنجم على سبيل المثال بسبب عمل آلة التصوير في اوقات مختلفة (ليل أو نهار) أو تحت طقس مختلف (غائم أو مشمس وغير ذلك).

الخوارزمية

تتألف الخوارزمية من أربع مراحل رئيسية

اكتشاف النقاط المميزة في الصورة Keypoints

يتم تحويل الصورة المراد معالجتها الي صورة اسود وأبيض فيما إذا كانت ملونة ثم يتم تمثيلها بارقام حقيقية بحيث تصبح قيم البكسل محصورة ضمن المجال (0-1) بدلا من المجال (0-255) لكي يمكن ترشيحها بواسطة مرشح غاوص. تطوى الصورة الناتجة مع مرشح غاوص بشكل متكرر أربع مرات على الأقل لكي تكون مجموعة من الصور لها ذات الابعاد تدعى الاوكتاف الأول. ثم تصغر الصورة الأخيرة بمعامل 2 عن طريق حذف كل ثاني سطر وكل ثاني عمود ثم تطوى هذه الصورة المصغرة مع مرشح غاوص بنفس العدد في المرة الأولى بحيث نحصل على الاوكتاف الثاني وهكذا يكرر التصغير والطي حتى تبلغ ابعاد الصورة حدا معينا لم تعد معه تضهر أي تفاصيل واضحة مهمة. حالما تنتهي هذة العملية نحصل على ما يدعي الهرم الغاوصي Gaussian Pyramid الذي يمكن تمثيله رياضيا بدالة ثلاثية المتحولات يرمز له بـ $L\left(x,y,\sigma \right)$ ، حيث تشير كل من x، y الي إحداثيات النقطة في الصورة اما $\sigma$ فهي الانحراف المعياري لمرشح غوص والذي يتغير من صورة إلى صورة ضمن الهرم بسبب الطي المتكرر. لتفسير ذلك نفترض انه لدينا صورة $I_{0}\left(x,y\ \right)$ نريد ترشيحهاباستخدام مرشح غاوص $G\left(\sigma \right)$ ذو انحراف معياري $\sigma$ نحصل على صورة جديدة مرشحة كما هو موضح في العلاقة التالية $I_{1}\left(x,y,\sigma \right)=G\left(x,y,\sigma \right)*I_{0}\left(x,y\right)$ و إذا تكرر الترشيح بنفس المرشح نحصل على صورة ثالثة $I_{2}\left(x,y,\sigma \right)=G\left(x,y,\sigma \right)*I_{1}\left(x,y\right)$ $I_{2}\left(x,y,\sigma \right)=G\left(x,y,\sigma \right)*G\left(x,y,\sigma \right)*I_{0}\left(x,y\right)$ و من المعلوم ان $G\left(x,y,\sigma \right)*G\left(x,y,\sigma \right)=G\left(x,y,{\sqrt {2}}\sigma \right)$ و بالتعويض في العلاقة التي قبلها نجد $I_{2}\left(x,y,\sigma \right)=G\left(x,y,{\sqrt {2}}\sigma \right)*I_{0}\left(x,y\right)$ الأمر الذي يفسر تغير الانحراف المعياري بسبب الطي التكرر. انطلاقا من الهرم الغاوصي ومن خلال طرح كل صورتين متجاورتين من كل اوكتاف نحصل على ما يدعى هرم الفرق الغاوصي Difference of Gaussian Pyramid DoG. الذي يرمز له بـ $D\left(x,y,\sigma \right)$ $D\left(x,y,\sigma \right)=L\left(x,y,k_{i}\sigma \right)-L\left(x,y,k_{j}\sigma \right)$ حيث يدل الرمز $k_{i}$ على تغير الانحراف المعياري من صورة لأخرى بسبب الطي المتكرر. انطلاقا من هرم الفرق الغاوصي يتم تحديد مواقع البكسلات ذات القيم المتطرفة (العظمى والصغرى) عن طريق مقارنة قيمتها مع قيم جيرانها الثمانية في نفس الصورة وقيم جيرانها التسعة الموجودة في الصورة التي من فوقها والتسعة التي من تحتها ضمن كل اوكتاف، إذا كانت أكبر أو اصغر من كل الـ 26 بكسل المحيطة بها يتم تعليم هذه النقطة كمركز لصفة محتملة.