Sıkıştırılmış Sinyallerin Geri Çıkarımı

SIKIìTIRILMIì SİNYALLERİN GERİ ÇIKARIMI

Prof. Dr. Arif Nacaroğlu Gaziantep Üniversitesi

Sinyal ve görüntü işleme uygulamalarında görüntü veya diğer işaretlerin elde edilmesi, iyileştirilmesi ve yeniden oluşturulması, saklanması; özellikle analog dünyadan sayısal dünyaya geçilmesi ile büyük önem kazandı, ancak beraberinde de birçok yeni sorunlar getirdi. Görüntünün analog olarak elde edilmesi ve basılması bizim hemen hemen gerçeğe yakın bilgi edinmemizi sağladı. Ancak kimyasal olarak gerçekleştirilen bu işlemle elde edilen görüntü ve hareketli görüntüler üzerinde renk, parlaklık gibi işlemler yapılabilmesi çok zordu.

Son yıllarda bilgisayar kapasiteleri ve hızlarındaki olağanüstü artış, analog bilgi üzerinde yapamadığımız birçok işi yapmamızı sağlamasına rağmen bilginin de olağanüstü artması, bilgilerin (ses, görüntü, radar, mr, video, v.s.) oldukları gibi değil kodlanarak, küçültülerek saklanması ve işlenmesi gerekliliğini beraberinde getirdi. Ve birçok bilim ve teknoloji insanının ilgilerini bu konuya çevirmelerine sebep oldu.

İlk olarak Candes ve arkadaşları [1-3] n-boyutlu bir vektöre yüklenmiş bilginin bazı özellikleri taşıması durumunda,

satır sayısı daha az (m) olan ve rastgele elde edilen bir

matriks yeni bir

ilme -(bHomyxunt)luçavrepkıltaörradkeknüçgüelrtiüelmldeesieidleileebldileeceedğilienni

gösterdiler. Yaklaşımlarındaki mantık, n uzunluğundaki

bilgi vektörünün (görüntü bilgisinin satır satır dizilmesi

ile elde edilen vektör) m uzunluğunda (m<<n) bir vektöre

dönüştürülmesi ve sonra bu çarpımı sağlayan orijinal bilgi

vektörünün (f) belli bir algoritma ile denenerek ne olabileceğinin bulunmasıydı. Ardından birçok bilim insanı [4]

bu yaklaşımın geliştirilmesi ve yapılan varsayımların en aza

indirilmesi için yoğun bir çalışma içerisine girdiler. Diğer

bir grup ise [5] az bilgiden orijinal bilginin en hızlı ve en

doğru nasıl elde edilebileceğine ilişkin çalışmalar yaparak

yeni algoritmalar geliştirdiler.

Sayısal ortamda gerçekleştirilen uygulama çalışmalarında gerek sayıların taban dönüşümünden, gerek diğer sebeplerden oluşan gürültünün, bilginin yeniden oluşturulmasındaki etkilerinin araştırılması ve işlemin hızlanması, bilginin yeniden elde edilebilme şartlarını kaybetmeden inebilecek en kısa vektör uzunlukları, bilginin bir kısmının önceden biliniyor olmasının geri oluşturmaya olumlu katkıları, uygulanacak geri oluşturma algoritmalarının matematiksel özellikleri gibi birçok konu halen konu ile uğraşan bilim insanlarının dikkatini çekmektedir.

Matematiksel Altyapı

Sayısal bilgi n-uzunluğunda bir f vektörü ile tanımlanmış olsun. Burada f, ses gibi tek boyutlu bilgiler için sürekli bilgiden

alınmış ve esas olarak en az örnekleme hızından daha hızlı

alınmış örneklerin büyüklüklerinin oluşturduğu bir vektör

olabileceği gibi, belli sayısal dönüşümler (Fourier, Dalgacık, Kosinüs) uygulanarak elde edilen katsayıların oluşturduğu

bir vektör bilgisi de

osalatıbrilsira.tıMr adtirziiklesrşeekkllixnl=del2ebldoeyuedtliulefnvGeklxtlögröürüenldtüe

edilir. ìimdi elimizde tüm bilgiden alınan ve analog bilginin geri çıkarımını sağlayacak n-boyutlu bir f vektörü vardır.

