Varyans Tabanlı Renk Nicemleme

Bir görüntüyü daha küçük bir dosyaya dönüştürmek ile görüntünün renk uzayını daha az sayıda temsilci renkle yeniden modellemek aynı işlem değildir. İlkinde kodlayıcının bit akışını sıkıştırma başarısı öne çıkar. İkincisinde ise milyonlarca olası rengin sınırlı bir palete hangi kayıpla indirgeneceği belirlenir. İncelediğim kütüphane bu iki problemi tek işlem hattında birleştirir. Önce RGBA renk uzayında istatistiksel bir nicemleme yapar, ardından elde edilen indeksli görüntüyü yeniden kodlayarak dosya boyutunun küçülüp küçülmediğini sınar.

Bu kütüphaneyi üretken yapay zeka destekli kodlama araçlarının yaygınlaşmasından önce, görüntü işleme alanındaki bilinen nicemleme ve palet optimizasyonu yaklaşımlarını inceleyerek geliştirdim. Çalışmanın kuramsal arka planı, daha sonra Nobel Akademik Yayıncılık tarafından yayımlanan Yapay Zeka Kuramdan Uygulamaya kitabında tarafımdan yazılan "Görüntü ve Ses İşleme" bölümüyle aynı teknik çizgide yer alır. Kitabın ilgili bölümünde görüntünün sayısal gösteriminden öznitelik vektörlerine, iyileştirme ve bölütlemeden yapay zeka tabanlı görüntü analizine kadar uzanan bir yapı kurmuştum. Bu kütüphane, orada ele aldığım kuramdan uygulamaya geçişin düşük seviyeli ve ölçülebilir örneklerinden biridir.

Kodun çekirdeğinde sinir ağı bulunmaz. Buna rağmen yapılan işlem yapay zeka ve örüntü tanıma açısından anlamlıdır. Her piksel dört boyutlu bir özellik vektörü olarak ele alınır, gözlenen renk dağılımı kümelere ayrılır ve her küme bir merkez renkle temsil edilir. Bu yapı, klasik istatistiksel öğrenme ve vektör nicemleme yaklaşımıdır. Algoritmanın açıklanabilir olması, her kararın momentler, varyans ve uzaklık üzerinden izlenebilmesini sağlar.

Renk nicemleme problemi

32 bitlik bir RGBA görüntüde her piksel dört adet 8 bitlik bileşen taşır:

• Alfa
• Kırmızı
• Yeşil
• Mavi

Kuramsal renk uzayı yaklaşık 4,29 milyar farklı RGBA bileşimine izin verir. İndeksli bir görüntüde ise piksel doğrudan renk değerini değil, bir palet girişinin numarasını taşır. PNG biçimi indeksli görüntüler için 1, 2, 4 ve 8 bitlik indisleri destekler. Böylece bir görüntü en fazla 2, 4, 16 veya 256 palet rengiyle gösterilebilir. İncelediğim gerçeklenim, çıktı için 1, 4 ve 8 bitlik biçimleri kullanır.

Nicemleme fonksiyonu genel olarak şöyle gösterilebilir:

[
Q: \mathbb{R}^{4} \rightarrow {c_0,c_1,\ldots,c_{K-1}}
]

Burada her piksel, RGBA uzayındaki en uygun temsilci renge eşlenir. Amaç palet büyüklüğü "K" ile yeniden oluşturma hatası arasında denge kurmaktır.

Basit bir yaklaşım her kanalın düşük bitlerini silerek renk sayısını azaltabilir. Bu yöntem hızlıdır ancak görüntünün gerçek renk dağılımını dikkate almaz. Median cut, renk uzayındaki kutuları nüfus veya eksen uzunluğuna göre böler. K-means ise pikselleri merkezlere atayıp merkezleri yinelemeli olarak günceller. İncelenen kodun asıl omurgası ise Xiaolin Wu'nun varyans azaltmaya dayalı renk nicemleme yaklaşımıyla belirgin biçimde örtüşür.

Wu'nun yöntemi RGB görüntüsünü üç boyutlu bir yoğunluk dağılımı olarak ele alır. Renk uzayını eksenlere paralel kutulara ayırır ve bölünmeleri küme içi varyansı azaltacak biçimde seçer. Yöntemin temel üstünlüğü, renk bölgelerine ilişkin istatistikleri önceden hesaplayıp olası kesimleri hızlı biçimde değerlendirmesidir.

