ضغط كسيري

مثال لمثلثان يظهر كيفية عمل الضغط الكسيري

الضغط كسيري (بالإنجليزية: Fractal compression)‏ هو طريقة ضغط بفقد بيانات للصور الرقمية، وهي تعتمد على الكسيريات. وتعد الطريقة الانسب للأنسجة والصور الطبيعية، معتمداً على تشابه اجزاء من الصورة لبعضها.[1] وتقوم الخوارزميات الكسيرية بتحويل هذه الأجزاء إلى بيانات رياضية تسمى «الأكواد الكسيرية» والتي تستخدم لإعادة إنشاء الصورة المشفرة.

نظم الدالة المتكررة

يمكن وصف تمثيل الصورة الكسيرية رياضيًا كنظام دالة متكرر (IFS).

للصور الثنائية

نبدأ بتمثيل الصورة الثنائية بأعتبار الصورة مجموعة فرعية من ${\displaystyle \mathbb {R} ^{2}}$ . ونظم الدالة المتكررة (IFS) عبارة عن مجموعة من التطبيقات الانكماشيّة ƒ ₁ . . . ƒ _N ،

${\displaystyle f_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}.}$

وفقًا لتخطيطات الدالة هذه، يصف IFS المجموعة S ثنائية الابعاد كنقطة ثابتة لمشغل Hutchinson

