ساده ترین فرمت تصویر چیست؟ الگوریتم های فشرده سازی تصویر فشرده سازی تصویر: JPEG و JPEG2000

به راحتی می توان محاسبه کرد که یک تصویر تمام رنگی فشرده نشده 2000*1000 پیکسل، حدود 6 مگابایت اندازه خواهد داشت. اگر در مورد تصاویر به دست آمده از دوربین های حرفه ای یا اسکنر صحبت کنیم کیفیت بالا، سپس اندازه آنها می تواند حتی بزرگتر باشد. با وجود رشد سریع ظرفیت دستگاه های ذخیره سازی، الگوریتم های مختلف فشرده سازی تصویر هنوز بسیار مرتبط هستند.
تمام الگوریتم های موجود را می توان به دو کلاس بزرگ تقسیم کرد:

• الگوریتم های فشرده سازی بدون تلفات؛
• الگوریتم های فشرده سازی با اتلاف

الگوریتم های فشرده سازی بدون تلفات

الگوریتم RLE

الگوریتم های دیکشنری

این جدول هم در سمت کسی است که اطلاعات را فشرده می کند و هم طرف کسی که فشرده می کند. اکنون به روند فشرده سازی نگاه خواهیم کرد.

جدول روند پر کردن فرهنگ لغت را نشان می دهد. به راحتی می توان محاسبه کرد که کد فشرده حاصل 105 بیت طول می کشد و متن اصلی (با فرض اینکه ما 4 بیت برای رمزگذاری یک کاراکتر صرف می کنیم) 116 بیت طول می کشد.
در واقع، فرآیند رمزگشایی به رمزگشایی مستقیم کدها کاهش می یابد، در حالی که مهم است که جدول به همان روشی که در هنگام رمزگذاری مقداردهی اولیه شود. حالا الگوریتم رمزگشایی را در نظر بگیرید.


رشته اضافه شده به فرهنگ لغت در مرحله i ام را می توان به طور کامل فقط در i+1 تعیین کرد. بدیهی است که خط i باید به اولین کاراکتر خط i+1 ختم شود. که ما تازه فهمیدیم که چگونه یک دیکشنری را بازیابی کنیم. زمانی که دنباله‌ای از شکل cScSc کدگذاری می‌شود، جایی که c یک کاراکتر واحد و S یک رشته است، و کلمه cS قبلاً در فرهنگ لغت وجود دارد، جالب توجه است. در نگاه اول ممکن است به نظر برسد که رمزگشا قادر به حل این وضعیت نخواهد بود، اما در واقع همه رشته‌ها از این نوع همیشه باید با همان کاراکتری که با آن شروع می‌شوند به پایان برسند.

الگوریتم های کدگذاری آنتروپی

الگوریتم هافمن

1. کاراکترهای الفبای ورودی فهرستی از گره های آزاد را تشکیل می دهند. هر برگ وزنی برابر با دفعات وقوع نماد دارد
2. دو گره درخت آزاد با کوچکترین وزن انتخاب شده است
3. والد آنها با وزنی برابر با وزن کل آنها ایجاد می شود
4. والد به لیست گره های رایگان اضافه می شود و دو فرزند آن از این لیست حذف می شوند.
5. یک قوس خروجی از والد به بیت 1 و دیگری به بیت 0 اختصاص داده شده است.
6. مراحل شروع از مرحله دوم تکرار می شود تا زمانی که فقط یک گره آزاد در لیست گره های آزاد باقی بماند. ریشه درخت در نظر گرفته خواهد شد.

کدگذاری حسابی

DCT تصویر را به دامنه های فرکانس های خاص تجزیه می کند. بنابراین، هنگام تبدیل، ماتریسی به دست می آوریم که در آن بسیاری از ضرایب یا نزدیک یا برابر با صفر هستند. علاوه بر این، به دلیل ناقص بودن دید انسان، می توان ضرایب را به طور تقریبی بدون کاهش قابل توجهی در کیفیت تصویر، تقریب زد.

برای این منظور از کمی سازی ضرایب استفاده می شود. در ساده ترین حالت، این یک شیفت بیتی حسابی به سمت راست است. این تبدیل برخی از اطلاعات را از دست می دهد، اما نسبت های فشرده سازی بزرگ را می توان به دست آورد.

الگوریتم چگونه کار می کند

بنابراین، بیایید الگوریتم را با جزئیات بیشتری در نظر بگیریم. فرض کنید یک تصویر 24 بیتی را فشرده می کنیم.

مرحله 1.

تصویر را از فضای رنگی RGB، با اجزای مسئول اجزای قرمز (قرمز)، سبز (سبز) و آبی (آبی) رنگ نقطه، به فضای رنگی YCrCb (گاهی اوقات YUV نامیده می‌شود) ترجمه می‌کنیم.

در آن، Y جزء روشنایی است و Cr، Cb اجزای مسئول رنگ (قرمز رنگی و آبی رنگی) هستند. با توجه به اینکه چشم انسان نسبت به روشنایی حساسیت کمتری به رنگ دارد، می توان آرایه هایی را برای اجزای Cr و Cb با تلفات زیاد و بر این اساس نسبت فشرده سازی زیاد بایگانی کرد. تحول مشابهی برای مدت طولانی در تلویزیون استفاده شده است. باند فرکانسی باریک تری به سیگنال های مسئول رنگ اختصاص داده می شود.

به صورت ساده، ترجمه از فضای رنگی RGB به فضای رنگی YCrCb را می توان با استفاده از ماتریس انتقال نشان داد:

تبدیل معکوس با ضرب بردار YUV در ماتریس معکوس انجام می شود.

گام 2

ما تصویر اصلی را به ماتریس های 8x8 تقسیم می کنیم. از هر کدام سه ماتریس کار DCT - 8 بیت به طور جداگانه برای هر جزء تشکیل می دهیم. در نسبت تراکم بالا، این مرحله می تواند کمی دشوارتر باشد. تصویر با مؤلفه Y تقسیم می شود - مانند مورد اول، و برای مؤلفه های Cr و Cb، ماتریس ها از طریق خط و از طریق ستون تایپ می شوند. آن ها از ماتریس اصلی 16x16، تنها یک ماتریس DCT فعال به دست می آید. در این حالت، همانطور که به راحتی قابل مشاهده است، 3/4 اطلاعات مفید در مورد اجزای رنگی تصویر را از دست می دهیم و بلافاصله فشرده سازی دو برابری دریافت می کنیم. ما می توانیم این کار را با کار در فضای YCrCb انجام دهیم. همانطور که تمرین نشان داده است، این تاثیر زیادی روی تصویر RGB ایجاد شده ندارد.

مرحله 3

ما DCT را برای هر ماتریس کاری اعمال می کنیم. در این مورد، ماتریسی به دست می آوریم که در آن ضرایب در سمت چپ گوشه بالاییبا مولفه فرکانس پایین تصویر و در سمت راست پایین - با فرکانس بالا مطابقت دارد.

در شکل ساده شده، این تبدیل را می توان به صورت زیر نشان داد:

مرحله 4

ما کوانتیزاسیون را انجام می دهیم. در اصل، این به سادگی تقسیم ماتریس کار بر عنصر ماتریس کوانتیزاسیون به عنصر است. برای هر جزء (Y، U و V)، در حالت کلی، ماتریس کوانتیزاسیون q خود (از این پس MC) مشخص شده است. در این مرحله نسبت تراکم کنترل می شود و بیشترین تلفات رخ می دهد. واضح است که با تنظیم MC با ضرایب بزرگ، به صفرهای بیشتر و در نتیجه نسبت تراکم بیشتر خواهیم رسید.

اثرات خاص الگوریتم نیز با کوانتیزاسیون همراه است. در مقادیر بالای ضریب گاما، تلفات در فرکانس‌های پایین می‌تواند آنقدر زیاد باشد که تصویر به مربع‌های 8x8 تقسیم شود. تلفات در فرکانس های بالا می تواند خود را در به اصطلاح "اثر گیبس" نشان دهد، زمانی که نوعی "نیمبوس" در اطراف خطوط با یک انتقال رنگ تیز شکل می گیرد.

مرحله 5.

ماتریس 8x8 را با استفاده از اسکن "زیگزاگ" به یک بردار 64 عنصری ترجمه می کنیم. عناصر را با شاخص های (0.0)، (0.1)، (1.0)، (2.0) بگیرید...

بنابراین، در ابتدای بردار، ضرایب ماتریس مربوط به آن را دریافت می کنیم فرکانس های پایین، و در پایان - بالا.

مرحله 6

ما بردار را با استفاده از الگوریتم کدگذاری گروهی در هم می‌کشیم. در این مورد، جفت هایی از نوع (پرش، عدد) دریافت می کنیم، که در آن "پرش" شمارنده صفرهای نادیده گرفته شده است، و "عدد" مقداری است که باید در سلول بعدی قرار گیرد. بنابراین، بردار 42 3 0 0 0 -2 0 0 0 0 1 ... به صورت جفت (0.42) (0.3) (3,-2) (4.1) ... تا می شود.

مرحله 7

جفت های به دست آمده را با کد گذاری هافمن با جدول ثابت تا می کنیم.

فرآیند بازسازی تصویر در این الگوریتم کاملاً متقارن است. این روش به شما امکان می دهد برخی از تصاویر را 10-15 بار بدون تلفات جدی فشرده کنید.

عملیات خط لوله مورد استفاده در الگوریتم JPEG.

جنبه های مثبت مهم الگوریتم عبارتند از:

1. نسبت تراکم را تنظیم می کند.
2. مرخصی روزانه یک تصویر رنگی می تواند 24 بیت در هر نقطه داشته باشد.

1. با افزایش نسبت فشرده سازی، تصویر به مربع های جداگانه (8x8) تقسیم می شود. این به دلیل این واقعیت است که تلفات زیادی در فرکانس های پایین در طول کوانتیزه شدن اتفاق می افتد و بازیابی داده های اصلی غیرممکن می شود.
2. اثر گیبس ظاهر می شود - هاله ها در امتداد مرزهای انتقال رنگ تیز.

نیاز اخیر اسباب‌بازی‌هایی مانند دوربین‌های دیجیتال را امکان‌پذیر کرد - دستگاه‌هایی به اندازه یک دوربین فیلمبرداری کوچک که عکس‌های 24 بیتی را روی یک کارت فلش 10-20 مگابایتی با رابط PCMCIA می‌گیرند. سپس این کارت در اسلات لپ تاپ شما قرار می گیرد و برنامه مربوطه به شما امکان خواندن تصاویر را می دهد. آیا این درست نیست که اگر الگوریتم نامتقارن بود، منتظر ماندن طولانی مدت تا زمانی که دستگاه "شارژ" شود - تصویر را فشرده کند، ناخوشایند است.

یکی دیگر از ویژگی های نه چندان خوشایند JPEG این است که اغلب افقی و راه راه های عمودیروی نمایشگر کاملاً نامرئی هستند و فقط زمانی می توانند ظاهر شوند که به شکل الگوی موآر چاپ شوند. زمانی اتفاق می‌افتد که یک الگوی چاپ اریب روی نوارهای افقی و عمودی تصویر اعمال شود. به دلیل این شگفتی‌ها، JPEG برای استفاده فعال در چاپ، تنظیم ضرایب بالا توصیه نمی‌شود. با این حال، هنگام آرشیو تصاویر در نظر گرفته شده برای مشاهده انسان، در حال حاضر ضروری است.

استفاده گسترده از JPEG برای مدت طولانی، شاید تنها به دلیل این واقعیت که با تصاویر 24 بیتی کار می کند، متوقف شد. بنابراین برای مشاهده تصویر با کیفیت قابل قبول بر روی مانیتور معمولیدر یک پالت 256 رنگ، به استفاده از الگوریتم های مناسب و در نتیجه زمان معینی نیاز داشت. در برنامه‌هایی که کاربر حساس را هدف قرار می‌دهند، مانند بازی‌ها، چنین تاخیرهایی غیرقابل قبول است. علاوه بر این، اگر تصاویری که دارید، مثلاً 8 بیتی هستند فرمت GIFبه JPEG 24 بیتی تبدیل می شود و سپس برای مشاهده به GIF برمی گردد، سپس با هر دو تبدیل دو بار از دست دادن کیفیت رخ می دهد. با این حال، افزایش اندازه آرشیو اغلب آنقدر زیاد است (3-20 برابر!)، و افت کیفیت آنقدر کم است که ذخیره تصاویر در JPEG بسیار کارآمد است.

در مورد اصلاحات این الگوریتم باید چند کلمه گفت. اگرچه JPEG یک استاندارد ISO است، فرمت فایل آن ثابت نشده است. با استفاده از این، سازندگان فرمت های ناسازگار خود را ایجاد می کنند و بنابراین می توانند الگوریتم را تغییر دهند. بنابراین، جداول داخلی الگوریتم توصیه شده توسط ISO با آنها جایگزین می شود. علاوه بر این، هنگام تنظیم درجه تلفات، سردرگمی جزئی وجود دارد. به عنوان مثال، هنگام آزمایش، معلوم می شود که کیفیت "عالی"، "100٪" و "10 امتیاز" تصاویر به طور قابل توجهی متفاوت است. در عین حال، به هر حال، کیفیت "100٪" به معنای فشرده سازی بدون تلفات نیست. همچنین انواع JPEG برای برنامه های خاص وجود دارد.

چگونه استاندارد ISO JPEG شروع به استفاده بیشتر و گسترده تر در تبادل تصاویر در شبکه های کامپیوتری می کند. الگوریتم JPEG در فرمت‌های Quick Time، PostScript Level 2، Tiff 6.0 پشتیبانی می‌شود و در حال حاضر جایگاه برجسته‌ای را در سیستم‌های چند رسانه‌ای اشغال می‌کند.

ویژگی های الگوریتم JPEG:

کلاس تصویر:تصاویر تمام رنگی 24 بیتی یا خاکستری بدون تغییر رنگ واضح (عکس).

تقارن: 1

مشخصات:در برخی موارد، الگوریتم یک "هاله" در اطراف لبه های افقی و عمودی تیز در تصویر ایجاد می کند (اثر گیبس). علاوه بر این، با درجه فشرده سازی بالا، تصویر به بلوک های 8x8 پیکسل تقسیم می شود.

ایده روش

بایگانی فراکتال مبتنی بر این واقعیت است که ما تصویر را به شکل فشرده تر نشان می دهیم - با استفاده از ضرایب سیستم توابع تکرار شده (سیستم تابع تکرار شده - که از این پس به عنوان IFS نامیده می شود). قبل از در نظر گرفتن خود فرآیند بایگانی، بیایید ببینیم IFS چگونه یک تصویر را می سازد، یعنی. فرآیند رفع فشار

به بیان دقیق، IFS مجموعه ای از تبدیل های سه بعدی است که در مورد ما، یک تصویر را به تصویر دیگر تبدیل می کند. نقاط در فضای سه بعدی (x_coordinate، y_coordinate، روشنایی) در معرض تبدیل قرار می گیرند.

این فرآیند به وضوح توسط بارنزلی در کتاب "فشرده سازی تصویر فراکتال" نشان داده شد. در آنجا مفهوم فتوکپی معرفی شد که شامل صفحه‌ای است که تصویر اصلی روی آن نمایش داده می‌شود و سیستمی از لنزهایی که تصویر را بر روی صفحه دیگری پخش می‌کنند.

• لنزها می توانند بخشی از تصویر را پخش کنند فرم رایگانبه هر مکان دیگری در تصویر جدید.
• مناطق، که در آنتصاویر پیش بینی می شود متقاطع نشوند.
• لنز می تواند تغییر روشنایی و کاهش کنتراست.
• لنز می تواند ورق بزنید و بچرخانیدقطعه تصویر شما
• لنز باید مقیاس کردن(کاهش) قطعه تصویر خود را.

با قرار دادن لنزها و تغییر مشخصات آنها می توانیم تصویر حاصل را کنترل کنیم. یک تکرار از کار ماشین شامل این واقعیت است که یک تصویر جدید از تصویر اصلی با کمک طرح ریزی ساخته می شود و پس از آن تصویر جدید به عنوان تصویر اولیه در نظر گرفته می شود. ادعا می شود که در فرآیند تکرارها تصویری دریافت خواهیم کرد که تغییر نخواهد کرد. این تنها به مکان و ویژگی های لنزها بستگی دارد و به تصویر اصلی بستگی ندارد. این تصویر نام دارد نقطه ثابت" یا جذب کنندهاین IFS تئوری مربوطه تضمین می کند که دقیقاً یک نقطه ثابت برای هر IFS وجود دارد.

از آنجایی که نگاشت لنز انقباضی است، هر عدسی به صراحت تعریف می کند خود مشابهمناطق در تصویر ما به لطف خود شباهت، ما یک ساختار تصویر پیچیده در هر بزرگنمایی دریافت می کنیم. بنابراین، به طور شهودی واضح است که سیستم توابع تکراری تعریف می کند فراکتال(غیر دقیق - شیء ریاضی خود مشابه).

معروف ترین آنها دو تصویر به دست آمده با کمک IFS است: "مثلث سیرپینسکی" و "سرس بارنسلی". "مثلث سیرپینسکی" با سه، و "سرس بارنسلی" با چهار تبدیل آفین (یا به تعبیر ما "عدسی") داده می شود. هر تبدیل در بایت های خوانده شده به معنای واقعی کلمه کدگذاری می شود، در حالی که تصویر ساخته شده با کمک آنها می تواند چندین مگابایت طول بکشد.

تمرین: 4 ناحیه را در تصویر مشخص کنید که با هم ترکیب شوند و کل تصویر را بپوشانند و هر کدام شبیه به کل تصویر باشد (ساقه سرخس را فراموش نکنید).

=>
در بدترین حالت، اگر یک الگوریتم بهینه‌سازی اعمال نشود، شمارش و مقایسه تمام قطعات تصویر ممکن در اندازه‌های مختلف ضروری خواهد بود. حتی برای تصاویر کوچک، با در نظر گرفتن گسستگی، تعداد نجومی گزینه هایی برای مرتب سازی دریافت خواهیم کرد. علاوه بر این، حتی باریک شدن شدید طبقات تبدیل، به عنوان مثال، تنها با مقیاس بندی تعداد معینی بار، سود قابل توجهی در زمان ایجاد نمی کند. علاوه بر این، کیفیت تصویر از بین می رود. اکثریت قریب به اتفاق تحقیقات در زمینه فشرده سازی فراکتال در حال حاضر با هدف کاهش زمان آرشیو مورد نیاز برای به دست آوردن یک تصویر با کیفیت بالا است.

تعریف.

جایی که الف، ب، ج، د، ه، فاعداد واقعی و فراخوانی می شود تبدیل افین دو بعدی.

تعریف. دگرگونی، قابل نمایش در شکل

که در آن a، b، c، d، e، f، p، q، r، s، t، u اعداد حقیقی هستند و به آن تبدیل سه بعدی می گویند.

تعریف. اجازه دهید یک تبدیل در فضای X باشد. نقطه ای مانند نامیده می شود نقطه ثابت(جذب) دگرگونی.

تعریف. تبدیل در یک فضای متریک (X, d) در صورت وجود یک عدد انقباضی گفته می شود s:، طوری که

اظهار نظر:به طور رسمی، ما می‌توانیم از هر نقشه انقباضی برای فشرده‌سازی فراکتال استفاده کنیم، اما در واقعیت فقط از تبدیل‌های آفین سه بعدی با محدودیت‌های نسبتاً قوی در ضرایب استفاده می‌شود.

قضیه. (درباره تبدیل فشرده سازی)

اجازه دهید در یک فضای متریک کامل (X، د). سپس دقیقاً یک نقطه ثابت از این تبدیل و برای هر نقطه دنباله وجود دارد همگرا می شود به .

فرمول کلی تر این قضیه همگرایی را تضمین می کند.

تعریف. تصویریک تابع S است که بر روی مربع واحد تعریف شده و مقادیر از 0 تا 1 یا را می گیرد

اجازه دهید تبدیل سه بعدی وابسته به صورت نوشته شود

و بر روی یک زیر مجموعه فشرده از مربع دکارتی x تعریف شده است. سپس بخشی از سطح را ترجمه می کند اسبه منطقه واقع با شیفت (e,f)و چرخش داده شده توسط ماتریس

با این حال، اگر مقدار را تفسیر کنیم اسهمانطور که روشنایی نقاط مربوطه کاهش می یابد پبار (تبدیل باید انقباضی باشد) و به یک تغییر تغییر خواهد کرد q.

تعریف. جمعیت محدود دبلیوانقباض تبدیل های سه بعدی وابسته تعریف شده در حوزه هایی به گونه ای که و ، نامیده میشود سیستم توابع تکراری ( IFS).

یک سیستم از توابع تکرار شده به طور منحصر به فرد با یک نقطه ثابت - یک تصویر مرتبط است. بنابراین، فرآیند فشرده سازی شامل یافتن ضرایب سیستم است و فرآیند رفع فشرده سازی شامل تکرار سیستم تا زمانی است که تصویر حاصل تثبیت شود. نقطه ثابت IFS). در عمل، 7-16 تکرار کافی است. مناطق به عنوان نامیده خواهد شد رتبه بندی، و مناطق دامنه.

ساخت الگوریتم

همانطور که قبلاً از مطالب بالا مشخص شد، وظیفه اصلی در فشرده سازی توسط الگوریتم فراکتال، یافتن تبدیل های وابسته مربوطه است. در کلی‌ترین حالت، می‌توانیم مناطق تصویر را با هر اندازه و شکلی ترجمه کنیم، با این حال، در این مورد، تعداد نجومی گزینه‌هایی برای دسته‌بندی قطعات مختلف دریافت می‌کنیم که در حال حاضر حتی در یک ابر رایانه قابل پردازش نیستند.

که در نسخه آموزشی الگوریتم ، در زیر بیان شده است، محدودیت های زیر در منطقه ایجاد شده است:

1. همه مناطق مربع هایی با اضلاع موازی با اضلاع تصویر هستند.این محدودیت کاملاً شدید است. در واقع، ما قصد داریم تمام انواع اشکال هندسی را فقط با مربع تقریب بزنیم.
2. هنگام تبدیل ناحیه دامنه به دامنه رتبه، اندازه آن کاهش می یابد دقیقا دوبار. این کار هم کمپرسور و هم کمپرسور را بسیار ساده می کند. وظیفه مقیاس بندی مناطق کوچک غیر ضروری است.
3. همه بلوک های دامنه مربع هستند و دارای اندازه ثابت. تصویر توسط یک شبکه یکنواخت به مجموعه ای از بلوک های دامنه تقسیم می شود.
4. مناطق دامنه گرفته شده است "از طریق یک نقطه" در هر دو X و Y، که بلافاصله جستجو را ضریب 4 کاهش می دهد.
5. هنگام تبدیل دامنه به رتبه یک، مکعب را می توان چرخاند فقط در 0 0، 90 0، 180 0 یا 270 0. همچنین مجاز است انعکاس آینه. تعداد کل تبدیل های ممکن (شمارش خالی) 8 است.
6. پوسته پوسته شدن (فشرده سازی) به صورت عمودی (روشنایی) انجام می شود تعداد دفعات ثابت- در 0.75.

