Realizing dreams and hopes

1. Guided Image Filter

영상의 필터링을 함에 있어 가우시안 분포 기반의 필터링은 임의로 발생하는 잡음을 자연스럽게 잡아줄 수 있다는 장점이 있다. 가우시안 분포를 이용한 필터링에는 가우시안 필터 뿐만 아니라 양방향 필터(Bilateral Filter), 그리고 결합 양방향 필터(Joint Bilateral Filter)가 존재한다.

위 그림에서 (a)가 가우시안 필터에서의 연산, (b)가 양방향 필터에서의 연산 방법이다. (a)와 달리 (b)에서는 값의 변화가 급격하게 일어난 부분에 대해서는 가우시안 커널의 값을 곱해주지 않았다. 이 부분이 바로 양방향 필터와 가우시안 필터가 갖는 큰 차이점이다. 여기서 나아가 결합 양방향 필터는 가이드 영상을 이용하는 방법이 추가됐는데, 여기서의 가이드 영상은 Ground Truth와 같은 목표하는 결과물을 사용할 수 있다고 한다. 이 필터에 대한 자세한 이야기는 차후에 다루는 쪽으로 하겠다.

이 글에서 다루고자 하는 필터는 Guided Image Filter인데, 이 필터의 가장 큰 장점은 결합 양방향 필터처럼 가우시안 커널과 같은 별도의 커널을 적용하지 않고 가이드 영상 하나를 활용한다는 점이다. 이로 인해 결합 양방향 필터가 갖는 다음의 두 단점을 해결해준다.

1. 가우시안 커널을 사용하는 연산이기 때문에 연산 속도가 느리다.

2. 영상의 기울기 값 부근에서 왜곡이 발생할 수 있다.

위 그림은 결합 양방향 필터와 가이디드 영상 필터를 이용한 필터링 과정을 대략적으로 보여준다. 앞서 언급했던 가우시안 커널을 응용한 양방향 커널을 사용하는 결합 양방향 필터와는 달리 가이디드 영상 필터링은 Window 크기 내에 있는 픽셀 값들의 평균과 분산, 상관계수 등의 값을 활용한다. 논문에 제시된 알고리즘의 흐름은 다음과 같다.

가이드 영상과 입력 영상에 대한 평균과 분산, 공분산 등을 1,2와 같이 계산한 뒤, a와 b를 정의하고 정의된 a와 b 값에 대해 평균을 구한다. a와 b의 평균값, 그리고 가이드 영상을 이용해 5번 연산을 수행하면 최종 필터링 결과물인 q를 얻을 수 있다. 주석에 나와있듯이 f_mean은 mean filter 결과를 사용한다.

알고리즘에 나와 있듯이, 필요한 연산의 갯수는 결합 양방향 필터에 비해서는 많은 편이다. 그러나 이를 구현하면 속도 면에서는 크나큰 향상을 보일 수 있다.

2. Fast Guided Filter

이 필터는 기존 가이디드 영상 필터에서 파생된 방법으로, 기본 개념은 다운샘플링을 통해 연산 속도를 더욱 향상시킨다는 점이다.

두 필터링 알고리즘을 비교하면 위 사진과 같다. 가이드 영상과 입력 영상의 평균을 구하기 전에 두 영상을 정해진 비율 만큼 다운샘플링하고, 그 결과를 이용해 가이디드 영상 필터링을 수행한다. 이 후의 필터링 과정에 대해서는 a와 b의 평균을 구하는 것 까지는 같으나, 최종 결과물인 q를 얻기 이전에 a와 b의 평균에 대해 다시 원래의 크기로 업샘플링을 수행하고 이 결과물과 가이드 영상을 이용해 최종 결과를 얻는다는 차이가 있다.

References

[1] He, K., Sun, J., & Tang, X. (2013). Guided image filtering. IEEE transactions on pattern analysis and machine intelligence, 35(6), 1397-1409.
[2] https://arxiv.org/abs/1505.00996

Mitsuba란 PBRT로부터 파생되어 나온 물리 기반 렌더러 프로그램이다.

