在C# 4.0中使用System.Numerics.BigInteger类进行计算机视觉和二值形态学运算
一个简单的框架，用于对二值图像执行形态学运算。
引言
形态学算子在计算机视觉中常用于执行基本的物体分类和识别任务。在这里，我将描述一种在C#中实现各种二值形态学算子的有效方法。广义上说，形态学运算是指在应用一组依赖于每个像素的直接邻域的规则后，将灰度或二值图像转换为新图像的运算。两个非常常见的形态学算子是腐蚀和膨胀算子，其中图像中正在处理的每个像素分别被其邻域中的像素的最小值或最大值替换。邻域是通过使用位掩码定义围绕正在操作的像素的一组像素来确定的。腐蚀、膨胀以及更一般的形态学掩码可以采用任何可能的形状或大小。本文中我们将考虑的最简单的掩码是具有5像素十字图案的掩码，如下图所示
将形态学算子应用于图像可以让你执行大量基础任务，这些任务在计算机视觉中至关重要，例如：为具有与掩码相同大小的对象的图像找到背景图像，描绘对象边界（即使它们在原始图像中是接触的），根据其邻居数量打开或关闭像素，粗略测量二值图像中对象的周长（这需要使用另一个算法对对象进行标记），等等……在接下来的文章中，我将展示如何使用前面描述的掩码对以下图像应用腐蚀和膨胀运算
我提出的形态学框架
- 利用C# 4.0的
BigInteger类，实现简洁高效 - 允许指定任何类型的掩码形状
- 为上面介绍的简单掩码实现了腐蚀和膨胀算子
- 提供了其他方法来执行周长估计、多数和少数运算
背景
腐蚀和膨胀的朴素实现
形态学运算最常用于计算密集型任务，如计算机视觉。因此，实现效率很重要。
当我开始在C#中实现腐蚀和膨胀时，我以为可以通过滑动最小/最大窗口实现近似线性时间算法，从而满足速度要求。滑动窗口的线性时间？！我听到你说。是的。简单来说，这个想法是先在原始图像上进行水平扫描，然后进行垂直扫描。考虑的窗口沿着图像的行或列滑动，在我们进行此操作时，我们通过窗口中的索引或指针来跟踪最小值的位置。当我们滑动时，一个新的值进入窗口范围，一个值退出窗口。如果新值小于或等于当前最小值，我们则将最小指针更新为这个新值。如果最小值指针指向的值退出窗口，我们就必须完全重新扫描窗口以查找新的最小值和指针。
事实证明，这种方法比我期望的慢得多，所以我选择编写一个使用指针和C# unsafe语句的相同想法的优化版本。结果仍然太慢。
这种方法的另一个缺点是它严重限制了我可以使用哪些类型的算子：由于所有处理都是使用滑动窗口的最小值进行的，我被迫仅使用可分离为由连续像素组成的水平和垂直分量的形态学算子。
重回正轨
我很快遇到了一篇发表于1992年的论文，它让我重回正轨：[1]的作者描述了如何使用位图二值图像、命中与未命中变换和算子掩码的对数分解（本文不详述）来有效地实现腐蚀和膨胀等形态学算子。在本文中，我将展示如何使用一种巧妙的技巧来实现这篇论文中描述的方法，该技巧需要我们编写更少的代码。
命中与未命中变换
数学形态学是数学领域，它正式描述形态学算子并为其操作提供框架。命中与未命中变换是这些算子之一，它可用于描述腐蚀和膨胀。
简而言之，它表示为：X 
(S,T)，其中X是我们的输入图像，S是命中掩码，T是未命中掩码；命中和未命中掩码“应用于”输入图像X中的每个像素，以返回我们的处理后的图像。如果r是应用命中与未命中变换后像素的结果值，p1,..,pn是命中掩码下非零像素的值，q1,...,qn是未命中掩码下非零像素的值，则我们有以下关系：
R = X (S,T) ;=> r=p1 & ... & pn & ~q1 & ... & ~qn
其中“~”是逻辑非运算符， 是命中与未命中运算符。
这可以转化为通俗的说法：为了使命中与未命中算子返回正面结果，所有命中像素必须打开，所有未命中像素必须关闭，同时忽略掩码中零值像素的值。
数学形态学用命中与未命中变换来描述腐蚀（
运算符）和膨胀（
运算符），如下所示：
X Sh = X (S,
)
X Sh = (X (,S))c
是一个只包含零的掩码，c 表示补集运算符。
进行此框架的数学推导后，我们发现：
腐蚀：r = p1&...&pn
膨胀：r = ~( ~q1 & ... & ~qn) = q1|...|qn
其中r是输出图像中的像素，pi和qi是原始图像中对应掩码像素被设置的像素值。
事实上，这个结果也可以更简单地找到，即考虑在二值图像中，像素可能的取值范围是0或1，并且最小值和最大值运算符可以用位运算符&和|替换。然而，这个数学框架对于将我刚刚描述的简单运算扩展到更复杂的掩码形状（例如，使用[1]中所述的对掩码（也称为结构元素）进行对数分解）或其他形态学算子非常有用。
一个明显的优化
既然我们已经认识到命中与未命中变换可以表达腐蚀和膨胀运算，并且这些运算仅通过&和|运算符来表达，那么一个明显的优化就是将我们的图像打包成位数组。这样，我们可以立即通过将腐蚀和膨胀运算的速度提高32倍。正如我们将在本文后面看到的，C# 4.0提供了一个很棒的数据结构，它允许我们以相当直接的方式处理这些打包格式的图像。
移位
应用变换需要访问当前正在处理的像素邻域中的像素值；这可以通过生成一个新图像来实现，该图像已向上或向下移动一个或多个像素，以及/或向左或向右移动一个或多个像素——具体取决于我们要应用的掩码——然后对新生成的图像和/或原始图像进行逐像素运算。
通过在打包格式图像上使用左移或右移运算符相应地移动字节数组中的位，可以处理向左和向右的移位。向上或向下移动一个像素需要将图像数据移位等于图像行大小的位数。
必须小心确保图像在每行的左侧或右侧都用零填充，因为一行末尾的像素在右移后会移到下一行的开头。因此，我们将确保图像的每行左侧或右侧填充至少与位掩码所需的预期移位大小相同的像素数。在本文提出的具体实现中，我们将看到这只适用于图像扫描线的左侧或右侧，而不适用于列的顶部或底部。
移位是一个快速的操作，并且在现代CPU上只需要一条指令即可完成。当使用C# >> 或 << 运算符时，C#编译器会确保使用硬件移位指令，使操作尽可能快。但是，移位的范围仅限于字长：32位或64位。当对包含图像数据的字应用移位时，一个空的（值为零的）位会从一侧进入，而我们图像中的一个位（值为零或一）会从另一侧退出。这意味着我们必须进行额外的簿记工作，以确保从32位或64位字中退出的位在移位行中的数据时被馈送到下一个32位或64位字中。如果这样做，我们将丢失图像中的每32个或64个像素。
使用代码
BigInteger类：完美的选择
幸运的是，我们不必做上一节中描述的任何簿记工作。.NET 4.0提供了一种高效的整数数据结构实现，具有无限精度（只要有足够的地址空间）。BigInteger类是完美的选择：它支持我们从整数类型期望的所有典型位运算：&, |, ^, ~, <<, >>，并且可以将图像数据存储为一个BigInteger。此外，即使按大位数（例如2048）移位，BigInteger的实现也很高效。
实现
为了支持不同类型的掩码形状，我们首先预处理形态学算子掩码，以便可以通用且高效地访问它。
HitOrMissMask类将接受一个包含-1、0和1的sbyte数组。在此掩码中，未命中像素用-1表示，命中像素用1表示。因此，我们看到一个像素要么是命中的，要么是未命中的，正如预期的那样，它不能同时是两者：我们当然不能期望一个像素同时打开和关闭。HitOrMissMask类将接受任何掩码，并负责将其信息压缩成一种忽略零值像素的格式，并且可以被BinaryMorphology类读取。
对于本文开头所示的掩码，其腐蚀掩码如下所示：
sbyte[] mask = new sbyte[]
{ 0, 1, 0,
1, 1, 1,
0, 1, 0 };
如果用于构造HitOrMissMask类的实例，它将在构造函数中按如下方式处理：
public HitOrMissMask(sbyte[] hitmiss, int width, int xCenter, int yCenter)
{
Width = width;
Height = hitmiss.Length / width;
// count the number of non zero pixels in the structuring element
int length = hitmiss.Where(p => p != 0).Count();
HitOrMissX = new sbyte[length];
HitOrMissY = new sbyte[length];
HitOrMiss = new sbyte[length];
// convert to something we can use more efficiently
int c=0;
for (int i = 0; i < hitmiss.Length; i++)
{
if (hitmiss[i] != 0)
{
sbyte x = (sbyte) (i / width - xCenter);
sbyte y = (sbyte) (i % width - yCenter);
HitOrMissX[c] = x;
HitOrMissY[c] = y;
HitOrMiss[c] = hitmiss[i];
c++;
}
}
}
结果存储在BinaryMorphology类中的三个成员数组中：HitOrMissX和HitOrMissY，它们包含相对于您指定的中心像素的位置，需要测试的像素，以及HitOrMiss数组，其中包含要测试的值：开或关。
在此示例中，以下代码将生成这三个数组，其值如下图所示：
sbyte[] mask = new sbyte[]
{ 0, 1, 0,
1, 1, 1,
0, 1, 0 };
HitOrMissMask hmMask = new HitOrMissMask(mask, 3, 1, 1);
水平填充
然后使用BinaryMorphology类来执行我们的形态学运算。首先，我们必须通过告诉它我们想处理哪个图像以及我们需要进行哪些填充才能正确处理它来创建一个BinaryMorphology类的实例。所需的填充仅取决于掩码的大小，并且应该等于掩码大小大约一半的水平或垂直方向上的最大值。对于3x3掩码，这应该对应于图像周围1像素的填充（(3-1)/2=1）。
垂直填充
图像的顶部和底部不需要填充，因为BigInteger对象上的<<和>>运算符将为我们处理这些：正如您在上一节关于移位的讨论中所记得的，<<和>>允许移位整数中的位，并在整数的最低有效位或最高有效位处引入零值位，具体取决于移位方向。将一个宽度为1024的图像向上移位一行相当于在BigInteger的最低有效位侧引入1024个零值位。
BinaryMorphology类的构造函数将接受一个bool[]图像或一个带阈值的byte[]图像、其宽度以及应用所需的形态学运算所需的填充量，并将其存储为BinaryMorphology类的PackedImage成员，作为一个BigInteger对象。
/// <summary>
/// constructor for BinaryMorphology class
/// </summary>
/// <param name="image">the image to process</param>
/// <param name="width">the width of the provided image</param>
/// <param name="padding">the padding to apply when
/// storing this image, usually half the length of the structuring element</param>
public BinaryMorphology(bool[] image, int width, int padding)
{
Width = width + padding;
int height = (image.Length / width);
Height = height;
Padding = padding;
// last padding is for right padding the last line
BinaryInput = new bool[Width * Height + Padding];
// copy the data in the new array with necessary amount of left padding at every line
for (int i = 0; i < height; i++)
Buffer.BlockCopy(image, i * width, BinaryInput,
i * Width + Padding, width); // one bool is encoded as 1 byte in c#
// convert to packed format
BitArray packed = new BitArray(BinaryInput);
// use intermediate byte[]
byte[] scratch = new byte[(BinaryInput.Length >\> 3) + 1];
packed.CopyTo(scratch, 0);
// create BigInteger Image
PackedImage = new BigInteger(scratch);
}
/// <summary>
/// constructor for BinaryMorphology class
/// </summary>
/// <param name="image">the image to process</param>
/// <param name="threshold">the threshold level</param>
/// <param name="width">the width of the provided image</param>
/// <param name="padding">the padding to apply when storing
/// this image, usually half the length of the structuring element</param>
public BinaryMorphology(byte[] image, byte threshold, int width, int padding)
: this(image.Select(b => b > threshold).ToArray(), width, padding)
{
}
创建结构
在填充图像时，我们只处理每行左侧的填充。这已足够，因为在这种情况下，图像中每行左侧的像素也与前一行右侧的像素相同。同样，出于同样的原因，我们需要显式地在最后一行右侧进行填充。
数据逐行复制，从bool[]图像复制到新的填充bool[]图像，然后使用BitArray将数据打包成一种格式，其中一个bool表示一个位。最后，数据复制到一个字节数组，该字节数组用作BigInteger对象的构造函数。
给定一个1024x1024的bool[]图像，以下代码行将为我们创建一个BinaryMorphology类实例，我们可以使用它来执行形态学运算，使用我们之前创建的HitOrMissMask。
sbyte[] mask = new sbyte[]
{ 0, 1, 0,
1, 1, 1,
0, 1, 0 };
HitOrMissMask hmMask = new HitOrMissMask(mask, 3, 1, 1);
BinaryMorphology morph = new BinaryMorphology(image, 1024, 1);
让我们来做一些工作
现在图像已转换为所需的打包格式，我们可以应用形态学算子：核心工作是通过以下代码段完成的，该代码段基本上应用了上面给出的命中与未命中变换公式以及我刚才描述的HitOrMissMask类实例。
public void ApplyHitOrMissTransform(HitOrMissMask hmMask,
ref BigInteger input, out BigInteger output)
{
BigInteger scratchImageHit = -1;
BigInteger scratchImageMiss = 0;
for (int i = 0; i < hmMask.HitOrMiss.Length; i++)
if (hmMask.HitOrMiss[i] > 0)
scratchImageHit &= (input >> (Width * hmMask.HitOrMissY[i] +
hmMask.HitOrMissX[i]));
for (int i = 0; i < hmMask.HitOrMiss.Length; i++)
if (hmMask.HitOrMiss[i] < 0)
scratchImageMiss |= (input >> (Width * hmMask.HitOrMissY[i] +
hmMask.HitOrMissX[i]));
output = scratchImageHit & (~scratchImageMiss);
}
给定之前创建的hmMask和morph实例，以下代码将对我们的图像执行腐蚀。
sbyte[] mask = new sbyte[]
{ 0, 1, 0,
1, 1, 1,
0, 1, 0 };
HitOrMissMask hmMask = new HitOrMissMask(mask, 3, 1, 1);
BinaryMorphology morph = new BinaryMorphology(image, 1024, 1);
morph.ApplyHitOrMissTransform(hmMask);
同样，本文随附的项目也提供了一些辅助方法，可用于执行标准形态学运算，并使用本文开头介绍的标准掩码形状。
架构说明
您可能已经注意到，通过使用ref和out参数修饰符，BigInteger在所有函数中都是通过引用传递的。这是因为BigInteger对象是一个值类型，因此，在将其作为函数参数传递时，默认情况下总是按值传递。由于我们用Image数据填充BigInteger对象，我们不希望来回复制这么多数据，因此使用了ref和out参数修饰符。
取回我们的数据
最后，一旦我们完成了所有必要的工作，我们就可以使用GetBoolArray方法来恢复我们转换后的图像。
sbyte[] mask = new sbyte[]
{ 0, 1, 0,
1, 1, 1,
0, 1, 0 };
HitOrMissMask hmMask = new HitOrMissMask(mask, 3, 1, 1);
BinaryMorphology morph = new BinaryMorphology(image, 1024, 1);
morph.ApplyHitOrMissTransform(hmMask);
morph.GetBoolArray();
这将基本上撤销填充并解包图像，使其更容易操作。
/// <summary>
/// unpack and return processed data in bool[]
/// </summary>
/// <returns></returns>
private bool[] GetBoolArray(BigInteger image)
{
bool[] boolProcessedCropped = new bool[(Width - Padding) * Height];
byte[] t1 = image.ToByteArray();
BitArray t2 = new BitArray(t1);
bool[] boolProcessed = new bool[t1.Length * 8];
t2.CopyTo(boolProcessed, 0);
for (int i = 0; i < Height; i++)
{
int off = i * (Width - Padding);
int bytesToCopy = Math.Max(0, Math.Min(boolProcessedCropped.Length,
off + Width - Padding) - i * (Width - Padding));
bytesToCopy =
Math.Min(bytesToCopy, boolProcessed.Length - (i * Width + Padding));
if (bytesToCopy > 0)
Buffer.BlockCopy(boolProcessed, i * Width + Padding,
boolProcessedCropped, off, bytesToCopy);
}
return boolProcessedCropped;
}
标准形态学运算和掩码
除了实现命中与未命中变换之外，所提出的框架还包括使用本文开头介绍的掩码进行腐蚀和膨胀算子。这在执行下一节描述的操作时非常有用，例如确定图像上对象的周长像素集。
private void ErodeDisk1(ref BigInteger input, out BigInteger output)
{
byte[] erodeMask = HitOrMissMask.Disk1;
Erode(erodeMask, 3, 1, 1, ref input, out output);
}
private void Erode(byte[] mask, int width, int xCenter, int yCenter,
ref BigInteger input, out BigInteger output)
{
sbyte[] erodeMask = mask.Select(p => (sbyte)((p == 0) ? 0 : 1)).ToArray();
HitOrMissMask erodeHmMask =
new HitOrMissMask(erodeMask, width, xCenter, yCenter);
ApplyHitOrMissTransform(erodeHmMask, ref input, out output);
}
其他膨胀以及图像开运算和闭运算的实现方式与我刚刚描述的相同。
以下是如何使用这些标准算子：
BinaryMorphology morph = new BinaryMorphology(image, 1024, 1);
morph.ErodeDisk1();
bool[] eroded = morph.GetBoolArray();
附加方法：周长和少数/多数运算
周长图像
这是如何从二值图像中的对象创建周长图像：
public bool[] GetPerimeterImage()
{
BigInteger perim, eroded;
ErodeDisk1(ref PackedImage, out eroded);
perim = PackedImage & ~eroded;
return GetBoolArray(perim);
}
正如您所见，找出对象的周长像素集就像腐蚀图像并从原始二值图像中删除该像素集一样简单。
少数和多数算子
我将描述少数算子；然而，同样的推理也适用于多数算子，只是方式相反。少数算子包括根据直接8连通邻域中至少一定数量的像素是否关闭来选择性地关闭像素。在图像处理方面，这会选择性地关闭密度较低区域的像素，同时使像素密度较高的区域（如您想要保留的对象）不受影响。
此功能实现在具有count参数的Erode方法中。我使用了8个缓冲区来存储像素在像素的8种可能的连通邻域中的数据。数据被移回到中心像素的帧，并使用临时数组进行排序，以便设置较低序图像中的位，并清除较高序图像中的位。然后，我们将原始图像与排序图像数组中的相应图像进行逻辑AND运算。
/// <summary>
/// clear pixels for which at least count neighbors are cleared else the pixel is set
/// </summary>
/// <param name="imageIn"></param>
/// <param name="imageOut"></param>
/// <param name="count"></param>
private void Erode(ref BigInteger imageIn, out BigInteger imageOut, int count)
{
BigInteger[] BitsAround = GetSortedNeighborhoodBits(ref imageIn, count);
imageOut = imageIn & BitsAround[8-count];
}
/// <summary>
/// returns a list of images that contain the bits in the 8-connected neighborhood of
/// every pixel in imageIn. The neighborhood bits are sorted (set and unset bits are
/// seperated). ones go in the images with low ordinals, zeros go in the images with
/// higher ordinals
/// </summary>
/// <param name="imageIn"></param>
/// <param name="count"></param>
/// <returns></returns>
private BigInteger[] GetSortedNeighborhoodBits(ref BigInteger imageIn, int count)
{
BigInteger temp;
BigInteger[] BitsAround = new BigInteger[8];
int index = 0;
for (int i = -1; i <= 1; i++)
for (int j = -Width; j <= Width; j += Width)
{
if (!(i == 0 && j == 0)) // avoid considering the center pixel
{
// negative shifts handled by framework
BitsAround[index] = imageIn << (j + i);
index++;
}
}
// swap bits such that ones go in the images with lower ordinals
// and zeros go in the images with higher ordinals
// need to do more than one pass to bring an on pixel in the highest ordinal
// down to the low ordinals
for (int i = 0; i < 7; i++)
for (int j = 0; j < 7; j++)
{
temp = BitsAround[j + 1];
BitsAround[j + 1] = BitsAround[j + 1] & BitsAround[j];
BitsAround[j] = BitsAround[j] | temp;
}
return BitsAround;
}
结论
在本文中，我们发现了一种非常简洁的方式来使用.NET 4.0的BigInteger类作为对二值图像执行高效形态学运算的手段。二值形态学框架的完整代码可以在本文关联的项目下载文件中查看。希望这将激发其他读者创造性地使用这个强大的类。
- (使用位图二值图像进行快速形态学图像变换的方法。REINVAN DEN BOOMGAARD, RICHARD VAN BALEN)
已知问题
- 演示应用程序中的缩放功能有些不稳定。
- 似乎.NET对
BigInteger的实现存在一个bug，如果BigInteger不是很大，会导致崩溃（感谢jdeh.medical的发现）——我们仍在调查此问题。
历史
- 2010年8月10日：初稿。