图像处理检测横向运动

2013-05-25 16:44:41 lwjaiyjk3 阅读数 2885
  • 综合布线系统优点

    网规下午案例分析出题思路紧跟技术发展脉搏,对热点技术都有所涉及。本课程对网规下午案例分析中的考点做了详细的讲解,通过在重要考点中穿插历年真题的强化讲解,帮助考生掌握考点的同时实时的感受了网规案例分析...

    13人学习 徐朋
    免费试看

你好!

    我虽然从事图像处理研究,但做的东西比较杂,也不是很深入。只能给你一些粗浅的建议。

    我感觉图像处理现在的发展有两个层次,一个是算法研究,需要较多的数学基础,如偏微分方程(PDE)、各种空间变换(小波、曲波、剪切波等)。这些领域研究文献特别多,但要想出点新东西确实比较难。如果能深入研究一下,写出来的论文有一定理论深度,估计比较容易被录用。

   另一个层次就是从横向拓展,找新的应用,也别的技术相结合,关键是找到研究内容,算法上只是将现有理论应用。最常见的与模式识别算法相结合,如人脸检测、行人检测、视频中运动检测,等等。只有点子新,文章应该也比较容易录用。

   王老师:

      你好,首先感谢你在繁忙的工作和学习中抽出时间来阅读我的邮件。我是云

南一所地方院校的教师,最近我在学习数字图像处理,看了冈萨雷斯的两本教材

,知道图像增强、恢复、压缩、编码、分割等基本概念,但觉得很多详细的内容

其实没看太懂。也不知道要做图像处理方面的研究需要学哪些东西。看了网上的

一些讨论说现在图像处理方面的理论研究已经很难做出新的东西,不知王老师怎

么看,现在做图像处理哪个方面比较容易发文章。我最近要选在职硕士的毕业论

文题目,不知道从何入手,希望得到王老师的一些建议。在此不甚感激!

       我是从《中国图象图形学报》上看到王老师的文章和邮箱的,于是冒昧的

给你发了邮件,打扰之处还请见谅。

 

 

图像处理是个老问题,也是个难问题。图像处理方面的研究以及做了很多很多年了,看现在很多问题都没解决。

举个简单的例子,比如去噪,到现在为止,都还没有完全研究透。但要提出更好的方案,也比较难。还有比如自然图像的模型问题,至少到现在为止还没有一个比较好的模型能够描述大量的自然图像。有的模型也是对一些情况适用。

因此,做图像处理还是有得做的,可也不是那么容易做的,就像上面的老师的回复,需要比较深的理论基础,尤其是数学,信号处理和统计方面的

 

研究的内容和研究的人员都比较多,不管研究什么,只要能提出自己的见解,或者在别人的基础上进行改进,应该都是可以的

 

图像分辨率增强,比如一个小尺寸图片放大数倍又要保证放大的效果,具体应用如人脸分辨率增强,应用于监控视频人脸检测等环境.

这也是一位老师给我的意见,我查了下相关分辨率增强的的文献,这方面中文的还挺少.有对这一方面了解的虫子来聊聊.

 

图像分辨率增强,比如一个小尺寸图片放大数倍又要保证放大的效果,具体应用如人脸分辨率增强,应用于监控视频人脸检测等环境.

这也是一位老师给我的意见,我查了下相关分辨率增强的的文献,这方面中文的还挺少.有 ...

好像做多分辨率图像增强的也有不少吧

 

创新的东西真的不是太容易做的。本人感觉把图像处理的理论和其他学科相结合才是能有最大发挥的途径。

 

我觉得这位老师的回信还是很中肯的,基本上多媒体领域(包括视频、音频等)都是这两条思路。

个人感觉:

如果你是学数学出身、对媒体本身感觉不明显,可以沿着第一条思路走,毕竟大部分学计算机出身的人理论功底都不如你,套用一些数学上常用的变换或优化就可能就会让方法看起来很新颖;

如果你是学计算机出身、数学功底一般的话,可以沿着第二条思路走,只要能找到一个有趣的应用,里面用的方法不算太土,就是很不错的文章了。

当然,如果你两方面都很强,就可以随心所欲了,横着走都没事。

PS:图形图象学报也许是国内在图像处理方面最好的期刊了,但如果想做研究,还是多关注一下知名国际会议,例如MM,ICIP……文章内容要新很多。

 

我觉得这位老师的回信还是很中肯的,基本上多媒体领域(包括视频、音频等)都是这两条思路。

个人感觉:

如果你是学数学出身、对媒体本身感觉不明显,可以沿着第一条思路走,毕竟大部分学计算机出身的人理论功底 ...

感谢谢你的回复。我是没法横着走了。数学不好,计算机也不行。郁闷得很,搞科研太难,很不适合我呀。呵呵

 

除了极少数人外,大部分人在本科刚毕业的时候,这两方面都不会太突出。只要你在同年级中还算可以,那么就不会有太大问题。

如果两个方面都比较欠缺,但又很想搞研究的话,建议先趁年轻补数学。虽然开始发文章会慢一些,但后面看文章、写文章都会快很多,少走很多弯路,磨刀不误砍柴工。

如果不是很想搞科研,就去工作吧。其实工作蛮好的,起码挣钱多,做到后来也不是很辛苦。

 

哎,我们做水印的更难啊

 

我也是做算法的,比较难做啊,而且需要静下心来看好多东西,嗨嗨。。只能努力了啊。。

中国图象图形学报很不错。但不是EI核心。

 

中国图象图形学报很不错。但不是EI核心。

能投到中国图象图形学报我觉得就很厉害了,因为我真的实在是菜鸟,虽然每天都在学习了,但还是什么都不懂,尝试写了第一篇论文投了一底层次的期刊,被要求改了下格式后被录用了,结果版面费1700元,嘿死人,算了,不交了.以后真能投到核心的1700就1700吧.

 

图像分辨率增强,比如一个小尺寸图片放大数倍又要保证放大的效果,具体应用如人脸分辨率增强,应用于监控视频人脸检测等环境.

这也是一位老师给我的意见,我查了下相关分辨率增强的的文献,这方面中文的还挺少.有 ...

这叫超分辨率重建,是一个不错的研究方向。

 

这叫超分辨率重建,是一个不错的研究方向。

非常感谢你的提示!之前我用"分辨率增强"搜索文章,找到的很少。经你提示后,发现这方面的文献还真是不少.

 

这叫超分辨率重建,是一个不错的研究方向。

这个研究方向已经有好多年了吧,记得04年一次学术交流会上很多人在做这个啊

 

额,我刚刚学习数字图像处理这门课程,看到你们所讲的好有感触啊

 

图像处理现在确实很难进一步发展,同样说明需要发展;自身理论创新不易,故国人大部分做应用。我认为图像处理瓶颈在于不像一维信号有FFT、Wavelet等的分解重构工具,图像也需要分解重构,图像处理需要自己的工具。但是现在往往图像处理仍使用一维信号分析方法,这接近自然本身的面目吗?希望大家能用图像的观点来思考图像,幸运的是已经有些科学家这样做了,比如Beamlet、Ridgelet等。

 

图像处理现在确实很难进一步发展,同样说明需要发展;自身理论创新不易,故国人大部分做应用。我认为图像处理瓶颈在于不像一维信号有FFT、Wavelet等的分解重构工具,图像也需要分解重构,图像处理需要自己的工具。 ...

呵呵,应该是只大牛

 

有一定道理!

 

图像处理现在确实很难进一步发展,同样说明需要发展;自身理论创新不易,故国人大部分做应用。我认为图像处理瓶颈在于不像一维信号有FFT、Wavelet等的分解重构工具,图像也需要分解重构,图像处理需要自己的工具。 ...

2013-12-24 12:32:07 zmycoco2 阅读数 6874
  • 综合布线系统优点

    网规下午案例分析出题思路紧跟技术发展脉搏,对热点技术都有所涉及。本课程对网规下午案例分析中的考点做了详细的讲解,通过在重要考点中穿插历年真题的强化讲解,帮助考生掌握考点的同时实时的感受了网规案例分析...

    13人学习 徐朋
    免费试看


本科毕业设计(论文)开题报告

 


         

课题名称

基于数字图像处理的车牌定位和分割的研究

毕业设计的内容和意义 

采用数字图像处理的原理和技术,进行车牌区域的准确定位和分割的研究,给出相应的算法,并通过VC编程实现。

毕业设计的具体内容:

1.熟悉和了解数字图像处理的原理和技术。

2.熟悉VC的编程和调试方法。

3.掌握数字图像处理的常规算法,尤其对图像的几何校正,边缘检测、区域定位和图像分割原理和算法要有深入的了解。

4. 完成车牌区域的准确定位和分割的设计方案,给出相应的算法,并通过编程实现。

本课题研究的意义:

在交通路口的违章监视,在高速公路收费入口,在涵洞、桥梁的入口以及在停车场和加油站的管理中,都需要对汽车牌照进行记录,而目前这些工作大多数都是由人工完成的,工作量很大,有时也难免会出现错误,如果改用智能系统进行自动的检测和识别,则会大大提高工作的速度,降低管理人员的工作量,提高服务的效率与质量。

在国内现有技术的基础之上进一步研究汽车牌照智能识别技术实现对实时采集到的汽车牌照图像进行分析,准确定位分割、提取出图像中的汽车牌照,并快速自动智能地识别出汽车牌照,还可以全面消除人为因素,因而对车牌识别技术的研究和应用系统开发具有重要的现实意义。

车牌自动识别系统从上一世纪80年代开始进入应用研究阶段、这个阶段的研究没有形成完整的系统体系,而是就某一具体的问题进行研究,通常采用简单的图像处理方法来解决。进入20世纪90年代后,随着计算机视觉的发展和计算机性能的提高,开始出现车牌识别的系统化研究。中国、美国、日本、法国等国家相继投入大量的人力、物力进行应用研究,随着社会的进一步发展,交通状况急需更快的发展来适应经济发展需要,各国更加关注对该系统的研究和应用。

文献[1]中阐述了智能交通系统的概念于1990年由美国智能交通学会(ITS America,当时名称为IVHS America)提出,并在世界各国大力推广。经过10多年的推广、试行和发展,智能交通系统目前己在世界上经济发达国家和经济较为发达国家的一些都市及高速公路系统中实施。实践证明,迄今为止,在美国、欧洲、亚洲都已有成功应用的范例。在国外,以色列Hi-Tech公司的See/Car System系列,香港Asia VisionTechnology公司的VECON产品,新加坡Optasia公司的VLPRS系列都是比较成熟的产品。虽然国外汽车牌照识别系统研究工作己有一定进展,但并不适合我国汽车牌照识别,其原因主要有我国车牌本身的特点决定的。我国车辆牌照缺乏统一的标准,根据不同汽车、车型、用途,规定了多种牌照格式(例如分为军车、警车、普通车等);悬挂位置随机,使得车牌识别过程中缺乏规律,使车牌定位分割、字符切分难度增加,准确性降低;车牌长期暴露易受污损,使得车牌区域模糊不清,易发生粘连、断裂等现象,在国外发达国家不允许由于环境、道路或人为因素造成汽车牌照污染严重的车辆上路行驶;我国车辆牌照由汉字、字母和数字组成,汉字的识别与字母和数字的识别有很大的不同,从而增加了识别的难度;其他国家汽车牌照的底色和字符颜色统一,只有对比度较强的两种颜色,而我国汽车牌照底色和字符有蓝/白、黑/红、黑/白等多种颜色组合;还有设置的营运牌照及张贴的广告信息,容易在车牌定位时产生干扰、误定位;车牌附近环境恶劣,往往有复杂的外形及安全杠等,不利于快速定位。

