未完待續（源代碼已完成，因為作業還沒
結束，是以不便于上傳源代碼，後續會補
上的）....
#在做并行計算的時候有這麼一個作業
從bmp圖檔檔案中讀取圖像像素資料，使用5×5的卷積核，步長為1，對該圖像進行卷積運算，MPI并行實作圖像卷積過程。請同學們認真檢視附件，明确要求。
要求：
1. 将卷積核和卷積後的像素矩陣輸出到文本文檔以供驗證。
2. 計算程式并行部分的運作時間！！在該程式段首尾加入傳回時間戳的函數并顯示各個核的運算時間
3. 給出并行部分的整體運作時間并對比2核與4核的并行加速比與效率。
4. 寫一份實驗報告說明實驗思路，實驗過程，創新和優化部分
5. 程式測試環境為linux
1. 卷積邊緣點時，采用空白點按照0處理，對應于opencv的border_constant模式。
2. 卷積核統一使用5x5高斯卷積核。圖檔現場給定。寬度會是32的整數倍。
3. 結果允許與實際結果有絕對值為1的誤差
卷積核是什麼
卷積是圖像處理常用的方法,給定輸入圖像,在輸出圖像中每一個像素是輸入圖像中一個小區域中像素的權重平均,其中權值由一個函數定義,這個函數稱為卷積核,
比如說卷積公式:R(u，v)=∑∑G(u-i，v-j)f(i，j) ，其中f為輸入，G為卷積核。
步長是什麼
請參考下面文章裡面的示例3
卷積如何計算
以下面的動态圖通俗直覺地來講，底層的虛線矩陣就代表原始矩陣，陰影矩陣就代表卷積核，陰影矩陣每次移動一格，意思就是步長是1，上層的實線有顔色的矩陣就是輸出矩陣，輸出矩陣的每個元素的計算方法就如動态圖所示範的
最好再參考一下這篇博文幫助了解計算原理（重點看後面的圖檔）以及填充邊
數字圖像處理：基本算法-卷積和相關
1、像素數量不變full,假定輸入矩陣為x*x, 卷積核為m*m,則輸出矩陣為（x-3+1+(3-1)）*（x-3+1+(3-1)），也就是x*x
2、假定輸入矩陣為x*x, 假定輸入矩陣為x*x, 卷積核為m*m,則輸出矩陣為（x-3+1+(3-2)）*（x-3+1+(3-2)），也就是(x-1)*(x-1)
........
m、假定輸入矩陣為x*x, 假定輸入矩陣為x*x, 卷積核為m*m(3*3為例),則輸出矩陣為（x-3+1+(3-3)）*（x-3+1+(3-3)），也就是(x-2)*(x-2)
高斯卷積核的生成（C/C++代碼）
高斯公式如下
C++實作生成高斯核的代碼
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void gen_gs() {
int i, j;
double sigma = 1;
const int N = 5;
double gussian[N][N];
double sum = 0.0;
for (i = 0; i<N; i++)
{
for (j = 0; j<N; j++)
{
gussian[i][j] = exp(-((i - N / 2)*(i - N / 2) + (j - N / 2)*(j - N / 2)) / (2.0*sigma*sigma));
sum += gussian[i][j];
}
}
FILE *fp;
fp = fopen("gs.txt", "w");
for (i = 0; i<N; i++)
{
for (j = 0; j<N; j++)
{
gussian[i][j] /= sum;
fprintf(fp,"%f ", gussian[i][j]);
}
fprintf(fp,"\n");
}
}
int main() {
gen_gs();
return 0;
}
計算優化
用兩個級聯的3*3的卷積核來代替一個5*5的卷積核。(7*7的可以換成3重的3*3的)
具體的原理可以參考下面的知乎問答。
為什麼一個5*5的卷積核可以用兩個3*3的卷積核代替，一個7*7的卷積核可以用三個的3*3卷積核代替？
（建議初學者了解一下變形卷積核、可分離卷積？卷積神經網絡中十大拍案叫絕的操作。這裡對卷積的原理及其發展做了非常清楚的介紹）
使用一個5*5卷積核和兩個級聯的3*3卷積核的參數量和計算量的對比
參數對比
參數個數僅和卷積核大小相關
| 5*5 | 兩個級聯的3*3 | |
| 參數個數對比 | 5*5+1=26 | （3*3+1）*2=20 |
| 更少參數 |
計算量對比
輸入記為x，為了友善讨論假設padding=0,stride=1。此時卷積計算公式 output =( input – kernel + 2padding) / stride + 1簡化為output = input – kernel + 1。
- 5*5卷積：有(x-5+1)* (x-5+1)個輸出點，每個輸出點對應5*5次乘法和5*5次加法（5*5次乘法的結果求和再加上b，一共5*5+1個數相加，是以需要5*5次加法）
- 3*3卷積：第一個3*3卷積有(x-3+1)*(x-3+1)個輸出點，每個輸出點對應3*3次乘法和3*3次加法，第二個3*3卷積的輸入是(x-3+1)*(x-3+1)，在其上做卷積有(x-3+1 -3+1)* (x-3+1-3+1)個輸出點，每個輸出點對應3*3次乘法和3*3次加法。
綜上，當x<22/7 或者10<x ，兩個3*3的卷積核在參數個數和計算量上都占優勢。
在計算卷積的時候，特别是我這裡是用來做BMP圖像的卷積計算，x的值一般比較大，是以選擇用兩個級聯的3*3的卷積核來代替5*5的卷積核
https://www.cnblogs.com/hejunlin1992/p/7624807.html
下面預計要寫的東西有：
MPI并行程式設計（這個需要，但是不打算寫了，因為主要是個人學習筆記，這部分已經學習過了，但更重要的是覺得自己并不足以寫出比網上教程更好的介紹，就略了）
2018-4-30續
參考bmp檔案格式解析BMP檔案格式詳解
BITMAPFILEHEADER fileHead;
fileHead.bfType = 0x4D42;//bmp類型
//bfSize是圖像檔案4個組成部分之和
fileHead.bfSize = sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + colorTablesize + lineByte*height;
上面是BMP圖像的C++代碼格式的表示，可以看到一幅bmp圖像分為：檔案頭、資訊頭、顔色表（僅灰階圖像有）、像素值4個部分，我們最終需要讀取的就是第4部分的資料資訊。前面的BITMAPFILEHEADER和BITMAPINFOHEADER這是兩個系統定義的結構體。結構體的定義我也順便貼出來吧：
typedef struct tagBITMAPFILEHEADER {
WORD bfType;
DWORD bfSize;
WORD bfReserved1;
WORD bfReserved2;
DWORD bfOffBits;
} BITMAPFILEHEADER, FAR *LPBITMAPFILEHEADER, *PBITMAPFILEHEADER;
typedef struct tagBITMAPINFOHEADER{
DWORD biSize;
LONG biWidth;
LONG biHeight;
WORD biPlanes;
WORD biBitCount;
DWORD biCompression;
DWORD biSizeImage;
LONG biXPelsPerMeter;
LONG biYPelsPerMeter;
DWORD biClrUsed;
DWORD biClrImportant;
} BITMAPINFOHEADER, FAR *LPBITMAPINFOHEADER, *PBITMAPINFOHEADER;
下面是讀取BMP圖像并輸出像素資料到檔案，另外再将同一張圖檔的各個部分輸出形成原圖的一份拷貝的示範代碼，以供參考
#define _CRT_SECURE_NO_WARNINGS
#include<math.h>
#include <iomanip>
#include <stdlib.h>
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
using namespace std;
//---------------------------------------------------------------------------------------
//以下該子產品是完成BMP圖像(彩色圖像是24bit RGB各8bit)的像素擷取，并存在檔案名為xiang_su_zhi.txt中
unsigned char *pBmpBuf;//讀入圖像資料的指針
int bmpWidth;//圖像的寬
int bmpHeight;//圖像的高
RGBQUAD *pColorTable;//顔色表指針
int biBitCount;//圖像類型，每像素位數 8-灰階圖 24-彩色圖
//-------------------------------------------------------------------------------------------
//讀圖像的位圖資料、寬、高、顔色表及每像素位數等資料進記憶體，存放在相應的全局變量中
bool readBmp(char *bmpName)
{
FILE *fp = fopen(bmpName, "rb");//二進制讀方式打開指定的圖像檔案
if (fp == 0)
return 0;
//跳過位圖檔案頭結構BITMAPFILEHEADER
fseek(fp, sizeof(BITMAPFILEHEADER), 0);
//定義位圖資訊頭結構變量，讀取位圖資訊頭進記憶體，存放在變量head中
BITMAPINFOHEADER head;
fread(&head, sizeof(BITMAPINFOHEADER), 1, fp); //擷取圖像寬、高、每像素所占位數等資訊
bmpWidth = head.biWidth; //寬度用來計算每行像素的位元組數
bmpHeight = head.biHeight; // 像素的行數
biBitCount = head.biBitCount;//定義變量，計算圖像每行像素所占的位元組數（必須是4的倍數）
int lineByte = (bmpWidth * biBitCount / 8 + 3) / 4 * 4;//灰階圖像有顔色表，且顔色表表項為256 (可以了解為lineByte是對bmpWidth的以4為步長的向上取整)
if (biBitCount == 8)
{
//申請顔色表所需要的空間，讀顔色表進記憶體
pColorTable = new RGBQUAD[256];
fread(pColorTable, sizeof(RGBQUAD), 256, fp);
}
//申請位圖資料所需要的空間，讀位圖資料進記憶體
pBmpBuf = new unsigned char[lineByte * bmpHeight];
cout << "lineByte" << lineByte << " bmpHeight" << bmpHeight << " bibitCount"<<biBitCount << endl;
fread(pBmpBuf, 1, lineByte * bmpHeight, fp);
fclose(fp);//關閉檔案
return 1;//讀取檔案成功
}
//-----------------------------------------------------------------------------------------
//給定一個圖像位圖資料、寬、高、顔色表指針及每像素所占的位數等資訊,将其寫到指定檔案中
bool saveBmp(char *bmpName, unsigned char *imgBuf, int width, int height, int biBitCount, RGBQUAD *pColorTable)
{
//如果位圖資料指針為0，則沒有資料傳入，函數傳回
if (!imgBuf)
return 0;
//顔色表大小，以位元組為機關，灰階圖像顔色表為1024位元組，彩色圖像顔色表大小為0
int colorTablesize = 0;
if (biBitCount == 8)
colorTablesize = 1024;//8*128
//待存儲圖像資料每行位元組數為4的倍數
int lineByte = (width * biBitCount / 8 + 3) / 4 * 4;
//以二進制寫的方式打開檔案
FILE *fp = fopen(bmpName, "wb");
if (fp == 0)
return 0;
//申請位圖檔案頭結構變量，填寫檔案頭資訊
BITMAPFILEHEADER fileHead;
fileHead.bfType = 0x4D42;//bmp類型
//bfSize是圖像檔案4個組成部分之和阿
fileHead.bfSize = sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + colorTablesize + lineByte*height;
fileHead.bfReserved1 = 0;
fileHead.bfReserved2 = 0;
//bfOffBits是圖像檔案前3個部分所需空間之和
fileHead.bfOffBits = 54 + colorTablesize;
//寫檔案頭進檔案
fwrite(&fileHead, sizeof(BITMAPFILEHEADER), 1, fp);
//申請位圖資訊頭結構變量，填寫資訊頭資訊
BITMAPINFOHEADER head;
head.biBitCount = biBitCount;
head.biClrImportant = 0;
head.biClrUsed = 0;
head.biCompression = 0;
head.biHeight = height;
head.biPlanes = 1;
head.biSize = 40;
head.biSizeImage = lineByte*height;
head.biWidth = width;
head.biXPelsPerMeter = 0;
head.biYPelsPerMeter = 0;
//寫位圖資訊頭進記憶體
fwrite(&head, sizeof(BITMAPINFOHEADER), 1, fp);
//如果灰階圖像，有顔色表，寫入檔案
if (biBitCount == 8)
fwrite(pColorTable, sizeof(RGBQUAD), 256, fp);
//寫位圖資料進檔案
fwrite(imgBuf, height*lineByte, 1, fp);
//關閉檔案
fclose(fp);
return 1;
}
//----------------------------------------------------------------------------------------
//以下為像素的讀取函數
void doIt()
{
//讀入指定BMP檔案進記憶體
char readPath[] = "nx.BMP";
readBmp(readPath);
//輸出圖像的資訊
cout << "width=" << bmpWidth << " height=" << bmpHeight << " biBitCount=" << biBitCount << endl;
//循環變量，圖像的坐标
//每行位元組數
int lineByte = (bmpWidth*biBitCount / 8 + 3) / 4 * 4;
//循環變量，針對彩色圖像，周遊每像素的三個分量
int m = 0, n = 0, count_xiang_su = 0;
//将圖像左下角1/4部分置成黑色
ofstream outfile("圖像像素.txt", ios::in | ios::trunc);
if (biBitCount == 8) //對于灰階圖像
{
//------------------------------------------------------------------------------------
//以下完成圖像的分割成8*8小單元，并把像素值存儲到指定文本中。由于BMP圖像的像素資料是從
//左下角：由左往右，由上往下逐行掃描的
int L1 = 0;
int hang = 63;
int lie = 0;
//int L2=0;
//int fen_ge=8;
for (int fen_ge_hang = 0; fen_ge_hang<8; fen_ge_hang++)//64*64矩陣行循環
{
for (int fen_ge_lie = 0; fen_ge_lie<8; fen_ge_lie++)//64*64列矩陣循環
{
//--------------------------------------------
for (L1 = hang; L1>hang - 8; L1--)//8*8矩陣行
{
for (int L2 = lie; L2<lie + 8; L2++)//8*8矩陣列
{
m = *(pBmpBuf + L1*lineByte + L2);
outfile << m << " ";
count_xiang_su++;
if (count_xiang_su % 8 == 0)//每8*8矩陣讀入文本檔案
{
outfile << endl;
}
}
}
//---------------------------------------------
hang = 63 - fen_ge_hang * 8;//64*64矩陣行變換
lie += 8;//64*64矩陣列變換
//該一行（64）由8個8*8矩陣的行組成
}
hang -= 8;//64*64矩陣的列變換
lie = 0;//64*64juzhen
}
}
//double xiang_su[2048];
//ofstream outfile("xiang_su_zhi.txt",ios::in|ios::trunc);
if (!outfile)
{
cout << "open error!" << endl;
exit(1);
}
else if (biBitCount == 24)
{//彩色圖像
for (int i = 0; i<bmpHeight; i++)
{
for (int j = 0; j<bmpWidth; j++)
{
for (int k = 0; k<3; k++)//每像素RGB三個分量分别置0才變成黑色
{
//*(pBmpBuf+i*lineByte+j*3+k)-=40;
m = *(pBmpBuf + i*lineByte + j * 3 + k);
outfile << m << " ";
count_xiang_su++;
if (count_xiang_su % 8 == 0)
{
outfile << endl;
}
//n++;
}
n++;
}
}
}
cout << "總的像素個素為:" << count_xiang_su << endl;
cout << "----------------------------------------------------" << endl;
//将圖像資料存盤
char writePath[] = "nvcpy.BMP";//圖檔處理後再存儲
saveBmp(writePath, pBmpBuf, bmpWidth, bmpHeight, biBitCount, pColorTable);
//清除緩沖區，pBmpBuf和pColorTable是全局變量，在檔案讀入時申請的空間
delete[]pBmpBuf;
if (biBitCount == 8)
delete[]pColorTable;
}
void main()
{
doIt();
}
可能遇到的問題
黑線的問題：是因為分發資料的時候導緻的，要得到x行的結果，分發的時候就必須有x+m-1行的原始資料（m代表卷積核的規格，不足部分使用0填充）
部分優化及分析
優化一
首先聲明：這裡我一定要說清楚，貼出我的一段錯誤代碼，但是主要是優化的思路及分析（個人感覺這個思路比較有mark的必要）。錯誤的代碼分析完了之後會附上正确的代碼
在計算行坐标時每計算一個像素就會多出3*5*5次加法和3*5*5次乘法，這樣總的計算次數就會多出3*5*5*height*width次加法和乘法
同樣的列坐标多出3*5*5*height*width次加法
如果隻是将3次計算統一成一次計算，那隻會将多餘的計算量減少為原來的1/3.而事實上注意到在卷積的過程中這個行坐标的計算在不同像素之間計算時也是有很多的重疊部分（同一行的像素）是以考慮對同一行多餘計算進行統一。
改進如下
對行坐标的多餘計算總共隻需要height次乘法和height*width*5次加法。
對列坐标的多餘計算總共隻需要5*5*height*width。
共計減少了(3*5*5* width- 1)* height次乘法
共計減少了(2*3*5-1-5）*5*height*width次加法，
實際上必須的乘法和加法為3*5*5*height*width次，
必須的加法為3*(5*5-1)* height*width次，
這樣優化之後，相當于把程式做的乘法次數減少了将近50%，加法次數減少到原來的46%（我在計算的時候把浮點乘和整數乘的時間看做相等來進行計算，記得去年做矩陣乘的時候這兩個相乘的時間好像就是差不太多）
綜上，經過這步優化，程式的計算效率大約提升為優化前的2倍。
下面是正确的代碼（其實優化效果沒有上面錯誤的那麼明顯，僅僅是減少了一些加法而已）
優化二：考慮cache的緩存資料更新的資源消耗
優化方法：改變循環的嵌套次序
優化前
優化後
這一步優化可以很明顯看出不會對計算結果産生影響，但是在計算的順序上有了很大的變化。
line=i+a放在外層循環，lie=j+b放在内層循環，很容易了解，先對一行進行計算，然後對下一行進行計算，
優化的原理是cache有一個預取技術，假如你去了R[0][0]位置的元素，它就會預測你可能還會使用臨近的R[0][1]以及更多的元素，然後會幫你把它一起取到緩存，而下一個要用的正好就是這個，是以直接在緩存中就可以找到，節省了存取時間，利用這個原理，以及矩陣的順序存儲的特性，我們計算完一行之後，再去計算下一行，而不是像原來那樣一個卷積核一個卷積核地計算，因為那樣會有5行的跨度，極大地浪費了緩存的資源。