ВЕКТОРНЫЙ КВАНТОВАТЕЛЬ Российский патент 2020 года по МПК G06F17/10 G06T9/00 H03M7/30 

Область техники, к которой относится изобретение

Предложенная технология относится, в общем, к векторному квантователю (VQ) и, в частности, к его точности и вычислительной сложности.

Уровень техники

Существует два основных класса алгоритмов квантования, а именно: скалярные квантователи (SQ), которые поэлементно обрабатывают входной вектор, и векторные квантователи, которые производят квантование входного вектора как одно целое (все размерности вектора квантуются совместно). При заданной битовой скорости векторные квантователи превосходят скалярные квантователи, в том числе по издержкам, связанным с повышенной вычислительной сложностью и объемом памяти.

Допустим, целевой вектор для квантования имеет размерность : . Алгоритм VQ выполняет поиск в кодовой книге (СВ) размером K предварительно сохраненных кодовых векторов, имеющих размерность М . Такой поиск возвращает индекс вектора кодовой книги, который обеспечивает наилучшее совпадение на основании меры искажения. Уравнения (1-2), приведенные ниже, описывают эту операцию при условии, что критерий поиска основан на квадратичной ошибке:

(1)

(2)

Оптимальный индекс передается в детектор, и соответствующий кодовый вектор извлекается из СВ (идентичные СВ имеются как в кодере, так и в декодере) и используется для восстановления целевого вектора. СВ обычно обучается в автономном режиме и собирает статистические свойства данных. Во многих случаях простая квадратичная ошибка (смотри уравнение (2)) модифицируется с помощью весов таким образом, что:

(3)

где веса зависят от приложения. Для простоты изложения в дальнейшем описании будет использоваться только квадратичная ошибка, которая определяется из уравнения (2). Тем не менее, следует отметить, что принципы, обсужденные здесь также справедливы также в случае, когда используются более сложные критерии, такие как критерий согласно уравнению (3).

Из представленного выше описания можно сделать вывод, что точность или качество восстановленного целевого сигнала зависит от размера кодовой книги; где большая СВ приводит к более высокой точности и тем самым к более высокому качеству. Вместе с этим из уравнения (1) можно сделать вывод, что основная вычислительная сложность также относится к размеру СВ, предполагая, что размерность вектора фиксируется приложением.

Как правило, построение систем передачи аудио осуществляется с учетом ограничений на ограниченную вычислительную сложность. То есть в наихудшем случае сложность не должна превышать некоторый заданный уровень . Например, вычислительная сложность аудиокодека типично измеряется посредством взвешенного значения миллионов операций в секунду (WMOPS), но так как мы рассматриваем модуль VQ, сложность непосредственно относится к размеру пространства поиска (к размеру СВ). VQ является наиболее сложным модулем в кодеке, и, кроме того, поиск СВ (число сравнений с векторами СВ) является таким, что делает VQ таким сложным.

Если в данный момент времени система VQ должна производить квантование одного целевого вектора s, пространство K поиска необходимо оптимизировать таким образом, чтобы сложность не превышала . Некоторые методы автономной оптимизации, такие как расщепленные и многоступенчатые VQ, позволяют обеспечить некоторое уменьшение сложности (и объема хранения), принимая во внимание свойства вектора s, и требования к качеству для восстановленного вектора.

Если система VQ должна одновременно производить квантование многочисленных целевых (входных) векторов с переменным числом векторов , то методы автономной оптимизации, упомянутые выше, не способны поддерживать ограничения по сложности и качеству. В таких случаях автономная оптимизация должна находить баланс между противоречивыми требованиями, такими как а) ограничение сложности (то есть ограничение поиска), когда необходимо одновременно производить квантование большого числа входных векторов, и b) поддержание высокой точности (то есть поиск большой кодовой книги), когда необходимо производить квантование малого числа векторов, что является непростой задачей.

Раскрытие изобретения

Технология, описанная здесь, применима, например, для систем сжатия/передачи аудио и видео, которые выполняют сжатие с потерями по входному потоку, и может быть описана в ряде различных аспектов. Технология, описанная здесь, включает в себя кодовую книгу, которая разделяется на классы и сортируется, классификацию входного целевого вектора s, которая будет подвергаться квантованию в одном из упомянутых классов. Описанная здесь технология позволяет отыскивать первым класс кодовых векторов в кодовой книге, которая содержит наиболее вероятный набор кодовых векторов-кандидатов в отношении входного вектора s, из классов в кодовой книге. Таким образом, кодовый вектор с наилучшим совпадением для входного вектора s можно легко найти во время поиска, и можно уменьшить вычислительную сложность.

Согласно первому аспекту выполнен способ в отношении векторного квантователя. Способ содержит этап сравнения входного целевого вектора s с множеством центроидов, то есть опорных векторов, где каждый центроид представляет собой соответствующий класс кодовых векторов в кодовой книге. Способ дополнительно содержит этап определения начальной точки в кодовой книге для поиска, который относится к входному целевому вектору в кодовой книге, где начальная точка определяется на основании результата сравнения. Кодовые векторы в кодовой книге сортируются согласно мере искажения, отражающей расстояние между каждым кодовым кодовым вектором и центроидами. Способ позволяет отыскивать первым класс кодовых векторов в кодовой книге, которая содержит наиболее вероятный набор кодовых векторов-кандидатов в отношении входного вектора s, из классов в кодовой книге.