단순히 렌더링 테스트를 할 수 있을 뿐만 아니라 C++를 통해 본인만의 렌더링 알고리즘을 구현해 테스트하는 것도 가능하다.
설치 및 관련 문서 등은 아래 사이트를 통해 확인할 수 있다.
https://www.mitsuba-renderer.org/

1. Windows에서 설치

윈도우에서 설치하는 방법은 아래 사이트에 적힌 방법을 토대로 문제점이 발생하는 부분에 대해 고쳐가며 설치 수행
https://www.ics.uci.edu/~yug10/projects/mitsuba/mitsuba_install.md.html

1) Visual Studio 2013 설치
2015의 지원 여부는 아직 확인하지 못했지만, 아직까지 미쯔바는 VS 2010과 2013버전만 지원한다고 한다. 따라서 미쯔바 설치를 위해서는 우선 VS 2013을 설치할 것.

2) Python 2.7 설치
윈도우 환경에서 파이썬을 설치하기 위해 우선 Anaconda를 설치한다.
https://www.anaconda.com/download/#windows

파이썬 버전에 맞게 설치할 수 있는데, 여기서는 2.7 버전에 맞게 설치를 진행한다.

아나콘다의 설치가 끝나면 아래 링크에서 파이썬 2.7 버전 설치 파일을 다운받아 설치를 수행한다.
https://www.python.org/downloads/windows/

3) Scons 설치
미쯔바를 컴파일해서 실행 파일을 만들어내기 위해 Scons를 사용한다. Scons는 아래 링크에서 다운받을 수 있다.
https://scons.org/pages/download.html

4) (Optional) PyWin 32 설치
선택사항인데, Gradient-domain path tracing을 쓰기 위해서 필요하다.
PyWin32: https://sourceforge.net/projects/pywin32/files/pywin32/Build216/
Gradient-domain path tracing: https://github.com/mmanzi/gradientdomain-mitsuba

5) Mitsuba 다운로드
공식 사이트에서 배포판 버전으로 처음부터 다운로드받을 수 있는 듯하나, 연구 목적으로 설치를 하는 것이므로 컴파일 이전의 형태를 아래 링크에서 받도록 한다.
https://www.mitsuba-renderer.org/repos/mitsuba

다운받은 압축파일은 원하는 경로에 압축을 해제한다.

6) Mitsuba dependencies 다운로드
위에서 받은 미쯔바의 저장 경로로 들어가 해당 경로 내에 dependencies 폴더를 생성한다.
이 후, 아래 링크에서 dependencies를 받아 저장해준다.
윈도우용 설치이기 때문에 여기선 윈도우용 dependencies를 다운로드한다.
https://www.mitsuba-renderer.org/repos/dependencies_windows

7) config 불러오기
미쯔바가 설치된 경로의 build 폴더로 들어가면 여러 환경에 해당하는 파이썬 코드 형태의 config파일이 존재한다.

여기서는 VS2013 환경에 맞게 설치할 예정이기 때문에 이에 맞는 파이썬 파일을 복사한다.

복사한 config 파일은 미쯔바 메인 폴더에 붙여넣고, 이름을 config.py로 바꿔준다.

8) SCons 컴파일 실행
SCons 컴파일은 아나콘다 프롬프트를 통해 수행한다.
아나콘다 프롬프트를 실행하고, 콘솔 창에서 미쯔바가 설치된 경로로 이동한다.

이동 후, 다음 명령어를 입력하여 컴파일을 시작한다. 

scons -j8

(-j8은 8개의 CPU 코어를 써서 병렬 컴파일을 수행하겠다는 의미. 생략해도 무방)

<Problem> Could not compile a simple C++ fragment, verify that cl is installed.

다음과 같은 오류 메시지가 출력됐을 경우, boost 라이브러리를 찾을 수 없음을 의미한다.

이 경우, build 폴더 내에 있는 SConscript.configure 파일의 내용을 아래 사진과 같이 수정한다.

9) (Optional) 볼륨기반 렌더링을 위한 설정
볼륨기반 렌더링을 위한 설정이라고 한다.
아래 링크에 있는 소스 코드를 다운로드한 뒤, 미쯔바가 설치된 경로 내 /src/volume/ 폴더에 저장한다.

https://www.ics.uci.edu/~yug10/projects/mitsuba/gridvolumeSimple.cpp

