Efficient Gaussian blur with linear sampling

원문 : Efficient Gaussian blur with linear sampling

이 글은 필요에 의해 모자란 번역실력으로 번역한 글이다.

좀 더 올바른 정보 습득을 위해서는 원문을 추천한다.

선형 샘플링과 효율적인 가우시안 블러

가우시안 블러는 원본 이미지를 부드럽고 흐리게 만드는데 사용하는 이미지 공간 효과다.

그리고 나서 이 이미지는 bloom이나 depth of field, heat haze or fuzzy glass 같은

좀 더 세련된 알고리즘을 만드는데 사용된다.

이 글에서는 효율적인 가우시안 필터를 만들기 위한 다양한 속성을 활용하는 방법과

텍스처 조회texture fetch) 수를 줄이기 위해 선형 텍스처 필터링을 활용하여

기본적인 가우시안 블러 필터 구현 성능을 크게 향상시킬수 있는 기술을 제시한다.

글 자체는 가우시안 블러 필터에 초점을 맞추고 있지만,

제시된 원리는 대부분은 실시간그래픽에서 사용되는 

convolution 필터들에서도 유효하다.

가우시안 블러는 컴퓨터 그래픽 분야에서 폭넓게 사용되고 있고

많은 렌더링 테크닉에서 그럴듯한 photorealistic(실사) 효과를 만들기 위해 사용하지만,

그에 상관없이 오프라인 렌더러나 게임엔진에 대해서 이야기해 보자.

텍스처 결합기를 통해 fragment 처리과정을 설정할수 있게 되면서

가우스 블러 또는 다른 흐림필터를 사용하는 거의 모든 렌더링 엔진에서는

fragment shader를 사용해야 한다.

기본적인 convolution 필터 알고리즘은 다소 비싼 반면,

그 계산 비용을 획기적으로 줄여서 꽤 오래된 하드웨어에서도

실시간 렌더링으로 사용할 수 있게 하는 산뜻한 기술들이 많이 있다.

이 문서는 대부분 현재 추천하는 사용가능한 최적화 기술들을 

제공하기위한 튜토리얼 형식이 될 거다.

이 기술들중 일부가 이미 대부분의 사람들에게 익숙하겠지만

선형 샘플링은 몇몇 사람들에게는 놀라운 방식일 거다.

하지만 바로 선형 샘플링에 대해 이야기 하기보다 기본적인 개념부터 알아보자.

전문용어

글을 읽는데 있어 혼란을 줄이기 위해 이 글의 도입부에 이 글에서 사용하는

몇가지 용어와 개념을 소개한다.

Convolution filter - 픽셀 그룹의 색상값을 조합하는 알고리즘

(추가 설명 : digital image processing에서 모든 채널을 포함한 각 pixel의

brightness값이 주위에 분포된 pixel 값들을 기준으로 다시 계산되는

방식을 convolution 이라고 한다.

이 convolution이 적용되는 룰이 바로 matrix에 의해 결정되기 때문에

통상 matrix를 사용하여 여러가지 효과를 얻어내는 image processing을

convolution이라 하고 convolution을 이용하는 filter을 보통 custom filter라 한다.)

NxN-tap filter - 측면의 길이가 N 픽셀인 정사각형 모양의 필터

N-tap filter - N 픽셀을 사용하는 필터. N-tap 필터가 반드시 N 텍셀을

                  사용하는걸 의미하지는 않으며 N-tap 필터는 N 이하의

                  texel을 사용하여(fetch) 구현할 수 있다.

Filter kernel - 필터의 픽셀을 결합하는데 사용되는 상대좌표와 가중치의 모음.

Discrete sampling - 정확히 한 텍셀을 데이터를 가져올때 쓰는 샘플링 방법

                  GL_NEAREST라고도 한다)

Linear sampling - 최종 색상값을 위해 2x2텍셀을 얻어 이중 선형보간 필터를

                  적용시키는 샘플링 방법.(GL_LINEAR 라고도 한다)

Gaussian filter

