毕业设计论文非接触人体测量技术中图像处理设计.doc

《毕业设计论文非接触人体测量技术中图像处理设计.doc》由会员分享，可在线阅读，更多相关《毕业设计论文非接触人体测量技术中图像处理设计.doc（41页珍藏版）》请在三一办公上搜索。

1、 分类号_ 密级_ UDC _ 学号 2008300016毕业设计（论文）论文题目非接触人体测量技术中图像处理设计thesis TopicThe contact of image processing technology body measurements学生姓名所 在 院 系轻纺工程与美术学院纺织服装系专 业 班 级机械0801班导师姓名职称2010年6月10日 编号： 毕业设计（论文）答辩许可证轻纺工程与美术学院 纺织与服装系 机械设计制造极其自动化专业陈涛学生所编写的毕业设计(论文) 61页，字数23874 ，符合毕业设计(论文)大纲的要求。经审查：该生已学完教学计划规定的全部课程，成

2、绩合格，毕业设计电子文档最后一稿已交，准予参加毕业设计（论文）答辩。相 关 材 料材 料 名 称数量毕业设计（论文）1册毕业论文缩写1册实习日记1册答辩汇报稿1份毕业设计（论文）电子版（最后一稿磁盘文件）1套指导教师： （签名）教研室主任： （签名）系 主 任： （签名）院 长： （签名） 2010年 6 月 日 毕业设计（论文）任务书毕业设计（论文）题目：非接触人体测量技术中图像处理设计毕业设计（论文）要求及原始数据（资料）：1.1 设计要求在非接触人体测量硬件部分得出的图像的前提下，通过基于深度优先遍历的Roberts算子从而完成边缘识别，再通过图像边缘像素点间距转换为实际参数。原始数据（

3、资料）第一阶段：毕业设计准备阶段1.基本了解非接触人体测量系统的工作原理及硬件构成。2. 将图像处理设计分为三个设计阶段。 第二阶段：拟定方案并进行设计1. 大学计划网站应用方案板块相关方案2. 实验指导书下册第三阶段: 软件调试阶段第四阶段：毕业设计论文缩写学生需向老师提交以下资料：1.毕业设计论文2.毕业（设计）论文全部电子文档，文件名格式：毕业设计（论文）主要内容：一、 硬件部分简介二、 软件部分设计1、 图的定义及数据存储结构2、 图的优先遍历设计部分3、 基于优先遍历的边缘识别部分、4、 像素点间距与实际参数间转换学生应交出的设计文件（论文）：1.毕业设计（论文） 1册2.毕业论文缩

4、写 1册3.实习报告 1册4.答辩汇报稿 1份5.毕业（设计）论文全部电子文档（最后一稿），文件名格式： 专业姓名：论文题目 专业姓名：论文缩写主要参考文献（资料）：1 翟文斌基于图像处理的人体测量D吉林大学2006-62 李昕，陈坚.基于MATLAB的数字图像处理.电脑知识与技术Vol.5,No.8,March 2009,pp.1979-19813 周亚罗,潘晓娣等.基于图像处理的轮廓提取方法应用.唐山学院学报.第22卷第6期2009年11月72744 王玉秀非接触式人体测量系统的研究一图像处理、人体围度曲线分析与计算D天津工业大学20035 马 瑾,陈立潮等.轮廓跟踪与边沿检测的图像自动识

5、别.中北大学学报(自然科学版) 2006年第27卷第5期4324356 王利辉.小波变换在图像边缘检测中的应用天津工程师范学院学报第17卷第1期2007年3月 17207 SPCE3200精简开发板eCos平台篇（多媒体实验）.凌阳科技实验指导书V1.0 2008-10-28 15208 刘正东,王颖等.服装人台建模中的视觉图像人体轮廓细化提取.计算机工程与应用2007,43(16) 2462489 陈冠楠,杨坤涛等,基于深度优先遍历的图像边缘检测方法.应用光学.第29卷第1期2008年1月141710 姚红革,杜亚勤等.基于小波分析和BP神经网络的图像特征提取.西安工业大学学报.第28卷第6