Согласно второму аспекту выполнен векторный квантователь, содержащий функциональные блоки, адаптированные для исполнения способа согласно первому аспекту. Векторный квантователь содержит блок сравнения, адаптированный для сравнения входного целевого вектора s с множеством центроидов, причем каждый центроид представляет собой соответствующий класс кодовых векторов в кодовой книге. Векторный квантователь дополнительно содержит блок определения, адаптированный для определения начальной точки для поиска в кодовой книге на основании результата сравнения. Кодовые векторы в кодовой книге сортируются согласно мере искажения, отражающей расстояние между каждым кодовым вектором и центроидами. Векторный квантователь позволяет отыскивать первым класс кодовых векторов, содержащих наиболее вероятные кодовые векторы-кандидаты в отношении входного вектора s, из классов в кодовой книге.

Согласно третьему аспекту выполнен кодек, который содержит векторный квантователь согласно второму аспекту.

Согласно четвертому аспекту выполнен мобильный терминал, который содержит векторный квантователь согласно второму аспекту, упомянутому выше.

Согласно пятому аспекту выполнена кодовая книга для векторного квантования, причем кодовая книга размещается таким образом, что бы кодовые векторы кодовой книги были разделены на множество классов, каждый из которых представлен центроидом, и где кодовые векторы дополнительно сортируются согласно мере искажения, отражающей их расстояния до центроидов множества классов. Кодовые векторы можно сортировать согласно, например, убыванию или увеличению значения искажения.

Согласно шестому аспекту выполнено использование кодовой книги для векторного квантования, причем кодовая книга размещается таким образом, чтобы кодовые векторы кодовой книги были разделены на множество классов, каждый из которых представлен центроидом, и где кодовые векторы дополнительно сортируются согласно мере искажения, отражающей их расстояния до центроидов множества классов. Кодовые векторы можно сортировать согласно, например, убыванию или увеличению значения искажения.

Согласно седьмому аспекту выполнена компьютерная программа, содержащая машиночитаемый код, который при запуске в блоке обработки побуждает векторный квантователь выполнять способ согласно первому аспекту.

Согласно восьмому аспекту выполнена компьютерная программа, содержащая машиночитаемый носитель и компьютерную программу согласно шестому аспекту, которая хранится на машиночитаемом носителе.

Размер области поиска в кодовой книге, в которой выполняется поиск, можно адаптировать на основании числа входных целевых векторов и ограничения максимальной сложности. Число входных целевых векторов в блоке кодирования может быть переменным. Кроме того, ограничение по максимальной сложности можно устанавливать динамическим способом. Кроме того, поиск можно выполнять в кодовой книге в определенном пространстве поиска, начиная с определенной начальной точки, где поиск дает наилучшие совпадения с входным целевым вектором s. Термин "наилучшее совпадение" означает в данном случае наиболее близкое совпадение, самое наикратчайшее расстояние в отношении меры расстояния между входным целевым вектором и вектором-кандидатом в кодовой книге, то есть наилучшее совпадение имеет кодовый вектор, который имеет наименьшее расстояние до входного целевого вектора согласно мере расстояния.

Пятый аспект может представлять собой кодек, содержащий векторный квантователь согласно второму аспекту.

Шестой аспект может представлять собой мобильный терминал, содержащий векторный квантователь второму аспекту.

Краткое описание чертежей

Ниже приводится более подробное описание предложенной технологии посредством примерных вариантов осуществления и со ссылкой на сопроводительные чертежи, на которых:

Фиг. 1а и 1b - структура упорядоченной СВ согласно решению, описанному здесь. Поиск начинается из точки 0 или точки 1 в направлении другого конца СВ.

Фиг. 2 - примерная структура СВ, использующая симметрию. Только кодовые векторы и хранятся в памяти ПЗУ.

Фиг. 3 - примерный функциональный блок для определения оптимального класса для входного вектора s путем сравнения входного вектора s с другим числом центроида , каждый из которых связан с классом в кодовой книге.

Фиг. 4 - функциональный блок для определения размера области поиска в кодовой книге на основании числа спектральных пиков, обнаруженных в текущем кадре, и, возможно, битовой скорости кодека.

Фиг. 5 - таблица, иллюстрирующая, что область поиска увеличивается при уменьшении числа пиков в кадре. В примере с 17-ю пиками (то есть с 17-ю входными векторами) поиск выполняется только в 7-битовой СВ (в этом примере ограниченным минимальным пространством поиска), но при 8 пиков или менее поиск выполняется в 8-битовой СВ (максимальное пространство поиска), поскольку это нельзя "предоставить" при минимальном ограничении сложности.

Фиг. 6а-6d - примеры различных областей поиска.

Фиг. 7 иллюстрирует сигнал, касающийся допустимой сложности , можно подавать в систему из внешнего объекта. Параметр может быть основан, например, на загрузке центрального процессора CPU или на состоянии зарядки аккумулятора.

Фиг. 8 - блок-схема последовательности операций, иллюстрирующая действие в процедуре создания кодовой книги СВ, которая будет использоваться в предложенной технологии.

Фиг. 9а-с - схема последовательности операций, иллюстрирующая действия в процедурах векторного квантования VQ согласно примерам предложенной здесь технологии.

