文章目录
  1. 1. 简介
  2. 2. 实现思路及细节

对于使用标定板进行相机标定的流程当中,有一个非常重要的步骤是找到标定板上点的位置,以及点在世界坐标系中的对应关系。
OpenCV相机标定参考的是Zhengyou Zhang的论文“Flexible Camera Calibration By Viewing a Plane From Unknown Orientations”。
在计算标定参数前,需要计算平面标定板的点位置,以及点对应的世界坐标。
对于标定板的类型,有棋盘格标定板,对称圆点标定板,非对称圆点标定板。本文要介绍的函数findCirclesGrid就是OpenCV中处理圆点标定板的函数。

简介

1
2
3
4
//! finds circles' grid pattern of the specified size in the image
CV_EXPORTS_W bool findCirclesGrid( InputArray image, Size patternSize,
OutputArray centers, int flags=CALIB_CB_SYMMETRIC_GRID,
const Ptr<FeatureDetector> &blobDetector = new SimpleBlobDetector());

参数说明:
@image - 圆形网格标定板图片,必须是8-bit灰度或彩图。
@patternSize - 每行每列的圆点个数 ( patternSize = Size(points_per_row, points_per_colum) )。
@centers - 输出结果,已经排序好的圆点中心点(按照行排序,每行从左到右)
@flags -
CALIB_CB_SYMMETRIC_GRID - 对称圆形网格
CALIB_CB_ASYMMETRIC_GRID - 非对称圆形网格
CALIB_CB_CLUSTERING - 使用特殊算法进行网格检测。对透视畸变最稳定,但是对背景混乱更敏感。

函数使用:

1
2
3
4
5
6
7
Size patternsize(7,7); //number of centers
Mat gray = ....; //source image
vector<Point2f> centers; //this will be filled by the detected centers
bool patternfound = findCirclesGrid(gray, patternsize, centers);
drawChessboardCorners(img, patternsize, Mat(centers), patternfound);

实现思路及细节

以下源码分析使用OpenCV2.4.8版本。另外,CALIB_CB_CLUSTERING这个参数是被OpenCV禁用了,传入该参数会报错,本文不对该参数的实现细节进行介绍(该参数实现和另外两个完全不同)。

findCirclesGrid函数涉及到的源码包含:calibinit.cpp,blobdetector.cpp,circlesgrid.cpp。主要涉及到两个类:SimpleBlobDetector、CirclesGridFinder。findCirclesGrid首先先调用SimpleBlobDetector类寻找潜在圆形中心点。然后调用CirclesGridFinder类寻找网格点。

寻找圆形中心点的算法思路简单点说就是二值化+找轮廓+粒子分析的过程,由SimpleBlobDetector的成员函数detectImpl实现。

1
void SimpleBlobDetector::detectImpl(const cv::Mat& image, std::vector<cv::KeyPoint>& keypoints, const cv::Mat&) const;

在实现中,为了减少光照对二值化的影响,使用多个阈值进行二值化。对每个二值化的图片,找到所有粒子轮廓(粒子的中心点为其质心,这种计算中心点的方式可能对精度存在问题),通过粒子面积、圆度、特征矩、凹凸性、粒子颜色(黑/白)进行过滤。

对每个二值化图得到的中心点,判断其是否是同一位置的中心点,是的话就放在同一个位置,否则加入新的位置。每个位置得到的中心点个数必须>=2。然后再重新计算所有位置的点。

【注】OpenCV源码存在bug,需要删掉:

1
2
3
line 304: vector < vector<Center> > newCenters;
line 334:newCenters.push_back(vector<Center> (1, curCenters[i]));
line 338std::copy(newCenters.begin(), newCenters.end(), std::back_inserter(centers));

以上代码与335行重复。

找到中心点后需要确定网格点关系,这一步会比较复杂。在bool CirclesGridFinder::findHoles();函数中实现,网格点有两种模式,一种是对称,一种是非对称,这里只针对对称性网格分析代码实现。

findHoles源码如下:

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
bool CirclesGridFinder::findHoles()
{
switch (parameters.gridType)
{
case CirclesGridFinderParameters::SYMMETRIC_GRID:
{
vector<Point2f> vectors, filteredVectors, basis;
Graph rng(0);
computeRNG(rng, vectors);
filterOutliersByDensity(vectors, filteredVectors);
vector<Graph> basisGraphs;
findBasis(filteredVectors, basis, basisGraphs);
findMCS(basis, basisGraphs);
break;
}
case CirclesGridFinderParameters::ASYMMETRIC_GRID:
{
vector<Point2f> vectors, tmpVectors, filteredVectors, basis;
Graph rng(0);
computeRNG(rng, tmpVectors);
rng2gridGraph(rng, vectors);
filterOutliersByDensity(vectors, filteredVectors);
vector<Graph> basisGraphs;
findBasis(filteredVectors, basis, basisGraphs);
findMCS(basis, basisGraphs);
eraseUsedGraph(basisGraphs);
holes2 = holes;
holes.clear();
findMCS(basis, basisGraphs);
break;
}
default:
CV_Error(CV_StsBadArg, "Unkown pattern type");
}
return (isDetectionCorrect());
//CV_Error( 0, "Detection is not correct" );
}

