محسن متوسط ​​التحويل الكمي المتتابع

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

وفقًا لورقة أخرى بعنوان SMQT-based Tone Mapping Operators لصور النطاق الديناميكي العالي ، فإنها ستنتج "صورة بتفاصيل محسّنة". تصف الورقة طريقتين لتطبيق هذا التحول على صورة.

1. تطبيق SMQT على نصوع كل بكسل - يصف الصيغة للحصول على النصوع من RGB لكل بكسل.

2. قم بتطبيق SMQT على كل قناة من RGB بشكل منفصل - للقنوات R و G و B بشكل فردي.

الصورة التالية توضح نتيجة التقنيتين:

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

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

خوارزمية SMQT

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

افترض أن لدينا المتجه التالي (يمكنك التفكير فيه كمصفوفة):

في حالة وجود صورة ملونة ، يمكننا التفكير فيها على أنها ثلاثة متجهات منفصلة ، يمثل كل منها قناة لونية معينة (RGB) ، ويمثل كل عنصر من عناصر المتجه شدة البكسل المقابل.

الخطوات المتبعة في تطبيق خوارزمية SMQT هي:

1. احسب متوسط ​​المتجه ، وهو في هذه الحالة 29.58.

2. اقسم المتجه إلى قسمين ، واترك الأعداد الأصغر أو التي تساوي 29.58 في النصف الأيسر ، والأرقام الأكبر في النصف الأيمن:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   الصف الثاني هو الكود الذي سننشئه لكل قيمة. القيم الأقل من أو التي تساوي 29.58 تحصل على 0 في كودها ، والأرقام الأكبر من 29.58 تحصل على 1 (هذا ثنائي).

