Menerapkan algoritma kertas teknis dalam C ++ atau MATLAB

Saya seorang mahasiswa Teknik Elektro. Saya sudah membaca banyak makalah teknis tentang algoritma pemrosesan sinyal dan gambar (rekonstruksi, segmentasi, pemfilteran, dll). Sebagian besar algoritma yang ditunjukkan dalam makalah ini didefinisikan dari waktu ke waktu dan frekuensi terus menerus, dan sering memberikan solusi dalam hal persamaan yang rumit. Bagaimana Anda menerapkan kertas teknis dari awal dalam C ++ atau MATLAB untuk mereplikasi hasil yang diperoleh dalam kertas tersebut?

Lebih khusus lagi, saya melihat kertas "Algoritma rekonstruksi kerucut umum" oleh Wang et al ( IEEE Trans Med Imaging. 1993; 12 (3): 486-96 ), dan saya bertanya-tanya, bagaimana saya memulai mengimplementasikan algoritma mereka? Persamaan 10 memberi Anda rumus gambar yang direkonstruksi di. Bagaimana Anda membuat kode itu? Apakah Anda memiliki for-loop melalui masing-masing voxel dan menghitung formula yang sesuai? Bagaimana Anda memberi kode fungsi fungsi dalam rumus itu? Bagaimana Anda mengevaluasi fungsi pada titik-titik yang berubah-ubah?

Saya sudah membaca buku "Pemrosesan Gambar Digital" oleh Gonzalez dan Woods tapi saya masih bingung. Saya juga membaca tentang seri buku Resep Numerik. Apakah itu cara yang benar?

Apa pengalaman Anda algoritma pemrograman dari makalah penelitian? Ada tips atau saran?

Algoritma pemrosesan sinyal yang didefinisikan dalam waktu / ruang / frekuensi kontinu biasanya diimplementasikan dengan mengambil sampel sinyal pada kisi-kisi diskrit dan mengubah integral menjadi jumlah (dan turunannya menjadi perbedaan). Filter spasial diimplementasikan melalui konvolusi dengan kernel konvolusi (yaitu jumlah tetangga tertimbang).

Ada banyak sekali pengetahuan tentang memfilter sinyal waktu-domain sampel; filter time-domain diimplementasikan sebagai filter respon impuls terbatas , di mana sampel keluaran saat ini dihitung sebagai jumlah tertimbang dari sampel input N sebelumnya; atau filter respon impuls tak terbatas, di mana output saat ini adalah jumlah tertimbang dari input sebelumnya dan output sebelumnya . Secara formal, filter waktu diskrit dijelaskan menggunakan z-transform , yang merupakan analog waktu diskrit dengan transformasi Laplace . The bilinear transform peta satu ke yang lain ( c2ddan d2cdi Matlab).

Bagaimana Anda mengevaluasi fungsi pada titik-titik yang berubah-ubah?

Ketika Anda membutuhkan nilai sinyal pada titik yang tidak terletak langsung di kisi-kisi sampling Anda, Anda menyisipkan nilainya dari titik terdekat. Interpolasi dapat sesederhana memilih sampel terdekat, menghitung rata-rata tertimbang dari sampel terdekat, atau menyesuaikan fungsi analitik rumit yang rumit dengan data sampel dan mengevaluasi fungsi ini pada koordinat yang diperlukan. Interpolasi ke grid yang lebih halus seragam adalah upsampling . Jika sinyal asli Anda (kontinu) tidak mengandung perincian (yaitu frekuensi) yang lebih baik dari setengah kisi pengambilan sampel, maka fungsi kontinu dapat direkonstruksi dengan sempurna dari versi sampel ( teorema pengambilan sampel Nyquist-Shannon ). Untuk contoh bagaimana Anda bisa melakukan interpolasi dalam 2D, lihatinterpolasi bilinear .

Dalam Matlab Anda dapat menggunakan interp1atau interp2untuk menginterpolasi 1D atau secara teratur mengambil sampel data 2D (masing-masing), atau griddatauntuk menginterpolasi dari data 2D yang diambil secara tidak teratur.

Apakah Anda memiliki for-loop melalui masing-masing voxel dan menghitung formula yang sesuai?

Ya persis.

Matlab menyelamatkan Anda dari keharusan melakukan ini melalui for-loop eksplisit karena ia dirancang untuk beroperasi pada matriks dan vektor (yaitu array multidimensi). Dalam Matlab ini disebut "vektorisasi". Integral tertentu dapat didekati dengan sum, cumsum, trapz, cumtrapz, dll

Saya sudah membaca buku "Pemrosesan Gambar Digital" oleh Gonzalez dan Woods tapi saya masih bingung. Saya juga membaca tentang seri buku Resep Numerik. Apakah itu cara yang benar?

Ya, Resep Numerik akan menjadi awal yang baik. Ini sangat praktis dan mencakup sebagian besar metode numerik yang akhirnya Anda perlukan. (Anda akan menemukan bahwa Matlab sudah mengimplementasikan semua yang Anda butuhkan, tetapi Numerical Recipes akan memberikan latar belakang yang sangat baik.)

