Pencuplikan Kompresif (2)

Ada dua transformasi penting dalam pencuplikan kompresif, yaitu sparsity transform dan projection transform. Transformasi pertama dipakai untuk mencari komponen sparse dari sinyal, sedangkan yang kedua dipakai dalam operasi pengukuran atau pengamatan. Tulisan ini memberikan contoh sederhana cara melakukan pencuplikan kompresif dan rekonstruksi sinyal secara eksak dari cuplikan terkompresi.

Aspek Penting dalam Pencuplikan Kompresif

Pada pembahasan mengenai dekomposisi sinyal dan pencarian basis ideal, telah dijelaskan cara menemukan vektor basis penyusun suatu sinyal hasil sintesis K buah vektor kamus basis , atau sebuah sinyal K-sparse. Berdasarkan prinsip ketidakpastian yang diperumum, jika jumlah komponen K kurang dari dengan menyatakan koherensi dari kamus basis, maka semua komponen penyusun sinyal akan dapat ditemukan oleh optimisasi terkendala P₁ (basis pursuit). Pada akhir pembahasan ditunjukkan, bahkan ketika sinyal sudah tercampur derau, seluruh komponen masih dapat ditemukan sehingga sinyal dapat direkonstruksi secara eksak.

Pencuplikan kompresif bekerja berdasarkan prinsip yang mirip seperti diatas, yakni: diberikan informasi M buah hasil pengamatan dari sinyal K-sparse, sinyal asal sepanjang N>>M>K akan dapat direkonstruksi jika dengan C bergantung pada sistem basis yang dipilih. Hal yang perlu dicermati disini, jumlah cuplikan yang diperlukan menjadi jauh lebih kecil daripada N, bahkan hanya dalam orde logaritma-nya. Disamping itu, nilai M juga dipengaruhi oleh tingkat sparsity K dari sinyal yang dapat dianggap menggambarkan kandungan informasi dari sinyal yang sebenarnya. Pemilihan kamus-basis akan menentukan kinerja kompresi karena dapat menentukan besar-kecilnya jumlah data cuplikan yang diperlukan. Berdasarkan penjelasan ini, ada beberapa hal penting yang perlu diperhatikan dalam melakukan pencuplikan secara kompresif.

Pertama, sinyal yang akan dicuplik haruslah bersifat K-sparse. Kebanyakan sinyal hasil pengamatan di dunia nyata pada dasarnya adalah sinyal sparse terhadap suatu basis tertentu, meskipun belum tentu demikian di kawasan sinyal tersebut diukur. Sistem basis atau transformasi yang membuat suatu sinyal menjadi bersifat sparse disebut sebagai transformasi penjarang (sparsity transform). Termasuk dalam kategori ini antara lain, berbagai sistem transformasi ortogonal yang telah disinggung pada tulisan-tulisan sebelumnya seperti, DCT, Hadamard, DFT, wavelet, … dll.

Aspek penting kedua adalah observasi atau pengukuran (observation/ measurement). Proses pencuplikan klasik dapat dianggap sebagai proses observasi dari suatu sinyal kontinyu. Secara umum, observasi dapat dinyatakan sebagai proyeksi sinyal pada basis tertentu. Pencuplikan klasik adalah proyeksi dari sinyal kontinyu ke basis impuls, sistem pencitraan SFCW-GPR (stepped-frequency continuous wave ground penetrating radar), MRI (magnetic resonance imaging), dan teleskop VLBI (very large base line interferometry) melakukan observasi data spasio-temporal didalam basis Fourier, sedangkan CT (computed tomography) scanner melakukan observasi dalam kawasan Radon. Sistem basis atau transformasi dimana suatu sinyal diamati disebut sebagai transformasi proyeksi (projection transform).

Yang terakhir, besarnya konstanta C yang akan menentukan jumlah minimum data observasi M berkaitan erat dengan derajat koherensi sistem basis. Kedua macam transformasi yang disebutkan akan menentukan besarnya nilai ini karena yang diukur adalah koherensi antara transformasi penjarang dengan transformasi proyeksi.

