Görüntü Renk İndirgeme

sinyal quantalama
Renk indirgeme-azaltma görüntü işleme uygulamalarında genellikle görüntüyü sıkıştırmak veya işlemciler üzerindeki işlem yükünü azaltmak için sıklıkla kullanılan bir tekniktir. Günümüz makinelerini göz önüne alarak görüntü sıkıştırma hala gerekli mi sorusunu sorma cesaretini gösterenler için 1 saniyelik ortalama bir Full HD (1920x1080) filmin sıkıştırma yapılmadan en az  142 MB ile saklanabileceğini belirtmek isterim. Yani teknoloji geliştikçe saklama gereksinimi de sorun olmaktan çıkmıyor tam aksine sorun olmaya başlıyor.




Film sıkıştırma örneğimizden devam edecek olursak; video boyutlarını azaltmak için taviz verilebilecek birkaç noktadan biri olan renk derinliği günümüz videolarında piksel başına ortalama 1 bit ile ifade edilebilecek seviyelere kadar indirgenmiştir. Bizim çalışmalarımızda bir piksel için 24 bit kullandığımız düşünülürse varılan sıkıştırma oranı gerçekten korkutucu düzeydedir zira 1 bit ile siyah-beyaz (var-yok) olmak üzere ancak 2 renk değerini ifade edebiliriz.

Peki o zaman nedir bu renk indirgeme işlemi? Adaptif Eşikleme yazımızda incelediğimiz siyah-beyaz dönüşüm en basit renk indirgeme işlemidir ve bir çok uygulamada işlem yükünü azaltmak için tercih edilmektedir. Ancak amacımızı bir video veya görüntüyü sıkıştırmak olduğunu düşünecek olursak, Otsu metodu ile eşiklemenin kullanılamayacak bir yöntem olduğu açıktır (Görüntüdeki pek çok detay kaybı hatırlanmalıdır). Bu yazımızda özellikle görüntü sıkıştırmak için kullanılan bir algoritma olan Floyd-Steinberg titreme (dithering) algoritmasından bahsedeceğiz. Bu algoritma günümüzde hala sıklıkla karşımıza çıkan gif formatında renk sayısını azaltmak için, eski siyah-beyaz ekranlı telefonlarımızda da görüntüleri gerçekçi ifade edebilmek için kullanılmıştır.

Algoritmayı anlatmak için gri seviye bir resmi siyah-beyaz tonlayacağımızı düşünelim. Klasik yaklaşıma göre her bir piksel değeri, değer eşik değerinden küçükse 0, büyükse 255 (veya mantıksal 1) ile değiştirlimelidir. Titreme algoritması tarafından önerilen şey ilk piksel dönüştürüldükten sonra yapılan hatanın komşu piksellere dağıtılarak eşiklemenin devam etmesidir. Bu sayede  bir piksel ile yapılan hata diğer piksele eklenerek toplam hata en aza indirilmeye çalışılmıştır. Bir örnek ile açıklamaya çalışalım:

Görüntü : 1 7 4 5 2 1 0 8 6 5 2 4 5 6 ve eşik değerimiz 5 ve mantıksal 1 değerimiz 7 olsun;

Klasik yaklaşıma göre  5 değerinden büyük tüm değerler 7 küçük veya eşit değerler ise 0 olarak doldurulmuş yeni bir görüntü elde edilmelidir.

Klasik  : 0 7 0 0 0 0 0 7 7 0 0 0 0 7

Titreme yaklaşımında ise bir piksel ile yapılan hata komşu piksellere dağıtılarak işleme devam edilmelidir. Örnek olarak yapılan hatayı bir sonraki piksele aktardığımızı düşünecek olursak;

1. piksel 1 eşikleme sonucunda 0 olacaktır. Bu işlem ile hatamız 1-0 = 1 yan piksele eklenir.
2. pikseli artık 7+1=8 olarak düşünüyoruz. Eşikleme sonucu 7 olacağından yapılan hata 7-7 = 0 yan piksele eklenir.
3. piksel 4+0=4 olarak işlem görecek ve eşikleme sonrası 0 olacaktır. Bu sefer yapılan hata 4-0 = 4 yan piksele aktarılır.
4. piksel 5+4=9 olacağından eşikleme sonrası 7 olacaktır ve hata 5-7 = -2 yan piksele aktarılacaktır.
5. piksel 2+-2=0 olacak ve eşikleme sonrası 0 olacaktır. Hatamız da 2-0 = 2 olarak yan piksele aktarılacaktır.
6. piksel 1+2=3 olarak eşiklenerek 0 değerini alacak ve yapılan hata 1-0 = 1 olarak komşu piksele aktarılacaktır.
7. piksel 0+1=1 olduğundan 0 değeri verilerek 0-0 = 0 hata yapılacaktır.
8. piksel 8+0=8 olduğundan 7 olarak eşiklenecek ve 8-7= 1 hata yan piksele aktarılacaktır.
9. piksel 6+1=7 olarak işlem görerek 7 değerini alacak ve yapılan hata 6-7 = -1 olacaktır.
10. piksel 5+-1=4 olarak işlem görecek ve 0 değerine eşitlenecek. Bu durumda yapılan hata 5-0 = 5 olacaktır.
11. piksel 2+5=7 olarak işlem görecek ve eşikleme sonrası 7 değerini alacaktır. Bu durumda yapılan hata 2-7 = -5 olacaktır.
12. piksel 4+-5=-1 olarak işlem görecek ve 0 değerini alacaktır. Bu eşikleme ile yapılan 4-0 = 4 hata değeri  de komşu piksele aktarılacaktır.
13. piksel 5+4=9 olarak işlem görerek 7 değerini alacak ve 5-7 = -2 kadarlık bir hata yapılacaktır.
14. piksel 6+-2 olarak işlem görerek 0 değerine eşiklenecektir.

İşlem sonrası eşiklenen görüntü aşağıdaki gibi olacaktır.

Titreme : 0 7 0 7 0 0 0 7 7 0 7 0 7 0
Klasik   : 0 7 0 0 0 0 0 7 7 0 0 0 0 7

Bir önceki eşikleme ile yapılan hatanın büyüklüğü doğrudan bir sonraki eşiklemeyi de etkilediğinden sonuç görüntüsünde siyah-beyaz (0-7) geçişlerinin fazla olduğunu yani oluşan görüntüdeki 0 ve 7 lerin titrediğini söyleyebiliriz. Algoritmanın Floyd-Steinberg' e ait olan tarafı hatayı komşulara yayma kısmında saklıdır. Yukarıdaki örnek için hatayı basitçe sağ piksele aktarmıştık, daha güzel bir titreme etkisi için Floyd-Steinberg aşağıdaki hata yayılım matrisini kullanmayı önermişlerdir. (verilen değerler 1/16 ile normalize edilmelidir)
  X 7
3 5 1
Burada verilen değerler X üzerinde işlem yaptığımız piksel olmak üzere hatanın hangi çarpanlar ile komşulara dağıtılacağını göstermektedir. Yani sağ komşu hatanın 7/16 sını alt komşu 5/16 sını şeklinde hata paylaştırılmaktadır. Bu paylaşıma ait yazılmış kod ile oluşturulan ikili çıktı aşağıdadır.

renk kuantalama
Renk indirgeme örneği
Örnek üzerinde de açıkça görüldüğü gibi titreme algoritması ile üretilen görüntü (en sağda) sadece siyah ve beyazlardan oluşmasına rağmen gerçek gri seviye görüntü ile neredeyse aynı görünmektedir. Ortada bulunan Otsu metodu ile eşiklenmiş görüntü de ise kaybolan pek çok detay vardır.

Renkli görüntüler üzerinde de çalışabilen bu algoritma için yazılan kod aşağıda verilmiştir. Kod içerisinde if koşulu kullanmamak için algoritma sınır bölgeler için parçalara ayrılarak yazılmıştır (örneğin yan komşu son sütun için yoktur). Bu nedenle algoritma bir hayli uzun görünmektedir ancak dikkatle bakılacak olursa aynı işlemin farklı bölgeler için tekrarlandığı kolaylıkla görülebilir.


