برش میانی

برش میانه ای (به انگلیسی: median cut) الگوریتمی برای یافتن نماینده‌هایی مناسب از یک مجموعه عناصر چند بعدی است که توسط پاول هکبرت (Paul Heckbert) در سال ۱۹۷۹ میلادی ابداع شد. این روش یک الگوریتم بازگشتی است و در هر مرحله داده‌ها را به دو دسته حول میانه بُعد با بزرگ‌ترین دامنه تغییرات تقسیم می‌کند و در پایان برای هر دسته نماینده ای مشخص می‌کند. برش میانی در حال حاضر پر استفاده‌ترین الگوریتم برای گسسته سازی رنگ است.

تحلیل الگوریتم

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

گسسته سازی رنگ

با در نظر گرفتن رنگ‌ها به صورت RGB , عدد هر رنگ یک عدد ۸ بیتی از ۰ تا ۲۵۵ خواهد بود. پس تعداد رنگ‌های ممکن برابر خواهد بود. اما می‌شود با استفاده از تعداد بسیار کمتری رنگ متفاوت، در بسیاری از تصاویر کیفیت مطلوب را به دست آورد. مسئله پیدا کردن این رنگ‌های پالت نسبتاً کوچک‌تر است. این تعداد بستگی به نوع نمایش دارد ولی در بسیاری از نمایشگرها ۲۵۶ انتخاب می‌شود.

مزایا

کاهش رنگ‌های نمایش داده شده برای نمایشگرها با تعداد رنگ کم عملی ضروری است تا نزدیکترین رنگ موجود به رنگ واقعی جایگزین آن شود؛ ولی علاوه بر این با کاهش رنگ‌های موجود می‌توان میزان حافظه لازم برای ذخیره تصاویر را تا حدی کاهش داد. برای این کار تهیه یک جدول که هر عدد دودویی را به رنگ کاهش یافته مورد نظر تناظر دهد لازم است تا نمایشگر بتواند برای نمایش رنگ هر پیکسل تصمیم بگیرد
از سال ۱۹۷۰ روش‌های زیادی برای کاهش رنگ‌های بیت مپ‌ها از جمله octree و روش‌های بر پایه واریانس ابداع شده که محبوب‌ترین آن‌ها همین روش برش میانی است. کاری که این الگوریتم انجام می‌دهد این است که محدوده‌هایی را برای داده‌ها پیدا می‌کند که داده‌ها در آن‌ها تجمع کرده‌اند و از دیگر نواحی به شکل محسوسی جدا افتاده‌اند.
بعد از این که رنگ‌های پالت مشخص شد کار بعدی متناظر کردن رنگ پیکسل‌های تصویر به آن رنگ هاست. این کار با این ایده انجام می‌شود که فاصله اقلیدسی بین رنگ واقعی و رنگ کاهش یافته کمینه شود. معمولاً برای بهتر شدن تصویر و کاهش خطا در پایان از روش Dithering استفاده می‌شود.

جدول مراجعه ایستا

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

الگوریتم محبوبیت

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