이미지 공간 가우시안 필터는 가우시안 함수를 기반으로 한

가중치 픽셀 형식의 NxN-tap convolution filter다. 

이 필터의 픽셀들은 블러효과를 위해 가우시안 함수로부터 

가중치가 적용된 값을 얻어 사용한다.

가우시안 필터의 공간적 표현은 때때로 "bell surface(종 표면)"라고 하며,

아래 그림은 개별 픽셀이 최종 픽셀 색상에 얼마나 기여하는지를 보여준다.

2차원 가우시안 함수의 그래픽적 표현.

이를 기반으로 몇몇은 벌써 "아하, 그래서 NxN texture fetch들을 할때

가중치가 필요하구나" 라고 할지 모른다.

이는 맞는말이지만 그다지 효율적으로 보이진 않는다.

1024 x 1024 이미지의 경우, 전체이미지에서 블러 효과를 주기 위해서는

33x33 tap 가우시안 필터를 기반으로 접근하면 1024 x 1024 x 33 x33 = 11억 4천

이라는 거대한 수의 texture fetche들을 필요로 한다.

보다 효율적인 알고리즘을 위해 가우시안 함수의 좋은 특성 중에 일부를

분석해 봐야 한다.

● 2차 가우시안 함수는 1차 가우시안 함수 두개를 곱함으로써 계산할수 있다.

● 2σ(시그마)의 가우스 함수 분포와 두개의 σ가우스 함수 분포의 결과물은 같다.

이러한 두 가우스 함수의 속성이 우리에게 많은 최적화의 여지를 준다.

첫번쨰 가우시안 함수의 특성을 기반으로, 2차 가우시안 함수를 두개의

1차 가우시안 함수로 나눌 수 있는데, fragment shader의 경우로 보면

가로 블러 필터와 세로블러 필로 가우시아 블러를 분리할 수 있고,

렌더링 후에도 여전히 정확한 결과를 얻을 수 있다.

두개의 N-tap 필터 결과에 추가로 두번째 필터를 위해 필요한 렌더링 패스가 있다.

예제로 돌아가서 1024 x 1024 이미지에 33-tap 가우시안 필터를 두 필터로 사용할 경우

1024 x 1024 x 33 x 2 = 6900백만 texture fetche들이 필요한걸 알 수 있다.

두번째 속성은 단일 패스에서 제한적인 texture fetches를 지원하는 플랫폼에서

하드웨어 제한을 우회하는데 사용될 수 있다.

(추가 설명

33x33 필터를 3개의 9x9 필터로 분해한다.

9+8 = 17 이며 17+16 = 33 이다.

이렇게 한다면 1024 x 1024 x 9 x 9 x 3 = 2억 5천번으로 줄어든다.

위 두가지 속성을 조합한다면 이렇게 생각할 수 있다.

33-tap 필터를 3개의 9-tap 필터로 변형하고 이를 수평과 수직으로 분할한다.

이렇게 할 경우 1024 x 1024 x 9 x 3 x 2 = 5600만개로 최적화 할 수 있다.)

가우시안 커널 가중치

우리는 적어도 이론적으로 우리의 응용프로그램에서 효율적인 

가우시안 블러 필터가 어떻게 만들어 지는지 살펴보았지만,

적절한 결과를 얻기 위해 필터를 이용해서 어떻게 각 픽셀의 가중치를

계산하여 결합할 건지에 대해서는 아직 이야기 하지 않았다.

커널 가중치를 결정하는 가장 간단한 방법은 단순히 가우시안 함수의

분포값을 계산하여 그걸 좌표로 사용하는 것이다.

이게 가장 일반적인 해결방법인데, 이항계수를 사용하여 가중치를

얻을 수 있는 간단한 방법이 있다.

왜 해야 할까?

가우시안 함수는 실제로 정규분포의 분포함수이며,

정규분포의 이산 수치는 샘플의 가중치를 얻기위해 이항계수를

사용하는 이항분포이다.

