تعرف على تقنيات ضغط الصور

الضغط باستعمال طريقة SPHIT:

هذا الموضوع طويل جدا, سأقدم هنا شرحا مختصرا جدا حتى ننتقل إلى البرنامج.

رأينا أن JPEG يعتمد على TCD بينما SPHIT يعتمد على TOD (Transformation en ondelettes), الفكرة هي أن نجري عملية ضرب بين معاملات مصفوفة الصورة و معاملات الـ ondelettes, و لهذا فإن الـ ondelette سنمثلها بمصفوفة, في الحقيقة سيكون هناك مصفوفتان, الأولى تمثل المصفاة passe-bas و الثانية تمثل المصفاة passe-haut.

هناك عدد لا بأس به من les ondelettes, مثلا هنا لدينا l’ondelette de Haar و كذلك l’ondelette de Daubechies:

Ondelette de Haar :
Passe-Bas : [0.71; 0.71]
Passe-Haut :[-0.71 ; 0.71]

Ondelette de Daubechies :
Passe-Bas : [0.027 ; -0.017 ; -0.078 ; 0.267 ; 0.603 ; 0.267 ; -0.078 ; -0.017 ; 0.027]
Passe-Haut: [0 ; 0 ; 0.046 ; -0.029 ; -0.296 ; 0.558 ; -0.296 ; -0.029 ; 0.046]

كيف يتم التحليل؟

مبدأ التحليل هو تقسيم المصفوفة باستعمال زوج من الفلاتر (h et g), الفيلتر g سيعطي كنتيجة التفاصيل أو معاملات الـ ondelette(les coefficients d’ondelettes), أما الآخر h فسيعطي

القيم التقريبية (les coefficients d’approximation) والتي بدورها سيتم تحليلها من جديد.

يمثل الحرف H نتيجة التحليل باستخدام الفيلتر h أو passe-haut, أما L فهي نتيجة الفيلتر passe-bas أو g.

العملية downsampling بواسطتها نختار عينة من نتيجة التصفية, بما أن H و L لهما نفس حجم الصورة الأصلية فيجب أن نأخذ منهما فقط النصف حتى ندمجهما لنحصل على صورة أخرى لها نفس حجم الصورة الأصلية, مثلا نأخذ من H المعاملات ذات الفهرس الفردي ومن L نأخذ المعاملات ذات الفهرس الزوجي.

أما العملية convolution فهي عملية تطبيق الفلاتر على الصورة.

كمثال على ذلك:

Cas d’ondelettes orthogonales:

ليكن لدينا المصفوفة s0(n), لنقم بتصفية المصفوفة إلى قسمين, s التي تمثل l’approximation و d التي هي التفاصيل بحيث:

الفلاتر passe-haut (g) و passe-bas (h) مرتبطان حسب القاعدة التالية:

g(n) = (-1)^n * h(n – 1)

أما العملية العكسية فتتم باستخدام زوج عكسي من الفلاتر وباستعمال هذه الصيغة:

مثلا, و باستعمال مصفاة Daubechie D4 :

هناك الكثير ليقال عن طرق التصفية و لكن ليس هنا, تلك فقط لمحة خاطفة.

عميلة التصفية ما هي إلا مرحلة من طريقة الضغط باستعمال SPHIT, فبعد التصفية يتم تجميع المعاملات الناتجة على شكل شجرة (arbre) كالتالي:

و ينتج لدينا ثلاثة أنواع من الأشجار:

D(i,j): مجموعة كل أطراف الشجرة التي تبدأ من المعامل (i,j).

O(i,j): مجموعة الأطراف المباشرة.

L(i,j): هي المجموعة D(i,j) – O(i,j).

ثم نستعمل بعد ذلك ثلاث قوائم, LIP, LIS و LSP ثم نطبق الألغوريتم التالي الذي يحتوي على مرحلتين, مرحلة الـSorting و مرحلة الـ refinement:

1. Initialization: Set n to _log2 maxi,j(ci,j)_ and transmit n. Set the LSP to empty. Set the LIP to the coordinates of all the roots (i, j) ∈ H. Set the LIS to the coordinates of all the roots (i, j) ∈ H that have descendants.
2. Sorting pass:
2.1 for each entry (i, j) in the LIP do:
2.1.1 output Sn(i, j);
2.1.2 if Sn(i, j) = 1, move (i, j) to the LSP and output the sign of ci,j ;
2.2 for each entry (i, j) in the LIS do:
2.2.1 if the entry is of type A, then
• output Sn(D(i, j));
• if Sn(D(i, j)) = 1, then
∗ for each (k, l) ∈ O(i, j) do:
・ output Sn(k, l);
・ if Sn(k, l) = 1, add (k, l) to the LSP, output the sign of ck,l;
・ if Sn(k, l) = 0, append (k, l) to the LIP;
∗ if L(i, j) _= 0, move (i, j) to the end of the LIS, as a type-B entry, and go to step 2.2.2; else, remove entry (i, j) from the LIS;
2.2.2 if the entry is of type B, then
• output Sn(L(i, j));
• if Sn(L(i, j)) = 1, then
∗ append each (k, l) ∈ O(i, j) to the LIS as a type-A entry:
∗ remove (i, j) from the LIS:
3. Refinement pass: for each entry (i, j) in the LSP, except those included in the last sorting pass (the one with the same n), output the nth most significant bit of |ci,j |;
4. Loop: decrement n by 1 and go to step 2 if needed.

كمثال, نفترض أن هذه المصفوفة (على اليسار)هي الناتجة عن تصفية الصورة المراد ضغطها:

أما على اليمين فنجد الشجرة التي تربط المعاملات.

2ⁿ = 2⁴ = 16.

هل المعامل (1,1) دال (دال أي أكبر من 2n)؟ نعم: أخرج 1.

LSP={(1,1)}, أخرج بت الإشارة:0.

هل D(1,1) دال؟ لا, أخرج 0.

LSP={(1,1)} , LIP={}, LIS={D(1,1)}

تم إخراج ثلاث بتات (نقصد بالإخراج الكتابة في الملف الذي سيحوي الصورة المضغوطة).

لا يوجد إخراج (لأن هذه مرحلة Refinement رقم n متعلقة بمرحلة الـ sorting رقم n-1).

ننقص قيمة n ب 1.

2ⁿ = 2³ = 8.

هل D(1,1) دال؟ نعم, أخرج 1.

هل (1,2) دال؟ لا, أخرج 0.

هل (2,1) دال؟ لا, أخرج 0.

هل (2,2) دال؟ لا, أخرج 0.

LIP={{1,2} ,{2,1},{2,2}}, LIS={L(1,1)}

هل L(1,1) دال؟ نعم, أخرج 1.

وهكذا نكمل إلى النهاية.

البرنامج المنجز ImgCompApp

بعد تلك المقدمة, أقدم لكم برنامج الضغط باستخدام SPHIT, ImgCompApp, هذا البرنامج يستعمل 10 فلاتر بتقنيتين مختلفتين, الـ filter bank و الـ lifting scheme كما يمكن من التحليل حسب ثلاث طرق.

لكن و بما أن البرنامج أكاديمي فإنه يتعامل مع الصور من نوع bmp 24 bits أو ppm أو pgm حيث تكون الصور هناك غير مضغوطة, كما أنه يتعامل فقط مع الصور ذات العرض المساوي لـ 2nx2n أي مثلا 128x128 أو 256x256...الخ.

تمت برمجته باستخدام Visual C++ 6.0 و باستعمال كائنات الـ MFC و أيضا تم استخدام OpenGL لعرض الصور قبل و بعد ضغطها, و هذا المخطط يوضح العلاقة بين الكائنات المكونة لهذا البرنامج:

