燕大學(xué)子謹(jǐn)慎參考

兩周后更新我自己寫的

7-1 ISBN號任務(wù)識別工作計劃 (20 分)

在對一幅ISBN圖像進(jìn)行識別時，我們需要將任務(wù)進(jìn)行分解，即分為輸入圖像、灰度化處理、去噪處理、二值化處理、字符分割處理、字符識別處理等步驟，但有些步驟必須在前一步驟完成的基礎(chǔ)上實(shí)現(xiàn)，因此我們需要計劃好各步驟完成的順序。我們?yōu)槊考蝿?wù)賦予一編號，并給出一件任務(wù)及其之前發(fā)生的任務(wù)，但由于其排序通常是不唯一的，故我們規(guī)定，同等情況下，編號小的任務(wù)在前?，F(xiàn)給定一些任務(wù)編號，請你將其按正確的順序輸出任務(wù)步驟。（假設(shè)頂點(diǎn)邊數(shù)的輸入均合法）

輸入格式:
輸入在第一行給出N個頂點(diǎn)和M條邊（N<100,M<100）；隨后M行給出每個編號及出現(xiàn)在其后的任務(wù)編號。

輸出格式:
在一行中輸出N個頂點(diǎn)的正確順序，其間以空格分隔。

輸入樣例:

5 5 
1 2
1 3
2 4 
3 4    
4 5

輸出樣例:
在這里給出相應(yīng)的輸出。例如：

1 2 3 4 5

代碼

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

int main()
{
int n, m;
cin >> n >> m;
int tmp[m][2];
    set<int> st;
for (int i = 0; i < m; i++)
{
cin >> tmp[i][0] >> tmp[i][1];
        st.insert(tmp[i][0]);
        st.insert(tmp[i][1]);
}
    for(std::set<int>::iterator it=st.begin(); it!=st.end(); ++it)
    {
        cout <<*it << " ";
    }

return 0;
}

7-2 讀取包含ISBN號的圖像文件的內(nèi)容 (20 分)

圖像文件在計算機(jī)中存儲的都是每一個像素對應(yīng)的顏色值，由RGB三通道顏色空間合成，通俗來講就是將三個分別只有R(red),G(green),B(blue)的矩陣疊加而成，基于此原理，請將包含ISBN號的圖像文件內(nèi)容以三維矩陣的形式展示出來。

輸入格式:
每個測試輸入包含一個測試用例，第一行給出矩陣的行數(shù)m和列數(shù)n，以空格隔開，以下分別輸入包含R、G、B三個顏色值的m行n列矩陣，顏色行值之間以空格隔開，矩陣之間以空行相隔。

輸出格式:
對每個測試用例第一行輸出矩陣的行數(shù)m和列數(shù)n，以空格隔開，下面分別輸出讀取到的RGB三通道顏色空間的矩陣，顏色行值之間以空格隔開，矩陣之間以空行相隔，末尾有一個空格。

輸入樣例:

3 3
7 7 8
2 6 9
1 3 5

10 12 14
16 17 19 
15 20 11

200 219 207
221 230 218
243 231 229

輸出樣例:
在這里給出相應(yīng)的輸出。例如：

3 3
7 7 8 
2 6 9 
1 3 5 

10 12 14 
16 17 19 
15 20 11 

200 219 207 
221 230 218 
243 231 229 

代碼

#include <iostream>

using namespace std;

int main()
{
    int m,n;
    cin>>m>>n;
    int rgb[3][m][n];
    for(int i=0;i<3;++i)
    {
        for (int j = 0; j < m; ++j)
            for (int k = 0; k < n; ++k)
                cin>>rgb[i][j][k];
        getchar();
    }
    cout<<m<<" "<<n<<endl;
    for(int i=0;i<3;++i)
    {
        for (int j = 0; j < m; ++j)
        {
            for (int k = 0; k < n; ++k)
                cout<<rgb[i][j][k]<<" ";
            cout<<endl;
        }
        if(i<2)
            cout<<endl;
    }
}
  
 
 

7-3 將24真彩色圖轉(zhuǎn)換為灰度圖像 (20 分)