Geliştirdiğim gerçeklenim bu fikri üç boyutlu RGB uzayında bırakmaz. Alfa kanalını da bağımsız bir boyut olarak modele katar. Böylece kutular şu dört eksende tanımlanır:

[
C=[A_0,A_1]\times[R_0,R_1]\times[G_0,G_1]\times[B_0,B_1]
]

Bu genişletme, yarı saydam piksellerin yalnız RGB bileşenlerine göre aynı kümeye alınmasını önleyebilir. Bunun karşılığında moment uzayının bellek maliyeti önemli ölçüde büyür.

Beş bitlik histogram ve renk momentleri

Tam RGBA uzayında doğrudan dört boyutlu histogram oluşturmak pratik değildir. Her kanal 256 değer taşıdığı için hücre sayısı:

[ 256^4 ]

olurdu. Kaynak kod her kanalı üç bit sağa kaydırarak 8 bitten 5 bite indirger. Böylece her eksen 32 etkin bölmeye ayrılır. Sınır hesaplarını kolaylaştıran sıfır katmanı da eklendiğinde her boyutun uzunluğu 33 olur:

[ B=33 ]

Dört boyutlu toplam hücre sayısı:

[ 33^4=1.185.921 ]

değerine düşer. Bu sayı halen büyüktür ancak sabittir ve güncel masaüstü sistemlerde yönetilebilir.

Her histogram hücresinde yalnız piksel sayısı tutulmaz. Aşağıdaki yeterli istatistikler biriktirilir:

[ w=\sum 1 ]

[
s_A=\sum A,\quad
s_R=\sum R,\quad
s_G=\sum G,\quad
s_B=\sum B
]

[
q=\sum(A^2+R^2+G^2+B^2)
]

Burada "w" hücredeki piksel ağırlığını, "s" değerleri kanal toplamlarını, "q" ise ikinci momenti temsil eder.

Belirli bir renk kutusunun ortalama rengi şu şekilde bulunur:

[
\mu_C=
\left(
\frac{s_A}{w},
\frac{s_R}{w},
\frac{s_G}{w},
\frac{s_B}{w}
\right)
]

Aynı kutunun toplam karesel hatası veya varyans ölçüsü ise kaynak koddaki hesapla şu ilişkiye karşılık gelir:

[
V(C)=q-\frac{s_A^2+s_R^2+s_G^2+s_B^2}{w}
]

Bu ifade, kutudaki piksellerin ortalama renkten olan karesel uzaklıklarının toplamıdır. Bir kutunun varyansı yüksekse, aynı palet rengiyle temsil edilmesi daha fazla hata üretir. Bu nedenle sonraki bölünme için yüksek varyanslı kutuların seçilmesi anlamlıdır.

Kısmi saydamlık için ayrıca bir eşik uygulanır. Alfa değeri çok düşük pikseller histogram dışında bırakılır ve şeffaf renk için ayrı bir indeks ayrılır. Orta alfa değerlerinde kullanılan ek düzeltme ise bir sıkıştırma sezgisidir. Bununla birlikte mod işlemine dayanan bu eşleme monoton değildir. Birbirine çok yakın iki alfa değeri, geçiş noktalarında farklı ve uzak histogram hücrelerine düşebilir. Üretim sürümünde alfa nicemlemesinin monoton bir aktarım fonksiyonuyla yapılması daha kararlı sonuç verir.

Dört boyutlu integral histogram

Yöntemin esas algoritmik gücü, histogram oluşturulduktan sonra dört boyutlu kümülatif momentlerin hesaplanmasıdır. Görüntü işlemede integral görüntü olarak bilinen yaklaşımın renk uzayına uygulanmış biçimi düşünülebilir.

Her hücre, kendisinden önce gelen bütün alfa, kırmızı, yeşil ve mavi hücrelerinin toplamını taşır. Bu ön hesaplamadan sonra herhangi bir dört boyutlu dikdörtgen bölgenin momentleri, bölge içindeki bütün hücreleri dolaşmadan elde edilir.