Gambar 1. Diagram ranah-jamak [1] dalam sistem pencuplikan kompresif sederhana

Hubungan berbagai transformasi yang terlibat dalam pencuplikan kompresif dilukiskan sebagai diagram ranah-jamak [1] pada Gambar 1. Sinyal s sepanjang N-cuplikan bersifat K-sparse dalam sistem basis . Pencuplikan atau pengamatan akan menghasilkan sinyal yang hanya mengandung sebagian data dari sinyal asalnya karena ada informasi yang hilang, yaitu . Jika jumlah pengamatan mencukupi, meskipun jauh dibawah N, K-buah basis sparse dapat ditemukan melalui P₁. Dengan demikian, karena seluruh basis S dapat ditemukan, maka sinyal asal dapat direkonstruksi secara eksak. Pada diagram ini, transformasi penjarang adalah , sedangkan transformasi proyeksi adalah .

Pencuplikan Kompresif Sederhana

Sebagai ilustrasi, akan ditinjau suatu sinyal s yang bersifat sparse terhadap basis DCT dengan derajat sparsity sebesar 4. Bagaimana cara melakukan pencuplikan kompresif dari sinyal ini dan cara melakukan rekonstruksinya?

Pada kasus ini bisa dipilih suatu basis acak Gaussian yang dinormalisasi sebagai transformasi proyeksi-nya. Karena pencuplikan langsung dari sinyal analog melibatkan beberapa hal teknis yang baru akan dibahas pada tulisan mendatang, anggap bahwa pengamatan ini dapat direpresentasikan sebagai subsampling terhadap sinyal waktu diskrit s sepanjang N-cuplikan. Dengan demikian, tahap pertama yang harus dilakukan adalah membentuk matriks pengamatan atau transformasi proyeksi . Dimensi matriks ini adalah MxN, dimana M<<N adalah jumlah pengamatan yang diharapkan. Berdasarkan teorema pencuplikan kompresif, agar sinyal s bisa direkonstruksi secara eksak, maka jumlah ini minimal-nya adalah sekitar CK log(N).

Berbagai peneliti bidang ini memberi nilai C yang berlainan. Pada umumnya nilai ini sebesar koherensi kamus-basis (yang tak-ternormalisasi), dimana kamus basis adalah perkalian antara matriks proyeksi dengan matriks sparsity, sehingga . Pada percobaan ini akan diambil C=1, dengan demikian yang kemudian menentukan M adalah derajat sparsity (K=4) dan logaritma dari cuplikan Nyquist N. Sebagai contoh diambil N=64, jadi M~17 yang berarti adalah faktor kompresi sekitar 3.8 kalinya.

Gambar 2. Sinyal asli dan sinyal cuplikan kompresif

Gambar 2 menunjukkan sinyal s dan cuplikan kompresif-nya . Terlihat bahwa hasil pencuplikan kompresif memberikan data yang lebih ringkas atau lebih pendek dari sinyal asalnya. Dalam skema pencuplikan yang sedang dibahas, sinyal ini adalah .

Gambar 3. Vektor basis terpilih hasil optimisasi P₁

Rekonstruksi dilakukan dengan terlebih dahulu mencari vektor sparse S dalam kawasan DCT melalui optimisasi P₁:

(P₁): min||S||₁ s.t.

Optimisasi ini memiliki arti: pilihlah vektor S paling sparse dalam basis yang dapat menjelaskan hasil pengamatan . Hasilnya ditampilkan dalam Gambar 3, dimana semua basis terpilih tepat sama dengan basis penyusun sinyal.

Gambar 4. Perbandingan sinyal asli dan hasil rekonstruksi

