بديل لقياس المسافة في أقرب خوارزمية الجيران؟

Question

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

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

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

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

Answer 1

يبدو أنها ليست مسألة اختلاف المنتجات الداخلية بعد كل شيء ، كما أنها ليست مسألة منتج DOT نفسه. تبين أنها مسألة رياضيات بسيطة.

أساسًا...

افترض ABS (A + B) = C ، حيث C هو بعض الثابت. ستكون القيمة القصوى الممكنة لـ A * B دائمًا هي النتيجة (S) حيث A == B == +- C / 2. لذلك ، ستكون المسافة بين A و B الحد الأدنى عندما يكون منتجها الحد الأقصى ، والعكس صحيح. يعمل هذا لجميع الأرقام الحقيقية (الإيجابية والسلبية) ويمتد أيضًا إلى أبعاد متعددة ، لذلك ربما يعمل بأرقام معقدة أيضًا (على الرغم من أنني لم أختبرها مع هذا).

مثال مع C = 20:

((أ ، ب) ، المسافة ، المنتج)

((0,  20),  20.0, 0)
((1,  19),  18.0, 19)
((2,  18),  16.0, 36)
((3,  17),  14.0, 51)
((4,  16),  12.0, 64)
((5,  15),  10.0, 75)
((6,  14),  8.0,   84)
((7,  13),  6.0,   91)
((8,  12),  4.0,   96)
((9,  11),  2.0,   99)
((10 ، 10) ، 0.0 ، 100) (كما ترون ، تكون المسافة الحد الأدنى بينما يكون المنتج الحد الأقصى.)
((11, 9),   2.0,   99)
((12, 8),   4.0,   96)
((13, 7),   6.0,   91)
((14, 6),   8.0,   84)
((15, 5),   10.0, 75)
((16, 4),   12.0, 64)
((17, 3),   14.0, 51)
((18, 2),   16.0, 36)
((19, 1),   18.0, 19)
((20, 0),   20.0, 0)