Saniyede 8 bin örnek alınarak ayrıklaştırılmış 1 dakikalık konuşma için 480 bin, periyodu 10 mikrosaniye ile örneklenmiş 3 dakikalık bir müzik parçası için 18 milyon örnek alınarak f vektörü oluşturulur. Bu boyut, görüntü bilgisi için çok daha fazladır.

Sayısal bilgilerin iyileştirilmesi, süzülmesi gibi işlemler de

göz önüne alındığında bilginin bu boyutu ile saklanması ve

işlenmesi; hem kapasite hem zaman olarak ciddi sorunları

da beraberinde getirecektir. Bu nedenle matriksi ile çarpılarak g vektörü elde edilir.

Hf vreaksttögreüleHelmdxen

edilen m (m<<n) boyutlu bir ölçüm matriksidir.

=

g=

H

f

H matriksinin elde edilmesinde, Gaussian, (bağımsız eş dağılımlı (independent identically distributed-iid) Gauss Beyaz Gürültü (GWN) elemanlı), Rademacher (iid +1, -1 elemanlı), Fourier (satırları rastgele seçilen) gibi yöntemler kullanılır. ìimdi bilgi taşıyan vektörün boyutu küçülmüş, ancak başka bir problem ortaya çıkmıştır. Elde edilen m denklemden (g), n bilinmeyen (f) bulunmalıdır ve temelde deneme yanılma gibi bir işlemle karşı karşıyayızdır. H matriksi kare matriks olmadığından tersi de yoktur. Yapılması gereken önce rastgele bir f vektörü oluşturmak ve bu vektörün g-Hf=0 denklemini sağlayıp sağlamadığına bakmaktır. Eğer f vektörü bu şartı sağlıyor olsaydı, f=f , yani orijinal bilgi olacaktı. Bu ilk denemede f vektörünün bulunması neredeyse imkansızdır. Bu nedenle sonuçtan uzaklaşmadan ve her denemede f’in f’ye daha da yaklaştığı bir mantık geliştirilmelidir. Bu nedenle g-Hf=0 denklemini sağlayacak f vektörünü deneyerek bulmak, yerini (g-Hf)vektörünün mümkün olduğu kadar 0’a yaklaştırılması işlemine bırakır. (g-Hf) vektörünün değerinin küçültülmesi göreceli bir kavramdır ve esas hedef tüm elemanlarının 0 yapılmasıdır. Bu şartın sağlanması bazı zorlukları da beraberinde getirdiğinden (g-Hf) vektörünün küçültülmesi için seçilen çok küçük H için sıfır yapılma (0norm) dışında özellikle vektörün enerjisi ile ilgili başka tanımlar (Norm-1, Norm-2 gibi) yapılabilir. Yani vektörün tüm elemanları 0 yapılmaktansa, elemanların toplamları, elemanların karelerinin toplamlarının karekökü gibi değişik küçültme yöntemleri kullanılabilir. H sayısının ne kadar

küçültülebileceği f vektörünün seyrekliğiyle (birçok elemanının sıfır olması veya kabul edilmesi), bazı elemanlarının önceden bilinmesiyle doğrudan ilişkilidir ve [6, 7] numaralı kaynaklarda kapsamlı olarak verilmektedir. İlave edilmesi gereken bir diğer nokta da f vektörünü küçültmek (g) için kullanılan ölçüm matriksi H’nin elde edilmesi ile ilgilidir. H matriksi Gauss dağılımı kullanılarak rastgele elde edilmektedir, ancak geri çıkarım için H matriksinin [6] numaralı referansta verilen bazı özelliklere sahip olması gerekir.

Seyreklik ve Bilinirlik g vektöründen geri elde edilmesi istenen f bilgi vektörünün geri elde edilebilmesi için seyrek olması gerekmektedir. f vektörünün zaman domeynindeki veya uygun bir dönüşümle (Fourier, Kosinüs, Dalgacık, gibi) elde edilen karşılığı, ortogonal bir domeyndeki değeri genellikle seyrektir. Geri çıkarımı istenen f bilgisi K-seyrektir (K: sıfırdan farklı eleman sayısı). Seyreklik alt sınırı [8] numaralı kaynakta kapsamlı şekilde verilmiştir. Buraya kadar verilen yaklaşımda, bilgi işaretinin küçültülmesi sırasında oluşabilecek gürültüler yok sayılmıştır. Ancak küçültme işlemi sırasında iki çeşit nedenden dolayı g işareti bozulmuş olabilir. Eklenen ve bozan gürültü olarak tanımlanabilecek bu gürültüler denklemlere g=H f + e (eklenen gürültü, e), g=(H+E) f (bozulma, E:sapma matriksi) veya her ikisi birden şeklinde ilave edilir ve yukarıda verilen geri çıkarım şartlarını etkiler [7].

