image - مقارنة الصور-خوارزمية سريعة



algorithm comparison (6)

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

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

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

https://code.i-harness.com


أعتقد أن إسقاط حجم الصورة إلى حجم أيقونة تقريبًا ، مثل 48 × 48 ، ثم التحويل إلى تدرج الرمادي ، ثم أخذ الفرق بين وحدات البكسل ، أو دلتا ، يجب أن يعمل جيدًا. نظرًا لأننا نقارن التغيير في لون البيكسل ، بدلاً من لون البيكسل الفعلي ، فلن يهم إذا كانت الصورة أخف أو أغمق قليلاً. ستشكل التغييرات الكبيرة أهمية نظرًا لأنه سيتم فقدان وحدات البكسل التي تصبح خفيفة جدًا / داكنة. يمكنك تطبيق ذلك عبر صف واحد أو على العدد الذي تريده لزيادة الدقة. على الأكثر ستحصل على 47x47 = 2،209 تسميات لتكوين مفتاح قابل للمقارنة.


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

http://phash.org/

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

يقدم phash عدة أنواع من التجزئة ويمكن استخدامه للصور أو الصوت أو الفيديو.


فيما يلي ثلاث طرق لحل هذه المشكلة (وهناك العديد من الطرق الأخرى).

  • الأول هو نهج قياسي في رؤية الكمبيوتر ، ومطابقة المفتاح. قد يتطلب ذلك بعض المعرفة الأساسية للتنفيذ ، ويمكن أن تكون بطيئة.

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

  • أما الطريقة الثالثة فهي سريعة وقوية ، ولكن من المحتمل أن تكون الأكثر صعوبة في التنفيذ.

مطابقة Keypoint

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

جانب سلبي واحد للمطابقة الرئيسية هو وقت تشغيل تطبيق ساذج: O (n ^ 2m) ، حيث n هو عدد نقاط المفاتيح في كل صورة ، و m هو عدد الصور في قاعدة البيانات. قد تجد بعض الخوارزميات الذكية أقرب تطابق أسرع ، مثل quadtrees أو تقسيم الفضاء الثنائي.

الحل البديل: طريقة الرسم البياني

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

إن حساب الرسم البياني للألوان هو أمر بسيط ، فما عليك سوى اختيار نطاق دلاء المدرج التكراري ، ولكل مجموعة عدد وحدات البكسل ذات اللون في هذا النطاق. على سبيل المثال ، ضع في الاعتبار المدرج التكراري "الأخضر" ، ونفترض أن نختار 4 شرائح لمدرجنا البياني: 0-63 و64-127 و 128-191 و 192-255. ثم ، بالنسبة إلى كل بكسل ، ننظر إلى القيمة الخضراء ، ونضيف رصيدًا إلى الدلو المناسب. عند الانتهاء من إجراء الحصر ، نقوم بتقسيم كل مجموعة من مجموعات البيانات على عدد البكسلات في الصورة بأكملها للحصول على رسم بياني عادي للقناة الخضراء.

بالنسبة إلى الرسم البياني لتوجه النسيج ، بدأنا عن طريق إجراء كشف الحافة على الصورة. تحتوي كل نقطة حافة على متجه عادي يشير في الاتجاه العمودي إلى الحافة. قمنا بتكبير زاوية vector العادية في واحدة من 6 دلاء بين 0 و PI (نظرًا لأن الحواف لها تماثل 180 درجة ، قمنا بتحويل الزوايا بين -PI و 0 إلى ما بين 0 و PI). بعد حساب عدد نقاط الحواف في كل اتجاه ، يوجد لدينا رسم بياني غير مقيس يمثل اتجاه النسيج ، والذي قمنا بتسويته بقسمة كل مجموعة على العدد الإجمالي لنقاط الحواف في الصورة.

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

لديك الآن 5 رسومات بيانية لكل صورة. لمقارنة صورتين ، فإنك تأخذ القيمة المطلقة للفرق بين كل دلو مدرج تكراري ، ثم تجمع هذه القيم. على سبيل المثال ، لمقارنة الصور A و B ، سنحسب

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

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

الخيار الثالث - Keypoints + أشجار القرار

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

تحديث :

خطأي - لا يتعلق ورق غابات النصوص الدلالية بالتحديد بالتطابق مع الصور ، ولكن بالأحرى تسمية المنطقة. الورقة الأصلية التي تتطابق مع هذا هو: التعرف على Keypoint باستخدام الأشجار العشوائية . أيضا ، تستمر الأوراق أدناه في تطوير الأفكار وتمثل حالة الفن (c. 2010):


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

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


