《二值图像的象元分组和哈夫曼压缩》由会员分享，可在线阅读，更多相关《二值图像的象元分组和哈夫曼压缩（20页珍藏版）》请在金锄头文库上搜索。
1、1二值图像的象元分组1需求规格说明【问题描述】二值图像中每个元素的值只能为 1 或 0，其中 1 表示有效像元，0 表示图像的背景。如果一个元素在另外一个元素的上、下、左、右四个方向，称两个元素为相邻元素。 “像元分组”算法是将二值图像中处于相邻的元素进行分组标号，使得属于同一个分组的像元集合，其编号都相同。如下图所示：分组前 分组后程序及算法分析运行结果附录/头文件“SeQueue.h”和源文件 “二值图像的像元分组.cpp”2#ifndef SEQQUEUE_H#define SEQQUEUE_H#include #include using namespace std;template
2、class SeqQueuepublic:SeqQueue(int sz = 50);SeqQueue()delete elements;bool EnQueue(const T bool DeQueue(T bool getFront(T void makeEmpty()front = rear = 0;bool IsEmpty()constreturn front = rear;bool IsFull()const3return (rear+1)%maxSize = front;int getSize()constreturn (rear-front+maxSize)% maxSize;f
3、riend ostream& operator &Q)os SeqQueue:SeqQueue(int sz)front = 0;rear = 0;4maxSize = 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 (
4、IsEmpty() return false;x = elementsfront;front = (front+1) % maxSize;return true;5template 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
5、argc, _TCHAR* argv)6static 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=0&h=0&agh=1)agh=o;q.m=g;q.n=h;z.EnQueue(q); d+; o+; /触发一次分
6、组则组号加19for( int i=0 ;i !=row ; i+ )for(int j=0 ; j!=column ; j+)if(aij!=0)aij=aij-1;coutusing 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;HT
7、Node * rchild;HTNode,*HTree;class HuffmanGKMprivate:HTree T; /构造 Huffman 树；string huffCodeCHNUM; /256 个字符的 Huffman 编码；unsigned long weightCHNUM; /256 个可打印字符的频度（或叫权重）unsigned long long file_size; /原始文件字符总数，即文件长度string original_file; /原始文件路径12string compress_file; /压缩文件存储路径string decompress_file; /解压缩
8、文件存储路径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(); /读取原文件，并记录每个字符频
9、度int BuildHuffTree(); /根据频度建立字符的 Huffman 树int CreateHuffCode(); /根据 huffman 树得到 huffman 编码int CompressFile(); /用新编码转换原文件int DecompressFile(); /根据 huffman 树解压缩 huffman 编码的压缩文件HuffmanGKM(); /析构函数，释放堆空间;/ 软件压缩和解压缩软件.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include #include #include Huffman.h#include #inc
10、lude 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;i left & htt right-w.w = HTPivot-w.w )right-;htt left = htt right ;while( left
11、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;/左移小元素。elsebreak;httleft-1=p;int HuffmanGKM:BuildHuffTree()int left=0,right=C
12、HNUM-1;HTree htCHNUM; /树结点的排序数组for( int i=0; iw.w=weighti; /字符频度hti-count=1; /树中结点个数,仅做测试用。hti-w.c=i-PLUS; /字符值hti-lchild =0;hti-rchild=0;15QuickSortHT( ht ,left , right ); /先把各结点字符按频度升序排序。HTree parent;while(leftcode =1;htleft+1-code =0;parent=new HTNode;parent-lchild =htleft;parent-rchild =htleft+1
13、;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 t
14、op=0;while( p|top )if(p)stacktop=p;signtop=1;top+;p=p-lchild ;else / p为空指针，循环出栈while( top!=0 ) /后序遍历中，当访问完一个结点时，则以该结点为根的树都访问完，所以下一步应该继续出栈，top-;p = stacktop;16if( 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;/whilereturn 0;int HuffmanGKM:CompressFile()ifstream read;read.open (original_file);if(read.fail ()coutb(next);read.get(next);for(int i=b.size()-1;i=0;i-)if(b.tes
