Teknik Kompresi data dengan COMPRESSIVE SENSING

Print Friendly, PDF & Email

Compresive sensing merupakan topik pembahasan yang dikenal dari pengolahan sinyal digital (digital image processing), dengan tumbuh cepatnya data, maka dibutuhkan sebuah teknik kompresi yang lebih baik. Ide dasar dari CS yaitu mengenai perkalian sebuah matrix secara linear.

x \in \Re^{n} adalah sinyal

Phi\in \Re^{m \cdot n} adalah nilai random, dan

y \in \Re^{m} disebut hasil compresi dengan persamaan berikut

    \[y=Phi \cdot x\]

Untuk mendapatkan nilai x kembali, maka cukup

    \[x = Phi^{-1} \cdot y\]

dengan syarat m < n.

Kalian bisa bayangkan, jika x(10000,1) mempunyai ukuran n=10000, maka bisa direduksi menjadi y(100,1).

Tapi apa yang terjadi jika Phi bukanlah square matrix? sehingga akan sulit dicari nilai invers(Phi) atau dilambangkan dengan Phi^{-1}, maka yang kalian butuhkan adalah function Moore-Penrose pseudoinverse yaitu

  1. Python : https://numpy.org/doc/stable/reference/generated/numpy.linalg.pinv.html
  2. matlab: https://www.mathworks.com/help/matlab/ref/pinv.html

Compres

Agar lebih paham, kalian bisa lihat berikut yaitu sinyal x mempunyai panjang 28 akan di kompres menjadi m = 16 saja

x =

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28

Compress

y =

  210.6920
  150.4647
  184.0508
  209.3858
  197.0023
  206.7937
  194.0519
  186.5565
  205.4035
  226.7545
  199.3873
  230.8093
  228.5523
  181.2891
  230.2884
  202.0982

>>

Lebih jelasnya lihat kode berikut

clc;clear all;close all;
A = 1:28;
x = A(:) %dibuat vector dengan ukuran (n,1)
n = length(x);
m = 16; %misalkan m = 16
Phi = rand(m,n); %generate random
disp('Compress');
y = Phi*x %hasil  compress

Melalui kode diatas didapatkan bahwa

    \[y=Phi \cdot x\]

Sehingga untuk mencari nilai x cukup dengan persamaan

    \[x=Phi^{-1} \cdot y\]

Tapi apa yang terjadi ketika proses rekonstruksi diatas dijalankan?

x_hat = pinv(Phi)*y

Hasilnya tidak seperti yang diharapkan! Ternyata \hat{x}  tidak sama dengan x padahal sudah dilakukan invers matrix!

atau kalian bisa lakukan cek perkalian berikut

    \[eye = Phi^{-1} \cdot Phi\]

kode dalam matlab yaitu

pinv(phi)*phi

eye adalah matrix identitas, jadi hasil daripinv(phi) sudah betul!

L1 Norm Minimisasi

Kalian butuh yang namanya L1 yang bisa kalian pelajari melalui referensi

  1. https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/journal/paperinformation.aspx?paperid=56972 dengan judul “Compressive Sensing Algorithms for Signal Processing Applications: A Survey”
  2. Theory of compressive sensing via ‘L1-minimization a non-rip analysis and extensions oleh yin zhang

Kalian bisa melihat A dengan ukuran 7 x 5 dapat dicompres menjadi y  ukuran 4 x 4 saja dengan hasil extract mempunyai perbedaan sebesar 0.6054

A =

     1     8    15    22
     2     9    16    23
     3    10    17    24
     4    11    18    25
     5    12    19    26
     6    13    20    27
     7    14    21    28

Compress
y =

  223.1871  241.8109  217.7096  198.4034
  196.6528  178.9742  189.6390  152.6269
  224.3557  229.8989  179.9579  176.0807
  179.6694  165.2379  211.5647  262.8088

Extract

xp =

    1.2857    8.0390   14.9550   21.7828
    2.0381    8.7984   15.9168   22.9610
    3.0816    9.9890   17.0175   24.0220
    4.0081   10.9803   17.9020   25.0883
    4.9590   12.1692   19.1690   26.1044
    5.9426   13.0946   19.9268   27.0004
    6.9885   14.0698   20.8066   27.8311


difference =

    0.6054

    keterangan    dimensi
    __________    _______

    'A'             28   
    'Compress'      16   
    'Extract'       28   

>>

Contoh berikut hasil saya run menggunakan sinyal sinus yang terdiri dari sampling 2.500 dapat diperkecil menjadi 100 saja, kemudian di extract kembali menjadi 2.500 dengan nilai perbedaan hanya 1.5 saja

Penulis juga mencoba untuk menggunakan image dengan ukuran 100 x 100

tantangan terbesar yaitu terletak pada proses extract yang membutuhkan waktu yang cukup lama

One thought to “Teknik Kompresi data dengan COMPRESSIVE SENSING”

Leave a Reply

Your email address will not be published. Required fields are marked *