使用无监督分水岭算法和过分割减少技术进行图像分割
4.92/5 (24投票s)
使用 OpenCV 和直方图匹配技术实现无监督分水岭算法进行图像分割，以减少过分割。
引言
图像分割是将图像划分为有意义的片段的过程。有许多可用的分割算法，但没有一种算法在所有情况下都完美。在计算机视觉中，图像分割算法有交互式和自动化两种方法。在医学影像中，由于医学应用对精度要求很高，因此交互式分割技术被广泛使用。但某些应用，如图像的语义索引，可能需要完全自动化的分割方法。
自动化分割方法可分为监督分割和无监督分割两大类。在监督分割中，该方法使用机器学习技术为分割算法提供图像中对象（或地面真实片段）的知识。这种方法模仿人类手动分割图像的过程。赋予机器稳健而强大的知识和经验并非易事。目前，由于技术的限制，我们只能创建特定领域图像的监督分割。因此，无监督分割方法在一般应用中得到了广泛应用。
无监督分割可能使用基本的图像处理技术到复杂的优化算法。因此，当我们要求更好的结果时，这些分割方法会花费更多时间。无监督分割算法的主要问题在于平衡过分割和欠分割的难度。
本文介绍了一种用于图像分割的无监督分水岭算法的实现，该算法使用直方图匹配技术来减少分割算法引起的过分割。此实现的一部分已在 OpenCV 官方文档中进行了说明，但我发现自行理解和实现非常困难。因此，我使用 OpenCV 2.4 和 Visual C++ (VS2008) 实现了该算法。但您可以轻松修改代码以适用于任何 C++ 版本。此代码对许多图像有效，但也可能无法按预期对所有图像都有效，这意味着代码需要根据您的应用程序进行调整。欢迎您使用、修改、研究和分享此代码。
背景
该算法包含几个概念，即 Otsu 阈值处理、形态学开运算、距离变换、分水岭算法、色相-饱和度直方图和直方图比较。
Otsu 阈值处理
图像阈值处理是将灰度图像转换为二值图像的方法之一。在任何阈值处理技术中，选择一个好的阈值是主要问题。Otsu 阈值处理是一种可用的自动阈值处理方法。
Otsu 阈值迭代所有可能的阈值，以找到前景和背景散布之和最小的阈值。散布度量的计算涉及几个简单的计算，这些计算已在此处得到了很好的解释。
图 1：原始图像
图 2：应用 Otsu 阈值处理后的图像
应用 Otsu 阈值处理后，会产生一组大大小小的斑块。为了去除小斑块，使用了形态学开运算。
形态学 - 开运算
形态学开运算是应用图像处理中的一些基本算子，即腐蚀和膨胀。开运算的效果更接近腐蚀，因为它会去除区域边缘的一些亮像素以及一些小的孤立前景（亮）像素。基本腐蚀和开运算之间的区别在于，形态学开运算的破坏性比腐蚀操作小。原因是开运算定义为先腐蚀后膨胀，两者都使用相同的结构元素（核）。要了解更多关于形态学开运算的信息，请参阅此文章。不熟悉基本图像处理操作的朋友请参阅此文章，以便了解腐蚀和膨胀的概念。
图 3：对 Otsu 阈值处理后的图像应用形态学开运算后的图像
有时，如果一些区域可以被分割成几个子区域，那么这些区域将更有意义。当分割由一个小线条或一束像素连接起来的包含几个子区域的区域时，可以使用距离变换。
距离变换
距离变换、距离图或距离场是将二值图像的前景表示为到最近障碍物或背景像素的距离的过程。此过程会淡出边缘和小的岛屿或前景，同时保留区域中心。
图 4：距离变换后的图像
图 5：对距离变换后的图像应用阈值处理后的图像：如果有任何松散连接的子区域，此步骤将分离它们。
可以使用前景斑块作为算法的种子来执行分水岭算法。
分水岭分割算法
分水岭分割是一种受自然启发的算法，它模仿了水流经地形的现象。在分水岭分割中，图像被视为地形，其中梯度幅度被解释为高程信息。分水岭算法已通过标记控制的填充技术得到改进，您可以在此处的动画中看到。在此实现中，我们不是手动选择标记，而是从图像中提取较亮的斑块。上述主题实际上解释了分水岭分割的标记提取过程。
图 6：应用分水岭分割后的图像
不同颜色的区域对应图像中的不同片段。在此图像中，我们可以看到它已分割了前景和背景，因为仅从形状就可以识别出对象。但同时，前景和背景都被分割成较小的区域，这些区域作为单个部分是无意义的。这称为过分割。减少这种过分割的一种方法是将视觉上相似的片段合并，并将其视为一个单一的片段。
在计算机视觉中，有许多可用方法来测量图像中两个区域的视觉相似性。匹配技术实际上应基于应用选择。对于具有独特纹理的对象，某些应用可以使用良好的纹理描述符。如果对象集具有独特的形状，则可以使用形状描述符。在一般情况下，可以使用一组众所周知的描述符，如 SIFT 或 SURF。但大多数情况下，由于计算复杂度高，使用复杂的描述符来度量相似性并不实用。一般应用（如网络图像的语义索引）中的大多数图像都包含具有各种纹理、形状和颜色的对象。如果我们假设在单个对象的不同区域中具有相同颜色分布的概率很大，那么我们可以使用颜色特征来度量对象不同片段的相似性。
表达颜色分布的最佳方法之一是使用直方图。但 RGB 颜色空间中图像的直方图并不总是能很好地代表所有应用的颜色分布。HSV（色相、饱和度、明度）颜色空间中的直方图在颜色信息占主导地位的几乎所有应用中都表现良好。
色相-饱和度直方图
颜色的色相分量对应一种主要颜色，而饱和度和明度则对应色相分量中颜色的变化。
图 7：HSV 颜色空间中的图像（直接应用于 OpenCV 中的 imshow() 函数）
图像清晰地显示了同一对象中不同区域（我们使用分水岭分割提取的）的颜色分布是相似的。因此，在此实现中，为每个区域提取了色相-饱和度直方图，并使用称为 Bhattacharyya 距离的度量来衡量相似性。Bhattacharyya 距离度量了两个离散或连续概率分布的相似性。当距离较小时，两个区域将被合并成一个片段。如果图像存在高度过分割，则此合并可以重复多次。
图 8：合并后的分割：不同颜色表示不同的片段。在合并片段之前，黑色区域以不同的颜色出现，这意味着对象已被过度分割。但在该图像中，对象的所有片段都已合并，因此对象的所有子区域颜色都相同。
图 9：合并后的分割映射到图像
使用代码
该代码在 VS2008 中使用 c++ 和 openCV 开发。它只有一个源文件，并且几乎所有代码行都附有注释。
以下代码行包含主函数，在该函数中加载图像、分割并显示最终结果。
int _tmain(int argc, _TCHAR* argv[])
{
//To store the image file name
char* filename = new char[50];
//Print image file name to the string
sprintf(filename,"C:\\img\\6.jpg");
//Read the file
Mat image = imread(filename, CV_LOAD_IMAGE_COLOR);
//show original image
imshow("Original Image",image);
//to store the number of segments
int numOfSegments = 0;
//Apply watershed
Mat segments = watershedSegment(image,numOfSegments);
//Merge segments in order to reduce over segmentation
mergeSegments(image,segments, numOfSegments);
//To display the merged segments
Mat wshed = createSegmentationDisplay(segments,numOfSegments);
//To display the merged segments blended with the image
Mat wshedWithImage = createSegmentationDisplay(segments,numOfSegments,image);
//Display the merged segments
imshow("Merged segments",wshed);
//Display the merged segments blended with the image
imshow("Merged segments with image",wshedWithImage);
waitKey(0);
return 0;
}
在此代码中，首先从本地驱动器加载图像。然后显示原始图像。分割使用函数 `watershedSegment` 完成。该函数通过 `numOfSegments` 返回分割图和片段数量。
然后调用函数 `mergeSegments` 使用直方图匹配技术减少过分割。调用此函数后，它将合并具有相似直方图的区域。根据应用，您可以多次调用此函数，以便进一步减少片段数量。变量 `numOfSegments` 的值将根据您通过调用函数更新的实际片段数量进行调整。
函数 `createSegmentDisplay` 创建一个可显示的图像，为不同片段分配不同的颜色。如果将原始图像传递给该函数，它将把片段颜色代码与原始图像混合，从而使分割清晰可见。
以上是此实现步骤的简要概述。下一节将解释 `watershedSegment`、`mergeSegments` 和 `createSegmentationDisplay` 这三个函数中的代码。
分水岭算法需要一组标记。这些标记通过一组图像处理步骤获得。首先将图像转换为灰度图并应用 Otsu 阈值处理。以下代码执行这两个步骤。
//To store the gray version of the image
Mat gray;
//To store the thresholded image
Mat ret;
//convert the image to grayscale
cvtColor(image,gray,CV_BGR2GRAY);
imshow("Gray Image",gray);
//threshold the image
threshold(gray,ret,0,255,CV_THRESH_BINARY_INV+CV_THRESH_OTSU);
imshow("Image after OTSU Thresholding",ret);
然后使用以下代码行对阈值处理后的图像执行形态学开运算。
//Execute morphological-open
morphologyEx(ret,ret,MORPH_OPEN,Mat::ones(9,9,CV_8SC1),Point(4,4),2);
imshow("Thresholded Image after Morphological open",ret);
应用距离变换以分离任何连接的子区域，并使用以下代码行对结果图像进行阈值处理（归一化是为了显示变换后的图像）。
//get the distance transformation
Mat distTransformed(ret.rows,ret.cols,CV_32FC1);
distanceTransform(ret,distTransformed,CV_DIST_L2,3);
//normalize the transformed image in order to display
normalize(distTransformed, distTransformed, 0.0, 1, NORM_MINMAX);
imshow("Distance Transformation",distTransformed);
//threshold the transformed image to obtain markers for watershed
threshold(distTransformed,distTransformed,0.1,1,CV_THRESH_BINARY);
//Renormalize to 0-255 to further calculations
normalize(distTransformed, distTransformed, 0.0, 255.0, NORM_MINMAX);
distTransformed.convertTo(distTransformed,CV_8UC1);
imshow("Thresholded Distance Transformation",distTransformed);
执行完这些行后，我们将得到一组黑白图像中的白色标记。然后我们需要找到这些标记的轮廓，以便馈送分水岭算法。此步骤使用以下代码行完成。
//calculate the contours of markers
int i, j, compCount = 0;
vector<vector<Point> > contours;
vector<Vec4i> hierarchy;
findContours(distTransformed, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE);
if( contours.empty() )
return Mat();
Mat markers(distTransformed.size(), CV_32S);
markers = Scalar::all(0);
int idx = 0;
//draw contours
for( ; idx >= 0; idx = hierarchy[idx][0], compCount++ )
drawContours(markers, contours, idx, Scalar::all(compCount+1), -1, 8, hierarchy, INT_MAX);
最后，我们可以使用以下代码行将分水岭算法应用于带有标记的图像。
//apply watershed with the markers as seeds
watershed( image, markers );
在 `mergeSegments` 函数中，首先为图像中的每个片段创建一个样本向量集，以便计算直方图。样本的分配和像素收集使用以下代码行完成。
//To collect pixels from each segment of the image
vector<Mat> samples;
//In case of multiple merging iterations, the numOfSegments should be updated
int newNumOfSegments = numOfSegments;
//Initialize the segment samples
for(int i=0;i<=numOfSegments;i++)
{
Mat sampleImage;
samples.push_back(sampleImage);
}
//collect pixels from each segments
for(int i = 0; i < segments.rows; i++ )
{
for(int j = 0; j < segments.cols; j++ )
{
//check what segment the image pixel belongs to
int index = segments.at<int>(i,j);
if(index >= 0 && index<numOfSegments)
{
samples[index].push_back(image(Rect(j,i,1,1)));
}
}
}
变量 `index` 存储当前像素 (j,i) 的片段索引。根据索引填充样本。之后，这些样本用于创建 HS 直方图。以下代码行计算每个样本的 HS 直方图。您可以根据内联注释的说明更改代码以生成任意维度的直方图。
//create histograms
vector<MatND> hist_bases;
Mat hsv_base;
/// Using 35 bins for hue component
int h_bins = 35;
/// Using 30 bins for saturation component
int s_bins = 30;
int histSize[] = { h_bins,s_bins };
// hue varies from 0 to 256, saturation from 0 to 180
float h_ranges[] = { 0, 256 };
float s_ranges[] = { 0, 180 };
const float* ranges[] = { h_ranges, s_ranges };
// Use the 0-th and 1-st channels
int channels[] = { 0,1 };
// To store the histograms
MatND hist_base;
for(int c=1;c<numOfSegments;c++)
{
if(samples[c].dims>0){
//convert the sample to HSV
cvtColor( samples[c], hsv_base, CV_BGR2HSV );
//calculate the histogram
calcHist( &hsv_base, 1, channels, Mat(), hist_base,2, histSize, ranges, true, false );
//normalize the histogram
normalize( hist_base, hist_base, 0, 1, NORM_MINMAX, -1, Mat() );
//append to the collection
hist_bases.push_back(hist_base);
}else
{
hist_bases.push_back(MatND());
}
hist_base.release();
}
最后，匹配相似性并使用以下代码合并具有相似直方图的片段。
//calculate the similarity of the histograms of each pair of segments
for(int c=0;c<hist_bases.size();c++)
{
for(int q=c+1;q<hist_bases.size();q++)
{
//if the segment is not merged alreay
if(!mearged[q])
{
if(hist_bases[c].dims>0 && hist_bases[q].dims>0)
{
//calculate the histogram similarity
similarity = compareHist(hist_bases[c],hist_bases[q],CV_COMP_BHATTACHARYYA);
//if similay
if(similarity>0.8)
{
mearged[q]=true;
if(q!=c)
{
//reduce number of segments
newNumOfSegments--;
for(int i = 0; i < segments.rows; i++ )
{
for(int j = 0; j < segments.cols; j++ )
{
int index = segments.at<int>(i,j);
//merge the segment q with c
if(index==q){
segments.at<int>(i,j) = c;
}
}
}
}
}
}
}
}
}
使用以下代码行（当原始图像不可用时，仅显示每个片段的彩色蒙版）创建可显示的图像。
Mat createSegmentationDisplay(Mat & segments,int numOfSegments,Mat & image)
{
//create a new image
Mat wshed(segments.size(), CV_8UC3);
//Create color tab for coloring the segments
vector<Vec3b> colorTab;
for(int i = 0; i < numOfSegments; i++ )
{
int b = theRNG().uniform(0, 255);
int g = theRNG().uniform(0, 255);
int r = theRNG().uniform(0, 255);
colorTab.push_back(Vec3b((uchar)b, (uchar)g, (uchar)r));
}
//assign different color to different segments
for(int i = 0; i < segments.rows; i++ )
{
for(int j = 0; j < segments.cols; j++ )
{
int index = segments.at<int>(i,j);
if( index == -1 )
wshed.at<Vec3b>(i,j) = Vec3b(255,255,255);
else if( index <= 0 || index > numOfSegments )
wshed.at<Vec3b>(i,j) = Vec3b(0,0,0);
else
wshed.at<Vec3b>(i,j) = colorTab[index - 1];
}
}
//If the original image available then merge with the colors of segments
if(image.dims>0)
wshed = wshed*0.5+image*0.5;
return wshed;
}
如果原始图像可用，则将其彩色蒙版与原始图像中的区域混合。
Linux 构建说明
原始代码已修改为可以在 Linux 环境中编译，由 CodeProject 会员 SoothingMist-Peter 完成。我非常感谢他与我们分享他的成果。以下是他分享的构建说明。
1. 首先下载包含 Linux 构建源文件的 zip 文件。
2. 使用终端设置环境变量，如下所示。
setenv LD_LIBRARY_PATH $PET_HOME/.unsupported/opencv-2.4.8/lib:$LD_LIBRARY_PATH
注意：您应该将行 $PET_HOME/.unsupported/opencv-2.4.8/lib 的部分替换为您安装 OpenCV 库文件夹的路径。
3. 卸载任何冲突的预加载模块，并如下加载 gcc 模块。请根据您计算机上安装的模块版本对此脚本进行必要的更改以提供支持。
module unload compiler/pgi/13.3
module unload mpi/pgi/openmpi/1.6.3
module load compiler/gcc/4.4
module list
4. 使用以下脚本在当前目录中编译文件 AutoSeedWatershed.cpp。
g++ AutoSeedWatershed.cpp -o AutoSeedWatershed `pkg-config $PET_HOME/.unsupported/opencv-2.4.8/lib/pkgconfig/opencv.pc --cflags --libs`
5. 现在您可以如下运行程序。
./AutoSeedWatershed
关注点
我对一些取自标准图像分类研究数据集的图像测试了此代码。但这并不意味着此代码应适用于所有领域的图像。不同领域的图像可能需要对代码的某些部分进行微调或修改。最重要的部分是为分水岭算法查找标记以及计算不同片段的相似性以减少过分割。您可以采用不同的方法，因为有许多方法可以做到这一点。请尝试使用此代码，并随时提出问题、提出建议以及对代码或文章提出任何评论。