Kernel (image processing)

In image processing, a kernel, convolution matrix, or mask is a small matrix useful for blurring, sharpening, embossing, edge detection, and more. This is accomplished by means of convolution between a kernel and an image.

Details

Depending on the element values, a kernel can cause a wide range of effects.

Identity	$\begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}$	File:Vd-Orig.png
Edge detection	$\begin{bmatrix} \ \ 1 & 0 & -1 \\ \ \ 0 & 0 & \ \ 0 \\ -1 & 0 & \ \ 1 \end{bmatrix}$	File:Vd-Edge1.png
	$\begin{bmatrix} 0 & \ \ 1 & 0 \\ 1 & -4 & 1 \\ 0 & \ \ 1 & 0 \end{bmatrix}$	File:Vd-Edge2.png
	$\begin{bmatrix} -1 & -1 & -1 \\ -1 & \ \ 8 & -1 \\ -1 & -1 & -1 \end{bmatrix}$	File:Vd-Edge3.png
Sharpen	$\begin{bmatrix} \ \ 0 & -1 & \ \ 0 \\ -1 & \ \ 5 & -1 \\ \ \ 0 & -1 & \ \ 0 \end{bmatrix}$	File:Vd-Sharp.png
Box blur (normalized)	$\frac{1}{9} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}$	File:Vd-Blur2.png
Gaussian blur (approximation)	$\frac{1}{16} \begin{bmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{bmatrix}$	File:Vd-Blur1.png
5×5 Unsharp (with no image mask)	$\frac{-1}{256} \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.

Origin

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.

Convolution

This is related to a form of mathematical convolution. It should be noted that the matrix operation being performed - convolution - is not traditional matrix multiplication, despite being similarly denoted by *.

Convolution is the process of multiplying each element of the image with its local neighbors, weighted by the kernel. For example, if we have two three-by-three matrices, one a kernel, and the other an image piece, convolution is the process of flipping both the rows and columns of the kernel and then multiplying locationally similar entries and summing. The [2,2] element of the resulting image would be a weighted combination of all the entries of the image matrix, with weights given by the kernel: $\left( \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix} * \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \right) [2,2] = (i*1)+(h*2)+(g*3)+(f*4)+(e*5)+(d*6)+(c*7)+(b*8)+(a*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 kernel is symmetric then place the centre(origin) of kernel on the current pixel. Then kernel will be overlapped with neighboring pixels too. Now multiply each kernel element with the pixel value it overlapped with and add all the obtained values. Resultant value will be the value for the current pixel that is 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.

Edge Handling

File:Extend Edge-Handling.png

Extend Edge-Handling

Kernel convolution usually requires values from pixels outside of the image boundaries. There are a variety of methods for handling image edges.

Extend

The nearest border pixels are conceptually extended as far as necessary to provide values for the convolution. Corner pixels are extended in 90° wedges. Other edge pixels are extended in lines.

Wrap

The image is conceptually wrapped (or tiled) and values are taken from the opposite edge or corner.

Crop

Any pixel in the output image which would require values from beyond the edge is skipped. This method can result in the output image being slightly smaller, with the edges having been cropped.

Normalization

Dividing each element in the kernel by the sum

External links

• Implementing 2d convolution on FPGA
• vImage Programming Guide: Performing Convolution Operations
• Image Processing using 2D-Convolution
• GNU Image Manipulation Program - User Manual - 8.2. Convolution Matrix
• Interactive Demonstration of 3x3 Convolution Kernels

• http://www.songho.ca/dsp/convolution/convolution2d_example.html