تحديد كمية اللون

في مجال رسومات الحاسوب ، يُعرف تكميم الألوان أو تكميم صور الألوان بأنه عملية تكميم تُطبق على فضاءات الألوان ؛ وهي عملية تُقلل عدد الألوان المختلفة المستخدمة في الصورة ، وعادةً ما يكون الهدف هو جعل الصورة الجديدة مشابهة بصريًا قدر الإمكان للصورة الأصلية. وقد دُرست خوارزميات الحاسوب لتنفيذ تكميم الألوان على الصور النقطية منذ سبعينيات القرن الماضي. ^{[ 1 ]} يُعد تكميم الألوان أمرًا بالغ الأهمية لعرض الصور متعددة الألوان على الأجهزة التي لا تستطيع عرض سوى عدد محدود من الألوان، عادةً بسبب قيود الذاكرة، كما أنه يُتيح ضغطًا فعالًا لأنواع معينة من الصور.

يُستخدم مصطلح "تكميم الألوان" بشكل أساسي في أدبيات أبحاث رسومات الحاسوب؛ أما في التطبيقات، فتُستخدم مصطلحات مثل " توليد لوحة ألوان مُحسّنة" أو "توليد لوحة ألوان مثالية" أو "تقليل عمق الألوان" . بعض هذه المصطلحات مُضلّل، لأن لوحات الألوان التي تُنتجها الخوارزميات القياسية ليست بالضرورة الأفضل.

تُعالج معظم التقنيات القياسية تكميم الألوان كمشكلة تجميع نقاط في فضاء ثلاثي الأبعاد، حيث تُمثل النقاط الألوان الموجودة في الصورة الأصلية، بينما تُمثل المحاور الثلاثة قنوات الألوان الثلاث. يُمكن تطبيق أي خوارزمية تجميع ثلاثية الأبعاد تقريبًا على تكميم الألوان، والعكس صحيح. بعد تحديد المجموعات، يتم عادةً حساب متوسط ​​النقاط في كل مجموعة للحصول على اللون المُمثل الذي تُمثله جميع الألوان في تلك المجموعة. قنوات الألوان الثلاث هي عادةً الأحمر والأخضر والأزرق ، ولكن يُعد فضاء ألوان Lab خيارًا شائعًا آخر ، حيث تتوافق المسافة الإقليدية فيه بشكل أكبر مع الاختلاف الإدراكي.

تُعدّ خوارزمية القطع الوسيطي الخوارزمية الأكثر شيوعًا على الإطلاق لتكميم الألوان، وقد طوّرها بول هيكبرت في أطروحته الجامعية عام 1980 ونُشرت لاحقًا في بحثٍ علمي عام 1982. ^{[ 2 ]} وتُستخدم العديد من التعديلات على هذه الخوارزمية. قبل ذلك، كان تكميم الألوان يتم في الغالب باستخدام خوارزمية التعداد السكاني ، التي تُنشئ أساسًا مدرجًا تكراريًا لنطاقات متساوية الحجم وتُخصّص ألوانًا للنطاقات التي تحتوي على أكبر عدد من النقاط. ومن الطرق الحديثة والشائعة التجميع باستخدام الأشجار الثمانية ، التي ابتكرها جيرفوتز وبورغاتوفر وحسّنها دان بلومبيرغ ، الباحث في مركز أبحاث زيروكس بارك .

إذا كانت لوحة الألوان ثابتة، كما هو الحال غالبًا في أنظمة تحديد كمية الألوان في الوقت الفعلي مثل تلك المستخدمة في أنظمة التشغيل، فإن تحديد كمية الألوان يتم عادةً باستخدام خوارزمية "مسافة الخط المستقيم" أو "أقرب لون"، والتي ببساطة تأخذ كل لون في الصورة الأصلية وتجد أقرب مدخل في لوحة الألوان، حيث يتم تحديد المسافة من خلال المسافة بين النقطتين المتناظرتين في الفضاء ثلاثي الأبعاد. بعبارة أخرى، إذا كانت الألوان${\displaystyle (r_{1},g_{1},b_{1})}$و${\displaystyle (r_{2},g_{2},b_{2})}$نريد تقليل المسافة الإقليدية إلى الحد الأدنى :

${\displaystyle {\sqrt {(r_{1}-r_{2})^{2}+(g_{1}-g_{2})^{2}+(b_{1}-b_{2})^{2}}}.}$