6、期2008年12月56857011 张进秋，李帼.图像像素距离与空间距离变换公式的求解.软件导刊.第8卷%第12期2009年12月179180专业班级 机械设计制造及其自动化0801 学生姓名 陈涛 要求设计（论文）工作起止日期： 2010.03.212010.06.14 指导教师签字 日期 教研室主任审查签字 日期 系主任批准签字 日期 第 3 页 中文摘要非接触人体测量技术中图像处理设计 -轻纺工程与美术学院-纺织服装工程系-机械设计制造及其自动化专业-0801班- 摘要该非接触式人体测量技术是指基于凌阳单片机中图像处理模块Eagle而设计的一种非接触式人体测量技术，包括测量方案设计、图像

7、获取、图像边缘识别、由图像求得实物实际关键参数，并利用MATLAB软件得以图像处理，从而使得人体测量比传统测量简单方便、精确可靠、比现代三维立体扫描测量节省成本，更适用于现实生活很多场合。本论文重在设计该技术中的图像处理部分，包括基于深度优先遍历的图像边缘识别以及由图像求的实物实际关键参数两部分。关键字人体测量；深度优先遍历；图像边缘识别；关键参数获取英文摘要The contact of image processing technology body measurementsAbstract: The non-contact measurement technology refers to

8、the human based on image processing module of sunplus microcontroller Eagle and design a non-contact measurement technique, including the human body measure scheme design, image acquisition, image edge detection, and obtained by image objects, and the actual key parameters of MATLAB software to imag

9、e processing, which makes human body measure than traditional measurement is simple and convenient, reliable, accurate than modern three-dimensional scan measuring cost saving, more applicable in real life on many occasions. This paper focuses on the design of the technology of image processing, inc

10、luding traverse the priority based on depth of image edge recognition by the image of objects and the actual key parameters of two parts.Keywords: Human body measurements； Depth-first traversal； Image edge detection； The key parameters、目 录扉页毕业设计（论文）答辩许可证毕业设计（论文）任务书1页第3页中文摘要 英文摘要 文献综述 1一、引言 1二、人体测量技术

11、的发展.1 三、人体测量学的应用 2 四、非接触人体测量技术的现状4 五、人体测量技术的发展前景4六、研究图像处理中尺寸自动获得的目的和意义5专题正文部分8 第一章引言8 第二章硬件设计8 第三章图像设计设计 10一.图的定义及存储结构10 二.图的优先遍历12三.图像的边缘识别14四.基于深度优先遍历的Roberts边缘检测方法19五.人体测量实际参数获取25中英文资料翻译27. 致谢32参考文献 33论文缩写34III太原理工大学毕业设计（论文）文 献 综 述学 院：轻纺工程与美术学院 系 别：纺织服装专业班级：机械0801 姓 名：陈涛指导教师：康莉一、 引言人体测量是通过测量人体各部位

12、的尺寸来确定个体之间和群体之间在人体尺寸上的差别,用从而为工业设计 、人机工医学等提供人体基础多个大规模的人体测量其中欧美国家占了大部分,亚洲国家约有而日本占了一半以上 。如CASER在美国 、荷兰 、意大利HQL协会提出了人体测量和增进人类福址计划，英国3D电在网上开展了三维人体数据方面的商务活动。非接触式人体测量技术是人体测量技术的计算机化，是数字化信息技术带来的又一项高科技产品。它不用接触人体，利用图像、光和波的形式完成测量。其用途是多方面的，如服装设计所需的体型描述、人体轮廓尺寸的测量、运动人体学研究、人体工效学应用等。随着时代发展和社会进步,人体测量技术必将在人类科学发展中发挥更大的

