安排用於顯示的項目的系統和方法

2023-04-25 19:24:36

專利名稱：安排用於顯示的項目的系統和方法
技術領域：
本發明涉及用於安排用於顯示的項目的系統和方法，尤其，但不僅僅涉及對當使用圖像瀏覽系統時可用圖形方式顯示的圖像的查看。本發明也可用於安排能在顯示上用圖形表示的其他數字資源。
背景技術：
人類能處理大量的可視化的和多媒體的信息。然而，他們通常很難精確地定義和描述這樣的信息。例如，據估計大腦可辨別大約10000個顏色上的細微差別，而個人只能命名少量的顏色詞(大約12個)。因此，當用通常採用元數據的基於文本的搜索來搜索資料庫時，訪問圖像可能是具有挑戰性的。基於內容的索引和檢索方法給該問題提供了部分解決方案。在許多基於內容的檢索系統中的重點在於基於對查詢項的相似性概念來自動檢索相關項。例如，基於內容的圖像檢索(CBIR)可使用繪畫、照片、列印、圖畫或其他對象的所選擇的圖像的特徵來找到視覺上相似的圖像並且定位集合中的匹配，即使它們沒有與原始圖像共享元數據。瀏覽為探索式搜索提供了有效的手段並且給傳統的基於內容的檢索提供了可用的替代方法，在所述基於內容的檢索中，用戶構造文本查詢或圖像查詢。另外，當探索圖像和/或多媒體集合時，用戶意圖可能是很模糊的。他們期望系統能夠提供大量的線索和選項來指導他們的導航。圖像和/或多媒體瀏覽系統需要通過適當地布置項目的集合用於顯示來使用戶能夠看見它們(或者它們的縮略圖或圖標)。許多系統將項目分為不同的類並且簡單地將這些項目在二維顯示上布置為每個類的ID列表(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頁)。這樣的ID列表不能很好地描繪項目之間的相互關係。或者,基於 2D 映射的可視化(例如，G. Nguyen and Μ. 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. iUl^^cfllliifet) °例如，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)來測量成對相異性和執行多維標度法(MDQ以將圖像顏色和紋理特徵轉換到2D空間。當在顯示上可視化大量的項目用於瀏覽時，這些項目將重疊並且重疊的程度將傾
4向於隨著項目的數量而增加。另外，該顯示空間的區域將經常是空的。由於降維技術在映射到顯示位置時沒有考慮用於表示這些項目(例如，圖像縮略圖或圖標)的圖像的大小，這些問題將進一步被惡化。兩個非常相似的項目可能被投影到非常接近的位置以致於一個項目將與另一個項目在很大程度上重疊。為了減少重疊，在通過降維獲得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顯示上。優選地，優化器模塊包括多個子模塊。
7
優選地，優化器模塊包括初始化器模塊，其產生項目的初始布局。優選地，優化器模塊包括搜尋引擎，其基於成本函數搜索最佳布局。優選地，以由多媒體內容模塊、布局展開模塊和布局範圍模塊計算的布局質量分數的組合來計算成本函數。優選地，多媒體內容子模塊計算度量布局對內容結構的保存程度的分數。優選地，布局展開子模塊計算度量布局的熵的分數。優選地，布局範圍子模塊計算度量對在布局區域或區域內放置項目的約束的滿意程度的分數。優選地，優化器模塊還包括組合器模塊，其將這些分數組合為總分數，搜尋引擎用該總分數作為布局的成本函數值。優選地，搜尋引擎應用最優化方法來建議將要被評分的布局。優選地，搜尋引擎在建議和評分布局的多次迭代後輸出經優化的布局。


現將參考附圖僅以示例的方式來描述本發明，其中圖Ia至Ic顯示了使用根據本發明實施例的系統的示例的、項目數據的收斂，尤其是，圖1(a)顯示了對於迭代次數的成本函數值，圖1(b)和1(c)顯示了基於初始圖像位置和收斂後的位置的圖像集合的可視化結果；圖2是顯示使用本發明的方法以及現有技術替代方法即Moghaddam的方法和 Nguyen的方法的內容結構錯誤和圖像重疊之間的關係的曲線圖；圖3a至圖3d分別顯示使用Isomap、Moghaddm的方法、Nguyen的方法和本發明方法的示例的100個圖像的可視化結果；圖如至虹顯示了 1000個藝術圖像的可視化結果，其中圖3至c顯示了初始圖像位置的分布、採用結構保存和圖像重疊間折衷的位置的分布，以及僅關注減少圖像重疊的位置的分布。圖4d、4f和4h顯示了對應於圖如、4b、如中的位置的圖像集合的可視化結果， 而圖像如、4g和4i顯示了在布局中心的一個圖像周圍縮放圖像位置之後部分圖像集的可視化結果；以及圖如至51顯示了 1000個藝術圖像的可視化結果，其中圖3至c顯示了初始圖像位置的分布、採用內容結構保存和熵之間折衷的位置的分布，以及僅關注熵的位置的分布。 圖5d、4f和處顯示了對應於圖如、413、如中的位置的圖像集合的可視化結果，而圖像^5、48 和4i顯示了在布局中心的一個圖像周圍縮放圖像位置之後部分圖像集的可視化結果；圖6示出了通過限制使所有圖像的位置位於矩形布局區域內的、藝術圖像的圖像位置和相應的圖像可視化結果；圖7是織物樣本被基於圖像位置可視化的又一個示例；圖和8b分別顯示了當優化500個圖像的布局時每次迭代的時間曲線圖和所獲得的圖像近似的準確度曲線圖。圖6c顯示了隨布局中圖像數量變化的平均計算時間的曲線圖，並表明了改善的縮放比例。圖6d顯示了使用本發明的近似法所獲得的100個圖像的布局；圖9示出了在步驟大小上沒有閾值τ (第一列)和閾值τ = 0. 05的幾次迭代中
8圖像位置的變化；圖10是當圖像的數量相對於可用的布局區域相對大時比較本發明和兩個現有技術的將圖像展開的能力的三個圖的集合。圖Ila至Ild說明了對圖10有關的描述的技術的性能上的變化的簡化的解釋；圖12顯示了使用本發明和現有的Isomap技術基於顏色直方圖的1000個圖像的
可視化結果。圖13是本發明一個實施例的框圖；以及圖14顯示了根據本發明實施例的優化器模塊的示例的更詳細的框圖。
具體實施例方式本發明提供允許基於圖像內容的相似性來安排用於顯示的項目的系統、方法和瀏覽器。本發明可用於根據項目內容的特徵(例如形狀、顏色、紋理和圖案)來安排項目(例如圖像)，以使得顯示上項目間的距離與就這些特徵而言的項目間的相似性相關。該過程的第一階段是計算在布局空間的項目的布局(layout)。一旦計算出布局， 該布局可以用來呈現項目用於在諸如計算機屏幕的裝置上顯示。在任何一次不需要將所有的布局空間都映射到顯示。例如，用戶可能想詳細查看該布局的一小部分，在這種情形中， 只有位於這一小部分布局中的項目將被實際地呈現到顯示空間/窗口中。應理解術語布局、布局區域和布局空間指的是在有關項目的數據被繪製到可見的顯示圖像中之前被處理的該數據。在本發明的至少一個示例中，目的是通過如下方式「充分」利用布局空間，所述方式包括近似均勻地布置項目以便有效地使用可用的布局區域；將項目保持在可用的布局區域(例如，其可以是圓形的、矩形的或環形的)的邊界之內；以及以依賴於項目內容的方式來布置項目，通常使相似的項目互相靠近(此處稱為 「內容結構保存」)。本發明優化成本函數並且使用通過將每個項目和混合模型中的分量相關聯而在布局空間中形成的混合模型。最大化該混合模型的熵可以在布局空間中展開圖像以佔據預定布局區域。特別地，每個項目可與高斯分布相關聯，所述高斯分布具有由該項目的空間範圍確定的協方差矩陣和被有效地計算和優化的二次Renyi熵。無意於被理論所束縛，但給出至少本發明的下列實施例通過其操作的數學描述的下列說明。給定一組項目{IJ，i = 1，...，N，其具有所提取的高維特徵向量{XJ和圖像(或縮略圖或圖標)大小{SJ，關心的問題是通過折衷如下兩個要求來在布局空間的預定區域或某些區域中布置項目，所述要求如下(1)在布局空間中項目之間的距離應該取決於項目內容的相似性，和( 項目應該分散以充分利用布局區域。第一個要求可通過流形(manifold)學習來實現。通過假設項目分布於嵌入在高維空間中的低維的非線性流形，流形學習技術能被應用以檢測和發現數據流形的結構並將該流形展開到向量空間中。一旦原始的高維數據點能被如實地嵌入到較低維的向量空間，資料庫中的圖像的相對近鄰將被近似地保存在較低維的(例如，2D或3D)空間中。這被稱為內容結構保存。大量的高維項目被可視化於2D或3D空間中用於瀏覽、探索和組織。根據用於流形結構和結構保存的標準，已經提出了許多不同的流形學習技術，例如，Isomap (Tenenbaum 等人，2000)，Laplacian eigenmaps (拉普拉斯特徵映射)(Belkin 和 Niyogi，2002)，擴散映射(Nadler等人，2005)，和最大方差展開(Weinberger等，2005)。原則上，可以使用任何流形學習技術。這裡Isomap被用作示例。Isomap首先基於{XJ構造稀疏圖，其中，稀疏圖中的頂點和項目之間一一對應。通過K-最近鄰(KNN)法來構造相似項目之間的邊。每條邊被分配以權重Wij，其是這兩個鄰近項目之間的相異性。然後，獲取任何兩個項目間的最短線的(geodesic)距離的近似值Du來作為這兩個項目在該圖中對應頂點之間的最短路徑。不失一般性，{Du}是歸一化的，這使得最大值{Du}由布局區域的大小來限定。Isomap能通過最小化Es來確定在較低維的(例如，2D或3D)向量空間中的圖像位置{YJ，所述Es滿足Es=ZllZ1J^lj-Dlj)2(1)其中Clij是Ji和y」之間的歐式距離。注意，當兩個項目、和Ij在內容上相似時，這兩個項目間的距離Dij將是很小的， 並且相應地在較低維空間中這兩個項目可能將顯得彼此靠近。對於第二個要求，提出了一種從熵的角度來度量在布局區域展開的項目的質量的方法。給定低維布局區域中的圖像位置使用高斯分布G(yi; Σ 0來近似該圖像在空間中的空間分布，其中Σ 1是由項目的大小和形狀、圖像的數量和布局區域的大小來確定的。接著，可合併將要被安排在該布局區域的所有項目的高斯分布以便獲得對每個高斯分量具有相同權重的高斯混合，即，p{y) = ^YjIlGiyYji )(2)為了在布局區域R中展開項目，該布局空間中的高斯混合的熵可以被最大化。這裡建議使用Renyi的二次熵測量，而不是傳統的香農熵。高斯混合的二次Renyi熵H可以作為高斯分量之間成對測量的總和而被有效地估計(TorkkOla，2003)，即η = -logi^zf.Z；.^·-力，Σ,+Σ, )} (3)通過最大化H(或最小化-H)可以很好地使用區域R。這可以安排項目使得保持較小的空的空間以及保持較小的項目間的重疊，並且這樣項目可以更均勻地分散在該區域上。不得不折衷這兩個要求。這意味著，該問題是要最小化Ελ，Ελ = (I-A)Es-AH, (4)受到每個項目應該停留在區域R內的約束，其中λ e
是折衷參數。應該以應用相關的方式來確定λ。當λ接近於0時，重點在於保存流形結構。當λ接近於1時， 重點在於最大化熵。可以使用任何數量的已知的最優化方法來解決這個最優化問題。這裡使用懲罰函數法來懲罰R之外的項目位置。直觀地，從項目位置Yi到布局區域R的歐式距離越大，該項目的位置越差，因此懲罰值越高。以Eb表示所有圖像位置的平均懲罰成本，即，
Eb =-ΣΓ=1/(Λ·)(5)其中，f(yi)是從yi到布局區域R的歐式距離(即minyeK| y-yj )的單調增加非負函數。然後，該問題可最終轉換為最小化E，E = EA+yEb,(6)其中，γ是平衡Ελ和、的常量。可使用基於梯度的優化來找到E的(局部)最小值。自公式
(I- λ)^-γ^(7)
^y j^y j ^y j ^y 3
Kruskal (Cox and Cox, 2001)已經推導出 Es 與 Yi 的梯度
^二-^^從-。(8)
°yjJ dv
從公式(3)，能推導出H與yj的梯度
dH ^iGiyl - Σ,+Σ,)((Σ,+Σ,)—1(兄-八)} (9)
Sy1 a-其中，α=Σ i Σ jG(Yi-Yj, Σ ^ Σ ρ。對於&與71的梯度，採用離散逼近，因為鑑於布局區域的自由形式的形狀，通常很難參數化地表示函數f(yj)。在該逼近中，Eb與yi的梯度的第k個分量通過以下公式來計算的，如產+Τ"力)(10)
Sy β N<5其中δ為離散的單位比例(unit scale)，Uk是對於布局區域的第k維的基本向量。對於優化，可以通過使用Isomap算法最小化艮來很容易地獲得良好的初始項目
位置{yj。該方法不受布局區域維度的限制，也不受項目形狀的限制。然後，為了實驗上評估該方法，在下文中，認為2D布局區域和每個圖像Ii被假設為具有高度Iii和寬度Wi的矩形。 在這種情形下，協方差矩陣Σ 1是對角的，即， Σ,=
0I0ση)σ π禾口 σ
(11)
會收斂為常數函數，因此圖像布局不能有效地展開。這裡，提出了一種通過圖像大小、布局區域大小和要展開的圖像的數量來自動確定ση和Oi2的方法，即，
「 ιW. ση= ·
2 V W-Ji
_ .,^-JSf(12)
2 V w-h 其中，|R|是布局區域的面積，。和;^是要展開的所有圖像的平均寬度和平均高度。是對於每個項目的全局尺度，使得所有項目的空間分布的組合P (y)(公式2)能有
V w-h
效地覆蓋布局區域，從而將項目展開為近似地均勻分布。對於固定的布局區域R，項目的數量越多，平均的項目大小越大，全局尺度就越小。對於固定的項目集合，布局區域越大，全局尺度就越大。每一對(ση，oi2)與對應的項目大小和全局尺度是線性相關的。現參考本發明在多個圖像資料庫上的使用來描述本發明的性能，所述多個圖形資料庫包括兩個圖像資料庫，第一個圖像資料庫具有1000個來自商業檔案的織物設計的圖像而第二個資料庫包括1000個來自公共博物館收藏的藝術圖像。使用兩類特徵來表示圖像。通過在HSV顏色空間有規則地量化色彩為32個值以及量化飽和度為16個值來提取具有512格的顏色直方圖。通過執行多解析度Gabor變換，接著計算在每級圖像解析度的變換係數的方差和均值，來提取紋理特徵，給出108個紋理特徵。對於這兩類特徵，使用歐式距離來確定用於構建流形結構的最近鄰。在該測試中， 預設布局區域大小為σ,=爿=1，調整每個項目Ii的大小，使得其長度和寬度的最大值為預設值Smax = 0. 08。此外，為了將所提出的算法與已有的兩個算法進行定量和定性的比較， 在公式4中γ =0，因為在已有的算法中不使用&。在這種情形下，對於每個Σ Qil = Wi/2和σ i2 =、/2而沒有全局尺度。在該評價中，通過結構錯誤&來度量結構保存的性能，es =~Dl})2}( 13 )其中，具有最小&的歸一化因子β可以由分析計算得到，
λΝ ^-^Ν
Σ Σ d, -D11
γ ι η ^z=I ^/=1 y y β= ^n '-
(14)
Σ" Σ" diβ對於計算 是必須的，因為直觀地，如果所有的知縮放相同量，那麼圖像分布的結構應該是相同的。對於該評價的第二量度是總體的圖像重疊e。，其是顯示空間中所有成對圖像重疊的總和，即，eo =YlX^(15)其中，重疊區域的面積Zij是可以從圖像位置以及圖像的大小，Ovhi)和 (wj; hj)直接計算得出的。應注意，在計算圖像重疊e。之前，所有Yi的和y」的圖像位置必須歸一化以使所有圖像位於預設顯示空間。d= 1。參考附圖，包括100個圖像的第一個示例是從如圖Ia和Ib所示的織物圖像集合均勻採樣得到的。每個圖像由Gabor特徵表示，並且λ被設置為0.5。圖Ia是說明相對於迭代次數的成本函數的值的曲線圖1。它顯示了在大約70次迭代後該成本值降到穩定值。圖Ib和Ic是基於初始圖像位置和收斂後的位置的所有100個圖像的可視化結果 (visualization).這些圖像是由灰度背景上由多件圖案化的織物組成的。圖Ib和Ic都包含了相同數量的織物圖像。圖Ib示出了聚集在布局空間3中心的圖像，而圖Ic中的圖像很明顯在布局空間5分散得更開。這可以從圖Ib和Ic的布局空間的視覺比較而看出，同時注意到圖Ic中布局空間的大部分面積被圖像覆蓋。換句話說，這些可視化結果顯示了圖像重疊已經降低到一定程度，而圖像的位置分布保持相當類似的程度。例如，圖Ib和Ic 的圖像7和9已保持在相同的位置，並且由參考標記11和13指示的左顯示邊界附近的幾個圖像間的重疊已被大量減少儘管它們仍相互靠近。在平衡圖像重疊和結構保存方面，本發明的系統和方法的一個實施例與兩個現有的算法進行了定量和定性的比較，這兩個現有算法為=Moghaddam的算法(Moghaddam等人， 2004)和Nguyen的算法(Nguyen和Worring，2006).為了公平比較，對於結構保存，在這三個方法的每一個的成本函數中使用同一 Es。在Moghaddam的方法和Nguyen的方法中，用半徑為Smax/2的圓形圖像來近似每個圖像。使用與上文相同的100個圖像和Gabor特徵。折衷參數λ從O到1逐漸地變化。對於每個λ的值，基於每個算法收斂的結果來測量結構錯誤A和重疊e。。如圖2所示的結構保存和重疊之間的關係，可看出對於任何給定的結構錯誤，本發明的方法總是可獲得與另外兩個算法相等或比另外兩個算法更少的圖像重疊。另外，由本發明的方法獲得的最小圖像重疊(即， 2)比由其他兩方法獲得的最小圖像重疊(例如，分別為 4. 5和 4)要少得多。這可以從圖像集的對應可視化結果(圖3)得到視覺上的驗證。與如圖3a所示的由Isomap獲得的初始的可視化結果相比，在由Moghaddam的方法和Nguyen的方法獲得的可視化結果(圖3 (b)和(c))中圖像重疊少得多。然而，最少的圖像重疊出現在如圖3(d)所示的由本發明的方法獲得的可視化結果中。可以看出，在圖 3(d)中，幾乎每個圖像都被清晰地可視化，與其他圖像的重疊非常少。應指出，本發明的方法的實施例性能較好可能是因為下面兩個原因。首先，每個圖像的寬度和高度都被嵌入到成本函數中，這樣可以更有效地近似成對圖像重疊。在前兩個方法中，用圓形圖像來近似每個圖像。其次，在所提出的成本函數 (公式5)中，成本項-H是平滑的並且在成對距離上有更大的影響區域。相比之下，前兩個方法中用於圖像重疊的成本項是分段光滑函數，當兩個圖像之間沒有重疊時對成對距離沒有影響，這使得其很難找到好的最小值。使用兩組1000個圖像測試了該算法對於大量圖像的性能。使用Gabor特徵表示織物圖像而使用顏色直方圖表示藝術圖像。圖如至1示出了藝術圖像集在2D顯示中的圖像位置和對應的圖像可視化結果。 在圖如所示的由Isomap獲得的初始圖像分布中，大部分圖像被聚集在顯示中心附近而少量的圖像不規則地分布在邊界處。通過折衷結構保存和圖像重疊，如圖4b所示，這些圖像更均勻地分布而沒有密的集群(strong clusters)。如果強調減少圖像重疊(S卩，λ = 1)， 那麼如圖4所示圖像與其相鄰圖像相隔更均勻。在圖4d、4f和4h中所示的對應的圖像可視化結果顯示了當放鬆對結構保存的要求時，相似的圖像位置仍相互靠近。在該黑白版本的圖像中，附圖標記21a-C、23a-C、2fe-C 和27a_c代表了不同的著色區域。為了說明本發明的方法在減少圖像重疊方面的效果，在顯示中心附近的一個圖像周圍放大了這三個分布，然後對應的可視化結果被顯示在圖4e、4g和4i中。注意，通過縮放操作對圖像的位置進行縮放，但圖像本身並沒有被縮放。圖4(e)、(g)和(i)清楚地顯示了通過本發明的方法可以有效地減少圖像重疊。
13
在圖像瀏覽方面，本發明可為用戶提供一種在大量圖像上放大的有效方式以便查看圖像細節且只有較少的圖像重疊。圖5示出了織物圖像的圖像位置和對應的圖像可視化結果，以及在顯示中心附近的一個圖像周圍的、通過在所選擇的圖像周圍縮放該圖像位置的坐標所產生的放大的可視化結果。對於藝術圖像可以進行如上的類似觀察。這裡，根據紋理特徵而不是顏色特徵來分布圖像。從圖5d、5f和5h，可以看出在用附圖標記31a至c、33a至c和3 至c標識的區域中，圖像紋理的粗糙度在顯示空間中從頂部至底部平滑地改變。紋理的光滑變化可有助於用戶瀏覽大量的圖像並且用特定的紋理信息來找到感興趣的圖像。圖5e、g和i清楚地顯示了通過本發明的方法可以有效地減少圖像重疊。所有上述的實驗結果均是在當Y =0時獲得的。圖6示出了通過設置Y =10(這足以限制所有圖像位置在布局區域中)的藝術圖像的圖像位置和對應的圖像可視化結果。 與圖4h和證相比，其顯示了圖像布局在整個布局空間更分散，從而減少了圖像重疊。圖7是又一個示例，其中根據圖像位置可視化了 10個織物樣品。圖7a是使用本發明的可視化結果，圖7b是使用Isomap的可視化結果，圖7c使用Moghaddam等人的技術， 而圖7d使用了 Nauyen等人的技術。使用本發明獲得的可視化結果與使用如圖7b、7c和7d 所示的已有技術產生的可視化結果相比幾乎沒有圖像重疊。此處描述的高熵布局法(HELD)產生項目的布局，其符合可用的布局區域、接近高維數據分布並且產生所的用項目均勻地填充的顯示。採用項目以便在低維布局空間形成分布。懲罰具有低熵的分布，因為它們導致了布局被多度填充而使其他區域被稀疏地填充或空白。一方面，本發明描述了基於內容可視化圖像集合的構想，組合現有的基於流形的學習方法與Reyi熵來創建以更有效的計算方式來安排圖像的系統和方法，其中在圖形用戶接口上顯示的圖像被更好地分配和組織以便幫助用戶從在屏幕上顯示的那些圖像中選擇一個或多個項目。此外，可以用熵的近似，其包含在小鄰近區域上的成對測量以便提高該系統和方法的有效性。在這種情況下，下列公式表示只在近鄰的每個圖像上求和的特定情形。圖像i的近鄰集合由F(i)表示，H = -logi^z^Z^o^^· -"Σ, + Σ, )}(16)近似法提供了在減少計算消耗和保持準確之間的良好的折衷。將要被包含在協方差矩陣中的最近鄰集合，特別是每個圖像中心的3 σ i之內的那些近鄰。Σ=卜2 0 2](IV)
厶 Io (ασ,Υ)其中，a是如先前所述的圖像的長寬比，最小化Renyi的二次熵將最小化布局空間
中空白空間，並且將最小化圖像重疊。圖8考察了進行近似對計算時間和準確性的影響。使用近似和不使用近似安排 500個織物圖像的集合併且對結果進行比較。圖8a和8b分別顯示了當優化500個圖像的布局時每次迭代的時間曲線和所獲得的圖像近似的準確度曲線。圖8c顯示了隨布局中圖像數量變化的平均計算時間的曲線圖，並表明了改善的縮放。圖8d顯示了使用本發明的近
14似所獲得的100個圖像的布局。儘管近似可以說是產生了稍微差的布局，但它好於由現有已知的競爭者產品所產生的布局，而且使用了較少的計算能力。為了研究在優化期間步驟大小α的作用，將本發明的方法應用於1000個藝術圖像，其中λ =1.0和γ =1.0。每個圖像是由顏色直方圖表示的，並且公式5的函數f(yi) 是從Yi到布局區域R的歐式距離的平方。圖9示出了在步驟大小上沒有閾值τ (第一列)和具有閾值τ = 0. 05 (第二列) 的幾次迭代中圖像位置的變化。當沒有使用閥值時，第一次迭代中大量圖像位置突然改變， 這導致了圖像互相「跳過(jump over)」對方和結構的重大損失。相比而言，當τ =0.05 時，最初圖像位置中的變化是有限的；最大的移動是可從右手側觀察的邊遠的圖像的移動。 之後，布局的密集的中心部分發散。在這兩種情形下，如圖9c所示，所產生的位置分布是相似的。控制步驟大小使得使用共軛梯度下降而不損失結構成為可能。這是本發明的一個重要方面，因為如果沒有它將會獲得較差的可視化結果。此夕卜，閾值τ的使用使該優化對大範圍的Y (例如，0. 1到100)和不同類型的函數f (Yi)(即從Ii到R的歐式距離的線性以及平方)不敏感。執行了進一步的實驗來比較當圖像的數量相對於可用的布局區域相對大時展開圖像的能力。1000個圖像的集合被自動安排在顏色直方圖上。在用Isomap初始化後，λ被設置為1以便儘可能地在布局區域展開這些圖像。圖10顯示了所得到的1000個圖像的位置。 依照本發明(圖IOa)的系統產生了圖像的最均勻的分布以及布局區域上基本上穩定的圖像密度。基於Moghaddam等人的結果顯示了一個緊密的集群(tight cluster)(圖10b)。 並且圖IOc中Nguyen等人的結果顯示了儘管圖像密度變化很大但更均勻地展開。圖Ila至Ild示出了關於圖10中所描述的技術的性能上變化的簡化解釋。在這個示例中，寬度w = 1. 0的4個正方形圖像被安排在寬為2. 0且高為1. 0的矩形區域中。其中兩個圖像位置是固定的，以便它們可以一起填充該區域。該布局區域的左下角是原點，因此這些圖像具有橫坐標0. 5和1. 5。另外兩個圖像在這兩個固定的圖像之間反對稱地移動，使得當其中一個在u(0. 彡1.5)處時，另一個在2.0處。圖Ila示出了對於u的三個值的該實驗的示意圖。圖lib至Ild顯示了重疊成本項的值。當這4個圖像以使得任何圖像和其最鄰近圖像之間的距離都進似地相同的方式放置時使用本發明的重疊成本被最小化。 圖lib、圖Ilc顯示了當這兩個可移動的圖像直接位於那兩個固定的圖像上時，Moghaddam 等人的方法的重疊成本被最小化。圖Ild顯示了當這兩個可移動的圖像互相只有稍微重疊時，Nguyen等人的方法的重疊成本被最小化。圖12顯示了使用本發明和已有的Isomap技術的基於顏色直方圖的1000個圖像的可視化結果。參數Y被設置為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。本發明的實施例可以作為例如一種用於在顯示上安排可搜索項目(例如數字圖像或多媒體圖標)的方法而存在，在這種情況下，該方法可採用加載到計算裝置上的電腦程式的形式。也可包括根據本發明的用於在顯示上安排諸如數字圖像或多媒體圖標的可搜索項目的系統，並且可以包括硬體和軟體的組合。應理解本發明的系統和方法可以被包含到現有的圖形瀏覽軟體和硬體中或者與其一起使用以便以如上所述的方式來提高它們的性能。此外，瀏覽器會是允許用戶執行從資料庫中選擇項目的任務的裝置。本發明的裝置或系統可包括瀏覽，並且瀏覽器能指定將要在其上顯示搜索結果的物理顯示器的區域。在使用中，瀏覽器可基於查詢項目(在其被要求找到最接近匹配時)、文本查詢或草圖查詢來開始項目資料庫的搜索。此外，搜索可開始於顯示上有代表性的一組項目，並因此提供對數據集的概覽。當用戶開始瀏覽時，他們可能不太知道或不知道要尋找什麼。他們可能會尋找靈感。當他們瀏覽根據各種標準布置的顯示時，他們可能突然遇到感興趣的項目，那麼他們的搜索可能變得更有目標。在這種情況下，強調的是用戶通覽項目空間以有效地找到感興趣的項目。在這些情形和其他情形下，顯示項目的用戶接口應該實時響應，在用戶和系統之間形成閉合的交互環。在不脫離本發明的範圍的情況下可併入改進和修改。
權利要求
1.一種安排用於顯示的諸如數字圖像或多媒體圖標的可搜索項目的系統，所述系統包括優化器模塊，其最小化用於在布局空間安排項目的成本函數，所述成本函數被應用於所述項目的一個或多個預定的特性；通過將每個項目視為具有在布局空間中的空間分布來創建混合分布；以及控制混合分布的熵以便最大化每個項目佔據布局空間中單獨位置的程度； 呈現器模塊，用於將這樣產生的布局呈現到顯示。
2.根據權利要求1所述的系統，其中，成本函數懲罰低熵混合分布，並對布局空間中的在其中項目間的距離取決於項目內容的相似性的布局進行獎勵。
3.根據前面任一權利要求所述的系統，其中，布局空間包括在其中包含項目的一個或多個布局區域。
4.根據前面任一權利要求所述的系統，其中，布局空間中每個項目的空間分布是高斯分布。
5.根據權利要求4所述的系統，其中，空間分布是高斯混合分布。
6.根據權利要求5所述的系統，其中，混合分布對每個高斯分量具有相同的權重。
7.根據前面任一權利要求所述的系統，其中，基於內容的相似性來布置項目。
8.根據前面任一權利要求所述的系統，其中，所述預定特性是描述諸如顏色、紋理和/ 或形狀的方面的特徵。
9.根據前面任一權利要求所述的系統，其中，每個項目的縮略圖或圖標的大小和形狀信息可被嵌入到成本函數中。
10.根據前面任一權利要求所述的系統，其中，所述熵是二次Renyi熵。
11.根據權利要求11所述的系統，其中使用Renyi熵的成對公式。
12.根據前面任一權利要求所述的系統，其中，處理項目的步驟包括；假定項目分布在數據流形上；確定所述數據流形的結構；以及應用流形學習技術來將項目映射到低維布局空間以便近似地保存項目的內容結構。
13.根據前面任一權利要求所述的系統，其中，成本函數還進一步適用於折衷布局空間中項目的內容結構保存和所述熵。
14.根據權利要求13所述的系統，其中，控制該折衷的參數是用戶定義的。有利地，這將允許用戶對內容結構保存和布局熵的折衷進行實驗。
15.根據前面任一權利要求所述的系統，其中，項目以2-D方式被安排顯示上。
16.根據權利要求1-14所述的系統，其中，放置項目以便在2-D顯示上給出3-D安排的外觀。
17.根據權利要求1-14所述的系統，其中，項目以3-D方式安排在3-D顯示上。
18.根據前面任一權利要求所述的系統，其中，該顯示包括可以是一個顯示的一部分的顯示空間使得項目在顯示空間之內展開。
19.根據前面任一權利要求所述的系統，其中，項目是圖像或其縮略圖。
20.根據權利要求1-18所述的系統，其中，項目是諸如音頻或視頻剪輯的多媒體項目的圖標。
21.根據前面任一權利要求所述的系統，其中，優化器模塊包括多個子模塊。
22.根據前面任一權利要求所述的系統，其中，優化器模塊包括初始化器模塊，其產生項目的初始布局。
23.根據前面任一權利要求所述的系統，其中，優化器模塊包括搜尋引擎，其基於成本函數搜索最佳布局。
24.根據前面任一權利要求所述的系統，其中，以由多媒體內容模塊、布局展開模塊和布局範圍模塊計算的布局質量分數的組合來計算成本函數。
25.根據權利要求M所述的系統，其中，多媒體內容子模塊計算度量布局對內容結構的保存程度的分數。
26.根據權利要求M所述的系統，其中，布局展開子模塊計算度量布局的熵的分數。
27.根據權利要求M所述的系統，其中，布局範圍子模塊計算度量對在布局區域或區域內放置項目的約束的滿意程度的分數。
28.根據權利要求23所述的系統，其中，優化器模塊還包括組合器模塊，其將這些分數組合為總分數，搜尋引擎用該總分數作為布局的成本函數值。
29.根據權利要求觀所述的系統，其中，搜尋引擎應用最優化方法來建議將要被評分的布局。
30.根據權利要求觀或四所述的系統，其中，搜尋引擎在建議和評分布局的多次迭代後輸出經優化的布局。
31.瀏覽器包括具有顯示的用戶接口；適於運行用於在顯示屏幕上安排諸如數字圖像或多媒體圖標的可搜索項目的計算機軟體的計算裝置，所述計算機軟體包括如權利要求1至30的任何一個所述的優化器模塊；以及將這樣產生的布局呈現到顯示的呈現器模塊。
全文摘要
一種安排諸如數字圖像或多媒體圖標的可搜索項目以用於在圖形用戶接口上展示的系統。該系統具有優化器模塊，其最小化用於在布局空間安排項目的成本函數並被應用於項目的一個或多個預定的特性。優化器模塊還通過將每個項目視為具有在布局空間中的空間分布來創建混合分布，以及控制混合分布的熵以便最大化每個項目在布局空間中佔用一個單獨位置的程度。然後，繪製器模塊繪製布局以產生顯示。
文檔編號G06F17/30GK102395963SQ201080014891
公開日2012年3月28日 申請日期2010年1月28日 優先權日2009年1月28日
發明者R·王, S·麥克肯納 申請人:敦提大學