فشرده سازی jpeg برای چه نوع تصاویری موثر است. الگوریتم های فشرده سازی تصویر

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

این الگوریتم بر اساس DCT اعمال شده بر روی یک ماتریس 8x8 پیکسل از بلوک های تصویری غیرمجاز است. 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 و دیگری برای chroma. این جداول در زیر ارائه شده است. روش دوم سنتز (محاسبه در پرواز) یک جدول کوانتیزاسیون است که به یک پارامتری که توسط کاربر مشخص شده است بستگی دارد. خود جدول با استفاده از فرمول ساخته شده است

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

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

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

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

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

مرحله 6.ما بردار را با استفاده از الگوریتم RLE اصلاح شده تبدیل می کنیم، که در خروجی آن جفت هایی از نوع (پرش، عدد) به دست می آید، که در آن "پرش" شمارنده صفرهای نادیده گرفته شده است و "عدد" مقداری است که باید در آن قرار داده شود. سلول بعدی به عنوان مثال، بردار 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 به طور ویژه برای فشرده سازی تصویر توسط Joint Photographic Expert Group (JPEG) توسعه یافته است و بر اساس DCT است.

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

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

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

کوانتیزاسیون معمولا بر اساس انجام می شود ماتریس ویژهکه شامل مقسوم‌کننده‌هایی است که عناصر DCT باید توسط آن‌ها تقسیم شوند. اغلب از الگوریتم زیر استفاده می شود:

Q (i، j) = 1 + ((1 + i + j) q);

جایی که Q (i، j) ماتریس مقسوم علیه است،

q یک پارامتر کیفیت است.

با انتخاب پارامتر q می توانید مقادیر مقسوم علیه ها را کنترل کرده و نسبت تراکم را تنظیم کنید. به عنوان مثال، برای q = 2، ماتریسی به شکل زیر دریافت می کنید (شکل 3.6):

شکل 3.6. نمونه ای از ماتریس کوانتیزاسیون

پس از تقسیم 64 عنصر ماتریس بر عناصر ماتریس Q (i، j)، ماتریسی به دست می آید که در آن:

تعداد زیادی از مقادیر صفر اضافی ظاهر می شود،

اثر کاهش مقادیر از سمت چپ بالا به گوشه سمت راست پایین حتی بیشتر خواهد بود.

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

شکل 3.7. تبدیل یک ماتریس دو بعدی به یک دنباله یک بعدی با استفاده از روش "زیگزاگ".

همانطور که در شکل مشاهده می کنید، یک ماتریس دو بعدی با فرمت 8*8 عنصر به دنباله ای تک بعدی با طول 64 عنصر تبدیل می شود. ویژگی اصلی چنین دنباله ای، محل مهم ترین ضرایب در ابتدای آن و کمترین آن خواهد بود. عناصر قابل توجه(معمولاً صفر) در انتهای آن.

پیاده سازی الگوریتم شامل راد است اقدام منسجم، که در شکل نشان داده شده است. 3.8.

شکل 3.8. توالی عملیات هنگام اجرای الگوریتم JPEG.

1. تصویر در صورت لزوم به فرمت YUV تبدیل می شود.

2. سیگنال های تفاوت رنگ U و V مطابق با فرمت 4: 2: 0 نمونه برداری می شوند. تقسیم یک تصویر به 8 در 8 قطعه. علاوه بر این، پردازش سیگنال‌های درخشندگی و کرومینانس می‌تواند به طور مستقل و موازی انجام شود.

3. تبدیل کسینوس گسسته بر روی تمام بلوک های 8*8 المان انجام می شود.

4. کوانتیزاسیون مطابق با پارامتر کیفیت انتخاب شده.

5. اسکن "زیگزاگ" برای به دست آوردن یک دنباله یک بعدی از 64 عنصر.

6. الگوریتم RLEبرای یک دنباله تک بعدی اعمال می شود.

7. الگوریتم هافمن به دنباله ای اعمال می شود که قبلاً با استفاده از RLE فشرده شده است.

8. ص. 3 - 7 برای همه بلوک ها با فرمت عناصر 8*8 و برای همه سطوح رنگی اجرا می شود.

ویژگی های کلیدی روش JPEGبه شرح زیر است:

1. نسبت فشرده سازی بالا، به خصوص برای تصاویر با کیفیت خوب یا عالی.

2. تعداد زیادی پارامتر که به کاربر ماهر اجازه می دهد تنظیمات روش را آزمایش کند و به تعادل فشرده سازی / کیفیت لازم دست یابد.

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

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

5. قابلیت استفاده از فشرده سازی بدون تلفات با نسبت تراکم نه چندان بالا.

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

