Санкт-Петербург

Ряскин Глеб Александрович 
Год рождения: 1995 
Университет ИТМО, факультет безопасных информационных 
технологий, кафедра проектирования и безопасности компьютерных 
систем, студент группы № N4154 
Направление подготовки: 10.04.01 – Информационная безопасность 
e-mail: [e-mail] 
Таранов Сергей Владимирович 
Год рождения: 1991 
Университет ИТМО, факультет безопасных информационных 
технологий, кафедра проектирования и безопасности компьютерных 
систем, аспирант 
Направление подготовки: 10.06.01 – Информационная безопасность 
e-mail: [e-mail] 
УДК 004.052.42+ 004.056.2 
ПРИМЕНЕНИЕ СПЛАЙН-ВЕЙВЛЕТОВ ВТОРОГО ПОРЯДКА НА СЕТКЕ, 
ГЕНЕРИРУЕМОЙ КЛЕТОЧНЫМИ АВТОМАТАМИ 
Мухамеджанов Д.Д., Ряскин Г.А., Таранов С.В. 
Научный руководитель – к.ф.-м.н., доцент Левина А.Б. 
Работа выполнена в рамках темы НИР № 617026 «Технологии киберфизических систем: 
управление, вычисления, безопасность». 
Вейвлетные преобразования находят широкое применение для сжатия, фильтрации и анализа 
сигналов. В работе проанализировано влияние метода генерации сетки для сплайн-вейвлетных 
разложений второго порядка на параметры сжатия исходного сигнала. Предложен метод создания 
сетки на основе клеточных автоматов, дающий лучшие показатели сжатия для сплайн-вейвлетных 
преобразований второго порядка. 
Ключевые слова: вейвлет-преобразование, сплайны, клеточные автоматы, сжатие, обработка 
сигналов. 
Одной из основных проблем киберфизических систем является обработка больших 
объемов данных, поэтому разработка новых и эффективных алгоритмов сжатия сигналов 
различной природы является актуальной задачей. В связи с этим последние десятилетия 
отмечены возрождением интереса к локальной аппроксимации и, в частности, к сплайнам и 
вейвлетам [1–3]. Это объясняется широким применением последних при обработке больших 
объемов информации, сжатии информации и фильтрации [4, 5]. Основная задача обработки с 
помощью – сокращение объема числового потока за счет выявления и отбрасывания 
несущественных (с той или иной точки зрения) частей [6]. Основная идея вейвлетного 

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
100 
разложения заключается в том, что информационный поток можно разделить на составляющие 
таким образом, чтобы можно было выделить основной информационный поток и уточняющий 
поток. Первый поток обычно называется основным, а второй – дополнительным. 
Вейвлетное разложение потока на составляющие может осуществляться более одного 
раза. На втором шаге/уровне вейвлетного разложения основной поток по аналогии с 
исходной последовательностью, разделяется на две составляющие. В итоге результатом 
второго уровня разложения является основной поток и два вейвлетных потока, которые 
могут при необходимости отбрасываться либо наоборот уточнять основной поток. Процесс 
перехода от исходного информационного потока к двум его составляющим называется 
декомпозицией, а соответствующие формулы – формулами декомпозиции. Для сплайн-
вейвлетного преобразования помимо самого информационного потока необходима сетка 
равной длины, состоящая из элементов того же поля, что и исходный поток. К тому же 
нужно определить номера элементов изначального информационного потока, которые будут 
из него выбрасываться. 
При сплайн-вейвлетном преобразовании из начального информационного потока 
выбрасывается элемент (или блок элементов), поэтому последовательность, получившаяся 
после подобного преобразования, представляет собой измененную версию исходного потока. 
Поток, получившийся в результате подобного изменения, является основным потоком. 
Результатом процесса декомпозиции является элемент дополнительного или вейвлетного 
потока. Для сплайн-вейвлетного преобразования необходима сетка элементов, которая 
вместе с исходным потоком модифицируется путем выбрасывания из нее блока элементов. 
Таким образом, для формулы декомпозиции второго порядка необходимо 
дополнительно определить сетку, которая будет оказывать влияние на параметры 
возможного сжатия, фильтрации, уточнения исходного сигнала. В данной работе сетка для 
вейвлет-преобразования задавалась с помощью клеточных автоматов. Клеточный автомат 
представляет собой динамическую систему с дискретными изменениями состояний в 
каждый момент времени. 
Клеточный автомат обладает следующими свойствами. 
1. Можно рассматривать как множество конечных автоматов. 
2. Каждая клетка (ячейка) может находиться в одном из состояний в конечном множестве. 
3. Изменение состояния каждой клетки зависит от состояния ее соседей и состояния самой 
клетки на данный момент времени. Множество соседей называют окружением клетки. 
4. Переходы состояний могут описываться «правилами». 
Простейшим клеточным автоматом будет одномерный клеточный автомат с двумя 
возможными состояниями, а соседями клетки будут смежные с ней клетки. Такие автоматы 
называются элементарными. Три клетки (центральная, ее соседи) порождают 8 комбинаций 
состояний этих трех клеток. Далее на основе анализа текущего состояния тройки 
принимается решение о том, будет ли центральная клетка 1 или 0 на следующем шаге. Всего 
существует 256 возможных правил, которые кодируются в соответствии с кодом Вольфрама. 
Например, правило 30 можно представить, как последовательность логических 
операций или в виде таблицы состояний (табл. 1). 
Таблица 1. Правило 30 для клеточного автомата 
111 
110 
101 
100 
011 
010 
001 
000 
0 
0 
0 
1 
1 
1 
1 
0 
Для эксперимента были построены программные модели простейших клеточных 
автоматов. Неравномерная сетка для сплайн-вейвлетного разложения второго порядка 
генерировалась правилами 22 и 193. В качестве сетки использовались с 100 по 220 уровни 
эволюции автомата. На каждом уровне первые 4 бита задают элемент сетки в 16 системе 
счисления. Последующие 4 бита задают количество выбрасываемых элементов на одном 

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
101 
этапе разложения. Всего в эксперименте было задано 120 элементов исходного потока и для 
данного потока, используя клеточные автоматы, была сгенерирована сетка по 
вышепредставленному алгоритму. 
В табл. 2 представлено сравнение существующих методов выбора сетки и 
предложенного в работе метода на основе клеточных автоматов. 
Таблица 2. Сравнение методов генерации сетки 
Метод задания сетки и 
выбрасывания элементов 
Количество 
сохраняемых 
элементов 
исходного потока 
Шаг 
сетки 
Количество 
единовременно 
выбрасываемых 
узлов 
Коэффициент 
сжатия Q после 
3 уровня 
разложения 
Метод с оценкой 
априорной информации 
<8 
4, 5, 6 
2×N 
0,8743 
Равномерная сетка с 
фиксированным шагом 
<8 
4, 5, 6 
8 
0,8623 
Сетка на основе 
клеточного автомата 
правило 193 
<8 
4 
1–16 
0,8273 
Сетка на основе 
клеточного автомата 
правило 22 
<8 
4 
1–16 
0,8426 
В табл. 2 переменная N обозначает уровень разложения в формуле сплайн-вейвлетного 
преобразования. В отличие от существующих методов сетка и выбрасываемые элементы 
зависят от исходного потока, что позволяет подстроиться под конкретные значения 
исходного потока. Если в других методах элементы выбрасываются независимо от исходных 
значений, в результате чего может быть потеряна информация в исходном потоке, либо 
каким-то образом искажена (смазанные участки на изображении, усредненные значения в 
экспериментальных данных), то в предложенном методе сетка коррелирует с исходными 
значениями, что позволяет добиться лучшего показателя сжатия. 
Алгоритмы задания сеток в сплайн-вейвлетных разложениях оказывают прямое 
влияние на параметры алгоритмов сжатия данных, таких как соотношение сжатия и качества 
восстанавливаемого сигнала. Сплайн-вейвлетные разложения являются крайне полезными 
при работе с большими массивами данных, а также при обработке экспериментальных 
данных (очистка от шумов, выделение областей интереса), вейвлет-преобразование дает 
наиболее наглядную и информативную картину результатов эксперимента, позволяет 
очистить исходные данные от шумов и случайных искажений, и даже выделить некоторые 
особенности анализируемых данных. 
В результате данной работы: 
1. был разработан метод генерации сетки на основе клеточных автоматов для сплайн- 
вейвлетных разложений второго порядка; 
2. исследованы характеристики разработанной конструкции и проведено сравнение с 
аналогичными методами; 
3. предложены области применения разработанного метода.