安排用于显示的项目的系统和方法

摘要

一种安排诸如数字图像或多媒体图标的可搜索项目以用于在图形用户接口上展示的系统。该系统具有优化器模块，其最小化用于在布局空间安排项目的成本函数并被应用于项目的一个或多个预定的特性。优化器模块还通过将每个项目视为具有在布局空间中的空间分布来创建混合分布，以及控制混合分布的熵以便最大化每个项目在布局空间中占用一个单独位置的程度。然后，绘制器模块绘制布局以产生显示。

说明书

技术领域

本发明涉及用于安排用于显示的项目的系统和方法，尤其，但不仅仅涉 及对当使用图像浏览系统时可用图形方式显示的图像的查看。本发明也可用 于安排能在显示上用图形表示的其他数字资源。

背景技术

人类能处理大量的可视化的和多媒体的信息。然而，他们通常很难精确 地定义和描述这样的信息。例如，据估计大脑可辨别大约10000个颜色上的 细微差别，而个人只能命名少量的颜色词(大约12个)。因此，当用通常采 用元数据的基于文本的搜索来搜索数据库时，访问图像可能是具有挑战性 的。

基于内容的索引和检索方法给该问题提供了部分解决方案。在许多基于 内容的检索系统中的重点在于基于对查询项的相似性概念来自动检索相关 项。例如，基于内容的图像检索(CBIR)可使用绘画、照片、打印、图画 或其他对象的所选择的图像的特征来找到视觉上相似的图像并且定位集合 中的匹配，即使它们没有与原始图像共享元数据。

浏览为探索式搜索提供了有效的手段并且给传统的基于内容的检索提 供了可用的替代方法，在所述基于内容的检索中，用户构造文本查询或图像 查询。另外，当探索图像和/或多媒体集合时，用户意图可能是很模糊的。他 们期望系统能够提供大量的线索和选项来指导他们的导航。

图像和/或多媒体浏览系统需要通过适当地布置项目的集合用于显示来 使用户能够看见它们(或者它们的缩略图或图标)。许多系统将项目分为不 同的类并且简单地将这些项目在二维显示上布置为每个类的1D列表(Kang， H.and Shneiderman，B.(2000).Visualization methods for personal photo  collections browsing and searching in the photofinder.在IEEE International  Conference on Multimedia and Expo中，第1539-1542页)。这样的1D列表不 能很好地描绘项目之间的相互关系。

或者，基于2D映射的可视化(例如，G.Nguyen and M.Worring(2006). Interactive access to large image collections using similarity-based visualization. Journal of Visual Languages and Computing，19(2)：203-224)这样布置项目以 使得相似的项目在2D显示上互相靠近而非常不同的图形将进一步分开。基 于2D映射的技术在其从项目提取高维特征向量、测量成对项目的相似性以 及执行降维以便将项目的分布从高维空间映射到2D显示空间的方式上存在 差异(Rodden，K.(2002).Evaluating similarity-based visualisations as interfaces  for image browsing.剑桥大学博士论文)。

例如，Rubner等人(Rubner，Y.，Tomasi，C.，and Guibas，L.(1998).A metric  for distributions with applications to image databases.In ICCV，第59-66页， Bombay，India)使用推土机距离(Earth Mover′s Distance)来测量成对相异性 和执行多维标度法(MDS)以将图像颜色和纹理特征转换到2D空间。

当在显示上可视化大量的项目用于浏览时，这些项目将重叠并且重叠的 程度将倾向于随着项目的数量而增加。另外，该显示空间的区域将经常是空 的。由于降维技术在映射到显示位置时没有考虑用于表示这些项目(例如， 图像缩略图或图标)的图像的大小，这些问题将进一步被恶化。两个非常相 似的项目可能被投影到非常接近的位置以致于一个项目将与另一个项目在 很大程度上重叠。为了减少重叠，在通过降维获得2D显示上的图像位置后， 使用梯度下降法来向未被占用的2D显示区域移动被重叠的图像。Basalaj (Basalaj，2000)和Liu等人(Liu et al.，2004)在离散域使用模拟MDS以在网格 的单个单元中显示每个图像。尽管这些方式能有助于减少图像重叠，但它们 主要处理少量的图像(大约20～200个)。

本发明的目标在于改善在显示上布置或安排项目的方式。

发明内容

根据本发明的第一个方面，提供了一种安排用于显示的诸如数字图像或 多媒体图标的可搜索项目的系统，所述系统包括：

优化器模块，其：最小化用于在布局空间安排项目的成本函数，所述成 本函数被应用于所述项目的一个或多个预定的特性；通过将每个项目视为具 有在布局空间中的空间分布来创建混合分布；以及

控制混合分布的熵以便最大化每个项目占据布局空间中单独的位置的 程度；

绘制器模块，用于将这样产生的布局绘制到显示。

优先地，成本函数惩罚低熵混合分布，并对布局空间中的在其中项目间 的距离取决于项目内容的相似性的布局进行奖励。

优选地，布局空间包括在其中包含项目的一个或多个布局区域。

优选地，布局空间中每个项目的空间分布是高斯分布。

优选地，高斯分布是高斯混合分布。

优选地，混合分布对每个高斯分量具有相同的权重。

优选地，基于内容的相似性来布置项目。

