نام (NAME)

quantize - الگوریتم کاهش رنگ ImageMagick

خلاصه دستور (SYNOPSIS)

#include <magick.h>

توضیحات (DESCRIPTION)

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

برای اهداف تخصیص رنگ، یک تصویر مجموعه‌ای از n پیکسل است که در آن هر پیکسل نقطه‌ای در فضای RGB محسوب می‌شود. فضای RGB یک فضای برداری ۳ بعدی است و هر پیکسل، pi، با یک سه‌تایی مرتب از مختصات قرمز، سبز و آبی تعریف می‌شود: (ri, gi, bi).

هر مؤلفه رنگ اصلی (قرمز، سبز یا آبی) بیانگر شدتی است که به صورت خطی از ۰ تا یک مقدار بیشینه، cmax، تغییر می‌کند که متناظر با اشباع کامل آن رنگ است. تخصیص رنگ روی دامنه‌ای شامل یک مکعب در فضای RGB با رأس‌های متقابل در (0,0,0) و (cmax,cmax,cmax) تعریف می‌شود. ImageMagick به مقدار cmax = 255 نیاز دارد.

این الگوریتم، دامنه مذکور را روی درختی نگاشت می‌کند که در آن هر گره نشان‌دهنده یک مکعب درون آن دامنه است. در ادامه بحث، این مکعب‌ها با مختصات دو رأس متقابل تعریف می‌شوند: رأسی که به مبدأ در فضای RGB نزدیک‌تر است و رأسی که دورترین فاصله را از مبدأ دارد.

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

الگوریتم پایه در سه فاز عمل می‌کند: دسته‌بندی (Classification)، کاهش (Reduction)، و تخصیص (Assignment). فاز دسته‌بندی یک درخت توصیف رنگ برای تصویر می‌سازد. فاز کاهش درخت را تا جایی جمع می‌کند که تعداد رنگ‌هایی که نشان می‌دهد حداکثر برابر با تعداد رنگ‌های مورد نظر در تصویر خروجی باشد. فاز تخصیص نقشه رنگ تصویر خروجی را تعریف کرده و رنگ هر پیکسل را با دسته‌بندی مجدد در درخت کاهش‌یافته تعیین می‌کند. هدف ما به حداقل رساندن اختلاف عددی میان رنگ‌های اصلی و رنگ‌های کوانتیزه‌شده است. برای اطلاعات بیشتر درباره خطای کوانتیزاسیون، بخش «اندازه‌گیری خطای کاهش رنگ» را در ادامه این سند ببینید.

فاز دسته‌بندی با مقداردهی اولیه یک درخت توصیف رنگ با عمق کافی برای نمایش هر رنگ ورودی ممکن در یک برگ آغاز می‌شود. با این حال، تولید یک درخت توصیف رنگ کامل در فاز دسته‌بندی برای مقادیر واقعی cmax غیرعملی است. اگر مؤلفه‌های رنگ در تصویر ورودی با دقت k-بیتی کوانتیزه شوند، به طوری که cmax = 2k-1 باشد، درخت برای اینکه بتواند هر رنگ ورودی ممکن را در یک برگ نمایش دهد، به k سطح زیر گره ریشه نیاز خواهد داشت. این حالت غیرعملی است زیرا تعداد کل گره‌های درخت برابر است با:

Σ ki=1 8k

یک درخت کامل برای k = 8, cmax = 255 به ۱۹,۱۷۳,۹۶۱ گره نیاز دارد. بنابراین، برای جلوگیری از ساخت یک درخت کامل و پرجمعیت، ImageMagick: (۱) ساختارهای داده برای گره‌ها را تنها در صورت نیاز مقداردهی اولیه می‌کند؛ (۲) یک بیشینه عمق برای درخت به عنوان تابعی از تعداد رنگ‌های مطلوب در تصویر خروجی انتخاب می‌کند (در حال حاضر log4(colormap size)+2). درختی با این عمق عموماً بهترین نمایش از تصویر مبدأ را با بیشترین سرعت محاسباتی و کمترین میزان حافظه فراهم می‌آورد. با این حال، عمق پیش‌فرض برای برخی تصاویر نامناسب است. بنابراین فراخواننده می‌تواند عمق مشخصی از درخت را درخواست کند.

