автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка и исследование методов и алгоритмов устранения избыточности видеопоследовательностей на основе сегментации видеоданных

На правах рукописи

Рубина Ирина Семеновна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ И АЛГОРИТМОВ УСТРАНЕНИЯ ИЗБЫТОЧНОСТИ ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЕЙ НА ОСНОВЕ СЕГМЕНТАЦИИ ВИДЕОДАННЫХ

Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата технических наук

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

005059177

Работа выполнена в Национальном Исследовательском университете информационных технологий, механики и оптики,

Научный руководитель: Тропченко Александр Ювенальевич,

доктор технических наук, профессор.

Официальные оппоненты: Потапов Алексей Сергеевич,

доктор технических наук, доцент, лаборатория интеллектуальных систем компьютерного видения ФГУП «Научно-производственная корпорация

«Государственный оптический институт им, С.И. Вавилова» (г. Санкт-Петербург), начальник.

Меженин Александр Владимирович, кандидат технических наук, доцент, кафедра инженерной и компьютерной графики НИУ ИТМО, доцент.

Ведущая организация: Филиал ФГУП Центральный научно-

исследовательский институт связи -Ленинградское отделение ЦНЙИС.

Защита диссертации состоится «23» мая 2013 г. в 15 часов 30 минут на заседании диссертационного совета Д 212.227.06 при Национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49, конференц-зал центра интернет-образования.

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

Автореферат разослан «22» апреля 2013 г. Ученый секретарь

диссертационного совета Лобанов И.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

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

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

Существенный вклад в теорию сжатия видеоданных внесли Ватолин Д., Сэломон Д., Гонсалес Р., Ричардсон Я. и многие другие видные ученые и специалисты.

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

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

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

Задачи исследования

В рамках диссертационного исследования решались следующие задачи:

1. Анализ алгоритмов построения траектории движущихся объектов на основе сегментации видеоданных.

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

3. Разработка алгоритмов сжатия на основе быстрых трехмерных алгоритмов кодирования преобразованием.

4. Разработка методов сжатия за счет новых алгоритмов интерполяции отсчетов сигнала и исследование их эффективности,

5. Построение модели кодека и программная реализация алгоритмов сжатия на основе предложенных подходов.

Методы исследования

Диссертационное исследование основано на ряде теоретических и экспериментальных методов. В рамках теоретической части исследования использовались методы теории информации (ШЭ-теории и устранения избыточности данных), методы распознавания образов и цифровой обработки сигналов, а также методы теории вероятностей. В рамках экспериментального исследования была проведена программная реализация алгоритмов сжатия с последующим сравнением реализованных алгоритмов с уже существующими алгоритмами. Экспериментальные методы подразумевают моделирование и реализацию алгоритмов на языке высокого уровня С++.

На защиту выносятся следующие положения:

1. Алгоритм выделения объектов видеопоследовательности, основанный на определении опорных пикселов видеокадра.

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

3. Быстрый трехмерный алгоритм нисходящего кодирования преобразованием с неразделимым ядром, основанный на дискретном преобразовании Хартли с переменным размером матрицы преобразования.

4. Быстрый трехмерный алгоритм кодирования преобразованием, основанный на дискретном косинусном преобразовании с переменным размером матрицы преобразования.

5. Алгоритм интерполяции отсчетов видеосигнала с переменным размером ядра.

6. Метод сжатия видеоданных, основанный на сочетании предложенных алгоритмов.

Научная новизна работы

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

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

3. Разработан быстрый трехмерный алгоритм нисходящего кодирования преобразованием с неразделимым ядром, основанный на дискретном преобразовании Хартли с переменным размером матрицы преобразования.

4. Разработан быстрый трехмерный алгоритм кодирования преобразованием, основанный на дискретном косинусном преобразовании с переменным размером матрицы преобразования.

5. Разработан алгоритм интерполяции отсчетов видеосигнала с переменным размером ядра.

6. Предложен метод сжатия видеоданных, основанный на сочетании предложенных алгоритмов, позволяющий повысить эффективность сжатия видеоданных.

Практическая ценность результатов работы заключается в следующем:

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

2. Разработанные быстрые алгоритмы многомерных преобразований Хартли и ДКП позволили сократить объем вычислительных затрат,

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

Внедрение результатов работы

Основные результаты работы внедрены в учебном процессе НИУ ИТМО и проведенных в НИУ ИТМО НИР №610481 «Разработка методов и средств системотехнического проектирования информационных и управляющих вычислительных систем с распределенной архитектурой» кафедры ВТ и НИР №211115 «Исследование и разработка методов искусственного интеллекта применительно к _ задаче построения обобщенного решения мультимодальной биометрической идентификации» кафедры РИС, Программное обеспечение, реализующее предложенные методы и алгоритмы прошло государственную регистрацию пакетов программ для ЭВМ (свидетельство №2013612402). Результаты исследования поддержаны грантами Правительства Санкт-Петербурга в 2010 и 2011 гг.

