在分層對象結構中的搜索方法
2023-05-07 05:03:21
專利名稱：在分層對象結構中的搜索方法
技術領域：
本發明涉及一種在一組對象中搜索最接近實例的對象的預定數目對象的方法。本發明還涉及包括用於實現這個搜索方法的裝置的電腦程式和設備。最後本發明涉及包括這樣設備的傳輸系統。
本發明在音頻/視頻數據的使用領域中具有很有意義的應用。
顯著地增加數據傳輸和存儲容量，以至於在包括消費電子學領域的各種領域中，用戶今後很難管理曾經供他使用的信息。在這一點上，對象搜索方法變得更加重要。
美國專利5,832,182描述了數據劃分方法並且討論了這種搜索方法的意義。有效的數據劃分允許減少為了進行搜索而進行的比較的次數，並且因此減少搜索所需的處理時間。
本發明為它的目的特別地提出了一種在各種層次上使用對象劃分的有效的對象搜索方法。
依據本發明的搜索方法特徵為，為了在一組對象中搜索最接近實例的預定數目的對象，通過使用具有包括節點和葉的樹形結構的多級劃分，節點包含表示對象類的元素，葉包含對象，上述方法包括下列步驟為了選擇一個或者多個葉，通過上述樹形結構從節點開始並且通過其代表元素最接近實例的節點到葉的步驟，檢驗被選擇的葉數是否低於上述對象的預定數的步驟，和，如果被選擇的葉數低於上述對象的預定數，則從最後通過的、最接近上述實例的節點的同級節點開始上述步驟的新的重複。
多級劃分的使用顯著地有利於進行搜索，因為它允許進一步的降低搜索所需的比較次數並且因此降低處理時間。它還允許處理比用單級劃分包括更多的對象的組。實際上，用單級劃分，當一組對象的大小顯著地增加的時候，這導致了類數的增加，或者包含在一個類中的對象數的增加。在兩種情況中，每種都導致搜索用的實例與大量的對象相比較。因此顯著地增加了處理時間。另一方面，用多級劃分，搜索用的實例在劃分的每級上只與有限的對象相比較。因此組的大小的增加在搜索的處理時間上影響很小。
本發明有利地提出通過多級劃分的樹形結構。
在本發明的優選的實施例中，對象的預定數是結果的預定數的倍數並且上述方法包括在被選擇的葉中只保留等於上述結果的預定數的葉數的附加選擇步驟，而被保留的葉是包含最接近上述實例的對象的那些。
對象的劃分導致為進行搜索而進行的比較的次數的減少。但是它也必然引起搜索結果的惡化。這個實施例允許限制這種惡化。實際上，通過首先選擇比想要的結果數更高的葉數，並且其後進行補充選擇，例如，通過包含在被選擇的葉中的對象與用於搜索的實例的徹底的比較，能夠顯著地改善所獲得的結果的質量。
一般的，本發明能夠應用於提供了為這種類型的對象定義的相似性量度的任何類型的對象，這個相似性量度是已經用於構造劃分的那個，並且它驗證3個下列條件f是聯合實數和初始組的兩個對象的應用。
以任何順序考慮這兩個對象，這個實數都相同，聯合兩個相同對象的實數高於聯合兩個不同對象的實數。
例如，通過元數據形成對象，也就是，聯合一組數據的結構。這樣的元數據，例如是視頻拍攝的描述，是很明顯的MPEG-7類型的描述。MPEG-7草圖實際上為視頻拍攝定義了確定數目的描述符(顏色描述符，文字描述符，攝像機移動描述符，。。。。。。)，並且提出聯合這些描述符的相似性量度。為了更加詳細，將參考做成文件ISO/IEC JTC1/SC29/WG11 N3521(2000年7月)，標題為《電影和相關音頻信息的代碼》，它參看了文件《可視化工作圖》版本4.0。
結合下文描述的實施例，通過非限制實例，本發明的這些和其他方面將更加明顯和清楚。
在圖中
圖1是描述劃分一組對象的方法的實例的操作的方框圖，它提供了依據本發明可以被搜索方法使用的多級劃分，圖2是依據本發明用於實現搜索方法的樹形結構的實例的圖，圖3是描述依據本發明的搜索方法的實例的操作的方框圖，圖4是依據本發明的設備的實例的圖，
圖5是依據本發明的傳輸系統的實例的圖。
在圖1中顯示了描述多級劃分方法的實例的操作的流程圖，它是為了生成依據本發明搜索方法使用的類型的多級劃分。
如圖1中所示的劃分方法包括下列步驟(SS0)定義初始劃分PZ0。這個劃分包括一個包含組X的全部對象的類C0，0。(SS1)為包含多於一個對象的劃分PZj-1的每一級Cj-1，k(k＝1，。。。Qj-1)生成一個劃分PZj。這個劃分包括Qj級Cj，1，Cj，2，。。。，Cj，Qj。(SS2)為劃分PZj的每一級Cj，1，Cj，2，。。。，Cj，Qj確定代表元素Rj，1，Rj，2，。。。，Rj，Qj。(SS3)這些代表元素存儲在這種類型的樹形結構TR中，其中每個代表元素Rj，1，Rj，2，。。。，Rj，Qj是類Cj-1，k的代表元素的子集。(SS4)重複(SS1)，(SS2)和(SS3)直到劃分PZj驗證了預定標準。(SS5)當驗證預定標準的時候，存儲類Cj，1，Cj，2，。。。，Cj，Qj的對象以便於分別形成節點Rj，1，Rj，2，。。。，Rj，Qj的葉。
在步驟(SS1)中可以使用例如在文章《有效的K方法集群算法》中描述的《K方法》類型的劃分方法，文章《有效的K方法集群算法》由K.Alsabti、S.Ranka和V.Singh在《IPPS/SPDP工作組高性能數據提煉，1998，Orlando Florida》上發表。同樣可以使用例如在引用的美國專利中介紹的通過結塊分層劃分方法，或者也可以是兩種方法的組合，用於初始化《K方法》方法的部分結塊方法。
類的代表元素例如是類的質心。為了確定類的質心，首先計算與類的所有元素都相似的虛擬元素。利用最接近虛擬元素的類的元素來形成質心。
當每類的對象數可能最接近最大值的時候，或者包含在劃分PZj的類中的對象充分地接近類的質心的時候，終止多級劃分方法(也就是，驗證了考慮過的預定條件)。
在圖2中顯示了用多級劃分方法獲得的並且可以用於實現依據本發明的搜索方法的樹形結構TR的實例。樹的節點表示成虛線。它們包含表示對象組的類的元素。樹的葉表示成實線。它們包含X組的對象x1，x2，。。。，xN。
圖3顯示了描述依據本發明的搜索方法的實例的操作的方框圖，實例用於在樹形結構Y中選擇預定數對象N。依據圖3，依據本發明的搜索方法包括下列步驟
(T0)初始化指示保留被選擇的葉數的變量NBO。它的初始值等於被選擇對象的預定數，NBO＝n。
(T1)確定依賴於當前節點n的葉數NBL(n)。依賴於節點的葉是這個節點的葉以及依賴這個節點的節點的葉。
(T2)比較依賴當前節點NBL(n)的葉數和保留被選擇的葉數NBO。
(T3)如果它們相同(NBL(n)＝NBO)，則選擇依賴當前節點n的葉(在圖3中這個選擇操作用S(n，xk)表示)。並且終止方法。
(T4.0)如果葉數NBL(n)低於保持被選擇的葉數(NBL(n)＜NBO)，則選擇依賴當前節點n的葉(S(n，xk))。
(T4.1)從保留被選擇的當前葉數中減去葉數NBL(n)，並用它更新指示保留被選擇的葉數的變量NBONBO＝NBO-NBL(n)。
(T4.2)表示為NTEB(n)的最接近實例的當前結點的同級節點成為新的當前結點n＝NTEB(n)，並且重複步驟(T1)。
(T5)如果葉數NBL(n)大於保留被選擇的葉數(NBL(n)＞NBO)，表示為NTEC(n)的最接近實例的當前結點的子節點成為新的當前結點n＝NTEC(n)，並且重複步驟(T1)。
有利地，被選擇的對象數NBO被設置成等於用戶想要的結果數NBR的倍數NBO＝aNBR。在這樣的情況下，依據本發明的搜索方法包括附加步驟(T6)，它用於從被選擇的aNBR對象中只保留最接近被搜索的實例的NBR對象。例如，在步驟(T6)中進行的這個附加選擇由包含在被選擇葉中的aNBR對象和被搜索的實例的系統比較組成。
通過利用依賴所關心的對象類型的相似性量度f來評價兩個對象的相似性，這種相似性量度已經用於建立樹形結構，並且滿足下列三個條件f是聯合實數與初始組的兩個對象的應用。
以任何順序考慮這兩個對象，這個實數都相同。
聯合兩個相同對象的實數高於聯合兩個不同對象的實數。
通過使用在MPEG-7標準的草圖中提出的關聯的相似性量度，本發明可以顯著地應用到在MPEG-7標準的草圖中定義的描述實例的對象。
圖4顯示依據本發明的設備的實例。這個設備是包括視頻捕獲裝置2(例如CCD類型)的攝像機1。攝像機1還包括用於存儲數據的存儲器3和用於存儲電腦程式的存儲器4，用於執行上述程序的微處理器部件5，和用於接收由用戶給定的命令和用於給用戶提供數據的用戶接口6。存儲器4顯著地包括用於編碼捕獲的視頻的一個或者多個程序的一組PG1。這組程序PG1特別陳述了存儲在存儲器3中的MPEG-7視頻拍攝的描述。存儲器4還包括由各種上述MPEG-7描述形成的一組多級劃分方法PG2，用於在包含上述描述的樹形結構中搜索的依據本發明的搜索程序PG4。
在圖5中顯示了依據本發明的傳輸系統的實例的圖。這個系統包括數據源10，用戶設備20和用於在數據源10和用戶設備20之間傳輸信號的媒體30。數據源10，例如，是視頻數據源。例如，通過電纜網、通過衛星、無線電通信線路的傳輸網絡等形成給用戶設備傳輸這些視頻信號的傳輸媒體。用戶設備包括特別用於接收由源10傳輸的數據的接收電路100，用於存儲數據特別是接收數據的存儲器110，包括電腦程式的存儲器120，用於執行上述程序的微處理器部件140，和用於接收由用戶給定的命令並且給用戶提供數據的用戶接口160。存儲器120特別包括用於根據接收的視頻數據來合計有關視頻拍攝的MPEG-7描述的對象資料庫的程序PG5。它還包含包括這個資料庫的對象的一組多級劃分的程序PG2，和用於依據本發明在包含上述描述的樹形結構中搜索對象的程序PG4。
權利要求
1.在一組對象中搜索最接近實例的對象的預定數的方法，通過使用具有包括節點和葉的樹形結構的多級劃分，節點包含表示對象類的元素，葉包含對象，上述方法包括以重複的方式執行下列步驟為了選擇一個或者多個葉，從節點開始通過上述樹形結構並且通過其代表元素最接近實例的節點來轉到葉的步驟，檢測被選擇的葉數是否低於上述的對象預定數的步驟，和，如果被選擇的葉數低於上述對象預定數，從最後通過的、最接近上述實例的節點的同級節點開始上述步驟的新的重複。
2.如權利要求1中所述的搜索方法，特徵為對象的預定數是結果的預定數的倍數，方法包括用於從被選擇的葉中只保留等於上述結果的預定數的葉數的附加選擇步驟，被保留的葉是包含最接近上述實例的對象的那些。
3.如權利要求1中所述的搜索方法，特徵為通過樹形結構的步驟包括如果連接到這個節點的葉數低於或者等於被選擇的對象數則為每個通過的節點進行驗證的測試，在這種情況下連接到這個節點的葉數直接被選擇而不必通過任何可能的中間節點。
4.如在權利要求1或者2的一個中所述的搜索方法，特徵為上述對象是視頻拍攝的描述。
5.如在權利要求1或者2的一個中所述的搜索方法，特徵為上述對象是MPEG-7描述。
6.如權利要求1中所述的搜索方法，特徵為通過使用相似性量度f來確定代表元素或者對象對所搜索的實例的相似性，f是已經用於構造所用的劃分的那一個並且驗證了下列屬性f是聯合實數和初始組的兩個數據的應用。無論兩個數據是任何順序，實數都相同，聯合兩個相同數據的實數高於聯合兩個不同數據的實數。
7.包括用於實現如在權利要求1或者2的一個中所述的搜索方法的指令的程序，當通過處理器來執行它的時候。
8.包括用於實現如在權利要求1或者2的一個中所述的搜索方法的裝置的設備。
9.至少包括如在權利要求8中所述的設備的傳輸系統。
全文摘要
本發明涉及在通過使用分層對象分類方法而獲得的分層對象結構中搜索最接近實例的預定數對象的方法。所提出的方法由從根部開始通過分層結構,下降直到最接近葉數低於所依賴的缺少的結果數的被搜索的實例的第一個節點,然後返回直到最接近被搜索實例的這個節點的同級節點,以便於增加其他結果等直到達到上述預定數來組成。
文檔編號G06F17/30GK1356655SQ0114563
公開日2002年7月3日 申請日期2001年11月24日 優先權日2000年11月28日
發明者B·莫裡, N·桑蒂尼 申請人:皇家菲利浦電子有限公司