ФРАКТАЛЬНОЕ КОДИРОВАНИЕ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ, ПРЕДСТАВЛЕННЫХ В ВИДЕ НАБОРА БИТОВЫХ СЕЧЕНИЙ
Касаткин А.С.
Вятский государственный университет, кафедра радиоэлектронных средств
610000, Киров, ул. Московская д.36, т. (8332)32-16-44, ф. (8332)62-65-78,
е-mail: res@riac.ru, i_trubin@mail.ru
В данной работе проведено исследование возможности использования корреляции между битовыми сечениями цифрового
полутонового изображения для реализации фрактального алгоритма кодирования.
Целью исследования является ответ на вопрос о возможности использования данного алгоритма для повышения
степени компрессии полутонового изображения.
Исследование, развитие и внедрение цифровых методов обработки изображений в различные области науки и
техники вынуждает разработчиков искать новые способы повышения эффективности хранения данных.
В настоящее время существуют разнообразные алгоритмы сжатия, использующие избыточность полутоновых изображений,
необходимую для качественного восприятия последних зрителем. Эффективность известных алгоритмов резко отличается.
В качестве критериев оценки эффективности алгоритмов сжатия обычно используют следующие: коэффициент
компрессии, потери при сжатии/восстановлении (наличие артефактов), время кодирования, время
декодирования исходного изображения.
Полутоновое изображение представляет собой матрицу пикселей, каждый пиксель содержит информацию об
яркостной составляющей сигнала. При рассмотрении изображения на двумерной плоскости следует выделить наличие в нем
областей равной или примерно равной яркости. Простейшие алгоритмы кодирования, такие как RLE, LZ, не
выделяют эти геометрические (пространственные) области, рассматривая изображение в виде длинной развернутой
строки, и поэтому не могут в полной мере использовать все особенности изображения в процессе сжатия,
обеспечивая невысокий коэффициент компрессии. Наиболее близко к решению данной проблемы подошли
разработчики фрактальных алгоритмов кодирования полутоновых изображений.
Фрактальные алгоритмы обеспечивают достаточно большие коэффициенты компрессии при хорошем восстановлении
изображения на приемной стороне. Недостатком данных алгоритмов является длительное время кодирования, которое
определяется поиском структуры (аттрактора) в изображении. Существенным толчком к развитию фрактального
кодирования полутоновых изображений послужило обоснование возможности использования системы итерируемых
кусочно-определенных функций (PIFS) для кодирования полутоновых изображений, полученных не искусственным
(компьютерное моделирование) путем.
Работа алгоритма подробно описана в [1] и происходит следующим образом: исходное изображение разбивается на доменные
(опорные) и ранговые (восстанавливаемые) растровые области; на основании определенного набора функциональных
преобразований для каждого рангового блока производится поиск подходящего доменного блока; скорость и качество кодирования
можно регулировать введением пороговых значений соответствия при сравнении ранговых и доменных областей. С учетом того,
что в процессе поиска лучшего доменного блока сравниваются растровые области, подходящий блок
должен обладать соответствующей яркостью и контрастностью, это снижает скорость кодирования и увеличивает
объем закодированного файла.
Исследуемый комплексный алгоритм кодирования полутонового изображения
Чтобы избежать подобных затруднений можно предложить альтернативный комплексный алгоритм, основанный на представлении
цифрового полутонового изображения в виде набора битовых сечений. Для этого исходное изображение равномерно квантуют
обычно на восемь битовых сечений, возможно также применение неравномерного квантования, что позволит снизить
необходимое количество битовых сечений для представления изображения. Соседние битовые сечения имеют похожие области,
часто области просто являются инверсными копиями друг друга. Особенно четко данный момент
прослеживается в старших битовых сечениях, обладающих высокой пространственной корреляцией, как по строкам, так и по
столбцам изображения. По мере снижения разрядности битового сечения средняя протяженность областей одинаковой яркости
также снижается. Сильная корреляционная связь между соседними битовыми сечениями позволяет значительно упростить
процедуру поиска [2], что увеличивает компрессию данных и повышает скорость кодирования. В данном случае в качестве
доменных блоков будут выступать области старшего (восьмого) битового сечения, т.к. пространственная корреляция в нем
обычно имеет наибольшее значение. Это сечение будет являться опорным, оно непосредственно передается на приемную
сторону без кодирования. Все остальные сечения разбиваются на ранговые блоки, для которых производится в соответствии с
алгоритмом поиск наилучшего доменного блока. С уменьшением разрядности битового сечения степень подобия сечений
значительно падает, поэтому процесс кодирования ограничим только старшими четырьмя битами.
В процессе сравнения ранговая область претерпевает различные функциональные преобразования, позволяющие достичь
схожести на начальных этапах кодирования. Набор и число этих функциональных преобразований позволяет
регулировать скорость кодирования с одной стороны и степень компрессии изображения с другой. В данной работе для
простоты вычислений битовые сечения исходного изображения разбивались на ранговые и доменные области квадратной формы,
кратной степени двойки, в качестве функциональных преобразований использовались инверсия и поворот области.
Использование бинарных изображений значительно упрощает процесс сравнения по сравнению с работой алгоритма с полутоновыми
областями, т.к. сигнал может принимать лишь два значения, и данный алгоритм может быть легко аппаратно
реализован. Качество восстановленного изображения будет определяться степенью схожести рангового и
доменного блоков. Регулировка этого процесса производится путем заранее выбранного порогового значения
соответствия. Если в процессе перебора всех доменных блоков подходящий так и не был найден, ранговый блок разбивается
на части, каждая из которых вновь сравнивается с доменными областями. Данный процесс продолжается до
достижения необходимого порогового уровня соответствия. Меняя это значение можно управлять как временем кодирования,
так и качеством восстановленного изображения. Большая часть наиболее распространенных алгоритмов сжатия применяет не одну,
а несколько методов сжатия, что позволяет подстроиться под характеристики кодируемого изображения.
С этой же целью файл, полученный после непосредственно фрактального алгоритма кодирования, дополнительно
сжимается архиватором WINZIP. Степень компрессии при этом достигается значительная, т.к. файл после фрактального этапа
кодирования содержит повторяющуюся структуру, эффективно кодируемую, например, алгоритмами Хаффмана или LZ.
Результаты работы алгоритма
Изображение кодировалось с уровнем доменных областей равным четырем и пороговым уровнем соответствия
равным 99%. Восстановленное изображение содержит всего четыре старших битовых сечения, этим объясняется сильное
различие в уровне яркости изображений. Однако следует отметить, что восстановленное изображение
достаточно точно передает общее содержание картинки, расхождение объясняется наличием в исходном
изображении множества мелких деталей, в основном передаваемых в младших битовых сечениях. Увеличение
корреляционной связи, как между битовыми сечениями, так и в самих сечениях по строкам и столбцам, значительно
повышает эффективность работы алгоритма. Для каждого изображения существуют оптимальные параметры алгоритма
кодирования, обеспечивающие компромисс между степенью компрессии и качеством восстановленного изображения. Субъективная
оценка также указывает на наличие оптимальных в смысле качество/сжатие параметров алгоритма. Выбор
параметров следует производить на основе предварительной оценки изображения. Оценка может производиться
по коэффициенту корреляции по строкам и столбцам в бинарном сечении изображения. Эта оценка также может использоваться и
для анализа количества кодируемых битовых сечений, которое может быть меньше или больше четырех, что позволит
определить количественный параметр, определяющий качество/сжатие кодируемого изображения.
Выводы
Таким образом, исходный алгоритм можно успешно применять для сжатия полутоновых изображений.
Полученные коэффициенты компрессии (5-25 раз) говорят о необходимости дальнейших исследований в этой области.
Так как алгоритм работает с бинарными сигналами, то его легко реализовать аппаратно. Параметры алгоритма позволяют
регулировать и скорость работы алгоритма и качество восстановления изображения в зависимости от требований
пользователя.
В данной работе не производилась оценка скорости работы алгоритма, поскольку во всех случаях производился поиск
наилучшего соответствия доменного и рангового блоков. В работе не производилась оценка с существующими
алгоритмами кодирования, такими как jpeg, поскольку, кодирование только старших битовых сечений приводит к достаточно
небольшому отношению сигнал/шум (PSNR). Повысить отношение сигнал/шум можно путем внесения в
младшие битовые сечения коррелированного шума, параметры которого будут определяться на основе корреляции
между битовыми сечениями изображения. Кроме того, повышение степени сжатия можно добиться путем оптимизации
структуры самого кодируемого файла и дополнительного кодирования опорного сечения [3].
Литература