Фиг. 10 - блок-схема, иллюстрирующая векторный квантователь согласно примеру предложенной здесь технологии.

Фиг. 11 - блок-схема, иллюстрирующая кодек, содержащий векторный квантователь согласно примеру предложенной здесь технологии.

Фиг. 12 - блок-схема, иллюстрирующая размещение для векторного квантования согласно примеру предложенной здесь технологии.

Осуществление изобретения

Как было кратко описано выше, решение, которое описывается в данном документе, относится к динамической адаптации пространства поиска VQ, при которой для любого числа целевых (входных) векторов (из расчета на блок или временной интервал) высокая точность и, таким образом, качество квантования достигается в пределах заданного ограничения сложности. То есть не должны нарушаться требования вычислительной сложностью (см. ). Это достигается за счет того, что поиск выполняется специальной классифицированной и упорядоченной СВ. Начальная точка в пространстве поиска для каждого целевого вектора базируется на процедуре классификации, и размер пространства поиска увеличивается или уменьшается, исходя из числа целевых векторов. Алгоритм VQ, описанный здесь, можно называть как "инструмент" для сжатия данных независимо от того, что данные, то есть могут быть, например, видео- и/или аудиоданными. В данном описании VQ описан в контексте аудиокодека, но концепция, описанная в данном документе, не ограничивается аудиокодеками. Например, VQ можно осуществить также с помощью видеокодеков.

Алгоритм, описанный здесь, базируется на специально разработанной CB. Некоторые варианты такой кодовой книги будут описаны более подробно ниже. Сначала будет описан основной случай, а затем будет подробно обсуждена наиболее перспективная схема. Кодовые векторы CB могут размещаться согласно решению, описанному в данном документе в автономном режиме.

Для того чтобы создать базовую версию специально разработанной преимущественной CB, кодовые векторы СВ делятся на два класса, обозначенные здесь как и (это обозначение будет использоваться для названий классов, а также для соответствующие центроидов, см. фиг. 1). Для деления данных на два класса можно использовать так называемый алгоритм K-средний (обобщенный алгоритм Ллойда). Он является известным методом, который получает на входе весь набор данных и желательный набор классов и выводит центроиды с требуемым числом классов. Например, алгоритм выводит 2 центроидных вектора в случае, если было указано необходимое число классов, равное 2. Следует отметить, что эти центроиды при использовании алгоритма K-средних представляют собой векторы одинаковой размерности в качестве векторов из набора данных, но они не принадлежат этому набору данных. То есть центроидные векторы находятся снаружи СВ и не должны совпадать с некоторыми существующими кодовыми векторами. В данном случае под "центроидом" обычно подразумевают опорный вектор, представляющий собой класс векторов.

Затем все кодовые векторы в СВ сортируются согласно мере искажения, например, как это определяется уравнением (4)

(4)

Вышеупомянутая мера искажения приводит к или предполагает большие отрицательные значения для кодовых векторов, близких к , и большие положительные значения для кодовых векторов, близких к . Кодовые векторы, которые расположены на равном расстоянии от центроидов ( и ) двух классов производят меру d искажения, которая близка к нулю. В СВ кодовые векторы упорядочиваются, например, путем увеличения меры искажения, как это иллюстрировано на фиг. 1а и b.

Каждый входной целевой вектор сравнивается с двумя центроидами (с соответствующим центроидом из двух классов) и в зависимости от результата присваивается, то есть принимается решение или определяется, что он принадлежит к классу или классу . Основываясь на этой классификации, начальная точка поиска выбирается как крайняя верхняя точка (фиг. 1а) или крайняя левая (фиг. 1b) точка 0 (когда целевой вектор принадлежит классу ), или крайняя нижняя точка (фиг. 1а) или крайняя правая (фиг. 1b) точка 1 (когда целевой вектор принадлежит классу ). Теперь размер пространства поиска должен зависеть от числа входных целевых векторов из расчета на блок или временной сегмент/интервал. Если при повторном определении пространства поиска не будет иметь размер всего СВ, но будет переменной величиной, концепцию, лежащую в основе адаптации, которая описана здесь, можно определить из уравнения (5)

(5)

Другими словами, , где "Quantizer" ("Квантователь") можно рассматривать как алгоритм, который отображает входной вектор в один из кодовых векторов.

Здесь в качестве примера VQ описывается в контексте кодека преобразования, который кодирует спектральные пики, или, строго говоря, области вокруг спектральных пиков. В контексте такого кодека входной целевой вектор может отражать спектральный пик (область) сегмента, обрабатываемого аудиосигнала. Число спектральных пиков в спектре сигнала временного сегмента, например, 30 мс, аудиосигнала зависит от спектральных свойств аудиосигнала в этом временном сегменте. Поскольку спектральные свойства аудиосигнала могут изменяться в зависимости от времени и отличаться, например, для различных типов аудиосигнала, число спектральных пиков может изменяться между различными временными сегментами и между различными аудиосигналами. Таким образом, при использовании кодера преобразования, который кодирует области спектральных пиков, число входных векторов из расчета на один блок или временной сегмент в VQ будет изменяться. В приведенных здесь примерах максимальное число входных векторов, соответствующее числу спектральных пиков во временном сегменте аудиосигнала, равно 17. Однако это число является только примером и, в общем, его не следует интерпретировать как ограничивающее решение.

