[發明專利]用于針對矢量量化器的快速最近鄰搜索的方法和設備

有效

• 申請號: 200980134689.4
• 申請日: 2009-07-02
• 公開（公告）號: CN102144256A
• 公開（公告）日: 2011-08-03
• 發明（設計）人: A·瓦希拉舍;L·拉克索南;M·塔米;A·拉莫
• 申請（專利權）人: 諾基亞公司
• 主分類號: G10L19/02
• 分類號: G10L19/02;G06T9/00
• 代理公司: 北京市金杜律師事務所 11256
• 代理人: 酆迅

技術領域

本發明涉及音頻數據的編碼和解碼。特別地，本發明涉及針對矢量量化器的最近鄰快速搜索。

背景技術

本部分旨在為權利要求書中陳述的本發明提供背景或上下文。在此的描述可能包括可以探究的概念，但不一定是那些之前已經想到或者探究的概念。因此，除非在此指出，否則在本部分中描述的內容對于本申請的說明書和權利要求書而言不是現有技術，并且并不因為包括在本部分中就被認為是現有技術。

量化是有損信號壓縮的主要工具之一。量化過程包括針對給定輸入數據找到接近的表示，該表示將使得利用較少的比特對數據進行存儲和傳輸。可以將量化函數寫作f：D＞C，其中D是輸入空間并且C是表示集合或碼書。對于來自于D的給定輸入，從C選擇表示或碼書，從而在整個碼書上最小化了輸入和表示之間的給定失真測量值。找到最小化失真測量值的碼書的過程通常稱作最近鄰搜索。

如果輸入空間以及碼書是一維的，則量化稱作標量量化；否則其被稱作矢量量化。在矢量量化的情況中，表示也稱作碼矢量。

碼書Cc的基數小于輸入空間的基數，這允許以較少的比特表示輸入數據。在碼書中，最近鄰碼字的索引可以表示為log₂Cc比特。如果利用同樣數量的比特來表示所有碼字，則量化率是R＝每個采樣log₂Cc/K比特，其中K是數據維度。

通常，最近鄰搜索包括針對每個碼字的失真測量值的評估，尤其對于矢量量化情況而言，從計算的觀點來看這可能是非常昂貴的。已經提出了各種快速最近鄰算法，它們基于停止評估的一個或多個條件而減少了失真評估的數量。

矢量量化是信號處理應用中廣泛使用的工具，其中應用例如是采用話音/音頻、圖像或視頻編碼的應用。

發明內容

在本發明的一個方面中，一種方法包括：從具有一個或多個碼矢量的碼書C中標識碼矢量的分量k；以及允許基于分量k來對所述碼書C中的碼矢量進行排序，從而促進使用經排序的碼矢量來搜索輸入矢量的最佳匹配矢量。

在一個實施方式中，將所述分量k標識為針對輸入矢量引入最高方差。

在一個實施方式中，允許對碼矢量進行排序包括根據分量k對所述碼書C中的碼矢量進行排序。在另一實施方式中，允許對碼矢量進行排序包括提供映射函數以形成所述碼書C的碼矢量索引。

在另一方面中，一種方法包括使用碼書C中經排序的碼矢量來搜索輸入矢量的最佳匹配矢量，其中基于所述碼矢量的分量k來對所述碼矢量進行排序，其中所述搜索包括在執行考慮所述輸入矢量的分量k的二分搜索；以及執行考慮全碼矢量的修改的部分失真搜索。可以以升序對所述碼矢量進行排序并且執行所述二分搜索可以找到滿足以下條件的具有最小索引j的矢量：

X_k＜C_j，k，

其中X是所述輸入矢量并且C’是所述經排序的碼矢量。

在一個實施方式中，執行所述修改的部分失真搜索包括執行開始于索引j-1的向下搜索；以及執行開始于索引j的向上搜索。可以在找到以下碼矢量時終止所述向下搜索，所述碼矢量導致比提供所述最佳匹配的當時(then-current)碼矢量更大的分量k的失真。可以在找到以下碼矢量時終止所述向上搜索，所述碼矢量導致比提供所述最佳匹配的當時碼矢量更大的分量k的失真。

在一個實施方式中，所述方法還包括在終止所述向上搜索和所述向下搜索兩者時選擇碼矢量作為搜索最佳匹配的輸出。

在本發明的另一方面中，一種裝置，包括解碼器，被配置用于從具有一個或多個碼矢量的碼書C中標識碼矢量的分量k，所述分量k引入輸入矢量的最高方差；以及允許基于分量k來對所述碼書C中的碼矢量進行排序，從而促進使用經排序的碼矢量來搜索輸入矢量的最佳匹配矢量。

在另一方面中，一種裝置包括解碼器，被配置用于使用碼書C中經排序的碼矢量來搜索輸入矢量的最佳匹配矢量，其中基于所述碼矢量的分量k來對所述碼矢量進行排序，其中所述解碼器被配置用于通過以下操作進行搜索：執行僅考慮所述輸入矢量的分量k的二分搜索；以及執行考慮全碼矢量的修改的部分失真搜索。

在另一方面中，一種裝置包括處理器和通信地連接至所述處理器的存儲器單元。所述存儲器單元包括用于從具有一個或多個碼矢量的碼書C中標識碼矢量的分量k的計算機代碼，所述分量k引入輸入矢量的最高方差；以及用于允許基于分量k來對所述碼書C中的碼矢量進行排序從而促進使用經排序的碼矢量來搜索輸入矢量的最佳匹配矢量的計算機代碼。