گسسته سازی و کمی سازی تصاویر. مسئله فوریه اپتیک و روشهای پردازش تصویر دیجیتال

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

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

AT سیستم های واقعیدو نوع کوانتیزاسیون عمدتا استفاده می شود - گامای خطی تصحیح شده. AT آخرین موردسیگنال آنالوگ قبل از کوانتیزاسیون تحت یک تبدیل غیر خطی قرار می گیرد x'=x 1 /  . این عملکرد تقریباً در تمام دوربین های CCD تولید شده در صنعت اجرا می شود. مقدار پیش فرض  1.4 است.

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

انتخاب بهینه تعداد سطوح نمونه گیری تا حد زیادی به ویژگی های دستگاه گیرنده (مثلاً دوربین مداربسته) بستگی دارد. دوربین های CCD همه منظورهبه ندرت نسبت سیگنال به نویز بیشتر از 46 دسی بل دارند. نسبت سیگنال به نویزبا عبارت زیر تعریف می شود:
، جایی که
- حداکثر دامنه سیگنال مفید،
دامنه rms نویز است. بر این اساس، با نسبت سیگنال به نویز 46 دسی بل، تعداد مفید سطوح کوانتیزاسیون 200 است که نشان دهنده مصلحت استفاده از کوانتایزر هشت بیتی است.

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

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

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

( ک ) - مقادیر پیش بینی شده این قرائت ها لازم است که خطای ریشه میانگین مربع حداقل باشد، یعنی. نیاز به پیدا کردن

min e = E (g(k) - } (4.21)

همه جا k و i

این یک کار شناخته شده است، و اگر روند g ( ک ) ساکن است، سپس محلول آن شکل می گیرد

, (4.22)

r (j - i) = E [ g (k - j) g (k - i) ] (4.23)

معمولاً به عنوان تابع همبستگی خودکار فرآیند شناخته می شود gشانس یک منبا حل سیستم معادلات (4.22) به دست می آیند.