커널 가중치를 계산하기 위해 사용될수 있는 이항계수를 보여주는 파스칼 삼각형

(각 후속행의 합은 상위 행의 합이다.)

수평과 수직으로 9-tap 가우시안 필터를 구현하기 위해서는 파스칼 삼각형 그림에서

마지막 행의 가중치 값을 사용해야 한다.

아마 8번째 행이 9개의 값을 가지는데 왜 그걸 사용하지 않느냐고 물을지도 모른다.

이는 정당한 질문이지만 대답하기는 쉽다.

전형적인 32비트 컬러 버퍼에서 가장 바깥쪽 계수는 마지막 이미지에 

아무 영향을 주지 않고 두번째 바깥쪽 계수도 거의 영향이 없거나 아예 없기 때문이다.

우리의 9-tap필터는 가능한한 높은 퀄리티의 블러여야만 하지만 texture fetch는

가능한한 최소화 해야 한다.

확실히, 매우 높은 정밀도의 결과는 반드시 더 높은 컬러버퍼가 가능해야 하므로

부동 소수점(floating point) 하나가 8번째 인덱스 행을 사용하는 것이 더 좋다.

하지만 원래의 아이디어에 충실하게 마지막 행을 사용하자...

필요한 계수를 얻음으로써, 픽셀의 선형보간을 위해 사용되어지는 가중치값을

계산하기가 아주 쉬워졌다.

이 경우에는 계수들의 합인 4096으로 계수를 나누어 주기만 하면 된다.

물론 네개의 바깥쪽 계수를 제거해서 4070으로 값을 감소시킬수 있는데

이럴경우 블러를 여러번 하면 이미지가 어두워 질 것이다.

이제, fragment shader에서 가중치 값을 얻는것은 매우 쉬워졌다.

어떻게 GLSL에서 세로(수직)를 계산하는 shader 파일을 보자.

01	uniform sampler2D image;

02

03	out vec4 FragmentColor;

04

05	uniform float offset[5] = float[]( 0.0, 1.0, 2.0, 3.0, 4.0 );

06	uniform float weight[5] = float[]( 0.2270270270, 0.1945945946, 0.1216216216,

07	0.0540540541, 0.0162162162 );

08

09	void main(void)

10

{

11	FragmentColor = texture2D( image, vec2(gl_FragCoord)/1024.0 ) * weight[0];

12	for (int i=1; i<5; i++) {

13	FragmentColor +=

14	texture2D( image, ( vec2(gl_FragCoord)+vec2(0.0, offset[i]) )/1024.0 )

15	* weight[i];

16	FragmentColor +=

17	texture2D( image, ( vec2(gl_FragCoord)-vec2(0.0, offset[i]) )/1024.0 )

18	* weight[i];

19

}

20

}

확실히 가로 필터도 다르지 않는데 fragment shader에서 단순히 x에 

오프셋값을 설정하지 않고 y에 오프셋값을 설정해 주면 된다.

여기서는 1024 크기의 이미지일 경우를 고려해서 이미지 공간 좌표를

나누는 코드를 하드코딩했다.

실제로 구현할 때는 uniform 값으로 대체하거나 단순하게

정규화되어지는 텍스쳐 좌표를 사용하지 않는 텍스쳐의 사각형을 사용한다.

만약 더 강한 블러 효과를 얻기 위해 필터를 몇번 더 적용해야 한다면,

이전 스텝의 결과물을 셰이더에 적용시키면서 두 프레임 버퍼(렌더타겟)을

핑퐁해주기만 하면 된다.

1024 x 1024 이미지에 9-tap 가우시안 블러 필터가 적용된 모습.

필터 미적용(왼쪽),  한번적용(중간), 9번 적용(오른쪽).

클릭해서 전체이미로 보면 다른부분이 더 명확하게 보인다.

선형 샘플링

지금까지, 우리는 9-tap 가우시안 블러를 얻기위해 두 렌더링 패스를 사용하여

분리된 가우시안 필터를 구현하는 방법을 보았다.

