السلام عليكم،
 
أبحث عن خوارزمية أو مكتبة برمجية لمقاربة الألوان. لنفرض أن لدي صورة بها 30,000 بكسل، وأريد أن أحصل على الـ 64 لون الأهم من هذه الصورة، حيث "الأهم" هو اللون الذي يتكرر كثيراً أو الذي يعتبر فريداً بين بقية الألوان في الصورة.
 
بعبارة أخرى شيء مطابق لما يفعله برنامج فوتوشوب عندما تحول صورة من المجال اللوني الكامل (RGB) لتصبح معنونة بعدد محدود من الألوان (Indexed).
 
هل من أفكار أو روابط إنترنت لحل هذه المسألة؟

الأمر بسيط. ما تقوم به هو:
1. بناء Histogram للألوان (كل لون و عدد مرات حدوثه)
2. بناء شجرة من هذا الجدول وذلك بقسمه إلى قسمين يميني ويساري بحيث يكون مجموع عدد مرات الحدوث لجميع الألوان في القسم اليميني مساوياً (أو شبه مساوٍ) لمجموعها في القسم اليساري.
3. إعادة العملية السابقة عدد كافياً من المرات حتى تحصل على أوراق في الشجرة مساوية لعدد الألوان المطلوبة (أي تعيد التقسيم 6 مرات إذا أردت 64
لون)
4. هنا لديك خياران. أخذ المتوسط الحسابي (average) أو الوسيط (median) لكل ورقة في الشجرة وهذا يكون اللون المطلوب

بقي أن تعرف اللون المقابل لكل لون في الصورة الأصلية. هنا أيضاً طريقتين
الأولى الأسرع هي بأخذ اللون المختار في نفس الورقة
الثانية الأبطأ والأدق هي أخذ اللون ذي المسافة الديكارتية الأصغر عن اللون الأصلي

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

إن كان لديك أي سؤال فلا تتردد

فكرت بهذه الطريقة، لكنها تظلم الألوان الشاذة. فلو كان لدي عدد كبير من الألوان المتشابهة (أزرق داكن مثلاً) ولون واحد مختلف (أبيض ناصع) فإن اللون الأبيض سيذهب هباء لو اعتمدت على عدد مرات التكرار فقط في التقسيم.
 
كنت أفكر باستخدام شجرة عديدة الأبعاد (kd-tree) لتجزئة الألوان اعتماداً على ابتعاداتها الفراغية عن بعضها البعض. بهذا الشكل ستتعنقد الألوان المتشابهة في مجموعات تحت أفرع واحدة، وستظل الفرصة متاحة للألوان الشاذة لأن تحصل على مدخل في القائمة النهائية.
 
بعد أن أصل لعمق معين في الشجرة، يتم انتقاء القيم اللونية النهائية عن طريق أخذ مركز كل خلية انتهائية في الشجرة، وإيجاد أقرب لون لهذا المركز من مجموعة الألوان في الخلية. هذه الطريقة صالحة أو المتوسط الحسابي أو الوسيط. كل منها له نتيجة قد تكون مناسبة أو قد لا تكون...
 
لقد حصلت الآن على نسخة من كود برنامج جيمب (GIMP) والذي يشابه فوتوشوب تقريباً، وذلك للاطلاع على الكود الخاص بتحويل الصور إلى 256 لون. قد تكون طريقته مفيدة، وإن كانت خيارات التحويل في جيمب أقل منها في فوتوشوب.

حسناً لقد انتهيت من قراءة كود التحويل في جيمب، وهو يطبق خوارزمية قريبة مما كنا نتحدث عنه، لكن مع بعض التفاصيل المختلفة. فهو يقوم بالآتي:
 
1- تحويل الألوان إلى النظام اللوني LAB (إضاءة، طيف لوني أول، طيف لوني ثاني). أعجبتني هذه العملية، فهي تعطي جودة أعلى من العمل في نظام إحداثيات RGB الاعتيادي.
 
2- بناء المدرج الإحصائي (histogram) لكافة الألوان في الصورة وحفظه في مصفوفة ثلاثية الأبعاد. للتخفيف من حجم الذاكرة المطلوبة هو يعطي ثمان بتات لقناة الإضاءة وست بتات فقط للقنوات اللونية، لذلك فإن مجال العمل هو مليون لون فقط بدلاً من 16 مليوناً.
 
3- تقسيم المدرج اللوني بطريقة مشابهة للشجرة الثمانية (octree)، حيث يقوم بإنشاء صندوق محيط بكل الألوان ويقسمه بمستوي متعامد مع أحد المحاور. هناك حيلة صغيرة لانتقاء أي الصناديق يتم الاستمرار في تقسيمها (معتمداً على مقدار الخطأ بين الألوان ومعدل الألوان في الصندوق).
 
4- يستمر التقسيم حتى يصبح عدد الصناديق مساوياً لعدد الألوان المطلوبة، ومن ثم ينتقي لوناً من كل صندوق باستخدام الوسيط (median).
 
الطريقة العامة وردت في كتاب Graphics Gems 2. لقد أرفقت مع هذه المشاركة ملفي الكود اللذان يحويان تعريفات إجراءات التحويل ومتعلقاتها لمن يحب أن يطلع عليها دون أن يضيع وقته في البحث بين ما يربو عن الـ 5500 ملف كود ☺ .
 
الكود مكتوب بلغة سي البحتة، وهو منظم بشكل جميل (على غير عادة المشاريع المفتوحة المصدر 😄 ).