二值图像的象元分组和哈夫曼压缩.doc

二值图像的象元分组1需求规格说明【问题描述】二值图像中每个元素的值只能为1或0，其中1表示有效像元，0表示图像的背景。如果一个元素在另外一个元素的上、下、左、右四个方向，称两个元素为相邻元素。“像元分组”算法是将二值图像中处于相邻的元素进行分组标号，使得属于同一个分组的像元集合，其编号都相同。如下图所示：分组前 分组后程序及算法分析运行结果附录/头文件“SeQueue.h”和源文件 “二值图像的像元分组.cpp”#ifndef SEQQUEUE_H#define SEQQUEUE_H#include #include using namespace std;template class SeqQueuepublic:SeqQueue(int sz = 50);SeqQueue()delete elements;bool EnQueue(const T &x);bool DeQueue(T &x);bool getFront(T &x)const;void makeEmpty()front = rear = 0;bool IsEmpty()constreturn front = rear;bool IsFull()constreturn (rear+1)%maxSize = front;int getSize()constreturn (rear-front+maxSize)% maxSize;friend ostream& operator(ostream & os,SeqQueue &Q)os front = Q.front , rear = Q.rear endl;for (int i = Q.front; i != Q.rear; i = (i+1) % Q.maxSize)os # i : Q.elementsi endl;os Queue Size: Q.getSize() endl;return os;protected:int rear, front;T *elements;int maxSize;template SeqQueue:SeqQueue(int sz)front = 0;rear = 0;maxSize = sz;elements = new TmaxSize;assert(elements != NULL);template bool SeqQueue:EnQueue(const T &x)if (IsFull()return false;elementsrear = x;rear = (rear+1) % maxSize;return true;template bool SeqQueue:DeQueue(T &x)if (IsEmpty()return false;x = elementsfront;front = (front+1) % maxSize;return true;template bool SeqQueue:getFront(T &x)constif (IsEmpty()return false;x = elementsfront;return true;#endif#include stdafx.h#includeSeqQueue.h#include#includestruct Locationint m,n;struct Directionint x,y;int _tmain(int argc, _TCHAR* argv)static int o=2;static int g,h;Direction move4=0,1,0,-1,1,0,-1,0;Location q;SeqQueue z;int row=8,column=7;int a87;ifstream in(c1.txt);ofstream out(c2.txt);for(int i=0 ; i !=row ; i+)for(int j=0 ; j !=column ; j+)inaij;cout输入的二维数组为endl;for( int i=0 ;i !=row ; i+ )for(int j=0 ; j!=column ; j+)coutaij ;coutendl;for(int i=0; i!=row; i+)for(int j=0; j!=column; j+)while(aij=1) /编组的触发条件q.m=i;q.n=j;aij=o;z.EnQueue(q); /初始判断点while(z.IsEmpty() =false)/如果队列空，则一组内全部改完，退出循环int d=0;int c,v;z.DeQueue(q); /避免重复判断，保证能退出循环c=q.m;v=q.n;while(d4) /四种情况，上下左右扫描g=c+moved.x; h=v+moved.y;if(g=0&h=0&agh=1)agh=o;q.m=g;q.n=h;z.EnQueue(q); d+; o+; /触发一次分组则组号加1for( int i=0 ;i !=row ; i+ )for(int j=0 ; j!=column ; j+)if(aij!=0)aij=aij-1;cout输出的二维数组为endl;for( int i=0 ;i !=row ; i+ )for(int j=0 ; j!=column ; j+)coutaij ;coutendl;for(int i=0 ; i !=row ; i+)for(int j=0 ; j !=column ; j+)outaij ;outendl;return 0;三、软件压缩/解压缩软件 Szip（Huffman算法及应用）1需求规格说明【问题描述】利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。2程序及算法分析运行结果101为原文件，102为压缩后文件，103为解压缩后文件3附录头文件“Huffman.h” 源文件“软件压缩和解压缩软件.cpp”#include stdafx.h #include using std:string; const int CHNUM=256; /字符数 const int PLUS=128; /字符下标偏移量 struct WeightGkm /字符频度结构，包含频度和字符值 unsigned long w; char c; ; typedef struct HTNode /huffman树结构 int count; WeightGkm w; string code; HTNode * lchild; HTNode * rchild; HTNode,*HTree; class HuffmanGKM private: HTree T; /构造Huffman树； string huffCodeCHNUM; /256个字符的Huffman编码； unsigned long weightCHNUM; /256个可打印字符的频度（或叫权重） unsigned long long file_size; /原始文件字符总数，即文件长度 string original_file; /原始文件路径 string compress_file; /压缩文件存储路径 string decompress_file; /解压缩文件存储路径 void QuickSortHT( HTree ht, int left, int right); /快速排序 int Partition( HTree ht, int left, int right); /快速排序中的“分半” void SelectInsert( HTree ht, HTree t, int left ,int right); /按序插入 public: HuffmanGKM( string originalFile , string compressFile, string decompressFile); int ReadFile(); /读取原文件，并记录每个字符频度 int BuildHuffTree(); /根据频度建立字符的Huffman树 int CreateHuffCode(); /根据huffman树得到huffman编码 int CompressFile(); /用新编码转换原文件 int DecompressFile(); /根据huffman树解压缩huffman编码的压缩文件 HuffmanGKM(); /析构函数，释放堆空间 ;/ 软件压缩和解压缩软件.cpp : 定义控制台应用程序的入口点。/ #include stdafx.h #include #include #include Huffman.h #include #include using std:bitset; using std:string; using std:ifstream; using std:ofstream; using std:cout; using std:endl; using std:ios; HuffmanGKM:HuffmanGKM( string originalFile , string compressFile, string decompressFile) for(int i=0;iCHNUM;i+) weighti=0; file_size=0; original_file=originalFile; compress_file=compressFile; decompress_file=decompressFile; int HuffmanGKM:ReadFile() ifstream read; read.open (original_file); if(read.fail() coutThe original file open failed when read file!; return 0; char next; read.get(next); while(!read.eof()/统计频度。 weightnext+PLUS+; read.get(next); file_size+; read.close (); return 0; void HuffmanGKM:QuickSortHT ( HTree htt, int left, int right ) int pivot; if( left right ) / 肯定为真的条件 pivot = Partition ( htt, left, right ); QuickSortHT( htt, left, pivot-1 ); QuickSortHT( htt, pivot+1, right ); /快速排序的patition算法 int HuffmanGKM:Partition ( HTree htt , int left, int right ) /这是左大右小的排序 HTree HTPivot = httleft; /这叫“虚左以待” while( left left & htt right-w.w = HTPivot-w.w ) right-; htt left = htt right ; while( left w.w w.w ) left+; htt right = htt left ; htt left = HTPivot; return left; /最后left=right，所以返回哪个都一样 void HuffmanGKM: SelectInsert( HTree htt, HTree p, int left ,int right)/left是第一个要比较的元素 for( ;leftw.w httleft-w.w ) httleft-1=httleft;/左移小元素。 else break; httleft-1=p; int HuffmanGKM:BuildHuffTree() int left=0,right=CHNUM-1; HTree htCHNUM; /树结点的排序数组 for( int i=0; iw.w=weighti; /字符频度 hti-count=1; /树中结点个数,仅做测试用。 hti-w.c=i-PLUS; /字符值 hti-lchild =0; hti-rchild=0; QuickSortHT( ht ,left , right ); /先把各结点字符按频度升序排序。 HTree parent; while(leftcode =1; htleft+1-code =0; parent=new HTNode; parent-lchild =htleft; parent-rchild =htleft+1; parent-w.c=0; parent-w.w=parent-lchild -w.w+parent-rchild -w.w ; parent-count=parent-lchild -count + parent-rchild-count + 1; SelectInsert( ht,parent,left+2,right); left+; T=parent; /T为建好的huffman树。 return 0; int HuffmanGKM:CreateHuffCode () /非递归后序遍历二叉树，访问叶子结点 HTree stackCHNUM; int signCHNUM=0; HTree p=T; int top=0; while( p|top ) if(p) stacktop=p; signtop=1; top+; p=p-lchild ; else / p为空指针，循环出栈 while( top!=0 ) /后序遍历中，当访问完一个结点时，则以该结点为根的树都访问完，所以下一步应该继续出栈， top-; p = stacktop; if( signtop = 2 ) /表示p的左右子树都已走过 if( p-lchild =0 & p-rchild =0 ) for(int i=1;iw.c+PLUS+=stacki-code; else /表示仅走过T的左子树 ，右子树必定是第一次遇到， stacktop=p; signtop=2; top+; p=p-rchild; break; /else if /while ( !IsEmpty ) if(top=0) break; /while return 0; int HuffmanGKM:CompressFile() ifstream read; read.open (original_file); if(read.fail () coutThe original file open failed when compress！; return 1; ofstream write; write.open(compress_file,ios:binary ); if(write.fail () coutThe compress files open failed when compress！ ; return 1; char next; unsigned char buff=0; int count=0; read.get(next); while(!read.eof() for(string:size_type i=0;ihuffCodenext+PLUS.size();i+) if( huffCodenext+PLUSi=0) buff=(buff1); else if(huffCodenext+PLUSi=1) buff=(buff1)|1; count+; if(count=8) writebuff; count=0; read.get(next); if(count!=0) for(;count!=8;count+) buff=(buff1); writebuff; read.close(); write.close(); return 0; int HuffmanGKM:DecompressFile () ifstream read; read.open (compress_file,ios:binary ); if(read.fail() coutThe compress file pen failed when decompress!endl; return 0; ofstream write; write.open (decompress_file); if(write.fail() coutThe decompress file open failed when decompress!endl; return 0; HTree p=T; char next; read.get(next); unsigned long long countSize=0; while(1) bitsetb(next); read.get(next); for(int i=b.size()-1;i=0;i-) if(b.test(i) p=p-lchild ; else p=p-rchild ; if(p-lchild =0 & p-rchild =0) writew.c; p=T; countSize+; if(countSize=file_size) break; if(countSize=file_size) b