3. الآن يتم تقسيم كلا المتجهين الناتج بشكل فردي ، بطريقة تعاودية ، باتباع نفس القاعدة. في مثالنا ، متوسط ​​المتجه الأول هو (15 + 4 + 0 + 5 + 18) / 5 = 8.4 ، ومتوسط ​​المتجه الثاني هو (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48.7. يتم تقسيم كل من هذين المتجهين إلى متجهين إضافيين ، ويتم إضافة جزء ثانٍ من التعليمات البرمجية لكل منهما اعتمادًا على مقارنته مع المتوسط. هذه هي النتيجة:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   لاحظ أنه تم إلحاق 0 مرة أخرى للأرقام الأقل من أو تساوي المتوسط ​​(لكل متجه) و 1 للأرقام الأكبر من المتوسط.

4. تتكرر هذه الخوارزمية بشكل متكرر:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

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

حتى الآن لدينا مستوى تكميم L = 5. إذا كنا سنستخدم L = 8 ، فيجب أن نلحق ثلاثة أصفار بكل كود. ستكون نتيجة تحويل كل رمز من ثنائي إلى عدد صحيح (لـ L = 8):

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

لاحظ أنه في المتجه الناتج:

• تمت إزالة الكسب. كان للكسب الأصلي ربحًا منخفضًا ، حيث انتقل نطاقه من 0 إلى 64. الآن ينتقل مكاسبه من 0 إلى 240 ، وهو ما يمثل تقريبًا نطاق 8 بت بالكامل. يُقال أنه تمت إزالة الكسب لأنه لا يهم إذا ضربنا جميع عناصر المتجه الأصلي في رقم ، مثل 2 ، أو إذا قسمنا الكل على 2 ، فسيكون متجه الإخراج متماثلًا تقريبًا. سيكون مداها حول النطاق الكامل لمتجه الوجهة (8 بتات لـ L = 8). إذا قمنا بضرب متجه الإدخال في اثنين ، فسيكون متجه المخرجات هو نفسه في الواقع ، لأنه في كل خطوة ستظل نفس الأرقام التي كانت أسفل أو أعلى من المتوسط ​​أسفله أو فوقه ، وسنضيف نفس 0 أو 1 في الإخراج. فقط إذا قسمناها ، فستكون النتيجة متطابقة تقريبًا ، وليست متطابقة تمامًا ، لأنه يجب تقريب الأرقام الفردية مثل 15 وقد تختلف الحسابات بعد ذلك. انتقلنا من صورة مظلمة إلى صورة تتراوح وحدات البكسل الخاصة بها من الألوان الداكنة (0) إلى الألوان الفاتحة (240) ، باستخدام النطاق الكامل.
• تمت إزالة التحيز ، على الرغم من أننا لا نستطيع ملاحظته تمامًا في هذا المثال. هذا لأنه ليس لدينا أي تحيز لأن أدنى قيمة لدينا هي 0. إذا كان لدينا بالفعل تحيز ، فسيتم إزالته. إذا أخذنا أي رقم 'K' وأضفناه إلى كل عنصر من عناصر متجه الإدخال ، فلن يختلف حساب الأرقام أعلى وأسفل المتوسط ​​في كل خطوة. سيظل الإخراج كما هو. سيؤدي هذا أيضًا إلى جعل الصور ساطعة جدًا بحيث لا تتحول إلى صور تتراوح من الألوان الداكنة إلى الألوان الفاتحة.
• لدينا صورة مع تفاصيل محسنة. لاحظ كيف لكل خطوة تكرارية نتخذها نحن في الواقع نقوم بتكبير التفاصيل ، وبناء المخرجات من خلال الكشف عن تلك التفاصيل قدر الإمكان. ونظرًا لأننا سنطبق هذه التقنية على كل قناة RGB ، فسوف نكشف أكبر قدر ممكن من التفاصيل ، على الرغم من فقدان المعلومات حول النغمات الأصلية لكل لون.

إعطاء صورة مثل متجه وحدات البكسل RGB ، حيث تكون كل نقطة 8 بت لـ R و 8 لـ G و 8 لـ B ؛ يمكننا استخراج ثلاثة نواقل منه ، واحد لكل لون ، وتطبيق الخوارزمية على كل متجه. ثم نقوم بتشكيل متجه RGB مرة أخرى من نواقل الإخراج الثلاثة هذه ولدينا الصورة المعالجة SMQT ، كما هو الحال مع أحد مسرح Bruin.

تعقيد

تتطلب الخوارزمية أنه بالنسبة لكل مستوى من مستويات التكمية (L) ، يجب فحص عناصر N في المرور الأول للعثور على المتوسط ​​لكل متجه ، ثم في التمرير الثاني ، يجب مقارنة كل عنصر من عناصر N مع المتوسط ​​المقابل في من أجل تقسيم كل متجه بدوره. أخيرًا ، يجب استبدال عناصر N برموزها. لذلك فإن تعقيد الخوارزمية هو O ((L * 2 * N) + N) = O ((2 * L + 1) * N) ، وهو O (L * N).

الرسم البياني المستخرج من الورقة يتوافق مع تعقيد O (L * N). كلما انخفض حرف L ، زادت سرعة المعالجة بطريقة خطية تقريبًا (عدد أكبر من الإطارات في الثانية). من أجل تحسين سرعة المعالجة ، تقترح الورقة خفض قيم L: "اختيار مستوى L أقل يمكن أن يكون طريقة مباشرة لتقليل سرعة المعالجة ولكن بجودة صورة منخفضة".

تحسين

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

لا يمكن تقسيم المتجهات بعد الآن ، ويجب إلحاق الأصفار حتى نصل إلى L.

من أجل البساطة ، لنفترض أن الإدخال يمكن أن ينتقل من 0 إلى 31 ، والإخراج من 0 إلى 7 (L = 3) ، كما يمكن رؤيته في المثال.

لاحظ أن حساب متوسط ​​المتجه الأول (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 يعطي نفس النتيجة مثل حساب متوسط ​​المتجه الأخير بأكمله ، لأنه فقط نفس المتجه مع العناصر بترتيب مختلف: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

في الخطوة الثانية ، يجب أن نحسب كل متجه بشكل متكرر. لذلك نحسب متوسط ​​المدخلات الرمادية ، وهي العناصر الستة الأولى ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8) ، ومتوسط ​​المدخلات الفارغة ، وهي العناصر الأربعة الأخيرة ((25 + 31 + 31 + 25) / 4 = 28):

لاحظ مرة أخرى أنه إذا استخدمنا المتجه الأخير ، الذي تم طلبه بالكامل ، فإن النتائج هي نفسها. بالنسبة للعناصر الستة الأولى لدينا: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8) ، وللعناصر الأربعة الأخيرة: ((25 + 25 + 31 + 31) / 4 = 28) . نظرًا لأنها مجرد إضافة ، فإن ترتيب المجموعات لا يهم.