Схема, описанная выше, сохраняет по существу число операций, необходимое для VQ, в узком (или почти постоянном) диапазоне, то есть когда число VQ возрастает, то есть когда число входных целевых векторов увеличивается, число операций из расчета на один VQ уменьшается (размер пространства поиска уменьшается, так как отыскивается только часть CB), поэтому требования, предъявляемые к сложности (то есть ограничения), не нарушаются. При уменьшениипространство поиска может увеличиваться не более чем до размера всей CB, что приводит к более высокой точности и, следовательно, к более высокому качеству восстановленного вектора. Точность векторного квантователя можно измерять в виде квадратичной ошибки между исходным сигналом и соответствующими восстановленными данными.

Таким образом, кодовую книгу VQ не нужно создавать для худшего сценария (то есть для максимального числа входных целевых векторов). Вместо этого, ее можно создать, например, для лучшего сценария, тем самым охватывая больше кодовых векторов, чем можно было бы найти для максимального числа входных целевых векторов в пределах ограничения L_MAX максимальной сложности. Требование к максимальной сложности будет выполняться за счет того, что объем поиска, то есть размера пространства поиска, в CB зависит от количества входных целевых векторов. Однако если это делать "вслепую", например, без CB, предложенной здесь, то качество квантования будет сильно страдать, поскольку невозможно будет узнать, где располагается вектор с "наилучшим совпадением" в CB, или располагается ли этот вектор с наилучшим совпадением в части кодовой книги, которую будут искать в случае, когда уменьшается пространство поиска. Эта задача решается с помощью особого построения кодовой книги, которая описана в данном документе. Следует отметить, что построение CB, описанное в данном документе, также полезно для приложений, где число входных векторов в расчете на один модуль кодирования является постоянным.

Примерный вариант 1 осуществления: VQ, ограниченный областями спектральных пиков

Набор целевых векторов представляет собой области спектральных пиков при аудиокодировании домена преобразования, например, коэффициенты преобразования в близлежащей области пиков MDCT. Таким образом, в данном контексте, число целевых векторов изменяется в зависимости от времени, поскольку число спектральных пиков варьируется от одного временного блока к другому.

В этом типе приложения (кодирование области пиков) целевые векторы проявляют определенную симметрию, которую можно использовать для дальнейшей оптимизации CB. Например, коэффициенты преобразования на обеих сторонах спектрального пика имеют аналогичную статистику. Если предположить, что целевые векторы расположены по центру в положении пика, симметрия, описанная выше, позволяет добавить дополнительную структуру в упорядоченную СВ, показанную на фиг. 1а и 1b. Структура такой новой, дополнительно улучшенной СВ иллюстрирована на фиг. 2. Фиг. 2 иллюстрирует СВ, где кодовые векторы левой части хранятся в памяти, такой как постоянное запоминающее устройство. Однако при этом отсутствуют кодовые векторы, предварительно сохраненные для правой стороны СВ, то есть для классов и . Кодовые векторы этих классов с зеркально отраженными версиями кодовых векторов правой стороны СВ. Таким образом, при выполнении поиска в классах C_0,flip и C_1,flip поиск выполняется по кодовым векторам левой стороны. Которые хранятся в памяти, но с элементами кодовых векторов, зеркально отраженных относительно центра, при этом кодовые векторы выражены уравнением (6)

, (6)

где - элементы вектора соответствующего класса C_j в сохраненной CB (то есть или ). То есть если элементы некоторого кодового вектора представляют собой {C₀₁ C₀₂ C₀₃ C₀₄}, элементы соответствующего кодового вектора в C_0,flip представляют собой {C₀₄ C₀₃ C₀₂ C₀₁}.

При использовании CB так, как иллюстрировано на фиг. 2, входной целевой вектор сравнивается с четырьмя центроидами и ему присваивается класс для того, чтобы определить начальную точку для поиска, то есть оптимальный класс для входного целевого вектора определяют путем сравнения входного вектора с каждым из центроидов . Это иллюстрировано на фиг. 3, где целевой вектор вводится в блок 302 назначения класса, который выдает индикатор C_j класса, в качестве выходного сигнала. Центроиды и не хранятся в таблице, но "создаются" за счет зеркального отображения элементов центроидов и . Элементы не нужно в буквальном смысле зеркально отображать, между тем модифицированная операция поиска позволяет считывать элементы и в обратном порядке при считывании C_0,flip и C_1,flip, то есть как центроидов, так и кодовых векторов. Таким образом, СВ можно увеличить так, чтобы она содержала в два раза большее количество кодовых векторов по сравнению с количеством, которое физически хранится в СВ, что означает экономию ресурсов памяти. Это становится возможным благодаря тому, что симметрия областей пиков используется так, как описано выше. Более конкретно, решение основано на том наблюдении, что можно использовать симметрию, тем самым зеркально отраженный действительный кодовый вектор является также действительным кодовым вектором.