Апробация результатов работы

Результаты выполненных исследований были представлены на конференциях:

- XXXIX научной и учебно-методической конференции СПбГУ ИТМО (2010 г.).

- VII Всероссийской межвузовской конференции молодых ученых (2010 г.).

- XL научной и учебно-методической конференции СПбГУ ИТМО (2011 г.).

- VIII Всероссийской межвузовской конференции молодых ученых (2011 г.).

- XLI научной и учебно-методической конференции НИУ ИТМО (2012 г.).

- I Всероссийском конгрессе молодых ученых (2012 г.).

- Международной научно-практической конференции «Научные исследования и

их практическое применение. Современное состояние и пути развития' 2012»

(2012 г.).

Публикации

Основные результаты диссертационного исследования опубликованы в 13-ти научных публикациях общим объемом 42 страницы: в том числе в 4-х статьях в изданиях, включенных в Перечень ВАК, 10 работ опубликовано без соавторов.

Структура и объем работы

Диссертационная работа состоит из введения, основной части, содержащей 5 разделов, заключения, списка литературы и 2 приложений. В приложениях представлены порядок тестирования, характер тестовых последовательностей, а также документы, подтверждающие использование диссертационной работы. Основной объем работы - 118 страниц. Объем приложений 26 страниц. Работа содержит 27 иллюстраций и 1 таблицу. Список литературы включает 78 библиографических источников.

СОДЕРЖАНИЕ РАБОТЫ

Введение содержит обоснование актуальности рассматриваемых в диссертации вопросов. Формулируются цель, задачи и методы исследования.

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

Также определяются основные этапы сжатия и выделяются основные функциональные единицы видеокомпрсссора, а именно пространственная и временная модели. Рассматриваются существующие критерии оценки качества восстановленной видеопоследовательности.

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

Во втором разделе исследуются алгоритмы оценки и компенсации движения на основе сегментации видеоданных.

Подход к устранению временной избыточности видеопоследовательности на основе блоков можно реализовать двумя способами - на основе сегментов фиксированного (FSBM) и переменного размера (VSBM). При этом выбор размера блока всегда является компромиссом между коэффициентом сжатия и уровнем вносимых искажений.

В основу разработанных алгоритмов выбора и классификации блоков положен алгоритм VSBM, поскольку он обеспечивает сокращение потока векторов движения на 60 % по сравнению с алгоритмом FSBM.

Для предложенного алгоритма ортогональной пирамиды (МРО) выбора блоков был использован иерархический поиск - алгоритм усредненной пирамиды (МР), а также алгоритм ортогонального поиска (OSA).

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

Для оценки эффективности предложенного алгоритма было выполнено его сравнение со следующими алгоритмами: полного перебора (FS), поиска по принципу «один за раз» (ОТА), ортогонального (OSA), трехшагового (TSS), двухмерного логарифмического (TDL), четырехшагового (FSS), иерархического (МР) поиска.

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

Уровень 2

1 ¡Уровень 1

Четыре точки лучшего совпадения: З МР+1 OSA

Окно поиска

лучшего

совпадения

2 ¡Уровень 1

Окна поиске лучшего совпадения

Окно поиска лучшего совпадения

2 ¡Уровень О

Рисунок 1 Схема отбора блоков по алгоритму МРО

При этом в алгоритме МРО поиск вектора движения для каждого блока не зависит от результатов поиска на более ранних итерациях алгоритма, что делает разработанный алгоритм наиболее эффективным для сложных траекторий движения.

В целях сокращения передаваемой информации о движении, было выработано требование объединения блоков в соответствии с выбранным критерием принадлежности локальной области. При этом рассматриваются два случая, приводящих к снижению качества: потеря областей малого движения и небольшое количество пикселов для блоков малого размера. Для первого случая выбрано ограничение размеров блока до 64x64 пиксела, а для второго случая предложено разделение сравниваемых блоков по различным их типам.

.і..........—Г.ч—

19 номер naipe

16 номер raflpa

Рисунок 2 Значения количества базовых операций (N) для ряда кадров последовательности «Береговая охрана» для перечня рассматриваемых алгоритмов: (а) —TSS; -- - TDL; —FSS; —-ОТА;--OSA; (б) - -FS; —МР; —МРО

PSNR^S ВО

TSS TDL FSS OTA OSA M* МРО

Рисунок 3 Значения PSNR для тестовых последовательностей: «Дети»; «Погода»; •*- «Береговая охрана»; -*-«Акийо»; -*-«Телефон в машине»

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