이 후, SConscript.configure 파일에 다음의 내용을 추가한다.

plugins += env.SharedLibrary('gridvolumeSimple', ['gridvolumeSimple.cpp'])

내용을 추가하면 scons를 통해 미쯔바를 다시 컴파일해 갱신된 배포판을 얻는다.

10) 테스트
테스트는 콘솔 환경과 GUI 환경에서 모두 가능하다.
콘솔 환경에서 테스트 할 경우, 아래 명령어를 입력해서 수행한다.

mitsuba $PATH_TO_XML\test_emitter.xml

혹은 dist 폴더에 생성된 exe 파일을 실행한 후, 원하는 xml 파일을 불러와 렌더링을 수행한다.

2. Ubuntu에서 설치

- 설치 시도 중 fftw3 설치에 문제가 있어 중단. 해결되는대로 작성 예정.

3. MacOS에서 설치

- 차후 시도 후 작성 예정

트리 형태의 구조에 대해 이 트리를 탐색할 때 사용하는 탐색법에는 깊이 우선 탐색과 너비 우선 탐색 두 방법이 있다.

하나의 트리가 있을 때, 깊이 우선 탐색의 경우에는 기준 노드로 부터 하나의 자식 노드로만 내려간다. 점점 자식 노드로 내려가며 밑으로 파고드는 형태로 탐색을 수행하게 된다. 반면, 너비 우선 탐색은 하나의 노드가 가지고 있는 모든 자식들을 우선적으로 넓게 탐색하고, 이 자식들에 대해서도 노드 하나가 갖는 바로 아래 자식 노드를 넓게 탐색하며 내려가는 형태로 탐색하는 방법을 말한다.

이 글에서는 간단하게 구현 요령이나 어느 문제에서 활용하는 것이 유용할지에 대해 짤막하게 언급하고자 하기 때문에 자세한 설명은 우선 생략하겠다.

깊이 우선 탐색을 구현할 때는 보통 스택 자료구조를 사용해서 탐색을 수행한다.

자식 노드로 내려가며 탐색을 수행하는데, 더 이상 내려갈 자식 노드가 없다면 다시 위로 돌아와야 하는데, 이 돌아오는 과정에서 스택의 pop 연산을 통해 되돌아가는 식으로 구현이 되어야하기 때문이다.

그러나 스택을 일일이 구현해서 하는 방법 외에 재귀 함수 형태로 탐색을 구현하는 방법도 사용될 수 있다고 한다.

이 경우, 별도로 스택같은 자료 구조 구현이 필요 없다는 장점을 가지고 있다.

너비 우선 탐색은 큐를 이용해서 탐색 알고리즘이 구현된다.

큐 같은 경우에는 알고리즘 문제에서 사용 되는 일반적인 언어 (C++, Java, Python)에 표준 라이브러리로써 존재한다.

따라서 스택처럼 별도의 라이브러리를 불러온다거나 직접 구현한다던가 하는 번거로움이 없다는 이점이 있다.

그렇다면 이 두 탐색을 실전 알고리즘 문제에서 활용한다고 할 때, 어떠한 경우에 어떤 탐색법을 활용하는 것이 좋을까?

깊이 우선 탐색의 경우,

• 트리의 모든 경로를 탐색하고, 이에 대한 결과들을 일일이 확인해야만 한다
• 사전에서 특정 단어를 탐색하는 경우처럼 앞에서부터 탐색해서 찾는 것이 효율적인 경우에 대해

이 두 가지의 경우, 깊이 우선 탐색을 활용하는 것이 더 효율적이라고 한다.

반대로 너비 우선 탐색의 경우,

• 특정 지점에서 가장 가까운 것을 찾고자 하는 경우
• 탐색 범위가 굉장히 넓은 경우. 깊이 우선 탐색을 사용할 때 스택이 대량으로 발생한다면 너비 우선 탐색이 더 효율적이다.
• 특정 지점을 기준으로 어느 정도 근처에 구하고 싶은 해가 존재한다는 사실을 알고 있을 때

이러한 세 가지의 경우, 너비 우선 탐색을 사용해 문제를 해결하는 것이 보다 효율적이라고 한다.