Blur 알고리즘

Blur is the expensive "post processing".

 

블러이펙트는 full screen scene이나 특정 사이즈를 blur효과를 주는 것이다. 
Texture를 렌더링한 장면에서 2d image를 연산하는 것을 “post processing“이라고 부른다.
"Post processing"은 꽤 expensive한 연산으로 shader 프로그램에 상당한 optimization을 해야한다. 

The blur effect is used for blurring the full screen scene or blurring individual objects in that scene.
Whenever we perform 2D image operations on a scene that has been rendered to texture it is called post processing. 
To perform any post processing it is generally quite expensive and requires heavy optimization in the shaders.

Box blur

Basic box blur

Box blur는 말 그대로 Box 형태로 이미지를 블러처리 하는 것이다. 예를 들면, 3x3 9개의 pixel을 가진 Box가 있다. 지름이 3이고(도형 중심에서의 끝과 끝) 반지름이 1(도형 지름에서 -1, /2, Box center로부터 pixel 갯수)이라고 하겠다. 
The above illustration shows a 9x9 surrounding pixels. I call this a Diameter of 3 pixels (since the width is 3 and the height is 3), and a radius of 1 (The radius is Diameter — 1 / 2), which is the number of pixels from the center of the image. This is the basic blur which is also named Box Blur. 

왼쪽에서 오른쪽, 위에서 아래로 한 칸씩 이동하며 주변 색상의 평균값으로 블러 처리를 다 하면 이미지는 약간 블러가 될 것이다.
Averaging the surrounding of color for a pixel is done for every pixel, from left to right, top to bottom.

블러를 더 강하게 적용하고 싶다면, Box의 크기를 늘리면 된다. (인접한 pixel의 값을 더 가져올 수 있도록)
이 반지름의 크기는 다음과 같이 더 크게할 수 있다. 박스의 크기에 따라 blur가 더 강하게 적용된 것 처럼 보인다. 
If we want a greater blur effect, we could expand to a greater radius, e.g. 2, then a greater blurring effect would be seen. An illustration radius of 2 is as below.

하지만, box blur의 반지름 크기를 크게 할수록, 
1) 평균값 box blur는 이미지를 아름답게 blur하지 못한다.
2) 그리고 성능이 좋지 않다. 반지름의 크기가 0일때는 40ms가 걸리지만 100일 때는 101 sec가 걸린다. 무려 1.5배나 늘어나는 것이다.
If we want a greater blur effect, we could expand to a greater radius, e.g. 2, then a greater blurring effect would be seen. An illustration radius of 2 is as below.
This is the basic blur which is also named Box Blur. Nonetheless, there are two issues with this approach.
1) As you could see on the radius 20 blur, the image is relatively pixelated, or boxed. The average of surrounding color is not a good value to blur the image smoothly. Let’s revisit how to solve this later in a section below.
2) The processing time increases in magnitude as the radius size increases. At radius 0, it uses about 40ms, but at radius 100, it uses 101seconds, which is more than 1.5 minutes just to blur the image!

Optimized box blur computation

위의 문제를 해결하기 위해서 box의 color의 blur값을 가져오는데 각 pixel의 평균값이 아닌 똑똑한 방법을 사용해보자. Two-pass만 가지고 값을 구할 것이다.

1. 반지름 안의 가로줄의 근처 pixel color의 평균 값을 구한다.
2. 위 결과를 이용해서 세로줄도 마찬가지로 평균 값을 구한다.

To solve the slow computation problem, there’s a smart way of getting the averaging boxes value, without averaging individually for each pixel. Instead, this could be done by having a two-pass through the image.
Traverse through the pixel row-by-row to compute the average of the pixel with its horizontal neighboring pixel within the stated radius.
After that, use the result from 1, traverse through the pixel column-by-column to compute the average of the pixel with its vertical neighboring pixel within the stated radius.

반지름 반경 안의 픽셀들의 평균값과 two-pass의 평균 값이 동일한 것을 확인할 수 있다. 

Believe it or not, the result for each of the pixels, after the two-pass above, is the same as averaging out the pixel with its surrounding given radius (two-dimensionally).

위에서 보는 것과 같이 two-pass는 평균값을 구하는 가장 빠른 방법이다. 정확히는 sum을 계산하는 시간을 줄이는 것이다. 