مقادیر بهینه ضرایب پیش بینی به روابط نقاط تصویر توصیف شده توسط تابع همبستگی خودکار بستگی دارد. از تعریف (4.20) می توان دریافت که در مورد داده های ثابت تابع همبستگی خودکاربا تابع فوق با یک مقدار ثابت تفاوت دارد. برای داده های غیر ثابت، تابع r(در رابطه (4.23) به متغیرهای فضایی بستگی دارد و ضرایب پیش‌بینی بهینه باید با مختصات مکانی متفاوت باشد. این برای تصاویر معمول است. خوشبختانه، ویژگی‌های آماری غیر ثابت تصاویر معمولاً به خوبی قابل تقریب هستند. توابع ثابت، به طوری که غیر قابل تبدیل دستگاه خطیپیش بینی های خوبی می دهد نتایج خوب. هنگام فشرده‌سازی اطلاعات ویدیویی با استفاده از روش DPCM، خطاها معمولاً در مرزهای اشیاء تصویر شده ظاهر می‌شوند، جایی که فرض ثابت بودن به کمترین میزان برآورده می‌شود و به صورت بصری در تصویر بازسازی‌شده به‌عنوان نقاط روشن یا تاریک غیرعادی درک می‌شوند.

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

حداقل تعداد سطوح کوانتیزه دو (اعداد یک رقمی) است و مربوط به چنین کمی سازی تصویر است، که در آن اختلاف روشنایی یک مقدار ثابت (مثبت یا منفی) می گیرد. این روش معمولا نامیده می شود مدولاسیون دلتا،مدار DPCM (شکل 4.8) را می توان با جایگزینی کوانتایزر با یک محدود کننده و پیش بینی کننده ساده کرد. n هفتمسفارش در هر یکپارچه کننده هنگامی که تصاویر اضافی توسط مدولاسیون دلتا کاهش می‌یابند، همان معایبی که با مدولاسیون دلتا سیگنال‌های دیگر مانند گفتار، یعنی کشیدن لبه و اعوجاج تکه تکه شدن مشاهده می‌شود. با این حال، اگر نرخ نمونه برداری از تصویر بسیار بیشتر از فرکانس Nyquist انتخاب شود، فشرده سازی مدولاسیون دلتا منجر به خطاهای کوچک (به طور ذهنی قابل توجه) می شود. اگر نرخ نمونه‌برداری به فرکانس Nyquist نزدیک شود، در این صورت تصویر کشش لبه (در لبه‌های تصویر) و اعوجاج تکه تکه شدن (در مناطق با روشنایی ثابت) را نشان می‌دهد. مانند فشرده سازی گفتار، مدولاسیون دلتا تطبیقی ​​اجازه می دهد تا این خطاها کاهش یابد. با این حال، به طور کلی، هنگام انتقال تصاویر، مدولاسیون دلتا نسبت به هنگام انتقال گفتار مؤثرتر بود.

کوانتیزاسیون با بیش از دو سطح، با کاهش افزونگی، امکان به دست آوردن تصاویر بیشتر را فراهم می کند کیفیت بالا. سیستم فشرده سازی DPCM با کوانتیزاسیون 8 سطحی (3 بیتی) در قرارگیری بهینهآستانه تصاویری را ارائه می دهد که کیفیت آنها مانند یک سیستم PCM با عمق کمی بین 6 تا 8 است. استثناء خطاهای نزدیک به خطوط تغییر شدید روشنایی است.

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

در بالا، مسائل فشرده‌سازی تصویر با استفاده از DPCM هنگام انتخاب عناصر توسط خط (یعنی نقاطی که روی آن‌ها قرار دارند، مورد بحث قرار گرفت. خط فعلیجارو می کشد). با توجه به ماهیت دو بعدی تصاویر، می توان (و توصیه می شود) روش DPCM را گسترش داد تا پیش بینی روشنایی در نقاطی را که نه تنها در جریان جریان، بلکه در خطوط اسکن قبلی قرار دارند، در نظر بگیرد. . طرح‌های فشرده‌سازی DPCM با این پیش‌بینی دوبعدی بر اساس همان اصول پیش‌بینی 1 بعدی است. از آنجایی که تصاویر با وجود روابط آماری دو بعدی مشخص می‌شوند، می‌توان امیدوار بود که پیش‌بینی دو بعدی نتایج بهتری در فشرده‌سازی تصویر داشته باشد، زیرا همبستگی تصویر با استفاده از عملیات پیش‌بینی و تفریق در دو مختصات انجام می‌شود. در واقع، دستگاه‌های دارای پیش‌بینی فضایی بیشتر می‌دهند تصاویر با کیفیت. حبیبی نشان داد که با کمک یک پیش بینی کننده مرتبه سوم دوبعدی با کوانتیزه سازی 8 سطحی (3 بیتی)، تصاویری به دست آمد که از نظر بصری قابل تشخیص نیستند. عکس های اصلیپردازش شده توسط PCM با اعداد 11 بیتی.

برای تصاویری که از فریم‌های متوالی تشکیل شده‌اند، مانند تلویزیون، ایده‌های پیش‌بینی و تفریق مرتبط با DPCM را می‌توان به حوزه زمانی گسترش داد. AT تصاویر مشابهروشنایی بسیاری از نقاط از فریم به فریم تغییر نمی کند یا به آرامی تغییر می کند. بنابراین می توان یک سیستم فشرده سازی DPCM ساخت که در آن روشنایی نقطه بعدی بر اساس روشنایی مجموعه دو بعدی از نقاط قاب فعلی و نقاط متناظر فریم های قبلی پیش بینی شود. در عمل، ترتیب پیش بینی زمانی نمی تواند زیاد باشد، زیرا برای هر ترم زمانی لازم است یک دستگاه حافظه داشته باشیم که در آن کل فریم ذخیره شود. مدل‌سازی با پیش‌بینی‌کننده مرتبه سوم با استفاده از نقاط واقع در این (و فریم‌های قبلی) در سمت چپ نقطه در نظر گرفته‌شده و از آن برای پیش‌بینی نشان داد که می‌توان به‌دست‌آمده بسیار زیادی تصاویر خوببا عمق بیت متوسط ​​1 بیت / نقطه.

4.3.3. طرح‌های کاهش افزونگی تصویر با پردازش دامنه تبدیل

برای توضیح عملیات اصلی انجام شده توسط سیستم فشرده سازی اطلاعات ویدئویی با پردازش در حوزه تبدیل، اجازه دهید به ماتریس کوواریانس تعریف شده توسط رابطه (4.20) بپردازیم. ماتریس [ Cg] همبستگی نمونه های تصویر را در صفحه توصیف می کند ( x، y)که صفحه مختصات تصویر است. یک روش مهمچند بعدی تحلیل آماریمطالعه آرایه داده ها نه تنها در مختصات طبیعی آنها، بلکه در سیستم های مختصات با ویژگی های راحت تر است. به طور خاص، سیستم های مختصات مبتنی بر مقادیر ویژه و بردارهای ویژه ماتریس کوواریانس

[ C g ] = [ Ф ] [

] [ Ф ] T = , (4.24)

جایی که [ اف] - ماتریسی متشکل از ستون های بردار ویژه متعامد اف منآ [ ] - ماتریس مورب مقادیر ویژه.

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

جلب توجه می کند

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

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

در ادامه، داستانی خسته کننده و غیرقابل درک در مورد روش برش میانی، الگوریتم پراکندگی خطای فلوید-اشتاینبرگ (نویز کوانتیزاسیون) (و نه تنها)، ویژگی های ادراک رنگ چشم انسان، و همچنین برخی کدهای مزخرف خواهید دید. .

زمینه

مدت‌ها پیش، زمانی که نوکیا گرم بود و لامپ بر بازار گوشی‌های هوشمند تسلط داشت و صاحبان گوشی‌های هوشمند با افتخار خود را «سازندگان گوشی‌های هوشمند» می‌نامیدند، در آن روزهای قدیم برنامه‌های ساده پایتون را برای سری60 می‌نوشتم. در حین کندوکاو در آرشیو به یکی از آنها برخوردم. GifTool برنامه ای برای ایجاد گیف انیمیشن از مجموعه ای از تصاویر است. در آن، من کوانتیزاسیون را با روش برش میانی، الگوریتم پیاده‌سازی کردم فشرده سازی LZW، کل ساختار فایل به طور مستقل ایجاد شده است، برای پیکسل هایی که در اسلاید بعدی تغییر نکرده اند، از شفافیت برای کاهش اندازه نهایی فایل استفاده شده است. می خواستم حافظه ام را تازه کنم، ببینم چگونه کار می کند. کد رو باز کرد و... اون حسی که وقتی نمیتونی کد ده ساله ی گنده ات رو بفهمی. من در آن زمان در مورد PEP8 نمی دانستم، بنابراین خوانایی کد کمی کمتر از هیچ بود (در آن زمان من مانند بسیاری از برنامه نویسان تازه کار مینیمالیسم را دوست داشتم). من اشک ریختم، تف کردم، در PyCharm بازسازی کردم، نحوه اجرای روش بخش متوسط ​​را فهمیدم، به سرعت یک اسکریپت "کثیف" انداختم. آثار! پالت ایجاد می شود، تصویر خروجی قابل تحمل است. و سپس گاز گرفتم - آیا می توانم به نتایج بهتری برسم تا تصویر از نظر بصری تا حد امکان به تصویر اصلی نزدیک شود.

بنابراین - روش بخش میانه. تا حد رسوایی ساده است. اولین قدم ایجاد یک مکعب RGB از تمام رنگ های منحصر به فرد تصویر است. بعد، آن را در امتداد طولانی ترین سمت برش دهید. به عنوان مثال، ما یک محدوده قرمز از 7 تا 231 (طول 231-7=224)، سبز از 32 تا 170 (طول 170-32=138)، آبی از 12 تا 250 (طول 250-12=238) داریم. بنابراین ما مکعب را در امتداد سمت آبی "برش" خواهیم داد. بخش های حاصل نیز در امتداد سمت بلند و غیره بریده می شوند. تا زمانی که به 256 قسمت برسیم. برای هر بخش، میانگین رنگ را محاسبه کنید - اینگونه است که پالت را بدست می آوریم.

چند عکس تقریباً به موضوع، برای وضوح

چه چیزی را می توان در اینجا بهبود بخشید؟ اولین چیزی که به ذهن می رسد این است که میانگین رنگ را نه با جمع کردن احمقانه همه رنگ ها و تقسیم بر تعداد آنها [جمع(رنگ) / تعداد(رنگ)]، بلکه با در نظر گرفتن تعداد دفعات تکرار هر رنگ در رنگ محاسبه کنید. تصویر یعنی هر رنگ را در تعداد دفعات آن در تصویر ضرب می کنیم، مقادیر به دست آمده را اضافه می کنیم، نتیجه را بر تعداد وقوع در تصویر همه رنگ های این بخش [ مجموع (رنگ * کل) / مجموع (کل) تقسیم می کنیم. ) ]. در نتیجه، رنگ‌هایی که اغلب با آنها مواجه می‌شوند در محاسبه اولویت دارند، اما رنگ‌های کمیاب نیز تنظیمات خاص خود را انجام می‌دهند، بنابراین پالت بهتر است، انحراف بصری رنگ‌ها کمتر است. برای بهترین نتیجه، مطلوب است که گاما را نیز در نظر بگیریم، اما من آن را برای بعد گذاشتم. مورد دوم چندان واضح نیست - بخش متوسط ​​​​اصلاً ویژگی های درک رنگ توسط چشم انسان را در نظر نمی گیرد. ما سایه های سبز را خیلی بهتر از سایه های آبی درک می کنیم. تصمیم گرفتم این سوء تفاهم را اصلاح کنم و مکعب را "مسطح" کردم - طول اضلاع را در ضرایب این مقاله ضرب کردم. در نتیجه، بخش‌های بیشتری در دو طرف سبز و قرمز و کمتر در سمت آبی وجود دارد. من چنین راه حلی را در هیچ جای دیگری ندیده ام (شاید بد نگاه می کردم) اما نتیجه واضح است.

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

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

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

