城上层楼叠巘

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

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跑了一下图形化,首先用中文的数据

输出了如下的打分矩阵

analysematc

用mathematica做一个GraphPlot,得到

analysec

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

analysemate

跑下来的图形是

analysee

 

对比原始数据,perfect!

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

下面是两个片段对比

 

屏幕快照 2013-09-14 上午4.07.32

屏幕快照 2013-09-14 上午4.10.00

 

 

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

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

如图

analyse

 

阕值0.6中文analyse

阕值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.     }

然后结果很漂亮

analysechine

mpeng

 

all done!

2.1.2 细匹配

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

2.2 合并

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

2.3 再输出

没什么好说的

发表评论

电子邮件地址不会被公开。 必填项已用*标注