使用 SSE2 优化的图像反转

• 下载源代码 - 11.4 KB
• 下载演示 - 4.75 KB

引言

图像反转是指将图像的亮度或颜色从正常形式更改为相反的表示。

背景

反转的图像可以被解释为图像负片的数字版本。反转后，每种颜色都会变成其完全相反的颜色（我知道这种术语不太科学，但作为概念信息很有用）。让我们用更科学的术语来解释。正片图像应定义为正常、原始的 RGB 或灰度图像。负片图像表示正片的色调反转，其中亮区变为暗区，暗区变为亮区。在负片图像中，还会实现颜色反转，例如红色区域变为青色，绿色区域变为品红色，蓝色区域变为黄色。简单来说，对于灰度图像，黑白图像，使用 0 表示黑色，255 表示白色，接近黑色的像素值 5 将转换为 250，或接近白色。

图像反转是图像处理中最简单的技术之一。因此，它非常适用于演示性能、加速和优化。许多最先进的图像处理库，如 OpenCV、Gandalf、VXL 等，都以尽可能快的速度执行此操作，尽管使用并行硬件可以实现更快的加速。

在本文中，我将演示三种图像反转的实现：一种基本实现，一种优化实现（C 级），以及一种使用现代 CPU 增强指令（在本例中为 SSE2）的优化实现。

代码使用 OpenCV，不是为了实现算法，而是仅用于读取和显示图像。因此，如果您不知道如何使用或配置它，请参阅 OpenCV 文档，或者简单地：http://opencv.willowgarage.com/wiki/VisualC%2B%2B。

算法

对于每个像素 I(x,y)，反转映射定义为 Y(x,y)=255-I(x,y)。对于彩色图像，完全相同的公式应用于所有三个通道 (R,G,B)。在计算机语言中，这是 Y(x,y)=~I(x,y)。基本算法如下所示：

int i=0;
for (;i!=src->imageSize; i++)
  dst->imageData[i]=~((uchar)src->imageData[i]);

优化

位优化

图像反转等同于反转像素值的每一位。1->0，0->1。简而言之，这不是一个操作。许多现代处理器都有由 32 个（我们暂时不关心 64 位机器）组成的寄存器。由于位反转与数据大小无关，我们应该获取我们寄存器大小的数据，以充分利用寄存器。这就是为什么我们将字节图像表示为整数指针，其大小小四倍。换句话说：

Sizeof(uchar) * imagesize = sizeof(int) * imagesize/4

这样，我们可以获得高达 3 倍的速度。

循环展开

循环展开的目标是通过减少（或消除）每次迭代中的“循环结束”测试来提高程序的速度。可以将循环重写为一系列独立语句，从而消除循环控制器开销。如果通过消除“循环结束”测试获得的速度足以抵消程序大小增加引起的性能下降，则可以实现显著的提升。此外，如果循环中的语句彼此独立，则出现在循环较早的语句不会影响后续语句，并且可以并行执行这些语句。（维基百科）

这是一个简单的循环展开示例：

计算机程序中的一个过程是从集合中删除 100 个项目。这通过调用函数 delete(item_number) 的 for 循环来实现。

for (int x = 0; x < 100;  x++)
{
    delete(x);
}

如果程序的这一部分要进行优化，并且循环的开销与 delete(x) 的开销相比需要大量资源，则可以使用循环展开来加快速度。这将生成一个优化的代码片段，如下所示：

for (int x = 0; x < 100;  x += 5)
{
   delete(x);
   delete(x+1);
   delete(x+2);
   delete(x+3);
   delete(x+4);
}

修改的结果是，新程序只需要执行二十次循环，而不是一百次。现在需要进行的跳转和条件分支的数量减少了五分之一，这在许多迭代中将是循环管理时间的一大改进。处理一行的最终算法如下所示：

for( ; i <= step1 - 16; i += 16 )
{
  const int* src1i=(const int*)(src1+i);
  int* dst1i=(int*)(dst1+i);
  int t0 = ~(src1i)[0];
  int t1 = ~(src1i)[1];
  int t2 = ~(src1i)[2];
  int t3 = ~(src1i)[3];

  dst1i[0]=t0;
  dst1i[1]=t1;
  dst1i[2]=t2;
  dst1i[3]=t3;
 }

SSE2 整数指令

由于我们使用整数指针处理数据，我们可以利用 SSE2 整数算术。这样，我们可以一次处理四个 int 值。讨论 SSE2 的整个架构不是本文的目标。如果您不确定如何使用它们，请参考以下网站：

• http://softpixel.com/~cwright/programming/simd/sse2.php
• http://www.jorgon.freeserve.co.uk/TestbugHelp/XMMintins.htm

（抱歉；我不知道网上有什么好的 SSE 教程。）

要使用 SSE2 实现反转，我们应该获取优化后的反转代码并将其转换为 SSE2。然而，据我所知，SSE2 没有直接的 NOT 指令。相反，我们利用 pandn（packed and not）指令。在这里，我们将问题转换为更数学化的陈述，即 Y(x,y)=~(0xff & I(x,y))。在这里，我们将像素与 255 进行按位 AND 操作，然后应用按位 NOT。还有一个额外的计算，但它可能仍然是值得的（因为指令直接在硬件上执行）。一个人可以简单地使用循环指令遍历所有像素，并在 SSE2 中应用相同的运算符进行优化。

以下是我在此应用程序中使用的 SSE2 指令：

• movdqa：将 128 位数据从内存或指针移动到 XMM 寄存器或反之。
• pandn：“and & not” 一个 XMM 寄存器。
• loop：继续循环。

内存对齐一直是重要的问题。为了使数据能够被 SSE 处理，我们应该将指针至少对齐到 16 字节边界（最好）。在本文中，我使用 align(32) 来确保安全。对齐总是有益的，因为 CPU 在读取对齐数据时可以实现更快的内存访问。

最后，整个图像的处理可以写成：

//Traverse:
// unroll the loop 4 times. 4th unroll is a half one.
// (as much as XMM's can hold)

// load 3 pixels
movdqa xmm0,[esi]
movdqa xmm1,[esi+16]
movdqa xmm2,[esi+32]
movdqa xmm3,[esi+48]

// 255- pixel for 3 pixels
pandn  xmm0, xmm7
pandn  xmm1, xmm7
pandn  xmm2, xmm7
pandn  xmm3, xmm7

// output the computed content
movdqa [edi], xmm0
movdqa [edi+16], xmm1
movdqa [edi+32], xmm2
movdqa [edi+48], xmm3

// traverse array
add esi,64
add edi, 64

// move on
loop Traverse;

结论

请注意，C 级优化对于需要性能的应用程序来说非常有前途。只有当你真正努力做得更好时，才去深入研究汇编代码。对于某些问题，你甚至可能不会获得性能提升！

问题

宽度不能被 4 整除的图像将在每行的末尾留下一些剩余像素。我忽略了反转这些剩余像素的任务。因此，最好添加此功能，或者干脆不要处理尺寸不能被 4 整除的图像。此代码假定您的硬盘驱动器上有一个图像“C:\\Data\\Waterfall.jpg”。如果您没有此图像，请修改代码，并将 main 函数中的第一行更改为您喜欢的图像。