خب میخواستم خلاصه توضیح بدم ولی یه سری نوشته های نامفهوم بود. امیدوارم بهتر از چیزی که توضیح دادم کدنویسی کنم، پس لینک github اینجاست. کد چندین بار بازنویسی شد، ابتدا الگوریتم بهبود یافت، تا زمانی که نتیجه مناسب من بود، سپس معلوم شد که هنگام پردازش عکس ها رم زیادی می خورد (در ابتدا آن را روی عکس های کوچک تست کردم)، مجبور شدم آن را منتقل کنم. مکعب RGB، بخش میانه و نقشه پیکسل به پایگاه داده (sqlite). اسکریپت بسیار کند است، اما نتیجه بهتر از کوانتیزه کردن با PIL / Pillow و GIMP است (در آن به این عملیات نمایه سازی می گویند).

نمایش تصویری:

اصلی

نتیجه کوانتیزاسیون در GIMP، پالت بهینه برای 256 رنگ + پراکندگی رنگ طبق فلوید-استنبرگ (عادی)

نتیجه کوانتیزاسیون PIL/Pillow image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, color=256)

نتیجه کمی سازی توسط کد من

به چه مواردی باید توجه کرد: اتلاف خطای GIMP بسیار "نویزدار" است، PIL/Pillow یک پالت زیر بهینه ایجاد می کند و تقریباً هیچ خطای هدر نمی رود (انتقال شدید بین رنگ ها).
اگر تفاوت را نمی بینید، نمونه های دیگر را در github بررسی کنید.

