أشجار الصفر المضمنة في تحويلات المويجات

تُعدّ خوارزمية EZW ( أشجار الصفر المضمنة لتحويلات المويجات ) خوارزمية ضغط صور مع فقدان للبيانات . عند معدلات بت منخفضة، أي بنسب ضغط عالية، تكون معظم المعاملات الناتجة عن تحويل النطاق الفرعي (مثل تحويل المويجات ) صفرًا أو قريبة جدًا من الصفر. يحدث هذا لأن صور العالم الحقيقي غالبًا ما تحتوي على معلومات منخفضة التردد (مترابطة بشكل كبير). مع ذلك، عندما توجد معلومات عالية التردد (مثل حواف الصورة)، فإنها تُصبح بالغة الأهمية من حيث إدراك الإنسان لجودة الصورة، وبالتالي يجب تمثيلها بدقة في أي نظام ترميز عالي الجودة.

باعتبار المعاملات المُحوَّلة شجرةً (أو أشجارًا) ذات معاملات تردد منخفضة عند العقدة الجذرية، وأبناء كل عقدة في الشجرة هم المعاملات المرتبطة مكانيًا في نطاق التردد الأعلى التالي، فإن احتمالية وجود شجرة فرعية واحدة أو أكثر تتكون بالكامل من معاملات تساوي صفرًا أو قريبة من الصفر عالية جدًا، وتُسمى هذه الأشجار الفرعية بالأشجار الصفرية . لهذا السبب، نستخدم مصطلحي "العقدة" و"المعامل" بشكل متبادل، وعندما نشير إلى أبناء معامل ما، فإننا نعني معاملات أبناء العقدة في الشجرة التي يقع فيها ذلك المعامل. نستخدم مصطلح "الأبناء" للإشارة إلى العقد المتصلة مباشرةً في أسفل الشجرة، ومصطلح "الأحفاد" للإشارة إلى جميع العقد التي تقع أسفل عقدة معينة في الشجرة، حتى لو لم تكن متصلة بها مباشرةً.

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

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

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

لقد تجاوزت SPIHT والعديد من مشتقاتها أداء الترميز الخاص بـ EZW منذ ذلك الحين.

تُمكّن خوارزمية الموجات الصفرية المضمنة (EZW)، التي طورها ج. شابيرو عام 1993، من نقل الصور وفك تشفيرها على نطاق واسع. وتستند هذه الخوارزمية إلى أربعة مفاهيم أساسية: أولاً، يجب أن تكون تحويلاً موجياً منفصلاً أو تفكيكاً هرمياً للنطاقات الفرعية؛ ثانياً، يجب أن تتنبأ بانعدام المعلومات المهمة عند استكشاف التشابه الذاتي الكامن في الصور؛ ثالثاً، تتميز بتكميم التقريب المتتالي المشفر بالإنتروبيا؛ رابعاً، تُمكّن من تحقيق ضغط بيانات شامل بدون فقدان البيانات عبر الترميز الحسابي التكيفي.

إلى جانب ذلك، تتضمن خوارزمية EZW أيضًا الميزات التالية:

1. تحويل موجي منفصل يمكنه استخدام تمثيل مضغوط متعدد الدقة في الصورة.
2. ترميز Zerotree الذي يوفر تمثيلاً مضغوطاً متعدد الدقة لخرائط الأهمية.
3. التقريب المتتالي لتمثيل متعدد الدقة مضغوط للمعاملات المهمة.
4. بروتوكول تحديد الأولويات الذي يتم فيه تحديد الأهمية من خلال الدقة والحجم والمقياس والموقع المكاني لمعاملات الموجة الصغيرة بالترتيب.
5. الترميز الحسابي متعدد المستويات التكيفي هو طريقة سريعة وفعالة لترميز سلاسل الرموز باستخدام الإنتروبيا.

