基于接缝裁剪的图像压缩

给定一幅彩色图像,它由$m\times n$的像素$A[1\cdots m,1\cdots n]$构成,每个像素是一个红绿蓝$(RGB)$亮度的三元组。假定我们希望轻度压缩这幅图像。具体地,我们希望从每一行中删除一个像素,使得图像变窄一个像素。

为了避免影响视觉效果,我们要求删除的像素必须位于同一列或者是相邻列,也就是说,删除的像素构成从底端到顶端的一条“接缝”(seam),相邻像素均在垂直或对角线方向上相邻。

a.证明:可能的接缝数量是$m$的指数函数,假定$n>1$

证明:第一行有n中可能的取像素的方式,第二行到第m行,每一行有3种可能:$A[i][j-1],A[i][j],A[i][j+1]$。(当j==1或者j==0时,是两种可能)
所以至少有$n\times 2^{(m-1)}$

b.假定现在对每个像素$A[i,j]$我们都已经计算出一个破坏度$d[i,j]$,表示删除像素$A[i,j]$对图像可视化效果的破坏程度。

直观地,一个像素的破坏度越低,它与像素的相似度越高。再假定一条接缝的破坏度定义为包含的响度的破坏度之和。设计算法,寻求破坏度最低的接缝。

01

seam_carving.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
using namespace std;
#define n 6 //数组行
#define m 5 //数组列
#define INFINITY 0x7fffffff
//总共n行 m列
void print_seam(int **A,int i,int j); //第i行 第j列
int Additional_Min(int **A,int i,int j) //第i行 第j列
{
int temp=0;
if(j==1)
{
temp=A[i-1][j]>A[i-1][j+1]?A[i-1][j+1]:A[i-1][j];
}
else if(j==m)
{
temp=A[i-1][j]>A[i-1][j-1]?A[i-1][j-1]:A[i-1][j];
}
else
{
if(A[i-1][j]>A[i-1][j-1])
{
temp=A[i-1][j-1];
if(A[i-1][j-1]>A[i-1][j+1])
temp=A[i-1][j+1];
}
else
{
temp=A[i-1][j];
if(A[i-1][j]>A[i-1][j+1])
temp=A[i-1][j+1];
}
}
return temp;
}
void seam_carving(int **d)
{
int **A,i; //二维数组表示破坏度之和
A=new int *[n+1];
for(i=0;i<=n;i++)
A[i]=new int[m+1];
for(int j=1;j<=m;j++)
A[1][j]=d[1][j];
for(i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
A[i][j]=d[i][j]+Additional_Min(A,i,j);
}
//输出最后接缝的位置
int min_seam=INFINITY;
int seam_plot=0;
for(int j=1;j<=m;j++)
{
if(A[n][j]<min_seam)
{
min_seam=A[n][j];
seam_plot=j;
}
}
cout<<"MIN break point is "<<min_seam<<endl;
print_seam(A,n,seam_plot);
for(int i=0;i<=m;i++)
delete [] A[i];
delete[] A;
}
void print_seam(int **A,int i,int j) //i行 j列,总共n行 m列
{
int seam_next;
if(i==0)
return;
else
{
if(j==m)
seam_next=A[i][j]>A[i][j-1]?j-1:j;
else if(j==1)
seam_next=A[i][j]>A[i][j+1]?j+1:j;
else
{
if(A[i][j]>A[i][j-1])
{
seam_next=j-1;
if(A[i][j-1]>A[i][j+1])
seam_next=j+1;
}
else
{
seam_next=j;
if(A[i][j]>A[i][j+1])
seam_next=j+1;
}
}
}
print_seam(A,i-1,seam_next);
cout<<"ROW: "<<i<<" "<<"COLUMN: "<<seam_next<<"->";
//输出方式,注意把这一句放在递归下面,从i=1--->i=n从上往下执行输出
//如果放在递归前面就是从下往上输出
}

seam_carving.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
using namespace std;
#define n 6 //数组行
#define m 5 //数组列
#define INFINITY 0x7fffffff
//总共n行 m列
void print_seam(int **A,int i,int j); //第i行 第j列
int Additional_Min(int **A,int i,int j) //第i行 第j列
{
int temp=0;
if(j==1)
{
temp=A[i-1][j]>A[i-1][j+1]?A[i-1][j+1]:A[i-1][j];
}
else if(j==m)
{
temp=A[i-1][j]>A[i-1][j-1]?A[i-1][j-1]:A[i-1][j];
}
else
{
if(A[i-1][j]>A[i-1][j-1])
{
temp=A[i-1][j-1];
if(A[i-1][j-1]>A[i-1][j+1])
temp=A[i-1][j+1];
}
else
{
temp=A[i-1][j];
if(A[i-1][j]>A[i-1][j+1])
temp=A[i-1][j+1];
}
}
return temp;
}
void seam_carving(int **d)
{
int **A,i; //二维数组表示破坏度之和
A=new int *[n+1];
for(i=0;i<=n;i++)
A[i]=new int[m+1];
for(int j=1;j<=m;j++)
A[1][j]=d[1][j];
for(i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
A[i][j]=d[i][j]+Additional_Min(A,i,j);
}
//输出最后接缝的位置
int min_seam=INFINITY;
int seam_plot=0;
for(int j=1;j<=m;j++)
{
if(A[n][j]<min_seam)
{
min_seam=A[n][j];
seam_plot=j;
}
}
cout<<"MIN break point is "<<min_seam<<endl;
print_seam(A,n,seam_plot);
for(int i=0;i<=m;i++)
delete [] A[i];
delete[] A;
}
void print_seam(int **A,int i,int j) //i行 j列,总共n行 m列
{
int seam_next;
if(i==0)
return;
else
{
if(j==m)
seam_next=A[i][j]>A[i][j-1]?j-1:j;
else if(j==1)
seam_next=A[i][j]>A[i][j+1]?j+1:j;
else
{
if(A[i][j]>A[i][j-1])
{
seam_next=j-1;
if(A[i][j-1]>A[i][j+1])
seam_next=j+1;
}
else
{
seam_next=j;
if(A[i][j]>A[i][j+1])
seam_next=j+1;
}
}
}
print_seam(A,i-1,seam_next);
cout<<"ROW: "<<i<<" "<<"COLUMN: "<<seam_next<<"->";
//输出方式,注意把这一句放在递归下面,从i=1--->i=n从上往下执行输出
//如果放在递归前面就是从下往上输出
}
原创技术分享,您的支持鼓励我继续创作