P.S.:یک برنامه شگفت‌انگیز Color Quantizer وجود دارد که با این کار بهتر و سریع‌تر کنار می‌آید، بنابراین اسکریپت من معنای عملی ندارد و صرفاً به دلیل علاقه "ورزشی" ساخته شده است.
UPD:پروژه را در github به روز کرد. اضافه شدن الگوریتم کوانتیزاسیون Octree (octree)، فرمول های پراکندگی خطای رایج، جستجو برای نزدیکترین رنگ با میانگین مقدار قرمز.

حاشیه نویسی: معرفی. الگوریتم پارتیشن بندی یکنواخت فضای رنگی. الگوریتم پارتیشن بندی فرکانس: ایده الگوریتم، روش پارتیشن بندی مکعب رنگ - جستجوی مرتب شده محلی. الگوریتم بخش میانه. روش های خوشه بندی برای کمی سازی تصویر: روش K-means، روش اتصال گراف، روش سلسله مراتبی، روش K-means تعمیم یافته یا روش ضخیم سازی پویا. نتیجه.

12.1. معرفی

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

کوانتیزاسیون برای موارد زیر مورد نیاز است:

• صرفه جویی در حافظه؛
• بهبود خواص توالی برای فشرده سازی؛
• آماده سازی برای پردازش بیشتر؛
• افزودن افکت ها

