СПОСОБ СОЗДАНИЯ КОДОВОЙ КНИГИ И ПОИСКА В НЕЙ ПРИ ВЕКТОРНОМ КВАНТОВАНИИ ДАННЫХ
METHOD OF CREATING CODEBOOK AND SEARCH THEREIN DURING VECTOR QUANTISATION OF DATA

Изобретение относится к области цифровой связи, а именно к методам сокращения объема данных при их обработке. Предлагаемый способ может быть использован для уменьшения затрат вычислительных ресурсов и требуемого объема запоминающих устройств при создании кодовых книг и реализации алгоритмов поиска опорных векторов в них, в том числе при осуществлении низкоскоростного кодирования речевых сигналов.
Векторное квантование требует достаточно большого числа операций при формировании кодовых книг и осуществления поиска векторов в них, что приводит к высокой вычислительной сложности данных процедур, особенно при больших объемах обрабатываемой информации. Следовательно, уменьшение количества вычислительных операций при поиске вектора в кодовой книге является актуальной задачей.
Известны способы векторного квантования для осуществления процедуры кодирования речи [Макхоул Д., Рукос С., Гиш Г. Векторное квантование при кодировании речи. // ТИИЭР. - 1985. - Т.73. - №11. - С.19-61], [V. Ramasubramanian and Kuldip К. Paliwal «Fast Nearest-Neighbor Search Based on Voronoi Projections and Its Application to Vector Quantization Encoding» in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, vol. 1, no. 2, March 1999]. Также известен способ создания кодовой книги и поиска в глубину, представленный в патенте RU 2175454 С2, в котором предлагается древовидная структура с определенным, заранее заданным количеством уровней. Данный способ характеризуется большей вычислительной сложностью, поскольку использует вероятностные методы для осуществления процедуры нахождения опорного вектора-центроида в каждой ячейке кодовой книги. В патенте RU 2391715 С2 описан принцип многомерного векторного квантования с применением многоуровневых кодовых книг. Недостатком данного способа являются требования к наличию достаточно большого объема памяти, необходимой для хранения таблиц координат опорных векторов-центроидов.
Наиболее близким по технической сущности к заявленному способу является метод, рассмотренный в патенте US 6161086, в котором при векторном квантовании данных при линейном предсказании речевого сигнала для формирования сигнала возбуждения синтезирующего фильтра используют объединенную кодовую книгу, состоящую из фиксированной и адаптивной кодовых книг, причем коррекция адаптивной кодовой книги производится при помощи инверсной процедуры BIFT (Backward and Inverse Filtered Target) на трех уровнях адаптивной кодовой книги. Фиксированная кодовая книга содержит стохастический компонент сигнала возбуждения, который отображает невокализованную составляющую. Адаптивная кодовая книга формируется на основе тонового компонента сигнала возбуждения и отображает наличие долговременных корреляционных связей за счет вокализованной структуры речевого сигнала и несет информацию о количестве отсчетов, соответствующем периоду основного тона анализируемого кадра речи.
Нахождение опорных векторов осуществляется с использованием древовидной структуры поиска ближайшего вектора в кодовой книге, что требует большой вычислительной сложности.
Недостатком прототипа является достаточно большое количество памяти, необходимой для хранения таблицы координат опорных векторов, а также высокая вычислительная сложность для осуществления данной операции.
Задачей изобретения является создание кодовой книги и поиска в ней при векторном квантовании, позволяющее уменьшить объем запоминающих устройств и вычислительную сложность при осуществлении процедуры поиска в кодовой книге.
Эта задача решается тем, что при создании кодовой книги и поиска в ней при векторном квантовании в объединенной кодовой книге для фиксированной кодовой книги используют самообучающуюся нейронную сеть Кохонена, известную также как карта самоорганизации - SOM (self-organizing шар), а для адаптивной кодовой книги применяют нейронную сеть с квантованием - LVQ (learning vector quantization). Процедуру поиска реализуют на многоступенчатом иерархическом векторном квантовании, которое обеспечивает малую потерю точности при одновременном повышении скорости вычислений.
Рассмотрим заявленный способ подробнее. Нейронная сеть SOM предназначена для преобразования поступающих векторов сигналов, имеющих произвольную размерность, в одно- или двухмерную дискретную карту. При этом такое преобразование производится адаптивно, в топологически упорядоченной форме. На фиг.1 представлена схематическая диаграмма двумерной решетки нейронов, используемой в качестве дискретной карты для функционирования фиксированной кодовой книги. Все нейроны этой решетки связаны со всеми узлами входного слоя. Эта сеть имеет структуру прямого распространения с одним вычислительным слоем, состоящим из нейронов, упорядоченных в столбцы и строки.
Сущность самообучения нейронной сети SOM состоит в формировании карты (пространства) координат векторов с разбиением на гиперпрямоугольные ячейки (многоугольники Вороного), с опорным вектором-центроидом в каждом многоугольнике. Существенными характеристиками алгоритма самообучения, необходимыми для формирования фиксированной кодовой книги, являются:
непрерывное входное пространство образов активации (стохастических векторов сигналов возбуждения), которые генерируются в соответствии с некоторым распределением вероятности;
- топология нейронной сети в форме решетки, состоящей из нейронов, определяющей дискретное выходное пространство;
j,i(x)
- зависящая от времени функция окрестности h(n), которая определяет радиус окрестности нейрона-победителя i(x);
0
- параметр скорости обучения η(n), для которого задается начальное значение η и который постепенно убывает во времени n, но никогда не достигает нуля.
Экспериментально установлено, что при формировании фиксированной кодовой книги значение η(n), равное 0,005, необходимо для хорошей статистической точности на этапе сходимости. При этом для создания кодовой книги использовался сигнал остатка долговременного линейного предсказания речи, полученный на выходе фильтра синтеза. Описание линейного предсказания речи достаточно подробно представлено в (Быков С.В., Журавлев В.И., Шалимов И.А. Цифровая телефония: Учеб. пособие для вузов. - М.: Радио и связь, 2003. - С.102-105).
Последовательность шагов предварительного обучения в фиксированной кодовой книге следующая.
j
1) Инициализация. Для исходных векторов синаптических весов нейронной сети w(0) выбирают случайные значения из множества входных векторов
. В качестве условия корректного обучения на векторах возбуждения фильтра синтеза речевых сигналов необходимо различие векторов для разных значений j=1,2,…,l, где l - общее количество нейронов в решетке.
2) Подвыборка. Выбирают вектор x из входного пространства с определенной вероятностью. Этот вектор представляет собой возбуждение, которое применяется к решетке нейронов. Размерность вектора x: равна m.
3) Поиск максимального правдоподобия. Находят наиболее подходящий (победивший) нейрон i(x) на шаге n, используя критерий минимума Евклидова расстояния:
4) Коррекция. Коррекция векторов синаптических весов всех нейронов
j
j
j,i(x)
j
w(n+1)=w(n)+η(n)h(n)(x-w(n)),
j,i(x)
где η(n) - параметр скорости обучения; h(n) - функция окрестности с центром в победившем нейроне i(x). Оба этих параметра динамически изменяют во время обучения с целью получения лучшего результата.
5) Продолжение. Возврат к шагу 2 и вычисление до достижения заданного числа итераций.
По завершении процесса сходимости самоорганизующаяся карта SOM отображает важные статистические характеристики пространства стохастических векторов сигналов возбуждения. Поскольку алгоритм SOM относится к алгоритмам обучения нейронных сетей «без учителя», то сформированное пространство ячеек Вороного является приближенным с точки зрения размещения опорных векторов-центроидов в N-мерной системе координат. При этом аппроксимация определяется векторами синаптических весов нейронов на карте признаков.
В качестве механизма точной подстройки необходимо произвести квантование векторов обучения. Для квантования вектора-центроида используют метод обучения «с учителем», который использует информацию о классе для небольшого смещения опорного вектора и, соответственно, границ ячейки Вороного, а следовательно, для улучшения качества областей решения классификатора. Если метки класса входного вектора x и вектора-центроида (вектора Вороного) w согласуются, то последний смещают в направлении первого. При несогласовании вектор-центроид смещается в сторону, противоположную вектору x. Кратко процесс квантования описывается следующим образом:
C
i
C
C
n
i
C
n
1) в случае максимальной близости вектора Вороного w к входному вектору x, w(n+1)=w(n)+α[x-w(n)], где 0<α<1;
C
C
n
i
C
2) при несовпадении w(n+1)=w(n)-α[x-w(n)];
3) остальные векторы Вороного не изменяются.
n
Постоянную обучения α для формирования фиксированной кодовой книги выбирают монотонно убывающей с начальным значением 0,05. В результате процедуры адаптации после нескольких проходов по входным данным координаты опорных векторов Вороного перестают изменяться, а следовательно, и завершается создание пространства многоугольников Вороного для фиксированной кодовой книги стохастического компонента сигналов возбуждения.
Для адаптивной кодовой книги предлагается использовать нейронную сеть LVQ. На фиг.2 представлена структура нейронной сети, выполняющей функции кодовой книги, хранящей информацию о пространстве ячеек Вороного с векторами тонового компонента сигнала возбуждения. В случае обработки речевых сигналов сеть LVQ представляет каскадное подключение слоя SOM и персептронной сети. Самоорганизующийся слой улавливает значимые признаки процесса (локализует их на основе входных данных), после чего им приписывается входной вектор в персептронном слое. Вследствие хорошей локализации признаков процесса тонового сигнала возбуждения первым слоем сети в большинстве приложений обработки речи бывает достаточным применение персептрона, содержащего только один слой нейронов (зачастую линейных).
1
1
2
2
Q
Q
1.1
2.1
2.1
1.1
1
1
1
LVQ-сеть обучают на основе множества пар вход/выход, составленных из элементов обучающей последовательности {Р,Т}: {р, t},{p, t},…,{Pt}. Каждый целевой вектор имеет единственный элемент, равный 1, а остальные равны 0. Для обучения сети задают вектор входа p таким образом, чтобы в конкурирующем слое была выполнена настройка элементов матрицы весов W. Весовые коэффициенты нейрона i* наиболее близки к вектору входа p, и нейрон i* выигрывает конкуренцию. Тогда конкурирующая функция активации возвращает 1 в качестве элемента i* вектора а, причем все другие элементы а равны 0. Во втором, персептронном слое произведение W*a выделяет некоторый столбец матрицы W и связанный с ним класс k*. Таким образом, сеть связывает вектор входа p с классом k*. Это назначение может оказаться либо правильным, либо ошибочным. Поэтому в процессе обучения необходимо откорректировать строку i* матрицы W таким образом, чтобы приблизить ее к вектору p, назначение правильное, и удалить от вектора p, если назначение неправильное. Исходя из этого, правило настройки параметров следующее:
n
В качестве механизма точной подстройки производят квантование векторов обучения аналогично коррекции фиксированной кодовой книги. Экспериментально установлено, что для формирования адаптивной кодовой книги монотонно убывающая постоянная обучения α равна 0,07.
Блок-схемы алгоритмов формирования фиксированной и адаптивной кодовых книг представлены на фиг.3 и фиг.4.
При осуществлении поиска используется процедура многоступенчатого иерархического векторного квантования, которое ускоряет скорость поиска в отличие от древовидного поиска опорного вектора-центроида. Многоступенчатое иерархическое векторное квантование разделяет общую операцию поиска на множество подопераций, каждая из которых требует малого объема вычислений как для фиксированной, так и адаптивной кодовой книги. В каждой подоперации обрабатывают остаток вектора, формируемый на предыдущем подэтапе. Входной вектор квантуют Li - уровневым векторным квантователем, остаток (ошибка) квантования подают на вход второго Lj - уровневого векторного квантователя. Процесс может повторяться для любого количества подэтапов.
Окончательное квантованное значение вектора для обеих кодовых книг представляют в виде суммы выходных векторов промежуточных и конечного квантователей.
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного устройства условию патентоспособности "новизна".
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности "изобретательский уровень".
Промышленная применимость изобретения обусловлена тем, что оно может быть осуществлено с помощью современной элементной базы, с достижением указанного в изобретении назначения.
Для фиксированной кодовой книги она состоит из блока формирования исходных данных векторов обучения стохастических компонент сигналов возбуждения 1, выход блока 1 соединен с входом блока предварительного обучения нейронной сети SOM 2, выход блока 2 соединен с входом блока коррекции опорных векторов-центроидов 3, выход блока 3 соединен с входом блока хранения индексированной таблицы векторов кандидатов 4.
Функциональная схема осуществления процедуры формирования фиксированной кодовой книги и индексированных таблиц векторов кандидатов показана на фиг.5.
Для адаптивной кодовой книги схема содержит блок формирования исходных данных векторов обучения тоновых компонент сигналов возбуждения 5, выход блока 5 соединен с входом блока первого уровня адаптации нейронной сети LVQ 6, выход блока 6 соединен с входом блока второго уровня адаптации нейронной сети LVQ 7, выход блока 7 соединен с входом блока коррекции опорных векторов-центроидов 8, выход блока 8 соединен с входом блока хранения индексированной таблицы векторов кандидатов 9.
Функциональная схема осуществления процедуры формирования адаптивной кодовой книги и индексированных таблиц векторов кандидатов показана на фиг.6.
Процедуры формирования исходных данных векторов обучения, выполняемые в блоках 1 и 5, рассмотрены в О.И.Шелухин, Н.Ф.Лукьянцев. Цифровая обработка и передача речи. М., Радио и Связь, 2000 г. - С.133-135. Этап предварительного обучения нейронной сети SOM, осуществляемый в блоке 2 фиксированной кодовой книги, исследован в Осовский С. Нейронные сети для обработки информации / Пер. с польского И.Д. Рудинского. - М.: Финансы и статистика, 2002. - С.233. Коррекция опорных векторов-центроидов, проводимая в блоке 3 фиксированной кодовой книги и блоке 8 адаптивной кодовой книги, описана в Хайкин С. Нейронные сети: полный курс, 2-е издание.: Пер. с англ. - М.: Издательский дом «Вильяме», 2006. - С.603-604. Функционирование блоков 4 фиксированной кодовой книги и 9 адаптивной кодовой книги хранения таблицы векторов кандидатов представлено в Макхоул Д., Рукос С, Гиш Г. Векторное квантование при кодировании речи. // ТИИЭР. - 1985. - Т.73. - №11. - С.44-45). Адаптация, осуществляемая в блоках 6 и 7 адаптивной кодовой книги, рассмотрена в В.С.Медведев, В.Г.Потемкин. Нейронные сети. MATLAB 6. - М.: ДИАЛОГ-МИФИ, 2002. - С.168-174.
Блок 1 содержит информацию об исходных данных для обучения нейронной сети SOM - это векторы возбуждения для синтезаторов речевых сигналов, содержащие стохастические (шумовые) компоненты. Данные векторы поступают на вход блока 2 предварительного обучения нейронной сети SOM фиксированной кодовой книга, в блоке 2 выполняется процедура настройки весовых коэффициентов указанной нейронной сети, формируя тем самым пространство ячеек Вороного с векторами-центроидами, с выхода блока 2 информация поступает на вход блока 3, где происходит коррекции опорных векторов согласно описанию механизма точной подстройки (С.5), с выхода блока 3 в блок 4 подаются данные о координатах ячеек Вороного и векторов кандидатов для их хранения в виде таблицы, которая представляет собой фиксированную кодовую книгу.
Блок 5 содержит информацию об исходных данных для обучения нейронной сети LVQ - это векторы возбуждения для синтезаторов речевых сигналов, содержащие тоновые (вокализованные) компоненты. Для обучения двухуровневой нейронной сети LVQ адаптивной кодовой книги векторы возбуждения подаются с выхода блока 5 на блок 6, где происходит настройка весовых коэффициентов первого слоя сети LVQ согласно алгоритму обучения «без учителя», аналогичного алгоритму обучения SOM. С выхода блока 6 на блок 7 второго слоя нейронной сети LVQ подаются предварительно созданные координаты ячеек и векторов Вороного, в котором происходит завершение процедуры адаптации при помощи алгоритма обучения «с учителем», так как второй уровень адаптации является персептронным слоем нейронной сети LVQ. С выхода блока 7 информация поступает на вход блока 8, где происходит коррекции опорных векторов согласно описанию механизма точной подстройки (С.5), с выхода блока 8 в блок 9 подаются данные о координатах ячеек Вороного и векторов кандидатов для их хранения в виде таблицы, которая представляет собой адаптивную кодовую книгу.
Блок-схема алгоритма многоступенчатого иерархического векторного квантования, осуществляющего процедуру поиска в фиксированной и адаптивной кодовых книгах, представлена на фиг.7.
Применение предлагаемого способа существенно уменьшит требуемый для реализации объем запоминающих устройств на 25-30%, а реализация процедуры многоступенчатого иерархического векторного квантования сократит объем вычислительных затрат на 20-23% по сравнению с известными решениями в данной области.