BMP   resim_dit(BMP kaynak,double tr[3][256]) {
      
   BMP im=yenim_bmp(kaynak.bminfo.width,kaynak.bminfo.height);
      
   // Fark Matrislerini Yarat her seferinde işlem yapmamak için
   double *tr_sagyan = new double [512]; //merkezin yeni saga etkisi       (7/16)
   double *tr_sagalt = new double [512]; //merkezin sag alt piksele etkisi (1/16)
   double *tr_solalt = new double [512]; //merkezin sol alta etkisisi      (3/16)
   double *tr_altalt = new double [512]; //merkezin alt etkisi             (5/16)
      
   unsigned int dif_red   = 0;
   unsigned int dif_green = 0;
   unsigned int dif_blue  = 0;
      
   unsigned int k;
   unsigned int i=0,j=0;
      
   for(k=0; k &lt 256; k++) {
                     
       tr_sagyan[k+256] = ((double)k*0.4375); // (7/16)   
       tr_sagalt[k+256] = ((double)k*0.0625); // (1/16) 
       tr_solalt[k+256] = ((double)k*0.1875); // (3/16) 
       tr_altalt[k+256] = ((double)k*0.3125); // (5/16) 
       // Negatif farklarıda hesapla                 
       tr_sagyan[255-k] = -tr_sagyan[k+256];   
       tr_sagalt[255-k] = -tr_sagalt[k+256] ; 
       tr_solalt[255-k] = -tr_solalt[k+256]; 
       tr_altalt[255-k] = -tr_altalt[k+256]; 

    } 
      
   for(j=0;j &lt kaynak.bminfo.height-1;j++) { 
            
       // 0 için döngü içerisi sıkıntılı olduğundan 0 için her satıra başlarken önceden yap
       im.pixels[0][j].red   =  gbyte_yap(tr[0][kaynak.pixels[0][j].red]);
       im.pixels[0][j].green =  gbyte_yap(tr[1][kaynak.pixels[0][j].green]);
       im.pixels[0][j].blue  =  gbyte_yap(tr[2][kaynak.pixels[0][j].blue]);
            
       // hatayı hesapla
       dif_red   = (kaynak.pixels[0][j].red - im.pixels[0][j].red + 255);
       dif_green = (kaynak.pixels[0][j].green - im.pixels[0][j].green + 255);
       dif_blue  = (kaynak.pixels[0][j].blue  - im.pixels[0][j].blue  + 255);
            
       // hatayı komşulara paylaştır
       kaynak.pixels[1][j  ].red   =  gbyte_yap( kaynak.pixels[1][j  ].red   + tr_sagyan[dif_red]   );
       kaynak.pixels[1][j+1].red   =  gbyte_yap( kaynak.pixels[1][j+1].red   + tr_sagalt[dif_red]   );
       kaynak.pixels[0][j+1].red   =  gbyte_yap( kaynak.pixels[0][j+1].red   + tr_altalt[dif_red]   );

       kaynak.pixels[1][j  ].green =  gbyte_yap( kaynak.pixels[1][j  ].green + tr_sagyan[dif_green] );
       kaynak.pixels[1][j+1].green =  gbyte_yap( kaynak.pixels[1][j+1].green + tr_sagalt[dif_green] );
       kaynak.pixels[0][j+1].green =  gbyte_yap( kaynak.pixels[0][j+1].green + tr_altalt[dif_green] );

       kaynak.pixels[1][j  ].blue  =  gbyte_yap( kaynak.pixels[1][j  ].blue  + tr_sagyan[dif_blue]  );
       kaynak.pixels[1][j+1].blue  =  gbyte_yap( kaynak.pixels[1][j+1].blue  + tr_sagalt[dif_blue]  );
       kaynak.pixels[0][j+1].blue  =  gbyte_yap( kaynak.pixels[0][j+1].blue  + tr_altalt[dif_blue]  );  
                                          
       for(i=1;i &lt kaynak.bminfo.width-1;i++) {
            
           // şimdi 1-(N-1) arasını yap bu arada sıkıntılı durum yok
           im.pixels[i][j].red   =  gbyte_yap(tr[0][kaynak.pixels[i][j].red]);
           im.pixels[i][j].green =  gbyte_yap(tr[1][kaynak.pixels[i][j].green]);
           im.pixels[i][j].blue  =  gbyte_yap(tr[2][kaynak.pixels[i][j].blue]);
           // hatayı hesapla
           dif_red   = (kaynak.pixels[i][j].red   - im.pixels[i][j].red   + 255);
           dif_green = (kaynak.pixels[i][j].green - im.pixels[i][j].green + 255);
           dif_blue  = (kaynak.pixels[i][j].blue  - im.pixels[i][j].blue  + 255);
           // hatayı komşulara paylaştır
           kaynak.pixels[i+1][j  ].red   = gbyte_yap( kaynak.pixels[i+1][j  ].red   + tr_sagyan[dif_red]   );
           kaynak.pixels[i+1][j+1].red   = gbyte_yap( kaynak.pixels[i+1][j+1].red   + tr_sagalt[dif_red]   );
           kaynak.pixels[i-1][j+1].red   = gbyte_yap( kaynak.pixels[i-1][j+1].red   + tr_solalt[dif_red]   );
           kaynak.pixels[i  ][j+1].red   = gbyte_yap( kaynak.pixels[i  ][j+1].red   + tr_altalt[dif_red]   );

           ////////////////////////AYNI İŞLEMLER YEŞİL ve MAVİ KANAL İÇİN DE YAPILDI//////////////////
       } 

      // şu anda i=kaynak.bminfo.width-2 aynı işlemi son sütun içinde yapalım
      // bir ileride artık piksel yok o yüzden bir alt ve gerimize dağıtabiliriz
      im.pixels[kaynak.bminfo.width-1][j].red   =  gbyte_yap(tr[0][kaynak.pixels[kaynak.bminfo.width-1][j].red]);
      im.pixels[kaynak.bminfo.width-1][j].green =  gbyte_yap(tr[1][kaynak.pixels[kaynak.bminfo.width-1][j].green]);
      im.pixels[kaynak.bminfo.width-1][j].blue  =  gbyte_yap(tr[2][kaynak.pixels[kaynak.bminfo.width-1][j].blue]);
            
      // hatayı hesapla
      dif_red   = (kaynak.pixels[kaynak.bminfo.width-1][j].red   - im.pixels[kaynak.bminfo.width-1][j].red   + 255);
      dif_green = (kaynak.pixels[kaynak.bminfo.width-1][j].green - im.pixels[kaynak.bminfo.width-1][j].green + 255);
      dif_blue  = (kaynak.pixels[kaynak.bminfo.width-1][j].blue  - im.pixels[kaynak.bminfo.width-1][j].blue  + 255);
            
      // hatayı komşulara paylaştır gerimizdeki ve altımızdaki komşuyu kullanabiliriz sağımızda piksel yok
      kaynak.pixels[kaynak.bminfo.width-2][j+1].red   = gbyte_yap( kaynak.pixels[kaynak.bminfo.width-2][j+1].red+tr_solalt[dif_red]   );
      kaynak.pixels[kaynak.bminfo.width-1][j+1].red   = gbyte_yap( kaynak.pixels[kaynak.bminfo.width-1][j+1].red + tr_altalt[dif_red] );
      ////////////////////////AYNI İŞLEMLER YEŞİL ve MAVİ KANAL İÇİN DE YAPILDI//////////////////
   } // tüm satırlar için tekrarla
            
// son satırı tüm sütunlar için yap
// bir altımızda kimse yok hatayı bir ileriye paylaştıralım
for(i=0;i &lt kaynak.bminfo.width-1;i++) {

im.pixels[i][kaynak.bminfo.height-1].red   =  gbyte_yap(tr[0][kaynak.pixels[i][kaynak.bminfo.height-1].red]);
im.pixels[i][kaynak.bminfo.height-1].green =  gbyte_yap(tr[1][kaynak.pixels[i][kaynak.bminfo.height-1].green]);
im.pixels[i][kaynak.bminfo.height-1].blue  =  gbyte_yap(tr[2][kaynak.pixels[i][kaynak.bminfo.height-1].blue]); 
            
// hatayı hesapla
dif_red   = (kaynak.pixels[i][kaynak.bminfo.height-1].red   - im.pixels[i][kaynak.bminfo.height-1].red   + 255);
dif_green = (kaynak.pixels[i][kaynak.bminfo.height-1].green - im.pixels[i][kaynak.bminfo.height-1].green + 255);
dif_blue  = (kaynak.pixels[i][kaynak.bminfo.height-1].blue  - im.pixels[i][kaynak.bminfo.height-1].blue  + 255);
            
kaynak.pixels[i+1][kaynak.bminfo.height-1].red   = gbyte_yap( kaynak.pixels[i+1][kaynak.bminfo.height-1].red   + tr_sagyan[dif_red]   );
kaynak.pixels[i+1][kaynak.bminfo.height-1].green = gbyte_yap( kaynak.pixels[i+1][kaynak.bminfo.height-1].green + tr_sagyan[dif_green] );
kaynak.pixels[i+1][kaynak.bminfo.height-1].blue  = gbyte_yap( kaynak.pixels[i+1][kaynak.bminfo.height-1].blue  + tr_sagyan[dif_blue]  );
}

// Son satır son sütun içinde yap ve bitir            
im.pixels[kaynak.bminfo.width-1][kaynak.bminfo.height-1].red   =  gbyte_yap(tr[0][kaynak.pixels[kaynak.bminfo.width-1][kaynak.bminfo.height-1].red]);
im.pixels[kaynak.bminfo.width-1][kaynak.bminfo.height-1].green =  gbyte_yap(tr[1][kaynak.pixels[kaynak.bminfo.width-1][kaynak.bminfo.height-1].green]);
im.pixels[kaynak.bminfo.width-1][kaynak.bminfo.height-1].blue  =  gbyte_yap(tr[2][kaynak.pixels[kaynak.bminfo.width-1][kaynak.bminfo.height-1].blue]);
            
return im;
}