الأمر نفسه ينطبق على الخطوة التالية:

الحسابات هي نفسها كما في المتجه الأخير: ((7 + 1 + 1 + 7) / 4 = 4) ستكون مساوية لـ ((1 + 1 + 7 + 7) / 4 = 4).

وينطبق الشيء نفسه على باقي المتجهات والخطوات.

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

دعونا نرى خطوات تطبيق ما سنسميه خوارزمية FastSMQT على مثالنا:

1. قم بإنشاء جدول مكون من 32 عمودًا و 3 صفوف كما ترى أدناه. يمثل الصف الأول في الجدول فهرس الجدول (0 إلى 31) وليس من الضروري تضمينه عند ترميز الجدول. ولكن من الواضح أنه يجعل هذا المثال أسهل في المتابعة.

2. كرر العناصر N بمجرد حساب تكرار كل قيمة. في مثالنا ، العناصر 1 و 7 و 16 و 25 و 31 لها تردد 2. كل العناصر الأخرى لها تردد 0. هذه الخطوة لها تعقيد O (N).

3. الآن بعد أن تم ملء متجه التردد ، نحتاج إلى تكرار هذا المتجه (متجه الترددات ، وليس متجه الإدخال). لم نعد نكرر عناصر N بعد الآن ، ولكن R (تكون R في النطاق: 2 ^ L) ، والتي في هذه الحالة هي 32 (0 إلى 31). عند معالجة وحدات البكسل ، يمكن أن يصل عدد N إلى عدة ملايين (ميغا بكسل) ، ولكن R عادةً يكون 256 (متجه واحد لكل لون). في مثالنا هو 32. سنملأ الصفين التاليين من الجدول في نفس الوقت. سيحتوي أول هذه الصفوف (الثاني من الجدول) على مجموع الترددات حتى الآن. الثاني (الثالث من الجدول) سيكون مجموع قيمة جميع العناصر التي ظهرت حتى الآن.

   في مثالنا ، عندما نصل إلى 1 ، نضع 2 في الصف الثاني من الجدول لأن اثنين من الآحاد ظهرت حتى الآن. ونضع أيضًا 2 في الصف الثالث من الجدول ، لأن 1 + 1 = 2. نستمر في كتابة هاتين القيمتين في كل من المواضع التالية حتى نصل إلى 7. نظرًا لأن الرقم 7 يظهر مرتين ، فإننا نضيف 2 إلى تراكم الصف الثاني ، لأنه ظهر الآن 4 أرقام (1 ، 1 ، 7 ، 7). ونضيف 7 + 7 = 14 إلى الصف الثالث ، مما ينتج عنه 2 + 14 = 16 ، لأن 1 + 1 + 7 + 7 = 16. نستمر في هذه الخوارزمية حتى ننتهي من تكرار تلك العناصر. تعقيد هذه الخطوة هو O (2 ^ L) ، وهو في حالتنا O (32) ، وعند العمل باستخدام RGB بكسل يكون O (256).

   أنا	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   ن	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   ن التراكمي	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   مجموع	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

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

   أنا	1	7	16	25	31
   ن	2	4	6	8	10
   مجموع	2	16	48	98	160

5. تذكر أنه يمكننا استخدام المتجه الأخير (المرتب بالكامل) لإجراء العمليات الحسابية لكل خطوة وستظل النتائج كما هي. لاحظ أنه هنا ، في هذا الجدول ، لدينا متجه آخر مع جميع الحسابات المسبقة التي تم إجراؤها بالفعل.

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

   نحتاج أولاً إلى حساب متوسط ​​جميع العينات. يمكننا العثور عليه بسهولة عن طريق: sum [31] / n [31] = 160/10 = 16. لذلك قمنا بتقسيم الجدول إلى متجهين ، ونبدأ في كتابة الكود الثنائي لكل منهما:

   أنا	1	7	16	25	31
   ن	2	4	6	8	10
   مجموع	2	16	48	98	160
   الشفرة	0	0	0	1	1

   الآن نقوم بتقسيم كل متجه مرة أخرى. متوسط ​​المتجه الأول هو: sum [16] / n [16] = 48/6 = 8. ومتوسط ​​المتجه الثاني هو: (sum [31] - sum [16]) / (n [31] - ن [16]) = (160-48) / (10-6) = 112/4 = 28.

   أنا	1	7	16	25	31
   ن	2	4	6	8	10
   مجموع	2	16	48	98	160
   الشفرة	00	00	01	10	11

   لا يوجد سوى متجه واحد متبقي للانقسام. المتوسط ​​هو: sum [7] / n [7] = 16/4 = 4.

   أنا	1	7	16	25	31
   ن	2	4	6	8	10
   مجموع	2	16	48	98	160
   الشفرة	000	001	010	100	110

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

   تعقيد هذه الخطوة هو O (L * (2 ^ L)) ، والذي بالنسبة لـ L = 8 ، وفي احتياجات معالجة الصور العملية ، يكون O (8 * (256)) = O (2048) = ثابت.

