原文转自：http://www.myexception.cn/operating-system/1268723.html
相关性搜索
void MarkerDetector::findMarkerCandidates( const ContoursVector& contours, std::vector<Marker>& detectedMarkers)
{
PointsVector approxCurve;//相似形状
std::vector<Marker> possibleMarkers;//可能的标记
//分析每个标记，如果是一个类似标记的平行六面体...
for (size_t i = 0; i < contours.size(); i++)
{
//近似一个多边形
double eps = contours[i].size() * 0.05;
//使多边形边缘平滑，得到近似的多边形
cv::approxPolyDP(contours[i], approxCurve, eps, true);
//这里只考虑四边形
if (approxCurve.size() != 4) continue;
//而且必须是凸面的
if (!cv::isContourConvex(approxCurve)) continue;
//确保相邻的两点间的距离“足够大”－大到是一条边而不是短线段就是了
float minDist = std::numeric_limits<float>::max();
for (int i = 0; i < 4; i++)
{
cv::Point side = approxCurve[i] - approxCurve[(i + 1)% 4] ;
float squaredSideLength = side.dot(side);
//取最小值
minDist = std::min(minDist, squaredSideLength);
}
//确保距离不要太短
if (minDist < m_minContourLengthAllowed) continue;
//保存相似的标记
Marker m;
for (int i = 0; i < 4; i ++)
{
m.points.push_back(cv::Point2f(approxCurve[i].x,approxCurve[i].y));
}
//逆时针排列这些点
//第一个点和第二个点之间连一条线
//如果第三个点在右边，那么这些点就是逆时针-？？？
cv::Point v1 = m.points[1] - m.points[0];
cv::Point v2 = m.points[2] - m.points[0];
double o = (v1.x * v2.y) - (v1.y * v2.x);
if (o < 0.0)//如果第三个点在左边，那么需要把点排列成逆时针
{
//http://blog.csdn.net/dizuo/article/details/6435847
//交换两点的位置
std::swap(m.points[1], m.points[3]);
}
possibleMarkers.push_back(m);
}
//移除角落太接近的元素
//第一次检测相似性
std::vector<std::pair<int, int>> tooNearCandidates;
for (size_t i = 0; i < possibleMarkers.size(); i ++)
{
const Marker& m1 = possibleMarkers[i];
//计算每个边角到其他可能标记的最近边角的平均距离
for (size_t j = i + 1; j < possibleMarkers.size(); j ++)
{
const Marker& m2 = possibleMarkers[j];
float distSquared = 0.0;
for (int c = 0; c < 4; c ++)
{
cv::Point v = m1.points[c] - m2.points[c];
//向量的点乘－》两点的距离
distSquared += v.dot(v);
}
distSquared /= 4;
if (distSquared < 100)
{
tooNearCandidates.push_back(std::pair<int, int>(i,j));
}
}
}
std::vector<bool> removalMask (possibleMarkers.size(),false);
for (size_t i = 0; i < tooNearCandidates.size(); i ++)
{ //周长
float p1 = perimeter(possibleMarkers[tooNearCandidates[i].first].points);
float p2 = perimeter(possibleMarkers[tooNearCandidates[i].second].points);
size_t removalIndex;
if (p1>p2)
{
removalIndex = tooNearCandidates[i].second;
}else
{
removalIndex = tooNearCandidates[i].first;
}
removalMask[removalIndex] = true;
}
//返回可能的对象
detectedMarkers.clear();
for (size_t i = 0; i < possibleMarkers.size(); i++)
{
if (!removalMask[i])
{
detectedMarkers.push_back(possibleMarkers[i]);
}
}
}
上面方法我们已经获取到了一系列的可疑标记，为了进一步确认它们是不是我们想要的标记，还需要以下三步：
1.去掉透视投影，得到平面／正面的矩形。
2.使用Otsu算法进行图像的阀值运算。
3.最后是标记的识别编码。
为了得到这些矩形的标记图像，我们不得不使用透视变换去恢复(unwarp)输入的图像。这个矩阵应该使用cv::getPerspectiveTransform函数，它首先根据四个对应的点找到透视变换，第一个参数是标记的坐标，第二个是正方形标记图像的坐标。估算的变换将会把标记转换成方形，从而方便我们分析。
//分析每一个捕获到的标记
Marker& marker = detectedMarkers[i];
// 找到透视投影，并把标记转换成矩形
//输入图像四边形顶点坐标
//输出图像的相应的四边形顶点坐标
cv::Mat markerTransform = cv::getPerspectiveTransform(marker.points, m_markerCorners2d);
// Transform image to get a canonical marker image
//输入的图像
//输出的图像
//3x3变换矩阵
cv::warpPerspective(grayscale, canonicalMarkerImage, markerTransform, markerSize);
图像转换成正视图：
现在测试我们的标记是否是有效的。
使用Otsu算法移除灰色的像素，只留下黑色和白色像素。
//这是固定阀值方法
//输入图像image必须为一个2值单通道图像
//检测的轮廓数组，每一个轮廓用一个point类型的vector表示
//阀值
//max_value 使用 CV_THRESH_BINARY 和 CV_THRESH_BINARY_INV 的最大值
//type
cv::threshold(grey, grey, 125, 255, cv::THRESH_BINARY | cv::THRESH_OTSU);
标记编码识别
我们（作者）所使用的标记都有一个内部的5x5编码，采用的是简单修改的汉明码。简单的说，就是5bits中只有2bits被使用，其他三位都是错误的识别码，也就是说我们至多有1024种不同的标识。
我们的汉明码最大的不同是，汉明码的第一位（奇偶校验位的3和5)是反向的。所有ID 0(在汉明码是00000)，在这里是10000，目的是减少环境造成的影响（？）。
然后我们根据标记计算每个5x5区域的黑色和白色像素的个数。
识别标记编码
//存储判断结构的矩阵
cv::Mat bitMatrix = cv::Mat::zeros(5,5,CV_8UC1);
//判断每个5x5区域，是白色像素还是黑色像素
for (int y=0;y<5;y++)
{
for (int x=0;x<5;x++)
{
int cellX = (x+1)*cellSize;
int cellY = (y+1)*cellSize;
//创建grey不同尺寸的图像
/*与以下等价
cv::Rect rect(cellX,cellY,cellSize,cellSize);
cv::Mat cell = grey(rect);
*/
cv::Mat cell = grey(cv::Rect(cellX,cellY,cellSize,cellSize));
//计算非0像素的个数
int nZ = cv::countNonZero(cell);
if (nZ> (cellSize*cellSize) /2)
bitMatrix.at<uchar>(y,x) = 1;
}
}
根据相机角度，有下列四种标记可能的形状：
我们已经有了四种可能的标记图片，我们不得不找出正确形态的标记。前面我们已经知道了每2bits的3个奇偶校验位（每5bits中只有2bits有效，其余3个只是为了校验存在）。正确的标记应该有0汉明距离误差！
//检查所有可能的位置
cv::Mat rotations[4];
int distances[4];
rotations[0] = bitMatrix;
//汉明距离
distances[0] = hammDistMarker(rotations[0]);
std::pair<int,int> minDist(distances[0],0);
for (int i=1; i<4; i++)
{
//找到最小的汉明距离
rotations[i] = rotate(rotations[i-1]);
distances[i] = hammDistMarker(rotations[i]);
if (distances[i] < minDist.first)
{
minDist.first = distances[i];
minDist.second = i;
}
}
以上代码找到的最小汉明距离应该是0，如果不是，则是一个错误的标记模式－遇到损坏的标记或者假阳性标记检测（false-positive marker detection）。
－汉明距离：
在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的字符不同的个数。换句话说，它就是将 一个字符串变换成另外一个字符串所需要替换的字符个数。
变换位置：
cv::Mat Marker::rotate(cv::Mat in)
{
cv::Mat out;
in.copyTo(out);
for (int i=0;i<in.rows;i++)
{
for (int j=0;j<in.cols;j++)
{
out.at<uchar>(i,j)=in.at<uchar>(in.cols-j-1,i);
}
}
return out;
}