（应用数学专业论文）可视化编程中focuscontext算法的改进.pdf

河南大学研究生硕士学位论文第1 页 摘要 与文字相比，图形本身所具有的直观、象形以及高度信息浓缩等特性使得可 视化程序设计为编程人员提供了一种比传统的文本程序设计更为直观的人机交互 方式。目前存在的可视化系统和正在开发的可视化程序设计工具大多将重点集中 在传统的图形布局方案来对整个程序结构进行静态可视化，由于采用了工作流编 程模式，包含大量的图形节点序列及其相应的注解是这些可视化编程工具的一个 显著特征。正是由于这一特征，在进行可视化程序设计时，由数以百计的二维图 形节点和数以千计将它们进行连接的边所组成的程序结构非常常见，而局限于单 台计算机屏幕的显示空间，这些繁杂的图形化元素往往会产生严重堵塞，无法对 其进行有效的管理和设计。所以，如何解决这一问题己成为可视化编程中新的研 究课题。采用f o c u s + c o n t e x t 算法，在保持可视化程序整体结构的同时提供对局 部细节的显示，允许程序员通过对图形节点进行重新定位和缩放来同时显示程序 的整体结构和某个具体图形对象的细节信息，即增加了可视化编程的灵活性和交 互性，同时又能够缓解由此产生的一系列问题。为了更具体的说明，本文以生物 信息可视化编程模型为参考对象，着重对此进行了探讨，主要内容包括以下几个 部分： 1 对可视化程序设计语言的基础理论进行介绍，并讨论了其在可视化编程中 的特点和应用。 2 针对目前可视化编程领域中遇到的阻碍和问题，提出并研究基于 f o c u s + c o n t e x t 算法的二维可视化程序设计语言的实验原型模型。 3 为了提高可视化编程的灵活性和交互性，详细论述和分析了对 f o c u s + c o n t e x t 算法进行适应性改进的基本思路，以及应用在具体的生物信息可 视化编程模型中所需要解决的关键值的计算、多焦点显示、合理布局等问题。 通过原型实验和算法分析表明，使用该改进算法的可视化编程模型能够解决 传统二维可视化语言设计环境中存在的上述问题。论文最后讨论了针对这一领域 未来的研究方向，包括如何对a p 合理取值、如何使显示效果更加合理和易于理 解等问题。 关键词：可视化编程：f o c u s + c o n t e x t ；s m a l l s c r e e n ；s c a l i n g u p a bs t r a c t c o m p a r e d w i t ht e x t ，t h ea t t r i b u t e so fi n t u i t i o n ，p i c t o g r a p ha n di t sh i g h e r i n f o r m a t i o ne n t r o p y , g r a p h i c sp r o v i d et h ep r o g r a md e s i g n e r sap o w e r f u lt o o lt od e s i g n f r i e n d l i e ri n t e r f a c ef o rh u m a n m a c h i n e b o t he x i s t i n ga n du n d e rd e v e l o p m e n ts y s t e m s c o n c e n t r a t eo nt h es t a t i cv i s u a l i z a t i o no fp r o g r a ms t r u c t u r e sb a s e do nc l a s s i c a lg r a p h l a y o u tm e t h o d s b e c a u s eo fa p p l y i n gw o r k f l o w sp r o g r a m m i n g m e t h o d ，t h el a r g es c a l e o fv i s u a lp r o g r a m m i n gn o d e sa n da n n o t a t i o nd a t ab e c o m eo n eo ft h ep r o m i n e n t c h a r a c t e r i s t i co ft h e s ea p p l i c a t i o n s h u n d r e d sa n dt h o u s a n d so fn o d e sa n de d g e sa r e f r e q u e n ti nl a r g es c a l e v i s u a lp r o g r a m ss ot h a tt o om a n yp i c t o r i a lp r o g r a m m i n g e l e m e n t sm a k et h es c r e e ns ob l o c k e da n df a i lt om a n a g ef l e x i b l ya n de f f e c t i v e l y t h e s e c h a l l e n g e sh a v em a d eo u rr e s e a r c hc o n c e n t r a t eo nu s i n gf o c u s + c o n t e x ta l g o r i t h mt o c a t e rt h ec u r r e n tn e e d so ft h e s es t r u c t u r e sd u et ot h e i rs i z ea n dc o m p l e x i t yr e q u i r e s m e t h o d sf o rf o c u s i n go nd e t a i l sw i t h o u tl o o s i n gt h ec o n t e x ta tt h es a l t l et i m e i ta l l o w s a p r o g r a m m e rt o s e eas p e c i f i c g r a p h i c a lo b j e c tw h i l e t h ew h o l es t r u c t u r eo f p r o g r a m m i n gi ss t i l ls h o w nt h r o u g hr e p o s i t i o n i n ga n dr e s i z i n gg r a p h i c a ln o d e ss ot h a t i t i m p r o v e st h ef l e x i b i l i t ya n di n t e r a c t i v i t yo fv i s u a lp r o g r a m m i n g t oi l l u s t r a t e o u r r e s e a r c h ，w e b a s e do u r e x p e r i m e n t a lp r o t o t y p e o nt h eb i o i n f o r m a t i c a lv i s u a l p r o g r a m m i n g m o d e l t h em a i nc o n t e n t si n c l u d e ： 1 t h eb a s i ct h e o r yo fv i s u a lp r o g r a m m i n gl a n g u a g e si si n t r o d u c e d ：t h et r a i t sa n d a p p l i c a t i o no fb i o i n f o r m a t i c sv i s u a lp r o g r a m m i n ga r e i n t r o d u c e d 2 1 1 1 eh i n d r a n c e sa n dp r o b l e m so fv i s u a lp r o g r a m m i n ga r ed i s c u s s e di nd e t a i l t h ef o c u s + c o n t e x ta l g o r i t h ma r ea n a l y z e da n dt h ee x p e r i m e n t a lp r o t o t y p ew h i c hb a s e d o nt h i sa l g o r i t h mi sp r e s e n t e da n dr e s e a r c h e d 3 a ni nd e p t ha n a l y s i so ft h ei m p r o v e df o c u s + c o n t e x ta l g o r i t h mi n2 dv i s u a l p r o g r a m m i n ge n v i r o n m e n tw a sm a d et os o l v et h ek e ym e t h o d ，m u l t i f o c u sa n dl a y o u t p r o b l e m sa n dt os h o w t h ef l e x i b i l i t ya n di n t e r a c t i v i t yo fv i s u a lp r o g r a m m i n g a c c o r d i n gt ot h ea n a l y s i so ft h ea l g o r i t h ma n dt h ee x p e r i m e n t a lp r o t o t y p e ， t h r o u g hi n t e g r a t i n gf o c u s + c o n t e x tt e c h n i q u e si n t o v i s u a lp r o g r a m m i n gm a p r o v e sa l a r g ea m o u n to ff l e x i b i l i t ya n di n t e r a c t i v i t y w h i l ep r o m i s i n gp r o b l e m sr e m a i nt ob e s o l v e d ， i n c l u d i n ga s s i g n i n gv a r i e dv a l u eo fa p io v e rt i m ea n dm a k i n gt h ed i s p l a y e f f e c tm o r ec o r n f o r t a b l ea n du n d e r s t a n d a b l e k e yw o r d s ：v i s u a lp r o g r a m m i n g ；f o c u s + c o n t e x t ；s m a l l - s c r e e n ；s c a l i n g u p 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发袁或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书雨 使用过的材料。与裁一同工作的同事对本研究所做的任何贡献均已在论文中作 本人经河南大学审核批准援子硕士学住。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用擘住论竞的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、奎阅，。，本人授权河南犬学出于宣扬、展览学校 学术发展币进行学术交流等司_ 昀可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 1 1 口 学位获得者( 学位论文作者) 签名：j 丝：聋 2 0o c 年6 月 日 学位论文指导教师釜名：淄熬臼 2 0 0 9 年g 月 目 河南大学研究生硕士学位论文第1 页 第1 章绪论 可视化技术是理解复杂现象和大规模数据的重要工具，在自然科学领域 得到了广泛应用。自2 0 世纪7 0 年代提出可视化这一概念以来，发达国家开 始竞相研究可视化的理论和方法，开发可视化的工具与环境，并将可视化的 研究成果广泛应用于虚拟仪器、生物信息、计算机仿真、机器人应用、医学 图像处理等众多科学与工程领域。随着图形、图像及计算机设备性能的日益 提高，逐渐促成了可视化在计算机科学研究领域应用条件的成熟。如今，可 视化己成为了计算机科学研究领域中的重要组成部分。 程序设计语言是一种重要且有效的设计工具，发展至今已有百十种。虽 然它们的应用领域各异且形式繁多，但它们也存在一些共通的概念和规律。 掌握这些规律性的东西，对包括非专业程序员、高级程序员和系统设计师在 内的广大编程人员来说都大有裨益。可视化程序设计语言一一v p l s ( v i s u a l p r o g r a m m i n gl a n g u a g e s ) 正是这样一种把这些共通的概念和规律进行规范性 总结，并以图形化的编程模式来表达编程思想，这样即使是一名对各类编程 语言不太熟悉的程序设计人员依然可以通过图形化的程序设计方式轻松的 表达出自己的设计思想和理念。 另一方面，虽然可视化编程工具向编程人员提供了一个良好的人机接口 使得编程过程变得简单易学，然而也正是由于大量采用了图形化模块作为主 要的编程元素，使得在进行较小规模的编程时用户能够明显感觉到可视化编 程带来的种种好处，然而在进行较大规模的可视化程序设计时，大量图形化 的编程模块和其间繁杂的连线阻碍了整个屏幕，以至于无法对其进行有效的 管理使得对整个可视化程序结构的理解造成困难。这些由可视化编程带来的 种种问题随着对可视化程序设计需求的同益增多，使得该领域的发展遇到了 所未有阻碍。 本章主要对可视化程序设计理论的发展、主要分类和应用领域进行了简 要介绍，并简要分析了可视化程序设计的研究现状和所面临的主要问题，同 时提出了解决这些问题的基本思路，最后是本文的内容组织安排的介绍。 第2 页河南大学研究生硕士学位论文 1 1 可视化程序设计语言的主要发展及应用 可视化的自然语言是对实体事物的可视化描述，而可视化编程语言是在 对现实世界抽象的基础上，对抽象后的数学模型进行可视化的处理。可视化 语言具有以下优点：( 1 ) 直观，信息的发出者和接收者可以直观地表述和接受 信息；( 2 ) 便于理解，直观、形象的图符与有形实体更为接近，能较好地反映 实体的特征，便于信息使用者的理解；( 3 ) 对行为过程的表述更为直接和形象 化( o n 工作流程图等) 。这些特点都是抽象的符号语言所不具备的。 1 1 1 可视化程序设计语言的发展 第一、二代计算机主要用于大型科学计算，服务对象为具有专业编程能 力的高级知识阶层，因此所涉及的问题领域为抽象的数学形式。这一阶段， 抽象的软件语言形式与其服务对象和问题领域相吻合，使得以高级编程语言 为代表的符号语言得以迅速发展。随着计算机的普及，其使用范围扩大到整 个相关领域，问题领域涉及到社会的各个行业，对计算机问题的求解也不只 局限于抽象的数学问题，而是越来越多地涉及到形象化的表达。这时，抽象 的高级编程语言在某种程度上制约了计算机语言的发展，并且许多复杂的问 题难以实现求解。这一切使得在程序设计中使用可视化编程技术成为必然。 然而，无论是专业的计算机编程人员还是业余编程人员，要从简单使用 计算机到直接与计算机进行深入交流，就需要掌握计算机语言。而抽象的语 素、苛刻的语法规则、晦涩的语义、复杂的算法往往使他们难以适从。鉴于 可视化语言形象、直观、便于理解的特点，对程序设计语言的可视化研究已 成为必然趋势。另外，随着计算机性能价格比的不断提高，以及计算机软 硬件技术的逐步成熟，可视化形式的一些主要缺点也可以通过相应的计算机 技术来进行弥补。如图形技术可以迅速生成规则的可视化语素，供信息发送 者使用；利用软件封装技术，将复杂信息尤其是算法信息封装在可视化语素 中，以解决抽象信息的表达问题；使用高速大容量存储器，使得信息存储问 题已不再成为制约计算机发展的主要问题。所有这些使得可视化技术应用在 计算机编程中已成为可能。 河南大学研究生硕士学位论文第3 页 1 1 2 可视化程序设计语言的主要分类 上世纪九十年代以来，包括c h a n g ，s h u 和b u r n e t t 在内的该领域的一些 著名的专家学者根据各种v p l s 的主要特征对它们进行了五种分类，以便在 不同的可视化系统之间进行比较和评估提供参考标准。 1 完全( 纯) 可视化语言 在整个编程过程中都要依赖于可视化技术。程序员操控图标或其他图形 表达式来创建程序并在同样的可视化环境中进行调试和执行。程序直接对其 可视化表达式来进行编译，不需要将其翻译成基于文本的过渡语言。这种完 全可视化代表系统包括v i p r ，p r o g r a p h 以及p i c t 。 2 混合文本的可视化系统 可视化程序设计语言的一个子集( 或分支) 就是将图形元素与文本相混 合的编程系统。在这种系统中程序体通过可视化的方式来建立，然后将其翻 译成高级的文本编程语言。例如e r w i g 等开发的r e h e a r s a lw o r l d 。 3 实例编程系统 除了以上两个主要的分类以外，也有不少v p l s 可以被归于较小的类别。 比如，与其它一些v p l s 和p y g m a l i o n 的开发思路类似，它们允许用户创建 和操控图形对象来让系统学习如何完成一项特别的任务或实现某一个功能。 4 面向约束系统 一些v p l s 向用户提供一种虚拟环境，在该环境中编程人员通过其中的 图形对象构建一个物理对象的模型，该模型受用户所定义的条件来约束，用 来模拟类似于重力这样的自然法则。像s u t h e r l a n d 开发的s k e t c h p a d 系统以 及t h i n g l a b 和a r k 系统都是主要的面向约束系统。 5 基于表格系统 还有一些v p l s 借鉴了电子制表系统( s p r e a d s h e e t s ) 的一些视觉模式和 编程理念，它们通过改变按照时间变化的一组相互连接的各个表格子条目的 不同状态来进行编程。f o r m s 3 就是这样的可视化编程系统。 需要说明的是，对v p l s 的这五种分类并非是完全独立、互不相关的。 事实上，许多可视化程序设计语言都可以归入多种类别。这五类中的前两个 是v p l s 的两个重要分支，本文的研究重点也主要集中于第一种，即完全( 纯) 可视化语言。 第4 页河南大学研究生硕士学位论文 1 1 3 可视化程序设计的应用 随着计算机技术以及生物学的飞速发展，产生了一门新兴的学科一一生 物信息学。这门学科在生物化学、生物医学等领域有着十分广泛的应用。而 作为计算机程序设计发展的重要阶段，可视化程序设计被认为是进行生物数 据分析的有力工具。与其相对应的生物信息可视化技术自被提出以来就引起 了国内外众多科研人员的关注，将可视化编程技术应用到生物信息领域已经 成为新的研究热点，是当前生物信息学领域中的重要研究方向之一，而本文 也正是以生物信息可视化编程模型为基础进行原型设计的。 生物信息可视化编程为分子生物学家提供了一条寻找和研究新基因的 新思路，即从高度自动化的实验出发，经过数据的获取与处理、序列片段的 拼接、可能基因的寻找、基因功能的预测一直到基因分子进化研究。该过程 的每一个环节，都是生物信息学研究的重要内容。因此，高度自动化实验数 据的获得、加工和整理，以及如何将实验室中得到的生物学信息转化为计算 机能够处理的数字信息，是生物信息学的一个重要研究课题。这种转化大量 地体现在各种自动化分子生物学仪器应用上，如模拟d n a 测序仪，p c r 仪 等，这类仪器将实验所得的物理化学信号转化为数字信息，并对其作简单分 析，然后将分析结果用于实验条件的控制，以完成高度自动化的实验过程。 通过使用生物信息可视化编程技术，可以使得从事大规模e s t 测序和d n a 物理图谱构建的实验通过高度可视化的程序设计系统来模拟其大部分的实 验工作，由此可以大大减少生物数据分析的成本。这不仅具有重大的科学意 义，而且具有巨大的经济效益。生物信息可视化的这些特点在现有的相关领 域中几乎是前所未有的，其广阔的应用领域必定会带动一些相关学科和产业 的发展，具有深远的现实意义和重要的战略影响。 1 2 可视化程序设计语言的研究现状 可视化程序设计语言领域的发展实际上是计算机图形学、程序设计语 言、以及人机接口这三个主要方面的结合【2 4 1 。因此，相对与其他领域来说， 把对可视化的研究视为一种开拓性的工作并不夸张。下面对可视化程序设计 语言的发展和应用进行简要介绍。 河南大学研究生硕士学位论文第5 页 对于可视化程序设计语言研究的基础性突破是i v a ns u t h e r l a n d 开发的画 板系统【5 】，该系统可以作为这一领域的最早应用先例。画板系统( s k e t c h p a d ) 于1 9 6 3 年在麻省理工学院的t x - 2 计算机上设计实现，被称为首个计算机图 形应用程序。该系统允许用户在一个统一的可视化环境中对数据流图进行创 建、调试和执行【6 】。其图形接口和对用户自定义图形约束的支持成为后来出 现的一些v p l s 对可视化图形约束条件的说明的必要条件之一。v p l s 发展 过程中的另一个重要的里程碑来自于19 7 5 年d a v i dc a n f i e l ds m i t h 设计的 p y g m a l i o n 程序开发环境【7 】。p y g m a l i o n 的重要贡献在于它引入实例化编程的 概念。用户“告诉 系统具体需要完成什么任务，系统通过接收到的信息产 生一个能够完成一般功能的程序模型，然后由用户再进行补充完善。 大概经历了十年时间，在1 9 8 6 年，由r s m i t h 设计完成的a r k 系统能 够提供给用户一个二维( 2 d ) 动画编程环境来实现一种交互式的模拟效果， 用户可以拖动屏幕中的手形图标对其中的物体进行操作以表现像重力之类 的物理法则【8 】。1 9 9 4 年，c i t r i n 等人在科罗拉多大学又开发出了v i p r 系统， 该系统是一种完全可视化的通用编程系统。该系统不再使用图标、表格等传 统的图形表达式，而是采用相互嵌套的同心圆圈来对编程进行可视化【9 】。商 业上的应用被认为比较成功是c o x & p i e t r y z k o w s k y 开发的p r o g r a p h 系统， 对于该系统的最初研究起源于1 9 8 2 年，后经多个版本的发布最终由p i c t o r i u s 公司开发上市【l 引。p r o g r a p h 把类和对象的概念引入可视化编程之中，并提供 给用户一个强大的可视化数据流声明机制。后来出现的f o r m s 3 系统也是一 个通用的面向对象的可视化编程语言，f o r m s 3 更加强调了对数据的抽象【1 1 1 。 n i 公司开发的l a b v i e w 系统以及微软开发的m s v p l 系统都是目前比较成 功的可视化编程系统，它们的出现逐步奠定了目前可视化程序设计语言的发 展方向和趋势。 可视化程序设计语言的众多优势和生物信息可视化的发展需要使得两 者的结合成为必然。目前已经存在一些可视化编程在生物信息方面的应用， 比如k d eb i o s c i e n c e ，v i p e r ，b i o b i k e ，b i o p i p e d 等，所有这些工具都提供 一种将生物信息程序集成到工作流中的机制【1 2 叫4 1 。这些工具在研究大量生 物数据方面以及观察原始形态复杂的生物数据方面都特别有用。 第6 页河南大学研究生硕士学位论文 本文挑选了一些具有代表意义的生物信息可视化工具介绍如下：k d e b i o s c i e n c e ，它基于知识发现领域的生物信息工作流平台，其基本原理是通 过一系列由连接结点构成的工作流( 或管道) 来表达一个生物学分析过程( 任 务) 【l5 1 。该原理包涵两个关键部分：( 1 ) 一个能够通过专有语法表达的数据 的数据模型：( 2 ) 能够表达各自算法的节点【l6 1 。v i p e r 是一种基于p y t h o n 和 t k i n t e r 的可视化编程环境【1 7 】。该环境能够使那些非专业的编程人员构建用 于计算和可视化的交互网络。节点之间的连接定义了一个定向图形用来传播 数据和对有新的输入数据的节点触发执行。v i p e r 与高级可视化模拟公司的 a v s 系统和i b m 公司的o p e n d x 系统类似【l 引。b i o b i k e 是一种基于w e b 的 生物计算环境，其b b l 语言能够使得生物学家来设计新颖的基因算法。通 过一个动态直接操控接口，即使之前没有编程经验的用户仍然能够较为容易 的创建b b l 代码【l9 1 。该方法的优点在于使用与海洋生物细菌发光体的案例 研究【2 们。b i o c h e