برای هر پیکسل در تصویر ورودی، دسته‌بندی از ریشه درخت توصیف رنگ به سمت پایین پیمایش می‌کند. در هر سطح از درخت، گره یکتایی را شناسایی می‌کند که نشان‌دهنده یک مکعب در فضای RGB حاوی رنگ آن پیکسل است. این فاز داده‌های زیر را برای هر یک از این گره‌ها به‌روزرسانی می‌کند:

n1:: تعداد پیکسل‌هایی که رنگ آن‌ها در مکعب RGB نشان‌داده‌شده توسط این گره قرار دارد؛
n2:: تعداد پیکسل‌هایی که رنگ آن‌ها در گره‌ای در عمق پایین‌تر درخت نشان داده نشده است؛ در ابتدا، برای تمام گره‌ها به جز برگ‌های درخت مقدار n2 = 0 است.
Sr, Sg, Sb:: مجموع مقادیر مؤلفه‌های قرمز، سبز و آبی برای تمام پیکسل‌هایی که در عمق پایین‌تر دسته‌بندی نشده‌اند. ترکیب این مجموع‌ها و n2 در نهایت رنگ میانگین مجموعه‌ای از پیکسل‌های ارائه‌شده توسط این گره را مشخص خواهد کرد.
E:: مجذور فاصله در فضای RGB بین هر پیکسل درون یک گره و مرکز آن گره. این مقدار نشان‌دهنده خطای کوانتیزاسیون برای یک گره است.

فاز کاهش به صورت مکرر درخت را هرس می‌کند تا زمانی که تعداد گره‌های با n2 > 0 کمتر یا مساوی با حداکثر تعداد رنگ‌های مجاز در تصویر خروجی باشد. در هر تکرار روی درخت، گره‌هایی را که مقدار E آن‌ها کمینه است برای هرس انتخاب کرده و آمار رنگ آن‌ها را به سمت بالا ادغام می‌کند. این فاز از یک آستانه هرس، Ep، برای هدایت انتخاب گره‌ها به صورت زیر استفاده می‌کند:

Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
    prune all nodes such that E <= Ep
    Set Ep  to minimum E in remaining nodes

این عمل خطای کوانتیزاسیون را هنگام ادغام دو گره به حداقل می‌رساند.

هنگامی که گره مورد نظر برای هرس دارای فرزند باشد، روند هرس خود را به صورت بازگشتی فرا می‌خواند تا درخت را از برگ‌ها به سمت بالا هرس کند. مقادیر n2 Sr, Sg, و Sb در گره‌ای که هرس می‌شود همیشه به داده‌های متناظر در والد آن گره اضافه می‌شوند. این کار مشخصه‌های رنگ گره هرس‌شده را برای میانگین‌گیری‌های بعدی حفظ می‌کند.

برای هر گره، n2 پیکسل وجود دارند که آن گره نشان‌دهنده کوچک‌ترین حجم در فضای RGB حاوی رنگ‌های آن پیکسل‌ها است. هنگامی که n2 > 0 باشد، این گره به صورت یکتا رنگی را در تصویر خروجی تعریف خواهد کرد. در ابتدای فاز کاهش، مقدار n2 = 0 برای تمام گره‌ها به جز برگ‌های درخت است که رنگ‌های موجود در تصویر ورودی را نشان می‌دهند.

شمارنده دیگر پیکسل‌ها، n1، نشان‌دهنده تعداد کل رنگ‌ها درون حجم مکعبی است که گره نشان می‌دهد. این شامل n1 - n2 پیکسل است که رنگ آن‌ها باید توسط گره‌ها در سطح پایین‌تری از درخت تعریف شود.

فاز تخصیص تصویر خروجی را از درخت هرس‌شده تولید می‌کند. تصویر خروجی از دو بخش تشکیل شده است: (۱) یک نقشه رنگ، که آرایه‌ای از توصیف‌های رنگ (سه‌تایی‌های RGB) برای هر رنگ موجود در تصویر خروجی است؛ (۲) یک آرایه پیکسل، که هر پیکسل را به عنوان یک اندیس در آرایه نقشه رنگ نشان می‌دهد.

