| ||||||||||||||||
 | ||||||||||||||||
| ||||||||||||||||
 | ||||||||||||||||
| ||||||||||||||||
|
|
Фрактальное сжатие и восстановление видеоинформации в реальном масштабе времени Введение В статье исследуется возможность построения эффективных алгоритмов фрактального сжатия неподвижных и динамических изображений, а также рассматривается простой иерархический алгоритм, основанный на идее фрактального кодирования без поиска [6], применённой к кодированию последовательностей полутоновых кадров. Данная статья является логическим продолжением работы [5]. Компьютерные технологии в наше время играют всё более важную роль во многих областях человеческой жизни. Неотъемлемыми атрибутами современной вычислительной техники становятся программно-аппаратные средства цифровой обработки изображений. Высококачественные оцифрованные изображения, а тем более видеоинформация в несжатом виде, представляют собой огромные массивы данных, для хранения которых требуются значительные объёмы памяти ЭВМ, а для передачи по цифровым каналам связи - большая пропускная способность. Для уменьшения объёмов хранимых и передаваемых данных используются различные методы их сжатия. Для сжатия изображений обычно используют алгоритмы компрессии с потерями, когда часть информации безвозвратно теряется. При этом качество субъективного восприятия восстановленного затем изображения может и не ухудшиться благодаря некоторым особенностям человеческого глаза [3]. Существуют алгоритмы компрессии с потерями, позволяющие сжимать изображения более чем в 50 раз. В настоящее время актуальным становится также нахождение эффективных алгоритмов для передачи видеоинформации по обычным низкоскоростным каналам связи. Такие алгоритмы могут быть применены для организации видеоконференций через всемирную сеть Интернет, для создания видеотелефонного сервиса, а также для разработки новых систем цифрового телевидения. Представленный в статье подход демонстрирует применимость методов фрактальной компрессии и декомпрессии к сжатию трёхмерной видеоинформации в реальном времени и может быть развит до реальных приложений.
1. Фрактальное сжатие полутоновых изображений Различные методы сжатия изображений основываются на устранении тех или иных форм избыточности, в частности фрактальные методы рассматривают самоподобие как источник избыточности. Считается, что самоподобие является свойством почти всех природных объектов и их изображений [8], и, следовательно, устранение этой формы избыточности может значительно уменьшить объём данных, необходимых для описания природного объекта или его изображения. Фрактальное кодирование (сжатие) полутоновых изображений основано на гипотезе, согласно которой в любом изображении можно обнаружить локальное самоподобие различных его частей. Существующие алгоритмы фрактального сжатия, как правило, придерживаются следующей схемы кодирования [7]. Кодируемое изображение разбивается на множество неперекрывающихся блоков (ранговых областей), для каждого из которых, в пределах этого же изображения, ищется блок большего размера (домен), пикселы которого путём некоторого преобразования, задаваемого несколькими коэффициентами, переводились бы в пикселы ранговой области. При этом для поиска оптимального соответствия ранговых областей и доменов необходим полный перебор вариантов, что влечёт за собой значительные вычислительные затраты. Из преобразований, переводящих домены в ранговые области, формируется отображение, переводящее изображение в изображение. При этом кодом изображения будут являться местоположение и размеры ранговых областей, а также коэффициенты преобразований, описывающих самоподобие внутри изображения. Количество бит, необходимых для описания кода, будет существенно меньше количества бит, необходимых для описания исходного изображения. Коэффициентом сжатия называется отношение битового представления изображения к битовому представлению кода. В известных фрактальных методах сжатия изображений значение этого коэффициента может достигать 100 при приемлемом качестве восстановления. Для восстановления закодированного таким образом изображения используется принцип сжатых отображений [1], который гласит, что сжимающее отображение, действующее в полном метрическом пространстве, имеет единственную неподвижную точку. В нашем случае мы используем полное метрическое пространство полутоновых изображений с определённой на нём метрикой. Отображение, действующее на полном метрическом пространстве изображений, формируется из преобразований, переводящих домены в ранговые области. Неподвижной точкой такого отображения (при условии, что оно является сжимающим) будет восстановленное полутоновое изображение. Итак, пусть полутоновое изображение разбито на N ранговых областей Ri, для каждой из которых найден соответствующий домен Di и преобразование wi, задаваемое коэффициентами (ci1,ci2,…,ciK), такое что для каждого rÎ Ri существует dÎ Di такое что r=wi(d). Причём преобразования wi должны являться сжимающими, т.е. такими, что для всех dl,dkÎ Di выполняется
где 0 £ s < 1. Из N преобразований wi сформируем отображение W, переводящее изображения Fj в изображение Fj+1
Следует учесть, что преобразования wi действуют только на соответствующие домены Di изображения F. Доказано, что если преобразования wi являются сжимающими, то и отображение W также является сжимающим [2]. Для восстановления изображения, закодированного таким образом, нужно запустить итерационный процесс, используя в качестве стартового любое изображение F0 (соответствующего размера). Согласно принципу сжатых отображений [1], отображение W будет иметь единственную неподвижную точку отображения (аттрактор), такую что F’=W(F’). Эта точка пространства изображений и будет восстановленным изображением, которое повторяет исходное с некоторой точностью. Задача построения оптимального кода изображения при использовании фрактального сжатия, как уже было сказано, требует значительных вычислительных затрат. Простейший путь ускорения вычислений заключается в использовании различных алгоритмов сужения поиска или вообще отказе от поиска [6]. При использовании последнего алгоритма изображение разбивается на неперекрывающиеся квадратные блоки, каждый из которых разбит на четыре одинаковых квадратных подблока. Каждый блок является доменом для своих подблоков, а подблоки - ранговыми областями. Задача кодирования изображения в этом случае сводится к проверке подобия ранговой области домену, содержащему эту область. В случае отсутствия подобия соответствующий подблок снова разбивается на четыре квадратных “подподблока” и сам становится доменом для своих подблоков.
Процесс разбиений продолжается до тех пор, пока очередной подблок не будет состоять из одного пиксела. Детальное описание фрактальных методов сжатия можно найти в [2] и [3] (с.171-181), а также в зарубежных источниках [7,8,9]. 2. Преобразование, задаваемое одним коэффициентом Пусть ранговая область имеет размеры n ´ n пикселов, а соответствующий домен - 2n ´ 2n. Тогда для всех пикселов rij ранговой области запишем преобразование яркостей пикселов: rij = a´ (dij-<d>) + b, где <d>- среднее значение яркостей пикселов домена, а dij - яркость, взятая как усреднение яркости соответ-ствующего блока домена размером 2 ´ 2 пиксела [4,5]. Вычитание среднего значения из яркости пиксела означает исключение постоянной составляющей. Коэффициент a отвечает за изменение контрастности, а коэффициент b - за смещение по яркости. Яркость пиксела кодируется восемью битами, т.е. изменяется от 0 до 255. Будем рассматривать случай, когда квадратный домен содержит четыре квадратных блока - предполагаемые ранговые области. Для того чтобы упростить преобразование, зафиксируем коэффициент a. На рисунке 1 показаны несколько первых итераций восстановления изображения из кода, соответствующего четырём преобразованиям с коэффициентами b, равными 192, 48, 48 и 0, и фиксированным коэффициентом a=0.5.
Влияние значения коэффициента a на восстанавливаемое изображение можно проследить на рис.2, где показаны изображения, сгенерированные из того же кода, что и на рис.1, но с другими значениями коэффициента a. 3. Реализация трёхмерного фрактального сжатия последователь-ностей изображений Алгоритм фрактального сжатия без поиска применительно к трёхмерным видеоданным изложен в [5]. Здесь мы представим результаты разработки программ кодирования и декодирования, обрабатывающих несколько кадров в секунду на компьютере с процессором Pentium-60. Как и в [5], моделью видеопотока будет последовательность полутоновых кадров размером 64´ 64 пиксела. Алгоритм кодирования заключается в следующем. Видеопоток делится на пакеты по 16 кадров (общий размер пакета - 64 Кбайт). Далее пакет разбивается на 16 кубов, как показано на рис.3,б. Каждый куб разбивается на 8 подкубов одинакового размера (рис.3,а). Подкубы считаются ранговыми областями, которые проверяются на подобие домену - кубу, их содержащему.
Домены подвергаются кодированию с использованием описанного выше преобразования с фиксированным a=0.6. При таком значении a отсутствуют “ступенчатые” искажения яркости (см.рис.2). Единственный коэффициент b, кодирующий ранговую область, определяется очень просто - он равен средней яркости пикселов кодируемой ранговой области. Таким способом ранговая область кодируется не точно, а с некоторой погрешностью. Перед началом процесса кодирования задаётся порог M максимального отклонения яркости пикселов кодируемого и восстановленного изображения. Чем выше порог, тем хуже качество восстановленного изображения, но больше коэффициент сжатия (отношение объёма данных до кодирования и после кодирования). Если погрешность кодирования (максимальное отклонение яркости пикселов) ранговой области выше порога M, то ранговая область разбивается на 8 подкубов и становится для них доменом. Процесс разбиения останавливается при достижении размера подкуба 2´ 2´ 2 пиксела. В этом случае подкуб кодируется яркостью составляющих его пикселов. Кодирование одного пакета на компьютере с процессором Pentium-60 выполняется от 2 до 4 секунд (4-8 кадров в секунду). Процесс декодирования пакета кадров, так же как и в двумерном случае, является итерационным процессом. Взяв какие-либо стартовые значения яркостей пакета и произведя несколько итераций, можно увидеть, что восстановленный пакет будет с некоторой точностью, заданной порогом M, повторять закодированный. Декодирующая программа должна одновременно выполнять две функции: декодировать очередные 16 кадров и показывать восстанавливаемый фильм, “склеивая” куски фильма по 16 кадров так, чтобы пользователь не замечал границ пакетов.
На компьютере с процессором Pentium-60 время декодирования одного пакета кадров может варьироваться от 2 до 5 секунд (3-8 кадров в секунду), а скорость демонстрации, в то же время, должна оставаться постоянной. Разработанная программа декодирования и демонстрации создавалась для ОС Windows-95, которая обладает развитыми возможностями по работе с параллельными цепочками программы и по синхронизации параллельных процессов. Программа запускает два параллельных процесса: процесс А и процесс В (рис.4). Процесс А выполняет чтение из файла и декодирование очередного пакета, а процесс В демонстрирует уже декодированные кадры. Синхронизация процессов производится следующим образом. Как показано на рис.4, в начале работы программы процесс А загружает и декодирует первый пакет, производя 5 итераций. В это же время процесс В ожидает окончания декодирования. В момент окончания декодирования запоминается промежуток времени T0 , в течение которого декодировался первый пакет. Исходя из значения T0, вычисляют длительность кванта времени, который выделяется затем одному кадру для демонстрации tk=T0/16. После этого запускается процесс В, который с периодом tk демонстрирует декодированные кадры. В то же время процесс А считывает и декодирует следующий пакет. По окончании “фильма”, когда все пакеты исчерпаны и процесс В начинает показывать кадры из последнего пакета, процесс А может снова начать считывать первый пакет “фильма”. Таким образом, “фильм” замыкается в кольцо без заметных задержек между последним и первым кадрами. Скорость воспроизведения зависит от производительности компьютера и размера окна, но программно ограничена значением в 16 кадров в секунду. При тестировании на компьютере с процессором Pentium-60 скорость смены кадров находилась в пределах 3-5 кадров в секунду.
Недостатком этого алгоритма синхронизации является необходимость того, чтобы время декодирования первого пакета было больше времени декодирования каждого из последующих пакетов. В таблице 1 представлена зависимость скорости кодирования, скорости декодирования и коэффициента сжатия от порога M. Приемлемое качество достигается при значениях M£ 32. В дальнейшем наша работа будет сконцентрирована на оптимизации применённых алгоритмов и на использовании изображений с большим разрешением.
Табл. 1. Зависимость результатов кодирования от порога M
Библиографический список
|
|
|
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
|