Successive Mean Quantization Transform (SMQT) algorithm is a non-linear transformation that reveals the organization or structure of the data and removes properties such as gain and bias. 在一篇题为 逐次均值量化变换SMQT“应用于语音处理和图像处理”. The algorithm when applied to images “can be seen as a progressive focus on the details in an image”.

根据另一篇题为 基于smqt的高动态范围图像色调映射算子，它将生成一张“细节增强的图像”。. 本文描述了将这种变换应用于图像的两种技术.

1. Apply SMQT on luminance of each pixel - it describes the formula to obtain the luminance from the RGB of each pixel.

2. 分别在RGB的每个通道上应用SMQT -分别用于通道R, G和B.

下图是两种技术的结果:

通过将第二种技术应用于布鲁因剧院的夜间照片, we can see how the algorithm progressively zooms on the details of the image and reveals details that are originally hidden by the darkness:

在本文中, 我们将仔细研究这个算法是如何工作的, and explore a simple optimization that allows the algorithm to be much more performant in practical image processing applications.

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

   Note that a 0 was again appended for numbers lower than or equal to the mean (for each vector) and a 1 for numbers greater than the mean.

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, since the number will always be equal to itself (the condition for a 0 is that the number must be less than or equal to the mean, 它本身).

到目前为止，我们的量化水平是L=5. 如果我们要使用L=8，我们必须在每个代码后面添加三个0. 将每个代码从二进制转换为整数(对于L=8)的结果将是:

最后的向量按递增顺序排序. To obtain the output vector, we must substitute the original value of the input vector by its code.

注意，在结果向量中:

• 增益被去掉了. 原来的增益很低，其范围从0到64. 现在它的增益从0到240，这几乎是整个8位范围. It is said that the gain is removed because it doesn’t matter if we multiply all the elements of the original vector by a number, 例如2, 或者全部除以2, 输出向量是一样的. 它的范围大约是目标向量的整个范围(L=8为8位). 如果我们把输入向量乘以2, 输出向量实际上是一样的, because in each step the same numbers that were below or above the mean will continue to be below or above it, 我们将在输出中添加相同的0或1. 只有把它除了，结果才会差不多, 而且不完全一样, 因为像15这样的奇数必须四舍五入，计算结果可能会有所不同. We went from a dark image to an image with its pixels ranging from dark colors (0) to lighter colors (240), 使用整个范围.
• 偏见被消除了，尽管我们在这个例子中不能完全观察到它. 这是因为我们没有偏差，因为我们的最低值是0. 如果我们真的有偏见，早就被消除了. 如果取任意数字K并将其与输入向量的每个元素相加, 在每一步中，高于和低于平均值的数字的计算不会改变. 输出仍然是相同的. This would also make images that are too bright to become images that range from dark to light colors.
• 我们有一张细节增强的图像. 注意，对于我们执行的每个递归步骤，我们实际上是如何放大细节的, 并通过尽可能多地揭示这些细节来构建输出. 由于我们将这种技术应用于每个RGB通道, 我们将尽可能多地披露细节, 尽管失去了每种颜色的原始色调信息.

给定一个像RGB像素向量的图像, 每个点代表8位R, 8为G, and 8 for B; we can extract three vectors from it, 每种颜色一个, 然后把算法应用到每个向量上. Then we form the RGB vector again from those three output vectors and we have the SMQT processed image, 就像在布鲁因剧院做的一样.

复杂性

该算法要求对于每一级量化(L), 第一次必须检查N个元素，以找到每个向量的平均值, 然后在第二次, each of those N elements must be compared to the corresponding mean in order to split each vector in turn. 最后，N个元素必须用它们的代码替换. 因此算法的复杂度为O((L*2*N) + N) = O((2*L + 1)*N)，即O(L*N).

本文提取的图符合O(L*N)复杂度. L越低, 以近似线性的方式处理速度越快(每秒帧数越多). 以提高加工速度, the paper suggests lowering values of L: “selecting a level L lower can be a direct way to reduce processing speed but with reduced image quality”.

改进

在这里，我们将找到一种在不降低图像质量的情况下提高速度的方法. 我们将分析变换过程，找到一个更快的算法. 为了更全面地理解这一点，我们来看一个带有重复数字的例子:

这些向量不能再分割了，必须在得到所需的L之前一直加零.

为了简单起见, 我们假设输入可以从0到31, 输出为0 ~ 7 (L=3), 从示例中可以看出.

Note that computing the mean of the first vector (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 gives the same result as computing the mean of the entire last vector, since it’s just the same vector with the elements in a different order: (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). 因为它只是一个加法，所以求和的顺序无关紧要.

这同样适用于下一步:

The calculations are the same as with the last vector: ((7 + 1 + 1 + 7) / 4 = 4) will be equal to ((1 + 1 + 7 + 7) / 4 = 4).

这同样适用于其他的向量和步骤.

均值的计算就是区间内各元素值的和, 除以区间内元素的个数. 这意味着我们可以预先计算所有这些值，避免重复计算L次.

让我们看看在我们的例子中应用FastSMQT算法的步骤:

1. 创建一个32列3行的表，如下所示. The first row in the table represents the index of the table (0 to 31) and is not necessary to be included when coding the table. 但它的显式显示是为了使示例更容易理解.

2. 迭代N个元素一次，计算每个值出现的频率. 在我们的例子中，元素1、7、16、25和31的频率都是2. 其他元素的频率都是0. 这一步的复杂度是0 (N).

3. 现在频率向量被填满了, 我们需要迭代这个向量(频率向量, 不是输入向量). 我们不再迭代N个元素, 而是R (R在2^L的范围内), 这里是32(0到31). 处理像素时, N可以是几百万像素, 但R通常是256(每种颜色一个向量). 在我们的例子中是32. 我们将同时填充表的以下两行. 这些行的第一行(表的第二行)将是到目前为止频率的总和. The second (the third of the table) will have the 总和 of the value of all elements that appeared so far.

   在我们的例子中, 当我们得到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), 在本题中是0 (32), 当使用RGB像素时，它是0 (256).

   i	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-cumulative	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的列, and to see the example clearer we will also remove the second row since it’s not relevant anymore, 你会看到.

   i	1	7	16	25	31
   n	2	4	6	8	10
   总和	2	16	48	98	160

