Fully Connected Neural Network로 학습된 Neural Graphic Primitive는 훈련이랑 연산 비용이 많이 듭니다.
우리는 작은 네트워크를 사용해서 이 비용(floating pint, memory access)을 줄이면서도, 품질을 좋게 유지할 수 있는, 다재다능한 새 input encoding 방법을 제안합니다.
Multi Resolution 구조는 해쉬 충돌을 막는데 도움을 주며, 병렬화하기도 쉽습니다.
그러므로, 이에 최적화된 시스템을 구성해서, 1920x1080 해상도의 이미지를 milisecond 단위에서 렌더링할 수 있습니다.
computer graphic primitive는 기본적으로 특정 모양을 매개변수로 사용하는 수학적 함수로 표현됩니다.
여기서 primitive는 high-frequency 정보와 local detail을 담기를 바랍니다.
주로 neural graphic primitive로서 사용되는 MLP는 이러한 조건들을 만족하는 것으로 나타납니다.
이런 작업을 할 때, 인코딩은 매우 중요한데, 인코딩이란 입력값을 고차원 공간에 mapping하는 것으로 compact한 model에서 높은 품질의 approximation을 가능하게 합니다.
Adaptivity : 계층별 그리드 구조를 그에 상응하는 고정된 크기의 feature vector로 매핑합니다.
대부분의 경우 gride point는 hashe table과 1:1 mapping 관계를 가지지만, 충돌이 발생하는 경우 gradient의 기울기가 평균이(?)되는 문제가 있으므로, 희소 영역에 대해서는 우선순위를 정할 필요가 있습니다.
Efficiency : 해쉬 테이블 사용시 O(1)의 계산 복잡도를 가지고, GPU에 최적화된 구조로 적용할 수 있습니다.
제안된 방법은 다음의 4가지 테스크에서 좋은 성능을 보여줍니다.
Gigapixel Image : MLP가 2D 좌표에서의 RGB 색상을 좀 더 고해상도로 매핑하는 방법을 배웁니다.
SDF - Neural Signed Distance Function : MLP가 3D 좌표에서 지표면까지의 거리에 대한 매핑을 학습할 수 있습니다.
NeRF - Neural Radiance and density Fields : MLP가 관측된 이미지로부터 3D density나 5D light field를 학습합니다.
Encoding : 인공지능을 이용한 학습에서는 다양한 인코딩 방법들이 있습니다.
one-hot encoding이나 kernel trick같은 방법들은 복잡한 데이터의 배열들을 선형으로 만드는 방법이 예전에는 많이 쓰였습니다.
Input Encoding의 경우에는 recurrent architecture나 Transformer에서 유용함이 예전에 입증되었습니다.
이러한 방법은 Neural Network가 현재 처리중인 특징정보의 위치를 파악하는데 도움이 됩니다.
그렇기에 이러한 Encoding과 관련해서는 다양한 방법들이 제안되었습니다.
주파수 기반의 Encoding을 시작으로, 좋은 성능을 보여주는 여러가지 Encoding들이 많이 제안되었습니다.
Parametric Encodings : 최근, 고전적 데이터 구조와 신경망의 접근 방식 사이의 경계에 있는 parametric encoding 기법들이 Sota를 찍고 있습니다.
parametric encoding들은 grid와 같은 추가적인 데이터 구조에서 학습 가능한 매개 변수들을 정렬하는 것입니다.
이러한 방법들은 적은 계산 비용을 사용하기 위해서 많은 메모리를 사용하는게 특징입니다.
예를 들어서, 3D그리드의 경우에는 각 샘플에 대해서 8개의 포인트를 업데이트하면 되는데, 매개 변수의 총 개수를 고정 입력 인코딩보다 많이 사용하지만,훈련 중 업데이트할 때 필요한 FLOPS 및 Memory Access의 수는 크게 증가하지 않습니다.
이러한 parametric encoding 방법은 MLP의 크기를 줄이면서도, quality를 희생하지 않고 훨씬 빠르게 수렴하도록 학습할 수 있습니다.
Parametric Encoding은 그동안 높은 정확도에 비해서, Efficiency가 낮고, 범용성이 떨어졌습니다.
Dense-grid한 방법들의 경우에는 일반적인 신경망의 weight보다 많은 memory들을 사용한다는 단점들이 있었습니다.
다음 그림을 가지고 예를 들어 보겠습니다.
fast NeRF로, 11000step을 학습하는동안 서로 다른 인코딩과, parametric data structure에 따른 성능 차이를 비교한 것입니다.
성능은 MLP weights, encoding parameter, trainint time, reconstructino accuracy(PSNR)순입니다.
(a) input data에 아무런 인코딩을 안한 경우에는 매우 blur하게 나오는 것을 알 수 있습니다.
이는 네트워크가 position과 관련해서 학습할 수 있는 정보량이 부족하기 때문에, light field에서 근사하는데 어려움을 겪는 것입니다.
(b) Frequency encoding 기법들의 경우에는 성능은 무난하게 나오는데, 학습 시간이 오래 걸립니다.
중간 크기의 네트워크가 사용되었습니다.
(c) Dense grid 방법의 경우에는 33M의 추가적인 encoding parameter가 필요하지만, 학습 시간이 1/10로 줄었습니다.
그리고 각 샘플은 8개의 grid point에만 영향을 미치므로 학습 과정에서 적은 시간안에 효율적으로 학습이 가능합니다.
(d) 추가로, Multi resolution을 넣은 경우에는 파라미터도 줄고, 성능이 많이 올라간것을 알 수 있습니다.
그러나 이러한 grid 방법은 두가지 측면에서 단점이 존재하는데
빈 공간이 많다는 것입니다. object는 실제 공간내에 일부에만 존재합니다. 애략적으로 보면, 관심영역은 O(N^2)이지만, 전체 영역은 O(N^3)에 해당합니다. 예를 들어 예시에서 실제 오브젝트가 공간을 차지하는 비율은, 전체 영역의 2.57%에 불과합니다.
Natural scenes을 자연스럽게 표현하기 위해서는 Multi resolution decompisition이 필요합니다.
(d)를 보게 되면, 8개의 grid로부터 interpolated된 feature를 학습에 사용한 것입니다. 2-dimensional feature가 8개의 feature를 사용해서, 16차원의 input vector를 생성하게 됩니다. 매개변수는 (c)의 절반에 불과함에도 성능은 늘어난 것을 볼 수 있습니다.
이러한 관점에서, sparse parametric encoding이 얼마나 중요한지 알 수 있습니다.
본 논문에서 제안하는 방법(e, f)은 이러한 단점들을 보완하기 위해서 제안되었습니다.
학습에 사용되는 trainable feature vector를 hash table에 저장해서 메모리를 줄이고, task에서 요구하는 quality에 따라 임의로 조정할 수 있도록 설정하였습니다. (여기서 중요한 것은, Hash table의 크기에 따라 성능이 좌지우지 되는 거라서, 학습 시간은 그대로라는 점입니다.)
또한, Multi-Resolution grid와 유사하게 Multi-Resolution Hash Table을 사용해서 서로 다른 resolution에서 학습한 hash table이 MLP를 통과하기 전에 interpolation된 후, concat되서 사용됩니다.
해당 방법은 매우 좋은 성능에서, dense-grid 방법에 비해 최대 20배 적은 파라미터로 학습 가능합니다.
해당 방법론에서는 hash collision에 대해서는 따로 처리하지 않습니다. Network에 충돌을 최대한 피할 수 있도록 학습함으로써, control flow divergence(?)를 방지하고 구현 복잡성을 줄이는 동시에 성능 또한 올리도록 합니다. 또한, cache는 데이터 구조에 영향을 좀 받는 편인데, 이러한 부분도 피해갈 수 있습니다.
Multi-Resolution Hasn Encoding
본 논문에서 제안하는 인코딩 방식은 다음과 같습니다.
특정 좌표 x가 주어지면, Multi-Resolution에서 각각 복셀을 찾고, 인접한 grid 각각에 할당해줍니다.
모서리의 각 좌표들을 모두 알아냈다면, 이를 통해 해당하는 F-dimensional feature vector를 hash table로부터 얻어 올 수 있습니다.
x의 좌표에 따라, 모서리로부터 떨어진 거리를 기반으로 feature vector들을 선형으로 보간해줍니다.
그런 다음, 각 resolution level에 해당하는 feature vector들을 concat해서 하나의 feature vector로 만듭니다. 여기에 추가적으로 보조 정보들이 auxiliary input으로 사용됩니다..(view direction이나 neural radiance caching의 textures 같은 것들, 그림에서 concatenation파트에서 초록색 블록들)
이렇게 만들어진 vector는 MLP를 통해서 encoding하는 방법을 학습하게 됩니다.
원본에 가장 먼 해상도를 N_min으로, 원본에 가장 가까운 해상도를 N_max라고 하겠습니다.
그러면 다음과 같이 정의할 수 있는데,
만약 Resolution 단계가 많아지면, resolution간 배율에 해당하는 b는 작아지게 될겁니다. 본 논문에서 resolution간 배율인 b는 [1.26, 2]로 정해집니다.
입력 좌표값은 2^d개의 vertices에서 나타낼 수 있습니다.
각 모서리는 최대 T라는 고정된 크기의 feature vector array에 매핑합니다.
corase한 level의 dense grid는 T보다 적은 파라미터를 사용합니다.
finer level에서는 해쉬 함수를 통해서 index값을 array로 해쉬 충돌 없이 매핑해줍니다.
우리는 spatial hash function으로 을 사용합니다.
⊕ 는 xor operation을, 𝜋는 큰 소수값을 의미합니다.
이 공식은 효과적으로 dimension linear congruential permutation의 결과를 XOR하여 해시된 값에 대한 차원의 영향을 상관관계를 해제합니다??
해쉬 값들끼리 독립적이기 위해서는 d차원 중 d-1개만 순열되어야 하므로, 더 나은 캐시 일관성을 위해 𝜋1 := 1, 𝜋2 = 2 654 435 761 및 𝜋3 = 8861 459를 선택합니다.
마지막으로, gride의 corner의 feature vector는 hypercube내 x의 위치에 따라 d-선형으로 보간됩니다.
보간에 사용되는 가중치는 w𝑙 := x𝑙 − ⌊x𝑙⌋.입니다.
해당 작업은 Multi-Resolution의 각 레벨별로 이루어지며, 보간된 feature vector 뿐만 아니라 보조적인 특징 정보들이 MLP학습을 위한 auxiliary input으로 사용됩니다.(view direction이나 neural radiance caching의 textures 같은 것들)
해쉬 함수를 사용하는 이유는, grid의 각 corner를 고유한 값에 매핑하는것이 목적이 아니라, 이를 최대한 효율적으로 생성하는 것입니다.
gird의 각 corner를 고유한 key값을 갖는 hash table로 만들기 위해서는, 데이터의 갯수만큼의 hash table이 있어야 하지만, 우리가 데이터의 실질적인 갯수를 모를 때에는 hash table의 길이를 임의로 지정하기도 힘들며, 이는 모두 addictional cost입니다.
그렇다면, hash를 일정한 크기로 만든 후, 추가적으로 들어오는 것에 대해서는 연결 리스트처럼 사용하면 될겁니다.
이걸 체이닝 방식이라고 합니다.
그런데, 만약 특정 hash key에만 value들이 매핑 될 경우, 최악의 경우에는 특정 key에 모든 값들이 매핑되고, 연결 리스트의 빅오인 O(n+1)을 갖게 될겁니다.
그렇다면, 이렇게 hash 충돌이 발생 했을 때, 탐색시간을 최소한으로 갖기 위해서는, 모든 hash들이 uniform하게 분포해야 겠죠.
hash는 다양한 방법이 있지만, 이 중 대표적인 방식이 division method인데, modular연산을 사용하는 방법입니다.
특정 key를 어떤 수로 나눈 나머지를 해쉬 값으로 사용하는 것입니다.
예를 들어 m이 100이면 k mod m은 0~99까지의 범위를 지니게 됩니다.
이 m의 범위는 해쉬 테이블의 성능과 크게 연관되는데, m은 보통 키의 수의 3배 이상으로 사용합니다.(적재율 30%까지는 충돌이 거의 일어나지 않으므로..) 또한, m은 2의 지수승에 근접한 소수를 사용해야 하는데, 만약 m이 2^3이면, 2진수로 00001000이고, 4번째 이하의 숫자만 해쉬값에 영향을 미치기 떄문입니다.
그렇게 되면, k1과 k2가 각각 10110100, 10120100이면 둘 다 같은 해쉬값을 출력해버리게 됩니다.
즉, 가장 최적의 m의 크기는 키의 갯수의 3배이며 2의 지숫승에 근접한 소수입니다.
인용 - https://hsp1116.tistory.com/35
이제, 여기서 추가적으로 hash collision을 효율적으로 방지할 수 있는 기법을 하나 추가하도록 하겠습니다.
hash(x,y,z) = ( xp1 xor yp2 xor z*p3) mod n
우선, 3차원에서의 좌표 x,y,z와, p1, p2, p3라는 큰 소수(73856093, 19349663, 83492791)를 사용합니다.
여기서 n은 hash table의 size입니다.
이렇게 하는 이유는 보통 2가지인데,
계산된 해쉬값들이 '동일한 확률'로 골고루 나타날 것 = 충돌횟수를 줄이기 위함.
각각의 해쉬값들은 서로 여관성을 가지지 않고 독립적으로 생성될 것. 이는 값들끼 연관성이 있다면 해쉬값이 등장할 패턴이나 순서가 발생할 수 있기 때문에 충돌 횟수를 줄이기 위함입니다.
해쉬 결합이란 보통, 여러가지 해쉬들을 결합함으로써, 데이터의 크기를 줄이는 것이 주 목적입니다.
본 논문에서는 hash table의 크기를 500K-12.6M개의 파라미터를 갖도록 설정하는데, 해쉬 결합을 하지 않는다면, key가 x,y,z좌표를 갖는것이 어려워지게 됩니다. 만약 key 때문에 hash table의 수가 3배가 된다면, 파라미터는 1.5M-40M가 되어버릴테니까요.
그렇기에, 본 논문에서는 x,y,z의 좌표를 큰 소수들과 곱한 뒤, x,y,z를 xor해서 결합해 하나의 key로 만들어줍니다.
Performance vs. quality
hash table의 사이즈 T에 따른 PSNR성능을 비교한 그래프입니다.
hash table의 사이즈에 따라서 성능이 상당히 많이 증가하는 것을 알 수 있습니다.
하지만, 연산량이나 상승폭을 비교해보면 maximum은 19로 잡는게 좋아 보입니다.
multi-resolution에서 resolution level과, hash table의 feature 갯수에 따른 성능 차이입니다.
F가 2일 때 가장 안정적으로 좋은 성능을 나타내는 것을 보여 주고 있습니다.
gusdlf93
commented
2 years ago
Fully Connected Neural Network로 학습된 Neural Graphic Primitive는 훈련이랑 연산 비용이 많이 듭니다. 우리는 작은 네트워크를 사용해서 이 비용(floating pint, memory access)을 줄이면서도, 품질을 좋게 유지할 수 있는, 다재다능한 새 input encoding 방법을 제안합니다. Multi Resolution 구조는 해쉬 충돌을 막는데 도움을 주며, 병렬화하기도 쉽습니다. 그러므로, 이에 최적화된 시스템을 구성해서, 1920x1080 해상도의 이미지를 milisecond 단위에서 렌더링할 수 있습니다.
computer graphic primitive는 기본적으로 특정 모양을 매개변수로 사용하는 수학적 함수로 표현됩니다. 여기서 primitive는 high-frequency 정보와 local detail을 담기를 바랍니다. 주로 neural graphic primitive로서 사용되는 MLP는 이러한 조건들을 만족하는 것으로 나타납니다.
이런 작업을 할 때, 인코딩은 매우 중요한데, 인코딩이란 입력값을 고차원 공간에 mapping하는 것으로 compact한 model에서 높은 품질의 approximation을 가능하게 합니다.
Adaptivity : 계층별 그리드 구조를 그에 상응하는 고정된 크기의 feature vector로 매핑합니다. 대부분의 경우 gride point는 hashe table과 1:1 mapping 관계를 가지지만, 충돌이 발생하는 경우 gradient의 기울기가 평균이(?)되는 문제가 있으므로, 희소 영역에 대해서는 우선순위를 정할 필요가 있습니다.
Efficiency : 해쉬 테이블 사용시 O(1)의 계산 복잡도를 가지고, GPU에 최적화된 구조로 적용할 수 있습니다.
제안된 방법은 다음의 4가지 테스크에서 좋은 성능을 보여줍니다.
Encoding : 인공지능을 이용한 학습에서는 다양한 인코딩 방법들이 있습니다. one-hot encoding이나 kernel trick같은 방법들은 복잡한 데이터의 배열들을 선형으로 만드는 방법이 예전에는 많이 쓰였습니다. Input Encoding의 경우에는 recurrent architecture나 Transformer에서 유용함이 예전에 입증되었습니다. 이러한 방법은 Neural Network가 현재 처리중인 특징정보의 위치를 파악하는데 도움이 됩니다. 그렇기에 이러한 Encoding과 관련해서는 다양한 방법들이 제안되었습니다.
주파수 기반의 Encoding을 시작으로, 좋은 성능을 보여주는 여러가지 Encoding들이 많이 제안되었습니다.
Parametric Encodings : 최근, 고전적 데이터 구조와 신경망의 접근 방식 사이의 경계에 있는 parametric encoding 기법들이 Sota를 찍고 있습니다. parametric encoding들은 grid와 같은 추가적인 데이터 구조에서 학습 가능한 매개 변수들을 정렬하는 것입니다. 이러한 방법들은 적은 계산 비용을 사용하기 위해서 많은 메모리를 사용하는게 특징입니다.
예를 들어서, 3D그리드의 경우에는 각 샘플에 대해서 8개의 포인트를 업데이트하면 되는데, 매개 변수의 총 개수를 고정 입력 인코딩보다 많이 사용하지만,훈련 중 업데이트할 때 필요한 FLOPS 및 Memory Access의 수는 크게 증가하지 않습니다. 이러한 parametric encoding 방법은 MLP의 크기를 줄이면서도, quality를 희생하지 않고 훨씬 빠르게 수렴하도록 학습할 수 있습니다.
Parametric Encoding은 그동안 높은 정확도에 비해서, Efficiency가 낮고, 범용성이 떨어졌습니다. Dense-grid한 방법들의 경우에는 일반적인 신경망의 weight보다 많은 memory들을 사용한다는 단점들이 있었습니다. 다음 그림을 가지고 예를 들어 보겠습니다.
(a) input data에 아무런 인코딩을 안한 경우에는 매우 blur하게 나오는 것을 알 수 있습니다. 이는 네트워크가 position과 관련해서 학습할 수 있는 정보량이 부족하기 때문에, light field에서 근사하는데 어려움을 겪는 것입니다. (b) Frequency encoding 기법들의 경우에는 성능은 무난하게 나오는데, 학습 시간이 오래 걸립니다. 중간 크기의 네트워크가 사용되었습니다. (c) Dense grid 방법의 경우에는 33M의 추가적인 encoding parameter가 필요하지만, 학습 시간이 1/10로 줄었습니다. 그리고 각 샘플은 8개의 grid point에만 영향을 미치므로 학습 과정에서 적은 시간안에 효율적으로 학습이 가능합니다. (d) 추가로, Multi resolution을 넣은 경우에는 파라미터도 줄고, 성능이 많이 올라간것을 알 수 있습니다.
그러나 이러한 grid 방법은 두가지 측면에서 단점이 존재하는데
이러한 관점에서, sparse parametric encoding이 얼마나 중요한지 알 수 있습니다.
본 논문에서 제안하는 방법(e, f)은 이러한 단점들을 보완하기 위해서 제안되었습니다. 학습에 사용되는 trainable feature vector를 hash table에 저장해서 메모리를 줄이고, task에서 요구하는 quality에 따라 임의로 조정할 수 있도록 설정하였습니다. (여기서 중요한 것은, Hash table의 크기에 따라 성능이 좌지우지 되는 거라서, 학습 시간은 그대로라는 점입니다.) 또한, Multi-Resolution grid와 유사하게 Multi-Resolution Hash Table을 사용해서 서로 다른 resolution에서 학습한 hash table이 MLP를 통과하기 전에 interpolation된 후, concat되서 사용됩니다. 해당 방법은 매우 좋은 성능에서, dense-grid 방법에 비해 최대 20배 적은 파라미터로 학습 가능합니다.
Multi-Resolution Hasn Encoding 본 논문에서 제안하는 인코딩 방식은 다음과 같습니다.
원본에 가장 먼 해상도를 N_min으로, 원본에 가장 가까운 해상도를 N_max라고 하겠습니다. 그러면 다음과 같이 정의할 수 있는데,
만약 Resolution 단계가 많아지면, resolution간 배율에 해당하는 b는 작아지게 될겁니다. 본 논문에서 resolution간 배율인 b는 [1.26, 2]로 정해집니다.
입력 좌표값은 2^d개의 vertices에서 나타낼 수 있습니다. 각 모서리는 최대 T라는 고정된 크기의 feature vector array에 매핑합니다. corase한 level의 dense grid는 T보다 적은 파라미터를 사용합니다. finer level에서는 해쉬 함수를 통해서 index값을 array로 해쉬 충돌 없이 매핑해줍니다. 우리는 spatial hash function으로 을 사용합니다.
⊕ 는 xor operation을, 𝜋는 큰 소수값을 의미합니다.
이 공식은 효과적으로 dimension linear congruential permutation의 결과를 XOR하여 해시된 값에 대한 차원의 영향을 상관관계를 해제합니다?? 해쉬 값들끼리 독립적이기 위해서는 d차원 중 d-1개만 순열되어야 하므로, 더 나은 캐시 일관성을 위해 𝜋1 := 1, 𝜋2 = 2 654 435 761 및 𝜋3 = 8861 459를 선택합니다. 마지막으로, gride의 corner의 feature vector는 hypercube내 x의 위치에 따라 d-선형으로 보간됩니다. 보간에 사용되는 가중치는 w𝑙 := x𝑙 − ⌊x𝑙⌋.입니다. 해당 작업은 Multi-Resolution의 각 레벨별로 이루어지며, 보간된 feature vector 뿐만 아니라 보조적인 특징 정보들이 MLP학습을 위한 auxiliary input으로 사용됩니다.(view direction이나 neural radiance caching의 textures 같은 것들)
해쉬 함수를 사용하는 이유는, grid의 각 corner를 고유한 값에 매핑하는것이 목적이 아니라, 이를 최대한 효율적으로 생성하는 것입니다. gird의 각 corner를 고유한 key값을 갖는 hash table로 만들기 위해서는, 데이터의 갯수만큼의 hash table이 있어야 하지만, 우리가 데이터의 실질적인 갯수를 모를 때에는 hash table의 길이를 임의로 지정하기도 힘들며, 이는 모두 addictional cost입니다. 그렇다면, hash를 일정한 크기로 만든 후, 추가적으로 들어오는 것에 대해서는 연결 리스트처럼 사용하면 될겁니다.
이걸 체이닝 방식이라고 합니다.
그런데, 만약 특정 hash key에만 value들이 매핑 될 경우, 최악의 경우에는 특정 key에 모든 값들이 매핑되고, 연결 리스트의 빅오인 O(n+1)을 갖게 될겁니다. 그렇다면, 이렇게 hash 충돌이 발생 했을 때, 탐색시간을 최소한으로 갖기 위해서는, 모든 hash들이 uniform하게 분포해야 겠죠. hash는 다양한 방법이 있지만, 이 중 대표적인 방식이 division method인데, modular연산을 사용하는 방법입니다. 특정 key를 어떤 수로 나눈 나머지를 해쉬 값으로 사용하는 것입니다. 예를 들어 m이 100이면 k mod m은 0~99까지의 범위를 지니게 됩니다. 이 m의 범위는 해쉬 테이블의 성능과 크게 연관되는데, m은 보통 키의 수의 3배 이상으로 사용합니다.(적재율 30%까지는 충돌이 거의 일어나지 않으므로..) 또한, m은 2의 지수승에 근접한 소수를 사용해야 하는데, 만약 m이 2^3이면, 2진수로 00001000이고, 4번째 이하의 숫자만 해쉬값에 영향을 미치기 떄문입니다. 그렇게 되면, k1과 k2가 각각 10110100, 10120100이면 둘 다 같은 해쉬값을 출력해버리게 됩니다. 즉, 가장 최적의 m의 크기는 키의 갯수의 3배이며 2의 지숫승에 근접한 소수입니다. 인용 - https://hsp1116.tistory.com/35
이제, 여기서 추가적으로 hash collision을 효율적으로 방지할 수 있는 기법을 하나 추가하도록 하겠습니다. hash(x,y,z) = ( xp1 xor yp2 xor z*p3) mod n 우선, 3차원에서의 좌표 x,y,z와, p1, p2, p3라는 큰 소수(73856093, 19349663, 83492791)를 사용합니다. 여기서 n은 hash table의 size입니다.
이렇게 하는 이유는 보통 2가지인데,
그럼 이렇게 xor을 이용해서 hash들을 결합하는 이유는 무엇일까요? 해쉬는 연산량 문제로 보통 bit단위로 결합을 진행하는데, and, or같은 연산보다 xor이 균일하게 분포하도록 만들어 주기 때문입니다. 0,1만 있는 bit연산에서 and는 0:3, 1:1 or는 1:3, 0:1 xor는 1:2, 0:2 이므로 xor이 and나 or에 비해서 상대적으로 적합한 연산이 되기 때문입니다. 인용 - http://daplus.net/cryptography-xor%EC%9D%B4-%ED%95%B4%EC%8B%9C%EB%A5%BC-%EA%B2%B0%ED%95%A9%ED%95%98%EB%8A%94-%EA%B8%B0%EB%B3%B8-%EB%B0%A9%EB%B2%95-%EC%9D%B8-%EC%9D%B4%EC%9C%A0%EB%8A%94-%EB%AC%B4%EC%97%87%EC%9E%85/
해쉬 결합이란 보통, 여러가지 해쉬들을 결합함으로써, 데이터의 크기를 줄이는 것이 주 목적입니다. 본 논문에서는 hash table의 크기를 500K-12.6M개의 파라미터를 갖도록 설정하는데, 해쉬 결합을 하지 않는다면, key가 x,y,z좌표를 갖는것이 어려워지게 됩니다. 만약 key 때문에 hash table의 수가 3배가 된다면, 파라미터는 1.5M-40M가 되어버릴테니까요. 그렇기에, 본 논문에서는 x,y,z의 좌표를 큰 소수들과 곱한 뒤, x,y,z를 xor해서 결합해 하나의 key로 만들어줍니다.
Performance vs. quality hash table의 사이즈 T에 따른 PSNR성능을 비교한 그래프입니다.
hash table의 사이즈에 따라서 성능이 상당히 많이 증가하는 것을 알 수 있습니다.
하지만, 연산량이나 상승폭을 비교해보면 maximum은 19로 잡는게 좋아 보입니다.
multi-resolution에서 resolution level과, hash table의 feature 갯수에 따른 성능 차이입니다.
F가 2일 때 가장 안정적으로 좋은 성능을 나타내는 것을 보여 주고 있습니다.