AT678 题解

Posted on Disqus:

文章中的内容可能已经过时，仅作为测试使用。

简要题意：

  • 给你一个01矩阵，从中识别出一个表达式（0~9、+、-、*、/、(、) )并求值

  • 字符有旋转

  • 有随机噪点

1.降噪

如果不降噪会影响图片的识别效果，而且我们很容易发现噪点连成一个很大的联通块基本是不可能的，所以我们可以通过 flood-fill 求出每一个联通块，并删掉所有大小<100的联通块。

降噪前：

降噪后：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void get_num_and_clean(){
    num=now=1;
    memset(vis,0,sizeof(vis));
    for(int j=1;j<=h;j++)
    for(int k=0;k<w;k++){
      if(a[j][k]=='#'&&vis[j][k]==0){
        num=0;
          maxy[now]=maxx[now]=0;
          miny[now]=minx[now]=1e8;
        dfs(j,k);
        if(num>=100){
          fnum[now]=num;
          now++;
        }
        else{
          num=0;
          maxy[now]=maxx[now]=0;
          miny[now]=minx[now]=1e8;
          dfs(j,k,1);
        }
      }
    }
    now--;
}//统计嵌入式文本文件中‘1’像素的个数并进行降噪

2.分离字符

我们用上一步被保留的联通块，求出左上角，右下角，左下角，右上角四个点的坐标，就把字符分离了出来。

分离效果：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int x,int y,int sz=0){
  maxx[now]=max(maxx[now],x);
  minx[now]=min(minx[now],x);
  maxy[now]=max(maxy[now],y);
  miny[now]=min(miny[now],y);
  num++;
  vis[x][y]=1;
  if(sz){
    a[x][y]='.';
  }
  for(int i=0;i<=7;i++){
    int nx=x+mx[i],ny=y+my[i];
    if(nx<1||ny<0||nx>h||ny>=w||a[nx][ny]!='#'||(vis[nx][ny]&&sz==0))continue;
    dfs(nx,ny,sz);
  }
}//（我把这一步和去除噪点写在一起了）

3.识别字符

这是本文的重点。

3.1生成特征矩阵

我们把每一个字符分成 5*5 份求出每一份的像素密度，作为特征矩阵，对于给出的模版字符，做同样的操作。

这种特征矩阵的好处是什么?

  • 不被放缩影响

  • 受噪点影响小

坏处呢？

  • 受旋转影响大

样例生成的特征矩阵：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
0.314286 0.628571 0.885714 0.571429 0 
0.4 0.371429 1 0.6 0 
0 0 1 0.6 0 
0 0 1 0.6 0 
0.622222 0.666667 1 0.866667 0.666667 
（3）
0.485714 0.857143 1 0.885714 0.265306 
0.771429 0.657143 0 0.685714 0.693878 
0 0 0.3125 0.95 0.464286 
0.0285714 0.571429 0.97619 0.428571 0.387755 
0.844444 1 0.833333 0.666667 1 
（*）
0.4 0.885714 1 0.942857 0.387755 
0.35 0.525 0 0.5 0.839286 
0 0.114286 0.857143 0.971429 0.530612 
0 0 0 0.35 0.964286 
0.644444 0.822222 0.777778 0.866667 0.555556 
（3）
0 0 0.47619 0.97619 0 
0 0.452381 0.928571 1 0 
0.55 0.9375 0.458333 1 0.25 
0.571429 0.571429 0.714286 1 0.571429 
0 0.296296 0.777778 1 0.571429 
（-）
0.4 1 0.857143 0.857143 0.571429 
0.457143 1 0.238095 0.257143 0.0204082 
0.45 0.8 0.625 0.85 0.75 
0.0285714 0 0 0.228571 1 
0.622222 0.822222 0.777778 0.888889 0.507937 
（4）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void prework4(){
  for(int l=1;l<=now;l++){
    double vv=double(maxy[l]-miny[l])/KUAN;
    //cerr<<vv<<endl;
    for(int j=1;j<=KUAN;j++){
      Hs2[j]=miny[l]+vv*(j-1);
    }
    Hs2[KUAN+1]=maxy[l]+1;
    vv=double(maxx[l]-minx[l])/KUAN;
    //cerr<<vv<<endl;
    for(int j=1;j<=KUAN;j++){
      Ws2[j]=minx[l]+vv*(j-1);
    }
    Ws2[KUAN+1]=maxx[l]+1;
  for(int i=1;i<=KUAN;i++)
  for(int j=1;j<=KUAN;j++){
    double aa=0,bb=0;
    //cout<<i<<" "<<Ws[i]<<" "<<Ws[i+1]-1<<endl;
    //cout<<j<<" "<<Hs[j]<<" "<<Hs[j+1]-1<<endl;
    for(int ii=Ws2[i];ii<Ws2[i+1];ii++){
      for(int jj=Hs2[j];jj<Hs2[j+1];jj++){
        bb+=1;
        aa+=(a[ii][jj]=='#');
      }
    }
    Features2[l][i][j]=aa/bb;
    if(isnan(Features2[l][i][j])){
      Features2[l][i][j]=0;
    }
  }

  }
}

