全息图生成方法（通用7篇）
全息图生成方法 篇1
0 引 言
信息检索是指将信息按一定的方式组织起来,并根据用户的需要找出有关信息的过程和技术。随着互联网的兴起,网络上的信息资源急剧增长,在带给我们海量信息的同时,也带来了信息爆炸的问题,我们往往借助搜索引擎来寻找需要的信息,搜索引擎已成为生活中不可或缺的重要工具。
但是在进行网络信息检索的时候,搜索引擎返回的结果准确性却不能让人满意,常常在返回的结果中夹杂着包含检索关键词却不是用户所需要的网页。这是因为当前的搜索引擎仅把用户的查询关键词作为独立的词单元进行检索,却没有考虑关键词之间的语义联系,导致出现不相关的结果。
文献[1]分析了用户查询,得出结论是一般用户在查询中仅使用少量几个关键词(1～3个),但是没有对用户查询作进一步的处理。文献[2]利用句法分析将句子转化为概念图,但其方法不适合处理仅有少数关键词的中文查询。文献[3]分析了用户查询需求并对用户查询进行了两阶段的概念图生成工作,但其方法复杂且具有局限性,不能很好推广。
本文利用语义概念图模型,尝试在概念层次上对一类限定领域的中文查询需求做出处理,将其转化为<实体-属性-值> (<Entity-Attribute-Value>即<E-A-V>)耦合联系的语义概念图,使得在整个语义检索过程中不丢失概念信息,从而能对返回的网页结果根据用户需求的完整概念内涵进行相关性衡量,达到重排序的效果。
为了更集中有效地研究需求概念图的生成,本文选择较熟悉的软件领域查询作为研究对象,事实上得出的方法也具有较好的推广性。另外本文在处理限定领域的中文查询时,面临一般语料中相关领域数据稀疏且语料集合封闭的问题,利用搜索引擎来访问网络语料资源,作为贯穿文章的一个有意义的应用。
1 概念图模型及应用
文献[4]提出的汉语内涵逻辑理论及概念图模型能从汉语概念层面上表达其语义内涵,指出概念、实体、词语间的对应关系符合语义三角,如图1所示。通过<实体-属性-值> (即<E-A-V>,本文以E-(A)→V表示)序偶组的形式来表征概念内涵,将概念实体节点与其属性名及属性值节点相联结,形成表达完整内涵的概念图,其模型可应用于概念检索。
在查询中用户输入简短,复合结构居多,而关键词之间的语义联系隐藏在需求中,不便解读其内涵,针对这些特点利用概念图进行需求的概念内涵重构是十分合适的。作者在2010年3月21日使用Google搜索“诺顿杀毒软件2010版”,在结果首页出现如图2所示不准确实例。
从上述实例来看,在查询“诺顿杀毒软件”中,诺顿是软件的品牌,杀毒是其功能,生成的概念图应为:
软件-(品牌)→诺顿
-(功能)→杀毒
在结果网页中的“瑞星杀毒软件”因其概念图为:
软件-(品牌)→瑞星
-(功能)→杀毒
两者概念图不完全匹配,从而可以使不够准确的结果推后展示或者不显示。
同理,对查询“报告管理软件”的概念图为:
软件-(功能)→管理-(对象)→报告
将查询“报告管理软件”提交至Baidu返回的结果首页中不准确的结果如图3所示,其概念图应为:
报告-(内容)→软件-(功能)→管理
两者在概念图表示上大不一样,内涵上也相差较大,但由于结果中包含了需求的所有关键词,也作为相关性高的结果在首页返回给用户,使得检索的准确性下降,这便是概念图模型应用于信息检索的初衷和必要。
基于概念图的思想,将用户查询和网页文档的关键词组表示为概念图的形式,再利用匹配算法,可计算出概念图间的相似程度,即查询和结果的相关性,从而对搜索引擎的返回结果进行基于相关性的重排序。利用概念图应用于语义检索的完整设想流程如图4所示,而本文工作集中在需求分析部分。
2 框架流程
2.1 流程说明
将选取的中文查询作为输入,经过如下流程,处理生成需求的概念图:
(1) 预处理阶段 通过分词、词性标记、校正等步骤,将中文查询转化为带有词性标注的词序列。
(2) 联结图生成阶段 利用规则或搜索引擎的方法,将关键词之间建立联结,生成联结图。
(3) 属性求解阶段 利用获取的模板及搜索引擎的有效信息,对各类词对进行语义关系识别,求解其概念属性。
(4) 概念图生成阶段 结合联结图和属性求解结果,将联结图结构完善为概念图结构,得到中文查询的语义概念图。
2.2 框架流程图
3 生成方法
3.1 联结图生成
将用户需求生成联结图,本文分别利用基于搜索引擎信息的方法和规则转换方法做了实验,并对实验结果作了对比。
(1) 基于搜索引擎的方法
对中文用户查询需求W1W2…Wi…Wn,由式(1):
得到结果表,表中元素Wij=hits(Wi, Wj)表示以“WiWj”形式提交至搜索引擎的返回结果数,表1是一个结果表示例。
可以看出表1是对称矩阵,有Wij=Wji,即hits(Wi, Wj)=hits(Wj, Wi),且对角线元素均为0。再由式(2):
对每个Wi,与使f(Wi, Wj)=1成立的Wj相联结,已存在边联结的词对间无需再添加,这样得到联结示例如图6所示。
另外,作者还进行了Wij=hits(Wi, Wj)表示以““WiWj””(即WiWj两边添加引号)为查询形式提交至搜索引擎的返回结果数以及表示点式互信息公式(3)的实验,式(3)对每个Wi:
(2) 规则转换
对预处理得到的带有词性标注的词序列进行规则匹配转换,得到图6,规则由对用户查询日志的分析得出,部分规则如下,其中V表示动词,N、N1、N2表示名词,W表示任意词。
① WVN中V与N相联结形成V-N对;
② N1VN2中N1、N2与V相联结形成N1-V-N2,其中N1不为公司或品牌名。
以上规则也适用于多词查询。后文将有两种方法的实验结果对比。
3.2 属性求解
(1) 词性对的初步识别
对得到的联结图,对于其词性对可根据下列规则集(部分)进行语义关系的识别,A、D表示形容词、副词。
① A-N ⇒ N-(特征)→A
② V-N ⇒ N-(功能)→V
③ D-V ⇒ V-(状态/方式)→D
另外简单起见,对N1-N2中N1落入作者定义的一个公司/品牌集中已有词的判断为:N2-(公司/品牌)→N1;N1满足“*语/*文”形式(*表示任意词)的判为:N2-(语言)→N1;其余判为:N2-(领域)→N1。一般的,N1-N2常例化为N1-软件的情况。
(2) N-V的属性名求解
对于查询中频繁出现的N-V型复合结构,本文将其作为属性求解的重点。文献[5]经过分析,N-V对可大致划分为四类语义关系:对象、主体、状态/方式、范围/时间,各类语义关系示例如表2所示。下面是对N-V型词对间的语义关系进行识别。
① 模板获取及筛选
由于N-V词对在查询中所能获得的信息特征较少,本文考虑利用介词及部分支撑动词所构成的模板来作为指示其语义关系的特征资源,模板也从搜索引擎返回结果中获取。
首先选出四类语义关系中典型的种子词对各20对N-V对,通过将“*N*V*”与“*V*N*”形式查询提交至搜索引擎(查询需加配对引号,表示严格匹配,Google对此类匹配更为有效),挖掘出匹配以上形式的模板P为W1NW2VW3,其中W1、W2、W3为1词或者没有,如“当N进行V时”。
从获取的模板中选出规范的模板作为初步模板集,其中不是所有模板都能有效指示词对的语义关系。结合种子词对S1…Sm通过(3)式对模板P1…Pi…Pn打分,其中这四类语义关系表示为C1、C2、C3、C4:
其中Pi∈Ct,Sj∈Ct,t∈{1,2,3,4},m=1,2,3,4。hits′(Pi, Sj)表示种子词对Sj替换模板Pi中N、V后形成的查询提交至搜索引擎得到的返回结果数。
在对模板打分后,从每类概念关系的模板集中取出得分最大的10个模板作为最终模板共计40个,部分模板如表3所示。
另外由于种子对数量太少,不足以作为下文所需的训练集。作者对筛选后的模板集,将模板形式中N、V替换为“*”后提交至搜索引擎,利用与上文类似的方式挖掘表示每种语义关系的N-V词对,筛选后得到256个词对作为训练集数据。
② 语义关系识别
在得到指示模板后,对每个N-V对Ti,替换语义指示模板Pj中N、V后得到的查询提交搜索引擎后返回结果数hits′ (Pj,Ti) (j=1,2,…,40),作为模板Pj维度方向上的值。这样每个N-V词对用向量表示,如表4所示。
在将训练集数据及待识别的N-V词对在模板维度上表示为向量后,可进行机器学习的语义关系识别。
KNN是一种memory-based的惰性学习方法,是利用与其最近的k个元素中最大数量的类别作为分类识别结果,特殊的当k=1时即为最近邻学习方法,对向量Vi、Vj,这里的距离公式为式(5):
本文实验利用KNN学习方法来做语义关系的识别,完成属性求解的任务。
4 实验及分析
4.1 数据获取
本文分析的用户查询日志来源于搜狗语料,经过处理分析后提出以下选取原则:
(1) 选取的是中文规范查询
由于本文研究的是中文概念图的构建,为保证研究的专门性,去除了英文、不规范表述及夹杂英文、数字、符号等的查询,只选取了中文的规范查询。
(2) 选取的是限定领域查询
查询内容宽泛,包罗万象,本文希望通过一类典型的代表领域来作出探索,总结出能推广的方法。因为对软件领域词汇较为熟悉,且此类查询在总的查询集中占有一定比重,故选择软件领域查询作处理分析。
特殊的,选取了包含“软件”关键词的查询需求,且去除了软件学院、软件公司等包含“软件”但为其他领域的内容。
(3) 选取只包含单纯概念图的查询
这里的单纯概念图指的是不包含子概念图的非递归概念图。理由是本文希望对单纯概念图完成构建后,可以通过类似方法及语法chunk技术对递归概念图进行递归构建[6],作出这样的限定可以保证只在软件领域内进行实验,不必涉及更多领域及概念关系。如“笔记本电脑软件”包含子概念图“笔记本电脑”其上位是电脑,而“电脑软件”则不包含,为单纯概念图查询。
(4) 主要选取3词查询
由文献[1,3]的分析结果可得用户提交搜索引擎的中文查询需求关键词一般在1～3词之内,另外作者从国内某搜索引擎得到的真实日志数据分析得出3词及3词以内的查询占比约为70%,上述结论也和在搜狗日志中的分析结论大致吻合。
本文主要选取了典型3词查询,同时也有少量2词查询及多词查询,查询中包含广泛的词性组合。
4.2 实验及结果
利用中科院计算所分词系统ICTCLAS对选取的查询进行分词、词性标注等,并作进一步的纠正,如将标注不当的词性纠正、将误切分的公司或品牌名进行合并等,得到分词及词性标注后的查询集合192条。
利用3.1节中方法对查询建立联结图,人工作出正确率判断。方法的正确率对比见表5,其中行表示不同的处理方法。
从表中可以看出利用搜索引擎的方法不及规则转换的方法有效,在这个阶段本文采用规则方法处理的结果。联结图生成后利用3.2中方法对N-V词对进行语义关系识别,其中将挖掘的256对N-V词对作为训练集,实验应用KNN方法进行识别,结果如表6所示。
结果可以看出KNN能有效识别词对间的语义关系,本文利用该方法处理得到的结果生成概念图。最后对得到的概念图进行最终判断,得到正确率如表7所示,其中完全正确率依据生成的概念图正确数计算,精细正确率的计算根据生成正确的序偶组对每个概念图打分值在[0,1]间。
4.3 结果分析
实验显示方法能够有效生成需求概念图,是对用户需求进行概念图生成的有益探索,但是在方法过程中还有诸多需要改进的地方。
在生成联结图中,单纯利用统计信息的正确率不高,作者认为是因为从搜索引擎获取的信息还不能很好表征W1与W2的概念联结,更多是一种在网络文本语料中的共现程度,且存在噪声信息和搜索算法偏差的影响。该方法后,作者对查询需求作进一步分析,总结出有效的联结规则,利用规则进行转换,联结正确率有了较大的提高。
在语义关系识别中,在查询需求中的有用信息较少,不能提取丰富的特征用以识别,这时考虑网络文本的海量语料是有必要的,模板对提示词对的语义关系是有效的。在识别中基于KNN的方法是有效的,可以理解为待识别的N-V对与训练集中词对的语言习惯与向量表示有很大程度的相似。
同时还与文献[3]的工作作了比较,其在不含关系名情况下效果较好,包含关系名效果较差。因其领域不同、多为名词性短语且包含专名,对比仅作参考。考虑到本文工作较为简洁且易通用,是对语义检索领域的一个有益的探索。
5 结 论
本文对查询需求的语义分析中利用搜索引擎作为接口访问网络语料资源,综合利用了规则与统计信息的方法,逐步建立概念层次上的语义概念图。方法还有待进一步提高,但是表明利用规则及网络海量语料对查询需求的概念分析及概念图生成是有效可行的,同时对语义检索的后续流程也有肯定作用。
本文的工作还只是一个起点,目前还存在准确率不够,没有完全自动化等需要改进的问题,下一步的工作考虑利用更多信息资源如专业语料库,改进概念联结的建立与识别的方法,并且考虑总结归纳方法,用于复合概念图的生成以及更多领域的扩展推广,为未来的语义检索做好基础工作。
参考文献
[1]Spink A,Wolfram D,Jansen M B J,et al.Searching the web:The pub-lic and their queries[J].Journal of the American Society for Informa-tion Science and Technology,2001,52(3):226-234.
[2]Nicolas S,Moulin B,Mineau G W.Sesei:A CG-Based Filter for Inter-net Search Engines[C]//Conceptual Structures for Knowledge Crea-tion and Communication:11th International Conference on ConceptualStructures,Iccs 2003,Dresden,Germany,2001:21-25.
[3]Hui Liu,Jinglei Zhao,Maosheng Zhong et al.Two Phase Semantic A-nalysis of Real World User Queries[J].Journal of Computational Infor-mation Systems,2009,5(3).
[4]陆汝占.中文检索与汉语语义概念图表示[C]//中国计算机语言学研究前沿进展(2007-2009),2009.
[5]Zhao Jinglei,Liu Hui,Lu Ruzhan.Semantic Labeling of CompoundNominalization in Chinese[C]//Proceedings of the ACL Workshop ona Broader Perspective on Multiword Expressions,ACL,2007:73-80.
[6]Yi Hu,Ruzhan Lu,Yuquan Chen,et al.A New Hierarchical concep-tual Graph Formalism Adapted for Chinese Text Retrieval[C]//Pro-ceedings of IEEE FSKD 2007,IEEE Computer Society,2007,2:653-657.
全息图生成方法 篇2
在现今的互联网上,图片已经成为一种的必要信息载体,是影响网上购物成交量的一个重要的因素。商品图片可以分为计算机生成图片和相机拍摄图片,由于这两类图片所附带的信息类型不同,根据具体的处理需求,在很多场合需要将其区分开来进行不同的处理。例如,商家销售商品时,会提供一些附加的图片来介绍其商品。如尺码介绍、买家好评、店铺公告等,这些图片都是计算机生成图片,如图1所示。它们都并非与特定商品严格相关,会给基于图片的数据挖掘带来很大的干扰,因此需要在做数据挖掘之前,将其剔除出来。
现有的一些用于区分计算机生成图片和相机拍摄图片的判断方法[1,2,3,9,10],分别利用了图片色彩数、主颜色率、色彩饱和度、图片边缘锐度等判断项进行判断。本文对这些方法进行了实现,并采用互联网上的商品图进行测试,发现这些方法并不满足商品图的批量处理需求。通过对商品图中的计算机生成图片的观察,发现这些图片中大部分是文字图片或者视觉感很差、色彩暗淡的图片。针对这两类图片本文分别提出了区分文字图片和图像图片的判断项,以及视觉垃圾图的判断项。对同样的商品图测试集进行测试,发现采用这两个判断项进行的计算机生成图片和相机拍摄图片的区分,其运行时间、召回率、准确率优于之前的判断项。
1 相关工作
通过提取图片的特征来区分计算机生成图片和相机拍摄图片,可以应用于网络图片搜索,商品垃圾图的剔除,图像处理的优化等方面。由于这些需求,前面的学者提出了一些判断方法来实现计算机生成图片和相机拍摄图片的区分。
Athitos V等[1]提出了一种基于图片色彩数、主颜色率、相邻最远距离大于阈值的点数、色彩饱和度、颜色直方图相关性等判断项的综合判断方法。他们认为计算机生成图片的颜色比较单一,主颜色率比较高,相邻像素点的差别比较大,色彩饱和度高的像素点较多。并且计算机生成图片的颜色直方图和统计所得的计算机生成图片的平均颜色直方图的相关性大于与统计所得的相机拍摄图片的平均颜色直方图的相关性。最后采用决策树整合这里判断项,综合的判定计算机生成图片和相机拍摄图片。
Chen Yuanhao等[2]在Athitos V的工作的基础上做出了改进,采用高频色彩率代替了主颜色率;采用均值、标准方差、失真度这三个色彩参量[4]代替了颜色直方图判断项;提出了色彩空间相关性[5]判断项,即像素与其领域点像素相似的概率统计;提出了高频色彩空间区域判断项,即统计大块的单色区域面积所占的比例;沿用了相邻最远距离直方图判断项。
Rainer Lienhart等[3]提出了采用图片的噪声量来区分计算机生成图片和相机拍摄图片的方法。认为相机拍摄图片不可避免的存在自然噪声,而计算机生成图片所含的噪声较少。在文章中作者不但对计算机生成图片和相机拍摄图片做了区分,还进一步对计算机生成图片做了细分,分成幻灯片图片、漫画卡通图片和其他图片;并进一步将相机拍摄图片细分成相机拍摄图片,人工合成但是和计算机拍摄图片很相近的图片。
另外还有一些采用贝叶斯统计结构[6]、图像纹理[7]、色彩直方图和纹理方向[8]等来实现户外拍摄图片和户内拍摄图片、城市图片和乡村图片等各式各样的图片的区分,这些判断项设置不同的阈值条件,也可以应用于计算机生成图片和相机拍摄图片的区分。
本文采用商品图片集测试了上述文献中的方法之后,发现这些文献中提到的判断项在处理商品图时效果很差,不能有效的进行区分。主要是因为商品图为了显示的方便,所采用的图片压缩改变了原本图片的一些性质,如颜色数、主颜色率等,使得这些特征对计算机生成图片和相机拍摄图片的区分力度变弱,甚至不能区分。本文在总结这些方法的基础上提出了一种简单实用的区分商品图中计算机生成图片和相机拍摄图片的方法。
2 方法讨论
对于计算机生成图片和相机拍摄图片的区分,不管采用什么样的判断项,都存在一定的局限性,针对不同的数据集其所需采用的判断项也应当不同。现有判断项都有一定理论依据,下面测试了常用的几个简单的判断项,基于测试的结果,分析了其在商品图中失败的原因。并阐述了我们提出的判别方法以及实现结果。
2.1 图片预处理
对于大规模的图片处理,必须考虑商品图片的具体情况,以及精确度和运算时间的权衡。商品图片是指商家提供用于展示其所需销售的商品的图片,大部分是商家自己拍摄的该商品的图片,另外还有一部分网上流传的该商品的模特图片。
在互联网上的商品图,由于显示的需求一般都需要压缩到指定的尺度大小。压缩的过程往往附带了插值运算,而插值运算一定会改变图片原有的信息,使得相应的判断项的值发生改变,以致一些判断项失去分辨计算机生成图片和相机拍摄图片的能力。本文中的处理都是采用预先压缩到200×200大小的图片,我们直接调用了Image magick中的Zoom方法进行尺度压缩,该方法采用双线型插值算法实现。
图像像素可以表示为R、G、B三原色,根据存储器的不同分为32 bit和64 bit像素,即RGB的取值范围分别为(0,256)、(0,216)。某些判断项的运算时间和色彩空间的大小是存在必然联系的,色彩空间过大必将导致分类时间的增加,以至于不适应于互联网上批量图片的处理。比如,对色彩数这个判断项来说,在一个有2 000张图片的测试集中,如果色彩空间为(0,28),每幅图片所需的平均时间为184 ms;而如果色彩空间为(0,25),那么每幅图片所需的平均处理时间将变为2 ms。针对这样的情况,本文在处理的过程中,将会对不同的判断项使用不同的色彩空间尺度进行压缩,以适应实时需求。
在表1中列出了,测试的几个判断项的阈值设定,色度空间的压缩尺度,以及实验结果的召回率、准确率、Fmeasure和每幅图运行时间(ms/幅)。其中,Fmeasure=2×(召回率×准确率)/(召回率+准确率)。下面将逐项对这些判断项进行描绘,并阐述它们具体的实现过程。
2.2 现有判断项和判别失败原因
1)颜色数
通过颜色数的统计来区分计算机生成图片和相机拍摄图片是一条常用的判断项。普遍认为由计算机生成的图片一般颜色比较单一,而相机拍摄的相机拍摄图片其颜色是相对比较复杂。于是,可以统计图片的色彩数并设定一个恰当阈值,高于这个阈值的图片认为是相机拍摄图片,低于该阈值的认为是计算机生成图片。
该判断项在理论上有一定的道理,但是在对商品图的处理中,实际商品图片存在的尺度压缩以及色彩空间的压缩都导致颜色数的统计发生了变化。具体实现中,首先将图片压缩到200×200大小,然后将色彩空间压缩到(0,25),再提取图片的色彩数。图片的压缩处理中的插值操作使得原本色彩数比较单一的计算机生成图片色彩数增加了,而色彩较为复杂的相机拍摄图片的色彩数增加却不明显;同时色彩空间的压缩也消除了相机拍摄图片的细节颜色,计算机生成图片的色彩影响却比较小。上述的两项操作使得理论上色彩数差别比较大的计算机生成图片和相机拍摄图片实际统计的结果其差别已经不再明显。如图2所示,设置阈值为100时所得到的计算机生成图片其中有大部分是判断失误的。对10 000幅图片的测试集,平均每幅图片的运行时间为2.3 ms,其准确率为14/37,召回率为14/193。
2)主颜色率与次主颜色率
主颜色率即为图片中频率最高的颜色在图片中所占的比率。由计算机生成的图片往往背景比较单一,即对应的主颜色率往往比较大。可以通过主颜色率来区分计算机生成图片和相机拍摄图片,但是在互联网上的商品图往往都是商家自己拍摄的,而且习惯于将其商品放在一个单一的背景进行拍摄,如墙上,地板上等。在计算这些商品图时发现他们的主颜色率也很高,这就是失去了以主颜色率作为计算机生成图片和相机拍摄图片判断项的实际意义。
为了剔除上述的影响,我们采用了次主颜色率作为新的判断项,即在去掉最高频颜色后再计算新的最高频色彩数所对应的覆盖率。这样子计算的色彩覆盖率就摒弃了商品图背景的影响。测试发现对于衣物类图片来说,存在大量的纯色的商品。设置次主颜色率的阈值为0.3,最后得到的计算机生成图片如图3所示,从同样的10 000幅图片的测试集得到相应的召回率为8/193,准确率为8/97,可见本方法不能适应商品图中区分计算机生成图片和相机拍摄图片的需求。
3)图像边缘锐度
图像边缘锐度是统计像素与其周围四个像素相差距离比较大的像素点所占的比率。假设一个像素的色彩向量为(r,g,b),其中的一个4领域像素的色彩向量为(r′,g′,b′),则相应的距离定义为d=|r-r′|+|g-g′|+|b-b′|。由于在求取该值之前将图片的色彩空间压缩到(0,32),则d的取值范围为0到96。求得每个像素与其4领域中的四个像素的距离中的最大值,当该值大于某个阈值的时候,本文通过测试选定的阈值为33,将该像素认定为高锐度值点。最后统计这类像素所占的比率作为图像边缘锐度的判断项。
由于相机感光元件的性质,其边缘是平滑过渡的,所以相机拍摄图片的边缘锐度比较低。相对的,计算机生成图片是由计算机生成的其边缘显得比较生硬一些,则其边缘锐度比较高。但是前面已经提到商品图都经过图片压缩处理,其中的插值操作会将原本生硬的边缘过渡变得平滑。再加上色彩处理过程中色彩空间的压缩也使得该判断最后的测试结果很差,找到的计算机生成图片大部分为格子图案的商品,如图4所示。10 000图片集测试其平均每幅运行时间为4.3 ms,召回率为10/193,准确率为10/68。可见该判断项同样不适用于计算机生成图片和相机拍摄图片的分类判定。
4)图像饱和度
图像饱和度[1]也是在之前文献中作为判断计算机生成图片和相机拍摄图片的一个判断项。由于计算机生成图片一般使用确定的色彩,使得计算机生成图片普遍饱和度比较高,相对而言相机拍摄图片的饱和度比低。然而,测试发现,对于商品图这项判断是失效的。大量的商品图片,其中的商品色彩是比较艳丽的,图像饱和点也比较多。在处理的过程中,没法找到一个合适的阈值来区分计算机生成图片和相机拍摄图片。该判断项可以用于判断自然风景相机拍摄图片,但是不能用于商品图的判定。
从上述四个常见的判断项的测试结果我们发现他们不适用于针对商品图的处理,商品图为了显示的需要而进行的Zoom尺度压缩,使得这些判断项失去了原本的区分意义。同时,为了降低运行时间所采用的色度空间的压缩也使得这些判断项适用性降低。基于这些考虑,我们提出了新的判别方法来区分商品图中的计算机生成图片和相机拍摄图片。
2.3 我们的判断项
1)文字图片判断项
在一个有文字图片和图像图片的集合中,人眼一般可以很容易分辨出文字图片和图像图片,这说明文字图片和图像图片存在很强烈的视觉差异。而商品图中的文字图片一般都是计算机生成图片,如商家的描绘图片,买家好评等。从这一点考虑,我们提出一个实现简单、运行速度快的判别文字图片的判断项。
从视觉的角度来说,人眼能够很方便的分辨出文字图片和图像图片,首先是因为文字图片所带来的整体的视觉影响,也就是说,文字图片中横向或者纵向的像素的堆积效应。因此可以通过统计横向和纵向的像素统计直方图来对文字图片进行判定,如图5所示。如果该直方图呈现出特殊的分布,对于文字图片来说直方图会出现图5所示的大量的梯度分布。统计这些梯度分布就可以方便的判断图片为文字图片还是图像图片,我们将判断的文字图片视为计算机生成图片,将图像图片视为相机拍摄图片。
同样测试上述的10 000张图片集合,选定合适的阈值,最后得到的基于该判断项的计算机生成图片,如图6所示。从图中可以看到,通过该判断项可以方便的挑出文字图片,还有一部分标记尺码的图片。在测试的图片集中,该判断项的平均每幅所花的时间为1.6 ms,其召回率为75/193,准确率为75/142。相比于前面提到的几个判断项,判断是否是文字的该判断项其招回率和准确率都有较大的提高。而且,该判断项的运算时间和色彩空间的大小没有必然的联系,可以更大的保留原有图片的色彩,使得判断的真实性更强,且运算时间又能满足实际的商品图需求。
2)视觉垃圾图判断项
观察商品图中计算机生成图片,发现有一部分计算机生成图片颜色比较暗淡,它们的主体颜色为白色或灰色或纯黑色。这部分图片的主观视觉感受是很差的,也就是这样的图片即使不是计算机生成图片它所携带的商品信息从视觉的角度来说也是有限的。可以通过简单判断它们大致的色彩情况以及所携带的色彩信息量将它们判定为计算机生成图片。
首先,判断图片的主颜色是否为白色或纯黑色,如果是则认为该图片有可能为垃圾图。但仍需进一步判断,因为有一定数量的商品图是将商品置于白色或黑色的背景下拍摄的。于是,将图片分成九个块,分别求取每个块中的主颜色,如果主颜色为黑色的图片其九个块中的主颜色也为黑色,则判定该图片为计算机生成图片;如果主颜色为白色,多个块中的主颜色也偏白色,且图片的有效颜色数比较低,则判定为计算机生成图片;如果主颜色为白色,中间块中主颜色也为白色,且对角上有主颜色为白色的块,也判定为计算机生成图片。结果如图7所示。
由于上述对图片的主颜色都是大致的判定,对色彩多样性的细节没有考虑,所以在实际处理的过程中可以对图片的色彩空间做大尺度的压缩,这里,我们将颜色空间压缩到(0,8)。这样不会影响判断,却能大量的节约运算时间。
在上述的10 000测试的图片集中,该判断项的平均每幅所花的时间为1.9 ms,其召回率为52/193,准确率为52/76。
从上述的几个判断项测试的情况来看,如表1所示,针对商品图的数据特征,文字图片判断项和视觉垃圾图判断项准确率远高于其他判断项或者它们的组合;分析这两项判断项以及它们的组合所得到的召回率可见,这两项判断具有很高的互补性;从所有判断项组合判定所得的召回率和准确率来看,其他判断项的加入对召回率提高并不大,却大大的降低了准确率,由此可见文字图片判断项和视觉垃圾图判断项对其他判断项的覆盖率比较高;从每幅图片所花的时间来看,这两个判断项所花的时间相对比较低。于是将这两个判断项结合起来判断计算机生成图片和相机拍摄图片。在前面的数据中,文字图片判断项的召回率比视觉垃圾图判断项的高,也就是它比视觉垃圾图判断项对更多的图片做出了判定,并且它对单幅图片的运算时间也短于视觉垃圾图判断项。基于上述的考虑,在处理过程中我们先做文字图片判定再进行视觉垃圾图判定。采用同样的10 000张图片的集合进行测试,两项结合的平均每幅所花的时间为2.3 ms,其召回率为109/192,准确率为109/201。同时我们也测试一个更大包含40 000张图片的集合,其召回率为412/682=0.604,准确率为412/828=0.498。可见对于不同的数据集,其相应的召回率和准确率将会不同。并且召回率和准确率对同一个方法来说是相互矛盾的两个参量。
3 结论
本文从商品图的图片特征和商品图的实时处理需求入手,提出了区分文字图片和图像图片方法,以及提取视角垃圾图的方法,并将它们结合用于商品图的计算机生成图片和相机拍摄图片区分。目前400张/s图片的处理量可以满足商品图的批量快速处理需求,50%左右的召回率和准确率也远高于其他的几个判断项。本文所提到的区分商品图中的计算机生成图片和相机拍摄图片的方法通过大量数据的测试显示不管从运行时间还是从召回率和准确率来说都是简单有效的。
参考文献
[1]Athitsos Vassilis,Swain Michael J,Frankel Charles.Distinguishing Photographs and Graphics on the World Wide Web[C]//IEEE Workshop on Content-Based Access of Image and Video Libraries,San Juan,Puerto Rico,June20,1997:10-17.
[2]CHEN Yuan-hao,LI Zhi-wei,LI Ming-jing,et al.Automatic Classification of Photographs and Graphics[C]//IEEE International Conference on Multimedia and Expo,Toronto,Ont,July9-12,2006:973-976.
[3]Lienhart Rainer,Hartmann Alexander.Classifying Images on the Web Automatically[J].Journal of Electronic Imaging(S1017-9909),2002,11(4):445-454.
[4]Stricker Markus A,Orengo Markus.Similarity of color images[J].Proc.of SPIE(S0277-786X),1995,2420:381-392.
[5]Huang Jing,Kumar S Ravi,Mitra Mandar,et al.Image Indexing Using Color Correlograms:USA,US6,246,790B1[P].2001-6-12.
[6]Vailaya Aditya,Figueiredo Mario,Jain Anil,et al.Content-based hierarchical classification of vacation images[C]//Processing of the IEEE International Conference on Multimedia Computing and Systems,Florence,Italy,June7-11,1999,1:518-523.
[7]Gorkani M M,Picard R W.Texture orientation for sorting photos"at a glance"[C]//Proceedings of the12th IAPR International Conference on Pattern Recognition,Jerusalem,Israel,Oct9-13,1994,1:459-464.
[8]Yiu Elaine C.Image Classification Using Color Cues and Texture Orientation[D].Cambridge of USA:Department of Electrical Engineering and Computer Science of MIT,1996.
[9]Ng Tian-Tsong,Chang Shih-Fu,Hsu Jessie,et al.Physics-motivated features for distinguishing photographic images and computer graphics[C]//Proceedings of the13th annual ACM international conference on Multimedia,Hilton,Singapore,Nov6-11,2005:239-248.
全息图生成方法 篇3
关键词：虚拟现实,全景,3D校园
虚拟现实(Virtual Reality,简称VR)是一种借助计算机对复杂数据进行可视化操作的全新方式。其在技术思想上有了质的飞跃。虚拟校园则是GIS、VR和Web等技术的集成,以虚拟现实场景实现校园信息的浏览查询。全景图的生成与制作是构建虚拟校园的重要手段之一。
1虚拟校园的建模方法
一般来说,有两种方法可实现虚拟场景的建模。一种是基于图形的建模与绘制(Geometry Based Modeling and Rendering,简称GBR),一种是基于图像的建模与绘制(Image Based Modeling and Rendering,简称IBR)。GBR是先借助于软件构建现实的三维几何模型,再以固定观察点和方位,实现模型的描绘、光照处理、纹理映射以及变换投影等操作,最后生成虚拟现实;而IBR则借助计算机图像学直接建造场景,在视觉技术的帮助下,让新的虚拟图像从传统手段获取的已知图像中生成。与GBR相比,IBR的优越性有:一是无需繁琐的场景建模;二是不需要特殊设备;三是可不考虑景物的复杂程度。
在众多IBR实现方法中,借助于海量的全景图所形成的全景图集合来构成VR是一种常见的方法。
2全景图
2.1全景图概念
全景图(Panorama)是虚拟实景的一种表现形式,它基于鱼眼技术,外部人员可在一个固定观察点上从多个角度察看实际场景,立体感直观。同时,海量的全景图集合可不断变换观察点,更有利实际场景的表达,也不局限于场景的复杂程度。
2.2全景图的特点
对于高质量360°的全景图,至少应具备三个方面的基本特征:
(1)全方位:全面的展示了360度范围内的所有景象;并可用从各个方向来观看场景。
(2)实景:可通过普通照片拼合获得,几乎是现实的最直观反映。
(3)三维:借助于专业软件,可最大程度的感知立体空间。
根据全景图模型建立的基础投影不同,可分为立方体、圆柱体和球体三种。其中,柱状建模是指将获取到的图像重新投影到一个以相机焦距为半径的柱面上,是目前最为成熟的方法。
3全景图生成制作技术
3.1虚拟全景空间生成流程
一般来说,要生成一个区域内的全景空间,大致可按下面流程处理:先选择合适的模型,然后通过相机获取图像数据,经过投影变形和图像拼接后形成全景图像,再通过空间图像编辑器,就可以将不同地点和阶段、且数量巨大的静态全景图组织为动态全景场景。基本流程详见图1。
3.2全景空间的生成
3.2.1图像的获取和投影变换
校园内的图像数据可采用普通照相机或摄像机等来获取。为保证相邻照片位于同一个水平面内且有一定的重叠,可将机器固定在可水平旋转的支架上,使得镜头位于支架的中心点,每间隔一定的角度拍一张照片。普通方式所得到的图像数据属于中心投影,还需进行柱状投影变换。
3.2.2图像拼接
图像拼接过程分成图像匹配和平滑连接两个步骤。图像匹配是确定相邻图像的重叠范围;平滑连接主要是为了提高图像的质量。
(1)自动拼接:一些相机直接提供了360相片的拼接软件,或者在Photoshop软件中,采用“合并到HDR”功能及其编辑功能,更可以在一定程度上降低图像的扭曲与变形。
(2)手动裁剪拼接:手动裁剪拼接可以制作出更完美的图片,特别是当采集的图像出现偏差或扭曲时,可实时对局部细节进行调整。手动拼接建议用卡片机带广角镜头采集图像更好。
3.2.3动态全景图的生成
制作成动态全景图就需要借助Flash脚本来实现,或者使用其它一些软件工具也可以实现。下面分别介绍两种方法。
(1)Flash脚本实现
(1)参数设置:打开Flash的“首选参数”,进行actionscript3.0设置,添加类包路径。依次新建pv3d类包的五个基本要素:container,scene,camera,material和object,并添加object到scene中,最后架好摄像机。
(2)元件按钮的制作:启动Flash,导入静态全景图,并插入控制脚本、控制按钮、显示区、全景图等新层;插入放大、缩小、响应等元件按钮;插入“影片剪辑”元件,打开图片完成拼接。
(3)舞台按钮的制作:打开库,将按钮拖放到“控制按钮”层第1帧的舞台上,要保证“响应”按钮在全景图显示区域内,然后进行透明度、宽度、高度等参数设置;再在显示区域层第1帧的舞台上绘制一个与“响应按钮”等大的矩形;最后将库中的“拼接全景图”影片拖放到“全景图”层,并激活。见图2所示。
(4)脚本输入:选中“拼接全景图”影片,单击“属性”修改实例名;在“控制脚本”层的第1帧插入关键帧,打开脚本输入面板,依次输入脚本,实现停止、放大缩小,以及全景显示功能。最后,可按照.swf格式进行发布。
(2)Pano2QTVR全景图实现
尽管借助于Flash软件制作的动态全景图应用范围较广泛,但是由于涉及到不少的代码,对使用者会造成很多的不便。实际上,完全可以借助某些开发好的类,来实现利用AS脚本来控制照片的呈现效果。基于苹果核心的虚拟现实软件Pano2QTVR就是其中之一。
该软件提供了矩形球面投影、立方体型、圆柱形三个建模实体对象,实际上就是将Flash软件中的三维建模包集成实现,制作中可直接选择。在软件的“Flash”选项中,可设置图像是否开启自动旋转以及旋转延迟的时间,另外,可根据需要是否添加外部控制器按钮,并可简单调节按钮位置。
参数设置完成以后,选择了输出位置和输出格式后,就可直接创建动态全景图。Pano2QTVR虽然实现了动态全景图的输出,但相对来说其灵活性不足,主要是其范围、帧频、以及观察视角的选择都已经被固化。
4结论
基于IBR构建的虚拟校园中,动态全景图的生产和制作是其关键部分,而采用Flash脚本和其它应用软件均可以实现动态全景图,两者可相互兼容。实际当中,可根据动态全景空间的要求进行方法的取舍。
参考文献
[1]彭勃.基于Open GL的地形与单株林木的三维可视化研究[D].东北林业大学,2013.
[2]马萍.三维虚拟校园立体场景的设计与实现[D].山东师范大学,2013.
[3]谭同德,乔木,丁安国.基于Open GL的虚拟环境建模技术[J].河南科技大学学报(自然科学版),2006(02):37-39+6.
[4]王桐,王亮,马楠.基于全景图的虚拟现实技术在数字博物馆中的研究与应用[J].山西电子技术,2011(01):75-76+81.
[5]郭蕊,杨立新,侯阳,赵伟韬.虚拟现实技术在园林设计中的应用研究[J].沈阳农业大学学报(社会科学版),2009(06):738-741.
真彩色全息图的研究 篇4
彩色全息图的记录和再现是全息显示中的一个重要内容。体积全息图利用厚乳胶记录介质记录的多层干涉条纹的布拉格衍射效应,能用白光再现出很好的真彩色全息像[1]。但是这种全息图只能记录在厚乳胶上,不能用模压方法转印在聚脂膜上。现在大量应用的全息防伪标识属于模压全息产品,其彩色化常采用单色激光多次记录编码的彩虹全息来实现,一般称作假彩色全息图。人们也企图利用这种编码彩虹全息图来实现把彩色图片制成彩色全息图,这在全息防伪标识的制作中将有广阔的用途。把彩色图片制成彩色全息图,一般要用红、绿、蓝三种波长激光器和全色全息干版把一张彩色透明片的三种颜色信息记录成三个彩虹全息图,这种合成的彩虹全息图在白光照明下可再现出真彩色全息像[2]。另外也可先把彩色图片按红、绿、蓝三色分色为三张黑白正片,以不同的物、参光夹角用单色激光器在同一全息干版上记录下这三张分色片的彩虹全息图,用白光照明这全息图仍可再现出真彩色象[3]。目前真彩色全息图的制作方法较多[4~6],我们采用的方法是用安装有三色光栅的照相机直接拍摄彩色景物,通过一次暴光,把彩色景物的红、绿、兰信息编码记录在一张与三色光栅密接的黑白胶片上,用单色光以不同的物、参光夹角在同一全息干版上记录下这张分色片的彩虹全息图,用白光照明这全息图可再现出真彩色像。本方法制出的彩色全息图色彩清晰、还原性好。
1 编码片的获得
在照相机中安装三色光栅,三色光栅紧贴在相机中的黑白胶片上,用照相机直接拍摄彩色景物,其景物的彩色信息通过三色光栅成像于在黑白胶片上,这样通过三色光栅的一次空间编码在黑白胶片上获得一张彩色景物图像的编码片,即彩色景物的信息按颜色组分编码记录到一张黑白胶片上。
我们可以把三色光栅[7]写成:
其中k为常数,p0为三色光栅的空间频率,x,x',x''和为红、绿、蓝三种光栅的取向。其x和x'及x和x''的夹角分别为90°和135°。
景物T(x,y)透过三色光栅TT=(x,y)在全色黑白胶片上成像,经过一次暴光和感光冲洗并处理后,得到:
如果能控制γ=2,则得到黑白编码片的振幅透过率为
其中k'为常量,tp是tr,tg,tb的线性函数,从上式知,彩色景物的信息通过三色光栅一次暴光记录在同一张黑白片上,实现了编码。
2 彩色全息图编码片的分色记录过程
图1是编码片的分色记录光路图。一单色光(He-Ne激光)由M1反射经第一个半波片后进入一偏光分束器,分为两束振动方向相互垂直的光Ⅰ、Ⅱ,光束Ⅰ可经分束镜分别以各自的入射角入射,光束Ⅱ经第二个半波片后,其光的振动方向改变并同光束Ⅰ的振动方向一致,经过M2反射扩束准直后射在黑白片OI上,此黑白片位于透镜L1的两倍焦距处,从透镜上衍射的光在透镜的焦平面上形成三个一级衍射焦点,它们分别载为原彩色图像中的红色信息、绿色信息和蓝色信息。分别挡住其中两个信息,让第三个信息的光射到一毛玻璃G上,散射光再通过后面的透镜L2和狭缝S,与某一角度的参考光干涉记录于干版上,即:先挡住绿、蓝信息,光开关E1打开,E2、E3关闭,让载红信息的物光与参考光干涉记录在干版上;然后打开光开关E2,关闭E1、E3,让载绿信息的物光与参考光干涉记录在干版上;最后挡住红、绿信息,打开开关E3,关闭E1、E2,让载蓝色信息的物光与参考光干涉记录在干版上。这样通过三次暴光把一张黑白编码片的红、绿、蓝三种透光信息分布以不同空间频率的全息图方式记录到同一张全息片上。下面给出从编码片中取出红、绿、蓝三色信息的数学描述。
图1中用激光束照明黑白编码片OI,经过透镜L1的焦平面滤波,最后在毛玻璃G上得到含某种颜色信息的图像,设振幅为1的平行光透过编码片OI的光场为
此光场经透镜L1后在其焦平面(ξ,η)上的场分布为
其中Tr,Tg,Tb分别是tr,tg,tb的付里叶变换,f是变换透镜的焦距,f0是光栅的空频,an是付里叶系数。由此式可见在ξ,ξ',ξ''轴上的付里叶频谱的不同级次将线性地色散开,如果光栅的空频f0大于彩色象所含的最大空频的二倍,则不同衍射级次不会相互重叠[8]。
由于所用的是单色激光,在经透镜后成的三基色信息的像中,若挡住绿、蓝信息的频谱,则可得空间谱面P2上相应的红色信息的频率成分为:
同理在P2上有绿色信息和蓝色信息的频率成分分别为:
这三种频率成分经透镜成象到毛玻璃上的过程,是一个付里叶变换过程。因为红色信息频率成分在毛玻璃上的像场分布为:
红色信息成分在毛玻璃G上的光强分布为:
这就是原彩色景物像的红色成分的光强分布。
同理,绿色和蓝色信息频率成分在毛玻璃上的光场分布分别为:
它们在毛玻璃G上的光强分布为:
这分别是原彩色景物像的绿色成分和蓝色成分的光强分布。
通过空间滤波,从编码片中解出了三种颜色成分的光强分布信息,以供作彩色全息图用。这里实际上是三次暴光同时记录了三个不同物参光夹角的三种颜色信息的三个彩虹全息图,其合成起来可用白光再现出一个真彩色像。
3 真彩色全息图的再现
按彩虹全息图的再现原理,每一种颜色信息对应的全息图的再现光都将在原物光狭缝的位置会聚成一系列色散的彩色狭缝像[9]。我们在不同的狭缝窗口处将看到不同颜色的彩虹像。对于这一由三张彩虹全息图合成的全息图来说,在同时再现出三张全息记录的同时,各全息图在原物光狭缝位置分别会聚成色散的彩色狭缝像。由于在记录这三种颜色信息的全息像时用了不同夹角的参考光束,因此再现出的三个像的衍射光方向就不同,这就使得三组色散彩色狭缝在空间的位置将在同一平面上互相错开。如果让记录红色信息彩虹全息图再现像的红色狭缝,记录绿色信息彩虹全息图再现像绿色狭缝和带蓝色信息再现像的蓝色狭缝三者在空间重合在一起,则在此重合处将看到原彩色照片所含红、绿、蓝三色信息以同样的红、绿、蓝三色重新合成在一起,因此可看到一个真彩色全息图像。我们采用本文的方法较容易得到了这种真彩色图像。
4 结论
本文提出的制作真彩色全息图的方法有以下特点:
1)用加有三色光栅的照相机直接将彩色景物的信息记录在黑白胶片上获得一张彩色图像的编码片,避免了先制作彩色透明片,再将彩色透明片通过三色光栅进行分色记录的复杂过程。
2)实验中是在同一张全息片上记录三个彩虹全息图,无须制作三张分色掩膜信息的全息图,避免了定位对准的困难,简化了操作步骤。
3)按要求将参光分成三束,分别对三路参光的强度、物参光夹角反复调整,不必在记录过程中改变光路,从而确保参考光方向定位。
4)用本方法制作多个彩色合成全息图,可节约大量胶片,简化合成全息图的操作过程。
5)用该方法获得的真彩色全息图,衍射效率高,其再现像效果优于单色像,像的色彩清晰,还原性好,能充分反映原彩色景物的颜色层次。
摘要：真彩色全息图的制作方法较多,为了提高真彩色全息图的质量,用安装有三色光栅的照相机直接拍摄彩色景物,通过一次暴光,把彩色景物的红、绿、蓝信息编码记录在一张与三色光栅密接的黑白胶片上,用单色激光同时再现出所记录的三种颜色的光强分布并将它们记录在一张全息片上作成彩色全息图,该方法的显著优点是制作过程中无须获得三张分色掩膜信息的全息图,改进了分色过程中的定位对准问题,提高了全息图的衍射效率,再现象的色彩明亮、保真度较高、还原性好。
关键词：彩色全息图,三色光栅,彩虹全息图,黑白编码片,颜色信息
参考文献
[1]李森森,刘守,张向东.用SLAVICH全息干版制作真彩色DANISYUK全息图技术[J].激光杂志,2000,21(4):7-8.
[2]Kzuhiko Ohnuma,Fujio Iwata,Color rainbow hologram and color reproduction.Appl.Opt.,1988,27(18):3859-3863.
[3]范诚,江朝川,郭履容.一种新的真彩色彩虹全息术[J].光学学报,1991,11(11):1032-1035.
[4]王丁,曾毅,三色光栅制作真彩色全息图[J].激光杂志,2004,25(3):48-51.
[5]王丁,李劲松.散射光方法制作真彩色全息图[J].激光杂志,2003,24(1):45-47.
[6]龙涛.用全息分色法制作彩色全息图[J].激光杂志,2001,22(6):60-62.
[7]母国光.白光光学信息处理及其彩色摄影术[J].物理与工程,2001,11(1):4-5.
[8]母国光,羊国光,庄松林.光全息及信息处理[M].天津:南开大学出版社,1986,366-370.
全息图生成方法 篇5
在程序分析领域,控制流图用以刻画程序的控制结构[1],在优化编译器设计[2]、程序测试[3]和程序结构复杂度分析[4] 中应用广泛。
控制流图可定义为有向图G=<Ns, Es>,其中,Ns是节点的有穷集合,Es是有向边的有穷集合且Es⊆Ns×Ns。一个控制流图有一个唯一的入口节点Entry∈Ns,其入度为0,有一个唯一的出口节点Exit∈Ns,其出度为0。控制流图中的一个节点对应源程序的一个基本块[1],即一段只能从它的开始处进入,并从它的结束处离开的线性代码序列。控制流图中的一条有向边代表一个程序转移。
文献[4]和文献[5]曾分别提出基于结构程序的程序复杂度分析和控制流图构造方法,在他们提出的方法中,没有考虑goto、break、continue和return语句对控制流图结构的影响,而实际的程序控制流图分析工具设计却不能回避这个问题。文献[6]提出了一种基于图转换的控制流图构造方法可以解决goto等语句的控制流图构造问题,但该技术较复杂,需要先将源程序编译为抽象语法图,然后再用图转换将其转化为控制流图,且用该技术构造的控制流图不太直观,难以直接应用于程序优化和复杂度分析。根据控制流图节点与基本块的对应关系,下文提出一种基于基本块标识的程序控制流图构造的方法,采用该方法实现的C语言[8]控制流图生成器可经过一趟编译就构造出程序的控制流图。
1 C语言程序控制流图生成器设计
基于基本块标识的控制流图构造方法的要点在于标识基本块,而标识基本块的要点在于识别基本块的第一条指令(对于源程序分析而言,一条基本块的指令为一个测试表达式或一条可执行语句)。基本块的第一条指令称为首领,只能是子程序的入口点、分支指令(含测试表达式和goto、continue、break等语句)的目标,或直接紧跟在分支或返回指令之后的指令[1]。显然,一个首领到下一个首领间的所有指令构成一个基本块。
C语言控制流图生成器采用以下方式实现:对每类不同语句设计一条“翻译”规则,“翻译”规则按以上原则标识基本块、构造控制流图节点,并根据具体语句的控制流语义生成控制流图有向边。“翻译”规则用翻译模式描述,这样,利用编译器的自动生成工具bison[8]就可以快速实现控制流图生成器设计。
C语言程序控制流图构造首先遵照以下几条原则:
(1) 每一个子程序生成一个单独的控制流图。在语法分析刚进入子程序体的时候,初始化控制流图,生成子程序入口节点和出口节点。
(2) 控制流图的有向边用控制转移的表达式的值作标签。控制流图的节点标识基本块,用一个唯一的整数编号加该节点对应的基本块作标签。
(3) 跳过空语句和变量声明语句。对赋值、过程调用、goto、break、continue、return等简单语句,先单独为其构造一个节点,然后根据1.1节方法合并属于同一基本块的节点。
下文遵照以下约定方式介绍其他的控制流图构造规则:语句的语法规则[7]用产生式描述,语法变元用<>括起来,语法变元后的大写英文字母用于表示出现在具体位置的语法变元。各语句的翻译动作用自然语言描述,其中术语节点的语句指的是控制流图节点对应的基本块中的语句,术语语句的节点指的是语句所在基本块所对应的控制流图节点。
1.1 组合语句和语句块
组合语句和语句块的语法如下:
<组合语句>→{<语句块>} (1)
<语句块>→ ε (2)
| <语句块B> <语句S> (3)
语句块的控制流图可以有多个出口节点,出口节点是那些出边的目的节点不在语句块流图内的节点。语句块的出口节点分五类:第一类出口语句为continue语句的continue节点。第二类是出口语句为break语句的break节点。第三类是出口语句为return语句的return节点。这三类节点的出边都可采用采取“回填”技术生成,即先用一个链表记录下所有目的节点相同的节点,再在以后明确其目的节点地址时,回头生成每个链表元素到目的节点的有向边。用于管理该三类节点“回填”的链表分别称为continue链表、break链表和return链表,continue链表、break链表在包含continue、break语句的各种复合语句分析过程中“回填”,return链表在子程序分析结束时用出口节点“回填”。第四类是goto节点,即出口语句为goto语句的节点,goto节点出边的构造在1.2节详细说明。其他出口节点为第五类普通出口节点,如出口语句为测试表达式或赋值语句的节点,一个语句块最多只有一个普通出口节点。和普通出口节点出边指向相同目的节点的出口节点又称为正常出口节点,正常出口节点用语句块或语句的out链表管理。
组合语句的控制流图和语句块的控制流图相同。对结构如语法(3)的语句块,假如语句块B为空,语句块的控制流图即语句S的控制流图,否则,将语句S的out链表复制为语句块的out链表,分三种情形生成控制流图:
(1) 语句块B的出口语句为continue、break、goto或return语句。
语句S的入口指令为基本块的首领,语句块控制流图图例如图1(a)所示。
(2) 语句块B的出口语句为if、while、do、switch、for等复合语句。或语句S为do、while、case、default语句或标号语句。
语句S的入口指令为基本块的首领。语句块的控制流图图例如图1(b)所示。
(3) 非(1)(2)两种情形。
语句S的入口指令和语句块B出口语句属同一基本块。将语句块B出口语句的节点和语句S的入口节点合并为语句S的入口节点。语句块控制流图形如图1(c)所示。
1.2 无条件跳转语句和标号语句
无条件跳转语句和标号语句的语法如下:
<无条件跳转语句>→goto<标号L> (4)
<标号语句>→<标号L>:<语句S> (5)
无条件跳转语句和标号语句的控制流图构造使用了一个GOTO表。GOTO表中记录包括三个域:第一个为label域,域元素为goto语句跳转到的标号语句的标号;第二个为target域,域元素为标号语句的控制流图节点地址;第三个为list域,域元素为一张链表,链表元素为跳转到标号的无条件跳转语句节点的地址。
标号语句为基本块的首领。分析到含无条件跳转语句时,将跳转语句的节点地址加入标号L对应记录的list域的链表中。分析到标号语句时,首先将语句S的控制流图复制为标号语句的控制流图,然后再查找GOTO表,在标号L的记录的target域中填入标号语句的控制流图的入口节点地址。在子程序分析结束时,遍历GOTO表,对每条记录,用记录的target域“回填”list域,生成所有list链表元素到其目的节点的有向边。
1.3 选择语句
C语言选择语句包括if语句和switch语句。
1) if语句
if语句的语法如下:
<if语句>→if(<测试>)<语句T> (6)
| if(<测试>)<语句T>else<语句F> (7)
语句T、语句F的入口指令均为基本块的首领。将if语句的测试节点、语句T的out链表元素、语句F 的out链表元素(如果有语句F的话)插入if语句的out链表。形如语法(6)、(7)的if语句的控制流图分别如图2(a)、 (b)所示。
2) switch语句
case、default语句只能和switch语句配合使用,常把它们合称switch-case语句。三种语句的语法如下:
<switch语句>→switch(测试)<组合语句> (8)
<case语句>→case<常数表达式> (9)
<default语句>→default (10)
case、default语句为基本块的首领。在分析switch语句的组合语句前先创建一个case链表,当分析switch的组合语句时,每分析到一条case语句,在链表中插入一个元素,元素包括case语句的常数表达式值和该语句节点地址信息,default语句当作常数表达式值为default的特殊case语句处理。分析完组合语句,根据case链表元素中的常数表达式值和case节点地址信息,生成测试节点到所有case节点的有向边,有向边的标签为case语句的常数表达式值。分析完switch-case语句,把组合语句的out链表和break链表合并为switch-case语句的out链表。switch-case语句控制流图如图3所示。
switch-case语句中可嵌套有switch-case语句,不同嵌套层次的case语句给控制流图的生成带来困难。为了解决switch-case语句嵌套问题,在分析子程序程序体之前先创建一个空的case栈,栈中元素为case链表,新创建的case链表总压入栈的顶部,当前switch语句和case语句分析时总是使用栈顶的case链表,分析完一个switch语句之后立即从case栈顶弹出该switch语句的case链表。类似的处理方法还应用于含break、continue语句的复合语句的控制流图构造中。
1.4 循环语句
C语言包括while、do和for三种循环语句,while、do两种语句的控制流图构造方法类似,仅以while语句的控制流图构造方法为例。
1) while语句
while语句的语法如下:
<while语句>→while(测试)<语句S> (11)
语句S 的入口指令为基本块的首领。分析完while语句,把测试节点和break链表中的元素全部加入while语句的out链表。生成的while语句控制流图如图4所示。
2) for语句
for语句的语法如下:
<for语句>→for(<初始化表达式>;<测试>; <更新表达式>)<语句S> (12)
初始化表达式和更新表达式用于给for循环控制变量赋初值和更新控制变量,其控制流图构造方法与赋值语句控制流图构造方法相同。
for语句的初始化表达式、测试、更新表达式可以为空。空初始化表达式和更新表达式视作空语句处理。for语句的控制流图在测试为空与否的情形下有所不同:
(1) 不含测试的for语句的控制流图与以下的for等价语句块A的控制流图相同。
<for等价语句块A>→<初始化表达式>;L:<语句S>;<更新表达式>;goto L; (13)
因此,采用语句块和goto语句的控制流图构造方法可构造出for等价语句块A的控制流图。
(2) 含测试的for语句的控制流图与以下结构的for等价语句块B的控制流图相同。
<for等价语句块B>→<初始化表达式>; while(测试){<语句S>;<更新表达式>;} (14)
因此,采用语句块和while语句的控制流图构造方法可构造出for等价语句块B的控制流图。
2 结束语
CfgGen基于1节介绍方法实现,利用CfgGen生成的求最大公约数子程序的控制流图如图5所示。
CfgGen构造的控制流图节点标识出程序的基本块,可以很方便地用于程序分析和优化[2,3]。由于各种命令式语言的语句结构及其控制流语义相似,且CfgGen程序具有基于规则的特点,因此,将CfgGen移植为其他语言的控制流图生成器较简单,其维护也较方便。
摘要：设计一个实用的程序控制流分析工具需要解决非结构程序中goto等语句的控制流图构造问题。C语言程序控制流图生成器CfgGen的设计采用基于基本块标识的控制流图构造方法解决该问题。CfgGen程序基于规则,通过语法制导翻译标识基本块、构造控制流图,易移植和维护。CfgGen构造的控制流图标识了基本块,可以很方便地用于程序分析和优化。
关键词：控制流图构造,基本块标识,语法制导翻译
参考文献
[1]Nielson F.Perspectives on programanalysis[J].ACMComputing Sur-veys,1996,28:Article Number 168.
[2]Muchnick S.Advanced compiler design and implementation[M].Nether-lands:Elsevier Science Publishers,1997.
[3]Pressman R S.Software engineering:a practitioner’s approach[M].6th ed.New York:McGraw-Hill Science Companies,2004.
[4]赵一心,王振宇.结构化程序复杂性度量方法的分析[J].计算机学报,1987(4):235-247.
[5]单永明.一种源程序到控制流图的自动生成方法[J].小型微型计算机系统,1996,17(10):45-49.
[6]Smelik R,Rensink A,Kastenberg H.Specification and construction ofcontrol flow semantics[C]//Proceedings of the Visual Languages andHuman-Centric Computing(VL/HCC'06),IEEE Computer Society,2006:65-72.
[7]ISO/IEC 9899-1999 Programming languages-C[S/OL].ISO,1999.[2008-08-02].http://www.open-std.org/JTC1/SC22/WG14/.
全息图生成方法 篇6
随着全息技术迅速发展,传统的全息图在观赏性、技术性方面已不能满足发展需求。于是相继出现各种动态全息图,如动态合成全息图、三维双视全息图和动态体视全息图等[1,2,3]。其原理是设法把全息再现光波限制在空间某一个窄带区域内,利用不同窄带区域来显示三维物体的不同姿态,通过一序列分立的窄带区域效应使观察者获得三维动态效果,该类全息图具有很强的艺术观赏价值和防伪功能。
三维动态合成全息图是采用分立空间序列的物体不同侧面的多幅图像拍摄而成,传统拍摄方法需要多次人为调整物体的序列不同侧面和窄缝位移,过程繁杂,拍摄效率低,从而导致这种全息图在全息防伪标识的实际应用上受到限制。
本文提出一种综合计算机技术、单片机原理[4]和光电子技术等现代信息处理手段,研制一套自动控制系统来控制载物台旋转,改变物体有序的不同侧面和窄缝的移动,实现三维动态合成全图的自动化拍摄,改善传统拍摄方法效率低的缺陷,有利于推动全息防伪标识产品市场化发展。
2 自动拍摄三维动态合成全息图的制作系统
根据合成全息原理和二步法彩虹全息术提出一种三维动态合成全息图自动拍摄系统,用于二步法彩虹全息的第一步记录过程。该系统针对传统合成全息图制作中存在的诸多困难,采用了由计算机自动控制的设备代替传统光学元器件,以实现三维合成全息图的自动化拍摄。
实验装置如图1所示,氦氖激光器发出的光束经反射镜M反射,通过快门到分束镜BS分成两束,一束经反射镜M4到扩束镜SL2扩束照射被拍摄物体,物体表面产生的漫反射光作为物光波投射到H1底片上;另一束光经反射镜M1、M2和M3反射到扩束镜SL1,扩束后经透镜L准直获取平行光作为参考光投射底片H1上和物光产生干涉记录拍摄物体的信息。图1中计算机、可编程控制器和X、Y步进电动机组成控制部分,在计算机中运行专用的控制软件,设置相关参数,通过RS-232接口向可编程控制器发送指令去控制X、Y步进电机(X步进电机控制载物转盘转动,Y步进电机控制H1窄缝移动架移动)移动和快门曝光。
3 光学系统参数设计
如图2所示,利用双目视差和体视对原理,借助彩虹全息物像关系及Y向面积分割法,采用双缝来制作三维动态合成全息图。拍摄光学系统中双缝间距△Y设计为50mm,窄条缝宽度α为4mm。
双缝间距确定后光路中物像关系的设计应满足:
△Y'=佐Y'R-Y'L襔=65mm(1)
其中Y'L、Y'R为左右双视子全息元重现像的纵向坐标,佐|Y'R-Y'L|襔表示重现时双缝像间距。由于人眼瞳距平均尺寸为65mm,只有当(1)式满足时,人的双眼才能同时处于相应的双缝重现像位置观察到同时记录的一对物体子全息图的像,每对子全息图的像与物体的某一姿态相对应。
窄条缝窗口像的宽度α'受眼瞳孔径的制约,一般应满足:
如果(2)式中α'过小,会造成单眼同时接收到两个以上的再现像而出现像串扰;α'若过大,会减少拍摄物体序列分立的窄带区域数量,导致再现像姿态不连贯,从而影响全息图的动态艺术效果,失去动态合成全息图的真正意义。
4 可编程控制系统设计
可编程控制系统的构成如图3所示,系统中上位机(计算机)使用VC++提供的串行通信控件MSCOMM通过RS-232接口与下位机(单片机)通信。由于RS-232信号的电平和单片机AT89C52串口信号的电平不一致,这里使用集成电平转换芯片MAX232为RS-232作电平转换芯片,转换完毕的串口信号TXD(信号发送端)、RXD(信号接收端)、GND(信号地端)可直接与AT89C52相应引脚输出端连接,通过TXD、RXD和GND三端接线便可以进行通信。X、Y步进电机行程上各设有限位开关,确定X、Y步进电机的行程范围及起到复位的功能。
上位机中设置拍摄参数如下:
X步进电机初始位置——XS;
Y步进电机初始位置——YS;
X步进电机移动次数——XN;
Y步进电机移动次数——YN;
X步进电机单次移动量——XD;
X步进电机单次移动量——XD;
稳定时间——TW;
曝光时间——TB。
单片机控制程序流程图如图4所示,上位机设置参数,向下位机发送指令,下位机根据设置参数指令控制X、Y步进电机进行初始化操作,然后移动到起始位置稳定等待曝光。完成一次记录后,单片机自动控制下一个周期进行同样操作,直到拍摄完毕。自动拍摄系统实时窗口显示了设置的各个参数和即时曝光位置,以及时间显示,方便操作者即时了解拍摄进程。如图5和图6所示。
5 实验结果与讨论
实验中采用632.8nm的氦氖激光器作为H1记录光源,选用一个石膏像作为拍摄实物,如图7所示。制作系统采用图1,实物固定放置在载物旋转台中心,记录介质是天津-I型全息干板,垂直固定于H1窄缝移动架上,实物中心距离全息干板垂直距离20cm。拍摄时载物转台每次旋转8°改变一次实物姿态,相应全息干板的双缝阻挡板垂直移动4mm,稳定时间10s,曝光时间30s。完整的拍摄设定为11次曝光,在全息干板上记录11对全息图元,也就是物体的22个窄带区域的像。把记录有22个实物窄带区域像的全息干板经显影处理后获得一个H1全息干板,用它的共轭光照射便可以重现实物22个窄带区域有序姿态的像,如图8所示。由于采用了自动拍摄系统,总花时间仅为60min。制作过程操作紧凑、直观、定位精确,自动拍摄程序开启后操作人员可离开实验室。与传统方法相比显著地缩短了拍摄周期,大大提高了生产效率。
为在白光下直观地观察到实物各个姿态的像,采用二步法彩虹全息图术制作H2,以441.6nm氦镉激光器作为光源,F9600型光刻胶版作为记录介质,用共轭光重现H1的像进行一次曝光记录,经显影处理获取三维动态全息图H2。在白光下,左右缓慢转动H2或横向人眼,便可以直观地看到实物22幅三维动态全息图像,该实物的三维图像姿态连续呈现,动态效果逼真。图9是模压在PET材料上的全息产品效果图。
6 结论
本系统使用了计算机技术和单片机技术对全息图记录系统进行自动控制,整个记录过程由计算机控制相应器件进行移动和曝光,实现了三维动态合成全息图制作的全自动化流程,拍摄过程操作紧凑、定位精准,操作界面简易、直观。与传统制作方法相比,本文提出的自动控制系统制作三维动态合成全息图,能够极大地提高制作效率和精度。
参考文献
[1]于美文,张静芳.光全息术[M].北京:教育出版社,1995.
[2]朱伟利,张可如,宋媛,等.双视三维动态反射全息图合成技术研究[J].光学技术,2000,26(3):222-224.
[3]郭欢庆,王肇哲,王金城,等.数字合成全息系统中空间光调制器DMD的研究[J].光电子激光,2004,15(1):9-2.
全息图生成方法 篇7
在软件开发的过程中,开发人员总是重复编写一些简单的代码,而且每当新技术来临,又不得不一再地重复过去的工作。同时,需求的变化也从来没有停止过[1]。为了解决这些问题,人们提出了代码自动生成技术。代码自动生成技术根据模型驱动架构MDA(Model Driven Architecture)的思想,将由开发人员描述的软件系统模型转换为代码,使得模型成为软件开发的核心制品,提升了软件开发的抽象层次,从而提高软件开发效率和软件的可维护性[2]。
统一建模语言UML是一种以图形方式对系统进行分析、设计的标准建模语言,使用UML建模可以清晰地表示系统的结构和行为信息。UML模型中的类图显示了系统中各个类的静态结构,顺序图描述了对象之间消息传递的时间顺序。因此,软件开发人员通常将二者结合描述软件系统的详细设计模型。代码自动生成就以类图和顺序图为输入,依据一定的转换规则生成具有静态和动态信息的代码。
目前关于将UML模型图生成代码的研究很多,文献[3,4]提出了一种将类图和顺序图生成具有结构和行为信息的Java代码的方法,文献[5]列出了多条顺序图到Java代码的转换规则,文献[6]提出了一种将类图生成C++代码的方法,文献[7]提出了静态模型到C代码的转换规则,文献[8]提出了一种将类图生成.Net组件代码的方法,文献[9]研究了代码自动生成技术中代码信息的来源。但对如何结合类图和顺序图生成与完整应用系统相接近的C++代码的研究却比较少。
本文提出了一种将类图和顺序图相结合生成包括静态结构和动态行为信息的C++代码的方法。
1 转换方法
图1描述了由UML模型转换到C++代码的过程框架,包括UML模型、UML元模型、代码生成器以及C++代码。UML模型包括语法正确的类图和顺序图,用来描述软件系统的静态结构和业务逻辑信息,由编程人员绘制。UML元模型包括类图、顺序图的元模型,用来定义类图、顺序图的绘制规则。代码生成器的核心是代码转换规则,转换规则是根据UML模型元素的特点和C++语言的代码结构建立的。自动生成代码时,首先输入符合UML元模型规则的UML模型,然后根据元模型的转换规则生成C++代码,其中类图生成C++中的类,顺序图生成方法内部的具体实现。
1.1 类图元模型
UML的元模型定义了使用UML描述对象模型的完整语法规则[10],图2为类图的元模型。UML类图中的类与元模型中的Class对应,属性和操作与Attribute和Operation对应。操作的参数对应Parameter,其中kind表示该参数的类型,若kind=in表示该参数为调用操作时传递的参数,kind=out则表示该参数为操作的返回值。各个类之间的关联关系用Association表示,Association End记录关联端的名称和属性。属性和参数的类型用Classifier表示。
1.2 顺序图元模型
图3为顺序图的元模型。一个顺序图用来描述类中的一个方法,对应元模型中的Interaction、Collaboration和Operation。其中Operation用来记录该顺序图所描述的方法的名称和可见性。顺序图中的对象对应元模型中的Classifier Role,不同对象间通信的消息对应Message,消息中要执行的动作对应Action,该动作执行的条件用recurrence表示,动作的内容用Request表示。动作分为调用(Call Action)、创建(Create Action)、发送(Send Action)、返回(Return Action)以及销毁(Destroy Action)。调用和创建操作的返回值用Return Var表示。参数的类型记录在Classifier中。
2 转换规则
下面介绍UML类图和顺序图到C++代码的转换规则。为了清楚准确地描述转换规则,UML模型元素使用文献[11]中定义的元素,转换规则中用到的标记如表1所示。转换规则使用表格描述,其中第一列为待转换的模型元素,第二列为该模型元素对应的元模型,第三列为该元模型对应的转换规则。
2.1 类图的转换规则
依据UML模型和C++代码的特性,得出类图和C++代码的关系为:UML模型中的类、属性、操作分别对应C++中的类、成员变量、成员函数。因此,UML类图到C++代码的转换规则包括类的转换规则、属性和操作的转换规则。
规则1 类的转换规则,如表2所示。待转换的模型元素是一个有名称的类,元模型中对象c的属性name记录了该类的名称。转换的第一步是.h文件(HFILE)和.cpp文件(CFILE)的生成,如表2转换规则第一行所示。.h文件包括头文件的引用IN-CLUDE、成员变量ATTRIBUTE和成员函数OPERATIONH的声明,被规则2中的内容替换。非终结符号c.name表示本规则所描述类的类名,被第一列中的类名所替换,语句#ifndef和#define后的c.name全部大写。在C++中,通常成员变量是私有的,成员函数是公有的,分别使用终结符号描述,如转换规则第二行所示。.cpp文件包括对应头文件的引用和成员函数OPERATIONC的具体实现,如转换规则第三行所示。
规则2 属性和操作的转换规则,如表3所示。待转换的是一个包含属性和操作的类,元模型中对象o和a分别记录操作和属性的名称,p1、p2分别为操作的参数和返回值,c1,c2,c3对应属性、参数、返回值的类型。转换规则的第一行定义了AT-TRIBUTE的转换过程,表示属性的类型和名称,二者组合完成了C++中成员变量的声明。该转换规则中的符号“_”是带下划线的空格,表示直接生成代码中的空格。OP-ERATIONH的转换过程与此相同。OPERATIONC的具体实现被顺序图生成的代码所替换,用非终结符号SEQUENCE表示。具体如规则4所示。
下面通过Reader类描述类转换到.h文件的过程,如表4所示,Reader类有一个int类型的属性id和一个返回值类型是void的操作create()。根据其元模型,对应的转换规则分别包括属性、操作、和参数的转换规则。根据规则1生成的代码如表中转换过程第一行所示,ATTRIBUTE和OPERATION还需要做进一步的转换,其他部分为最终生成的代码。根据规则2生成的代码如表中第二到四行所示,属性和操作的声明分别为int id和void create(int id)。最后经过合并,得到的代码如下所示。
规则3 关联关系的转规则,如表5所示。元模型中c1,c2表示两个相互关联的类,它们之间的关联关系用a记录。转换规则中定义了在Class A中添加对Class B的引用,用符号IN-CLUDE表示。
2.2 顺序图的转换规则
依据UML模型和C++代码的特性,得出顺序图和C++代码的关系为:UML顺序图中的内容对应C++成员函数的具体实现细节,顺序图中的分支、函数调用、对象创建分别对应C++中的if语句、“.”运算符、new关键字。因此,顺序图到C++代码的转换规则包括顺序图的转换规则、条件的转换规则、变量赋值的转换规则、对象创建的转换规则、方法调用的转换规则、消息发送的转换规则。消息返回和对象销毁操作不需要生成对应的代码。
规则4 顺序图的转换规则,如表6所示。对象o表示该顺序图是方法oper()的具体实现。非终结符号SEQUENCE被LOCALDATA和MESSAGE替换,说明一个方法的实现细节中包括局部变量的定义以及各对象之间相互传递消息的过程。
规则5 条件的转换规则,如表7所示。对象a向对象b发送了一个包含条件的消息。元模型中对象m的属性recurrence记录了条件的内容,当该条件满足时,执行这个消息上的操作。C++中使用if语句表示条件,如表中第三列所示。
规则6 变量赋值的转换规则,如表8所示。将Class B的方法oper()的返回值赋给变量x,元模型中对象rv表示变量的名称,r记录了方法的名称,c表示函数的返回值类型即变量的类型。转换规则的第一行显示了变量x的定义,第二行中非终结符号ASIGNMENT表示该变量会被赋值,它可以被函数的返回值赋值,如规则8所示,也可以被常量或表达式赋值。
规则7 对象创建的转换规则,如表9所示。“<<create>>”表示该消息是一个创建对象的操作。元模型中r表示待创建的对象的名称,p和c2表示参数的名称和类型。C++中有两种创建对象的方式,分别为Class Name object(param)和ClassName*object=new Class Name(param)。为了避免用户使用完对象后忘记删除而造成内存泄露,本文采用第一种对象创建的方法。转换规则第一行定义了创建对象时需要使用的参数,第二行MESSAGE生成对象创建的代码,第三行中非终结符号PARA转换为待传递的参数(PARAMETER包含参数的类型和名称,PARA仅包含参数的名称)。
规则8 方法调用的转换规则,如表10所示。消息的内容为调用对象object B中的方法oper()。元模型中cr记录对象的名称,r表示方法的名称,p和c2表示参数的名称及类型。方法调用包括其他对象方法的调用和对象自身方法的调用。C++中使用符号“.”访问成员函数,转换规则的第二行显示了调用其他对象的方法并将结果赋值给一个变量的规则,当调用自身方法时,去掉即可。无返回值的方法的转换规则如表中第四行所示。
规则9 消息发送的转换规则,如表11所示。消息中不包含任何方法调用或者对象创建的内容,元模型中r记录了消息的内容。消息发送包括发送到其他对象的消息和发送给自身的反身消息。二者都只需直接将消息中的内容直接生成代码,如表中第三列所示。
3 实例分析
本文以图书管理系统为例,描述如何结合类图和顺序图生成包含结构和行为信息的C++代码。为了便于理解,对实例进行了简化,只给出了一个概念性的模型。该模型包括图书Book、读者Reader、借书记录Record以及系统交互界面Sys Interface四个类,如图4所示。读者可以使用该系统借书、还书、查看书籍的详细信息。
图5是Sys Interface类中方法return()对应的顺序图。还书时,系统首先提示用户输入图书编号book ID,并根据该编号创建一个Book类的对象b,调用search()方法将该书的信息从数据库读入b中。然后将该书的数量加1,调用modify()方法将更新后的结果保存至数据库中。最后创建一个图书编号为book ID,读者编号为reader ID的Record对象rc,调用该对象的方法del()在数据库中删掉该条借阅记录。
类Sys Interface生成代码的过程为:
(1)应用规则1,生成Sys Interface.h和Sys Interface.cpp文件;
(2)应用规则2,生成Sys Interface.h文件中的成员变量choice、book ID、reader ID和成员函数run()、login()、borrow()、return()、display Book()的声明,Sys Interface.cpp文件中成员函数run()、login()、borrow()、return()、display Book()的框架;
(3)应用规则3,生成Sys Interface.h文件中对Book.h、Record.h、Reader.h文件的引用;
(4)应用规则4,生成return()函数的具体实现结构,先声明变量,然后顺序显示对象间传递的消息;
(5)应用规则9,生成提示用户输入图书编号,并存储该编号到变量book ID的语句;
(6)应用规则7,生成创建Book类的对象b的语句;
(7)应用规则8,生成调用对象b的方法search()的语句;
(8)应用规则6和规则8,生成变量num的声明和赋值语句;
(9)应用规则9,生成变量num加1操作的语句;
(10)应用规则8,生成调用对象b的方法set Num()和modify()的语句;
(11)应用规则7,生成类Record的对象rc的创建语句;
(12)应用规则8,生成调用对象rc的方法del()的语句;
经过以上步骤后自动生成的代码如表12所示,由于篇幅有限,Sys Interface.cpp中没有列出run()、login()、display Book()的框架。结果显示,在search()、modify()、get Num()、set Num()、del()已定义的条件下,自动生成的return()方法清楚地描述了还书操作的执行流程,是可执行的C++代码。由此可见,可以使用细粒度的顺序图描述各个方法的动态行为信息,应用本文提出的转换规则生成与图书管理系统相接近的C++代码。与多数文献中提出的只能生成代码框架的方法相比,本文提出的方法可以生成内容更加完整的代码。
根据以上研究成果,本文实现了一个基于PSM的代码自动生成工具,该工具采用Eclipse插件开发的方式,元模型使用基于XML的元数据表示方法,转换规则使用VTL编写的模板实现,代码生成器使用JDom技术解析XML文件内容,然后使用Velocity引擎根据模板的访问请求返回相应的模型数据并与代码模板合并生成目标代码。如图6所示,其中包括Sys Interface类对应的XML文件、类图到C++代码的转换模板、自动生成的C++代码。由于时间有限,顺序图到C++代码的转换模板还未完成。Veolcity技术的使用提高了代码的生成效率与代码模板的灵活度,从而为生成可执行的代码提供了技术支持。
4 结语
本文描述了一种结合类图和顺序图生成具有结构和行为信息的C++代码的方法。先将UML模型中的各个元素映射到相应的元模型,然后根据元模型的转换规则逐步生成C++代码。与多数文献中提出的只能生成C++代码框架的方法相比,本文提出的方法可以生成内容更加完整的代码,减少了编程人员手动添加代码的工作,从而提高了软件的开发效率和软件产品的质量。由于顺序图不易于描述代码中复杂的逻辑信息,所以部分逻辑复杂的代码需要编程人员手动添加或者参考活动图的信息。此外本论文只关注了类图和顺序图中的主要模型元素,类图中的关联类、受限关联以及顺序图中的片段都还没有相应的转换规则。所以,下一步将继续完善类图和顺序图的转换规则并提出活动图的转换规则。
参考文献
[1]Anneke Kleppe,Jos Warmer,Wim Bast.解析MDA[M].鲍志云,译.北京:人民邮电出版社,2004.
[2]刘辉,麻志毅,邵维忠.元建模技术研究进展[J].软件学报,2008,19(6):1317-1327.
[3]Abilio G Parada,Eliane Siegert,Lisane B de Brisolara.Generationgjava code from UML class and sequence diagrams[C]//2011 BrazilianSymposium on Computing System Engineering(SBESC).Pelotas,Brazil,2011.
[4]Usman M,Nadeem A.Automatic generation of java code from UML di-agrams using UJECTOR[C]//International Journal of Software Engi-neering and its applications(IJSEIA),2009,3.
[5]Mathupays Thongmak,Pornsiri Muenchaisri.Design of rules for trans-forming UML sequence diagrams into java code[C]//Proceedings ofNinth Asia-Pacific Software Engineering Conference.Gold Coast,Aus-tralia,2002.
[6]Dan Regep,Fabrice Kordon.Using metascribe to prototype an UML toC++/Ada code generator[C]//11th International Workshop on Rap-id System Prototyping.Paris,France,2000.
[7]由志远.基于MDA的嵌入式软件代码生成器设计与实现[D].西安:西安电子科技大学,2010.
[8]Deuk Kyu Kum,Soo Dong Kim.A systematic method to generate.Netcomponents from MDA/PSM for pervasive service[C]//Fourth Inter-national Conference on Software Engineering Research,Managementand Applications.Washington,USA,2006.
[9]Jichen Fu,Wei Hao,Farlkh B Bastani.Model-Driven Development:Where Does the Code Come from?[C]//Fifth IEEE International Confer-ence on Semantic Computing.Palo Alto.USA,2011.
[10]OMG.UML Semantics.Version 1.1[R].The Object Management Group,Document ad/97-08-05,Framingham MA,1997.
【全息图生成方法】推荐阅读：
探测波导全息光栅傅里叶变换光谱的新方法07-18
全息信息05-11
“全息”操作09-23
全息投影技术07-03
数字化全息图像09-28
一种保持地貌特征的数字高程模型生成方法08-14
将PPT生成.EXE的可执行文件的方法06-14
原位生成07-19
过程生成05-18
生成因素05-29