先要介绍下Graph类,这个类的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Graph
{
public:
typedef std::set<size_t> Neighbors;
struct Vertex
{
Neighbors neighbors;
};
typedef std::map<size_t, Vertex> Vertices;
// 此处忽略成员函数
private:
Vertices vertices;
};

Graph里面用来存储网格点,每个网格点Vertex包含它的所有邻居网格点下标。

1
void CirclesGridFinder::computeRNG(Graph &rng, std::vector<cv::Point2f> &vectors, Mat *drawImage) const;

computeRNG用来计算点集之间的近邻关系,返回结果存储在Graph结构体中。该函数的复杂度位O(n^3),n为点集个数。判断两个点A, B是邻居点的条件是不存在第三个点C,使得|AC| < |AB| && |BC| < |AB|。
注意到还有一个输出参数:vectors。这个向量用来存储矢量AB。要注意的是A,B如果是近邻点,那么矢量AB, BA都会存储在vectors中。

计算完点的近邻关系,将得到的vectors进行过滤,

1
void CirclesGridFinder::filterOutliersByDensity(const vector<Point2f> &samples, vector<Point2f> &filteredSamples);

过滤的条件很简单,对每个向量,统计和它相近的向量个数,如果个数大于一个阈值,保留这个向量。可以想象,对于网格点,必然存在大量的相近向量。但是另外要注意的是,畸变后的网格点,相近的向量会减少,因此,这个阈值设置不能太高。

下图是测试过程中绘制的图片,左边是原图,右边图像表示点集的关系,所有边相连的点是近邻点。




computeRNG结果绘制

接着调用函数

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
void CirclesGridFinder::findBasis(const vector<Point2f> &samples, vector<Point2f> &basis, vector<Graph> &basisGraphs)
{
basis.clear();
Mat bestLabels;
TermCriteria termCriteria;
Mat centers;
const int clustersCount = 4;
// 将方向矢量聚类成4个方向(有两对方向相反)
kmeans(Mat(samples).reshape(1, 0), clustersCount, bestLabels, termCriteria, parameters.kmeansAttempts,
KMEANS_RANDOM_CENTERS, centers);
assert( centers.type() == CV_32FC1 );
// 提取基准向量
vector<int> basisIndices;
//TODO: only remove duplicate
for (int i = 0; i < clustersCount; i++)
{
int maxIdx = (fabs(centers.at<float> (i, 0)) < fabs(centers.at<float> (i, 1)));
if (centers.at<float> (i, maxIdx) > 0)
{
Point2f vec(centers.at<float> (i, 0), centers.at<float> (i, 1));
basis.push_back(vec);
basisIndices.push_back(i);
}
}
if (basis.size() != 2)
CV_Error(0, "Basis size is not 2");
if (basis[1].x > basis[0].x)
{
std::swap(basis[0], basis[1]);
std::swap(basisIndices[0], basisIndices[1]);
}
const float minBasisDif = 2;
if (norm(basis[0] - basis[1]) < minBasisDif)
CV_Error(0, "degenerate basis" );
// 对所有方向向量,提取和基准向量同类的向量
vector<vector<Point2f> > clusters(2), hulls(2);
for (int k = 0; k < (int)samples.size(); k++)
{
int label = bestLabels.at<int> (k, 0);
int idx = -1;
if (label == basisIndices[0])
idx = 0;
if (label == basisIndices[1])
idx = 1;
if (idx >= 0)
{
clusters[idx].push_back(basis[idx] + parameters.convexHullFactor * (samples[k] - basis[idx]));
}
}
// 计算两个类的向量凸包
for (size_t i = 0; i < basis.size(); i++)
{
convexHull(Mat(clusters[i]), hulls[i]);
for (size_t j = 0; j < hulls[i].size(); j++)
{
parameters.minDistanceToAddKeypoint = MAX(parameters.minDistanceToAddKeypoint, cvCeil(norm(basis[i] - hulls[i][j])));
}
}
// 对所有顶点,按照基准方向分别统计近邻关系。
basisGraphs.resize(basis.size(), Graph(keypoints.size()));
for (size_t i = 0; i < keypoints.size(); i++)
{
for (size_t j = 0; j < keypoints.size(); j++)
{
if (i == j)
continue;
Point2f vec = keypoints[i] - keypoints[j];
for (size_t k = 0; k < hulls.size(); k++)
{
if (pointPolygonTest(Mat(hulls[k]), vec, false) >= 0)
{
basisGraphs[k].addEdge(i, j);
}
}
}
}
if (basisGraphs.size() != 2)
CV_Error(0, "Number of basis graphs is not 2");
}