يُحوّل هذا فعليًا مكعب الألوان إلى مخطط فورونوي ، حيث تمثل عناصر لوحة الألوان النقاط، وتحتوي كل خلية على جميع الألوان المرتبطة بعنصر واحد من عناصر لوحة الألوان. توجد خوارزميات فعّالة من الهندسة الحسابية لحساب مخططات فورونوي وتحديد المنطقة التي تقع فيها نقطة معينة؛ ولكن عمليًا، تكون لوحات الألوان المفهرسة صغيرة جدًا لدرجة أن هذه الخوارزميات غالبًا ما تكون غير ضرورية.

غالبًا ما يُدمج تكميم الألوان مع التمويه اللوني ، مما يُزيل التشوهات غير المرغوب فيها، مثل التدرجات اللونية غير المتجانسة التي تظهر عند تكميم التدرجات اللونية السلسة، ويُعطي انطباعًا بوجود عدد أكبر من الألوان. تحاول بعض الطرق الحديثة لتكميم الألوان دمج اختيار لوحة الألوان مع التمويه اللوني في مرحلة واحدة، بدلًا من تنفيذهما بشكل منفصل.

تم ابتكار عدد من الطرق الأخرى الأقل استخدامًا والتي تعتمد على مناهج مختلفة تمامًا. صُممت خوارزمية التجميع المحلي K-means، التي ابتكرها أوليغ فيريفكا عام 1995، للاستخدام في أنظمة النوافذ حيث يتم تحديد مجموعة أساسية من "الألوان المحجوزة" لاستخدامها من قِبل النظام، ويمكن عرض العديد من الصور ذات أنظمة ألوان مختلفة في وقت واحد. وهي عبارة عن مخطط تجميع لاحق يقوم بتخمين أولي للوحة الألوان ثم يُحسّنها بشكل متكرر.

في بدايات تقنية تكميم الألوان، اعتُبرت خوارزمية التجميع k-means غير مناسبة نظرًا لمتطلباتها الحسابية العالية وحساسيتها للتهيئة. في عام 2011، أعاد إمره سيليبي دراسة أداء خوارزمية k-means كأداة لتكميم الألوان. ^{[ 3 ]} وقد أثبت أن تطبيقًا فعالًا لخوارزمية k-means يتفوق على عدد كبير من طرق تكميم الألوان.

• صورة آدا لوفليس - تمثيل أمين وعدة نسخ تمت معالجتها بواسطة تكميم الألوان k-means.
• 
  إبداعي
• 
  لونان
• 
  5 ألوان
• 
  10 ألوان
• 
  15 لونًا
• 
  100 لون

تُقلل خوارزمية NeuQuant، ذات الجودة العالية ولكنها بطيئة، الصور إلى 256 لونًا من خلال تدريب شبكة عصبية من نوع Kohonen ، والتي تُنظم نفسها ذاتيًا من خلال تعلم مطابقة توزيع الألوان في الصورة المدخلة. ويُعطي تحديد موقع كل عصبون في فضاء RGB خريطة ألوان عالية الجودة تتشابه فيها الألوان المتجاورة. ^{[ 4 ]} وتُعد هذه الخوارزمية مفيدة بشكل خاص للصور ذات التدرجات اللونية.

أخيرًا، من بين الطرق الحديثة، تقنية التكميم اللوني المكاني ، التي ابتكرها بوزيتشا وهيلد وكيتيرير وبومان وفيلنر من جامعة بون ، والتي تجمع بين التمويه اللوني وتوليد لوحة الألوان ونموذج مبسط للإدراك البشري لإنتاج نتائج بصرية مبهرة حتى مع عدد قليل جدًا من الألوان. ولا تتعامل هذه التقنية مع اختيار لوحة الألوان كمسألة تجميع فحسب، إذ تؤثر ألوان البكسلات المجاورة في الصورة الأصلية أيضًا على لون البكسل. انظر الصور النموذجية .