유투브에 설명이 잘 나와있다. 3x3박스로 블러값을 구할 때, 일반 Box blur는 (0,0)과 (1,0) 계산에서 볼 수 있듯이 9개의 샘플을 다 쓴다. 
하지만 Optimized box blur는 2개의 스테이지로 나눠서 가로줄의 평균 값을 미리 구해놓은 뒤, (0,0), (0,1)의 블러 값을 구할 때 세로줄의 평균을 구한다. 
이 세로줄의 평균 값이 Box blur의 결과 값이 된다. 

	(0,0)	(1,0)	Result
Box blur
Optimized box blur - horizontal
Optimized box blur - vertical

여기서 trick하나를 더 소개하면 계산된 sum값을 재활용할 수 있다.

A의 sum값에서 1을 마이너스하고 8을 더하면 B의 sum 값이 된다. 이렇게 구해놓은 sum 값에 없는 값을 빼고 있는 값을 더하는 식으로 새로운 pixel들의 평균값을 빠르게 구할 수 있다. 

Other than the above trick, there is also a quick way to get the average of the long radius pixel.
As we understood, Average = Sum/Count.
If we could reduce the number of times we compute sum, then we could speed up the computation further.
Check out the below idea, you’ll notice we just need to sum up the first pixel. The second (and subsequent) pixel, we just need to minus the front pixel, and add the last pixel, which then eliminates the need for computing the sum.

이런 식의 trick을 적용하면 반지름 값에 관계없이 항상 일정한 속도를 유지할 수 있다. 

Using this approach, regardless of the radius size, it is always flat within the 270-305ms range, as you can see in the chart below.

Stack(Fast) blur 

Mario Klingemann이라는 아티스트가 만든 Stack blur이다. 
Gaussian blur와 동작은 비슷하지만 더 빠르고 똑똑한 blur 계산 방법이다. 아래 웹페이지에서 빠르게 결과물을 확인해볼 수 있다. 
http://www.quasimondo.com/StackBlurForCanvas/StackBlurDemo.html

Optimized Box Blur Approach

먼저 Optimized box blur를 이용해 Stack blur를 이해해보자. 

1. 일단 가로줄들 먼저 계산해 temporary 결과물을 만든다. (Row-by-row)
2. 비슷한 방식으로 1번의 결과물로 세로줄의 평균 값을 구한다. (Column-by-column) 이 결과물이 최종 blur된 이미지다.

First of all, it leverages the optimized box blur approach as described above closely, by having a two-pass operation, i.e.

1. Horizontally, row-by-row compute the stack blur to produce a temporal result.
2. Repeat the similar step as in 1, but instead do it vertically, column-by-column, with the source as the temporal result. The result produces a final blurred image.

그러면 Stack blur single pass는 어떻게 동작할까? Box blur와 가장 큰 차이는 box내의 모든 픽셀의 평균값을 구하는 것이 아니라, 인접한 pixel의 값보다 자기 자신, 구할 pixel을 더 더하는 것이다.

즉, 구할 pixel의 위치에서 멀리 있는 pixel은 sum을 할 때, 덜 더해진다는 의미이다. 
인접한 pixel을 얼마나 더하냐면, (radius - distance - 1) 횟수만큼 더한다. (distance는 구할 pixel로부터 얼만큼 떨어져있는지 거리이다)

The main difference between stack blur and box blur is, instead of getting the average color of the sum of the surrounding radius pixels, it adds itself more times than its neighboring pixels.
The further the neighbor pixel is from the computed pixel, the lesser it will be added to the sum.
As for how many times it will add its neighboring pixel, it is radius - distance - 1, where the distance is how far the neighbor pixel is from the targeted pixel.

이제 그림으로 이해해보자. 큐와 스택이 있다.  각각 큐와 스택은 radius가 3이다. (=(7-1)/2) 
Stack Blur는 스택을 이용해 평균을 구한다. 
Pixel4는 Stack에서 4번, 가장 많이 더해질 숫자이다. (radius +1) 
Pixel3와 5는 3번 더해지고 Pixel2와 6은 2번, Pixel 1과 7은 한 번만 더해진다. 
스택의 모든 숫자를 더하면 4+12+20+28=64이고 16(radius*(radius+2)+1)을 나누면 4를 구할 수 있다. 

This is more clearly illustrated below. Note that Pixel 4 is added most (i.e. radius + 1 times), while Pixel 3 and 5 are added 3 times, Pixel 2 and 6 are added 2 times, and Pixel 1 and 7 are added once only.

Optimized calculation

