OpenCV C++记录(十四)：距离变换与基于标记的分水岭算法

距离变换算法

距离变换算法是基于二值化图像转换，得到与前景输入类似的灰度图，其基本原理是计算前景像素(255)到背景像素(0)的最小距离，背景像素值的距离仍然为0，距离变换算法能简单地在图像生成前景特征，在图像分割、特征提取中有重要作用，此处所说的距离是三种经典距离，在前面文章OpenCV C++记录(八)：Sobel、Scharr、Laplacian、Canny算子简单提过，其数学特征是：

欧氏距离(DIST_L2)：

曼哈顿距离(城市距离,DIST_L1):

棋盘距离(切比雪夫距离,DIST_C)

OpenCV实现

OpenCV提供了距离变换接口，可以计算二值图的前景和背景距离灰度分布情况：

void distanceTransform(cv::InputArray src, //输入二值化图
    cv::OutputArray dst, //输出距离 
    int distanceType, //三种类型距离
    int maskSize, //掩图大小，一般为3
    int dstType = 5 //输出类型，默认CV_32F=5，L1时可为CV_8U
)

注意，当distanceType是城市距离L1或者棋盘距离C时，该函数使用maskSize=3的效果和其他奇数值效果一致，而如果是欧氏距离，mask=5的情况下会考虑更多的像素距离，求得最小距离精度更高，但时间也更长；

示例：

cv::Mat_<uchar> m = (cv::Mat_<uchar>(5,5)<<
    255,255,255,0,255,
    255,255,255,0,255,
    255,0,255,0,255,
    255,255,255,255,255,
    255,255,255,255,255
);

cv::Mat result;
cv::distanceTransform(m, result, cv::DIST_L1, 3, CV_32F);
cout << result << endl;

结果：

[3, 2, 1, 0, 1;
2, 1, 1, 0, 1;
1, 0, 1, 0, 1;
2, 1, 2, 1, 2;
3, 2, 3, 2, 3]

对图片需要归一化后显示：

#include <iostream>
#include <opencv2/opencv.hpp>
#include <assert.h>

using namespace std;
using namespace cv;

int main(){
    Mat rawPic = imread("D:/Documents/Desktop/cards.png",0);
    cv::Mat binary;
    cv::threshold(rawPic, binary, 0, 255, cv::THRESH_BINARY | cv::THRESH_OTSU);

    cv::Mat dist;
    cv::distanceTransform(binary, dist, cv::DIST_L1, 3, CV_32F);
    cv::imshow("dist",dist);

    cv::Mat dist_norm;
    cv::normalize(dist, dist_norm, 0, 255, cv::NORM_INF, CV_32FC1);
    cv::Mat dist_8u;
    dist.convertTo(dist_8u, CV_8UC1);
    cv::imshow("dist_8u",dist_8u);

    cout<<"Done"<<endl;
    waitKey(0);
    return 0;
}

效果：距离变换

基于标记的分水岭算法

传统的分水岭算法将图像按照灰度划分成地形，灰度高的区域成为海拔高的山脊，灰度低的地方成为海拔低的山谷，然后进行漫水操作，当两片山谷的水交汇，就在交汇处建立大坝作为边界，这种边界就是图像分割的基本依据。这种算法的原理和缺点都很浅显，本质上就是根据图像的灰度极小值进行像素分割，然而图像中同一个物体对象也可能具有多个极小值，从而被错误分割成多个类别，这就是分水岭算法的过度分割(over-segmented)问题。

要解决这个问题，常见手段主要有几种：

设定阈值，当谷深超过一定的灰度高度，才采纳这个极小值；
做高斯平滑，本质上是平滑地形，去除图像噪声，减少其带来的极小值干扰；
基于标记的分水岭算法。

OpenCV提供的分水岭算法采纳了第三种做法，用户需要对图像的前景元素和背景元素进行标记，这些标记区域作为种子进行分水岭算法，从漫水的角度叙述，标记前景元素，相当于提前将某个区域全部灌水，分水岭算法就无需再对该区域进行分割；标记背景区域，就决定了开始漫水的极小值分布(种子分布)，而抑制了噪声的影响，然后再进行漫水，对前景和背景区分明显的图像有较好的分割效果。可见，分水岭算法也是一种基于灰度相似性的阈值分割问题，但引入了灰度距离、极小值等概念，其往往比普通的二值化、大津法等有更好的阈值分割效果。

从算法上而言，前景和背景像素的标记并不复杂，前景像素可以通过前述的距离变换，获取距离0像素点足够远的像素，基于这些像素做形态学的腐蚀，所得到的区域作为前景是高置信的，而对于图像背景，如果存在背景信息（例如绿幕等）可以直接标记，否则就对图像的非0像素做形态学膨胀，那么膨胀区以外的像素，就认为是背景像素，其余未标记区域由分水岭算法确定边界。习惯上，前景像素会被标记成大于0的灰度，不同的物体前景使用不同的灰度，其余未知区域均标记成像素0，对于背景像素要求并不高，有的代码将其直接无视（为像素0），有的代码将其标记成正数的前景像素。

分水岭算法的接口很简洁：

1	cv::watershed(rawPic, marker); //输入rawPic CV_8UC3彩图和CV_32SC1 marker的标记图