优选地，所述预定特性是描述诸如颜色、纹理和/或形状的方面的特征。

优选地，每个项目的缩略图或图标的大小和形状信息可被嵌入到成本函 数中。

优选地，所述熵是二次Renyi熵。

优选地，处理项目的步骤包括；假定项目分布在数据流形上；

确定所述数据流形的结构；

以及应用流形学习技术来将项目映射到低维布局空间以便近似地保存 项目的内容结构。

优选地，成本函数还进一步适用于折衷布局空间中项目的内容结构保存 和熵。

优选地，控制该折衷的参数是用户定义的。有利地，这将允许用户对内 容结构保存和布局熵的折衷进行实验。

优选地，项目被以2-D方式安排在显示上。

或者，放置项目以便在2-D显示上给出3-D安排的外观。

或者，项目被以3-D方式安排在3-D显示上。

优选地，显示包括可以是包括显示的一部分的显示空间使得项目在显示 空间内展开。

优选地，项目是图像或其缩略图。

或者，项目是诸如音频或视频剪辑的多媒体项目的图标。

优选地，优化器模块包括多个子模块。

优选地，优化器模块包括初始化器模块，其产生项目的初始布局。

优选地，优化器模块包括搜索引擎，其基于成本函数搜索最佳布局。

优选地，以由多媒体内容模块、布局展开模块和布局范围模块计算的布 局质量分数的组合来计算成本函数。

优选地，多媒体内容子模块计算度量布局对内容结构的保存程度的分 数。

优选地，布局展开子模块计算度量布局的熵的分数。

优选地，布局范围子模块计算度量对在布局区域或区域内放置项目的约 束的满意程度的分数。

优选地，优化器模块还包括组合器模块，其将这些分数组合为总分数， 搜索引擎用该总分数作为布局的成本函数值。

优选地，搜索引擎应用最优化方法来建议将要被评分的布局。

优选地，搜索引擎在建议和评分布局的多次迭代后输出经优化的布局。

根据本发明的第二个方面，提供了一种安排用于显示的诸如数字图像或 多媒体图标的可搜索项目的方法，所述方法包括：

通过将每个项目视为具有在布局空间中的空间分布来创建混合分布；以 及最小化用于在布局空间安排项目的成本函数，所述成本函数被应用于所述 项目的一个或多个预定的特性；

控制混合分布的熵以便最大化每个项目占据布局空间中一个单独位置 的程度；以及

将这样产生的布局绘制到显示。

优选地，成本函数惩罚低熵混合分布，并对在其中布局上项目间的距离 取决于项目内容的相似性的布局进行奖励。

优选地，布局空间包括在其中包含项目的一个或多个布局区域。

优选地，布局空间中每个项目的空间分布是高斯分布。

优选地，混合分布是高斯混合分布。

优选地，混合分布对每个高斯分量具有相同的权重。

优选地，基于内容的相似性来布局项目。

优选地，所述预定特性是描述诸如颜色、纹理和/或形状的方面的特征。

优选地，每个项目的缩略图或图标的形状信息可被嵌入到成本函数中。

优选地，所述熵是二次Renyi熵。

优选地，处理项目的步骤包括；假定项目分布在数据流形上；

确定所述数据流形的结构；

以及应用流形学习技术来将项目映射到低维布局空间以便近似地保存 项目的内容结构。

优选地，成本函数还进一步适用于折衷布局空间中项目的内容结构保存 和熵。

优选地，控制该折衷的参数是用户定义的。有利地，这将允许用户对内 容结构保存和布局熵的折衷进行实验。

优选地，项目被以2-D方式安排在显示上。

或者，放置项目以便在2-D显示上给出3-D安排的外观。

或者，项目被以3-D方式安排在3-D显示上。

优选地，显示包括可以是显示的一部分的显示空间使得项目在显示空间 内展开。

优选地，项目是图像或其缩略图。

或者，项目是诸如音频或视频剪辑的多媒体项目的图标。

根据本发明的第三个方面，提供浏览器，其包括：

具有显示的用户接口；

适于运行用于在显示屏幕上安排诸如数字图像或多媒体图标的可搜索 项目的计算机软件的计算装置，所述计算机软件包括：

优化器模块，用于：

最小化用于在布局空间安排项目的成本函数，所述成本函数被应用于所 述项目的一个或多个预定的特性；通过将每个项目视为具有在布局空间中的 空间分布来创建混合分布；以及

控制混合分布的熵以便最大化每个项目占据布局空间中一个单独位置 的程度；

绘制器模块，用于将这样产生的布局绘制到显示。

优选地，成本函数惩罚低熵混合分布，并对在其中布局上的项目间的距 离取决于项目内容的相似性的布局进行奖励。

优选地，布局空间包括在其中包含项目的一个或多个布局区域。

优选地，布局空间中每个项目的空间分布是高斯分布。

优选地，混合分布是高斯混合分布。

优选地，混合分布对每个高斯分量具有相同的权重。

优选地，基于内容的相似性来布置项目。

优选地，所述预定特性是描述诸如颜色、纹理和/或形状的方面的特征。

优选地，每个项目的缩略图或图标的形状信息可被嵌入到成本函数中。

优选地，所述熵是二次Renyi熵。

优选地，处理项目的步骤包括；假定项目分布在数据流形上；

