최적화된 연속 평균 양자화 변환

SMQT(연속 평균 양자화 변환) 알고리즘은 데이터의 조직 또는 구조를 드러내고 이득 및 편향과 같은 속성을 제거하는 비선형 변환입니다. 연속 평균 양자화 변환이라는 제목의 논문에서 SMQT는 "음성 처리 및 이미지 처리에 적용"되었습니다. 이미지에 적용되는 알고리즘은 "이미지의 세부 사항에 대한 점진적인 초점으로 볼 수 있습니다".

High Dynamic Range 이미지를 위한 SMQT 기반 Tone Mapping Operators라는 제목의 또 다른 문서에 따르면 "세부 사항이 향상된 이미지"가 생성됩니다. 이 문서에서는 이 변환을 이미지에 적용하는 두 가지 기술을 설명합니다.

1. 각 픽셀의 휘도에 SMQT를 적용합니다. 각 픽셀의 RGB에서 휘도를 구하는 공식을 설명합니다.

2. RGB의 각 채널에 SMQT를 개별적으로 적용합니다(채널 R, G 및 B에 대해 개별적으로).

다음 그림은 두 가지 기술의 결과를 보여줍니다.

밤에 Bruin Theatre의 사진에 두 번째 기술을 적용하여 알고리즘이 이미지의 세부 사항을 점진적으로 확대하고 원래 어둠에 의해 숨겨져 있던 세부 사항을 드러내는 방법을 볼 수 있습니다.

이 기사에서는 이 알고리즘이 어떻게 작동하는지 자세히 살펴보고 실제 이미지 처리 응용 프로그램에서 알고리즘의 성능을 훨씬 높일 수 있는 간단한 최적화를 살펴보겠습니다.

SMQT 알고리즘

원본 논문에서 알고리즘은 추상적인 방식으로 설명되어 있습니다. SMQT를 더 잘 이해하기 위해 몇 가지 간단한 예를 살펴보겠습니다.

다음 벡터가 있다고 가정합니다(배열처럼 생각할 수 있음).

컬러 이미지의 경우, 각각은 특정 컬러 채널(RGB)을 나타내고 벡터의 각 요소는 해당 픽셀의 강도를 나타내는 3개의 개별 벡터로 생각할 수 있습니다.

SMQT 알고리즘을 적용하는 단계는 다음과 같습니다.

1. 벡터의 평균을 계산합니다. 이 경우에는 29.58입니다.

2. 벡터를 둘로 나누어 왼쪽 절반에 29.58보다 작거나 같은 숫자를 남기고 오른쪽 절반에 더 큰 숫자를 남겨둡니다.

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   두 번째 행은 각 값에 대해 생성할 코드입니다. 29.58보다 작거나 같은 값은 코드에서 0을 얻고 29.58보다 큰 숫자는 1을 얻습니다(2진법).