اجازه دهید در مورد این نکات با جزئیات بیشتری در رابطه با تصاویر توضیح دهیم.

بدیهی است که صرفه جویی در حافظه با کاهش هزینه ذخیره مقادیر مشخصه حاصل می شود. بسیاری از فرمت های ذخیره سازی تصویر 1 مانند PNG، GIF، به جای ذخیره مقادیر مشخصه، اعداد مرجع را برای رشته های پالت ذخیره می کنند. پالت جدولی است که سطرهای آن دارای یک مقدار مشخصه ثابت هستند. قبلا از مکانیزم پالت برای شکل‌دهی و نمایش تصاویر روی نمایشگر استفاده می‌شد، زیرا میزان حافظه ویدئویی قبل از سال 1995 در حد معمول بود. کامپیوتر رومیزیاز یک مگابایت تجاوز نکرد.

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

برنج. 12.1.

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

برای افزودن می توان از کمی سازی تصویر استفاده کرد جلوه های هنریو تعیین مرزها

این فصل فرض می‌کند که مقادیر ویژگی پیکسل تصویر در فضای رنگی RGB هستند ("مفاهیم اساسی. نمایش رنگ در گرافیک کامپیوتر"). کدهای شبه الگوریتم ها برای سادگی ارائه برای یک تصویر 8 بیتی در مقیاس خاکستری (256 سایه) داده شده است (شکل 12.1 را ببینید)، تبدیل به یک تصویر 4 بیتی (16 سایه) انجام می شود.

برنج. 12.2.

12.2. الگوریتم پارتیشن بندی یکنواخت فضای رنگی

ساده ترین الگوریتم کوانتیزاسیون را در نظر بگیرید - الگوریتم پارتیشن بندی یکنواخت فضای رنگی، همچنین به نام کوانتیزاسیون خطی. بیایید خرد کنیم فضای رنگیبه قسمت های مساوی در هر یک از جهت های اصلی (برای RGB سه جهت وجود دارد - با توجه به تعداد اجزا). به عنوان مثال، در جهت محور آبی یا سبز (به شکل 1.5 مراجعه کنید)، مکعب را به 8 قسمت و در جهت قرمز - به 4 قسمت تقسیم می کنیم. مجموعه مقادیری که در تقاطع پارتیشن ها تشکیل می شوند در جدول وارد می شوند. در مثال ما، 256 مقدار به طور مساوی در سراسر مکعب RGB توزیع شده است. علاوه بر این، تبدیل تصویر به جستجوی عدد مربوطه در جدول کاهش می‌یابد تا فاصله بین رنگ واقعی و رنگ جایگزین حداقل باشد. این را می توان به سرعت با گرد کردن انجام داد.

// از 256 سایه خاکستری 16 می کنیم // I(pixel) - ویژگی پیکسل // Inew(pixel) ویژگی جدید - شماره مرجع در پالت // پالت - پالت // تعداد سایه ها در تصویر اصلی NOldColors = 256; // تعداد عناصر در پالت NNewColors = 16; // 1. پالت را برای (i = 0; i.) پر کنید< NNewColors; i++) { Palette[i] = i * (NOldColors / NNewColors); } // 2. Вычиcляем новые значения атрибутов foreach(pixel in I) // для каждого пикселя { // округляем, отбрасывая قسمت کسری Inew(pixel) = I(pixel) / (NOldColors / NNewColors)؛ ) فهرست 12.1. الگوریتم پارتیشن بندی یکنواخت فضای رنگی

در نتیجه کار این الگوریتم (شکل را ببینید 12.2) در تصویر اغلب مرزهای خیلی واضح ظاهر می شوند و برعکس جزئیات پاک می شوند. اما از مزایای اصلی این الگوریتم می توان به سادگی و سرعت بالا اشاره کرد.

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

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

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

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

(1.12)

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