في بدايات الحواسيب الشخصية، كان من الشائع أن تدعم محولات الفيديو لونين أو أربعة أو ستة عشر لونًا فقط، أو (لاحقًا) 256 لونًا، نظرًا لمحدودية ذاكرة الفيديو؛ إذ كان يُفضّل تخصيص ذاكرة الفيديو لزيادة عدد البكسلات (دقة أعلى) بدلًا من زيادة عدد الألوان. وقد ساعد تكميم الألوان في تبرير هذه المقايضة، إذ مكّن من عرض العديد من الصور عالية الألوان في وضعَي 16 و256 لونًا مع تدهور بصري محدود. تقوم العديد من أنظمة التشغيل تلقائيًا بتكميم الألوان وتنعيمها عند عرض صور عالية الألوان في وضع فيديو 256 لونًا، وهو أمر بالغ الأهمية عندما كانت أجهزة الفيديو التي تقتصر على 256 لونًا هي السائدة. أما اليوم، فتستطيع الحواسيب الحديثة عرض ملايين الألوان في آنٍ واحد، وهو عدد يفوق بكثير قدرة العين البشرية على تمييزه، مما يحدّ من استخدام هذه التقنية بشكل أساسي في الأجهزة المحمولة والأجهزة القديمة.

يُستخدم تكميم الألوان حاليًا بشكل أساسي في صور GIF و PNG . يدعم تنسيق GIF، الذي كان لفترة طويلة التنسيق الأكثر شيوعًا للصور النقطية المتحركة وغير المضغوطة على شبكة الإنترنت ، 256 لونًا فقط، مما يستلزم تكميم العديد من الصور. وقد قيّدت بعض متصفحات الويب القديمة الصور باستخدام لوحة ألوان محددة تُعرف بألوان الويب ، مما أدى إلى تدهور كبير في الجودة مقارنةً بلوحات الألوان المُحسّنة. تدعم صور PNG ألوان 24 بت، ولكن يمكن تقليل حجم ملفاتها بشكل كبير دون تدهور ملحوظ في جودة الصورة من خلال تطبيق تكميم الألوان، نظرًا لأن ملفات PNG تستخدم عددًا أقل من البتات لكل بكسل للصور المُكمّمة.

يستحيل عرض العدد الهائل من الألوان المتاحة عبر عدسة الكاميرا على شاشة الحاسوب؛ لذا فإن تحويل أي صورة فوتوغرافية إلى تمثيل رقمي يستلزم بالضرورة نوعًا من التكميم. عمليًا، يُعدّ نظام الألوان ذو 24 بت غنيًا بما يكفي لتمثيل جميع الألوان التي يمكن للعين البشرية إدراكها تقريبًا، مع هامش خطأ ضئيل بما يكفي لضمان تطابقها بصريًا (إذا عُرضت بدقة)، ضمن نطاق الألوان المتاح . مع ذلك، فإن رقمنة اللون، سواء في مستشعر الكاميرا أو على الشاشة، تحدّ بالضرورة من نطاق الألوان المتاح. ونتيجةً لذلك، هناك العديد من الألوان التي قد يستحيل إعادة إنتاجها، بغض النظر عن عدد البتات المستخدمة لتمثيل اللون. على سبيل المثال، يستحيل في أنظمة ألوان RGB التقليدية (الشائعة في شاشات الحاسوب) إعادة إنتاج النطاق الكامل لدرجات اللون الأخضر التي تستطيع العين البشرية إدراكها.

نظراً لقلة الألوان المتاحة في الحواسيب القديمة، أنتجت خوارزميات التكميم المختلفة صوراً متباينة المظهر. ونتيجة لذلك، تم تخصيص وقت طويل لكتابة خوارزميات متطورة لجعل الصور أكثر واقعية.

• اللون المفهرس
• لوحة (الحوسبة)
• قائمة لوحات البرامج - قسم اللوحات التكيفية .
• التردد
• التكميم (معالجة الصور)
• تجزئة الصور

• بول إس. هيكبرت. تكميم الصور الملونة لعرضها في مخزن الإطارات . وقائع مؤتمر ACM SIGGRAPH '82. أول منشور لخوارزمية القطع الوسيط.
• دان بلومبيرغ. تكميم الألوان باستخدام الأشجار الثمانية . ليبتونيكا.
• أوليغ فيريفكا. تكميم الصور الملونة في أنظمة ويندوز باستخدام خوارزمية K-means المحلية . وقائع ندوة رسومات الحاسوب الغربية لعام 1995.
• ج. بوزيتشا، م. هيلد، ج. كيتيرر، ج. م. بومان، و د. فيلنر. حول التكميم المكاني للصور الملونة . ( النص الكامل بصيغة ps.gz ) تقرير فني IAI-TR-98-1، جامعة بون. 1998.