C++ ile Konvolüsyon İşlemi

Konvolüsyon veya daha yaygın adıyla evrişim; iki işaretin birleştirilerek üçüncü bir işaret elde edilmesinde kullanılan bir işlemdir. Üretilen bu işaret, birleştirilen iki işaretin kesişimlerinin altında kalan alanın miktarıdır. Özellikle işaret işleme ve matematik alanlarında sıklıkla kullanılan bu işlem, doğrusal zamanla değişmeyen sistemlerin birim dürtü yanıtı $h(t)$ veya transfer fonksiyonu $H(f)$ bilindiğinde, girişinden verilen $x(t)$ işaretine karşı üreteceği çıktıyı hesaplamada kullanılır. Görüntü işleme alanında ise birim dürtü yanıtı $h(t)$ elle oluşturularak istenilen özellikte sistemler (görüntü bulanıklaştırma sistemi, görüntü kenar bulma sistemi, vs.) üretmek için kullanılır.


Konvolüsyon işlemi $\ast$ sembolü ile gösterilir ve bir boyutlu sürekli zamanlı evrişim işlemi aşağıdaki formül ile hesaplanır. $$y(t)=\int_{-\infty}^{\infty}x(\tau) h(t-\tau) d \tau$$ Konvolüsyon işleminin daha iyi anlaşılması için aşağıdaki hareketli resim incelenebilir. Burada kırmızı renkli işaret sistemin birim dürtü yanıtının ters çevrilmiş şeklini simgelemektedir. Bu işaret -∞ dan başlayarak +∞ a doğru adım adım kaydırılır ve her kaydırma sonrası $x$ işareti ile örtüşen kısımın altında kalan alanı hesaplanır. Hesaplanan bu sonuç lineer zamanla değişmeyen sistemin $x$ giriş işaretine karşı ürettiği çıkış işaretidir.

Evrişimi daha iyi anlamak için bir örnek üzerinden formülün kullanımını görelim. Örneğimizde giriş işaretimiz $x(t)$ parçalı bir fonksiyonla
$$
x(t)=
\begin{cases}
t+1,& 0\leq t \leq 1 \\
2-t, & 1< t \leq 2 \\ 0, & \text{diğer} \end{cases} $$ şeklinde verilmiştir. Sistemin birim dürtü yanıtı ise $h(t)=\delta(t+2)+2\delta(t+1)$ şeklindedir. Verilen örnekte, $x(t) \ast h(t)$ sürekli zamanlı konvolüsyon işleminin sonucu sorulmaktadır. Bu sürekli zamanlı konvolüsyonu yukarıda verilen formülü kullanarak aşağıdaki şekilde hesaplayabiliriz. $$x(t) \ast h(t)=\int_{-\infty}^{\infty} x(\tau)h(t-\tau)d\tau=\int_{-\infty}^{\infty} h(\tau)x(t-\tau)d\tau$$Burada $h(t)=\delta(t+2)+2\delta(t+1)$ ifadesini yerine koyarsak; $$x(t) \ast h(t)=\int_{-\infty}^{\infty} \delta(\tau+2)x(t-\tau)d\tau + 2\int_{-\infty}^{\infty} \delta(\tau+1)x(t-\tau)d\tau$$ integral toplamı elde edilir.

Burada kullanılan $\delta(t)$ fonksiyonu birim dürtü fonksiyon olarak adlandırılır ve sadece sıfır noktasında $\infty$ değeri vardır. Birim sıfatının gereği bu fonksiyonun altında kalan alan $\int_{0^-}^{0^+}\delta(\tau) d\tau=1$ dir. Benzer şekilde $\delta(t+1)$ ifadesi de $\int_{-1^-}^{-1^+}\delta(\tau) d\tau=1$ dir. Bu bilgi yukarıdaki integral toplamı ifadesinde kullanılırsa; $$x(t) \ast h(t)=x(t-\tau)|_{\tau=-2} + 2x(t-\tau)|_{\tau=-1} = x(t+2)+2x(t+1)$$ olarak bulunur. Bulunan bu ifadenin ve giriş işaretinin çizimi aşağıdaki grafikte verilmiştir.