1. разделение по направленню движения в соответствии с алгоритмом (VJ -Vectors Joint based), который выполняется в три этапа:

• сортировка векторов движения по принципу увеличения параметров движения;

• разделение векторов движения в соответствие с допустимым уровнем отклонения параметров движения на группы;

• выравнивание поля векторов за счет значений векторов локальной окрестности,

2. разработанный алгоритм разделения в соответствии с маской классификации по мажоритарному признаку (Pol - Points of Interest based). При этом маска формируется в соответствии с этапами, приведенными на рисунке 4.

Выбор алгоритма выделения опорных точек основан на исследовании следующих алгоритмов: алгоритм ADC (Absolute Difference Criteria), алгоритм Харриса, а также алгоритм SIFT (Scale Invariant Feature Transform). По результатам

проведенного анализа алгоритм SIFT с размером ядра Гаусса 5x5 был выбран в

На рисунке представлены

Рисунок 4 Последовательность этапов алгоритма Pol

5

зависимости РЙЖ и вычислительных затрат 0, выражаемых количеством базовых операций на блок кадра, от размеров блока, выражаемых минимальным размером 5 и максимальным приращением по каждой из сторон А, а также ЯП-характеристика.

МЛ MvU 414,14 4'4,- II W.+W |М,+И8,й,ш*

ЗкХ'Х Мів ¡UAH4 4*4М 410,4-IJ 44-Ji" ІАШИДго*

R. К еж,

/1\ Г""............................................. V s .....ч...........................................

V • \ * \ s ________і

• ■----

15,00 20,00 25,00 30,00 35,00 40,00 45,00 50,00 53,00 60,00 О.яВ

Рисунок 5 Зависимости для алгоритмов классификации - - У8ВМ+Ро1+МРО; — ■■ УБВМ+У^МРО и — алгоритма УБВМдля последовательности «Теннис»

Анализ результатов показал, что предложенный алгоритм способствует улучшению показателей сжатия воспроизведенной видеопоследовательности (если PSNR > ЗОдБ, то качество работы алгоритма оценки и компенсации движения считается хорошим). Алгоритм VSBM+PoI+MPO превзошел существующие алгоритмы VSBM и VSBM+VJ+MPO как с точки зрения качества восстановленной видеопоследовательности, так и с точки зрения коэффициента её сжатия при схожей вычислительной сложности. Необходимо также отметить, что при максимальном значении размера блока, равном 64x64, проявляется эффект мажоритарности.

Третий раздел посвящен исследованию алгоритмов кодирования преобразованием.

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

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

Нисходящий алгоритм быстрого трехмерного преобразования Хартли (3D-БПХП) на основе неразделимого ядра преобразования для блоков целой размерности можно сформулировать следующим образом:

7

X(u,v,t) = ^Xt(u,v,t),

г«0

где и, V, / - размерность вычисляемого целого блока, г - номер частичной суммы,

X,С.".')-r.J.'.v,/)™^^)], x,(»,v,0- ^'„.(".V^^+^+i)], «-i^-ií-i

/.q M N M Г

N, M, P - размерность куба-кадра, casx=sinx+cos*, a abe - трехбитный двоичный код, определяющий номер формируемой суммы.

Блоки промежуточной размерности формируются иерархически при помощи более крупных блоков целой размерности на основе вычисляемых частичных сумм по формуле:

A'(«'.v',0 = ¿:(±x(«,v,0)

г-О

где и', v', t' - размерность вычисляемого промежуточного блока. Промежуточный блок может иметь размерность, уменьшаемую вдвое хотя бы по одной из координат.

X0(u,v,t) x,(u,v,t)

Х(и,у,1) Х(и,У.1-у)

__ N

