البحث عن صور مماثلة ، تحليل خوارزمية واحدة

اضطررت مؤخرًا إلى حل مشكلة تحسين البحث عن صور مكررة.

يعمل الحل الحالي على مكتبة Python مشهورة إلى حد ما ، هي Image Match ، بناءً على توقيع IMAGE لأي نوع من الصور ، تأليف H. H. Wong و Marshall Bern و David Goldberg.

لعدة أسباب ، تقرر إعادة كتابة كل شيء إلى Kotlin ، مع التخلي في الوقت نفسه عن التخزين والبحث في ElasticSearch ، الأمر الذي يتطلب مزيدًا من الموارد ، الحديد والبشر ، للحصول على الدعم والإدارة ، لصالح البحث في ذاكرة التخزين المؤقت المحلية في الذاكرة.

لفهم كيف يعمل ، كان عليّ أن أغمر نفسي في رمز بيثون "المرجعي" ، لأن العمل الأصلي في بعض الأحيان ليس واضحًا تمامًا ، وفي بعض الأماكن يجعلني أتذكر "كيفية رسم بومة". في الواقع ، أود أن أشارككم نتائج هذه الدراسة ، وفي نفس الوقت أتحدث عن بعض التحسينات ، سواء من حيث حجم البيانات وسرعة البحث. ربما شخص ما سوف يأتي في متناول اليدين.

إخلاء المسئولية: هناك احتمال بأن أكون قد افسدت في مكان ما ، هل قمت به بشكل خاطئ أم لا. حسنًا ، سأكون سعيدًا بأي نقد وتعليقات. :)

كيف تعمل؟

1. يتم تحويل الصورة إلى تنسيق أبيض وأسود 8 بت (نقطة واحدة بايت واحد في القيمة 0-255)
2. يتم اقتصاص الصورة بطريقة تتجاهل 5٪ من الفرق المتراكم (أكثر أدناه) من كل جانب من الجوانب الأربعة. على سبيل المثال ، إطار أسود حول الصورة.
3. يتم تحديد شبكة عمل (9 × 9 افتراضيًا) ، حيث ستُستخدم عقدتها كنقاط مرجعية لتوقيع الصورة.
4. لكل نقطة مرجعية ، على أساس منطقة معينة من حولها ، يتم حساب سطوعها.
5. لكل نقطة مرجعية ، يتم حساب مقدارها أكثر إشراقًا / أغمق من جيرانها الثمانية. يتم استخدام خمسة تدرجات ، من -2 (أغمق كثيرًا) إلى 2 (أكثر إشراقًا).
6. كل هذا "الفرح" يتكشف في صفيف أحادي البعد (متجه) ويسمى بتوقيع الصورة.

يتم التحقق من تشابه الصورتين على النحو التالي:



انخفاض د ، كان ذلك أفضل. في الحقيقة ، d <0.3 يكاد يكون ضمانًا للهوية.

الآن بمزيد من التفاصيل.

الخطوة الأولى

أعتقد أن الحديث عن التحويل إلى تدرج الرمادي ليس له معنى كبير.

الخطوة الثانية

دعنا نقول أن لدينا صورة مثل هذا:


يمكن ملاحظة أن هناك إطارًا أسودًا يتكون من 3 بكسل على اليمين واليسار و 2 بكسل في الأعلى والأسفل ، وهو ما لا نحتاج إليه على الإطلاق مقارنة

يتم تحديد حد القطع بواسطة الخوارزمية التالية:

1. لكل عمود ، نحسب مجموع الاختلافات المطلقة للعناصر المجاورة.
   
2. نقوم بقص عدد البكسل إلى اليسار واليمين الذي تقل مساهمته في إجمالي الفرق التراكمي عن 5٪.

نحن نفعل الشيء نفسه بالنسبة للأعمدة.

توضيح مهم: إذا كانت أبعاد الصورة الناتجة غير كافية للخطوة 4 ، فنحن لا نقطعها!

الخطوة الثالثة

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

الخطوة الرابعة

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

الخطوة الخامسة

لكل نقطة مرجعية ، يتم حساب الفرق في سطوعها مع سطوع جيرانها الثمانية. بالنسبة لتلك النقاط التي لا يوجد بها جيران (الصفوف العليا والسفلى والعمود الأيمن والأيسر) ، يتم اعتبار الفرق على أنه 0.

علاوة على ذلك ، يتم تقليل هذه الاختلافات إلى خمسة تدرجات:


اتضح شيء مثل هذه المصفوفة:

الخطوة السادسة

لا أعتقد أن هناك حاجة إلى تفسير.

والآن عن التحسين

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


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


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


هذا صحيح لكل من البسط وكلا مصطلحي المقام.

كذلك في العمل الأصلي ، يلاحظ أن ثلاث وحدات بت كافية لتخزين كل تدرج. هذا ، على سبيل المثال ، في Unsigned Long سوف يتناسب مع 21 تقديرًا. هذا توفير كبير جدًا في الحجم ، لكنه ، من ناحية أخرى ، يضيف تعقيدًا عند حساب مجموع مربعات الفرق بين التوقيعين. يجب أن أقول إن هذه الفكرة اشتعلت بها كثيرًا ولم أتركها لبضعة أيام ، حتى فجر إحدى الأمسيات كيفية تناول السمك ، وهو مكان لحفظ وتبسيط الحساب. راقب يديك.

نستخدم هذا المخطط للتخزين ، 4 بت لكل تدرج:

نعم ، سيتم احتساب 16 تدرجًا فقط في Long Unsigned Long ، مقابل 21 ، ولكن بعد ذلك سيتم حساب صفيف الفرق بين التواقيعين بنقطة xor و 15 نوبة إلى اليمين مع حساب عدد البتات التي تم تعيينها لكل تكرار للتحول. أي


العلامة لا تهمنا ، حيث سيتم تربيع جميع القيم.

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

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

في الواقع ، هذا كل شيء. شكرا لاهتمامكم :)