الفئة CCodecClass هي الفئة الرئيسة و من خلالها تتم كل العمليات و هذا مثال عن كيفية ضغط الصورة lena.pgm باستعمال الفيلتر Daubechie9 وتطبيقه بشكل symetric للحصول على ملف بحيث نمثل كل بيكسل من الصورة الرئيسية بربع بت, أي أن كل أربعة بكسالات يتم تمثيلهم بواحد بت(bpp = 0.25), ثم نحفظ الصورة المضغوطة في الملف lena.spt لنعيد قرائتها و نعيد بناء الصورة الاصلية و نحفضها إلى lena_spt.pgm.

//La création d'une instance de la classe CCodecClass.
CCodecClass * CodecClass = new CCodecClass();
//Sélection de l'ondelette.
CodecClass->CodecClassSelectWavelet("CohenDaubechiesFeauveau.9-7.lft", "symetric");
CodecClass->CodecClassOpenImage("lena.pgm");
//codage SPIHT(0.25 bpp).
CodecClass->CodecClassSPIHTEncode("lena.spt", 0.25);
//décodage SPIHT.
CodecClass->CodecClassSPIHTDecode("lena.spt");
CodecClass->CodecClassSaveImage("lena_spt.pgm");

كيف يعمل البرنامج؟

أولا قم بفتح البرنامج...

بحيث:

1. القائمة الرئيسية.

2. منطقة عرض الصورة الأصلية.

3. منطقة عرض الصورة المضغوطة.

4. منطقة لعرض بعض المعلومات أثناء الضغط.

5. القسم الأول من شريط الحالة, خاص بعرض معلومات حول الصورة الأصلية.

6. حجم ملف الصورة الأصلية.

حجم ملف الصورة المضغوطة.

كيف نضغط صورة ما؟

قم بفتح الصورة من خلال file->open:

اختر الصورة و اضغط Ouvrir:

بعد ذلك نضغط على الزر compresser:

ثم ندخل اسم الملف الذي سيحوي الصورة المضغوطة و ليكن car:

بعد ذلك سنحصل على النتيجة:

وكما تلاحظ, حجم الصورة الأصلية هو 768 kb أما حجم الصورة المضغوطة فهو 8 kb.

طبعا يمكنك تغيير بعض نوع الفلتر و نوعية الصورة المضغوطة من خلال القائمة file->option.

مثلا, لدينا الصورة الأصلية peppers.ppm ذات العرض 512x512 بحجم مساو لـ 768 kb :

نقوم بضغطها باستعمال زوج الفلاتر C-D-F(9/7) و بـ bpp = 0.2 لنحصل على الصورة peppers.spt التالية و بحجم 6.4 kb أي أن الصورة الأصلية تقلص حجمها بنسبة 99,16 % !

و لفتح الصور المضغوطة استعمل file->open spt file.

وفي الأخير أقدم لكم رابط البرنامج ImgCompApp استعمل هذا الرابط:

و هذا رابط آخر لتحميل الكود سورس:

ما شاء الله

شكرا لك بصراحة موضوع أعجبني كثيرا..

شكراً جزيلاً أخي على هذه المعلومات القيمة

أخ ياسين بصراحة لم أفهم صيغة التحويل والتحويل العكسي ...

فهمت من الموضوع أن الفلترة تتم بدمج عدة بتات في بت واحد ...

وهناك نقطة أخرى للتأكد : يتم تقسيم الصورة إلى 8*8 حتى نقوم بتشفير كل جزء من ال64 جزءا على حدة أليس هذا صحيحاً ؟

سأعيد قراءة المقالة مرة أخرى .. وأنتظر إجابتك على سؤالي الأول ...

جزاك الله خيراً مقالة مرتبة ...

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

1-Transformation TCD:

ما هي الوسطاء u , v إحداثيات النقطة مثلاً

ما هي N

2-المثال الذي استخدمته ... هذه الأرقام في المصفوفة ماذا تمثل ؟ ألوان ؟

ثم لماذا كل هذا التعقيد .؟؟ ألا يكفي مثلاً أن نأخذ اللون الوسطي لX بكسل ثم نستعيض عنها ببكسل واحد له اللون الوسطي ؟؟

