Currently we use blur for thumbnails, but we can explicitly define BitmapTransformations to unload Phroom.kt's code.
But also we need to optimize the algorithm itself. Let's define 2 main problems:
-
Currently we take each pixel and for each of them we take (2r+1)^2 amount of pixels around, where r = radius of the blurring. Now lets say we have w=width and h=height of a bitmap. Then our algorithm work with complexity O(w*h*(2r+1)^2) ~ O(w*h*r^2). If the r will be big enough (close to size of bitmap) then complexity will be O((w*h)^2)
-
Also we do not treat edges well. Today if you will blur the corner pixel it will take into account only near pixels, but should take into account that this pixel itself is a corner one, so it is more "strong" in terms of mixing colors (blurring the image)
So we need to resolve both problems. One thing, that to resolve first one, we probably will need to use additional space for some pre-computations.
FIRST PROBLEM
To increase the time of computing the blurred version. Let's understand firstly, that we can not be faster that O(w*h), since we need to apply transformation to every pixel in the bitmaps. That why we need to at least one passage through all pixels.
Now our task is to get closer to that estimation. To do that we need to somehow 'cache' and 'reuse' our calculations. Particularly for 'counting window'. Counting window = all neighbor pixels to current one to mix them app and thus 'blur' the current one.
Reduce to O(w*h*r)
-
Let's compute the sum of all pixels in counting window for first pixel in our bitmap. Then let's go to right neighbor pixel. From the sum just remove all leftmost neighbors for previous pixel and add all rightmost neighbors for current pixel. Continue to go to right until the end of line.
-
Go to one pixel below. From the sum just remove all upmost neighbors for previous pixel and add all downmost neighbors for current pixel.
-
Apply 1. step mirrored. Now go to left.
-
repeat 2. 1. 3. 2. steps until finish. So we will go thought bitmaps snake-wise
For each pixel we have a sum from previous one and we need to add/remove one row/column from window (update counting window). Each row/column contains (2r + 1) pixel. Thus to compute each pixel we need to make O((2r + 1) + (2r + 1)) ~ O(r). Now doing that for each pixel we have O(w*h*r) estimation. NICE!
Reduce to O(w*h)
For sure we repeatedly computing row/columns from the prev optimization. Now let's build two tables one will contains all row's part sum and other will contains all column's part sum. Then we will just use those tables to build the final one. This optimization will require from us additional 2*w*h space.
Let's describe the filling or row's table. For the column's table algorithm is same
- For the beggining of row let's compute counting window contains of (2r+1) items.
- Go to next pixel in right. Remove leftmost pixel. Add rightmost pixel.
- Continue until the end of the row
Repeat 1. 2. 3. for all rows of the row's table
After we will have a both tables we just need to repeat algoright from the previous optimizations, but because all sums pre-computed we will have O(1) computations for each pixel and thus all computations will take O(w*h) time
Now we need to estimate building time for two aforementioned tables. Let's estimate row's table. For column's everithing is same. So to start fill each row we need to make a initial sum, which takes O(r). Then to finish will row we need to go thourgh it, which is O(w). So for one row time will be O(r + w). Thus, for the whole row's table time is O((r+w)*h). Let's put the upper estimation on r. r <= max(w, h), because it is meaningles to make radius really-really big.
THUS, O((r+w)*h) <= O((2*w*h)) ~ O(w*h)
Thus overall estimation is O(w*h) :)
SECOND PROBLEM
To treat corners more strong we need to not only work with available near pixels, but also with fake pixels, that are places out of bitmap (with negative coordinates and coordinates more the w or h). fake pixel will be equal to closest not fake pixel. Let's demonstrate that on line:
Suppose we want have a line of numirated pixels and radius 2.
- 1 - 2 - 3 - 4 - 5 - 6 - 7 -
So counting window for pixel 3 will be 1 - 2 - 3 - 4 - 5.
For today's implementation counting window for pixel 1 will be 1 - 2 - 3
But with new algorithm it should be 1 - 1 - 1 - 2 - 3
For today's implementation counting window for pixel 2 will be 1 - 2 - 3 - 4
But with new algorithm it should be 1 - 1 - 2 - 3 - 4
Currently we use blur for thumbnails, but we can explicitly define BitmapTransformations to unload Phroom.kt's code.
But also we need to optimize the algorithm itself. Let's define 2 main problems:
Currently we take each pixel and for each of them we take (2r+1)^2 amount of pixels around, where r = radius of the blurring. Now lets say we have w=width and h=height of a bitmap. Then our algorithm work with complexity O(w*h*(2r+1)^2) ~ O(w*h*r^2). If the r will be big enough (close to size of bitmap) then complexity will be O((w*h)^2)
Also we do not treat edges well. Today if you will blur the corner pixel it will take into account only near pixels, but should take into account that this pixel itself is a corner one, so it is more "strong" in terms of mixing colors (blurring the image)
So we need to resolve both problems. One thing, that to resolve first one, we probably will need to use additional space for some pre-computations.
FIRST PROBLEM
To increase the time of computing the blurred version. Let's understand firstly, that we can not be faster that O(w*h), since we need to apply transformation to every pixel in the bitmaps. That why we need to at least one passage through all pixels.
Now our task is to get closer to that estimation. To do that we need to somehow 'cache' and 'reuse' our calculations. Particularly for 'counting window'. Counting window = all neighbor pixels to current one to mix them app and thus 'blur' the current one.
Reduce to O(w*h*r)
Let's compute the sum of all pixels in counting window for first pixel in our bitmap. Then let's go to right neighbor pixel. From the sum just remove all leftmost neighbors for previous pixel and add all rightmost neighbors for current pixel. Continue to go to right until the end of line.
Go to one pixel below. From the sum just remove all upmost neighbors for previous pixel and add all downmost neighbors for current pixel.
Apply 1. step mirrored. Now go to left.
repeat 2. 1. 3. 2. steps until finish. So we will go thought bitmaps snake-wise
For each pixel we have a sum from previous one and we need to add/remove one row/column from window (update counting window). Each row/column contains (2r + 1) pixel. Thus to compute each pixel we need to make O((2r + 1) + (2r + 1)) ~ O(r). Now doing that for each pixel we have O(w*h*r) estimation. NICE!
Reduce to O(w*h)
For sure we repeatedly computing row/columns from the prev optimization. Now let's build two tables one will contains all row's part sum and other will contains all column's part sum. Then we will just use those tables to build the final one. This optimization will require from us additional 2*w*h space.
Let's describe the filling or row's table. For the column's table algorithm is same
Repeat 1. 2. 3. for all rows of the row's table
After we will have a both tables we just need to repeat algoright from the previous optimizations, but because all sums pre-computed we will have O(1) computations for each pixel and thus all computations will take O(w*h) time
Now we need to estimate building time for two aforementioned tables. Let's estimate row's table. For column's everithing is same. So to start fill each row we need to make a initial sum, which takes O(r). Then to finish will row we need to go thourgh it, which is O(w). So for one row time will be O(r + w). Thus, for the whole row's table time is O((r+w)*h). Let's put the upper estimation on r. r <= max(w, h), because it is meaningles to make radius really-really big.
THUS, O((r+w)*h) <= O((2*w*h)) ~ O(w*h)
Thus overall estimation is O(w*h) :)
SECOND PROBLEM
To treat corners more strong we need to not only work with available near pixels, but also with fake pixels, that are places out of bitmap (with negative coordinates and coordinates more the w or h). fake pixel will be equal to closest not fake pixel. Let's demonstrate that on line: