برش میانی
برش میانه ای (به انگلیسی: median cut) الگوریتمی برای یافتن نماینده‌هایی مناسب از یک مجموعه عناصر چند بعدی است که توسط پاول هکبرت (Paul Heckbert) در سال ۱۹۷۹ میلادی ابداع شد. این روش یک الگوریتم بازگشتی است و در هر مرحله داده‌ها را به دو دسته حول میانه بُعد با بزرگ‌ترین دامنه تغییرات تقسیم می‌کند و در پایان برای هر دسته نماینده ای مشخص می‌کند. برش میانی در حال حاضر پر استفاده‌ترین الگوریتم برای گسسته سازی رنگ است.
این الگوریتم به این شکل عمل می‌کند که در هر دسته ابتدا مولفه ای که دامنه تغییرات عناصر در آن از بقیه بزرگ‌تر است را پیدا کرده و داده‌ها را برحسب مقادیر در آن بُعد مرتب می‌کند. سپس با پیدا کردن میانه داده‌ها را به دو دسته قبل و بعد میانه تقسیم می‌کند. اگر هنوز تعداد دسته‌های ایجاد شده از تعداد مورد نظر کمتر بود این عملیات را بر روی هر دو دسته ایجاد شده تکرار می‌کند. در پایان معمولاً میانگین عناصر هر دسته را به عنوان نماینده آن دسته انتخاب می‌کنند.
معمولاً عناصر مجموعه را به شکل یک بردار در نظر می‌گیرند. در این صورت شبه کد الگوریتم به این شکل خواهد بود: def median_cut (array, reprsnt_num, step):
اگر formula_1داده در فضای formula_2بعدی داشته باشیم، درصورتی که در پیاده‌سازی این الگوریتم از مرتب‌سازی هرمی (از formula_3)استفاده کنیم و در هر مرحله برای پیدا کردن مولفه با بیشتربن بازه، کمینه و بیشینه را برای هر مولفه بیابیم (از formula_4) و ادغام لیست‌ها را در formula_5انجام دهیم، داریم:formula_6
از قضیه اصلی واکاوی الگوریتم‌ها داریم که چون: formula_7
یعنی:formula_8(معمولاً formula_1از formula_2بسیار بزرگ‌تر است) در پیاده‌سازی این الگوریتم بازگشتی از پشته استفاده می‌شود پس بهتر است با توجه به حجم بزرگ داده‌ها، از مرتب‌سازی‌های بازگشتی صرف نظر کنیم. با در نظر گرفتن رنگ‌ها به صورت RGB , عدد هر رنگ یک عدد ۸ بیتی از ۰ تا ۲۵۵ خواهد بود. پس تعداد رنگ‌های ممکن برابر formula_11خواهد بود. اما می‌شود با استفاده از تعداد بسیار کمتری رنگ متفاوت، در بسیاری از تصاویر کیفیت مطلوب را به دست آورد. مسئله پیدا کردن این رنگ‌های نسبتاً کوچک‌تر است. این تعداد بستگی به نوع نمایش دارد ولی در بسیاری از نمایشگرها ۲۵۶ انتخاب می‌شود. کاهش رنگ‌های نمایش داده شده برای نمایشگرها با تعداد رنگ کم عملی ضروری است تا نزدیکترین رنگ موجود به رنگ واقعی جایگزین آن شود؛ ولی علاوه بر این با کاهش رنگ‌های موجود می‌توان میزان حافظه لازم برای ذخیره تصاویر را تا حدی کاهش داد. برای این کار تهیه یک جدول که هر عدد دودویی را به رنگ کاهش یافته مورد نظر تناظر دهد لازم است تا نمایشگر بتواند برای نمایش رنگ هر پیکسل تصمیم بگیرد
از سال ۱۹۷۰ روش‌های زیادی برای کاهش رنگ‌های بیت مپ‌ها از جمله و روش‌های بر پایه واریانس ابداع شده که محبوب‌ترین آن‌ها همین روش برش میانی است. کاری که این الگوریتم انجام می‌دهد این است که محدوده‌هایی را برای داده‌ها پیدا می‌کند که داده‌ها در آن‌ها تجمع کرده‌اند و از دیگر نواحی به شکل محسوسی جدا افتاده‌اند.
بعد از این که رنگ‌های پالت مشخص شد کار بعدی متناظر کردن رنگ پیکسل‌های تصویر به آن رنگ هاست. این کار با این ایده انجام می‌شود که فاصله اقلیدسی بین رنگ واقعی و رنگ کاهش یافته کمینه شود. معمولاً برای بهتر شدن تصویر و کاهش خطا در پایان از روش Dithering استفاده می‌شود.
یک راه بسیار ساده برای حل این مسئله تقسیم کردن فضای رنگها به مکعب‌هایی برابر (طول و عرض و ارتفاع دلخواه) است. در این روش، ضرب برداری این سطوح رنگ المان‌های اصلی در پالت نهایی هستند. به‌طور معمول، با تقسیم محور رنگ قرمز به ۸ قسمت برابر، محور سبز به ۸ قسمت برابر و محور رنگ آبی به ۴ سطح رنگی، formula_12 رنگ مختلف معین می‌شود که پس از این مرحله هر رنگ تصویر اصلی به نماینده قسمتی که در آن قرار دارد نگاشت می‌شود. این متد هرجند سرعت خوبی دارد اما کیفیت آن قابل قبول نیست.
ایده اصلی این الگوریتم پیدا کردن و استفاده از formula_13رنگی است که بیشترین استفاده را در تصویر داشته‌اند. به همین خاطر رنگ‌ها در یک هیستوگرام ذحیره می‌شوند. با استخراج محبوب‌ترین رنگ‌ها (رنگ‌ها با بیشترین استفاده)،از آن‌ها بع عنوان رنگ‌های پالت نهایی استفاده می‌شود.
تنها سؤال باقی مانده در این روش چگونگی نگاشت از رنگ‌های اصلی به رنگ‌های کاهیده شده‌است. برای کوچک نگه داشتن خطا، باید برای هر پیکسل باید با تمام رنگ‌های کاهیده شده مقایسه شود تا نزدیک‌ترین آن‌ها به عنوان جانشین مورد استفاده قرار گیرد.
ایده این روش تقسیم تصویر به چند قطعه و پردازش جداگانه هر قسمت است. در حالت بهینه تعداد ‌ها برابر هسته‌های پردازشی در دسترس است. چون کار هر رشته از دیگری جداست، فقط در پایان نتایج با یک دیگر ادغام می‌شوند. این کار چند مرحله دارد:
به دلیل تخصیص وظایف معین به هر رشته، سرعت هر کدام بالا می‌رود و این در کارایی کلی عملیات تأثیر مثبت می‌گزارد. به شکلی که برای تصاویر مختلف به‌طور میانگین ۱٫۵ برابر سرعت را افزایش می‌دهد و این برای تصاویر حجیم بسیار مهم است.