3. 이제 두 결과 벡터는 동일한 규칙에 따라 재귀 방식으로 개별적으로 분할됩니다. 이 예에서 첫 번째 벡터의 평균은 (15 + 4 + 0 + 5 + 18) / 5 = 8.4이고 두 번째 벡터의 평균은 (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48.7. 이 두 벡터 각각은 두 벡터로 더 분할되고 평균과의 비교에 따라 두 번째 코드 비트가 각각에 추가됩니다. 결과는 다음과 같습니다.

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   평균보다 작거나 같은 숫자에는 0이 다시 추가되었고(각 벡터에 대해) 평균보다 큰 숫자에는 1이 추가되었습니다.

4. 이 알고리즘은 재귀적으로 반복됩니다.

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   이 시점에서 모든 벡터에는 하나의 요소만 있습니다. 따라서 모든 연속 단계에 대해 숫자가 항상 자체와 같기 때문에 0이 추가됩니다(0의 조건은 숫자가 자신인 평균보다 작거나 같아야 한다는 것입니다).

지금까지 우리는 L=5의 양자화 레벨을 가지고 있습니다. L=8을 사용하려면 각 코드에 세 개의 0을 추가해야 합니다. 각 코드를 이진수에서 정수로 변환한 결과(L=8의 경우)는 다음과 같습니다.

최종 벡터는 오름차순으로 정렬됩니다. 출력 벡터를 얻으려면 입력 벡터의 원래 값을 해당 코드로 대체해야 합니다.

결과 벡터에서 다음을 확인하십시오.

• 이득이 제거되었습니다. 원래의 이득은 0에서 64까지의 범위로 낮은 이득을 가졌습니다. 이제 이득은 거의 전체 8비트 범위인 0에서 240까지입니다. 원래 벡터의 모든 요소에 2와 같은 숫자를 곱하거나 모두 2로 나누면 출력 벡터는 거의 같을 것이기 때문에 이득이 제거되었다고 합니다. 그 범위는 대상 벡터의 전체 범위에 관한 것입니다(L=8의 경우 8비트). 입력 벡터에 2를 곱하면 출력 벡터는 실제로 동일할 것입니다. 각 단계에서 평균보다 낮거나 높은 동일한 숫자가 계속 평균보다 낮거나 높기 때문에 동일한 0 또는 1을 추가하기 때문입니다. 출력에. 15와 같은 홀수는 반올림해야 하고 계산은 달라질 수 있기 때문에 우리가 그것을 나누는 경우에만 결과가 거의 같을 것이고 정확히 같지는 않습니다. 전체 범위를 사용하여 어두운 이미지에서 어두운 색상(0)에서 밝은 색상(240)까지 픽셀 범위가 있는 이미지로 이동했습니다.
• 이 예에서는 잘 관찰할 수 없지만 편향이 제거되었습니다. 가장 낮은 값이 0이므로 편향이 없기 때문입니다. 실제로 편향이 있었다면 제거되었을 것입니다. 숫자 'K'를 가져와서 입력 벡터의 각 요소에 추가하면 각 단계에서 평균 위와 아래에 있는 숫자의 계산이 달라지지 않습니다. 출력은 여전히 ​​​​동일합니다. 이렇게 하면 너무 밝은 이미지가 어두운 색상에서 밝은 색상 범위의 이미지가 되기에 너무 밝습니다.
• 디테일이 향상된 이미지가 있습니다. 우리가 취하는 각 재귀 단계에 대해 실제로 세부 사항을 확대하고 가능한 한 많은 세부 사항을 공개하여 출력을 구성하는 방법에 유의하십시오. 그리고 이 기술을 각 RGB 채널에 적용할 것이기 때문에 각 색상의 원래 톤에 대한 정보는 손실되지만 가능한 한 많은 세부 사항을 공개합니다.

RGB 픽셀의 벡터와 같은 이미지가 주어지면 각 포인트는 R에 대해 8비트, G에 대해 8비트, B에 대해 8비트입니다. 각 색상에 대해 하나씩 3개의 벡터를 추출하고 각 벡터에 알고리즘을 적용할 수 있습니다. 그런 다음 세 개의 출력 벡터에서 RGB 벡터를 다시 형성하고 Bruin Theatre 중 하나에서 수행한 것처럼 SMQT 처리된 이미지를 얻습니다.

복잡성

알고리즘은 각 수준의 양자화(L)에 대해 각 벡터에 대한 평균을 찾기 위해 첫 번째 패스에서 N개의 요소를 검사해야 하고 두 번째 패스에서 N개의 요소 각각을 해당 평균과 비교해야 합니다. 각 벡터를 차례로 분할합니다. 마지막으로 N개의 요소는 해당 코드로 대체되어야 합니다. 따라서 알고리즘의 복잡도는 O((L*2*N) + N) = O((2*L + 1)*N), 즉 O(L*N)입니다.

논문에서 추출한 그래프는 O(L*N) 복잡도와 일치합니다. L이 낮을수록 대략 선형 방식으로 처리 속도가 빨라집니다(초당 프레임 수가 더 많음). 처리 속도를 향상시키기 위해 논문에서는 L 값을 낮추는 것을 제안합니다. "레벨 L을 더 낮게 선택하면 처리 속도를 줄이는 직접적인 방법이 될 수 있지만 이미지 품질은 떨어집니다."

개선

여기에서 이미지 품질을 낮추지 않고 속도를 향상시키는 방법을 찾을 수 있습니다. 우리는 변환 과정을 분석하고 더 빠른 알고리즘을 찾을 것입니다. 이에 대한 보다 완전한 관점을 얻기 위해 반복되는 숫자가 있는 예를 살펴보겠습니다.

벡터는 더 이상 분할할 수 없으며 원하는 L에 도달할 때까지 0을 추가해야 합니다.

간단하게 하기 위해 예에서 볼 수 있듯이 입력은 0에서 31까지, 출력은 0에서 7(L=3)까지 갈 수 있다고 가정해 보겠습니다.

첫 번째 벡터(16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16의 평균을 계산하면 전체 마지막 벡터의 평균을 계산하는 것과 동일한 결과를 얻을 수 있습니다. (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16의 순서로 요소가 있는 동일한 벡터입니다.

두 번째 단계에서는 각 벡터를 재귀적으로 계산해야 합니다. 따라서 처음 6개 요소((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8)인 회색 입력의 평균과 마지막 4개 요소인 공백 입력의 평균을 계산합니다. ((25 + 31 + 31 + 25) / 4 = 28):

완전히 정렬된 마지막 벡터를 사용하면 결과가 동일하다는 점에 다시 주의하십시오. 처음 6개 요소에 대해 ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), 마지막 4개 요소에 대해 ((25 + 25 + 31 + 31) / 4 = 28) . 단지 덧셈일 뿐이기 때문에 summands의 순서는 중요하지 않습니다.

다음 단계에도 동일하게 적용됩니다.

계산은 마지막 벡터와 동일합니다. ((7 + 1 + 1 + 7) / 4 = 4)는 ((1 + 1 + 7 + 7) / 4 = 4)와 같습니다.

나머지 벡터와 단계에도 동일하게 적용됩니다.

평균 계산은 구간의 요소 값의 합을 구간의 요소 수로 나눈 것입니다. 이것은 우리가 모든 값을 미리 계산할 수 있고 이 계산을 L번 반복하지 않아도 된다는 것을 의미합니다.

FastSMQT 알고리즘이라고 부를 예제를 적용하는 단계를 살펴보겠습니다.

1. 아래와 같이 32개의 열과 3개의 행이 있는 테이블을 만듭니다. 테이블의 첫 번째 행은 테이블의 인덱스(0 ~ 31)를 나타내며 테이블을 코딩할 때 포함할 필요는 없습니다. 그러나 예제를 더 쉽게 따라할 수 있도록 명시적으로 표시되어 있습니다.

2. 각 값의 빈도를 계산하여 N 요소를 한 번 반복합니다. 이 예에서 요소 1, 7, 16, 25 및 31의 빈도는 모두 2입니다. 다른 모든 요소의 빈도는 0입니다. 이 단계의 복잡도는 O(N)입니다.

3. 이제 주파수 벡터가 채워졌으므로 해당 벡터(입력 벡터가 아니라 주파수 벡터)를 반복해야 합니다. 우리는 더 이상 N개의 요소를 반복하지 않지만 R(R은 범위: 2^L)이며, 이 경우에는 32(0에서 31)입니다. 픽셀을 처리할 때 N은 수백만(메가픽셀)이 될 수 있지만 R은 일반적으로 256(각 색상에 대해 하나의 벡터)입니다. 이 예에서는 32입니다. 테이블의 다음 두 행을 동시에 채울 것입니다. 첫 번째 행(표의 두 번째)에는 지금까지의 빈도 합계가 있습니다. 두 번째(표의 세 번째)는 지금까지 나타난 모든 요소의 값을 합한 값을 갖습니다.

   이 예에서 1에 도달하면 지금까지 두 개의 1이 나타났기 때문에 테이블의 두 번째 행에 2를 넣습니다. 또한 1 + 1 = 2이기 때문에 테이블의 세 번째 행에 2를 넣습니다. 7이 될 때까지 다음 위치 각각에 이 두 값을 계속 기록합니다. 숫자 7이 두 번 나타나기 때문에 2를 추가합니다. 두 번째 행의 누산기, 지금까지 4개의 숫자(1, 1, 7, 7)가 나타났기 때문입니다. 그리고 7 + 7 = 14를 세 번째 행에 추가하여 2 + 14 = 16이 됩니다. 1 + 1 + 7 + 7 = 16이기 때문입니다. 해당 요소의 반복을 마칠 때까지 이 알고리즘을 계속합니다. 이 단계의 복잡성은 O(2^L)이며 이 경우에는 O(32)이고 RGB 픽셀로 작업할 때는 O(256)입니다.

   나	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   N	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-누적	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   합집합	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. 다음 단계는 빈도가 0인 요소가 있는 열을 테이블에서 제거하는 것입니다. 예제를 더 명확하게 보기 위해 더 이상 관련이 없는 두 번째 행도 제거합니다.

   나	1	7	16	25	31
   N	2	4	6	8	10
   합집합	2	16	48	98	160

5. 마지막(완전히 정렬된) 벡터를 사용하여 각 단계에 대한 계산을 수행할 수 있으며 결과는 여전히 동일하다는 것을 기억하십시오. 여기 이 테이블에는 모든 사전 계산이 이미 이루어진 마지막 벡터가 있습니다.

   우리는 기본적으로 이 작은 벡터에 대해 SMQT 알고리즘을 수행해야 하지만, 우리가 시작한 원래 벡터에 대해 수행하는 것과 달리 이것은 훨씬 더 쉬울 것입니다.

   먼저 모든 샘플의 평균을 계산해야 합니다. sum[31] / n[31] = 160 / 10 = 16으로 쉽게 찾을 수 있습니다. 따라서 테이블을 두 개의 벡터로 분할하고 각각에 대한 이진 코드를 작성하기 시작합니다.

   나	1	7	16	25	31
   N	2	4	6	8	10
   합집합	2	16	48	98	160
   암호	0	0	0	1	1

   이제 각 벡터를 다시 분할합니다. 첫 번째 벡터의 평균은 sum[16] / n[16] = 48 / 6 = 8입니다. 두 번째 벡터의 평균은 (sum[31] – sum[16]) / (n[31]입니다. – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   나	1	7	16	25	31
   N	2	4	6	8	10
   합집합	2	16	48	98	160
   암호	00	00	01	10	11

   분할할 벡터는 하나뿐입니다. 평균은 합계[7] / n[7] = 16 / 4 = 4입니다.

   나	1	7	16	25	31
   N	2	4	6	8	10
   합집합	2	16	48	98	160
   암호	000	001	010	100	110

   보시다시피, 각 요소의 코드는 원래 알고리즘을 따랐다면 동일합니다. 그리고 N개의 요소가 있는 벡터보다 훨씬 작은 벡터에서 SMQT를 수행했으며 평균을 찾는 데 필요한 모든 값을 미리 계산했기 때문에 결과 벡터를 계산하는 것이 간단하고 빠릅니다.

   이 단계의 복잡도는 L=8인 경우 O(L*(2^L))이며 실제 이미지 처리 요구 사항에서는 O(8*(256)) = O(2048) = 상수입니다.

6. 마지막 단계는 각 요소에 대한 코드로 요소를 교체하는 N 요소를 다시 한 번 반복하는 것입니다. element[i] = code[i]. 복잡도는 O(N)입니다. FastSMQT의 복잡도는 O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

병행

여러 벡터를 변환해야 하는 경우 대신 코어당 하나의 알고리즘을 실행하는 것이 더 효율적이지만 두 알고리즘 모두 병렬화할 수 있습니다. 예를 들어 이미지를 처리할 때 세 가지 계산을 각각 병렬 처리하는 대신 다른 코어에서 각 RGB 채널을 처리할 수 있습니다.

SMQT 알고리즘을 병렬화하기 위해 벡터를 둘로 나눌 때 코어가 사용 가능한 경우 새 코어에서 각 하위 벡터를 처리할 수 있습니다(실제로 현재 코어에 하나의 하위 벡터와 새 코어에 있는 다른 하나). 이것은 사용 가능한 총 코어 수에 도달할 때까지 재귀적으로 수행할 수 있습니다. 코드에 의한 값의 교체도 병렬로 수행될 수 있습니다.

FastSMQT 알고리즘도 병렬화할 수 있습니다. 첫 번째 단계에서는 입력 벡터를 사용 가능한 코어 수(C)로 나누어야 합니다. 각 부품에 대해 하나의 빈도 수 벡터를 생성하고 병렬로 채워야 합니다. 그런 다음 해당 벡터의 값을 주파수의 결과 벡터 하나에 추가합니다. 병렬화할 수 있는 다음 단계는 값을 코드로 대체할 때 마지막 단계입니다. 이것은 병렬로 수행할 수 있습니다.

복잡성 비교

원래 SMQT 알고리즘의 총 복잡도는 O((2*L + 1)*N)이며 이는 O(L*N)입니다.

FastSMQT의 복잡도는 O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

고정된 L이 주어지면 복잡도는 둘 다 O(N)이 됩니다. 그러나 N을 곱하는 상수는 FastSMQT의 경우 훨씬 작고 처리 시간에 큰 차이를 만듭니다.

다음 그래프는 이미지 처리의 경우인 L=8에 대한 SMQT 및 FastSMQT 알고리즘의 성능을 비교합니다. 그래프는 N개의 요소를 처리하는 데 걸리는 시간(밀리초)을 보여줍니다. L=8에 대한 SMQT의 복잡도(상수 포함)는 O(17*N)인 반면 FastSMQT의 경우 O(2*N + 2304)입니다.

N이 클수록 SMQT가 이미지를 처리하는 데 더 오래 걸립니다. 반면 FastSMQT의 경우 성장이 훨씬 느립니다.

N 값이 더 크면 성능 차이가 훨씬 더 분명해집니다.

여기서 SMQT는 특정 이미지를 처리하는 데 최대 몇 초의 시간이 걸리는 반면 FastSMQT는 여전히 "수 밀리초" 영역 내에 있습니다.

다중 코어(이 경우 2개)를 사용하는 경우에도 FastSMQT는 여전히 SMQT보다 우수합니다.

FastSMQT는 L에 종속되지 않습니다. 반면 SMQT는 L 값에 선형적으로 종속됩니다. 예를 들어 N = 67108864인 경우 SMQT의 런타임은 L 값이 증가함에 따라 증가하지만 FastSMQT는 다음을 수행하지 않습니다.

결론

모든 최적화 기술을 모든 알고리즘에 적용할 수 있는 것은 아니며 알고리즘의 성능을 향상시키는 핵심은 알고리즘 작동 방식에 대한 통찰력 안에 숨겨져 있는 경우가 많습니다. 이 FastSMQT 알고리즘은 값을 미리 계산할 수 있는 가능성과 평균 계산의 특성을 활용합니다. 결과적으로 원래 SMQT보다 더 빠른 처리가 가능합니다. 속도는 L의 증분에 영향을 받지 않지만 메모리 사용량이 2^L이기 때문에 L이 일반적인 8보다 훨씬 클 수는 없지만 8의 경우 허용 가능한 256(주파수 테이블의 열 수)이지만 성능은 향상됩니다. 명백한 실용적인 이점이 있습니다.

이러한 속도 향상 덕분에 MiddleMatter는 iOS 애플리케이션(및 Android 애플리케이션)에서 저조도 조건에서 캡처한 사진과 비디오를 개선하는 알고리즘을 구현할 수 있었습니다. 이 개선으로 iOS 기기에서는 너무 느린 애플리케이션에서 비디오 처리를 수행할 수 있었습니다.

SMQT 및 FastSMQT 알고리즘에 대한 C++ 코드는 GitHub에서 사용할 수 있습니다.