Удаленная обработка данных на суперкомпьютере при решении задачи автоматизированной интерпретации аэрокосмических изображений
Высокопроизводительные вычисления в обработке данных дистанционного зондирования Земли. Классификация аэрокосмических изображений. Способы удаленного доступа к суперкомпьютеру. Сжатие без потерь и с потерями. Программное обеспечение системы сжатия.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 28.09.2011 |
| Размер файла | 2,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
УДАЛЕННАЯ ОБРАБОТКА ДАННЫХ НА СУПЕРКОМПЬЮТЕРЕ ПРИ РЕШЕНИИ ЗАДАЧИ АВТОМАТИЗИРОВАННОЙ ИНТЕРПРЕТАЦИИ АЭРОКОСМИЧЕСКИХ ИЗОБРАЖЕНИЙ
Выпускная квалификационная работа
на соискание квалификации инженер
Содержание
- Глава 1. Высокопроизводительные вычисления в обработке данных дистанционного зондирования земли
- 1.1 Типы аэрокосмических изображений
- 1.2 Высокопроизводительная обработка аэрокосмических изображений
- 1.3 Неконтролируемая классификация аэрокосмических изображений
- 1.4 Способы удаленного доступа к суперкомпьютеру
- 1.4.1 Сжатие без потерь
- 1.4.2 Сжатие с потерями
- 1.5 Классификация аэрокосмических изображений
- 1.6 Сжатие аэрокосмических изображений
- Вывод по главе
- Глава2. Принципы построения системы удаленной обработки данных
- 2.1 Подход к дифференцированному сжатию аэрокосмических изображений
- 2.1 Этапы дифференцированного сжатия
- 2.2 Подход к сжатию многозонального аэрокосмических изображений
- Вывод по главе
- Глава 3. Эксперименты
- 3.1 Постановка задачи исследования
- 3.2Результаты экспериментов
- 3.2.1Сжатие одноканальных аэрокосмических изображений
- 3.2.2Сжатие многозональных аэрокосмических изображений
- Вывод по главе
- Глава 4. Программное обеспечение системы сжатия
- 4.1 Выбор среды программирования
- 4.2 Структура программного обеспечения
- 4.3 Особенности программной реализации
- 4.4 Интерфейс программы
- 4.4.1 Модуль дифференциального сжатия
- 4.4.2 Модуль сжатия по заданному коэффициенту качества
- 4.4.3 Модуль сравнения двух изображений
- Вывод по главе
- Перечень использованных источников
Глава 1. Высокопроизводительные вычисления в обработке данных дистанционного зондирования земли
1.1 Типы аэрокосмических изображений
Дистанционное зондирование Земли (ДЗЗ) - наблюдение поверхности Земли авиационными и космическими средствами, оснащёнными различными видами съемочной аппаратуры. Аэрокосмическое изображение является примером таких данных ДЗЗ. Часть данных ДДЗ сразу поступает в цифровом виде, что позволяет непосредственно использовать для их обработки современные компьютерные технологии. Снимки могут быть преобразованы в цифровую растровую форму представления с помощью специальных сканирующих устройств (сканеров). Цифровое изображение в форме растра представляет матрицу чисел. Каждый элемент этой матрицы, называемый пикселем, отвечает за какие либо характеристики (отражательная способность, температура и т.д.) участка местности в определенной зоне электромагнитного спектра. Следует отметить, что размер этого участка зависит от разрешения снимка.
Аэрокосмические изображения разделяются на панхроматические и мультиспектральные изображения. Панхроматические изображения занимают практически весь видимый диапазон электромагнитного спектра (450-900 нм) и поэтому являются черно-белыми. Мультиспектральные (или спектрозональные) изображения представлены в виде отдельных спектральных каналов или виде синтеза отдельных каналов для получения цветного изображения. Поочередный синтез отдельных каналов позволяет решать многочисленные тематические задачи, а также помогает при дешифрировании снимков.
1.2 Высокопроизводительная обработка аэрокосмических изображений
Интенсивное развитие средств дистанционного зондирования Земли аэрокосмического базирования, увеличение объемов и информативности аэрокосмической информации приводит к непрерывному расширению круга задач, решаемых с использованием данных дистанционного зондирования. Дистанционное зондирование из космоса находит все более широкое применение при решении задач контроля загрязнений окружающей среды, в картографии, в исследованиях природных ресурсов, климатологии, океанографии, для мониторинга земной поверхности, для наблюдения за пожарами и др. Необходимость обработки больших объемов данных и требования к оперативности получения результатов обуславливают интенсивное внедрение компьютерных технологий обработки изображений. Несмотря на стремительный прогресс в развитии аппаратных компьютерных средств, возможностей даже самых быстродействующих компьютеров последовательной архитектуры не достаточно для оперативного решения ряда задач обработки изображений, полученных методами дистанционного зондирования. Для решения задач анализа, преобразования и обработки большого объема аэрокосмической информации с минимальными временными затратами требуется мобилизации всех возможностей доступных аппаратно-программных средств. На сегодняшний день средствами, позволяющими существенно время вычислений, в частности являются различные архитектуры параллельной обработки данных.
Можно выделить четыре основных типа архитектур систем параллельной обработки данных:
1) Конвейерная и векторная обработка.
Основу конвейерной обработки составляет раздельное выполнение некоторой операции в несколько этапов (за несколько ступеней) с передачей данных одного этапа следующему. Производительность при этом возрастает благодаря тому, что одновременно на различных ступенях конвейера выполняются несколько операций. Конвейеризация эффективна только тогда, когда загрузка конвейера близка к полной, а скорость подачи новых операндов соответствует максимальной производительности конвейера. Если происходит задержка, то параллельно будет выполняться меньше операций и суммарная производительность снизится. Векторные операции обеспечивают идеальную возможность полной загрузки вычислительного конвейера.
При выполнении векторной команды одна и та же операция применяется ко всем элементам вектора (или чаще всего к соответствующим элементам пары векторов). Для настройки конвейера на выполнение конкретной операции может потребоваться некоторое установочное время, однако затем операнды могут поступать в конвейер с максимальной скоростью, допускаемой возможностями памяти. При этом не возникает пауз ни в связи с выборкой новой команды, ни в связи с определением ветви вычислений при условном переходе. Таким образом, главный принцип вычислений на векторной машине состоит в выполнении некоторой элементарной операции или комбинации из нескольких элементарных операций, которые должны повторно применяться к некоторому блоку данных. Таким операциям в исходной программе соответствуют небольшие компактные циклы.
2) Машины типа SIMD. Машины типа SIMD состоят из большого числа идентичных процессорных элементов, имеющих собственную память. Все процессорные элементы в такой машине выполняют одну и ту же программу. Очевидно, что такая машина, составленная из большого числа процессоров, может обеспечить очень высокую производительность только на тех задачах, при решении которых все процессоры могут делать одну и ту же работу. Модель вычислений для машины SIMD очень похожа на модель вычислений для векторного процессора: одиночная операция выполняется над большим блоком данных.
сжатие аэрокосмическое изображение программное
В отличие от ограниченного конвейерного функционирования векторного процессора, матричный процессор (синоним для большинства SIMD-машин) может быть значительно более гибким. Обрабатывающие элементы таких процессоров - это универсальные программируемые ЭВМ, так что задача, решаемая параллельно, может быть достаточно сложной и содержать ветвления. Обычное проявление этой вычислительной модели в исходной программе примерно такое же, как и в случае векторных операций: циклы на элементах массива, в которых значения, вырабатываемые на одной итерации цикла, не используются на другой итерации цикла.
Модели вычислений на векторных и матричных ЭВМ настолько схожи, что эти ЭВМ часто обсуждаются как эквивалентные.
3) Машины типа MIMD. Термин "мультипроцессор" покрывает большинство машин типа MIMD и (подобно тому, как термин "матричный процессор" применяется к машинам типа SIMD) часто используется в качестве синонима для машин типа MIMD. В мультипроцессорной системе каждый процессорный элемент (ПЭ) выполняет свою программу достаточно независимо от других процессорных элементов. Процессорные элементы, конечно, должны как-то связываться друг с другом, что делает необходимым более подробную классификацию машин типа MIMD. В мультипроцессорах с общей памятью (сильносвязанных мультипроцессорах) имеется память данных и команд, доступная всем ПЭ. С общей памятью ПЭ связываются с помощью общей шины или сети обмена. В противоположность этому варианту в слабосвязанных многопроцессорных системах (машинах с локальной памятью) вся память делится между процессорными элементами и каждый блок памяти доступен только связанному с ним процессору. Сеть обмена связывает процессорные элементы друг с другом.
Базовой моделью вычислений на MIMD-мультипроцессоре является совокупность независимых процессов, эпизодически обращающихся к разделяемым данным. Существует большое количество вариантов этой модели. На одном конце спектра - модель распределенных вычислений, в которой программа делится на довольно большое число параллельных задач, состоящих из множества подпрограмм. На другом конце спектра - модель потоковых вычислений, в которых каждая операция в программе может рассматриваться как отдельный процесс. Такая операция ждет своих входных данных (операндов), которые должны быть переданы ей другими процессами. По их получении операция выполняется, и полученное значение передается тем процессам, которые в нем нуждаются. В потоковых моделях вычислений с большим и средним уровнем гранулярности, процессы содержат большое число операций и выполняются в потоковой манере.
4) Многопроцессорные машины с SIMD-процессорами.
Многие современные супер-ЭВМ представляют собой многопроцессорные системы, в которых в качестве процессоров используются векторные процессоры или процессоры типа SIMD. Такие машины относятся к машинам класса MSIMD.
Языки программирования и соответствующие компиляторы для машин типа MSIMD обычно обеспечивают языковые конструкции, которые позволяют программисту описывать "крупнозернистый" параллелизм. В пределах каждой задачи компилятор автоматически векторизует подходящие циклы. Машины типа MSIMD, как можно себе представить, дают возможность использовать лучший из этих двух принципов декомпозиции: векторные операции ("мелкозернистый" параллелизм) для тех частей программы, которые подходят для этого, и гибкие возможности MIMD-архитектуры для других частей программы.
Многопроцессорные системы за годы развития вычислительной техники претерпели ряд этапов своего развития. Исторически первой стала осваиваться технология SIMD. Однако в настоящее время наметился устойчивый интерес к архитектурам MIMD. Этот интерес главным образом определяется двумя факторами:
1. Архитектура MIMD дает большую гибкость: при наличии адекватной поддержки со стороны аппаратных средств и программного обеспечения MIMD может работать как однопользовательская система, обеспечивая высокопроизводительную обработку данных для одной прикладной задачи, как многопрограммная машина, выполняющая множество задач параллельно, и как некоторая комбинация этих возможностей.
2. Архитектура MIMD может использовать все преимущества современной микропроцессорной технологии на основе строгого учета соотношения стоимость/производительность. В действительности практически все современные многопроцессорные системы строятся на тех же микропроцессорах, которые можно найти в персональных компьютерах, рабочих станциях и небольших однопроцессорных серверах.
Одной из отличительных особенностей многопроцессорной вычислительной системы является сеть обмена, с помощью которой процессоры соединяются друг с другом или с памятью. Модель обмена настолько важна для многопроцессорной системы, что многие характеристики производительности и другие оценки выражаются отношением времени обработки к времени обмена, соответствующим решаемым задачам. Существуют две основные модели межпроцессорного обмена: одна основана на передаче сообщений, другая - на использовании общей памяти. В многопроцессорной системе с общей памятью один процессор осуществляет запись в конкретную ячейку, а другой процессор производит считывание из этой ячейки памяти. Чтобы обеспечить согласованность данных и синхронизацию процессов, обмен часто реализуется по принципу взаимно исключающего доступа к общей памяти методом "почтового ящика".
В архитектурах с локальной памятью непосредственное разделение памяти невозможно. Вместо этого процессоры получают доступ к совместно используемым данным посредством передачи сообщений по сети обмена. Эффективность схемы коммуникаций зависит от протоколов обмена, основных сетей обмена и пропускной способности памяти и каналов обмена.
Часто, и притом необоснованно, в машинах с общей памятью и векторных машинах затраты на обмен не учитываются, так как проблемы обмена в значительной степени скрыты от программиста. Однако накладные расходы на обмен в этих машинах имеются и определяются конфликтами шин, памяти и процессоров. Чем больше процессоров добавляется в систему, тем больше процессов соперничают при использовании одних и тех же данных и шины, что приводит к состоянию насыщения. Модель системы с общей памятью очень удобна для программирования и иногда рассматривается как высокоуровневое средство оценки влияния обмена на работу системы, даже если основная система в действительности реализована с применением локальной памяти и принципа передачи сообщений.
В сетях с коммутацией каналов и в сетях с коммутацией пакетов по мере возрастания требований к обмену следует учитывать возможность перегрузки сети. Здесь межпроцессорный обмен связывает сетевые ресурсы: каналы, процессоры, буферы сообщений. Объем передаваемой информации может быть сокращен за счет тщательной функциональной декомпозиции задачи и тщательного диспетчирования выполняемых функций.
Таким образом, существующие MIMD-машины распадаются на два основных класса в зависимости от количества объединяемых процессоров, которое определяет и способ организации памяти и методику их межсоединений.
К первой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизованную общую память и объединить процессоры и память с помощью одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (UniformMemoryAccess). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Структура подобной системы представлена на рис.1
Рис.1. Типовая архитектура мультипроцессорной системы с общей памятью.
Вторую группу машин составляют крупномасштабные системы с распределенной памятью. Для того чтобы поддерживать большое количество процессоров приходится распределять основную память между ними, в противном случае полосы пропускания памяти просто может не хватить для удовлетворения запросов, поступающих от очень большого числа процессоров. Естественно при таком подходе также требуется реализовать связь процессоров между собой. На рис.2 показана структура такой системы.
С ростом числа процессоров просто невозможно обойти необходимость реализации модели распределенной памяти с высокоскоростной сетью для связи процессоров. С быстрым ростом производительности процессоров и связанным с этим ужесточением требования увеличения полосы пропускания памяти, масштаб систем (т.е. число процессоров в системе), для которых требуется организация распределенной памяти, уменьшается, также как и уменьшается число процессоров, которые удается поддерживать на одной разделяемой шине и общей памяти.
Распределение памяти между отдельными узлами системы имеет два главных преимущества. Во-первых, это эффективный с точки зрения стоимости способ увеличения полосы пропускания памяти, поскольку большинство обращений могут выполняться параллельно к локальной памяти в каждом узле. Во-вторых, это уменьшает задержку обращения (время доступа) к локальной памяти. Эти два преимущества еще больше сокращают количество процессоров, для которых архитектура с распределенной памятью имеет смысл.
Обычно устройства ввода/вывода, также как и память, распределяются по узлам и в действительности узлы могут состоять из небольшого числа (2-8) процессоров, соединенных между собой другим способом. Хотя такая кластеризация нескольких процессоров с памятью и сетевой интерфейс могут быть достаточно полезными с точки зрения эффективности в стоимостном выражении, это не очень существенно для понимания того, как такая машина работает, поэтому мы пока остановимся на системах с одним процессором на узел. Основная разница в архитектуре, которую следует выделить в машинах с распределенной памятью заключается в том, как осуществляется связь и какова логическая модель памяти.
Рис.2. Типовая архитектура машины с распределенной памятью.
Модели связи и архитектуры памяти.
Как уже было отмечено, любая крупномасштабная многопроцессорная система должна использовать множество устройств памяти, которые физически распределяются вместе с процессорами. Имеется две альтернативных организации адресации этих устройств памяти и связанных с этим два альтернативных метода для передачи данных между процессорами. Физически отдельные устройства памяти могут адресоваться как логически единое адресное пространство, что означает, что любой процессор может выполнять обращения к любым ячейкам памяти, предполагая, что он имеет соответствующие права доступа. Такие машины называются машинами с распределенной разделяемой (общей) памятью (DSM - distributedsharedmemory), масштабируемые архитектуры с разделяемой памятью, а иногда NUMA's - Non-UniformMemoryAccess, поскольку время доступа зависит от расположения ячейки в памяти.
В альтернативном случае, адресное пространство состоит из отдельных адресных пространств, которые логически не связаны и доступ к которым не может быть осуществлен аппаратно другим процессором. В таком примере каждый модуль процессор-память представляет собой отдельный компьютер, поэтому такие системы называются многомашинными (multicomputers).
С каждой из этих организаций адресного пространства связан свой механизм обмена. Для машины с единым адресным пространством это адресное пространство может быть использовано для обмена данными посредством операций загрузки и записи. Поэтому эти машины и получили название машин с разделяемой (общей) памятью. Для машин с множеством адресных пространств обмен данными должен использовать другой механизм: передачу сообщений между процессорами; поэтому эти машины часто называют машинами с передачей сообщений.
Каждый из этих механизмов обмена имеет свои преимущества. Для обмена в общей памяти это включает:
· Совместимость с хорошо понятными используемыми как в однопроцессорных, так и маломасштабных многопроцессорных системах, механизмами, которые используют для обмена общую память.
· Простота программирования, когда модели обмена между процессорами сложные или динамически меняются во время выполнения. Подобные преимущества упрощают конструирование компилятора.
· Более низкая задержка обмена и лучшее использование полосы пропускания при обмене малыми порциями данных.
· Возможность использования аппаратно управляемого кэширования для снижения частоты удаленного обмена, допускающая кэширование всех данных как разделяемых, так и неразделяемых.
Основные преимущества обмена с помощью передачи сообщений являются:
· Аппаратура может быть более простой, особенно по сравнению с моделью разделяемой памяти, которая поддерживает масштабируемую когерентность кэш-памяти.
· Модели обмена понятны, принуждают программистов (или компиляторы) уделять внимание обмену, который обычно имеет высокую, связанную с ним стоимость.
Конечно, требуемая модель обмена может быть надстроена над аппаратной моделью, которая использует любой из этих механизмов. Поддержка передачи сообщений над разделяемой памятью, естественно, намного проще, если предположить, что машины имеют адекватные полосы пропускания. Основные трудности возникают при работе с сообщениями, которые могут быть неправильно выровнены и сообщениями произвольной длины в системе памяти, которая обычно ориентирована на передачу выровненных блоков данных, организованных как блоки кэш-памяти. Эти трудности можно преодолеть либо с небольшими потерями производительности программным способом, либо существенно без потерь при использовании небольшой аппаратной поддержки.
Построение механизмов реализации разделяемой памяти над механизмом передачи сообщений намного сложнее. Без предполагаемой поддержки со стороны аппаратуры все обращения к разделяемой памяти потребуют привлечения операционной системы как для обеспечения преобразования адресов и защиты памяти, так и для преобразования обращений к памяти в посылку и прием сообщений. Поскольку операции загрузки и записи обычно работают с небольшим объемом данных, то большие накладные расходы по поддержанию такого обмена делают невозможной чисто программную реализацию.
При оценке любого механизма обмена критичными являются три характеристики производительности:
1. Полоса пропускания: в идеале полоса пропускания механизма обмена будет ограничена полосами пропускания процессора, памяти и системы межсоединений, а не какими-либо аспектами механизма обмена. Связанные с механизмом обмена накладные расходы (например, длина межпроцессорной связи) прямо воздействуют на полосу пропускания.
2. Задержка: в идеале задержка должна быть настолько мала, насколько это возможно. Для ее определения критичны накладные расходы аппаратуры и программного обеспечения, связанные с инициированием и завершением обмена.
3. Упрятывание задержки: насколько хорошо механизм скрывает задержку путем перекрытия обмена с вычислениями или с другими обменами.
Каждый из этих параметров производительности воздействует на характеристики обмена. В частности, задержка и полоса пропускания могут меняться в зависимости от размера элемента данных. В общем случае, механизм, который одинаково хорошо работает как с небольшими, так и с большими объемами данных будет более гибким и эффективным.
Таким образом, отличия разных машин с распределенной памятью определяются моделью памяти и механизмом обмена. Исторически машины с распределенной памятью первоначально были построены с использованием механизма передачи сообщений, поскольку это было очевидно проще и многие разработчики и исследователи не верили, что единое адресное пространство можно построить и в машинах с распределенной памятью. С недавнего времени модели обмена с общей памятью действительно начали поддерживаться практически в каждой разработанной машине (характерным примером могут служить системы с симметричной мультипроцессорной обработкой). Хотя машины с централизованной общей памятью, построенные на базе общей шины все еще доминируют в терминах размера компьютерного рынка, долговременные технические тенденции направлены на использование преимуществ распределенной памяти даже в машинах умеренного размера. Как мы увидим, возможно, наиболее важным вопросом, который встает при создании машин с распределенной памятью, является вопрос о кэшировании и когерентности кэш-памяти.
Если говорить кратко, то вычислительный кластер - это совокупность компьютеров, объединенных в рамках некоторой сети для решения одной задачи. В качестве вычислительных узлов обычно используются доступные на рынке однопроцессорные компьютеры, двух или четырехпроцессорные SMP-серверы. Каждый узел работает под управлением своей копии операционной системы, в качестве которой чаще всего используются стандартные операционные системы: Linux, NT, Solaris и т.п. Состав и мощность узлов может меняться даже в рамках одного кластера, давая возможность создавать неоднородные системы. Выбор конкретной коммуникационной среды определяется многими факторами: особенностями класса решаемых задач, доступным финансированием, необходимостью последующего расширения кластера и т.п. Возможно включение в конфигурацию специализированных компьютеров, например, файл-сервера, и, как правило, предоставлена возможность удаленного доступа на кластер через Internet.
1.3 Неконтролируемая классификация аэрокосмических изображений
Современные системы ДЗЗ как мультиспектральные, так и гиперспектральные обладают различным количеством спектральных каналов, что затрудняет проведение визуальной классификации изображений, поэтому алгоритмы классификации реализованы в различном программном обеспечении, предназначенном для работы с данными ДЗЗ.
Поскольку классификация является одной из основных задач обработки спутниковых изображений, требующая применения специализированных программных пакетов, то очевидна необходимость рассмотрения ее применения при использовании специализированного программного обеспечения.
Под процессом классификации изображения будем понимать процесс количественного отбора данных из изображения и группирования точек или частей изображения в классы, предназначенные для представления различных физических объектов или типов. Результатом выполнения процесса классификации изображения будут являться карты классификации. Основные технологии классификации изображения используют радиометрические данные изображения.
Известны два типа классификации:
классификация с обучением (контролируемая классификация)
классификация без обучения (неконтролируемая классификация)
Методы контролируемой классификации учитывают априорную информацию о типах объектов и вероятности их представления данными снимка, эталонных значениях спектральных характеристик этих объектов. В процессе проведения такой классификации значения яркости текущего пиксела сравниваются с эталонными и на основании этого сравнения пиксел относится к наиболее подходящему классу объектов. После проведения классификации по имеющимся наземным данным оценивается качество проведенной классификации. Обычно контролируемая классификация применяется, когда классы хорошо различаются на снимке и их число варьируется от 25 и выше.
Среди алгоритмов контролируемой классификации выделяются алгоритмы, основанные на методах:
метод параллелепипедов;
метод классификации по минимальному расстоянию;
метод классификации по правилу максимального правдоподобия.
Нами опробованы алгоритмы неконтролируемой классификации, чаще называемые алгоритмами кластеризации, которые целесообразнее применять при отсутствии априорной информации об объекте съемки. Поскольку кластерный анализ относится к цифровым автоматизированным методам обработки космических изображений, то он позволяет выделять контура с неконтрастной по спектральной яркости структурой, например растительность, открытые почвы, вода, облака другие объекты. С использованием алгоритмов кластеризации удалось выполнить автоматическое разделение пикселов изображения на группы сходных по спектральным характеристикам пикселов - кластеры. При использовании алгоритмов неконтролируемой классификации необходимо иметь минимум исходной информации, например, число классов, длительность классификации и т.д. После проведения неконтролируемой классификации полученная карта классификации более объективно отражает близкие по значениям дешифровочных признаков группы объектов, чем при контролируемой классификации, так как кластеры определяются автоматически. Однако полученная карта классификации требует дальнейшего объединения или разбиения классов, поскольку одни и те же объекты могут попасть в разные кластеры, например из-за условий освещения, а разные объекты - оказаться в одном кластере из-за одинаковой яркости. В первом случае необходимо объединить кластеры в единый класс, а во втором - привлечь дополнительные дешифровочные признаки для различения объектов. Наиболее популярными среди алгоритмов неконтролируемой классификации (кластеризации) являются алгоритмы: K-Means и ISODATA.
Главное отличие алгоритмов ISODATA и K-Means заключается в том, что на стадии инициализации алгоритма ISODATA происходит распределение пиксел, в то время как для алгоритма K-Means происходит распределение значений математических ожиданий. Поэтому ниже будет рассмотрен результат применения алгоритма ISODATA.
Алгоритм ISODATA использует минимальное спектральное расстояние, для определения соответствующего кластера (класса) для каждого пиксела. Процесс начинается с назначения случайного (приближенного) среднего значения кластера и повторяется до тех пор, пока это значение не достигнет величины среднего для каждого кластера исходных данных. Начальные средние значения кластеров распределяются равномерно вдоль центрального вектора спектрального пространства.
В течение первой итерации кластеризации пространство равномерно разбивается на области, центром каждой из которых являются средние значения кластеров. Пикселы анализируются с левого верхнего угла изображения к нижнему правому. Вычисляется спектральное расстояние между пикселом и средним значением кластера. Пикселы назначаются в тот кластер, где это расстояние минимально. После итерации рассчитывают реальные средние значения спектральных признаков по полученным кластерам, т.к. их средние значения меняются в зависимости от преобладающих яркостей попавших в них пиксел. Затем выполняется вторая итерация, в процессе которой повторяют кластеризацию с новыми средними значениями и рассчитывают границы кластеров. После этого определяют новые средние значения и выполняют новую итерацию. В процессе второй итерации снова определяются минимальные спектральные расстояния между точками и новыми средними значениями кластеров, по окончанию которой пикселы будут перераспределены.
Такие пересчеты повторяются до тех пор, пока все пикселы с заданной вероятностью (порог сходимости) не попадут в какой-либо кластер. Отметим, что возможна ситуация, когда распределение значений яркости на снимке не фиксируются в каком-либо кластере, поэтому ограничивающим здесь фактором будет являться заданное число итераций.
1.4 Способы удаленного доступа к суперкомпьютеру
1.4.1 Сжатие без потерь
Сжатие без потерь (англ. Losslessdatacompression) - метод сжатия информации, при использовании которого закодированная информация может быть восстановлена с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь [4]. Сжатие данных без потерь используется во многих приложениях. Например, оно используется во всех файловых архиваторах. Оно также используется как компонент в сжатии с потерями.
Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример - исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG или GIF, используют только сжатие без потерь; тогда как другие (TIFF, MNG) могут использовать сжатие как с потерями, так и без [5].
Рассмотрим несколько алгоритмов сжатия данных, которые не вносят изменений в исходные файлы и гарантируют полное восстановление данных.
Алгоритм RLE. Алгоритм группового кодирования (RLE - RunLengthEncoding) позволяет сжимать данные любых типов независимо от содержащейся в них информации [6]. Сама информация влияет лишь на коэффициент сжатия. Он является самым быстрым, простым и понятным алгоритмом компрессии и при этом иногда оказывается весьма эффективным.
Он оперирует группами данных - последовательностями, в которых один и тот же символ встречается несколько раз подряд. Суть его заключается в том, что при кодировании строка повторяющихся символов, составляющих группу, заменяется строкой, которая содержит сам повторяющийся символ (значение группы) и количество его повторов (счетчик группы).
Из специфики работы алгоритма можно легко понять, для каких изображений коэффициент сжатия будет максимальным. Это изображения, содержащие минимальное количество цветов, без плавных переходов (с резкими границами) и с большими участками, заполненными одним цветом. Так как сканирование данных осуществляется построчно с лева на право, высокий коэффициент сжатия будет достигаться на изображениях, строки которых содержат достаточно длинные цепочки одинаковых пикселей. То есть, алгоритм будет давать хорошие результаты на изображениях 1 и частично 2 классов.
Алгоритм группового кодирования применяется в форматах РСХ, TIFF, ВМР.
АлгоритмLZW. Название алгоритм получил по первым буквам фамилий его разработчиков Lempel, Ziv и Welch [7]. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт.
Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов - это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.
Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
Алгоритм Хаффмана. Это более распространенный метод сжатия без потерь. Сжимая файл по алгоритму Хаффмана первое что необходимо сделать - это прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII [8].
После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать мнимую компоновку между кодами по убыванию. То есть, не меняя местонахождение каждого символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем "узлом". В дальнейшем (в дереве) будем размещать указатели, которые указывают на этот "узел".
Например, имеется файл с длиной в 100 байт, содержащий 6 различных символов с соответствующими частотами вхождения (табл.1.1)
Таблица 1. 1 - Частоты распределения символов
|
Символ |
A |
B |
C |
D |
E |
F |
|
|
Число вхождений |
10 |
20 |
30 |
5 |
25 |
10 |
Отсортируем эти символы в соответствии с частотой вхождения (по убыванию) (табл.1.2)
Таблица 1. 2 - Отсортированные частоты распределения символов
|
Символ |
C |
E |
B |
F |
A |
D |
|
|
Число вхождений |
30 |
25 |
20 |
10 |
10 |
5 |
Возьмем из табл.1.2 символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ с частотой 10 (F или A), например A.
Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A.
Рисунок 1. 1 - Формирование первого "узла дерева"
Номер в рамке (рис.1.1) - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Повторяем операцию слияния узлов (рис.1.2).
Рисунок 1. 2. Формирование второго "узла дерева"
Рассматриваем частоты встречаемости символов (табл.1.2) для следующих двух символов (B и E). Продолжаем пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.
Рисунок 1.3. Законченное "дерево"
Теперь, когда дерево создано, можно кодировать файл. Необходимо всегда начинать из корня (Root) (рис.1.3). Кодируя первый символ (лист дерева С) прослеживаем вверх по дереву все повороты ветвей и если делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Код Хаффмана для символа C - 00. Для следующего символа (А) - 0100. Выполнив вышесказанное для всех символов получим:
C = 00 (2 бита)
A = 0100 (4 бита)
D = 0101 (4 бита)
F = 011 (3 бита)
B = 10 (2 бита)
E = 11 (2 бита)
Каждый символ изначально представлялся 8-ю битами (один байт), и так как уменьшили число битов необходимых для представления каждого символа, следовательно уменьшили размер выходного файла. Сжатие складывается следующим образом:
Таблица 1. 3. Уменьшение объема данных при сжатии Хаффмана
|
Частота |
Первоначально |
Уплотненные биты |
Уменьшено на |
|
|
C 30 |
30 Ч 8 = 240 |
30 Ч 2 = 60 |
180 |
|
|
A 10 |
10 Ч 8 = 80 |
10 Ч 3 = 30 |
50 |
|
|
D 5 |
5 Ч 8 = 40 |
5 Ч 4 = 20 |
20 |
|
|
F 10 |
10 Ч 8 = 80 |
10 Ч 4 = 40 |
40 |
|
|
B 20 |
20 Ч 8 = 160 |
20 Ч 2 = 40 |
120 |
|
|
E 25 |
25 Ч 8 = 200 |
25 Ч 2 = 50 |
150 |
Первоначальный размер файла: 100 байт - 800 бит;
Размер сжатого файла: 30 байт - 240 бит;
240 - 30% из 800, так что сжали этот файл на 70%.
Следует помнить, что для восстановления первоначального файла, необходимо иметь декодирующее дерево, так как деревья будут различны для разных файлов. Поэтому необходимо сохранять дерево вместе с файлом, что приводит к увеличению размеров выходного файла.
1.4.2 Сжатие с потерями
Сжатие данных с потерями - это метод сжатия данных, когда распакованный файл отличается от оригинального, но "достаточно близок" для того, чтобы быть полезным каким-то образом [9]. Этот тип компрессии часто используется в Интернете, особенно в потоковой передаче данных и телефонии. Эти методы часто называются кодеками в этом контексте.
JPEG - один из самых новых и достаточно мощных алгоритмов [10]. Практически он является стандартом де-факто для полноцветных изображений. Оперирует алгоритм областями 8х8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого, при разложении матрицы такой области в двойной ряд по косинусам значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении. Упаковка значений матрицы выполняется за три этапа.
· Дискретное косинус преобразование (ДКП);
Дискретное косинусное преобразование представляет собой разновидность преобразования Фурье. Оно позволяет переходить от пространственного представления изображения к его спектральному представлению и обратно. На этом этапе рассматриваем изображение как равные части с размером 8Ч8. Из матриц пикселей изображения получаем матрицы, в которых коэффициенты в левом верхнем углу матриц соответствуют низкочастотной составляющей изображения, а в правом нижнем - высокочастотной.
Следует создать матрицы FDCT [8Ч8] (1.1) (при сжатий) и матрицуIDCT [8Ч8] (1.2) (при восстановлений) матрицы, используя такие формулы:
(1.1)
(1.2)
где x (i,j) - значение элементов матрицы пикселей, X (u,v) - значение матрицы при восстановлений, C (u), C (v) - коэффициенты ДКП, соответствующие положению элемента в матрице, C (u), C (v) = если u,v=0, C (u), C (v) = 1 остальные.
Высокая эффективность сжатия, которую дает этот алгоритм, основана на том факте, что в матрице частотных коэффициентов, образующейся из исходной матрицы после дискретного косинусного преобразования, низкочастотные компоненты расположены ближе к левому верхнему углу, а высокочастотные - внизу справа. Это важно потому, что большинство графических образов на экране компьютера состоит из низкочастотной информации, так что высокочастотные компоненты матрицы можно безболезненно выбросить. "Выбрасывание" выполняется путем округления частотных коэффициентов.
· Квантование;
Основным этапом работы алгоритма является квантование. Для получения матрицы квантования Q [8Ч8] (1.3) используется следующая формула
Q (i,j) =Q50*scale, (1.3)
где scale - множитель, где scale=50/qеслиq<50 иначе scale=2-q/50, q - коэффициент качества сжатия, от него зависит степень потери качества сжатого изображенияq, Q50 (1.4) - рекомендованная стандартная матрица квантования, построенная опытным путем
|
Q50= 16 11 10 16 24 40 51 61 12 12 14 19 26 58 60 55 14 13 16 25 40 57 69 56 14 17 22 29 51 85 80 62 18 22 37 56 68 109 103 77 24 35 55 64 81 104 113 92 49 64 78 87 103 121 120 101 72 92 95 98 112 100 103 99 |
(1.4) |
Теперь нужно каждое число в матрице FDCTразделить на число в соответствующей позиции в матрице квантования.
A (i,j) =
Таким образом, при преобразовании мы получаем матрицу, в которой многие коэффициенты либо близки, либо равны нулю. Чем больше значения в матрице квантования, тем больше отбрасывается информации из изображения и тем более плотно сжимается изображение. Компромисс состоит в том, что более высокие значения квантования приводят к худшему качеству изображения.
После округления отличные от нуля значения низкочастотных компонент остаются, главным образом, в левом верхнем углу матрицы. Округленная матрица значений кодируется с учетом повторов нулей. В результате графический образ сжимается более чем на 90%, теряя очень немного в качестве изображения только на этапе округления.
· Вторичное сжатие
Для уменьшения избыточности квантованных данныхпри вторичном сжатии применяется сжатие без потерь. Распространенным методом вторичного сжатия является метод Хаффмана (п.1.2.1).
1.5 Классификация аэрокосмических изображений
Одним из наиболее распространенных путей использования аэрокосмических изображений является их классификация. Классификация так же относится к методу сжатия с потерями. Точность классификации является важнейшим критерием качества классифицированного восстановленного изображения (например, после проведения неконтролируемой классификации).
Под процессом классификации изображения будем понимать процесс количественного отбора данных из изображения и группирования точек или частей изображения в классы, предназначенные для представления различных физических объектов или типов [11]. Результатом выполнения процесса классификации изображения будут являться карты классификации. Основные технологии классификации изображения используют радиометрические данные изображения.
Известны два типа классификации:
· классификация с обучением (контролируемая классификация);
· классификация без обучения (неконтролируемая классификация).
Классификация с обучением учитывает априорную информацию о типах объектов и вероятности их представления данными снимка, эталонных значениях спектральных характеристик этих объектов. В процессе проведения такой классификации значения яркости текущего пикселя сравниваются с эталонными и на основании этого сравнения пикселя относится к наиболее подходящему классу объектов. После проведения классификации по имеющимся наземным данным оценивается качество проведенной классификации. Обычно контролируемая классификация применяется, когда классы хорошо различаются на снимке и их число варьируется от 25 и выше.
Классификация без обучения предполагает выявление системой классов по спутниковым изображениям без предварительного знания о типах поверхности, которые могут встретиться на изучаемой местности. Проводится такая классификация на базе кластерного анализа. Кластеры формируются из пикселей со сходными значениями, причем учитываются все данные спектральных измерений. Если при применении методов классификации с обучением основной проблемой было выбрать обучающие полигоны, которые надежно представляли бы системе нужные классы, то при использовании классификации без обучения основная проблема заключается в соотнесении найденных системой классов с реально существующими типами поверхности или элементами местности. Со времени своего первого появления в 1987 году система IDRISI зарекомендовала себя, как простой в использовании инструмент для обработки растровых изображений, доступный и интересный пользователям весьма разного уровня, обладающий при этом широкими возможностями по обработке разнообразных географических данных. Система IDRISI предлагает метода классификации без обучения ISOCLUST.
Метод кластерного анализа с элементами самообучения (ISOCLUST). Метод ISOCLUST является гибридным методом, объединяющим подходы классификации изображений с обучением и без обучения. На первом этапе работы этого метода реализуется поиск центров кластеризации и решается вопрос о количестве кластеров, далее вокруг центров кластеризации формируются обучающие полигоны, которые используются на втором этапе для самообучения системы.
При запуске модуля ISOCLUST возникает диалоговое окно, определяющее необходимые данные для работы модуля. Это число изображений в разных участках спектра, которые будут использованы при классификации, названия файлов этих изображений, имя композитного изображения для определения положений центров кластеризации и имя выходного файла.
После нажатия на кнопку Continue… система отрабатывает первый этап процедуры кластеризации, фиксируя возможные положения кластеров. По окончании этого процесса на экране появляется гистограмма и диалоговое окошко, где пользователь должен зафиксировать число кластеров, которое следует оставить при классификации, и число итераций. Возникшая гистограмма призвана облегчить пользователю процесс выбора итогового количества кластеров. Гистограмма полученного изображения будет выглядеть примерно так, как показано на рис.1.4 Она показывает, что на итоговом изображении доминируют два кластера (два класса), кроме того, есть еще два класса, занимающих меньшую и примерно равную площадь, и еще два класса, которые также, пожалуй, можно отнести к группе наиболее значимых классов.
Группа из первых шести классов отделена на гистограмме от последующих классов резким перепадом значения частоты. Следующий перепад наблюдается после 17-го класса, следующий - после 22-го. Каждая группа классов показывает возможный выбор числа классов при проведении кластеризации. Каждая из них отражает разный уровень генерализации картины классов, основываясь на особенностях нашего конкретного изображения.
Рисунок 1.4 - Гистограмма изображения, полученного методом кластерного анализа, при условии, что оставлены все полученные классы.
Мы должны выбрать число классов, опираясь на информацию гистограммы, и ввести соответствующее число в диалоговое окно после фразы Numberofclustersdesired.
Рисунок 1.5 - Результат работы модуля ISOCLUST.
Что касается необходимого числа итераций, опыт показывает, что 3-х обычно достаточно. Результат первой итерации получается после классификации с самообучением для выбранного количества классов, причем информация для самообучения формируется исключительно по значениям яркости пикселей, попавших в группу кластеров, ограниченную выбранным числом (начиная с первого). Далее информация для самообучения меняется с учетом пикселей, попавших в каждый из классов после первой итерации.
1.6 Сжатие аэрокосмических изображений
Для задач передачи и последующего хранения аэрокосмических изображений представляют интерес системы сжатия изображений, позволяющие значительно уменьшить требования к системам передачи данных, повысить емкость банков изображений и, в конечном счете, обеспечить большую эффективность работы с ними. Сейчас известно несколько основных групп методов компрессии, достаточно хорошо зарекомендовавших себя при решении различных задач формирования, передачи и хранения аэрокосмических изображений: методы дифференциального кодирования, методы кодирования с преобразованием (к ним относится и широко известный алгоритм JPEG), интерполяционные методы, методы, основанные на содержательном разбиении (сегментации) изображения, фрактальные методы и другие компрессии/декомпрессии [12].
Алгоритм фрактального сжатия аэрокосмических изображений, используя функцию повторного теория позволяет сжать эти сложные естественные изображения в кодифицированных шаблон, из которого факсимиле исходного изображения может использоваться повторно. Метод кодирования использует фрактальные свойства масштабной инвариантности математической и самоподобия генерирования множеств преобразований, которые занимают минимальное пространство. Результатом является то, что эти изображения могут быть сжаты в часть своего первоначального размера и с высокой степенью сжатия. Сжатие изображений с использованием фрактального потеряет информацию. Это означает, что изображение, формируемое на основе шаблона будет приближение к исходному изображению. По этой причине, необработанные данные не должны быть обработаны таким методам. Однако, для информационно-поисковых систем, где это необходимо хранить сотни изображений, этот метод позволит способность таких систем, увеличилось в несколько раз [13].
Вывод по главе
В данной главе был рассмотрены особенности аэрокосмических изображений, процедур классификации и методы сжатия. Аэрокосмические изображения разделяются на панхроматические и мультиспектральные изображения. Классификация, являющаяся одним из путей использования аэрокосмических изображений, разделяет на классификации с обучением и без обучения.
Одной из задач, повышающих эффективность хранения и передачи таких данных является сжатие, имеющее 2 типа: сжатие без потерь и сжатие с потерями. Сжатие без потерь основано на простом принципе преобразования данных из одной группы символов в другую, более компактную. Наиболее известен алгоритм сжатия без потерь: это кодирование Хаффмана (Huffman). Его принцип заключается в уменьшении количества битов, используемых для представления часто встречающихся символов и соответственно в увеличении количества битов, используемых для редко встречающихся символов. Сжатие с потерями используются для аналоговых данных - графики (JPEG), то есть там, где в силу огромных размеров файлов степень сжатия очень важна, и можно пожертвовать деталями, не существенными для восприятия этой информации человеком. Преимущество методов сжатия с потерями над методами сжатия без потерь состоит в увеличении степени сжатия но количество информации изображений уменьшается.
Подобные документы
Типы изображений (черно-белые, полутоновые, цветные) и их форматы. Устройства, создающие цифровые изображения, и их параметры. Применение и характеристики методов сжатия изображений. Поиск по содержимому в базах данных изображений. Структуры баз данных.
презентация [360,4 K], добавлен 11.10.2013Обработка изображений на современных вычислительных устройствах. Устройство и представление различных форматов изображений. Исследование алгоритмов обработки изображений на базе различных архитектур. Сжатие изображений на основе сверточных нейросетей.
дипломная работа [6,1 M], добавлен 03.06.2022Особенности работы программы ENVI, которая является наиболее совершенным программным обеспечением для работы с данными дистанционного зондирования. Спектральный анализ. Поддерживаемые форматы данных. Традиционный анализ изображений. Анализ местности.
отчет по практике [4,5 M], добавлен 28.08.2014Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.
курсовая работа [2,6 M], добавлен 26.01.2011Положения алгоритмов сжатия изображений. Классы приложений и изображений, критерии сравнения алгоритмов. Проблемы алгоритмов архивации с потерями. Конвейер операций, используемый в алгоритме JPEG. Характеристика фрактального и рекурсивного алгоритмов.
реферат [242,9 K], добавлен 24.04.2015Выполнение геометрической коррекции сканированного листа карты Украины масштаба 1:1000000 в среде Erdas. Возможности выявления объектов с использованием радиолокационных снимков. Создание цифровых моделей рельефа и перспективных изображений местности.
курсовая работа [2,0 M], добавлен 17.12.2013Архивация и компрессия как методы сжатия изображений. Алгоритмы сжатия данных. Вспомогательные средства, которые используются для понижения объемов файлов: изменение цветовой модели изображения, изменение разрешения растрового файла, ресемплирование.
презентация [45,3 K], добавлен 06.01.2014Изучение современных методик компьютерной обработки биомедицинских изображений с целью улучшения изображений для их наилучшего визуального восприятия врачом-диагностом и эффективного сжатия изображений – для надежного хранения и быстрой передачи данных.
курсовая работа [2,3 M], добавлен 15.04.2019Классификация и основные характеристики метода сжатия данных. Вычисление коэффициентов сжатия и оценка их эффективности. Алгоритмы полиноминальных, экстраполяционных и интерполяционных методов сжатия и их сравнение. Оптимальное линейное предсказание.
курсовая работа [1,1 M], добавлен 17.03.2011Методы обработки растровых изображений (кластеризация, пороговая и интерактивная сегментация). Разработка программного модуля для системы мониторинга биосферы и дистанционного зондирования. Создание пользовательского интерфейса программного модуля.
курсовая работа [2,2 M], добавлен 29.04.2015
