優化的逐次均值量化變換

連續平均量化變換 (SMQT) 算法是一種非線性變換，它揭示了數據的組織或結構，並去除了增益和偏差等屬性。 在一篇名為 The Successive Mean Quantization Transform 的論文中，SMQT 被“應用於語音處理和圖像處理”。 當應用於圖像時，該算法“可以看作是對圖像細節的漸進式關注”。

根據另一篇名為 SMQT-based Tone Mapping Operators for High Dynamic Range Images 的論文，它將產生“具有增強細節的圖像”。 該論文描述了將這種變換應用於圖像的兩種技術。

1. 將 SMQT 應用於每個像素的亮度 - 它描述了從每個像素的 RGB 中獲取亮度的公式。

2. 分別在 RGB 的每個通道上應用 SMQT - 分別用於通道 R、G 和 B。

下圖顯示了兩種技術的結果：

通過將第二種技術應用於布魯因劇院的夜間照片，我們可以看到算法如何逐步放大圖像的細節並揭示最初被黑暗隱藏的細節：

在本文中，我們將仔細研究該算法的工作原理，並探索一種簡單的優化方法，使該算法在實際圖像處理應用中的性能更高。

SMQT 算法

在原始論文中，算法是用抽象的方式描述的。 為了更好地理解 SMQT，我們將介紹一些簡單的示例。

假設我們有以下向量（你可以把它想像成一個數組）：

對於彩色圖像，我們可以將其視為三個獨立的向量，每個向量代表一個特定的顏色通道 (RGB)，向量的每個元素代表相應像素的強度。

應用 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（這是二進制）。

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。現在它的增益從 0 到 240，幾乎是整個 8 位範圍。 據說增益被移除是因為如果我們將原始向量的所有元素乘以一個數字（例如 2），或者如果我們將所有元素除以 2，則輸出向量將大致相同。 它的範圍大約是目標向量的整個範圍（L=8 時為 8 位）。 如果我們將輸入向量乘以 2，則輸出向量實際上是相同的，因為在每一步中，低於或高於平均值的相同數字將繼續低於或高於平均值，我們將添加相同的 0 或 1到輸出。 只有當我們除以它時，結果才會大致相同，而不是完全相同，因為像 15 這樣的奇數必須四捨五入，然後計算可能會有所不同。 我們使用整個範圍從深色圖像變為像素範圍從深色 (0) 到淺色 (240) 的圖像。
• 偏差被消除了，儘管在這個例子中我們不能完全觀察到它。 這是因為我們沒有偏差，因為我們的最小值是 0。如果我們真的有偏差，它就會被刪除。 如果我們取任何數字“K”並將其添加到輸入向量的每個元素中，那麼每一步中高於和低於平均值的數字的計算將不會發生變化。 輸出仍然是相同的。 這也會使太亮的圖像無法變成從深色到淺色的圖像。
• 我們有一張細節增強的圖像。 請注意，對於我們採取的每個遞歸步驟，我們實際上是如何放大細節，並通過盡可能多地揭示這些細節來構建輸出。 由於我們會將這種技術應用於每個 RGB 通道，我們將盡可能多地顯示細節，儘管會丟失有關每種顏色的原始色調的信息。

給定一個像 RGB 像素向量的圖像，每個點對於 R 來說是 8 位，對於 G 來說是 8 位，對於 B 來說是 8 位； 我們可以從中提取三個向量，每種顏色一個，然後將算法應用於每個向量。 然後我們再次從這三個輸出向量中形成 RGB 向量，並且我們擁有經過 SMQT 處理的圖像，就像在 Bruin Theatre 中所做的那樣。

複雜

該算法要求對於每個量化級別 (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 到 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) . 因為它只是一個加法，所以加法的順序並不重要。

這同樣適用於下一步：

計算與最後一個向量相同：((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 時，我們將 2 放在表的第二行，因為到目前為止已經出現了兩個 1。 我們還在表格的第三行放了一個 2，因為 1 + 1 = 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

   只剩下一個向量要拆分。 平均值為：sum[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，並且我們還預先計算了我們需要的所有值以找到平均值，因此計算結果向量非常簡單快速。

   這一步的複雜度是 O(L*(2^L))，對於 L=8，在實際的圖像處理需要中，它是 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)。 但是對於 FastSMQT，乘以 N 的常數要小得多，並且正如我們將看到的，它在處理時間上有很大的不同。

下圖比較了 SMQT 和 FastSMQT 算法在 L=8 時的性能，圖像處理就是這種情況。 該圖顯示了處理 N 個元素所需的時間（以毫秒為單位）。 請注意，對於 L=8，SMQT 的複雜度（使用常數）是 O(17*N)，而對於 FastSMQT，複雜度是 O(2*N + 2304)。

N 越大，SMQT 處理圖像所需的時間越長。 另一方面，對於 FastSMQT，增長要慢得多。

對於更大的 N 值，性能差異更加明顯：

這裡 SMQT 處理某些圖像最多需要幾秒鐘的時間，而 FastSMQT 仍處於“幾毫秒”區域內。

即使有多個內核（在本例中為兩個），FastSMQT 顯然仍優於僅 SMQT：

FastSMQT 不依賴於 L。另一方面，SMQT 線性依賴於 L 的值。例如，當 N = 67108864 時，SMQT 的運行時間隨著 L 值的增加而增加，而 FastSMQT 則不：

結論

並非所有優化技術都適用於所有算法，提高算法性能的關鍵通常隱藏在對算法工作原理的一些了解中。 此 FastSMQT 算法利用了預先計算值的可能性和平均計算的性質。 因此，它允許比原始 SMQT 更快的處理。 速度不受 L 增量的影響，雖然 L 不能比通常的 8 大很多，因為內存使用量是 2^L，對於 8 來說是可以接受的 256（我們的頻率表中的列數），但是性能增益具有明顯的實際效益。

這種速度上的改進使 MiddleMatter 能夠在 iOS 應用程序（和 Android 應用程序）中實現該算法，以改進在弱光條件下拍攝的圖片和視頻。 通過這一改進，可以在應用程序中執行視頻處理，否則對於 iOS 設備來說太慢了。

GitHub 上提供了 SMQT 和 FastSMQT 算法的 C++ 代碼。