文献[2]中阐述了国内在90年代也开始了车牌识别的研究。由于中国车牌与国外的差异,加上车牌上汉字的存在。所以照搬国外的技术并不完全可行。对于国内的己应用系统中较成功的有浙江大学开发的基于web模式的LPR系统,中科院自动化研究所汉王科技公司开发的“汉王眼车牌识别系统”。另外,亚洲视觉科技有限公司、深圳吉通电子有限公司、中国信息产业部下属的中智交通电子有限公司等也有自己的产品,另外西安交通大学的图像处理和识别研究室、上海交通大学的计算机科学和工程系、清华大学人工智能国家重点实验室等也做过类似的研究。目前这些系统普遍存在的问题有:全天候识别率并不稳定,

特别是在夜间,或不良天气下识别率会降低到50%左右。还有许多其它问题需要解决,如国内许多论文谈及已实现的系统,都是在对近似理想条件下的汽车图像识别,对于车牌倾斜角度很大,车牌上字符模糊等情况提出的解决办法甚少。因此这样的系统即使识别率较高,也是建立在苛刻的特定的拍照环境下的。车牌自动识别系统产品中还存在一些不足,因而LPR技术的研究还有许多工作要做:从目前一些产品的性能指标可以看出,LPR系统的识别率和识别速度有待提高。研究高速、准确的定位与识别算法是当前的主要任务。上述产品中所使用的汽车图像均为灰度图像,而车牌本身是彩色物体,其底色和字符颜色为有限的几种,具有明显的颜色特征,车牌定位及字符的分割和识别没有用到颜色特征,采用彩色图像模式,目前的算法也很少涉及颜色特征,这在一定程度上影响了系统的性能。对于车牌彩色信息的利用有待于深入研究。另外目前只能处理单个车牌的汽车图像,对于一幅图像中多个车牌的识别则无能为力。这使得目前对多个车道进行监控时,需要多套摄像设备和车牌识别所需的计算机。如能深入研究一幅图像中多个车牌的识别问题,则可降低系统成本,提高工作效率。

所以从技术上对牌照自动识别系统进行进一步的改进完善是很有必要的。在软件上这主要要求提高字符识别率,同时提高软件的运行速度,提高实时性。相信随着研究的深入,LPR技术定会走向成熟。

文献[3]中阐述了目前国内外汽车牌照定位与识别技术主要采用软硬结合方式和软件方式两种技术方案。所谓软硬结合方式,就是首先通过专用的图像抓拍设备获取一幅适合于计算机识别汽车牌照的高质量图像,然后用软件和硬件结合的方式对所获取的专用图像进行牌照识别,它的最大优点就是识别率高,能够全天候工作。所谓软件方式,就是通过识别软件对普通的车辆图像进行牌照识别,它的最大优点就是成本低,通用性好。车牌自动识别系统主要有摄像装置、视频采集接口、计算机和辅助照明装置组成。计算机通过视频采集接口采集摄像装置摄入的视频图像,经处理和识别得到车牌号。在自然光较暗影响识别效果时,由辅助照明装置提供摄像光源。硬件部分包括车辆感应器,高速摄影装置等。车辆感应器的功能是感应车辆的到来,触发高速摄影装置在一定时间内动作抓拍图像。如在高速公路上,通常在收费处前方公路两侧埋置电磁感应圈,当车辆驶入感应区内,电磁感应圈产生电流,触发摄影头工作。除此之外,还有激光红外线车辆感应器等。埋置电磁感应线圈的缺点是工程量大,而激光红外线车辆感应器容易引起二次触发,即脱车引起的触发拍照。动态车牌图像捕捉系统主要由高分辨率摄像机,多光谱照明灯,图像处理器及控制器组成。它根据亮度变化,即可完成车牌的抓拍。相比而言,动态车牌图像捕捉

系统可以在白天和夜间等多种情况下工作,清楚捕捉高速运动中的汽车牌照图像,其效果不受日光,车灯等环境因素的影响。大量实验表明该方案是最理想的解决可靠性的方案。

图像输入通常由硬件完成,牌照定位与字符识别通常由软件完成。

文献[4][5][6]中阐述了日前存在的大量的车牌定位算法,选择一个好的定位算法成为车牌识别的一个关键问题。文中针对基于投影法的车牌定位算法。在VC平台上对车牌图像进行预处理后,再通过找点和标出矩形即可实现车牌的定位。通过大量的试验得出,本算法可以解决车牌定位时遇到的绝大部分问题,具有较高的研究价值和社会经济效益。

文献[7]中对智能交通系统的核心技术——汽车牌照识别技术进行了研究,在图像处理技术的基础上,着重研究了车牌区域定位技术,析了日前有代表性的车牌定位方法,介绍了利用粒子图像测速关联PIV(Particle Image Velocimeter)算法原理,提出了一种采用车牌字符笔画2个边缘互相关值最大的方法进行车牌定位的算法,准确而快速地检出了车牌区域,为后续车牌字符识别打下了很好的基础。

文献[8][9][10][11]中阐述了针对不同尺寸车牌图像的定位问题,提出了一种新的自适应车牌定位方法。该方法首先根据车牌区域的共性来提取图像的纵向边缘;然后由车牌区纵向纹理和边缘密度等特征,采用一系列步骤自适应去除干扰边缘来保留类车牌特征区域;最后通过横向形态学运算使类车牌区闭合,以有效地克服以往形态学结构元素难以随车牌尺寸变化自适应选取的问题;同时提出了根据场景实际情况,选用灰度调整和颜色来判别模块的观点。通过实际场景中大量车牌样本的验证结果表明,该算法不仅准确率较高,而且自适应性良好,具有实用价值。

参考文献:

[1] 刘允才.智能交通国际发展概况和国内优先考虑的课题[J].公路,2001,11(11):26-34.

[2] Liu Jilin,Ma Hongqing.A High Performance License Plate Recognition System Basedon the Web Technique[D].

[3] 郑南宁,张西宁,戴莹,朱海安.行驶车辆牌照自动识别系统[J].西安交通大学学报,1991,l:43-53.

[4] 张俭鸽,李娜.车牌定位在VC中的实现[J].中国科技信息,2009, (13):123-124.

[5] 郑影.基于VC++的汽车牌照定位与识别系统的设计[D].吉林大学硕士学位论文,2009.

[6] 张宏林.精通Visual C++数字图像模式识别技术及工程实践[M]:第2版.北

京:人民邮电出版社,2008.

[7] 张丽伟,张晶.基于图像处理的车牌定位方法的研究[J].长春工程学院学报(自然科学版),2009,10(2):100-103.

[8] 李宇成,阴亮.基于图像的运动车辆速度测量[J].北方工业大学学报,2008(3):32—36.

[9] 王广宇.汽车牌照识别系统综述[J].郑州轻工业学院学报(自然科学报),2001,16(2):47-50.

[10] 李波,曾致远,周建中.一种自适应车牌图像定位新方法[J].中国图象图形学报,2009,14(10):1978-1984.

[11]Kenneth.R.Castleman.Digital Image Processing,Prentice Hall.1998,4.

本课题主要利用数字图像处理的原理和技术,完成车牌区域的准确定位和分割的设计方案,研究相应的算法,并通过编程实现。

其具体内容如下:

1、理解和掌握数字图像处理的原理和技术,能熟练运用数字图像处理的常规算法。

2、深入研究预处理中的灰度化、二值化、背景削弱、中值滤波等原理,以及图像的灰度变换空间滤波处理等,探索车牌定位常用的方法,研究现在流行的一些算法,总结出其优点和缺点,能够继承传统方法的优点,并加以改进和提高。

3、掌握算法实现的编程语言,熟练运用设计实现的平台Visual C++ 6.0,提高查阅资料的能力,并通过编程实现车牌的定位。

4、研究一种新型的车牌定位方法,本课题采用多层次分割的思想,每次分割都尽可能地减少分析范围,经过多次分割后最终定位出车牌区域。

第1-2周     收集资料,熟悉课题,确定系统总体研究方案。

第3周        熟悉资料,写出开题报告。

第4—5周     熟悉数字图像处理的主要内容。

第6—7周     熟悉VC语言的编程和调试方法。

第8—9周     熟悉并掌握数字图像的常规算法,重点研究边缘检测和区域分割等算法。

第10-11周   用VC编程实现并调试各个处理模块。

第12-13周   对整个系统进行软件联调,整理设计成果。

第14周       撰写论文。

第15周       修改论文,准备答辩。

第16周       毕业答辩。

在车辆识别系统中,牌照区域定位是影响车牌识别系统性能的重要因素之一车牌定位准确与否直接影响字符识别的准确率,以往的拍照定位重要包括:J.Barroso等基于提出的基于水平线搜索的定位方法;R.Parisi提出的机遇TFC变换的频域分析法;Charl Coeitzee等提出的基于Niblack二值化算法及自适应边界搜索算法的定位方法。这些方法或者对背景比较复及光照条件比较敏感,或者定位速度比较慢,为了克服这些缺陷,本课题提出了基于特征的车辆牌照实时定位算法和多层次分割算法,能够更高效地实现车牌的准确定位和分割,充分体现了该系统的实时性。

指导教师

意  见

指导教师签名:

         年   月   日

教研室意见

  主任签名:

      年   月   日

系部意见

 

                                         教学主任签名:

                                                 年   月   日

 

2019-02-27 16:06:02 weixin_42152656 阅读数 2849
  • 综合布线系统优点

    网规下午案例分析出题思路紧跟技术发展脉搏,对热点技术都有所涉及。本课程对网规下午案例分析中的考点做了详细的讲解,通过在重要考点中穿插历年真题的强化讲解,帮助考生掌握考点的同时实时的感受了网规案例分析...

    13人学习 徐朋
    免费试看

摘要:医学图像分割是决定医学图像在临床诊疗中能否提供可靠依据的关键问题。医学图像分割技术的发展不仅影响到医学图像处理中其他相关技术的发展,如可视化、三维重建等,而且在生物医学图像的分析中也占有极其重要的地位。近年来,由于深度学习算法在医学图像分割中的应用, 医学图像分割技术取得了显著的进展。


MR图像

 

磁共振成像(MRI)是无线电成像领域中使用最广泛的技术。作为一种动态且灵活的技术,MRI可以实现多变的图像对比度,该过程的实现是通过使用不同的脉冲序列和改变成像参数对应纵向松弛时间(T1)和横向松弛时间(T2),T1加权和T2加权成像的信号强度与特定组织的特征有关[10]。MR成像中,图像的对比度依赖于相位对比脉冲序列参数,最常见的脉冲序列是T1加权和T2加权自旋回波序列[12]。通过MR成像可以观察大脑、肝脏、胸、腹部和骨盆的结构细节,这有利于诊断检测或治疗[13]。

