OpenCV
在模块opencv_contrib
中实现了基于图的图像分割算法,其实现和作者提供的工程源码略有差别
下面首先解析源码,然后通过示例验证分割效果
官网参考文档:cv::ximgproc::segmentation::GraphSegmentation Class Reference 头文件segmentation.hpp - /path/to/include/opencv4/opencv2/ximgproc/segmentation.hpp
源文件graphsegmentation.cpp - /path/to/opencv_contrib/modules/ximgproc/src/graphsegmentation.cpp
实现示例graphsegmentation_demo.cpp - /path/to/opencv_contrib/modules/ximgproc/samples/graphsegmentation_demo.cpp
OpenCV
源码比较复杂,抽取相应实现到GraphLib/cplusplus/samples/graphsegmentation
命令空间 算法位于命令空间cv::ximgproc::segmentation
中
1 2 3 namespace cv { namespace ximgproc { namespace segmentation {
并查集 OpenCV
实现了并查集操作,定义了并查集元素类PointSetElement
以及并查集操作类PointSet
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class PointSetElement { public: int p; int size; PointSetElement() { } PointSetElement(int p_) { p = p_; size = 1; } }; // An object to manage set of points, who can be fusionned class PointSet { public: PointSet(int nb_elements_); ~PointSet(); int nb_elements; // Return the main point of the point's set int getBasePoint(int p); // Join two sets of points, based on their main point void joinPoints(int p_a, int p_b); // Return the set size of a set (based on the main point) int size(unsigned int p) { return mapping[p].size; } private: PointSetElement* mapping; };
对于PointSetElement
而言,定义了分量大小$size$以及当前像素点在最小生成树中的父指针$p$
对于PointSet
而言,有两个成员和3
个函数
nb_elements
:分量个数mapping
:点集元素指针getBasePoint(int p)
:得到元素所属分量的根节点坐标joinPoints(int p_a, int p_b)
:合并两个分量size(unsigned int p)
:返回元素p
所在分量个数1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 PointSet::PointSet(int nb_elements_) { nb_elements = nb_elements_; mapping = new PointSetElement[nb_elements]; for ( int i = 0; i < nb_elements; i++) { mapping[i] = PointSetElement(i); } } PointSet::~PointSet() { delete [] mapping; } int PointSet::getBasePoint( int p) { int base_p = p; while (base_p != mapping[base_p].p) { base_p = mapping[base_p].p; } // Save mapping for faster acces later mapping[p].p = base_p; return base_p; } void PointSet::joinPoints(int p_a, int p_b) { // Always target smaller set, to avoid redirection in getBasePoint if (mapping[p_a].size < mapping[p_b].size) swap(p_a, p_b); mapping[p_b].p = p_a; mapping[p_a].size += mapping[p_b].size; nb_elements--; }
在构造函数中,通过输入的参数nb_elements_
创建指针空间,初始化每个点集元素的父指针指向自身 函数getBasePoint
查询根节点,使用了路径压缩进行优化 函数joinPoints
合并两个分量,累加两个分量个数到根节点。与工程实现不同的是,这里比较size
大小进行合并 边 定义类Edge
保存边信息
1 2 3 4 5 6 7 8 9 10 class Edge { public: int from; int to; float weight; bool operator <(const Edge& e) const { return weight < e.weight; } };
包含两个顶点坐标以及边权重,同时重写比较函数,可作用于边集排序
图分割算法 OpenCV
定义了一个图分割算法声明类GraphSegemntation
以及一个图分割算法实现类GraphSegmentationImpl
声明 图分割算法声明类GraphSegmentation
位于segmentation.hpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class CV_EXPORTS_W GraphSegmentation : public Algorithm { public: /** @brief Segment an image and store output in dst @param src The input image. Any number of channel (1 (Eg: Gray), 3 (Eg: RGB), 4 (Eg: RGB-D)) can be provided @param dst The output segmentation. It's a CV_32SC1 Mat with the same number of cols and rows as input image, with an unique, sequential, id for each pixel. */ CV_WRAP virtual void processImage(InputArray src, OutputArray dst) = 0; CV_WRAP virtual void setSigma(double sigma) = 0; CV_WRAP virtual double getSigma() = 0; CV_WRAP virtual void setK(float k) = 0; CV_WRAP virtual float getK() = 0; CV_WRAP virtual void setMinSize(int min_size) = 0; CV_WRAP virtual int getMinSize() = 0; }; /** @brief Creates a graph based segmentor @param sigma The sigma parameter, used to smooth image @param k The k parameter of the algorythm @param min_size The minimum size of segments */ CV_EXPORTS_W Ptr<GraphSegmentation> createGraphSegmentation(double sigma=0.5, float k=300, int min_size=100);
声明了对外提供的接口,同时提供了创建图分割类对象的辅助函数createGraphSegmentation
实现 图分割算法实现类GraphSegmentationImpl
位于segmentation.hpp
,其继承了接口类GraphSegmentation
并实现了分割算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 class GraphSegmentationImpl : public GraphSegmentation { public: GraphSegmentationImpl() { sigma = 0.5; k = 300; min_size = 100; name_ = "GraphSegmentation"; } ~GraphSegmentationImpl() CV_OVERRIDE { }; virtual void processImage(InputArray src, OutputArray dst) CV_OVERRIDE; virtual void setSigma(double sigma_) CV_OVERRIDE { if (sigma_ <= 0) { sigma_ = 0.001; } sigma = sigma_; } virtual double getSigma() CV_OVERRIDE { return sigma; } virtual void setK(float k_) CV_OVERRIDE { k = k_; } virtual float getK() CV_OVERRIDE { return k; } virtual void setMinSize(int min_size_) CV_OVERRIDE { min_size = min_size_; } virtual int getMinSize() CV_OVERRIDE { return min_size; } virtual void write(FileStorage& fs) const CV_OVERRIDE { fs << "name" << name_ << "sigma" << sigma << "k" << k << "min_size" << (int)min_size; } virtual void read(const FileNode& fn) CV_OVERRIDE { CV_Assert( (String)fn["name"] == name_ ); sigma = (double)fn["sigma"]; k = (float)fn["k"]; min_size = (int)(int)fn["min_size"]; } private: double sigma; float k; int min_size; String name_; // Pre-filter the image void filter(const Mat &img, Mat &img_filtered); // Build the graph between each pixels void buildGraph(Edge **edges, int &nb_edges, const Mat &img_filtered); // Segment the graph void segmentGraph(Edge * edges, const int &nb_edges, const Mat & img_filtered, PointSet **es); // Remove areas too small void filterSmallAreas(Edge *edges, const int &nb_edges, PointSet *es); // Map the segemented graph to a Mat with uniques, sequentials ids void finalMapping(PointSet *es, Mat &output); };
public
函数包括
private
函数包括:
filter
:高斯滤波buildgraph
:创建边集segmentGraph
:Kruskal
算法得到最小生成树filterSmallAreas
:合并小分量finalMapping
:创建输出图另外createGraphSegmentation
创建了分割类对象
createGraphSegmentation 创建类对象,赋值高斯滤波参数sigma
,阈值函数参数k
,最小分量大小min_size
,最后返回对象指针
1 2 3 4 5 6 7 8 9 10 Ptr<GraphSegmentation> createGraphSegmentation(double sigma, float k, int min_size) { Ptr<GraphSegmentation> graphseg = makePtr<GraphSegmentationImpl>(); graphseg->setSigma(sigma); graphseg->setK(k); graphseg->setMinSize(min_size); return graphseg; }
filter 首先将输入图像转换成浮点类型,再调用高斯滤波函数GaussianBlur
进行处理
1 2 3 4 5 6 7 8 9 10 void GraphSegmentationImpl::filter(const Mat &img, Mat &img_filtered) { Mat img_converted; // Switch to float img.convertTo(img_converted, CV_32F); // Apply gaussian filter GaussianBlur(img_converted, img_filtered, Size(0, 0), sigma, sigma); }
输入卷积核大小为$Size(0,0)$,参考getGaussianKernel ,表示根据sigma
值计算卷积核大小
buildgraph 从左到右,从上到下的遍历像素点,计算当前顶点和上/下/左/右 顶点的边
1 2 3 4 5 for (int delta = -1; delta <= 1; delta += 2) { for (int delta_j = 0, delta_i = 1; delta_j <= 1; delta_j++ || delta_i--) { int i2 = i + delta * delta_i; int j2 = j + delta * delta_j;
i2/j2
取值为
1 2 3 4 i2 = -1 j2 = 0 i2 = 0 j2 = -1 i2 = 1 j2 = 0 i2 = 0 j2 = 1
边权重通过计算相邻像素点之间的$L2$距离获得
1 2 3 for ( int channel = 0; channel < nb_channels; channel++) { tmp_total += pow(p[j * nb_channels + channel] - p2[j2 * nb_channels + channel], 2); }
创建的边集会出现重复边的情况(对无向图而言,虽然通过属性from/to
明确了初始点和终止点 ),不过在后续操作中都会使用到
segmentGraph 通过Kruskal
算法实现分量的合并。首先进行边集排序,类Edge
重写了比较函数,所以按权值升序排序
1 std::sort(edges, edges + nb_edges);
然后创建并查集类PointSet
1 *es = new PointSet(img_filtered.cols * img_filtered.rows);
并设置阈值函数,初始时每个分量个数为1
,所以阈值大小为k
1 2 3 4 float* thresholds = new float[total_points]; for (int i = 0; i < total_points; i++) thresholds[i] = k;
遍历所有边,判断两个顶点是否位于同一分量。如果不是,判断是否满足边界条件。如果不是,合并两分量,更新阈值并设置边权重为0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 for ( int i = 0; i < nb_edges; i++) { int p_a = (*es)->getBasePoint(edges[i].from); int p_b = (*es)->getBasePoint(edges[i].to); if (p_a != p_b) { if (edges[i].weight <= thresholds[p_a] && edges[i].weight <= thresholds[p_b]) { (*es)->joinPoints(p_a, p_b); p_a = (*es)->getBasePoint(p_a); thresholds[p_a] = edges[i].weight + k / (*es)->size(p_a); edges[i].weight = 0; } } }
由于边集存在重复边的情况,所以将已使用的边权值设置为0
之后,还有另一条相同的无向边存在
filterSmallAreas 再次遍历所有边,合并小分量
1 2 3 4 5 6 7 8 9 10 11 12 void GraphSegmentationImpl::filterSmallAreas(Edge *edges, const int &nb_edges, PointSet *es) { for ( int i = 0; i < nb_edges; i++) { if (edges[i].weight > 0) { int p_a = es->getBasePoint(edges[i].from); int p_b = es->getBasePoint(edges[i].to); if (p_a != p_b && (es->size(p_a) < min_size || es->size(p_b) < min_size)) { es->joinPoints(p_a, p_b); } } } }
finalMapping 本函数作用于最后的不同分量颜色设置,输入参数为合并操作后的点集PointSet *es
以及单通道图像Mat &output
。同一分量的像素点赋值同一个值,像素值从0
开始递增
示例 实现代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 #include "opencv2/ximgproc/segmentation.hpp" #include "opencv2/highgui.hpp" #include "opencv2/core.hpp" #include "opencv2/imgproc.hpp" #include <iostream> using namespace cv; using namespace cv::ximgproc::segmentation; Scalar hsv_to_rgb(Scalar); Scalar color_mapping(int); static void help() { std::cout << std::endl << "A program demonstrating the use and capabilities of a particular graph based image" << std::endl << "segmentation algorithm described in P. Felzenszwalb, D. Huttenlocher," << std::endl << " \"Efficient Graph-Based Image Segmentation\"" << std::endl << "International Journal of Computer Vision, Vol. 59, No. 2, September 2004" << std::endl << std::endl << "Usage:" << std::endl << "./graphsegmentation_demo input_image output_image [simga=0.5] [k=300] [min_size=100]" << std::endl; } Scalar hsv_to_rgb(Scalar c) { Mat in(1, 1, CV_32FC3); Mat out(1, 1, CV_32FC3); float *p = in.ptr<float>(0); p[0] = (float) c[0] * 360.0f; p[1] = (float) c[1]; p[2] = (float) c[2]; cvtColor(in, out, COLOR_HSV2RGB); Scalar t; Vec3f p2 = out.at<Vec3f>(0, 0); t[0] = (int) (p2[0] * 255); t[1] = (int) (p2[1] * 255); t[2] = (int) (p2[2] * 255); return t; } Scalar color_mapping(int segment_id) { double base = (double) (segment_id) * 0.618033988749895 + 0.24443434; return hsv_to_rgb(Scalar(fmod(base, 1.2), 0.95, 0.80)); } int main(int argc, char **argv) { if (argc < 2 || argc > 6) { help(); return -1; } Ptr<GraphSegmentation> gs = createGraphSegmentation(); if (argc > 3) gs->setSigma(atof(argv[3])); if (argc > 4) gs->setK((float) atoi(argv[4])); if (argc > 5) gs->setMinSize(atoi(argv[5])); if (!gs) { std::cerr << "Failed to create GraphSegmentation Algorithm." << std::endl; return -2; } Mat input, output, output_image; input = imread(argv[1]); if (!input.data) { std::cerr << "Failed to load input image" << std::endl; return -3; } gs->processImage(input, output); double min, max; minMaxLoc(output, &min, &max); int nb_segs = (int) max + 1; std::cout << nb_segs << " segments" << std::endl; output_image = Mat::zeros(output.rows, output.cols, CV_8UC3); uint *p; uchar *p2; for (int i = 0; i < output.rows; i++) { p = output.ptr<uint>(i); p2 = output_image.ptr<uchar>(i); for (int j = 0; j < output.cols; j++) { Scalar color = color_mapping(p[j]); p2[j * 3] = (uchar) color[0]; p2[j * 3 + 1] = (uchar) color[1]; p2[j * 3 + 2] = (uchar) color[2]; } } imwrite(argv[2], output_image); std::cout << "Image written to " << argv[2] << std::endl; return 0; }
首先解析命令行参数,创建图像分割类对象并初始化参数
然后图像分割函数进行基于图的图像分割,输出单通道灰度图像
最后将创建3
通道图像并赋值,同一分量的像素点设置相同的值。与论文提供的实现不同,为了使得分量间的颜色更加有区别,进行HSV
颜色空间和RGB
颜色空间的转换
sigma=0.5, k=500, min_size=50
sigma=0.5, k=300, min_size=100