在自然界中，顏色本身非常容易受到光照的影響，RGB變化很大。因此，在進(jìn)行圖像處理之前，至關(guān)重要的一步就是將圖像轉(zhuǎn)化為灰度圖。對于彩色轉(zhuǎn)灰度，有一個很著名的心理學(xué)公式：Gray = R * 0.299 + G * 0.587 + B * 0.114。對于一張圖像，我們會得到3個N行M列的矩陣分別表示R、G、B的像素值（RGB對應(yīng)的范圍均為0~255），我們需要將相應(yīng)的每一組像素值代入以上公式，計算出相應(yīng)的灰度值?，F(xiàn)給出一幅圖像R、G、B的像素值，請計算出它的灰度圖。

輸入格式:
每個輸入包含一個測試用例，第一行輸入正整數(shù)N（N<100）和M（M<100），中間以空格隔開。接下來3*N行依次輸入R的像素值矩陣、G的像素值矩陣、B的像素值矩陣。每個像素值間以空格隔開，每兩個矩陣無間隔（RGB取值均為0~255）。

輸出格式:
在N行M列中輸出計算得到的灰度圖像素值。像素值間以空格隔開，末尾無多余空格。

輸入樣例:

3 3
3 6 8
4 8 6
3 9 5
1 4 8
5 2 8
2 5 9
2 5 7
7 5 2
3 9 6

輸出樣例:

1 4 7
4 4 6
2 6 7

代碼

#include <iostream>

using namespace std;

int main()
{
    int m,n;
    cin>>n>>m;
    int rgb[3][n][m],gray[n][m];

    for(int i=0;i<3;++i)
    {
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < m; ++k)
                cin>>rgb[i][j][k];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            gray[i][j] = (299 * rgb[0][i][j] + 587 * rgb[1][i][j] + 114 * rgb[2][i][j]) / 1000;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if(j==m-1)
            cout<<gray[i][j];
            else
            cout << gray[i][j] <<" ";
        }
        cout << endl;
    }
          
}
  
 

7-4 做出灰度圖的灰度直方圖 (20 分)

圖像的灰度直方圖是反映一幅圖片中各灰度級像素出現(xiàn)的頻率與灰度級之間的關(guān)系，也就是說，把這幅圖片中每一個像素出現(xiàn)的次數(shù)統(tǒng)計出來。請根據(jù)給出的灰度值矩陣統(tǒng)計出此圖的灰度直方圖，即統(tǒng)計每一個灰度值出現(xiàn)的頻數(shù)。

輸入格式:
每個測試包含一個測試樣例，第一行給出矩陣的行數(shù)m和列數(shù)n，以空格隔開，以下輸入一個灰度值矩陣，灰度行值之間以空格隔開，灰度值取值范圍為0-255。

輸出格式:
對每個測試用例中的每一個灰度值，以 灰度值v:出現(xiàn)頻數(shù)t 的格式在一行中輸出該灰度值v及其在矩陣中出現(xiàn)的次數(shù)t。要求按灰度值的升序輸出,末尾無多余空格。

輸入樣例:

4 5
1 3 7 9 12 
4 4 8 10 12
4 3 8 9 10
1 4 10 12 8

輸出樣例:
在這里給出相應(yīng)的輸出。例如：

1:2
3:2
4:4
7:1
8:3
9:2
10:3
12:3

代碼

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

int main()
{
    int m,n;
    cin>>n>>m;
    int tmp;
    int arr[256];
    memset(arr,0,sizeof(arr));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
        {
            cin>>tmp;
            arr[tmp]++;
        }
   for (int i = 0; i < 256; ++i)
   {
        if (arr[i]==0)
            continue;
        cout<<i<<":"<<arr[i]<<endl;
   }

}
  
 

7-5 找最小的值做圖像分割 (20 分)

對ISBN號圖像進(jìn)行一系列處理之后，我們要將圖像中的ISBN號與背景分離開來，以便于下一步對ISBN號進(jìn)行分割的處理。對一幅圖像進(jìn)行分割，是利用圖像要提取的目標(biāo)與背景在灰度上的差異，通過設(shè)置閾值來將像素級分成若干類，從而實(shí)現(xiàn)目標(biāo)與背景分離?，F(xiàn)給定N個灰度級的頻數(shù)，請你找出灰度級頻數(shù)最小的值。

輸入格式:
輸入在第一行給出N（0-255）個灰度級；隨后一行輸入N個灰度級對應(yīng)的頻數(shù)（頻數(shù)小于256）。