Dört boyutlu bir kutunun hacmi inclusion-exclusion ilkesiyle 16 köşe değeri kullanılarak hesaplanır. Boyut sayısı "D" olduğunda gereken köşe sayısı:

[ 2^D ]

olduğundan, dört boyutta 16 sabit erişim yeterlidir.

Bu tercih, pahalı hesaplamayı bir kez yapılan moment oluşturma aşamasına taşır. Sonraki yüzlerce kesme adayında kutu ağırlığı, kanal toplamları ve ikinci moment sabit zamanda bulunabilir.

"N" piksel sayısını gösterdiğinde histogram oluşturma maliyeti:

[
\Theta(N)
]

olur. Kümülatif moment tablosunun maliyeti ise:

[
\Theta(B^4)
]

değerindedir. "B=33" sabit tutulduğu için bu maliyet görüntü çözünürlüğünden bağımsızdır. Büyük görüntülerde piksel taraması baskın hale gelir. Çok küçük görüntülerde ise sabit moment tablosunun hazırlanması görece pahalı olabilir.

Moment yapısının ham boyutu yaklaşık 40 bayttır. Dört boyutlu tablonun yalnız moment verisi:

[ 1.185.921\times40 ]

hesabıyla yaklaşık 45,2 MiB yer kaplar. Bitmap, akış ve satır tamponları bu değere dahil değildir. Üç boyutlu Wu histogramıyla karşılaştırıldığında alfa boyutunun eklenmesi hücre sayısını 33 kat artırır. Bu, kaliteden önce verilmiş bilinçli bir bellek karşılığıdır.

Varyansla yönlendirilen kutu bölme

Başlangıçta bütün renk uzayını kapsayan tek bir kutu bulunur. Her adımda bu kutulardan biri iki parçaya ayrılır. Kesme için dört eksenin tamamı ayrı ayrı değerlendirilir.

Belirli bir kesme noktası kutuyu "C_1" ve "C_2" olarak ikiye ayırsın. Kod şu değeri büyütmeye çalışır:

[
J=
\frac{|s_1|^2}{w_1}
+
\frac{|s_2|^2}{w_2}
]

Toplam ikinci moment sabit olduğu için bu ifadeyi büyütmek, iki alt kutunun toplam küme içi varyansını küçültmeye eşdeğerdir:

[
V(C_1)+V(C_2)
]

Alfa, kırmızı, yeşil ve mavi eksenlerinde bulunan en iyi kesimler karşılaştırılır. En yüksek kazancı veren eksen ve konum seçilir. Bölünmeden sonra iki yeni kutunun varyansı yeniden hesaplanır.

Sonraki adımda rastgele bir kutu değil, mevcut kutular arasında en yüksek varyansa sahip olan bölünür. Bu açgözlü strateji, palet renklerini görüntünün renk dağılımına göre yoğunlaştırır. Düz renkli bölgeler az sayıda kutuyla temsil edilirken renk geçişi veya doku içeren bölgeler daha fazla kutu alır.

İşlem, istenen palet büyüklüğüne ulaşılana veya hiçbir kutu daha fazla bölünemeyene kadar sürer. Gerçeklenimde şeffaf piksel için bir giriş ayırma düşüncesi bulunduğundan, görünür renk sayısı pratikte 256 sınırının altında tutulur.

Kutuların ortalama RGBA değerleri ilk palet merkezlerini oluşturur. Bu aşama Wu nicemleyicisinin istatistiksel bölümünü tamamlar.

En yakın renk araması

Palet oluşturulduktan sonra görüntüdeki her piksel bir palet indeksine dönüştürülmelidir. Kaynak kod, RGBA uzayında karesel Öklid uzaklığı kullanır:

[
d(p,c)=
(A_p-A_c)^2+
(R_p-R_c)^2+
(G_p-G_c)^2+
(B_p-B_c)^2
]

En küçük uzaklığa sahip merkez, pikselin palet rengi olur.

Bütün piksellerin bütün palet renkleriyle karşılaştırılması en kötü durumda:

[
\Theta(NK)
]

maliyet üretir. "K" 255'e yaklaştığında bu aşama histogram hesaplamasından daha pahalı hale gelebilir.