1. الگوریتمی بسازید که به تعداد نسبتاً کمی عملیات حتی روی تصاویر به اندازه کافی بزرگ نیاز دارد.
2. نمایش داده هایی که باید در یک فایل نوشته شوند بسیار فشرده است. ما برای هر تبدیل افین در IFS نیاز داریم:

• دو عدد برای تنظیم افست بلوک دامنه. اگر تصاویر ورودی را به 512x512 محدود کنیم، 8 بیت برای هر عدد کافی است.
• سه بیت برای تعیین تبدیل تقارن هنگام تبدیل یک بلوک دامنه به یک بلوک رتبه.
• 7-9 بیت به منظور تنظیم تغییر در روشنایی در طول ترجمه.

به عنوان مثال، برای یک فایل در مقیاس خاکستری با 256 رنگ 512x512 پیکسل، با اندازه بلوک 8 پیکسل، تبدیل های افین 4096 (512/8x512/8) خواهد بود. هر کدام به 3.5 بایت نیاز دارند. بنابراین، اگر فایل اصلی 262144 (512x512) بایت (به استثنای هدر) را اشغال کرده باشد، فایل با ضرایب 14336 بایت خواهد بود. ضریب بایگانی - 18 برابر. در عین حال، ما در نظر نمی گیریم که یک فایل با ضرایب نیز می تواند افزونگی داشته باشد و با استفاده از روش بایگانی بدون ضرر، مانند LZW، بایگانی شود.

جنبه های منفی محدودیت های پیشنهادی:

1. از آنجایی که همه مناطق مربع هستند، استفاده از شباهت اجسامی که از نظر شکل از مربع دور هستند (که در تصاویر واقعی کاملاً رایج است) غیرممکن است.
2. به همین ترتیب، ما نمی توانیم از شباهت اشیاء در تصویر استفاده کنیم که ضریب شباهت بین آنها با 2 بسیار متفاوت است.
3. الگوریتم قادر به استفاده از شباهت اشیاء در تصویر که زاویه بین آنها مضرب 90 0 نیست، نخواهد بود.

خود الگوریتم بسته بندی به شمارش تمام بلوک های دامنه و انتخاب برای هر بلوک رتبه مربوطه کاهش می یابد. در زیر نموداری از این الگوریتم آمده است.

برای (همه بلوک های محدوده) (
min_distance = حداکثر فاصله;
آر ij= image->CopyBlock(i,j);
برای (همه بلوک های دامنه) ( // با چرخش و نگ.
فعلی = مختصات فعلی تحولات؛
D=image->CopyBlock(current);
جریان_فاصله = R ij L2distance(D);
if(current_dance< min_distance) {
// اگر بهترین شانس بدتر باشد:
حداقل_فاصله = فاصله_ فعلی;
بهترین = فعلی;
}
) //محدوده بعدی
Save_Coefficients_to_file(best);
) //دامنه بعدی

همانطور که از الگوریتم بالا مشاهده می شود، برای هر بلوک رتبه ای آن را با تمام بلوک های دامنه ممکن (از جمله آنهایی که دچار تبدیل تقارن شده اند) بررسی می کنیم، واریتی را با کوچکترین اندازه L پیدا می کنیم. 2 (کمترین انحراف معیار) و ضرایب این تبدیل را در یک فایل ذخیره کنید. ضرایب عبارتند از (1) مختصات بلوک یافت شده، (2) عددی از 0 تا 7 که تبدیل تقارن (چرخش، انعکاس بلوک) را مشخص می کند، و (3) تغییر در روشنایی برای این جفت بلوک. تغییر درخشندگی به صورت زیر محاسبه می شود:

,

جایی که r ij- مقادیر پیکسل بلوک رتبه بندی ( آر)، آ د ij- مقادیر پیکسل بلوک دامنه ( D). در این مورد، اندازه گیری به صورت زیر در نظر گرفته می شود:

.

ما محاسبه نمی کنیم ریشه دوماز L 2 اندازه گیری کنید و آن را تقسیم نکنید nاز آنجایی که داده‌های تبدیل یکنواخت هستند و ما را از یافتن اکسترموم باز نمی‌دارند، با این حال، می‌توانیم دو عملیات کمتر برای هر بلوک انجام دهیم.

بیایید تعداد عملیاتی را که برای فشرده سازی یک تصویر نیاز داریم در مقیاس خاکستری 256 رنگ 512x512 پیکسل با اندازه بلوک 8 پیکسل محاسبه کنیم:

بنابراین، ما موفق شدیم تعداد عملیات الگوریتم فشرده سازی را به مقادیر کاملاً قابل محاسبه (البته در چند ساعت) کاهش دهیم.

نمودار الگوریتم رفع فشرده سازی تصویر

رفع فشرده سازی الگوریتم فشرده سازی فراکتال بسیار ساده است. لازم است چندین تکرار از تبدیل های سه بعدی سه بعدی انجام شود که ضرایب آن در مرحله فشرده سازی به دست آمده است.

مطلقاً هر تصویر (مثلاً کاملاً سیاه) را می توان به عنوان تصویر اولیه در نظر گرفت، زیرا دستگاه ریاضی مربوطه همگرایی توالی تصاویر به دست آمده در طول تکرارهای IFS را به یک تصویر ثابت (نزدیک به تصویر اصلی) تضمین می کند. معمولا 16 تکرار برای این کار کافی است.

