作者：非妃是公主
专栏：《算法》
个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩
专栏系列文章
软件最终形态
压缩8位图中每一个8位的数据（范围0~255），通过dp算法，实现用<=8位的数据来表示8位数据，设计文件结构，使得用户可以通过用户界面
① 点击压缩按钮，弹出文件对话框，选择压缩文件
② 弹出文件保存路径，并实现对bmp文件的过滤。
③ 用户自定义文件名。
④ 将bmp文件压缩，得到更小的文件，方便用户存储。
⑤ 点击解压缩按钮，选择解压缩文件。
⑥ 弹出选择文件路径对话框，并实现对.dp文件的过滤。
⑦ 用户选择解压文件保存路径。
⑧ 用户自定义解压文件名。
⑨ 支持用户使用中文路径名。
⑩ 在8位图的基础上，改进文件结构，拓展软件，使其支持16位图、24位图、32位图的压缩。并提示“压缩成功”信息！
⑪ 进度条功能，可以提供用户当前压缩进度。根据处理字节数，动态显示压缩进度。
文件结构
其中CCompressImage为压缩算法部分，其中包括了dp算法，按位读取和写入文件，CCompressImage.h中存放类的声明，CCompressImage.cpp中存放类的定义。
BmpDpCompress文件为窗口界面，其中BmpDpCompress.ui文件为qt自动生成的ui界面，BmpDpCompress.h文件和BmpDpCompress.cpp文件分别存放qt控件、信号、槽函数的声明和定义。
类结构
bmp位图读取算法
首先根据位图结构读取文件头和信息头
fin.read((char*)&bmp_fh, sizeof(BITMAPFILEHEADER));
fin.read((char*)&bmp_ih, sizeof(BITMAPINFOHEADER));
然后根据信息头中的调色板信息，读出调色板的数量，并存到内存中
num = bmp_ih.biClrUsed;
bmp_tsb = new RGBQUAD[num];
fin.read((char*)bmp_tsb, sizeof(RGBQUAD) * num);
vector<vector<unsigned char>>Pix(bmp_ih.biHeight, vector<unsigned char>(bmp_ih.biWidth));
for (int i = 0; i < bmp_ih.biHeight; i++) {
for (int j = 0; j < bmp_ih.biWidth; j++) {
fin.read((char*)&Pix[i][j], sizeof(char));
}
}
然后将二维举证蛇形化：
for (int i = 0; i < bmp_ih.biHeight; i++) {
if (i % 2 == 0) {
for (int j = 0; j < bmp_ih.biWidth; j++) {
p[bmp_ih.biWidth * i + j + 1] = Pix[i][j];
}
}
else {
for (int j = bmp_ih.biWidth - 1; j >= 0; j--) {
p[bmp_ih.biWidth * i + bmp_ih.biWidth - j] = Pix[i][j];
}
}
}
read bmp整体代码如下：
void readBmp(string path) {
m = 0;
std::ifstream fin(path, std::ios::binary);
if (!fin)
return;
fin.read((char*)&bmp_fh, sizeof(BITMAPFILEHEADER));
fin.read((char*)&bmp_ih, sizeof(BITMAPINFOHEADER));
n = bmp_ih.biHeight * bmp_ih.biWidth;
p.resize(n + 1);
s.resize(n + 1);
q.resize(n + 1);
b.resize(n + 1);
num = bmp_ih.biClrUsed;
bmp_tsb = new RGBQUAD[num];
fin.read((char*)bmp_tsb, sizeof(RGBQUAD) * num);
vector<vector<unsigned char>>Pix(bmp_ih.biHeight, vector<unsigned char>(bmp_ih.biWidth));
for (int i = 0; i < bmp_ih.biHeight; i++) {
for (int j = 0; j < bmp_ih.biWidth; j++) {
fin.read((char*)&Pix[i][j], sizeof(char));
}
}
fin.close();
for (int i = 0; i < bmp_ih.biHeight; i++) {
if (i % 2 == 0) {
for (int j = 0; j < bmp_ih.biWidth; j++) {
p[bmp_ih.biWidth * i + j + 1] = Pix[i][j];
}
}
else {
for (int j = bmp_ih.biWidth - 1; j >= 0; j--) {
p[bmp_ih.biWidth * i + bmp_ih.biWidth - j] = Pix[i][j];
}
}
}
}
Dp压缩算法及追溯解过程
在写这段代码时，自己算法出了大问题。一开始以为是自己的位读取出问题了，从来没想到是算法出问题了，在这里找bug找了有2天……实际上，是对b[i]的定义出现了问题，b[i]定义为了每一位的长度，但是后面使用时当作了每一段的长度。所以导致解错误。
void dp(){
int Lmax = 256, header = 11;
s[0] = 0;
for (int i = 1; i <= n; i++)
{
/*计算像素点p需要的存储位数,此处为针对p[i]==0情况的处理，
很容易出错，如果p[i]为0 log(p[i])会返回错误的结果。*/
b[i] = log2(max(p[i], 1)) + 1;
//b[i] = getBits(p[i]);
int bmax = b[i];
s[i] = s[i - 1] + bmax + header;
q[i] = 0;
for (int j = 2; j <= i && j <= Lmax; j++) {
bmax = max(bmax, log2(max(p[i - j + 1], 1)) + 1);
if (s[i] > s[i - j] + j * bmax + header) {
s[i] = s[i - j] + j * bmax + header;
q[i] = j - 1;
b[i] = bmax;
}
}
}
}
在追溯解，即获取分段信息的时候采用了栈的非递归方式（否则在数据量较大的情况下会发生栈溢出）
int Output()
{
//非递归
stack<int> stk;
int nn = n;
while (nn != 0)
{
nn = nn - q[nn] - 1;
stk.push(q[nn]); //l[0]=0,也被压入栈中
stk.push(b[nn]);
}
m = 0;
while (!stk.empty())
{
b[m] = stk.top();
stk.pop();
q[m] = stk.top(); //此时ｌ[]，用来存储，第ｉ组中，元素个数
stk.pop();
m++;
}
b[m] = b[n];
q[m] = q[n];
ofstream o("q.txt");
for (int i = 1; i <= m; i++) {
o << (int)q[i] + 1 << endl;
}
o.close();
return m;
}
位运算写文件算法
写文件的时候主要分为以下几个部分，
1、先把文件头写入
2、再把信息头写入
3、然后写调色板最后将分段信息写入
4、最后写入分段信息，分为以下3个部分，每个段像素数量，每段的位长度，具体像素数据，最终放到一个long数组中存放。
- 存段长
for (unsigned int i = 1; i <= m; i++)
{
// 存段长，即该段元素的数量，最多256个，占8bit
if (index + 8 < 64)
{
value <<= 8;
value |= (q[i]);
index += 8;
}
else if (index + 8 == 64)
{
value <<= 8;
value |= (q[i]);
myWrite(fout, value);
index = 0;
value = 0;
}
else // index + 8 > 64
{
unsigned char t = 64 - index; // 8位先存t位
value <<= t;
value |= ((q[i]) >> (8 - t)); // 存前t位
myWrite(fout, value);
value = 0;
unsigned char temp = q[i] << t;
value |= (static_cast<unsigned char>(temp >> t)); // 8 - (8 - t)
index = 8 - t;
}
}
- 存段中各元素的统一长度
// 存段中各元素的统一长度，最长8位，占3bit
for (unsigned int i = 1; i <= m; i++) {
if (index + 3 < 64)
{
value <<= 3;
value |= (b[i] - 1);
index += 3;
}
else if (index + 3 == 64)
{
value <<= 3;
value |= (b[i] - 1);
fout.write((char*)&value, sizeof(value));
index = 0;
value = 0;
}
else // index + 3 > 64
{
unsigned char t = 64 - index; // 3位先存t位
value <<= t;
value |= ((b[i] - 1) >> (3 - t)); // 存前t位
fout.write((char*)&value, sizeof(value));
value = 0;
unsigned char temp = b[i] - 1 << (5 + t);
value |= (static_cast<unsigned char>(temp) >> (5 + t)); // 8 - (3 - t)
index = 3 - t;
}
}
- 存段中像素数据
// 存段中元素的像素数据，注意这里是q[i] + 1，才是我们的段长
for (unsigned int i = 1; i <= m; i++){
for (unsigned int j = 1; j <= q[i] + 1; j++)
{
dataNum++;
if (index + b[i] < 64)
{
value <<= b[i];
value |= p[dataNum];
index += b[i];
}
else if (index + b[i] == 64)
{
value <<= b[i];
value |= p[dataNum];
fout.write((char*)&value, sizeof(value));
index = 0;
value = 0;
}
else // index + b[i] > 64
{
unsigned char t = 64 - index; // b[i]位先存t位
value <<= t;
value |= (p[dataNum] >> (b[i] - t)); // 存前t位
fout.write((char*)&value, sizeof(value));
value = 0;
unsigned char temp = p[dataNum] << (8 - (b[i] - t));
value |= (static_cast<unsigned char>(temp) >> (8 - (b[i] - t)));
index = b[i] - t;
}
if (dataNum == count) //最后一个数据
{
value <<= (64 - index);
fout.write((char*)&value, sizeof(value));
}
}
}
位运算读文件算法
- 读文件头、信息头、调色板
//读文件头
fin.read((char*)&bmp_fh, sizeof(BITMAPFILEHEADER));
fin.read((char*)&bmp_ih, sizeof(BITMAPINFOHEADER));
num = bmp_ih.biClrUsed;
if (bmp_tsb)delete bmp_tsb;
bmp_tsb = nullptr;
bmp_tsb = new RGBQUAD[num];
fin.read((char*)bmp_tsb, sizeof(RGBQUAD) * num);
- 读取我们的分段数量
// 读取我们的分段数量。
unsigned int segNum;
// 读段的数量m
fin.read((char*)&segNum, sizeof(int));
q.clear();
b.clear();
q.resize(segNum + 1);
b.resize(segNum + 1);
- 通过bitMap的信息头的biWidth和biHeight的乘积来获取位图数量，并初始化data数组（蛇形化数组）
// 通过bitMap的信息头的biWidth和biHeight的乘积来获取位图数量
unsigned int count = bmp_ih.biWidth * bmp_ih.biHeight;
// 存储我们解压出来的像素数据
vector<unsigned char> data(count + 1);
data[0] = 0;
- 写操作的逆操作，读入文件。(读段长，每一段统一的位数，读段中的元素数据)
for (unsigned int i = 1; i <= segNum; i++)
{
// 读取段元素的数量，最多256个，占8bit
if (index + 8 < 64)
{
q[i] = ((value << index) >> 56);
index += 8;
}
else if (index + 8 == 64)
{
q[i] = ((value << 56) >> 56);
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + 8 > 64
{
unsigned char t = 64 - index; // 先读t位
q[i] = static_cast<unsigned char>((value << index) >> index);
index = 8 - t; // 再读8-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
q[i] <<= index;
q[i] |= (value >> (64 - index));
}
}
// 读取段中各元素的统一长度，最长8位，占3bit
for (unsigned int i = 1; i <= segNum; i++) {
if (index + 3 < 64)
{
b[i] = ((value << index) >> 61) + 1;
index += 3;
}
else if (index + 3 == 64)
{
b[i] = ((value << 61) >> 61) + 1;
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + 3 > 64
{
unsigned char t = 64 - index; // 先读t位
b[i] = static_cast<unsigned char>((value << index) >> index);
index = 3 - t; // 再读3-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
b[i] <<= index;
b[i] |= (value >> (64 - index));
b[i]++;
}
}
// 读取段中元素的像素数据
for (unsigned int i = 1; i <= segNum; i++){
for (unsigned int j = 0; j < q[i] + 1; j++)
{
if (index + b[i] < 64)
{
data[dataNum++] = static_cast<unsigned char>((value << index) >> (64 - b[i]));
index += b[i];
}
else if (index + b[i] == 64)
{
data[dataNum++] = static_cast<unsigned char>((value << index) >> index);
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + y > 64
{
unsigned char t = 64 - index; // 先读t位
data[dataNum] = static_cast<unsigned char>((value << index) >> index);
index = b[i] - t; // 再读y-t位
fin.read((char*)(&value), sizeof(value));
data[dataNum] <<= index;
data[dataNum] |= (value >> (64 - index));
dataNum++;
}
}
}
- 将一维蛇形数组按照二维矩阵的顺序，写入到bmp文件中得到解压缩后的bmp图像
ofstream fout(SavePath, ios::binary);
fout.write((char*)&bmp_fh, sizeof(BITMAPFILEHEADER));
fout.write((char*)&bmp_ih, sizeof(BITMAPINFOHEADER));
fout.write((char*)bmp_tsb, sizeof(RGBQUAD) * num);
// 将data数组按蛇形写入输出文件，即还原成2维数组
for (int i = 0; i < bmp_ih.biHeight; i++) {
if (i % 2 == 0) {
for (int j = 1; j <= bmp_ih.biWidth; j++) {
fout.write((char*)&data[bmp_ih.biWidth * i + j], sizeof(char));
}
}
else {
for (int j = bmp_ih.biWidth; j > 0; j--) {
fout.write((char*)&data[bmp_ih.biWidth * i + j], sizeof(char));
}
}
}
fout.close();
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/130528.html