أي، H هو مشغل يقوم بتخطيط مجموعات لمجموعات أخرى، و S هي المجموعة الفريدة التي ترضي H (S) = S. والفكرة هي ان تنشئ نظام الدالة المتكررة بحيث أن مجموعة S هي الصورة الثنائية المدخلة. ونستطيع استعادة S من نظام الدالة المتكررة عن طريق تكرار النقطة الثابتة: لأي مجموعة أولية مضغوطة غير فارغة (A ₀₎ ، التكرار A _{k +1} = H (A _k) يتقارب مع S.

المجموعة S تتشابه ذاتياً لأن H(S) = S تلمّح أن S نسخ مرتبطة مخططة من نفسها:

${\displaystyle S=f_{1}(S)\cup f_{2}(S)\cup \cdots \cup f_{N}(S)}$

فلذلك نرى أن نظام الدالة المتكررة هو تمثيل كسيري لـ S.

التمديد إلى التدرج الرمادي

يمكن تمديد تمثيل نظام الدالة المتكررة إلى صورة ذات تدرج رمادي عن طريق اعتبار الرسم البياني للصورة كمجموعة فرعية من ${\displaystyle \mathbb {R} ^{3}}$ . وللحصول على صورة بتدرج الرمادي u (x ، y)، أعتبر المجموعة S = {(x ، y ، u (x ، y))}. وكما في الحالة الثنائية، يتم وصف S بواسطة نظام الدالة المتكررة باستخدام مجموعة من التطبيقات الانكماشيّة ƒ ₁ . . . ƒ _N ، ولكن في ${\displaystyle \mathbb {R} ^{3}}$

${\displaystyle f_{i}:\mathbb {R} ^{3}\to \mathbb {R} ^{3}.}$

التشفير

إحدى المشاكل الصعبة في البحث القائم في تمثيل الصور الكسيرية هي كيفية اختيار ƒ ₁ . . . ƒ _N بحيث أن نقطته الثابتة تعادل تقريبا الصورة المدخلة، وكيفية فعل ذلك بكفاءة.

من الطرق البسيطة للقيام بذلك هو نظام الدالة المتكررة المقسمة (PIFS) التالية:

1. قسّم نطاق الصورة إلى كتل مدى R _i بحجم s × s .
2. لكل R _i ، ابحث في الصورة لتعثر على كتلة D _i بحجم 2 s × 2 s تشبه بشكل كبير ل R _i .
3. أختر الدالات التخطيطية مثل H (D _i) = Ri لكل i .

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

التقسيم التربيعي المبدئي وخوارزمية البحث الشامل التي قدمها جاكوين توفّر نقطة بداية لأضافات وبحوث أكثر بالعديد من الاتجاهات الممكنة، وكذلك طرق مختلفة لتقسيم الصورة إلى مدى للكتل مختلفة الاحجام والاشكال; وهي تقنيات سريعة للعثور على نطاق كتله مشابه بشكل قريب بما فيه الكفاية لكل مدى للكتلة بدلاً عن البحث الشامل، كخوارزمية تقدير الحركة السريعة ؛ وطرق أخرى لتشفير التخطيط من نطاق الكتلة إلى مدى الكتلة؛ إلخ [2]

يحاول الباحثون الاخرين العثور على خوارزميات لتشفير الصور العشوائية بشكل آلي لنظام الدالة المتكررة المعاود أو نظام الدالة المتكررة العالمي، بدلاً من نظام الدالة المتكررة المقسمة; والخوارزميات لضغط الفيديو الكسيري شاملاً تعويض الحركة وأنظمة الدالة المتكررة ثلاثية الأبعاد.[3][4]

ويحتوي الضغط الكسيري للصور على الكثير من اوجه الشبه بينه وبين ضغط تكميم النواقل للصور.[5]

المزايا

باستخدام الضغط الكسيري، يصبح التشفير مكلف حسابيا للغاية بسبب البحث المستخدم لإيجاد التشابه الذاتي. بينما فك التشفير سريع للغاية. في حين أن هذا الاختلال -لحد الآن- جعله غير عملي لتطبيقات الوقت الحقيقي، فعندما نأرشف الفيديو للنشر عن طريق التخزين بالاقراص أو تحميل الملفات، عندها يصبح الضغط الكسيري أكثر تنافسيا.[6][7]

وفي نسب الضغط الشائعة، إلى حوالي 50:1، يوفر الضغط الكسيري نتائج تشابه الخوارزميات القائمة على DCT مثل JPEG.[8] في نسب الضغط العالية، الضغط الكسيري قد يوفر جودة فائقة. وبالنسبة لصور الأقمار الصناعية فالنسب الأكثر من 170:1 [9] تم تحقيقها بنتائج مقبولة. وضغط الفيديو الكسيري بنسب بين 25:1 - 244:1 تم تحقيقها بأوقات ضغط معقولة (2.4 إلى 66 ثانية / إطار).

كفاءة الضغط تزيد مع تعقيد الصورة وعمق اللون، مقارنةً بالتدرج الرمادي البسيط للصور.

استقلال الدقة والقياس الكسيري

إحدى المزايا المتأصلة في الضغط الكسيري هي أن الصور تصبح بدقة مستقلة [10] بعد تحويلها إلى كود كسيري. وهذا لأن انظمة الدالة المتكررة في الملف المضغوط يقاس بشكل غير محدود. وخاصية القياس غير المحدود في الكسيرية تعرف ب«المقياس الكسيري».

الاستفياء الكسيري

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

تاريخ

قاد مايكل بارنسلي تطوير الانضغاط الكسيري في عام 1987، وحصل على العديد من براءات الاختراع على هذه التقنية. قام بارنسلي وآلان سلون بأختراع أكثر خوارزمية ضغط كسيري عملية معروفة. نفذ طالب بارنسلي الخريج، أرنو جاكين، أول خوارزمية تلقائية في البرمجيات في عام 1992.[15][16] تعتمد جميع الطرق على التحويل الكسيري باستخدام أنظمة الدالة المتكررة. قام مايكل بارنسلي وآلان سلون بتأسيس شركة Iterated Systems Inc.[17] في عام 1987 والتي تم منحها أكثر من 20 براءة اختراع إضافية تتعلق بالضغط الكسيري.

وكانت أحد الانجازات الكبيرة لشركة Iterated Systems Inc. هي عملية التحويل الكسيري الآلية التي الغت الحاجة للتدخل البشري اثناء عملية الضغط كما كان في التجارب المبكرة لتقنية الضغط الكسيري. وفي عام 1992، تلقت شركة Iterated Systems Inc. منحة حكومية بقيمة 2.1 مليون دولار أمريكي [18] لتطوير نموذج أولي لتخزين الصور الرقمية وشريحة فك الضغط باستخدام تقنية ضغط الصور ذات التحويل الكسيري.

تم استخدام ضغط الصور الكسيري في عدد من التطبيقات التجارية: برنامج onOne ، الذي تم تطويره بترخيص من شركة Iterated Systems Inc. و Genuine Fractals 5 [19] وهو مكون إضافي لبرنامج Photoshop قادر على حفظ الملفات بتنسيق FIF مضغوط (تنسيق صورة كسيرية). ولهذا اليوم، فإن الاستخدام الأكثر نجاحًا لضغط الصور الثابتة هو بواسطة Microsoft في موسوعة الوسائط المتعددة Encarta الخاصة بها [20] أيضًا بموجب ترخيص.

قامت شركة Iterated Systems Inc. بتزويد برنامج مشفر تجريبي (Fractal Imager)، ووحدة فك تشفير مستقلة، وإضافة وحدة فك تشفير لNetscape وحزمة تطوير للاستخدام تحت Windows. وحينما تحسنت طرق ضغط الصور المستندة إلى الموجة واصبح ترخصيها أسهل من قبل بائعي البرامج التجارية، فشل اعتماد صيغة الصورة الكسيرية في التطور. كما ان إعادة توزيع «ملف DLL للضغط» الذي توفره ColorBox III SDK كان محكومًا بأنظمة ترخيص مقيدة لكل قرص أو سنويًا لموردي البرامج الاحتكارية من خلال مخطط تقديري يستلزم الترويج لمنتجات Iterated Systems لفئات معينة من المستخدمين الآخرين.[21]

خلال التسعينيات، أنفقت شركة Iterated Systems Inc. وشركاؤها الكثير من الموارد لجلب الضغط الكسيري إلى الفيديو. ومع ان نتائج الضغط كانت واعدة، فقد افتقرت معدات الحاسب في ذلك الوقت قوة المعالجة الكافية لجعل ضغط الفيديو الكسيري عملي بعد عدة من الاستخدامات الاختيارية. حيث كان يتطلب ضغط دقيقة واحد من الفيديو أكثر من 15 ساعة.

ClearVideo – يُعرف أيضًا باسم RealVideo (كسيرية) – و SoftVideo كانت منتجات مبكرة لضغط الفيديو الكسيري. ClearFusion هو إضافة بث الفيديو لمتصفحات الويب التي تم توزيعها مجانا من Iterated. في عام 1994، تم ترخيص SoftVideo لشركة Spectrum Holobyte لتستخدم في ألعاب الأقراص المضغوطة بما في ذلك Falcon Gold و Star Trek: The Next Generation A Final Unity.[22]

في عام 1996، أعلنت شركة Iterated Systems Inc.[23] تحالفًا مع شركة Mitsubishi لتسويق ClearVideo لعملائها اليابانيين. ولا يزال محرك فك الشفرات الاصلي الخاص بـ ClearVideo 1.2 مدعومًا [24] بواسطة Microsoft في Windows Media Player على الرغم من أن برنامج التشفير لم يعد مدعومًا.

كما قامت شركتان، وهما Total Multimedia Inc. و Dimension ، بإدعاء امتلاك الرخصة الحصرية لتقنية الفيديو الخاصة بـIterated ، ولكن لم يصدر أي منهما منتجا صالحا حتى الآن. ويبدو أن أساس التكنولوجيا هو براءات اختراع Dimension الأمريكية 8639053 و 8351509، والتي تم تحليلها بشكل كبير.[25] فخلاصة الموضوع هو إنه نظام نسخ كتل رباعي بسيط بلا كل من كفاءة عرض النطاق الترددي ولا جودة PSNR لبرامج الترميز التقليدية المعتمدة على DCT. وفي يناير 2016، أعلنت TMMI أنها ستتخلى تمامًا عن التكنولوجيا المعتمدة على الكسور.

وقد تم نشر العديد من البحوث التي تناقش حلول محتملة لتحسين الخوارزميات الكسيرية ومعدات التشفير خلال السنوات الماضية.[26][27][28][29][30][31][32][33][34]

تطبيقات

ولقد تم إنشاء مكتبة تسمى فياسكو من قبل أولريتش هافنر. وفي عام 2001، تمت تغطية فياسكو في مجلة لينكس.[35] ووفقا لكتيب فياسكو لعام 2000-04 ، يمكن استخدام فياسكو لضغط الفيديو.[36] تتضمن مكتبة Netpbm مكتبة فياسكو.[37][38]

قامت Femtosoft بتطوير تطبيق لضغط الصور الكسيرية في Object Pascal وJava.[39]

مراجع

1. May، Mike (1996). "Fractal Image Compression". American Scientist. ج. 84 ع. 5: 442–451. Bibcode:1996AmSci..84..442M. JSTOR:29775747. بروكويست 215266230. {{استشهاد بدورية محكمة}}: templatestyles stripmarker في |المعرف= في مكان 1 (مساعدة)
2. Saupe، Dietmar؛ Hamzaoui، Raouf (نوفمبر 1994). "A review of the fractal image compression literature". ACM SIGGRAPH Computer Graphics. ج. 28 ع. 4: 268–276. DOI:10.1145/193234.193246.
3. Lacroix، Bruno (1999). Fractal image compression (Thesis). DOI:10.22215/etd/1999-04159.
4. Fisher، Yuval (2012). Fractal Image Compression: Theory and Application. Springer Science & Business Media. ص. 300. ISBN:978-1-4612-2472-3. مؤرشف من الأصل في 2021-05-06.
5. Henry Xiao. "Fractal Compression". 2004. نسخة محفوظة 2021-03-21 على موقع واي باك مشين.
6. John R. Jensen، "Remote Sensing Textbooks"، Image Compression Alternatives and Media Storage Considerations (reference to compression/decompression time)، جامعة كارولاينا الجنوبية، مؤرشف من الأصل في 2008-03-03
7. Steve Heath (23 أغسطس 1999). Multimedia and communications technology. Focal Press. ص. 120–123. ISBN:978-0-240-51529-8. مؤرشف من الأصل في 2021-05-06. Focal Press link
8. Sayood، Khalid (2006). Introduction to Data Compression. Elsevier. ص. 560–569. ISBN:978-0-12-620862-7.
9. Wee Meng Woon؛ Anthony Tung Shuen Ho؛ Tao Yu؛ Siu Chung Tam؛ Siong Chai Tan؛ Lian Teck Yap (2000). "Achieving high data compression of self-similar satellite images using fractal". IGARSS 2000. IEEE 2000 International Geoscience and Remote Sensing Symposium. Taking the Pulse of the Planet: The Role of Remote Sensing in Managing the Environment. Proceedings (Cat. No.00CH37120). ج. 2. ص. 609–611. DOI:10.1109/IGARSS.2000.861646. ISBN:0-7803-6359-0.
10. Walking, Talking Web نسخة محفوظة 2008-01-06 على موقع واي باك مشين. Byte Magazine article on fractal compression/resolution independence
11. He، Chuan-jiang؛ Li، Gao-ping؛ Shen، Xiao-na (مايو 2007). "Interpolation decoding method with variable parameters for fractal image compression". Chaos, Solitons & Fractals. ج. 32 ع. 4: 1429–1439. Bibcode:2007CSF....32.1429H. DOI:10.1016/j.chaos.2005.11.058.
12. Navascués، M. A.؛ Sebastián، M. V. (2006). "Smooth fractal interpolation". Journal of Inequalities and Applications. ج. 2006: 1–20. DOI:10.1155/JIA/2006/78734.
13. Uemura, Satoshi; Haseyama, Miki; Kitajima, Hideo (28 Jan 2003). "EFIFを用いた自己アフィンフラクタル図形の拡大処理に関する考察" [A Note on Expansion Technique for Self-Affine Fractal Objects Using Extended Fractal Interpolation Functions]. IEICE Technical Report (باليابانية). 102 (630): 95–100. DOI:10.11485/itetr.27.9.0_95. قالب:NAID.
14. Kuroda, Hideo; Hu, Xiaotong; Fujimura, Makoto (1 Feb 2003). "フラクタル画像符号化におけるスケーリングファクタに関する考察" [Studies on Scaling Factor for Fractal Image Coding]. The Transactions of the Institute of Electronics, Information and Communication Engineers (باليابانية). 86 (2): 359–363. قالب:NAID.
15. Using Fractal Coding to Index Image Content for a Digital Library Tech report نسخة محفوظة 2016-03-03 على موقع واي باك مشين.
16. Jacquin، A.E. (1992). "Image coding based on a fractal theory of iterated contractive image transformations". IEEE Transactions on Image Processing. ج. 1 ع. 1: 18–30. Bibcode:1992ITIP....1...18J. DOI:10.1109/83.128028. PMID:18296137.
17. Iterated Systems Inc. changed its name to MediaBin Inc. Inc. in 2001 and in turn was bought out by Interwoven, Inc. in 2003) نسخة محفوظة 15 مايو 2018 على موقع واي باك مشين.
18. NIST SP950-3, "Capturing and Integrating Patient Healthcare Information to Improve Accessibility"; see page 36, "MediaBin Fractal-Based Technology to Compress Digital Image Files" نسخة محفوظة 2015-09-23 على موقع واي باك مشين.
19. Genuine Fractals Product Review نسخة محفوظة 2022-12-25 على موقع واي باك مشين.
20. "MAW 1998: Theme Essay". www.mathaware.org. مؤرشف من الأصل في 2016-08-31. اطلع عليه بتاريخ 2018-04-18.
21. Aitken، William (مايو 1994). "The big squeeze". Personal Computer World.
22. 1994 Manual specifying on page 11 SoftVideo under license to Spectrum Holobyte نسخة محفوظة 2017-02-02 على موقع واي باك مشين.
23. "Mitsubishi Corporation Inks Agreement With Iterated Systems" (Press release). Iterated Systems. 29 أكتوبر 1996. مؤرشف من الأصل في 2012-07-08.
24. "Windows Media Player for Windows XP Supported Codecs". 31 أكتوبر 2003. مؤرشف من الأصل في 2004-10-28.
25. "April - 2014 - Due Diligence Study of Fractal Video Technology". paulschlessinger.wordpress.com. مؤرشف من الأصل في 2018-04-20. اطلع عليه بتاريخ 2018-04-18.
26. Kominek، John (1 يونيو 1997). "Advances in fractal compression for multimedia applications". Multimedia Systems. ج. 5 ع. 4: 255–270. DOI:10.1007/s005300050059.
27. Harada، Masaki؛ Kimoto، Tadahiko؛ Fujii، Toshiaki؛ Tanimoto، Masayuki (2000). "Fast calculation of IFS parameters for fractal image coding". في Ngan، King N؛ Sikora، Thomas؛ Sun، Ming-Ting (المحررون). Visual Communications and Image Processing 2000. ج. 4067. ص. 457–464. Bibcode:2000SPIE.4067..457H. DOI:10.1117/12.386580. INIST:1380599.
28. Rajkumar، Wathap Sapankumar؛ Kulkarni، M.V.؛ Dhore، M.L.؛ Mali، S.N. (2006). "Fractal image compression performance synthesis through HV partitioning". 2006 International Conference on Advanced Computing and Communications. ص. 636–637. DOI:10.1109/ADCOM.2006.4289976. ISBN:978-1-4244-0715-6.
29. Simple and Fast Fractal Image Compression Circuits, Signals, and Systems - 2003 نسخة محفوظة 2018-04-19 على موقع واي باك مشين.
30. Wu، Ming-Sheng؛ Jeng، Jyh-Horng؛ Hsieh، Jer-Guang (يونيو 2007). "Schema genetic algorithm for fractal image compression". Engineering Applications of Artificial Intelligence. ج. 20 ع. 4: 531–538. DOI:10.1016/j.engappai.2006.08.005.
31. Wu، Xianwei؛ Jackson، David Jeff؛ Chen، Hui-Chuan (سبتمبر 2005). "A fast fractal image encoding method based on intelligent search of standard deviation". Computers & Electrical Engineering. ج. 31 ع. 6: 402–421. DOI:10.1016/j.compeleceng.2005.02.003.
32. Wu، Xianwei؛ Jackson، David Jeff؛ Chen، Hui-Chuan (2005). "Novel fractal image-encoding algorithm based on a full-binary-tree searchless iterated function system". Optical Engineering. ج. 44 ع. 10: 107002. Bibcode:2005OptEn..44j7002W. DOI:10.1117/1.2076828.
33. Truong، Trieu-Kien؛ Jeng، Jyh H. (2000). "Fast classification method for fractal image compression". في Schmalz، Mark S (المحرر). Mathematics and Applications of Data/Image Coding, Compression, and Encryption III. ج. 4122. ص. 190–193. Bibcode:2000SPIE.4122..190T. DOI:10.1117/12.409247. {{استشهاد بكتاب}}: |عمل= تُجوهل (مساعدة)
34. Erra، Ugo (2005). "Toward Real Time Fractal Image Compression Using Graphics Hardware". Advances in Visual Computing. Lecture Notes in Computer Science. ج. 3804. ص. 723–728. DOI:10.1007/11595755_92. ISBN:978-3-540-30750-1.
35. Hafner، Ullrich (2001). "FIASCO - An Open-Source Fractal Image and Sequence Codec". لينكس جورنال ع. 81. مؤرشف من الأصل في 2021-03-22. اطلع عليه بتاريخ 2013-02-19.
36. "Manpage of fiasco". castor.am.gdynia.pl. مؤرشف من الأصل في 2012-03-09. اطلع عليه بتاريخ 2018-04-18.
37. "Pnmtofiasco User Manual". netpbm.sourceforge.net. مؤرشف من الأصل في 2017-05-24. اطلع عليه بتاريخ 2018-04-18.
38. "Fiascotopnm User Manual". netpbm.sourceforge.net. مؤرشف من الأصل في 2017-05-26. اطلع عليه بتاريخ 2018-04-18.
39. "Archived copy". مؤرشف من الأصل في 2010-10-23. اطلع عليه بتاريخ 2010-07-10.