优化的连续均值量化变换

本文概述

• SMQT算法
• 总结

连续均值量化变换(SMQT)算法是一种非线性变换, 可揭示数据的组织或结构并消除诸如增益和偏置之类的属性。在题为”连续平均量化变换”的论文中, SMQT被”应用于语音处理和图像处理”。当应用于图像时, 该算法”可以看作是逐步关注图像中的细节”。

优化的连续均值量化变换算法

鸣叫

根据另一篇名为”基于SMQT的高动态范围图像的色调映射运算符”的论文, 它将产生”具有增强细节的图像”。本文介绍了将这种转换应用于图像的两种技术。

1. 在每个像素的亮度上应用SMQT-它描述了从每个像素的RGB获得亮度的公式。

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

下图显示了两种技术的结果：

来源：用于高动态范围图像的基于SMQT的色调映射运算符

通过将第二种技术应用于夜间的布鲁因剧院的图片, 我们可以看到算法如何逐步缩放图像的细节并揭示最初被黑暗隐藏的细节：

在本文中, 我们将仔细研究该算法的工作原理, 并探索一种简单的优化方法, 使该算法在实际的图像处理应用中具有更高的性能。

SMQT算法

在原始论文中, 以抽象方式描述了该算法。为了更好地理解SMQT, 我们将逐步介绍一些简单的示例。

假设我们有以下向量(你可以将其视为一个数组)：

对于彩色图像, 我们可以将其视为三个独立的向量, 每个向量代表一个特定的颜色通道(RGB), 并且向量的每个元素代表相应像素的强度。

应用SMQT算法涉及的步骤为：

计算向量的平均值, 在这种情况下为29.58。

将向量一分为二, 左半部分小于或等于29.58的数字, 右半部分大于或等于29.58的数字：

第二行是我们将为每个值创建的代码。小于或等于29.58的值在其代码中获得0, 大于29.58的数字获得1(这是二进制)。

现在, 遵循相同规则, 以递归方式分别拆分两个结果向量。在我们的示例中, 第一个向量的平均值为(15 + 4 + 0 + 5 + 18)/ 5 = 8.4, 第二个向量的平均值为(32 + 48 + 60 + 64 + 59 + 47 + 31)/ 7 = 48.7。这两个向量中的每一个都进一步分为两个向量, 并根据与平均值的比较将第二个代码位添加到每个向量中。结果如下：

请注意, 对于小于或等于平均值​​的数字(对于每个向量), 再次附加0；对于大于平均值的数字, 附加1。

递归重复此算法：

此时, 每个向量只有一个元素。因此, 对于每个后续步骤, 将附加一个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处理的图像。

复杂

该算法要求, 对于每个量化级别(L), 必须在第一遍检查N个元素以找到每个矢量的平均值, 然后在第二遍检查中, 必须将这N个元素中的每个元素与相应的平均值进行比较。为了依次分割每个向量最后, 必须用其代码替换N个元素。因此, 算法的复杂度为O((L * 2 * N)+ N)= O((2 * L +1)* N), 即O(L * N)。

来源：用于高动态范围图像的基于SMQT的色调映射运算符

从论文中提取的图形与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算法的示例应用于示例的步骤：

创建一个包含32列3行的表, 如下所示。表中的第一行代表表的索引(0到31), 在对表进行编码时不必包括在内。但已明确显示它, 使该示例更易于理解。

一旦计数每个值的频率, 就迭代N个元素。在我们的示例中, 元素1、7、16、25和31的频率均为2。所有其他元素的频率为0。此步骤的复杂度为O(N)。

现在已经填充了频率向量, 我们需要迭代该向量(频率向量, 而不是输入向量)。我们不再重复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的元素的列, 并且为了更清楚地看到示例, 我们还将删除第二行, 因为它不再相关了, 如你所见。

请记住, 我们可以使用最后一个(完全有序的)向量来进行每个步骤的计算, 结果仍然是相同的。请注意, 在此表中, 这里是最后一个向量, 其中已经进行了所有预先计算。

我们基本上需要在这个小的向量上执行SMQT算法, 但是与在我们最初使用的原始向量上执行此算法不同, 此方法会容易得多。

首先, 我们需要计算所有样本的平均值。我们可以通过以下方式轻松找到它：sum [31] / n [31] = 160/10 =16。因此, 我们将表格分为两个向量, 并开始为每个向量编写二进制代码：

现在我们再次分割每个向量。第一个向量的平均值为：sum [16] / n [16] = 48/6 =8。第二个向量的平均值为：(sum [31] – sum [16])/(n [31] – n [16])=(160 – 48)/(10 – 6)= 112/4 = 28。

仅剩一个向量可拆分。平均值为：sum [7] / n [7] = 16/4 = 4。

如你所见, 如果我们遵循原始算法, 则每个元素的代码都相同。而且, 我们对SMQT的处理比使用N个元素的处理要小得多, 而且我们还预先计算了寻找均值所需的所有值, 因此计算所得向量非常简单快捷。

此步骤的复杂度为O(L *(2 ^ L)), 对于L = 8, 在实际的图像处理需求中, 它的O(8 *(256))= O(2048)=常数。

最后一步是迭代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的常数要小得多, 这将在处理时间上产生很大的差异, 正如我们将看到的。

下图比较了L = 8(图像处理的情况)下SMQT和FastSMQT算法的性能。该图显示了处理N个元素所花费的时间(以毫秒为单位)。请注意, 对于L = 8, SMQT的复杂度(具有常数)为O(17 * N), 而对于FastSMQT, SMQT的复杂度为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 ++代码。