做建模式时候写了些随手笔记

1 模型简化

这个问题说白了就是两个步骤，一个是拼，一个是认，边缘匹配太简单了我们得在下一步做文章。

2 大概思路

很简单，两大步，首先把纸条链接打分，然后把打的分做个有向图，然后开心的哈密顿回路即可。

1.     void buildedge()
2.     {
3.         edges=new double[cuts.length][cuts.length];
4.         for(int i=0;i<cuts.length;i++)
5.             for(int j=0;j<cuts.length;j++)//a right to b left
6.             {
7.                 if(i!=j)
8.                 {
9.                     edges[i][j]=appra(cuts[i],cuts[j]);
10.                 }
11.                 else
12.                 {
13.                     edges[i][j]=0;
14.                 }
15.             }
16.     }

2.1 打分

打分大致分为粗匹配和细匹配

2.1.1 粗匹配

截断的字符串在边缘有黑色像素点，我们把黑色像素点两两距离抽取为特征向量，然后用类kmp字符串匹配算法匹配，从而获得拼接图像的信息。

1.     static double appra(bmp a,bmp b)//appra a right and b left
2.     {
3.         int r=a.width–1;
4.         int h=a.height;
5.         double sameblack=0;
6.         double sumblack=0;
7.         double res=0;
8.         for(int i=0;i<h;i++)
9.         {
10.             if(a.mat01[i][r]||b.mat01[i][0])
11.             {
12.                 sumblack++;
13.                 if(a.mat01[i][r]>>b.mat01[i][0])
14.                 {
15.                     sameblack++;
16.                 }
17.                 else if(i>1)
18.                 {
19.                     if(a.mat01[i–1][r]>>b.mat01[i][0])
20.                     {
21.                         sameblack++;
22.                     }
23.                     else if(a.mat01[i][r]>>b.mat01[i–1][0])
24.                     {
25.                         sameblack++;
26.                     }
27.                 }
28.             }
29.         }
30.         if(sumblack==0)
31.             res=0;
32.         else
33.             res=sameblack/sumblack;
34.         if(res<0.3)
35.             res=0;
36.         return res;
37.     }

跑出的结果放到mathematica跑了一下图形化,首先用中文的数据

输出了如下的打分矩阵

用mathematica做一个GraphPlot，得到

再用英文的数据，得到了这个矩阵

跑下来的图形是

 

对比原始数据，perfect!

显然与我们的要求还有一定差别，观察图像.可见已经构成了几条链，下来我们观察对比了01矩阵化后的英文中文，发现了一些问题

下面是两个片段对比

 

 

 

可见这是一个不错的算法，在英文上取得了成功

其实在之前的尝试中，我们尝试过更高的阕值

如图

 

阕值0.6中文

阕值0.3英文，对于断链的情况是我们最害怕的，不过还好。几乎都有一定匹配。这也为我们一下一步坐下了基础。

因为在阕值缩放过程中出现各种图形，我们并不着重强调阕值的大小。因为完全可以把所有权值留下，做一个类似贪心的拓扑序列完全可以解决这一问题。

算法ver0.1：

边界一张连通有向图，取图中无入度的第一点，放入循环对列

循环步骤

1. 从队列尾取点，找到和他链接的权值最大的。
2. 将这个点放入队列尾。
3. 直到世界末日，停止。

代码如下

1.     int[] mkfirstsquence()//生成第一个序列
2.     {
3.         int []sequence=new int[19];
4.         boolean[] used=new boolean[19];
5.         int num=0;
6.         double max=0;
7.         for(int i=0;i<19;i++)
8.             if(indegree(i)==0)//入度为零的点作为起点
9.             {
10.                 sequence[0]=i;
11.                 used[i]=true;
12.             }
13.         while(num<19)
14.         {
15.             int k=outdegreemax(sequence[num],used);//贪心找一个权值最大的点
16.             used[k]=true;//占用之
17.             num++;
18.             if(num<19)
19.                 sequence[num]=k;
20.         }
21.         for(int i=0;i<19;i++)
22.         {
23.             System.out.println(sequence[i]);
24.         }
25.         return sequence;
26.     }

然后直接对01矩阵拼图

1.     boolean[][]output(int[]sequence)
2.     {
3.         boolean [][]res=new boolean[cuts[0].height][19*cuts[0].width];
4.         for(int j=0;j<cuts[0].height;j++)
5.             for(int i=0;i<19;i++)
6.             {
7.                 int k=sequence[i];
8.                 for(int ix=0;ix<cuts[ k ].width;ix++)
9.                 {
10.                     res[j][i*cuts[k].width+ix]=cuts[k].mat01[j][ix];
11.                 }
12.             }
13.         return res;
14.     }

然后结果很漂亮

 

all done!

2.1.2 细匹配

从粗匹配得到的图像做截断单词的ocr，把单词撇到单词库（此处需要一个靠谱的本地词库，以及在线词库），如果查有此词。加分，反之减分。

2.2 合并

匹配出来以后是一个有向图，其权值就是打分值，然后我们做一个哈密顿回路，算法的话退火吧。防止过大数据

2.3 再输出

没什么好说的