6. الخطوة الأخيرة هي تكرار N العناصر مرة أخرى واستبدال العنصر بكوده لكل عنصر: element [i] = code [i]. التعقيد هو O (N). تعقيد FastSMQT هو O (N) + O (2 ^ L) + O (L * (2 ^ L)) + O (N) = O (2 * N) + O ((L + 1) * (2 ^ L)) = O (N + L * (2 ^ L)).

تماثل

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

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

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

مقارنة التعقيد

التعقيد الكلي لخوارزمية SMQT الأصلية هو O ((2 * L + 1) * N) ، وهو O (L * N).

تعقيد FastSMQT هو O (N) + O (2 ^ L) + O (L * (2 ^ L)) + O (N) = O (2 * N) + O ((L + 1) * (2 ^ L)) = O (N + L * (2 ^ L)).

بالنظر إلى L ثابت ، يصبح التعقيد فقط O (N) لكليهما. لكن الثابت الذي يضربه N يكون أصغر بكثير بالنسبة لـ FastSMQT ، ويحدث فرقًا كبيرًا في وقت المعالجة كما سنرى.

يقارن الرسم البياني التالي أداء كل من خوارزميات SMQT و FastSMQT لـ L = 8 ، وهي حالة معالجة الصور. يوضح الرسم البياني الوقت (بالملي ثانية) الذي تستغرقه معالجة عناصر N. لاحظ أن التعقيد (مع الثوابت) لـ SMQT لـ L = 8 هو O (17 * N) ، بينما بالنسبة لـ FastSMQT هو O (2 * N + 2304).

كلما كان N أكبر ، كلما استغرق SMQT وقتًا أطول لمعالجة الصورة. من ناحية أخرى ، بالنسبة لـ FastSMQT ، يكون النمو أبطأ بكثير.

بالنسبة إلى القيم الأكبر لـ N ، يكون الاختلاف في الأداء أكثر وضوحًا:

هنا يستغرق SMQT عدة ثوانٍ من الوقت لمعالجة صور معينة ، بينما لا يزال FastSMQT يقع ضمن منطقة "بضع ميلي ثانية".

حتى مع وجود نوى متعددة (اثنان ، في هذه الحالة) ، من الواضح أن FastSMQT لا يزال متفوقًا على SMQT فقط:

لا يعتمد FastSMQT على L. SMQT ، من ناحية أخرى ، يعتمد خطيًا على قيمة L. على سبيل المثال ، مع N = 67108864 ، يزيد وقت تشغيل SMQT مع زيادة قيمة L ، بينما لا يقوم FastSMQT بما يلي:

خاتمة

ليست كل تقنيات التحسين قابلة للتطبيق على جميع الخوارزميات ، وغالبًا ما يكون مفتاح تحسين أداء الخوارزمية مخفيًا ضمن بعض الأفكار حول كيفية عمل الخوارزمية. تستفيد خوارزمية FastSMQT هذه من إمكانيات الحساب المسبق للقيم وطبيعة الحسابات المتوسطة. ونتيجة لذلك ، فإنه يسمح بمعالجة أسرع من SMQT الأصلي. لا تتأثر السرعة بزيادة L ، على الرغم من أن L لا يمكن أن تكون أكبر بكثير من المعتاد 8 لأن استخدام الذاكرة هو 2 ^ L ، وهو رقم مقبول بالنسبة لـ 8 وهو 256 (عدد الأعمدة في جدول التردد لدينا) ، ولكن زيادة الأداء له فوائد عملية واضحة.

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

يتوفر كود C ++ لخوارزميات SMQT و FastSMQT على GitHub.