برش میانی

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

الگوریتم

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

معمولاً عناصر مجموعه را به شکل یک بردار در نظر می‌گیرند. در این صورت شبه کد الگوریتم به این شکل خواهد بود:

def median_cut (array, reprsnt_num, step):
    if (2 ^ step>= reprsnt_num or array.length <= 1 ):
        return [average(array)]

    # max_range_dim finds the dimension with max "range"
    idx = max_range_dim(array)

    # sort_by_nth_comp sorts array by comparing nth component in elements
    sorted_array = sort_by_nth_comp(array, idx)

    # merge two arrays
    return median_cut(array[0,int(length(array) / 2) - 1], reprsnt_num, step + 1) +
        median_cut(array[int(length(array) / 2) , length(array) - 1], reprsnt_num, step + 1)

مرحله ۰ - نمودار داده‌های دو بعدی	مرحله ۱ - داده‌ها حول میانه به دو دسته تقسیم شده‌اند	مرحله ۲ - هر دسته خود به دو دسته دیگر تقسیم شده‌است

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

اگر $n$داده در فضای $m$بعدی داشته باشیم، درصورتی که در پیاده‌سازی این الگوریتم از مرتب‌سازی هرمی (از $O(nlog(n))$)استفاده کنیم و در هر مرحله برای پیدا کردن مولفه با بیشتربن بازه، کمینه و بیشینه را برای هر مولفه بیابیم (از $O(mn)$) و ادغام لیست‌ها را در $O(n)$انجام دهیم، داریم:

$$T(n)={\begin{cases}1,&{\text{if }}n{\text{ = k}}\\T(n/2)+T(n/2)+n\log(n)+Cmn,&{\text{if }}n>{\text{ k}}\end{cases}}$$

از قضیه اصلی واکاوی الگوریتم‌ها داریم که چون:

$$f(n)=n\log(n)+mn=\Omega \left(n^{\log _{b}a+\epsilon }\right)=\Omega \left(n\right)\Longrightarrow T\left(n\right)=\Theta \left(f\left(n\right)\right)$$

یعنی:

$$T\left(n\right)=\Theta \left(n*(\log(n)+m\right))$$

(معمولاً $n$از $m$بسیار بزرگ‌تر است) در پیاده‌سازی این الگوریتم بازگشتی از پشته استفاده می‌شود پس بهتر است با توجه به حجم بزرگ داده‌ها، از مرتب‌سازی‌های بازگشتی صرف نظر کنیم.

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

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

مزایا

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

از سال ۱۹۷۰ روش‌های زیادی برای کاهش رنگ‌های بیت مپ‌ها از جمله octree و روش‌های بر پایه واریانس ابداع شده که محبوب‌ترین آن‌ها همین روش برش میانی است. کاری که این الگوریتم انجام می‌دهد این است که محدوده‌هایی را برای داده‌ها پیدا می‌کند که داده‌ها در آن‌ها تجمع کرده‌اند و از دیگر نواحی به شکل محسوسی جدا افتاده‌اند.

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

دیگر روش ها

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

یک راه بسیار ساده برای حل این مسئله تقسیم کردن فضای رنگها به مکعب‌هایی برابر (طول و عرض و ارتفاع دلخواه) است. در این روش، ضرب برداری این سطوح رنگ المان‌های اصلی در پالت نهایی هستند. به‌طور معمول، با تقسیم محور رنگ قرمز به ۸ قسمت برابر، محور سبز به ۸ قسمت برابر و محور رنگ آبی به ۴ سطح رنگی، ${\textstyle 8*8*4=256}$ رنگ مختلف معین می‌شود که پس از این مرحله هر رنگ تصویر اصلی به نماینده قسمتی که در آن قرار دارد نگاشت می‌شود. این متد هرجند سرعت خوبی دارد اما کیفیت آن قابل قبول نیست.

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

ایده اصلی این الگوریتم پیدا کردن و استفاده از ${\textstyle K}$رنگی است که بیشترین استفاده را در تصویر داشته‌اند. به همین خاطر رنگ‌ها در یک هیستوگرام ذحیره می‌شوند. با استخراج محبوب‌ترین رنگ‌ها (رنگ‌ها با بیشترین استفاده)،از آن‌ها بع عنوان رنگ‌های پالت نهایی استفاده می‌شود.

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

پیاده‌سازی همروند

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

1. تقسیم وظایف: در ابتدا با توجه به منابع، تعداد وظایف مشخص شده و بر اساس آن تصویر قسمت بندی می‌شود. هر رشته مسئول بخشی از تصویر می‌شود.
2. اجرا الگوریتم: سپس هر رشته الگوریتم را بر روی قسمت مربوط به خودش اجرا می‌کند. فقط در پایان عملیات نتایج با هم ادغام می‌شوند.

به دلیل تخصیص وظایف معین به هر رشته، سرعت هر کدام بالا می‌رود و این در کارایی کلی عملیات تأثیر مثبت می‌گزارد. به شکلی که برای تصاویر مختلف به‌طور میانگین ۱٫۵ برابر سرعت را افزایش می‌دهد و این برای تصاویر حجیم بسیار مهم است.

جستارهای وابسته

• پیچیدگی زمانی
• توابع بازگشتی
• بیت مپ
• فضای رنگ
• الگوریتم‌های همروند