ABSTRACT

The MST (Minimum Spanning Tree) is an effective structure for representing images in applications such as image matching and image retrieval. However, previous methods only use MST to connect the structural elements in images and are unable to quantitatively analyze the capability of the elements in describing the image. A method for structural description of images based on MST is proposed in this paper. The MST constructed from the structural elements extract from the image supports the image like the skeleton of the image, which reflects the structure of image. Three indexes for evaluating the distribution uniformity, the distinctiveness and the span ning degree of a set of image structural elements are defined based on the MST. The evaluating indexes can be used to analyze the structural information of an image and can also be used to evaluate the capability of a set of structural elements to describe the structure of an image. Experiments on simulated points and real images validate the proposed indexes. The indexes can be used to classify the structures of image scene and to evaluate the difficulty of image matching.

Keywords:Image Structure Description, MST, Evaluation Indexes, Image Matching, Scene Classification

基于最小生成树的图像结构描述

曲智国，谭贤四，张伟，王红，林强

空军预警学院二系，湖北 武汉

收稿日期：2017年4月8日；录用日期：2017年4月27日；发布日期：2017年4月30日

摘 要

最小生成树是表示图像的常用结构，在图像匹配和图像检索等任务中应用广泛。但是，现有方法只是利用最小生成树来表示图像，缺乏分析和描述图像结构的量化指标。本文提出了基于最小生成树的图像结构描述指标，首先采用最小生成树来表示图像中的结构基元，然后基于最小生成树定义了分布均匀度、支撑度和描述符独特性三个量化指标，来衡量图像中结构基元对图像结构的描述能力。采用仿真点集和实际图像进行实验，结果表明，基于最小生成树定义的量化指标可以较好地描述图像的结构，可用来对图像场景粗略分类和评价图像匹配的难易程度。

关键词 :图像结构描述，最小生成树，评价指标，图像匹配，场景分类

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图像描述是图像处理、分析和理解中的关键问题，是指根据应用任务不同而对图像采取的不同表示方式，最直观的描述方式就是灰度表示(灰度图像)或RGB三色表示(彩色图像)。为了降低运算量，简化描述方式，在一些典型应用中，如图像匹配、目标识别、图像检索等，通常提取点、线、区域等特征来描述图像结构，即基于特征的描述方式。

在基于特征的图像结构描述方式中，结构基元(点、线、区域等特征)反映了图像的内容信息，单个结构基元表示了图像的局部灰度变化，而结构基元之间的相对位置关系则隐式地反映了图像的结构。进一步，为了显式地描述图像的结构，学者们采用图的方式来表示图像中提取的结构基元，如赋权完全图 [1] 、DT图 [2] 、近邻图 [3] 、最小生成树(MST) [4] 等，从而形成图像的结构化描述。但是，这些方法只是采用图的结构来表示图像中提取的基元，即将图像结构基元用不同形式的图连接起来，侧重点在后续的处理任务中，如匹配、识别等，而没有分析图像中所提取的一组结构基元对于图像结构的描述能力，缺乏图像结构化描述的量化指标。

对于图像中提取的结构基元，这些基元在图像中分布情况是否均匀、相互之间的独特性如何、对整幅图像的覆盖程度，目前都是定性的描述，缺乏量化的指标，而这些因素对图像匹配和检索等任务都具有重要的影响 [5] [6] [7] 。例如，从有利于图像匹配的角度，常常要求图像结构基元要稳定存在、尽量分布均匀且相互之间要有区分度。

为了量化分析图像结构基元对图像结构的描述能力，本文利用最小生成树来表示图像中的结构基元，提出了基于最小生成树(MST)的图像结构描述评价指标。直观上看，最小生成树如同图像的“骨架”结构支撑着整幅图像，如图1所示，其支撑范围越大、边的总长度越长，则结构基元的分布越均匀，对图像的描述越充分。从理论上讲，文献 [8] [9] 证明最小生成树所有边的加权和与Rényi熵之间存在着正比的关系，最小生成树边的加权和越长，其熵值越大，则结构基元在图像中分布越均匀，对图像结构的描述越充分。根据这一理论，本文分别在图像空间和结构基元的描述符空间构造最小生成树，基于最小生成树边的加权和定义了分布均匀度、独特性和支撑度三个指标，来量化衡量结构基元的描述能力。

2. 基于MST的图像结构描述

2.1. 最小生成树与Rényi熵

