الاستيفاء والتمييز ، لماذا هم بحاجة لتحويل الصور الإسقاطية؟

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




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

$$

$$x = \frac{t_{11} u + t_{12} v + t_{13}}{t_{31} u + t_{32} v + t_{33}}, \ \ \ y = \frac{t_{21} u + t_{22} v + t_{23}}{t_{31} u + t_{32} v + t_{33}},$$

أين $$$T = (t_{ij}), \ \ i \in \{1, 2, 3\}, \ \ j \in \{1, 2, 3\}$مصفوفة التحول الإسقاطي ، $$$(u, v)$و $$$(x, y)$ينسق على المصدر والصور المحولة.

تحويل الصور الهندسية

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

لفهم كيفية حل مشكلة التحول الهندسي للصورة الرقمية ، تحتاج إلى النظر في نموذج تكوينها من صورة بصرية على مصفوفة الكاميرا. وفقًا لـ G. Wahlberg [1] ، يجب أن تقرب الخوارزمية العملية التالية:

1. استعادة الصورة البصرية من الرقمية.
2. التحول الهندسي للصورة البصرية.
3. أخذ عينات من الصورة المحولة.

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

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

هنا ، تقابل الخطوة 3 استعادة الصورة البصرية ، والخطوتين 1 و 4 تتوافق مع أخذ العينات.

إقحام

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

سننظر في طرق الاستيفاء التالية:

• بواسطة أقرب بكسل
• خطين
• ثنائي التكعيب
• ب- شبل مكعب
• الفتحة المكعبة ، 36 نقطة.

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

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



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

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

أقرب إقحام بكسل

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

الاستيفاء Bilinear

أفضل في الجودة ، ولكنه يتطلب المزيد من الحساب بالإضافة إلى طمس حدود الكائنات.

استيفاء تكعيبي

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

الاستيفاء ب- خدد

يحتوي b-spline على نطاق ضيق للغاية ، مما يعني صورة "ضبابية" قوية (ولكن أيضًا تقليل الضوضاء بشكل جيد ، والذي يمكن أن يكون مفيدًا).

الاستيفاء على أساس شريحة هيرميت مكعب

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


كما نقارن هذه الطرق من حيث عدد مداخل الذاكرة (عدد وحدات البكسل للصورة الأصلية للاستكمال عند نقطة واحدة) وعدد الضرب حسب النقطة.

يمكن ملاحظة أن الطرق الثلاثة الأخيرة هي أكثر تكلفة من الناحية الحسابية بشكل كبير من الطريقة الأولى.

أخذ العينات

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

سنوضح بوضوح التحف الناتجة عن ضغط عينة جواز السفر الروسي وحقله الفردي - مكان الولادة (مدينة أرخانجيلسك) ، مضغوطة باستخدام أخذ العينات بكسل تلو بكسل أو خوارزمية FAST ، والتي سننظر فيها أدناه.



يمكن ملاحظة أن النص الموجود في الصورة اليسرى أصبح غير قابل للقراءة. هذا صحيح ، لأننا نأخذ نقطة واحدة فقط من منطقة كاملة من الصورة المصدر!

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

تم اختراع طرق أكثر كفاءة من الناحية الحسابية في نهاية القرن الماضي ، عندما حلت رسومات الكمبيوتر مشكلة عرض القوام المتراكب على الأشياء المسطحة. واحدة من هذه الأساليب هي التحويل باستخدام الخريطة المصغرةبناء. Mip-map هو هرم من الصور التي تتكون من الصورة الأصلية نفسها ، بالإضافة إلى نسخها التي تم تقليلها بمقدار 2 و 4 و 8 وما إلى ذلك. لكل بكسل ، نقوم بتقييم درجة انضغاط خصائصه ، ووفقًا لهذه الدرجة نختار المستوى المطلوب من الهرم ، كصورة المصدر. هناك طرق مختلفة لتقييم المستوى المناسب للخريطة mip (انظر التفاصيل [2]). هنا سوف نستخدم الطريقة القائمة على تقدير المشتقات الجزئية فيما يتعلق بمصفوفة التحول الإسقاطي المعروفة. ومع ذلك ، من أجل تجنب القطع الأثرية في مناطق الصورة النهائية حيث ينتقل مستوى واحد من بنية الخريطة المصغرة إلى مستوى آخر ، يتم استخدام الاستكمال الداخلي الخطي بين مستويين متجاورين للهرم (وهذا لا يزيد التعقيد الحسابي بشكل كبير ، لأن إحداثيات النقاط في المستويات المجاورة مرتبطة بشكل فريد).

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

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

