خوارزمية Bi-level Thresholding

توظف هذه الخوارزمية في الصور التي لها منحني إحصائي ذو نسقين (bimodal histograms).

في خوارزمية Bi-level Thresholding يكون الهدف والأرضية (الخلفية) من مجموعتين مختلفتين بتدرج رمادي واضح المعالم.

فمثلاً: تكون رموز الأحرف والأرقام في كتاب ما عادة أغمق من الخلفية (الورق الأبيض). في هذه الحالة تكون الأشكال ذات منحني إحصائي ذو نسقين (bimodal histograms) بقمم (ذرى) متناسقة مع مناطق الهدف والخلفية بالإضافة لوديان فيما بين تلك القمم.

عادةً ما يتم اختيار نقطة الوادي (أدنى قيمة في المنحني الإحصائي) كعتبة T (Threshold)، في المنحني الإحصائي ذو النسقين (bimodal histograms) فإن  جميع قيم اللون الرمادي التي تكون أكبر من العتبة T  (Threshold) تعيّن لرقعة الهدف، وجميع قيم اللون الرمادي الباقية تعيّن لرقعة الخلفية، وهكذا يتم فصل نقاط الهدف عن نقاط الخلفية.

يظهر الشكل (3) صورة ذات نسقين (bimodal) مع خرج الصورة وفق خوارزمية Thresholding.

شكل (3)

Thresholding هي عملية تحويل لصورة الدخل A إلى صورة الخرج المقطعة B كالتالي:

حيث أن  لنقاط الهدف و لنقاط الخلفية.

تمثّل الخطوات التالية المبسطة والتكرارية آلية عمل خوارزمية Bi-level Thresholding لاختيار العتبة لصورة ذات نسقين:

خوارزمية Median cut

^([1])

هي إحدى خوارزميات ترتيب وتصنيف البيانات، لعدد غير محدد من الأبعاد إلى سلسلة من المجموعات وذلك بتقطيع كل مجموعة من البيانات إلى نقطة (قيمة) متوسطة.

ولكن خوارزمية Median cut عادةً ما تستخدم لتكميم الصور، مثلاً لتحويل ألوان صورة ما بعمق 64k لون إلى 256 لون، حيث تقوم خوارزمية Median cut بإيجاد 256 لون التي تكون أكثر ما يمكن مطابقة للألوان الأصلية.

تقوم خوارزمية ^([2]) Median cut بتقسيم فضاء الألوان بشكل تبادلي إلى صناديق أصغر وأصغر ولك بالاعتماد على توزيع الألوان للصورة الأصلية.

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

تكرر الخطوة السابقة (تقسيم الصندوق لصناديق أصغر) حتى يتم توليد K صندوق، حيث أن K هو العدد الأعظمي للألوان المدخلة في خريطة الألوان المتاحة (مثلاً 256 لون).

بعد ذلك يتم إيجاد الألوان المناسبة بأخذ متوسط قيم الألوان الموجودة في كل صندوق، كما في الشكل (2).

الشكل (2): مثال لإنقاص ألوان صورة باستخدام خوارزمية  Median cut

---

([1]) من موقع: http://en.wikipedia.org/wiki/Median_cut

([2]) من كتاب: Encyclopedia of Multimedia, By Borko Furht, Page: 417-418

خوارزمية Octree Algorithm

خوارزمية  Octree Algorithm هي إحدى خوارزميات تكميم الألوان

Color Quantization Algorithms

[1]

وهي بنية شجرة معطيات حيث أن كل عقدة داخلية فيها تحتوي على 8 (عقد أولاد)، وغالبا ما تستخدم في تقسيم الأبعاد الثلاثة للفراغ إلى 8 أثمان بشكل متكرر كما في الشكل (1):

شكل (1)

تطبيقات Octree في تكميم الألوان:

تم تقديم خوارزمية تكميم الألوان octree color quantization من قبل Gervautz and Purgathofer في العام 1988.

حيث تم ترميز بيانات ألوان الصورة بعمق 9 مستويات. وقد تم استخدام Octree لأن 23 = 8 ، حيث أنه توجد ثلاثة ألوان في نظام RGB.

تعتبر هذه الخوارزمية ذات ذاكرة عالية الكفاءة. المستوى السفلي من Octree يتألف من (عقد أوراق) ينتج بيانات لون غير ممثلة في الشجرة؛ هذه العقد بشكل مبدئي تحتوي على Bit بت واحد.

إذا تم إدخال أكثر من العدد المطلوب لألوان الـ Palette في شجرة Octree ، فإن حجمها يمكن أن يتناقص باستمرار بالانتقال إلى العقد ذات المستوى السفلي وأخذ المتوسط لبياناتها حتى تصل لعقدة الورقة، يتم تقليم جزء من الشجرة.

حالما تنتهي عملية أخذ العينات Sampling، يتم استعراض جميع المسارات في الشجرة من الأعلى وحتى عقد الأوراق، مع ملاحظة البتات Bits على طول المسار، سوف يثمر عن عدد الألوان المطلوب بشكل تقريبي.

---

([1]) من موقع: http://en.wikipedia.org/wiki/Octree