MRI对软组织有很好的成像能力;有非常高的分辨率;具有较高的信噪比;利用不同的脉冲序列可以得到对比度多变的多通道图像,进而用于不同解剖结构的目标分割和分类[14]。然而,在MRI中存在多种伪影,如部分容积、随机场噪声、强度不均匀性、梯度、运动、环绕、吉布斯振铃、磁化性等[15]。此外,相比于CT图像,MRI的获取需要相当长的时间,且通常条件下很难得到统一的图像质量。
 

CT图像

医学CT成像设备使用X射线(一种电磁波)得到人体的结构和功能信息。CT影像是基于X射线吸收剖面的重构图像,由于不同物质和组织吸收X射线能力不同,因此X射线可用于诊断[16]。CT成像作为当前多类疾病实体诊断的金标准,广泛应用于大脑、肝脏、胸部、腹部、骨盆、脊柱等身体部位以及CT血管造影的早期诊断筛查[17]。但是与MR图像相比较,CT图像敏感性和特异性相对较差。

CT成像中的伪影[18]包括:部分容积效应、条形伪影、运动伪影、束硬化伪影、环状伪影、金属伪影等。由于这些伪影的存在给CT图像分割带来了一定的难度,不同组织部位分割精度也不一样[19]。
 

 医学图像分割的特点
医学图像分割是医学图像处理与分析领域的复杂而关键的步骤,其目的是将医学图像中具有某些特殊含义的部分分割出来,并提取相关特征,为临床诊疗和病理学研究提供可靠的依据,辅助医生做出更为准确的诊断[20]。图像分割过程是把图像分割成多个区域,这些区域内部有类似的性质,如灰度、颜色、纹理、亮度、对比度等。医学图像分割的目标是(以放射治疗为例)[21]:(1)研究解剖结构;(2)识别感兴趣区域(即定位肿瘤、病变和其他异常组织);(3)测量组织体积;(4)观察肿瘤生长或治疗中肿瘤体积的减少,为治疗前的计划和治疗中提供帮助;(5)辐射剂量计算。

从医学图像中自动分割出目标是个艰巨的任务,因为医学图像具有较高的复杂性且缺少简单的线性特征;此外分割结果的准确率还受到部分容积效应、灰度不均匀性、伪影、不同软组织间灰度的接近性等因素的影响[22]。针对通常采用的校正技术来说,可以将MR和CT图像中的伪影分类为[23]:(1)需要适当的滤波算法处理的伪影,如噪声伪影、敏感性伪影、存在非清晰边缘的伪影;(2)需要适当图像修复算法的伪影,如运动伪影;(3)需要特定算法的伪影,如部分容积和灰度不均匀性。图像处理领域尽管在已存在很多算法处理上述问题,但是医学图像分割仍然是个复杂和具有挑战性的问题。从医学图像处理过程的角度来看,基于灰度和基于纹理特征技术的分类是常规的分类方式[24]。此外,用机器学习的工具去优化这些图像分割算法是当前较受关注的技术[25].

CT和MR图像的分割主要涉及3个相关问题:变化的噪声、像素灰度分类的不确定性及灰度的非均衡性[26]。图像中单一组织的灰度水平一般是逐渐变化的,且其概率密度服从特定的分布函数,该组织对应的图像区域包含有限的像素(或体素)且满足部分容积平均,然而该区域中的单个像素(或体素)的灰度不与任何一类一致,往往被看作混合组织类[28]。

CT和MR图像分割常用的一些方法有:基于阈值[29]、基于区域[30]、基于形变模型[31]、基于模糊[32]及基于神经网络[34]。

当前,基于深度学习的方法已在图像分割领域取得了显著成就,其分割准确率已超过了传统分割方法。本文在对近几年深度学习和医学图像分割文献研习的基础上,对深度学习方法和常用的图像分割算法进行了深入的研究和比较,总结了各种深度学习方法的优缺点及其在医学图像分割领域的应用,最后展望了深度学习在医学图像分割领域的未来发展。
 

 

 

2013-07-11 19:47:33 saintfox001 阅读数 4146
  • 综合布线系统优点

    网规下午案例分析出题思路紧跟技术发展脉搏,对热点技术都有所涉及。本课程对网规下午案例分析中的考点做了详细的讲解,通过在重要考点中穿插历年真题的强化讲解,帮助考生掌握考点的同时实时的感受了网规案例分析...

    13人学习 徐朋
    免费试看

——(完整工程文件到我的资源下载)

Prewitt算子边缘检测

一、实验背景与意义

图像处理就是对信息加工以满足人的视觉心理或应用需求的方法。图像处理的方法有光学方法和电子学方法。从20世纪60年代起随着电子计算机和计算技术的不断提高和普及,数字图像处理进入了高速发展时期,而数字图像处理就是利用数字计算机或其它的硬件设备对图像信息转换而得到的电信号进行某些数学处理以提高图像的实用性。图像处理在遥感技术、医学领域、安全领域,工业生产中有着广泛的应用。其中在医学应用中的超声、核磁共振和CT等技术,安全领域和模式识别技术,工业中的无损检测技术尤其引人注目。计算机进行图像处理一般有两个目的:(1)生产更适合人观察和识别的图像。(2)希望能由计算机自动识别和理解图像。数字图像的边缘检测是图像分割、目标区域的识别、区域形状提取等图像分析领域的重要基础。图像处理分析的第一步往往就是边缘检测。物体的边缘是以图像的局部特征不连续的形状出现的,也就是指图像局部亮度变化最显著的部分,例如灰度值的突变、颜色的突变、纹理结构的突变等,同时物体的边缘也是不同的区域分界处。图像边缘有方向和幅度两个特性,通常沿边缘的走向灰度变化平缓,垂直于边缘走向的像素灰度变化剧烈。根据灰度变化的特点,图像边缘可分为阶跃型、房顶型和凸缘型。

边缘检测是图像处理、目标识别和计算机视觉等领域中最经典的研内容之一,已有较长的研究历史,边缘检测是所有基于边界分割方法的第一步。经典的边缘检测方法是对原始图像按像素的某邻域构造边缘检测算子。应用边缘检测的算法是基于边界的分割方法,常用的边缘检测算子有RobertsSobelKirschPrewitt以及Laplace等。其中Prewitt算子通过对图像进行八个方向的边缘检测,将其中方向响应最大的作为边缘幅度图像的边缘,且对噪声具有平滑作用。传统的边缘检测算子的噪声平滑能力和边缘定位能力是矛盾的。为了克服这个不足,正确地得到图像的边缘信息,已经提出了很多方法,其中边缘检测和边缘细化相结合可以有效地调节噪声平滑和边缘定位能力的矛盾。

二、基于Prewitt算法边缘检测的原理

Prewitt算子是一种一阶微分算子的边缘检测,利用像素点上下、左右邻点的灰度差,在边缘处达到极值检测边缘,去掉部分伪边缘,对噪声具有平滑作用。其原理是在图像空间利用两个方向模板与图像进行邻域卷积来完成的,这两个方向模板一个检测水平边缘,一个检测垂直边缘。

Prewitt边缘检测算法是一种类似Sobel边缘检测算法的边缘模板算法。Prewitt边缘检测算子并不把重点放在相邻的像素上,它对噪声具有平滑作用。采用3*3邻域可以避免在像素之间内插点上计算梯度。Prewitt算子也是一种梯度幅值,该算子包含两组3*3的矩阵,分别为横向及纵向,将之与图像作平面卷积,即可分别得出横向及纵向的亮度差分近似值。如果以A代表原始图像,及分别代表经横向及纵向边缘检测的图像,其模板的卷积因子如下:

                    

  该算子包含两组3*3的矩阵,分别为横向及纵向,将之与图像作平面卷积,即可分别得出横向及纵向的亮度差分近似值。具体卷积算法如下:

   经典Prewitt算子认为:凡灰度新值大于或等于阈值的像素点都是边缘点。即选择适当的阈值T,若G(i,j)≥T,则(i,j)为边缘点,G(i,j)为边缘图像。这种判定是欠合理的,会造成边缘点的误判,因为许多噪声点的灰度值也很大,而且对于幅值较小的边缘点,其边缘反而丢失了。Prewitt算子利用像素点上下、左右邻点灰度差,在边缘处达到极值检测边缘。对噪声具有平滑作用,定位精度不够高。

三、算法编程步骤

1、为了对图像利用Prewitt算子进行边缘检测,编程主要步骤如下:

   输入:原灰度图像sourceIMG;

   输入:噪声强度range;

输出:加噪后的高斯噪声图像resultIMG;

Step 1:获取原图像的高rows与宽度cols;

Step 2:为输出图像resultIMG申请空间;

Step 3:for ( i=0; i< cols*(rows-2) - 2; i++)

         取3*3模板对应的原始像素;

         利用Prewitt垂直算子和水平算子计算相应差分并取绝对值输出像素=垂直方向差分+水平方向差分;

end for     

Step 4: 输出图像resultIMG,程序结束。

2、C语言代码如下:

/* ======================================================================== */

/*  Copyright 2006 by Wintech Digital System Technology Corp.               */

/*  All rights reserved. Property of Texas Instruments Incorporated.        */

/*  Restricted rights to use, duplicate or disclose this code are           */

/*  granted through contract.                                             */

/* ======================================================================== */

/*========  头文件引用===========*/

#include "stdio.h"

#include "math.h"

/*============= 工作变量定义======*/

unsigned char *pr_n;    //指针定义

unsigned char *pr_s;    //指针定义

//说明:定义数据存放变量

#pragma        DATA_SECTION(IMG,"data"); 

int  IMG[30000];

#pragma        DATA_SECTION(Noise_IMG,"data");

unsigned char  Noise_IMG[30000];

#pragma        DATA_SECTION(Smooth_IMG,"data");

unsigned char  Smooth_IMG[30000];

void  IMG_Smooth();

void IMG_sobel

(

    const unsigned char *restrict in,   /* Input image data   */

    unsigned char       *restrict out,  /* Output image data  */

    short cols, short rows              /* Image dimensions   */

);

///////////////////////////////////////////////////////////////////////////////////////////////////////////////

//使用说明:

//   1. 本程序可以在Simulator下运动;

//   2. 程序编译、链接、加载成功后,先

//      执行File/data/load,将要进行颜色转换的图像数据从RGB_peppers96x128.dat 

//     (说明:*.dat格式,内部存放了某图像各像素的RGB颜色值)加载入数据存储器存储地址RGB_IMG中

//   3. 数据加载成功后,再Debug/Go Main, 一步一步运行程序

///////////////////////////////////////////////////////////////////////////////////////////////////////////////

int CoefArray[9]={1,1,1,1,1,1,1,1,1};

/*================= 主程序 ================*/

main()

{   

long n;

int imgH,imgW;

    int *ptr;

    imgH=160;  //图像高与宽,因为数据文件中的图像是160X160像素的

    imgW=160; 

/*=========== 初始化 ==========*/

    //1 把图像数据从IMG中移到Noise_IMG数组中

    ptr=IMG;

    pr_n=Noise_IMG;

    for (n=0;n<imgH*imgW;n++)

       *pr_n++=*ptr++;

    //说明:在此暂停,可看到噪声图像 

//指针指向数组

pr_n=Noise_IMG;

pr_s=Smooth_IMG;

ptr=IMG;

    //2 调用子程序,进行彩色图像变换成灰度图像

    while (1)

    { 

       

       //IMG_Smooth(pr_n,pr_s,imgW,imgH);

       

       IMG_sobel(pr_n,pr_s,imgW,imgH);

       //说明:上面子程序执行后,在此暂停,可看平滑后的图像 

     }

    //说明:在此暂停,可看变换后的灰度图像 

}