^ Х(и—,у,0 Х(и-у,У,1- у)

V, N М ..

Х(и-Т,у—,1)

N М . Р,

Х(и-т,у.т,1-т)

Рисунок б Схема итерации

алгоритма ЗО-БПХП с соответствующими связями ■ вычитаниясложения

Если размер блока уменьшается по одному или по трем аргументам для функции cas, то знак суммы считается отрицательным. При уменьшении размеров ни по одному или по двум аргументам для функции cas знак не изменяется.

Иерархический процесс продолжается, пока размерность целого блока не составит 2x2 пиксела. Схема одной итерации предложенного алгоритма представлена на рисунке 6,

Алгоритм быстрого трехмерного косинусного преобразования на основе вычисления текущего отсчета по набору

предыдущих отсчетов (SD-БКПП) можно сформулировать следующим образом:

СТ( і г,:; -*" ¿L А^п-;/*'г-;:

+S^.h»(F-i.m " F-iin ~Fmo+Fu» - 2co,|£(F ~F~h\- Fm))+ +ZA:-M.,(F-,w-F.-BrF,M+F,»rJC0»^(F,M-FMn-F„l))+

hi(F-i.M ~ F. 1-й " F.IM=FH-I+F m+Fm+F-m+Fm)

где c({k,v,í}) ~ j n/2 , Klbe = COS i—

COS

(Зу-2+і)л-у ЇМ

eos

(3k-2+c)at 2 P

I F+K* ' £ £ fc/P' - 2 + ОУ - 2 + M* - 2 + е)ЯЛ.

■и).

!»1 J.l Ы

a abo трехбитный троичный код, каждый разряд которого принадлежит множеству М,0,1}.

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

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

восстановлении по сравнению с двухмерными вариантами алгоритмов. Это объясняется тем, что алгоритмы выполняют преобразование не только в пространстве, но и во времени, устраняя соответствующую избыточность.

В результате исследования для кадров последовательности «Теннис» получены зависимости, представленные на рисунках 7 и 8.

яааі

4 9 V И 32

нЗО-бПХ ПЗО-6КП ВЮ-БПХ® ОЗО-БКЛФ

Рисунок 7 Вычислительная сложность алгоритмов кодирования преобразованием (<2], <22-количество умножений и сложений, У-размер стороны блока).

П.Ксж. 30 ■

43 "

53 34 55 36 57 » 59 В,дВ

Рисунок 8 ЯЛ-крпвые для алгоритмов —Зй-БПХФ, —ЗП-БПХП, .......ЗИ-БКПФ,

— ■ -ЗО-БКПП кодирования преобразованием.

Предложенный быстрый алгоритм ЗБ-БПХП позволил на 30 % сократить число операций сложения/умножения на пиксел кадра видеопоследовательности за счет иерархического расчета коэффициентов преобразования по сравнению с предложенным ДжеонгомИ. алгоритмом. Также он позволил повысить качество восстановленной видеопоследовательности на 2 % и коэффициент ее сжатия на 1,5 % по сравнению с алгоритмом на основе фиксированного размера ядра (ЗО-БПХФ).

Предложенный быстрый алгоритм ЗО-БКПП позволил на 40 % сократить число операций умножения на пиксел кадра видеопоследовательности при незначительном увеличении числа сложений по сравнению с предложенным Алшибами X.

алгоритмом, Также он обеспечил повышение качества восстановленной видеопоследовательности и коэффициента ее сжатия на 3 % по сравнению с подходом на основе фиксированного размера ядра (ЗО-БКПФ).

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

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

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

О \

X

V

о N о

к

0 \

О О /

/

0

Рисунок 9 Адаптивная интерполяция центрального отсчета з 5

О О О

с' с'

О с О

с' с'

0 О О

с"

с"

0 О О 0 0 0 0 0 0

О"' О"' с"' с'" с"' с'" с"' с"'

О с" О с" а 0" 0 с" 0

с™ с'" с"' с"' 0"' с"' е"' с"'

О О с' 0 о 0 о' 0 0

0"' с'" с'" о"' с"1 с"1 с'" с'"

О о" О с" 0 0" 0 о" 0

с'" о"' с"1 О"' 0'" 0'" с"' о"'

О 0 О О с 0 0 0 0

о"' О'" с"' 0'" с"' с"' 0'" 0'"

О с" О с" 0 0" 0 о" 0

с'" 6'" с'" о'" о"' с"' с'" с"'

О О с' О 0 0 с' 0 0

о"' о"' с'" с'" о"' о"' о"' с"'

О с" О с" 0 с" 0 с" 0

О'" с"' с"' 0'" 0'" с'" с'" с"'

О О О О 0 0 0 0 0

Рисунок 10 Интерполяция с адаптивным размером ядра: 1 - 2x2, 2 • 4x4, 3 - 8x8, 4 ■ 16x16, 5 - 32x32, о - опорные отсчеты, с - центральные отсчеты

Алгоритм интерполяции с адаптивным размером ядра является рекурсивным алгоритмом, в рамках которого центральный основной и побочные симметричные отсчеты вычисляются нисходящим образом в рамках адаптивного алгоритма центрального отсчета, причем направление предсказания определяется в целом для блока в соответствии с критерием минимизации суммарной ошибки интерполяции и передается кодовым словом длиной 2 бита на блок. Оставшиеся пикселы являются крайними и вычисляются по алгоритму «прямой крест», преимущества качественных характеристик которого показаны в разделе 1.

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

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

Сравнительные оценки алгоритмов интерполяции, представленные на рисунке 11, показали возможность увеличения коэффициента сжатия видеопоследовательности на 20% за счет алгоритмов интерполяции, и в среднем на 30% за счет предложенного алгоритма интерполяции.

