Книги по разным темам Pages:     | 1 |   ...   | 10 | 11 | 12 | 13 | 14 |   ...   | 82 |

XII-th International Conference "Knowledge - Dialogue - Solution" Технологии компрессии графической информации По отношению к файловой По форме представления структуре представления данных графической информации Сжатие, включенное Комбинированные Сжатия метафайловые векторная файла в структуру файла формы целиком CDR DXF ESP Вейвлет - CGM CLP ZIP RAR программная преобразования текстовая мультимедийная PPM растровая WIF EZW BMP По полноте сохранения сжимаемой информации GIF LZ LZC IMG TIFF LWZ С семантической коррекцией Без потерь С потерями сжимаемой информации KWE RLE алгоритмические изображения Алгоритм Хаффмана Алгоритмы последовательного PCX Рисунок- Текстсканирования Со сжатием текст- рисунокрисунок текст LOCO-I Алгоритмы на основе РисунокС повторением MLP преобразований рисунок FELICS CALIC JPEG SPIHT По виду преобразования По виду семантической компрессии спектровыделяющие MTF BWT аннотирование конспектирование реферирование графическая аналитическая По виду кодирования арифметическое ранжированное ассоциативное квазиарифметическое префиксное Рис.3 Общая классификация технологий сжатия графической информации Neural and Growing Networks Представление сцены изображения в виде программных файлов как на языках программирования, так и языках инструкций графических пакетов, позволяет в значительной степени сократить объем информации об изображении, поскольку такой подход предполагает применение иной формы описания изображения и допускает использование в графических файлах программных процедур. Однако при этом обязателен компилятор, или наличие соответствующего графического пакета. Для более сложных изображений требуется полный цикл повторного создания изображения.

По отношению к файловой структуре представления данных анализируемые технологии выполняют сжатие сразу всего файла целиком или сжатие, включенное в структуру файла; а также комбинированные формы. Форматы, в которых сжатие является частью структуры файла, менее зависимы при их дальнейшем использовании. Полностью сжатый файл обычно нельзя использовать до тех пор, пока он не будет восстановлен до исходного состояния. Поэтому, в дальнейшем, сжатый формат растровых изображений декомпрессируется соответствующей совместимой программой. Наиболее распространены форматы сжатия ZIP и RAR, которые используются для сжатия как символьной, так и графической информации. Вейвлет-компрессия графических данных, которую отнесем к технологиям по виду преобразований, заключается в сжатии всего изображения целиком до так называемых WIF-файлов (Wavelet Image File) с целью сохранения временных и частотных характеристик сигналов. Основная идея лифтинг-преобразований, называемых также вейвлетами второго поколения, выражается в том, что при каждой операции должна изменяться только одна составляющая, поэтому, например, для построения обратного преобразования достаточно выполнить зеркальное отображение прямого преобразования и добавить инвертирование сигнала там, где это нужно. Алгоритм сжатия EZW (Embedded Zerotree Wavelet) предполагает простое отбрасывание коэффициентов со значениями, меньшими некоторой величины. Не намного более сложный в вычислительном отношении алгоритм SPIHT (Set Partitioning in Hierarchical Trees) дает гораздо лучшие результаты компрессии.

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

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

В работе алгоритмов на основе последовательного сканирования, ориентированных на сжатие изображений без потерь, можно выделить следующие фазы: предсказание, моделирование ошибки и кодирование, причем предсказание значения следующего пикселя производится на основе значений уже закодированных соседних пикселей. В основу технологий сжатия по ключевым словам KWE (Key Word Encoding) положен принцип кодирования лексических единиц, например обычных слов, группами байт фиксированной длины. Результат такого кодирования помещается в специальном словаре. Технология Лемпеля-Зива-Велча (LZW), которая является модификацией технологии Лемпеля-Зива (LZ), основана на поиске и сохранении шаблонов внутри заданной структуры. Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения на коды фиксированной длины.

Сжатие по этой технологии выполняет растровый формат TIFF, который поддерживает большое количество алгоритмов сжатия для различных типов изображений. В растровом формате GIF изображение рассматривается как одномерная последовательность пикселей, которые кодируются по строкам с использованием алгоритма LZC (модификация алгоритма LZW). Формат рассчитан на изображения с индексными цветами и обладает более высокой степенью сжатия, чем формат PCX. Существуют модификации этого формата, которые отличаются количеством поддерживаемых типов блоков расширений, в том числе анимации. В целом алгоритмы KWE выполняют сжатие без потерь информации, и наиболее эффективны для текстовых данных больших объемов, но из-за необходимости создания и сохранения словаря малоэффективны для файлов небольших размеров. В основе алгоритма Хаффмана, также производящего сжатие без потерь информации, лежит идея кодирования битовыми группами. После проведения частотного анализа входной последовательности данных, то есть XII-th International Conference "Knowledge - Dialogue - Solution" определения частоты вхождения каждого символа, который в ней встречается, символы сортируются по уменьшению этой частоты. Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Алгоритм RLE (Run-Length Encoding) основан на выявлении повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения, поэтому он дает лучший эффект сжатия при большей длине повторяющейся последовательности данных. Следовательно, алгоритм RLE более эффективен при сжатии графических данных (в особенности для однотонных изображений). Кодирование по алгоритму RLE поддерживает графический формат PCX.

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