ضرایب تمام بلوک ها را از فایل بخوانید.
یک تصویر سیاه با اندازه دلخواه ایجاد کنید.
تا (تصویر ثابت نمی ماند)(
برای (هر محدوده (R))(
D=image->CopyBlock(D_coord_for_R);
برای(هر پیکسل( من، ج) در بلوک (
آر ij = 0.75 D ij + o R;
) //پیکسل بعدی
) //بلوک بعدی
)//تا پایان

از آنجایی که ما ضرایب بلوک ها را ثبت کردیم آر ij(که همانطور که تصریح کردیم در مورد خاص ما مربع هایی هم اندازه هستند) به طور متوالی، معلوم می شود که تصویر را با استفاده از یک تبدیل افین به طور متوالی توسط مربع های شبکه پارتیشن پر می کنیم.

همانطور که می توان محاسبه کرد، تعداد عملیات در هر پیکسل تصویر خاکستری در طول بازیابی به طور غیرمعمول کم است (N عملیات "+"، 1 عملیات "*"، که در آن N تعداد تکرار است، یعنی 7-16). به همین دلیل، فشرده سازی تصویر برای الگوریتم فراکتال سریعتر از رفع فشرده سازی است، به عنوان مثال، برای الگوریتم JPEG، که در آن 64 "+" و 64 "؟ ” (به استثنای مراحل RLE و کدگذاری هافمن!). در همان زمان، برای الگوریتم فراکتال، ضرب با یک عدد گویا، یک برای هر بلوک اتفاق می‌افتد. این بدان معناست که ما می‌توانیم ابتدا از محاسبات منطقی اعداد صحیح استفاده کنیم که به طور قابل ملاحظه‌ای سریع‌تر از محاسبات ممیز شناور است. ثانیاً، ضرب یک بردار در عدد یک عملیات ساده‌تر و سریع‌تر است که اغلب در معماری پردازنده (پردازنده‌های SGI، Intel MMX...) تعبیه شده است، تا حاصل ضرب اسکالر دو بردار، که در مورد JPEG ضروری است. برای یک تصویر تمام رنگی، وضعیت از نظر کیفی تغییر نمی کند، زیرا هر دو الگوریتم از تبدیل به فضای رنگی دیگر استفاده می کنند.

برآورد تلفات و راه های تنظیم آنها

در خلاصه ای از نسخه ساده شده الگوریتم، بسیاری از سوالات مهم. به عنوان مثال، اگر الگوریتم نتواند تصویر مشابهی را برای هر قطعه از تصویر پیدا کند، چه؟ راه حل به اندازه کافی واضح این است که این قطعه را به قطعات کوچکتر تقسیم کنید و سعی کنید آنها را جستجو کنید. در عین حال، واضح است که این روش نمی تواند به طور نامحدود تکرار شود، در غیر این صورت تعداد تبدیل های لازم به قدری زیاد می شود که الگوریتم دیگر یک الگوریتم فشرده سازی نخواهد بود. بنابراین، ما اجازه از دست دادن در بخشی از تصویر را می دهیم.

برای الگوریتم فشرده سازی فراکتال و همچنین برای سایر الگوریتم های فشرده سازی با اتلاف، مکانیسم هایی که توسط آن ها امکان کنترل درجه فشرده سازی و درجه تلفات وجود خواهد داشت بسیار مهم است. تا به امروز، مجموعه ای به اندازه کافی بزرگ از این روش ها توسعه یافته است. ابتدا، می توان با اطمینان از اینکه نسبت تراکم کمتر از یک مقدار ثابت نیست، تعداد تبدیل های آفین را محدود کرد. ثانیاً، می توان در شرایطی که تفاوت بین قطعه در حال پردازش و بهترین تقریب آن بالاتر از یک مقدار آستانه مشخص است، این قطعه الزاماً تقسیم شود (لزوماً چندین "عدسی" برای آن ایجاد می شود). ثالثاً، ممکن است تکه تکه شدن قطعات کوچکتر از مثلاً چهار نقطه ممنوع شود. با تغییر مقادیر آستانه و اولویت این شرایط، کنترل بسیار انعطاف پذیری بر نسبت فشرده سازی تصویر در محدوده از تطبیق بیت تا هر نسبت فشرده سازی خواهیم داشت. توجه داشته باشید که این انعطاف پذیری بسیار بالاتر از نزدیکترین "رقیب" - الگوریتم JPEG خواهد بود.

ویژگی های الگوریتم فراکتال :

نسبت فشرده سازی: 2-2000 (تعریف شده توسط کاربر)

کلاس تصویر:تصاویر تمام رنگی 24 بیتی یا خاکستری بدون تغییر رنگ واضح (عکس). مطلوب است که نواحی با اهمیت بیشتر (برای ادراک) متضاد تر و واضح تر و مناطق با اهمیت کمتر - کنتراست کم و تار باشند.

تقارن: 100-100000

مشخصات:می‌تواند آزادانه تصویر را در هنگام باز کردن زیپ مقیاس‌بندی کند و آن را 2 تا 4 برابر افزایش دهد، بدون اینکه «افکت راه پله» ظاهر شود. با افزایش سطح فشرده‌سازی، یک افکت بلوکی در مرز بلوک‌های تصویر ظاهر می‌شود.

نام انگلیسی فشرده سازی بازگشتی موجک است. به روسی به عنوان فشرده سازی موج و به عنوان فشرده سازی با استفاده از انفجار ترجمه شده است. این نوع آرشیو از دیرباز شناخته شده است و مستقیماً از ایده استفاده از انسجام مناطق ناشی می شود. این الگوریتم بر روی تصاویر رنگی و سیاه و سفید متمرکز شده است انتقال های صاف. ایده آل برای عکس هایی مانند اشعه ایکس. نسبت تراکم تنظیم شده است و بین 5-100 متغیر است. هنگامی که سعی می کنید ضریب بالاتری را روی مرزهای تیز تنظیم کنید، به ویژه آنهایی که به صورت مورب عبور می کنند، یک "اثر پلکان" ظاهر می شود - مراحل با روشنایی متفاوت در اندازه چندین پیکسل.

ایده الگوریتم این است که ما تفاوت را در فایل ذخیره می کنیم - تعداد بین مقادیر متوسط ​​بلوک های همسایه در تصویر، که معمولاً مقادیر نزدیک به 0 را می گیرد.

پس دو عدد آ 2منو آ 2من +1 همیشه می تواند به عنوان نشان داده شود ب 1 i=(آ 2من +آ 2من +1 )/2 و ب 2 من=(آ 2من -آ 2من +1 )/2. به طور مشابه دنباله آ منرا می توان به صورت جفت به یک دنباله ترجمه کرد ب 1.2i.

بیایید به یک مثال خاص نگاه کنیم: بیایید یک رشته از مقادیر روشنایی 8 پیکسل را فشرده کنیم ( آ من): (220، 211، 212، 218، 217، 214، 210، 202). دنباله های زیر را دریافت خواهیم کرد ب 1 i، و ب 2 من: (215.5، 215، 215.5، 206) و (4.5، -3، 1.5، 4). توجه داشته باشید که مقادیر ب 2 منبه اندازه کافی نزدیک به 0. اجازه دهید عملیات را با در نظر گرفتن تکرار کنیم ب 1 iچگونه آ من. این عمل به صورت بازگشتی انجام می شود، از این رو نام الگوریتم است. ما از (215.5، 215، 215.5، 206): (215.25، 210.75) (0.25، 4.75) می گیریم. ضرایب به دست آمده را که به اعداد صحیح گرد کرده و فشرده شده اند، برای مثال با استفاده از الگوریتم هافمن با جداول ثابت، می توانیم در یک فایل قرار دهیم.

توجه داشته باشید که ما فقط دو بار تبدیل خود را به زنجیره اعمال کردیم. در واقعیت، ما می توانیم تبدیل موجک را 4-6 بار اعمال کنیم. علاوه بر این، فشرده سازی اضافی را می توان با استفاده از جداول الگوریتم گام غیریکنواخت هافمن به دست آورد (یعنی باید کد هافمن را برای نزدیکترین مقدار در جدول ذخیره کنیم). این تکنیک ها به شما این امکان را می دهد که به نسبت تراکم قابل توجهی دست یابید.

ورزش:ما زنجیره (215، 211) (0، 5) (5، -3، 2، 4) را از فایل بازیابی کردیم (به مثال مراجعه کنید). رشته‌ای از هشت مقدار روشنایی پیکسل بسازید که الگوریتم فشرده‌سازی موج دوباره ایجاد کند.

با استفاده از این فرمول ها، برای یک تصویر 512x512 پیکسل، پس از اولین تبدیل، 4 ماتریس با اندازه 256x256 عنصر بدست می آوریم:

-- اولین مورد، همانطور که ممکن است حدس بزنید، یک کپی کاهش یافته از تصویر را ذخیره می کند. در دوم - تفاوت میانگین جفت مقادیر پیکسل در امتداد افقی. در سوم - تفاوت میانگین جفت مقادیر پیکسل در امتداد عمودی. در چهارم - تفاوت میانگین در مقادیر پیکسل در امتداد مورب. با قیاس با حالت دو بعدی، می توانیم تبدیل خود را تکرار کنیم و به جای ماتریس اول، 4 ماتریس به اندازه 128x128 بدست آوریم. با تکرار تبدیل خود برای بار سوم، در نهایت به 4 ماتریس 64x64، 3 ماتریس 128x128 و 3 ماتریس 256x256 خواهیم رسید. در عمل، هنگام نوشتن در یک فایل، مقادیر به دست آمده در خط آخر() معمولاً نادیده گرفته می شوند (فوراً حدود یک سوم حجم فایل را به دست می آورند - 1- 1/4 - 1/16 - 1/64...).

از مزایای این الگوریتم می توان به این واقعیت اشاره کرد که به راحتی به شما امکان می دهد هنگام انتقال تصویر از طریق شبکه، امکان "توسعه" تدریجی تصویر را درک کنید. علاوه بر این، از آنجایی که ما در واقع یک کپی کوچک از آن را در ابتدای تصویر ذخیره می کنیم، نشان دادن تصویر "درشت" بر اساس عنوان آسان تر است.

بر خلاف JPEG و الگوریتم فراکتال، این روش با بلوک ها، به عنوان مثال، پیکسل های 8x8 عمل نمی کند. به طور دقیق تر، ما با بلوک های 2x2، 4x4، 8x8 و غیره کار می کنیم. با این حال، با توجه به این واقعیت که ما ضرایب این بلوک ها را به طور مستقل ذخیره می کنیم، می توانیم به راحتی از تقسیم تصویر به مربع های "موزاییک" جلوگیری کنیم.

ویژگی های الگوریتم موج:

نسبت فشرده سازی: 2-200 (تعریف شده توسط کاربر)

کلاس تصویر:مانند فراکتال و JPEG.

تقارن: ~1.5

مشخصات:علاوه بر این، با درجه فشرده سازی بالا، تصویر به بلوک های جداگانه تقسیم می شود.

نتیجه

در پایان، اجازه دهید به جداولی نگاه کنیم که پارامترهای الگوریتم های مختلف فشرده سازی تصویر در بالا را خلاصه می کند.

این الگوریتم توسط Joint Photographic Expert Group به طور خاص برای فشرده سازی تصاویر 24 بیتی و مقیاس خاکستری در سال 1991 توسعه داده شد. این الگوریتم تصاویر دوسطحی را به خوبی فشرده نمی کند، اما تصاویر با تن پیوسته را به خوبی مدیریت می کند، که در آن پیکسل های مجاور تمایل به رنگ های مشابه دارند. معمولاً چشم با فشرده شدن 10 یا 20 بار با این روش نمی تواند تفاوتی را متوجه شود.

این الگوریتم بر اساس DCT اعمال شده بر روی ماتریسی از بلوک‌های تصویر غیر همپوشانی، با اندازه 8×8 پیکسل است. DCT این بلوک ها را با توجه به دامنه فرکانس های خاص تجزیه می کند. نتیجه ماتریسی است که در آن بسیاری از ضرایب به صفر نزدیک می‌شوند، که می‌توان آن را به شکل عددی تقریبی نشان داد. به شکل کوانتیزه بدون کاهش قابل توجهی در کیفیت ترمیم.

بیایید عملکرد الگوریتم را با جزئیات بیشتری در نظر بگیریم. فرض کنید که یک تصویر 24 بیتی تمام رنگی را فشرده می کنید. در این صورت مراحل کار زیر را بدست می آوریم.

مرحله 1.تصویر را از فضای RGB به فضای YCbCr با استفاده از عبارت زیر ترجمه می کنیم:

فوراً متذکر می شویم که تبدیل معکوس به راحتی با ضرب ماتریس معکوس در یک بردار به دست می آید که اساساً یک فضای YUV است:

.

گام 2ما تصویر اصلی را به ماتریس های 8x8 تقسیم می کنیم. از هر کدام سه ماتریس کار DCT - 8 بیت به طور جداگانه برای هر جزء تشکیل می دهیم. در تا اندازه زیادیبلوک فشرده سازی 8x8 به اجزای YCbCr در قالب 4:2:0 تجزیه می شود. اجزای Cb و Cr از طریق نقطه در سطرها و ستون ها گرفته می شوند.

مرحله 3استفاده از DCT بر روی بلوک های تصویر 8x8 پیکسل. به طور رسمی، DCT مستقیم برای یک بلوک 8x8 می تواند به صورت نوشته شود

جایی که . از آنجایی که DCT "قلب" الگوریتم JPEG است، در عمل مطلوب است که آن را با بیشترین سرعت ممکن محاسبه کنید. یک روش ساده برای سرعت بخشیدن به محاسبات، محاسبه توابع کسینوس از قبل و جدول بندی نتایج محاسبه است. علاوه بر این، با توجه به متعامد بودن توابع کسینوس با فرکانس های مختلف، فرمول فوق را می توان به صورت زیر نوشت:

.

در اینجا یک ماتریس 8x8 است که فضای 8 بعدی را برای نشان دادن ستون های بلوک در این فضا توصیف می کند. ماتریس یک ماتریس جابجا شده است و همان کار را انجام می دهد اما برای ردیف های بلوک. نتیجه یک تبدیل قابل تفکیک است که به صورت ماتریسی به صورت نوشته شده است

در اینجا، نتیجه DCT است که محاسبه آن نیاز به عملیات ضرب و تقریباً همان تعداد جمع دارد که بسیار کمتر از محاسبات مستقیم با استفاده از فرمول بالا است. به عنوان مثال، برای تبدیل یک تصویر 512x512 پیکسل، شما نیاز دارید عملیات حسابی. با در نظر گرفتن 3 جزء روشنایی، مقدار 12,582,912 عملیات حسابی را به دست می آوریم. با استفاده از الگوریتم تبدیل فوریه سریع می توان تعداد ضرب و جمع را کاهش داد. در نتیجه، برای تبدیل یک بلوک 8×8، باید 54 ضرب، 468 جمع و جابجایی بیت انجام دهید.

در نتیجه DCT، ماتریسی به دست می‌آوریم که در آن ضرایب در گوشه سمت چپ بالا با مولفه فرکانس پایین تصویر و در سمت راست پایین با فرکانس بالا مطابقت دارد.

مرحله 4کوانتیزاسیون در این مرحله، برخی از اطلاعات حذف می شوند. در اینجا، هر عدد از ماتریس بر یک عدد خاص از "جدول کوانتیزاسیون" تقسیم می شود و نتیجه به نزدیکترین عدد صحیح گرد می شود:

.

علاوه بر این، برای هر ماتریس Y، Cb و Cr، می توانید جداول کوانتیزاسیون خود را تنظیم کنید. استاندارد JPEG حتی به جداول کوانتیزاسیون خود اجازه می دهد، که با این حال، باید به رمزگشا به همراه داده های فشرده منتقل شوند، که باعث افزایش اندازه کلی فایل می شود. واضح است که انتخاب مستقل 64 ضریب برای کاربر دشوار است، بنابراین استاندارد JPEG از دو رویکرد برای ماتریس های کوانتیزاسیون استفاده می کند. اولین مورد این است که استاندارد JPEG شامل دو جدول کوانتیزاسیون توصیه شده است: یکی برای luma و دیگری برای chrominance. این جداول در زیر نشان داده شده است. روش دوم سنتز (محاسبه در پرواز) یک جدول کوانتیزاسیون بسته به یک پارامتر است که توسط کاربر مشخص می شود. خود جدول طبق فرمول ساخته شده است

در مرحله کوانتیزاسیون، نسبت تراکم کنترل می شود و بیشترین تلفات رخ می دهد. واضح است که با تنظیم جداول کوانتیزاسیون با ضرایب بزرگ، به صفرهای بیشتر و در نتیجه نسبت تراکم بیشتر خواهیم رسید.

اثرات خاص الگوریتم نیز با کوانتیزاسیون همراه است. در مقادیر زیاد مرحله کوانتیزاسیون، تلفات می تواند به حدی باشد که تصویر به مربع های 8x8 ساده تقسیم شود. به نوبه خود، تلفات در فرکانس های بالا می تواند خود را در به اصطلاح "اثر گیبس" نشان دهد، زمانی که یک "نیمبوس" مواج در اطراف خطوط با یک انتقال رنگ تیز تشکیل می شود.

مرحله 5ماتریس 8x8 را با استفاده از اسکن "زیگزاگ" به یک بردار 64 عنصری ترجمه می کنیم (شکل 2).

برنج. 2. اسکن زیگزاگ

در نتیجه در ابتدای بردار قاعدتاً ضرایب غیر صفر نوشته می شود و در انتها زنجیره های صفر تشکیل می شود.

مرحله 6ما بردار را با استفاده از اصلاح شده تبدیل می کنیم الگوریتم RLE، که در خروجی آن جفت هایی از نوع (پرش، عدد) به دست می آید، که در آن "skip" شمارنده صفرهای پرش شده است و "number" مقداری است که باید در خانه بعدی قرار داده شود. برای مثال، بردار 1118 3 0 0 0 -2 0 0 0 0 1 … به جفت (0, 1118) (0.3) (3,-2) (4.1) … تا می شود.

لازم به ذکر است که عدد اول مولفه تبدیل شده اساساً برابر با میانگین روشنایی بلوک 8x8 است و ضریب DC نامیده می شود. به طور مشابه برای همه بلوک های تصویر. این شرایط نشان می دهد که ضرایب DC می توانند به طور موثر فشرده شوند اگر مقادیر مطلق آنها ذخیره نشود، بلکه ضرایب نسبی به شکل اختلاف بین ضریب DC بلوک فعلی و ضریب DC بلوک قبلی و ضرایب اول ذخیره شوند. ضریب همانطور که هست ذخیره می شود. در این حالت می توان ترتیب ضرایب DC را به عنوان مثال به صورت زیر انجام داد (شکل 3). ضرایب باقی مانده که ضرایب AC نامیده می شوند، بدون تغییر باقی می مانند.

مرحله 7جفت های حاصل را با استفاده از کدهای هافمن غیریکنواخت با جدول ثابت جمع می کنیم. علاوه بر این، کدهای مختلفی برای ضرایب DC و AC استفاده می شود، به عنوان مثال. جداول مختلفبا کدهای هافمن

برنج. 3. طرح سفارش ضرایب DC

برنج. 4. بلوک دیاگرام الگوریتم JPEG

فرآیند بازسازی تصویر در این الگوریتم کاملاً متقارن است. این روش به شما امکان می دهد تصاویر را 10-15 بار بدون از دست دادن دید قابل توجه فشرده سازی کنید.

توسعه این استاندارد با این واقعیت هدایت شد که این الگوریتمقرار بود تصاویر را خیلی سریع فشرده کند - بیش از یک دقیقه در یک تصویر متوسط. این در سال 1991 است! و اجرای سخت افزاری آن باید نسبتاً ساده و ارزان باشد. در این مورد، الگوریتم باید از نظر زمان اجرا متقارن باشد. برآورده شدن نیاز اخیر، ظهور دوربین های دیجیتالی را که تصاویر 24 بیتی می گیرند، امکان پذیر کرد. اگر الگوریتم نامتقارن بود، منتظر ماندن طولانی تا زمانی که دستگاه "شارژ" شود - تصویر را فشرده کند، ناخوشایند خواهد بود.

اگرچه الگوریتم JPEG یک استاندارد ISO است، اما فرمت فایل آن ثابت نشده است. با استفاده از این، سازندگان فرمت های ناسازگار خود را ایجاد می کنند و بنابراین می توانند الگوریتم را تغییر دهند. بنابراین، جداول داخلی الگوریتم توصیه شده توسط ISO با آنها جایگزین می شود. همچنین انواع JPEG برای برنامه های خاص وجود دارد.

JPEG خوب قدیمی، علیرغم مزایای غیرقابل انکار زیاد، هنوز محدودیت های قابل توجهی دارد. برای حذف آنها روش جدیدی برای فشرده سازی تصویر نامیده می شد که توسعه آن برای مدت طولانی ادامه داشته است. اکنون که JPEG2000 به یک فرمت رسمی شناخته شده تبدیل شده است، این باید آغازی برای پشتیبانی فعال آن توسط تولیدکنندگان مختلف نرم افزار باشد.

مطمئناً بسیاری از افرادی که با گرافیک روی رایانه کار می کنند به این سؤال علاقه مند هستند: چگونه می توان تصویری را که مقدار بسیار چشمگیری در حافظه رایانه شخصی اشغال می کند در اندازه بسیار کوچکتر روی دیسک فشرده شود؟ به یاد دارم که در طلوع فعالیت انتشاراتم، کلمه "فشرده سازی" برای من بسیار مرموز و غافلگیر کننده بود ... در واقع، فشرده سازی تصویر چگونه کار می کند - به هر حال، اکنون تصور کردن وب، عکاسی دیجیتال یا غیر قابل تصور است. چاپ رنگی بدون آن؟

بنابراین فشرده سازی. ممکن است منجر به کاهش کیفیت شود یا خیر. مورد آخر روش هایی مانند RLE (Run Length Encoding، کدگذاری طول اجرا، که در نتیجه جفت های نوع ( جست و خیز کردن, ارزش، جایی که جست و خیز کردنتعداد صفرهای متوالی است و ارزش- مقدار به دنبال آنها) و LZW (فشرده سازی با روش Lempel-Ziff-Welch)، پیاده سازی شده در فرمت های PSD، GIF و TIFF. آنها به طور گسترده توسط آرشیوهایی مانند RAR و ZIP استفاده می شوند. میانگین نسبت فشرده سازی بدون تلفات 2-3 برابر است.

اگر نیاز به فشرده سازی تصویر با شدت بیشتری دارید، بدون افت کیفیت نمی توانید این کار را انجام دهید. اصول چیست؟ اولاً، هر تصویر حاوی افزونگی خاصی است که حذف آن منجر به تغییر قابل توجهی در کیفیت تصویر نمی شود. ثانیاً، چشم انسان به تغییرات روشنایی حساس تر از رنگ است. بنابراین، نسبت های فشرده سازی مختلف برای کانال های مختلف تصویر استفاده می شود - اطلاعات از بین می رود، اما این از نظر بصری قابل توجه نیست. علاوه بر این، حساسیت چشم به عناصر کوچک تصویر کم است که حذف آنها را بدون افت کیفیت ممکن می سازد. به این ترتیب می توانید تصویر را (حتی اگر افت کیفیت از قبل محسوس باشد) تا حد آستانه قابل قبول فشرده کنید. درجه تنزل کیفیت برای هر مورد خاص تعیین می شود. برای چاپ، فقط حداقل تحریف قابل قبول است، و برای ارسال در اینترنت (بسته به هدف) - خیلی بیشتر.

محبوب ترین روش فشرده سازی با اتلاف JPEG است که کیفیت تصویر کافی را حتی با فشرده سازی 30 برابر حفظ می کند. به هر حال، در اکثر روش های مدرن فشرده سازی داده ها (به عنوان مثال، Layer-4، معروف به mp3، و همچنین MPEG)، مکانیسم هایی شبیه به JPEG اجرا می شود. بیایید نگاهی دقیق‌تر به این قالب بیندازیم، به‌ویژه که چندی پیش آخرین پیاده‌سازی آن، JPEG2000، سرانجام تأیید شد، که شامل تمام موارد اضافه‌شده به JPEG/MPEG طی ده سال توسعه آن می‌شود.

JPEG

نام الگوریتم فشرده سازی مخفف Joint Photographic Expert Group است، یک گروه ابتکاری که توسط کارشناسان ITU (اتحادیه بین المللی مخابرات) و ISO (سازمان بین المللی استانداردسازی) تشکیل شده است. به همین دلیل است که پیشوند Joint در نام آن وجود دارد. در سال 1992، JPEG استاندارد بین المللی گرافیک اعلام شد.

فشرده سازی JPEG همیشه کیفیت خود را از دست می دهد. در این مورد، همیشه یک انتخاب وجود دارد: اولویت دادن به کیفیت به ازای حجم (اندازه فایل حدود سه برابر فشرده می شود) یا برعکس، برای دستیابی به حداقل اندازه تصویر که در آن همچنان قابل تشخیص باقی بماند ( نسبت تراکم می تواند به 100 برسد). فشرده سازی، که در آن تفاوت کیفیت بین تصویر به دست آمده و تصویر اصلی هنوز قابل توجه نیست، باعث کاهش 10 تا 20 برابری در اندازه فایل می شود.

منطقه برنامه

JPEG تصاویر تمام رنگی و تک رنگ با کیفیت عکاسی را به بهترین نحو فشرده می کند. اگر می خواهید یک تصویر را با یک پالت فهرست ذخیره کنید، ابتدا آن را به رنگ کامل تبدیل می کنید. هنگام فشرده‌سازی با استفاده از روش JPEG، باید در نظر داشته باشید که همه چیز به ماهیت تصاویر بستگی دارد: آن‌هایی که تغییر رنگ در آن‌ها ناچیز است و تغییر رنگ واضحی وجود ندارد، حجم بسیار کمتری را اشغال می‌کنند. JPEG در هر جایی که نیاز است تصاویر عکس ذخیره شوند استفاده می شود: in دوربین های دیجیتال، پلی گرافی (EPS DCS 2.0)، اینترنت بدون آن غیر قابل تصور است.

انواع مختلفی از فشرده سازی JPEG وجود دارد، اما ما تنها دو مورد از آنها را در نظر خواهیم گرفت که در بسته استاندارد برای کار با بیت مپ ها فتوشاپ, — خط پایهو ترقی خواه. دو روش دیگر - ariphmetic وlessless - عجیب و غریب هستند، به دلایلی که به طور گسترده مورد استفاده قرار نمی گیرند.

فشرده سازی چگونه اتفاق می افتد

1. مرحله اول شامل تبدیل مدل رنگتصویر (معمولاً RGB) به مدلی تبدیل می شود که در آن اجزای روشنایی و رنگ از هم جدا می شوند (به عنوان مثال، YCbCr یا YUV)، که به شما امکان می دهد به طور بهینه به انتخاب سطوح فشرده سازی برای هر کانال (با در نظر گرفتن ادراک چشم) نزدیک شوید. تبدیل به این صورت است:

Y = 0.299xR+0.587*G+0.114xB Cb = (B-Y)/0.866/2+128 Cr = (R-Y)/0.701/2+128

2. در مرحله بعدی، به اصطلاح. پیش فیلتراسیون، که در آن پیکسل های مجاور به طور جداگانه در هر یک از کانال های Cb و Cr به صورت جفت در جهت افقی و عمودی گروه بندی می شوند و کانال روشنایی Y بدون تغییر باقی می ماند. پس از آن، کل گروه چهار پیکسلی مقدار متوسط ​​مولفه های Cb و Cr مربوطه را دریافت می کند. برای اختصار، چنین طرحی را می توان به عنوان 4: 1: 1 تعیین کرد (همان فرم نمایش در DRAW - پنجره صادرات jpeg اتخاذ شده است). با در نظر گرفتن این واقعیت که هر پیکسل در 3 بایت رمزگذاری شده است (256 سطح برای هر یک از سه کانال)، در نتیجه میزان داده به طور خودکار 2 برابر کاهش می یابد (به جای 12 بایت برای انتقال 4 پیکسل، برای انتقال فقط 4+1+1 = 6 بایت کافی است. از دیدگاه ریاضیات، چنین تحولی منجر به از دست دادن قابل توجه اطلاعات می شود، اما چشم انسان از دست دادن را درک نمی کند، زیرا در تصاویر عکاسی معمولی افزونگی قابل توجهی وجود دارد.

3. اطلاعات دریافت شده، که مرحله "تمیز کردن" اولیه را پشت سر گذاشته است، دوباره در هر کانال به طور جداگانه به بلوک ها، اما در حال حاضر به اندازه 8x8 گروه بندی می شود، پس از آن فشرده سازی اصلی به آنها اعمال می شود - به اصطلاح. تبدیل کسینوس گسستهبه طور خلاصه - DCT (تبدیل کسینوس گسسته). در نتیجه اطلاعات در مورد توزیع روشنایی پیکسل به شکل دیگری تبدیل می شود، جایی که با توزیعی بر اساس توصیف می شود فراوانی وقوع یک یا آن روشنایی پیکسل DCT دارای تعدادی مزیت نسبت به سایر تبدیل ها (به عنوان مثال، تبدیل فوریه) است که بازیابی اطلاعات بهتری را ارائه می دهد.

به جای آرایه ای از 64 مقدار (8x8 پیکسل) برای هر بلوک که تصویر را می سازد، آرایه ای از 64 فرکانس دریافت می کنیم. عملکرد DCT را در یک مثال در نظر بگیرید. فرض کنید روشنایی پیکسل ها در یک بلوک از تصویر ما به شکلی است که در شکل نشان داده شده است. 1 در سمت چپ، سپس نتیجه تبدیل مانند نشان داده شده در سمت راست خواهد بود.

با وجود دقت قابل توجه، مقداری از دست دادن اطلاعات در این مرحله رخ می دهد - به همین دلیل است که JPEG همیشه منجر به از دست دادن کیفیت می شود. هدف اصلی از تحول، کشف است تصویر بزرگتوزیع اشیاء بزرگ (در شکل - بالا سمت چپ) و کوچک (پایین سمت راست) که بعداً هنگام حذف اطلاعات ناچیز مفید خواهند بود.

4. مرحله بعدی حذف اطلاعاتی است که به سختی برای چشم قابل توجه است از بلوک یا کوانتیزاسیون(کوانتیزاسیون). همه اجزا به ضرایب مختلفی تقسیم می شوند که اهمیت هر یک از آنها را برای بازیابی کیفی تصویر اصلی و نتیجه تعیین می کند. گرد کردن به یک مقدار صحیح این روش است که بیشترین کاهش کیفیت را ایجاد می کند و حجم نهایی تصویر را کاهش می دهد. اجزای فرکانس بالا به صورت درشت کوانتیزه می شوند و اجزای فرکانس پایین با دقت بیشتری کوانتیزه می شوند، زیرا بیشتر قابل توجه هستند. برای هموار کردن کاهش کیفیت، از فاکتورهای تقسیم کوچکتری در کانال روشنایی نسبت به کانال های رنگ استفاده می شود. اما بیشتر اوقات (این برای سرعت بخشیدن به محاسبات انجام می شود) ، به جای مقادیر ویژه انتخاب شده ، فقط یکی گرفته می شود - موردی که کاربر هنگام انتخاب درجه فشرده سازی وارد می کند.

برای مثال، هنگام ذخیره یک تصویر با استفاده از عملیات Save for web، پنجره فتوشاپ چگونه به نظر می رسد، جایی که پارامتر Quality (یا بهتر است بگوییم، مشتق آن) یکسان است. عامل گرد(شکل 2).

در نتیجه کوانتیزه کردن، مجموعه ای از اجزا به دست می آید که بر اساس آن تصویر اصلی با دقت معینی بازیابی می شود (شکل 3).

4

روی انجیر شکل 4 نتیجه بازیابی مربع سیاه و سفید را به ترتیب با یک، چهار و پانزده جزء نشان می دهد.

5. پس از انجام کار اصلی در فشرده سازی تصویر، تبدیلات بیشتر به وظایف ثانویه کاهش می یابد: اجزای باقی مانده به ترتیب رفتنبه گونه ای که ابتدا مسئولین جزئیات بزرگ و سپس همه موارد کوچکتر قرار می گیرند. اگر به شکل نگاه کنید، حرکت انکودر مانند یک خط زیگزاگ به نظر می رسد. مرحله زیگ زاگ نامیده می شود (شکل 5).

5

سپس توالی حاصل فشرده می شود: ابتدا با RLE معمول، سپس با روش هافمن.

6. و در نهایت تمیز مرحله فنی- داده ها در یک پوسته محصور شده اند، همراه با یک هدر، که تمام پارامترهای فشرده سازی را نشان می دهد تا بتوان تصویر را بازیابی کرد. با این حال، گاهی اوقات این اطلاعات در هدرها گنجانده نمی‌شود، که باعث افزایش فشرده‌سازی می‌شود، اما در این مورد باید مطمئن باشید که برنامه‌ای که فایل را می‌خواند از آنها اطلاع دارد.

در اینجا، به طور کلی، و همه تحولات. حالا بیایید محاسبه کنیم که در مثال ما چقدر فشرده سازی به دست آمده است. ما 7 مقدار دریافت کردیم که تصویر 8x8 اصلی را بازیابی می کند. بنابراین، فشرده سازی حاصل از استفاده از تبدیل DCT در هر دو کانال رنگی 8x8/7 9 برابر بود. بیایید نه هفت، بلکه 11 ضریب را به کانال روشنایی اختصاص دهیم، که 8x8/11 6 را می دهد. برای هر سه کانال، (9+9+6)/3=8 برابر می شود. کاهش کیفیت در هنگام "تخریب" تصویر که در مرحله دوم رخ داد افزایش مضاعف اضافی را به همراه دارد (طرح 4-1-1 با در نظر گرفتن ویژگی های رمزگذاری مؤلفه روشنایی) که نتیجه نهایی را به دست می دهد - 16 بار این یک تخمین تقریبی است که برخی از جنبه ها را در نظر نمی گیرد، اما تصویر واقعی را منعکس می کند. برای کاهش 30 برابری اندازه فایل، باید تنها 3-4 جزء باقی بگذارید.

فرآیند بازسازی تصویر به ترتیب معکوس انجام می شود: ابتدا مولفه ها در مقادیر جدول کوانتیزاسیون ضرب می شوند و ضرایب تقریبی برای تبدیل کسینوس معکوس به دست می آید. هرچه در هنگام فشرده سازی کیفیت بهتری انتخاب شود، درجه تقریب به ضرایب اصلی بیشتر می شود، به این معنی که تصویر با دقت بیشتری بازیابی می شود. باقی مانده است که فقط یک عمل اضافه کنیم: قبل از پایان، برخی تنظیمات (نویز) را در پیکسل های مرزی از بلوک های همسایه انجام دهید تا تفاوت های شدید بین آنها حذف شود.

معایب JPEG

1. عدم امکان دستیابی به نسبت تراکم بالا به دلیل محدودیت اندازه بلوک (فقط 8x8).
2. ساختار بلوکی در نسبت تراکم بالا.
3. گرد کردن گوشه های تیزو محو کردن عناصر ظریف در تصویر.
4. فقط تصاویر RGB پشتیبانی می شوند (شما فقط می توانید از JPEG برای تصاویر CMYK در فرمت EPS از طریق DCS استفاده کنید).
5. تا زمانی که تصویر به طور کامل بارگذاری نشده باشد، نمی توان آن را نمایش داد.

ده سال از تایید JPEG به عنوان استاندارد می گذرد. در طول این مدت، گروه های تحقیقاتی تعدادی افزودنی قابل توجه به نسخه اصلی پیشنهاد کرده اند که منجر به ظهور استاندارد جدیدی در پایان سال گذشته شد.

JPEG2000

از سال 1997، کار با هدف ایجاد یک سیستم کدگذاری جهانی آغاز شده است که تمام محدودیت های اعمال شده توسط JPEG را حذف می کند و می تواند به طور موثر با همه انواع تصاویر کار کند: سیاه و سفید، مقیاس خاکستری، تمام رنگی و چند جزیی، و صرف نظر از محتوا. عکس، متن نسبتاً کوچک یا حتی نقاشی باشد). همراه با سازمان های استاندارد بین المللی، غول های صنعتی مانند آگفا، کانن، فوجی فیلم، هیولت پاکارد، کداک، لوراتک، موتورولا، ریکو، سونی و دیگران در توسعه آن شرکت کردند.

از آنجایی که الگوریتم جدید ادعا می کرد جهانی است، علاوه بر این، وظیفه استفاده از روش های مختلف انتقال داده ها را نیز بر عهده داشت. حالت واقعیزمان و با پهنای باند باریک)، که به ویژه در برنامه های چند رسانه ای، به عنوان مثال، در پخش واقعی از طریق اینترنت بسیار مهم است.

الزامات اساسی برای فرمت JPEG2000:

1. دستیابی به درجه فشرده سازی بالاتر در مقایسه با JPEG.
2. پشتیبانی از تصاویر تک رنگ، که امکان استفاده از آن را برای فشرده سازی تصاویر با متن فراهم می کند.
3. امکان فشرده سازی بدون اتلاف
4. خروجی تصاویر با بهبود تدریجی جزئیات (مانند GIF مترقی).
5. استفاده از نواحی اولویت دار در تصویر که می توان کیفیت آن را بالاتر از بقیه قسمت های تصویر قرار داد.
6. رمزگشایی در زمان واقعی (بدون تاخیر).

اصل فشرده سازی

به عنوان مکانیسم اصلی فشرده سازی در JPEG2000، بر خلاف JPEG، تبدیل موج (موجک) استفاده می شود - سیستمی از فیلترها که بر روی کل تصویر اعمال می شود. بدون پرداختن به جزئیات فشرده سازی، فقط نکات اصلی را یادداشت می کنیم.

6

به عنوان مثال، تصویری که پس از فیلتر کردن پایین گذر توسط ردیف ها و ردیف ها (بالا سمت چپ) به دست می آید، بیشترین میزان را دارد. مقدار زیاداطلاعات، و دریافت پس از فرکانس بالا - حداقل. محتوای اطلاعاتی تصاویر به دست آمده پس از فیلتر پایین گذر برای ردیف ها و فیلتر بالا گذر برای ستون ها (و بالعکس) متوسط ​​است. آموزنده ترین تصویر دوباره فیلتر می شود و اجزای حاصل، مانند فشرده سازی jpeg، کوانتیزه می شوند. این چندین بار اتفاق می افتد: برای فشرده سازی بدون تلفات، حلقه معمولاً 3 بار تکرار می شود، با تلفات - 10 تکرار یک مصالحه منطقی بین اندازه، کیفیت و سرعت رفع فشار در نظر گرفته می شود. نتیجه یک تصویر کوچک و مجموعه ای از تصاویر با جزئیات دقیق است که به طور متوالی و با دقت خاصی آن را به اندازه طبیعی. بدیهی است که بیشترین درجه فشرده سازی در تصاویر بزرگ به دست می آید، زیرا چرخه های بیشتری را می توان تنظیم کرد.

پیاده سازی عملی

از زمانی که پایه های فشرده سازی JPEG2000 گذاشته شد، تعدادی از شرکت ها الگوریتم های نسبتاً کارآمدی را برای پیاده سازی آن ایجاد کرده اند.

در میان توسعه دهندگان اصلی نرم افزار، می توان به Corel اشاره کرد (به هر حال، این یکی از اولین کسانی بود که پشتیبانی از فرمت wi را بر اساس تبدیل امواج به بسته های خود معرفی کرد، که برای آن افتخار و ستایش است) - تمام تصاویر ارائه شده بر روی سی دی ها با بسته CorelDRAW تا نسخه نهم، به این صورت فشرده شدند.

بعدها، Adobe نیز به آن توجه کرد. برخی از ایده های پشت JPEG2000 توسط توسعه دهندگان فتوشاپ 6 در قالب گزینه های پیشرفته هنگام ذخیره یک تصویر به صورت JPEG (معمولی، بر اساس تبدیل کسینوس) به کار گرفته شده است. از جمله JPEG پیشرونده (گزینه Progressive در پنجره Save for Web) است. این الگوریتم اساساً برای سیستم های بلادرنگ در نظر گرفته شده است و دقیقاً مانند GIF پیشرونده عمل می کند. ابتدا یک کپی تقریبی از تصویر ظاهر می‌شود که فقط از چند بلوک بزرگ تشکیل شده است و با گذشت زمان، وقتی بقیه داده‌ها بارگذاری می‌شوند، ساختار با وضوح بیشتری و واضح‌تر دیده می‌شود تا در نهایت، تصویر نهایی به دست آید. به طور کامل بازسازی شده است. برخلاف GIF، این الگوریتم بار زیادی بر روی بیننده ایجاد می کند، زیرا باید کل چرخه تبدیل را برای هر نسخه ارسال شده تکمیل کند.

در میان سایر موارد اضافه شده، ما به گنجاندن چندین تصویر فشرده شده با JPEG با درجات مختلف فشرده سازی، وضوح و حتی در فایل اشاره می کنیم. مدل های رنگی. بر این اساس، در فتوشاپ 6 امکان انتخاب مناطق جداگانه در تصویر و اعمال تنظیمات مختلف فشرده سازی برای آنها فراهم شد. منطقه مورد نظر، برای اولین بار چنین مکانیزمی در سال 1995 با استفاده از مقادیر پایین تر در جدول کوانتیزاسیون ارائه شد. برای انجام این کار، ناحیه مورد نیاز تنظیم می شود (مثلاً به شکل یک کانال جدید در تصویر) و نماد ماسک در کنار آیتم Quality فشار داده می شود. در پنجره ای که ظاهر می شود، می توانید با حرکت دادن لغزنده ها، تصویر را آزمایش کنید - نتیجه نهایی روی صفحه نمایش داده می شود و به شما امکان می دهد به سرعت مصالحه لازم بین کیفیت و اندازه را پیدا کنید.

مبدل ها و بینندگان تخصصی

از آنجایی که استاندارد پیاده‌سازی خاصی از روش‌های فشرده‌سازی/فشرده‌سازی را مشخص نمی‌کند، این فضا را برای توسعه‌دهندگان شخص ثالث الگوریتم‌های فشرده‌سازی باز می‌کند. در واقع، شما می توانید از یک الگوریتم شکل موج ساده استفاده کنید و در نتیجه فرآیند فشرده سازی را سرعت بخشید، یا برعکس، از یک الگوریتم پیچیده تر استفاده کنید و بر این اساس، به منابع سیستم زیادی نیاز دارید.

راه حل های تخصصی از شرکت های دیگر به عنوان توسعه تجاری در دسترس هستند. برخی به عنوان برنامه های جداگانه (JPEG 2000 توسعه یافته توسط Aware)، برخی دیگر به عنوان ماژول های الحاقی برای رایج ترین ویرایشگرهای شطرنجی (ImagePress JPEG2000 توسعه یافته توسط Pegasus Imaging و ماژول LEAD JPEG2000 از LEAD Technologies) اجرا می شوند. در مقابل پیشینه آنها، شرکت LuraTech متمایز است که مدت هاست با این موضوع سروکار داشته است. این فناوری LuraWave خود را در محصول مستقل LuraWave SmartCompress (نسخه سوم اکنون در دسترس است) ترویج می‌کند و ماژول‌هایی را برای Photoshop، Paintshop، Photopaint ارائه می‌دهد. ویژگی متمایز- بیشتر سرعت بالاکار (تبدیل تقریباً آنی) حتی با تصاویر چند مگابایتی. بر این اساس، قیمت این ماژول بالاترین - 79 دلار است.

برای مشاهده تصاویر JPEG2000 در مرورگرها، باید یک ماژول نمایشگر ویژه نصب کنید (همه توسعه دهندگان آن را به صورت رایگان ارائه می دهند). درج یک تصویر در یک سند html، مانند هر افزونه، به استفاده از ساختار EMBED (با پارامترهای اضافی) منجر می شود. به عنوان مثال، به این معنی است که از روش انتقال تصویر پیشرونده استفاده خواهد شد. یعنی در مثال ما (فایل 139 کیلوبایتی) ابتدا فقط 250 بایت منتقل می شود که بر اساس آن یک تصویر خشن ساخته می شود سپس پس از بارگذاری 500 بایت تصویر به روز می شود (این کار تا زمانی که مقدار LIMIT ادامه یابد ادامه می یابد. رسیده).

اگر می خواهید تصویر بهتری داشته باشید، باید مورد Improve را از منویی که در دکمه سمت راست ظاهر می شود انتخاب کنید (شکل 9). برای چهار رزومه، کل تصویر به طور کامل دانلود می شود.

9

نتیجه گیری

بنابراین، JPEG2000 به طور عینی نشان می دهد بالاترین امتیازهااز JPEG فقط در نسبت فشرده سازی بالا. با فشرده سازی 10-20 بار، تفاوت زیادی وجود ندارد. آیا می تواند جایگزین قالب گسترده شود یا به سادگی با آن رقابت کند؟ در آینده نزدیک - به سختی، در بیشتر موارد، نسبت کیفیت / اندازه ارائه شده توسط JPEG کاملا قابل قبول است. و آن 10 تا 20 درصد فشرده‌سازی اضافی که JPEG2000 با کیفیت بصری یکسان ارائه می‌کند، بعید است که منجر به افزایش محبوبیت آن شود.

از سوی دیگر، شرکت‌های دوربین‌های دیجیتال علاقه زیادی به فرمت جدید نشان می‌دهند، زیرا اندازه ماتریس‌های حساس به نور هر سال به طور پیوسته افزایش می‌یابد و قرار دادن تصاویر در حافظه سخت‌تر می‌شود. و سپس فرمت جدید گسترده تر خواهد شد، و چه کسی می داند، شاید پس از مدتی JPEG2000 به JPEG برسد. در هر صورت، آنالوگ میکرو دیوایس اخیراً یک تراشه تخصصی منتشر کرده است که در آن فشرده‌سازی/فشرده‌سازی با استفاده از یک فناوری جدید در سطح سخت‌افزار اجرا می‌شود و وزارت دفاع ایالات متحده در حال حاضر فعالانه از فرمت جدیدی برای ضبط عکس‌های دریافتی از ماهواره‌های جاسوسی استفاده می‌کند.

حقایق و حدسیات

1. JPEG هنگام باز کردن و ذخیره مجدد فایل کیفیت خود را از دست می دهد.

درست نیست.کیفیت فقط زمانی از بین می رود که نسبت فشرده سازی کمتر از نسبت فشرده سازی انتخاب شده باشد که تصویر در آن ذخیره شده است.

2. JPEG هنگام ویرایش فایل کیفیت خود را از دست می دهد.

آیا حقیقت دارد.هنگامی که یک فایل اصلاح شده را ذخیره می کنید، همه تبدیل ها دوباره انجام می شوند - بنابراین از ویرایش مکرر تصویر خودداری کنید. این فقط زمانی اعمال می‌شود که فایل بسته باشد، اگر فایل باز بماند، دلیلی برای نگرانی وجود ندارد.

3. نتیجه فشرده سازی با پارامترهای یکسان در برنامه های مختلف یکسان خواهد بود.

درست نیست. برنامه های متفرقهمقادیر وارد شده توسط کاربر را متفاوت تفسیر کنید. به عنوان مثال، در یک برنامه، کیفیت تصویر ذخیره شده (به عنوان مثال، در فتوشاپ)، در برنامه دیگر، میزان فشرده سازی آن (مقابله) نشان داده شده است.

4. وقتی روی حداکثر کیفیت تنظیم می شود، تصویر بدون افت کیفیت ذخیره می شود.

درست نیست. JPEG همیشه با تلفات فشرده می شود. اما تنظیم، به عنوان مثال، کیفیت 90٪ به جای 100٪ باعث کاهش حجم فایل بیشتر از کاهش کیفیت می شود.

5. هر فایل JPEG را می توان در هر ویرایشگری که فرمت JPEG را درک می کند باز کرد.

درست نیست.پیشرو JPEG گونه ای از JPEG است که برخی از ویرایشگران آن را درک نمی کنند.

6. JPEG از شفافیت پشتیبانی نمی کند.

آیا حقیقت دارد.گاهی اوقات ممکن است به نظر برسد که بخشی از تصویر شفاف است، اما در واقع رنگ آن به سادگی طوری انتخاب می شود که با رنگ پس زمینه در صفحه html مطابقت داشته باشد.

7. JPEG بهتر از GIF فشرده می شود.

درست نیست.آنها حوزه های کاربردی مختلفی دارند. به طور کلی، یک تصویر "گیف" معمولی پس از تبدیل به JPEG حجم بیشتری خواهد داشت.

JPEG2000 در مقابل JPEG

2. با فشرده سازی بالاتر، کیفیت JPEG2000 به طور قابل توجهی بالاتر از JPEG است، که به شما امکان می دهد بدون تلفات زیاد تا 50 بار فشرده سازی کنید، و با مقداری تلفات (ما در مورد تصاویر برای اینترنت صحبت می کنیم) - تا 100 و حتی بیشتر تا 200

3. با نسبت فشرده سازی بالا در مناطقی که تغییر رنگ صاف وجود دارد، تصویر ساختار بلوکی مشخصه یک JPEG ساده را به دست نمی آورد. JPEG2000 همچنین لبه های تیز را تا حدودی لکه دار و گرد می کند - عکس ها را ببینید (شکل 7 و 8).

نتایج فشرده سازی فایل آزمایشی را با نسبت های مختلف فشرده سازی نشان می دهد (در سمت چپ - ذخیره شده در فتوشاپ با فرمت JPG، در سمت راست - با فرمت JPEG2000). برای تصویر در شکل 7 سطح فشرده سازی 20، 40، 70 و 145 انتخاب شد (در هنگام ذخیره در JPEG2000 می توان آنها را به صراحت مشخص کرد)، درجه فشرده سازی JPGبه گونه ای انتخاب شد که اندازه فایل مانند پس از فشرده سازی توسط JPEG2000 باشد. همانطور که می گویند، نتایج در. برای وضوح، آزمایش دوم بر روی تصویری با جزئیات واضح تر (با سطوح فشرده سازی 10، 20، 40 و 80) انجام شد. مزیت دوباره JPEG2000 است (شکل 8).

8

4. از آنجایی که در واقع، کپی هایی با وضوح های مختلف در یک فایل JPEG2000 ذخیره می شوند

بنابراین، برای کسانی که گالری تصاویر در اینترنت می سازند، نیازی به ایجاد تصاویر کوچک برای آنها نیست.

5. فشرده سازی بدون اعوجاج (حالت بدون از دست دادن) مورد توجه خاص است. بنابراین، فایل آزمایشی با فشرده سازی LZW از فتوشاپ 827 کیلوبایت گرفت و JPEG2000 - 473 کیلوبایت فشرده شد.

6. در مقایسه با JPEG، همنام پیشرفته‌تر آن منابع سیستم را به میزان قابل توجهی مصرف می‌کند. اما قدرت کامپیوترها که طی دو سال گذشته به طور قابل توجهی افزایش یافته است، این امکان را فراهم می کند که با روشی جدید مشکلات فشرده سازی تصویر را با موفقیت حل کنیم.

7. عدم پشتیبانی از JPEG2000 در مرورگرها. برای مشاهده چنین تصاویری، باید یک افزونه نسبتاً بزرگ (1.2 مگابایت) دانلود کنید.

8. عدم وجود نرم افزار رایگان برای ذخیره تصاویر در فرمت جدید.

مجلات در حوزه عمومی

در همین موضوع:

• آموزش

UPD. من مجبور شدم قالب بندی monospace را حذف کنم. یک روز خوب، habraparser درک قالب‌بندی داخل تگ‌های پیش و کد را متوقف کرد. همه متن ها به یک آشفتگی تبدیل شده است. اداره حبر نتوانست به من کمک کند. اکنون ناهموار، اما حداقل قابل خواندن است.

آیا تا به حال خواسته اید بدانید که یک فایل jpg چگونه کار می کند؟ حالا بیایید بفهمیم! کامپایلر و ویرایشگر هگز مورد علاقه خود را گرم کنید، بیایید این را رمزگشایی کنیم:

به خصوص یک نقاشی کوچکتر گرفت. این فاویکون آشنا اما به شدت فشرده شده گوگل است:

من بلافاصله به شما هشدار می دهم که توضیحات ساده شده است و اطلاعات ارائه شده کامل نیست، اما پس از آن درک مشخصات آسان خواهد بود.

حتی بدون اینکه بدانیم رمزگذاری چگونه انجام می‌شود، می‌توانیم چیزی را از فایل استخراج کنیم.
- نشانگر شروع همیشه در ابتدای همه فایل های jpg است.
بایت ها دنبال می شوند. . این نشانگری است که شروع یک بخش نظر را نشان می دهد. 2 بایت بعدی - طول بخش (از جمله این 2 بایت). بنابراین در دو بعدی - خود نظر اینها کدهای کاراکتر ":" و ")" هستند، یعنی. شکلک معمولی می توانید آن را در خط اول در سمت راست ویرایشگر هگز مشاهده کنید.

کمی تئوری

اجازه دهید یادآوری کنم که هر بلوک Y ij , Cb ij , Cr ij ماتریسی از ضرایب DCT است که با کدهای هافمن کدگذاری شده است. آنها به ترتیب زیر در فایل قرار دارند: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20

خواندن یک فایل

• فایل به بخش هایی تقسیم می شود که قبل از آنها نشانگرها وجود دارد.
• طول توکن ها 2 بایت است و اولین بایت .
• تقریباً همه سکتورها طول خود را در 2 بایت بعدی بعد از نشانگر ذخیره می کنند.

نشانگر: DQT - جدول کوانتیزاسیون.

FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF
اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف

هدر بخش همیشه 3 بایت است. در مورد ما، این است. سربرگ شامل موارد زیر است:
طول: 0x43 = 67 بایت
طول مقادیر در جدول: 0 (0 - 1 بایت، 1 - 2 بایت)
[_0] شناسه جدول: 0
64 بایت باقی مانده باید جدول 8x8 را پر کند.

به ترتیب پر شدن مقادیر جدول دقت بیشتری کنید. به این ترتیب نظم زیگزاگ می گویند:

نشانگر: SOF0 - Baseline DCT

FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01

طول: 17 بایت
دقت: 8 بیت در روش پایه، همیشه 8 است. همانطور که من متوجه شدم، این عمق بیت مقادیر کانال است.
ارتفاع تصویر: 0x10 = 16
عرض الگو: 0x10 = 16
تعداد اجزاء: 3. اغلب آن Y، Cb، Cr است.

جزء اول:
شناسه: 1
نازک شدن افقی (H 1): 2
[_2] نازک شدن عمودی (V 1): 2
شناسه جدول کوانتیزاسیون: 0

جزء دوم:
شناسه: 2
نازک شدن افقی (H 2): 1
[_1] نازک شدن عمودی (V 2): 1

جزء سوم:
شناسه: 3
نازک شدن افقی (H 3): 1
[_1] نازک شدن عمودی (V 3): 1
شناسه جدول کوانتیزاسیون: 1

اکنون به نحوه تعیین میزان نازک شدن یک تصویر نگاه کنید. ما H max \u003d 2 و V max \u003d 2 را پیدا می کنیم. کانال i با H max /H i بار افقی و V max /V i بار عمودی کاهش می یابد.

نشانگر: DHT (نمودار هافمن)

FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02

طول: 21 بایت
کلاس: 0 (0 - جدول ضریب DC، 1 - جدول ضریب AC).
[_0] شناسه جدول: 0
طول کد هافمن: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
تعداد کدها:
تعداد کدها به معنای تعداد کدهای آن طول است. توجه داشته باشید که این بخش فقط طول کدها را ذخیره می کند نه خود کدها را. خودمان باید کدها را پیدا کنیم. بنابراین، ما یک کد به طول 1 و یکی از طول 2 داریم. در کل 2 کد وجود دارد، هیچ کد دیگری در این جدول وجود ندارد.
هر کد دارای یک مقدار مرتبط با آن است و در ادامه در فایل فهرست شده است. مقادیر تک بایتی هستند، بنابراین ما 2 بایت را می خوانیم.
- مقدار کد 1.
- مقدار کد دوم

ساختن درختی از کدهای هافمن

درختان برای همه جداول در این مثال:


UPD (با تشکر): گره های اولین درخت (DC، id = 0) باید دارای مقادیر 0x03 و 0x02 باشند.

در دایره ها - مقادیر کدها، زیر دایره ها - خود کدها (توضیح خواهم داد که ما آنها را با رفتن از بالا به هر گره دریافت کردیم). با چنین کدهایی (این و سایر جداول) است که محتوای شکل رمزگذاری می شود.

نشانگر: SOS (شروع اسکن)

  FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00

طول هدر (نه کل بخش): 12 بایت.
تعداد اجزای اسکن ما 3، هر کدام برای Y، Cb، Cr داریم.

جزء اول:
شماره جزء تصویر: 1 (Y)
شناسه جدول هافمن برای ضرایب DC: 0
[_0] شناسه جدول هافمن برای ضرایب AC: 0

جزء دوم:
شماره قطعه تصویر: 2 (Cb)

[_1]

جزء سوم:
شماره قطعه تصویر: 3 (Cr)
شناسه جدول هافمن برای ضرایب DC: 1
[_1] شناسه جدول هافمن برای ضرایب AC: 1

این اجزا به صورت چرخه ای متناوب می شوند.

این جایی است که قسمت هدر به پایان می رسد، از اینجا تا انتهای داده های رمزگذاری شده (مارکر).

0

پیدا کردن ضریب DC
1. خواندن دنباله ای از بیت ها (اگر ما 2 بایت را ملاقات کنیم، این یک نشانگر نیست، بلکه فقط یک بایت است). پس از هر بیت، بسته به بیت خوانده شده، در امتداد درخت هافمن (با شناسه مربوطه) در امتداد شاخه 0 یا 1 حرکت می کنیم. اگر در گره نهایی باشیم متوقف می شویم.
10 1011101110011101100001111100100

2. مقدار گره را می گیریم. اگر برابر 0 باشد، ضریب 0 است، آن را روی جدول بنویسید و به خواندن ضرایب دیگر ادامه دهید. در مورد ما - 02. این مقدار طول ضریب در بیت است. یعنی 2 بیت بعدی را می خوانیم این ضریب می شود.
10 10 11101110011101100001111100100

3. اگر رقم اول مقدار در نمایش باینری 1 است، آن را به همین صورت رها کنید: DC_coef = مقدار. در غیر این صورت، تبدیل: DC_coef = value-2 value length +1 . ضریب را در جدول در ابتدای زیگزاگ - گوشه سمت چپ بالا می نویسیم.

یافتن ضرایب AC
1. مشابه مورد 1، یافتن ضریب DC. ما به خواندن دنباله ادامه می دهیم:
10 10 1110 1110011101100001111100100

2. مقدار گره را می گیریم. اگر برابر با 0 باشد، به این معنی است که مقادیر باقیمانده ماتریس باید با صفر پر شود. سپس ماتریس بعدی کدگذاری می شود. چند نفر اولی که تا این لحظه مطالعه کردند و در مورد آن به صورت شخصی برای من نوشتند، یک امتیاز مثبت در کارما دریافت خواهند کرد. در مورد ما، مقدار گره 0x31 است.
اولین نیبل: 0x3 - این مقدار صفر است که باید به ماتریس اضافه کنیم. اینها 3 ضریب صفر هستند.
نیبل دوم: 0x1 - طول ضریب در بیت. بیت بعدی را بخوانید.
10 10 1110 1 110011101100001111100100

3. مشابه نقطه 3 یافتن ضریب DC.

همانطور که قبلاً فهمیدید، باید ضرایب AC را بخوانید تا زمانی که به مقدار صفر کد برخورد کنید یا تا زمانی که ماتریس پر شود.
در مورد ما، ما دریافت خواهیم کرد:
10 10 1110 1 1100 11 101 10 0 0 0 1 11110 0 100
و ماتریس:

آیا توجه کرده اید که مقادیر با همان الگوی زیگزاگ پر شده اند؟
دلیل استفاده از این ترتیب ساده است - زیرا هر چه مقادیر v و u بزرگتر باشد، ضریب S vu در تبدیل کسینوس گسسته کمتر است. بنابراین، در نسبت های فشرده سازی بالا، ضرایب ناچیز روی صفر تنظیم می شود و در نتیجه حجم فایل کاهش می یابد.

[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

آخه یادم رفت بگم ضرایب DC کد شده خود ضرایب DC نیست بلکه تفاوتشون بین ضرایب جدول قبلی (همون کانال) هست! شما باید ماتریس ها را اصلاح کنید:
DC برای دوم: 2 + (-4) = -2
DC برای سوم: -2 + 5 = 3
DC برای چهارمین: 3 + (-4) = -1

[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………

حالا سفارش بده این قانون تا پایان فایل معتبر است.

و با ماتریس برای Cb و Cr:

[-1 0 0 0 0 0 0 0]
[ 1 1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

از آنجایی که هر کدام تنها یک ماتریس وجود دارد، ضرایب DC می توانند دست نخورده باقی بمانند.

محاسبه

کوانتیزاسیون

[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

به طور مشابه، ما 3 ماتریس کانال Y دیگر دریافت می کنیم ...

[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

… و با ماتریس برای Cb و Cr.

[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

تبدیل کسینوس گسسته معکوس

فرمول نباید سخت باشد*. S vu ماتریس ضریب حاصله ما است. u - ستون، v - ردیف. s yx - مقادیر کانال مستقیم.

* به طور کلی، این کاملاً درست نیست. وقتی توانستم یک طراحی 16x16 را رمزگشایی کنم و روی صفحه نمایش دهم، یک تصویر 600x600 گرفتم (به هر حال، این جلد آلبوم مورد علاقه من Mind.In.A.Box - Lost Alone بود). بلافاصله کار نکرد - اشکالات مختلفی ظاهر شد. به زودی می توانم تصویری که به درستی بارگذاری شده بود را تحسین کنم. تنها ناامیدی سرعت دانلود بود. هنوز به یاد دارم که 7 ثانیه طول کشید. اما این تعجب آور نیست، اگر بدون فکر از فرمول فوق استفاده کنید، سپس برای محاسبه یک کانال یک پیکسل، باید 128 کسینوس، 768 ضرب، و برخی از جمع ها را در آنجا پیدا کنید. فقط در مورد آن فکر کنید - تقریباً هزار عملیات دشوار فقط برای یک کانال از یک پیکسل! خوشبختانه جا برای بهینه سازی وجود دارد (پس از آزمایش های زیاد زمان بارگذاری را تا حد دقت تایمر 15 میلی ثانیه کاهش دادم و بعد از آن تصویر را به عکسی 25 برابر بزرگتر تغییر دادم. شاید در مقاله ای جداگانه در این مورد بنویسم) .

من نتیجه محاسبه تنها ماتریس اول کانال Y را خواهم نوشت (مقادیر گرد هستند):


[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]

و 2 تای دیگه:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]

1. اوه، بریم بخوریم!
2. بله من اصلا وارد نمی شوم، این چه حرفی است که می زنی؟
3. هنگامی که مقادیر رنگ YCbCr به دست آمد، تبدیل به RGB باقی می ماند، مانند این: YCbCrToRGB(Y ij، Cb ij، Cr ij)، Y ij، Cb ij، Cr ij - ماتریس های دریافتی ما.
4. 4 ماتریس Y و هر کدام یک Cb و Cr، زیرا ما کانال ها را نازک کردیم و 4 پیکسل Y مربوط به هر یک Cb و Cr است. بنابراین، به این صورت محاسبه کنید: YCbCrToRGB(Y ij , Cb , Cr )

YCbCr به RGB

در اینجا جداول به دست آمده برای کانال های R، G، B برای مربع 8x8 سمت چپ مثال ما آمده است:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108

231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186

255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134

پایان