13、作用。二、人体测量技术的发展1、人体数据测量技人的作业状态一般有静态和动态两种形式,所以人体测量也分为静态和动态两种。从实用人体测量内容一般有以下三类:、形态的测量 它可以得到人体的基本尺度 、主要有人体长度测定(包括廓人体体积和重量的测定;人体表面积测定 。、生理的测定 主要内容有人体出力测定;人体触觉反应测定;任意疲劳测定等 。、运动的测定 主要内容有动作范围测定;动作过程测定;体型变化测定;皮肤变化测定等 。 2、从技术发展来看,人体测量技术可以分为普通测量技术和三维数字化人体测量技术 。 、普通测量技术 普通人体测量仪器可以采用一般的人体生理测量的有关仪器,包括人体测高仪 、直角规 、

14、弯角规 、三脚平行规 、软尺 、测齿规 、立方定颅器 、平行定点仪等,其数据处理采用人工处理或者人工输入与计算机处理相结合的方式 。此种测量方式耗时耗力,数据处理容易出错,数据应用不灵活,但成本低廉,具有一定的适用性 。 、三维数字化人体测量技术 从仪器本体的原理来讲,三维数字化人体测量分为手动接触式 、手动非接触式 、自动接触式 、自动非接触式等;最终可以根据所需速度 、精度和造价确定合适的方式,下面介绍典型的几种非接触式人体测量仪器 。 Loughborough人体扫描仪Loughborough大学联同马莎百货及Courtaulds内衣公司，利用其人体扫描搜集身体三围数据，当一个人站立不动

15、，投影在其身上的光线将被电视摄像机录取下来，身体形状用一系列横截面表达，从而建立三维身体的表面模型。TC分层轮廓测量方法TC，美国纺织及服装技术中心选用白光分层轮廓测量方法，来取得全身人体的三维描绘，与密栅云纹法相似，它利用白色光源来投射正弦曲线在物体表面，当物体不规则的形状令投射的密栅影子变形，产生的图样将可表示其物体表面的轮廓，并用六部摄影机检测，然后将所摄取的影像合成为一完整形象。英国防卫服装及纺织代办处之自动身体测量仪英国Colchester的防卫服装及纺织代办处选用分层轮廓测量方法来度量人体，他们开发了一部三维测量系统，定名为Auto-mate (自动身体测量仪)，跟TC相似，这个身

16、体测量仪可提供直接身体扫描的电脑数据，加上防弹部门的参与，他们可以制造防护盔甲，满足顾客贴身的防卫要求。Cyberware的全身扫描机与上述的密栅云纹投影系统不同，Cyberware于1995引进一个商品化的全身扫描机WB2和WB4。该机器用镭射扫描三角测量技术来获取三维影像。工作站的软件，控制整个扫描及移动过程。只需几秒钟便完成一次扫描，然后使用者便可以用工作站上的图像工具看扫描结果，多个扫描造型亦会结合成一个完整的人体模型。三、 人体测量学的应用人体测量学对人类的发展具有重要的研究和应用价值,主要体现以下方面:体质变异研究 对不同种族 、不同人群进行人体测量和分析比较,可以找出他们之间的共

17、同点与差异,找出人类体质特征变异的规律 。生长发育研究 对不同年龄群体或个体进行人体测量,绘出生长曲线和生长速率曲线,可以找出人体生长发育的规律 。为建立适应我国国民体型的原型提供依据，我国目前尚无适合本国国民体格的原型,而世界发达国家如英 、法 、美 、日等都早已形成较成熟的原型技术,并根据风格的不同形成各种流派,在服装设计和生产中起着重要作用 。要建立适合的原型,最根本的途径就是首先建立人体体型尺寸的检测系统,在不同区域进行大量的人体测量,为我国原型的建立提供数据依据 。在工业 、国防 、医学 、法医 、教育 、体育 、建筑 、美术等领域有广泛的应用 人体测量数据可以应用于机器 、家具 、

18、武器 、车辆和飞机座舱 、船舶 、房屋 、课桌等的设计,并形成了一门应用学科 人类工效学或人体工程学 。为标准服装人台设计和服装规格标准的制订提供依据,应用于服装立体裁剪 、商品检查或服装展示等 。虚拟环境 应用于因特网上购物 、电子商务 、产品广告 、人机工程研究等 。目前,基于人体测量等技术而建立起来的人体数据咨询 、仿真设计软件也较多 。如英国OpenErgonomics公司开发的PeopleSize人体数据咨询系统,包括英国儿童(从出生起)、成年人的尺寸以及其它一些国家人的尺寸,其中包括部分中国人人体尺寸(18245岁,这些尺寸是由新加坡南洋理工大学的Professor L . Lim

19、提供的)。这些数据是在19941995年间测量了13 678至16 443个样本得到的,基本覆盖了英国的各个阶层,包括人体全身尺寸 、人体头部尺寸 、手部尺寸 、足部尺寸等 。利用此人体测量数据库,他们还进行了一些人体姿势分析,座椅等的设计,为民航 、铁路 、汽车 、国防 、劳动安全等服务,如图3所示 。Delima公司11 (国际上较早的数字化企业)已经将3D虚拟人体溶入到从过程计划 、成本预算 、质量控制 、人机分析到数字化制造中;另外,基于开 放 的C商 业 平 台(open c2commerce platformOCP) , EDS Unigraphics公司提出了e2Factory概

20、念,也将虚拟人作为咨询 、仿真 、评价的一个重要因素 。Transom公司开发的Transom JACK人机工程软件,包括人体数据录入接口 、人体数据咨询系统 、人机工程仿真系统 、人机工程评价系统等 。其中虚拟人体建立在生物力学 、运动学 、人体测量学 、认知心理学等学科基础上,可以代替真实人体实现行走 、搬运 、举升 、关节运动 、视觉范围 、调节姿势等活动,评价安全姿势 、举升与能量消耗 、疲劳与体能恢复 、静态受力 、人体关节移动范围等人机工程性能指标。由于JACK具有的优势,已经在航空 、车辆 、船舶 、工厂规划 、维修 、产品设计等领域广泛应用 。长庚大学和台湾清华大学等院校和企业

21、已经花了近5年时间,联合进行了非接触式人体测量技术和台湾人体数据库的研究,取得了一定的成果 。四、非接触人体测量技术的现状非接触式三维人体测量技术（interactive 3D whole body scanner system）人体全身扫描技术，通过应用光敏设备捕捉设备投射到人体表面的光（激光、白光及红外线）在人体上形成的图像，描述人体三维特征。国际上常用的人体扫描仪有Telmat的SYMCAD、 Turbo Flash/3D、TC2-3T6、TechMath-RAMSIS、Cyberware-WB4、Vitronic-Vitus等。三维非接触式扫描系统具有扫描时间短，精确度高、测量部位多等

22、多种优于传统测量技术和工具的特点，如德国的TechMath扫描仪在20秒内完成扫描过程，可捕捉人体的80，000个数据点，获得人体相关的85个部位尺寸值，精确度为0.2mm；美国的TC2 通过对人体4.5万个点的扫描，迅速获得人体的80多个数据，可以全面精确地反映人体体型情况。英国的TuringC3D系统还可以捕捉表面的材质，对物体表面的色彩质地进行描述，在研究有标识的物体时非常有用。扫描输出的数据可直接用于服装设计软件，对人体进行量身定制。目前，人体扫描仪广泛应用于：人体测量学研究、服装工业（MTM量身定制系统，虚拟试衣）、娱乐业（如电影特技）、计算机动画和医学（目前最为广泛如 弥补术和塑型

23、手术）等领域。非接触三维人体测量技术虽然仅有二、三十年的发展史，但却能以其独特的优势逐步应用、并将普遍到与人体相关的各类产品的设计与研究中，使产品真正做到以人为本。在服装工业中，它加快了企业对市场反应速度；同时是开展服装电子商务必要条件和重要依据，它将服装生产与高科技紧密结合起来，使服装生产和设计更具个性化和人行化，提高了服装的适体性，对服装工业的快速发展有极大的推动作用。五、人体测量技术的发展前景随着计算机技术和网络技术的发展,人体测量技术也将呈现新的面貌 。地域的幅员广大，形成了地域性的人体差别；不同年龄、不同职业等形成的人体的差异，更使得人体数据多样化、复杂化。而为自身产品准确定位适合的

24、人群，使产品对定位人群获得较高覆盖率，是每一个产品设计者的目标之一。 这样，在复杂的数据环境中如何采集所需数据并达到统计所需要的基本量，是所有数据需求者要面临的课题。这也将呼唤和促使人体数据库社会化和企业化。社会化的人体数据库是为社会需求服务的，它的特点是人体数据量的极大化，并且经过长期的数据积累和多用途的统计分析，形成它的产业特点。 因此使用高效、便捷、准确的测量工具是社会化人体数据库采集数据的基础保障。智能化 人工智能技术的发展,为人体测量技术智能化 、人性化奠定了基础 。包括扫描过程的智能化 、人机界面的智能化 、数据采集与分类的智能化 、NURBUS曲面的自动合成与光顺智能化等 。网络

25、化 21世纪是网络的世纪,人体测量将依托网络向更广泛的领域拓展 。测量技术 、商业模式的网络化,是今后人体测量技术的必然趋势;设计过程 、制造过程和流通过程的一体化,将使人体测量在网络经济时代发生重大的变革 。 综上所述，我们可以看到，自动人体测量产品有着广泛的应用前景，它对各行业业的技术水平的提高具有重要意义。 六、 研究图像处理中尺寸自动获得的目的和意义（一）我的观点及论文题目对于毕业设计我的观点是：第一：通过这次设计能让我把大学四年所学的专业课都有所回顾，在做设计的同时我们不管是翻阅这几年所学的课本，还是上网查资料等等，都能使我对所学的课程有个系统的巩固。第二：通过做这次毕业设计，不仅拓

26、宽了我的见识，增长了我的阅历，同时也使得我从一名大学生到一名社会工作者之间有了一个很好的过渡。我所选择的毕业论文设计题目为：非接触人体测量技术中图像处理设计（二）做这篇设计的主要意义和目的随着人类文明的发展，社会劳动的工业化、自动化程度不断提高，工程人体测量学的应用已渗透到社会生产、生活的各个领域。人体测量学是人类学的一个分支学科，主要研究人体测量和观察方法，并通过整体测量与局部测量探讨人体的特征、类型、变异和发展规律。有关人体参量的测量工作进行得最多的，就是人体尺寸的测量。为了使各种与人体尺度有关的设计对象能符合人的生理特点，让人在使用中处于舒适的状态和适宜的环境之中，就必须在设计中充分考虑

27、人体的各种尺度。人体尺度主要有两类，即人体的静态结构尺寸和动态功能尺寸。在设计中所有涉及人体尺度的参数的确定，都需要应用大量的测量数据。设计中若不能很好地考虑这些人体参数，就很可能造成操作的困难和不能充分发挥人机系统的效率，例如：（1）在服装人体测量上，通过人体的正、侧面的图像对人的体型进行分类，从而有针对性的进行服装设计和调整，同时进美学评价；（2）在进行工具仪表、机器或工程系统设计时，需要掌握有关人体测量数据，以使各种显示和操作装置的尺寸、位置等设计更适合人的使用；（3）在建筑行业，确定各种空间尺度也离不开人体资料；（4）卫生部门用来评定儿童及成年人的体质发育、整形外科等领域也需要这方面的

28、资料，等等。由此可见，人体测量在各行业中都占有重要的地位，起着不容忽视的作用。做这片毕业设计的目的：通过了解学习SPCA563A图像处理模组、SPCE061A芯片的工作原理、主要硬件构成、内部电路及各引脚功能，还有对旋转平台的设计来总结和巩固大学所学的知识并为进入社会打一个好的基础。六、本课体研究思路及方案针对以上情况，结合国内人体测量技术领域的发展现状和需求特点，参考国外成熟的工业检测设备，本文在实际工程应用的基础上，提出了基于凌阳单片机SPCE3200的人体测量系统的技术方案。通过使用SPCE3200模组，直接拍摄人体正面和侧面的数字图像，自动进行三维立体标定，并提取出轮廓线的平面坐标，测

29、量获得人体相应部位的平面尺寸。再建立数学模型，进行围度拟合，从而得到人体相应的围度尺寸，而人体的长度尺寸则可以完全由平面测量的数据直接获取。(一) 论文提纲及各部分内容间的逻辑关系1、系统设计（1）测量系统硬件设计（2）图像处理即图像边缘识别设计（3）图像像素点间距与实际参数间转换2、图像边缘识别设计内容（1）图的数据结构设计（2）图的深度优先遍历设计（3）边缘识别方法的选择（4）基于深度优先遍历的Roberts边缘识别方法(二) 拟采用的研究方法与手段1确定硬件的整体连接方法及工作原理2了解图的数据结构及存储方式3了解各种边缘识别方法参考文献1 丁玉兰 ,郭刚 ,赵江洪. 人机工程学 M .

30、 北京理工大学出版社 ,2000.2 翟文斌基于图像处理的人体测量D吉林大学2006-6 3 赖维铁. 人机工程学 M .华中理工大学出版社 ,1989.4 李雯雯 ,张文斌. 信息化 :服装人体计测的发展方向 EB/ OL . h ,2001.6,5 王玉秀非接触式人体测量系统的研究一图像处理、人体围度曲线分析与计算D天津工业大学专题正文部分第一章 引 言现实生活中人们在很多场合需要对人体进行尺寸的测量。例如在为人体制做衣服时，需要对被设计对象进行身体尺寸的测量，即所谓“量体裁衣”；在一些医疗机构中对人体的检查以及对人体的尺寸测量，对于研究分析人体健康程度和一些机能参数例如人的吸引力、生育能

31、力等都是很重要的。人体尺寸测量技术已经由简单的人工接触式逐步转变为非接触式自动测量，基于图像处理的人体尺寸测量就是其中之一。现代人体测量技术大多使用三维人体扫描技术采集原始数据与图像，将所获取的信息综合处理得到人体各部位的三维尺寸，进行人体重建，三维扫描技术为该自动化测量的核心部分，例如:激光测量法、红外线测量法、密栅云纹法和摄影测量法等。由这些方法研制的量体系统结构复杂，体积庞大，成本高，从原理推断，测量精度应较高，但实际应用上尚存在问题。本论文是建立在凌阳单片机中的图像识别模组基础上建立的全新的非接触式测量技术，包括硬件设计及软件设计两大部分，本文重在软件设计中的图像处理部分，包括基于深度

32、优先遍历的图像边缘处理设计，以及对图像中关键参数的获取。第二章 硬件设计（由于本论文重在图像边缘识别级参数获取方面，故只对硬件设计作简要说明）本设计中所包含的主要器件有：自动旋转平台，基于凌阳单片机的图像识别模组包含摄像头模组，LCD模组和SPCE3200的开发板。它的工作原理就是通过图像识别模组采集和处理来自旋转平台上目标物体的图像数据从而得到他的各种尺寸，然后通过显示屏显示出来。工作原理：景物通过镜头生成的光学图像投射到CMOS图像传感器表面上，然后转为电信号，经A/D（模数转换）转换后变为数字图像信号，再送到数字信号处理芯片中处理并通过接口总线输出。其中CMOS影像传感器它在捕获图像信息

33、的过程中会实时的将图像数据在时钟的配合下传送到CSI单元，CSI单元在内部控制器的控制条件下完成数据的接收和处理，然后再把格式化的数据传送到指定的DRAM缓冲区中。然后在LCD上显示出来。如下图，当目标物体放在旋转平台上时，图像处理模组开始工作即光敏元件开始采集目标物体图像，传到SPCE3200中并开始处理图片，从中得到所需要的信息。然后，平台开始旋转，当转到特定位置时即旋转90度，平台停止旋转，从而是光敏元件得到目标侧面图片，通过这些图片我们就可以得到目标物体的相关数据。系统流程图示、测量示意图如图所示。、摄像头模组和SPCE3200开发板的集成盒自动旋转平台显示屏第三章 图像设计设计一.

34、图的定义及存储结构图（Graph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，即每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，虽然每一层上的数据元素可能和下一层中多个元素（孩子）相关，但只能和上一层中一个元素（双亲）相关；而在图形结构中，结点之间的关系可以是任意的，任意两个数据元素之间都可能相关。 首先先介绍一下图的定义:图是一种数据结构，它的形式化定义为Graph = （V，R），其中V=x|x dataobject ，R=VRVR= |P（x ，y） （x ，y V） 在图中的数据元素通常称做顶点（vertex），

35、V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。若 VR，则 表示从x到y的一条弧（arc），且称x为弧尾（tail）或初始点（initia1 node），称y为弧头（head）或终端点（terminal node），此时的图称为有向图（digraph）。若 VR必有 VR，即VR是对称的，则以无序对（x，y）代替这两个有序对，表示x和y之间的一条边（edge），此时的图称为无向图（undigraph）。 在计算机中有很多方法来存储图的信息，由于图的结构复杂，使用广泛，经常使用链式存储结构。一般应根据实际的应用，来选择合适的表示方法。常用的存储图的结构有：数组表示法、邻接表、十字链表、

36、邻接多重表一，数组表示法（邻接矩阵）。在此我们以邻接表作为研究对象。图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。如图1为无向图的邻接表示意图。有向图的邻接表有出边表和入边表（又称逆邻接

37、表）之分。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点；入边表的表结点存放的则是指向表头结点的某个头顶点。如图2所示，为有向图(a)的出边表和入边表。图1图2/以下是有向图的邻接表存储表示/#define MAX_VEXTEX_NUM 20typedef struct ArcNode int adjvex； /该弧所指向的顶点的位置 struct ArcNode *nextarc； /指向下一条弧的指针 InfoType *info； /该弧相关信息的指针ArcNode；typedef struct VNode VextexType data； /顶点信息 ArcNode *fir

38、starc； /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VEXTEX_NUM；typedef struct AdjList vertices； int vexnum,arcnum； /图的当前顶点数和弧数int kind； /图的种类标志二.图的优先遍历图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可

39、达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜

40、索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 图的深度遍历的C语言程序#include stdio.htypedef int datatype; /*假定线性表元素的类型为整型*/#define maxsize 1024 /*假定线性表的最大长度为1024

41、*/# define n 100 /* 图的顶点最大个数 */typedef char VEXTYPE; /* 顶点的数据类型 */typedef float ADJTYPE; /* 权值类型 */typedef struct VEXTYPE vexsn ; /* 顶点信息数组 */ ADJTYPE arcsnn ; /* 边权数组 */ int num ; /* 顶点的实际个数 */GRAPH;/*图的深度周游*/void DFS(GRAPH g,int qidian,int mark)/从第qidian个点出发深度优先周游图g中能访问的各个顶点g.num=0; int v1; markqidian=1; printf(%c ,g.vexsqidian); for(v1=0;v1g.num;v1+) if(g.arcsqidianv1!=0&markv1=0) DFS(g,v1,mark); 三图像的边缘识别边缘是图象最基本的特征. 边缘检测在计算机视觉、图象分析等应用中起着重要的作用,是图象分析与识别的重要环节,这是因为子图象的边缘包含了用于识别的有用信息. 所以边缘检测是图像分析和模式识别的主要特征提取手段。所谓边缘是指其周围像素灰度后阶变化或屋顶状变化的那些像素的集合,它存