实现 K-Means 图像分割算法
5.00/5 (21投票s)
如何实现 K-Means 聚类算法以进行图形栅格图像分割
引言
本文将特别讨论 k-means 聚类算法的实现，以执行栅格图像分割。我们将通过在 C# 中开发实现 k-means 聚类算法以执行图像分割的代码来演示栅格图像分割过程。
什么是图像分割
本文演示了用 C# 开发代码，该代码实现了一种最基本的经典 k-means 聚类算法变体，该变体可以轻松用于执行简单的图形栅格图像分割。图像分割基本上是指图像矢量化颜色量化的过程，其中图像的调色板被减少到一定数量的有限颜色。在以下过程中，我们实际上将整个图像划分为多个片段（即超像素），从而通过使用各种图像处理算法更容易分析以下图像。在执行图像分割时，我们实际上旨在定位原始图像中的对象，并找到定义所定位对象区域的边界。执行以下过程的主要思想是找到共享相同色相参数值的像素区域。因此，这些像素集被分组到多个标记的片段中。在这种情况下，这些多个片段是整个图像的组成部分。
通常，图像分割可以有效地用于许多应用，例如栅格图像压缩或矢量化
-
图像数据压缩：图像分割是许多现有栅格图像有损压缩算法（如 BPG、JPEG-2000、S3TC、PDF、DjVu 等）的基本阶段之一。在这种情况下，分割允许我们通过将整个图像划分为包含相同色相像素的聚类数量，从而显著提高压缩比。通过执行分割，我们实际上将每个像素的色相替换为在单个聚类中选择的质心像素的颜色，从而增加相同颜色的像素数量。这通常导致获得的图像颜色比被压缩的原始图像少得多。有损压缩算法基本上执行对具有相同颜色的像素集的查找，并最终编码较少的数据，这反过来导致更好的图像数据压缩比，并且明显减少图像文件长度。
-
矢量化：从另一方面看，图像分割也可以成功应用于栅格图像矢量化过程。在执行图像矢量化时，分割可以成功用于查找构成整个图像的特定片段的边界。这反过来使得从矢量化过程的一开始就很容易定位整个图像的轮廓。此外，这些轮廓随后被矢量化并由多个矢量线性方程表示。同时，分割允许消除那些冗余和不必要的图像片段，其数据可能不会分配给特定的数据结构，这允许简化矢量化过程，或减少输出矢量化图像文件的潜在大小，使其更轻量化。
图1a 和 图1b 分别说明了作为图像数据压缩或矢量化一部分执行的图像分割结果。
具体来说，栅格图像分割可以通过使用各种算法来执行，例如阈值分割、基于梯度的分割、基于直方图的分割或基于压缩的分割等。在这些算法中，k-means 聚类实际上被证明是最明显和最可靠的算法。实际上，k-means 聚类算法是人工智能机器学习和数据挖掘以及回归分析中最基本的算法之一。在大多数情况下，它允许我们在图像处理过程中避免实际失真，从而获得高质量的图像分割结果。
正如我们已经讨论过的，这通常通过将从图像数据中学习到的观察值数量划分为相应数量的聚类来完成，其中最近的均值表现为超像素，作为整个聚类的颜色原型。此外，让我们回顾一下 k-means 聚类属于 NP-hard 算法类别。
然而，有许多现有的元启发式搜索算法，它们通过最佳聚类图像分解而非常快速地收敛，这反过来允许我们有效地实现整个图像分割，消除图像部分分割的情况。
背景
在本文的这一部分，我们将重点关注 k-means 聚类算法的一种变体，该变体允许我们执行栅格图像分割，而不是其他数据分区任务，例如生成推荐或平方误差和 (SSE) 计算。传统的 k-means 聚类算法已在我之前发表的一篇文章中详细讨论过。这实际上就是为什么在本文中，我们将特别讨论仅处理栅格图像分割的 k-means 聚类算法变体。
图像分割算法
基本上，讨论的图像分割算法非常简单，可以表述如下：
- 创建一个初始聚类，其中包含原始图像和从图像中随机选择的一组质心像素。将构建的初始聚类添加到聚类数组中。
- 从数组中检索当前聚类，并遍历那些超像素（即质心）的集合。
- 对于每个超像素，计算到当前图像中每个像素的实际距离。为此，我们通常使用欧几里得距离公式的变体，该变体允许我们分别找到超像素或给定图像中当前像素的两种颜色 (R; G; B) 3D 向量之间的距离。
- 执行线性搜索以找到那些到当前超像素（即质心）的距离值不超过特定边界的像素。
- 根据新图像构建一个新聚类，该图像包含上一步中选择的所有像素和超像素的当前值。在这种情况下，超像素将作为新构建聚类的质心。此外，我们需要将每个像素的颜色替换为质心的颜色。
- 通过使用质心公式计算当前聚类中所有超像素的最近均值，以找到当前聚类超像素集的特定中心点的坐标。
- 执行检查，如果上一步获得的中心点坐标与新构建聚类中超像素的坐标不相等（中心点未移动）。如果不相等，则将新聚类添加到聚类数组中。
- 执行检查，如果当前聚类是聚类数组中的最后一个聚类。如果是，则转到步骤9，否则返回并继续步骤2。
- 遍历聚类数组，并将每个特定聚类图像合并到被分割的整个图像中。
- 将分割后的图像保存到文件中。
初始化
k-means 图像分割算法的第一个重要步骤是初始化阶段。在此阶段，我们基本上从源图像和随机选择的像素数组创建初始聚类。在这种情况下，生成具有特定坐标的随机像素初始源数组的过程是一个特殊的兴趣点，我们将在本节中详细讨论。
在正常情况下，我们可能会生成一组不同的像素，其随机坐标 (X; Y) 在 W * H 循环的每次迭代中随机选择，其中 W - 宽度，H - 源图像的高度。为此，我们需要实现一个循环并执行多次迭代。在每次迭代中，我们通常分别生成 X <- RAND[0; W] 和 Y <- [0;H] 的值，并创建一个具有特定坐标的点。此外，我们正在检查生成的以下点是否已存在于像素数组中。
然而，上述方法的使用通常会导致所谓的“不良”聚类，并导致分割过程几乎无法预测。这实际上就是为什么为了提供所需的图像分割质量，我们需要通过对随机像素选择过程应用特定条件来修改以下初始值生成方法。
通常，我们至少有两个主要因素对图像分割算法初始数据集的生成过程有很大影响。显然，第一个因素是随机选择点之间的实际距离。距离的典型小值会导致选择两个具有相同颜色的像素的概率增加。这实际上就是为什么距离参数的值必须是最佳的。
让我们事先回顾一下，在这种特殊情况下，实际距离和颜色偏移是实验取值的参数。例如，实际距离的值可以从100到图像宽度或高度的大约一半（例如 W / 2 或 H / 2）不等。同样，为了实现高质量的图像分割，我们可能会将颜色偏移参数的值设置为50，以确保我们选择颜色绝对不同的像素。
为此，我们生成新的随机像素坐标，并检查之前生成的点中是否有任何点到当前点的距离小于上述特定参数的值。为此，我们遍历之前生成的像素坐标数组，并对于每个现有像素，我们检查其到新生成点的距离是否不大于或等于指定距离参数的值。为此，我们通常使用欧几里得距离公式。同样，此时，我们检查随机选择像素的颜色值是否完全符合指定标准。如果两个条件都满足，我们将新生成的点添加到初始像素数组中。
在以下阶段，由于我们已经获得了将作为新构建的初始聚类质心的初始像素集，我们还需要将原始源图像与生成的初始数组关联起来。正如我们可能已经注意到的那样，在这种情况下，图像被表示为像素矩阵，其中该矩阵的每个元素是像素颜色 (R; G; B) 的实际向量。矩阵行 X 和列 Y 的索引实际上是以下像素的坐标。
K-Means 聚类阶段
为了执行实际的图像分割，我们通常会创建一个数组，其中包含在初始化阶段生成的所有聚类。此外，我们还会实现一个循环来遍历以下数组，正如您可能已经从算法的分步说明中了解到的那样，在以下循环的每次迭代中，我们通常会遍历超像素数组（即，为当前聚类预先选择的质心）。对于每个超像素，我们执行线性搜索以找到图像像素的集合，这些像素具有与所应用的边界条件相对应的特定颜色距离。然后，我们从为新构建的聚类选择的像素中创建新图像。每个像素的颜色都将替换为质心超像素的颜色。在这种情况下，新图像将包含相同颜色的像素，这些像素勾勒出原始图像的特定区域。最后，将新构建的聚类添加到聚类数组中。
之后，我们通过找到父聚类中超像素数组的质心来计算中心点的坐标，并检查新构建聚类的质心超像素是否相对于父聚类的中心点移动了。如果是，我们将新构建的聚类添加到聚类数组中，否则根据新构建的聚类和父聚类相同的假设而忽略它。
通常，我们会对目标聚类数组中的每个特定聚类重复上述过程，直到没有更多聚类需要处理。
最后，为了获得准备好的分割图像，我们需要将所有这些聚类构建的图像合并成一个完整的图像。显然，与这些聚类中的每一个相关联的图像将包含原始图像的一个特定颜色区域。关于如何累积合并所有这些图像的指南将在本文后面讨论。
计算欧几里得距离
正如我们已经讨论过的，使用 k-均值聚类算法执行图像分割的主要方面是欧几里得距离公式。在这种情况下，我们主要处理以下公式的两种主要变体，用于计算两个像素之间的实际距离，或者确定两个 3D 向量颜色的相似性。
欧几里得距离公式的最一般表示如下：
其中 L - 是欧几里得距离的值，x，y - 我们将计算实际距离值的两个向量，n - 维度数量（即这些向量的分量）（n = 2）。
由于在这种情况下，我们基本上只处理二维或三维向量，因此使用了以下公式的简化变体。
为了计算两个具有特定坐标的像素之间的实际距离，我们将使用欧几里得距离公式的以下变体
其中 L - 是欧几里得距离值，(x1;x2) 和 (y1;y2) - 分别是两个像素 x 和 y 在笛卡尔平面中的 (X;Y) 坐标值。
此外，为了获得两个颜色 (R; G; B) 3D 向量之间的相似度值，我们将使用此公式的相同 3D 变体
其中 S - 两个颜色向量之间的相似度大小值，其分量分别为 (r1;g1;b1) 和 (r2;g2;b2)。
此外，为了获得更复杂的图像分割结果，我们可以使用皮尔逊相关公式或允许计算两个选定向量之间夹角值的公式来测量两个像素之间的距离或颜色的相似性。
使用现成的聚类构建分割图像
合并过程是分割图像创建过程中的最后一个重要步骤。正如我们已经讨论过的，通过执行 k-means 聚类，我们通常会获得一个聚类数组，其中每个聚类都包含一个特定分割区域的图像。此时，我们的目标是将所有这些分割区域组装成一个完整的输出图像。
为此，我们将使用一个简单的线性算法，该算法处理像素矩阵，将当前矩阵中的每个有效像素复制到先前分配的像素目标矩阵中。具体来说，该算法具有以下公式。
根据以下算法，我们通常需要遍历聚类数组，对于每个聚类中的图像，我们必须检索属于当前分割区域的像素坐标。为此，我们遍历像素矩阵，并对每个像素执行检查，如果以下像素的颜色不等于 (0xFFFFFF) - “白色”。如果不是，我们将当前像素的颜色数据分配给目标像素矩阵中具有相同坐标位置的相应像素。我们通常会继续以下过程，直到我们遍历了在 k-mean 聚类阶段生成的所有聚类。通过合并每个特定聚类的所有这些图像，我们获得了一个现成的分割图像。
Using the Code
在本节中，我们将讨论如何用 C# 开发代码，该代码实现上述简要讨论的算法。在开始之前，让我们特别关注用于存储多个不同对象（例如像素、图像或聚类）数据的各种数据结构。显然，`KMCPoint
class KMCPoint<t>
{
// KMCPoint constructor
public KMCPoint(T X, T Y, Color Clr) { this.X = X; this.Y = Y; this.Clr = Clr; }
// X coordinate property
public T X { get { return m_X; } set { m_X = value; } }
// Y coordinate property
public T Y { get { return m_Y; } set { m_Y = value; } }
// Colorref property
public Color Clr { get { return m_Color; } set { m_Color = value; } }
private T m_X; // X coord
private T m_Y; // Y coord
private Color m_Color; // Colorref (R;G;B)
}
从上面的代码中可以看出，以下类包含两个字段 `private` 变量 `m_X` 和 `m_Y`，它们用于保存特定像素的 X 坐标或 Y 坐标数据。此外，以下类还有另一个 `private` 变量 `m_Color`，它实际上是 `Color` 泛型类的对象，用于以 (R;G;B) 格式存储像素的实际颜色数据。由于所有这些变量都是 `private` 的，我们还额外实现了三个相应的属性 `X`、`Y` 和 `Clr` 来访问和修改这些 `private` 变量的值。通常，以下类还包含一个接受三个参数作为参数的构造函数。当构造 `KMCPoint
在开始讨论代码之前，让我们提醒一下，在以下开发的代码中，为了实例化和处理位图，我们将使用泛型 `Bitmap` 类的修改变体，该变体允许操作存储在先前分配的数组中的像素，而不是使用传统的 `Bitmap.GetPixel(...)` 或 `Bitmap.SetPixel(...)` 方法。
这通常有望 :) 在处理尺寸通常较大的图像时提高图像分割过程的性能。
class LockedBitmap
{
// LockedBitmap class constructors
public LockedBitmap(string filename)
{
// If the m_Bitmap internal object is unitilialized
if (m_Bitmap == null)
{
// Initialize the bitmap object and copy source bitmap into
// the object being constructed
m_Bitmap = new Bitmap(filename);
// Initilaize the rectange area object having size equal to
// size of the bitmap
m_rect = new Rectangle(new Point(0, 0), m_Bitmap.Size);
}
}
public LockedBitmap(Int32 Width, Int32 Height)
{
// If the m_Bitmap internal object is unitilialized
if (m_Bitmap == null)
{
// Initialize the bitmap object and copy source bitmap into
// the object being constructed
m_Bitmap = new Bitmap(Width, Height);
// Initilaize the rectange area object having size equal to
// size of the bitmap
m_rect = new Rectangle(new Point(0, 0), m_Bitmap.Size);
}
}
public LockedBitmap(Bitmap bitmap)
{
// If the m_Bitmap internal object is unitilialized
if (m_Bitmap == null)
{
// Initialize the bitmap object and copy source bitmap into
// the object being constructed
m_Bitmap = new Bitmap(bitmap);
// Initialize the rectangle area object having size equal to
// size of the bitmap
m_rect = new Rectangle(new Point(0, 0), m_Bitmap.Size);
}
}
// Assignment operator overloading for LockedBitmap class object
public static implicit operator LockedBitmap(Bitmap bitmap)
{
// Construct the LockedBitmap class object from the value of
// generic Bitmap object
return new LockedBitmap(bitmap);
}
// Call this method to lock the bitmap pixels buffer
public void LockBits()
{
// Lock bitmap's bits and obtain the BitmapData object
m_BitmapInfo = m_Bitmap.LockBits(m_rect, System.Drawing.Imaging.
ImageLockMode.ReadWrite, m_Bitmap.PixelFormat);
// Obtain the value of pointer of the first line of pixels
m_BitmapPtr = m_BitmapInfo.Scan0;
// Allocating the array of pixels having size equal to
// BitmapInfo.Stride x Bitmap.Height
m_Pixels = new byte[Math.Abs(m_BitmapInfo.Stride) * m_Bitmap.Height];
// Use marshal copy routines to copy the entire buffer of pixels
// to the previously allocated array m_Pixels
System.Runtime.InteropServices.Marshal.Copy(m_BitmapPtr, m_Pixels,
0, Math.Abs(m_BitmapInfo.Stride) * m_Bitmap.Height);
}
// Call this method to unlock and reflect changes to the pixels buffer
public void UnlockBits()
{
// Obtain the value of pointer of the first line of pixels
m_BitmapPtr = m_BitmapInfo.Scan0;
// Use marshal copy routines to copy all elements
// in the array m_Pixels back to the pixels buffer
System.Runtime.InteropServices.Marshal.Copy(m_Pixels, 0,
m_BitmapPtr, Math.Abs(m_BitmapInfo.Stride) * m_Bitmap.Height);
// Unlock the bits.
m_Bitmap.UnlockBits(m_BitmapInfo);
}
// Call this method to retrieve the color reference of pixel
// with coordinates (Row;Col)
public Color GetPixel(Int32 Row, Int32 Col)
{
// Obtain the value of color depth
Int32 Channel = System.Drawing.Bitmap.GetPixelFormatSize
(m_BitmapInfo.PixelFormat);
// Compute the value of index of pixel in the m_Pixels buffer
Int32 Pixel = (Row + Col * m_Bitmap.Width) * (Channel / 8);
// Declaring three variables to be assigned the values of colors (R;G;B)
Int32 Red = 0, Green = 0, Blue = 0, Alpha = 0;
// Check if the bitmap is 32-bit color depth
if (Channel == 32)
{
// Assign the values of specific elements in the
// array of pixels to corresponding variables
Blue = m_Pixels[Pixel];
Green = m_Pixels[Pixel + 1];
Red = m_Pixels[Pixel + 2];
Alpha = m_Pixels[Pixel + 3];
}
// Check if the bitmap is 24-bit color depth
else if (Channel == 24)
{
// Assign the values of specific elements in the
// array of pixels to corresponding variables
Blue = m_Pixels[Pixel];
Green = m_Pixels[Pixel + 1];
Red = m_Pixels[Pixel + 2];
}
// Check if the bitmap is 16-bit color depth
else if (Channel == 16)
{
// Assign the values of specific elements in the
// array of pixels to corresponding variables
Blue = m_Pixels[Pixel];
Green = m_Pixels[Pixel + 1];
}
// Check if the bitmap is 8-bit color depth
else if (Channel == 8)
{
// Assign the value of specific element in the
// array of pixels to corresponding variables
Blue = m_Pixels[Pixel];
}
// Construct the color reference object from the value of variables
// assigned the specific values of colors
return (Channel != 8) ?
Color.FromArgb(Red, Green, Blue) : Color.FromArgb(Blue, Blue, Blue);
}
// Call this method to set the color of pixel Clr with coordinates (Row;Col)
public void SetPixel(Int32 Row, Int32 Col, Color Clr)
{
// Obtain the value of color depth
Int32 Channel =
System.Drawing.Bitmap.GetPixelFormatSize(m_BitmapInfo.PixelFormat);
// Compute the value of index of pixel in the m_Pixels buffer
Int32 Pixel = (Row + Col * m_Bitmap.Width) * (Channel / 8);
// Check if the bitmap is 32-bit color depth
if (Channel == 32)
{
// If so, assign the value of each color (R;G;B;A) to the specific
// elements in the array of pixels
m_Pixels[Pixel] = Clr.B;
m_Pixels[Pixel + 1] = Clr.G;
m_Pixels[Pixel + 2] = Clr.R;
m_Pixels[Pixel + 3] = Clr.A;
}
// Check if the bitmap is 24-bit color depth
else if (Channel == 24)
{
// If so, assign the value of each color (R;G;B) to the specific
// elements in the array of pixels
m_Pixels[Pixel] = Clr.B;
m_Pixels[Pixel + 1] = Clr.G;
m_Pixels[Pixel + 2] = Clr.R;
}
// Check if the bitmap is 16-bit color depth
else if (Channel == 16)
{
// If so, assign the value of each color (B;G) to the specific
// elements in the array of pixels
m_Pixels[Pixel] = Clr.B;
m_Pixels[Pixel + 1] = Clr.G;
}
// Check if the bitmap is 8-bit color depth
else if (Channel == 8)
{
// If so, assign the value of each color (B) to the specific
// element in the array of pixels
m_Pixels[Pixel] = Clr.B;
}
}
// Use this property to retrieve the width and height of an image locked
public Int32 Width { get { return m_Bitmap.Width; } }
public Int32 Height { get { return m_Bitmap.Height; } }
// Use this method to save the bitmap to file
public void Save(string filename)
{
// Calling Save(filename) method to save the bitmap to a file
m_Bitmap.Save(filename);
}
// Declaring Bitmap class object
public Bitmap m_Bitmap = null;
// Declaring Rectangle class Object
private Rectangle m_rect;
// Declaring point to bitmap pixels buffer
private IntPtr m_BitmapPtr;
// Declaring array of pixels;
private byte[] m_Pixels = null;
// Declaring BitmaData object
private BitmapData m_BitmapInfo = null;
}
当 `LockedBitmap` 类对象初始化时，会调用适当的构造函数。在此代码中，我们使用多个构造函数声明，无论是从文件加载 `bitmap`，创建指定 `width` 和 `height` 的空 `bitmap`，还是使用浅层复制机制将一个 `bitmap` 对象复制到另一个对象。当调用这些三个构造函数中的一个时，我们正在检查内部泛型 `Bitmap` 类对象是否尚未初始化，如果是，我们使用 new 运算符初始化该对象。此外，此时，我们正在初始化泛型 `Rectangle` 类对象，以操作具有特定大小的 `bitmap` 矩形区域。之后，在对 `bitmap` 的像素矩阵执行各种操作之前，我们需要调用 `LockBits()`/`UnlockBits()` 方法，通过调用 `GetPixel(...)`/`SetPixel(...)` 方法。通过调用这两个方法，我们实际上锁定或解锁持有位图像素矩阵的内部内存缓冲区。为此，我们调用泛型 `Bitmap.LockBits(...)` 方法，这会导致内部缓冲区被锁定。之后，我们获得以下内部缓冲区中第一行像素的指针。最后，我们使用泛型封送复制方法将内部缓冲区的元素实际移动到先前分配的像素数组中。同样，我们通过调用 `UnlockBits()` 方法执行解锁，在执行过程中，我们获得位图内部缓冲区的第一个像素行的指针，并调用相同的封送复制方法将像素数组移回位图的内部缓冲区。
这些方法也在 `LockedBitmap` 类对象中重新使用。实际上，在以下方法执行期间，我们通常计算具有坐标 (`Row`; `Col`) 的特定像素在像素间隔数组中的绝对索引值。由于我们已经获得了索引的实际值，因此我们通过调用上述方法来检索或设置给定像素的颜色参考值。
我们要讨论的另一个类是 `KMCFrame`，它用于存储在 k-means 聚类过程中创建的每个聚类的数据。让我们提醒一下，“聚类”实际上是一个对象，具有诸如包含原始图像当前分割区域的图像对象、质心超像素数组、计算为所有质心质量中心的中心超像素等参数
class KMCFrame
{
// KMCFrame Constructor
public KMCFrame(LockedBitmap Frame, List<KMCPoint<int>> Centroids,
KMCPoint<int> Center)
{
this.Frame = Frame;
this.m_Centroids = Centroids; this.Center = Center;
}
// Bitmap Frame Property
public LockedBitmap Frame
{
get { return m_Frame; }
set { m_Frame = value; }
}
// Centroids List Property
public List<KMCPoint<int>> Centroids
{
get { return m_Centroids; }
set { m_Centroids = value; }
}
// Central Super-Pixel Property
public KMCPoint<int32> Center
{
get { return m_Center; }
set { m_Center = value; }
}
// Bitmap Frame Object
private LockedBitmap m_Frame = null;
// Central Super-Pixel Point Object
private KMCPoint<double><int32> m_Center;
// Array of Super-Pixel Objects (i.e. Centroids)
private List<KMCPoint<int>><kmcpoint<int> m_Centroids = null;
}
显然，以下类包含三个 `private` 成员变量，例如 `m_Frame`，它是一个 `Bitmap` 类对象，实际用于存储与以下聚类相关联的图像数据；`m_Centroids`，一个 `List
我们需要实现的另一个数据结构是 `KMCClusters` 类，并将其派生自 `IEnumerable
特别是，以下类包含 `void Init(string Filename, Int32 Distance, Int32 Offset)` 方法，该方法将进一步用于初始化空聚类数组。以下 C# 代码演示了以下方法的实现
public void Init(string Filename, Int32 Distance, Int32 Offset)
{
// Declare a bitmap object to load and
// use the original image to be segmented
LockedBitmap FrameBuffer = new LockedBitmap(Filename);
// Initialize the array of super-pixels
// by creating List<KMCPoint<int>> class object
List<KMCPoint<int>> Centroids = new List<KMCPoint<int>>();
// Generate an initial array of super-pixels of the original source image
// stored in the FrameBuffer bitmap object
this.Generate(ref Centroids, FrameBuffer, Distance, Offset);
// Compute the value of the centeral super-pixel coordinates and assign it
// to the Mean local variable
KMCPoint<int> Mean = this.GetMean(FrameBuffer, Centroids);
// Append an initial cluster being initialized to the array of clusters
m_Clusters.Add(new KMCFrame(FrameBuffer, Centroids, Mean));
}
以下方法接受作为参数传递的三个参数值，包括原始源图像的文件名，以及距离和颜色偏移参数的值。当调用以下方法时，首先，它构造一个 `bitmap` 对象 `FrameBuffer`，并将其第一个参数 `Filename` 的值传递给其构造函数。当创建此对象时，它会从文件加载原始图像，并将原始图像的每个像素的数据分配给特定的内部 `private` 数据结构，例如像素矩阵。加载原始图像后，通过构造 `List
在初始化了用于保存初始聚类的图像和超像素数组数据的特定数据结构之后，我们现在计算中心超像素坐标并将其分配给正在创建的 `KMCFrame` 类对象的一个参数。之后，我们调用方法 `m_Clusters.Add(new KMCFrame(FrameBuffer, Centroids, Mean));` 将初始聚类数据添加到聚类数组中。
`Generate(...)` 方法在此代码中具有特殊意义，因为它实现了允许为初始聚类随机创建超像素数组的算法
public void Generate(ref List<kmcpoint<int>> Centroids,
LockedBitmap ImageFrame, Int32 Distance, Int32 Offset)
{
// Compute the number of iterations performed by the main loop
// equal to image W * H
// The following value is the maximum possible number of random
// super-pixel being generated
Int32 Size = ImageFrame.Width * ImageFrame.Height;
ImageFrame.LockBits();
// Performing Size - iterations of the following loop
// to generate a specific amount of super-pixels
for (Int32 IterCount = 0; IterCount < Size; IterCount++)
{
// Obtain a random value of X - coordinate of the current super-pixel
Int32 Rand_X = rand.Next(0, ImageFrame.Width);
// Obtain a random value of Y - coordinate of the current super-pixel
Int32 Rand_Y = rand.Next(0, ImageFrame.Height);
// Create and instantiate a point object by using the values of
// Rand_X, Rand_Y and Colorref parameters. The value of colorref is
// retrieved by using the GetPixel method for the current bitmap object
KMCPoint<int> RandPoint = new KMCPoint<int>(Rand_X,
Rand_Y, ImageFrame.GetPixel(Rand_X, Rand_Y));
// Performing a validity check if none of those super-pixel previously
// selected don't exceed the distance and color offset boundary to the
// currently generated super-pixel with coordinates Rand_X and Rand_Y
// and specific color stored as a parameter value of Clr variable
if (!this.IsValidColor(Centroids, RandPoint, Offset) &&
!this.IsValidDistance(Centroids, RandPoint, Distance))
{
// If not, check if the super-pixel with the following
// coordinates and color already exists in the array of centroid
// super-pixels being generated.
if (!Centroids.Contains(RandPoint))
{
// If not, append the object RandPoint to the array
// of super-pixel objects
Centroids.Add(RandPoint);
}
}
}
ImageFrame.UnlockBits();
}
在以下方法执行期间，我们首先计算与随机超像素最大可能数量完全对应的总迭代次数，并执行一系列迭代，其次数等于之前获得的总迭代次数。在每次特定迭代期间，我们分别在 `[0; ImageFrame.Width]` 和 `[0; ImageFrame.Height]` 范围内生成两个随机值，以获得当前超像素的坐标。之后，我们构造一个 `KMCPoint` 类对象，并将之前获得的值作为参数传递给该对象的构造函数。此外，由于已经获得了新超像素的坐标，我们还通过调用 `ImageFrame.GetPixel(Rand_X, Rand_Y)` 方法从图像像素矩阵中获取颜色数据。
在添加正在构造的超像素对象之前，我们正在检查生成的超像素坐标和颜色是否完全符合上述条件。为此，我们使用 `this.IsValidDistance(Centroids, RandPoint, Distance)` 或 `this.IsValidColor(Centroids, RandPoint, Offset)` 两种方法执行超像素有效性验证。以下 C# 代码片段实现了上述两种方法
private bool IsValidDistance(List<kmcpoint<int>> Points,
KMCPoint<int> Target, Int32 Distance)
{
Int32 Index = -1; bool Exists = false;
// Iterate through the array of super-pixels until we've found
// the super-pixel which distance to the target super-pixel
// is less than or equals to the specified boundary
while (++Index < Points.Count() && !Exists)
// For each super-pixel from the array, we compute the value of
// distance and perform a check
// if the following value is less than or equals to
// the value of specific boundary parameter.
Exists = ((Math.Abs(Target.X - Points.ElementAt(Index).X) <= Distance) ||
(Math.Abs(Target.Y - Points.ElementAt(Index).Y) <= Distance)) ?
true : false;
return Exists;
}
private bool IsValidColor(List<kmcpoint<int>> Points, KMCPoint<int> Target,
Int32 Offset)
{
Int32 Index = -1; bool Exists = false;
// Iterate through the array of super-pixels until we've found
// the super-pixel which color offset to the target super-pixel
// is less than or equals to the specified boundary
while (++Index < Points.Count() && !Exists)
// For each super-pixel from the array, we compute the value of
// color offset and perform a check
// if the following value is less than or equals to
// the value of specific boundary parameter.
Exists = (Math.Sqrt(Math.Pow(Math.Abs(Points[Index].Clr.R -
Target.Clr.R), 2) +
Math.Pow(Math.Abs(Points[Index].Clr.G -
Target.Clr.G), 2) +
Math.Pow(Math.Abs(Points[Index].Clr.B -
Target.Clr.B), 2))) <= Offset ? true : false;
return Exists;
}
通过执行这些方法，我们通常遍历生成的超像素数组，并对每个特定项计算到新超像素的距离或颜色偏移，新超像素的坐标已在 `Generate` 方法执行期间生成。此外，我们正在检查到新超像素的距离或颜色偏移是否不超过指定边界。如果是，我们中断循环执行并返回特定的结果值。特别是，如果超像素数组中至少包含一个超像素，其相对于新超像素的距离或颜色偏移小于或等于特定边界参数的值，则此方法返回 `false`。这意味着新超像素无效，不能添加到超像素数组中。为了计算实际距离和颜色偏移，我们通常使用本文背景部分讨论的相同欧几里得距离公式。
此外，在此类中，我们还实现了另一个重要方法 `KMCPoint
public KMCPoint<int> GetMean(LockedBitmap FrameBuffer,
List<KMCPoint<int>> Centroids)
{
// Declaring two variables to assign the value of the "mean" of
// the sets of coordinates (X;Y) of each super-pixel
double Mean_X = 0, Mean_Y = 0;
// Iterating through the array of super-pixels and for each
// super-pixel retrieve its X and Y coordinates and divide it
// by the overall amount of super-pixels. After that, sum up
// each value with the values of Mean_X and Mean_Y variables
for (Int32 Index = 0; Index < Centroids.Count(); Index++)
{
Mean_X += Centroids[Index].X / (double)Centroids.Count();
Mean_Y += Centroids[Index].Y / (double)Centroids.Count();
}
// Convert the values of Mean_X and Mean_Y to Int32 datatype
Int32 X = Convert.ToInt32(Mean_X);
Int32 Y = Convert.ToInt32(Mean_Y);
FrameBuffer.LockBits();
Color Clr = FrameBuffer.GetPixel(X, Y);
FrameBuffer.UnlockBits();
// Constructing KMCPoint<int> object and return its value
return new KMCPoint<int>(X, Y, Clr);
}
在以下方法执行期间，我们通常遍历之前生成的超像素数组，对于每个超像素，检索其 X 或 Y 坐标，并将其除以数组中超像素的总数。然后，我们将获得的每个值累加到 `Mean_X` 和 `Mean_Y` 和变量中。您可能已经注意到，X 或 Y 坐标的“均值”是单独计算的。之后，这些 `Mean_X` 和 `Mean_Y` 的值转换为 `Int32` 数据类型。通过使用这些值以及从原始图像中检索到的超像素颜色值，我们最终构造 `KMCPoint
我们现在要讨论的最基本的类是 `ImageSegmentation` 类的实现。在以下类中，我们通常声明方法 `public void Compute(string InputFile, string OutputFile)`，它是图像分割引擎的主要部分，执行实际的 k-means 聚类。此外，除了此方法之外，我们还将实现两个更简单的方法，用于执行欧几里得距离计算，我们将在后面详细讨论。
这是上述 `Compute` 方法的实现
public void Compute(string InputFile, string OutputFile)
{
// Initialize the code execution timer
var watch = System.Diagnostics.Stopwatch.StartNew();
// Initialize the directory info reference object
DirectoryInfo dir_info = new DirectoryInfo("Clusters");
// Check if the directory with name "Clusters" is created.
// If not, create the directory with name "Clusters"
if (dir_info.Exists == false) dir_info.Create();
// Initialize the array of clusters by generating an initial cluster
// containing the original source image associated
// with the array of super-pixels
m_Clusters.Init(InputFile, m_Distance, m_OffsetClr);
// Initialize the bitmap object used to store the resulting segmented image
LockedBitmap ResultBitmap =
new LockedBitmap(m_Clusters[0].Frame.Width, m_Clusters[0].Frame.Height);
Int32 FrameIndex = 0;
// Iterate throught the array of clusters until we've processed
// all clusters being generated
for (Int32 Index = 0; Index < m_Clusters.Count(); Index++)
{
// For each particular cluster from the array,
// obtain the values of bitmap object and
// the List<KMCPoint<int>> object which is the array of
// centroid super-pixels
List<KMCPoint<int>> Centroids = m_Clusters[Index].Centroids.ToList();
LockedBitmap FrameBuffer =
new LockedBitmap(m_Clusters[Index].Frame.m_Bitmap);
// Save the image containing the segmented area associated with
// the current cluster to the specific file,
// which name has the following format,
// for example "D:\Clusters\Cluster_N.jpg"
FrameBuffer.Save("Clusters\\Cluster_" + FrameIndex + ".jpg");
FrameBuffer.LockBits();
// Iterating through the array of centroid super pixels
// and for each super-pixel, perform a linear search
// to find all those pixels in the current image whose distance
// does not exceed the value of specific boundary parameter.
for (Int32 Cnt = 0; Cnt < Centroids.Count(); Cnt++)
{
// Obtain the value of Width and Height of the image
// for the current cluster
Int32 Width = FrameBuffer.Width;
Int32 Height = FrameBuffer.Height;
// Create a bitmap object to store an image for
// the newly built cluster
LockedBitmap TargetFrame = new LockedBitmap
(FrameBuffer.Width, FrameBuffer.Height);
TargetFrame.LockBits();
// Iterate through each element of the matrix of pixels
// for the current image
for (Int32 Row = 0; Row < FrameBuffer.Width; Row++)
{
for (Int32 Col = 0; Col < Height; Col++)
{
// For each pixel in this matrix,
// compute the value of color offset of
// the current centroid super-pixel
double OffsetClr = GetEuclClr(new KMCPoint<int>
(Row, Col, FrameBuffer.GetPixel(Row, Col)),
new KMCPoint<int>(Centroids[Cnt].X,
Centroids[Cnt].Y, Centroids[Cnt].Clr));
//Perform a check if the color offset value
//does not exceed the value of boundary parameter
if (OffsetClr <= 50)
{
// Copy the current pixel to the target image
// for the newly created cluster
TargetFrame.SetPixel(Row, Col, Centroids[Cnt].Clr);
}
// Otherwise, set the color of the current pixel
// to "white" (R;G;B) => (255;255;255)
// in the target bitmap for the newly built cluster
else TargetFrame.SetPixel
(Row, Col, Color.FromArgb(255, 255, 255));
}
}
TargetFrame.UnlockBits();
// Create an array of centroid super-pixels and append
// it the value of current centroid super-pixel retrieved
List<KMCPoint<int>> TargetCnts = new List<KMCPoint<int>>();
TargetCnts.Add(Centroids[0]);
// Compute the "mean" value for the newly created cluster
KMCPoint<int> Mean = m_Clusters.GetMean(TargetFrame, TargetCnts);
// Perform a check if the "mean" point coordinates
// of the newly created cluster are
// not equal to the coordinates of the current
// centroid super-pixel (e.g. the centroid
// super-pixel has been moved). If so,
// append a newly built cluster to the array of clusters
if (Mean.X != m_Clusters[Index].Center.X &&
Mean.Y != m_Clusters[Index].Center.Y)
m_Clusters.Add(TargetFrame, TargetCnts, Mean);
FrameIndex++;
}
FrameBuffer.UnlockBits();
}
ResultBitmap.LockBits();
// Iterate through the array of clusters previously obtained
for (Int32 Index = 0; Index < m_Clusters.Count(); Index++)
{
// For each cluster, retrieve a specific image
// containing the segmented area
LockedBitmap FrameOut = new LockedBitmap
(m_Clusters[Index].Frame.m_Bitmap);
FrameOut.LockBits();
FrameOut.Save("temp_" + Index + ".jpg");
// Obtain the dimensions of that image
int Width = FrameOut.Width, Height = FrameOut.Height;
// Iterate through the matrix of pixels
// for the current image and for each
// pixel, perform a check if its color is not equal to
// "white" (R;G;B) => (255;255;255).
// If not, copy the pixel data to the target matrix of pixels
// for the resulting segmented image
for (Int32 Row = 0; Row < Width; Row++)
{
for (Int32 Col = 0; Col < Height; Col++)
{
if (FrameOut.GetPixel(Row, Col) !=
Color.FromArgb(255, 255, 255))
{
ResultBitmap.SetPixel(Row, Col,
FrameOut.GetPixel(Row, Col));
}
}
}
FrameOut.UnlockBits();
}
ResultBitmap.UnlockBits();
// Save the segmented image to file with name
// which is the value of OutputFile variable
ResultBitmap.Save(OutputFile);
watch.Stop(); // Stop the execution timer
// Obtain the value of executing time in milliseconds
var elapsedMs = watch.ElapsedMilliseconds;
// Create timespan from the elapsed milliseconds value
TimeSpan ts = TimeSpan.FromMilliseconds(elapsedMs);
// Print the message "Done" and the formatted execution time
Console.WriteLine("***Done***\n" + ts.ToString(@"hh\:mm\:ss"));
}
在执行 k-means 聚类计算时，我们实际上需要在执行主循环迭代之前，通过生成初始聚类并将其附加到以下数组来初始化聚类数组。为此，我们调用上面详细讨论的 `m_Clusters.Init(...)` 方法。之后，我们进入主处理循环。在以下主循环的每次迭代中，我们检索当前图像和分配给当前聚类对象的特定数据结构的质心超像素数组的数据。在获得质心超像素数组后，我们遍历此数组的元素，对于每个超像素，我们旨在找到当前图像中颜色偏移值不超过特定边界值（例如，有效像素）的像素子集。由于我们已经获得了这样的子集，我们通过将这些有效像素复制到新图像中并为新构建的聚类分配新的质心超像素子集来构建新聚类。之后，我们正在检查“均值”超像素坐标是否不等于所取父聚类中当前质心超像素的坐标。如果不是，我们构造一个新的聚类对象并将其附加到聚类数组中。此时，我们通常会为从数组中检索到的当前聚类的每个特定质心超像素继续以下过程。请注意，只有初始聚类可能包含多个质心超像素，其他聚类仅限于包含一个超像素。
完成 k-means 聚类过程后，我们需要实际将每个聚类的图像“收集”到分割结果图像中。为此，我们遍历聚类数组并检索每个特定图像的像素矩阵。然后，我们遍历以下矩阵并检查当前像素（具有特定坐标）的颜色是否不等于“白色”0xFFFFFF。如果不是，我们将以下当前像素复制到结果图像的像素矩阵中。
本节我们将讨论的最后一个方面是执行两个像素或两种色相之间欧几里得距离计算的方法。
public double GetEuclD(KMCPoint<int> Point1, KMCPoint<int> Point2)
{
// Compute the Euclidian distance between two pixel in the 2D-space
return Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) +
Math.Pow(Point1.Y - Point2.Y, 2));
}
public double GetEuclClr(KMCPoint<int> Point1, KMCPoint<int> Point2)
{
// Compute the Euclidian distance between two colors in the 3D-space
return Math.Sqrt(Math.Pow(Math.Abs(Point1.Clr.R - Point2.Clr.R), 2) +
Math.Pow(Math.Abs(Point1.Clr.G - Point2.Clr.G), 2) +
Math.Pow(Math.Abs(Point1.Clr.B - Point2.Clr.B), 2));
}
以下方法非常简单，通常返回本文背景理论部分讨论的欧几里得距离公式表达式的计算值。
最后，下面列出的 C# 代码演示了程序的主函数以及 `ImageSegmentation` 类对象的创建和初始化。
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Image Segmentation Utility v.1.0a
by Arthur V. Ratz, CPOL @ 2017\n");
Console.Write("Input file name: ");
string InpFile = Console.ReadLine();
Console.Write("Output file name: ");
string OutFile = Console.ReadLine();
ImageSegmentation ImageSeg = new ImageSegmentation();
ImageSeg.Compute(InpFile, OutFile);
Console.ReadKey();
}
}
关注点
本文讨论的算法有许多有趣的变体，基于使用机器学习和数据挖掘的不同技术和方法，包括使用皮尔逊相关代替欧几里得距离公式，实现 k-means++ 初始化算法以提高聚类质量，使用 min-max 选择方法来找到所有那些距离特定超像素最近的像素。
历史
- 2017年8月27日 - 文章第一次修订发布
- 2017年8月29日 - 文章最终修订发布