下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 十五个经典算法研究与总结、目录+索引(by_...

十五个经典算法研究与总结、目录+索引(by_....pdf

十五个经典算法研究与总结、目录+索引(by_...

以後為自己
2017-05-15 0人阅读 举报 0 0 暂无简介

简介:本文档为《十五个经典算法研究与总结、目录+索引(by_...pdf》,可适用于IT/计算机领域

十五个经典算法研究与总结作者:July时间:年月末年月。微博:http:weibocomjulyweibo出处:http:blogcsdnnetvJULYv声明:版权所有侵权定究。文档制作者:花明月暗有鱼网http:wwwyouyurcomCEO吴超前言:本人的原创作品经典算法研究系列自从10年12月末至11年12月写了近一年。可以这么说开博头俩个月一直在整理微软等公司的面试题而后的四个月至今则断断续续除了继续微软面试100题系列和程序员编程艺术系列之外便在写这经典算法研究系列和相关算法文章。本经典算法研究系列涵盖A*DijkstraDPBFSDFS红黑树KMP遗传启发式搜索图像特征提取SIFT傅立叶变换Hash快速排序SPFA快递选择SELECT等个经典基础算法共计篇文章包括算法理论的研究与阐述及其编程的具体实现。很多个算法都后续写了续集如第二个算法:Dijkstra算法便写了篇文章sift算法包括其编译及实现写了篇文章而红黑树系列则更是最后写了篇文章成为了国内最为经典的红黑树教程。OK任何人有任何问题欢迎随时在blog上留言评论或来信:zhouleiyahoocn批评指正。谢谢。以下是已经写了的个经典算法集锦算是一个目录索引共计篇文章:十五个经典算法研究集锦目录一、A*搜索算法一(续)、A*DijkstraBFS算法性能比较及A*算法的应用二、Dijkstra算法初探二(续)、彻底理解Dijkstra算法二(再续)、Dijkstra算法fibonacci堆的逐步c实现二(三续)、Dijkstra算法Heap堆的完整c实现源码三、动态规划算法四、BFS和DFS优先搜索算法五、教你透彻了解红黑树(红黑数系列六篇文章之其中两篇)五(续)、红黑树算法的实现与剖析六、教你初步了解KMP算法、updated(KMP算法系列三篇文章)六(续)、从KMP算法一步一步谈到BM算法六(三续)、KMP算法之总结篇(必懂KMP)七、遗传算法透析GA本质八、再谈启发式搜索算法九、图像特征提取与匹配之SIFT算法(SIFT算法系列五篇文章)九(续)、sift算法的编译与实现九(再续)、教你一步一步用c语言实现sift算法、上九(再续)、教你一步一步用c语言实现sift算法、下九(三续):SIFT算法的应用目标识别之Bagofwords模型十、从头到尾彻底理解傅里叶变换算法、上十、从头到尾ons-directories中将C:WinGsl下的libgsl分别加入到库文件和头文件的搜索路径中。以下是可能会出现的错误情况处理:I、OpenCV安装后“没有找到cxcoredll”的错误处理在安装时选择“将OpenCVbin加入系统变量”(AddOpenCVbintothesystermPATH)。但该选项并不一定能成功添加到系统变量如果编写的程序在运行时出现“没有找到cxcoredll因为这个应用程序未能启动。重新安装应用程序可能会修复此问题。”的错误。手动在我的电脑>属性>高级>环境变量>系统变量>path添加c:programfilesopencvbin添加完成后需要重启计算机。II、vc下配置了一下可是编译程序时遇到如下一个错误:LinkingLINK:fatalerrorLNK:cannotopenfile"odbccplibcxcorelib"可能是:在工程设置的时候添加连接库时没加空格或来把两个文件名(odbccplibcxcorelib)分开。注意每一次操作后记得保存。若经过以上所有的步骤之后如果还不能正常编译那就是还要稍微修改下你下载的RobHess代码。ok日后若有空再好好详细剖析下此sift的源码。最后祝你编译顺利。完。版权声明:原创文章若需转载请标明出处。谢谢。九(再续)、教你一步一步用c语言实现sift算法、上作者:July、二零一一年三月十二日出处:http:blogcsdnnetvJULYv参考:RobHess维护的sift库环境:windowsxpvc条件:c语言实现。说明:本BLOG内会陆续一一实现所有经典算法。引言:在我写的关于sift算法的前倆篇文章里头已经对sift算法有了初步的介绍:九、图像特征提取与匹配之SIFT算法而后在:九(续)、sift算法的编译与实现里我也简单记录下了如何利用opencvgsl等库编译运行sift程序。但据一朋友表示是否能用c语言实现sift算法同时尽量不用到opencvgsl等第三方库之类的东西。而且RobHess维护的sift库也不好懂有的人根本搞不懂是怎么一回事。那么本文就教你如何利用c语言一步一步实现sift算法同时你也就能真正明白sift算法到底是怎么一回事了。ok先看一下本程序最终运行的效果图sift算法分为五个步骤(下文详述)对应以下第二第六幅图:sift算法的步骤要实现一个算法首先要完全理解这个算法的原理或思想。咱们先来简单了解下什么叫sift算法:sift尺度不变特征转换是一种电脑视觉的算法用来侦测与描述影像中的局部性特征它在空间尺度中寻找极值点并提取出其位置、尺度、旋转不变量此算法由DavidLowe在年所发表年完善总结。所谓Sift算法就是用不同尺度(标准差)的高斯函数对图像进行平滑然后比较平滑后图像的差别差别大的像素就是特征明显的点。以下是sift算法的五个步骤:一、建立图像尺度空间(或高斯金字塔)并检测极值点首先建立尺度空间要使得图像具有尺度空间不变形就要建立尺度空间sift算法采用了高斯函数来建立尺度空间高斯函数公式为:G(x,y,e)=*pi*e^*exp(x^y^)e^上述公式G(x,y,e)即为尺度可变高斯函数。而一个图像的尺度空间L(x,y,e),定义为原始图像I(x,y)与上述的一个可变尺度的维高斯函数G(x,y,e)卷积运算。即原始影像I(xy)在不同的尺度e下与高斯函数G(x,y,e)进行卷积得到L(x,y,e)如下:L(x,y,e)=G(x,y,e)*I(x,y)以上的(xy)是空间坐标e是尺度坐标或尺度空间因子e的大小决定平滑程度大尺度对应图像的概貌特征小尺度对应图像的细节特征。大的e值对应粗糙尺度(低分辨率)反之对应精细尺度(高分辨率)。尺度受e这个参数控制的表示。而不同的L(x,y,e)就构成了尺度空间具体计算的时候即使连续的高斯函数都被离散为(一般为奇数大小)(*k)*(*k)矩阵来和数字图像进行卷积运算。随着e的变化建立起不同的尺度空间或称之为建立起图像的高斯金字塔。但像上述L(x,y,e)=G(x,y,e)*I(x,y)的操作在进行高斯卷积时整个图像就要遍历所有的像素进行卷积(边界点除外)于此就造成了时间和空间上的很大浪费。为了更有效的在尺度空间检测到稳定的关键点也为了缩小时间和空间复杂度对上述的操作作了一个改建:即提出了高斯差分尺度空间(DOGscalespace)。利用不同尺度的高斯差分与原始图像I(x,y)相乘卷积生成。D(x,y,e)=((G(x,y,ke)G(x,y,e))*I(x,y)=L(x,y,ke)L(x,y,e)DOG算子计算简单是尺度归一化的LOG算子的近似。ok耐心点咱们再来总结一下上述内容:、高斯卷积在组建一组尺度空间后再组建下一组尺度空间对上一组尺度空间的最后一幅图像进行二分之一采样得到下一组尺度空间的第一幅图像然后进行像建立第一组尺度空间那样的操作得到第二组尺度空间公式定义为L(x,y,e)=G(x,y,e)*I(x,y)图像金字塔的构建:图像金字塔共O组每组有S层下一组的图像由上一组图像降采样得到效果图图A如下(左为上一组右为下一组):、高斯差分在尺度空间建立完毕后为了能够找到稳定的关键点采用高斯差分的方法来检测那些在局部位置的极值点即采用俩个相邻的尺度中的图像相减即公式定义为:D(x,y,e)=((G(x,y,ke)G(x,y,e))*I(x,y)=L(x,y,ke)L(x,y,e)效果图图B:SIFT的精妙之处在于采用图像金字塔的方法解决这一问题我们可以把两幅图像想象成是连续的分别以它们作为底面作四棱锥就像金字塔那么每一个截面与原图像相似那么两个金字塔中必然会有包含大小一致的物体的无穷个截面但应用只能是离散的所以我们只能构造有限层层数越多当然越好但处理时间会相应增加层数太少不行因为向下采样的截面中可能找不到尺寸大小一致的两个物体的图像。咱们再来具体阐述下构造D(x,y,e)的详细步骤:、首先采用不同尺度因子的高斯核对图像进行卷积以得到图像的不同尺度空间将这一组图像作为金子塔图像的第一层。、接着对第一层图像中的倍尺度图像(相对于该层第一幅图像的倍尺度)以倍像素距离进行下采样来得到金子塔图像的第二层中的第一幅图像对该图像采用不同尺度因子的高斯核进行卷积以获得金字塔图像中第二层的一组图像。、再以金字塔图像中第二层中的倍尺度图像(相对于该层第一幅图像的倍尺度)以倍像素距离进行下采样来得到金字塔图像的第三层中的第一幅图像对该图像采用不同尺度因子的高斯核进行卷积以获得金字塔图像中第三层的一组图像。这样依次类推从而获得了金字塔图像的每一层中的一组图像如下图所示:、对上图得到的每一层相邻的高斯图像相减就得到了高斯差分图像如下述第一幅图所示。下述第二幅图中的右列显示了将每组中相邻图像相减所生成的高斯差分图像的结果限于篇幅图中只给出了第一层和第二层高斯差分图像的计算(下述俩幅图统称为图):、因为高斯差分函数是归一化的高斯拉普拉斯函数的近似所以可以从高斯差分金字塔分层结构提取出图像中的极值点作为候选的特征点。对DOG尺度空间每个点与相邻尺度和相邻位置的点逐个进行比较得到的局部极值位置即为特征点所处的位置和对应的尺度。二、检测关键点为了寻找尺度空间的极值点每一个采样点要和它所有的相邻点比较看其是否比它的图像域和尺度域的相邻点大或者小。如下图图所示中间的检测点和它同尺度的个相邻点和上下相邻尺度对应的×个点共个点比较以确保在尺度空间和二维图像空间都检测到极值点。因为需要同相邻尺度进行比较所以在一组高斯差分图像中只能检测到两个尺度的极值点(如上述第二幅图中右图的五角星标识)而其它尺度的极值点检测则需要在图像金字塔的上一层高斯差分图像中进行。依次类推最终在图像金字塔中不同层的高斯差分图像中完成不同尺度极值的检测。当然这样产生的极值点并不都是稳定的特征点因为某些极值点响应较弱而且DOG算子会产生较强的边缘响应。三、关键点方向的分配为了使描述符具有旋转不变性需要利用图像的局部特征为给每一个关键点分配一个方向。利用关键点邻域像素的梯度及方向分布的特性可以得到梯度模值和方向如下:其中尺度为每个关键点各自所在的尺度。在以关键点为中心的邻域窗口内采样并用直方图统计邻域像素的梯度方向。梯度直方图的范围是~度其中每度一个方向总共个方向。直方图的峰值则代表了该关键点处邻域梯度的主方向即作为该关键点的方向。在计算方向直方图时需要用一个参数等于关键点所在尺度倍的高斯权重窗对方向直方图进行加权上图中用蓝色的圆形表示中心处的蓝色较重表示权值最大边缘处颜色潜表示权值小。如下图所示该示例中为了简化给出了方向的方向直方图计算结果实际sift创始人DavidLowe的原论文中采用方向的直方图。方向直方图的峰值则代表了该特征点处邻域梯度的方向以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性只保留峰值大于主方向峰值%的方向作为该关键点的辅方向。因此对于同一梯度值的多个峰值的关键点位置在相同位置和尺度将会有多个关键点被创建但方向不同。仅有%的关键点被赋予多个方向但可以明显的提高关键点匹配的稳定性。至此图像的关键点已检测完毕每个关键点有三个信息:位置、所处尺度、方向。由此可以确定一个SIFT特征区域。四、特征点描述符通过以上步骤对于每一个关键点拥有三个信息:位置、尺度以及方向。接下来就是为每个关键点建立一个描述符使其不随各种变化而改变比如光照变化、视角变化等等。并且描述符应该有较高的独特性以便于提高特征点正确匹配的概率。首先将坐标轴旋转为关键点的方向以确保旋转不变性。接下来以关键点为中心取×的窗口。上图图中左部分的中央黑点为当前关键点的位置每个小格代表关键点邻域所在尺度空间的一个像素箭头方向代表该像素的梯度方向箭头长度代表梯度模值图中蓝色的圈代表高斯加权的范围(越靠近关键点的像素梯度方向信息贡献越大)。然后在每×的小块上计算个方向的梯度方向直方图绘制每个梯度方向的累加值即可形成一个种子点如图右部分所示。此图中一个关键点由×共个种子点组成每个种子点有个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力同时对于含有定位误差的特征匹配也提供了较好的容错性。实际计算过程中为了增强匹配的稳健性Lowe建议对每个关键点使用×共个种子点来描述这样对于一个关键点就可以产生个数据即最终形成维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响再继续将特征向量的长度归一化则可以进一步去除光照变化的影响。五、最后一步:当两幅图像的SIFT特征向量生成后下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取上图中图像A中的某个关键点并找出其与图像B中欧式距离最近的前两个关键点在这两个关键点中如果最近的距离除以次近的距离少于某个比例阈值则接受这一对匹配点。降低这个比例阈值SIFT匹配点数目会减少但更加稳定。sift算法的逐步c实现ok上文搅了那么多的理论如果你没有看懂它咋办列没关系下面咱们来一步一步实现此sift算法即使你没有看到上述的理论慢慢的你也会明白sift算法到底是怎么一回事sift算法到底是怎么实现的。yeah请看:前期工作:在具体编写核心函数之前得先做几个前期的准备工作:、头文件:viewplaincopytoclipboardprint#ifdefCH#pragmapackage<opencv>#endif#ifndefEiC#include<stdioh>#include"stdlibh"#include"stringh"#include"malloch"#include"mathh"#include<asserth>#include<ctypeh>#include<timeh>#include<cvh>#include<cxcoreh>#include<highguih>#include<vector>#endif#ifdefEiC#defineWIN#endif、定义几个宏及变量以免下文函数中突然冒出一个变量而您却不知道怎么一回事:viewplaincopytoclipboardprint#defineNUMSIZE#defineGAUSSKERN#definePISigmaofbaseimageSeeDL'spaper#defineINITSIGMASigmaofeachoctaveSeeDL'spaper#defineSIGMAsqrt()NumberofscalesperoctaveSeeDL'spaper#defineSCALESPEROCTAVE#defineMAXOCTAVESintnumoctaves#defineCONTRASTTHRESHOLD#defineCURVATURETHRESHOLD#defineDOUBLEBASEIMAGESIZE#definepeakRelThresh#defineLENtemporarystorageCvMemStorage*storage=、然后咱们还得声明几个变量以及建几个数据结构(数据结构是一切程序事物的基础麻:D。):viewplaincopytoclipboardprintDatastructureforafloatimagetypedefstructImageSt{*金字塔每一层*floatlevelsigmaintlevelsigmalengthfloatabsolutesigmaCvMat*LevelCvMat是OPENCV的矩阵类其元素可以是图像的象素值}ImageLevelstypedefstructImageSt{*金字塔每一阶梯*introw,colDimensionsofimagefloatsubsampleImageLevels*Octave}ImageOctavesImageOctaves*DOGoctavesDOGpyrDOG算子计算简单是尺度归一化的LoG算子的近似。ImageOctaves*magthreshImageOctaves*magpyrImageOctaves*gradpyrkeypoint数据结构Listsofkeypointsarelinkedbythe"next"fieldtypedefstructKeypointSt{floatrow,col*反馈回原图像大小特征点的位置*floatsx,sy*金字塔中特征点的位置*intoctave,level*金字塔中特征点所在的阶梯、层次*floatscale,ori,mag*所在层的尺度sigma,主方向orientation(rangePI,PI)以及幅值*float*descrip*特征描述字指针:维或维等*structKeypointSt*next*Pointertonextkeypointinlist*}*Keypoint定义特征点具体变量Keypointkeypoints=用于临时存储特征点的位置等KeypointkeyDescriptors=用于最后的确定特征点以及特征描述字、声明几个图像的基本处理函数:图像处理基本函数其实也可以用OPENCV的函数代替但本文咱们选择了用c语言实现尽量不用第三方库的东西所以还得自己编写这些函数:viewplaincopytoclipboardprintCvMat*halfSizeImage(CvMat*im)缩小图像:下采样CvMat*doubleSizeImage(CvMat*im)扩大图像:最近临方法CvMat*doubleSizeImage(CvMat*im)扩大图像:线性插值floatgetPixelBI(CvMat*im,floatcol,floatrow)双线性插值函数voidnormalizeVec(float*vec,intdim)向量归一化CvMat*GaussianKernelD(floatsigma)得到维高斯核voidnormalizeMat(CvMat*mat)矩阵归一化float*GaussianKernelD(floatsigma,intdim)得到维高斯核在具体像素处宽度方向进行高斯卷积floatConvolveLocWidth(float*kernel,intdim,CvMat*src,intx,inty)在整个图像宽度方向进行D高斯卷积voidConvolveDWidth(float*kern,intdim,CvMat*src,CvMat*dst)在具体像素处高度方向进行高斯卷积floatConvolveLocHeight(float*kernel,intdim,CvMat*src,intx,inty)在整个图像高度方向进行D高斯卷积voidConvolveDHeight(float*kern,intdim,CvMat*src,CvMat*dst)用高斯函数模糊图像intBlurImage(CvMat*src,CvMat*dst,floatsigma)算法核心本程序中sift算法被分为以下五个步骤及其相对应的函数(可能表述与上或与前俩篇文章有所偏差但都一个意思):viewplaincopytoclipboardprintSIFT算法第一步:图像预处理CvMat*ScaleInitImage(CvMat*im)金字塔初始化SIFT算法第二步:建立高斯金字塔函数ImageOctaves*BuildGaussianOctaves(CvMat*image)建立高斯金字塔SIFT算法第三步:特征点位置检测最后确定特征点的位置intDetectKeypoint(intnumoctaves,ImageOctaves*GaussianPyr)voidDisplayKeypointLocation(IplImage*image,ImageOctaves*GaussianPyr)SIFT算法第四步:计算高斯图像的梯度方向和幅值计算各个特征点的主方向voidComputeGradDirecandMag(intnumoctaves,ImageOctaves*GaussianPyr)intFindClosestRotationBin(intbinCount,floatangle)进行方向直方图统计voidAverageWeakBins(double*bins,intbinCount)对方向直方图滤波确定真正的主方向boolInterpolateOrientation(doubleleft,doublemiddle,doubleright,double*degreeCorrection,double*peakValue)确定各个特征点处的主方向函数voidAssignTheMainOrientation(intnumoctaves,ImageOctaves*GaussianPyr,ImageOctaves*magpyr,ImageOctaves*gradpyr)显示主方向voidDisplayOrientation(IplImage*image,ImageOctaves*GaussianPyr)SIFT算法第五步:抽取各个特征点处的特征描述字voidExtractFeatureDescriptors(intnumoctaves,ImageOctaves*GaussianPyr)为了显示图象金字塔而作的图像水平、垂直拼接CvMat*MosaicHorizen(CvMat*im,CvMat*im)CvMat*MosaicVertical(CvMat*im,CvMat*im)特征描述点网格#defineGridSpacing主体实现ok以上所有的工作都就绪以后那么接下来咱们就先来编写main函数因为你一看主函数之后你就立马能发现sift算法的工作流程及其原理了。(主函数中涉及到的函数下一篇文章:一、教你一步一步用c语言实现sift算法、下咱们自会一个一个编写):viewplaincopytoclipboardprintintmain(void){声明当前帧IplImage指针IplImage*src=IplImage*image=IplImage*greyim=IplImage*DoubleSizeImage=IplImage*mosaic=IplImage*mosaic=CvMat*mosaicHorizen=CvMat*mosaicHorizen=CvMat*mosaicVertical=CvMat*imageMat=CvMat*tempMat=ImageOctaves*Gaussianpyrintrows,cols#defineImMat(ROW,COL)((float*)(imageMat>dataflimageMat>stepsizeof(float)*(ROW)))(COL)灰度图象像素的数据结构#defineImB(ROW,COL)((uchar*)(image>imageDataimage>widthStep*(ROW)))(COL)*#defineImG(ROW,COL)((uchar*)(image>imageDataimage>widthStep*(ROW)))(COL)*#defineImR(ROW,COL)((uchar*)(image>imageDataimage>widthStep*(ROW)))(COL)*storage=cvCreateMemStorage()读取图片if((src=cvLoadImage("streetjpg",))==)testjpgeinsteinpgmbackbmpreturn为图像分配内存image=cvCreateImage(cvSize(src>width,src>height),IPLDEPTHU,)greyim=cvCreateImage(cvSize(src>width,src>height),IPLDEPTHU,)DoubleSizeImage=cvCreateImage(cvSize(*(src>width),*(src>height)),IPLDEPTHU,)为图像阵列分配内存假设两幅图像的大小相同tempMat跟随image的大小imageMat=cvCreateMat(src>height,src>width,CVFC)转化成单通道图像再处理cvCvtColor(src,greyim,CVBGRGRAY)转换进入Mat数据结构,图像操作使用的是浮点型操作cvConvert(greyim,imageMat)doublet=(double)cvGetTickCount()图像归一化cvConvertScale(imageMat,imageMat,,)intdim=min(imageMat>rows,imageMat>cols)numoctaves=(int)(log((double)dim)log())金字塔阶数numoctaves=min(numoctaves,MAXOCTAVES)SIFT算法第一步预滤波除噪声建立金字塔底层tempMat=ScaleInitImage(imageMat)SIFT算法第二步建立Guassian金字塔和DOG金字塔Gaussianpyr=BuildGaussianOctaves(tempMat)t=(double)cvGetTickCount()tprintf("thetimeofbuildGaussianpyramidandDOGpyramidisfn",t(cvGetTickFrequency()*))#defineImLevels(OCTAVE,LEVEL,ROW,COL)((float*)(Gaussianpyr(OCTAVE)Octave(LEVEL)Level>dataflGaussianpyr(OCTAVE)Octave(LEVEL)Level>stepsizeof(float)*(ROW)))(COL)显示高斯金字塔for(inti=i<numoctavesi){if(i==){mosaicHorizen=MosaicHorizen((GaussianpyrOctave)Level,(GaussianpyrOctave)Level)for(intj=j<SCALESPEROCTAVEj)mosaicHorizen=MosaicHorizen(mosaicHorizen,(GaussianpyrOctave)jLevel)for(j=j<NUMSIZEj)mosaicHorizen=halfSizeImage(mosaicHorizen)}elseif(i==){mosaicHorizen=MosaicHorizen((GaussianpyrOctave)Level,(GaussianpyrOctave)Level)for(intj=j<SCALESPEROCTAVEj)mosaicHorizen=MosaicHorizen(mosaicHorizen,(GaussianpyrOctave)jLevel)for(j=j<NUMSIZEj)mosaicHorizen=halfSizeImage(mosaicHorizen)mosaicVertical=MosaicVertical(mosaicHorizen,mosaicHorizen)}else{mosaicHorizen=MosaicHorizen((GaussianpyriOctave)Level,(GaussianpyriOctave)Level)for(intj=j<SCALESPEROCTAVEj)mosaicHorizen=MosaicHorizen(mosaicHorizen,(GaussianpyriOctave)jLevel)for(j=j<NUMSIZEj)mosaicHorizen=halfSizeImage(mosaicHorizen)mosaicVertical=MosaicVertical(mosaicVertical,mosaicHorizen)}}mosaic=cvCreateImage(cvSize(mosaicVertical>width,mosaicVertical>height),IPLDEPTHU,)cvConvertScale(mosaicVertical,mosaicVertical,,)cvConvertScaleAbs(mosaicVertical,mosaic,,)cvSaveImage("GaussianPyramidofmejpg",mosaic)cvNamedWindow("mosaic",)cvShowImage("mosaic",mosaic)cvWaitKey()cvDestroyWindow("mosaic")显示DOG金字塔for(i=i<numoctavesi){if(i==){mosaicHorizen=MosaicHorizen((DOGoctavesOctave)Level,(DOGoctavesOctave)Level)for(intj=j<SCALESPEROCTAVEj)mosaicHorizen=MosaicHorizen(mosaicHorizen,(DOGoctavesOctave)jLevel)for(j=j<NUMSIZEj)mosaicHorizen=halfSizeImage(mosaicHorizen)}elseif(i==){mosaicHorizen=MosaicHorizen((DOGoctavesOctave)Level,(DOGoctavesOctave)Level)for(intj=j<SCALESPEROCTAVEj)mosaicHorizen=MosaicHorizen(mosaicHorizen,(DOGoctavesOctave)jLevel)for(j=j<NUMSIZEj)mosaicHorizen=halfSizeImage(mosaicHorizen)mosaicVertical=MosaicVertical(mosaicHorizen,mosaicHorizen)}else{mosaicHorizen=MosaicHorizen((DOGoctavesiOctave)Level,(DOGoctavesiOctave)Level)for(intj=j<SCALESPEROCTAVEj)mosaicHorizen=MosaicHorizen(mosaicHorizen,(DOGoctavesiOctave)jLevel)for(j=j<NUMSIZEj)mosaicHorizen=halfSizeImage(mosaicHorizen)mosaicVertical=MosaicVertical(mosaicVertical,mosaicHorizen)}}考虑到DOG金字塔各层图像都会有正负所以必须寻找最负的以将所有图像抬高一个台阶去显示doubleminval=doublemaxval=cvMinMaxLoc(mosaicVertical,minval,maxval,,,)if(minval<)cvAddS(mosaicVertical,cvScalarAll(()*minval),mosaicVertical,)mosaic=cvCreateImage(cvSize(mosaicVertical>width,mosaicVertical>height),IPLDEPTHU,)cvConvertScale(mosaicVertical,mosaicVertical,(maxvalminval),)cvConvertScaleAbs(mosaicVertical,mosaic,,)cvSaveImage("DOGPyramidofmejpg",mosaic)cvNamedWindow("mosaic",)cvShowImage("mosaic",mosaic)cvWaitKey()SIFT算法第三步:特征点位置检测最后确定特征点的位置intkeycount=DetectKeypoint(numoctaves,Gaussianpyr)printf("thekeypointsnumberaredn",keycount)cvCopy(src,image,)DisplayKeypointLocation(image,Gaussianpyr)cvPyrUp(image,DoubleSizeImage,CVGAUSSIANx)cvNamedWindow("image",)cvShowImage("image",DoubleSizeImage)cvWaitKey()cvDestroyWindow("image")SIFT算法第四步:计算高斯图像的梯度方向和幅值计算各个特征点的主方向ComputeGradDirecandMag(numoctaves,Gaussianpyr)AssignTheMainOrientation(numoctaves,Gaussianpyr,magpyr,gradpyr)cvCopy(src,image,)DisplayOrientation(image,Gaussianpyr)cvPyrUp(image,DoubleSizeImage,CVGAUSSIANx)cvNamedWindow("image",)cvResizeWindow("image",*(image>width),*(image>height))cvShowImage("image",image)cvWaitKey()SIFT算法第五步:抽取各个特征点处的特征描述字ExtractFeatureDescriptors(numoctaves,Gaussianpyr)cvWaitKey()销毁窗口cvDestroyWindow("image")cvDestroyWindow("mosaic")释放图像cvReleaseImage(image)cvReleaseImage(greyim)cvReleaseImage(mosaic)cvReleaseImage(mosaic)return}更多见下文:一、教你一步一步用c语言实现sift算法、下。本文完。版权声明:本文版权归本人和CSDN共同拥有。转载请注明出处及作者本人。侵犯版权者无论任何人任何网站、永久追踪、永久谴责、永久追究法律责任的权利。July、二零一一年三月十二日声明。九(再续)、教你一步一步用c语言实现sift算法、下作者:July、二零一一年三月十二日出处:http:blogcsdnnetvJULYv。参考:RobHess维护的sift库环境:windowsxpvc条件:c语言实现。说明:本BLOG内会陆续一一实现所有经典算法。本文接上教你一步一步用c语言实现sift算法、上而来:函数编写ok接上文咱们一个一个的来编写main函数中所涉及到所有函数这也是本文的关键部分:viewplaincopytoclipboardprint下采样原来的图像返回缩小倍尺寸的图像CvMat*halfSizeImage(CvMat*im){unsignedinti,jintw=im>colsinth=im>rowsCvMat*imnew=cvCreateMat(h,w,CVFC)#defineIm(ROW,COL)((float*)(im>dataflim>stepsizeof(float)*(ROW)))(COL)#defineImnew(ROW,COL)((float*)(imnew>dataflimnew>stepsizeof(float)*(ROW)))(COL)for(j=j<hj)for(i=i<wi)Imnew(j,i)=Im(j*,i*)returnimnew}上采样原来的图像返回放大倍尺寸的图像CvMat*doubleSizeImage(CvMat*im){unsignedinti,jintw=im>cols*inth=im>rows*CvMat*imnew=cvCreateMat(h,w,CVFC)#defineIm(ROW,COL)((float*)(im>dataflim>stepsizeof(float)*(ROW)))(COL)#defineImnew(ROW,COL)((float*)(imnew>dataflimnew>stepsizeof(float)*(ROW)))(COL)for(j=j<hj)for(i=i<wi)Imnew(j,i)=Im(j,i)returnimnew}上采样原来的图像返回放大倍尺寸的线性插值图像CvMat*doubleSizeImage(CvMat*im){unsignedinti,jintw=im>cols*inth=im>rows*CvMat*imnew=cvCreateMat(h,w,CVFC)#defineIm(ROW,COL)((float*)(im>dataflim>stepsizeof(float)*(ROW)))(COL)#defineImnew(ROW,COL)((float*)(imnew>dataflimnew>stepsizeof(float)*(ROW)))(COL)filleverypixelsowedon'thavetoworryaboutskippingpixelslaterfor(j=j<hj){for(i=i<wi){Imnew(j,i)=Im(j,i)}}*ABCEFGHIJpixelsACHJarepixelsfromoriginalimagepixelsBEGIFareinterpolatedpixels*interpolatepixelsBandIfor(j=j<hj=)for(i=i<wi=)Imnew(j,i)=*(Im(j,i)Im(j,i))interpolatepixelsEandGfor(j=j<hj=)for(i=i<wi=)Imnew(j,i)=*(Im(j,i)Im(j,i))interpolatepixelFfor(j=j<hj=)for(i=i<wi=)Imnew(j,i)=*(Im(j,i)Im(j,i)Im(j,i)Im(j,i))returnimnew}双线性插值返回像素间的灰度值floatgetPixelBI(CvMat*im,floatcol,floatrow){intirow,icolfloatrfrac,cfracfloatrow=,row=intwidth=im>colsintheight=im>rows#defineImMat(ROW,COL)((float*)(im>dataflim>stepsizeof(float)*(ROW)))(COL)irow=(int)rowicol=(int)colif(irow<||irow>=height||icol<||icol>=width)returnif(row>height)row=heightif(col>width)col=widthrfrac=(row(float)irow)cfrac=(col(float)icol)if(cfrac<){row=cfrac*ImMat(irow,icol)(cfrac)*ImMat(irow,icol)}else{row=ImMat(irow,icol)}if(rfrac<){if(cfrac<){row=cfrac*ImMat(irow,icol)(cfrac)*ImMat(irow,icol)}else{row=ImMat(irow,icol)}}returnrfrac*row(rfrac)*row}矩阵归一化voidnormalizeMat(CvMat*mat){#defineMat(ROW,COL)((float*)(mat>dataflmat>stepsizeof(float)*(ROW)))(COL)floatsum=for(unsignedintj=j<mat>rowsj)for(unsignedinti=i<mat>colsi)sum=Mat(j,i)for(j=j<mat>rowsj)for(unsignedinti=i<mat>rowsi)Mat(j,i)=sum}向量归一化voidnormalizeVec(float*vec,intdim){unsignedintifloatsum=for(i=i<dimi)sum=vecifor(i=i<dimi)veci=sum}得到向量的欧式长度范数floatGetVecNorm(float*vec,intdim){floatsum=for(unsignedinti=i<dimi)sum=veci*vecireturnsqrt(sum)}产生D高斯核float*GaussianKernelD(floatsigma,intdim){unsignedintiprintf("GaussianKernelD():Creatingxdvectorforsigma=fgaussiankerneln",dim,sigma)float*kern=(float*)malloc(dim*sizeof(float))floats=sigma*sigmaintc=dimfloatm=(sqrt(*CVPI)*sigma)doublevfor(i=i<(dim)i){v=m*exp((*i*i)(*s))kernci=vkernci=v}normalizeVec(kern,dim)for(i=i<dimi)printf("f",kerni)printf("n")returnkern}产生D高斯核矩阵CvMat*GaussianKernelD(floatsigma){intdim=(int)max(f,GAUSSKERN*sigma)intdim=(int)max(f,*GAUSSKERN*sigmaf)makedimoddif(dim==)dimn",dim,dim,sigma)CvMat*mat=cvCreateMat(dim,dim,CVFC)#defineMat(ROW,COL)((float*)(mat>dataflmat>stepsizeof(float)*(ROW)))(COL)floats=sigma*sigmaintc=dimprintf("ddn",matsize(),matsize())floatm=(sqrt(*CVPI)*sigma)for(inti=i<(dim)i){for(intj=j<(dim)j){printf("dddn",c,i,j)floatv=m*exp((*i*i*j*j)(*s))Mat(ci,cj)=vMat(ci,cj)=vMat(ci,cj)=vMat(ci,cj)=v}}normalizeMat(mat)returnmat}x方向像素处作卷积floatConvolveLocWidth(float*kernel,intdim,CvMat*src,intx,inty){#defineSrc(ROW,COL)((float*)(src>dataflsrc>stepsizeof(float)*(ROW)))(COL)unsignedintifloatpixel=intcolintcen=dimprintf("ConvolveLoc():Applyingconvoluationatlocation(d,d)n",x,y)for(i=i<dimi){col=x(icen)if(col<)col=if(col>=src>cols)col=src>colspixel=kerneli*Src(y,col)}if(pixel>)pixel=returnpixel}x方向作卷积voidConvolveDWidth(float*kern,intdim,CvMat*src,CvMat*dst){#defineDST(ROW,COL)((float*)(dst>datafldst>stepsizeof(float)*(ROW)))(COL)unsignedinti,jfor(j=j<src>rowsj){for(i=i<src>colsi){printf("d,dn",i,j)DST(j,i)=ConvolveLocWidth(kern,dim,src,i,j)}}}y方向像素处作卷积floatConvolveLocHeight(float*kernel,intdim,CvMat*src,intx,inty){#defineSrc(ROW,COL)((float*)(src>dataflsrc>stepsizeof(float)*(ROW)))(COL)unsignedintjfloatpixel=intcen=dimprintf("ConvolveLoc():Applyingconvoluationatlocation(d,d)n",x,y)for(j=j<dimj){introw=y(jcen)if(row<)row=if(row>=src>rows)row=src>rowspixel=kernelj*Src(row,x)}if(pixel>)pixel=returnpixel}y方向作卷积voidConvolveDHeight(float*kern,intdim,CvMat*src,CvMat*dst){#defineDst(ROW,COL)((float*)(dst>datafldst>stepsizeof(float)*(ROW)))(COL)unsignedinti,jfor(j=j<src>rowsj){for(i=i<src>colsi){printf("d,dn",i,j)Dst(j,i)=ConvolveLocHeight(kern,dim,src,i,j)}}}卷积模糊图像intBlurImage(CvMat*src,CvMat*dst,floatsigma){float*convkernelintdim=(int)max(f,*GAUSSKERN*sigmaf)CvMat*tempMatmakedimoddif(dim==)dimtempMat=cvCreateMat(src>rows,src>cols,CVFC)convkernel=GaussianKernelD(sigma,dim)ConvolveDWidth(convkernel,dim,src,tempMat)ConvolveDHeight(convkernel,dim,tempMat,dst)cvReleaseMat(tempMat)returndim}五个步骤ok接下来进入重点部分咱们依据上文介绍的sift算法的几个步骤来一一实现这些函数。为了版述清晰再贴一下主函数顺便再加强下对sift算法的五个步骤的认识:、SIFT算法第一步:图像预处理CvMat*ScaleInitImage(CvMat*im)金字塔初始化、SIFT算法第二步:建立高斯金字塔函数ImageOctaves*BuildGaussianOctaves(CvMat*image)建立高斯金字塔、SIFT算法第三步:特征点位置检测最后确定特征点的位置intDetectKeypoint(intnumoctaves,ImageOctaves*GaussianPyr)、SIFT算法第四步:计算高斯图像的梯度方向和幅值计算各个特征点的主方向voidComputeGradDirecandMag(intnumoctaves,ImageOctaves*GaussianPyr)、SIFT算法第五步:抽取各个特征点处的特征描述字voidExtractFeatureDescriptors(intnumoctaves,ImageOctaves*GaussianPyr)ok接下来一一具

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/463

十五个经典算法研究与总结、目录+索引(by_...

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利