/*============== 子程序 =============*/

void IMG_Smooth

(   unsigned char   *F,         /* 输入带有噪声的灰度图像      */

    unsigned char   *G,         /* 输出的平滑后的灰度图像      */

    int cols, int rows      /* 图像的宽度与高度            */

)

{    //定义局部变量

    unsigned char *ptr, *pp, *newpp;

    int tmpNum,x, y,k,m,temp;

    int tmp[9];

    //图像四周的像素不进衅交扔谠?

    for (x=0; x< cols -1; x++)  //处理第一行的像素

         G[x] = F[x];

      //处理最后一行的像素

      newpp  =  G + (rows-1)* cols;    //指针指向平滑图像

      pp     =  F+ (rows-1)* cols;     //指针指向噪声图像        

      for (x=0; x< cols -1; x++) 

          * newpp++ = * pp++;

      //处理最左边一列的像素

      newpp  =  G;    //指针指向平滑图像

      pp     =  F;     //指针指向噪声图像        

      for (y=0; y< rows -1; y++) 

      {

          *newpp = *pp;  

          newpp+=cols; pp+=cols;  //指针偏移到下一行像素的位置

      }

      //处理最右边一列的像素

      newpp  =  G+cols;    //指针指向平滑图像

      pp     =  F+cols;     //指针指向噪声图像        

      for (y=0; y< rows -1; y++) 

      {

         * newpp = * pp;  

         newpp+=cols; pp+=cols;  //指针偏移到下一行像素的位置

      }

      //采用中值滤波的方式对图像中的每个像素进行平滑

      for (y=1; y< rows -1; y++)

           for (x=1; x<cols -1; x++)

           {

                newpp   = G + y* cols +x;    //指针指向平滑图像

                pp      = F + y* cols +x;     //指针指向噪声图像        

                //累加第一排的3个像素的值

                ptr      =   pp-cols-1;             

                tmp[1]  =  (*ptr++)*CoefArray[0];

                tmp[2]=  (*ptr++)*CoefArray[1];

                tmp[3]=  (*ptr++)*CoefArray[2];

                //累加第二排的3个像素的值

                ptr      = pp-1;             

                tmp[4]=  (*ptr++)*CoefArray[3];

                tmp[5]=  (*ptr++)*CoefArray[4];

                tmp[6]=  (*ptr++)*CoefArray[5];

                //累加第三排的3个像素的值

                ptr      = pp+cols-1;             

                tmp[7]=  (*ptr++)*CoefArray[6];

                tmp[8]=  (*ptr++)*CoefArray[7];

                tmp[9]=  (*ptr++)*CoefArray[8];

               //累加的结果除以9

                tmpNum /=9;                      

               //检测数据是否溢出,且将平均值赋给平滑图像

               if (tmpNum > 255)

                    *newpp=255;

               else

                     

                    

            {

               for(k=0;k<7;k++)

                  for(m=k+1;m<8;m++)

                   {

             if ( tmp[m]>tmp[m+1] )

                  {

                 temp=tmp[m];

                  tmp[m]=tmp[m+1];

                 tmp[m+1]=temp;

                   }

               }    

             *newpp=tmp[4];

          

          }

       //取排序好的数组的中值赋给当前像素

      // *newpp=tmp[4];

      // newpp++;                                

       //pp++;                                                   

                                         

}

             

                 

} //程序结束

void IMG_sobel

(

    const unsigned char *restrict in,   /* Input image data   */

    unsigned char       *restrict out,  /* Output image data  */

    short cols, short rows              /* Image dimensions   */

)

{

    int H, O, V, i;

    int i00, i01, i02;

    int i10,      i12;

    int i20, i21, i22;

    int w = cols;

    /* -------------------------------------------------------------------- */

    /*  Iterate over entire image as a single, continuous raster line.      */

    /* -------------------------------------------------------------------- */

    for (i = 0; i < cols*(rows-2) - 2; i++)

    {

        /* ---------------------------------------------------------------- */

        /*  Read in the required 3x3 region from the input.                 */

        /* ---------------------------------------------------------------- */

        i00=in[i    ]; i01=in[i    +1]; i02=in[i    +2];

        i10=in[i+  w];                  i12=in[i+  w+2];

        i20=in[i+2*w]; i21=in[i+2*w+1]; i22=in[i+2*w+2];

        /* ---------------------------------------------------------------- */

        /*  Apply horizontal and vertical filter masks.  The final filter   */

        /*  output is the sum of the absolute values of these filters.      */

        /* ---------------------------------------------------------------- */

        H = -   i00 - 2*i01 -   i02 +

            +   i20 + 2*i21 +   i22;

        V = -   i00         +   i02

            - 2*i10         + 2*i12

            -   i20         +   i22;

        O = abs(H) + abs(V);

        /* ---------------------------------------------------------------- */

        /*  Clamp to 8-bit range.  The output is always positive due to     */

        /*  the absolute value, so we only need to check for overflow.      */

        /* ---------------------------------------------------------------- */

        if (O > 255) O = 255;

        else O = 0;

        /* ---------------------------------------------------------------- */

        /*  Store it.                                                       */

        /* ---------------------------------------------------------------- */

        out[i + 1] = O;

    }

}  

/* ======================================================================== */

/*             Copyright (c) 2012 LDX Digital System Technology Corp.   */

/*                         All Rights Reserved.                             */

/* ======================================================================== */

四、实验步骤与结果

1、设置CCS 2.2工作在软件仿真环境

(1)双击桌面上Setup CCS studio图标,运行CCS Setup,进入CCS设置窗口;

(2)在出现的窗口中,按下图所示的方法与顺序进行CCS设置;

  

(3)在弹出的窗口中点击“是”按键保存设置,退出CCS Setup,进入CCS开发环境,此时CCS被设置成Simulator仿真模式。

2、启动CCS。

双击桌面上CCS 2 (C6000)图标,运行CCS。

3、创建工程

(1)创建新的“BYJC”工程文件

   选择菜单“Project”的“New…”项

弹出如下对话框:


输入项目名称BYJC后,点击完成即可。

3先新建源程序窗口:点击“File/New/Source File”,输入源代码(上一步已给出)

点击“File/Save”,在弹出的保存对话框中,选择保存目录为“BYJC”,选择保存类型为“C Source Files”,保存源程序为main.c。

4. 运行程序,观察试验结果。

按如下方法观看试验结果:(1)编译、链接程序:执行菜单Project/Rebuild All,汇编结果在将汇编信息输出窗口中给出。编译后将在Bebug目录中产生一个ImgSmooth.out文件。

2)加载程序:执行File/Load Program,选择ImgSmooth.out并打开,即将可执行文件加载到DSP软件仿真器simulator中,此时CCS将自动打开一个反汇编窗口。

3)将RGB彩色图像的数据从dat文件读入到内存:执行File/data/load,将要进行颜色转换的图像数据从Gray_Lenna160x160.dat (说明:*.dat格式,内部存放了某图像各像素的RGB颜色值)文件中加载入到数据存储器,即在弹出的窗口中输入存储地址IMG与数据的长度,如下图所示。


4)运行程序:执行Debug/Run。为了便于观看试验前后的结果,可以在程序中设置断点,采用单步执行的方法运行程序。

5)显示平滑前的噪声图像:执行View/Graph/Image,在弹出的对话框中选择颜色类型为RGB,并输入RGB彩色图像三个通道数据的地址,以及图像显示格式(显示几行、每行几像素)等内容,如下图所示。这样,原始的噪声图像如图1所示。




图1 原始图像

(6)显示平滑后的图像:执行View/Graph/Image,在弹出的对话框中选择颜色类型为RGB,并输入灰度图像据的地址,以及图像显示格式(显示几行、每行几像素)等内容,如下图所示。


图二为Prewitt算子边缘检测结果


五、分析与总结

  Prewitt算子:利用像素点上下、左右邻点灰度差,在边缘处达到极值检测边缘。对噪声具有平滑作用,但定位精度不够高。对噪声有抑制作用,抑制噪声的原理是通过像素平均,但是像素平均相当于对图像的低通滤波,所以Prewitt算子对边缘的定位不如Roberts算子。图像的峰值处对应着图像的边缘点,边缘位置和导数(微分)间具有一定对应关系,可通过微分进行边缘检测。无噪声时,可用Roberts算子;Prewitt和Sobel算子同时具有平均,即抑制噪声作用;对阶跃状边缘,Roberts得到的边缘宽度≥1个像素,Prewitt和Sobel算子得到的边缘宽度≥2个像素。


2018-06-21 15:11:26 QiangLi_strong 阅读数 19728
  • 综合布线系统优点

    网规下午案例分析出题思路紧跟技术发展脉搏,对热点技术都有所涉及。本课程对网规下午案例分析中的考点做了详细的讲解,通过在重要考点中穿插历年真题的强化讲解,帮助考生掌握考点的同时实时的感受了网规案例分析...

    13人学习 徐朋
    免费试看

传统图像处理部分

图像处理基础知识

彩色图像、灰度图像、二值图像和索引图像区别?

彩色图像:RGB图像。灰度图像:0-255像素值。二值图像:0和1,用于掩膜图像。

索引图像:在灰度图像中,自定义调色板,自定义输出256种颜色值。

常用的图像空间

HSI、HSV、RGB、CMY、CMYK、HSL、HSB、Ycc、XYZ、Lab、YUV色彩空间(颜色模型)

RGB颜色空间是算法处理中应用最多的颜色空间。

HSI颜色空间,色调(Hue)、色饱和度(Saturation或Chroma)和亮度(Intensity或Brightness)

YUV,分为三个分量,“Y”表示明亮度(Luminance或Luma),也就是灰度值;而“U”和“V” 表示的则是色度(Chrominance或Chroma),作用是描述影像色彩及饱和度,用于指定像素的颜色。YUV 4:4:4采样,每一个Y对应一组UV分量。YUV 4:2:2采样,每两个Y共用一组UV分量。 YUV 4:2:0采样,每四个Y共用一组UV分量。 紧缩格式(packed formats)平面格式(planar formats)。YYYYYYYYUVUV YYYYYYYYUUVV

图像的像素数与分辨率有什么区别?

像素数为图像实际组成的像素的个数,像素是没有固定宽度和高度的,是一个感光单元。

分辨率的单位为 像素/英寸(1英寸(inch)=2.54厘米(cm)),这里指的不是面积,而是对角线的长度,即dpi、ppi。分辨率也称之为点密度,分辨率越高,看的越细腻。

视频帧播放速度的单位

PAL制式是——25fps,NTSC是——30fps。

图像预处理

叙述GABOR滤波器原理?

使用一个三角函数(如正弦函数)与一个高斯函数叠加我们就得到了一个Gabor滤波器。Gabor滤波器可以抽取空间局部频度特征,是一种有效的纹理检测工具。

附:图像的空域是指二维坐标系上的操作,频域指的是图像经过傅里叶变换后的频谱。在频率域中,高频分量表示图像中灰度变换比较快的那些地方,比如物体的边缘就是灰度的突然变化,所以物体边缘就是高频分量。而物体内部比较平坦的区域,灰度基本没有变化,对应的就是低频分量。比如低通滤波只让低频分量通过,往往就是使图像模糊,因为边缘信息被去除了。高频对应图像细节,低频对应图像大致轮廓。

