图片压缩算法

本来想多写一些Java的学习笔记,然而最近在参加数学建模美赛的集训,所以关于数模的学习是必须的,而Java基础的复习可以说就拉下了。大概说明我是一个deadline驱动型的人吧,失落。

这次的题目是图像的压缩和恢复,看到题目的第一反应是霍夫曼算法来压缩,仔细一想又不对,还是通过网上的博客找到了思路。

首先,最简单的操作就是把8位数字转换为5位或者6位,简单粗暴,也有不错的压缩率,这里不提了。

SVD算法压缩

然后查到可以使用svd算法压缩

对于每一个矩阵M(m*n),可以分解为M=UDV(T),

其中,U是一个 m×n 的矩阵,满足 U(T)U=In,In是n×n的单位阵。

V是一个 n×n 的矩阵,满足 VTV=In。

D 是一个 n×n 的对角矩阵,所有的元素都非负。

我们知道,电脑上的图像(特指位图)都是由像素点组成的,所以存储一张 1000×622 大小的图片,实际上就是存储一个 1000×622 的矩阵,共 622000 个元素。这个矩阵用 SVD 可以分解为 622 个矩阵之和,如果我们选取其中的前 100 个之和作为对图像数据的近似,那么只需要存储 100 个奇异值 di,100 个 ui 向量和 100 个 vi 向量,共计 100×(1+1000+622)=162300 个 元素,大约只有原始的 26% 大小。

clear all;
clc;
%导入图像
X = imread('lena.jpg');
if (size(X,3) ~= 1) 
   X = rgb2gray(X);
end
%奇异值分解
[U S V] = svd(double(X));
%绘制奇异值的分布曲线
plot(diag(S),'b-','LineWidth',3);
title('图像矩阵的奇异值');
ylabel('奇异值');
%图像大小
[m n] = size(X);
%图像矩阵的秩
Rank = rank(double(X));
%显示原图
figure,subplot(1,2,1),imshow(X);
Image_Rank = ['图像矩阵的秩 = ' int2str(Rank)];
title(Image_Rank,'Color','b');
%%
%循环改变奇异值选取的个数,动态观察图像压缩的效果
%循环次数
it = 1;
iter = fix((Rank/4 - 1)/10 +1);
%保存奇异值的个数
K_Store = ones(iter);
%保存不同奇异值个数对应的压缩比
CR_store = ones(iter);
for K=11
    K_Store(it) = K;
    %选取K个奇异值,并恢复原图
    R = U(:,1:K)*S(1:K,1:K)*V(:,1:K)';
    T = uint8(R);
    %显示恢复结果
    subplot(1,2,2),imshow(T);
    SVD_number = ['选取的奇异值的个数 = ' int2str(K)];
    title(SVD_number,'Color','b');
    %计算压缩比
    src_elements = m*n;
    compress_elements = m*K + K*K + K*n;
    compress_ratio = (1 - compress_elements/src_elements)*100;
    CR_store(it) = compress_ratio;
    it = it+1;
    fprintf('Rank = %d : K = %d 个: compress_ratio = %.2f\n',Rank,K,compress_ratio);
    %暂停0.5秒,便于观察效果
    pause(0.5);
end
%%
%绘制奇异值个数与压缩比的关系曲线
figure,plot(K_Store,CR_store,'b-','LineWidth',3);
title('奇异值个数与压缩比的关系');
xlabel('奇异值个数');
ylabel('压缩比');

DCT压缩

首先人眼对低频敏感对高频不敏感,而维基百科里说了

由于离散余弦变换具有很强的”能量集中”特性:大多数的自然信号(包括声音和图像)的能量都集中在离散余弦变换后的低频部分

所以可以省去离散余弦变换后矩阵里的高频部分来对图像进行压缩。

Matlab自带DCT和IDCT函数,因此也没有对这两种算法更深入的进行了解学习,仅仅看了一下大概的原理。

首先是离散余弦变换,具体也不好解释,只好show code了。之后在舍位取最接近的整数。

clear;
clc; 
I = [12,23,53,16;42,16,68,45;34,62,73,26;72,15,34,28]; %数据块 
A = zeros(4); %变换矩阵A,也可以通过函数dctmtx(n)求得 
for i = 1:4 
    for j = 1:4 
        if i == 1 
            a = sqrt(1/4); 
        else 
            a = sqrt(2/4); 
        end 
        A(i,j) = a*cos((j-0.5)*pi*i/4) 
    end 
end 
D = A*I*A'; %DCT变换

或者

clc;
clear all;
close all; 
N = 4; % 这个是一个可以修改的参数,与原始的正方形图像的尺寸相同。 
I = rand(N) % 被变换的矩阵,这里是一个随机生成的、元素分布在0到1的N*N的方阵 
A = sqrt(2 / N)*cos((0:N-1)'*((0:N-1)+0.5)*pi/N); 
A(1,:) = A(1,:) / sqrt(2);
D = A*I*A' % DCT变换

最后,简单地把频率领域上每个成份,除以一个对于该成份的常数就可完成,且接着舍位取最接近的整数。这是整个过程中的主要有损运算。以这个结果而言,经常会把很多更高频率的成份舍位成为接近0,且剩下很多会变成小的正或负数。

常数来源于广泛的实验,可以在网上找到。

最后因为数据中大量的0,即可采用各种方式压缩,这不是本文的重点。

发表评论

电子邮件地址不会被公开。 必填项已用*标注