М.+3 2СП4 Ы'12 4*121 І«» ШАНШЦиш

«6,1 змо

(»0 1«*)

I

I.

У"'

М-14 4к4,*!2 «ДО М.'Х&Алш

V

о

сж.

•"V.....

..................................

........——— ................................................

20,00 И,00 30,00 35,00 40,00 43,00 30,00 .«,00 «ДО ДдБ

Рисунок 11 Зависимости для алгоритмов интерполяции — адаптивной центрального отсчета, —УЗВМ без квантования, адаптивного размера ядра для последовательности «Теннис»

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

На рисунке 12 представлена модель кодера. Пунктирной стрелкой обозначена связь по данным блоков временной и пространственной модели.

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

Энтропийное кодирование осуществляется модифицированным кодом

Рисунок 12 Модель кодера

Блок анализатора кодирования (АК) представляет собой анализатор движения, описанный в разделе 3 с расширенным функционалом. На основании значений порога анализатора Т] и Тг , равных 4 и 14 соответственно, осуществляется выбор 215/30 режима. Анализатор кодирования формируется в соответствии с условием:

трвойтоскости, если <Т<и М-1< Т\ плоскоапькуба« га-дпх,есм Тг<М,<Т* • < 20-/ДО7, если М>т<

за-тхп, если ТХ<М1<Т, ЪО - ВКПП, емв Тг <М, < Т,

где

Л/, - О. у). . 0), . у)>• Л/, - ™*<т,<0. ). «¡4'7В' "Ри £ £ £ £ ¡фл0)-фл0|'

где с и с1 значения яркостей пикселов текущего и предыдущего кадров.

Двухмерные алгоритмы кодирования преобразованием реализуются строчно-столбцовым методом.

В ходе исследования было выявлено, что лучшие значения RD - характеристики показали значения порогов анализатора Т3 и Т4, равные 8 и 17.

Благодаря симметричности алгоритма, декодирование осуществляется аналогично в обратном направлении,

В ходе диссертационной работы были разработаны программные средства в среде разработки Visual С++. Блок-схема взаимодействия основных процедур разработанного приложения представлена на рисунке 13. Программные средства позволяют:

1. осуществлять основных кодирования;

2. отображать оценки и

выбор параметров

результаты компенсации

Рисунок 13 Блок-схема взаимодействия на основе стандарта Н.264.

движения в виде кадра, с обозначением блоков и векторов движения;

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

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

Экспериментальные результаты, представленные на рисунке 14, показали, что качество работы предложенного видеокомпрессора не уступает видеокомпрессору

