Содержание к диссертации
Введение
ГЛАВА I Обзор состояния проблемы, существующих решений и технологий передачи мультимедиа мобильным абонентам ... 7
ГЛАВА II Математический аппарат вейвлет-анализа сигналов ...26
2.1, Частотно-временной анализ сигналов 26
2.2. Виды вейвлет-преобразований 27
2.2.1. Непрерывное вейвлет-преобразование 28
2.2.2. Ортогональное диадное («дискретное») вейвлет-преобразование. 30 2.3 Быстрое лифтинговое вейвлет-преобразование 40
ГЛАВА III Применение вейвлет-преобразований для обработки мультимедийной информации 51
3.1. Постановка задачи 5\
3.2. Обработка статичных изображений 52
3.3. Обработка видеопоследовательностей 62
3.4. Обработка аудиосигналов 7!
3.5, Выводы , 76
ГЛАВА IV Применение разработанных методов при построении мультимедийных услуг в сетях мобильной связи 78
41 Постановка задачи .., 78
4.2. Описание моделей проверки помехоустойчивости 79
4.3. Оценка работы алгоритма обработки статичных изображений 83
4.4. Оценка работы алгоритма обработки видеопоследовательностей 87
4.5. Оценка работы алгоритма обработки аудиосигналов 93
4.6. Пример мультимедийной услуги на базе предложенных алгоритмов 97
4.7. Выводы ,., 105
Заключение 106
Литература
- Частотно-временной анализ сигналов
- Ортогональное диадное («дискретное») вейвлет-преобразование. 30 2.3 Быстрое лифтинговое вейвлет-преобразование
- Обработка статичных изображений
- Описание моделей проверки помехоустойчивости
Введение к работе
Основной тенденцией развития предоставляемых современным абонентам мобильных сетей услуг является использование всё более сложных и насыщенных мультимедийных элементов, что, в свою очередь, предъявляют всё более высокие требования к пропускной способности каналов связи и к вычислительным ресурсам мобильных терминалов.
Несмотря на то, что научно-технический прогресс последних лет позволил существенно увеличить быстродействие процессоров и объём памяти, мобильных терминалов, проблема оптимальных и быстрых вычислительных алгоритмов, обрабатывающих мультимедийную информацию, является актуальной. Применение подобных алгоритмов позволит снизить энергопотребление мобильных терминалов в процессе работы.
В отличие от вычислительных и энергетических мощностей мобильных терминалов, которые растут с течением времени и развитием прогресса, канальный ресурс, выделенный для предоставления всех возможных услуг абонентам, является крайне ограниченным. Следовательно, встаёт проблема максимально эффективного использования данного ресурса, которое требует изменения алгоритмов обработки пакетов данных, передаваемых по радиоканалу, а также изменения самой структуры организации данных.
Существующие решения обработки и доставки пользователю мультимедийной информации, построены на основе аналогичных решений для персональных компьютеров, наследуя их преимуіцесіва и недосгатки. Вместе с тем, мобильные сети накладывают свои специфические ограничения, в частности, крайне нестабильный канал. При этом существующие решения не предусматривают эффективной работы в данных условиях. В результате реализованные услуги не учитывают реальную специфику сетей и оборудования мобильной связи, и, следовательно, работают недостаточно эффективно.
Результаты моделирования и экспериментов показали существенно более высокую потенциальную эффективность организации сервисов по дос-
тавке мультимедийных сообщений, использующих альтернативные алгоритмы обработки и сжатия с допустимыми потерями данных, основанные на применении математического аппарата вейвлет-нреобразований, и учитывающих специфику каналов и устройств мобильной связи - нестабильность соединения, малые размеры дисплея и низкие вычислительные мощности мобильного терминала.
Таким образом, диссертационная работа, посвященная повышению эффективности организации сервисов по обработке и доставке мультимедийной информации абонентам мобильной связи, соответствует современной научной проблематике и является актуальной.
Цель диссертационной работы состоит в повышении эффективности и улучшении эксплуатационных характеристик сервисов потоковой доставки мультимедиа подвижным абонентам путем разработки альтернативных алгоритмов обработки данных, соответствующих специфике мобильных сетей и терминалов связи.
Защищаемые в диссертационной работе научные положения могут быть сформулированы следующим образом:
разработка алгоритмов, использующих математические методы вейвлет-нреобразований для обработки и сжатия мультимедийной информации с допустимыми потерями;
разработка модели исследования с целью определения влияния случайных битовых ошибок, потерь пакетов и сбоев в синхронизации принимаемого потока на качество реконструированного сигнала;
сравнительная оценка гибкости и помехоустойчивости потоков данных, подвергнутых обработке на основе различных алгоритмов сжатия, к ошибкам, возникающим при передаче по каналам мобильной связи. Теоретическое и экспериментальное обоснование предложенных алгоритмов сжатия.
Диссертащюнная работа состоит из введения, четырёх глав, заключения, библиографического списка и приложений.
Частотно-временной анализ сигналов
Непрерывным вейвлет-преобразованием (CWT - continuous wavelet transform) функции f(x)eL2(R) называют функцию двух переменных: W(a,b) = Wf(a,b) = (f(t)Ma,b,t)), a,beR, а 0 (2.3) где вейвлеты yab{t) = y{ci,b,t) являются масштабированными и сдвинутыми копиями порождающего (материнского) вейвлета \j/{t)ei2{R): Vej»(0 = 4=fV(—), ,beR, а 0 (2.4)
Если для порождающего вейвлета выполняется условие: C \ -Ldco , (2.5) О) где Т(СУ) - образ Фурье вейвлета y/{t), то вейвлет-преобразование обратимо, т.е. существует обратное непрерывное вейвлет-преобразование: Д0 == )w(a,b)W{a,b,t) (2.6) ЦІ -да o
Таким образом, непрерывное вейвлет-преобразование - это разложение сигнала по всем возможным сдвигам и сжатиям (растяжениям) некоторой функции. [23]
При этом, помимо условия ограниченности (2.5), базисные функции вейвлет-анализа должны быть локализованными, т.е. определёнными как во временной, так и в частотной областях: (КфС-О + И)"1" («фС-О + Іф"1" при о0 (2.7) и обладать нулевым средним: JV(/)c// = o (2.8) -00 [33]
В приведённых выше выражениях переменная а определяет масштаб вейвлета и является аналогом частоты в преобразовании Фурье. Переменная b определяет величину сдвига вейвлета. Таким образом, для каждой нары а и Ь функция W(a,b) определяет амплитуду соответствующего вейвлета. [2]
В отличие от анализа Фурье, конкретный вид вейвлета не оговаривается - он должен лишь удовлетворять условиям (2.5), (2.7) и (2.8). Наибольшей популярностью пользуются функции на основе производных функций Гаусса: „.W-Hr oJ-L (2.9)
Это вызвано тем обстоятельством, что функция Гаусса имеет наилучшие показатели локализации как во временной, так и в частотной областях. Получаемый при т=1 вейвлет с равным нулю нулевым моментом (см. рис. 2.3а) называют WAVE-вейвлет. При т=2 получают МНАТ-вейвлет «мексиканская шляпа» (см. рис.2.36): ,K0 = (l-/2)exp{-yj, (2.10) Рис. 2.3 Примеры базисных вейвлет-функций: a) WAVE б) МНАТ у которого нулевой и первый моменты равны нулю. Спектр Фурье этого вейвлета более узкий, поэтому он обеспечивает лучшее разрешение. [5]
В случае анализа Фурье каждой частоте соответствует всего одна гармоническая составляющая. В случае вейвлет-анализа каждой частоте соответствует множество сдвинутых друг относительно друга функций. Если сигнал имеет особенность, например, разрыв, то на наличие этого разрыва укажут относительно высокие значения амплитуд высоких частот преобразования Фурье этого сигнала. В то же время у вейвлет-образа высокие амплитуды будут только у тех вейвлетов, экстремумы которых окажутся вблизи точки разрыва. Следовательно, можно не только определить наличие особенности, но и ту точку, в которой она имеет место. [41]
Количество копий порождающего вейвлета, необходимое для обратимого разложения, можно существенно сократить.
Распространённый случай - вычисление значений W(a,b) только для а и b вида: а = 2 , - = J, i,jeZ а Вместо непрерывной функции (2.3) получается конечное множество значений: =(/( Х(0) , (2.11) где (// (/) = (2 -/), ijeZ (2.12) Обратное преобразование выглядит следующим образом: /(o-12У № (2-13) /=-00 /=-00
Заметим, что значения, вычисляемые по (2.11), являются обобщёнными коэффициентами Фурье разложения сигнала/ по системе функций (2.12), а выражение (2.13) есть обобщённый ряд Фурье f(t) относительно системы (2.12). Следовательно, чтобы представление (2.13) имело смысл, вейвлет у/( должен быть таким, чтобы порожденная им система (2.12) являлась ортонормированным базисом в L2(l().
Формулы (2.11), (2.12) и (2.13) определяют диадное (dyadic) ортогональное вейвлет-преобразование. Иногда его называют дискретным, что вызывает определённую неоднозначность, поскольку так же именуют и вейвлет-преобразование дискретных сигналов.
С одной стороны, диадное преобразование является частным случаем преобразования непрерывного. С другой, это совершенно иной объект с особой структурой и специфическими свойствами. Диадное преобразование является аналогом не дискретного преобразования Фурье, а ряда Фурье.
Представление (2.13) имеет чётко выраженную многоуровневую иерархическую структуру. При фиксированном индексе / (назовём его уровнем разрешения или разрешением) масштаб вейвлетов не меняется (т.е. все вейвлеты для каждого разрешения являются сдвинутыми копиями друг друга). При увеличении разрешения на 1 величина сдвига уменьшается вдвое и вдвое сжимаются вейвлеты (именно поэтому преобразование называется диадным). Похожую структуру имеет и ряд Фурье, но у ряда Фурье каждому уровню разрешения соответствует лишь пара гармонических функций, сдвинутых друг относительно друга на половину периода.
Любую частичную сумму ряда Фурье можно считать огрублённым (низкочастотным) приближением исходного сигнала. Самым грубым начальным приближением является первый член - константная функция.
Ортогональное диадное («дискретное») вейвлет-преобразование. 30 2.3 Быстрое лифтинговое вейвлет-преобразование
Как было показано выше, вейвлет-преобразование сигналов (именуемое также субполосным кодированием, либо многочастотным анализом) может быть представлено как банк фильтров. Простой одноуровневый банк фильтров показан на рис. 2.5 Mt;; vy— Х- к f Ї2 — Й 12 —» Z A (± r Рис. 2.5. Представление вейвлет-преобразования в виде банка фильтров
На рис. 2.5 показано, каким образом вейвлет-преобразование использует два фильтра; низкочастотный фильтр К и высокочастотный фильтр g\ за которыми следует децимация сигнала (subsampling).
Низкочастотный и высокочастотный фильтры h и g в правой части схемы сглаживают нулевые значения, появляющиеся между отсчётами сигнала после операции интерполяции сигнала (upsampling). [54] Формулы (2,27) и (2.28) могут быть записаны с помощью Z-преобразований. Z-преобразованием дискретного сигнала 5 = { .}z называют полином вида:
Этот полином может содержать члены как с положительными, так и с отрицательными степенями аргумента; такой полином носит название полинома Лорана. Очевидно, что если сигнал имеет конечное число отличных от нуля элементов, то и его Z-преобразование будет полиномом с конечным числом членов. Z-преобразования обладают следующими важным свойством: свёртка двух дискрегаых сигналов эквивалентна перемножению их Z-преобразований (произведению полиномов), т.е. для любых сигналов, q, г и s справедливо следующее: q = r soPq(z) = Pr{z)Pa(z). Как известно, аналогичным свойством обладает преобразование Фурье.
В дальнейшем для записи Z-иреобразований некоторого сигнала s вместо обозначения l\{z) будем использовать сокращённое обозначение s(z).
Использование Z-преобразований в записи вейвлет-преобразований с помощью фильтров делает её более удобной и наглядной. В частности, чтобы показать, что компоненты сигнала s нужно брать в обратном порядке, не требуется вводить новое обозначение л . Если s(z) - Z-нреобразование сигнала s, то Z-иреобразованием сигнала s является ф ). Кроме того, если фильтр выписан в виде Z-преобразования, то сразу становится видно, какие индексы имеют его элементы (индекс элемента равен степени соответствующего члена, взятой с противоположным знаком).
Формулы (2.27) и (2.28) в записи с использованием Z-преобразований выглядят следующим образом: v,(2) =l2 A(r )vJtI(2)J ф) =l2 k(2 w(s)J і е z (2.29) vM(z) = h(z)x t2 [v,.(z)]+ g(z)x t2 [w,{z)\ іe Z (2.30) Отметим важное свойство полученных формул: в них нигде в явном виде не фигурируют ни скейлинг-функция, ни вейвлеты. Вместо них используются фильтры h и g (или h(z) и g(z)), элементами которых являются коэффициенты соответствующих масштабных соотношений.
Есть целое семейство ортогональных вейвлетов, которые вообще не имеют аналитического выражения и определяются только фильтрами. Это семейство носит название вейвлетов Добеши. [23] Скейлинг-функции и вейвлеты Добеши - это непрерывные функции, не тождественные нулю на конечном отрезке и нигде на этом отрезке не дифференцируемые. Приведём коэффициенты фильтров для скейлинг-функций и вейвлетов Добеши D4 (число 4 обозначает количество ненулевых коэффициентов в фильтрах):
h(z) = fi0+hiz-]+h2z-2 + hiz-\ g(z) = - 2 + V- + V"1
/ -1 + _з + Уз _з-Уз _1-л/3
%=4V2 4 2 -=4л/2 3=4л/2
Поскольку в формулах (2.27), (2.28) и в эквивалентных им формулах (2.29), (2.30) вместо базисных функций используются фильтры, то условие обратимости преобразования также имеет смысл выразить через эти же фильтры (напомним, что условием обратимости в терминах функций было требование ортонормированности базиса).
Очевидно, что преобразование будет- обратимым тогда и только тогда, когда при подстановке выражений (2.29) в формулу (2.30) последняя превратится в верное тождество для любого vM(s). Для этого достаточно выполнения следующих условий [6]: Kz)Kz-l)+g(z)g(z-l) = 2 (2.31) h(:)h(-=-i) + g(=)g(-= i) = 0
Преобразование Баттерворта [3], также используемое в настоящей работе для анализа межкадровых зависимостей при обработке видеопоследовательностей, в терминах z-нреобразований может быть записано следующим образом:
Обработка статичных изображений
Любое статичное изображение может быть представлено в виде двухмерной (2D) матрицы с отсчётами исходного сигнала, причём, в случае стандартного цветного изображения (RGB, 24 бита на пиксель), эта матрица распадается на три независимых слоя, то есть, фактически, любое цветное изображение может быть представлено в виде трёх 20-матриц с исходными отсчётами, [14]
Здесь мы рассматриваем обработку полутоновых (фотографических) статичных изображений вследствие того, что, во-первых, они являются наиболее общим случаем любых статичных изображений, а, во-вторых, находят наибольшее применение в сервисах сетей мобильной связи. Очевидно, что в случае рассмотрения вопросов эффективной обработки индексных (рисованных) изображений, описываемые методы потребуют ряда корректировок для приведения их в соответствие с возможными резкими перепадами цветов в подобных файлах. [12] [8] [53]
В общем виде процесс обработки статичного изображения может быть представлен следующим образом (см. рис.3, і):
Процесс 20-мреобразования матрицы отчетов может быть представлен в виде двух ID-Преобразований - столбцов и строк исходной матрицы, что позволяет построить эффективные и оптимизированные вычислительные алгоритмы.[43] [44]
В качестве метода вей влет-преобразования при обработке отсчётов используем фильтры Дебети 4-го порядка как наиболее эффективно реализуемые на платформе мобильных устройств и в то же время обеспечивающие высокие степени разложения исходного сигнала, в частности, применительно к реальным фотографическим изображениям. [9] Как упоминалось ранее, данные фильтры могут быть определены с помощью коэффициентов, определяемых следующими условиями теории вейвлет Таким образом, вся наиболее значимая низкочастотная информация, являющаяся уменьшенной копией исходного сигнала, сосредоточена лишь в небольшой части конечного изображения. Остальные области изображения содержат информацию о тонких деталях, причём при увеличении частоты количество деталей уменьшается. [52]
Следовательно, после разложения сигнала по степени значимости вейвлет-коэффициентов, в обработанной 2П-матрице установлен ряд взаимосвязей между отсчётами в различных частотных диапазонах, и это свойство может быть использовано для эффективного кодирования и сжатия с потерями информации. [21]
Кодер методом погруженного нуль-дерева (EZW - Embedded Zerotree Wavelet encoder) был разработан специально для обработки данных после вейвлет-преобразования. В первую очередь данный кодер ориентирован на изображения (то есть 20-сигналы), но он может быть использован и при многомерных сигналах, [62]
EZW-кодер основан на прогрессивном кодировании для обеспечения сжатия изображения в битовый поток с увеличивающейся точностью: то есть, чем большее количество бит добавлено в поток, тем выше детализация декодированного изображения.
Кодирование изображения EZW-кодером может дать не только значительную степень компрессии, но и позволяет, с другой стороны, организовывать передачу данных на произвольной скорости, гибко меняя качество декодированных изображений в зависимости от состояния канала. Сжатие без потерь с помощью EZW-кодера также возможно, но этот вопрос выходит за рамки данной рукописи, [91] [40] [59]
Алгоритм работы EZW-кодера базируется на двух важных наблюдениях: 1. Обычные изображения имеют спектр, смещённый в область низких частот. При преобразовании изображения с помощью вейвлетов энергия в поддиапазонах уменьшается вместе с уменьшением масштаба (напомним, что малый масштаб означает- высокое разрешение). Таким образом, вейвлет-коэффициенты, как правило, в верхних поддиапазонах будут меньшими, чем в нижних. 2. Большие вейвлет-коэффициенты являются более важными, чем меньшие.
Эти наблюдения привели к необходимости кодирования вейвлет-коэффициентов в порядке уменьшения, за несколько проходов. Во время каждого прохода выбирают некоторый порог, с которым по очереди сравнивают все вейвлет-коэффициенты. Если коэффициент превышает порог, его кодируют и удаляют из изображения, в противном случае коэффициент оставляют до следующего прохода кодера. В конце каждого прохода порог понижают и снова кодируют изображения для добавления деталей в закодированное изображение. Этот процесс повторяют до тех пор, пока не будут проанализированы все коэффициенты, либо цока не будет достигнут максимум полосы пропускания, [99J [30]
Вейвлет-преобразование переносит сигнал из временной области в масштабно-временную - таким образом, вейвлет-коэффициенты являются двумерными. При сжатии данных необходимо закодировать не только значение коэффициента, но и его положение во времени. Если сигнал представляет собой изображение, то вместо понятия положения во времени лучше пользоваться положением в пространстве. После представления сигнала в виде вейвлет-коэффициентов мы можем ввести понятие дерева -коэффициент в нижней части спектра имеет четыре ниспадающих коэффициента в более высоких частях спектра (см. рис. 3.3). Каждый из этих коэффициентов, в свою очередь, имеет по четыре ниспадающих коэффициента в ещё более высоких частях спектра. Таким образом, получено квадратурное дерево - каждый узел имеет четыре ветви. [97J
Описание моделей проверки помехоустойчивости
В гл. 3 были рассмотрены методы обработки мультимедийной информации, основанные на математическом аппарате вейвлет-иреобразований, а также приведены эффективные алгоритмы, реализуемые на мобильных платформах с ограниченными вычислительными возможностями.
Очевидно, что, помимо возможности реализации представленных алгоритмов, ключевую роль играют степень компрессии данных и качество восстановленного сигнала - именно эти аспекты будут являться решающими при оценке необходимости и коммерческой эффективности внедрения новых сервисов.
Существующие сервисы в сетях подвижной связи 2,50 [7] и развёртываемых сетях 3G уже используют достаточно эффективные решения по обработке различных видов мультимедийной информации (JPEG, MPEG-4, МРЗ), которые, однако, не лишены ряда недостатков, но при этом имеют широчайшую поддержку со стороны контент-провайдеров и производителей программного обеспечения.
Таким образом, предложенные алгоритмы должны обладать существенно более высокими характеристиками по сравнению с существующими методами обработки, чтобы быть востребованными на рынке.
Следоватезшно, необходимо произвести оценку эффективности предложенных алгоритмов по следующим показателям: степень компрессии качество восстановленного сигнала помехоустойчивость полученного кода к различным видам ошибок в канале. Для оценки перечисленных выше параметров будем использовать общепринятые объективные качественные показатели.
Также рассмотрим возможность применения предложенных методов обработки мультимедийной информации при организации услуг в сетях мобильной связи, причем в качестве платформы построения услуг рассмотрим решение IMS (IP Multimedia Subsystem) как наиболее перспективное на текущий момент.
Описание моделей проверки помехоустойчивости
Для оценки устойчивости кода к различным ошибкам, накладываемым на сигнал в процессе передачи по каналу связи, используем модели, предусматривающие следующие типовые виды ошибок: единичные битовые ошибки, случайно распределённые по всему сигналу; потеря пакета данных потеря синхронизации, при которой происходит смещение потока данных на некоторое число отсчётов.
При этом мы не будем учитывать технику повторных запросов (ARQ -automatic repeat request), поскольку для декодирующего устройства, работаюіцеїо с конечным полученным вектором отсчётов, это не имеет значения, [1]
В общем виде алгоритм, накладывающий на код единичные битовые ошибки, распределённые случайным образом, с некоторой заданной плотностью ошибок BER (bit error ratio), можно представить в следующем виде:
1. В соответствии с заданным BER и длиной анализируемого вектора L в битах, вычислить количество Q бит, которые должны быть инвертированы: Q = L-BER бит
2. Запустить цикл от 1 до Q, в котором случайным образом определять смещение х в анализируемом векторе X, которое будет определять местоположение ошибочного бита, и замещать существующий бит случайным числом: Х[х]= rand{0,\) 3. Сохранить полученный вектор в файл.
При моделировании ситуации потери единичного пакета данных длиной L байт используем схожий алгоритм: 1. Определить смещение х в исходном векторе X, которое будет определять начало потерянного пакета данных. 2. Запустить цикл от 1 до L, в котором, увеличивая относительное смещение на 1, замещать существующий в векторе X байт случайным значением: Х[х + / ] = rand(0,255), / = 1.../. 3. Сохранить полученный вектор в файле.
И, наконец, приведём алгоритм моделирования потери синхронизации в принимаемом потоке данных, заключающейся в сдвиге части потока на определённую величину L байт. Здесь, в отличие от приведённых выше алгоригмов, длина обрабатываемого вектора отсчётов не останется неизменной, а также увеличится на L байт.
