C++画像圧縮アルゴリズムbmpハフマンツリー
12302 ワード
Compressor.h #pragma once
#include"HuffmanTree.h"
#include"HCode.h"
#include
#include
class Compressor
{
public:
Compressor();
~Compressor();
void compress(string TargetPath, string sourcePath);//
void decompress(string TargetPath, string sourcePath);//
private:
int colorTypeCount;
int imageWidth;
int imageHeight;
string filePath;
HuffmanTree *tree;
};
HCode.h
#pragma once
#include
#include
using namespace std;
class Color
{
int color;
int count;
};
class HCode
{
public:
HCode();
~HCode();
void addColor(unsigned char color);
int getCodeLen();
bool getBItAt(int inidx);
void addBit(bool in, unsigned char color);
void tranverse();
HCode& operator<
HuffmanTree.h
#pragma once
#include"HCode.h"
#include
using namespace std;
class HuffmanTreeNode
{
public:
HuffmanTreeNode();
char data;//
int weight;//
HuffmanTreeNode * leftChild;
HuffmanTreeNode * rightChild;
};
class HuffmanTree
{
public:
int size;
void HuffmanTreeCreate();
HuffmanTree();
HCode hcode;
~HuffmanTree();
void getCodeRecusion(HuffmanTreeNode * root, string code);
void getCodeMa();
HuffmanTreeNode *root;
void deleteTree(HuffmanTreeNode *root);
};
class MinHeap
{
public:
HuffmanTreeNode ** heapArray;
int currentSize;
int maxSize;
MinHeap(int max);
bool insert(HuffmanTreeNode * data);
HuffmanTreeNode * removeMin();
void shiftDown(int left);
void shiftUp(int child);
};
Compressor.cpp
#include "Compressor.h"
typedef struct tagBITMAPFILEHEADER//BMP (14 )
{
unsigned short bfType; // ， BM(0-1 )
unsigned int bfSize; // ， (2-5 )
unsigned short bfReserved1; // ， 0(6-7 )
unsigned short bfReserved2; // ， 0(8-9 )
unsigned int bfOffBits; // ， (10-13 )
// ，
} BITMAPFILEHEADER;
typedef struct tagBITMAPINFOHEADER // (40 )
{
unsigned int biSize; // (14-17 )
unsigned int biWidth; // ， (18-21 )
unsigned int biHeight; // ， (22-25 )
unsigned short biPlanes; // ， 1(26-27 )
unsigned short biBitCount;// ， 1( ),(28-29 )
// 4(16 )，8(256 ) 24( )
unsigned int biCompression; // ， 0( ),(30-33 )
// 1(BI_RLE8 ) 2(BI_RLE4 )
unsigned int biSizeImage; // ， (34-37 )
unsigned int biXPelsPerMeter; // ， (38-41 )
unsigned int biYPelsPerMeter; // ， (42-45 )
unsigned int biClrUsed;// (46-49 )
unsigned int biClrImportant;// (50-53 )
} BITMAPINFOHEADER;
typedef struct tagRGBQUAD
{
unsigned char Blue;// ( 0-255)
unsigned char Green; // ( 0-255)
unsigned char Red; // ( 0-255)
unsigned char Alpha;//
} RGBA;
Compressor::Compressor()
{
tree = new HuffmanTree;
}
Compressor::~Compressor()
{
}
void Compressor::compress(string TargetPath,string sourcePath)
{
ofstream outfile(TargetPath, ios_base::binary);
ifstream infile(sourcePath, ios_base::binary);
if (!infile.is_open())
{
cout << " " << endl;
return;
}
if (!outfile.is_open())
{
cout << " " << endl;
return;
}
BITMAPFILEHEADER bmphead;
tagBITMAPINFOHEADER bmptag;
infile.read((char *)&bmphead, 14);
infile.read((char *)&bmptag, 40);
cout << bmptag.biHeight << " " << bmptag.biWidth << bmptag.biBitCount << endl;
int max = 4 * bmptag.biWidth*bmptag.biHeight;
unsigned char * bmpdot = new unsigned char[max];
cout << max;
for (int i = 0; i < max; i++)
{
infile.read((char *)(bmpdot + i), 1);
tree->hcode.addColor(bmpdot[i]);
}
tree->HuffmanTreeCreate();//
for (int i = 0; i < 256; i++)
{
if (tree->hcode.codeLength[i] != 0)
cout << " " << i << " " << tree->hcode.codeContent[i] << " " << tree->hcode.codeLength[i] << endl;
}
tree->getCodeMa();
outfile.write((char *)&bmphead, 14);
outfile.write((char *)&bmptag, 40);
for (int i = 0; i < 256; i++) //
{
if (tree->hcode.codeLength[i] != 0)
{
outfile.write((char *)&i, 1);
outfile.write((char *)&(tree->hcode.codeLength[i]), 1);
for (int p = 0; phcode.codeBYTE[i]; p++)
outfile.write((char *)&(tree->hcode.code[i][p]), 1);
}
}
int i = 0;
outfile.write((char *)&i, 4);
unsigned int Buffer = 0;
int Bufferlen = 0;
for (int i = 0; i < max; i++) //
{
unsigned char thiscolor = bmpdot[i];
int thisColorLen = tree->hcode.codeLength[thiscolor];
for (int k = 0; k < tree->hcode.codeBYTE[thiscolor]; k++)
{
int mmm = tree->hcode.codeBYTE[thiscolor];
if (thisColorLen >= 8)
{
Buffer = (Buffer << 8) | tree->hcode.code[thiscolor][k];
Bufferlen += 8;
thisColorLen -= 8;
}
else
{
Buffer = (Buffer << thisColorLen) | (tree->hcode.code[thiscolor][k] >> (8 - thisColorLen));
Bufferlen += thisColorLen;
thisColorLen = 0;
}
if (Bufferlen >= 8)
{
int temp = Buffer >> (Bufferlen - 8);
outfile.write((char *)&temp, 1);
Bufferlen -= 8;
}
}
}
infile.close();
outfile.close();
}
void Compressor::decompress(string TargetPath, string sourcePath)
{
ofstream outfile(TargetPath, ios_base::binary);
ifstream infile(sourcePath, ios_base::binary);
if (!infile.is_open())
{
cout << " " << endl;
return;
}
if (!outfile.is_open())
{
cout << " " << endl;
return;
}
BITMAPFILEHEADER bmphead;
tagBITMAPINFOHEADER bmptag;
infile.read((char *)&bmphead, 14);
infile.read((char *)&bmptag, 40);
outfile.write((char *)&bmphead, 14);
outfile.write((char *)&bmptag, 40);
cout << bmptag.biHeight << " " << bmptag.biWidth << bmptag.biBitCount << endl;
int max = 4 * bmptag.biWidth*bmptag.biHeight;
unsigned char * bmpdot = new unsigned char[max];
tree->root = new HuffmanTreeNode;
while (1) // ,
{
HuffmanTreeNode *p=tree->root;
unsigned char color;
int length=0;
infile.read((char *)&color, 1);
printf(" %d ", color);
infile.read((char *)&length, 1);
cout << " " << length<> (8 - m)&0x00000001;
count++;
if (lead == 0)
{
cout << "0";
if (p->leftChild == 0)
{
p->leftChild = new HuffmanTreeNode;
}
p = p->leftChild;
}
else
{
cout << "1";
if (p->rightChild == 0)
{
p->rightChild = new HuffmanTreeNode;
}
p = p->rightChild;
}
if (count == length)
{
count = 0;
p->data = color;
goto XX;
}
}
}
XX: cout << endl;
}
unsigned int Buffer;
int bufferLen = 8;
infile.read((char *)&Buffer, 1);
HuffmanTreeNode *q=tree->root;
for (int i = 0; i < max; i++)
{
q = tree->root;
while (1)
{
int lead=Buffer >> (bufferLen-1) & 0x00000001;
bufferLen --;
if (bufferLen == 0)
{
infile.read((char *)&Buffer, 1);
bufferLen += 8;
}
if (lead == 1)
{
q = q->rightChild;
}
else
{
q = q->leftChild;
}
if (q->leftChild == NULL||q->rightChild == NULL)
{
outfile.write((char *)&(q->data), 1);
break;
}
}
}
}
HCode.cpp
#include "HCode.h"
#include
using namespace std;
HCode::HCode()
{
codeLength = new int[256];
codeContent = new string[256];
colorWeight = new int[256];
for (int i = 0; i < 256; i++)
{
codeLength[i]=0;
colorWeight[i]=0;
}
}
HCode::~HCode()
{
}
void HCode::addColor(unsigned char color)
{
colorWeight[color]++;
}
void HCode::addBit(bool in, unsigned char color)
{
if (in == 0)
{
codeContent[color] += '0';
}
else
{
codeContent[color] += '1';
}
codeLength[color]++;
//cout << " " << (int)color << " 1， "<
HuffmanTree.cpp
#include "HuffmanTree.h"
HuffmanTree::~HuffmanTree()
{
}
void HuffmanTree::HuffmanTreeCreate()
{
MinHeap heap(256);
HuffmanTreeNode *parent, *firstChild, *secondChild;
HuffmanTreeNode *newNode;
for (int i = 0; i < 256; ++i)
{
if (hcode.colorWeight[i] != 0)
{
size++;
newNode = new HuffmanTreeNode;
newNode->weight = hcode.colorWeight[i];
newNode->data = i;
heap.insert(newNode);
}
}
cout << "size==" << size << "maxln=" << heap.currentSize << endl;
for (int i = 0; i < size-1 ; ++i)
{
parent = new HuffmanTreeNode;
firstChild = heap.removeMin();
secondChild = heap.removeMin();
parent->weight = firstChild->weight + secondChild->weight;
parent->leftChild = firstChild;
parent->rightChild = secondChild;
heap.insert(parent);
root = parent;
}
root = heap.heapArray[0];
string ll;
getCodeRecusion(root, ll);
}
HuffmanTree::HuffmanTree()
{
size = 0;
}
void HuffmanTree::getCodeRecusion(HuffmanTreeNode * root, string code)
{
if (root->leftChild == NULL&&root->rightChild == NULL)
{ for (int i = 0; i < code.length(); i++)
{
if (code[i] == '0')
hcode.addBit(0, root->data);
else
hcode.addBit(1, root->data);
}
}
else
{
getCodeRecusion(root->leftChild, code + '0');
getCodeRecusion(root->rightChild, code + '1');
}
}
void HuffmanTree::getCodeMa()
{
for (int i = 0; i < 256; i++)//
{
if (hcode.codeLength[i] != 0)
{
int lenth = hcode.codeLength[i];
unsigned int temp = 0;//
int count = 0;
int zijiecount = 0;
for (int j = 0; j 0)
{
int parent = (child - 1) / 2;
if (heapArray[child]->weight <= heapArray[parent]->weight)
{
HuffmanTreeNode *temp = heapArray[parent];
heapArray[parent] = heapArray[child];
heapArray[child] = temp;
child = parent;
}
else break;
}
}
HuffmanTreeNode * MinHeap::removeMin()
{
if (currentSize == 1)
{
currentSize--;
return heapArray[0];;
}
HuffmanTreeNode * temp = heapArray[0];
heapArray[0] = heapArray[currentSize - 1];
currentSize--;
shiftDown(0);
return temp;
}
void MinHeap::shiftDown(int left)
{
int i = left;
int j = 2 * i + 1;
HuffmanTreeNode *temp = heapArray[i];
while (j < currentSize)
{
if ((j < currentSize - 1) && heapArray[j]->weight > heapArray[j + 1]->weight)
j++;
if (temp->weight > heapArray[j]->weight)
{
heapArray[i] = heapArray[j];
i = j;
j = 2 * j + 1;
}
else break;
}
heapArray[i] = temp;
}
HuffmanTreeNode::HuffmanTreeNode()
{
leftChild = rightChild = NULL;
weight = 0;
}