椒盐噪声用什么滤波处理比较有效?

参考:中值滤波与椒盐噪声

椒盐噪声:也称为脉冲噪声:

在图像中,它是一种随机出现的白点或者黑点,可能是亮的区域有黑色像素或是在暗的区域有白色像素(或是两者皆有)。

滤除椒盐噪声比较有效的方法是对信号进行中值滤波处理。

插值

最近邻插值

双线性插值

立方卷积插值

二值图像连通域搜索

matlab中连通区域标记函数bwlabel中的算法,一次遍历图像,并记下每一行(或列)中连续的团(run)和标记的等价对,然后通过等价对对原来的图像进行重新标记。

  1. 创建RUN(团)结构体,包含(纵坐标、横坐标开始、横坐标结束、标记号)
  2. 开始逐行扫描图像,寻找所有的团,将他们放到一个二维数组vector< vector<Stuct> >中,以下为每一行的操作。
    1. 当遇到一个255时,创建一个团的对象,标记纵坐标和横坐标的开始。
    2. 从开始点向右寻找,直到遇到0或者这行结束,则标记为这个团的横坐标结束。
    3. 将该行的RUN push到对应的位置。回到步骤2.1.
  3. 对众多的团进行分析,对团进行标记且得到等价对,创建一个vector< pair<int, int> >用于存放所有的等价对。
    1. 遍历所有相邻行。
    2. 若该行为第一行,则直接进行标记。
    3. 对于相邻行,遍历该行的所有RUN,对于每一个RUN,遍历上一行的所有RUN(超出范围即停止循环)。
      1. 若上一行中没有与该行RUN邻接,则创建新的标记。
      2. 若上一行只有一个与该RUN邻接,则沿用相邻RUN的标记。
      3. 若上一行有多个与该RUN邻接,则使用这多个RUN中最小的标记,并创建多个等价对。
  4. 消除等价对,可使用并查集,使得所有的团都拥有自己的祖先。
    1. 假设标记从0开始,到1000结束。标记对为类似的(0,10).(10,39)。
    2. 创建一个prev[1000]数组,初始化值为-1,记录该标记的上一级领导。初始prev[10]=0,prev[39]=10。初始化所有的等价对。
    3. 遍历所有的等价对,修改每一级的上一级领导为最上层领导。
  5. 修改每个团中的标记为最上层领导的标记。

代码见github

开源库cvBlob中使用的标记算法,它通过定位连通区域的内外轮廓来标记整个图像,这个算法的核心是轮廓的搜索算法

TODO:轮廓跟踪算法

并行计算

Intel指令集中MMX,SSE,SSE2,SSE3和SSE4指的是什么?

MMX(Multi Media eXtension,多媒体扩展指令集)是一些整数并行运算指令。

SSE(Streaming SIMD Extensions,单指令多数据流扩展)是一系列浮点并行运算指令。

SIMD,单指令多数据流,是指用一条指令执行多个计算,比如图像像素一般是BYTE占8位,而计算机中总线是64位,所以理论上可以同时进行8个像素的运算。

并行计算有哪些实现方式?

单指令多数据流SIMD、对称多处理机SMP、大规模并行处理机MPP、工作站机群COW、分布共享存储DSM多处理机。

机器学习面试题链接

机器学习部分

特征算子

常用边缘检测有哪些算子,各有什么特性和优缺点?

  1. Prewitt算子
    优点:一阶微分算子,平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。
  2. Sobel算子Sobel算子
    优点:一阶微分算子,加权平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。
  3. Roberts算子Roberts
    优点:一种利用局部差分算子寻找边缘的算子,定位比较精确。缺点:对噪声敏感,无法抑制噪声的影响。
  4. Laplacian算子
    优点:各向同性,二阶微分,精确定位边缘位置所在。缺点:无法感知边缘强度。只适用于无噪声图象。存在噪声情况下,使用Laplacian算子检测边缘之前需要先进行低通滤波。
  5. Laplacian of Gaussian(LoG)算子:先对图像做高斯滤波,再做Laplacian算子检测。
  6. Canny算子:一个具有滤波,增强,检测的多阶段的优化算子。先利用高斯平滑滤波器来平滑图像以除去噪声,采用一阶偏导的有限差分来计算梯度幅值和方向,然后再进行非极大值抑制。

请描述以下任一概念:SIFT/SURF LDA/PCA

SIFT/SURF为了实现不同图像中相同场景的匹配,主要包括三个步骤:
1. 尺度空间的建立;
2. 特征点的提取;
3. 利用特征点周围邻域的信息生成特征描述子;
4. 特征点匹配。

之所以采用尺度空间,是为了应对尺度不变性。

SIFT

  1. 生成高斯差分金字塔(DOG金字塔),尺度空间构建
    • 通过对原始图像进行尺度变换,获得图像多尺度下的尺度空间表示序列
    • 对这些序列进行尺度空间主轮廓的提取,并以该主轮廓作为一种特征向量,实现边缘、角点检测不同分辨率上的关键点提取等
    • 尺度空间构建的基础是DOG金字塔,DOG金字塔构建的基础是高斯金字塔
  2. 空间极值点检测(关键点的初步查探)
    • 为了寻找DOG函数的极值点,每一个像素点要和它所有的相邻点比较,看其是否比它的图像域和尺度空间域的相邻点大或者小
    • 在二维图像空间,中心点与它3*3邻域内的8个点做比较,在同一组内的尺度空间上,中心点和上下相邻的两层图像的2*9个点作比较,如此可以保证检测到的关键点在尺度空间和二维图像空间上都是局部极值点
  3. 稳定关键点的精确定位
    • DOG值对噪声和边缘比较敏感,所以在第2步的尺度空间中检测到的局部极值点还要经过进一步的筛选,去除不稳定和错误检测出的极值点,另一点就是在构建高斯金字塔过程中采用了下采样的图像,在下采样图像中提取的极值点对应在原始图像中的确切位置,也是要在本步骤中解决的问题。
  4. 稳定关键点方向信息分配
    • 稳定的极值点是在不同尺度空间下提取的,这保证了关键点的尺度不变性。为关键点分配方向信息所要解决的问题是使得关键点对图像角度和旋转具有不变性。方向的分配是通过求每个极值点的梯度来实现的。
    • 分配给关键点的方向并不直接是关键点的梯度方向,而是按照一种梯度方向直方图的方式给出的。
    • 具体的方法是:计算以关键点为中心的邻域内所有点的梯度方向,当然梯度方向一定是在0~360°范围内,对这些梯度方向归一化到36个方向内,每个方向代表了10°的范围。然后累计落到每个方向内的关键点个数,以此生成梯度方向直方图。
  5. 关键点描述
    • 对关键点的描述是后续实现匹配的关键步骤,描述其实就是一种以数学方式定义关键的过程。描述子不但包含关键点,也包括关键点周围对其有贡献的邻域点。
    • 描述的思路是:对关键点周围像素区域分块,计算快内梯度直方图,生成具有独特性的向量,这个向量是该区域图像信息的一种抽象表述。
    • 如下图,对于2*2块,每块的所有像素点的荼毒做高斯加权,每块最终取8个方向,即可以生成2*2*8维度的向量,以这2*2*8维向量作为中心关键点的数学描述。
    • David G.Lowed的实验结果表明:对每个关键点,采用4*4*8共128维向量的描述子进项关键点表征,综合效果最佳:
  6. 特征点匹配
    • 特征点的匹配是通过计算两组特征点的128维的关键点的欧式距离实现的。欧式距离越小,则相似度越高,当欧式距离小于设定的阈值时,可以判定为匹配成功。

线性判别分析(LDA), 主成分分析(PCA)

参考参考

LDA和PCA最终的表现都是解一个矩阵特征值的问题,分类的目标是,使得类别内的点距离越近越好(集中),类别间的点越远越好。

LDA的全称是Linear Discriminant Analysis(线性判别分析),是一种supervised learning。

LDA的原理是,将带上标签的数据(点),通过投影的方法,投影到维度更低的空间中,使得投影后的点,会形成按类别区分,一簇一簇的情况,相同类别的点,将会在投影后的空间中更接近。要说明白LDA,首先得弄明白线性分类器(Linear Classifier):因为LDA是一种线性分类器。对于K-分类的一个分类问题,会有K个线性函数 y = wx+b.

当满足条件:对于所有的j,都有Yk > Yj,的时候,我们就说x属于类别k。对于每一个分类,都有一个公式去算一个分值,在所有的公式得到的分值中,找一个最大的,就是所属的分类了。

y = wx+b实际上就是一种投影,是将一个高维的点投影到一条高维的直线上,LDA最求的目标是,给出一个标注了类别的数据集,投影到了一条直线之后,能够使得点尽量的按类别区分开

主成分分析(PCA)与LDA有着非常近似的意思,LDA的输入数据是带标签的,而PCA的输入数据是不带标签的,所以PCA是一种unsupervised learning。

PCA更像是一个预处理的方法,它可以将原本的数据降低维度,而使得降低了维度的数据之间的方差最大

它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性。

通俗的理解,如果把所有的点都映射到一起,那么几乎所有的信息(如点和点之间的距离关系)都丢失了,而如果映射后方差尽可能的大,那么数据点则会分散开来,以此来保留更多的信息。可以证明,PCA是丢失原始数据信息最少的一种线性降维方式。(实际上就是最接近原始数据,但是PCA并不试图去探索数据内在结构)

Linear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一种有监督的(supervised)线性降维算法。与PCA保持数据信息不同,LDA是为了使得降维后的数据点尽可能地容易被区分!

特征点匹配

如下图所示,请以准确快速实现配准为目标,设计算法,让两图中对应的特征点(至少一部分特征点)配准(即精准地地找出对应点之间对应的坐标关系值)。

参考

之前是用角点检测,后来采用SIFT算子,Sift算法的实质是在不同的尺度空间上查找关键点(特征点),计算关键点的大小、方向、尺度信息,利用这些信息组成关键点对特征点进行描述的问题。

  1. 生成高斯差分金字塔(DOG金字塔),尺度空间构建
  2. 空间极值点检测(关键点的初步查探)
  3. 稳定关键点的精确定位
  4. 稳定关键点方向信息分配
  5. 关键点描述(128维向量算子)
  6. 特征点匹配(欧氏距离)

极值点邻域筛选

对于一般应用图像中,景物可能存在任意特征(如折线,弧形、亮度极值、色调等),请设计合适的算法,找到图像中可以作为明显特征点的灰度的极值点所在的邻域。以准确快速实现极值点邻域筛选为目标,设计算法。用流程图表达)。

也使用SIFT特征

特征离散化的好处

  1. 增减特征较为方便,易于迭代。
  2. 离散化后运算速度快,存储方便。
  3. 对脏数据的鲁棒性较强。
  4. 离散化一定程度简化了模型,可以防止过拟合。

分类算法

常用的分类器有哪些,并简述其原理?

线性分类器:Logistic回归 y=sigmoid(wx+b)

传统方式:特征描述和检测

KNN,K最近邻,判断图像与各个类别的距离

SVM,选定特征, SVM算法输出一个最优化的分隔超平面(分类面)。本科课题:SIFT、k-means、Bag of Words、SVM。映射函数可能为多项式。

