? ? ? 給定一副彩色圖像，它由一個mxn的像素數組A[1..m,1..n]構成，每個像素是一個紅綠藍(RGB)亮度的三元組。假定我們希望輕度壓縮這幅圖像。具體地，我們希望從每一行中刪除一個像素，使得圖像變窄一個像素。但為了避免影響視覺效果，我們要求相鄰兩行中刪除的像素必須位于同一列或相鄰列。也就是說，刪除的像素構成從頂端行到底端行的一條“接縫”(seam)，相鄰像素均在垂直或對角線方向上相鄰。

????????a.證明：可能的接縫數量是m的指數函數，假定n>1.

??????? 第1行有n種可能選取像素點方式，第2到m行中每行有2-3種(可能選中A[i][j-1],A[i][j],A[i][j+1]. (j=1 or j=n時，是2種可能))，所以總共有至少大于n*2^(m-1).

????????b 假定現在對每個像素A[i,j]我們都已計算出一個實型的“破壞度”d[i,j],表示刪除像素A[i,j]對圖像可視效果的破壞程度。直觀地，一個像素的破壞度越低，它與相鄰像素的相似度越高。再假定一條接縫的破壞度定義為包含的響度的破壞度之和。設計算法，尋找破壞度最低的接縫。分析算法的時間復雜度。

? ? ? ? 求破壞度最低的接縫很簡單，c[i,j]記錄接縫走到當前像素的最低破壞度。從第一行開始，c[i,j]只有當前像素的破壞度，直接賦值即可；第i行，每個像素的上一個像素來源一共有三個，左上、正上和右上方，每次計算c[i,j]時，需要去三種情況中破壞度最低的情況然后加上當前像素的破壞度，就是接縫走到當前像素的最低破壞度。遞推式為c[i][j]=d[i][j]+min{c[i-1][j-1],c[i-1][j],c[i-1][j+1]}。

參考鏈接：http://www.ithao123.cn/content-6605545.html

// 15-8.cpp : 定義控制臺應用程序的入口點。 //#include "stdafx.h" #include<iostream> #include<time.h> #define ROW 10 #define COL 10 #define Left -1 #define Center 0 #define Right 1 #define INF 65536 using namespace std;int c[ROW + 1][COL + 2]; int r[ROW + 1][COL + 1]; int maxj; void carving(int d[][COL + 1]) {//給第0，1行賦值for (int j = 0; j <= COL; j++) { c[0][j] = 0;r[0][j] = Center;c[1][j] = d[1][j];r[1][j] = Center;}//給邊界0，COL賦值做哨兵，由此在下面求C[i][j]時不用檢查j是否為0或COL；for (int i = 0; i <= ROW; i++) {c[i][0] = INF;c[i][COL + 1] = INF;}//根據遞歸式求c[i][j],從第二行開始for(int i=2;i<=ROW;i++) for (int j = 1; j <= COL; j++){int temp = INF;for (int k = j - 1; k <= j + 1; k++){if (c[i - 1][k] < temp){temp = c[i - 1][k];r[i][j] = k - j;}}c[i][j] = temp+d[i][j];}//求最后一行最小的值就是最小的裁剪代價int temp = INF;for (int j = 1; j <= COL; j++) if (c[ROW][j] < temp){ temp = c[ROW][j];maxj = j;}//打印出c[i][j]cout << "c[i][j]:\n" << "最小的切縫代價為" << temp << endl; for (int i = 1; i <= ROW; i++) {for (int j = 1; j <= COL; j++)cout << c[i][j] << '\t';cout << endl;} }//因為從最后一行回推出路徑，因此用遞歸來打印 void display(int row,int maxj) {switch (r[row][maxj]){case -1:display(row - 1, maxj - 1); cout << "\\" << endl; break;case 0: display(row - 1, maxj); cout << "||" << endl; break;case 1:display(row - 1, maxj + 1); cout << "//" << endl; break;} }int main() {//用5-15隨機數初始化d[i][j];srand((int)time(0)); //產生隨機數種子int d[ROW + 1][COL + 1];for (int i = 0; i <= ROW; i++)for (int j = 0; j <= COL; j++)d[i][j] = 5 + rand() % 10;cout << "d[i][j]:\n";for (int i = 1; i <= ROW; i++) {for (int j = 1; j <= COL; j++)cout << d[i][j] << '\t';cout << endl;}cout << "----------------------------------------------------------------------------" << endl;carving(d);cout << "----------------------------------------------------------------------------" << endl;display(ROW, maxj);while (1);return 0;}

　　結果如下圖所示：

?

轉載于:https://www.cnblogs.com/linear/p/6671141.html

總結

以上是生活随笔為你收集整理的基于接缝裁剪的图像压缩 算法导论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。