نمایش مبدأ برای برش میانی

برش میانه ای (به [[زبان انگلیسی|انگلیسی]]: median cut) [[الگوریتم|الگوریتمی]] برای یافتن نماینده‌هایی مناسب از یک مجموعه عناصر چند بعدی است که توسط پاول هکبرت (Paul Heckbert) در سال ۱۹۷۹ میلادی ابداع شد. این روش یک [[توابع بازگشتی|الگوریتم بازگشتی]] است و در هر مرحله داده‌ها را به دو دسته حول [[میانه (آمار)|میانه]] بُعد با بزرگ‌ترین دامنه تغییرات تقسیم می‌کند و در پایان برای هر دسته نماینده ای مشخص می‌کند.<ref>{{یادکرد وب|عنوان=An Overview of Color Quantization Techniques|نشانی=https://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQindex.html|وبگاه=web.cs.wpi.edu|بازبینی=2019-04-29}}</ref> برش میانی در حال حاضر پر استفاده‌ترین الگوریتم برای [[گسسته سازی رنگ]] است.

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

معمولاً عناصر مجموعه را به شکل یک بردار در نظر می‌گیرند. در این صورت [[شبه‌کد|شبه کد]] الگوریتم به این شکل خواهد بود:<syntaxhighlight lang="python3">
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)

</syntaxhighlight>
{| class="wikitable"
!مرحله ۰ - نمودار داده‌های دو بعدی
!مرحله ۱ - داده‌ها حول میانه به دو دسته تقسیم شده‌اند
!مرحله ۲ - هر دسته خود به دو دسته دیگر تقسیم شده‌است
|-
|[[پرونده:مرحله ۰.png|جایگزین=نمودار داده‌های دو بعدی|وسط|بندانگشتی]]
|[[پرونده:مرحله ۱.png|جایگزین=داده‌ها حول میانه به دو دسته تقسیم شده‌اند.|وسط|بندانگشتی]]
|[[پرونده:مرحله ۲.png|جایگزین=هر دسته خود به دودسته دیگر تقسیم شده‌است.|وسط|بندانگشتی]]
|}

== تحلیل الگوریتم ==
اگر <math>n</math>داده در فضای <math>m</math>بعدی داشته باشیم، درصورتی که در پیاده‌سازی این الگوریتم از [[مرتب‌سازی هرمی]] (از <math>O(nlog(n))</math>)استفاده کنیم و در هر مرحله برای پیدا کردن مولفه با بیشتربن بازه، کمینه و بیشینه را برای هر مولفه بیابیم (از <math>O(mn)</math>) و ادغام لیست‌ها را در <math>O(n)</math>انجام دهیم، داریم:<math display="block">T(n) = \begin{cases} 1, & \text{if }n\text{ = k} \\ T(n/2) + T(n/2) + n\log(n) + C mn , & \text{if }n>\text{ k} \end{cases}</math>

از [[قضیه اصلی واکاوی الگوریتم‌ها|قضیه اصلی]] واکاوی الگوریتم‌ها داریم که چون: <math display="block">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)</math>

