[快速阅读八] Matlab中bwlookup的实现及其在计算二值图像的欧拉数、面积及其他morph变形中的应用。

• Locate the pixel neighborhood in input image
  BW
  based on the coordinates of the target pixel in
  A
  . The function zero-pads border pixels of image
  BW
  when the neighborhood extends past the edge of
  BW
  .

• Calculate an index,
  idx
  , based on the binary pixel pattern of the neighborhood.

• Set the target pixel in
  A
  as the value of the lookup table at the index
  idx
  , in other words, the value of
  lut(idx)
  .

• 具有零个
  on
  像素的情形（面积 = 0）

• 具有一个
  on
  像素的情形（面积 = 1/4）

• 具有两个相邻
  on
  像素的情形（面积 = 1/2）

• 具有两个对角
  on
  像素的情形（面积 = 3/4）

• 具有三个
  on
  像素的情形（面积 = 7/8）

• 具有所有四个
  on
  像素的情形（面积 = 1）

用图形化的表达方式上述六种情况对应如下（为了显示，使用绿色表示黑色值，红色表示白色值）：

索引值          　   0　　 　 1　　 　  2　　　　3　　    4　　　 5　　　 6　　　    7　　　  8　　     9　　     10　　   11　　    12　　   13　　    14　　    15

面积值　　　　  0　　 　1/4　　   1/4　　　1/2　　  1/4　　 1/2　　 3/4　　　  7/8　　　1/4　　   3/4　　   1/2　　  7/8　　   1/2　　    7/8　　    7/8　　    1

把面积值放大八倍得到面积值依次为：  0 2 2 4 2 4 6 7 2 6 4 7 4 7 7 8，我们翻看matlab的bwarea函数，可以得到其代码如下：

lut = [0     2     2     4     2     4     6     7     2     6     4     7...4     7     7     8];% Need to zero-pad the input.

bb= false(size(b)+2);

bb(2:end-1,2:end-1) =b;



weights=bwlookup(bb,lut);

a= sum(weights(:),[],'double')/8;

查找表和这里的一摸一样。

使用查找表的优点是把领域所有的组合提前计算出结果来，而不用到程序里进行一些列复杂的判断，这样在很多情况下是可以提高速度的，比如刚刚这个面积计算的东西，如果在循环内部做，则要做N种判断，那如果是涉及到3*3的领域，那就更为复杂了。

朴素的来说，有了bwlookup的原理，要把这个算法移植到C++中，就是一个比较简单的过程了，假如是处理16元素的表，也就是涉及到了4个像素，假定他们的值分别为P0\P1\P2\P3，则最基本的C代码如下所示：

int Index = 0;if (P0 == 255)    Index += 1;if (P1 == 255)    Index += 2;if (P2 == 255)    Index += 4;if (P3 == 255)    Index += 8;

LinePD[X]= Lut[Index];

处理512个元素的过程也是类似的，只不过索引值多加了几个（注意，这里用255表示白色，而不是1）。

如果考虑指令集优化，一个自然的翻译过程如下所示：

__m128i Index =_mm_setzero_si128();

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(1)), _mm_cmpeq_epi8(P0, _mm_set1_epi8(255)));

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(2)), _mm_cmpeq_epi8(P1, _mm_set1_epi8(255)));

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(4)), _mm_cmpeq_epi8(P2, _mm_set1_epi8(255)));

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(8)), _mm_cmpeq_epi8(P3, _mm_set1_epi8(255)));

    _mm_storeu_si128((__m128i*)(LinePD + X), _mm_shuffle_epi8(Lut128, Index));

一次性处理16个字节，最为关键的一点是，这个查表可以方便的直接使用_mm_shuffle_epi8非常高效的实现，这个在我前期的文章里多次提到（16个字节表的查找，我们假定lut的类型为字节类型，这个在实际的应用中也足够了），

__m128i Index =_mm_setzero_si128();

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(1)), P0, _mm_set1_epi8(255));

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(2)), P1, _mm_set1_epi8(255));

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(4)), P2, _mm_set1_epi8(255));

    Index= _mm_blendv_epi8(Index, _mm_add_epi8(Index, _mm_set1_epi8(8)), P3, _mm_set1_epi8(255));

    _mm_storeu_si128((__m128i*)(LinePD + X), _mm_shuffle_epi8(Lut128, Index));

int Index = 0;

    Index+= (1 &P0);

    Index+= (2 &P1);

    Index+= (4 &P2);

    Index+= (8 &P3);

    LinePD[X]= Lut[Index];

__m128i Index =_mm_setzero_si128();

    Index= _mm_add_epi8(Index, _mm_and_si128(_mm_set1_epi8(1), P0));

    Index= _mm_add_epi8(Index, _mm_and_si128(_mm_set1_epi8(2), P1));

    Index= _mm_add_epi8(Index, _mm_and_si128(_mm_set1_epi8(4), P2));

    Index= _mm_add_epi8(Index, _mm_and_si128(_mm_set1_epi8(8), P3));//可以直接接用shuffle实现查找表

    _mm_storeu_si128((__m128i*)(LinePD + X), _mm_shuffle_epi8(Lut128, Index));