Пошук векторів у кодових книгах при ущільненні мовлення на основі бінарного дерева

Abstract

Передача мовленнєвих сигналів у неущільненому вигляді потребує швидкісних каналів зв’язку через велику надлишковість даних. Саме тому в сучасних системах цифрового зв’язку широко застосовуються алгоритми кодування мовлення, що реалізують високу ступінь ущільнення при збереженні достатнього рівня якості звучання, зокрема з використанням кодових книг. При цьому широко застосовується векторне квантування. Проте практичне застосування векторного квантування у реальному масштабі часу обмежено через різке зростання витрат пам’яті та часу на пошук кодованого вектора у кодових книгах. Для скорочення часу пошуку найближчого вектора у кодових книгах запропоновано метод структуризації кодових книг на основі бінарного дерева. Показано, що використання бінарного дерева дозволяє суттєво зменшити кількість вимірювань відстані, необхідних для пошуку найближчого сусіднього вектора. Проаналізовано основні фактори, що впливають на ефективність пошуку. Розглянуто кілька варіантів розбиття області параметрів при створенні дерева, а саме: midpt, коли комірка ділиться січною площиною посередині перпендикулярно найдовшій стороні; sl_midpt, що відрізняється від попереднього можливістю зсуву січної площини з метою зменшення кількості тривіальних листів; sl_fair, що поєднує методи розбиття по медіані та sl_midpt з врахуванням обмеження на відношення сторін створюваних комірок. Наведено результати порівняльного аналізу вказаних варіантів. Розглянуто властивості LSF як об’єкта квантування, які необхідно враховувати при побудові бінарного дерева Експериментально досліджено продуктивність методів. Оскільки всі вектори в кодових книгах займають лише верхню частину прямокутної області, було запропоновано повернути осі координат на 45 градусів проти годинникової стрілки, перерахувавши координати векторів. Це дало можливість дещо скоротити час пошуку за рахунок штучного досягнення більшої симетричності розбиття дерева. Оцінювання результатів проводилося за кількістю обчислень відстаней у кодових книгах, необхідною для пошуку найближчого вектора, відносно розміру тестової вибірки. Застосування методу при квантуванні мовлення дозволило зменшити час пошуку найближчого вектора до 5% від часу повного пошуку. Скорочення часу пошуку (? в 17 разів) в процесі передавання мовленнєвих сигналів досягається за рахунок додаткових обчислювальних витрат на підготовчому етапі, необхідних для побудови бінарного дерева, а також збільшення обсягів пам’яті, потрібної для його зберігання.

Передача речевых сигналов в несжатом виде требует скоростных каналов связи через большую избыточность данных. Именно поэтому в современных системах цифровой связи широко применяются алгоритмы кодирования речи, реализующих высокую степень уплотнения при сохранении достаточного уровня качества звучания, в частности с использованием кодовых книг. При этом широко применяется векторное квантование. Однако практическое применение векторного квантования в реальном масштабе времени ограничено из-за резкого роста затрат памяти и времени на поиск кодированного вектора в кодовых книгах. Для сокращения времени поиска ближайшего вектора в кодовых книгах предложен метод структуризации кодовых книг на основе бинарного дерева. Показано, что использование бинарного дерева позволяет существенно уменьшить количество измерений расстояния, необходимых для поиска ближайшего соседнего вектора. Проанализированы основные факторы, влияющие на эффективность поиска. Рассмотрено несколько вариантов разбиения области параметров при создании дерева, а именно: midpt, когда ячейка делится секущей плоскостью посередине перпендикулярно самой длинной стороне; sl_midpt, отличающийся от предыдущего возможностью смещения секущей плоскости с целью уменьшения количества тривиальных листов; sl_fair, сочетающий методы разбиения по медиане и sl_midpt с учетом ограничения на отношение сторон создаваемых ячеек. Приведены результаты сравнительного анализа указанных вариантов. Рассмотрены свойства LSF как объекта квантования, которые необходимо учитывать при построении бинарного дерева. Экспериментально исследовано производительность методов. Поскольку все векторы в кодовых книгах занимают лишь верхнюю часть прямоугольной области, было предложено повернуть оси координат на 45 градусов против часовой стрелки, перечислив координаты векторов. Это позволило несколько сократить время поиска за счет искусственного достижения большей симметричности разбиения дерева. Оценка результатов проводилось по количеству вычислений расстояний в кодовых книгах, необходимых для поиска ближайшего вектора, относительно размера тестовой выборки. Применение метода при квантовании речи позволило уменьшить время поиска ближайшего вектора до 5% от времени полного поиска. Сокращения времени поиска (? в 17 раз) в процессе передачи речевых сигналов достигается за счет дополнительных вычислительных затрат на подготовительном этапе, необходимых для построения бинарного дерева, а также увеличение объемов памяти, необходимой для его хранения.

Speech signals transmission without coding requires high-speed communication channels because of a large redundancy of data. That is why in modern digital communication systems are widely used speech coding algorithms that implement a high degree of coding while maintaining a sufficient level of sound quality, in particular including codebooks using. It is widely used vector quantization. However, the practical use of vector quantization in real time is limited due to the sharp increase in costs of memory and coded vector search time in the codebooks. To reduce the nearest vector search time in codebooks the method of structuring the codebook is proposed. Shown that using of the binary tree allows to reduce the distance measurements number significantly that are needed to find the nearest neighbor vector. The main factors influencing search performance are analyzed. Several parameters partition options are considered when creating the tree, namely: midpt, which cuts the current cell by the splitting plane through its midpoint orthogonal to its longest side; sl_midpt, that differs from the previous by ''sliding" the splitting plane, if a trivial split were to result in order to avoid this; sl_fair, that combines split at the median with sl_midpt taking into account the aspect ratio bound. The results of comparative analysis of the listed methods are presented. Properties LSF as an object of quantization are considered when building the binary tree. The methods performance are studied experimentally. As all vectors in codebooks cover only the top of the rectangular area it was proposed to rotate the coordinate axis 45 degrees counterclockwise, recalculating the vectors coordinates. This enabled us to reduce the search time due to the achieving more symmetrical tree partitioning. Results evaluation was based on distances calculations number in the codebooks needed to find the nearest vector, among the sample test. The method using for speech quantization reduced the nearest vector search time to 5% of full-time search. Search time reducing (? 17 times) when the transmission of speech signals is achieved by additional computational costs of the preparatory steps needed for building a binary tree, and also increase the amount of memory needed to store.