Fork me on GitHub

seamCarving

发表于 | 分类于 | 热度 ℃  |  
字数统计 1,064 字 | 阅读时长 5 分钟

其实吧，问题求解课还是有点意思的。。

Seam Carving：以水平和垂直两种方式简单地压缩和拉伸图片，常用于一些图像处理软件，能够做到主要目标不失真。结果肖老师二话不多说就让我们自己写一个。。我哪会写什么图像压缩，网上一查全是java的代码，可我已经忘得差不多了。再查c++，结果c++要用到openCV，呵呵，我还是用java吧。可毕竟菜得扣脚（其实是懒），就拿来了同学的代码看了看，其实并不难，我就顺手补充了点注释。

代码如下：

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import edu.princeton.cs.algs4.Picture;
import java.awt.*;
import java.util.*;
public class seamCarving {
	
    private int[][] colors;
    private int width;
    private int height;
    
    public seamCarving(Picture picture) {
        width=picture.width();
        height=picture.height();
        colors = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                colors[i][j] = picture.get(j, i).getRGB(); //普林斯顿大学把这个函数的参数定为先写col，后写row
            }
        }
    }
    
    public Picture picture() {
        Picture picture = new Picture(width,height);
        for (int i = 0; i <height; i++)
            for (int j = 0; j <width; j++) {
                Color color = new Color(colors[i][j]);
                picture.set(j, i, color);
            }
        return picture;
    }
  
    //能量函数
    public double energy(int x, int y) {
        if (x==0||x==height-1||y==0||y==width-1) {
            return 1000.0;
        }
        else {
            int dxRed = red(colors[x - 1][y]) -red(colors[x + 1][y]);
            int dxGreen = green(colors[x - 1][y]) -green(colors[x + 1][y]);
            int dxBlue = blue(colors[x - 1][y]) -blue(colors[x + 1][y]);
            int dyRed = red(colors[x][y - 1]) - red(colors[x][y + 1]);
            int dyGreen = green(colors[x][y - 1]) - green(colors[x][y + 1]);
            int dyBlue = blue(colors[x][y - 1]) - blue(colors[x][y + 1]);
            return Math.sqrt(Math.pow(dxRed, 2) + Math.pow(dxBlue, 2) + Math.pow(dxGreen, 2) + Math.pow(dyRed, 2) + Math.pow(dyBlue, 2) + Math.pow(dyGreen, 2));
        }
    }
    
    public int[] findVerticalSeam() {
        double[][] dist=new double[height][width];
        int[][] node=new int[height][width];
        int[] seam=new int[height];
        //初始化
        for(int i=0;i<height;i++) { 
        	for(int j=0;j<width;j++) {
        		if(i==0) {
        			dist[i][j]=0.0;
        		} else {
        			dist[i][j]=Double.POSITIVE_INFINITY;
        		}
        	}
        }
        for(int i=1;i<height;i++) {
        	for(int j=0;j<width;j++) {
        		for(int k=-1;k<=1;k++) {
        			if(j+k<0||j+k>=width) continue;
        			if(dist[i][j]>(dist[i-1][j+k]+energy(i,j))) {
        				dist[i][j]=(dist[i-1][j+k]+energy(i,j));
        				node[i][j]=j+k; //记录是从哪个点过来的
        			}
        		}
        	}
        }
        int index=0;
        //找到最后一行中路径总和最短的那一个点
        for(int j=1;j<width;j++) {
        	if(dist[height-1][j]<dist[height-1][index])	{
        		index=j;
        	}
        }
        //向上回溯
        for(int i=height-1;i>=0;i--) {
        	seam[i]=index;
        	index=node[i][index];
        }
        return seam; //返回这条路径的下标数组
    }
    
    public void removeVerticalSeam(int[] seam) {
        int[][] a = new int[height][width-1];
        for (int i=0; i<height; i++) {
            System.arraycopy(colors[i],0,a[i],0,seam[i]);//参数说明：原数组，原数组起始点，目标数组，目标数组起始点，长度
            System.arraycopy(colors[i],seam[i]+1,a[i],seam[i],width-seam[i]-1);
        }
        width--;
        colors = a;
    }
    
    public void tailor(int tx,int ty) {
    	int i=0;
    	for(i=1;i<tx;i++) {
    		removeVerticalSeam(findVerticalSeam());
    	}
    	colors=transpose(colors); //矩阵转置，这样可以用同样 的函数处理高度上的缩减
    	for(i=0;i<ty;i++) {
    		removeVerticalSeam(findVerticalSeam());
    	}
    	colors=transpose(colors); //再转置回来
    	return ;
    }
    
    private int[][] transpose(int[][] origin) {
        int temp;
        temp=width;
        width=height;
        height=temp;
    	int[][] result = new int[height][width];
        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                result[i][j] = origin[j][i];
            }
        }
        return result;
    }
    
    private int red(int rgb) {
        return (rgb >> 16) & 0xFF;
    }
    
    private int green(int rgb) {
        return (rgb >> 8) & 0xFF;
    }
    
    private int blue(int rgb) {
        return (rgb >> 0) & 0xFF;
    }
    
	public static void main(String[] args) {
        Picture picture = new Picture("seamCarving.jpg");
        int dx=0,dy=0;
        Scanner in=new Scanner(System.in);
        dx=in.nextInt();
        dy=in.nextInt();
        in.close();
        seamCarving sc = new seamCarving(picture);
        sc.tailor(dx,dy);
        picture.show(); //显示原图像
        Picture newpicture = sc.picture();
        newpicture.show(); //把sc的colors数组包装为picture对象，再调用picture的show显示修改后的样子
        newpicture.save("swamCarving_result.jpg");
        return ;
    }
	
}

要用到普林斯顿大学的包文件。核心算法就是个dp，没什么大花头，能量函数什么的就不多说了，这么用就行了，原理就说不清了。

知识点补充：

颜色方面的小知识，以白色为例：0xFFFFFFFF 前两个F是透明度的大小，然后是红色的，绿色的，蓝色的亮度。因为是十六进制，所以一个F占四位二进制数，两个占八位，也就是一个byte，代码中要取到红色的值怎么办，很简单，用(rgb >> 16) & 0xFF;,后面十六位舍弃，再和0xFF，（也就是二进制11111111） 位与一下，就截取下来了，绿色蓝色同理。

donate the author