یعنی:<math display="block">T\left(n \right) = \Theta \left( n * ( \log(n) + m \right))</math>(معمولاً <math>n</math>از <math>m</math>بسیار بزرگ‌تر است) در پیاده‌سازی این الگوریتم بازگشتی از [[پشته]] استفاده می‌شود پس بهتر است با توجه به حجم بزرگ داده‌ها، از [[مرتب‌سازی‌های بازگشتی]] صرف نظر کنیم.<ref>{{یادکرد وب|عنوان=SEP94: Median-Cut Color Quantization|نشانی=http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/DDJ/1994/9409/9409e/9409e.htm|وبگاه=collaboration.cmc.ec.gc.ca|بازبینی=2019-04-29|archiveurl=https://web.archive.org/web/20190317171034/http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/DDJ/1994/9409/9409e/9409e.htm|archivedate=۱۷ مارس ۲۰۱۹|dead-url=yes}}</ref>

== [[:en:Color quantization|گسسته سازی رنگ]] ==
با در نظر گرفتن رنگ‌ها به صورت [[RGB]] , عدد هر رنگ یک عدد ۸ بیتی از ۰ تا ۲۵۵ خواهد بود. پس تعداد رنگ‌های ممکن برابر <math>256^3 = 16777216 </math>خواهد بود. اما می‌شود با استفاده از تعداد بسیار کمتری رنگ متفاوت، در بسیاری از تصاویر کیفیت مطلوب را به دست آورد. مسئله پیدا کردن این رنگ‌های [[:en:Palette (computing)|پالت]] نسبتاً کوچک‌تر است. این تعداد بستگی به نوع نمایش دارد ولی در بسیاری از نمایشگرها ۲۵۶ انتخاب می‌شود.
[[پرونده:Color quan.png|جایگزین=|بندانگشتی|267x267پیکسل]]

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

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

بعد از این که رنگ‌های پالت مشخص شد کار بعدی متناظر کردن رنگ پیکسل‌های تصویر به آن رنگ هاست. این کار با این ایده انجام می‌شود که [[فاصله اقلیدسی]] بین رنگ واقعی و رنگ کاهش یافته کمینه شود. معمولاً برای بهتر شدن تصویر و کاهش خطا در پایان از روش Dithering استفاده می‌شود.<ref>{{یادکرد وب|نویسنده=Michael T. Orchard, Member, IEEE, and Charles A. Bouman, Member, ZEEE|کد زبان=en|تاریخ=|وبگاه=|نشانی=https://pdfs.semanticscholar.org/fc50/a3950d6ce54717b945079329069dcd8ccb7a.pdf|عنوان=Color Quantization of Images|بازبینی=2 ژوئن 2019|archive-date=2 ژوئن 2019|archive-url=https://web.archive.org/web/20190602114438/https://pdfs.semanticscholar.org/fc50/a3950d6ce54717b945079329069dcd8ccb7a.pdf}}</ref>

=== دیگر روش ها<ref>{{یادکرد وب|عنوان=Color Quantization Overview|نشانی=http://algolist.manual.ru/graphics/quant/qoverview.php|وبگاه=algolist.manual.ru|بازبینی=2019-06-02}}</ref> ===
==== جدول مراجعه ایستا ====
یک راه بسیار ساده برای حل این مسئله تقسیم کردن فضای رنگها به مکعب‌هایی برابر (طول و عرض و ارتفاع دلخواه) است. در این روش، [[ضرب برداری]] این سطوح رنگ المان‌های اصلی در پالت نهایی هستند. به‌طور معمول، با تقسیم محور رنگ قرمز به ۸ قسمت برابر، محور سبز به ۸ قسمت برابر و محور رنگ آبی به ۴ سطح رنگی، <math display="inline">8 * 8 * 4 = 256</math> رنگ مختلف معین می‌شود که پس از این مرحله هر رنگ تصویر اصلی به نماینده قسمتی که در آن قرار دارد [[نگاشت‌کاهش|نگاشت]] می‌شود. این متد هرجند سرعت خوبی دارد اما کیفیت آن قابل قبول نیست.

==== الگوریتم محبوبیت ====
ایده اصلی این الگوریتم پیدا کردن و استفاده از <math display="inline">K</math>رنگی است که بیشترین استفاده را در تصویر داشته‌اند. به همین خاطر رنگ‌ها در یک [[بافت‌نگار رنگ|هیستوگرام]] ذحیره می‌شوند. با استخراج محبوب‌ترین رنگ‌ها (رنگ‌ها با بیشترین استفاده)،از آن‌ها بع عنوان رنگ‌های پالت نهایی استفاده می‌شود.

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

== پیاده‌سازی همروند ==
ایده این روش تقسیم تصویر به چند قطعه و پردازش جداگانه هر قسمت است. در حالت بهینه تعداد [[:en:Thread (computing)|رشته]]‌ها برابر هسته‌های پردازشی در دسترس است. چون کار هر رشته از دیگری جداست، فقط در پایان نتایج با یک دیگر ادغام می‌شوند. این کار چند مرحله دارد:
# تقسیم وظایف: در ابتدا با توجه به منابع، تعداد وظایف مشخص شده و بر اساس آن تصویر قسمت بندی می‌شود. هر رشته مسئول بخشی از تصویر می‌شود.
# اجرا الگوریتم: سپس هر رشته الگوریتم را بر روی قسمت مربوط به خودش اجرا می‌کند. فقط در پایان عملیات نتایج با هم ادغام می‌شوند.

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

== جستارهای وابسته ==
* [[پیچیدگی زمانی]]
* [[توابع بازگشتی]]
* [[بیت‌مپ|بیت مپ]]
* [[فضای رنگ]]
* [[الگوریتم‌های همروند]]

== منابع ==

{{پانویس}}

[[رده:الگوریتم‌ها]]
[[رده:الگوریتم‌های آماری]]
[[رده:الگوریتم‌های مرتب‌سازی]]
[[رده:فشرده‌سازی تصویر]]