여기서 값을 더할 때, optimized box blur와 마찬가지로 sum연산을 재활용할 수 있다. 자세히보면 전체 스택은 다음 pixel에 의해 재활용될 수 있다. 아래 그림을 보자. 
다음 pixel을 계산할 때, 기존 스택의 연산에 다음 연산할 pixel에 대해서 더하고 이미 지나간 pixel에 대해서 빼주면 된다. 

At first looks, the computation seems to be complex. However, if examined closely, the entire stack could be reused by the next pixel. Check out the below diagram, it’s pretty similar to the box blur long radius averaging technique.

진행 방법은 다음과 같다.

1.커널과 이미지 픽셀, 큐, 스택이 있다. 그리고 보이지는 않지만 결과가 저장되는 공간이 따로 있을 것이다. 커널은 진행상황을 알려주고(box blur의 long radius 버전이다) 큐와 스택은 왼쪽의 커널로부터 받은 값이 미리 채워져있고 값이 구해져있다.  

2.커널은 왼쪽에서 오른쪽으로 진행하고 새로운 값이 커널에 추가된다. 새로운 값이 추가되면 큐에도 값이 들어오고 큐의 왼쪽 부분은 빠질 부분, 오른쪽 부분은 더해질 부분으로 나뉘게 된다. 큐의 왼쪽 부분은 스택에서 빠지게 되고 오른쪽 부분은 새로이 더해지게 된다. 스택은 가중치를 보여주기 위한 그림이기도 하지만, 사실상 모든 값의 sum 이다. 블러값은 이 합계의 평균이다. 

3. 2의 과정은 반복되고 커널이 오른쪽 밖을 벗어나면 큐에는 오른쪽 값만이 추가된다. 

4. 가로줄의 계산이 끝나면 가로줄을 이용해서 세로줄의 값도 계산된다. 

1.At the left edge queue and stack get profiled with left most edge pixel value.

2.The kernel progresses one pixel to the right. The new value is added to the queue at the right and the leftmost queue value is removed.
Values in the left half of the queue get subtracted from the stack, values in the right half get added to the stack.
The stack is actually just sum of all the values, not a structure it’s just here to visualize the weight of the single values.

3.From now on the process repeats until the kernel is outside the right edge (at the right edge the rightmost pixel value gets added when the parts of the kernel are outside).
When the end of the line is reached the kernel moves down one line and starts refilling like in step #1.

4.When the horizontal pass is finished, the process repeats in vertical direction using the results of the horizontal pass.

Box blur와 Stack blur의 radius 20으로 비교한 결과이다. Stack blur는 2번 적용해도 Box blur보다는 꽃이 덜 손상된 모양새다.
Stack blur once at 20 radius already has a smoother blur.
Stack blur 2 times makes it more blurry, but the blurred flowers are still very much intact.

http://underdestruction.com/2004/02/25/stackblur-2004/
https://medium.com/better-programming/blurring-image-algorithm-example-in-android-cec81911cd5e

Gaussian Blur

English version
http://www.rastertek.com/dx11tut36.html
https://learnopengl.com/Advanced-Lighting/Bloom


The Gaussian Blur algorithm
1. texture에 scene을 render한다.
2. texture를 절반의 사이즈나 그 이하로 Down sample 한다. 
3. Down sample 된 texture에 horizontal blur를 연산한다.
4. Vertical blur를 연산한다.
5. texture를 Original size로 다시 up sample한다.
6. screen에 texture를 렌더링한다. 

Down sample된 texture로 연산 

첫번째 Texture 렌더링은 이미 다룬 내용이다. 두번째 step은 full screen 사이즈 보다 작은 사각형 안에다 full screen texture를 올릴 것이다. 왜 작은 도형에 그리냐면, 일단은 큰 texture보다 작은 texture일 때 연산량이 줄어든다. 두번째 이유로 down sampling후 다시 up sampling했을 때 blur효과를 수행하므로 결과가 두배 더 좋아보인다. Texture를 줄이고 사용한 다음에 날려버려도 되긴 하지만 옛날에 사용되던 알고리즘 방식의 하나이다. (예전에는 real time blur를 수행하기에는 몇 가지 안 되는 옵션 중 하나였다.) (GPU를 programmable 하게 다룰 수 있기 전의 이야기이다.)

Blur 연산 (two-pass Gaussian blur)