فشرده سازی JPEG در چند مرحله انجام می شود. هدف این است که داده های گرافیکی را به گونه ای تبدیل کنیم که اطلاعات بصری ناچیز به راحتی شناسایی و دور ریخته شوند. این فشرده‌سازی «تلفات» با بسیاری از روش‌های دیگر مورد استفاده در فرمت‌های گرافیکی متفاوت است، که سعی می‌کنند هر ذره‌ای از تصویر را دست نخورده نگه دارند.

مدل رنگ

اولین قدم در JPEG انتخاب روش مناسب برای نمایش رنگ ها است. رنگ ها معمولاً در یک سیستم مختصات سه بعدی مشخص می شوند. این سیستم که برای اکثر برنامه نویسان به خوبی شناخته شده است، رنگ را ترکیبی از قرمز، سبز و آبی (RGB) توصیف می کند. متأسفانه از نظر امکان فشرده سازی اینطور نیست بهترین راهتوضیحات رنگ مشکل این است که هر سه جزء - قرمز، سبز و آبی - برابر هستند. با این حال، انتقال به یک سیستم رنگی متفاوت به شما امکان می دهد تا موارد بیشتری را برجسته کنید اطلاعات مهم.

حرفه ای ها از دو مدل رنگی استفاده می کنند: HSL (Hue-Saturation-Lightness) و HSV (Hue-Saturation-Value). به طور شهودی واضح است که مؤلفه Lightness مدل HSL و مؤلفه روشنایی (Value) مدل HSV هر کدام به روشی نسبت نور و سایه را تعیین می کنند. اشباع سطح رنگ "خالص" را مشخص می کند. رنگ های غیراشباع اغلب به طور غیررسمی به عنوان "خاکستری" نامیده می شوند. رنگ چیزی است که ما به عنوان رنگ یک شی، مانند قرمز یا سبز مایل به خاکستری درک می کنیم. در اینجا توجه به آن ضروری است حقیقت جالب: بینایی انسان نسبت به تغییرات نور حساس تر است و نه رنگ!

پیاده سازی های مختلف الگوریتم فشرده سازی JPEG از موارد متفاوتی استفاده می کنند سیستم های رنگی... سیستم رندر رنگ YCbCr که توسط JFIF استفاده می شود بسیار شبیه به سیستمی است که سال ها پیش برای تلویزیون رنگی ساخته شد.

لاغر کننده

دلیل اصلی تبدیل یک مدل رنگی به مدل دیگر نیاز به شناسایی اطلاعاتی است که کمتر برای مشاهده تصویر ضروری هستند. JPEG مقدار اطلاعات رنگ را کاهش می دهد. در حالی که جزء luma با وضوح کامل منتقل می شود، اجزای تفاوت رنگ از نیمی از محدوده مقادیر استفاده می کنند. در نتیجه مرحله سادهحجم داده ها یک سوم کاهش می یابد.

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

تبدیل کسینوس گسسته (DCT)

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

همانطور که در مورد تصویر حذف شده، مقدار متوسط ​​رنگ اطلاعات بسیار مهمی در مورد منطقه تصویر است. چشم شما نسبت به سرعت تغییر رنگ حساسیت کمتری دارد، بنابراین چندان مهم نیست. با تبدیل اطلاعات رنگ به روشی مشابه، ما اطلاعات قابل اهدا را برجسته می کنیم.

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

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

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

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

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

عملیات کوانتیزه توضیح می دهد که چرا فشرده سازی JPEG در مورد خطوط واضح منجر به خطوط "جیت" می شود. خطوط با فرکانس بالا (به سرعت در حال تغییر) جزء فضایی تعریف می شوند. (در نگاه اول، ممکن است به نظر برسد که باید یک طرح کلی مبهم داشته باشید، اما به یاد داشته باشید که C در DCT مخفف کسینوس است.)

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

فشرده سازی

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

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

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

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

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

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

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

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

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

یکی از مشکلات جدی گرافیک کامپیوتری این است که هنوز معیار مناسبی برای ارزیابی افت کیفیت تصویر پیدا نشده است. و به طور مداوم از بین می رود - هنگام دیجیتالی کردن، هنگام انتقال به یک پالت محدود رنگ، هنگام انتقال به سیستم نمایش رنگ دیگری برای چاپ، و، که به ویژه برای ما مهم است، هنگام بایگانی با ضرر. یک مثال از یک معیار ساده می توان ارائه داد: انحراف استاندارد مقادیر پیکسل (L 2 اندازه گیری، یا ریشه میانگین مربع - RMS):

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

برای مثال حداکثر انحراف را در نظر بگیرید:

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

معیاری که اکنون در عمل استفاده می شود، نسبت سیگنال به نویز پیک به پیک (PSNR) نامیده می شود.

این اندازه گیری در واقع شبیه انحراف معیار است، اما به دلیل مقیاس لگاریتمی مقیاس، استفاده از آن تا حدودی راحت تر است. همان معایب انحراف معیار را دارد.

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