輸出格式:
在一行中輸出灰度級頻數(shù)最小的值。

輸入樣例:

6
3 5 8 6 7 2

輸出樣例:

2

代碼

#include<stdio.h>
#include<iostream>
#include<set>

using namespace std;

int main()
{
int n,tmp;
cin >> n ;
    set<int> st;
for (int i = 0; i < n; i++)
{
cin >> tmp;
        st.insert(tmp);
}

    cout << *st.begin();


return 0;
}

7-6 標(biāo)識每一個數(shù)字圖元區(qū)域 (20 分)

給出一幅二值圖圖片，即圖像的亮度值只有兩個狀態(tài)：0和1，接下來就可以進(jìn)行連通區(qū)域的分析了，也就是說它通過對白色像素（目標(biāo)）的標(biāo)記，讓每個單獨(dú)的點(diǎn)形成一個被標(biāo)識的連通區(qū)域，在此過程中，常見的尋找連通區(qū)域的方法為4鄰域和8鄰域，4鄰域包含上下左右四個點(diǎn)，8鄰域包含上下左右及對角線總共八個頂點(diǎn)，若頂點(diǎn)的圖像亮度值相同，認(rèn)為它們可以形成一個區(qū)域，標(biāo)注為同一個數(shù)字，以此類推，找到所有的圖元區(qū)域。（注：本題采用8鄰域方法）

輸入格式:
每一個測試包含一個測試用例，第一行給出矩陣的行數(shù)m和列數(shù)n，以空格隔開，以下輸入一個二值矩陣，使用0和1標(biāo)注,矩陣行值之間以空格隔開。

輸出格式:
對每個測試用例的二值矩陣找出的連通區(qū)域以數(shù)字標(biāo)注，其中標(biāo)注數(shù)字從1開始，每次加1，以此類推，最后輸出標(biāo)注完成的矩陣，即包含數(shù)字圖元區(qū)域的結(jié)果，矩陣行值之間以空格隔開，末尾無多余空格。

輸入樣例:

4 6
0 1 1 0 0 1
1 1 1 0 1 1
0 0 0 0 1 1
1 1 1 0 0 1

輸出樣例:

0 1 1 0 0 2
1 1 1 0 2 2
0 0 0 0 2 2
3 3 3 0 0 2

代碼

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

int m, n;
int dir[8][2] = { 0,1,
0,-1,
-1,0,
1,0 ,
1,1,
-1,-1,
-1,1,
1,-1 };  // 方向
int gra[1000][1000];
bool vis[1000][1000];

int num = 1;
int temp = 0;
void dfs(int x, int y, int cnt)
{
for (int i = 0; i < 8; ++i)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];

if (xx < 0 || yy < 0 || xx > m || yy > n)
{
// 出界了就進(jìn)行下一個
continue;
}
if (!vis[xx][yy] && gra[xx][yy] == 1)
{
vis[xx][yy] = 1;
gra[xx][yy] = cnt;
temp++;
dfs(xx, yy, cnt);
}
}

return;
}

int main()
{
cin >> m >> n;
memset(gra, 0, sizeof(gra));
memset(vis, 0, sizeof(vis));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
{
cin >> gra[i][j];
}


for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
{
if (gra[i][j] == 1 && !vis[i][j])
{
vis[i][j] = 1;
gra[i][j] = num;
dfs(i, j, num);
if (temp > 0)
{
num++;
temp = 0;
}
}
}

for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
cout << gra[i][j] << " ";
}
cout << endl;
}
}

7-7 提取每一個數(shù)字的最小平行外接矩陣 (20 分)

在對ISBN圖像進(jìn)行識別時，通過對ISBN序列進(jìn)行垂直投影，即對ISBN字符區(qū)域進(jìn)行從左到右的掃描，依次檢測每一個坐標(biāo)的投影數(shù)值，當(dāng)我們發(fā)現(xiàn)像素值為1的點(diǎn)時，我們就認(rèn)為找到一個字符的左邊界，繼續(xù)向右掃描到最后一個像素值為1的點(diǎn)時，我們就認(rèn)為找到了一個字符的左邊界。對每一個垂直投影得到的字符區(qū)域，我們再進(jìn)行水平投影，得到一個最小的外接矩形區(qū)域?，F(xiàn)給出一個數(shù)字的二值矩陣（用0、1表示），請你找出其最小外接矩形。