对于图像中提取的一组结构基元(如特征点、特征曲线等)，将其抽象为一组点集，其中为结

图1. 最小生成树表示的图像结构

构基元的个数，对结构基元的描述可以用随机向量表示，表示向量的维数。一般地，对结构基元的描述由其坐标和特征描述符两部分组成，坐标决定了其在图像平面上的空间位置，特征描述符反映了结构基元的属性信息。

在点集形成的无向完全图上求解MST，是连接中所有顶点的边集，且不构成回路，两个顶点之间的边长为。最小生成树(MST)的加权长度总和为：

(1)

式中，称作边的加权指数， [9] ，为点集的维数。

如果是d-维独立同分布随机向量，服从Lebesgue多元密度函数，图的边长函数连续且拟可加(Quasi additive)，则当时，从图中建立的最小生成树长度满足下式 [8] ：

(2)

式中，，为独立于的常数，仅仅依赖于图的边加权指数。

Rényi熵是Shannon熵的广义形式，也称熵，其定义如下 [10] ：

(3)

式中，是概率密度函数，。

结合式(2)和式(3)，可以得到最小生成树的边加权总和与Rényi熵的关系：

(4)

式中，为可移除的偏置量，忽略该常数，可得：

(5)

由式(5)可以看出，最小生成树的边长加权总和与Rényi熵之间存在着正比的关系，值越大，则其Rényi熵值也越大，说明该组变量的随机性越大，因此我们也可以利用来衡量点集的随机性 [11] 。

2.2. 图像结构描述评价指标

对于大小为的图像I，从中提取的一组结构基元，可以构造最小生成树，利用边长加权总和来衡量点集的随机性。因此，基于最小生成树定义以下指标来评价结构基元对图像结构的描述能力。

定义1：分布均匀度(Distribution Uniformity, DU)。当结构基元用其图像坐标表示时，定义分布均匀度如下：

(6)

式中，，此时，若边加权指数取为，则。这一指标反映了结构基元在图像平面上的分布情况。

定义2：描述符独特性(Descriptor Distinctiveness)。当结构基元采用描述符向量表示时，在描述符空间构造最小生成树，定义为结构基元描述符的独特性：

(7)

式中，其取值随着描述符的维数的变化而不同。这一指标反映了结构基元描述符向量在其高维空间的分布情况。

定义3：支撑度(Spanning Degree, SD)。定义包围最小生成树的最小凸多边形的面积与图像面积之比为结构基元对整幅图像的支撑度：

(8)

这一指标反映了结构基元对图像的覆盖程度，也即对图像结构描述的充分程度。

上述三个指标，分布均匀度和支撑度描述了结构基元在图像空间上的分布情况：其值越大，表明结构基元对图像的覆盖越充分，分布越均匀，对图像的描述能力越强。描述符独特性描述了结构基元在描述符空间的分布情况：其值越大，表明结构基元的描述符的之间的相关性越小，匹配过程中出现误匹配的概率也越小。另外，由于描述符是基于结构基元构造的，描述符独特性也反映了图像中结构基元的重复情况，该值越大，说明图像中的重复模式越少。

从应用的角度来看，一方面，上述三个指标可以用于评价图像中一组结构基元对图像的描述能力：对于同一图像中提取的不同结构基元，哪些结构基元的组合在图像中分布更均匀，对图像覆盖更充分，更有利于图像匹配；另一方面，由于图像中的结构基元分布情况取决于图像自身内容，上述指标还可以用于分析不同图像的场景，进行场景粗略分类：是结构化的场景(如存在建筑物、人工目标等的场景)还是非结构化的场景(存在树、草等的自然场景)。下节通过实验来说明上述指标的应用，并验证其可行性。

3. 实验分析

3.1. 仿真点集实验

在二维平面上，生成在内服从均匀分布和高斯分布的两组点集，如图2所示，其中高斯分布点集的均值为，标准差为。

基于点集构造最小生成树，加权指数设为，计算不同分布点集分布均匀度与支撑度，其随着点集数目的变化曲线如图3所示。由图可以看出，对于包含相同数目的点集，服从均匀分布的点

图2. 在单位区间上服从均匀分布和高斯分布的100个点及其最小生成树和外接多边形

图3. 不同分布的点集的均匀分布度和支撑度