Типовая схема алгоритма такова - преобразование, квантизация, моделирование преобразованных коэффициентов, кодирование. Существуют два подхода к выполнению преобразований. Первый выражается в многократном выполнении преобразования, отделяющего самую высокочастотную составляющую изображения. Второй подход заключается в выполнении. преобразования, результатом которого является спектр изображения. Высокая вычислительная сложность таких преобразований не позволяет применять их для фрагментов изображения большого размера. Тогда при сжатии с потерями, например в формате JPEG, происходит отбрасывание части данных исходного изображения. При этом используются особенности чувствительности нашего зрения по восприятию изменений яркости, цвета или тона. Сначала изображение разделяется на яркостную и две цветовые составляющие. Яркостная составляющая более важна при восприятии изображения человеческим глазом, поэтому ее следует сжимать с лучшим качеством. Затем эти составляющие разбиваются на квадраты размером 8х8 пикселей, и для каждого из которых выполняется дискретное косинус-преобразование Фурье. После этого производится квантизация результатов и кодирование. Для кодирования коэффициентов используется кодирование Хаффмана с фиксированными таблицами, как разновидность префиксного кодирования, либо арифметическое кодирование. По виду кодирования выделим: префиксное, арифметическое, ранжированное, ассоциативное и квазиарифметическое кодирование.

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

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

превосходящей алгоритмы сжатия текстовых естественно-языковых или программных структурных описаний. Вторая схема применима для случая предметной области, в которой сжатие естественноязыковых текстов и программных формализмов выполняется лучше, чем компрессия графических представлений информационного материала. Третья схема предполагает семантическое сжатие непосредственно графических изображений без промежуточных вспомогательных текстовых форм. К этой же схеме примыкает задача понимания графических языков: рисунков, чертежей, иллюстраций, фотоизображений и др. Такие схемы допускают несколько вариантов реализации. В В - РАН [3] построена система ТЕКРИС - генерации рисунков на основе текстов, использующая схему: анализ текста - синтез графического образа.

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

Neural and Growing Networks В качестве примера реализации конспектирования естественно-языковых текстов приведем программу КОНСПЕКТ[4], которая передает смысл, но не восстанавливает исходный текст после проведенного сжатия. При работе этой программы фразы исходного текста подвергаются синтактико-семантическому анализу с целью отбора полносоставных предложений. После этого на основе онтологии ассоциаций осуществляется тематический анализ текста. Онтологией ассоциаций является словарь терминов, в котором термины индексируются наборами ассоциативных признаков, обозначающих ассоциации понятий. В результате работы программы КОНСПЕКТ формируется обобщенный текст, который по объему и связности близок к сложившимся представлениям о свойствах конспектов. Другим вариантом является использование словарного комплекса РУСЛАН [5] как инструмента сжатия содержания текста.

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

Графический объект можно считать определенным только тогда, когда зафиксирована его форма для визуализации, проставлены размеры и выполнена пространственная ориентация и расположение[6].

Одной из первых программ, которая в интерактивном режиме могла воспринимать взаимное расположение блоков разных форм и цветов и производить их описание, является программа Винограда SHRDLU[7], однако ее разработчикам не удалось решить задачу абстрагирования. Семантическое сжатие непосредственно графического изображения также близко семантическому масштабированию. Отличие лишь в том, что при семантическом сжатии сокращенная информация опускается или видоизменяется, а при семантическом масштабировании она временно исключается при увеличении масштаба, но затем, при уменьшении масштаба, вновь возвращается. При декомпрессии также возможен семантический аспект, т.е. декомпрессия изображения с раскрытием изображаемой темы и ее дополнении информацией из базы знаний или базы данных, например, в самом простом варианте, списком литературы. Ряд алгоритмов компьютерной графики [8,9] используют генерирование семейств отрезков прямых, окружностей, эллипсов, парабол и гипербол, и допускают применение сжатия и повторения. Выигрыш от применения метода повторений тем больше, чем длиннее генерируемый отрезок и чем больше коэффициент повторения. Для каждого квадранта с учетом асимптотических ветвей и симметрии определяются последовательности, по которым вычисляются точки, наиболее близко расположенные к проектируемой кривой линии и соответствующим образом распределяется яркость между выбранной алгоритмически основной точкой и вспомогательной, выбор которой зависит от расстояния относительно кривой. Такие алгоритмы применимы при разработке программ семантической декомпрессии.

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

Pages:     | 1 |   ...   | 10 | 11 | 12 | 13 | 14 |   ...   | 82 |    Книги по разным темам