最近apply了新的算法, 并且更新在了github的主页上面
在youtube上也有效果展示链接
文章中描述的算法是以前的版本, 太长了没空改, 后面空了会更新文章. 新算法的具体实现可以直接去看代码.
这篇文章主要解决这样一个问题：
有一张倾斜了的图片（当然是在Z轴上也有倾斜，不然直接旋转得了o(╯□╰)o），如何尽量将它纠正到端正的状态。
而要解决这样一个问题，可以用到透视变换。
关于透视变换的原理，网上已经有一大推了，这里就不再做介绍了。
这篇文章的干货是：
- 对OpenCV晦涩难懂的透视变换接口的使用细节的描述;
- 基于两套自己提出的自动选择顶点进行透视变换的可以运行的 完整代码
关于干货的第1点，相信很多同学在使用OpenCV透视变换接口的时候，一定google了不少东西吧。。。
而关于干货的第2点，应该更能引起大家的共鸣吧。就像我当初想做这个的时候，信心满满地去搜了很多博客，然而发现绝大部分博客或者教程中，关于透视变换的举例无非是如下两种：
- 是把一张端正的图像进行扭曲，比如下面这样：
可以说对要做的工作毫无卵用。。。
-
把上图中变换后的图片恢复成原图。look here
可以说刚看到可以这样子的时候，大家应该是非常激动的。。。赶紧去看看代码里面用了什么方法，然后看啊看，发现仿射变换的4个关键点是手动确定的。。。又可以说毫无卵用了。。毕竟每张图片都要通过手动的方法来确定4个关键点，还是很容易让人崩溃的。。。
于是乎，我决定，自己设计一套算法，来自动确定这4个关键点的坐标。当然，由于才疏学浅，我的这套算法当然可谓是漏洞百出，权当抱砖引玉，欢迎大家提出更好的思路，一起交流~~
干货来啦~~~
OpenCV的透视变换接口
API：
void warpPerspective(InputArray src,
OutputArray dst,
InputArray M,Size dsize,
intflags=INTER_LINEAR,
int borderMode=BORDER_CONSTANT,
const Scalar&borderValue=Scalar()
)
参数含义：
InputArray src：输入的图像；
OutputArray dst：输出的图像；
InputArray M：透视变换的矩阵；
Size dsize：输出图像的大小；
int flags=INTER_LINEAR：输出图像的插值方法。
其中的透视变换矩阵还需要函数findHomography的计算来得到一个单映射矩阵。findHomography的函数接口如下：
Mat findHomography(InputArray srcPoints,
InputArray dstPoints,
int method=0,
doubleransacReprojThreshold=3,
OutputArray mask=noArray()
)
参数含义：
InputArray srcPoints：输入图像的顶点；
InputArray dstPoints：输出图像的顶点。
关于自动计算仿射变换顶点的两种算法实现
以下处理的原图如下：
基于边缘提取
在OpenCV中，表示直线的数据结构一般是Vec4i，这本身是一个vector[1]结构，包含了4个元素，分别对应直线起点和终点的横纵坐标，在工程代码里，用vector<Vec4i>来表示经过直线提取后的的直线簇：
vector<Vec4i> lines;
首先，对原图进行边缘检测，为了使边缘检测和直线提取的结果尽可能主要体现在轮廓方面，工程代码里，将Canny边缘检测的threshold1设定为一个带初值的变量，并设置最多检测出的直线条数，迭代地通过增加threshold1的值，去减少每次检测出的直线条数，通过工程代码也能体现出来：
const int maxLinesNum = 12;//最多检测出的直线条数
while (this->lines.size() >= maxLinesNum)
{
this->cannyThreshold += 2;
Canny(this->srcImage, this->midImage,this->cannyThreshold,
this->cannyThreshold * factor);
threshold(this->midImage, this->midImage, 128,255, THRESH_BINARY);
cvtColor(this->midImage, this->edgeDetect,CV_GRAY2RGB);
HoughLinesP(this->midImage, this->lines, 1,CV_PI / 180, 50, 100, 100);
}
```
可以看出，只要本次检测出的直线条数大于12条，那么就增加Canny函数的threshold1的值，使下次检测出的直线条数减少，知道第一次小于12条，才退出循环。另外，由于一些照片拍摄的情形过于复杂，有许多环境噪声的干扰不可避免，因此，算法里还加入了一个滤波器，这个滤波器可以有效地对过于贴近图像边缘的平行直线进行过滤：
lines.erase(remove_if(
lines.begin(),lines.end(),
[](Vec4i line)
{return abs(line[0] - line[2]) < 10 ||abs(line[1] - line[3]) < 10; }
),
lines.end());
通过以上步骤的处理后，就可以得到下图：
至此，左上、右上、左下、右下这四个顶点已经被包含在了紫色的线条之中，下一步的工作就是从这些紫色的线条中解析出这四个顶点。
在解析这四个点之前，还需要对这些紫色的线条进行一次处理：将所有点从这些线段中剥离出来。剥离的方法很直观：由于每条线段包含了两个点，因此点的个数最多是线段数的两倍（考虑到有的线段共用了顶点），因此新建一个用于存储所有点的vector，将他的大小初始化为lines这个vector大小的两倍：
vector<Point> points(lines.size() * 2);//各个线段的起止点，然后根据对应关系直接将直线的起始点存入
points这个vector[3]中：
for (size_t i = 0; i < lines.size(); ++i)//将Vec4i转为point
{
points[i * 2].x = linesi;
points[i * 2].y = linesi;
points[i * 2 + 1].x = linesi;
points[i * 2 + 1].y = linesi;
}
这样就完成了对各个起始点的剥离。为了提高之后计算的效率，并且合并一些由于直线提取的误差所产生的同一个点分离的情况，再对这些已经剥离了的点进行一次过滤：
vector<Point> candidates(candidate);
vector<Point> filter(candidate);
for (auto i = candidates.begin(); i !=candidates.end();)
for (auto j = filter.begin(); j != filter.end(); ++j)
{
if(abs((i).x - (j).x) < 5 &&
abs((i).y - (j).y) < 5 &&
abs((i).x - (j).x) > 0 &&
abs((i).y - (j).y) > 0
)
i= filter.erase(i);
else
++i;
}
return filter;
这次过滤是非常有必要进行的，由于直线提取的阈值不可能适用于各种情形下拍摄的照片，因此有些照片的直线提取结果中，某些看上去是一条线段，实际上是由两条甚至更多条线段合并而成，如果直接把他们剥离成点用于算法后面的计算的话，由于后面的计算时间复杂度是O(N^2)，盲目的计算会消耗非常多的时间，而这些消耗是没有必要的。这次过滤后，重合的点将被删除，而原本逻辑上是同一个点而计算后成为不同点的那些点将被合并为一个点。在经过这次过滤后，再对剩余点进行一次排序，排序的依据是这些点到（0,0）点的距离（图像处理中的（0,0）点一般是左上角的点，横坐标向右增加，纵坐标向下增加）：
sort(points.begin(), points.end(),
[](const Point& lhs, const Point& rhs)
{return lhs.x + lhs.y < rhs.x + rhs.y; }
);
经过这次处理后，points中的所有点都是有序排列了。
为了保证对左上、右上、左下、右下这四个点计算结果的精确性，我设计了两种方法来分别计算这四个点的坐标，并且在保证经过两种方法的计算后，各自的误差满足一定条件后，取两种计算结果的平均值，作为最终的计算结果。这两种方法中有部分思想是一致的：在绝大多数正常拍摄的照片中，左上、和右下这两个顶点是容易提取的。不难发现，左上这个顶点是距离原点最近的点，右下这个顶点是距离原点最远的点。在经过上述过滤和排序步骤后，我们得到过滤后的点，就可以直接从中取出左上、右下这两个点：
vector<Point> temp = this->axisSort(lines);
Point leftTop, rightDown; //左上和右下可以直接判断
leftTop.x = temp[0].x;
leftTop.y = temp[0].y;
rightDown.x = temp[temp.size() - 1].x;
rightDown.y = temp[temp.size() - 1].y;
下面分别介绍两种方法计算左下和右上这两个点的思路。
第一种思路相对简单。
具体思想是，将“右上”、“左下”定义为点簇而非具体的某个点。在除开左上和右下这两个点外的所有点中，经行两次过滤：第一次过滤可以选出右上的点簇，利用的是在剩余的点中，如果某个点的横坐标大于左上点的横坐标并且纵坐标小于右下点的纵坐标，那么将这个点归到“右上”这个点簇中，如下图所示；如果某个点的纵坐标大于左上点的纵坐标并且横坐标小于右下点的横坐标，那么将这个点归到“左下”这个点簇中，如下图所示。
工程中的代码如下:
vector<Point>rightTop(temp.size());
vector<Point>leftDown(temp.size());//左下和右上有多个点可能符合
for (auto & i : temp)[2]
if (i.x > leftTop.x&& i.y < rightDown.y)
rightTop.push_back(i);
for (auto & i : temp)
if (i.y > leftTop.y&& i.x < rightDown.x)
leftDown.push_back(i);
经过这个步骤后，就将所有满足条件的点分别归到了“左下”和“右上”这两个点簇中。那么接下来，如何从这两个点簇中选出真正的左上点和右下点呢。这就要用到一个矩形中最长的线段是对角线这个性质了。即使原图由于拍摄原因可能已经产生了畸变，但是在“左下”和“右上”这两个点簇中，能构成最长线段的点仍然是真正的右上点和左下点。于是在“左下”和“右上”这两个点簇中从容器起始位置进行遍历，不断更新最长距离和此距离对应的两个容器中的元素位置，直到这两个位置到达两个容器的末尾，就停止更新。此时记录下的元素位置所对应的点，就是真正的左下点和右上点，如工程代码所示：
int maxDistance = (rightTop[0].x - leftDown[0].x) *(rightTop[0].x - leftDown[0].x)
+ (rightTop[0].y - leftDown[0].y) *(rightTop[0].y - leftDown[0].y);
for (size_t i = 0; i < rightTop.size(); ++i)
for (size_t j = 0; j < leftDown.size(); ++j)
if (
(rightTop[i].x - leftDown[j].x) * (rightTop[i].x -leftDown[j].x)
+ (rightTop[i].y - leftDown[j].y) * (rightTop[i].y -leftDown[j].y)
> maxDistance
)
{
maxDistance = (rightTop[i].x - leftDown[j].x) * (rightTop[i].x - leftDown[j].x)
+ (rightTop[i].y - leftDown[j].y) *(rightTop[i].y - leftDown[j].y);
rightTopFlag= i;
leftDownFlag= j;
}
下面介绍第二种方法。
通常，输入图像在视觉直观上可以分成端正、向左倾斜、向右倾斜这三种状态。之所以很难通过通常的想法来确定一个图像的左下点和右上点，是因为通常的想法下，左下点应该是横坐标最小且纵坐标最大，右上点应该是横坐标最大且纵坐标最小。然而，这种判断只适用于“端正”这种状态，如下图所示。但是对于“向右倾斜”和“向左倾斜”这两种状态，这种直观的判断就失效了，如下图所示。在“向右倾斜”这种状态下，左下点实际上是横坐标最小而纵坐标却不是最小，右上点实际上是横坐标最大而纵坐标不是最小；在“向左倾斜”这种状态下，左下点实际上是纵坐标最大而横坐标却不是最小，右上点实际上是纵坐标最小而横坐标却不是最大。
如果不对图像的状态进行区分就直接计算左下点和右上点，是非常困难的。但是，如果将图片分成上述三种状态后再对左下点和右上点进行计算，那么将会容易得多。如果输入图片本身就是“端正”状态，可以对左上点和右下点进行直接判断，下面介绍在“向右倾斜”和“想做倾斜”这两种状态下，对这两个点计算的方法。
在介绍根据不同倾斜状况对两个顶点的计算方法之前，先介绍一下如何确定右上点簇和左下点簇。在图片处于端正状态下，位于右上点两侧边缘上的点就被定义为“右上点簇”，位于左下点两侧边缘上的点就被定义为“左下点簇”。在此之后，无论这张图片如何倾斜，“右上点簇”和“左下点簇”的相对位置都不会改变。
如何区分图片是“向右倾斜”还是“向左倾斜”呢？首先，按照第一种方法的思路，将除开左上点和右下点的其余所有点归类进“左下”和“右上”这两个点簇中。如果某张图片的“右上”点簇中的所有点的纵坐标都大于左上点的纵坐标，就说明这张图是“向右倾斜”；否则这张图就是“向左倾斜”。上述思路的工程代码如下：
enum imageStyle { normal, leanToRight, leanToLeft };
if (rightTop.end() == find_if(
rightTop.begin(), rightTop.end(),
[leftTop, rightTop](Point p)
{return p.y < leftTop.y; }
))//如果所有右上点的y值都 > 左上点的y值，说明图像向右倾斜
imageState = imageStyle::leanToRight;
else
imageState = imageStyle::leanToLeft;
在“向右倾斜”状态下，对“右上”点簇中的所有点按照横坐标降序排列，横坐标最大的点就是真正的右上点，如图所示；对“左下”点簇中的所有点按照横坐标升序排列，横坐标最小的点就是真正的左下点，如图所示。在“向左倾斜”状态下，对“右上”点簇中的所有点按照纵坐标升序排列，纵坐标最小的点就是真正的右上点，如图所示；对“左下”点簇中的所有点按照纵坐标降序排列，纵坐标最大的点就是真正的左下点，如图所示。
工程代码如下：
if (imageState == imageStyle::leanToRight)//向右倾斜
{
sort(rightTop.begin(), rightTop.end(),
[rightTop](Point p1, Point p2){return p1.x > p2.x; });//对所有右上点按X值排序，X最大的就是真正的右上点
rightTop.erase(remove(rightTop.begin(), rightTop.end(), Point(0, 0)), rightTop.end());
trueRightTop = rightTop[0];
sort(leftDown.begin(), leftDown.end(),
[leftDown](Point p1, Point p2){return p1.x < p2.x; });//对所有左下点按X值排序，X最小的就是真正的左下点
leftDown.erase(remove(leftDown.begin(), leftDown.end(), Point(0, 0)), leftDown.end());
trueLeftDown = leftDown[0];
}
else //向左倾斜
{
sort(rightTop.begin(), rightTop.end(),
[rightTop](Point p1, Point p2){return p1.y < p2.y; });//对所有右上点按Y值排序，Y最小的就是真正的右上点
rightTop.erase(remove(rightTop.begin(), rightTop.end(), Point(0, 0)), rightTop.end());
trueRightTop = rightTop[0];
sort(leftDown.begin(), leftDown.end(),
[leftDown](Point p1, Point p2){return p1.y > p2.y; });//对所有左下点按Y值排序，Y最大的就是真正的左下点
leftDown.erase(remove(leftDown.begin(), leftDown.end(), Point(0, 0)), leftDown.end());
trueLeftDown = leftDown[0];
}
基于轮廓提取
轮廓提取的思路和边缘提取基本相同，就是预处理中，将提边缘换成体轮廓。
当初想到基于轮廓提取是为了互相验证这两种方法的可靠性~~
就不再详述这种方法了~~~
The END
在文章的最后，当然还是要放几张效果图啦~~~
当然，还是存在一些显而易见的问题：
如果输入图像的顶点本身已经缺失过多，那我提出的两种顶点计算方法都不可能完全还原出该图本身的缺失顶点（因为该顶点已处于图像像素范围之外，无法计算）；
另外，边缘提取和轮廓提取的参数也不可能做到完全的自适应。