또한 5600만 texture fetche들을 사용하여 33-tap 가우시안 블러를 얻기 위해

이 필터를 1024x1024 크기의 이미지로 세번 실행하였다.

이는 꽤나 효율적이긴 하지만 CPU에서 거의 수정되지 않고 잘 동작하는 

알고리즘 형식처럼 GPU의 가능성을 나타내지는 않는다.

이제, GPU의 하드웨어에서 가능한 고정함수의 이점으로

 texture fetch 횟수를 더 줄일수 있는지 알아볼 것이다.

이 최적화를 위해서 이 글을 쓸때 만들었던 가정에 대해서 논의하자.

지금까지, 우리는 하나의 단일 픽셀 정보를 얻기 위해서는 

하나의 texture fetch를 만들어야 한다고 가정했는데,

이는 9개의 픽셀정보를 얻기 위해서는 9번의 texture fetch가 필요하다는 것이다.

CPU에서 구현한다면 이는 맞는 말 이지만, GPU에서 구현한다면

이렇게 할 필요가 없다.

GPU는 이중 선형 필터링을 특별한 비용 없이 처리하기 때문이다.

이는 텍스처의 중간텍셀은 fetch하지 않으면, 여러개의 

픽셀들의 정보를 얻을 수 있다는 것을 의미한다.

실제로 가우시안 함수의 분리적 속성을 사용하여 두개의 1D로

작업하는 하기에 이중 우리에게 선형 필터는 두 픽셀의 정보를 제공할 것이다.

적당한 텍스처의 오프셋을 적용함으로써 하나의 texture fetch로

두개의 텍셀이나 픽셀들의 정보를 정확하게 얻을 수 있다.

이는 9-tap 가로/세로 가우시안 필터를 구현하기 위해 단순히

5번의 texture fetch만 하면 된다는 것을 의미한다.

일반적으로, N-tap 필터는 [N/2] 횟수 만큼의 texture fetch를 필요로 한다.

이전에 사용되어진 가우시안 필터의 이산 샘플의 가중치 값은 어떤 의미인가?

두 텍셀에 관한 정보를 얻기 위해 하나의 texture fetch를 사용하는 경우

두 텍셀에 상응하는 가중치의 합으로 색상값을 구해 가중치를 줘야한다는 의미이다.

이제우리는 가중치가 무었인지 알고 있으므로 적절한 텍스처 오프셋을 계산해야 한다.

텍스처 좌표에서, 단순하게 두 텍셀의 중심 사이의 중간값을 사용할수 있다.

이는 좋은 접근방법이이며 우리가 이산샘플링을 사용했었던 때와 정확히

같은 결과이지만 더 나은 좌표를 계산할수 있도록 하지는 않는다.

두 텍셀을 결합하는 경우 텍셀1의 중심으로부터 정해진 좌표의 거리가

두 가중치의 합으로 나누어준 텍셀2의 가중치와 같게 되도록

좌표를 조정해야 한다.

(texel2 center + offset) == texel2 weight / (texel1 weight + texel2 weight)

결과로, 아래와 같이 선형으로 샘플된 가우시안 블러 필터의 가중치와 오프셋을

정하는 공식을 얻을 수 있다.

이 공식을 이용하려면 아래의 셰이더에서 단지 uniform 상수를 교체하고 

수직필터 반복 횟수를 줄이기만 하면 된다.

01	uniform sampler2D image;

02

03	out vec4 FragmentColor;

04

05	uniform float offset[3] = float[]( 0.0, 1.3846153846, 3.2307692308 );

06	uniform float weight[3] = float[]( 0.2270270270, 0.3162162162, 0.0702702703 );

07

08	void main(void)

09

{

10	FragmentColor = texture2D( image, vec2(gl_FragCoord)/1024.0 ) * weight[0];

11	for (int i=1; i<3; i++) {

12	FragmentColor +=

13	texture2D( image, ( vec2(gl_FragCoord)+vec2(0.0, offset[i]) )/1024.0 )

14	* weight[i];

15	FragmentColor +=

16	texture2D( image, ( vec2(gl_FragCoord)-vec2(0.0, offset[i]) )/1024.0 )

17	* weight[i];

18

}

19

}

