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

最小生成树是表示图像的常用结构，在图像匹配和图像检索等任务中应用广泛。但是，现有方法只是利用最小生成树来表示图像，缺乏分析和描述图像结构的量化指标。本文提出了基于最小生成树的图像结

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

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

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

为了量化分析图像结构基元对图像结构的描述能力，本文利用最小生成树来表示图像中的结构基元， 提出了基于最小生成树(MST)的图像结构描述评价指标。直观上看，最小生成树如同图像的“骨架”结构支撑着整幅图像，如图1 所示，其支撑范围越大、边的总长度越长，则结构基元的分布越均匀，对图像的描述越充分。

从理论上讲， 文献[8] [9]证明最小生成树所有边的加权和与Rényi 熵之间存在着正比的关系， 最小生成树边的加权和越长，其熵值越大，则结构基元在图像中分布越均匀，对图像结构的描述越充分。

根据这一理论， 本文分别在图像空间和结构基元的描述符空间构造最小生成树， 基于最小生成树边的加权和定义了分布均匀度、独特性和支撑度三个指标，来量化衡量结构基元的描述能力。

2. 基于MST 的图像结构描述 2.1. 最小生成树与Rényi 熵 对于图像中提取的一组结构基元(如特征点、特征曲线等)，将其抽象为一组点集{ }1niiZ= ，其中n 为结