بيانات DCT ترتيب مسح ZeroTree (EZW) 63 -34 49 10 7 13 -12 7 AB BE BF E1 E2 F1 F2 -31 23 14 -13 3 4 6 -1 CD BG BH E3 E4 F3 F4 15 14 3 -12 5 -7 3 9 CI CJ DM DN G1 G2 H1 H2 -9 -7 -14 8 4 -2 3 2 CK CL DO DP G3 G4 H3 H4 -5 9 -1 47 4 6 -2 2 I1 I2 J1 J2 M1 M2 N1 N2 3 0 -3 2 3 -2 0 4 I3 I4 J3 J4 M3 M4 N3 N4 2 -3 6 -4 3 6 3 6 ك1 ك2 L1 L2 O1 O2 P1 P2 5 11 5 6 0 3 -4 4 ك3 ك4 L3 L4 O3 O4 P3 P4 D1: pnzt p ttt tztt tttttptt (20 رمزًا) PNZT P(t) TTT TZTT TPTT (D1 بواسطة M-EZW، 16 رمزًا) PNZT P(t) Z(t) TZ(p) TPZ(p) (D1 بواسطة NM-EZW، 11 رمزًا) PN (t)، P أو N فوق مسح شجرة الصفر PNZ(tp)، حيث p=زوج T، و t=ثلاثي T، و P/N + TT/TTT في كود D1 S1: 1010 D2: ztnp tttttttt S2: 1001 10 (نهاية ملف شابيرو PDF هنا) D3: zzzz zppnppnttnnp tpttntttttttptttptttttttttpttttttttttttt S3: 1001 11 01111011011000 D4: zzzzzzzztznzzzzpttptpptpnptntttttptpnppppttttttptptttpnp S4: 1101 11 11011001000001 110110100010010101100 D5: zzzzzztzzzzztpzzzttpttttnptppttptttnppnttttpnnptttpttpptt S5: 1011 11 00110100010111 110101101100100000000 110110110011000111 D6: zzzttztttztttttnnttt ( http://www.polyvalens.com/wavelets/ezw/ ) التفاصيل: (يتم حساب S الجديد أولاً، ويتم حساب الباقي بواسطة الدورات السابقة) الخطوة 1 21 321 فال D1 S1 R1 D2 S2 R2 D3 S3. ... آر 3 ... د 4، س 4 ... أ 63 ف 1 >=48 56 ض .1 >=56 60 ض ..1 >=60 62 ب -34 شمال 0 <48 -40 ت .0 <40 -36 ز ..0 <36 -36 C -31 IZ <32 0 N 1. >=24 -28 Z .1. >=28 -30 D 23 T <32 0 P 0. <24 20 Z .1. >=20 22 BE 49 P 1 >=48 56 .0 <56 52 Z ..0 <52 50 BF 10 T <32 0 P 0 <12 10 BG 14 T <32 0 P 1 >=12 14 BH -13 T <32 0 N 1 >=12 -14 CI 15 T <32 0 T <16 0 P 1 >=12 14 CJ 14 IZ <32 0 T <16 0 P 1 > = 12 14 CK -9 T <32 0 T <16 0 N 0 <12 -10 CL -7 T <32 0 T <16 0 T <8 0 DM 3 T <16 0 T <8 0 DN -12 T <16 0 N 1 >=12 -14 DO -14 T <16 0 N 1 >=12 -14 DP 8 T <16 0 P <12 10 E1 7 T <32 0 .E,F,G,H(1,2,3,4) E2 13 T <32 0 .I,J,K(1,2,3,4) E3 3 T <32 0 .N,O,P(1,2,3,4) E4 4 T <32 0 . J1 -1 T <32 0 . J2 47 P 0 >48 40 1 >=40 44 . J3 -3 T <32 0 J4 2 T <32 0 D = تمريرة مهيمنة (P=موجب، N=سالب، T=شجرة الصفر، IZ=صفر معزول) S = تمريرة تابعة؛ (R = القيمة المعاد بناؤها) 

• تقسيم المجموعات في الأشجار الهرمية (SPIHT)

• جيه إم شابيرو (1993). "ترميز الصور المضمن باستخدام أشجار الصفر لمعاملات المويجات". معاملات IEEE في معالجة الإشارات . 41 (12): 3445-3462 . CiteSeerX 10.1.1.131.5757 . doi : 10.1109/78.258085 . ISSN 1053-587X . S2CID 18047405. Zbl 0841.94020 . Wikidata Q56883112 .     

• كليمنس فالينز (24 أغسطس 2003). "ترميز EZW" . مؤرشف من الأصل بتاريخ 3 فبراير 2009.