ضغط كسيري

ضغط كسيري
الضغط كسيري هو طريقة ضغط بفقد بيانات للصور الرقمية، وهي تعتمد على الكسيريات. وتعد الطريقة الانسب للأنسجة والصور الطبيعية، معتمداً على تشابه اجزاء من الصورة لبعضها. وتقوم الخوارزميات الكسيرية بتحويل هذه الأجزاء إلى بيانات رياضية تسمى «الأكواد الكسيرية» والتي تستخدم لإعادة إنشاء الصورة المشفرة.
نظم الدالة المتكررة
يمكن وصف تمثيل الصورة الكسيرية رياضيًا كنظام دالة متكرر (IFS).
للصور الثنائية
نبدأ بتمثيل الصورة الثنائية بأعتبار الصورة مجموعة فرعية من . ونظم الدالة المتكررة (IFS) عبارة عن مجموعة من التطبيقات الانكماشيّة ƒ 1 . . . ƒ N ،
وفقًا لتخطيطات الدالة هذه، يصف IFS المجموعة S ثنائية الابعاد كنقطة ثابتة لمشغل Hutchinson
أي، H هو مشغل يقوم بتخطيط مجموعات لمجموعات أخرى، و S هي المجموعة الفريدة التي ترضي H (S) = S. والفكرة هي ان تنشئ نظام الدالة المتكررة بحيث أن مجموعة S هي الصورة الثنائية المدخلة. ونستطيع استعادة S من نظام الدالة المتكررة عن طريق تكرار النقطة الثابتة: لأي مجموعة أولية مضغوطة غير فارغة (A 0) ، التكرار A k +1 = H (A k) يتقارب مع S.
المجموعة S تتشابه ذاتياً لأن H(S) = S تلمّح أن S نسخ مرتبطة مخططة من نفسها:
فلذلك نرى أن نظام الدالة المتكررة هو تمثيل كسيري لـ S.
التمديد إلى التدرج الرمادي
يمكن تمديد تمثيل نظام الدالة المتكررة إلى صورة ذات تدرج رمادي عن طريق اعتبار الرسم البياني للصورة كمجموعة فرعية من . وللحصول على صورة بتدرج الرمادي u (x ، y)، أعتبر المجموعة S = {(x ، y ، u (x ، y))}. وكما في الحالة الثنائية، يتم وصف S بواسطة نظام الدالة المتكررة باستخدام مجموعة من التطبيقات الانكماشيّة ƒ 1 . . . ƒ N ، ولكن في
التشفير
إحدى المشاكل الصعبة في البحث القائم في تمثيل الصور الكسيرية هي كيفية اختيار ƒ 1 . . . ƒ N بحيث أن نقطته الثابتة تعادل تقريبا الصورة المدخلة، وكيفية فعل ذلك بكفاءة.
من الطرق البسيطة للقيام بذلك هو نظام الدالة المتكررة المقسمة (PIFS) التالية:
قسّم نطاق الصورة إلى كتل مدى R i بحجم s × s .
لكل R i ، ابحث في الصورة لتعثر على كتلة D i بحجم 2 s × 2 s تشبه بشكل كبير ل R i .
أختر الدالات التخطيطية مثل H (D i) = Ri لكل i .
في الخطوة الثانية، من المهم العثور على كتلة مماثلة بحيث يمثل -بدقة- نظام الدالة المتكررة الصورة المدخلة، ولذلك عدد كاف من الكتل المرشحة لDi يجب ان تكون بالحسبان. في المقابل، القيام بعملية بحث كبيرة حول العديد من الكتل مكلفة حسابياً. إن عقبة البحث عن كتل متشابهه هو السبب في أن التشفير الكسيري لنظام الدالة المتكررة المقسمة أبطأ بكثير من DCT، والصورة القائمة على المويجات على سبيل المثال.
التقسيم التربيعي المبدئي وخوارزمية البحث الشامل التي قدمها جاكوين توفّر نقطة بداية لأضافات وبحوث أكثر بالعديد من الاتجاهات الممكنة، وكذلك طرق مختلفة لتقسيم الصورة إلى مدى للكتل مختلفة الاحجام والاشكال; وهي تقنيات سريعة للعثور على نطاق كتله مشابه بشكل قريب بما فيه الكفاية لكل مدى للكتلة بدلاً عن البحث الشامل، كخوارزمية تقدير الحركة السريعة ؛ وطرق أخرى لتشفير التخطيط من نطاق الكتلة إلى مدى الكتلة؛ إلخ
يحاول الباحثون الاخرين العثور على خوارزميات لتشفير الصور العشوائية بشكل آلي لنظام الدالة المتكررة المعاود أو نظام الدالة المتكررة العالمي، بدلاً من نظام الدالة المتكررة المقسمة; والخوارزميات لضغط الفيديو الكسيري شاملاً تعويض الحركة وأنظمة الدالة المتكررة ثلاثية الأبعاد.
ويحتوي الضغط الكسيري للصور على الكثير من اوجه الشبه بينه وبين ضغط تكميم النواقل للصور.
المزايا
باستخدام الضغط الكسيري، يصبح التشفير مكلف حسابيا للغاية بسبب البحث المستخدم لإيجاد التشابه الذاتي. بينما فك التشفير سريع للغاية. في حين أن هذا الاختلال -لحد الآن- جعله غير عملي لتطبيقات الوقت الحقيقي، فعندما نأرشف الفيديو للنشر عن طريق التخزين بالاقراص أو تحميل الملفات، عندها يصبح الضغط الكسيري أكثر تنافسيا.
وفي نسب الضغط الشائعة، إلى حوالي 50:1، يوفر الضغط الكسيري نتائج تشابه الخوارزميات القائمة على DCT مثل JPEG. في نسب الضغط العالية، الضغط الكسيري قد يوفر جودة فائقة. وبالنسبة لصور الأقمار الصناعية فالنسب الأكثر من 170:1 تم تحقيقها بنتائج مقبولة. وضغط الفيديو الكسيري بنسب بين 25:1 - 244:1 تم تحقيقها بأوقات ضغط معقولة (2.4 إلى 66 ثانية / إطار).
كفاءة الضغط تزيد مع تعقيد الصورة وعمق اللون، مقارنةً بالتدرج الرمادي البسيط للصور.
استقلال الدقة والقياس الكسيري
إحدى المزايا المتأصلة في الضغط الكسيري هي أن الصور تصبح بدقة مستقلة بعد تحويلها إلى كود كسيري. وهذا لأن انظمة الدالة المتكررة في الملف المضغوط يقاس بشكل غير محدود. وخاصية القياس غير المحدود في الكسيرية تعرف ب«المقياس الكسيري».
الاستفياء الكسيري
يمكن استخدام استقلالية دقة الصورة المشفرة كسيريا لزيادة دقة عرض الصورة. وتُعرف هذه العملية أيضًا باسم «الاستفياء الكسيري». وفي الاستفياء الكسيري، يتم تشفير الصورة إلى أكواد كسيرية عن طريق الضغط الكسيري، وبعد ذلك يتم فك الضغط بدقة أعلى. والنتيجة هي صورة مرفوعة العيّنات أستخدم فيها نظام الدالة المتكررة مثل الاستفياء. يحافظ الاستيفاء الكسيري على التفاصيل الهندسية بشكل جيد جدًا مقارنة بطرق الاستيفاء التقليدية مثل الاستيفاء الثنائي الخطي والاستيفاء التكعيبي. ولأن الاستيفاء لا يمكنه عكس إنتروبيا شانون، فإنه ينتهي به الامر بصقل الصورة عن طريق إضافة تفاصيل عشوائية بدلاً من التفاصيل ذات المعنى. وعلى سبيل المثال، فلا نستطيع تكبير صورة تحتوي على العديد من الاشخاص وكل شخص مكوّن وجهه من بيكسل أو اثنان ونأمل التعرّف عليهم.
تاريخ
قاد مايكل بارنسلي تطوير الانضغاط الكسيري في عام 1987، وحصل على العديد من براءات الاختراع على هذه التقنية. قام بارنسلي وآلان سلون بأختراع أكثر خوارزمية ضغط كسيري عملية معروفة. نفذ طالب بارنسلي الخريج، أرنو جاكين، أول خوارزمية تلقائية في البرمجيات في عام 1992. تعتمد جميع الطرق على التحويل الكسيري باستخدام أنظمة الدالة المتكررة. قام مايكل بارنسلي وآلان سلون بتأسيس شركة Iterated Systems Inc. في عام 1987 والتي تم منحها أكثر من 20 براءة اختراع إضافية تتعلق بالضغط الكسيري.
وكانت أحد الانجازات الكبيرة لشركة Iterated Systems Inc. هي عملية التحويل الكسيري الآلية التي الغت الحاجة للتدخل البشري اثناء عملية الضغط كما كان في التجارب المبكرة لتقنية الضغط الكسيري. وفي عام 1992، تلقت شركة Iterated Systems Inc. منحة حكومية بقيمة 2.1 مليون دولار أمريكي لتطوير نموذج أولي لتخزين الصور الرقمية وشريحة فك الضغط باستخدام تقنية ضغط الصور ذات التحويل الكسيري.
تم استخدام ضغط الصور الكسيري في عدد من التطبيقات التجارية: برنامج onOne ، الذي تم تطويره بترخيص من شركة Iterated Systems Inc. و Genuine Fractals 5 وهو مكون إضافي لبرنامج Photoshop قادر على حفظ الملفات بتنسيق FIF مضغوط (تنسيق صورة كسيرية). ولهذا اليوم، فإن الاستخدام الأكثر نجاحًا لضغط الصور الثابتة هو بواسطة Microsoft في موسوعة الوسائط المتعددة Encarta الخاصة بها أيضًا بموجب ترخيص.
قامت شركة Iterated Systems Inc. بتزويد برنامج مشفر تجريبي (Fractal Imager)، ووحدة فك تشفير مستقلة، وإضافة وحدة فك تشفير لNetscape وحزمة تطوير للاستخدام تحت Windows. وحينما تحسنت طرق ضغط الصور المستندة إلى الموجة واصبح ترخصيها أسهل من قبل بائعي البرامج التجارية، فشل اعتماد صيغة الصورة الكسيرية في التطور. كما ان إعادة توزيع «ملف DLL للضغط» الذي توفره ColorBox III SDK كان محكومًا بأنظمة ترخيص مقيدة لكل قرص أو سنويًا لموردي البرامج الاحتكارية من خلال مخطط تقديري يستلزم الترويج لمنتجات Iterated Systems لفئات معينة من المستخدمين الآخرين.
خلال التسعينيات، أنفقت شركة Iterated Systems Inc. وشركاؤها الكثير من الموارد لجلب الضغط الكسيري إلى الفيديو. ومع ان نتائج الضغط كانت واعدة، فقد افتقرت معدات الحاسب في ذلك الوقت قوة المعالجة الكافية لجعل ضغط الفيديو الكسيري عملي بعد عدة من الاستخدامات الاختيارية. حيث كان يتطلب ضغط دقيقة واحد من الفيديو أكثر من 15 ساعة.
ClearVideoيُعرف أيضًا باسم RealVideo (كسيرية)و SoftVideo كانت منتجات مبكرة لضغط الفيديو الكسيري. ClearFusion هو إضافة بث الفيديو لمتصفحات الويب التي تم توزيعها مجانا من Iterated. في عام 1994، تم ترخيص SoftVideo لشركة Spectrum Holobyte لتستخدم في ألعاب الأقراص المضغوطة بما في ذلك Falcon Gold و Star Trek: The Next Generation A Final Unity.
في عام 1996، أعلنت شركة Iterated Systems Inc. تحالفًا مع شركة Mitsubishi لتسويق ClearVideo لعملائها اليابانيين. ولا يزال محرك فك الشفرات الاصلي الخاص بـ ClearVideo 1.2 مدعومًا بواسطة Microsoft في Windows Media Player على الرغم من أن برنامج التشفير لم يعد مدعومًا.
كما قامت شركتان، وهما Total Multimedia Inc. و Dimension ، بإدعاء امتلاك الرخصة الحصرية لتقنية الفيديو الخاصة بـIterated ، ولكن لم يصدر أي منهما منتجا صالحا حتى الآن. ويبدو أن أساس التكنولوجيا هو براءات اختراع Dimension الأمريكية 8639053 و 8351509، والتي تم تحليلها بشكل كبير. فخلاصة الموضوع هو إنه نظام نسخ كتل رباعي بسيط بلا كل من كفاءة عرض النطاق الترددي ولا جودة PSNR لبرامج الترميز التقليدية المعتمدة على DCT. وفي يناير 2016، أعلنت TMMI أنها ستتخلى تمامًا عن التكنولوجيا المعتمدة على الكسور.
وقد تم نشر العديد من البحوث التي تناقش حلول محتملة لتحسين الخوارزميات الكسيرية ومعدات التشفير خلال السنوات الماضية.
تطبيقات
ولقد تم إنشاء مكتبة تسمى فياسكو من قبل أولريتش هافنر. وفي عام 2001، تمت تغطية فياسكو في مجلة لينكس. ووفقا لكتيب فياسكو لعام 2000-04 ، يمكن استخدام فياسكو لضغط الفيديو. تتضمن مكتبة Netpbm مكتبة فياسكو.
قامت Femtosoft بتطوير تطبيق لضغط الصور الكسيرية في Object Pascal وJava.
مراجع
ضغط بيانات
ضغط الصور
كسيريات