BPNN,全连接网络,计算量巨大

CNN,卷积神经网络

迁移学习,利用别人训练好的参数,自定义网络

LR与线性回归的对比

LR的优化函数为似然函数,经典线性回归的优化函数为最小二乘。

LR将预测范围缩小到了[0,1],而经典线性回归的预测范围为整个实数。

LR与SVM的对比

相同:都是分类模型。都处理二分类。都可以添加正则项。

区别:LR是参数模型,SVM是非参数模型;LR采用logistical loss,SVM采用hinge loss;SVM之所以称之为支持向量,是因为SVM只考虑了与分类最相关的少数点来学习分类器。

KNN的K是如何选取的

K值较小意味着模型会越复杂,容易发生过拟合。K值过大会使模型过于简单,使得预测发生错误。实际使用中K一般取较小的数字。

什么是SVM?

参考http://blog.csdn.net/v_july_v/ … 24837

是一个二分分类器,找寻数据之间间隔最大的线性分类器。其学习策略是使分隔间隔最大化。对于线性可分的数据,SVM构造一个分隔面。对于线性不可分的数据,SVM采用核函数将低维空间的问题映射到了高维空间,从而线性可分。常用核函数有多项式核函数、高斯核函数、线性核函数。为了应对维度爆炸的情形,核函数事先在低维空间上进行计算,再将分类的实际效果展现在高维上。

SVM的损失函数叫做Hinge(hɪndʒ) Loss,形式为max(0,1-y*a),y为真实值+-1,a为预测值,介于-1到1之间。

简述BP神经网络

BP(back propagation)神经网络,输入X,通过隐藏节点的非线性变换后,输出信号Y,通过误差分析,来调整隐藏节点的W和b。

AdaBoost的基本原理?

AdaBoost是一个广泛使用的BOOSTING算法,其中训练集上依次训练弱分类器,每次下一个弱分类器是在训练样本的不同权重集合上训练。权重是由每个样本分类的难度确定的。分类的难度是通过分类器的输出估计的。

参考资料

//TODO 详细学习

聚类算法

简述你熟悉的聚类算法并说明其优缺点

K均值聚类(K-meansClustering)

将输入数据分到K个类中。K均值是通过循环更新类中心的初始估计值来实现的。优势是实现起来很简单,是并行化的。主要缺陷是,类的数目需要提前确定。

主要分三步:
1. 随机选取k个聚类质心点(cluster centroids)
2. 对于每一个样例i,计算其应该属于的类
3. 对于每一个类j,重新计算该类的质心
1. 重复下面过程直到收敛

层次聚类

层次聚类(或者叫做凝聚聚类)是另一个简单但是强大的聚类算法。其思想是基于成对距离建立一棵相似度树。该算法首先分组成为两个最近的对象(基于特征向量之间的距离),并且在一棵有着两个对象作为孩子的树中创建一个平均结点。然后在余下的结点中找到一个最近的pair,并且也包含任何平均节点,等等。在每一个结点,两个孩子之间的距离也会被存储。簇然后可以通过遍历这棵树并在距离比某个阈值小以至于决定聚类的大小的结点处停止来被提取出来。

层次聚类有几个优势。比如,树结构可以被用来可视化关系,并且显示簇是如何关联起来的。一个好的特征向量将得到树中好的分离。另一个优势是树可以在不同的簇阈值中被重用,而不需要重新计算树。缺点是需要选择一个阈值如果实际的簇需要的话

谱聚类

对于n个元素的相似度矩阵(或者叫affinity matrix, 有时也叫距离矩阵)是一个有着成对相似度分数的n*n矩阵。谱聚类的这个名称是从相似度矩阵构造的矩阵的谱的使用得来。这个矩阵的特征向量被用来降维,然后再聚类。

谱聚类方法的其中一个优势是唯一的输入就是这个矩阵,并且可以被你可以想到的任何相似度度量构造出来。像K均值和层次聚类这样的方法计算特征向量的平均值,这个限制了特征(或者是描述符)对向量(为了能够计算平均值)。有了谱方法,不再需要任何类型的特征向量,只有“距离”或者“相似度”。

Mean Shift 聚类算法

  1. 在未被标记的数据点中随机选择一个点作为中心center;
  2. 找出离center距离在bandwidth之内的所有点,记做集合M,认为这些点属于簇c。同时,把这些求内点属于这个类的概率加1,这个参数将用于最后步骤的分类
  3. 以center为中心点,计算从center开始到集合M中每个元素的向量,将这些向量相加,得到向量shift。
  4. center = center+shift。即center沿着shift的方向移动,移动距离是||shift||。
  5. 重复步骤2、3、4,直到shift的大小很小(就是迭代到收敛),记住此时的center。注意,这个迭代过程中遇到的点都应该归类到簇c。
  6. 如果收敛时当前簇c的center与其它已经存在的簇c2中心的距离小于阈值,那么把c2和c合并。否则,把c作为新的聚类,增加1类。
  7. 重复1、2、3、4、5直到所有的点都被标记访问。
  8. 分类:根据每个类,对每个点的访问频率,取访问频率最大的那个类,作为当前点集的所属类。

简单的说,mean shift就是沿着密度上升的方向寻找同属一个簇的数据点。

欧式距离和曼哈顿距离的区别

欧式距离为最常见的2点之间的距离,为2点之间的直线距离。

曼哈顿距离又称为L1距离或者城市区块距离,是两个点的1范数距离。

图像分割

Graph-cut的基本原理和应用?

Graph cuts是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。

利用图,将目标和背景进行分割。

图像融合,镶嵌

已知两幅拼接好的图像,两幅图像在几何关系配准之后,但两图之间存在明显灰度差别跳变,请设计一个算法对图像进行处理,让两幅图之间的灰度看不出跳变,形成自然过渡。(可以不考虑两图之间的黑图部分)。

影像融合是指高分辨率灰度图像和低分辨率彩色图像融合得到具有高分辨率的彩色图像。该算法称之为图像镶嵌。简单的做法可以是寻找两幅影像的镶嵌线,镶嵌线是指两幅影像公共区域区别最小的一条线,可以利用相关系数法判断得到,然后根据镶嵌线上两幅影像的灰度差异对右影像进行反差调整,最后拼接。

其他模型

Random Forest的随机性表现在哪里。

Bagging方法是ensemble methods中获得用于训练base estimator的数据的重要一环。 正如其名,Bagging方法就是将所有training data放进一个黑色的bag中,黑色意味着我们看不到里面的数据的详细情况,只知道里面有我们的数据集。然后从这个bag中随机抽一部分数据出来用于训练一个base estimator。抽到的数据用完之后我们有两种选择,放回或不放回。

我们可以看到从根节点开始往下会有分支,最终会走向叶子节点,得到分类结果。每一个非叶子节点都是一个特征,上图中共有三维特征。但是决策树的一个劣势就是容易过拟合,下面我们要结合上文提到的bagging技术来中和一下。

img

bagging + decision trees,我们得到了随机森林。将决策树作为base estimator,然后采用bagging技术训练一大堆小决策树,最后将这些小决策树组合起来,这样就得到了一片森林(随机森林)。

(X[1],Y[1])….(X[n],Y[n])是数据集,我们要训练T棵决策树g[1]….g[t]…g[T]。 每次从数据中有放回地随机抽取size-N’的子数据集D[t]用于训练第t棵决策树g[t]。

随机森林的随机性体现在每颗树的训练样本是随机的,树中每个节点的分裂属性集合也是随机选择确定的。有了这2个随机的保证,随机森林就不会产生过拟合的现象了。

GMM的基本原理和应用

高斯混合模型(Gaussian Mixture Model, GMM)将一个事物分解为若干的基于高斯概率密度函数(正态分布曲线)形成的模型。

高斯混合模型(GMM,Gaussian mixture model)是建模最为成功的方法之一,同时GMM可以用在监控视频索引与检索。

用于动目标检测中的背景建模。

  • 混合高斯模型使用K(++基本为3到5个++) 个高斯模型来表征图像中各个像素点的特征。
  • 在新一帧图像获得后更新混合高斯模型,用当前图像中的每个像素点与混合高斯模型匹配,如果成功则判定该点为背景点, 否则为前景点。
  • 通观整个高斯模型,他主要是有++方差++和++均值++两个参数决定,,对均值和方差的学习,采取不同的学习机制,将直接影响到模型的稳定性、精确性和收敛性。
  • 由于我们是对运动目标的背景提取建模,因此需要对高斯模型中方差和均值两个参数实时更新。
  • 为提高模型的学习能力,改进方法对均值和方差的更新采用不同的学习率
  • 为提高在繁忙的场景下,大而慢的运动目标的检测效果,引入权值均值的概念,建立背景图像并实时更新,然后结合权值、权值均值和背景图像对像素点进行前景和背景的分类。

其他理论

监督学习和非监督学习。

  • 监督学习:通过已有的一部分输入数据与输出数据之间的对应关系,生成一个函数,将输入映射到合适的输出,例如分类。
  • 非监督学习:直接对输入数据集进行建模,例如聚类。
  • 半监督学习:综合利用有类标的数据和没有类标的数据,来生成合适的分类函数。

目前最广泛被使用的分类器有人工神经网络、支持向量机、最近邻居法、高斯混合模型、朴素贝叶斯方法、决策树和径向基函数分类。

无监督学习里典型的例子就是聚类了。聚类的目的在于把相似的东西聚在一起,而我们并不关心这一类是什么。因此,一个聚类算法通常只需要知道如何计算相似度就可以开始工作了。

过拟合的解决方法

减小模型复杂度、加大数据、batch normalization、dropout、正则化、early stopping。

谈谈判别式模型和生成式模型?

常见的判别模型有:K近邻、SVM、决策树、感知机、线性判别分析(LDA)、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场。通过决策函数来进行判别。

常见的生成模型有:朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机。通过联合概率密度分布函数来进行预测。

L1和L2的区别

  • L1范数为向量中各个元素的绝对值之和,符合拉普拉斯分布,可以使权值稀疏。
  • L2范数为向量中各个元素的平方和的1/2次方,符合高斯分布,可以防止过拟合。
  • Lp范数为向量中各个元素的p次方和的1/p次方。

归一化的好处

归一化加快了梯度下降求解最优解的速度;归一化还可能会提高精度。

归一化的种类

  • 线性归一化。利用max和min进行归一化,如果max和min不稳定,则常用经验值来替代max和min。
  • 标准差归一化。利用所有样本的均值和方差将样本归一化为正态分布。
  • 非线性归一化。比如指数、对数、三角函数等。

归一化和标准化的区别

标准化是依照特征矩阵的列处理数据,其通过求z-score的方法,将样本的特征值转换到同一量纲下。归一化是依照特征矩阵的行处理数据,其目的在于样本向量在点乘运算或其他核函数计算相似性时,拥有统一的标准,也就是说都转化为“单位向量”。

对于深度网络而言,归一化的目的是方便比较,可以加快网络的收敛速度;标准化是将数据利用z-score(均值、方差)的方法转化为符合特定分布的数据,方便进行下一步处理,不为比较。

熵是指样本的随机程度。样本越无序,熵越大, 信息越多。