Область поиска адаптирована к числу спектральных пиков, которое соответствует числу входных целевых векторов. Примером этому служит фиг. 4, на которой показан функциональный блок 402, в который подается в качестве входного сигнала индикатор числа пиков/векторов, и который выдает индикатор области поиска в качестве выходного сигнала. Фиг. 4 дополнительно иллюстрирует, например, что битовая скорость кодека, использующего VQ, можно также принимать во внимание при определении области поиска (пространства поиска). Например, могут существовать различные требования к качеству для различных битовых скоростей, например, чем выше битовая скорость, тем выше ожидаемое качество. Кроме того, допустимую максимальную сложность можно заменить на битовую скорость, например, поскольку на различных битовых скоростях активизируются различные модули в кодеке, которые не являются в равной степени сложными, то есть оставшаяся допустимая сложность для VQ из ограничения по максимальной сложности на всю процедуру кодирования может быть неодинаковой. То есть информация относительно битовой скорости отражает изменения в требованиях к качеству и сложности, которые можно принимать во внимание при векторном квантовании.

Таблица, приведенная на фиг. 5, иллюстрирует то, как область поиска адаптирована к числу пиков. На фиг. 5 область поиска показана в виде числа коэффициентов (кодовых векторов) в поиске из расчета на один входной вектор. Числа в таблице, приведенной на фиг. 5, получены при допущении того, что СВ, показанная на фиг. 2, содержит четыре 7-битовых сегментов (четыре сегмента с 128 кодовыми векторами в каждом), в которых два сегмента являются "нормальными" или "физическими", и два сегмента являются "зеркально отраженными" или "виртуальными".

Логика, лежащая в основе таблицы, представленной на фиг. 5, состоит в том, что когда в коде на один пик меньше, например, 16 вместо 17, "сэкономленные" 128 сравнений можно распределить среди оставшихся пиков. В некоторой точке длина поиска насыщается, так как она достигает физического размера СВ. В примере, иллюстрированном на фиг. 5, эта точка достигается тогда, когда число пиков становится равным 8 или менее. То есть в примере, иллюстрированном на фиг. 5, когда число пиков становится равным 8 или менее, полный поиск можно произвести для всех входных целевых векторов (то есть пиков) без достижения максимально допустимой сложности.

Примеры процедуры поиска иллюстрированы на фиг. 6а-d. Фактически она является тем же самым типом поиска, описанным ранее в связи с фиг. 1а-b, но с дополнительной классификацией на "нормальные" и "зеркально отражённые" сегменты/классы СВ.

В примере, показанном на фиг. 6а, входной вектор принадлежит к классу (позиция, показанная нижней стрелкой). Затем пространство поиска ограничивается до размеров между только классом и совместным пространством классов и . На фиг. 6а это проиллюстрировано тремя пунктирными стрелками, показывающими пространства поиска различных размеров. Фиг. 6b иллюстрирует случай, где входной вектор принадлежит классу (позиция показана нижней стрелкой), в случае которого поиск имеет другую начальную точку.

Аналогично, как показано на фиг. 6c-d, поиск можно выполнить в классах и/или , если входной вектор принадлежит к одному из этих классов. Поиск не выполняется в совместном пространстве и . Причина этого заключается в том, что совместное пространство регулярного или зеркально отображенного класса не соответствует реальному набору данных (их статистика не соответствует реальной статистики данных). Таким образом, маловероятно, что в таком пространстве можно найти хорошее совпадение для входного вектора.

Примерный вариант 2 осуществления: система связи с внешним управлением максимально допустимой сложностью

Концепцию VQ, имеющего сложность, которая динамически настраивается на число векторов , можно распространить на случай, когда предел сложности не является предварительно определенным, но может изменяться, например, на основании некоторого критерия и передавать сигнал в VQ и/или объект, в котором применяется VQ. Это иллюстрировано в виде блок-схемы на фиг. 7, на которой показан функциональный блок 702, принимающий в качестве входного сигнала индикатор или число пиков/векторов, и дополнительно принимающий в качестве входного сигнала ограничение L_MAX по сложности. Функциональный блок 702 выдает индикатор пространства поиска/области СВ, как показано пунктирными стрелками на фиг. 6а-d.

Представленный здесь алгоритм VQ с регулируемой сложностью обеспечивает оптимальный баланс между точностью квантования (то есть качеством) и поддержанием вычислительной сложности ниже предварительно определенного порога.

Примерная процедура для достижения структуры CB

Примерная процедура для построения или организации CB, которая будет использоваться в VQ, будет описана ниже со ссылкой на фиг. 8. Эта процедура предназначена для создания CB для использования в VQ, обеспечивающего квантование в аудиокодере преобразования, таком, например, как кодер MDCT.

Процедура, описанная ниже, относится к частям процедуры создания CB, которая отклоняется от и/или является дополнительной к традиционному критерию или организации CB VQ.

На этапе 802 CB разделяют на классы, например, используя так называемый алгоритм K-средних, как было описано ранее. Затем кодовые векторы СВ сортируются в СВ на основании меры искажения, например, как выражено уравнением (4). Мера искажения для каждого кодового вектора зависит от связи между кодовым вектором и центроидами, представляющими собой каждый класс СВ, как было описано ранее.

Эта организация CB обеспечивает адаптацию пространства поиска и, таким образом, сложность поиска в VQ с весьма высоким сохраненным качеством VQ (например, с качеством восстановленных целевых векторов).

Примерная процедура VQ

