Добавлен: 26.06.2023
Просмотров: 92
Скачиваний: 3
Многопозиционные коды, алфавит которых состоит из большого числа символов, пока не нашли широкого применения в информационных системах.
По форме представления сигнала в канале передачи данных различают последовательные и параллельные коды. В последовательных кодах элементарные сигналы, составляющие кодовую комбинацию, посылаются в канале передачи последовательно во времени. Как правило, они разделены между собой определенным временным интервалом.
В параллельных кодах элементарные сигналы посылаются одновременно по нескольким электрическим цепям, число которых соответствует количеству элементов кода.
Параллельная форма представления кода, хотя и связана с меньшей затратой времени для передачи сообщений, используется для передачи информации по каналу связи редко, так как требует значительных материальных затрат на многопроводные линии связи. Практически параллельная форма кода при передаче информации по однопроводной линии связи используется лишь в тех случаях, когда в качестве импульсного признака применяется частота и на приемной стороне элементы кодовой комбинации можно легко разделить с помощью частотных фильтров.
Параллельная форма представления кода часто используется при преобразовании аналоговых величин в код и обратных преобразованиях, в устройствах памяти, регистрации, при логической и математической обработке информации, когда важную роль играет быстродействие.
В зависимости от возможности обнаружения и исправления ошибок в полученных по каналу связи кодах различают простые и корректирующие коды. В простых кодах все возможные кодовые комбинации используются непосредственно для передачи информации и ошибка в приеме хотя бы одного элемента кодовой комбинации приводит к неправильной регистрации передаваемого сообщения. В простых равномерных кодах превращение одного символа комбинации в другой, например 1 в 0 или 0 в 1, приводит к появлению новой комбинации, т.е. к ошибке.
Корректирующие коды - это коды, позволяющие по имеющейся в кодовой комбинации избыточности обнаруживать и исправлять определённые ошибки, появление которых приводит к образованию ошибочных или запрещенных комбинаций. Применяются при передаче и обработке информации в вычислительной технике, телеграфии, телемеханике и технике связи, где возможны искажения сигнала в результате действия различного рода помех. Кодовые слова корректирующих кодов содержат информационные и проверочные разряды (символы). В процессе кодирования при передаче информации из информационных разрядов в соответствии с определёнными для каждого корректирующего кода правилами формируются дополнительные символы — проверочные разряды. При декодировании из принятых кодовых слов по тем же правилам вновь формируют проверочные разряды и сравнивают их с принятыми; если они не совпадают, значит при передаче произошла ошибка. Существуют коды, обнаруживающие факт искажения сообщения, и коды, исправляющие ошибки, т.е. такие, с помощью которых можно восстановить первичную информацию.
Исходя из числа одновременно кодируемых символов первичного алфавита кодирование классифицируют на алфавитное и блочное. При алфавитном кодировании передаваемое сообщение представляет собой последовательность кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, при которых кодовый знак относится сразу к нескольким буквам первичного алфавита (будем называть такую комбинацию блоком) или даже к целому слову первичного языка.
Кодирование блоков понижает избыточность. Применение блочного метода кодирования имеет свои недостатки. Во-первых, необходимо хранить огромную кодовую таблицу и постоянно к ней обращаться при кодировании и декодировании, что замедлит работу и потребует значительных ресурсов памяти. Во-вторых, помимо основных слов разговорный язык содержит много производных от них, например, падежи существительных в русском языке или глагольные формы в английском; в данном способе кодирования им всем нужно присвоить свои коды, что приведет к увеличению кодовой таблицы еще в несколько раз. В-третьих, возникает проблема согласования (стандартизации) этих громадных таблиц, что непросто. Наконец, в-четвертых, алфавитное кодирование имеет то преимущество, что буквами можно закодировать любое слово, а при кодировании слов – можно использовать только имеющийся словарный запас.
2 Кодирование при сжатии данных изображений: вейвлет-кодирование
Поскольку цифровые файлы изображений занимают значительно место, обычной альтернативой является хранение изображений в сжатой форме, используя форматы JPEG, JPEG2000, ECW и MrSID.
Прототип технологии MrSID был разработан в Национальной Лаборатории Лос-Аламоса в 1992 году. Последовавшая коммерческая версия технологии от компании LizardTech была названа MrSID Generation 2 (MG2) форматом и внедрена в 1998 г. Следующая версия, формат MrSID Generation 3 (MG3), внедрённый в 2002 г., предоставлял улучшенное качество изображения и ключевые функции, такие как кодирование без потерь. В 2010 году LizardTech представил новый формат – MrSID Generation 4 (MG4). В нём поддерживаются мультиспектральные изображения, альфа диапазоны, а также есть многие другие улучшения.
Формат JPEG2000 развивался не столь динамично. Когда в середине 90-х стало ясно, что возможностей JPEG недостаточно для некоторых применений, М. Болиек в 1996 году предложил создать новый стандарт. В 2000-м году была выпущена первая часть. Стандарт до конца еще не разработан, сейчас, по данным ISO, находится в разработке 14-я часть, «Структурное XML-представление и справочная информация». В настоящее время формат в основном используется для хранения кадров в видеопотоках и для хранения фотографий в базах данных.
Формат ECW, как и MrSID, специализирован для воздушных и космических фотографий. Он разработан организацией Earth Resource Mapping, которая ныне является частью подразделения ERDAS компании Intergraph.
В 1998 году основатель компании Стюарт Никсон и два программиста исследовали скоростную транспортировку терабайтовых изображений через интернет, результатом этих изысканий стало два продукта – Image Web Server и ECW (Enhanced Compression Wavelet). В отличие от разработчиков MrSID, которые делали упор на эффективность сжатия, разработчики ECW делали упор на производительность преобразований.
Существует три вида сжатия и меры потери качества: несжатый без потерь; сжатый без потерь; а также сжатый с потерями. Все эти методы работают, но никакими средствами невозможно предоставить высокие степени сжатия, высокое качества изображения и высокую производительность. Чтобы хорошо выполнить сжатие в реальном мире алгоритмы должны быть разработаны для определенных видов данных.
Массив чисел, представляющих пикселы изображения, можно представить несколькими способами:
1. Используя метод усреднения. При этом вычисляется среднее значение пары каждых соседних чисел.
2. В методе кодирования последовательности заменяется последовательность идентичных значений всего двумя числами, самим значением и количеством повторов.
3. С помощью словарного метода, отмечаются общие последовательности значений и заменяются специальными ключами, сохраняя последовательности и ассоциированные ключи в словаре в начале файла. Здесь снижается количество актуальных данных, но необходимо также хранить словарь.
Благодаря этим упрощённым примерам можно сделать некоторые наблюдения. Во-первых, кодирование и декодирование может занять некоторое время. Во-вторых, есть возможность потерять данные: в примере с «усреднением» мы потеряли данные в операции округления и мы можем никогда не получить их обратно.
Технологии MrSID, ECW и JPEG2000 для кодирования данных полагаются на два ключевых алгоритма. Первый, вейвлет, используется чтобы изменить данные в форму, которая служит для представления данных на нескольких разрешениях. Вейвлет-трансформация это математическая трансформация данных, которая, как правило, не вносит потерь. Следующий шаг – закодировать полученные данные в новое представление, которое значительно компактнее оригинала, но по-прежнему может не вносить потерь; опционально, этот шаг может также снижать точность данных для еще большего сохранения пространства.
С английского слово wavelet дословно переводится как «небольшая волна (рябь)». В различных переводах иностранных статей используют также термины: «волночка», «всплесковая функция», «всплеск» и др.
Вейвлет-преобразование одномерного сигнала – это его представление в виде обобщенного ряда или интеграла Фурье по системе базисных функций
, (1)
сконструированных из материнского (исходного) вейвлета . Этот вейвлет обладает определенными свойствами за счет операций сдвига во времени (b) и изменения временного масштаба (a). Множитель () обеспечивает независимость нормы этих функций от масштабирующего числа a. Таким образом, для заданных значений параметров a и b функция и есть вейвлет, порождаемый материнским вейвлетом .
Рисунок 1 – Вейвлет-преобразование
Иными словами, представим список из 4 чисел: {2, 6, 14, 6}. Путем попарного усреднения мы можем снизить его до списка «второго уровня» из двух чисел {4, 10}, и списка «различий» второго уровня, {+2, -4}. Выполняя ту же операцию снова на списке {4, 10}, мы получаем список третьего уровня {7} и список различий третьего уровня {+3}. Это показано на Рисунке 1.
Эти три списка, а также два связанных списка различий, используются для представления оригинального списка из 4-х чисел на трех уровнях разрешения. Заметьте что только последний одно-элементный список {7}и два списка различий {+3} и {+2, -4} требуются, чтобы выполнить обратную операцию и восстановить оригинальный входной список. Только с помощью этих трех списков, мы можем восстановить второй уровень: список третьего уровня {7} и список различий {+3} вернет {4, 10} (поскольку 7 – 3 = 4 и 7 + 3 = 10). Список второго уровня {4, 10} и список различий второго уровня {+2, -4} вернет, в свою очередь, оригинальный список (4-2, 4+2, 10-(-4), 10+(-4)).
Хотя на практике детали несколько сложнее, принцип для графических данных именно такой. Используя одномерный вейвлет для обоих измерений двумерного массива пиксельных данных, мы разбиваем рисунок на пирамиду рисунков, в которой каждый уровень по ширине и высоте равен половине предыдущего, и включаем соответствующий список различий. Это процесс математически не вносит потерь. Значимое сжатие не достигнуто, но мы имеем лучшее представление данных, поскольку они по своей сути отражают данные на многих уровнях разрешения.
Но даже при отношении 20:1, сжатие данных размером 20 Гб даст очень большой (1Гб) файл. Пользователи часто переживают по поводу работы с файлами такого размера, поскольку многие приложения GIS будут пытаться заглотить файл целиком, приводя к избыточным и подчас фатальным запросам к ЦП и ОЗУ. Два аспекта всех трёх форматов решают эту проблему.
Во-первых, используемый метод кодирования создает множество разрешений изображения внутри сгенерированного файла. По эффекту это похоже на создание «пирамид» рисунков, но никаких дополнительных файлов для всех уровней пирамиды не создаётся. Приложения могут быть инструктированы извлекать и обрабатывать только уровень нужной детализации, без декодирования целого полноразмерного изображения.
В дополнение к возможности запросов только желаемого уровня разрешения, технологии предоставляет выборочную распаковку так называемых «зон интереса», которая позволяет приложениям запрашивать и декодировать только интересующий вид (географическую область) из файла. Некоторые другие форматы файлов и методы сжатия, наоборот, требуют полное декодирование файла, даже если только маленькая часть его будет показана на экране.
При этом, так как форматы MrSID и ECW являются геопространственными форматами, файлы также содержат геопространственную информацию, такую как систему координат, географическое пространство (угловые точки) изображения, и разрешение в точках.
В формате MrSID метаданные основаны на хорошо известной схеме меток GeoTIFF. При выполнении операций перепроецирования или одного из оптимизационных этапов, описанных ранее, метаданные обновляются, чтобы отразить параметры производного изображения: при уменьшении масштаба, например, метаданные о разрешении соответственно обновляются.
Формат JPEG2000 универсальный, ног в нѐм есть возможность хранения произвольных XML-тегов. Для стандартизации структуры этих тегов под геоинформационные нужды Open Geospatial Consortium разработал специальный Географический Язык Разметки – (Geography Markup Language, GML). Это средство позволяет сохранять в файле большое количество метаинформации. Помимо того, что можно сохранять в MrSID и ECW, также можно на самом рисунке делать метки, подписанные текстом или дополнительным изображением, например, фотографией места. Нужно только учесть, что XML-формат избыточен по своей сути, что чревато увеличением занимаемого места.
Как мы видим, все три формата являются достойными конкурентами друг для друга. В выборе какого-либо конкретного нужно опираться на следующие моменты:
1. с какими данными приходится работать: есть ли уже база изображений, в каком она формате, есть ли дополнительные диапазоны (такие как, например, инфракрасный), характер метаданных;
2. также важно принять решение, что важнее – степени сжатия или же производительность, так как еще в начале статьи было сказано, что никакими способами не получить одновременно и высокую степень сжатия и высокую производительность;