完成机器学习项目流程

  1. 抽象成数学问题。明确我们可以获得什么样的数据,这个问题是回归还是分类。
  2. 获取数据。增加数据的代表性,防止因数据引起的过拟合。
  3. 特征预处理和特征选择。进行数据清洗,包括归一化、离散化等操作。结合数据和业务的特点来确定需要选取的特征算子。
  4. 训练模型和调优。选择一个模型进行训练,并对超参数进行调节。
  5. 模型诊断。分析模型是否过拟合或者欠拟合,然后进行相应的操作。同时可以进行误差分析,针对不同的问题来优化模型。
  6. 模型融合。将预处理和预测进行统一。
  7. 上线运行。

深度学习部分

潮流

图像检测和分割,增强学习,生成对抗网络,预测学习

基础理论

SGD 中 S(stochastic)代表什么

Stochastic Gradient Descent 随机梯度下降。GD即Full-Batch,SGD即为Mini-Batch。随机性表现在训练数据的shuffle。

Softmax Loss推一下

Sigmoid、Tanh、ReLU比较

Rectified Linear Unit, ReLU

ReLU比Sigmoid、Tanh好的原因

  1. 指数函数运算量大。ReLU节省运算量。
  2. Sigmoid容易引发梯度消失问题,因为Sigmoid函数在两端的导数趋近于0.
  3. ReLU使得一部分神经元死亡,这样可以使得网络变得比较稀疏,缓解了过拟合的发生。

引入非线性激活函数的原因?

若使用线性激活函数,则无论神经网络有多少层,输出都是输入的线性组合。

好的激活函数有以下特点:

  1. 非线性:即导数不是常数。
  2. 几乎处处可微:可微性保证了在优化中梯度的可计算性。
  3. 计算简单。
  4. 非饱和性(saturation):饱和指的是在某些区间梯度接近于零(即梯度消失),使得参数无法继续更新的问题。
  5. 单调性(monotonic):即导数符号不变。
  6. 输出范围有限:有限的输出范围使得网络对于一些比较大的输入也会比较稳定
  7. 接近恒等变换(identity):即约等于x。这样的好处是使得输出的幅值不会随着深度的增加而发生显著的增加
  8. 参数少:大部分激活函数都是没有参数的。
  9. 归一化(normalization):这个是最近才出来的概念,对应的激活函数是SELU。类似于Batch Normalization。

什么造成了梯度消失和梯度膨胀?

深度网络的链式连乘法则,使得反向传播时到达前几层时,权值更新值非常小或非常大。

可以通过ReLU解决一部分。

各大指标

先是混淆矩阵,这是基础。

混淆矩阵

包含四部分的信息:
1. True negative(TN),称为真阴率,表明实际是负样本预测成负样本的样本数
2. False positive(FP),称为假阳率,表明实际是负样本预测成正样本的样本数
3. False negative(FN),称为假阴率,表明实际是正样本预测成负样本的样本数
4. True positive(TP),称为真阳率,表明实际是正样本预测成正样本的样本数

前面有的表示预测正确。

ROC曲线

二分类标签的输出概率需要定义一个阈值p,p值的选取反映了分类器的分类性能。ROC曲线的横轴为FP(将真实负样本预测为了正样本,越低越好),纵轴为TP(将真实正样本预测为正样本,越高越好)

ROC

  • (0,0):假阳率和真阳率都为0,即分类器全部预测成负样本
  • (0,1):假阳率为0,真阳率为1,全部完美预测正确,happy
  • (1,0):假阳率为1,真阳率为0,全部完美预测错误,悲剧
  • (1,1):假阳率和真阳率都为1,即分类器全部预测成正样本
  • TPR=FPR,斜对角线,预测为正样本的结果一半是对的,一半是错的,随机分类

则,若ROC曲线处于对角线之下,则分类性能差于随机分类器。希望该曲线向左上角凸。

AUC指标

AUC(Area under the ROC curve),适用于二元分类问题,AUC实际上就是ROC曲线下的面积。AUC直观地反映了ROC曲线表达的分类能力。

  • AUC = 1,代表完美分类器
  • 0.5 < AUC < 1,优于随机分类器
  • 0 < AUC < 0.5,差于随机分类器

求解步骤:

  1. 获得样本的输出概率和标签值。
  2. 对于不同的从高到低的阈值,计算不同的TP和FP。
  3. 绘制ROC曲线,计算面积。

AUC含义:从所有真实的正样本中取一个数据,判断这个样本是正样本的概率是p1,从所有真实的负样本中取一个数据,判断这个样本是正样本的概率是p2。对于分类器来说p1越大越好,p2越小越好。则p1大于p2的概率称之为AUC。

mAP

计算步骤,参考

  1. 得到所有测试样本的id、输出概率和真实标签值。
  2. 对输出概率进行排序。
  3. 假设有M个recall值,分别计算不同recall下的准确率。
  4. 取M个准确率的平均值。

AP(average precision),

卷积神经网络

图像预处理手段

卷积和相关

相关和卷积的机理相似,但卷积滤波器首先要旋转180度。

卷积算法的时间复杂度

因为在图像的每个位置都要计算一遍卷积核,所以图像像素数为M,卷积核大小为N,则卷积的时间复杂度为O(M*N)。

池化层的作用

  • 保留主要特征的同时进行降维和减少计算量,防止过拟合,提高模型泛化能力。
  • 增加一定的不变性,在池化窗口内。包括平移、旋转、尺度不变性。

CNN特性

CNN的四个特点:局部连接、权值共享、池化操作、多层次结构。

局部连接使网络可以提取数据的局部特征;权值共享降低了网络的训练难度,一个Filter只提取一个特征;池化操作与多层次结构一起,实现了数据的降维,将低层次的局部特征组合成为较高层次的特征,从而对整个图片进行表示。

为什么很多做人脸的Paper会最后加入一个Local Connected Conv?

人脸在不同的区域存在不同的特征(眼睛/鼻子/嘴的分布位置相对固定),当不存在全局的局部特征分布时,Local-Conv更适合特征的提取。

循环神经网络

LSTM为何比RNN好

LSTM可以防止梯度消失或者爆炸

其他网络

生成对抗网络

简称GAN。该网络包含2个部分,一个称之为生成器generator,主要作用是生成图片,并且尽量使得其看上去是来自于训练样本的。另一方是discriminator,其目标是判断输入图片是否属于真实训练样本。

TensorFlow

如何理解TensorFlow的计算图?

TensorFlow分为二部分,一部分是构造部分,用来构造网络;一部分是执行部分,用来执行网络中的计算。

图像相关开放性知识

怎样在一张街拍图像中识别明星的衣着服饰信息?

我们需要把服装与背景、人物、建筑等等元素区别开来,确定是否有衣服以及衣服在什么位置。接下来需要对衣服进行分析,提取出服装的属性、特征等等。最后再根据这些特征,在庞大的数据库里搜索同款或者类似的服装图片。

上衣纯色,裙子花色,怎样做区分?

方差判断,梯度变化。

怎样判断一张广告图片中是否有文字信息?是否用到OCR技术?怎样应用?

场景文字检测与识别,先用CNN等对文字进行定位,然后再使用LSTM、OCR进行文字识别。

给一张二值化图片(包含一个正方形),怎样识别图片中的正方形?如果图片污损严重,怎样识别并恢复?

首先检测轮廓,然后对轮廓进行分析(角点)。

如果图像污损严重,如何识别?

简述图像识别在移动互联网中的应用

人脸识别、识别各类东西、检索各类图像。

图像处理领域相关顶级论文

  • Image and Vision Computing (IVC)
  • Pattern Recognition (PR)
  • ICCV: IEEE International Conference on Computer Vision
  • CVPR: IEEE Conf on Comp Vision and Pattern Recognition
  • NIPS: Neural Information Processing Systems

数学部分

公式

贝叶斯全概率公式题

全概率公式

对任一事件A,若有互不相容的事件Bi(i=1,2,...,n),满足P(Bi)>0,i=1nP(Bi)=1(i=1,2,...,n)i=1nBiA,则事件A的概率可用下式计算:

P(A)=i=1nP(Bi)P(A|Bi)

img

此概率称之为全概率公式。

Bayes公式

利用乘法公式与全概率公式可导出Bayes公式

对任一事件A,若有互不相容的事件Bi(i=1,2,,n),满足P(Bi)>0,i=1nP(Bi)=1(i=1,2,...,n)i=1nBiA,(跟上个公式条件相同)则

P(Bi|A)=P(Bi)P(A|Bi)i=1nP(Bi)P(A|Bi)(i=1,2,,n)

最小二乘拟合的公式推导和代码实现。

最小二乘法通常用于 曲线拟合 (least squares fitting) 。

推导过程

核心思想是最小化损失函数:距离差值的平方((diR)2),若想公式可导,则可以计算平方差的平方(di2R2)2

C/C++部分

基本概念

关键字static的作用是什么?

  1. 在函数体,一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
  2. 在模块内(但在函数体外),一个被声明为静态的变量可以被模块内所用函数访问,但不能被模块外其它函数,它是一个本地的全局变量。
  3. 在模块内,一个被声明为静态的函数只可被这一模块的它函数调用。那就是,这个函数被限制在声明它的模块的本地范围内使用。

简述C,C++程序编译的内存分配情况?

C,C++中内存分配方式可以分为三种:

  1. 从静态存储区域分配:内存在程序编译时就已经分配好,这块内存在程序的整个运行期间都存在。速度快,不容易出错,因有系统自行管理。它主要存放静态数据、全局数据和常量。会默认初始化,其他两个不会自动初始化。
  2. 在栈上分配:在执行函数时,函数内局部变量的存储单元都在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。
  3. 从堆上分配:即运态内存分配。程序在运行时候用malloc或new申请任意大小的内存,程序员自己负责在何进用free 和delete释放内存。

一个C、C++程序编译时内存分为5大存储区:堆区、栈区、全局区、文字常量区和程序代码区。

new 和 malloc的区别

  1. malloc/free是C的标准库函数,new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
  2. 当使用一些非内置数据类型的对象时,maloc/free不能自动执行构造函数和析构函数。这是因为malloc/free是库函数,不在编译器控制下。

图的遍历

深度搜索DFS

递归写法

  1. 定义一个visited数组。
  2. 访问当前节点,输出该节点。
  3. 循环遍历该节点的相邻的,未被访问过的节点。
    1. 递归第二步。

非递归写法

  1. 定义一个栈和一个visited数组。
  2. 将初始节点入栈。开始循环,直道栈空。循环如下:

广度搜索BFS

设置队列

  1. 定义一个队列Queue和visited数组。
  2. 将开头节点入队。
  3. 开始循环
    1. 出队,访问该节点
    2. 遍历该节点的相邻的未被访问过的节点,入队

hash 冲突及解决办法

键字值不同的元素可能会映象到哈希表的同一地址上就会发生哈希冲突。解决办法:

  1. 开放定址法。按照一定的方法进行顺延。
  2. 再哈希法。同时构造多个不同的哈希函数。
  3. 链地址法。数组后的每个元素后添加单链表。

红黑树的特征

具有二叉查找树的所有特征。二叉查找树查找的效率最坏为O(n),红黑树通过颜色着色的方法将最坏降低到平均水平。

  1. 每个结点要么是红的要么是黑的。
  2. 根节点是黑的。
  3. 每个叶结点(树尾端的NIL指针或者NULL结点)都是黑的。
  4. 如果一个节点是红色,他的两个孩子都是黑色。
  5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