对于标记图主要是要使用不同的像素值来描绘每一个独立的连通域对象，使用CV_32S支持更多的轮廓输入范围；所有复杂的处理都来自如何更好地识别和标记前景轮廓，对于这个扑克分割任务，边缘检测比较重要，例子使用了Scharr算子处理。

另一个值得讨论的地方是circle(marker, Point(5, 5), 3, Scalar(255), -1)，在marker的角落标记了一个255小圆，主要作用是告诉分水岭此处的轮廓是背景轮廓，这种方法比自己实现背景检测的方法更好，因为背景检测有可能将某些不完全清晰的边缘也去除了（例如下面注释的dilate方法），导致将某些物体也算入了背景，只要标记一个小圆，分水岭会自动将该小圆所在的连通域都算作背景。

#include <iostream>
#include <opencv2/opencv.hpp>
#include <assert.h>

using namespace std;
using namespace cv;

int main(){
    Mat rawPic = imread("D:/Documents/Desktop/cards.png");

    cv::Mat gray;
    cv::cvtColor(rawPic, gray, cv::COLOR_BGR2GRAY);

    cv::Mat pic;
    cv::threshold(gray, pic, 254, 0, cv::THRESH_TOZERO_INV); //背景255像素均设置成0，其余仍为原灰度
    cv::imshow("Noback", pic);

    cv::Mat scharr1, scharr2;
    Scharr(pic, scharr1 , -1 , 0 , 1, 3);
    Scharr(pic, scharr2 , -1 , 1 , 0, 3); //计算x和y方向的边缘梯度
    //cv::Laplacian(pic, laplacian, -1, 3);
    //Canny(pic, laplacian, 50, 200, 3, false);

    Mat kernelclosed = getStructuringElement(cv::MORPH_RECT,Size(7,7)); //膨胀去除部分扑克内部黑色方块
    cv::dilate(pic, pic, kernelclosed);
    cv::morphologyEx(pic, pic, cv::MORPH_CLOSE, kernelclosed);

    pic -= scharr1; //x边缘置黑锐化
    pic -= scharr2; //y边缘置黑锐化，保留膨胀前的边缘信息

    cv::Mat binary;
    cv::threshold(pic, binary, 0, 255, cv::THRESH_BINARY | cv::THRESH_OTSU); //二值化
    cv::imshow("binary", binary);

    //腐蚀 + 距离变换查找高置信的前景像素
    cv::Mat kernel = getStructuringElement(cv::MORPH_RECT, Size(5, 5));
    cv::Mat eroded;
    cv::erode(binary, eroded, kernel);
    cv::imshow("erode", eroded); 

    cv::Mat dist;
    cv::distanceTransform(binary, dist, cv::DIST_L2, 3, CV_32F);
    cv::imshow("dist",dist);

    cv::Mat dist_norm;
    cv::normalize(dist, dist_norm, 0, 1, cv::NORM_MINMAX, CV_32FC1);
    cv::Mat dist_8u;
    dist_norm.convertTo(dist_8u, CV_8UC1);
    cv::threshold(dist_8u, dist_8u, 0.2, 255, cv::THRESH_BINARY);
    cv::imshow("dist_8u_distance",dist_8u);

    //绘制前景轮廓
    vector<vector<Point>> contours;
    findContours(dist_8u, contours, RETR_EXTERNAL, CHAIN_APPROX_SIMPLE); 

    cv::Mat marker = cv::Mat::zeros(dist_8u.size(), CV_32SC1);
    for(int i=0; i<contours.size(); i++){
        drawContours(marker, contours, i , Scalar(static_cast<int>(i+1)), -1);
    }

    //方法1：标记背景像素为255
    circle(marker, Point(5, 5), 3, Scalar(255), -1);

    //方法2：使用膨胀获取可信背景，再置为255，但是该方法存在干扰物体边缘问题
    // cv::Mat dilated;
    // kernel = getStructuringElement(cv::MORPH_RECT, Size(5, 5));
    // cv::dilate(binary, dilated, kernel);
    // cv::imshow("dilate", dilated);

    // cv::threshold(dilated, dilated, 0, 255, cv::THRESH_BINARY_INV);
    // cv::imshow("back", dilated);
    // marker.setTo(255, dilated);

    cv::Mat marker_8u;
    marker.convertTo(marker_8u, CV_8UC1, 10);
    cv::imshow("front", marker_8u); //前景像素

    //分水岭
    cv::watershed(rawPic, marker);

    //生成随机颜色，绘制不同前景轮廓
    vector<Vec3b> colors;
    for(int i=0; i<contours.size(); i++){
        int r = cv::theRNG().uniform(0, 256); 
        int g = cv::theRNG().uniform(0, 256); 
        int b = cv::theRNG().uniform(0, 256); 
        colors.push_back(Vec3b(b,g,r));
    }

    cv::Mat result = cv::Mat::zeros(rawPic.size(), CV_8UC3);
    result.setTo(0);
    for(int i=0; i<result.rows; i++){
        for(int j=0; j<result.cols; j++){
            int index = marker.at<int>(i,j);
            if(index > 0 && index <= contours.size())
                result.at<Vec3b>(i, j) = colors.at(index-1);
        }
    }
    imshow("result", result);

    cout<<"Done"<<endl;
    waitKey(0);
    return 0;
}

参考链接：