3.2匹配

我们对于每一个字符，求出它和所有模版字符相似度最大的一个即可。

怎么求相似度？

把矩阵变成向量，求向量相似度，给出两种方法：

  • 欧几里得距离（较坏）

  • 余弦相似度（较好）

代码(我用的是余弦相似度）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(int i=1;i<=now;i++){
    double minn=0;
    int id;
    for(int j=0;j<=15;j++){
      double sumarrayA=0,sumarrayB=0;
      double cosine=0;
      for(int ii=1;ii<=KUAN;ii++)
      for(int jj=1;jj<=KUAN;jj++){
        sumarrayA+=Features[j][ii][jj]*Features[j][ii][jj];
        sumarrayB+=Features2[i][ii][jj]*Features2[i][ii][jj];
        cosine+=Features2[i][ii][jj]*Features[j][ii][jj];
      }
      sumarrayA=sqrt(sumarrayA);
    sumarrayB=sqrt(sumarrayB);
    cosine/=(sumarrayA*sumarrayB);
      cout<<i<<" "<<j<<" "<<cosine<<endl;
      if(cosine>minn){
        minn=cosine;
        id=j;
      }
    }
    ...

这就结束了？

3.3其他注意事项

上边的代码只能得到100分左右（满分500分）

3.3.1:我们发现上边的代码可能把运算符识别成数字，于是我们提高矩阵精度再跑一次（5*5->7*7)，如果识别结果为运算符，则以这次的结果为准，否则以上一次的结果为准。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
...
int bfid=id;
    minn=0;
      for(int j=0;j<=15;j++){
        double sumarrayA=0,sumarrayB=0;
        double cosine=0;
        for(int ii=1;ii<=KUAN2;ii++)
        for(int jj=1;jj<=KUAN2;jj++){
          sumarrayA+=Features3[j][ii][jj]*Features3[j][ii][jj];
          sumarrayB+=Features4[i][ii][jj]*Features4[i][ii][jj];
          cosine+=Features4[i][ii][jj]*Features3[j][ii][jj];
        }
        sumarrayA=sqrt(sumarrayA);
        sumarrayB=sqrt(sumarrayB);
        cosine/=(sumarrayA*sumarrayB);
        if(cosine>minn){
          minn=cosine;
          id=j;
        }
      }


    if(ch[id]=='+'||ch[id]=='-'||ch[id]=='*'||ch[id]=='/'){
    fin_ans.push_back(ch[id]);

    }
    else
    fin_ans.push_back(ch[bfid]);
  }

3.3.2（我不会）:把所有字符手动旋转为正。

3.3.3:我的这份代码最后也没有AC（因为我在3.1提到过特征矩阵的缺点）（我太弱了QwQ)，只能得到221分。