Примерная процедура, выполняемая в векторном квантователе (VQ), будет описана ниже со ссылкой на фиг. 9а. Эта процедура пригодна для использования в аудиокодере преобразования, таком как, например, кодер MDCT, кодирующий например, области спектральных пиков. Аудиосигнал может содержать, например, речь и/или музыку.

С помощью VQ принимают N входных целевых векторов, как было описано ранее. Ниже будут описаны этапы, связанные с одним из входных целевых векторов из соображения простоты.

Входной целевой вектор s сравнивается с числом кодовых векторов, каждый из которых представляет собой класс CB (смотри классы и и т.д.), описанные ранее, предпочтительно центроид каждого класса. Сравнение иллюстрировано как этап 902 на этапе 9а-с. Этап 902 можно альтернативно рассматривать как единое целое с этапом 904, иллюстрированным на фиг. 9с. В зависимости от результата сравнений, входному целевому вектору s назначается один из классов или секций СВ на этапе 904. Входной целевой вектор s назначается или принимается решение относительно того, чтобы принадлежать к классу, который имеет наикратчайшее расстояние, то есть к которому он наиболее близок, согласно некоторой мере расстояния (мере ошибки). Начальная точка поиска в СВ определяется на этапе 906 на основании назначения класса или меры расстояния.

На этапе 910 можно выполнить поиск в кодовой книге. Писк инициируется в выбранной начальной точке и выполняется во всем пространстве писка, которое может иметь определенный размер, содержащий один или более классов или их частей. Благодаря преимущественному построению и организации СВ, вероятность того, что наилучшее совпадение всех кодовых векторов-кандидатов в пределах всей СВ для входного целевого вектора s будет найдена в пределах пространства поиска, является очень высокой даже в случае, когда пространство поиска ограничено, например, половиной СВ. В случае, когда пространство поиска будет содержать всю кодовую книгу, кодовый вектор с наилучшим совпадением будет обнаружен вначале стадии поиска, то есть когда начинается поиск в определенной начальной точке.

После того как найдено наилучшее совпадение в пределах определенного пространства поиска, на этапе 912 предоставляют кодовый вектор с наилучшим совпадением в качестве результата из VQ для использования в аудиодекодере.

Кроме того, размер пространства поиска можно определить на этапе 908, показанном на фиг. 9с. Пространство поиска можно описать как число кодовых векторов в СВ, которое следует оценить во время поиска для лучшего совпадения для входного целевого вектора s. Размер пространства поиска определяется на основании числа входных целевых векторов и ограничения на вычислительную сложность L_MAX. Таким образом, размер пространства поиска можно определить, например, один раз для каждого блока кодирования, или некоторый другой временной интервал в зависимости, например, от характеристик сигнала, который будет подвергаться квантованию и/или атрибутов кодека. Если число входных целевых векторов и ограничение L_MAX ограничено или является условно постоянным с течением времени, размеры пространства поиска можно также поддерживать постоянным в течение соответствующего периода времени.

Пример размещения VQ

Ниже, со ссылкой на фиг. 10, будет описан пример размещения VQ, пригодный для использования в кодере/кодеке преобразования. Кодек преобразования может представлять собой, например, кодек MDCT. VQ адаптирован для выполнения действий процедуры, описанной выше.

VQ 1001 показан как поддерживающий связь с другими объектами (например, аудиокодеком) через блок 1002 связи. VQ дополнительно может содержать другие функциональные блоки 1016, такие как, например, функциональные блоки, обеспечивающие регулярные функции, и может дополнительно содержать один или более запоминающих устройств 1014.

VQ 1001 можно осуществить, например, с помощью процессора или микропроцессора и соответствующего программного обеспечения с подходящей памятью, программируемого логического устройства (PLD) или других электронных компонентов и/или схем.

Предполагается, что блок 1002 связи содержит функциональные блоки для получения адекватных параметров, таких как входные целевые векторы и L_MAX, подаваемые, например, из объекта кодирования.

VQ может содержать блок 1004 сравнения, который адаптирован для сравнения входного целевого вектора s с векторами, представляющими каждый класс CB, например, центроидный вектор каждого класса. Кроме того, VQ может содержать блок 1006 назначения, который адаптирован для назначения класса входному целевому вектору s (или назначения вектора s классу), то есть принимать решение, к какому классу принадлежит вектор на основании сравнения. Кроме того, VQ может содержать блок 1008 определения, адаптированный для определения адекватной начальной точки для поиска в CB на основании класса, назначенного вектору s. Блок определения можно дополнительно адаптировать для определения размера пространства поиска в CB на основании, например, числа принятых входных целевых векторов и ограничения на вычислительную сложность.

Кроме того, VQ может содержать блок 1010 поиска, который адаптирован для выполнения поиска в СВ, начиная с определенной начальной точки и отыскивая определенное пространство поиска. Поиск должен приводить к одному или нескольким индексам СВ, показывающим, какой из кодовых векторов наиболее всего совпадает со входным целевым вектором s. VQ может дополнительно содержать блок 1012 подачи индексов, который адаптирован для обеспечения подачи упомянутого индекса или индексов в другой блок, например, в (или для использования с помощью) кодек преобразования.

Пример размещения

