طور ميخائيل بسميلتسيف وزميله خوارزميات جديدة لتوجيه الرسومات

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

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

ظهرت أول خوارزميات توجيه الصور في أوائل التسعينات و
تستخدم في أدوات تحرير المتجهات مثل Adobe Illustrator (Live Trace) و CorelDRAW (PowerTRACE) و Inkscape. على الرغم من اعتمادها على نطاق واسع في الصناعة ، لا تزال هذه الخوارزميات تعاني من أوجه قصور خطيرة وهي قيد التطوير النشط. في العديد من الصناعات التي تكون فيها الرسوم المتحركة أمرًا بالغ الأهمية ، بما في ذلك الرسوم المتحركة والهندسة التقليدية ، غالبًا ما يتم ذلك يدويًا. يتتبع المصممون بدقة الصورة الممسوحة ضوئيًا باستخدام أدوات الرسم.

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

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


أ) يمكن أن يؤدي النهج المحلي للتحول الانتقالي ، الذي اقترحه نوريس وزملاؤه في عام 2013 ، إلى اتصالات غير صحيحة أو غير دقيقة. ب) يمكن لطريقة Favreaux وآخرون (2016) أن تنتج نتيجة تنحرف بشكل كبير عن الأصل النقطي. (ج) الطريقة الجديدة التي اقترحها Bessmeltsev و Solomon تتفوق على التصميمات السابقة للتوجيه

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

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


في المجال المجهز ، يتم محاذاة المجال في المنحنى الأصلي على الأقل باتجاه واحد ، ويتم محاذاته في كلا الاتجاهين بالقرب من تقاطع X و T

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

أمثلة

(تفتح صورة عالية الدقة عند النقر)


حساسية الأداة للتغيرات الصغيرة في الصورة الأصلية






الطريقة ليست حساسة لدقة الصورة الأصلية.


يعمل Vectorization بشكل جيد حتى على إصدار أصلي صاخب جدًا

ستعمل الأداة الجديدة على تسهيل حياة المصممين والرسامين بشكل كبير: "وفقًا لتقدير تقريبي ، ستوفر من 20 إلى 30 دقيقة عند العمل باستخدام الأدوات الآلية [في كل صورة]. يقول ميخائيل بسميلتسيف ، المؤلف الرئيسي للعمل العلمي ، موظف سابق في CSAIL ، وأستاذ مساعد في جامعة مونتريال: "هذه نتيجة مهمة للرسامين الذين يعالجون الكثير من الرسومات". "نأمل أن نجعل أدوات التهيئة الآلية أكثر ملاءمة للفنانين الذين يهتمون بجودة عملهم."

تم نشر المقالة العلمية في 5 يناير 2018 على موقع الطباعة المسبقة arXiv.org ( الإصدار الثاني من المقالة هو 5 سبتمبر 2018 ، arXiv: 1801.01922v2). مقبول للنشر في المجلة العلمية ACM Transactions on Graphics .