Bunu azaltmak için kütüphanede veri bağımlı bir maskeleme ve kova yapısı geliştirdim. Palet kanallarındaki benzersiz değerlerin dağılımına göre alfa, kırmızı, yeşil ve mavi için bit maskeleri oluşturulur. Aynı maskeli anahtarı taşıyan palet renkleri bir kovaya yerleştirilir. Gelen piksel önce kendi kovasında aranır. Kova yoksa bütün palet taranır ve sonuç aynı anahtar için önbelleğe alınır.

Bu yöntem klasik bir uzamsal indeks değildir. Renk uzayını veri dağılımına göre kaba hücrelere ayıran hafif bir yaklaşık arama katmanıdır. Palet küçükken ağaç tabanlı bir yapıdan daha düşük sabit maliyet sağlayabilir.

Bununla birlikte, dolu bir kovada yalnız o kovanın renklerinin aranması küresel en yakın komşuyu garanti etmez. En yakın palet rengi komşu bir maskeli bölgede bulunabilir. Bu nedenle hız kazanımı ile tam en yakın renk doğruluğu arasında bir değiş tokuş vardır.

Kodda ilk kutu merkezleriyle atama yapıldıktan sonra, her palet girişine atanan gerçek piksellerin kanal ortalamaları yeniden hesaplanır. Bu işlem tek bir centroid güncellemesi olarak görülebilir. Tam k-means algoritmasındaki gibi atama ve merkez güncellemesi yakınsayıncaya kadar tekrarlanmaz. Buna rağmen Wu merkezlerinin ardından yapılan bu düzeltme, paletin gerçek atama kümelerine yaklaşmasını sağlar.

K-means tabanlı renk nicemleme çalışmalarında da iyi başlangıç merkezlerinin ve verimli en yakın komşu aramasının kalite ile çalışma süresini belirlediği gösterilmiştir. İncelenen yapı, tam bir k-means uygulaması olmadan benzer bir merkez düzeltme fikrini kullanır.

İndekslerin bit düzeyinde paketlenmesi

Renk sayısı belirlendikten sonra hedef piksel biçimi seçilir:

• 1 renk bölgesi için 1 bitlik çıktı
• 2 ile 16 arasındaki renkler için 4 bitlik çıktı
• Daha fazla renk için 8 bitlik çıktı

Bir bitlik biçimde sekiz piksel tek bayta paketlenir. Dört bitlik biçimde iki piksel bir baytın üst ve alt yarısına yazılır. Sekiz bitlik biçimde her piksel bir baytlık palet indisi taşır.

Bu bölümde "SetPixel" gibi yüksek seviyeli çağrılar kullanılmaz. Satırlar doğrudan kilitlenir ve paketlenmiş indisler bitmap belleğine aktarılır. Bu, piksel başına yönetilen metot çağrısı maliyetini ortadan kaldırır.

PNG standardı indeksli renklerde piksel değerinin palet indisi olduğunu, palet uzunluğunun bit derinliğinin izin verdiği sınırı aşamayacağını ve alfa bilgisinin palet girişleriyle ilişkilendirilebileceğini belirtir. PNG'deki alfa değerleri premultiplied değildir.

Kaynak kodun şeffaflık yaklaşımı, düşük alfa değerlerini ayrı bir palet girişine yönlendirir ve daha sonra belirli bir rengi şeffaf olarak işaretler. Bu, ikon türü görüntülerde işe yarayabilecek pratik bir çözümdür. Ancak gerçek alfa paleti yönetimine göre daha kırılgandır. Şeffaflık anahtarıyla aynı RGB değerine sahip görünür piksellerin yanlışlıkla etkilenmemesi ayrıca doğrulanmalıdır.

Dosya boyutuna göre yinelemeli optimizasyon

Kütüphane ilk nicemlenmiş çıktıyı son sonuç olarak kabul etmez. Kodlanan görüntüyü tekrar açar, yeniden nicemler ve yeni dosya boyutunu önceki sonuçla karşılaştırır. Yeni sonuç daha büyükse işlem durur. Daha küçük veya eşitse yeni çıktı korunur.

Bu yaklaşım açgözlü bir boyut optimizasyonudur:

[
L_{i+1}\leq L_i
]

koşulunu sağlayan sonuçlar kabul edilir. Üst sınır olarak belirli sayıda yineleme uygulanır.