輸入格式:
輸入一個數(shù)字的二值矩陣的行數(shù)M和列數(shù)N；隨后輸入一個M行、N列的二值矩陣（只包含0、1），每個數(shù)字之間一個空格。

輸出格式:
輸出這個數(shù)字外接矩形的左上點(diǎn)坐標(biāo)和右下點(diǎn)坐標(biāo)，每個坐標(biāo)用半角括號（<>）括起來，兩個括號之間無空格，每個坐標(biāo)之間一個空格。

輸入樣例:

8 9
1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 1 1 0 
0 0 0 0 0 1 1 0 0 
0 0 0 0 1 1 0 0 0 
0 0 0 1 1 0 0 0 0 
0 0 1 1 0 0 0 0 0 
0 1 1 0 0 0 0 0 0 
1 1 0 0 0 0 0 0 0 

輸出樣例:

<0 0><7 8>

代碼

#include <iostream>
#include<vector>
using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    int a,b,c,d;
    a=b=0x3f,c=d=-0x3f;
    int gra[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> gra[i][j];
    for(int i=0;i<m;i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (gra[i][j] == 1)
            {
                if (i < a)
                    a = i;
                if (j < b)
                    b = j;
                if (i > c)
                    c = i;
                if (j > d)
                    d = j;
            }
        }
    }
    cout << "<" << a << " " << b << ">" << "<" << c << " " << d << ">";
}

7-8 數(shù)字圖像尺度歸一化 (20 分)

在圖像處理過程中，有時需要把圖像調(diào)整到同樣大小，因此需要把各個圖像調(diào)整為同樣大小。這里我們給出一種簡單的最近鄰插值法，即定義左上角第一個像素值坐標(biāo)為（0，0），橫軸向右，縱軸向下，例如原圖像為m行n列，我們要實(shí)現(xiàn)的統(tǒng)一的圖像大小為p行q列，則在新圖像中坐標(biāo)為（x，y）的像素值為原圖像坐標(biāo)為（x*(m/p)，y*(n/q)）對應(yīng)的值?，F(xiàn)給出原圖像的像素值矩陣和需要?dú)w一化的圖像大小，請計算出歸一化后的像素矩陣。

輸入格式:
第一行依次輸入m、n、p、q，數(shù)字之間空格隔開，且均小于1000，接下來m行輸入原圖像像素矩陣。各數(shù)字之間空格隔開（各像素值均在0~255之間，保證m，n，p，q均大于0）。

輸出格式:
在m行中輸出計算得出的歸一化之后的矩陣，各數(shù)字之間空格隔開，末尾無多余空格。

輸入樣例:

3 3 4 4
45 25 27
46 25 63
27 47 72

輸出樣例:

45 45 25 27
45 45 25 27
46 46 25 63
27 27 47 72

代碼

  ### 這個測試點(diǎn)判斷一下  
  + 不是三行三列的第二行前面+“ ” 
  + 是三行三列 不用加

#include <iostream>
#include<vector>
#define N 1000
using namespace std;
int main()
{
    int m,n,p,q;
    cin>>m>>n>>p>>q;
    int pic[1000][1000];
    int change[1000][1000];
    getchar();
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
          cin>>pic[i][j];
    for(int i=0;i<p;i++)
        for(int j=0;j<q;j++)
            change[i][j]=pic[i][j];
    for(int i=0;i<p;i++)
        for(int j=0;j<q;j++)
            change[i][j]=pic[i*m/p][j*n/q];
         
    for (int i = 0; i < p; i++)
    {
        if(n!=3 && i==1)
           cout<<" ";
        for (int j = 0; j < q; j++)
        {
            if(j==q-1)
                cout<<change[i][j];
            else
                cout << change[i][j] <<" ";
        }
        cout << endl;
    }
    
 
 } 

7-9 中值濾波 (20 分)

