Bagaimana Konvolusi Dapat Dinyatakan sebagai Perkalian Matriks (Bentuk Matriks)?

11

Saya tahu pertanyaan ini mungkin tidak terlalu relevan dengan pemrograman, tetapi jika saya tidak mengerti teori di balik pemrosesan gambar saya tidak akan pernah bisa mengimplementasikan sesuatu dalam praktiknya.

Jika saya benar, filter Gaussian berbelit-belit dengan gambar untuk pengurangan noise karena mereka menghitung rata-rata lingkungan piksel yang ditimbang dan mereka sangat berguna dalam deteksi tepi, karena Anda dapat menerapkan blur dan mendapatkan gambar pada saat yang sama dengan hanya berbelit-belit dengan turunan dari fungsi Gaussian.

Tetapi adakah yang bisa menjelaskan saya, atau memberi saya beberapa referensi tentang bagaimana mereka dihitung?

Misalnya detektor tepi Canny berbicara tentang filter Gaussian 5x5, tetapi bagaimana mereka mendapatkan angka-angka tertentu? Dan bagaimana mereka beralih dari konvolusi kontinu ke perkalian Matriks?

image-processing filtering gradient edge-detection Matteo
sumber
dsp.stackexchange.com/questions/2969/…
Andrey Rubshtein
Saya menambahkan jawaban dengan kode lengkap untuk menghasilkan matriks untuk Konvolusi Gambar.
Royi

Jawaban:

3

Agar operasi ini berfungsi, Anda perlu membayangkan bahwa gambar Anda dibentuk kembali sebagai vektor. Kemudian, vektor ini dikalikan di sebelah kirinya oleh matriks konvolusi untuk mendapatkan gambar yang kabur. Perhatikan bahwa hasilnya juga merupakan vektor dengan ukuran yang sama dengan input, yaitu gambar dengan ukuran yang sama.

Setiap baris matriks konvolusi sesuai dengan satu piksel pada gambar input. Ini berisi bobot kontribusi semua piksel lain dalam gambar ke mitra kabur dari piksel yang dipertimbangkan.

3×36×636×36

  • Mari init matriks ini ke 0 di mana-mana.
  • (i,j)1/9(i−1,j−1);(i−1,j),(i−1,j+1),…,(i+1,j+1)
  • (i,j)6∗i+j1/9(6i+j)
  • Lakukan hal yang sama dengan semua piksel lainnya.

Ilustrasi visual dari proses yang berkaitan erat (konvolusi + pengurangan) dapat ditemukan di posting blog ini (dari blog pribadi saya).

sansuiso
sumber
sebuah tautan mati.
gauteh
2

Untuk aplikasi ke gambar atau jaringan konvolusi, untuk lebih efisien menggunakan pengganda matriks dalam GPU modern, input biasanya dibentuk kembali menjadi kolom-kolom matriks aktivasi yang kemudian dapat dikalikan dengan beberapa filter / kernel sekaligus.

Lihat tautan ini dari Stan2's CS231n, dan gulir ke bawah ke bagian "Implementasi sebagai Penggandaan Matriks" untuk detailnya.

Proses ini bekerja dengan mengambil semua tambalan lokal pada gambar input atau peta aktivasi, yang akan dikalikan dengan kernel, dan merentangkannya ke dalam kolom matriks X baru melalui operasi yang biasa disebut im2col. Kernel juga diregangkan untuk mengisi baris-baris dari matriks bobot W sehingga ketika melakukan operasi matriks W * X, matriks yang dihasilkan Y memiliki semua hasil konvolusi. Akhirnya, matriks Y harus dibentuk kembali lagi dengan mengubah kolom kembali menjadi gambar dengan operasi yang biasanya disebut cal2im.

Rodrigo
sumber
1
Ini tautan yang sangat bagus, terima kasih! Namun adalah praktik yang baik untuk menambahkan ekstrak penting dari tautan ke dalam jawaban, dengan cara ini jawabannya valid bahkan jika tautan rusak. Harap pertimbangkan untuk mengedit jawaban Anda agar diterima!
Matteo
1

Konvolusi dalam domain Waktu sama dengan perkalian matriks dalam domain frekuensi dan sebaliknya.

Penyaringan setara dengan konvolusi dalam domain waktu dan karenanya penggandaan matriks dalam domain frekuensi.

Adapun peta atau topeng 5x5, mereka datang dari mendiskreditkan operator canny / sobel.

Naresh
sumber
2
Saya tidak setuju dengan kenyataan bahwa penyaringan adalah konvolusi dalam domain frekuensi. Jenis filter yang kita bicarakan di sini adalah konvolusi dalam domain spasial (yaitu, perkalian elemen-bijaksana dengan respons filter dalam domain frekuensi).
pichenettes
Terima kasih telah memperbaiki apa yang saya tulis. Saya membuat suntingan berikutnya. Saya kira saya harus memeriksa ulang jawaban saya sebelum memposting. Namun, sebagian besar jawaban saya masih berlaku.
Naresh
Transformasi Fourier memang mengubah konvolusi menjadi multiplikasi (dan sebaliknya). Namun, mereka adalah perkalian pint bijaksana, sedangkan pertanyaannya adalah tentang perkalian matriks-vektor yang diperoleh dengan membentuk kembali gambar.
sansuiso
Saya memang menyebutkan bagaimana mendiskritasikan operator adalah alasan matriks 5x5 diperoleh untuk operator canny / sobel.
Naresh
1

Saya menulis sebuah fungsi yang memecahkan ini dalam StackOverflow Q2080835 GitHub Repository saya (Lihat CreateImageConvMtx()).
Sebenarnya fungsi tersebut dapat mendukung bentuk konvolusi yang Anda inginkan - full, samedan valid.

Kode tersebut adalah sebagai berikut:

function [ mK ] = CreateImageConvMtx( mH, numRows, numCols, convShape )

CONVOLUTION_SHAPE_FULL  = 1;
CONVOLUTION_SHAPE_SAME  = 2;
CONVOLUTION_SHAPE_VALID = 3;

switch(convShape)
    case(CONVOLUTION_SHAPE_FULL)
        % Code for the 'full' case
        convShapeString = 'full';
    case(CONVOLUTION_SHAPE_SAME)
        % Code for the 'same' case
        convShapeString = 'same';
    case(CONVOLUTION_SHAPE_VALID)
        % Code for the 'valid' case
        convShapeString = 'valid';
end

mImpulse = zeros(numRows, numCols);

for ii = numel(mImpulse):-1:1
    mImpulse(ii)    = 1; %<! Create impulse image corresponding to i-th output matrix column
    mTmp            = sparse(conv2(mImpulse, mH, convShapeString)); %<! The impulse response
    cColumn{ii}     = mTmp(:);
    mImpulse(ii)    = 0;
end

mK = cell2mat(cColumn);


end

Saya juga membuat fungsi untuk membuat Matriks Penyaringan Gambar (Ide serupa dengan MATLAB imfilter()):

function [ mK ] = CreateImageFilterMtx( mH, numRows, numCols, operationMode, boundaryMode )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

OPERATION_MODE_CONVOLUTION = 1;
OPERATION_MODE_CORRELATION = 2;

BOUNDARY_MODE_ZEROS         = 1;
BOUNDARY_MODE_SYMMETRIC     = 2;
BOUNDARY_MODE_REPLICATE     = 3;
BOUNDARY_MODE_CIRCULAR      = 4;

switch(operationMode)
    case(OPERATION_MODE_CONVOLUTION)
        mH = mH(end:-1:1, end:-1:1);
    case(OPERATION_MODE_CORRELATION)
        % mH = mH; %<! Default Code is correlation
end

switch(boundaryMode)
    case(BOUNDARY_MODE_ZEROS)
        mK = CreateConvMtxZeros(mH, numRows, numCols);
    case(BOUNDARY_MODE_SYMMETRIC)
        mK = CreateConvMtxSymmetric(mH, numRows, numCols);
    case(BOUNDARY_MODE_REPLICATE)
        mK = CreateConvMtxReplicate(mH, numRows, numCols);
    case(BOUNDARY_MODE_CIRCULAR)
        mK = CreateConvMtxCircular(mH, numRows, numCols);
end


end


function [ mK ] = CreateConvMtxZeros( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if((ii + kk <= numRows) && (ii + kk >= 1) && (jj + ll <= numCols) && (jj + ll >= 1))
                    vCols(elmntIdx) = pxIdx + pxShift;
                    vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);
                else
                    vCols(elmntIdx) = pxIdx;
                    vVals(elmntIdx) = 0; % See the accumulation property of 'sparse()'.
                end
            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end


function [ mK ] = CreateConvMtxSymmetric( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if(ii + kk > numRows)
                    pxShift = pxShift - (2 * (ii + kk - numRows) - 1);
                end

                if(ii + kk < 1)
                    pxShift = pxShift + (2 * (1 -(ii + kk)) - 1);
                end

                if(jj + ll > numCols)
                    pxShift = pxShift - ((2 * (jj + ll - numCols) - 1) * numCols);
                end

                if(jj + ll < 1)
                    pxShift = pxShift + ((2 * (1 - (jj + ll)) - 1) * numCols);
                end

                vCols(elmntIdx) = pxIdx + pxShift;
                vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);

            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end


function [ mK ] = CreateConvMtxReplicate( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if(ii + kk > numRows)
                    pxShift = pxShift - (ii + kk - numRows);
                end

                if(ii + kk < 1)
                    pxShift = pxShift + (1 -(ii + kk));
                end

                if(jj + ll > numCols)
                    pxShift = pxShift - ((jj + ll - numCols) * numCols);
                end

                if(jj + ll < 1)
                    pxShift = pxShift + ((1 - (jj + ll)) * numCols);
                end

                vCols(elmntIdx) = pxIdx + pxShift;
                vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);

            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end


function [ mK ] = CreateConvMtxCircular( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if(ii + kk > numRows)
                    pxShift = pxShift - numRows;
                end

                if(ii + kk < 1)
                    pxShift = pxShift + numRows;
                end

                if(jj + ll > numCols)
                    pxShift = pxShift - (numCols * numCols);
                end

                if(jj + ll < 1)
                    pxShift = pxShift + (numCols * numCols);
                end

                vCols(elmntIdx) = pxIdx + pxShift;
                vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);

            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end

Kode divalidasi terhadap MATLAB imfilter().

Kode lengkap tersedia di Repositori GitHub StackOverflow Q2080835 saya .

Royi
sumber