На фиг. 12 схематично показан вариант осуществления размещения 1200, подходящий для использования, например, в аудиодекодере преобразования, который также может представлять собой альтернативный способ раскрытия варианта осуществления VQ, иллюстрированного на фиг. 5. В данном случае блок 1206 обработки содержит размещение 1200, например, с DSP (процессором цифровых сигналов). Блок 1206 обработки может представлять собой одиночный блок или множество блоков для выполнения различных этапов процедур, описанных в данном документе. Размещение 1200 может также содержать входной блок 1202 для приема сигналов, таких как входные целевые векторы и индикаторы, например, битовая скорость и/или ограничение на сложность; и, кроме того выходной блок 1204 для выходных сигналов, таких как индексы СВ для кодовых векторов с наилучшим совпадением. Входной блок 1202 и выходной блок 1204 можно выполнить как одно целое в аппаратной части размещения.

Кроме того, размещение 1200 содержит по меньшей мере один компьютерный программный продукт 1208 в виде невременной памяти, например, электрически стираемое программируемое постоянное запоминающее устройство (ЭСППЗУ), флэш-память и жесткий диск. Компьютерный программный продукт 1208 содержит компьютерную программу 1210, которая содержит кодовое средство, которое при запуске в блоке 1206 обработки в размещении 1200 побуждает размещение выполнять действия процедуры, описанной ранее в связи с фиг. 9а-с.

Следовательно, в описанных примерных вариантах осуществления кодовое средство в компьютерной программе 1210 размещения 1200 может содержать модуль 1210а сравнения для сравнения входного целевого вектора с центроидами классов СВ. Компьютерная программа может содержать модуль 1210b назначения для назначения класса входному целевому вектору. Компьютерная программа 1210 может дополнительно содержать блок 1210с определения для определения начальной точки для поиска в СВ; и, кроме того, для определения пространства поиска или области, основываясь на входных параметрах. Компьютерная программа 1210 может дополнительно содержать блок 1210d поиска для поиска СВ согласно вышеизложенному. Кроме того, компьютерная программа 1210 может содержать модуль 1210е обеспечения для обеспечения подачи индексов, которые получаются в результате поиска, в другие объекты.

Компьютерная программа 1210 находится в форме компьютерного программного кода, структурированного в виде компьютерных программных модулей. Модули 1210а-е могут по существу выполнять действия последовательности операций, иллюстрированной на любой из фиг. 9а-с для эмуляции по меньшей мере части VQ 1001, иллюстрированного на фиг. 10. Другими словами, когда различные модули 1210a-d начинают работу в блоке 1206 обработки, то они соответствуют по меньшей мере блокам 1004-1012 (фиг. 10).

Хотя кодовое средство в варианте осуществления, раскрытом выше в связи с фиг. 12, осуществлено в виде компьютерных программных модулей, которые при запуске в блоке обработке побуждают размещение и/или аудиокодер преобразования выполнять этапы, описанные выше, в связи с фигурами, упомянутыми выше, по меньшей мере одно из кодовых средств можно осуществить в виде альтернативных вариантов осуществления по меньшей мере частично в качестве аппаратных схем.

Хотя предложенная технология была описана со ссылкой на специфические примерные варианты осуществления, описание, в общем, предназначено только для иллюстрации концепции и не рассматривается как ограничивающая масштаб технологии, описанной здесь. Различные признаки примерных вариантов осуществления, описанных выше, можно объединить различными способами согласно потребности, требованиям или предпочтению.

Описанное выше решение можно использовать везде, где применяются VQ, например, в кодеках, расположенных в устройствах, таких как мобильные терминалы, планшетные компьютеры, компьютеры, смартфоны и т.д.

Следует понимать, что выбор взаимодействующих блоков и модулей, а также название блоков представлены только с целью примера, и узлы, подходящие для исполнения любого из способов, описанных выше, можно сконфигурировать многочисленными альтернативными способами для того, чтобы можно было исполнить действие предложенного процесса.

Функции различных элементов, включающих в себя функциональные блоки, включающие в себя, но неограниченные этим, обозначены или описаны как "функциональный блок", "процессор" или "контроллер", можно выполнить путем использования аппаратных средств, таких как схемные аппаратные средства и/или аппаратные средства с возможностью исполнения программного обеспечения в форме кодированных инструкций, которые хранятся на машиночитаемом носителе. Таким образом, такие функции и иллюстрированные функциональные блоки следует понимать как аппаратно-реализуемые и/или компьютерно-реализуемые и, таким образом, машинореализуемые.

С точки зрения аппаратной реализации функциональные блоки могут включать в себя или охватывать, без ограничения, аппаратные средства процессора цифровых сигналов (DSP), процессор с уменьшенным набором инструкций, аппаратную (например, цифровую или аналоговую) схему, включающую в себя, но не ограниченную этим, специализированные интегральные схемы (ASIC) и (там, где это необходимо) машины состояний, способные выполнять такие функции.

Аббревиатура

SQ - скалярное квантование

VQ - векторное квантование

CB - кодовая книга

WMOPS - взвешенное значение миллионов операций в секунду

MDCT - модифицированное дискретное косинусное преобразование.