نخست، فاز تخصیص یک بار از روی درخت توصیف رنگ هرس‌شده عبور می‌کند تا نقشه رنگ تصویر را ایجاد کند. برای هر گره با n2 > 0، مقادیر Sr، Sg و Sb را بر n2 تقسیم می‌کند. این عمل رنگ میانگین تمام پیکسل‌هایی را که در سطحی پایین‌تر از این گره دسته‌بندی نشده‌اند تولید می‌کند. هر یک از این رنگ‌ها به یک مدخل در نقشه رنگ تبدیل می‌شوند.

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

شواهد تجربی نشان می‌دهد که فواصل در فضاهای رنگی مانند YUV یا YIQ نسبت به فواصل در فضای RGB، تطابق نزدیک‌تری با تفاوت‌های ادراکی رنگ دارند. این فضاهای رنگ ممکن است هنگام کاهش رنگ تصویر نتایج بهتری ارائه دهند. در اینجا الگوریتم همان‌طور که شرح داده شد عمل می‌کند، با این تفاوت که هر پیکسل نقطه‌ای در فضای رنگ جایگزین است. برای سهولت، مؤلفه‌های رنگ به بازه ۰ تا یک مقدار بیشینه، cmax، نرمال‌سازی می‌شوند. سپس فرآیند کاهش رنگ می‌تواند طبق توضیحات ادامه یابد.

اندازه‌گیری خطای کاهش رنگ (MEASURING COLOR REDUCTION ERROR)

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

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

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

این خطاها در صورتی که -verbose و -colors در خط فرمان مشخص شده باشند، اندازه‌گیری و چاپ می‌شوند:

mean error per pixel:: میانگین خطا برای هر پیکسل منفرد در تصویر است.
normalized mean square error:: میانگین مجذور خطای کوانتیزاسیون نرمال‌شده برای هر پیکسل منفرد در تصویر است.

این معیار فاصله به محدوده‌ای بین ۰ و ۱ نرمال‌سازی شده است و مستقل از محدوده مقادیر قرمز، سبز و آبی در تصویر است.

normalized maximum square error:: بزرگ‌ترین مجذور خطای کوانتیزاسیون نرمال‌شده برای هر پیکسل منفرد در تصویر است.

این معیار فاصله به محدوده‌ای بین ۰ و ۱ نرمال‌سازی شده است و مستقل از محدوده مقادیر قرمز، سبز و آبی در تصویر است.

همچنین ببینید (SEE ALSO)

display(1), animate(1), mogrify(1), import(1), miff(5)

حق نشر (COPYRIGHT)

حق نشر (C) سال 2002 ImageMagick Studio، سازمانی غیرانتفاعی اختصاص‌یافته به ارائه رایگان راهکارهای نرم‌افزاری پردازش تصویر.

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

اطلاعیه حق نشر فوق و این مجوزنامه باید در تمامی نسخه‌ها یا بخش‌های عمده ImageMagick درج شود.

این نرم‌افزار «همان‌طور که هست» ارائه می‌شود، بدون هیچ‌گونه ضمانت صریح یا ضمنی، از جمله اما نه محدود به ضمانت‌های قابلیت تجاری، مناسب بودن برای یک هدف خاص و عدم نقض حق. در هیچ شرایطی ImageMagick Studio در قبال هرگونه ادعا، خسارت یا مسئولیت دیگر، اعم از اقدام قراردادی، شبه‌جرم یا موارد دیگر که ناشی از، مرتبط با یا در پیوند با ImageMagick یا استفاده یا سایر معاملات در ImageMagick باشد، مسئولیتی نخواهد داشت.

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

قدردانی‌ها (ACKNOWLEDGEMENTS)

پل راولینگ (Paul Raveling)، از مؤسسه علوم اطلاعات دانشگاه کالیفرنیای جنوبی (USC Information Sciences Institute)، برای ایده اولیه استفاده از تقسیم‌بندی فضا در الگوریتم کاهش رنگ. با اجازه پل، این سند اقتباسی از سندی است که او نوشته است.

نویسندگان (AUTHORS)

جان کریستی (John Cristy)، استودیوی ImageMagick (ImageMagick Studio)