确定所述数据流形的结构；

以及应用流形学习技术来将项目映射到低维布局空间以便近似地保存 项目的内容结构。

优选地，成本函数还进一步适用于折衷布局空间中布局的内容结构保存 和熵。

优选地，控制该折衷的参数是用户定义的。有利地，这将允许用户对内 容结构保存和布局熵的折衷进行实验。

优选地，项目被以2-D方式安排在显示上。

或者，放置项目以便在2-D显示上给出3-D安排的外观。

或者，项目被以3-D方式安排在3-D显示上。

优选地，优化器模块包括多个子模块。

优选地，优化器模块包括初始化器模块，其产生项目的初始布局。

优选地，优化器模块包括搜索引擎，其基于成本函数搜索最佳布局。

优选地，以由多媒体内容模块、布局展开模块和布局范围模块计算的布 局质量分数的组合来计算成本函数。

优选地，多媒体内容子模块计算度量布局对内容结构的保存程度的分 数。

优选地，布局展开子模块计算度量布局的熵的分数。

优选地，布局范围子模块计算度量对在布局区域或区域内放置项目的约 束的满意程度的分数。

优选地，优化器模块还包括组合器模块，其将这些分数组合为总分数， 搜索引擎用该总分数作为布局的成本函数值。

优选地，搜索引擎应用最优化方法来建议将要被评分的布局。

优选地，搜索引擎在建议和评分布局的多次迭代后输出经优化的布局。

附图说明

现将参考附图仅以示例的方式来描述本发明，其中：

图1a至1c显示了使用根据本发明实施例的系统的示例的、项目数据的 收敛，尤其是，图1(a)显示了对于迭代次数的成本函数值，图1(b)和1(c)显 示了基于初始图像位置和收敛后的位置的图像集合的可视化结果；

图2是显示使用本发明的方法以及现有技术替代方法即Moghaddam的 方法和Nguyen的方法的内容结构错误和图像重叠之间的关系的曲线图；

图3a至图3d分别显示使用Isomap、Moghaddm的方法、Nguyen的方 法和本发明方法的示例的100个图像的可视化结果；

图4a至4i显示了1000个艺术图像的可视化结果，其中图a至c显示了 初始图像位置的分布、采用结构保存和图像重叠间折衷的位置的分布，以及 仅关注减少图像重叠的位置的分布。图4d、4f和4h显示了对应于图4a、4b、 4c中的位置的图像集合的可视化结果，而图像4e、4g和4i显示了在布局中 心的一个图像周围缩放图像位置之后部分图像集的可视化结果；以及

图5a至5i显示了1000个艺术图像的可视化结果，其中图a至c显示了 初始图像位置的分布、采用内容结构保存和熵之间折衷的位置的分布，以及 仅关注熵的位置的分布。图5d、4f和4h显示了对应于图4a、4b、4c中的位 置的图像集合的可视化结果，而图像5e、4g和4i显示了在布局中心的一个 图像周围缩放图像位置之后部分图像集的可视化结果；

图6示出了通过限制使所有图像的位置位于矩形布局区域内的、艺术图 像的图像位置和相应的图像可视化结果；

图7是织物样本被基于图像位置可视化的又一个示例；

图8a和8b分别显示了当优化500个图像的布局时每次迭代的时间曲线 图和所获得的图像近似的准确度曲线图。图6c显示了随布局中图像数量变 化的平均计算时间的曲线图，并表明了改善的缩放比例。图6d显示了使用 本发明的近似法所获得的100个图像的布局；

图9示出了在步骤大小上没有阈值τ(第一列)和阈值τ＝0.05的几次迭 代中图像位置的变化；

图10是当图像的数量相对于可用的布局区域相对大时比较本发明和两 个现有技术的将图像展开的能力的三个图的集合。

图11a至11d说明了对图10有关的描述的技术的性能上的变化的简化 的解释；

图12显示了使用本发明和现有的Isomap技术基于颜色直方图的1000 个图像的可视化结果。

图13是本发明一个实施例的框图；以及

图14显示了根据本发明实施例的优化器模块的示例的更详细的框图。

具体实施方式

本发明提供允许基于图像内容的相似性来安排用于显示的项目的系统、 方法和浏览器。本发明可用于根据项目内容的特征(例如形状、颜色、纹理 和图案)来安排项目(例如图像)，以使得显示上项目间的距离与就这些特 征而言的项目间的相似性相关。

该过程的第一阶段是计算在布局空间的项目的布局(layout)。一旦计算 出布局，该布局可以用来呈现项目用于在诸如计算机屏幕的装置上显示。在任 何一次不需要将所有的布局空间都映射到显示。例如，用户可能想详细查看 该布局的一小部分，在这种情形中，只有位于这一小部分布局中的项目将被 实际地呈现到显示空间/窗口中。

应理解术语布局、布局区域和布局空间指的是在有关项目的数据被绘制 到可见的显示图像中之前被处理的该数据。

在本发明的至少一个示例中，目的是通过如下方式“充分”利用布局空 间，所述方式包括：

近似均匀地布置项目以便有效地使用可用的布局区域；

将项目保持在可用的布局区域(例如，其可以是圆形的、矩形的或环形 的)的边界之内；以及