Görüntü işleme ve bilgisayar ortamında yapılan pek çok sinyal işleme işlemi ayrık zamanlı olduğundan, evrişim  $$y[n]=x[n]\ast h[n] = \sum_{k=-\infty}^{\infty} x[k] h [n-k]$$ formülü ile ayrık zamanlı olarak hesaplanır. Buna ek olarak görüntüler iki boyutlu işaretler olduğundan iki boyutlu konvolüsyon işlemide benzer olarak aşağıdaki formül ile ifade edilir.
$$y(m,n)=x(m,n)\ast h(m,n)=\sum_{i=-\infty}^{\infty}\sum_{j=-\infty}^{\infty}x(i,j)h(m-i,n-j)$$
Burada $h(m,n)$ konvolüsyon çekirdek matrisi(kernel) olarak adlandırılır ve genellikle $3x3,5x5,7x7$ gibi büyüklükte seçilir. Seçilen çekirdek matrisinde yer alan değerler komşu piksellerin merkez piksele yapacağı etkinin ağırlığını gösterir. Aşağıda $x$ matrisinin $h$ çekirdek matrisi ile evrişimi gösterilmiştir.
$$
x=
\begin{bmatrix}
17 & 1 & 24 & 8 & 15\\
23 & 5 & 7 & 14 & 16\\
4 & 6 & 13 & 20 & 22\\
10 & 12 & 19 & 21 & 3\\
11 & 18 & 25 & 5 & 9
\end{bmatrix}
\;\;\;
h=
\begin{bmatrix}
8 & 1 & 6\\3 & 5 & 7\\4 & 9 & 2
\end{bmatrix}
\;\;\;\;
x\ast h =
\begin{bmatrix}
17 & 1 & 24^2 & 8^9 & 15^4\\
23 & 5 & 7^7 & 14^5 & 16^3\\
4 & 6 & 13^6 & 20^1 & 22^8\\
10 & 12 & 19 & 21 & 3\\
11 & 18 & 25 & 5 & 9
\end{bmatrix}
$$
Yukarıda $x\ast h$ işleminin hesaplanması için $h$ matrisi ters çevrilerek hesaplanmak istenen $(2,4)$ pikselin üzerine koyuldu. Bu durumda hesaplanan $(2,4)$ pikselinin yeni değeri ise $$g(2,4)=24*2+9*8+15*4+7*7+14*5+16*3+13*6+20*1+22*8= 621$$ buludu.

Evrişim özellikle görüntü işleme alanında kullanılacaksa bazı önemli noktalara dikkat edilmelidir.

▲ Bunlardan ilki şüphesiz ki kenar noktalardır. Çekirdek matrisin merkez elemanı görüntü üzerindeki ilk pikselin üzerine gelecek şekilde konulduğunda çekirdek matrisin bazı elamanlarına karşılık çarpılacak eleman bulunmaz. Bu durumda programın hata vermemesi için yazılan kodlarda giriş matrisine çekirdek matrisin boyunun bir eksiği kadar satır ve sütun eklenmiş ve bu satırlar 0 alınarak programın hata vermesi engellenmiştir.

▲Bir diğer sorun ise işlem sonrası hesaplanan yeni piksel değerinin seçilen çekirdek matris ağırlıklarına bağlı olarak 0-255 aralığı dışında kalmasıdır. Bu durumda programda kontrol edilmiş ve sınırlar dışında kalan değerler sınır değerlerine çekilmiştir.

▲ Hesaplama yapılırken hesaplanan yeni değerler yeni bir matris üzerinde tutularak yeni değerler ile işlem yapılan matrisin değerlerinin karışması ve hatalı sonuç üretmesi engellenmiştir.

    BMP im=yenim_bmp(kaynak.bminfo.width,kaynak.bminfo.height);
    BMP kaynako=yenim_bmp(kaynak.bminfo.width+k-1,kaynak.bminfo.height+k-1);
    int i,j,m,n;
    double red,green,blue;
            
     for (i=0;i < kaynak.bminfo.width;i++) {
         for (j=0;j < kaynak.bminfo.height;j++) {           
     kaynako.pixels[i+(k-1)/2][j+(k-1)/2].red=kaynak.pixels[i][j].red;
     kaynako.pixels[i+(k-1)/2][j+(k-1)/2].green=kaynak.pixels[i][j].green;
     kaynako.pixels[i+(k-1)/2][j+(k-1)/2].blue=kaynak.pixels[i][j].blue; }}
     
     for (i=0;i < kaynak.bminfo.width;i++) {
         for (j=0;j < kaynak.bminfo.height;j++) { 
             for (m=0;m < k; m++) {
                 for (n=0;n < k; n++) {
     
     red+=kaynako.pixels[i+m][j+n].red*filt[m][n];
     green+=kaynako.pixels[i+m][j+n].green*filt[m][n];
     blue+=kaynako.pixels[i+m][j+n].blue*filt[m][n];
     }}
     im.pixels[i][j].red= red    < 0 ? 0: red > 255   ? 255:(byte)red;
     im.pixels[i][j].green=green < 0 ? 0: green > 255 ? 255:(byte)green;
     im.pixels[i][j].blue=blue   < 0 ? 0: blue > 255  ? 255:(byte)blue;
     red=0;
     green=0;
     blue=0;
     }}
            
     return im;

