خوارزمية لقياس اختلاف مسارات قطاع الخط

Question

لنفترض أن لدي مسارين لخطين ، مثل مجموعة فرعية من الأمثلة أدناه. كيف يمكنني تحديد الفرق بينهما؟

1. |__
2. \_
3. __
4. /\
5. \/
6. |
7. _

قد يكون للمسارين عدد مختلف من الأجزاء ، وطول كل جزء والزاوية بينهما متغير.

كنت أفكر أنه سيكون من الجيد إنشاء نظام إحداثيات وتحديد الأجزاء كعقد وحواف. ربما يمكن قياس الفرق من خلال العمليات اللازمة لتحويل واحد إلى الآخر ، على غرار مسافة Levenshtein خوارزمية. للأسف مساحة العملية ضخمة. أيه أفكار؟ شكرًا!

Answer 1

سأذهب إلى أبعد قليلاً مما أشار إليه Awoodland: كيف تحددها تعتمد تماما لماذا تريد تحديد الفرق.

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

إذا كنت ترغب في إنشاء رمز التجزئة ، أقترح إنشاء CRCs 32 بت (أو شيء مشابه): واحد لأطوال القطاع والآخر للزوايا. بمجرد حساب تلك CRCs ، ضعها معًا بقيمة 64 بت مع الزوايا في 32 بت عالية والأطوال في 32 بت منخفضة. اعتمادًا على عدد الأجزاء ، ربما ستفعل قيمة CRC واحدة: لكل جزء ، أضف الطول ثم الزاوية بينه وبين الجزء التالي.

لاحظ أنه من المحتمل أن يمنحك ما سبق رقمًا فريدًا لكل مسار ، ولكن ليس مضمونًا.

إذا كنت ترغب في تحديد تعقيد مسار قطاع الخط ... ليس لدي الكثير من الأفكار.

Answer 2

يمكنك رسمها إلى صور ثابتة الحجم ثم استخدام المسافة الإقليدية لمقارنة الصور.

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

كيف تحددها إلى حد ما تعتمد على لماذا تريد تحديد الفرق بينهما.

Answer 3

يمكنك إلقاء نظرة على هذه الورقة:

http://www.vision.ee.ethz.ch/~calvin/publications/ferrari07pami.pdf

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

واصفنا ليس ثابتًا للتناوب ، لذلك قد لا يناسبك.

Answer 4

إذا كنت تستخدم العمليات:

• أضف الزاوية والقطاع
• إزالة الزاوية والجزء
• شريحة التمدد (مع وزن الفرق)
• الزاوية المنحنى (مع وزن الفرق)

ستظل قادرًا على استخدام مسافة Levenshtein بينما لا تزال في وقت n^2.

قم بتشفير الأجزاء على النحو التالي [الجزء ، الزاوية]*. لذلك سيكون:

[length, rotation] [length, rotation]...

حيث يكون الدوران كله لاتجاه توجيه القطاع.

حساب التمدد والانحناء واضح تماما. Value[i-1, j-1] + stretch + bend.

حساب إضافة/إزالة. يضيف Value[i,j-1] + Cost of adding, ، إزالة Value[i-1, j] + cost of removal.