Bu tasarım, gerçek dosya kodlayıcısını optimizasyon döngüsünün içine alması bakımından dikkat çekicidir. Sadece ham piksel sayısına veya palet büyüklüğüne bakılmaz. Palet sırası, renk tekrarları, filtreleme ve sıkıştırılmış bit akışı birlikte son dosya boyutuna yansır.

Bununla birlikte amaç fonksiyonu yalnız byte uzunluğudur. Görsel hata ölçülmez. Yeniden nicemleme her seferinde özgün görüntü yerine önceki nicemlenmiş sonuç üzerinden yapılır. Bu nedenle kayıp birikebilir. Dosya küçülürken bantlaşma, kenar renklerinin bozulması veya yarı saydam bölgelerde hale oluşması mümkündür.

Daha güçlü bir optimizasyon şu iki koşulu birlikte değerlendirmelidir:

[ \min L ]

[
D(I,\hat I)\leq D_{\max}
]

Burada "L" dosya boyutunu, "D" ise özgün görüntü ile sonuç arasındaki bozulmayı gösterir. PSNR veya yapısal benzerlik gibi ölçüler kullanılabilir. Ancak palet nicemlemede insan algısıyla daha uyumlu bir renk farkı ve alfa bileşim ölçüsü tercih edilmesi daha anlamlıdır.

Algoritmik karmaşıklık

Bir nicemleme turu için:

• "N": piksel sayısı
• "B": histogram eksen uzunluğu, burada 33
• "K": palet rengi sayısı
• "I": dış optimizasyon yinelemesi

olsun.

Histogram oluşturma:

[
\Theta(N)
]

Kümülatif moment hesabı:

[
\Theta(B^4)
]

Her kutu için dört eksende kesim arama:

[
O(KB)
]

Her bölünmeden sonra en yüksek varyanslı kutuyu doğrusal taramayla seçme:

[
O(K^2)
]

Piksel-palete eşleme, maskeleme başarısına bağlı olarak ortalama durumda daha düşük olmakla birlikte en kötü durumda:

[
O(NK)
]

olur.

Toplam üst sınır yaklaşık olarak:

[
O\left(
I\left[
N+B^4+KB+K^2+NK
\right]
\right)
]

şeklinde ifade edilebilir.

Gerçek görüntülerde kova tabanlı arama "NK" terimini önemli ölçüde küçültebilir. Dört boyutlu moment tablosu ise görüntü boyutundan bağımsız yaklaşık 45 MiB sabit alan kullanır. Bitmap ve akış kopyaları nedeniyle toplam bellek tüketimi ayrıca "O(N)" bileşeni taşır.

Algoritma küçük ikon ve web görsellerinde güçlü bir kalite-boyut dengesi sağlayabilir. Çok büyük görüntülerde ise tekrarlanan kod çözme, bitmap kopyaları ve dört boyutlu moment tablosu dikkate alınmalıdır.

Kaynak incelemesinde görülen sınırlar

Kodun genel algoritmik yapısı tutarlıdır. Bununla birlikte incelenen nüshada üretim öncesinde düzeltilmesi gereken bazı sınır durumları bulunur.

Palet arama maskesi oluşturulurken mavi kanalın en yüksek değeri yerine alfa kanalının en yüksek değerinin kullanıldığı görülmektedir. Bu ifade, mavi kanalın maske konumunu yanlış belirleyebilir. Kanal dağılımları birbirinden farklı olduğunda kova kalitesini düşürmesi mümkündür.

Renk sayısının tam 16 olduğu durumda, şeffaflık için ayrılan ek giriş ile 4 bitlik paletin 16 girişlik kapasitesi arasında sınır uyuşmazlığı oluşabilir. Palet kapasitesi ile görünür renk sayısı ve ayrılmış şeffaf giriş ayrı değişkenler olarak yönetilmelidir.

Şeffaflık denetimindeki genel hata yakalama davranışı, piksel okuma hatasını "şeffaflık yok" sonucuna dönüştürür. Bu yaklaşım işlemi kesintiye uğratmaz ancak gerçek hatayı gizleyebilir. Hata türünün kaydedilmesi veya çağırana aktarılması daha güvenilir olur.

