如果是给定的是数组，那么我做这个就基本没有什么意义了，想要做到的效果：
对于给定的数独照片（尽可能干净整齐），进行一系列处理，提取位置和数字信息，这中间可能要用到一系列图像处理的基本算法，数字识别时初步打算用knn来做，knn对手写体的精度一般，这里要求输入应该是打印体，这样才能保证正确率，最后通过数独求解的算法算出答案。
做这个小项目的主要目的是练手，opencv那本书早就看完了，也就写了些书上的历程，最复杂的代码也就是读了DCF的c++代码，做了一点小小的修改，还是希望多写一些代码，今天随意找了一下，有人用python写过数独求解的这个项目，源码也都给了，大体思路也给出了，参考其大体思路，我这里用c++写一下，边用边学吧。
代码放到这里:数独
环境：win10+vs2015+opencv3.4
一、预处理
对于这样一张很干净的图像，如何找到每个数字的位置，并把数字识别出来，是我们进行数独求解首先需要关注的事情。
先对图像进行一些锐化，使图像更加清晰。然后进行阈值化，因为一般是白纸黑字，阈值化的选择应该是反阈值（具体看函数）。
然后为了方便提取，消除一些连通域之间的小间隙，我们对连通域做一个膨胀操作，实验的时候发现，这个膨胀的多少也是一个比较敏感的参数，一旦膨胀过多，格子就可能和数字链接起来，我只想先把这个流程走下来，就不考虑那么多了，这个操作中我是进行了两次3*3十字形膨胀。这样就可以得到比较理想的预处理结果了，下一步在这个基础上进行数字分割。
下面结合代码说下这个过程，顺便熟悉opencv的函数。
- 图像转换为灰度，做拉普拉斯滤波，阈值化处理。
srcImg.copyTo(Img);
cvtColor(Img, Img_gray,COLOR_BGR2GRAY);
Mat kernel = (Mat_<float>(3, 3) << 0, -1, 0, -1, 5, -1, 0, -1, 0);
filter2D(Img_gray, Img_g, -1, kernel);
threshold(Img_g, Img_g, 150, 255, THRESH_BINARY_INV); //二值阈值化，这个阈值自己选,这里是反着的，因为一般是白纸黑字
这个阈值化后的图像为：
可以看到这个图像其实已经比较理想了，轮廓线比较清楚，分格线稍微有一点细，分格线的边缘还有一些小白点，为了进一步扩张线的宽度和吸收这些小白点，我们对原图进行膨胀。
- 膨胀操作
膨胀腐蚀操作是图像形态学操作最基本也是最常用的两个操作，对应的函数分别是:
void erode( InputArray src, OutputArray dst, InputArray kernel,
Point anchor = Point(-1,-1), int iterations = 1,
int borderType = BORDER_CONSTANT,
const Scalar& borderValue = morphologyDefaultBorderValue() );
void dilate( InputArray src, OutputArray dst, InputArray kernel,
Point anchor = Point(-1,-1), int iterations = 1,
int borderType = BORDER_CONSTANT,
const Scalar& borderValue = morphologyDefaultBorderValue() );
这两个函数都是支持原位操作的。这些参数的意义：
@param src input image; the number of channels can be arbitrary, but the depth should be one of
CV_8U, CV_16U, CV_16S, CV_32F or CV_64F.(输入图像)
@param dst output image of the same size and type as src\`.（输出图像，和原图大小相同）
@param kernel structuring element used for dilation; if elemenat=Mat(), a 3 x 3 rectangular
structuring element is used. Kernel can be created using getStructuringElement（膨胀核，可由getStructuringElement()这个函数得来）
@param anchor position of the anchor within the element; default value (-1, -1) means that the
anchor is at the element center. （锚点位置，默认最中心）
@param iterations number of times dilation is applied.（迭代的次数，调用函数可以进行多次迭代膨胀或腐蚀，默认是一次）
@param borderType pixel extrapolation method, see cv::BorderTypes
@param borderValue border value in case of a constant border
@sa erode, morphologyEx, getStructuringElement
（后面两个参数都是和边缘处理相关的，一般使用时不用管）
getStructuringElement这个函数可以获得不同的核形状。
Mat getStructuringElement(int shape, Size ksize, Point anchor = Point(-1,-1));
第一个参数是形状，可选三种，分辨是下面的标志位：
矩形：MORPH_RECT;
交叉形：MORPH_CORSS;
椭圆形：MORPH_ELLIPSE;
第二个是尺寸，必须是奇数，第三个是锚点位置，默认中心点。
这样的话，这里就讲的很清楚了，看膨胀后的图像:
膨胀得到的图像更加平滑。得到这样的结果我们就可以去检测轮廓了，这是最关键的一环。当然前面的处理在真实情况下肯定不会这么简单，真实的场景更加复杂，可能还涉及到仿射变换才能把图像摆正，前面的我就简化了。
- 查找轮廓及数字定位
初步的思路是对图像进行轮廓查找，然后根据轮廓之间的拓扑结构来寻找数字及其在9*9矩阵中的位置。说到轮廓的拓扑结构，就不得不说下面要用到的这个函数：
void findContours( InputOutputArray image, OutputArrayOfArrays contours,
OutputArray hierarchy, int mode,
int method, Point offset = Point());
image: 输入图像，应该是二值图像，如果不是，会被当做二值图像处理（即非零都被当做1或255）。
contours: 查找到的轮廓，应该存储在vector<vector<Point>>里，每一条封闭的轮廓中的所有点会被当做一个vector<Point>来存储。
hierarchy: 存储图像中的拓扑结构，规定如果一个轮廓被另外一个轮廓包含，则这两个轮廓称作父子轮廓，被包含者为子轮廓，存储在vector<Vec4i>中，于contours中的对应，每一条轮廓都有这样的一个拓扑信息表，由四位int型数字组成,第i个轮廓的拓扑信息为：
| 标志位 | 含义 | 不存在的话 |
|---|---|---|
| hir[][0] | 后一个轮廓编号 | -1 |
| hir[][1] | 前一个轮廓编号 | -1 |
| hir[][2] | 父轮廓编号 | -1 |
| hir[][3] | 子轮廓编号 | -1 |
mode：
取值一：CV_RETR_EXTERNAL只检测最外围轮廓，包含在外围轮廓内的内围轮廓被忽略
取值二：CV_RETR_LIST 检测所有的轮廓，包括内围、外围轮廓，但是检测到的轮廓不建立等级关
系，彼此之间独立，没有等级关系，这就意味着这个检索模式下不存在父轮廓或内嵌轮廓，
所以hierarchy向量内所有元素的第3、第4个分量都会被置为-1，具体下文会讲到
取值三：CV_RETR_CCOMP 检测所有的轮廓，但所有轮廓只建立两个等级关系，外围为顶层，若外
内的内围轮廓还包含了其他的轮廓信息，则内围内的所有轮廓均归属于顶层
取值四：CV_RETR_TREE， 检测所有轮廓，所有轮廓建立一个等级树结构。外层轮廓包含内层轮廓，内
层轮廓还可以继续包含内嵌轮廓。
method：
寻找轮廓的算法,具体有下面几种可选：
取值一：CV_CHAIN_APPROX_NONE 保存物体边界上所有连续的轮廓点到contours向量内
取值二：CV_CHAIN_APPROX_SIMPLE 仅保存轮廓的拐点信息，把所有轮廓拐点处的点保存入contours
向量内，拐点与拐点之间直线段上的信息点不予保留
取值三和四：CV_CHAIN_APPROX_TC89_L1，CV_CHAIN_APPROX_TC89_KCOS使用teh-Chinl chain近
似算法
没有什么特殊要求的话用这几种算法得到的结果都是可以接受的，我们这里选用的是SIMPLE这种。
offset：
Point偏移量，所有的轮廓信息相对于原始图像对应点的偏移量，相当于在每一个检测出的轮廓点上加
上该偏移量，并且Point还可以是负值！
这个偏移量可能是为了画出一种类似于投影那样的效果用的，一般情况用默认值0就可以了。
如何利用这些轮廓间的拓扑关系找到数字呢？
参考了别人的一些做法，采取如下策略：
首先找到最大的一个框，即拓扑结构下的0号轮廓，然后找到以0号框为父轮廓的所有二级子轮廓，理想的条件下是有9_9=81个，这就是81个框，然后再找到有数字的框，有数字的框的特点是这些框还有子轮廓，而这些子轮廓就是我们要找的数字。
核心判断代码是这一句
if (hierarchy[i][3] == 0&&hierarchy[i][2]!=-1) //父轮廓是0号轮廓的话，就是小矩形，存在子轮廓，则子轮廓是数字
81个小方框里面如果有轮廓的话，我们认为这个轮廓是数字，下面就是要定位这些数字，一种直观的方法是用最小矩形包围数字，把数字抠图抠出来，这样也便于再后面的处理中对数字进行识别，这里要用到另外一个函数：
Rect boundingRect( InputArray points );这个函数就非常简单，获得一个点集的最小包围矩形，而且是正矩形，边与坐标轴平行，不旋转，同样有旋转版本的函数可用。
这样的话如果在原图中画出，是这样的效果：
按照流程下面该做的应该是识别数字了，先把这个问题放下，做到这里的时候我发现另外一个问题，那就是这些数字如何定位，现在我是得到了26个矩形，但是这些矩形在原图中的对应位置是怎样的？这个我并不知道，而且我依靠拓扑结构选出来的这26个矩形框并没有一个拓扑关系可用，这里卡了有半个多小时。
最后我想出来一个比较暴力但是有效的方法：
通过矩形的质心在整幅图中的位置来确定这个数字到底是哪行那列的，这要求数独图像必须基本是正方形，而且边缘应该尽可能的小。
设原图宽度和高度分别是W和H，第i个矩形的质心为(x,y).
则其索引应该是：
[i,j]=[x/W*9,y/H*9];
要注意的是，做乘除之前把int型的数据转换为double，然后最后再转为int，去掉小数部分（去尾，不四舍五入）
这样，可以得到对应的位置索引和Rect信息，整合起来放到vector<pair<point,rect>>中备用。因为还没有进行数字识别，所以我把这些小矩形根据其坐标命名都保存了起来，验证结果是否正确，结果让我非常开心：
可以对照着原图检查一下，这些数字的检测是完全正确的，注意索引是从0开始的，下一步只要把这些图片对应的数字识别出来，根据其索引值放在矩阵中，就可以调用解数独的算法进行计算了。
大程序我就不放了，现在还是个测试版本的，写了很多调试用的辅助程序，放到git中，链接见最上面。
二、数字识别
数字识别的话是打算用knn，因为问题相对比较简单，而且要求准确率也比较高。
knn是最简单的一种机器学习的算法，可以用来分类也可以用来回归，opencv里有相应的API可用，用到的时候再介绍。关于knn算法详解：knn
knn优点和缺点都是比较突出的，优点就是简单有效，无需训练。缺点是准确率一般，复杂的问题往往束手无策，虽然无需训练，但是每一次分类都必须遍历所有训练样本，当训练样本比较大的时候，计算量还是很客观的。数字识别这里主要有两个任务，第一，构建训练样本，第二建立分类器进行分离，对于一般的机器学习算法来说，是有个训练的过程的，直到损失函数符合要求，才会进行预测，我们这里用的knn就可以省略掉训练这个过程，而且由于样本实在太少，交叉验证也去掉了。下面分别介绍。
-
训练样本制作
c++有一个ml模块，其中有TrainData这个类，里面介绍了其对训练数据格式的要求。
traindata
简单的使用只需要关注前三个参数。
| 参数 | 意义 |
|---|---|
| samples | matrix of samples. It should have CV_32F type. |
| layout | see ml::SampleTypes. |
| responses | matrix of responses. If the responses are scalar, they should be stored as a single row or as a single column. The matrix should have type CV_32F or CV_32S (in the former case the responses are considered as ordered by default; in the latter case - as categorical) |
SampleTypes是采样方式，行采样或者列采样，链接里有宏定义对应的名称。
其中samples和responses都是Mat型的数据，分别是样本和其对应的标签。
samples应该是CV_32F类型的数据。
这个数据格式的要求非常严格，如果格式不对，则训练数据构建就是不成功的。这一点特别注意。一定要注意数据之间的格式转换，为了识别简单和带来不必要的通道问题，最好一开始就将原图灰度化或者灰度读入，这是比较稳妥的一种方法，c++里面调试没有matlab或者Python那么简单，不要因为这些不注意的低级错误影响心情。
另外，数据格式要求一行或者一列是一个数据，所以在放入mat之前，应该reshape()成一行或者一列。Mat是支持push_back的，一行一行地放入也比较简单。
responses是样本对应的标签，应该是一个一维向量，行或列均可，格式为CV_32F or CV_32S，即32位浮点或者整型都可，我在64_release下用的int的也可以。为了保证万无一失，还是转换一下比较好。
了解了格式要求，来制作训练数据，首先先要找来图像，因为要识别的是打印体，所以我在word里直接打了0-9十个数字，变换了十种不同的字体分别截图，得到了初始的图像数据：
然后想办法把每个数字提取出来，放在一个
vector<vector<Mat>>矩阵里，最后的结果是这样：
这里为了显示方便我把它放在一个Mat里画出来了，实际上放在
vector<vector<Mat>>里就可以进行下一步制作了。
值得一提的是，opencv里自带例程里给了手写体识别的样本，就是以这样一张图片给出的，那里面是手写体，样本很多，长这样：
手写体样本
怎么得到逐个数字简单说一下思路：对于每一张图像来说，从左至右有10个数字，先阈值化，查找轮廓，没有父轮廓的轮廓就是数字的轮廓，然后查找这些轮廓的最小包围矩形，把这些矩形按照x坐标进行排序，排序之后的结果就是从0-9了，然后分别resize到20x20,放入vector<vector<Mat>>中就可以了。为此写了个函数，如果有更多的训练样本图像，还是可以加上去的，修改一些参数就可以了，除了解数独的函数，就一共只写了这一个函数，这样就导致我的主函数达到了300行，一些测试用的代码也没有去掉，有时间再封装封装吧！
void getTrainImg(vector<vector<Mat>> &TrainImgMat)
{
Mat tmp_srcImg;
Mat tmp_Img_thresh;
vector<vector<Point>> cons;
vector<Vec4i> hies;
vector<Rect> img0_9;
for (int i = 0; i < 10; i++)
{
//读入，阈值化
tmp_srcImg = imread(".\\TrainImg\\" + to_string(i) + ".jpg",0);
tmp_srcImg.copyTo(tmp_Img_thresh); //拷贝一份，阈值化是在原图上做的
threshold(tmp_Img_thresh, tmp_Img_thresh, 150, 255, CV_THRESH_BINARY_INV);
//3*3十字膨胀
auto kernel=getStructuringElement(CV_SHAPE_CROSS, Size(3, 3));
dilate(tmp_Img_thresh, tmp_Img_thresh, kernel);
//查找轮廓
findContours(tmp_Img_thresh, cons, hies, RETR_TREE, CHAIN_APPROX_SIMPLE);
//筛选没有父轮廓的轮廓为数字，并求其最小包围矩形
for (int j = 0; j < hies.size(); j++)
{
if (hies[j][3] == -1)
{
img0_9.push_back(boundingRect(cons[j]));
}
}
//排序，按照矩形包围圈的x坐标排序
sort(img0_9.begin(), img0_9.end(), [](Rect &a, Rect &b)->bool {return a.x < b.x; });
for (int k = 0; k < img0_9.size(); k++)
{
Mat img20;
resize(tmp_srcImg(img0_9[k]), img20, Size(20, 20));
TrainImgMat[i].push_back(img20);
}
//清除内存空间，下次用
cons.clear();
hies.clear();
img0_9.clear();
}
}
然后制作训练数据和标签，也比较简单：
Mat trainData;
Mat Label;
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
trainData.push_back(TrainImgMat[j][i].reshape(0,1));
//imshow(" s", TrainImgMat[j][i]);
Label.push_back(i);
}
}
imshow("das",trainData);
总共是100个数据，每个数据长度是400。Label顺便也赋值了。
到这里训练数据的准备工作就算做好了，下面是训练数据制作，一句代码就搞定了：（记得转换格式）
//转换成浮点备用
trainData.convertTo(trainData, CV_32F); //格式转化必不可少
Ptr<TrainData> tData = TrainData::create(trainData, ROW_SAMPLE, Label);
-
knn构造和求解
待检测的数据我是存放在一个Mat里了，和训练的数据一样，进行了reshape()操作。
//Numbers是vector<Mat>类型，是检测出来的数字图片
Mat TestData;
for (auto nums:Numbers)
{
TestData.push_back(nums.reshape(0, 1));
}
TestData.convertTo(TestData, CV_32F);
下面简单介绍一下KNearest这个类，详细要看这里
KNearest这个类在opencv的ml模块中，要使用的话要包含#include<opencv2\ml.hpp>,其中各种命名都包含在cv::ml这个命名空间之中。
官方的参考程序一般会直接声明成一个智能指针，然后再进行其他的操作：
成员函数：
static Ptr< KNearest > create ()
还有一些截图在这里：
| 返回类型 | 函数 | 功能 |
|---|---|---|
| virtual float | findNearest (InputArray samples, int k, OutputArray results, OutputArray neighborResponses=noArray(), OutputArray dist=noArray()) const =0 | 预测 |
| virtual int | getAlgorithmType () const =0 | 获取算法类型 |
| virtual int | getDefaultK () const =0 | 获取默认k值 |
| virtual int | getEmax () const =0 | KDtree实现的参数（不懂） |
| virtual bool | getIsClassifier () const =0 | 是否是分类器 |
| virtual void | setAlgorithmType (int val)=0 | 设置算法类型 |
| virtual void | setDefaultK (int val)=0 | 设置k值 |
| virtual void | setEmax (int val)=0 | 设置KDtree实现的参数 |
| virtual void | setIsClassifier (bool val)=0 | 设置做分类还是回归 |
还有两个继承来的常用的函数：
一个训练一个预测，其中训练的函数是重载过的。可以现场构造训练数据，也可以用
Prt<TrainData>.预测的话
samples是带预测数据，可以是一行，返回值就是一个float，我的程序中用的就是这个。还要介绍一下最上面的一个函数：
findNearest (InputArray samples, int k, OutputArray results, OutputArrayneighborResponses=noArray(), OutputArray dist=noArray()) const =0
这个函数有三个参数，一个是数据，一个是k值，一个是响应值，可以批量计算，得到的结果储存在一个Mat里，这里的k可以设置的和creat()时不同。
把我用到knn的时候的代码放到这里便于理解这些函数的用法，我也是参考的官方程序和一些博客的写法，一个典型的knn的初始化，训练和测试应该是这样的：
//---------【knn分类器设置，k=3,分类打开】-----------------
Ptr<TrainData> tData = TrainData::create(trainData, ROW_SAMPLE, Label); //
Ptr<ml::KNearest> knn = ml::KNearest::create();
knn->setDefaultK(4);
knn->setIsClassifier(true);
knn->train(tData);
//---【检测方法1】--------
/*Mat predictRes;
knn->findNearest(TestData, 4, predictRes);
cout << predictRes;*/
//----【检测方法2】-----------------
vector<int> PredicrRes;
for (int i = 0; i < TestData.rows; i++)
{
Mat tmp = TestData.row(i);
int response = knn->predict(tmp);
PredicrRes.push_back(response);
//cout << response <<"\t"<<i<< endl;
}
这里就检测的部分就完成了，结合上面存储的这些数字在图像中的位置，我们把检测到的数据打印上去可以看一下是否正确：
这里k取的4，这里k的取值还是挺敏感的，因为训练样本确实太少。而数独的特殊性也要求不能有检测错误，一旦检测错误数独可能就无解。
三.数独求解及结果显示。
-
数独求解
首先根据上面的检测结果来重构数独矩阵,这就比较简单了，因为在第一部分我们已经获得了所有的位置，只需要把一个全零矩阵的对应位置写上数字就可以了：
vector<vector<int>> ShuDuMat(9,vector<int>());
//全零矩阵
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
ShuDuMat[i].push_back(0);
}
}
//对应位置赋值
for (int i = 0; i < PredicrRes.size(); i++)
{
ShuDuMat[PosOfNum[i].y][PosOfNum[i].x] = PredicrRes[i];
}
重构的矩阵：
然后就是矩阵求解了，这个网上的程序很多，用的是所谓的回溯法，重点不在这里我也没细看，可以参考这里,我就是复制的这个网页的代码，加了个矩阵的接口。
求解的结果（顺便检测了一下）：
-
结果显示
按理说到上面就可以结束了，不过还是想把结果显示到原图上，这样才完整一些，现在数字有了，图也有，唯一的一个困难就是原图上81个方框的位置，在第一步检测的时候我们是把81个轮廓检测出来了，但是这些轮廓在存储的时候并没有按照一个空间的顺序，所以有必要解决这个问题：
最后的方法：
①求出81个轮廓的最小包围矩形。
②81个矩形按照y坐标进行排序，这样从第一个开始，每九个应该是一行。
③81个矩形分别存储到一个vector<Rect>中，这样的话每一个应该对应的是一行。整体放入vector<vector<Rect>>中
④对③得到的个矩阵中的每一行vector<Rect>按照x坐标进行排序，这样就对应原图中从左至右。
⑤根据上面得到vector<vector<Rect>>和得到的数独结果，显示在原图上。
//---------【获得81个矩形对应的位置，矩阵的位置和原图位置对应】----------
vector<Rect> Pos;
for (int i = 0; i < hierarchy.size(); i++)
{
Rect tmp;
if (hierarchy[i][3] == 0)
{
Pos.push_back(boundingRect(contours[i]));
}
}
//按照y来排序，一排一排都链在一起
sort(Pos.begin(), Pos.end(), [](Rect &a, Rect &b)->bool{return a.y < b.y; });
cout << "小矩形的个数是" << Pos.size() << endl;
vector<vector<Rect>> PosMat(9,vector<Rect>());
int index = 0;
for (int i = 0; i < 81; i+=9)
{
PosMat[index++].assign(Pos.begin() + i, Pos.begin() + i + 9); //赋值每一行
}
for (int i=0;i<9;i++)
{
sort(PosMat[i].begin(), PosMat[i].end(), [](Rect &a, Rect &b)->bool {return a.x < b.x; }); //每一行按照x排列
cout << PosMat[i].size() << endl;
}
//把数字写到图上
Mat ResultImg;
cvtColor(srcImg, ResultImg, CV_GRAY2BGR);
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
string text = to_string(res[i][j]);
putText(ResultImg, text, Point(PosMat[i][j].x, PosMat[i][j].y+15), FONT_ITALIC, 1, Scalar(0, 0, 255), 2);
}
}
imshow("最终求解结果", ResultImg);
最终的结果：
四、总结
总共花了大概三个晚上的时间，包括写这个笔记，总算把数独求解的这个流程走下来了，其中还是遇到了一些困难的，卡的最久的地方是TrainData这个格式不对构造不成功，最后还是看着官方的例程找到了问题。写完这个感觉学到了很多，比如轮廓查找的这个函数，比如knn的这个API。
这还是一个非常脆弱的版本，主要有三地方：
①数字提取，因为用的是找轮廓的方法，目前也只能针对于比较规整清晰的图像进行处理。
②knn的样本太少，一共才100个，主要还是着急看最后的结果，手动做训练数据还是挺费事的。
③程序略乱，主要还是因为着急看结果，做一步检查一步，基本所有的代码都写在主函数里了，不过注释的还算比较清楚。还有些辅助的调试输出代码我也保留了，反正是自己做着玩的。
再接再厉吧！