以依赖于项目内容的方式来布置项目，通常使相似的项目互相靠近(此 处称为“内容结构保存”)。

本发明优化成本函数并且使用通过将每个项目和混合模型中的分量相 关联而在布局空间中形成的混合模型。最大化该混合模型的熵可以在布局空 间中展开图像以占据预定布局区域。特别地，每个项目可与高斯分布相关联， 所述高斯分布具有由该项目的空间范围确定的协方差矩阵和被有效地计算 和优化的二次Renyi熵。

无意于被理论所束缚，但给出至少本发明的下列实施例通过其操作的数 学描述的下列说明。

给定一组项目{I_i}，i＝1，...，N，其具有所提取的高维特征向量{X_i}和图像 (或缩略图或图标)大小{S_i}，关心的问题是通过折衷如下两个要求来在布 局空间的预定区域或某些区域中布置项目，所述要求如下：(1)在布局空间 中项目之间的距离应该取决于项目内容的相似性，和(2)项目应该分散以 充分利用布局区域。

第一个要求可通过流形(manifold)学习来实现。通过假设项目分布于 嵌入在高维空间中的低维的非线性流形，流形学习技术能被应用以检测和发 现数据流形的结构并将该流形展开到向量空间中。一旦原始的高维数据点能 被如实地嵌入到较低维的向量空间，数据库中的图像的相对近邻将被近似地 保存在较低维的(例如，2D或3D)空间中。这被称为内容结构保存。

大量的高维项目被可视化于2D或3D空间中用于浏览、探索和组织。 根据用于流形结构和结构保存的标准，已经提出了许多不同的流形学习技 术，例如，Isomap(Tenenbaum等人，2000)，Laplacian eigenmaps(拉普拉 斯特征映射)(Belkin和Niyogi，2002)，扩散映射(Nadler等人，2005)，和最大 方差展开(Weinberger等，2005)。原则上，可以使用任何流形学习技术。这 里Isomap被用作示例。Isomap首先基于{X_i}构造稀疏图，其中，稀疏图中 的顶点和项目之间一一对应。

通过K-最近邻(KNN)法来构造相似项目之间的边。每条边被分配以 权重W_ij，其是这两个邻近项目之间的相异性。然后，获取任何两个项目间 的最短线的(geodesic)距离的近似值D_ij来作为这两个项目在该图中对应顶 点之间的最短路径。不失一般性，{D_ij}是归一化的，这使得最大值{D_ij}由布 局区域的大小来限定。Isomap能通过最小化E_s来确定在较低维的(例如， 2D或3D)向量空间中的图像位置{Y_i}，所述E_s满足：

$E_s={\Sigma }_{i=1}^N{\Sigma }_{j=1}^N{(d_{\mathrm{ij}}-D_{\mathrm{ij}})}^2---\left(1\right)$

其中d_ij是y_i和y_j之间的欧式距离。

注意，当两个项目I_i和I_j在内容上相似时，这两个项目间的距离D_ij将是 很小的，并且相应地在较低维空间中这两个项目可能将显得彼此靠近。

对于第二个要求，提出了一种从熵的角度来度量在布局区域展开的项目 的质量的方法。给定低维布局区域中的图像位置y_i，使用高斯分布G(y_i，∑_i) 来近似该图像在空间中的空间分布，其中∑_i是由项目的大小和形状、图像的 数量和布局区域的大小来确定的。接着，可合并将要被安排在该布局区域的 所有项目的高斯分布以便获得对每个高斯分量具有相同权重的高斯混合， 即，

$p\left(y\right)=\frac{1}{N}{\Sigma }_{i=1}^{N}G({y-y}_i,{\Sigma }_i)---\left(2\right)$

为了在布局区域R中展开项目，该布局空间中的高斯混合的熵可以被最 大化。这里建议使用Renyi的二次熵测量，而不是传统的香农熵。高斯混合 的二次Renyi熵H可以作为高斯分量之间成对测量的总和而被有效地估计 (Torkkola，2003)，即

$H=-\log \left\{\frac{1}{N^2}{\Sigma }_{i=1}^N{\Sigma }_{j=1}^{N}G(y_i-y_j,{\Sigma }_i+{\Sigma }_j)\right\}---\left(3\right)$

通过最大化H(或最小化-H)可以很好地使用区域R。这可以安排项目 使得保持较小的空的空间以及保持较小的项目间的重叠，并且这样项目可以 更均匀地分散在该区域上。不得不折衷这两个要求。这意味着，该问题是要 最小化E_λ，

E_λ＝(1-λ)E_s-λH，(4)

受到每个项目应该停留在区域R内的约束，其中λ∈[0，1]是折衷参数。 应该以应用相关的方式来确定λ。当λ接近于0时，重点在于保存流形结构。 当λ接近于1时，重点在于最大化熵。

可以使用任何数量的已知的最优化方法来解决这个最优化问题。这里使 用惩罚函数法来惩罚R之外的项目位置。直观地，从项目位置Y_i到布局区 域R的欧式距离越大，该项目的位置越差，因此惩罚值越高。以E_b表示所 有图像位置的平均惩罚成本，即，

$E_b=\frac{1}{N}{\Sigma }_{i=1}^{N}f\left(y_i\right)---\left(5\right)$

