W jaki sposób konwolucję można wyrazić jako mnożenie macierzy (macierz)?

11

Wiem, że to pytanie może nie być zbyt istotne dla programowania, ale jeśli nie zrozumiem teorii leżącej u podstaw przetwarzania obrazu, nigdy nie będę w stanie zaimplementować czegoś w praktyce.

Jeśli dobrze to rozumiem, filtry Gaussa są splecione z obrazem w celu redukcji szumów, ponieważ obliczają średnią ważoną sąsiedztwa piksela i są bardzo przydatne w wykrywaniu krawędzi, ponieważ można zastosować rozmycie i uzyskać obraz jednocześnie po prostu splecione z pochodną funkcji Gaussa.

Ale czy ktoś może mi wyjaśnić lub podać odniesienia do sposobu ich obliczania?

Np . Wykrywacz krawędzi Canny'ego mówi o filtrze Gaussa 5x5, ale jak uzyskali te konkretne liczby? Jak przeszli od ciągłego splotu do mnożenia macierzy?

Matteo
źródło
I dodał odpowiedź z pełnym kodem do generowania macierzy Splot obrazu.
Royi

Odpowiedzi:

3

Aby ta operacja zadziałała, musisz sobie wyobrazić, że twój obraz jest przekształcany jako wektor. Następnie wektor ten jest mnożony po lewej stronie przez macierz splotu w celu uzyskania zamazanego obrazu. Zauważ, że wynikiem jest również wektor tego samego rozmiaru co dane wejściowe, tj. Obraz o tym samym rozmiarze.

Każdy rząd macierzy splotu odpowiada jednemu pikselowi na obrazie wejściowym. Zawiera wagę wkładu wszystkich innych pikseli w obrazie do rozmytego odpowiednika rozpatrywanego piksela.

Weźmy przykład: rozmycie pola wielkości 3)×3) piksele na obrazie wielkości 6×6piksele. Przekształcony obraz to kolumna 36 wybranych, a matryca rozmycia ma rozmiar36×36.

  • Zacznijmy tę macierz od 0 wszędzie.
  • Teraz rozważ piksel współrzędnych (ja,jot)na obrazie wejściowym (nie na granicy dla uproszczenia). Jego zamazany odpowiednik uzyskuje się przez zastosowanie masy1/9 do siebie i każdego z sąsiadów na stanowiskach (ja-1,jot-1);(ja-1,jot),(ja-1,jot+1),,(ja+1,jot+1).
  • W wektorze kolumny piksel (ja,jot) ma pozycję 6ja+jot(przy założeniu porządku leksykograficznego). zgłaszamy wagę1/9 w (6ja+jot)-ta linia macierzy rozmycia.
  • Zrób to samo ze wszystkimi innymi pikselami.

Wizualną ilustrację ściśle powiązanego procesu (splot + odejmowanie) można znaleźć w tym poście na blogu (z mojego osobistego bloga).

sansuiso
źródło
link jest martwy.
gauteh
2

W przypadku aplikacji do obrazów lub sieci splotowych, w celu bardziej wydajnego wykorzystania mnożników macierzy we współczesnych procesorach graficznych, dane wejściowe są zwykle przekształcane w kolumny macierzy aktywacji, które można następnie zwielokrotnić za pomocą wielu filtrów / jąder jednocześnie.

Sprawdź ten link w CS231n Stanforda i przewiń w dół do sekcji „Implementacja jako mnożenie macierzy”, aby uzyskać szczegółowe informacje.

Proces ten polega na pobraniu wszystkich lokalnych poprawek na obrazie wejściowym lub mapie aktywacji, które zostałyby pomnożone przez jądro, i rozciągnięciu ich do kolumny nowej macierzy X za pomocą operacji zwanej im2col. Jądra są również rozciągane, aby zapełnić rzędy macierzy wagowej W, aby podczas wykonywania operacji macierzowej W * X uzyskana macierz Y miała wszystkie wyniki splotu. Na koniec macierz Y należy ponownie przekształcić, przekształcając kolumny z powrotem w obrazy za pomocą operacji zwykle zwanej cal2im.

Rodrigo
źródło
1
To bardzo dobry link, dzięki! Jednak dobrą praktyką jest dodawanie ważnych fragmentów linku do odpowiedzi, w ten sposób odpowiedź jest ważna, nawet jeśli link się zepsuje. Proszę rozważyć edycję swojej odpowiedzi, aby ją zaakceptować!
Matteo
1

Konwolucja w dziedzinie czasu równa się mnożeniu macierzy w dziedzinie częstotliwości i odwrotnie.

Filtrowanie jest równoważne splotowi w dziedzinie czasu, a zatem zwielokrotnieniu macierzy w dziedzinie częstotliwości.

Jeśli chodzi o mapy lub maski 5x5, pochodzą one od dyskrecji operatorów canny / sobel.

Naresh
źródło
2
Nie zgadzam się z tym, że filtrowanie to splot w dziedzinie częstotliwości. Rodzajami filtrów, o których tutaj mówimy, są zwoje w dziedzinie przestrzennej (to znaczy mnożenie elementarne przez odpowiedź filtra w dziedzinie częstotliwości).
fenenety
Dzięki za poprawienie tego, co napisałem. Dokonałem kolejnej edycji. Chyba powinienem dokładnie sprawdzić swoje odpowiedzi przed opublikowaniem. Jednak większość mojej odpowiedzi jest nadal aktualna.
Naresh
Transformacja Fouriera faktycznie przekształca splot w multiplikacje (i odwrotnie). Są to jednak mądre pomnożenia, podczas gdy pytanie dotyczy multiplikacji macierz-wektor, które są uzyskiwane przez przekształcenie obrazów.
sansuiso
Wspomniałem, jak dyskrecjonowanie operatorów jest przyczyną uzyskania macierzy 5x5 dla operatorów canny / sobel.
Naresh,
1

Napisałem funkcję, która rozwiązuje to w moim StackOverflow Q2080835 GitHub Repository (spójrz na CreateImageConvMtx()).
Właściwie funkcja może obsługiwać dowolny kształt splot, który chcesz - full, samei valid.

Kod jest następujący:

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

Stworzyłem również funkcję do tworzenia matrycy do filtrowania obrazów (podobne pomysły do ​​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

Kod został sprawdzony pod kątem MATLAB imfilter().

Pełny kod jest dostępny w moim repozytorium GitHub StackOverflow Q2080835 .

Royi
źródło