Kernel (image processing)
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. g_{x,y} = \omega * f_{x,y} = \sum_{i=-a}^a {\sum_{j=-b}^b { \omega_{i,j} f_{x-i,y-j}}}, where g(x,y) is the filtered image, f(x,y) is the original image, \omega is the filter kernel. Every element of the filter kernel is considered by -a \leq i \leq a and -b \leq j \leq b . Depending on the element values, a kernel can cause a wide range of effects: The above are just a few examples of effects achievable by convolving kernels and images. \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 \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. The general form for matrix convolution is \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{mn} \\ \end{bmatrix} \begin{bmatrix} y_{11} & y_{12} & \cdots & y_{1n} \\ y_{21} & y_{22} & \cdots & y_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ y_{m1} & y_{m2} & \cdots & y_{mn} \\ \end{bmatrix} = \sum^{m-1}_{i=0} \sum^{n-1}_{j=0} x_{(m-i)(n-j)} y_{(1+i)(1+j)}
Optimization
Fast convolution algorithms include: separable convolution
Separable convolution
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. Here a concrete convolution implementation done with the GLSL shading language : // author : csblo // Work made just by consulting : // https://en.wikipedia.org/wiki/Kernel_(image_processing) // Define kernels define identity mat3(0, 0, 0, 0, 1, 0, 0, 0, 0) define edge0 mat3(1, 0, -1, 0, 0, 0, -1, 0, 1) define edge1 mat3(0, 1, 0, 1, -4, 1, 0, 1, 0) define edge2 mat3(-1, -1, -1, -1, 8, -1, -1, -1, -1) define sharpen mat3(0, -1, 0, -1, 5, -1, 0, -1, 0) define box_blur mat3(1, 1, 1, 1, 1, 1, 1, 1, 1) * 0.1111 define gaussian_blur mat3(1, 2, 1, 2, 4, 2, 1, 2, 1) * 0.0625 define emboss mat3(-2, -1, 0, -1, 1, 1, 0, 1, 2) // Find coordinate of matrix element from index vec2 kpos(int index) { return vec2[9] ( vec2(-1, -1), vec2(0, -1), vec2(1, -1), vec2(-1, 0), vec2(0, 0), vec2(1, 0), vec2(-1, 1), vec2(0, 1), vec2(1, 1) )[index] / iResolution.xy; } // 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 channel mat3[3] region3x3(sampler2D sampler, vec2 uv) { // Create each pixels for region vec4[9] region; for (int i = 0; i
Sources
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 GLSL Demonstration of 3x3 Convolution Kernels Complete C++ open source project
Text derived from https://en.wikipedia.org/w/index.php?oldid=1315294573 under CC BY-SA 4.0; modifications have been made.