《媒体数据库技术》实验指导与报告书

《多媒体数据库技术》实验指导与报告书2011学年第二学期专业：□□□□□□□□学号： 姓名： □□□□： □□□□：□□□□□□□□□□2011.02实验目录TOC\o"1-5"\h\z\o"CurrentDocument"实验 文本媒体的压缩与解压 2\o"CurrentDocument"实验 签名文件的仿真实现 9\o"CurrentDocument"实验 音频信号的时频转换 12\o"CurrentDocument"实验 基于直方图的图像检索 17实验文本媒体的压缩与解压实验目的）给定一段文本，采用变长编码进行压缩，生成压缩码流;）解压生成的压缩码流，还原成原始 文本；）掌握变长编码的基本原理和方法。预习内容编码实验内容1）采用C/C++实现压缩算法；2）采用C/C++实现解压算法；3）统计和分析生成的码流，计算压缩比；4）分析Huffman编码的性能，什么情况下其性能最好？什么情况下性能最差?实验结果（可续页）#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>defineMAX_SINGLECODE_LEN10〃单个字符最大码长defineMAX_STRING_LEN1000〃要编码的字符串的最大长度defineMAX_CODESTRING_LEN10000〃产生的二进制码的最大长度defineMAX_WORDS1000〃要编码的字符串中字符种数最大值defineEND_TREE30000〃树部分存储的结束符definePATH_LEN50〃路径串最大长度/*****哈夫曼树结构定义*****/typedefstructHuffmantree{charch;〃字符部分intweight;〃结点权值intmark;//标记是否加入树中structHuffmantree*parent,*lchild,*rchild,*next;}HTNode,*LinkTree;/*****编码字典结构定义*****/typedefstruct{charch;〃字符部分charcode[MAX_SINGLECODE_LEN];〃编码部分}CodeDictionary;LinkTreesetWeight(char*);LinkTreesortNode(LinkTree);LinkTreecreateHTree(LinkTree);voidcodeHTree(LinkTree,CodeDictionary*);voiddecodeHTree(LinkTree,char*,char*);voiddeleteNode(LinkTree);voidcompressString(char*s,CodeDictionary*,char*);voidreadFile(char*);voidwriteFile(char*);voidreadCode(LinkTree,char*);voidwriteCode(LinkTree,char*);voidmenu();/**主函数输入：空返回：空/voidmain(void){charchoice;//菜单选择变量charstring[MAX_STRING_LEN];〃保存从文件中读取的内容LinkTreetemp;〃保存赋了权值的表LinkTreeht;〃保存排序后的表LinkTreehtcopy,tempcopy;〃表备份LinkTreehtree;〃保存哈夫曼树LinkTreeptr=NULL;CodeDictionarycodedictionary[MAX_WORDS];//编码字典charcodestring[MAX_CODESTRING_LEN];〃保存0-1形的代码串charcodestring2[MAX_CODESTRING_LEN];〃保存0-1形的代码串LinkTreeht2;〃保存读取的树LinkTreehtree2;〃保存排序后的表charfilestring[MAX_STRING_LEN];〃解码后要写入文件中的内容if((ht2=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建链表的头结点{printf("内存不足！)getch();exit(0);}ht2->next=NULL;while(1){menu();//调入主菜单choice=getch();〃读入用户选项switch(choice)//判断用户选择{case'c':case'C':printf("\n您选择了压缩文件模式:\n\n");readFile(string);〃读取要编码的文件(字符串)temp=setWeight(string);〃得到有权值的表tempcopy=setWeight(string);ht=sortNode(temp);//按权值排序后的表htcopy=sortNode(tempcopy);〃用于记录解码树htree=createHTree(ht);//得到哈夫曼树codeHTree(htree,codedictionary);〃哈夫曼编码compressString(string,codedictionary,codestring);〃压缩为0-1码writeCode(htcopy,codestring);〃将解码树和0-1码保存deleteNode(htree);〃释放空间*/break;case'u':case'U':printf("您选择了解压缩文件模式:\n\n");readCode(ht2,codestring2);〃读取要解码的0-1码htree2=createHTree(ht2);〃得到哈夫曼树codeHTree(htree2,codedictionary);〃哈夫曼编码decodeHTree(htree2,codestring2,filestring);//解码writeFile(filestring);//将解码文件保存deleteNode(htree2);〃释放空间break;case'e':case'E':exit(0);〃退出程序}}}/**整理输入的字符串，求出每个字符在数组中出现的次数，作为权值*输入：(字符型指针)字符串的地址返回：(哈夫曼结点指针)含权链表的首地址/LinkTreesetWeight(char*string){inti=0;//文件字符串下标LinkTreetree;〃头指针LinkTreeptr,beforeptr;〃创建指针与其前驱HTNode*node;if((tree=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建链表的头结点returnNULL;tree->next=NULL;for(i=0;string[i]!='\0';i++){ptr=tree;beforeptr=tree;if((node=(HTNode*)malloc(sizeof(HTNode)))==NULL)returnNULL;node->next=NULL;node->parent=NULL;node->lchild=NULL;node->rchild=NULL;node->mark=0;node->ch=string[i];node->weight=1;if(tree->next==NULL)//如果是第一个非头结点tree->next=node;else{ptr=tree->next;while(ptr&&ptr->ch!=node->ch)〃查找相同字符{ptr=ptr->next;beforeptr=beforeptr->next;}if(ptr&&ptr->ch==node->ch)〃如果链表中某结点的字符与新结点的字符相同{ptr->weight++;〃将该结点的权加一free(node);}else〃将新结点插入链表后{node->next=beforeptr->next;beforeptr->next=node;}}}returntree;//返回头指针}/***将整理完的字符串(带权链表)按出现次数从小到大的顺序排列*输入：(哈夫曼结点指针)要排序的表头地址*返回：(哈夫曼结点指针)排序后的表头地址*/LinkTreesortNode(LinkTreetree){LinkTreehead;//头指针LinkTreeph,beforeph;〃创建指针及其前驱LinkTreept;if((head=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建新链表的头结点returnNULL;head->next=NULL;ph=head;beforeph=head;while(tree->next){pt=tree->next;//取被*作链表的头结点tree->next=pt->next;pt->next=NULL;ph=head->next;beforeph=head;if(head->next==NULL)head->next=pt;〃创建当前*作链表头结点else{while(ph&&ph->weight<pt->weight)//将被*作结点插入相应位置{ph=ph->next;beforeph=beforeph->next;}pt->next=beforeph->next;beforeph->next=pt;}}free(tree);returnhead;//返回排序后的头指针}/***用排完序的字符串建立哈夫曼树*输入：(哈夫曼结点指针)要建立哈夫曼树的地址*返回：(哈夫曼结点指针)建立后的哈夫曼树地址*/LinkTreecreateHTree(LinkTreetree){LinkTreep,q,beforep;HTNode*newnode;for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next)//p、q初值为头结点后的两个结点，即最小权结点{tree->next=q->next;q->next=NULL;p->next=NULL;if((newnode=(HTNode*)malloc(sizeof(HTNode)))==NULL)//申请新结点作为哈夫曼树的中间结点returnNULL;newnode->next=NULL;newnode->mark=0;newnode->lchild=p;〃取链表头结点后的两个结点作为新结点的左、右孩子newnode->rchild=q;p->parent=newnode;q->parent=newnode;newnode->weight=p->weight+q->weight;〃权值相力口p=tree->next;beforep=tree;if(p!=NULL&&p->weight>=newnode->weight){newnode->next=beforep->next;//将新结点插入原链表的相应位置beforep->next=newnode;}else{while(p!=NULL&&p->weight<newnode->weight){p=p->next;beforep=beforep->next;}newnode->next=beforep->next;beforep->next=newnode;}}return(tree->next);}/**对哈夫曼树进行编码输入：(哈夫曼结点指针)要编码的哈夫曼树地址(编码字典类型指针)存放字典的首地址*返回：空*/voidcodeHTree(LinkTreetree,CodeDictionary*codedictionary){intindex=0,k=0;charcode[MAX_SINGLECODE_LEN];〃用于统计每个字符的哈夫曼编码LinkTreeptr=tree;//从树的根结点开始if(ptr==NULL){printf("要压缩的文件是空的!\n");exit(0);}教师评分教师评分实验签名文件的仿真实现实验目的）给定一段文本以及一组关键词，实现文本索引的签名文件技术;）设计一种哈希函数，把各关键词映射为比特串（签名）；）将文本分块，采用“位或”操作实现文本块的签名文件；）输入任意查询关键词，采用“位与”操作实现文本检索。预习内容P79：3.4.3签名文件实验内容1）采用C/C++仿真签名文件技术的整个流程；2）分析产生文本块“误选”的原因，以及避免误选的关键要素。实验结果(可续页)#include<stdio.h>#include<stdlib.h>#include<string.h>#defineB100#defineW20#defineINPUT_FILE"name.txt"enumyn{yes,no};structcell{charname[W+1];structcell*next;};inth(char*x){inti=0,hash=0;while(x[i]!=0&&i<W){hash+=(int)x[i];++i;}hash%=B;returnhash;}voidinsertcell(char*x,structcell**A){intk=h(x);structcell*p=(structcell*)malloc(sizeof(structcell));structcell*q=A[k];structcell*r=NULL;if(q==NULL){A[k]=p;}else{while(q!=NULL){if(strcmp(q->name,x)==0){free(p);return;}else{r=q;q=q->next;}}r->next=p;}strcpy(p->name,x);p->next=NULL;return;}enumynmember(char*x,structcell**A){structcell*q=A[h(x)];while(q!=NULL)if(strcmp(q->name,x)==0)return(yes);q=q->next;}return(no);}intmain(void){structcell*A[B]={0};charx[W+1];FILE*p;if(p=fopen(INPUT_FILE,"r")){while(!feof(p)){fscanf(p,"%20s",x);x[W]='\0';insertcell(x,A);}fclose(p);while(1){printf("Inputaname:");scanf("%20s",x);x[W]='\0';printf("%s%s\n",x,member(x,A)?"notfound":"found");}}elseprintf("Cannotopen%s\n",INPUT_FILE);return0;教师评分教师评分实验 音频信号的时频转换实验目的给定一段音频信号的时域采样序列％(n),n=0,1,2,…,N-1,采用离散Fourier变换计算其频域采样序列X(k),k=0,1,2,…N-1。(注：实际中N一般取2的自然数次幂。)预习内容1)离散Fourier变换：X(k)=记％(n)Wnk=0,1,2,...,N-1Nn=0TOC\o"1-5"\h\z2)离散Fourier反变换：％(n)=—NBX(k)W-knn=0,1,2,...,N-1N nk=0其中W=e-j(2k/N), Wkn=e-j(2k/N)kn；N N根据欧拉公式e-jt=cos(t)+j(sint)，离散Fourier变换可重写为：X(k)=Re[X(k)]+jIm[X(k)]=NB%(n)cos(2knn/N)+jNB%(n)sin(2knk/N)] k=0,1,2,…，N-1n=0 n=0从而，音频信号的频谱表示为：X(k)|=[Re2[X(k)]+Im2[X(k)][1/2k=0,1,2,...,N-1相位角为：0(k)=arctan[Im[X(k)]/Re[X(k)]]k=0,1,2,...,N-1实验内容1)对给定的音频信号，进行时域离散采样，得到采样序列%(n),n=0,1,2，…,N-1；2)对采样序列作离散Fourier变换，得到频域采样序列X(k),k=0,1,2,…N-1；3)计算音频信号的频谱和相位角；4)查阅资料，了解加快离散Fourier变换速度的方法。实验结果(可续页)#include<stdio.h>#include<math.h>#include<stdlib.h>#defineN1000typedefstruct{doublereal;doubleimg;}complex;void fft();/*快速傅里叶变换*/voidifft();/*快速傅里叶逆变换*/voidinitW();voidchange();voidadd(complex,complex,complex*);/*复数加法*/voidmul(complex,complex,complex*);/*复数乘法*/voidsub(complex,complex,complex*);/*复数减法*/voiddivi(complex,complex,complex*);/*复数除法*/void output();/*输出结果*/complexx[N], *W;/*输出序列的值*/int $126_*=0;/*输入序列的长度，只限2的N次方*/doublePI;intmain(){inti,method;system("cls");PI=atan(1)*4;printf("Pleaseinputthesizeofx:\n");/*输入序列的长度*/scanf("%d",&size_x);printf("Pleaseinputthedatainx[N]:(suchas:56)\n");/*输入序列对应的值*/for(i=0;i<size_x;i++)scanf("%lf%lf”,&x[i].real,&x[i].img);initW();/*选择FFT或逆FFT运算*/printf("UseFFT(0)orIFFT(1)?\n");scanf("%d",&method);if(method==0)fft();elseifft();output();return0;}/*进行基-2FFT运算*/voidfft(){inti=0,j=0,k=0,l=0;

complexup,down,product;change();for(i=0;i<log(size_x)/log(2)；i++){l=1<<i;for(j=0;j<size_x;j+=2*l ){for(k=0;k<l;k++){mul(x[j+k+l],W[size_x*k/2/l],&product);add(x[j+k],product,&up);sub(x[j+k],product,&down);x[j+k]=up;x[j+k+l]=down;}}}}voidifft(){inti=0,j=0,k=0,l=size_x;);i++)/*蝶形运算);i++)/*蝶形运算*/for(i=0;i<(int)(log(size_x)/log(2){l/=2;for(j=0;j<size_x;j+=2*l ){for(k=0;k<l;k++){add(x[j+k],x[j+k+l],&up);up.real/=2;up.img/=2;sub(x[j+k],x[j+k+l],&down);down.real/=2;down.img/=2;divi(down,W[size_x*k/2/l],&down);x[j+k]=up;x[j+k+l]=down;}}}change();}

size_x);voidinitW(){inti;size_x);W=(complex*)malloc(sizeof(complex)for(i=0;i<size_x;i++){W[i].real=cos(2*PI/size_x*i);W[i].img=-1*sin(2*PI/size_x*i);}}voidchange(){complextemp;unsignedshorti=0,j=0,k=0;doublet;for(i=0;i<size_x;i++){k=i;j=0;t=(log(size_x)/log(2));while((t--)>0 ){j=j<<1;j|=(k & 1);k=k>>1;}if(j>i){temp=x[i];x[i]=x[j];x[j]=temp;}}}voidoutput() /*输出结果*/{inti;printf("Theresultareasfollows\n");for(i=0;i<size_x;i++){printf("%.4f",x[i].real);if(x[i].img>=0.0001)

printf("+%.4fj\n",x[i].img);elseif(fabs(x[i].img)<0.0001)printf("\n");elseprintf("%.4fj\n",x[i].img);}}voidadd(complex{c->real=a.real+b.real;c->img=a.img+b.img;}voidmul(complex{c->real=a.real*b.realc->img=a.real*b.img}voidsub(complex{c->real=a.real-b.real;c->img=a.img-b.img;}voiddivi(complexa,complexb,complexvoidadd(complex{c->real=a.real+b.real;c->img=a.img+b.img;}voidmul(complex{c->real=a.real*b.realc->img=a.real*b.img}voidsub(complex{c->real=a.real-b.real;c->img=a.img-b.img;}voiddivi(complexa,complexb,complexa,complexb,complex-a.img*b.img;+a.img*b.real;a,complexb,complexa,complexb,complex*c)*c)*c)*c){c->real=(a.real*b.real+a.img*b.img)/(b.real*b.real+b.img*b.img);c->img=(a.img*b.real-a.real*b.img)/(b.real*b.real+b.img*b.img);}教师评分教师评分实验 基于直方图的图像检索实验目的1）给定一组灰度图像，计算每帧图像的灰度直方图；2）把每帧图像的灰度直方图表示成向量的形式，建立检索系统的直方图特征数据库；3）定义直方图特征向量的距离公式，以计算两帧图像的相似度；4）给定一个查询要求（草图），计算其直方图特征，根据相似度公式从特征数据库中找到最接近的特征向量，返回特征向量对应的图像作为检索结果。预习内容： 颜色直方图（设备无关位图）文件格式（）实验内容1）采用C/C++实现实验目的4步骤；2）直方图特征向量距离可采用L-1度量法，公式（6.3），更好的方法是累加直方图;3）可对图像先分块，把空间区域信息考虑进去；4）上网查找资料，了解改进直方图图像检索的有效策略。实验结果（可续页）#include<stdio.h>#include<stdlib.h>typedefcharUC;typedefstruct{intp;intsx;intsy;intvmax;char*v;}IMG;voidReadPPM（char*filename,IMG*img） 〃打开PPM文件{FILE*fp;longlen;charc1,c2;if((fp=fopen(filename,"rb"))==NULL){printf("Cannotopenthefile.\n");〃若打不开，则停止程序exit(1);}fscanf(fp,"%c%d%d%d%d%c",&c1,&img->p,&img->sx,&img->sy,&img->vmax,&c2);〃读取各参数〃第一个％©是读取PPM文件格式当中的P,若其不是P,则不是PPM文件〃最后一个％c为图像格式后面的空格，防止将其被误认为是像素的大小被读入if(c1!='P'll(img->p!=5&&img->p!=6))〃判断图像是否为PPM文件{printf("It'swrongtoopenthefile \n");exit(1);}len=img->sx*img->sy;if(img->p==5) 〃当图像为黑白时，只分配一个len大小的空间{img->v=(UC*)calloc(len,1);fread(img->v,len,1,fp);〃将图像的像素信息写入新分配的空间当中}if(img->p==6)〃为彩色时，则分配3个len大小的空间{img->v=(UC*)calloc(len,3);fread(img->v,len,3,fp);}fclose(fp);〃关闭文件}voidWritePPM(char*filename,IMGimg)//写PPM文件{FILE*fp;longlen=img.sx*img.sy;if((fp=fopen(filename,"wb"))==NULL){printf("Cannotopenthefile.\n");exit(0);}if(img.p==5)〃判断黑白，将其写入一个len大小的空间当中{fprintf(fp,"P%d%d%d%d",img.p,img.sx,img.sy,img.vmax);fwrite(img.v,len,1,fp);}if(img.p==6){fprintf(fp,"P%d%d%d%d",img.p,img.sx,img.sy,img.vmax);fwrite(img.v,len,3,fp);}fclose(fp);}voidHistogram(UC*v,longsz,intvmax,long*h)//统计图像直方图{inti;intpv;for(i=0;i<=vmax;i++