首页 > 代码库 > 区域生长算法的一种C++实现

区域生长算法的一种C++实现

  区域生长算法是一种图像分割方法,能够将图像中具有相同特征的连通区域分割出来,同时保证较好的边缘信息。

  区域生长算法的优点是简单,容易实现;但空间和时间复杂度较高,对分割图像要求较高,否则容易形成孔洞和过分割。

  区域生长算法的基本思想是首先获取分割区域的一个种子点,然后在种子点的周围搜索与该种子点有相似性质的像素点,合并到种子区域中。然后将合并的像素作为新的种子点继续搜索,直到种子区域中所有像素周围没有相似的像素点,算法结束。

  如果要实现区域生长算法,基本算法流程是:

  1. 选取种子点p(x0,y0),用堆栈表示种子区域,将种子点push到种子堆栈中

  2. 将种子堆栈中第一个种子点pop出堆栈,并以该点为中心,遍历该中心8邻域像素

  3. 判断遍历像素点是否已经在种子区域中,如果否,判断遍历像素点是否满足相邻种子点相似性,如果像素点(x,y)满足相似性,将(x,y)push到堆栈中

  4. 重复步骤 2-3,直至种子堆栈为空。

  从基本思想可以知道,影响区域生长算法的要素有三个:种子点的选取搜索路径的选择像素相似性的判断

  种子点的选取:一般情况下,区域生长算法是半交互式的分割算法,需要用户选取种子点。也可以是通过其他算法计算出来的种子点。

  搜索路径的选择:搜索路径一般选择相邻的像素,以二维图像为例,一般为8邻域搜索,或者4邻域搜索;以三维图像为例,一般为26邻域搜索或者6邻域搜索。

  像素相似性的判断:相似性一般以像素值的相近程度为判断标准,例如,可以设置一定灰度范围做为相似的标准。也可以通过计算满足某种形状或者性质作为判断标准。

  接着根据上文中提到的算法,作者提出一种C++的实现方法,该实现不基于任何类库,以二维图像为例,假设图像的数据类型为char型。

首先,为了便于操作,需要定义种子点的类:

技术分享
 1 class Point2D
 2 {
 3 public:
 4     Point2D(){}
 5     Point2D(int ix, int iy)
 6     {
 7         this->x = ix;
 8         this->y = iy;
 9     }
10 
11     ~Point2D(){}
12 
13     Point2D operator+(const Point2D& a) const
14     {
15         return Point2D(x + a.x, y + a.y);
16     }
17 
18     Point2D operator-(const Point2D& a) const
19     {
20         return Point2D(x - a.x, y - a.y);
21     }
22 
23     bool operator=(const Point2D & a)
24     {
25         return (x == a.x && y == a.y);
26     }
27 
28     int x;
29     int y;
30 };
View Code

然后,定义种子点的邻域信息:

技术分享
const Point2D PointShift2D[8] =
{
    Point2D(1, 0),
    Point2D(1, -1),
    Point2D(0, -1),
    Point2D(-1, -1),
    Point2D(-1, 0),
    Point2D(-1, 1),
    Point2D(0, 1),
    Point2D(1, 1)
};
View Code

然后,定义区域生长算法类的头文件:

技术分享
class RegionGrowing
{
public:
    RegionGrowing();
    ~RegionGrowing();

    void SetInputData(char *pData, int width, int height);

    void SetSeedPoint(Point2D &p);

    void SetThreshold(int low, int hight);

    bool RegionGrow2D();

    char* GetOutput();

private:
    int LowThreshold;
    int HighThreshold;

    int Width;
    int Height;

    char *InputData;
    char *OutputData;

    Point2D SeedPoint;
};
View Code

然后,是区域生长算法类的实现:

技术分享
 1 #include "RegionGrowing.h"
 2 #include <stack>
 3 
 4 RegionGrowing::RegionGrowing()
 5 {
 6     this->InputData =http://www.mamicode.com/ nullptr;
 7     this->OutputData =http://www.mamicode.com/ nullptr;
 8 }
 9 
10 RegionGrowing::~RegionGrowing()
11 {
12 
13 }
14 
15 void RegionGrowing::SetInputData(char *pData, int width, int height)
16 {
17     this->InputData =http://www.mamicode.com/ pData;
18     this->Width = width;
19     this->Height = height;
20 }
21 
22 void RegionGrowing::SetSeedPoint(Point2D &p)
23 {
24     this->SeedPoint = p;
25 }
26 
27 void RegionGrowing::SetThreshold(int low, int high)
28 {
29     this->LowThreshold = low;
30     this->HighThreshold = high;
31 }
32 
33 bool RegionGrowing::RegionGrow2D()
34 {
35     if (this->InputData =http://www.mamicode.com/= nullptr || this->OutputData =http://www.mamicode.com/= nullptr)
36     {
37         return false;
38     }
39 
40     int index = this->SeedPoint.y * this->Width + this->SeedPoint.x;
41     int seedValue = http://www.mamicode.com/this->InputData[index];
42 
43     std::stack<Point2D> pointStack;
44     pointStack.push(this->SeedPoint);
45 
46     memset(this->OutputData, 0, sizeof(char)*this->Width*this->Height);
47 
48     while (!pointStack.empty())
49     {
50         Point2D topPoint = pointStack.top();
51         pointStack.pop();
52 
53         for (int i = 0; i < 8; i++)
54         {
55             Point2D p = topPoint + PointShift2D[i];
56 
57             index = p.y * this->Width + p.x;
58 
59             if (this->InputData[index] > this->LowThreshold &&
60         this->InputData[index] < this->HighThreshold &&
61               this->OutputData[index] == 0)
62             {
63                 this->OutputData[index] = 126;
64                 pointStack.push(p);
65             }
66         }
67     }
68 
69     return true;
70 }
71 
72 char* RegionGrowing::GetOutput()
73 {
74     return this->OutputData;
75 }
View Code

 

 声明本博客文章未特殊注明均为原创,转载请注明作者和原地址

区域生长算法的一种C++实现