是红黑树的这5条性质,使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”

其他编程

嵌入式系统总是用户对变量或寄存器进行位操作。给定一个整型变量a,写两段代码,第一个设置a的bit3,第二消除a的 bit 3。在以上两个操作中,要保持其它位不变.

#include <iostream>
#include <bitset>
using namespace std;

#define BIT3 (0x1<<3)
void set_bit3(unsigned &a)
{
    a |= BIT3;
}
void clear_bits(unsigned &a)
{
    a &= ~BIT3;
}

int main()
{
    unsigned a = UINT_MAX;
    clear_bits(a);
    cout << (bitset<32>)a << endl;
    set_bit3(a);
    cout << (bitset<32>)a << endl;
    return 0;
}

行列递增矩阵的查找

解法一、分治法

因为矩阵的行和列都是递增的,所以整个矩阵的对角线上的数字也是递增的,故我们可以在对角线上进行二分查找,如果要找的数是6介于对角线上相邻的两个数4、10,可以排除掉左上和右下的两个矩形,而在左下和右上的两个矩形继续递归查找

解法二、定位法

首先直接定位到最右上角的元素,比要找的数大就往左走,比要找数的小就往下走,直到找到要找的数字为止,走不动,说明这个数不存在。这个方法的时间复杂度O(m+n)。代码如下:

#include <iostream>
#include <vector>
using namespace std;

bool YoungMatrix(vector< vector<int> > mat, int target){
    int y = 0, x = mat[y].size() - 1;
    int var = mat[y][x];
    while (true) {
        if (var == target){
            printf("Mat[%d][%d]=%d\n", y, x, target);
            return true;
        }
        else if (var < target && y < mat.size() - 1){
            var = mat[++y][x];
        }
        else if (var > target && x > 0){
            var = mat[y][--x];
        }
        else{
            return false;
        }
    }
}

int main(){
    vector<vector<int> > matrix(20);
    for (int i = 0; i < 20; i++){
        for (int j = 0; j < 20; j++) {
            matrix[i].push_back(i+j);
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    cout << YoungMatrix(matrix, 38) << endl;
    return 0;
}

从1到500的500个数,第一次删除奇数位上的所有数,第二次删除剩下来的奇数位,以此类推,最后剩下的唯一一位数是什么?

就是当1~n,2^i

给出了一个n*n的矩形,编程求从左上角到右下角的路径数(n > =2),限制只能向右或向下移动,不能回退。例如当n=2时,有6条路径。

从左上角到右下角总共要走2n步,其中横向要走n步,所以总共就是C2nn次。

给出一棵二叉树的前序和中序遍历,输出后续遍历的结果。

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为多少?

#include <iostream>
#include <string>
using namespace std;

string Subsequent(string pre, string mid) {
    if (pre.size() != mid.size() || pre.empty()) return "";
    char root = pre[0];
    int rootIndex = mid.find(root);
    string leftPre = pre.substr(1, rootIndex);
    string leftMid = mid.substr(0, rootIndex);
    string rightPre = pre.substr(rootIndex + 1);
    string rightMid = mid.substr(rootIndex + 1);

    string res;
    res += Subsequent(leftPre, leftMid);
    res += Subsequent(rightPre, rightMid);
    res += root;
    return res;
}

int main(){
    string pre = "ABDEGCFH";
    string mid = "DBGEACHF";
    cout << Subsequent(pre, mid) << endl;
    return 0;
}

自定义实现字符串转为整数的算法,例如把“123456”转成整数123456.(输入中可能存在符号,和数字)

代码见github

字符串最长公共子序列

动态规划推导式

img

代码见github

字符串最长公共子串

与上文区别是不等时的处理方式,和最后是整个矩阵中寻找最大值。

代码见github

请实现一个函数:最长顺子。输入很多个整数(1<=数值<=13),返回其中可能组成的最长的一个顺子(顺子中数的个数代表顺的长度); 其中数字1也可以代表14;

直方图

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> LongestShunZi(vector<int> input) {
    // 统计直方图
    vector<int> hist;
    hist.resize(15);
    for (int i = 0; i < input.size(); i++)
        if (input[i] > 0 && input[i] < 15)
            hist[input[i]] ++;
    hist[14] = hist[1];
    //最大牌数
    int maxCount = 0;
    for (int i = 1; i < 15; i++)
        if (hist[i] > maxCount)
            maxCount = hist[i];
    //求结果
    int resLen = 0;
    int resCount = 0;
    int resEnd = 0;
    for (int i = 1; i <= maxCount; i++)
    {
        int len = 0;
        int longestLen = 0;
        int longestEnd = 1;
        for (int j = 1; j < 15; j++) {
            if (hist[j] >= i) {
                len++;
                if (len > longestLen) {
                    longestLen = len;
                    longestEnd = j;
                }
            }
            else {
                len = 0;
            }
        }
        if (longestLen == 14 && 2 * i > hist[1]) longestLen--;
        if (longestLen * i > resLen * resCount) {
            resLen = longestLen;
            resCount = i;
            resEnd = longestEnd;
        }
    }

    vector<int> res;
    for (int i = resEnd - resLen + 1; i <= resEnd; i++)
        for (int j = 0; j < resCount; j++)
            res.push_back(i);
    return res;
}

int main() {
    int arr[] = { 1, 5, 2, 3, 4, 4, 5, 9, 6, 7, 2, 3, 3, 4 };
    vector<int> v(arr, arr+sizeof(arr)/sizeof(int));
    vector<int> res = LongestShunZi(v);
    for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
    cout << endl;
    return 0;
}

对一批编号为1-100,全部开关朝上(开)的亮灯进行如下操作

对一批编号为1-100,全部开关朝上(开)的亮灯进行如下操作:凡是编号为1的倍数的灯反方向拨一次开关;凡是编号为2的倍数的灯反方向又拨一次开关;编号为3的倍数的灯反方向又拨一次开关……凡是编号为100的倍数的灯反方向拨一次开关。编写程序,模拟此过程,最后打印出所熄灭灯的编号。

#include <iostream>
using namespace std;

int main() {
    bool arr[101];
    memset(arr, 0, 101);

    for (int i = 2; i <= 100; i++) {
        for (int j = 1; j <= 100; j++) {
            if (j % i == 0) {
                arr[j] = !arr[j];
            }
        }
    }
    for (int i = 1; i <= 100; i++) {
        if (!arr[i])
            cout << i << endl;
    }
    return 0;
}
1
4
9
16
25
36
49
64
81
100

一个数的约数个数为奇数。所有的数都包含1和自己,平方数的约数肯定是奇数个。

实现个函数 unsigned int convect(char* pstr)

实现个函数 unsigned int convect(char* pstr)。其中pstr是十六进制数的字符串。函数convectpstr转换成数字返回(比如:字符串’1A’,将返回数值26.注意,pstr[0]是’1’)。pstr中只有数字字符0到9、A到F。不得借助其它的系统函数调用。

#include <iostream>
using namespace std;

unsigned int convect(char* pstr) {
    char *p = pstr;
    unsigned long long res = 1;
    unsigned long long maxInt = (res << 32) - 1;
    res = 0;
    while (*p != '\0') {
        if (*p >= '0' && *p <= '9') {
            res = res * 16 + *p - '0';
        }
        else if (*p >= 'A' && *p <= 'F') {
            res = res * 16 + *p - 'A' + 10;
        }
        else return 0;
        p++;
    }
    if (res > maxInt) return 0;
    return res;
}

int main() {
    cout << convect((char*)"1A") << endl;
    cout << convect((char*)"FFFFFFFF") << endl;
    cout << convect((char*)"FFFFFFFFF") << endl;
    return 0;
}

实现一个函数unsigned int counter(char* pstr)

实现一个函数unsigned int counter(char* pstr)。函数将打印出匹配的括号对。比如:字符串”a(bc(d)ef(12)g)”就存在3对匹配的括号对,分别是:
1. 位置4上的(与位置6上的)匹配。打印4 6即可。
1. 位置9上的(与位置12上的)匹配。打印9 12即可。
1. 位置1上的(与位置14上的)匹配。打印1 14即可。

软件编程部分

设计

给你一个模块要求,你要做出这个模块,那么你的做出该模块的思路和步骤是什么?

明确这个模块的功能,明确其输入以及输出。

尽量去除与其他模块的耦合关系,确保独立性。

我会首先编写输入和输出的接口函数,然后由粗到精,逐步实现细节算法。

同时还需要编写模块的测试代码,保证交付的可靠性。

Matlab编程

Matlab 中读、写及显示一幅图像的命令各是什么?

imread(), imwrite(), imshow()

Matlab 与VC++混合编程有哪几种方式?

Matlab引擎方式(Matlab后台程序为服务器,VC前端为客户端,C/S结构)、Matlab编译器(将Matlab源代码编译为C++可以调用的库文件)及COM组件(Matlab生成COM组件,VC调用)

Matlab运算中 .** 的区别?

.*表示矩阵元素分别相乘,要求两个矩阵具有相同的shape。*表示矩阵相乘。

逻辑推理部分

智力题

药丸问题

有四人装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被污染的重量+1.只称量一次,如何判断哪个罐子的药被污染了?

答:在四个罐子里面分别取1、2、3、4颗药丸,然后进行称量。如果称量结果比实际(污染前)重了n,就是第n罐被污染了。 (因为每加一颗被污染的药丸就增加1所以增加n就是增加n颗就是在第n个罐子里拿的)

帽子黑白问题

一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其他人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?

解:假如只有一个人戴黑帽子,那他看到所有人都戴白帽,在第一次关灯时就应自打耳光,所以应该不止一个人戴黑帽子;如果有两顶黑帽子,第一次两人都只看到对方头上的黑帽子,不敢确定自己的颜色,但到第二次关灯,这两人应该明白,如果自己戴着白帽,那对方早在上一次就应打耳光了,因此自己戴的也是黑帽子,于是也会有耳光声响起;可事实是第三次才响起了耳光声,说明全场不止两顶黑帽,依此类推,应该是关了几次灯,有几顶黑帽。

金条问题

让工人为你工作7天,给工人的回报是一根金条。金条平分成相连的7段,你必须在每天结束时给他们一段金条,如果只许你两次把金条弄断,你如何给你的工人付费?

答:分成1、2、4段。利用1,2,4可以组合成1,2,3,4,5,6,7

拆字游戏

下面玩一个拆字游戏,所有字母的顺序都被打乱。你要判断这个字是什么。假设这个被拆开的字由5个字母组成:
1. 共有多少种可能的组合方式?
2. 如果我们知道是哪5个字母,那会怎么样?
3. 找出一种解决这个问题的方法。

个人解答:
1. A55=54321=120
1. 会依靠英文字母的规则等大致弄几种可能性出来。
1. 将弄出来的可能性的单词进行查找。

为什么下水道的盖子是圆的?

解:很大程度上取决于下水道的形状,一般为了使得各个方向的管子都可以接入到下水道中,所以下水道设计成了圆柱形,所以盖子相应的也是圆形。且圆形比较省材料,便于运输。

请估算一下CNTOWER电视塔的质量

首先在纸上画出了CNTOWER的草图,然后快速估算支架和各柱的高度,以及球的半径,算出各部分体积,然后和各部分密度运算,最后相加得出一个结果。

图像处理小结

阅读数 4249