Wie kann eine Faltung als Matrixmultiplikation (Matrixform) ausgedrückt werden?

11

Ich weiß, dass diese Frage für die Programmierung möglicherweise nicht sehr relevant ist, aber wenn ich die Theorie hinter der Bildverarbeitung nicht verstehe, kann ich nie etwas in die Praxis umsetzen.

Wenn ich es richtig verstanden habe, werden Gaußsche Filter mit einem Bild zur Rauschreduzierung gefaltet, da sie einen gewogenen Durchschnitt der Nachbarschaft eines Pixels berechnen und bei der Kantenerkennung sehr nützlich sind, da Sie eine Unschärfe anwenden und das Bild gleichzeitig durch ableiten können einfach mit der Ableitung einer Gaußschen Funktion falten.

Aber kann mir jemand erklären oder mir einige Hinweise geben, wie sie berechnet werden?

Zum Beispiel spricht Cannys Kantendetektor von einem 5x5-Gauß-Filter, aber wie haben sie diese bestimmten Zahlen erhalten? Und wie sind sie von einer kontinuierlichen Faltung zu einer Matrixmultiplikation gekommen?

image-processing filtering gradient edge-detection Matteo
quelle
dsp.stackexchange.com/questions/2969/…
Andrey Rubshtein
Ich habe eine Antwort mit vollständigem Code zum Generieren einer Matrix für die Bildfaltung hinzugefügt .
Royi

Antworten:

3

Damit dieser Vorgang funktioniert, müssen Sie sich vorstellen, dass Ihr Bild als Vektor umgeformt wird. Dann wird dieser Vektor links von ihm mit der Faltungsmatrix multipliziert, um das unscharfe Bild zu erhalten. Beachten Sie, dass das Ergebnis auch ein Vektor mit derselben Größe wie die Eingabe ist, dh ein Bild mit derselben Größe.

Jede Zeile der Faltungsmatrix entspricht einem Pixel im Eingabebild. Es enthält das Gewicht der Beiträge aller anderen Pixel im Bild zum unscharfen Gegenstück des betrachteten Pixels.

Nehmen wir ein Beispiel: Box-Unschärfe mit einer Größe von Pixel auf einem Bild mit einer Größe von 6 × 6 Pixel. Das umgeformte Bild ist eine Spalte mit 36 ​​Wählungen, während die Unschärfematrix die Größe 36 × 36 hat .3×36×636×36

  • Lassen Sie uns diese Matrix überall auf 0 setzen.
  • Betrachten Sie nun das Koordinatenpixel im Eingabebild (der Einfachheit halber nicht an seinem Rand). Sein Gegenstück verschwommenes durch Anlegen einer Gewichts erhaltene 1 / 9 auf sich selbst und jedem seiner Nachbarn an den Positionen ( i - 1 , j - 1 ) ; ( i - 1 , j ) , ( i - 1 , j + 1 ) , … , ( i + 1 ,(ich,j)1/.9 .(ich- -1,j- -1);;(ich- -1,j),(ich- -1,j+1),…,(ich+1,j+1)
  • In dem Spaltenvektor hat das Pixel die Position 6 ∗ i + j (unter der Annahme einer lexikografischen Reihenfolge). berichten wir , das Gewicht 1 / 9 in der ( 6 i + j ) -ten Zeile der Unschärfe - Matrix.(ich,j)6∗ich+j1/.9(6ich+j)
  • Machen Sie dasselbe mit allen anderen Pixeln.

Eine visuelle Darstellung eines eng verwandten Prozesses (Faltung + Subtraktion) finden Sie in diesem Blog-Beitrag (aus meinem persönlichen Blog).

Sansuiso
quelle
Ein Link ist tot.
Gauteh
2

Für Anwendungen auf Bilder oder Faltungsnetzwerke, um die Matrixmultiplikatoren in modernen GPUs effizienter zu verwenden, werden die Eingaben normalerweise in Spalten einer Aktivierungsmatrix umgeformt, die dann mit mehreren Filtern / Kerneln gleichzeitig multipliziert werden können.

Schauen Sie sich diesen Link aus Stanfords CS231n an und scrollen Sie zum Abschnitt "Implementierung als Matrixmultiplikation", um weitere Informationen zu erhalten.

Der Prozess funktioniert, indem alle lokalen Patches auf einem Eingabebild oder einer Aktivierungszuordnung, die mit dem Kernel multipliziert werden, genommen und durch eine allgemein als im2col bezeichnete Operation in eine Spalte einer neuen Matrix X gestreckt werden. Die Kernel werden auch gestreckt, um die Zeilen einer Gewichtsmatrix W zu füllen, so dass bei der Ausführung der Matrixoperation W * X die resultierende Matrix Y alle Ergebnisse der Faltung aufweist. Schließlich muss die Y-Matrix erneut umgeformt werden, indem die Spalten durch eine Operation namens cal2im wieder in Bilder umgewandelt werden.

Rodrigo
quelle
1
Dies ist ein sehr guter Link, danke! Es wird jedoch empfohlen, die wichtigen Auszüge aus dem Link in die Antwort einzufügen. Auf diese Weise ist die Antwort auch dann gültig, wenn der Link unterbrochen wird. Bitte bearbeiten Sie Ihre Antwort, um sie zu akzeptieren!
Matteo
1

Die Faltung im Zeitbereich entspricht der Matrixmultiplikation im Frequenzbereich und umgekehrt.

Das Filtern entspricht der Faltung im Zeitbereich und damit der Matrixmultiplikation im Frequenzbereich.

Die 5x5-Karten oder -Masken stammen aus der Diskretisierung der Canny / Sobel-Operatoren.

Naresh
quelle
2
Ich stimme der Tatsache nicht zu, dass das Filtern eine Faltung im Frequenzbereich ist. Die Art von Filtern, über die wir hier sprechen, sind Faltungen im räumlichen Bereich (dh elementweise Multiplikation mit der Filterantwort im Frequenzbereich).
Pichenettes
Vielen Dank für die Korrektur, was ich geschrieben habe. Ich habe eine nachfolgende Bearbeitung vorgenommen. Ich denke, ich sollte meine Antworten vor dem Posten noch einmal überprüfen. Der Großteil meiner Antwort steht jedoch noch.
Naresh
Die Fourier-Transformation wandelt tatsächlich Windungen in Multiplikationen um (und umgekehrt). Es handelt sich jedoch um pintweise Multiplikationen, während es sich um Matrix-Vektor-Multiplikationen handelt, die durch Umformen der Bilder erhalten werden.
Sansuiso
Ich habe erwähnt, dass die Diskretisierung der Operatoren der Grund für die 5x5-Matrizen ist, die für die Canny / Sobel-Operatoren erhalten werden.
Naresh
1

Ich habe eine Funktion geschrieben, die dies in meinem StackOverflow Q2080835 GitHub Repository löst (siehe CreateImageConvMtx()).
Eigentlich kann die Funktion jeder Faltung Form unterstützen Sie möchten - full, sameund valid.

Der Code lautet wie folgt:

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

Ich habe auch eine Funktion zum Erstellen einer Matrix für die Bildfilterung erstellt (ähnliche Ideen wie bei 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

Der Code wurde gegen MATLAB validiert imfilter().

Der vollständige Code ist in meinem GitHub-Repository StackOverflow Q2080835 verfügbar .

Royi
quelle