Piksel yapısının aynı bellek üzerinde bayt kanallarıyla 32 bitlik tamsayıyı örtüştürmesi hızlıdır. Ancak kanal sıralaması işlemci byte sırasına ve kullanılan grafik altyapısına bağlıdır. Kodun geliştirildiği Windows ve GDI+ ortamında bu düzen öngörülebilirdir. Başka bir platforma geçişte byte sırası açıkça test edilmelidir.

Kütüphane tarihsel olarak "System.Drawing" ve GDI+ üzerinde geliştirilmiştir. Güncel .NET sürümlerinde "System.Drawing.Common" Windows'a özgü kabul edilmektedir. Çapraz platformlu yeni bir sürümde piksel çekirdeğinin platformdan bağımsız tutulması ve yalnız kod çözücü-kodlayıcı katmanının değiştirilmesi gerekir.

Yapay zeka ve görüntü işleme açısından anlamı

Bu kütüphaneyi yalnız bir PNG küçültme aracı olarak değerlendirmek eksik olur. İşlem hattı, yapay zeka ve görüntü işleme açısından dört temel kavramı bir araya getirir:

1. Özellik uzayı oluşturma
2. Yeterli istatistikleri çıkarma
3. Varyans tabanlı kümeleme
4. Merkez temsili ve en yakın örnek eşleme

Her piksel dört bileşenli bir vektördür. Histogram görüntünün ampirik dağılımıdır. Kutular kümeleri, palet renkleri ise prototipleri temsil eder. Nicemlenmiş görüntü, özgün verinin sınırlı sayıda prototiple yeniden oluşturulmuş biçimidir.

Bu yaklaşım, Yapay Zeka Kuramdan Uygulamaya kitabındaki "Görüntü ve Ses İşleme" bölümünde ele aldığım temel düşünceyle örtüşür. Görüntü işleme ile yapay zeka arasındaki bağ yalnız derin sinir ağlarından kurulmaz. Verinin uygun bir özellik uzayında gösterilmesi, dağılımının modellenmesi ve temsil maliyetinin düşürülmesi de aynı disiplinin temelidir. Bölümün görüntü kaydı, öznitelik vektörleri, iyileştirme ve yapay zeka tabanlı analiz başlıkları bu ilişkinin kuramsal çerçevesini oluşturur.

Geliştirdiğim gerçeklenimin özgün mühendislik yönü, bilinen bir varyans nicemleme yaklaşımını doğrudan kopyalamak yerine onu alfa boyutuyla genişletmesi, palet aramasına veri bağımlı bir ön indeks eklemesi, atama sonrasında merkezleri yeniden hesaplaması ve gerçek kodlanmış dosya boyutunu yinelemeli durdurma ölçütü olarak kullanmasıdır.

Kod aynı zamanda klasik algoritmalarda sık görülen temel değiş tokuşları açık biçimde gösterir. Daha hızlı bölge istatistikleri için bellek ayrılır. Daha hızlı renk eşleme için yaklaşık arama kabul edilir. Daha küçük dosya için tekrar nicemleme yapılır. Şeffaflık desteği için renk uzayına dördüncü boyut eklenir.

İyi bir görüntü optimizasyonu algoritması yalnız dosyayı küçültmez. Hangi bilgiyi koruduğunu, hangi bilgiyi kaybettiğini ve bu kaybı hangi maliyetle azalttığını açıklayabilir. Bu kütüphanenin asıl teknik değeri de buradadır. Renk paleti üretimini kapalı bir kodlayıcı davranışına bırakmak yerine momentler, varyans, kutu bölme ve merkez atama aşamalarını açık bir algoritma halinde kurar.

Kaynakça

Köker, M. A. "Görüntü ve Ses İşleme." Yapay Zeka Kuramdan Uygulamaya. Nobel Akademik Yayıncılık, 2022. ISBN 978-625-427-802-0.

Wu, X. "Efficient Statistical Computations for Optimal Color Quantization." Graphics Gems II, ss. 126-133, 1991. DOI: 10.1016/B978-0-08-050754-5.50035-9.

Celebi, M. E. "Improving the Performance of K-Means for Color Quantization." 2011.

World Wide Web Consortium. Portable Network Graphics Specification, Third Edition. 2025.