集的分布均匀度指标和支撑度明显大于服从高斯分布的点集，而且方差较大的高斯分布的点集的分布均匀度指标和支撑度大于方差较小的点集。这与图2所示的点集分布情况的视觉效果是一致的，服从均匀分布的点集广泛地、均匀地分布在整幅图像上，而服从高斯分布的点集聚集地分布在局部区域内，而且方差越小，点集分布的范围越小，从而不能充分地描述整幅图像的结构。这表明本文提出的均匀分布度指标和支撑度指标是有效的，能构描述图像中的结构基元在图像空间的分布情况，和越大，说明结构基元在图像中的分布越均匀，对图像的覆盖越充分。

由2.2节可知，描述符独特性与分布均匀度的定义是相同的，二者的差异仅仅是描述的空间不同，因此上述对分布均匀度讨论可以推广至描述符独特性指标。

3.2. 实际图像实验

采用文献 [12] 提供的图像序列作为实验图像，其中Wall图像序列和Trees图像序列是纹理场景(自然场景)，Graffiti图像序列、Leuven图像序列描述的是结构化场景(人工目标场景)，而Boat图像序列和Ubc图像序列描述的场景中同时存在结构化目标(建筑物、船只)和纹理目标(数木、草地)。每个图像序列中的第一幅图像如图4所示。

对于每个图像序列的第一幅图像，首先根据特征点响应强度(显著度)大小分别从其中提取不同数目的特征点 [12] ，，并为每个特征点构造SIFT描述符 [13] ；然后利用提取的不同数目特征点构造最小生成树，计算支撑度和分布均匀度，绘制和的变化关系图；利用SIFT描述符距离构造最小生成树，计算独特性指标，并绘制的变化曲线。计算、时的加权指数分别为和，图5给出了不同类型图像中的特征点的三种指标比较，图中数值为采用相应数目的均匀分布点集进行归一化后的取值。根据图5，可以得出结论如下：

1) 比较不同类型图像的和可以看出，纹理场景图像、结构化场景图像和混合场景图像大致排序是：纹理场景图像 > 结构化场景图像 > 混合场景图像。这表明，本文提出的评价指标可以用来粗略判断图像场景的类型。

2) 6个图像序列中的分布均匀度都小于均匀分布点集的，说明特征点集在图像中的分布是非均匀的，这是由图像内容决定，实际图像中总是存在一定结构的。尽管如此，使特征点尽量均匀分布在图

图4. 图像序列的第一幅图像示意图

图5. 不同图像类型的分布均匀度、支撑度和描述符独特性

像场景中，对于减少特征点数量和图像匹配都是有利的，因此在实际应用选取特征点时可以利用分布均匀度作为一个准则。

3) 在6幅图像中，Leuven图像序列的特征点描述符独特性最大，Graffiti图像和Trees图像的特征点描述符独特性较差，其他图像的特征点描述符独特性指标几乎相当，表明Leuven图像中的重复模式较少，特征点匹配难度最低，而Graffiti图像序列和Trees图像序列中的重复模式较多，特征点匹配难度较高，其他图像序列的匹配难度居中。上述结论与文献 [12] [13] 的识别率实验结果是一致的，表明本文提出的描述符独特性指标可以用来分析图像匹配难易程度。

综上所述，基于最小生成树定义的三个指标可以用来评价图像中结构基元的分布情况、重复模式情况，实现对图像结构的描述，从而获取图像场景内容的抽象信息，为后续高层处理提供指导。具体地讲，本文提出的指标可以用于图像场景的粗略分类、衡量图像匹配的难易程度以及图像结构基元选取等应用任务中。

4. 结束语

本文基于最小生成树定义了三个指标来量化描述图像的结构基元分布情况和重复模式情况，从而实现对图像结构的量化描述。实验表明，这三个指标是可行的、有效的。从应用上讲，对于图像中提取的一组结构基元，这三个指标可以用来评价该组结构基元对图像结构的描述能力，从而可以作为评价准则应用于结构基元选取任务中。另外，由于图像结构基元的分布情况是由图像自身内容决定的，这三个指标也可以用来判断图像的场景类型和分析图像匹配难易程度。

基金项目

本文受国家自然科学基金(61401504)、中国博士后基金面上项目(2014M562562)基金资助。

文章引用

曲智国,谭贤四,张伟,王红,林强. 基于最小生成树的图像结构描述
Image Structure Description Based on MST[J]. 图像与信号处理, 2017, 06(02): 106-113. http://dx.doi.org/10.12677/JISP.2017.62013

参考文献 (References)