Örnek ìekil 1’de görülen renkli Ferit, n=3686400 uzunluğunda bir vektöre dönüştürülmüş, önce sayısal dalgacık dönüşümü kullanılmış (dwt) ve seyrekleştirilmiştir. Geri elde edilmesinde bilginin yüzde 20’sinin bilindiği varsayılarak ve p=0.5 için geri çıkarım algortiması çalıştırılmış ve görüntü neredeyse orijinale yakın elde edilmiştir. Siyah-Beyaz Ferit benzer işlemlerle (ìekil 2) önce dönüşüm kullanılarak sıkıştırılmış ve sonra farklı bilinme oranı (s), farklı seyreklik sayıları (k) ve farklı optimizasyon katsayıları (p) kullanılarak geri elde edilmesi incelenmiştir.

ìekil 1: a) Orijinal Ferit, b) Farklı seyreklik, bilinirlik ve m değeri ile küçültülüp, farklı norm değerleri ile geri kazanılmış Feritler.

ìekil 2: (a) Siyah-Beyaz Ferit, (b) Farklı m, s, k, p değerleri

için küçültülüp, geri kazanılan Ferit’ler

Sonuç

2D ve 3D görüntü sıkıştırma ve geri çıkarıma ilişkin çalışmalar özellikle son yılllarda ivme kazandı. Görüntü işleme uygulamalarında yüz tanımadan, hareketli görüntülerin işlenmesine, tıp uygulamalarına, askeri uygulamalara kadar geniş bir alanda teorik ve uygulama çalışmaları yapılıyor. Büyük boyutlu bilgilerin küçültülerek saklanması ve işlenmesi, geri çıkarılması için çok sayıda çalışma yapılmakta. Özellikle geri kazanımda, küçültme işlemleri kadar geri çıkarım algoritmaları da geliştirilmeye çalışılıyor. Bu alanlarda, aşağıdaki konularda çalışmalar halen daha da geliştirilmeyi bekliyor:

• Uygun H matriksinin oluşturulması, RIP şartlarının geliştirilmesi (daha düşük m) • Çarpım ve eklenen gürültülerin etkileri • Bilginin seyrekliği, k • Bilginin bir kısmının önceden biliniyor olması, s •En azı bulma (minimizasyon) algoritmalarında farklı norm tanımları • Tüm bu parametrelerin çapraşık olarak değiştirilmesi ve nihayetinde bilgiyi en az bilgi ile en çabuk ve en doğru şekilde elde etme.

Kaynaklar [1] EJ Candès, J Romberg, T Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”, Information Theory, IEEE Transactions on 52 (2), 489-509, 2006. [2] EJ Candès, MB Wakin, “An introduction to compressive sampling”, Signal Processing Magazine, IEEE 25 (2), 21-30, 2008 [3] EJ Candes, T Tao, “Near-optimal signal recovery from random projections: Universal encoding strategies?” Information Theory, IEEE Transactions on 52 (12), 5406-5425, 2006 [4] Z. Dong, W. Zhu, “An improvement of the penalty decomposition method for sparse approcimation”, Signal Processing, 113, (2015), 52-60. [5] Y. Pang, X. Jiang, X. Li, J. Pan, “Efficient object detection by prediction in 3D space”, Signal Processing, 112 (2015), 64-73. [6] T. Ince, A. Nacaroğlu, N. Watsuji, “Nonconvex compressed sensing with partially known signal support”, Signal Processing, 93 (2013), 338-344 [7] T. Ince, A. Nacaroğlu, “On the perturbation of measurement matrix in non-convex compressed sensing”, Signal Processing, 98 (2014), 143-149 [8] M. E. Lopea, “Estimating unkonwn sparsity in compressed sensing”, Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013.JMLR: W&CP volume 28.