题解 AT678

swiftc

2020-02-29 10:53:49

Solution

简要题意: - 给你一个01矩阵,从中识别出一个表达式(0~9、+、-、*、/、(、) )并求值 - 字符有旋转 - 有随机噪点 ### 1.降噪 如果不降噪会影响图片的识别效果,而且我们很容易发现噪点连成一个很大的联通块基本是不可能的,所以我们可以通过 flood-fill 求出每一个联通块,并删掉所有大小<100的联通块。 降噪前: ![](https://cdn.luogu.com.cn/upload/image_hosting/qnwv2ulf.png) 降噪后: ![](https://cdn.luogu.com.cn/upload/image_hosting/er452yyj.png) 代码: ```cpp 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.分离字符 我们用上一步被保留的联通块,求出左上角,右下角,左下角,右上角四个点的坐标,就把字符分离了出来。 分离效果: ![](https://cdn.luogu.com.cn/upload/image_hosting/c9ufpdkc.png) 代码: ```cpp 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 份求出每一份的像素密度,作为特征矩阵,对于给出的模版字符,做同样的操作。 这种特征矩阵的好处是什么? - 不被放缩影响 - 受噪点影响小 坏处呢? - 受旋转影响大 样例生成的特征矩阵: ``` 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) ``` 代码: ```cpp 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匹配 我们对于每一个字符,求出它和所有模版字符相似度最大的一个即可。 怎么求相似度? 把矩阵变成向量,求向量相似度,给出两种方法: - 欧几里得距离(较坏) - 余弦相似度(较好) 代码(我用的是余弦相似度): ```cpp 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),如果识别结果为运算符,则以这次的结果为准,否则以上一次的结果为准。 代码: ```cpp ... 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分。 ![](https://cdn.luogu.com.cn/upload/image_hosting/hd6kvcmx.png) 3.3.4:源代码下载地址 : [https://jxjjxy-my.sharepoint.com/:u:/g/personal/swift_t_odmail_cn/EaclKqmVZMBBuLacEuGqdQkBZw3nmHKp79v76yZ00fitgQ?e=gSMocs](https://jxjjxy-my.sharepoint.com/:u:/g/personal/swift_t_odmail_cn/EaclKqmVZMBBuLacEuGqdQkBZw3nmHKp79v76yZ00fitgQ?e=gSMocs)