【OJ】网易互娱2017增强现实扩招

1/300:30:52
[编程|100分] 图像模板匹配
时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 65536K，其他语言 131072K
题目描述
注意：本题只允许使用C/C++，Java或Python进行解答，其他编程语言提交均视作无效处理。

图像模版匹配是计算机视觉领域中一项非常常用的算法，他所描述的问题是根据给定的模版图像T，在源图像S中找到与T最相似的块（可能有多个）。

由于模版T在源图像S中可能是任意尺度的，因此在搜索时需要在多尺度上进行匹配。为简单起见，我们只对模版T进行下采样操作，并使用缩小后的模版图像进行匹配，模版T的尺度变化为（1,1/2,1/4,1/8。。。），模版尺寸最小不能小于1X1，下采样算法采用最近邻方法。

假定源图像S的分辨率为MM，模版图像T的分辨率为NN（N<M,且N为2的整数次幂），模版图像与源图像中的块的相似性判定为 ，其中P为源图像S中的一个像素，Q为模版图像T中的一个像素。

从图像I中找到和模版图像T（包括多个尺度的）最相似的块的所有的坐标。

输入描述:
每个输入数据包含多个测试点。所有的图像我们只考虑灰度图，即只有一个（0~255）的灰度值。 第一行为源图像的尺寸M(M<=30)。 第二行为源图像中所有像素的值（0~255的正整数）。 第三行为模版图像的原始尺寸N(N<=30)。 第四行为模版图像中所有像素的值（0~255的正整数）。
输出描述:
输出找到所有匹配的数量。 输出匹配块的大小和坐标。
示例1
输入

5
108,156,153,205,169,196,133,26,214,142,140,203,24,236,90,194,185,81,63,197,216,253,26,101,8
4
133,26,214,142,203,24,236,90,185,81,63,197,253,26,101,8
输出

2
1: 1, 1
4: 1, 1
说明

以行优先的方式输入矩阵

源图像为
108 156 153 205 169
196 133 26 214 142
140 203 24 236 90
194 185 81 63 197
216 253 26 101 8
模版图像为
133 26 214 142
203 24 236 90
185 81 63 197
253 26 101 8
模版图像进行下采样得到多个尺度的模版图像
22的图像
133 214
185 63
以及11的图像
133
分别用44（原尺寸），22和11的模版图像去源图像中寻找最佳的匹配。
可以容易看到以（1，1）点为左上角可以分别匹配到44的模版和1*1的模版。

#include<iostream>
#include<cmath>//use abs()
#include<vector>
#include<algorithm>//use sort()

using namespace std;

typedef struct ANS{
    int size;
    int x;
    int y;
    int score;
    ANS(int size_,int x_,int y_,int score_):size(size_),x(x_),y(y_),score(score_){}
}Ans;

bool compare(const Ans& a,const Ans& b)
{
    return a.score<b.score;
}

int main()
{
    while(1)
    {
        int num;
        int count=0;
        
        int m,n;
        vector<vector<int> > sdata;
        vector<vector<int> > tdata;
        vector<Ans> ans;//存放答案
        
        //-----------------------input-----------------------
        cin>>m;
        while(cin>>num)
        {
            if(count-(count/m)*m == 0)
                sdata.push_back(vector<int>(m));
            sdata[count/m][count-(count/m)*m] = num;
            //cout<<"sdata = "<<sdata[count/m][count-(count/m)*m]<<endl;
            if(cin.get()==10) break;
            count++;
        }
        
        count = 0;
        cin>>n;
        while(cin>>num)
        {
            if(count-(count/n)*n == 0)
                tdata.push_back(vector<int>(n));
            tdata[count/n][count-(count/n)*n] = num;
            //cout<<"sdata = "<<sdata[count/m][count-(count/m)*m]<<endl;
            if(cin.get()==10) break;
            count++;
        }
        
        //-----------------------begin-----------------------
        int templatesize = n;
        while (templatesize) {
            for(int i=0;i<sdata.size()-templatesize;i++)
            {
                for(int j=0;j<m-templatesize;j++)
                {
                    int sum = 0;
                    for(int k=0;k<templatesize;k++)
                        for(int l=0;l<templatesize;l++)
                            sum+=(sdata[i+k][j+l] - tdata[k][l]);
                    sum = abs(sum);
                    ans.push_back(Ans(templatesize,i,j,sum));
                }
            }
            
            templatesize/=2;//产生新的模板
        }
        
        //sort
        sort(ans.begin(),ans.end(),compare);
        
        //print answer
        int anscount =0;
        for(int i=0;i<ans.size();i++)
        {
            if(ans[0].score == ans[i].score)
                anscount++;
            else
                break;
        }
        cout<<anscount<<endl;
        for(int i=0;i<anscount;i++)
            cout<<ans[i].size<<":"<<ans[i].x<<","<<ans[i].y<<endl;
    }
}