Saya telah mengambil kelas "algoritma dan struktur data", tetapi saya tidak melihat hubungan antara materi yang disajikan di sana dan menerapkan algoritma ilmiah.

Materi yang diperlakukan dalam kursus "Algoritma dan struktur data" cenderung berkonsentrasi pada struktur seperti daftar, array, pohon, dan grafik yang mengandung bilangan bulat atau string dan operasi seperti menyortir dan memilih: masalah yang biasanya ada satu hasil yang benar. Ketika datang ke algoritma ilmiah, ini hanya setengah dari cerita. Setengah lainnya menyangkut metode untuk memperkirakan bilangan real dan fungsi analitik. Anda akan menemukan ini dalam kursus "Metode Numerik" (atau "Analisis Numerik"; seperti ini- gulir ke bawah untuk slide): cara memperkirakan fungsi khusus, cara memperkirakan integral dan turunannya, dll. Di sini salah satu tugas utama adalah memperkirakan keakuratan hasil Anda, dan satu pola umum adalah untuk mengulangi rutin yang meningkatkan memperkirakan sampai cukup akurat. (Anda mungkin bertanya pada diri sendiri bagaimana Matlab tahu bagaimana melakukan sesuatu yang sederhana seperti memperkirakan nilai sin(x)untuk beberapa orang x.)

Sebagai contoh sederhana, berikut ini adalah skrip pendek yang menghitung transformasi radon dari sebuah gambar di Matlab. Transformasi radon mengambil proyeksi gambar di atas sekumpulan sudut proyeksi. Alih-alih mencoba menghitung proyeksi sepanjang sudut sewenang-wenang, saya malah memutar seluruh gambar menggunakan imrotate, sehingga pengambilan proyeksi selalu vertikal. Kemudian kita dapat mengambil proyeksi hanya menggunakan sum, karena summatriks mengembalikan vektor yang berisi jumlah dari setiap kolom.

Anda dapat menulis sendiri imrotatejika Anda suka, menggunakan interp2.

%%# Home-made Radon Tranform

%# load a density map (image).  
A = phantom;

n_pixels = size(A, 1);  %# image width (assume square)

%# At what rotation angles do we want to take projections?
n_thetas = 101;
thetas = linspace(0, 180, n_thetas);

result = zeros(n_thetas, n_pixels);

%# Loop over angles
for ii=1:length(thetas)
    theta = thetas(ii);
    rotated_image = imrotate(A, theta, 'crop');
    result(ii, :) = sum(rotated_image);
end

%# display the result
imagesc(thetas, 1:n_pixels, result.');
xlabel('projection angle [degrees]');

Apa yang tadinya merupakan bagian integral dari kerapatan sepanjang sinar sekarang adalah jumlah di atas kolom gambar sampel yang diambil secara terpisah, yang pada gilirannya ditemukan dengan menginterpolasi gambar asli melalui sistem koordinat yang diubah.

Menambahkan ke penjelasan nibot yang luar biasa , hanya beberapa poin lagi.

• Lingkungan komputasi numerik seperti MATLAB, Octave atau SciPy / NumPy akan menghemat banyak usaha dibandingkan dengan melakukannya sendiri dalam bahasa pemrograman generik seperti C ++. Menyulap dengan doublearray dan loop hanya tidak bisa dibandingkan dengan memiliki tipe data seperti angka kompleks dan operasi seperti integral di ujung jari Anda. (Ini bisa dilakukan dengan pasti, dan kode C ++ yang baik dapat menjadi urutan besarnya lebih cepat, dengan abstraksi dan templat perpustakaan yang baik bahkan bisa cukup bersih dan jelas, tetapi jelas lebih mudah untuk memulai dengan misalnya MATLAB.)

• MATLAB juga memiliki "toolkit" untuk mis. Pemrosesan Gambar dan Pemrosesan Sinyal Digital , yang mungkin banyak membantu, tergantung pada apa yang Anda lakukan.

• Digital Signal Processing Mitra adalah buku yang bagus untuk dipelajari (dalam MATLAB!) Dasar-dasar waktu diskrit, filter, transformasi, dll. Yang merupakan pengetahuan wajib untuk melakukan algoritma teknis yang layak.

Metode numerik. Ini biasanya kursus universitas dan buku teks universitas divisi atas.

DSP biasanya dekat persimpangan metode numerik dan implementasi yang efisien. Jika Anda mengabaikan efisiensi, maka yang mungkin Anda cari adalah metode aproksimasi numerik apa pun yang mungkin menghasilkan hasil "cukup akurat" untuk persamaan kepentingan makalah teknis. Kadang-kadang orang mungkin berurusan dengan data sampel, di mana teorema pengambilan sampel akan memberi batasan pada metode akuisisi data (pra-filtering) dan kisaran atau kualitas hasil yang Anda dapatkan dari data tersebut.

Terkadang Matlab, resep numerik, atau berbagai pustaka pemrosesan gambar / sinyal akan memiliki algoritma atau kode yang efisien untuk solusi numerik yang diinginkan. Tetapi kadang-kadang Anda mungkin harus memutar sendiri, sehingga membantu untuk mengetahui matematika di balik berbagai metode solusi numerik. Dan itu adalah subjek yang besar dengan sendirinya.