Basit bir de kenar bulma algoritması ile fonksiyonun nasıl kullanacağını görelim.

resim=resim_acm("istanbul.bmp");//istanbul.bmp resmi açılıyor

double **filtre;
filtre = new double* [3];
for(i=0;i < 3;i++) { filtre[i]=new double [3]; }

filtre[0][0]=-1;
filtre[0][1]=-1;
filtre[0][2]=-1;
filtre[1][0]=-1;
filtre[1][1]= 8;
filtre[1][2]=-1;
filtre[2][0]=-1;
filtre[2][1]=-1;
filtre[2][2]=-1;

yeni=resim_kon(resim,filtre,3);//resim matrisi ile filtre matrisinin konvolüsyonu alınıyor.
resim_yaz(yeni,"istanbul_k.bmp");//resim istanbul_k adında kaydediliyor


Yukarıda basit bir $3\times 3$ çekirdek matrisi ile kenar noktalarının nasıl bulunacağı götserilmiştir. Yukarıda verilen çekirdek matrisinde 8 yerine 9 yazarsak imgenin keskinleştirildiğini, çekirdek matrisinin tüm elemanları 1/9 olacak şekilde güncelleme yaparsak, sonuç imgesinin bulanıklaştığını gözlemleyebiliriz.

12 yorum:

  1. Eline sağlık Bahri döktürmüşün yine. Örnek konvolüsyon işleminde 5*8 yanlış olmuş heralde 9*8 olacak? Sonuçta da bir hata var gibi. Dikkatimi çekti söylim dedim yorumu silebilirsin ;)

    YanıtlaSil
    Yanıtlar
    1. Estağfurullah Erhan, dediğin gibi bir yazım ve işlem hatası olmuş. Gerekli düzeltmeyi yaptım, teşekkürler ;)

      Sil
  2. Site harika olmuş. Emeğine sağlık...

    YanıtlaSil
  3. Hocam matrisi neden ters çevirdik acaba?

    "Yukarıda x∗hx∗h işleminin hesaplanması için hh matrisi ters çevrilerek hesaplanmak istenen (2,4)(2,4) pikselin üzerine koyuldu."

    YanıtlaSil
    Yanıtlar
    1. İki boyutlu konvolüsyon işlemini yazı içerisinde Toplam[ x(i,j)h(m−i,n−j) ] şeklinde tanımlamıştık. Burada i,j imge üzerindeki koordinatları göstermektedir. m,n toplam boyunca sabit olduğundan h(m-i,n-j) işleminin h(-i,-j) ile ilişkili olduğunu söyleyebiliriz. Yani konvolüsyon işlemi x(i,j)*h(-i,-j) ile ilişkilidir. Burada h çekirdeğini x ve y ekseninde ters çevirirsek aynı işlemi x(i,j)*h_ters(i,j) şeklinde tanımlayabiliriz. Bu tanımlama kod yazımını basitleştirdiğinden ve anlamayı kolaylaştırdığından çoğu uygulamada çekirdek matrisi önce ters çevrilerek x(i,j)*h_ters(m+i,n+j) işleminin hesaplanması tercih edilir.

      Sil
    2. Hocam detaylı açıklamanız için müteşekkirim.

      for (i=0;i < kaynak.bminfo.width;i++) {
      for (j=0;j < kaynak.bminfo.height;j++) {
      kaynako.pixels[i+(k-1)/2][j+(k-1)/2].red=kaynak.pixels[i][j].red;
      kaynako.pixels[i+(k-1)/2][j+(k-1)/2].green=kaynak.pixels[i][j].green;
      kaynako.pixels[i+(k-1)/2][j+(k-1)/2].blue=kaynak.pixels[i][j].blue; }}

      Buradaki k değişkeni, içerisinde neyin değerini tutmakta acaba?

      Sil
    3. K değeri konvolusyon çekirdek matrisinin boyunu göstermekte. Yazıdaki örnek için k=3 yani çekirdek 3x3 boyutunda demek. Bu boyutta bir çekirdeğin merkezini imgenin köşe noktalarına koydugumuzda 1 pixellik bir kısım dışarıda kalacaktır. Belirttiğiniz kod parçasında işleme başlamadan önce resmin boyutu k değerine göre k-1 kadar artırılmış ve orijinal resim bu imgeye ortalanarak tekrar yazılmıştır. Yani işlemin köşe noktalardaki belirsizliği köşe noktaları 0 kabul edilerek giderilmiştir.

      Sil
    4. Teşekkürler detaylı cevaplandırmanız için.

      Sil
  4. Bu yorum yazar tarafından silindi.

    YanıtlaSil
  5. Merhaba,
    Anlattıklarınız çok takdire şayan husus ve detaylar.
    Fakat üzüldüğüm, muhtemelen yabancı dilde çok iyi anladığınız anlamları Türkçede çok kötü ifade ediyor oluşunuz.
    Daha açık ifade edeyim, "ifade ettiğinizi sanıyorsunuz" fakat bu aslında Türkçeyi sadece bir "interface" olarak kullanmış olmanızdan ibaret. Yani, Google Türkçesinden hiç farklı değil. Böylesine "sahte" bir dil ile Türkçenin semantik bütünlüğüne asla ulaşılamaz. Bu Türkçe değil, bir garabet.
    Bu dilde "evrişim" gibi bir kelime yok. "Varmış" gibi bir komunal kabul üzerinden takdim etmenizin de hiçbir anlamı yok.
    Biz buna benzer "zorlamaları" on yıllar boyu çok gördük. Hiçbiri Türkçe merkezli olmadığından "Türkçe zihin ve onun eseri olan bilinçte" tutunamadı.
    Hatta daha da ötesini söyleyeyim, sanki bir dll dosyası gibi sipariş ettirilip, meselâ haber kanallarına microsoft word şablonu gibisinden rezillikler halinde dağıtılan bu şey ile Türkçeyi güdebilmek şansınız yok...
    Bununla sonuna kadar savaşmak boynumuzun borcudur. Savaştık ta. Ve savaşacağız.
    Computer Graphics ile programlama değil de DCC anlamında haşır neşir olmuş biri olarak bu konuyu çok daha mühim görüyorum.

    Mesut Demirhan
    Eskişehir

    YanıtlaSil
    Yanıtlar
    1. Merhabalar Mesut Bey,

      Öncelikle yorumunuz için teşekkür ederim. Benim de yorumunuzda katıldığım ve katılmadığım noktalar var. Bunları belirmek isterim.

      Bildiğiniz gibi yazılı ve sözlü anlatım birbirinden tamamen farklı dinamikleri olan iletişim biçimleridir. Bu yazıda yer alan evrişim konusunu Türkçe ve İngilizce dillerinde haftalarca anlatmış birisi olarak, herhangi bir kavramı Türkçede "kötü" ifade ediyorsam bu tamamen benim yazılı iletişimimin yetersiz olmasından kaynaklanmaktadır.

      Bu dilde (günlük dilde) "evrişim" diye bir kelimenin olmadığına gelince, İngilizcede de "convolution" kelimesinin olmadığını (bizim kullandığımız anlamıyla) belirtmek isterim. Bilimsel dil ile günlük dil veya yazı dili bambaşka şeylerdir. Bilimsel ve teknik kelimeler sadece o konu ile ilgili çalışan bir topluluk içerisinde bilinir ve bu topluluk içerisinde kabul edilir. Eğer bir bilimsel paylaşım yapılıyorsa da doğal olan bu dilin kullanılmasıdır.

      Bu kavramların zihinde tutunamamasını ise tam olarak anlayamadım. Evrişim kelimesi yerine konvolüsyon kelimesini kullandığımda konunun daha iyi anlaşılmasını veya zihinde tutunmasını tam olarak ne sağlayacak bilmiyorum. Eğer kastettiğiniz yabancı dilde yazılmış kaynakları okurken veya yabancı birisi ile bilimsel bir tartışma yaparken yaşadığınız zorlanma ise bu konuda sizinle hemfikirim.

      Günümüzde fiziksel sınırlar bilimsel topluluklar için neredeyse kalkmış olduğundan bilimsel dil hızla tek dile (İngilizce) doğru gitmekte ve bilimsel çalışma yapanlar olarak biz de bu dili kullanmaya mecbur kalanlardanız. Ancak bilimsel dili günlük dil veya yazılı dil ile iç içe kullanırsak da tek dile doğru olan yolculuğun Türkçeyi çok daha hızlı yok etmesine katkı sağlayacağını düşünmekteyim.

      Bu nedenle bilimsel kavramların Türkçe karşılıklarının olmasını ve Türkçe bir bilimsel açıklamada bu kavramların kullanılmasını gerektiğini düşünmekteyim.

      Sil

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