在處理圖像時，由于噪聲的影響處理識別的效果并不是很好。為了盡可能保存圖像原本信息，我們需要在濾除噪聲的同時，能夠保護(hù)信號的邊緣，使之不被模糊。中值濾波采用非線性的方法，它在平滑脈沖噪聲方面非常有效,同時它可以保護(hù)圖像尖銳的邊緣，選擇適當(dāng)?shù)狞c(diǎn)來替代污染點(diǎn)的值，所以處理效果好。對一個圖像的像素值N行M列的矩陣，我們保留其邊緣像素值，對于其他數(shù)值，我們?nèi)∫运行牡?*3矩陣，里面有9個像素點(diǎn)，我們將9個像素進(jìn)行排序，最后將這個矩陣的中心點(diǎn)賦值為這九個像素的中值。并對賦值后的矩陣?yán)^續(xù)進(jìn)行下一像素的運(yùn)算，直至全部完成。

輸入格式:
每個輸入包含一個測試用例，第一行輸入正整數(shù)N（N<100）和M（M<100），中間以空格隔開。接下來N行輸入一個圖像的像素矩陣。

輸出格式:
在N行M列中輸出中值濾波后的像素矩陣。像素值間以空格隔開，末尾無多余空格。

輸入樣例:

4 4
1 5 6 7
3 4 2 8
9 6 3 2
1 5 8 6

輸出樣例:

1 5 6 7
3 4 5 8
9 4 5 2
1 5 8 6

代碼

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int gra[n][m], temp[9],arr[n][m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> gra[i][j];
            arr[i][j]=gra[i][j];
        }
    for (int i = 1; i < n-1; i++)
        for (int j = 1; j < m-1; j++)
        {
            temp[0]=gra[i-1][j-1];
            temp[1]=gra[i-1][j-0];
            temp[2]=gra[i-1][j+1];
            temp[3]=gra[i+1][j-0];
            temp[4]=gra[i+1][j-1];
            temp[5]=gra[i+1][j+1];
            temp[6]=gra[i-0][j+1];
            temp[7]=gra[i-0][j-0];
            temp[8]=gra[i-0][j-1];
            sort(temp,temp+9);
            arr[i][j]=temp[4];
        }
    for (int i = 1; i < n-1; i++)
        for (int j = 1; j < m-1; j++)
            gra[i][j]=arr[i][j];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (j == m - 1)
                cout << gra[i][j];
            else
                cout << gra[i][j] << " ";
        }
        cout << endl;
    }    
}

7-10 計算正確率和準(zhǔn)確率 (20 分)

恭喜大家完成了ISBN碼的識別，為了檢驗(yàn)識別效果，我們需要完成最后一步——計算識別正確率和準(zhǔn)確率。將我們需要識別的ISBN碼與正確的ISBN碼進(jìn)行比較，當(dāng)兩個碼完全相等時，識別正確數(shù)加1，識別正確的數(shù)量與需要識別的ISBH好總數(shù)相除即為識別正確率；對于所有ISBN的每一個數(shù)字的識別正確數(shù)量與所有需要識別的數(shù)字?jǐn)?shù)量相除即為識別準(zhǔn)確率?，F(xiàn)在，我們給出了正確ISBN碼與同學(xué)識別出的ISBN碼，請計算該同學(xué)識別的正確率與準(zhǔn)確率。（保證每一對識別與正確的ISBN碼長度相等，保證至少輸入一對進(jìn)行比較）

輸入格式:
第一行輸入正整數(shù)N（N<100），表示輸入N對ISBN碼。接下來N行分別輸入正確的ISBN碼和識別出的ISBN碼，字符串間以空格隔開。

輸出格式:
在一行中分別輸出正確率和準(zhǔn)確率，保留兩位小數(shù)，數(shù)字間以空格隔開，末尾無多余空格。

輸入樣例:

3
9787111478188 9787111470108
9270862579026 9270862579026
8927518936148 0938518956143

輸出樣例:

0.33 0.82

代碼

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

int main()
{
    int n;
    cin>>n;
    string str_l,str_s,str1,str2;
    int r_num=0,s_num=0;
    for (int i = 0; i < n; ++i)
    {
        cin>>str1;
        str_l+=str1;
        cin>>str2;
        str_s+=str2;
        if(str1==str2)
            r_num++;
    }
    for (int i = 0; i < str_l.length(); ++i)
    {
        if (str_l[i]==str_s[i])
            s_num++;
    }
    printf("%.2lf %.2lf\n", (double)r_num/n*1.0,(double)s_num/str_s.length()*1.0);

}