## Jun 30, 2015

### Image convolution

In this post I want explain a one of the most common and simple algorithm used in image processing. I will give a very basic introduction to its mathematical formulation, the source code in C++/Qt, and a some output examples.

## What is a convolution?

The mathematical formulation of a convolution is as follow:

$$(f*g)(t)=\int_{-\infty}^{\infty}f(x)g(t-x)dx$$

But, what this formula means? what it does?, let see an example. Let define f(x) as:

$$f(x)=\left\{\begin{matrix} 1, & |x| \leqslant 1 \\ 0, & otherwise \end{matrix}\right.;$$

And let define g(x) as:

$$f(x)=\left\{\begin{matrix} 1 - |x|, & |x| \leqslant 1 \\ 0, & otherwise \end{matrix}\right.;$$

The convolution of f(x) and g(x) will define a new function in which the values of (f * g)(t) will be the area enclosed by f(x) and g(x) in the instant t.

Since an image can be treated as a function of two variables that returns the color of a pixel relative to its coordinates, we can extend the mathematical definition of the convolution to the following formula:

$$(f*g)(u, v)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(x, y)g(u - x, v - y)dxdy$$

## How convolution formula is applied to an image?

An image can be treated as a discrete function, so we will use the discrete form of the last formula:

$$pixel(x,y)=\sum_{j=0}^{kh}\sum_{i=0}^{kw}inImage\left(x+i-\frac{kw-1}{2},y+j-\frac{kh-1}{2}\right)kernel(i,j)$$

inImage is the image in which we will apply the convolution over every pixel, kernel is a kw * kh array values, the convolution is applied to a group of pixels in which the center of the kernel y aligned to the coordinates of the pixel that is begin processed. Graphically:

The pseudo-algorithm for convolution is:
for (y = 0; y < height; y++)
for (x = 0; x < width; x++) {
pixel = 0;

// Apply convolution
for (j = 0; j < kh; j++)
for (i = 0; i < kw; i++)
pixel += inImage(x + i - (kw - 1) / 2, y + j - (kh - 1) / 2) * kernel(i, j);

outImage(x, y, pixel);
}


## The source code

At this point there is not much to explain, just apply the algorithm above. This is the source code for the project file in Qt Creator:

QT += core gui

TARGET = convolution
CONFIG += console
CONFIG -= app_bundle

TEMPLATE = app

SOURCES += main.cpp


And this is the source code for main.cpp:

#include <QCoreApplication>
#include <QImage>

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
Q_UNUSED(a)

QImage inImage("lena.png");
inImage = inImage.convertToFormat(QImage::Format_RGB32);
QImage outImage(inImage.size(), inImage.format());

int kw = 3;
int kh = 3;
qreal kernel[] = {0, 0, 0,
0, 1, 0,
0, 0, 0};

int offsetX = (kw - 1) / 2;
int offsetY = (kh - 1) / 2;

for (int y = 0; y < inImage.height(); y++) {
QRgb *outLine = (QRgb *) outImage.scanLine(y);

for (int x = 0; x < inImage.width(); x++) {
qreal pixelR = 0;
qreal pixelG = 0;
qreal pixelB = 0;

// Apply convolution to each channel.
for (int j = 0; j < kh; j++) {
if (y + j < offsetY
|| y + j - offsetY >= inImage.height())
continue;

const QRgb *inLine = (QRgb *) inImage.constScanLine(y + j - offsetY);

for (int i = 0; i < kw; i++) {
if (x + i < offsetX
|| x + i - offsetX >= inImage.width())
continue;

qreal k = kernel[i + j * kw];
QRgb pixel = inLine[x + i - offsetX];

pixelR += k * qRed(pixel);
pixelG += k * qGreen(pixel);
pixelB += k * qBlue(pixel);
}
}

quint8 r = qBound(0., pixelR, 255.);
quint8 g = qBound(0., pixelG, 255.);
quint8 b = qBound(0., pixelB, 255.);
outLine[x] = qRgb(r, g, b);
}
}

outImage.save("out.png");

return EXIT_SUCCESS;
}


## Some examples

You can try giving different size and values to kernel and see what results you get. Here are some examples:

// Identity kernel (original image)
int kw = 3;
int kh = 3;
qreal kernel[] = {0, 0, 0,
0, 1, 0,
0, 0, 0};


// Edge detection
int kw = 3;
int kh = 3;
qreal kernel[] = {-1, -1, -1,
-1,  8, -1,
-1, -1, -1};

// Sharppening
int kw = 3;
int kh = 3;
qreal kernel[] = {-1, -1, -1,
-1,  9, -1,
-1, -1, -1};

// Brightness
int kw = 3;
int kh = 3;
qreal kernel[] = {0, 0, 0,
0, 2, 0,
0, 0, 0};

// Blur
int kw = 7;
int kh = 7;
qreal kernel[] = {1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49,
1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49,
1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49,
1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49,
1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49,
1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49,
1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49, 1. / 49};


// Gaussian Blur (Denoise)
int kw = 5;
int kh = 5;
qreal kernel[] = {1 / 273.,  4 / 273.,  7 / 273.,  4 / 273., 1 / 273.,
4 / 273., 16 / 273., 26 / 273., 16 / 273., 4 / 273.,
7 / 273., 26 / 273., 41 / 273., 26 / 273., 7 / 273.,
4 / 273., 16 / 273., 26 / 273., 16 / 273., 4 / 273.,
1 / 273.,  4 / 273.,  7 / 273.,  4 / 273., 1 / 273.};


#### 1 comment:

1. Good information . Thanks alot