لدي فكرة ، والتي يمكن أن تعمل وعلى الأرجح أن تكون سريعة جدا. يمكنك أخذ عينة من الصورة لتقول دقة 80x60 أو مقارنتها ، وتحويلها إلى مقياس رمادي (بعد أخذ عينة فرعية سيكون أسرع). قم بمعالجة الصورتين اللتين تريد مقارنتهما. ثم قم بتشغيل المجموع الطبيعي للفروق المربعة بين صورتين (صورة الاستعلام وكل منها من db) ، أو حتى أفضل ارتباط متقاطع عادي ، والذي يعطي الاستجابة أقرب إلى 1 ، إذا كانت الصورتين متشابهتين. ثم إذا كانت الصور متشابهة يمكنك الانتقال إلى تقنيات أكثر تطوراً للتحقق من أنها نفس الصور. من الواضح أن هذه الخوارزمية خطية من حيث عدد الصور في قاعدة البيانات الخاصة بك ، على الرغم من أنها ستكون سريعة للغاية تصل إلى 10000 صورة في الثانية على الأجهزة الحديثة. إذا كنت بحاجة إلى الثبات للدوران ، فيمكن حساب التدرج السائد لهذه الصورة الصغيرة ، ومن ثم يمكن تدوير نظام الإحداثيات بأكمله إلى التوجه الكنسي ، على الرغم من ذلك ، سيكون أبطأ. لا ، ليس هناك ثبات للقياس هنا.

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


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

بالنسبة للحل العام ، من الأفضل استخدام عدة استراتيجيات. كل خوارزمية هي الأنسب لأنواع معينة من تحويلات الصور ويمكنك الاستفادة من ذلك.

في الجزء العلوي ، أسرع الخوارزميات. في الجزء السفلي أبطأ (على الرغم من دقة أكثر). يمكنك تخطي الأخطاء البطيئة في حالة العثور على تطابق جيد على المستوى الأسرع.

  • يستند إلى ملف التجزئة (md5 ، sha1 ، الخ) للحصول على التكرارات الدقيقة
  • تجزئة إدراكية (phash) للصور المقطوعة
  • تستند إلى الميزة (SIFT) للصور المعدلة

أواجه نتائج جيدة للغاية مع Phash. دقة جيدة للصور rescaled. إنها ليست جيدة للصور المعدلة (بشكل ملموس) (اقتصاص ، استدارة ، مرايا ، إلخ). للتعامل مع سرعة التجزئ ، يجب أن نستخدم ذاكرة التخزين المؤقت / قاعدة البيانات للحفاظ على تجزئات كومة القش.

الشيء الجميل حقا حول phash هو أنه بمجرد بناء قاعدة البيانات الخاصة بك (والتي بالنسبة لي هي حوالي 1000 صورة / ثانية) ، يمكن أن تكون عمليات البحث سريعة جدا ، خاصة عندما يمكنك الاحتفاظ بقاعدة بيانات التجزئة بالكامل في الذاكرة. هذا أمر عملي إلى حدٍ ما نظرًا لأن التجزئة لا تتعدى 8 بايت فقط.

على سبيل المثال ، إذا كان لديك 1 مليون صورة ، فستحتاج إلى مجموعة من 1 مليون من قيم التجزئة 64 بت (8 ميغابايت). على بعض وحدات المعالجة المركزية (CPUs) هذا يناسب في ذاكرة التخزين المؤقت L2 / L3! في الاستخدام العملي لقد رأيت corei7 مقارنة في أكثر من 1 جيجا-هام / ثانية ، هو فقط مسألة عرض النطاق الترددي الذاكرة إلى وحدة المعالجة المركزية. هناك قاعدة بيانات بحجم مليار صورة عملية على وحدة معالجة مركزية 64 بت (8 جيجا بايت ذاكرة الوصول العشوائي) ولا تزيد عمليات البحث عن ثانية واحدة!

بالنسبة للصور المعدلة / التي تم اقتصاصها ، يبدو أنها ميزة / كاشف مفتاح ثابت للتحويل مثل SIFT هي الطريقة المثلى. سوف تنتج SIFT نقاط المفاتيح الجيدة التي ستكتشف المحاصيل / التدوير / المرآة الخ. ومع ذلك فإن مقارنة الواصف تكون بطيئة للغاية مقارنة بمسافة التعثر المستخدمة من قبل phash. هذا هو القيد الرئيسي. هناك الكثير من عمليات المقارنة للقيام به ، حيث يوجد الحد الأقصى من واصف IxJxK يقابله البحث عن صورة واحدة (I = num haystack images، J = target keypoints لكل صورة haystack، K = target keypoints لكل صورة إبرة).

للالتفاف حول مشكلة السرعة ، حاولت استخدام phash حول كل نقطة مفتاح موجودة ، باستخدام حجم / نصف قطر الميزة لتحديد المستطيل الفرعي. الخدعة لجعل هذا العمل بشكل جيد ، هو أن ينمو / يتقلص نصف القطر لتوليد مستويات مختلفة من المستويين الفرعي (على صورة الإبرة). عادةً ما يتطابق المستوى الأول (بدون تحديد) معًا في كثير من الأحيان يتطلب الأمر بضع مرات أخرى. لست متأكداً بنسبة 100٪ لماذا يعمل هذا ، ولكن يمكنني أن أتخيل أنه يمكن الميزات التي تكون صغيرة جداً لكي تعمل phash (صور مقياس phash إلى 32x32).

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

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

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

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

يمكن أن تحتوي صورة الإبرة على نقاط أساسية أقل من صور كومة القش ولا تزال تحصل على نتائج جيدة. إضافة المزيد ليس بالضرورة أن تحصل على مكاسب ضخمة ، على سبيل المثال مع J = 400 و K = 40 ، معدل نجاحي هو حوالي 92٪. مع J = 400 و K = 400 ، يصل معدل الضرب إلى 96٪ فقط.

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





computer-vision