قبل مقارنة هذه الأساليب من حيث التعقيد الحسابي ، نقوم بإجراء تحفظ من أجل تسريع حساب التحول الإسقاطي العكسي ، فمن المنطقي إجراء التغيير التالي:

$$$q(x, y) = \frac{1}{f_3(x) + g_3(y)},$
$$$u(x, y) = q(x, y)(f_1(x) + g_1(y)),$
$$$v(x, y) = q(x, y)(f_3(x) + g_3(y)),$

أين $$$f_i(x) = p_{i1} x, g_i(y) = p_{i2} y + p_{i3}, P = (p_{ij}) = T ^ {-1}, i \in \{1, 2, 3\}, j \in \{1, 2, 3\}$، $$$P$هي مصفوفة التحول الإسقاطي العكسي. مثل$$$f(x)$ و $$$g(y)$وظائف وسيطة واحدة ، يمكننا حسابها مسبقًا لفترة تتناسب مع الحجم الخطي للصورة. ثم ، لحساب إحداثيات الصورة المعكوسة لنقطة واحدة من الصورة النهائية$$$(u, v)$مطلوب قسم واحد فقط ومضاعفتين. يمكن إجراء خدعة مماثلة باستخدام مشتقات جزئية ، والتي تُستخدم لتحديد المستوى في هيكل الخريطة المصغرة أو الخريطة الممزقة.

الآن نحن على استعداد لمقارنة النتائج من حيث التعقيد الحسابي.

وقارن بصريًا (من اليسار إلى اليمين أخذ العينات بكسلًا تلو الآخر ، وأخذ عينات متفوقة بـ 49 عينة ، خريطة صغيرة ، خريطة ممزقة ، سريعة).

تجربة

الآن ، دعنا نقارن نتائجنا تجريبيا. نحن نؤلف خوارزمية تحويل إسقاطية تجمع بين كل من 5 طرق للاستيفاء و 5 طرق لتقدير (إجمالي 25 خيارًا). التقط 20 صورة من المستندات التي تم اقتصاصها إلى 512 × 512 بكسل ، وقم بإنشاء 10 مجموعات من 3 مصفوفات تحويل إسقاطية ، بحيث تكون كل مجموعة معادلة بشكل عام للتحول المتطابق ، وسنقوم بمقارنة PSNR بين الصورة الأصلية والصورة المحولة. تذكر أن PSNR$$$10 \log \frac{MAX^2}{MSE}$أين $$$MAX$هذا هو الحد الأقصى في الصورة الأصلية أ $$$MSE$- الانحراف المعياري للنهائي عن الأصل. كلما زاد PSNR كلما كان ذلك أفضل. سنقيس أيضًا وقت تشغيل التحويل الإسقاطي إلى ODROID-XU4 باستخدام معالج ARM Cortex-A15 (2000 ميجاهرتز و 2 جيجابايت رام).

طاولة وحشية مع النتائج:

ما هي الاستنتاجات التي يمكن استخلاصها؟

• يؤدي استخدام الاستيفاء بأقرب عينات بكسل أو بكسل بعد بكسل إلى جودة رديئة (كان ذلك واضحًا من الأمثلة أعلاه).
• 36 — .
• b- , , .
• Rip-map FAST , 9 ( , ?).
• mip-map b- PSNR , .

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

ملاحظة: يستند المنشور إلى التقرير: A. Trusov و E. Limonova ، "تحليل خوارزميات التحول الإسقاطية للتعرف على الصور على الأجهزة المحمولة" ، ICMV 2019 ، 11433 ed. ، Wolfgang Osten ، Dmitry Nikolaev ، Jianhong Zhou ، Ed. ، SPIE ، يناير 2020 ، المجلد. 11433 ، ISSN 0277-786X ، ISBN 978-15-10636-43-9 ، المجلد. 11433 ، 11433 0 ص ، ص. 1-8 ، 2020 ، دوى: 10.1117 / 12.2559732.