이 알고리즘의 단순화는 수학적으로 올바르고 만약 우리가 

이중 선형 필터의 하드웨어 구현으로부터의 결과가 발생 가능한 

반올림 에러를 고려하지 않는다면 이산 샘플링 한 경우처럼

선형 샘플링 셰이더와 정확히같은 결과를 얻을 수 있다.

 

9번 9-tap 가우시안 블러가 이산샘플링으로 적용된 왼쪽과 선형샘플링으로 적용된 오른쪽.

전체해상도로보려면 이미지를 클릭하면된다.

심지어 패스를 몇번 더 돌려도시각적으로 두 이미지간 차이가 없다.

선형샘플링의 구현은 매우 간단하지만 가우스 블러 필터 성능에 상당히

가시적 효과가 있다.

9-tap 필터를 구현하기 위해 9개의 texture fetch 대신에 

단지 5개의 texture fetch를 사용하는 것을 고려하면, 예제로 돌아가서

1024 x 1024 이미지를 33-tap 필터로 블러링 하는데 5600만번 대신

1024 x 1024 x 5 x 3 x2 = 3100만번의 

texture fetch의 이산 샘플링을 요구한다

이는 꽤나 타당한 차이이며, 두 기술간의 차이를측정하기 위해

몇가지 실험을 수행했다.

결과는 명백하다 : 

Radeon HD5770에서 9-tap 가우시안 필터의 이산샘플링과 선형샘플링의 성능비교.

세로축이 초당 프레임률(높을수록 좋다)이며 가로축은

블러의 횟수를 나타낸다.(높을수록 더 흐리다).

위에서 볼 수 있듯이, 선형샘플링으로 구현한 가우시안 필터가

이산 샘플링으로 보다 이미지에 블러 단계를 적용시키는게 

60프로 정도 더 빠르다.

이는 선형필터링을 사용하여 절약되어지는 texture fetch의 수에 얼추 비례한다.

결론

효율적인 가우시안 필터에 대해 알아보았는데 구현이 꽤나 쉽고

특히 선형샘플링을 사용하면 결과가 실시간 알고리즘으로 매우 빨라서

고급 렌더링 기술의 기반으로 사용될수 있다.

이 문서에서는 가우시안 블러에만 집중했음에도 불구하고,

대부분의 convolution 필터 타입들에 적용하는 원리에 대해

많이 논의하였다.

또한 일반적으로 블룸효과에서 필요로 하는 사이즈를 줄인 

블러 처리된 이미지가(다운샘플링 관련) 필요한 경우 선형 샘플링을

포함해서 대부분의 이론이 적용된다.

크기를 줄인 블러된 이미의 경우 실제로 다른것은

pixel의 중심이 "두개의 픽셀"이라는 것이다.

이는 우리가 파스칼 삼각형에서 행을 선형샘플하는 중간 텍셀들도 

짝수의 계수를 가지는 행을 사용해야 한다는 것을 의미한다.

또한 우리는 다양한 기술들의 복잡성 계산과 

어떻게 GPU에서 필터가 효율적으로 구현되어질 수 있는가에 대해

간단한 통찰을 가졌다.

데모 프로그램은 이산 샘플링과 선형샘플링 방법에 대한

효율성을 비교하기 위해 만들어졌고 아래 링크에서 다운로드 받을 수 있다.

Binary release

Platform: Windows
Dependency: OpenGL 3.3 capable graphics driver
Download link: gaussian_win32.zip (2.96MB)

Source code

Language: C++
Platform: cross-platform
Dependency: GLEW, SFML, GLM
Download link: gaussian_src.zip (5.37KB)

Reference Link

- convolution filters

- GL_NEAREST vs GL_LINEAR

- binormal coefficient (이항계수)

- binomial distribution (이항분포)

-