Изобретение относится к кодеку преобразования. Технический результат - возможность одновременно производить большое число входных векторов. Для этого предусмотрено: сравнение входного целевого вектора s с множеством центроидов, причем каждый центроид представляет собой соответствующий класс кодовых векторов в кодовой книге. Кроме того, начальная точка для поиска, которая относится к входному целевому вектору в кодовой книге, определяется на основании результата сравнения. Кодовые векторы в кодовой книге сортируются согласно мере искажения, отражающей расстояние между каждым кодовым вектором и центроидами классов, при этом кодовые векторы в кодовой книге сортируются согласно мере искажения, отражающей расстояние между каждым кодовым вектором и двумя из указанного множества центроидов. Число входных целевых на блок или временной интервал является переменным, а пространство поиска динамически настраивается на число входных целевых векторов. Кодек преобразования и способ позволяют отыскивать первым класс кодовых векторов, содержащий наиболее вероятные кодовые векторы-кандидаты в отношении входного вектора s. 4 н. и 8 з.п. ф-лы, 18 ил.

1. Способ поиска кодовых векторов в кодовой книге, выполняемый кодеком (1100) преобразования, содержащим векторный квантователь, причем способ содержит этапы, на которых:

сравнивают (902) входной целевой вектор s с множеством центроидов, причем каждый центроид представляет соответствующий класс кодовых векторов в кодовой книге,

определяют (906) начальную точку для поиска, относящуюся к входному целевому вектору в кодовой книге, на основании результата сравнения,

выполняют (910) поиск в кодовой книге, начиная с определенной начальной точки, и идентифицируют кодовый вектор для представления входного целевого вектор s,

при этом кодовые векторы в кодовой книге отсортированы согласно мере искажения, отражающей расстояние между каждым кодовым вектором и двумя из указанного множества центроидов, при этом число входных целевых векторов на блок или временной интервал является переменным, а пространство поиска динамически настраивается на число входных целевых векторов.

2. Способ по п.1, в котором пространство поиска динамически настраивается посредством увеличения или уменьшения размера пространства поиска на основании числа целевых векторов.

3. Способ по п.1 или 2, в котором кодовые векторы в кодовой книге отсортированы так, что кодовые слова, ближайшие к первому центроиду C₀ и наиболее удаленные от второго центроида C₁ находятся на одной стороне кодовой книги, а кодовые слова, ближайшие к C₁ и наиболее удаленные от C₀, сгруппированы на другой стороне кодовой книги.

4. Способ по любому из пп.1-3, в котором входной целевой вектор s сравнивают с четырьмя центроидами С₀, С₁, С_0,flip и C_1,flip, причем кодовые векторы для класса С_0,flip являются зеркально отраженными вариантами кодовых векторов для класса C₀, а кодовые векторы для класса C_1,flip являются зеркально отраженными вариантами кодовых векторов для класса C₁.

5. Способ по п. 4, в котором элементы кодовых векторов c_k,flip в классе С_j,flip определяются формулой:

,

где - элементы вектора соответствующего класса C_j, M - длина кодового вектора, а k - индекс кодового вектора.

6. Кодек (1100) преобразования, содержащий векторный квантователь (1000), при этом кодек содержит:

блок (1002) связи, выполненный с возможностью получения переменного числа входных целевых векторов s на блок или временной интервал;

блок (1004) сравнения, выполненный с возможностью сравнения входного целевого вектора s с множеством центроидов, причем каждый центроид представляет собой соответствующий класс кодовых векторов в кодовой книге (1014); и

блок (1008) определения, выполненный с возможностью определения начальной точки для поиска в кодовой книге на основании результата сравнения и динамической настройки пространства поиска в соответствии с числом входных целевых векторов;

блок (1010) поиска, выполненный с возможностью выполнения поиска в кодовой книге, начиная с определенной начальной точки, и идентификации кодового вектора для представления входного целевого вектора s;

при этом кодовые векторы в кодовой книге (1014) отсортированы согласно мере искажения, отражающей расстояние между каждым кодовым вектором и двумя из указанного множества центроидов.

7. Кодек преобразования по п.6, в котором блок определения выполнен с возможностью динамической настройки пространства поиска посредством увеличения или уменьшения размера пространства поиска на основании числа целевых векторов.

8. Кодек преобразования по п.6 или 7, в котором кодовые векторы в кодовой книге отсортированы так, что кодовые слова, ближайшие к первому центроиду C₀ и наиболее удаленные от второго центроида C₁, находятся на одной стороне кодовой книги, а кодовые слова, ближайшие к C₁ и наиболее удаленные от C₀, сгруппированы на другой стороне кодовой книги.

9. Кодек преобразования по любому из пп.6-8, в котором блок (1004) сравнения выполнен с возможностью сравнения входного целевого вектора s с четырьмя центроидами С₀, С₁, С_0,flip и C_1,flip, причем кодовые векторы для класса С_0,flip являются зеркально отраженными вариантами кодовых векторов для класса C₀, а кодовые векторы для класса C_1,flip являются зеркально отраженными вариантами кодовых векторов для класса C₁.

10. Кодек преобразования по п. 9, в котором элементы кодовых векторов c_k,flip в классе С_j,flip определяются формулой:

,

где - элементы вектора соответствующего класса C_j, M - длина кодового вектора, а k - индекс кодового вектора.

11. Мобильный терминал, содержащий кодек преобразования по любому из пп.6-10.

12. Машиночитаемый носитель, хранящий компьютерную программу (1210), содержащую машиночитаемый код, который при запуске в блоке обработки вызывает выполнение векторным квантователем соответствующего способа по любому из пп.1-5.