[{.Кож «50

«О 3» 2Ю 210 140 70 0

.......>...............\_____________

\ ,..Л. ........ V ч

ч ч \ч

......"N..... ........VVS ......V-v min\\

... \ \ х .....Ч......X ч max ............"»».. ^ w v 1' • - - ' - ч Л * ч • <* 1 «Ч

1В 20 22 24 26 2S 30 32 34 К .'» 40 П,ДВ

18 20 23 24 26 28 1С 32

3S 38 40 D,aJi

Рис.14 Зависимости коэффициента сжатия и битрейта от качества для различных значений параметра квантования для видеокомпрессоров - - Н.264; - ■ -VP8 и —разработанного метода

Представленные зависимости приведены для двух крайних случаев для последовательностей наименьшей (min) и наибольшей (шах) динамичности.

Применение предложенного метода сжатия видеоданных позволило повысить качество восстановленной видеопоследовательности на 5%, коэффициент ее сжатия на 30% по сравнению с методом VP8, а также сократить необходимый битрейт на 30% и вычислительные затраты на 20%.

В заключении представлены основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. В результате исследования алгоритмов выбора блоков для сравнения предложен иерархический алгоритм выбора блоков для сравнения.

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

3. Предложен иерархический алгоритм быстрого преобразования Хартли на основе неразделимого ядра преобразования переменного размера.

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

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

6. Разработаны модель и метод сжатия видеоданных, основанные на сочетании предложенных алгоритмов.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Рубина, И. С, Анализ методов построения траектории движущихся объектов на основе сегментации видеоданных / И. С. Рубина // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. - 2011, - С. 127-132 (из перечня ВАК).

2. Рубина, И. С. Анализ сегментного подхода к компенсации движения в задачах детектирования движения и сжатия видеоданных в рамках натуралистических исследований / И. С. Рубина, А. С. Румянцев // Сборник научных трудов Sworld. Материалы международной научно-практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития '2012». - вып. 3. т. 4. - Одесса: Черноморье..- 2012. - С. 14-24 (из перечня ВАК).

3. Рубина, И, С, Исследование алгоритмов выбора опорных пикселов в задачах выделения сегментов кадра видеопоследовательности / И. С. Рубина,

А. Ю. Тропченко // Научно-технический журнал «Известия вузов. Приборостроение». - 2012. - С. 9-14 (из перечня ВАК).

4. Рубина, И, С. Исследование алгоритмов кодирования преобразованием в задачах сжатия кадров видеопоследовательности / И. С. Рубина, А, Ю. Тропченко II Научно-Технический журнал «Известия вузов. Приборостроение». - 2012. - С. 26-31 (из перечня ВАК).

5. Рубина, И. С. Анализ методов построения траектории движущихся объектов на основе сегментации видеоданных / И. С. Рубина // Сборник тезисов VII Всероссийской межвузовской конференции молодых ученых. - 2010. - вып. 1. -С. 24-25.

6. Рубина, И. С. Анализ проблем передачи видео в существующих системах видеоконференцсвязи / И. С. Рубина // Материалы XXXIX научной и учебно-методической конференции СПбГУ ИТМО. - 2010. - С. 32.

7. Рубина, И, С. Исследование алгоритмов выделения опорных точек в задачах классификации сегментов кадра видеопоследовательности / И. С. Рубина // Материалы XL научной и учебно-методической конференции СПбГУ ИТМО. -2011.-С. 32.

8. Рубина, И. С. Исследование методов устранения временной избыточности а перспективных стандартах сжатия видеоданных / И. С. Рубина // Сборник научно - исследовательских выпускных квалификационных работ студентов СПбГУ ИТМО.-2010.-С. 51-53.

9. Рубина, И. С. Исследование пространственно - временных алгоритмов компенсации движения / И. С. Рубина // Материалы XLI научной и учебно-методической конференции НИУ ИТМО. - 2012. - С. 32.

10. Рубина, И. С. Исследование способов повышения эффективности сжатия видео путем устранения временной избыточности сегментов кадра видеопоследовательности за счет решения апертурной проблемы / И. С. Рубина // Сборник «XVI Санкт-Петербургская ассамблея молодых ученых и специалистов». - 2011. - С. 144.

И, Рубина, И. С. Методы и алгоритмы построения траектории движущихся объектов на основе сегментации видеоданных / И, С. Рубина // Сборник «XV Санкт-Петербургская ассамблея молодых ученых и специалистов», - 2011. - С, 142.

12. Рубина, И. С. Устранение временной избыточности на основе сегментного подхода к решению задач оценки и компенсации движения / И. С. Рубина // Сборник тезисов VIII Всероссийской межвузовской конференции молодых ученых.-2011.-вып. 1.-С. 116-117.

13. Рубина, И, С. Устранение избыточности видеоданных на основе алгоритмов кодирования преобразованием / И. С. Рубина // Сборник тезисов I Всероссийского конгресса молодых ученых. - 2012. - вып. 1. - С. 48-49.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел.(812) 233 4669 Объем 1 у.п.л. Тираж 100 экз.

САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И

ОПТИКИ

РУБИНА ИРИНА СЕМЕНОВНА

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ И АЛГОРИТМОВ УСТРАНЕНИЯ ИЗБЫТОЧНОСТИ ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЕЙ НА ОСНОВЕ СЕГМЕНТАЦИИ ВИДЕОДАННЫХ

Специальность: 05.13.11 -Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

04201357460

На правах рукописи

Научный руководитель -доктор технических наук, профессор А. Ю. Тропченко

Диссертация на соискание ученой степени кандидата технических наук

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

Оглавление

Введение.............................................................................................5

1. Анализ современных методов сжатия видеопоследовательностей............11

1.1. Основные принципы сжатия видеоданных....................................11

1.1.1. Устранение избыточности видеосигнала. Основные этапы сжатия........................................................................................13

1.1.2. Подходы к оценке качества и степени сжатия видеоданных..............................................................................19

1.2. Современные технологии сжатия видеопоследовательностей............21

1.2.1. Алгоритмы временной модели видеокомпрессора.....................21

1.2.1.1. Анализ попиксельных алгоритмов компенсации движения................................................................................22

1.2.1.2. Анализ алгоритмов соотнесения признаков......................25

1.2.2. Алгоритмы пространственной модели видеокомпрессора...........27

1.2.2.1. Алгоритмы кодирования преобразованием в частотно-временном пространстве..............................................................................27

1.2.2.2. Алгоритмы интерполяции отсчетов сигнала....................32

1.2.3. Особенности современных алгоритмов сжатия........................33

1.3. Основные результаты и выводы.................................................39

2. Исследование алгоритмов на основе сегментного подхода к компенсации движения..........................................................................................42

2.1. Алгоритмы сегментации...........................................................42

2.1.1. Определение алгоритмов сегментации...................................42

2.1.2. Анализ алгоритмов сегментации..........................................46

2.2. Алгоритмы выбора блоков для сравнения.....................................47

2.2.1. Определение алгоритмов выбора блоков для сравнения.............47

2.2.2. Анализ алгоритмов выбора блоков для сравнения.....................51

2.3. Алгоритмы разделения..............................................................53

2.3.1. Алгоритмы разделения по признаку направления............................53

2.3.2. Алгоритмы разделения по признаку принадлежности большинства пикселов сегмента некоторой области.............................................54

2.3.2.1. Алгоритмы выделения опорных пикселов............................54

2.3.2.2. Алгоритм построения маски разделения..........................56

2.3.2.3. Алгоритм разделения в соответствии с маской.................58

2.3.3. Анализ алгоритмов разделения.............................................59

2.4. Основные результаты и выводы.................................................61

3. Исследование блочных алгоритмов кодирования преобразованием.........62

3.1. Сравнение двухмерных и трехмерных алгоритмов кодирования преобразованием..................................................................................62

3.2. Алгоритмы быстрого преобразования...........................................65

3.2.1. Быстрый трехмерный алгоритм преобразования Хартли.............65

3.2.2. Быстрый трехмерный алгоритм косинусного преобразования......76

3.3. Алгоритм с переменным размером ядра преобразования..................87

3.4. Анализ быстрых алгоритмов кодирования преобразованием.............87

3.5. Основные результаты и выводы.................................................89

4. Исследование алгоритмов интерполяции отсчетов сигнала....................91

4.1. Определение алгоритмов интерполяции отсчетов сигнала..................91

4.2. Анализ алгоритмов интерполяции отсчетов сигнала........................94

4.3. Основные результаты и выводы.................................................95

5. Модель кодека видеоданных...............................................................................96

5.1. Схема разработанного метода сжатия..........................................96

5.1.1. Временная модель............................................................97

5.1.2. Пространственная модель....................................................98

5.2. Программные средства кодека....................................................99

5.3. Анализ полученных результатов...............................................102

5.4. Основные результаты и выводы................................................106

Заключение......................................................................................107

Список литературы...........................................................................109

Список терминов..............................................................................117

Приложение 1. Документы, подтверждающие использование диссертационной

работы.............................................................................................119

Приложение 2. Порядок тестирования и характер тестовых последовательностей..........................................................................126

Введение

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

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

Существенный вклад в теорию сжатия видеоданных внесли Ватолин Д., Сэломон Д., Гонсалес Р., Ричардсон Я. и многие другие видные ученые и специалисты.

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

Выбранное направление работы основано на анализе современных методов сжатия видеоданных. К настоящему моменту разработан ряд стандартов сжатия

г"

видеоданных, на которых основывается подавляющее большинство схем кодирования/декодирования. Среди них особое место занимают MPEG-4 Visual (ISO/IEC 14496 Part 2) и Н.264 (ITU-E R264/ISO/ffiC 144496 Part 10), которые разрабатывались специалистами со всего мира и представляют собой доработку стандартов MPEG-1 и MPEG-2, позволяющую повысить степень сжатия при более высоком качестве принятых видеоданных. Кроме того, существует ряд свободно распространяемых кодеков типа WebM (VP8), которые в некоторых случаях достигают производительности эталонных стандартов кодирования.

Разработчики стандарта Н.264 поставили перед собой цель повысить эффективность сжатия. MPEG-4 Visual, в свою очередь нацелен на вариабельность, перейдя к объекту произвольной формы, обладающему гибкостью и адаптивностью. Таким образом, данные стандарты используют диаметрально противоположные подходы к сжатию видеоданных, что порождает определенный ряд недостатков, преодоление которых и задало направление диссертационной работы.

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

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

Задачами исследования являются:

1. Анализ алгоритмов построения траектории движущихся объектов на основе сегментации видеоданных.

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

нового алгоритма классификации сегментов по маске, получаемой на основе алгоритма выделения опорных пикселов.

3. Разработка алгоритмов сжатия на основе быстрых трехмерных алгоритмов кодирования преобразованием.

4. Разработка методов сжатия за счет новых алгоритмов интерполяции отсчетов сигнала и исследование их эффективности.

5. Построение модели кодека и программная реализация алгоритмов сжатия на основе предложенных подходов.

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

Программная реализация алгоритмов осуществлялась в среде Visual С++.

Научная новизна работы;

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

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

Г

3. Разработан быстрый трехмерный алгоритм нисходящего кодирования преобразованием с неразделимым ядром, основанный на дискретном преобразовании Хартли с переменным размером матрицы преобразования.

4. Разработан быстрый трехмерный алгоритм кодирования преобразованием, основанный на дискретном косинусном преобразовании с переменным размером матрицы преобразования.

5. Разработан алгоритм интерполяции отсчетов видеосигнала с переменным размером ядра.

6. Предложен метод сжатия видеоданных, основанный на сочетании предложенных алгоритмов, позволяющий повысить эффективность сжатия видеоданных.

Практическая ценность результатов работы заключается в следующем:

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

2. Разработанные быстрые алгоритмы многомерных преобразований Хартли и ДКП позволили сократить объем вычислительных затрат.

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

Основные результаты работы внедрены в учебном процессе НИУ ИТМО и проведенных в НИУ ИТМО НИР №610481 «Разработка методов и средств системотехнического проектирования информационных и управляющих

вычислительных систем с распределенной архитектурой» кафедры ВТ и НИР №211115 «Исследование и разработка методов искусственного интеллекта применительно к задаче построения обобщенного решения мультимодальной биометрической идентификации» кафедры РИС. Программное обеспечение, реализующее предложенные методы и алгоритмы прошло государственную регистрацию пакетов программ для ЭВМ (свидетельство №2013612402). Результаты исследования поддержаны грантами Правительства Санкт-Петербурга в 2010 и 2011 гг.( Приложение 1).

Основные положения, выносимые на защиту:

1. Алгоритм выделения объектов видеопоследовательности, основанный на определении опорных пикселов видеокадра.

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

3. Быстрый трехмерный алгоритм нисходящего кодирования преобразованием с неразделимым ядром, основанный на дискретном преобразовании Хартли с переменным размером матрицы преобразования.

4. Быстрый трехмерный алгоритм кодирования преобразованием, основанный на дискретном косинусном преобразовании с переменным размером матрицы преобразования.

5. Алгоритм интерполяции отсчетов видеосигнала с переменным размером ядра.

6. Метод сжатия видеоданных, основанный на сочетании предложенных алгоритмов.

Апробация результатов работы.

Результаты выполненных исследований были представлены на конференциях:

- XXXIX научной и учебно-методической конференции СПбГУ ИТМО (2010 г.).

- VII Всероссийской межвузовской конференции молодых ученых (2010 г.).

- XL научной и учебно-методической конференции СПбГУ ИТМО (2011 г.).

- VIII Всероссийской межвузовской конференции молодых ученых (2011 г.).

- XLI научной и учебно-методической конференции НИУ ИТМО (2012 г.).

- I Всероссийском конгрессе молодых ученых (2012 г.).

- Международной научно-практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития' 2012» (2012 г.).

Публикации. Основные результаты диссертационного исследования опубликованы в 13-ти научных публикациях общим объемом 42 страницы: в том числе в 4-х статьях в изданиях, включенных в Перечень ВАК, 10 работ опубликовано без соавторов.

Структура и объем работы. Диссертационная работа состоит из введения, основной части, содержащей 5 разделов, заключения, списка литературы, списка терминов и 2 приложений. В приложениях представлены порядок тестирования, характер тестовых последовательностей, а также документы подтверждающие использование диссертационной работы. Основной объем работы - 118 страниц. Объем приложений 26 страниц. Работа содержит 27 иллюстраций и 1 таблицу. Список литературы включает 78 библиографических источников.

Í

и

1. Анализ современных методов сжатия видеопоследовательностей

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

1.1. Основные принципы сжатия видеоданных

Говоря о системах обработки последовательностей изображений, необходимо сформулировать понятия временной и пространственной последовательности изображений. Эти понятия можно проиллюстрировать следующим примером. Рассмотрим сенсор в трехмерной системе координат. Он фиксирует информацию об окружающей среде, постепенно формируя изображения, а затем и их последовательность. Эта группа кадров может быть представлена функцией яркости 1(х,у^), где х и у - координаты на плоскости изображения, а t - координата по оси времени. Такой подход иллюстрирует представление о временной последовательности изображений. Рассматривая некоторое дополнение описанной модели, сенсор возможно не только перемещать но и поворачивать в трех измерениях. Необходимо отметить, что вращение сенсора вокруг оси не изменит результирующего изображения. И если предположить наличие бесконечной последовательности таких сенсоров в пространстве, мы сможем покрыть все возможные конфигурации во всем доступном пространстве. Именно в этом случае, каждое из полученных изображений можно рассматривать, как единицу пространственной последовательности изображений. С течением времени эти изображения формируют пространство изображения. Тогда осуществляется переход к функции четырех координат 1(х,у^, ?), где 5Б вектор ? фиксирует положение сенсора в трехмерном пространстве. Т.е. 3 = (х,у,г,р,у), где соответствующие координаты

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