Rekonstruksi dilakukan dengan menyusun kembali sinyal dari vektor basis terpilih. Hasilnya ditampilkan pada Gambar 4, dimana sinyal rekonstruksi identik dengan sinyal asalnya dan sinyal kesalahan bernilai nol.

Pemilihan basis acak sebagai transformasi proyeksi sangat menguntungkan jika dilihat dari beberapa sisi. Yang pertama, setiap data cuplikan didalam s dapat dianggap sama pentingnya. Dengan demikian tidak perlu skema pencuplikan adaptif dengan memilih komponen dominan saja karena semuanya sama penting. Yang kedua, basis acak bersifat universal karena hampir ortogonal ke semua basis lain. Basis ini bisa diterapkan ke berbagai kasus pencuplikan kompresif. Dan yang terakhir, modulasi dengan basis acak untuk mendapatkan membuat hasil pengamatan sedikit terenkripsi (weakly encrypted). Hal ini sangat menguntungkan jika pencuplikan kompresif akan dipakai didalam sistem sensor tersebar kompresif (distributed compressed sensing) dan data yang diamati bersifat rahasia.

Daftar Pustaka

1. AB Suksmono, “A graphical representation of the multi-domain signal processing,” Proc. of SICE-ICASE 2006, Busan, Korea.

Program Matlab

%———————————————–
%Contoh Pencuplikan Kompresif
%———————————————–
clear;%close all;clc;
N=64; %panjang sinyal
%Pembentukan sinyal 4-sparse
PSI=dct(eye(64,64)); %buat matriks DCT
K_sparse=4;%tingkat sparsity
%pN=randperm(nAtoms);
pN=[3 13 42 58];
x=zeros(N,1);
X=zeros(N,1);%’transformed-domain signal
for k=1:K_sparse;
x=x+(-1)^k*PSI(:,pN(k)); %masukkan faktor polaritas basis
X(pN(k))=1;
end;
x0=x;

%lakukan pengukuran atau subsampling
%estimasikan minimal jumlah cuplikan M>CKlog(N)
mu=1*(1/sqrt(N)); %tentukan koherensi->perkiraan
C=sqrt(N)*mu; %koherensi tak ternormalisasi=sqrt(N).koh
M_sub=ceil(C*K_sparse*log(N))
%bentuk matriks pengukuran
PHI=orth(randn(M_sub,N)’)';
%lakukan pengukuran x_sub=PHI*x
x_sub=PHI*x;
x_sub_xtd=zeros(N,1); x_sub_xtd(1:M_sub)=x_sub(1:M_sub);
figure(1);plot(1:N, x0,’k-’,1:N,x_sub_xtd,’b:’);title(’subsampling’);
legend(‘original’,’sub-samples’); xlabel(‘time’);ylabel(‘amplitude’);
%Lakukan recovery
%Bentuk dictionary D=PHI*PSI
D=PHI*PSI;

[D_row,D_col]=size(D);
D_pos=-D;
%define dictionary A
A=zeros(D_row,2*D_col);
A(:,1:D_col)=D;
A(:,D_col+1:2*D_col)=D_pos;

%Pecahkan P1
f=ones(2*D_col,1);
lb=zeros(2*D_col,1);

%*******************
%alpha1=alpha;
f1=ones(2*D_col,1);
lb1=zeros(2*D_col,1);
A1=-A;
x_sub1=x_sub;
%*******************

alpha0=linprog(f,[],[],A,x_sub,lb); %ambil solusi positif
alpha1=linprog(f1,[],[],A1,x_sub1,lb1); %ambil solusi negatif