其中，f(y_i)是从y_i到布局区域R的欧式距离(即min_y∈R||y-y_i||)的单调增 加非负函数。然后，该问题可最终转换为最小化E，

E＝E_λ+γE_b，     (6)

其中，γ是平衡E_λ和E_b的常量。

可使用基于梯度的优化来找到E的(局部)最小值。自公式(4)

$\frac{\partial E}{{\partial y}_j}=(1-\lambda )\frac{{\partial E}_S}{{\partial y}_j}-\lambda \frac{\partial H}{{\partial y}_j}+\gamma \frac{{\partial E}_b}{{\partial y}_j}---\left(7\right)$

Kruskal(Cox and Cox，2001)已经推导出E_s与y_i的梯度：

$\frac{{\partial E}_s}{{\partial y}_j}=-2{\Sigma }_{i\ne j}\frac{(d_{\mathrm{ij}}-D_{\mathrm{ij}})}{d_{\mathrm{ij}}}·(y_i-y_j)---\left(8\right)$

从公式(3)，能推导出H与y_j的梯度：

$\frac{\partial H}{{\partial y}_j}=-\frac{1}{\alpha }{\Sigma }_i\left\{G(y_i-y_j,{\Sigma }_i+{\Sigma }_j)\right({({\Sigma }_i+{\Sigma }_j)}^{-1}(y_i-y_j)\}---\left(9\right)$

其中，α＝∑_i∑_jG(y_i-y_j，∑_i+∑_j)。

对于E_b与y_i的梯度，采用离散逼近，因为鉴于布局区域的自由形式的形 状，通常很难参数化地表示函数f(y_j)。在该逼近中，E_b与y_i的梯度的第k个 分量通过以下公式来计算的：

$\frac{{\partial E}_b}{{\partial y}_{\mathrm{jk}}}\stackrel{·}{=}\frac{1}{N}{\Sigma }_{i=1}^N\frac{f(y_j+{\mathrm{\delta u}}_k)-f\left(y_j\right)}{\delta }---\left(10\right)$

其中δ为离散的单位比例(unit scale)，u_k是对于布局区域的第k维的基本向 量。

对于优化，可以通过使用Isomap算法最小化E_s来很容易地获得良好的 初始项目位置{y_i}。

该方法不受布局区域维度的限制，也不受项目形状的限制。然后，为了 实验上评估该方法，在下文中，认为2D布局区域和每个图像I_i被假设为具 有高度h_i和宽度w_i的矩形。在这种情形下，协方差矩阵∑_i是对角的，即，

${\Sigma }_i=\left(\begin{array}{cc}{\sigma }_{i1}^2& 0\\ 0& {\sigma }_{i2}^2\end{array}\right)---\left(11\right)$

注意，σ_i1和σ_i2不应该是非常小或非常大，因为在这两种情况下，H(公 式3)将会收敛为常数函数，因此图像布局不能有效地展开。这里，提出了 一种通过图像大小、布局区域大小和要展开的图像的数量来自动确定σ_i1和 σ_i2的方法，即，

${\sigma }_{i1}=\frac{w_i}{2}·\sqrt{\frac{\left|R\right|/N}{\bar{w}·\bar{h}}}$

${\sigma }_{i2}=\frac{h_i}{2}·\sqrt{\frac{\left|R\right|/N}{\bar{w}·\bar{h}}}---\left(12\right)$

其中，|R|是布局区域的面积，和是要展开的所有图像的平均宽度和 平均高度。是对于每个项目的全局尺度，使得所有项目的空间分布的 组合p(y)(公式2)能有效地覆盖布局区域，从而将项目展开为近似地均匀 分布。对于固定的布局区域R，项目的数量越多，平均的项目大小越大，全 局尺度就越小。对于固定的项目集合，布局区域越大，全局尺度就越大。每 一对(σ_i1，σ_i2)与对应的项目大小和全局尺度是线性相关的。

现参考本发明在多个图像数据库上的使用来描述本发明的性能，所述多 个图形数据库包括两个图像数据库，第一个图像数据库具有1000个来自商 业档案的织物设计的图像而第二个数据库包括1000个来自公共博物馆收藏 的艺术图像。使用两类特征来表示图像。通过在HSV颜色空间有规则地量 化色彩为32个值以及量化饱和度为16个值来提取具有512格的颜色直方图。 通过执行多分辨率Gabor变换，接着计算在每级图像分辨率的变换系数的方 差和均值，来提取纹理特征，给出108个纹理特征。

对于这两类特征，使用欧式距离来确定用于构建流形结构的最近邻。在 该测试中，缺省布局区域大小为调整每个项目I_i的大小，使得 其长度和宽度的最大值为预设值S_max＝0.08。此外，为了将所提出的算法与已 有的两个算法进行定量和定性的比较，在公式4中γ＝0，因为在已有的算法 中不使用E_b。在这种情形下，对于每个∑_i，σ_i1＝w_i/2和σ_i2＝h_i/2而没有全局尺 度。

在该评价中，通过结构错误e_s来度量结构保存的性能，

$e_s={\min }_{\beta }\left\{{\Sigma }_{i=1}^N{\Sigma }_{i=1}^N{(\beta ·d_{\mathrm{ij}}-D_{\mathrm{ij}})}^2\right\}---\left(13\right)$

其中，具有最小e_s的归一化因子β可以由分析计算得到，

$\beta =\frac{{\Sigma }_{i=1}^N{\Sigma }_{j=1}^N{d}_{\mathrm{ij}}·D_{\mathrm{ij}}}{{\Sigma }_{i=1}^N{\Sigma }_{j=1}^N{d}_{\mathrm{ij}}^2}---\left(14\right)$

β对于计算e_s是必须的，因为直观地，如果所有的d_ij缩放相同量，那么图像 分布的结构应该是相同的。

对于该评价的第二量度是总体的图像重叠e_o，其是显示空间中所有成对图像 重叠的总和，即，

$e_o={\Sigma }_{i-1}^N{\Sigma }_{j=1}^N\sqrt{Z_{\mathrm{ij}}}---\left(15\right)$

其中，重叠区域的面积Z_ij是可以从图像位置y_i和y_j以及图像的大小，(w_i， h_i)和(w_j，h_j)直接计算得出的。应注意，在计算图像重叠e_o之前，所有 y_i的和y_j的图像位置必须归一化以使所有图像位于缺省显示空间σ_d＝1。

参考附图，包括100个图像的第一个示例是从如图1a和1b所示的织物 图像集合均匀采样得到的。每个图像由Gabor特征表示，并且λ被设置为0.5。

图1a是说明相对于迭代次数的成本函数的值的曲线图1。它显示了在大 约70次迭代后该成本值降到稳定值。

图1b和1c是基于初始图像位置和收敛后的位置的所有100个图像的可 视化结果(visualization)。这些图像是由灰度背景上由多件图案化的织物组 成的。图1b和1c都包含了相同数量的织物图像。图1b示出了聚集在布局 空间3中心的图像，而图1c中的图像很明显在布局空间5分散得更开。这 可以从图1b和1c的布局空间的视觉比较而看出，同时注意到图1c中布局 空间的大部分面积被图像覆盖。换句话说，这些可视化结果显示了图像重叠 已经降低到一定程度，而图像的位置分布保持相当类似的程度。例如，图1b 和1c的图像7和9已保持在相同的位置，并且由参考标记11和13指示的 左显示边界附近的几个图像间的重叠已被大量减少尽管它们仍相互靠近。

在平衡图像重叠和结构保存方面，本发明的系统和方法的一个实施例与 两个现有的算法进行了定量和定性的比较，这两个现有算法为：Moghaddam 的算法(Moghaddam等人，2004)和Nguyen的算法(Nguyen和Worring，2006). 为了公平比较，对于结构保存，在这三个方法的每一个的成本函数中使用同 一E_s。在Moghaddam的方法和Nguyen的方法中，用半径为S_max/2的圆形图 像来近似每个图像。使用与上文相同的100个图像和Gabor特征。折衷参数 λ从0到1逐渐地变化。对于每个λ的值，基于每个算法收敛的结果来测量 结构错误e_s和重叠e_o。

如图2所示的结构保存和重叠之间的关系，可看出对于任何给定的结构 错误，本发明的方法总是可获得与另外两个算法相等或比另外两个算法更少 的图像重叠。另外，由本发明的方法获得的最小图像重叠(即，～2)比由 其他两方法获得的最小图像重叠(例如，分别为～4.5和～4)要少得多。这 可以从图像集的对应可视化结果(图3)得到视觉上的验证。与如图3a所示 的由Isomap获得的初始的可视化结果相比，在由Moghaddam的方法和 Nguyen的方法获得的可视化结果(图3(b)和(c))中图像重叠少得多。 然而，最少的图像重叠出现在如图3(d)所示的由本发明的方法获得的可视 化结果中。可以看出，在图3(d)中，几乎每个图像都被清晰地可视化，与 其他图像的重叠非常少。应指出，本发明的方法的实施例性能较好可能是因 为下面两个原因。

首先，每个图像的宽度和高度都被嵌入到成本函数中，这样可以更有效 地近似成对图像重叠。在前两个方法中，用圆形图像来近似每个图像。其次， 在所提出的成本函数(公式5)中，成本项-H是平滑的并且在成对距离上有 更大的影响区域。相比之下，前两个方法中用于图像重叠的成本项是分段光 滑函数，当两个图像之间没有重叠时对成对距离没有影响，这使得其很难找 到好的最小值。

使用两组1000个图像测试了该算法对于大量图像的性能。使用Gabor 特征表示织物图像而使用颜色直方图表示艺术图像。

图4a至i示出了艺术图像集在2D显示中的图像位置和对应的图像可视 化结果。在图4a所示的由Isomap获得的初始图像分布中，大部分图像被聚 集在显示中心附近而少量的图像不规则地分布在边界处。通过折衷结构保存 和图像重叠，如图4b所示，这些图像更均匀地分布而没有密的集群(strong  clusters)。如果强调减少图像重叠(即，λ＝1)，那么如图4所示图像与其相 邻图像相隔更均匀。

在图4d、4f和4h中所示的对应的图像可视化结果显示了当放松对结构 保存的要求时，相似的图像位置仍相互靠近。在该黑白版本的图像中，附图 标记21a-c、23a-c、25a-c和27a-c代表了不同的着色区域。

为了说明本发明的方法在减少图像重叠方面的效果，在显示中心附近的 一个图像周围放大了这三个分布，然后对应的可视化结果被显示在图4e、4g 和4i中。注意，通过缩放操作对图像的位置进行缩放，但图像本身并没有被 缩放。图4(e)、(g)和(i)清楚地显示了通过本发明的方法可以有效地减少 图像重叠。

在图像浏览方面，本发明可为用户提供一种在大量图像上放大的有效方 式以便查看图像细节且只有较少的图像重叠。

图5示出了织物图像的图像位置和对应的图像可视化结果，以及在显示 中心附近的一个图像周围的、通过在所选择的图像周围缩放该图像位置的坐 标所产生的放大的可视化结果。对于艺术图像可以进行如上的类似观察。这 里，根据纹理特征而不是颜色特征来分布图像。从图5d、5f和5h，可以看 出在用附图标记31a至c、33a至c和35a至c标识的区域中，图像纹理的粗 糙度在显示空间中从顶部至底部平滑地改变。纹理的光滑变化可有助于用户 浏览大量的图像并且用特定的纹理信息来找到感兴趣的图像。图5e、g和i 清楚地显示了通过本发明的方法可以有效地减少图像重叠。

所有上述的实验结果均是在当γ＝0时获得的。图6示出了通过设置γ＝10 (这足以限制所有图像位置在布局区域中)的艺术图像的图像位置和对应的 图像可视化结果。与图4h和5h相比，其显示了图像布局在整个布局空间更 分散，从而减少了图像重叠。

图7是又一个示例，其中根据图像位置可视化了10个织物样品。图7a 是使用本发明的可视化结果，图7b是使用Isomap的可视化结果，图7c使 用Moghaddam等人的技术，而图7d使用了Nauyen等人的技术。使用本发 明获得的可视化结果与使用如图7b、7c和7d所示的已有技术产生的可视化 结果相比几乎没有图像重叠。

此处描述的高熵布局法(HELD)产生项目的布局，其符合可用的布局 区域、接近高维数据分布并且产生所的用项目均匀地填充的显示。采用项目 以便在低维布局空间形成分布。惩罚具有低熵的分布，因为它们导致了布局 被多度填充而使其他区域被稀疏地填充或空白。

一方面，本发明描述了基于内容可视化图像集合的构想，组合现有的基 于流形的学习方法与Reyi熵来创建以更有效的计算方式来安排图像的系统 和方法，其中在图形用户接口上显示的图像被更好地分配和组织以便帮助用 户从在屏幕上显示的那些图像中选择一个或多个项目。此外，可以用熵的近 似，其包含在小邻近区域上的成对测量以便提高该系统和方法的有效性。

在这种情况下，下列公式表示只在近邻的每个图像上求和的特定情形。 图像i的近邻集合由F(i)表示，

$H=-\log \left\{\frac{1}{N^2}{\Sigma }_{i=1}^N{\Sigma }_{j\in F\left(i\right)}^{N}G(y_i-y_j,{\Sigma }_i+{\Sigma }_j)\right\}---\left(16\right)$

近似法提供了在减少计算消耗和保持准确之间的良好的折衷。将要被包含在 协方差矩阵中的最近邻集合，特别是每个图像中心的3σ_i之内的那些近邻。

${\Sigma }_i=\left(\begin{array}{cc}{\sigma }_i^2& 0\\ 0& {\left({\mathrm{a\sigma }}_i\right)}^2\end{array}\right)---\left(17\right)$

其中，a是如先前所述的图像的长宽比，最小化Renyi的二次熵将最小化布 局空间中空白空间，并且将最小化图像重叠。

图8考察了进行近似对计算时间和准确性的影响。使用近似和不使用近 似安排500个织物图像的集合并且对结果进行比较。图8a和8b分别显示了 当优化500个图像的布局时每次迭代的时间曲线和所获得的图像近似的准确 度曲线。图8c显示了随布局中图像数量变化的平均计算时间的曲线图，并 表明了改善的缩放。图8d显示了使用本发明的近似所获得的100个图像的 布局。尽管近似可以说是产生了稍微差的布局，但它好于由现有已知的竞争 者产品所产生的布局，而且使用了较少的计算能力。

为了研究在优化期间步骤大小α的作用，将本发明的方法应用于1000 个艺术图像，其中λ＝1.0和γ＝1.0。每个图像是由颜色直方图表示的，并且 公式5的函数f(y_i)是从y_i到布局区域R的欧式距离的平方。

图9示出了在步骤大小上没有阈值τ(第一列)和具有阈值τ＝0.05(第 二列)的几次迭代中图像位置的变化。当没有使用阀值时，第一次迭代中大 量图像位置突然改变，这导致了图像互相“跳过(jump over)”对方和结构 的重大损失。相比而言，当τ＝0.05时，最初图像位置中的变化是有限的；最 大的移动是可从右手侧观察的边远的图像的移动。之后，布局的密集的中心 部分发散。在这两种情形下，如图9c所示，所产生的位置分布是相似的。 控制步骤大小使得使用共轭梯度下降而不损失结构成为可能。这是本发明的 一个重要方面，因为如果没有它将会获得较差的可视化结果。

此外，阈值τ的使用使该优化对大范围的γ(例如，0.1到100)和不同类 型的函数f(y_i)(即从y_i到R的欧式距离的线性以及平方)不敏感。

执行了进一步的实验来比较当图像的数量相对于可用的布局区域相对 大时展开图像的能力。

1000个图像的集合被自动安排在颜色直方图上。在用Isomap初始化后， λ被设置为1以便尽可能地在布局区域展开这些图像。图10显示了所得到的 1000个图像的位置。依照本发明(图10a)的系统产生了图像的最均匀的分 布以及布局区域上基本上稳定的图像密度。基于Moghaddam等人的结果显 示了一个紧密的集群(tight cluster)(图10b)。并且图10c中Nguyen等人的 结果显示了尽管图像密度变化很大但更均匀地展开。

图11a至11d示出了关于图10中所描述的技术的性能上变化的简化解 释。在这个示例中，宽度w＝1.0的4个正方形图像被安排在宽为2.0且高为 1.0的矩形区域中。其中两个图像位置是固定的，以便它们可以一起填充该 区域。该布局区域的左下角是原点，因此这些图像具有横坐标0.5和1.5。另 外两个图像在这两个固定的图像之间反对称地移动，使得当其中一个在u (0.5≤u≤1.5)处时，另一个在2.0处。图11a示出了对于u的三个值的该实 验的示意图。图11b至11d显示了重叠成本项的值。当这4个图像以使得任 何图像和其最邻近图像之间的距离都进似地相同的方式放置时使用本发明 的重叠成本被最小化。图11b、图11c显示了当这两个可移动的图像直接位 于那两个固定的图像上时，Moghaddam等人的方法的重叠成本被最小化。 图11d显示了当这两个可移动的图像互相只有稍微重叠时，Nguyen等人的 方法的重叠成本被最小化。

图12显示了使用本发明和已有的Isomap技术的基于颜色直方图的1000 个图像的可视化结果。参数γ被设置为10并且该方法每次迭代大约花10秒 (没有邻近近似)。在由Isomap得到的初始分布(图12a)中，大部分图像 被聚集在布局中心周围，而少量的图像不规则地分布在边界附近。当强调熵 (λ＝1)时，图像密度变得近似稳定(图12b)。为了更好地说明这一点，将在布 局中心附近的一个图像周围的可视化结果进行放大。所得到的可视化结果如 图12c和12d所示。通过缩放操作重新调整了图像位置的比例大小但图像本 身的比例大小并没有被重新调整。

图13是显示本发明一个实施例的框图。在这个示例中，本发明包括加 载到计算机上的一系列软件模块。系统101包括优化器105，所述优化器105 处理多媒体数据103以在布局空间的布局区域中提供经优化的布局，所述经 优化的布局用于在用户的控制下在显示装置上进行呈现。

用户具有对下述的控制：在比较项目内容时使用的差异性的概念(即， 用于组织多媒体数据的概念)，和数据的内容结构的保存应该与利用可用的 布局区域的要求相折衷的程度。用户也可指定要使用的布局区域的大小和形 状。

图14更详细地显示了本发明一个实施例的优化器模块。优化器模块110 包括多个子模块。初始化器模块119例如通过应用Isomap算法来产生多媒 体数据或项目111的初始布局。搜索引擎123基于成本函数来搜索最佳布局， 所述成本函数是由三个子模块多媒体内容113、布局展开115和布局范围117 所计算的布局质量分数的组合。多媒体内容子模块113计算度量布局对内容 结构的保存程度的分数。布局展开子模块115计算度量布局的熵的分数。布 局范围子模块117计算度量对在布局区域或区域内放置项目的约束的满意程 度的分数。组合器模块121将这些分数组合为总分数，搜索引擎使用该总分 数作为布局的成本函数值。搜索引擎122应用优化方法来建议将要被评分的 布局。搜索引擎在建议布局和对布局评分的多次迭代后输出经优化的布局 125。

本发明的实施例可以作为例如一种用于在显示上安排可搜索项目(例如 数字图像或多媒体图标)的方法而存在，在这种情况下，该方法可采用加载 到计算装置上的计算机程序的形式。也可包括根据本发明的用于在显示上安 排诸如数字图像或多媒体图标的可搜索项目的系统，并且可以包括硬件和软 件的组合。应理解本发明的系统和方法可以被包含到现有的图形浏览软件和 硬件中或者与其一起使用以便以如上所述的方式来提高它们的性能。

此外，浏览器会是允许用户执行从数据库中选择项目的任务的装置。本 发明的装置或系统可包括浏览，并且浏览器能指定将要在其上显示搜索结果 的物理显示器的区域。

在使用中，浏览器可基于查询项目(在其被要求找到最接近匹配时)、 文本查询或草图查询来开始项目数据库的搜索。

此外，搜索可开始于显示上有代表性的一组项目，并因此提供对数据集 的概览。当用户开始浏览时，他们可能不太知道或不知道要寻找什么。他们 可能会寻找灵感。当他们浏览根据各种标准布置的显示时，他们可能突然遇 到感兴趣的项目，那么他们的搜索可能变得更有目标。在这种情况下，强调 的是用户通览项目空间以有效地找到感兴趣的项目。在这些情形和其他情形 下，显示项目的用户接口应该实时响应，在用户和系统之间形成闭合的交互 环。

在不脱离本发明的范围的情况下可并入改进和修改。