JPEG یکی از جدیدترین و قدرتمندترین الگوریتم ها است. در عمل، این استاندارد بالفعل برای تصاویر تمام رنگی است. این الگوریتم با نواحی ۸×۸ عمل می‌کند، جایی که روشنایی و رنگ نسبتاً آرام تغییر می‌کنند. در نتیجه، زمانی که ماتریس چنین ناحیه‌ای در یک سری دوگانه در کسینوس بسط می‌یابد (به فرمول‌های زیر مراجعه کنید)، تنها ضرایب اول مهم هستند. بنابراین، فشرده سازی در JPEG به هزینه تغییرات صاف در رنگ ها در تصویر انجام می شود.

الگوریتمی که توسط گروهی از متخصصان عکاسی به طور خاص برای فشرده سازی تصاویر 24 بیتی توسعه یافته است. JPEG - Joint Photographic Expert Group یک بخش در ISO - سازمان بین المللی استانداردسازی است. نام الگوریتم به عنوان ["jei" peg] خوانده می شود. به طور کلی، این الگوریتم مبتنی بر تبدیل کسینوس گسسته (از این پس DCT) است که بر روی ماتریس تصویر اعمال می شود تا ماتریس جدیدی از ضرایب به دست آید. برای به دست آوردن تصویر اصلی، یک تبدیل معکوس اعمال می شود.

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 خود (از این پس MK) مشخص شده است. در این مرحله نسبت تراکم کنترل می شود و بیشترین تلفات رخ می دهد. واضح است که با مشخص کردن MK با ضرایب بزرگ، به صفرهای بیشتر و در نتیجه نسبت تراکم بیشتر خواهیم رسید.

کوانتیزاسیون نیز با اثرات خاص الگوریتم همراه است. در مقادیر زیاد ضریب گاما، از دست دادن در فرکانس‌های پایین می‌تواند آنقدر زیاد باشد که تصویر به مربع‌های 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. اثر گیبس آشکار می شود - هاله ها در امتداد مرزهای انتقال رنگ تیز.

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

نیاز اخیر این امکان را برای اسباب‌بازی‌هایی مانند دوربین‌های دیجیتال - دستگاه‌هایی به اندازه یک دوربین فیلم‌برداری کوچک فراهم می‌کند تا عکس‌های 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 هستند: مثلث Sierpinski و Barnsley Fern. "مثلث سیرپینسکی" با سه و "سرس بارنسلی" با چهار تبدیل وابسته (یا در اصطلاح ما "عدسی") تعریف می شود. هر تبدیل به معنای واقعی کلمه توسط بایت های خوانده شده رمزگذاری می شود، در حالی که تصویر ساخته شده با کمک آنها می تواند چندین مگابایت را اشغال کند.

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

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

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

تعریف.

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

تعریف. تبدیل به عنوان نشان داده شده است

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

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

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

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

قضیه. (درباره تبدیل قرارداد)

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

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

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

اجازه دهید تبدیل افین سه بعدی به شکل نوشته شود

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

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

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

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

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

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

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

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 بیت به منظور تنظیم تغییر روشنایی در طول ترجمه.

اطلاعات اندازه بلوک را می توان در هدر فایل ذخیره کرد. بنابراین، ما کمتر از 4 بایت را برای یک تبدیل affine صرف کردیم. بسته به اندازه بلوک، می توانید محاسبه کنید که چند بلوک در تصویر وجود دارد. بنابراین، می توانیم تخمینی از درجه فشرده سازی به دست آوریم.

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

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

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

این هزینه برای سرعت فشرده سازیو برای سادگی بسته بندی ضرایب در یک فایل.

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

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

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

,

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

.

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

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

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

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

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

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

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

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

همانطور که می توانید محاسبه کنید، تعداد عملیات در هر پیکسل از یک تصویر در مقیاس خاکستری در طول بازیابی به طور غیرمعمول کم است (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،2 i.

بیایید تحلیل کنیم مثال خاص: اجازه دهید یک رشته از مقادیر روشنایی 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) را از فایل بازیابی کرده ایم (به مثال مراجعه کنید). رشته ای از هشت مقدار روشنایی پیکسل بسازید که توسط الگوریتم فشرده سازی موج دوباره ایجاد می شود.

الگوریتم داده های دو بعدی نیز به روشی مشابه پیاده سازی شده است. اگر مربع 4 نقطه با روشنایی داشته باشیم آ 2 i، 2 j,آ 2 i +1، 2 j,آ 2 i، 2 j +1، و آ 2 i +1، 2 j +1، سپس

اصلی		ب 1	ب 2
تصویر		ب 3	ب 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

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

نتیجه

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