alpha=alpha0-alpha1; %gabungkan keduanya
%Tampilkan hasil
figure(2);plot(1:D_col,X,’r.’,1:D_col,abs(alpha(1:D_col)),’b-’);
title(‘extracted dct vectors by P1′);
legend(‘original components’,'extracted components’);
xlabel(‘DCT vector index’);ylabel(‘magnitude’);
%obtain a few largest component, by sorting alpha
[z,imax]=sort(abs(alpha(1:D_col)),’descend’);
%Reconstruct the estimated values
x_hat=zeros(N,1);
for k=1:K_sparse;
x_hat=x_hat+alpha(imax(k))*PSI(:,imax(k));
end;
figure(3);plot(1:N,x0,’k.’,1:N,x_hat,’r:’,1:N,x0-x_hat,’b-’);
xlabel(‘time’);ylabel(‘amplitude’);
legend(‘original’,'reconstructed’,'error’);

Pencuplikan Kompresif (1)

Pencuplikan adalah salah satu proses terpenting dalam tahapan pengolahan sinyal dijital, dimana sinyal analog diubah menjadi sinyal diskrit (dijital). Teorema pencuplikan Shannon menetapkan aturan batas minimal laju pencuplikan agar sinyal dapat direkonstruksi ke asalnya, yakni sebesar dua kali lebar-pita dari sinyal. Berdasarkan paradigma pencuplikan kompresif, aturan ini dapat dilanggar karena yang berperanan dalam menentukan rekonstruktivibilitas bukanlah kandungan frekuensi sinyal, melainkan kandungan informasinya yang tercermin dalam derajat sparsity.

Batas Nyquist untuk Pencuplikan Sinyal

Didalam Pengolahan sinyal dijital, pencuplikan (sampling) adalah proses mengambil cuplikan dari sinyal analog secara periodik. Proses ini dapat dinyatakan sebagai perkalian antara sinyal analog dengan deretan impuls , dimana n adalah bilangan bulat dan T adalah perioda pencuplikan. Besaran yang lebih populer dibandingkan dengan T, yaitu kecepatan pencuplikan atau fekuensi pencuplikan .

Seperti yang tergambar didalam blok diagram pengolahan sinyal dijital, pita frekuensi dari sinyal akan terlebih dahulu dibatasi (bandlimited) dengan sebuah tapis anti-aliasing sebelum pencuplikan dilakukan. Secara matematis, proses pencuplikan dapat dirumuskan sebagai perkalian antara (modulasi) sinyal analog dengan sebuah deretan impuls

(1)

Gambar 1 menjelaskan proses pencuplikan yang dilihat dari kawasan waktu. Tinjauan kawasan waktu berguna untuk melihat terbentuknya sinyal waktu diskrit (dijital) dan aspek pencuplikan selang-seragam (uniform sampling) terhadap keluarannya. Namun demikian, untuk mengetahui persyaratan laju pencuplikan minimum atau selang pencuplikan maksimum agar sinyal s_a(t) dapat diperoleh kembali, maka proses ini perlu dilihat dari kawasan frekuensi.

Gambar 1. Pandangan proses pencuplikan dari kawasan waktu.

Ekspresi suatu sinyal dalam kawasan frekuensi dapat diperoleh melalui transformasi Fourier dari persamaan dalam kawasan waktu-nya. Karena perkalian dalam kawasan waktu ekivalen dengan konvolusi dalam kawasan frekuensi, maka hasil transformasi Fourier dari persamaan (1) adalah

(2)

Gambar 2 memperlihatkan proses pencuplikan jika dilihat dari kawasan frekuensi. Karena transform Fourier dari deretan impuls adalah juga suatu deretan impuls, maka konvolusi antara spektrum sinyal dengan impuls menghasilkan pergeseran spektrum sejauh . Sebagai akibatnya akan terjadi pengulangan (tiling) spektrum di seluruh rentang frekuensi pada posisi kelipatan dari frekuensi pencuplikan. Gambar 2 bagian kiri bawah menunjukkan spektrum dari sinyal yang lebar pitanya yang kemudian mengalami proses tiling akibat proses pencuplikan.

Gambar 2. pencuplikan dilihat dari kawasan frekuensi

Jika jarak antar pengulangan atau grid tiling cukup lebar, seperti diperlihatkan pada Gambar 3 bagian atas, yang juga berarti bahwa frekuensi pencuplikannya cukup besar, maka tidak akan terjadi tumpang tindih antar spektrum yang bertetangga. Kondisi ini disebut sebagai non-aliasing. Selanjutnya sifat keunikan dari transformasi Fourier akan menjamin bahwa sinyal asal dapat diperoleh secara sempurna. Sebaliknya, jika kurang besar, maka akan terjadi tumpang tindih antar spektrum yang mengakibatkan hilangnya sebagian dari informasi. Peristiwa ini disebut aliasing, seperti diperlihatkan pada Gambar 3 bagian bawah. Pada kondisi ini, sinyal tidak dapat lagi direkonstruksi secara eksak.

Gambar 3. Kondisi non-aliasing dan aliasing pada proses pencuplikan

Dengan memahami peristiwa aliasing dalam kawasan frekuensi, maka batas minimum laju pencuplikan atau batas Nyquist dapat diperoleh, yaitu sebesar . Hasil ini durumuskan sebagai teorema Shannon untuk pencuplikan sebagai berikut:

Teorema Pencuplikan Shannon. Suatu sinyal pita-terbatas dengan lebar dapat direkonstruksi secara eksak dari cuplikannya jika laju pencuplikan minimum dua kali dari lebar pita tersebut, atau .

Sebagai contoh, manusia dapat mendengar suara dari frekuensi 20 Hz sampai dengan sekitar 20kHz, artinya lebar pita dari suara yang mampu didengar manusia adalah sekitar 20 KHz. Dengan demikian, pengubahan suara menjadi data dijital memerlukan laju pencuplikan sedikitnya 2×20kHz = 40 kHz atau 40.000 cuplikan/detik supaya sinyal suara dapat direkonstruksi secara sempurna, yang berarti juga kualitas dari suara hasil perekaman dijital dapat dimainkan tanpa distorsi.

Pada teori pencuplikan klasik, rekonstruksi sinyal s_r(t) akan ditempuh dengan cara melakukan konvolusi antara sinyal disktrit s(n) hasil cuplikan, dengan tapis rekonstruksi

(3)

Dengan demikian,

(4)

adalah sinyal terekonstruksi yang diinginkan. Tanggapan impuls dari tapis rekonstruksi pada persamaan (3) diperlihatkan pada Gambar 4 berikut ini.

Gambar 4. Tanggapan impuls dari tapis rekonstruksi

Pencuplikan Sub-Nyquist dengan Compressive Sensing

Teorema pencuplikan Shannon memberikan batas minimal laju pencuplikan atau jumlah cuplikan persatuan waktu supaya sinyal kontinyu dapat direkonstruksi secara eksak. Pencuplikan dibawah laju ini akan mengakibatkan terjadinya distorsi atau cacat aliasing. Apakah ada cara untuk memperkecil batas ini tanpa mengakibatkan distorsi?

Teorema pencuplikan diatas didasarkan pada analisis Fourier, dimana fungsi basis dalam transformasi sinyal berupa fungsi sinusoid dari berbagai frekuensi. Bahkan, makna sebenarnya dari transformasi Fourier adalah penguraian suatu sinyal kedalam basis sinusoid. Batas Nyquist menjaga supaya semua komponen frekuensi tetap utuh didalam hasil cuplikan sehingga sinyal dapat dikembalikan ke bentuk asalnya. Jika basis selain sinusiod dipakai dalam mendekomposisi sinyal, tentu aturan ini akan berubah karena yang sebenarnya menggambarkan kandungan informasi dari sinyal bukanlah lebar pita fekuensi-nya.

Gambar 5. Pencuplikan dan rekonstruksi sebuah impuls

Kaitan antara pencuplikan dan kandungan informasi diperlihatkan pada Gambar 5. Sebuah impuls akan memiliki transform Fourier S(k) yang tersebar ke seluruh kawasan frekuensi. Berdasarkan informasi kandungan frekuensi sinyal, maka seluruh komponen frekuensi didalam S(k) diperlukan untuk merekonstruksi sebuah impuls. Penghilangan sebagian dari cuplikan, dalam gambar diperlihatkan hanya 25% nya saja, akan menghasilkan rekonstruksi yang tak sempurna. Sinyal impuls yang telah terdistorsi akibat hilangnya sebagian dari komponen frekuensi diperlihatkan pada Gambar 5 bagian bawah.

Seandainya diketahui ada satu buah impuls di kawasan waktu diskrit dalam selang 32 cuplikan, berapa banyakkah informasi yang dibutuhkan untuk mendeskripsikan sinyal ini?

Gambar diatas menyatakan bahwa seluruh 32 buah komponen frekuensi perlu. Tetapi yang sebenarnya diperlukan hanya satu buah saja, yaitu posisi dari impuls. Informasi inilah yang sesungguhnya lebih esensial dibandingkan dengan lebar pita frekuensi. Satu buah informasi, dalam hal ini posisi impuls, disebut juga sebagai derajat kebebasan dari sinyal s(n). Dalam terminologi CS, besaran ini dinamakan tingkat sparsity dari sinyal. Dengan demikian, sinyal s(n) diatas adalah sebuah sinyal 1-sparse. Hasil penting dari pencuplikan kompresif dirumuskan dalam teorema berikut ini:

Teorema Pencuplikan Kompresif. Suatu sinyal K-sparse sepanjang N-cuplikan dapat direkonstruksi secara eksak berdasarkan buah cuplikannya, dimana C sebuah konstanta kecil yang nilainya bergantung pada sistem-basis yang digunakan.

Jumlah M ini jauh lebih kecil daripada N didalam teknik pencuplikan klasik. Inilah alasan mengapa pencuplikan kompresif dapat dianggap sebagai pencuplikan Sub-Nyquist. Bagaimana melakukan rekonstruksi sinyal jika cuplikannya jauh lebih kecil dari batas Nyquist? Yang jelas, proses rekonstruksi klasik melalui konvolusi sinyal pengamatan dengan tapis rekonstruksi tidak lagi bisa dipakai.

Referensi

1. D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, 52, 2006, pp.1289-306.
2. E. J. Candes and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Problems, 23 (2007), pp.696-985.
3. E.J. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inf. Theory, Vol. 52, No. 2, Feb. 2006, pp. 489-509.

Kode Matlab

Kode Matlab untuk membuat kurva tanggapan impuls dari tapis rekonstruksi

%MATLAB codes to generate hr(t)

%define sampling period

T = 0.1 ;%0.1 seconds, sampling at 10 Hz

%define time axis

t=-1.0:0.001:1.0; %2 second

hr=sin(pi*t/T)./(pi*t/T);

figure(1);plot(10*t,hr);

xlabel(‘time in Ts’); ylabel(‘hrec’)

title(‘ideal reconstruction filter’);

Kode Matlab untuk melihat pengaruh penghilangan sebagian cuplikan terhadap hasil rekonstruksi sinyal impuls.

%generate an impulse in N=32 sample intervals;

clear;close all; clc;

N=32; s=zeros(N,1);

s(16)=1; %put impulse in the middle

figure(1);stem(s);title(‘Time Domain’);

xlabel(‘time’); ylabel(‘magnitude’);

S=fft(s); %transform s into freq-domain S

figure(2); stem(abs(S));title(‘Frequency Domain’);

xlabel(‘time’); ylabel(‘magnitude’);

%discard some 25% of the components

S1=S; for k=1:round(N/4); S1(4*k)=0;end;

s1=ifft(S1); %signal inversion by IDFT

figure(3); stem(abs(S1));title(‘Frequency Domain’);

xlabel(‘time’); ylabel(‘magnitude’);

figure(4);stem(abs(s1));title(‘Time Domain’);

xlabel(‘time’); ylabel(‘magnitude’);