5. Remember that we could use the last (completely ordered) vector to do the calculations for each step and the results will still be the same. 请注意，在这个表中，我们有最后一个向量，所有的预计算都已经完成了.

   我们基本上需要在这个小向量上做SMQT算法, 但不像在我们开始的原始向量上做, 这个就简单多了.

   首先，我们需要计算所有样本的均值. 我们可以很容易地找到它:总和[31] / n[31] = 160 / 10 = 16. 因此，我们将表格分成两个向量，并开始为每个向量编写二进制代码:

   i	1	7	16	25	31
   n	2	4	6	8	10
   总和	2	16	48	98	160
   code	0	0	0	1	1

   现在我们再拆分每个向量. 第一个向量的均值为:总和[16] / n[16] = 48 / 6 = 8. And the mean of the second vector is: (总和[31] – 总和[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   i	1	7	16	25	31
   n	2	4	6	8	10
   总和	2	16	48	98	160
   code	00	00	01	10	11

   只剩下一个向量要分割. 均值为:总和[7] / n[7] = 16 / 4 = 4.

   i	1	7	16	25	31
   n	2	4	6	8	10
   总和	2	16	48	98	160
   code	000	001	010	100	110

   正如您所看到的，如果我们遵循原始算法，每个元素的代码是相同的. And we did the SMQT on a much smaller vector than the one with N elements and we also have pre calculated all the values we need in order to find the mean, 所以计算结果向量是简单快捷的.

   这一步的复杂度是O(L*(2^L)), 当L=8时, 并在实际的图像处理需求, 它是0(8*(256))= 0(2048)=常数.

6. The final step is to iterate N elements once again replacing the element by its code for each element: element[i] = code[i]. 复杂度为0 (N). The complexity of FastSMQT is O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2^L)) = O(N + L*(2^L)) .

并行性

这两种算法都可以并行化, although it’s more efficient to run one algorithm per core instead if multiple vectors must be transformed. 例如, when processing images we can process each RGB channel in a different core instead of parallelizing each of those three calculations.

并行化SMQT算法, 当我们把一个向量分成两部分, we can process each sub-vector in a new core if a core is available (actually one sub vector in current core and the other in a new core). 这可以递归地完成，直到我们达到可用内核的总数. 代码对值的替换也可以并行执行.

FastSMQT算法也可以并行化. 在第一步中，输入向量必须分成可用核数(C)。. 必须为每个部分创建一个频率计数向量，并并行填充. 然后我们将这些向量的值加到一个结果频率向量中. 下一个可以并行化的步骤是最后一个, 当我们用它们的代码替换值时. 这可以并行地为.

复杂度比较

原SMQT算法的总复杂度为O((2*L + 1)*N)，即O(L*N).

The complexity of FastSMQT is 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的常数要小得多, 我们会看到，这在处理时间上有很大的不同.

下图比较了L=8时SMQT和FastSMQT算法的性能, 这是图像处理的情况吗. 该图显示了处理N个元素所需的时间(以毫秒为单位). 注意，当L=8时，SMQT的复杂度(带常数)为0 (17*N)。, 而对于FastSMQT是0 (2*N + 2304).

N越大，SMQT处理图像所需的时间就越长. 另一方面，对于FastSMQT，增长要慢得多.

对于更大的N值，性能上的差异更加明显:

在这里，SMQT最多需要几秒钟的时间来处理某些图像, 而FastSMQT仍然停留在“几毫秒”的范围内.

即使使用多核(在这种情况下是两个)，FastSMQT显然仍然优于SMQT:

FastSMQT不依赖于L. 另一方面，SMQT线性依赖于L的值. 例如, N = 67108864, SMQT的运行时间随着L值的增加而增加, 而FastSMQT没有:

结论

并非所有的优化技术都适用于所有人 算法, and the key to improving an algorithm’s performance is often hidden within some insight of how the algorithm works. This FastSMQT algorithm takes advantage of the possibilities of precalculating values and the nature of mean calculations. 因此，它允许比原来的SMQT更快的处理. 速度不受L的增量影响, 尽管L不能比通常的8大很多，因为内存使用量是2^L, 对于8来说是可以接受的256(频率表中的列数), 但是性能的提高有明显的实际好处.

这种速度上的改进使MiddleMatter能够在一个 iOS应用程序 (以及一个Android应用程序)，可以改善在弱光条件下拍摄的照片和视频. 有了这个改进, 在应用中进行视频处理是可能的, 否则就太慢了 iOS 设备.

SMQT和FastSMQT算法的c++代码是 可以在GitHub上找到.