维普资讯 http://www.cqvip.com 第２７卷第７期 计算机应用 Ｖｏ１．２７ Ｎｏ．７ ２００７年７月 Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ Ｊｕｌｙ ２００７ 文章编号：１００１—９０８１（２００７）０７—１６４４—０３ 基于等高线建立的ＴＩＮ中平坦区域的修正算法 陈学工，黄晶晶 （中南大学信息科学与工程学院，长沙４１００８３） （ｃｎ１２３３＠２６３．ｎｅｔ） 摘要：在基于等高线建立的数字高程模型ＴＩＮ中，由平坦三角形连接成的平坦区域不能真实地 反映地表的真实形状，需要进行适当地修正。在不需要地形特征线的情况下，基于内部平坦三角 形，提出平坦区域的修正算法。该算法能保证修正了平坦区域后的ＴＩＮ最大限度地虚拟现实地表的 真实形状，并且能提高平坦区域的修正速度，算法的时间复杂度为０（ｎ）。 关键词：等高线；ＴＩＮ；平坦区域；平坦三角形 中图分类号：ＴＰ３９１．４１ 文献标志码：Ａ Ｃｏｒｒｅｃｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｏｆ ｉｆａｔ ａｒｅａｓ ｏｃｃｕｒｒｉｎｇ ｉｎ ＴＩＮ ｃｏｎｓｔｒｕｃｔｅｄ ｆｒｏｍ ｃｏｎｔｏｕｒｓ ＣＨＥＮ Ｘｕｅ—ｇｏｎｇ，ＨＵＡＮＧ Ｊｉｎｇ－ｊｉｎｇ ｆ Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｗｅ￣ｉｔｙ，Ｃｈａｎｇｓｈａ Ｈｕｎａｎ ４１００８３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ １１Ｎ ｏｆ ｄｉ ｔａｌ ｅｌｅｖａｔｉｏｎ ｍｏｄｅｌ ｃｏｎｓｔｒｕｃｔｅｄ ｆｒｏｍ ｃｏｎｔｏｕｒｓ，ｆｉａｔ ａｒｅａｓ ｗｈｉｃｈ ａＹｅ ｍａｄｅ ｕｐ ｏｆ ｆｉａｔ ｔｒｉａｎｇｌｅｓ Ｃａｌｌ ｎｏｔ ｒｅｆｌｅｃｔ ｔｈｅ ｒｅａｌ ｓｈａｐｅ ｏｆ ｔｈｅ ｓｕｒｆａｃｅ，ｓｏ ｔｈａｔ ｔｈｅｙ ｎｅｅｄ ｂｅ ｃｏｒｒｅｃｔｅｄ ｐｒｏｐｅｒｌｙ．Ａ ｃｏｒｒｅｃｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｏｆ ｆｌａｔ ａｒｅａｓ ｗａｓ ｐｒｅｓｅｎｔｅｄ ｂｙ ｔｈｅ ｍｅｔｈｏｄ、Ｔｈｅ １１Ｎ ｗｈｉｃｈ ｆｌａｔ ａｒｅａｓ ｗｅｒｅ ｃｏｒｒｅｃｔｅｄ ｃｏｕｌｄ ｓｉｍｕｌａｔｅ ｔｈｅ ｒｅａｌ ｓｈａｐｅ ｏｆ ｔｈｅ ｓｕｌｆａｃｅ ｔｏ ｔｈｅ ｆｕｌｌｅｓｔ ｅｘｔｅｎｔ ａｎｄ ｃｏｕｌｄ ｉｍｐｒｏｖｅ ｔｈｅ ｓｐｅｅｄ ｏｆ ｃｏｒｒｃｅｔｉｎｇ ｆｉａｔ ａｒｅａｓ，ｉｎ ｗｈｉｃｈ ｔｈｅ ｉｎｎｅｒ ｉｆａｔ ｔｉｒａｎｇｌｅｓ ａｙｅ ｄｉｖｉｄｅｄ ｏｆ ｈａｖｉｎｇ ｎｏ ｕｓｅ ｏｆ ｔｅｒｒａｉｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｌｉｎｅｓ．Ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｌａｇｏｒｉｔｈｍ ｉｓ Ｏ（ｎ）． Ｋｅｙ ｗｏｒｄｓ：ｃｏｎｔｏｕｒ；ＴＩＮ；ｆｉａｔ ａｒｅａｓ；ｆｉａｔ ｔｉｒａｎｇｌｅ 基于等高线的三维地形的重建和可视化，最基本的问题 定义７是内部三角形，但不是平坦三角形的三角形称 都是对地形图中的等高线信息进行数字化，数字化的等高线 为内部非平坦三角形。 通过一定的处理，然后建立ＴＩＮ模型，再通过三维可视化工具 进行虚拟现实显示。基于等高线建立的ＴＩＮ具有一定的几何 ２平坦区域修正算法 精度，而且包含有丰富的地貌特征，所以成为虚拟现实系统常 综合分析相关文献，基于等高线建立的ＴＩＮ中的平坦区 用的数字模型。但在基于等高线建立的ＴＩＮ中，由于等高线 域修正算法现在基本上分为特征线插入修正法” 和平坦区 源数据缺少应有的特征线数据，通常会在相邻的等高线间或 域搜索修正法 两类。 一个封闭的等高线内出现大量的平坦三角形（三个顶点具有 特征线插入修正法可以处理各种原因形成的平坦区域， 相同高程值的三角形），平坦三角形连接在一起形成平坦区 而且修改后的平坦区域比较符合地形特征。但此类算法需要 域。平坦区域不能反映地表的真实形状，所以需要进行适当 先从等高线图提取等高线的邻接关系 ，再提取特征线，最 的修正。本文提出了一个新的平坦区域修正算法，该算法适 好将特征线插入ＴＩＮ中修正平坦区域。特征线的提取是一个 用于优化虚拟现实系统的地形建模结果。 比较复杂的问题，而且此类算法需要插入比较多的点，三角网 １ 基本概念 重构的工作量比较大。如图１（ａ）所示，图中的虚线就是依据 文献［１］的方法提取的特征线。 在平坦区域的修正过程中，会遇到ＴＩＮ中一些具有特殊 平坦区域搜索修正法只考虑了两条等高线间存在平坦区 性质的边和三角形。为了下面叙述方便和清楚，特引入以下 域的情况。而且如果在三角网中存在内部平坦三角形，建立 一些定义： 平坦区域链表时，搜索到内部平坦三角形后有两条路径都可 定义１非约束边称为内部边，这里的约束条件包括等 继续下一个平坦三角形的搜索（路径二义性问题），影响了修 高线约束和边界约束。 正的速度。由于此类算法根本没有考虑地形特征，如果等高 定义２两端点的高程值相等的边称为水平边。 线间关系复杂，则修正结果远差于特征线插入修正法。 定义３既是内部边又是水平边的边称为内部水平边。 图１（ｂ）和图１（ｅ）分别是使用上述两类算法修正图１（ａ） 定义４三条边都是内部边的三角形称为内部三角形。 中带有内部平坦三角形的平坦区域（多边形 定义５三个端点的高程值都相等的三角形称为平坦三 ＡＢＣＧＪＫＬＭＮＯＰ）的结果。如图１（ｂ）所示，特征线插入修正 角形。 法的修正结果中形成了较多的新三角形。如图１（ｅ）所示，平 定义６既是内部三角形又是平坦三角形的三角形称为 坦区域搜索修正法的修正结果中形成了过于狭长的三角形， 内部平坦三角形。 而且修正的结果没有考虑任何地形特征。 收稿日期：２００７～Ｏ１—１８。 基金项目：国家８６３计划项目（２００２ＡＡ１３５１６０）。 作者简介：陈学工（１９６５一），男，湖南长沙人，副教授，博士，主要研究方向：地质构造、地理信息系统；黄晶晶（１９８２一），女，湖南长沙人， 硕士研究生，主要研究方向：地理信息系统的数字高程模型。 维普资讯 http://www.cqvip.com 第７期 陈学工等：基于等高线建立的ＴＩＮ中平坦区域的修正算法 １６４５ 实际应用中，由于等高线数据量较大和等高线间关系比 ｝Ｐｏｉｎｔ； 较复杂，特征线插入算法效率低，而平坦区域搜索法修正结果 ２）有向边表。该表保存三角形的边与该边相邻的三角 不理想且不能修正一条等高线内的平坦区域。由于内部平坦 形信息。表中每个元素的结构为： 三角形的重心与测量或计算得到的地形特征线的分叉点基本 ｔｙｐｅｄｅｆ ｓｔｒｅｅｔＩ 重合 Ｊ，如果将内部平坦三角形的重心作为地形特征点插入 ｉｎｔ ＴｒｉＮｏ［２１； ／／两相邻三角形编号 三角网，平坦区域从分叉处被，可以使得修正后的三角形 Ｐｏｉｎｔ ｓ，ｅ； ／／有向边的起始和终止顶点 ｉｎｔ ｃｏｎＥｄｇｅＦｌａｇ； 优于平坦区域搜索修正法，并使得修正效果更接近特征线插 ∥内部边的标志位，１表示不是内部边，０表示是内部边 入修正法。而且插入重心内部平坦三角形将其变为内部 ）Ｅｄｇｅ； 非平坦三角形，可以消除路径二义性问题，并且修正过程中不 ３）三角形表。该表保存生成的各个三角形的信息。表 需要搜索平坦区域。内部平坦三角形的重心的Ｘ，Ｙ坐标可以 中每个元素的结构为： 由重心公式得到，而重心的ｚ坐标可以根据应用的需要设置， ｔｙｐ￣ｅｆ ｓｔｅｒｅｔＩ 只要不同于与其相关等高线的高程值即可。 ｌｏｎｇ ｅＮｏ【３】； ／／三条边号，按边号存储 Ｐｏｉｎｔ Ｐ【３】； ／／三个点，逆时针存储 ｉｎｔｔｒｉＦｌａｇ； Ｐ Ｐ ／／三角形形态的标志位，１表示是平坦三角形出的三角形 ｝Ｔｒｉａｎｇｌｅ； 本文处理的ＴＩＮ是基于等高线建立的。基于等高线建立 ＴＩＮ的一般方法是先将等高线离散化为离散点集建立初始三 角网，再将等高线作为约束条件嵌入＂Ｊ。在进行等高线嵌入 处理的时候，有向边的内部边标志位可以确定下来，修正过程 中加入的边不能和非内部边相交。 Ｅ Ｅ 第一步处理相邻等高线间平坦区域，算法的具体描述如 （ａ）平坦区域未修正 Ｃｏ）特征线插入算法修正结果 下： １）初始化三角形链表Ｔｒｉ，初始化整型变量ｉ＝１，初始化 Ｐ 三角形变量Ｔ、Ｔ ，初始化整型变量Ｔｒｉｎｕｍ存储三角形的个 数，初始化有向边变量ｅ。 ２）如果ｉ＞Ｔｒｉｎｕｍ，转９）；否则将Ｔｒｉ中的ｉ个三角形赋 值给Ｔ。 ３）如果Ｔ不是含有水平边的内部非平坦三角形，ｉ＝ｉ＋ １，转２）。 ４）将Ｔ的水平边赋值给ｅ。如果ｅ是非内部边，ｉ＝ｉ＋１， Ｅ Ｅ 转２）。将与Ｔ共ｅ的相邻三角形赋值给Ｔ 。如果Ｔ和Ｔ 是 （ｃ）平坦区域搜索算法修正结果 （ｄ）本文算法修正结果 平坦三角形出的三角形，转６）。如果Ｔ 不是平坦三角 图１ 相邻等高线间平坦区域的修正结果比较 形，贝ｌｊｉ＝ｉ＋１，转２）。如果Ｔ 是内部平坦三角形，转５）。如 根据以上论述为依据，本文算法的基本思想是：先利用内 果Ｔ和Ｔ 组成的四边形是凸四边形，转７）。如果Ｔ和Ｔ 组成 部非平坦三角形和平坦三角形的相邻关系，插入三角形重心 的四边形是非凸四边形，转８）。 内部平坦三角形或交换内部非平坦三角形与平坦三角形 ５）在Ｔ 的内部插入其重心Ｐ（Ｐ点的高程可以根据Ｔ和 组成的凸四边形的对角线（非凸四边形则在其对角线上插入 Ｔ 形成四边形的四个顶点的高程值线性插值得到），将Ｔ 分 点四边形），逐个消除平坦三角形以此修正相邻等高线 成３个三角形，将它们的三角形标志位置１。将含ｅ的新三角 间的平坦区域；再搜索剩余平坦三角形（此时只存在一条等 形替代原来的Ｔ 放入Ｔｒｉ，并将其他两个新三角形插入Ｔｒｉ的 高线内的平坦三角线），插入三角形重心内部平坦三角 尾部，Ｔｒｉｎｕｍ增加２，修改三角网拓扑结构，将含ｅ的新三角 形或插入内部水平边中点其相邻三角形，逐个消除平坦 形赋值给Ｔ 。 三角形以此修正一条等高线内的平坦区域。如图１（ｄ）所示， ６）将Ｔ和 的三角形标志位置０。如果Ｔ和Ｔ 组成的四 本文算法只在内部平坦三角形ＡＢＪＮ中插入了其重心Ｑ，即 边形是凸四边形，交换四边形的对角线，两个新三角形替代原 能使修正结果优于平坦区域搜索算法，并接近特征线插入算 来的Ｔ和Ｔ 放入 。如果Ｔ和Ｔ 组成的四边形是非凸四边 法，而且对原三角网的重构工作量较少。 形，ｅ上插入中点Ｐ（Ｐ点的高程可以根据非凸四边形顶点的高 ３数据结构和算法描述 程值线性插值得到），将四边形分为四个三角形，将其中两个替 代三角形Ｔ和Ｔ 放入 ，将另外两个三角形插入 的尾部， 算法的执行效率与数据结构之间存在密切的关系。一个 Ｔｒｉｎｕｍ增加２。修改三角网拓扑结构，ｉ＝ｉ＋１，转２）。 良好的数据结构有利于对数据进行高效的管理，从而提高算 ７）将Ｔ和Ｔ 的三角形标志位置０，交换Ｔ和Ｔ 组成的四 法的执行效率。本文提出的算法用到以下数据结构： 边形对角线，两个新三角形替代Ｔ和Ｔ 放入 ，修改三角网 １）有序点表。该表保存散乱点集和预处理后的点序列。 拓扑结构。如果新三角形中存在某个三角形含有内部水平 表中每个元素的结构为： 边，将这个三角形赋值给Ｔ，转４）；否则ｉ＝ｉ＋１，转２）。 ｔｙｐｅｄｅｆ ｓｔｅｒｅｔＩ ８）将Ｔ和Ｔ 的三角形标志位置０，在ｅ上插入其中点Ｐ ｄｏｕｂｌｅ Ｘ，Ｙ，ｚ； ／／点的坐标 （Ｐ点的高程可以根据Ｔ的三个顶点的高程值线性插值得 维普资讯 http://www.cqvip.com １６４６ 计算机应用 ２００７血 到），将四边形分为四个三角形，将其中两个替代Ｔ和Ｔ 放入 Ｔｒｉ，另外两个插入 的尾部。Ｔｒｉｎｕｍ增加２，修改三角网拓 扑结构。如果新三角形中存在某个三角形含有内部水平边， 将这个三角形赋值给Ｔ，转４）；否则ｉ＝ｉ＋１，转２）。 形顶点高程相差０到１个等高距之间的任意值，具体可根据 需求设定），用该点将Ｔ为３个三角形Ｔ１、，Ｉ２和ｒＩ３，将Ｔ１ 替代Ｔ，，Ｉ２和ｒＩ３加入％的尾部，Ｔｒｉｎｕｍ增加２，修改三角网 拓扑结构。如果Ｔｉ（ｉ＝１，２，３）有水平边，将水平边的编号加 入ＦｌａｔＥｄｇｅＮｏ，保证其中无重复的边。ｉ＝ｉ＋１，转２）。 无重复的边，ｉ＝ｉ＋１，转２）。 ９）结束。 相邻等高线间平坦区域的修正过程如图２所示。依据算 法的描述，搜索到含水平边ＡＣ的内部非平坦ＺｋＡＢＣ，与其相 邻的／￣ＡＣＧ是平坦三角形，由于△ＡＢＣ和△ＡＣＧ组成非凸四 边形，所以在ＡＣ上插入其中点Ｐ 这个非凸四边形； ＡＡＣＧ出的ＡＰ。ＣＧ为另一个含水平边ＣＧ的内部非平 中点Ｐ（Ｐ点的高程可以设置为与Ｈ相差０到一个等高距之 间的任意值，具体可根据需求设定），将相邻三角形成四 帮 蘑 Ｆ Ｇ 蘑 ５）三角形Ｔ的内部边的编号加入ＦｌａｔＥｄｇｅＮｏ，保证其中 ６）依次对ＦｌａｔＥｄｇｅＮｏ中的边进行以下处理：在边的插入 坦三角形，与其相邻的△ＣＥＧ为内部平坦三角形，所以在 △ＣＥＧ内部插入其重心Ｐ２，成三个内部非平坦三角形， 交换ＺｋＰ，ＣＧ和△Ｐ２Ｇｃ的对角线（这个处理使得修正后的结 果与特征线插入法相似）。继续搜索到含水平边的内部非平 坦三角形△Ｐ２ＥＧ和ＡＰ ＣＥ，因为与其相邻平坦三角形构成 凸四边形，交换它们的对角线即可。 线 珥等高线 Ｆ Ｇ ＋－等高线 （ａ）相邻等高线间的平坦区域 Ｈ等高线 Ｆ Ｇ （ｃ）ＡＣＥＧ的第一步修正 ＋－等高线 ＋－等高线 （ｄ）ＡＣＥＧ的第二步修正 线 Ｆ Ｇ ＋ 等高线 等高线 （ｅ）ＡＥＦＧ的修正 （ｆ）Ａ ＣＤＥ的修正 图２相邻等高线间平坦区域的修正 第二步修正一条等高线内的平坦区域，算法具体描述如 下： １）初始化三角形链表Ｔｒｉ，初始化整型变量ｉ＝１，初始化 整型变量Ｔｒｉｎｕｍ存储三角形的个数，初始化三角形变量Ｔ、 Ｔ１、他和ｒＩ３，初始化空间点变量Ｐ，初始化整型数组 ＦｌａｔＥｄｇｅＮｏ记录需要插入点的内部边的编号。 ２）如果ｉ＞Ｔｒｉｎｕｍ，转６）；否则从 中取第ｉ个三角形 Ｔ。 。 ３）如果Ｔ不是平坦三角形，ｉ＝ｉ＋１，转２）。如果Ｔ不是 内部平坦三角形，转５）。 ４）在Ｔ内插入其重心Ｐ（Ｐ点的高程可以设置为与三角 个三角形，Ｔｒｉｎｕｍ增加２，修改三角网拓扑结构。 ７）结束。 一条等高线内的平坦区域修正过程如图３所示。在第二 次遍历三角网时，遇到内部平坦三角形△ＢＥＧ，插入其重心， 成三个非平坦三角形。搜索出所有内部水平边ＣＥ，ＢＥ， ＥＧ，ＢＧ后，再处理与每一条内部水平边相邻的三角形。 （ａ）一条等高线内的平坦区域 Ｃｏ）ＡＢＥＧ的修正 等高线 一 Ｆ 等高线 Ｆ （ｅ）ＥＧ上插入点 ．Ｌ插入点 图３一条等高线内平坦区域的修正 ４ 实例与结论 一（Ｄ ＢＧ．图４和图５分别是该程序根据实际工程项目等高线数据 构筑的数字高程模型实例局部的平面投影图（平坦区域未作 修正），及对该数字高程模型中平坦区域修正后的平面投影 图。实验结果证明本文算法能有效地修正相邻等高线间的平 坦区域和一条等高线内平坦区域。 与现存算法比较，本文提出的算法具有以下特点： １）能处理各种原因造成的平坦区域，补充了平坦区域搜 索法没有完成的部分； ２）在不用提取地形特征线的情况下，修正后的三角网能 较好地体现地形特征； ３）提高了平坦区域的修正速度，时间复杂度为Ｏ（ｎ）。 在处理相邻等高线间平坦区域时基本操作是边交换、边 上插入点和三角形内部插入点，每进行一次基本操作都会减 少ＴＩＮ中的一个平坦三角形，平坦三角形的个数不可能达到 ｎ（ｎ表示ＴＩＮ中三角形个数），所以这部分算法的时间复杂度 为Ｏ（ｎ）。在处理一条等高线内平坦区域时，算法的基本操作 是在平坦三角形的内部边上插入点，需要处理的内部边条数 不会超过３ｎ，所以这部分的算法时间复杂度为Ｏ（ｎ）。因此整 （下转第１６５３页） 维普资讯 http://www.cqvip.com 第７期 韩合民等：基于边缘颜色分布的图像检索方法 １６５３ 检索准确率为５７．１％。由于边缘颜色分布综合考虑了图像 的局部颜色和边缘分布特征，所以本文的方法返回了颜色空 间分布更为相似的图像，并且对图像中背景的变化有一定的 鲁棒性，检索结果明显优于基于传统颜色直方图的方法。 为进一步验证本文算法的检索性能，采用检索的准确率 （Ｐｒｅｃｉｓｉｏｎ）和查全率（Ｒｅｃａｌ１） 驯作为评价标准，与文献［４］算 容信息，克服了传统颜色直方图忽略空间信息的缺陷，同时对 图像的背景变化具有一定的鲁棒性。实验结果表明，本文方 法与其他同类方法相比具有更好的检索性能。 参考文献： 【１】ＳＷＡＩＮ Ｍ Ｊ，ＢＡＬＬＡＲＤＤＨ．Ｃｏｌｏｒｉｎｄｅｘｉｎｇ【Ｊ】．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，１９９１，７（１）：１ １—３２． 【２】 ＧＯＮＧ Ｙ，ＣＨＵＡＮ Ｃ Ｈ，ＸＩＡＯＹＩ Ｇ．Ｉｍａｇｅ Ｉｎｄｅｘｉｎｇ ａｎｄ Ｒｅｔｒｉｅｖａｌ Ｕｓｉｎｇ Ｃｏｌｏｒ Ｈｉｓｔｏｇｒａｍｓ【Ｊ】．Ｍｕｌｉｔｍｅｄｉａ Ｔｏｏｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， 法及基于传统颜色直方图的检索算法进行比较。其中，查全 率（Ｒｅｃａｌ１）定义为检索到的相关图像与图像库中所有相关图 像的比值。 实验中，在测试库中对每一类图像随机抽取１０幅作为查 １９９６，２（２）：１３３—１５６． 【３】 ＳＴＲＩＣＫＥＲ Ｍ，ＤＩＭＡＩ Ａ．Ｃｏｌｏｒ ｉｎｄｅｘｉｎｇ ｗｉｔｈ ｗｅａｋ ｓｐａｔｉａｌ ｃｏｎｓｔｒａｉｎｔｓ【Ｃ】／／Ｓｔｏｒａｇｅ ａｎｄ Ｒｅｔｒｉｅｖａｌ ｆｏｒ Ｉｍａｇｅ ａｎｄ Ｖｉｄｅｏ Ｄａｔａ— ｂａｓｅ８ ＩＶ，Ｓａｎ Ｊｏｓｅ，ＣＡ：ＳＰＩＥ ２６７０，１９９６：２９—４０． 询图像，记录每一幅查询图像的检索准确率和查全率，最后取 平均值，得到准确率－查全率曲线，如图５所示。实验结果显 示，本文提出的基于ＥＣＤ的检索算法在检索性能上明显优于 基于传统颜色直方图及文献［４］中基于颜色布局的检索算法。 ［４】 ＫＡＳＵＴＡＮＩ Ｅ，ＹＡＭＡＤＡ Ａ．Ｔｈｅ ＭＰＥＧ－７ ｃｏｌｏｒ ｌａｙｏｕｔ ｄｅｓｃｒｉｐｔｏｒ： ａ ｃｏｍｐａｃｔ ｉｍａｇｅ ｆｅａｔｕｒｅ ｄｅｓｃｒｉｐｔｉｏｎ ｆｏｒ ｈｉｇｈ－－ｓｐｅｅｄ ｉｍａｇｅ／ｖｉｄｅｏ ｓａｇ－－ ｍｅｎｔ ｒｅｔｒｉｅｖａｌ【Ｃ】／／Ｐｒｏｃｃｅｄｉｎｇｓ ｏｆ ＩＣＩＰ．Ｇｒｅｅｃｅ：【Ｓ．ｎ．】，２００１： ６７４—６７７． 【５】 孟繁杰，郭宝龙．一种基于兴趣点颜色及空间分布的图像检索 方法【Ｊ】．西安电子科技大学学报（自然科学版），２００５，３２（２）： ２５６—２５９． 【６】 ＧＥＶＥＲＳ Ｔ，ＳＭＥＵＬＤＥＲＳ Ａ Ｗ Ｍ．ＰｉｅＴｏＳｎｋ：Ｃｏｍｂｉｅｒｌ！ｎｇ ｃｏｌｏｒ ｎｄ ｓｈａｐｅ ｉａｎｖａｒｉｎｔｆａｅａｍｒｅｓｆｏｒｉｍａｇｅ ｒｅｔｒｉｅｖａｌ【Ｊ】．ＩＥＥＥ Ｔｒａｎｓａｃ— ｔｉｏｎｓ ｏｎＩｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，２０００，９（１）：１０２—１１９． 【７】 曹莉华，柳伟，李国辉．基于多种主色调的图像检索算法研究与 实现【Ｊ】．计算机研究与发展，１９９９，３６（１）：９６—１００． 【８】 ＭＰＥＧ．ＩＳＯ／ＩＥＣＪＴＣ１／ＳＣ２９／ＷＧ１ １／Ｎ５５２５，ＭＰＥＧ一７Ｏｖｅｒｖｉｅｗ （ｖｅｒｓｉｏｎ ９）：ｒｅｑｕｉｒｅｍｅｎｔｓ ｄｏｃｕｍｅｎｔ【Ｓ】．Ｐａｔｔａｙａ，２００３． ４ 【９】 ＷＡＮＧ Ｊ Ｚ，ＬＩ Ｊ，ＷＩＥＤＥＲＨＯＬＤ Ｇ．ＳＩＭＬＰＬＩｅｉｔｙ：Ｓｅｍａｎｔｉｃｓ ｓｅｎ— ｓｉｔｉｖｅ ｉｎｔｅｇｒａｔｅｄ ｍａｔｃｈｉｎｇ ｆｏｒ ｐｉｃｔｕｒｅ ｌｉｂｒａｒｉｅｓ【Ｊ】．ＩＥＥＥ Ｔｒａｎｓａｃ— 本文提出了一种基于边缘颜色分布的图像检索方法。该 方法利用五种不同类型边缘附近的颜色分布来表达图像的内 容信息，使用２Ｄ颜色直方图对所提取的ＥＣＤ特征进行描述。 由于综合考虑了局部颜色特征和边缘方向的空间分布特征， ２Ｄ边缘颜色直方图与颜色直方图相比包含了更多的图像内 （上接第１６４６页） ｔｉｏｎｓ ｏｎ Ｐａｔｔｅｍ ＡｎＭｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００１，２３（９）： ９４７—９６３． 【１０】ＳＭＥＵＬＤＥＲＳ Ａ Ｗ Ｍ，ＷＯＲＲＩＮＧ Ｍ，ＳＡＮＴＩＮＩ Ｓ．Ｃｏｎｔｅｎｔ—ｂａｓｅｄ ｉｍ－ ａｇｅ ｒｅｔｒｉｅｖａｌ ａｔ ｔｈｅ ｅｎｄ ｏｆｔｈｅ ｅａｒｌｙ ｙｅａｒｓ［Ｊ］．Ｗ，ＥＥ Ｔｒａｎｓａｃｔｉｏｎ Ｏ１１ Ｐａｔ— ｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉ￣ｎｃｅ，２０００，２２（１２）：１３４９—１３８０． 个算法的时间复杂度为Ｄ（ｎ）。表１是６组不同的等高线数 据生成ＴＩＮ后处理平坦区域的时间，平坦三角形的个数基本 一致，为什么时间会有比较大的差别？这是由于处理平坦区 图５一条等高线内平坦区域处理前后的平面投影图 域时需要遍历ＴＩＮ造成的，原三角形个数较多的ＴＩＮ的处理 时间会有所增加。 参考文献： 【１】 陈仁喜，龙毅．顾及三角形处理的ＴＩＮ建立算法【Ｊ】．武汉大学学 报（信息科学版），２００３，２８（５）：６１９－６２２． 【２】李志林，朱庆．数字高程模型【Ｍ】．武汉：武汉大学出版社，２００３： 图４相邻等高线间平坦区域处理前后的平面投影图 表１ 平坦区域的处理时间 ８４—８９． 【３】 章孝灿．快速高精度ＤＥＭ生成技术研究【Ｄ】．杭州：浙江大学， ２００２． 等高线离散点原三角平坦三角现有三角插入点时间 条数数个数形个数形个数 形个数 个数 ／ｓ 【４】 邸元．基于等高线建立ＤＴＭ中平坦区域的一种处理方法【Ｊ】．计 算机辅助设计与图形学学报，２０００，１２（８）：５６６－５７０． 【５】 ，王东华，乔朝飞，等．等高线邻接关系的表达及应用研究 【Ｊ】．测绘学报，２００４，３３（８）：１７４—１７８． 【６】 ＣＨＲＩＳＴＯＰＨＥＲ Ｍ Ｇ，ＭＡＣＩＥＪ Ｄ．Ｔｅｒｒａｉｎ ｍｏｄｅｌｌｉｎｇ ｆｒｏｍ ｃｏｎｔｏｕｒｓ 【Ｃ】／／３ｒｄ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｈｅ Ｉｎｔｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｄｙｎａｍｉｃ ｎｄ Ｍｕｌａｉｔ—ｄｉｍｅｎｓｉｏｎａｌ ＧＩＳ．ａａｎｇｈｏｋ：【Ｓ．ｎ．】，２００１：４２７—４３２．