خطای کوانتیزاسیون rms (1.12) برابر است با

. (1.13)

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

.

لازم به ذکر است که آستانه های شدید با محدوده دینامیکی روشنایی تعیین می شوند. معادلات (1.14) را می توان به راحتی به شکل کاهش داد

.

از (1.15) نتیجه می شود که آستانه ها باید در وسط بین دو سطح همسایه قرار گیرند و . حل این معادلات را می توان به صورت تکراری یافت. کوانتایزر بهینه ای که معیار (1.12) را برآورده می کند، کوانتایزر Lloyd-Max نامیده می شود و ریشه میانگین مربعات خطای چنین کوانتایزری است.

(1.16)

با توزیع یکنواخت روشنایی، معادلات غیر خطی (1.15) را می توان به صورت

,

و ریشه میانگین مربعات خطا است.

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

خطوط کاذب به طور قابل توجهی کیفیت بصری تصویر را کاهش می دهند، زیرا. بینایی انسان به خصوص به خطوط خطوط حساس است. برای کمی سازی یکنواخت تصاویر معمولی، حداقل 64 سطح مورد نیاز است. شکل‌های 1.7.a و 1.7.b نتایج کمی‌سازی یکنواخت تصویر "Portrait" را به ترتیب در 256 و 14 سطح کوانتیزه‌سازی نشان می‌دهند.

شکل 1.6. به مکانیسم وقوع خطوط کاذب

شکل 1.7. نتایج کوانتیزاسیون یکنواخت
شکل 1.8. نتیجه کوانتیزاسیون غیر یکنواخت	شکل 1.9. هیستوگرام تصویر "پرتره".

در قسمت های تاریک تصویر در شکل. 1.7.b، خطوط کاذب قابل توجه است. استفاده از کوانتایزر Lloyd-Max می تواند سطح آنها را به میزان قابل توجهی کاهش دهد (شکل 1.8 را ببینید، جایی که تعداد سطوح کوانتیزاسیون نیز 14 است). روی انجیر 1.9 هیستوگرام روشنایی تصویر "Portrait" را در 256 سطح کوانتیزاسیون نشان می دهد و آستانه ها را در . از شکل برمی آید که مناطقی از محدوده دینامیکی که در آنها مقادیر روشنایی نمونه ها گروه بندی می شوند، اغلب کوانتیزه می شوند.

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

شکل 1.10. کوانتیزاسیون با پیش تبدیل غیر خطی

برای از بین بردن خطوط کاذب، رابرتز پیشنهاد کرد که نویز با چگالی احتمال یکنواخت را قبل از کوانتیزاسیون یکنواخت به خوانش‌های روشنایی اضافه کنید. نویز اضافه شده، برخی از نمونه های تصویر را یک سطح به بالا و برخی دیگر را به یک سطح پایین می برد. بنابراین، خطوط کاذب از بین می روند. واریانس نویز اضافه شده باید کم باشد تا منجر به اعوجاج هایی نشود که به عنوان "برف" در تصویر درک می شود و در عین حال برای از بین بردن خطوط نادرست کافی است. معمولاً از نویز یکنواخت توزیع شده در بازه استفاده می شود. نتایج کوانتیزاسیون یکنواخت در 14 و 8 سطح تصویر "Portrait" با اضافه کردن اولیه نویز در شکل 1.11.a و 1.11.b نشان داده شده است. در 8 سطح کوانتیزاسیون، نویز اضافه شده بسیار محسوس می شود، اما خطوط کاذب تقریباً به طور کامل از بین می روند.

شکل 1.11. نتایج کوانتیزاسیون یکنواخت با اضافه کردن نویز اولیه

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

.

این عمل برای همه بلوک ها تکرار می شود. تصویر حاصل به دو سطح کوانتیزه می شود. روی انجیر 1.12.a یک تصویر در مقیاس خاکستری "Portrait" را با یک سیگنال مزاحم اضافه نشان می دهد. روی انجیر 1.12.b، c نتایج کوانتیزاسیون باینری تصویر "Portrait" را با یک سیگنال مزاحم اضافه شده نشان می دهد (شکل 1.12.b) و بدون آن (شکل 1.12.c).

شکل 1.12. شطرنجی سازی تصاویر

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