Post processing인 blur는 간단하게 구현하면 pixel의 값을 계산하기 위해 둘러싼 모든 pixel의 평균값을 구할 수 있는데 이건 성능엔 좋지 않다. 예를 들면 블러를 계산할 텍스쳐 샘플 박스의 크기가 9x9 pixel이라고 하면 pixel 하나당 모든 pixel의 평균 값이 필요하므로 9x9=81번의 연산이 필요하다.

그래서 Gaussian blur라는 것을 사용할 것이다. Gaussian blur는 Gaussian curve 모양을 기반으로 하는데 가장 높은 값을 중심으로 점차 값이 줄어드는 bell 모양의 곡선으로 표시된다. 

Gaussian curve는 가운데의 가장 큰 영역을 가지고 있으므로 이 값을 가중치로 사용해서 이미지를 blur처리하는데 진하게 표시할 sample일 수록 큰 값을 사용하도록 해서 괜찮은 결과를 얻을 수 있다. 그리고 진하게 표시할 sample에서 멀어질 수록 작은 값을 사용하게 한다. Gaussian blur를 구현하기 위해서는 blur를 계산하는 영역으로(x,y 좌표를 갖는 박스) Gaussian kernal이 하나 필요하다. 이 박스는 가중치를 가지고 있는데, 가중치는 Gaussian curve 2D 방정식을 이용해 얻는다.

우리는 Blurring된 원형의 texture를 한 번에 다 그리지 않는다. 색상 값을 계산하는 연산은 수행하기에 복잡하고 expensive하기 때문에 2단계로 나눠서 수직/수평 linear 선 하나씩만 계산한다.
우선 첫 번째 단계로 수평 pixel의 color값을 먼저 계산한다. 여기서 9x9의 kernel 박스의 크기라면 9번의 연산만 하면 된다. 
다음 단계는 수평 pixel color값을 이용해 수직 pixel들의 color값을 계산한다. 이 수직 pixel color 값은 이미 수평 blur가 적용된 texture를 이용한다. 
이 두 단계의 blur 계산으로 모든 pixel에 gaussian blur가 적용된 텍스쳐를 얻게 된다. 여기서도 9x9의 kernel 박스의 크기라면 픽셀 하나당 9번의 연산만 하면 된다. 
그래서 이 two-pass Gaussian blur 연산으로 픽셀 하나당 9+9=18번의 연산만 필요하게 된다. 

Guassian kernal 영역이 커질 수록 읽어야할 sample 영역이 커지므로 성능에는 좋지 않다. 그리고 pixel의 가중치 값이 1.0일 때, 바로 왼쪽/오른쪽에 있는 pixel값이 0.9라면 그 다음 두번째 인접한 pixel값은 0.8이 된다. 혹은 blur를 더 강하게 적용하려면 1.0, 0.75, 0.5 순으로 weight를 적용할 수 있다.


Further more : Original texture -> FrameBuffer A (horizontal blur) -> FrameBuffer B (vertical blur) -> Main framebuffer

https://forum.libcinder.org/topic/fbo-gaussian-blur-shader-101

Pros vs Cons

Optimized Box blur

장점

단순한 연산 - 모든 픽셀에 동일한 가중치

Due to its property of using equal weights, it can be implemented using a much simpler accumulation algorithm.

단점

블러 퀄리티 문제 - 박스느낌(blocky)을 지울 수 없다.

The blurred image is relatively pixelated, or boxed.

https://medium.com/better-programming/blurring-image-algorithm-example-in-android-cec81911cd5e

 

Stack(fast) blur

장점

Stack blur는 가우시안 블러보다는 빠르고 box blur보다 퀄리티가 좋다. 성능 스피드의 관건은 가운데의 값에 가중치를 주면서 새로운 픽셀을 더할 때, 기존의 스택 값을 이용하고 동시에 제거될 픽셀만 빼는 것이 관건이다. 

This “tower” controls the weights of the single pixels within the convolution kernel and gives the pixel in the center the highest weight. The secret of the speed is that the algorithm just has to add one new pixel to the right side of the stack and at the same time remove the leftmost pixel. 

단점

가우시안보다 퀄리티는 낮은 것 같다. 

 

Gaussian blur

장점

블러 퀄리티가 좋다.

단점

연산량이 많아 모바일 CPU연산엔 성능이 좋지 않다. 

이미지 한장 테스트

• CPU Gaussian blur 2~3초 
• CPU Stack blur 0.5초
• GPU Gaussian blur 5ms
• GPU Stack blur 5ms
• GPU Box blur 5ms

 

 

 

Refer

https://www.youtube.com/watch?v=uZlwbWqQKpc