In image processing, a kernel, convolution matrix, or mask is a small matrix used for blurring, sharpening, embossing, edge detection, and more. This is accomplished by doing a convolution between the kernel and an image. Or more simply, when each pixel in the output image is a function of the nearby pixels (including itself) in the input image, the kernel is that function.
The general expression of a convolution is
g(x,y)=\omega
| b{ | |
| *f(x,y)=\sum | |
| j=-b |
\omega(i,j)f(x-i,y-j)}},
where
g(x,y)
f(x,y)
\omega
-a\leqi\leqa
-b\leqj\leqb
Depending on the element values, a kernel can cause a wide range of effects:
| Operation | Kernel ω | Image result g(x,y) | |||
|---|---|---|---|---|---|
| Identity | \begin{bmatrix} 0& 0& 0\\ 0& 1& 0\\ 0& 0& 0 \end{bmatrix} | ||||
| Ridge or edge detection | \begin{bmatrix} 0&-1&0\\ -1& 4&-1\\ 0&-1&0 \end{bmatrix} | ||||
\begin{bmatrix} -1&-1&-1\\ -1& 8&-1\\ -1&-1&-1 \end{bmatrix} | |||||
| Sharpen | \begin{bmatrix} 0&-1& 0\\ -1& 5&-1\\ 0&-1& 0 \end{bmatrix} | ||||
| Box blur (normalized) |
\begin{bmatrix} 1& 1& 1\\ 1& 1& 1\\ 1& 1& 1 \end{bmatrix} | ||||
| Gaussian blur 3 × 3 (approximation) |
\begin{bmatrix} 1& 2& 1\\ 2& 4& 2\\ 1& 2& 1 \end{bmatrix} | ||||
| Gaussian blur 5 × 5 (approximation) |
\begin{bmatrix} 1&4&6&4&1\\ 4&16&24&16&4\\ 6&24&36&24&6\\ 4&16&24&16&4\\ 1&4&6&4&1 \end{bmatrix} | ||||
| Unsharp masking 5 × 5 Based on Gaussian blur with amount as 1 and threshold as 0 (with no image mask) |
\begin{bmatrix} 1&4& 6&4&1\\ 4&16& 24&16&4\\ 6&24&-476&24&6\\ 4&16& 24&16&4\\ 1&4& 6&4&1 \end{bmatrix} | ||||
The above are just a few examples of effects achievable by convolving kernels and images.
The origin is the position of the kernel which is above (conceptually) the current output pixel. This could be outside of the actual kernel, though usually it corresponds to one of the kernel elements. For a symmetric kernel, the origin is usually the center element.
See also: Symmetric convolution.
Convolution is the process of adding each element of the image to its local neighbors, weighted by the kernel. This is related to a form of mathematical convolution. The matrix operation being performed - convolution - is not traditional matrix multiplication, despite being similarly denoted by *.
For example, if we have two three-by-three matrices, the first a kernel, and the second an image piece, convolution is the process of flipping both the rows and columns of the kernel and multiplying locally similar entries and summing. The element at coordinates [2, 2] (that is, the central element) of the resulting image would be a weighted combination of all the entries of the image matrix, with weights given by the kernel:
\begin1 & 2 & 3 \\4 & 5 & 6 \\7 & 8 & 9\end \right) [2,2]= (i \cdot 1)+(h \cdot 2)+(g \cdot 3)+(f \cdot 4)+(e \cdot 5)+(d \cdot 6)+(c \cdot 7)+(b \cdot 8)+(a \cdot 9).
The other entries would be similarly weighted, where we position the center of the kernel on each of the boundary points of the image, and compute a weighted sum.
The values of a given pixel in the output image are calculated by multiplying each kernel value by the corresponding input image pixel values. This can be described algorithmically with the following pseudo-code:
for each image row in input image: for each pixel in image row: set accumulator to zero for each kernel row in kernel: for each element in kernel row: if element position corresponding* to pixel position then multiply element value corresponding* to pixel value add result to accumulator endif set output image pixel to accumulator
*corresponding input image pixels are found relative to the kernel's origin.
If the kernel is symmetric then place the center (origin) of the kernel on the current pixel. The kernel will overlap the neighboring pixels around the origin. Each kernel element should be multiplied with the pixel value it overlaps with and all of the obtained values should be summed. This resultant sum will be the new value for the current pixel currently overlapped with the center of the kernel.
If the kernel is not symmetric, it has to be flipped both around its horizontal and vertical axis before calculating the convolution as above.[1]
The general form for matrix convolution is
\begin y_ & y_ & \cdots & y_ \\ y_ & y_ & \cdots & y_ \\ \vdots & \vdots & \ddots & \vdots \\ y_ & y_ & \cdots & y_ \\ \end = \sum^_ \sum^_ x_ y_
Kernel convolution usually requires values from pixels outside of the image boundaries. There are a variety of methods for handling image edges.
Normalization is defined as the division of each element in the kernel by the sum of all kernel elements, so that the sum of the elements of a normalized kernel is unity. This will ensure the average pixel in the modified image is as bright as the average pixel in the original image.
Fast convolution algorithms include:
2D convolution with an M × N kernel requires M × N multiplications for each sample (pixel). If the kernel is separable, then the computation can be reduced to M + N multiplications. Using separable convolutions can significantly decrease the computation by doing 1D convolution twice instead of one 2D convolution.[2]
Here a concrete convolution implementation done with the GLSL shading language :
// Define kernels
// Find coordinate of matrix element from indexvec2 kpos(int index)
// Extract region of dimension 3x3 from sampler centered in uv// sampler : texture sampler// uv : current coordinates on sampler// return : an array of mat3, each index corresponding with a color channelmat3[3] region3x3(sampler2D sampler, vec2 uv)
// Convolve a texture with kernel// kernel : kernel used for convolution// sampler : texture sampler// uv : current coordinates on samplervec3 convolution(mat3 kernel, sampler2D sampler, vec2 uv)
void mainImage(out vec4 fragColor, in vec2 fragCoord)