الگوریتم	ویژگی های تصویر که به دلیل آن فشرده سازی رخ می دهد
RLE	رنگهای یکسان متوالی: 2 2 2 2 2 2 15 15 15
LZW	زنجیر یکسان: 2 3 15 40 2 3 15 40
هافمن	فرکانس رنگ های مختلف: 2 2 3 2 2 4 3 2 2 2 4
CCITT-3	غلبه سفیددر تصویر، مناطق بزرگ با یک رنگ پر شده است
بازگشتی	انتقال رنگ صاف و بدون لبه های تیز
Jpeg	عدم وجود مرزهای دقیق
فراکتال	شباهت بین عناصر تصویر

الگوریتم	کیت فشرده سازی	تقارن زمانی	برای چی جهت دار	تلفات	بعد، ابعاد، اندازه
RLE	32, 2, 0.5	1	3.4 بیتی	نه	1D
LZW	1000, 4, 5/7	1.2-3	1-8 بیت	نه	1D
هافمن	8, 1.5, 1	1-1.5	8 بیت	نه	1D
CCITT-3	213(3), 5, 0.25	~1	1 بیتی	نه	1D
JBIG	2-30 بار	~1	1 بیتی	نه	2 بعدی
JPEG بدون اتلاف	2 بار	~1	24 بیتی، خاکستری	نه	2 بعدی
Jpeg	2-20 بار	~1	24 بیتی، خاکستری	آره	2 بعدی
فشرده سازی بازگشتی	2-200 بار	1.5	24 بیتی، خاکستری	آره	2 بعدی
فراکتال	2-2000 بار	1000-10000	24 بیتی، خاکستری	آره	2.5 بعدی

• آموزش

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

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

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

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

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

کمی تئوری

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

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

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

پس از استخراج نظر، درک این موضوع باید آسان باشد:

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

برای راحتی، بیایید نشانگرها را برجسته کنیم:
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78



FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 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 FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00 AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9

نشانگر: 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 FF
اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف اف

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

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

نشانگر: SOF0 - Baseline DCT

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

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 = 2 و V max = 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.
- مقدار کد دوم

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

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

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


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

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

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

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

& nbsp 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 (کروم)
شناسه جدول هافمن برای ضرایب 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 طول مقدار +1. ضریب را در جدول در ابتدای زیگزاگ - گوشه سمت چپ بالا می نویسیم.

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

2. مقدار گره را می گیریم. اگر برابر با 0 باشد، به این معنی است که مقادیر باقیمانده ماتریس باید با صفر پر شوند. سپس ماتریس بعدی کدگذاری می شود. چند نفر اولی که تا اینجا خوانده اند و در مورد آن به صورت شخصی برای من نوشته اند، یک امتیاز مثبت در کارما دریافت خواهند کرد. در مورد ما، مقدار گره 0x31 است.
اولین nibble: 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 را می توان به حال خود رها کرد.

محاسبات

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

آیا به یاد دارید که ماتریس از مرحله کوانتیزاسیون عبور می کند؟ عناصر ماتریس باید ترم به ترم با عناصر ماتریس کوانتیزاسیون ضرب شوند. باقی مانده است که مورد نیاز خود را انتخاب کنید. ابتدا مؤلفه اول را اسکن کردیم، مؤلفه تصویر آن = 1. مؤلفه تصویر با این شناسه از ماتریس کوانتیزاسیون 0 استفاده می کند (ما آن را اولین مورد از این دو هستیم). بنابراین پس از ضرب:

[ 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)

اگر 1 و 4 را انتخاب کردید، برای شما خوشحالم. یا درست متوجه شدید یا به زودی از غذایتان لذت خواهید برد.

YCbCr به RGB

R = Y + 1.402 * کر
G = Y - 0.34414 * Cb - 0.71414 * Cr
B = Y + 1.772 * Cb
فراموش نکنید که 128 را اضافه کنید. اگر مقادیر خارج از محدوده هستند، مقادیر مرزی را تعیین کنید. فرمول ساده است، اما کسری از زمان CPU را نیز مصرف می کند.

در اینجا جداول حاصل برای کانال های 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

پایان

به طور کلی، من متخصص JPEG نیستم، بنابراین به سختی می توانم به همه سؤالات پاسخ دهم. فقط وقتی داشتم رسیورم را می نوشتم، اغلب مجبور بودم با چیزهای مختلفی سر و کار داشته باشم مشکلات غیر قابل درک... و وقتی تصویر به اشتباه نمایش داده شد، نمی دانستم کجا اشتباه کرده ام. شاید او بیت ها را اشتباه تعبیر کرده است یا شاید از DCT سوء استفاده کرده است. من از دست دادم مثال گام به گامبنابراین امیدوارم این مقاله هنگام نوشتن رمزگشا کمک کند. من فکر می‌کنم که شرح روش اصلی را پوشش می‌دهد، اما هنوز هم نمی‌توانید این کار را انجام دهید. در اینجا چند لینک است که به من کمک کرد: