快速中值滤波及c语言实现

1、快速中值滤波及c语言实现学生姓名：刘勇学号:6100410218专业班级:数媒101【摘要】本文讨论了用C语言在微机上实现中值滤波及快速算法，在程序设计的过程中充分考虑到程序运行的时间复杂度和空间复杂度的问题.解决了由于图像太大而内存不够的问题，运用对程序运行时的方法，得出在PENTIUM-S100MHz中值滤渡的一般算法运行4.23秒.而快速算法运行258秒。【关键词】c语言；中值滤波；快速算法1引言中值滤波是涂基发明的一种非线性信号处理技术，对抑制图像的噪声非常有效，在二维形式下，中值滤渡器是一个古有奇数个像素的滑动窗口，窗口正中的象素的灰度值用窗口内各个象素的中值代替窗口的中值为窗口中象

2、素按大小顺序排列后处于中间位置的象素；本文讨论中值滤的一般算法并比较其运算速度。2用C语言实现算法的若干问题在设计算法编制程序的时候，我们充分考虑到程序运行的时间复杂度和空间复杂度问题，在解决问题的前提下，使算法尽量简单，使程序运行占有的空间尽量的小，这样来减少不必要的时问浪费和空间浪费，从而太大的提高程序执行的效率。首先考虑到的内存问题。由于在本文算法中用的图像是512+5128bit,这就存在一个内存不够大一整幅图像不能一次性调入的问题。为了解受此问题，可以只开辟一个3"512的缓冲区n,将原图像采用分批调入缓冲区，使内存不够的问题得到了圆满的解决。另外为了对中值滤波的快速算法和

3、普通算法进行精确的比较，采用对程序运行计时的方法，并精确计算每个算法运行的时间，使得出的结论更可靠。3中值滤波算法的C语言程序实现本算法采用对开辟的3*512的缓冲区从左到右依次形成一个3*3的窗口.然后将此3*3的窗口放人一个一维数组中，调用求中值子函数.通过排序得出中值，当此中值不等于窗口中间位置的象素时.用此中值来代替窗VI中间位置的象素灰度值.若此缓冲区处理完毕后，将缓冲区的第一行存入新建的文件中，将第二、第三行分别向上移动一行，若存人新建的文件中的行数小于或等于511（即这样处理的行数小于或等于511）,则从原文件中调入一行作为缓冲区第三行，按上述方法进行直到处理的总行数等于511为

4、止，最后，将缓冲区的第二、三行存人新建的文件，程序流程框图如图14中值滤波快速算法的C语言程序实现本算法充分利用了上一次处理的结果.采用迭代，逐次逼近的方法得到本次的中值，在一行处理完毕后转人下一行也采用走SS的方法.这样除第一个窗口采用了一伏排序得到中值外，其它的窗口都利用上伏的窗口的象素删除无用的3个象素后再加人新的3个象素，利用迭代的方法得到本次窗口的中值.这样太大地提高了程序执行的效率。4.1算法的解释首先是开辟一个3*512的缓冲区a,在初始化缓冲区时考虑到时间复杂度的问题，所以只初始化了第二、三行，而对第一行只初始化了前三个象素，这样便在缓冲区中可以得到一个3*3的窗口，对此窗口进

5、行排序求中值后得出第一个窗口的中间象素的值.将文件指针定位在2*512处。然后开始循环，当处理的行数小于或等于511时，将缓冲区a中的第二、三行分别向上移动一行变为第一、二行，从文件中读人512个字节作为缓冲区的第三行，并用行数模2的方法设置方向标志k.当k为0时，从左向右移动窗口.当k为1时.从右向左移动窗口.而每一窗口都利用上次的窗口的像素删除无用的3个象素后再加入新的3个象素.利用迭代的方法从上次的中值得到本次的中值。当处理完一行后将缓冲区的第一行存入新建的文件中，最后将缓冲区的第二、三行存入文件中。4.2算法代码/ImageProcessingDoc.cpp:implementatio

6、noftheCImageProcessingDocclass/#include"stdafx.h"#include"ImageProcessing.h"#include"ImageProcessingDoc.h"#include"GreyRatio.h"#include<math.h>#definePI(acos(0.0)*2)#ifdef_DEBUG#definenewDEBUG_NEW#undefTHIS_FILEstaticcharTHIS_FILE=_FILE_;#endif/CImagePro

7、cessingDocIMPLEMENT_DYNCREATE(CImageProcessingDoc,CDocument)BEGIN_MESSAGE_MAP(CImageProcessingDoc,CDocument)/AFX_MSG_MAP(CImageProcessingDoc)ON_COMMAND(ID_HISTOGRAM_ADJUSTIFCOTH)stogramAdjustifcation)ON_COMMAND(ID_FFT,OnFft)ON_COMMAND(ID_SALT_PEPPER_NOICE,OnSaltPepperNoice)ON_COMMAND(ID_RANDOM_NOISE

8、,OnRandomNoise)ON_COMMAND(ID_MEDIAN_FILTERING,OnMedianFiltering)ON_COMMAND(ID_DCT,OnDct)ON_COMMAND(ID_FWT,OnFwt)ON_COMMAND(ID_DHT,OnDht)ON_COMMAND(ID_WAVELET_TRANSFORM,OnWaveletTransform)ON_COMMAND(ID_GREY_ADJUSTIFCATION,OnGreyAdjustifcation)ON_COMMAND(ID_GREY_LINEAR_ADJUSTIFCATION,OnGreyLinearAdjus

9、tifcation)ON_COMMAND(ID_GREY_SEGLINEAR_ADJUSTIFCATION,OnGreySeglinearAdjustifcation)ON_COMMAND(ID_2DGRAD,On2dgrad)ON_COMMAND(ID_ROBERT,OnRobert)/AFX_MSG_MAPEND_MESSAGE_MAP()/CImageProcessingDocconstruction/destructionCImageProcessingDoc二CImageProcessingDoc()/TODO:addone-timeconstructioncodeheremImag

10、eFile=NULL;bFileIsLoad=FALSE;nRows=256;nCols=256;mSourceData=NULL;pSourceData=NULL;bDataIsProcessed=FALSE;mResultData=FALSE;pResultData=FALSE;FourierDataR=NULL;FourierDataI=NULL;CImageProcessingDoc二CImageProcessingDoc。BOOLCImageProcessingDoc二OnNewDocument()if(!CDocument二OnNewDocument()returnFALSE;/T

11、ODO:addreinitializationcodehere/(SDIdocumentswillreusethisdocument)returnTRUE;/CImageProcessingDocserializationvoidCImageProcessingDoc二Serialize(CArchive&ar)if(ar.IsStoring()/TODO:addstoringcodehereelse/TODO:addloadingcodehere/CImageProcessingDocdiagnostics#ifdef_DEBUGvoidCImageProcessingDoc:Ass

12、ertValid()constCDocument:AssertValid();voidCImageProcessingDoc:Dump(CDumpContext&dc)constCDocument:Dump(dc);#endif/_DEBUG/CImageProcessingDoccommandsBOOLCImageProcessingDoc二OnOpenDocument(LPCTSTRIpszPathName)(intx;inty;if(!CDocument二OnOpenDocument(lpszPathName)returnFALSE;/TODO:Addyourspecialize

13、dcreationcodehereif(mSourceData)(free(mSourceData);mSourceData=NULL;)if(!(mSourceData=(unsignedchar*)malloc(nRows*nCols*sizeof(unsignedchar)returnFALSE;if(pSourceData)(free(pSourceData);pSourceData=NULL;)if(!(pSourceData=(unsignedchar*)malloc(3*nRows*nCols*sizeof(unsignedchar)returnFALSE;if(mResultD

14、ata)(free(mResultData);mResultData=NULL;)if(!(mResultData=(unsignedchar*)malloc(nRows*nCols*sizeof(unsignedchar)returnFALSE;if(pResultData)(free(pResultData);pResultData=NULL;if(!(pResultData=(unsignedchar*)malloc(3*nRows*nCols*sizeof(unsignedchar)returnFALSE;if(mImageFile)fclose(mImageFile);mImageF

15、ile=NULL;if(!(mImageFile=fopen(lpszPathName,"rb")free(mSourceData);returnFALSE;if(fread(mSourceData,sizeof(unsignedchar),nRows*nCols,mImageFile)!=(unsigned)nCols*nRows)free(mSourceData);fclose(mImageFile);mImageFile=NULL;bFileIsLoad=false;returnFALSE;for(y=0;y<nRows;y+)for(x=0;x<nCol

16、s;x+)pSourceData3*y*nCols+3*x=mSourceDatay*nCols+x;pSourceData3*y*nCols+3*x+1=mSourceDatay*nCols+x;pSourceData3*y*nCols+3*x+2=mSourceDatay*nCols+x;bFileIsLoad=TRUE;returnTRUE;voidCImageProcessingDoc二OnHistogramAdjustifcation()/TODO:Addyourcommandhandlercodehereintx,y;double*mR;double*mS;mR=newdouble

17、256;mS=newdouble256;for(x=0;x<256;x+)(mRx=mSx=0.0;/统计直方图for(y=0;y<nRows;y+)for(x=0;x<nCols;x+)(mRmSourceDatay*nCols+x+;for(x=0;x<256;x+)(for(y=0;y<x;y+)mSx+=mRy;mSx/=nRows*nCols;/直方图变换for(y=0;y<nRows;y+)for(x=0;x<nCols;x+)mResultDatay*nRows+x=(char)(255*mSmSourceDatay*nRows+x);/

18、灰度计算for(y=0;y<nRows;y+)for(x=0;x<nCols;x+)(pResultData3*y*nCols+3*x=mResultDatay*nCols+x;pResultData3*y*nCols+3*x+1=mResultDatay*nCols+x;pResultData3*y*nCols+3*x+2=mResultDatay*nCols+x;/更新显示UpdateAllViews(NULL);/FFTandIFFT一维傅立叶变换与你变换函数/输入时域数据实部Tr,虚部Ti/输出频域数据实部Tr,虚部Ti/序列长度N,N等于2的r次幕/FFTorlFFT,逻

19、辑变量，非零做正变换，零做反变换voidCImageProcessingDoc二FFTandIFFT(float*Tr,float*Ti,intN,boolFFTorIFFT)(intr;/迭代次数intl,j,k;/循环变量intp;/用于蝶形计算加权系数的指数intB;/对偶结点距离floatX,Y,XX,YY;floatw;floatcosw,sinw;if(!FFTorIFFT)/如果做傅立叶你变换，则必须对数列除以for(l=0;l<N;l+)Trl/=N;Til/=N;/计算循环次数rr=0;l=N;while(l/=2)r+;/倒序intLH=N/2;inti;floatt

20、emp;j=0;for(i=1;i<N-1;i+)k=LH;while(j>=k)j=j-k;k=k/2;j=j+k;if(i<=j)temp=Tri;Tri=Trj;Trj=temp;temp=Tii;Tii=Tij;Tij=temp;for(l=0;l<=r;l+)/共r级B=1<<(l-1);/第l层对偶结点距离为2A(l-1)for(j=0;j<B;j+)(p=j*(1<<(r-l)；w=2*PI*p/N;for(k=j;k<N-1;k+=(1<<l)(if(FFTorlFFT)/若做傅立叶正变换cosw=cos(

21、-w);sinw=sin(-w);)else/傅立叶反变换cosw=cos(w);sinw=sin(w);)X=Trk+Trk+B*cosw-Tik+B*sinw;Y=Tik+Trk+B*sinw+Tik+B*cosw;XX=Trk-Trk+B*cosw+Tik+B*sinw;YY=Tik-Trk+B*sinw-Tik+B*cosw;Trk=X;Tik=Y;Trk+B=XX;Tik+B=YY;)voidCImageProcessingDoc二OnFft()/TODO:Addyourcommandhandlercodehereinti,j;intii,jj;floattemp;float*Tr;

22、float*Ti;Tr=newfloatnCols;Ti=newfloatnCols;if(FourierDataR)(deleteFourierDataR;FourierDataR=NULL;if(FourierDataI)(deleteFourierDataI;FourierDataR=NULL;FourierDataR=newfloatnRows*nCols;FourierDataI=newfloatnRows*nCols;for(i=0;i<nRows;i+)for(j=0;j<nCols;j+)/图像数据先给傅立叶变换数组FourierDataRi*nCols+j=(fl

23、oat)mSourceDatai*nCols+j;FourierDataIi*nCols+j=0.0;for(i=0;i<nRows;i+)/每行进行傅立叶变换for(j=0;j<nCols;j+)Trj=FourierDataRi*nCols+j;Tij=FourierDataIi*nCols+j;FFTandIFFT(Tr,Ti,nCols,1);for(j=0;j<nCols;j+)FourierDataRi*nCols+j=Trj;FourierDataIi*nCols+j=Tij;deleteTr;deleteTi;Tr=newfloatnRows;Ti=newfl

24、oatnRows;for(j=0;j<nCols;j+)/每列进行傅立叶变换for(i=0;i<nRows;i+)Tri=FourierDataRi*nCols+j;Tii=FourierDataIi*nCols+j;FFTandIFFT(Tr,Ti,nRows,1);for(i=0;i<nRows;i+)FourierDataRi*nCols+j=Tri;FourierDataIi*nCols+j=Tii;for(i=0;i<nRows;i+)for(j=0;j<nCols;j+)temp=sqrt(FourierDataRi*nCols+j*FourierDa

25、taRi*nCols+j+FourierDataIi*nCols+j*FourierDataIi*nCols+j);temp/=100;if(temp>255.0)temp=255.0;ii=nRows-1-(i<nRows/2?i+nRowsi-nRows/2);jj=(j<nCols/2)?(j+nCols/2):(j-nCols/2);/将变换后现实的原点调整在中心位置pResultData3*ii*nCols+3*jj=(int)temp;pResultData3*ii*nCols+3*jj+1=(int)temp;pResultData3*ii*nCols+3*jj

26、+2=(int)temp;/更新显示UpdateAllViews(NULL);deleteFourierDataR;deleteFourierDataI;FourierDatal=NULL;FourierDataR=NULL;return;)voidCImageProcessingDoc:OnSaltPepperNoice()(/TODO:Addyourcommandhandlercodehere/TODO:Addyourcommandhandlercodehereintx;inty;Salt_Pepper_Noise(mSourceData,nCols,nRows);for(y=0;y<

27、;nRows;y+)for(x=0;x<nCols;x+)(pSourceData3*y*nCols+3*x=(unsignedchar)mSourceDatay*nCols+x;pSourceData3*y*nCols+3*x+1=(unsignedchar)mSourceDatay*nCols+x;pSourceData3*y*nCols+3*x+2=(unsignedchar)mSourceDatay*nCols+x;)UpdateAllViews(NULL);)voidCImageProcessingDoc:OnRandomNoise()(/TODO:Addyourcommand

28、handlercodehereintx;inty;Random_Noise(mSourceData,nRows,nCols);for(y=0;y<nRows;y+)for(x=0;x<nCols;x+)(pSourceData3*y*nCols+3*x=(unsignedchar)mSourceDatay*nCols+x;pSourceData3*y*nCols+3*x+1=(unsignedchar)mSourceDatay*nCols+x;pSourceData3*y*nCols+3*x+2=(unsignedchar)mSourceDatay*nCols+x;)UpdateA

29、llViews(NULL);)voidCImageProcessingDoc:Salt_Pepper_Noise(unsignedchar*mdata,intnHeight,intnWidth)unsignedchar*lpSrc;/循环变量longi;longj;/生成伪随机种子srand(unsigned)time(NULL);/在图像中加噪for(j=0;j<nHeight;j+)for(i=0;i<nWidth;i+)if(rand()>31500)/指向源图像倒数第j行，第i个象素的指针lpSrc=(unsignedchar*)&mdataj*nWidth+

30、i;/图像中当前点置为黑*lpSrc=0;)/返回return;)voidCImageProcessingDoc二Random_Noise(unsignedchar*mdata,intnHeight,intnWidth)/指向源图像的指针unsignedchar*lpSrc;/循环变量longi;longj;/像素值unsignedcharpixel;/噪声BYTENoisePoint;/生成伪随机种子srand(unsigned)time(NULL);/在图像中加噪for(j=0;j<nHeight;j+)for(i=0;i<nWidth;i+)NoisePoint=rand()

31、/1024;/指向源图像倒数第j行，第i个象素的指针lpSrc=(unsignedchar*)&mdatanWidth*j+i;/取得像素值pixel=(unsignedchar)*lpSrc;*lpSrc=(unsignedchar)(pixel*224/256+NoisePoint);/返回return;voidCImageProcessingDoc:MedianFiltering(unsignedchar*sourcedata,unsignedchar*resultdata,intnHeight,intnWidth,intnR)inti,j,m,n,r;unsignedtmp;unsignedchar*mdata=newunsignedchar(2*nR+1)*(2*nR+1);for(i=0;i<nRows;i+)for(j=0;j<nCols;j+)if(i<nR)|(i>nHeight-nR-1)|(j<nR)|(j>nWidth-nR-1)resultdatai*nWidth+j=0;elsefor(m=-nR;m<=nR;m+)for(n=-nR;n<=nR;n+)mdata(