findBasis这个函数利用过滤完的网格向量,寻找网格的基准方向,同时构造基准方向上的点关系图。
首先用kmeans函数将向量聚类成4类(同一条边有两个方向)。提取其中的“正向”作为基准方向。这里要注意的是由于使用聚类中心作为基准方向,对透视畸变图误差较大。这个对下面要介绍的函数findMCS会有影响。
找到基准方向后,重新遍历所有顶点,构造两张图,每张图只考虑一个基准方向的近邻关系。

下图左边是聚类后的基准方向,右边是根据基准方向构造的两张图:




findBasis结果绘制

以上都是准备工作,接下来终于要开始找网格的行了:

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
void CirclesGridFinder::findMCS(const vector<Point2f> &basis, vector<Graph> &basisGraphs)
{
holes.clear();
Path longestPath;
size_t bestGraphIdx = findLongestPath(basisGraphs, longestPath);
vector<size_t> holesRow = longestPath.vertices;
while (holesRow.size() > std::max(patternSize.width, patternSize.height))
{
holesRow.pop_back();
holesRow.erase(holesRow.begin());
}
if (bestGraphIdx == 0)
{
holes.push_back(holesRow);
size_t w = holes[0].size();
size_t h = holes.size();
//parameters.minGraphConfidence = holes[0].size() * parameters.vertexGain + (holes[0].size() - 1) * parameters.edgeGain;
//parameters.minGraphConfidence = holes[0].size() * parameters.vertexGain + (holes[0].size() / 2) * parameters.edgeGain;
//parameters.minGraphConfidence = holes[0].size() * parameters.existingVertexGain + (holes[0].size() / 2) * parameters.edgeGain;
parameters.minGraphConfidence = holes[0].size() * parameters.existingVertexGain;
for (size_t i = h; i < patternSize.height; i++)
{
addHolesByGraph(basisGraphs, true, basis[1]);
}
//parameters.minGraphConfidence = holes.size() * parameters.existingVertexGain + (holes.size() / 2) * parameters.edgeGain;
parameters.minGraphConfidence = holes.size() * parameters.existingVertexGain;
for (size_t i = w; i < patternSize.width; i++)
{
addHolesByGraph(basisGraphs, false, basis[0]);
}
}
else
{
holes.resize(holesRow.size());
for (size_t i = 0; i < holesRow.size(); i++)
holes[i].push_back(holesRow[i]);
size_t w = holes[0].size();
size_t h = holes.size();
parameters.minGraphConfidence = holes.size() * parameters.existingVertexGain;
for (size_t i = w; i < patternSize.width; i++)
{
addHolesByGraph(basisGraphs, false, basis[0]);
}
parameters.minGraphConfidence = holes[0].size() * parameters.existingVertexGain;
for (size_t i = h; i < patternSize.height; i++)
{
addHolesByGraph(basisGraphs, true, basis[1]);
}
}
}

找网格行的过程稍微复杂点,先遍历两张图,调用如下函数找到最长的路径,并记录下它所在的基准图。

1
size_t CirclesGridFinder::findLongestPath(vector<Graph> &basisGraphs, Path &bestPath);

该函数使用Floyd Warshall算法求图中顶点间的最短路径长度。
将最长路径longestPath经过的点作为行,该行称为种子行。然后调用addHolesByGraph开始找行,使用“列”基准方向开始找其他行,这里只贴出部分代码进行分析:

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
void CirclesGridFinder::findCandidateLine(vector<size_t> &line, size_t seedLineIdx, bool addRow, Point2f basisVec,
vector<size_t> &seeds)
{
line.clear();
seeds.clear();
if (addRow)
{
// 通过种子行,向列基准方向寻找下一行
for (size_t i = 0; i < holes[seedLineIdx].size(); i++)
{
Point2f pt = keypoints[holes[seedLineIdx][i]] + basisVec;
addPoint(pt, line);
seeds.push_back(holes[seedLineIdx][i]);
}
}
else
{
for (size_t i = 0; i < holes.size(); i++)
{
Point2f pt = keypoints[holes[i][seedLineIdx]] + basisVec;
addPoint(pt, line);
seeds.push_back(holes[i][seedLineIdx]);
}
}
assert( line.size() == seeds.size() );
}

对行上每个点,加上“列”基准向量,得到新行的点,判断这个点是否在顶点集中(是否存在有足够接近的点),如果不在顶点集中,则把得到的新点添加到顶点集中,再把这个点加入到新行中。这里就会出现,由于基准向量存在误差,导致得到的点不在原始点集中。最后计算新行的Confidence时,如果新行中有点不在原始顶点集中,Confidence值就不达不到阈值。

找到所有的行后,需要判断是否行列满足要求。事实上,由于透视畸变的存在,不满足要求的情况还挺多。因此,OpenCV在findHoles中又做了一步操作。如果不满足要求,利用找到的点的坐标,计算图像的透视变换。将原始点集进行透视畸变校正,校正后的点集再按照上述步骤重新进行一次计算。

事实上,OpenCV的这个函数涉及很多阈值的参数,这些参数都是固定的,因此,对于很多测试图片无法正常的找到圆点中心。但是只要知道了实现原理,改起来就很容易很多了。

文章目录
  1. 1. 简介
  2. 2. 实现思路及细节