In the previous post when I talked about image convolution, I had shown a convolution kernel that produces the effect of blurring an image.
// 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};
Bigger the kernel, more noticeable is the blurring effect. The problem is that a convolution is very slow and expensive image processing technique, bigger the kernel, more time it takes to process a single image frame. The integral image allow to process a frame in constant time regardless of kernel size.
As said before, an image can be treated as a function of two variables, f(x, y), so the integral of f(x, y) is:
$$I(x,y)=\iint f(x,y)dxdy$$
and it's discrete form:
$$I(x, y)=\sum_{j=0}^{y} \sum_{i=0}^{x} f(i,j)$$
For example, if the pixels values of the image are:
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 |
Then, the resulting integral image is:
| 1 | 3 | 6 | 10 | 15 |
|---|---|---|---|---|
| 7 | 16 | 27 | 40 | 55 |
| 18 | 39 | 63 | 90 | 120 |
| 34 | 72 | 114 | 160 | 210 |
| 55 | 115 | 180 | 250 | 325 |
The formula for calculating sum of all pixels contained in the rectangle defined by (x, y, width, height) is:
$$ \begin{align} sum & = integral(x-1,y-1) \\ & - integral(x+width-1,y-1) \\ & - integral(x-1,y+height-1) \\ & + integral(x+width-1,y+height-1) \end{align} $$
For example, if I want to calculate the sum of all pixels in the rectangle (1, 2, 4, 2), that is:
sum = 12 + 13 + 14 + 15
+ 17 + 18 + 19 + 20 = 128
using the above formula:
p0 = integral(x - 1, y - 1) = integral(1 - 1, 2 - 1) = integral(0, 1) = 7 p1 = integral(x + width - 1, y - 1) = integral(1 + 4 - 1, 2 - 1) = integral(4, 1) = 55 p2 = integral(x - 1, y + height - 1) = integral(1 - 1, 2 + 2 - 1) = integral(0, 3) = 34 p3 = integral(x + width - 1, y + height - 1) = integral(1 + 4 - 1, 2 + 2 - 1) = integral(4, 3) = 210 sum = p0 - p1 - p2 + p3 = 7 - 55 - 34 + 210 = 128
Now, what happens if I want to calculate the sum of the rectangle (0, 0, 5, 5) or any rectangle where it's coordinates x or y are zero? It will return a pixel that doesn't exists, but we can safely assume is equal to zero, so it will not affect the result of the formula. We can fix this problem padding the top and the left side of the SAT, making the values equal to zero.
| 0 | 0 | 0 | 0 | 0 | 0 |
|---|---|---|---|---|---|
| 0 | 1 | 3 | 6 | 10 | 15 |
| 0 | 7 | 16 | 27 | 40 | 55 |
| 0 | 18 | 39 | 63 | 90 | 120 |
| 0 | 34 | 72 | 114 | 160 | 210 |
| 0 | 55 | 115 | 180 | 250 | 325 |
In that case, the new formula is:
$$ \begin{align} sum & = integral(x,y) \\ & - integral(x+width,y) \\ & - integral(x,y+height) \\ & + integral(x+width,y+height) \end{align} $$
And the code for the integral image is this:
#include <QImage>
class Pixel
{
public:
explicit Pixel():
r(0), g(0), b(0)
{
}
Pixel(quint32 r, quint32 g, quint32 b):
r(r), g(g), b(b)
{
}
Pixel operator +(const Pixel &other)
{
return Pixel(this->r + other.r,
this->g + other.g,
this->b + other.b);
}
Pixel &operator +=(QRgb pixel)
{
this->r += qRed(pixel);
this->g += qGreen(pixel);
this->b += qBlue(pixel);
return *this;
}
quint32 r;
quint32 g;
quint32 b;
};
void integralImage(const QImage &image, QVector<Pixel> &integral)
{
int oWidth = image.width() + 1;
int oHeight = image.height() + 1;
integral.resize(oWidth * oHeight);
for (int y = 1; y < oHeight; y++) {
const QRgb *line = (const QRgb *) image.constScanLine(y - 1);
// Reset current line summation.
Pixel sum;
for (int x = 1; x < oWidth; x++) {
QRgb pixel = line[x - 1];
// Accumulate pixels in current line.
sum += pixel;
// Offset to the current line.
int offset = x + y * oWidth;
// Offset to the previous line.
// equivalent to x + (y - 1) * oWidth;
int offsetPrevious = offset - oWidth;
// Accumulate current line and previous line.
integral[offset] = sum + integral[offsetPrevious];
}
}
}
The blur effect can be defined as the average of all pixels surrounding a pixel I(x, y) in a radius r:
$$Blur(x, y)=\frac{1}{(2r+1)^2}\sum_{j=-r}^{r}\sum_{i=-r}^{r}I(x+i, y+j)$$
And the final code for the image blur:
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 oWidth = inImage.width() + 1;
QVector<Pixel> integral;
integralImage(inImage, integral);
// Here we configure how much strong the blur will be.
int radius = 50;
for (int y = 0; y < inImage.height(); y++) {
const QRgb *iLine = (const QRgb *) inImage.constScanLine(y);
QRgb *oLine = (QRgb *) outImage.scanLine(y);
int yp = qMax(y - radius, 0);
int kh = qMin(y + radius, inImage.height() - 1) - yp + 1;
for (int x = 0; x < inImage.width(); x++) {
int xp = qMax(x - radius, 0);
int kw = qMin(x + radius, inImage.width() - 1) - xp + 1;
Pixel *p0 = integral.data() + xp + yp * oWidth;
Pixel *p1 = p0 + kw;
Pixel *p2 = p0 + kh * oWidth;
Pixel *p3 = p2 + kw;
quint32 sumR = p0->r - p1->r - p2->r + p3->r;
quint32 sumG = p0->g - p1->g - p2->g + p3->g;
quint32 sumB = p0->b - p1->b - p2->b + p3->b;
qreal ks = kw * kh;
quint8 r = qRound(sumR / ks);
quint8 g = qRound(sumG / ks);
quint8 b = qRound(sumB / ks);
oLine[x] = qRgba(r, g, b, qAlpha(iLine[x]));
}
}
outImage.save("out.png");
return EXIT_SUCCESS;
}
And this is the result for r=50:
:o
ReplyDelete