[Algorithm] كيف يمكنني قياس التشابه بين صورتين؟


Answers

إن الطريقة "الكلاسيكية" لقياس هذا هو تقسيم الصورة إلى بعض الأجزاء المتعارف عليها من الأقسام (مثل شبكة 10x10) ثم حساب الرسم البياني لقيم RGB داخل كل خلية ومقارنة الرسوم البيانية المقابلة. ويفضل هذا النوع من الخوارزمية بسبب بساطته ومدى ثباته في التدريج وترجمة (صغيرة!).

Question

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

هل توجد مكتبة / أداة تقوم بذلك بالفعل؟ كيف تقوم بتطبيقه؟




يمكنك استخدام مقاربة رياضية صافية لـ O(n^2) ، ولكنها لن تكون مفيدة إلا إذا كنت متأكدًا من عدم وجود إزاحة أو شيء من هذا القبيل. (على الرغم من أنه إذا كان لديك بعض الأشياء مع تلوين متجانس فإنها ستظل تعمل بشكل جيد).

على أي حال ، فإن الفكرة هي حساب ناتج نقطي طبيعي للمصفوفتين. C = sum(Pij*Qij)^2/(sum(Pij^2)*sum(Qij^2)) .

هذه الصيغة هي في الواقع "جيب تمام" الزاوية بين المصفوفات (غريب). كلما كان التشابه أكبر (دعنا نقول Pij=Qij ) ، C سيكون 1 ، وإذا كانت مختلفة تمامًا ، دعنا نقول لكل i,j Qij = 1 (تجنب التقسيم الصفري) ، Pij = 255 ، ثم للحجم nxn ، سيكون أكبر n ، أقرب إلى الصفر سنحصل. (بحساب تقريبي: C=1/n^2 ).




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




للتوسع في مذكرة Vaibhav ، فإن hugin هو "autostitcher" مفتوح المصدر والذي يجب أن يكون لديه بعض الأفكار حول المشكلة.




يمكنك استخدام شبكة سيامي لمعرفة ما إذا كانت الصورتين متشابهتين أو غير متابعتين بعد هذا tutorial . تجمع هذه المجموعة التعليمية الصور المتشابهة بينما يمكنك استخدام المسافة L2 لقياس تشابه صورتين.




قد تبحث في التعليمات البرمجية الخاصة بأداة المصدر المفتوح التي تم findimagedupes ، على الرغم من أنه يبدو أنها مكتوبة في perl ، لذلك لا يمكنني تحديد مدى سهولة تحليلها ...

قراءة الصفحة findimagedupes التي أحببت ، أرى أن هناك تنفيذ C ++ من الخوارزمية نفسها . من المفترض أن يكون هذا أسهل للفهم.

ويبدو أنه يمكنك أيضًا استخدام gqview .




حسنًا ، يمكن استخدام طريقة أساسية على مستوى القاعدة من خلال كل بكسلات اللون ومقارنتها بلون البكسل المقابل في الصورة الثانية - ولكن هذا الحل ربما يكون بطيئًا جدًا .




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

إذا كان لديك صورتان متطابقتان ، فستحصل على مربع أبيض ، والذي سيضغط جيدًا. وكلما اختلفت الصور ، كلما كان الأمر أكثر تعقيدًا ، وبالتالي أصبحت أقل انضغاطًا.

ربما لا يكون الاختبار المثالي ، وربما أبطأ بكثير من اللازم ، ولكنه قد يعمل كتنفيذ سريع وقذر.