连续平均量化变换(SMQT)算法是一种非线性变换，它揭示了数据的组织或结构，并消除了增益和偏差等属性. 在一篇题为 逐次均值量化变换SMQT“应用于语音处理和图像处理”. 当该算法应用于图像时，“可以被视为对图像细节的渐进关注”。.

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

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像素向量的图像, 每个点代表8位R, 8为G, and 8 for B; we can extract three vectors from it, 每种颜色一个, 然后把算法应用到每个向量上. 然后我们从这三个输出向量再次形成RGB向量，我们有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到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. 这一步的复杂度是0 (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), 在本题中是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的列, 为了更清楚地看到这个例子，我们还将删除第二行，因为它不再相关了, 你会看到.

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

5. 请记住，我们可以使用最后一个(完全有序的)向量来执行每一步的计算，结果仍然是相同的. 请注意，在这个表中，我们有最后一个向量，所有的预计算都已经完成了.

   我们基本上需要在这个小向量上做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. 第二个向量的均值为:(总和[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

   正如您所看到的，如果我们遵循原始算法，每个元素的代码是相同的. 我们在一个比有N个元素的向量小得多的向量上做了SMQT我们还预先计算了我们需要的所有值来找到平均值, 所以计算结果向量是简单快捷的.

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

6. 最后一步是再次迭代N个元素，用每个元素的代码替换元素:element[i] = code[i]. 复杂度为0 (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的常数要小得多, 我们会看到，这在处理时间上有很大的不同.

下图比较了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没有:

结论

并非所有的优化技术都适用于所有人 算法, 而提高算法性能的关键往往隐藏在对算法工作原理的一些洞察中. 这个FastSMQT算法利用了预计算值的可能性和平均值计算的性质. 因此，它允许比原来的SMQT更快的处理. 速度不受L的增量影响, 尽管L不能比通常的8大很多，因为内存使用量是2^L, 对于8来说是可以接受的256(频率表中的列数), 但是性能的提高有明显的实际好处.

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

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