获取外接矩形和内接矩形

我们有两种需要构造内接矩形的场景:

  • 一种是使用扫描仪做连续扫描的场景. 在这种情况下, 拼接之后的大图本身就是比较规整的矩形, 我们其实并不需要真正寻找内接矩形的操作, 只需要将外围截掉一定的大小, 就可以得到一个完美的矩形. 我们使用M*N的方式来计算左上角和右下角需要向内收缩的尺寸, M是行/列方向上的视野的个数, N一般取30个像素就绰绰有余了. 为了弥补由于截断丢失的内容, 我们只需要在扫描的时候将扫描区域外扩做一下补偿即可.

  • 另一种情况是手工操作显微镜连续拍摄的情况. 在这种情况下, 用户最终会扫出一个什么形状完全不可控, 就只能计算内接矩形了.

获取外接矩形

外接矩形十分简单, 只要计算一下boundingRect就可以得到. 没有太多需要讨论的.

获取内接矩形

下面使用的算法是一个比较直观易懂的算法, 没有进行优化.

我们构造一个和要检测的图像等尺寸的矩形leftMat, 用于保存要处理的图像中每个像素左边的非零像素的个数.
然后, 再遍历leftMat, 统计每个位置上面的每个像素, 获取能够组成的最大的矩形.

我们要处理的图像是一张相当大的图片, 我们也没有必要检查每个像素, 因此, 我们首先将原始图像缩小比例, 再进行检测. 即使是有空洞, 也也不会是很大的问题.

下面是算法的简易实现: 

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
cv::Rect ImageTool::inscribeRect(const cv::Mat &src)
{
    int src_width = src.cols;
    int src_height = src.rows;
    int MAX_SIZE = 512;
    int div = 1;

    // 要将图像缩小比例计算. 最大保留到512.
    if(src.rows>MAX_SIZE || src.cols>MAX_SIZE)
    {
        int r = floor(log(src_width)/log(2) - log(MAX_SIZE)/log(2));
        div = pow(2, r);
    }
    div = std::max(div, 8);
    int width = src.cols/div;
    int height = src.rows/div;

    cv::Mat resizeMat;
    cv::resize(src, resizeMat, cv::Size(width, height));
    cv::Mat grayMat;
    if(resizeMat.channels()>1)
    {
        cv::cvtColor(resizeMat, grayMat, cv::COLOR_BGR2GRAY);
    }
    else
    {
        grayMat = resizeMat;
    }
    cv::Mat binMat;
    // 注意, 这里必须是1!
    cv::threshold(grayMat, binMat, 0, 1, cv::THRESH_BINARY);

    // 计算binMat中每个像素左边的非0像素数, 并保存到矩阵leftMatrix中.
    cv::Mat leftMat = cv::Mat::zeros(binMat.rows, binMat.cols, CV_32SC1);
    for(int row=0; row<binMat.rows; ++row)
    {
        for(int col=0; col<binMat.cols; ++col)
        {
            if(col==0)
            {
                leftMat.at<qint32>(row, col) = binMat.at<quint8>(row, col);
            }
            else if (binMat.at<quint8>(row, col) ==0)
            {
                leftMat.at<qint32>(row, col) = 0;
            }
            else
            {
                leftMat.at<qint32>(row, col) = leftMat.at<qint32>(row, col-1) + 1;
            }
            if(leftMat.at<qint32>(row, col)>col+1){
                TRACE() << "leftmat 值异常 at: " << row << col << leftMat.at<qint32>(row, col);
            }
        }
    }
    // 遍历leftMatrix中的每个像素, 对每个像素, 检查它上面的每个像素,获取他们能
    // 组成的最大的矩形的面积. 最大的就是要求的.
    int ret_left=0, ret_top=0, ret_right=0, ret_bottom=0;
    int ret_area=0;
    for(int row=0; row<binMat.rows; ++row)
    {
        for(int col=0; col<binMat.cols; ++col)
        {
            if(binMat.at<quint8>(row, col)==0)
            {
                continue;
            }
            int width = leftMat.at<qint32>(row, col);
            int area = width;
            int max_top = row;
            int max_left = col - width + 1;
            for(int k=row-1; k>=0; k--)
            {
                width = std::min(width, leftMat.at<qint32>(k, col));
                int tmp_area = (row - k + 1) * width;
                if(tmp_area > area)
                {
                    area = tmp_area;
                    max_top = k;
                    max_left = col - width + 1;
                }
            }

            if(area > ret_area)
            {
                ret_area = area;
                ret_left = max_left;
                ret_top = max_top;
                ret_right = col;
                ret_bottom = row;
            }
        }
    }
    ret_left ++;
    ret_top ++;
    ret_right --;
    ret_bottom--;
    return cv::Rect(ret_left*div, ret_top*div, (ret_right-ret_left)*div, (ret_bottom-ret_top)*div);

}