Yazılan bu uzun koddan sonra denemelerin tadını çıkarabiliriz. dediğim gibi kod renkli resimleri de düşünerek 3 boyut için aynı işlemlerin tekrarı şeklinde yazıldı. Yeni oluşacak resimde kaç tane renk değerinin olacağını daha önceki yazılarımızda renk haritalama olarak gördüğümüz matris ile veriyoruz. Örnek bir kullanım olarak her kanal için 1 bit veri tutan bir (toplamda 3 bit 2^3=8 renk eder) dönüşüm matrisi ile neler elde edeceğimize bakalım.

int main() {
    
    BMP I   = resim_oku("gray.bmp");
    BMP G   = resim_cev(I,rgb2gra);

    int M = I.bminfo.height;
    int N = I.bminfo.width;
    
    double map[3][256];
    int i,j,t=0;  

    for(i=0;i < 256;i++) {
           map[0][i] = i < 128 ? 0:255; // 1bit
           map[1][i] = i < 128 ? 0:255; // 1bit
           map[2][i] = i < 128 ? 0:255; // 1bit
    }
                  
    BMP Map = resim_dit(I,map);                  
    resim_yaz(Map,"llena1.bmp");

    return 0;
} 

Yukarıdaki kod parçacığı gray.bmp resmini okuyarak 0 ve 255 lerden oluşturulan renk haritasını kullanarak titreme işlemi uygulamaktadır. Sonuç olarak döndürülen Map görüntüsü yalnızca 8 adet farklı renkten oluşan bir görüntüdür.

Renk İndirgeme
Renkli seviye renk indirgeme
 Örnekten de açıkça görüldüğü üzere bizde bir piksel için 3 bit tutarak gerçek görüntümüze yakın bir görüntü elde edebildik  (en azından uzaktan öyle gözüküyor). Videolarda sıkıştırma için pek çok parametrenin de kullanıldığı düşünülürse piksel başına 1 bit  in o kadar da korkutucu bir oran olmadığı anlaşılabilir sanırım. Yazımızın başında değindiğimiz gibi standart bir görüntüde 24 bitlik (16 milyon renk) renk haritası kullanıldığı düşünülürse pek çok görüntüyü bu teknikle sıkıştırmak özellikle video lar için akıl karı görülebilir. Dahası renk sayısı 8 den 256-1024 lere çıkarılarak kayıpsız denilebilecek sıkıştırmalarda yapılabilir.

Hiç yorum yok:

Yorum Gönderme

Görüntü işleme ile ilgili yeni yazıları ve bu sitede yer alan yazıların güncellenmiş sürümlerini www.imlab.io veya cescript.github.io adreslerinden takip edebilirsiniz.

X