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

有效

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

1.一種方法，包括：

使用碼書C中經排序的碼矢量來搜索輸入矢量的最佳匹配矢量，其中基于所述碼矢量的分量k來對所述碼矢量進行排序，其中所述搜索包括：

執行僅考慮所述輸入矢量的分量k的二分搜索；以及

執行考慮全碼矢量的修改的部分失真搜索。

2.根據權利要求1所述的方法，其中以升序對所述碼矢量進行排序并且其中執行所述二分搜索找到滿足以下條件的具有最小索引j的矢量：

????????????????X_k＜C_j，k，

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

3.根據權利要求2所述的方法，其中執行所述修改的部分失真搜索包括：

執行開始于索引j-1的向下搜索；以及

執行開始于索引j的向上搜索。

4.根據權利要求3所述的方法，其中在找到以下碼矢量時終止所述向下搜索，所述碼矢量導致比提供所述最佳匹配的當時碼矢量更大的分量k的失真。

5.根據權利要求3所述的方法，其中在找到以下碼矢量時終止所述向上搜索，所述碼矢量導致比提供所述最佳匹配的當時碼矢量更大的分量k的失真。

6.根據權利要求3所述的方法，還包括：

在終止所述向上搜索和所述向下搜索兩者時選擇碼矢量作為所述最佳匹配矢量。

7.一種方法，包括：

從具有一個或多個碼矢量的碼書C中標識碼矢量的分量k；以及

允許至少部分地基于分量k來對所述碼書C中的碼矢量進行排序，從而促進使用經排序的碼矢量來搜索輸入矢量的最佳匹配矢量。

8.根據權利要求7所述的方法，其中將所述分量k標識為來自于所述碼書C的、引入最高方差的碼矢量的分量。

9.根據權利要求7所述的方法，其中允許對碼矢量進行排序包括根據分量k對所述碼書C中的碼矢量進行排序。

10.根據權利要求7所述的方法，其中允許對碼矢量進行排序包括提供映射函數以形成所述碼書C的碼矢量索引。

11.一種裝置，包括：

編碼器，被配置用于：

使用碼書C中經排序的碼矢量來搜索輸入矢量的最佳匹配矢量，其中基于所述碼矢量的分量k來對所述碼矢量進行排序，其中解碼器被配置用于通過以下操作進行搜索：

執行僅考慮所述輸入矢量的分量k的二分搜索；以及

執行考慮全碼矢量的修改的部分失真搜索。

12.根據權利要求11所述的裝置，其中以升序對所述碼矢量進行排序并且其中執行所述二分搜索找到滿足以下條件的具有最小索引j的矢量：

????????????????????X_k＜C_j，k，

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

13.根據權利要求12所述的裝置，其中執行所述修改的部分失真搜索包括：

執行開始于索引j-1的向下搜索；以及

執行開始于索引j的向上搜索。

14.根據權利要求13所述的裝置，其中在找到以下碼矢量時終止所述向下搜索，所述碼矢量導致比提供所述最佳匹配的當時碼矢量更大的分量k的失真。

15.根據權利要求13所述的裝置，其中在找到以下碼矢量時終止所述向上搜索，所述碼矢量導致比提供所述最佳匹配的當時碼矢量更大的分量k的失真。

16.根據權利要求13所述的裝置，其中所述編碼器還被配置用于：

在終止所述向上搜索和所述向下搜索兩者時選擇碼矢量作為所述最佳匹配矢量。

17.一種裝置，包括：

編碼器，被配置用于：

從具有一個或多個碼矢量的碼書C中標識碼矢量的分量k；以及

允許至少部分地基于分量k來對所述碼書C中的碼矢量進行排序，從而促進使用經排序的碼矢量來搜索輸入矢量的最佳匹配矢量。

18.根據權利要求17所述的裝置，其中將所述分量k標識為來自于所述碼書C的、引入輸入矢量的最高方差的碼矢量的分量。