وشكرا جزيلا لك ...

مصطفى 36a2 كتب:

أخ ياسين بصراحة لم أفهم صيغة التحويل والتحويل العكسي ...

فهمت من الموضوع أن الفلترة تتم بدمج عدة بتات في بت واحد ...

ما هي الوسطاء u , v إحداثيات النقطة مثلاً

ما هي N

2-المثال الذي استخدمته ... هذه الأرقام في المصفوفة ماذا تمثل ؟ ألوان ؟

سأحاول أن أشرح

التحويل TDC نقوم فيه بتطبيق صيغة معينة على مصفوفة حتى نتحصل على مصفوفة جديدة, و تحويله العكسي DCTI نطبقه على المصفوفة الجديدة حتى نتحصل على المصفوفة الأصلية, طبعا بعد ضغط الصورة نحتاج أن نفك الضغط حتى نفتحها

بالنسبة لصيغة التحويل, i و j يمثلان index للمصفوفة الأصلية في المجال 0..N-1

حيث N هو عدد الأعمدة أو الصفوف

و u و v نفس لبشيء, فقط بالنسبة للمصفوفة الناتجة عن تحويل المصفوفة الأصلية

مثلا من أجل أن نحسب tcd(0,3) راح نطبق هالصيغة على المصفوفة الأصلية

تلاحظ أن حساب عنصر واحد من المصفوفة الناتجة عن التحويل يتطلب اجراء صيغة على كل عناصر المصفوفة الأصلية, و ليس فقط على العنصر X(0,3)

الفلترة في حد ذاتها ليس فيها أي ضغط للصورة, الفلترة تقوم باجراء صيغة أو تحويل على مصفوفة الصورة بحيث نحصل على أكبر عدد ممكن من الأصفار المتتالية في المصفوفة الناتجة

و عند ضغطها باستعمال اي الغوريتم ضغط مثلا باستخدام Codage arithmétique راح تكون النتيجة أفضل بكثير مقارنة بتطبيق ألغورتيم الضغط على الصورة الأصلية

لذلك الهدف من الفلترة, الحصول على مصفوفة بها أكبر عدد من الأصفار مع امكانية الرجوع للمصفوفة الأصلية

طبعا الضغط هنا هو lossy, أي لا يمكن الرجوع للمصفوفة الأصلية و لكن نرجع لمصفوفة مقاربة جدا لها, سيكون هناك تشويه للصورة و لكن غير ملاحظ بالعين المجردة

و كلما زدنا عدد الأصفار, تتشوه الصورة أكثر و تزداد نسبة الضغط أكثر

أجل المصفوفة تمثل الألوان, سيكون لدينا ثلاث مصفوفات للصورة, ثلاث ألوان لكل بيكسل

مصطفى 36a2 كتب:

وهناك نقطة أخرى للتأكد : يتم تقسيم الصورة إلى 8*8 حتى نقوم بتشفير كل جزء من ال64 جزءا على حدة أليس هذا صحيحاً ؟

نقسمها إلى 8x8 حتى نقوم تطبيق صيغة TCD على مصفوفة N=8, لان الصيغة عبارة عن جمع داخل جمع, و اذا كانت المصفوفة كبيرة راح ياخذ وقت طويل جدا حتى يحسب الصيغة

مصطفى 36a2 كتب:

ثم لماذا كل هذا التعقيد .؟؟ ألا يكفي مثلاً أن نأخذ اللون الوسطي لX بكسل ثم نستعيض عنها ببكسل واحد له اللون الوسطي ؟؟

اذا افترضنا أن هذه الطريقة ستشتغل و لن تؤثر على ألوان الصورة سلبا, أي كل RGB ستمثلهم بـ L مثلا

أي ستضغط المصفوفة بنسبة 33 إل 100, قليل جدا نحن نتحدث عن الضغط بنسبة 5 إلى 100 تقريبا

صورة المصفوفة TCD الناتجة حذفت, هذه الصورة