Прецедентное распознавание фрагментов изображений земной поверхности Лихошерстный Алексей Юрьевич

Содержание к диссертации

Введение

ГЛАВА 1. Методы распознавания фрагментов изображений земной поверхности. состояние вопроса

1.1 Спутниковые изображения земной поверхности 11

1.2 Информационные процессы с изображениями земной поверхности 21

1.3 Дешифрирование изображений земной поверхности 23

1.4 Задачи исследования 31

ГЛАВА 2. Принятие решений при прецедентном распознавании фрагментов изображений земной поверхности 32

2.1 Концептуальные основы процедуры идентификации фрагментов изображения земной поверхности 32

2.2 Меры идентичности на основе долей энергии, попадающих в заданные подобласти плоскости пространственных частот 33

2.3 Меры идентичности на основе субполосного расстояния отрезков трансформант Фурье из заданных подобластей плоскости пространственных частот 44

2.4 Решающая функция 46

2.5 Результаты и выводы главы 48

ГЛАВА 3. Обработка изображений в задачах прецедентного распознавания фрагментов изображений земной поверхности 49

3.1 Процедура обучения по прецедентам 49

3.2 Процедура распознавания по прецедентам 51

3.3 Компенсация аппаратных искажений 67

3.4 Результаты и выводы главы 76

ГЛАВА 4. Программно-алгоритмическая реализация на многоядерных графических процессорах 77

4.1 Обоснование выбора аппаратно-программных средств 77

4.2 Разработка параллельных алгоритмов обработки изображений при прецедентном распознавании 94

4.3 Архитектура программной поддержки 102

4.4 Результаты и выводы главы 106

Заключение 107

Список использованных источников 109

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

Введение к работе

Актуальность работы.

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

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

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

В соответствии со сложившейся терминологией такой анализ естественно называть прецедентным распознаванием фрагментов ИЗП. При этом естественно рассматривать два класса фрагментов: идентичные заданному и все остальные.

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

Проблема построения решающих функций при прецедентном распознавании образов рассматривалась в работах многих авторов, среди которых следует отметить Журавлева Ю.И. и его учеников. Вместе с тем необходимо отметить, что задача поиска идентичных фрагментов ИЗП детальным исследованиям не подвергалась.

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

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

малоэнергетических частотных компонент, например порождаемых широкополосными шумами.

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

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

Таким образом, разработка методов и алгоритмов прецедентного распознавания объектов на ИЗП на основе субполосных представлений и параллельной программно-алгоритмической их реализации на современных высокопроизводительных вычислительных системах является актуальной задачей.

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

Целью диссертационного исследования является разработка субполосного метода прецедентного распознавания объектов изображений земной поверхности и параллельных алгоритмов его реализации на базе многоядерных процессоров.

Для достижения поставленной цели решены следующие задачи:

1. Разработка решающих функций для прецедентного распознавания объектов ИЗП на основе субполосного анализа;

2. Разработка алгоритмов обработки ИЗП для прецедентного распознавания объектов на основе субполосного анализа;

3. Разработка методов и алгоритмов компенсации помех в задачах распознавания объектов ИЗП;

4. Программно-алгоритмическая реализация разработанных алгоритмов прецедентного распознавания на многоядерных графических процессорах;

5. Оценка работоспособности разработанных алгоритмов на основе

вычислительных экспериментов.

Объект и предмет исследования. Объект исследования – изображения земной поверхности. Предмет исследования – методы прецедентного распознавания объектов на изображениях земной поверхности.

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

Научную новизну работы составляет следующее:

5. Решающая функция распознавания объектов ИЗП на основе субполосного анализа;

6. Метод обучения по субполосным признакам прецедентов;

7. Метод компенсации аппаратных помех;

8. Параллельные алгоритмы реализации процедуры распознавания на базе многоядерных процессоров NVIDIA с использованием технологии CUDA.

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

Полученные результаты также используются при проведении НИР и ОКР ООО НПП «Сигнал», что подтверждается соответствующим актом, а также в учебном процессе магистрантов НИУ «БелГУ».

Связь с научными и инновационными программами.

Результаты диссертационного исследования были использованы в рамках выполнения следующих НИР:

ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, госконтракты: № 14.514.11.4088 от 20 июня 2013; № 14.132.21.1795 от 5 октября 2012; № 14.740.11.0390 от 20 сентября 2010.

Программа Фонда содействия развитию малых форм предприятий в научно-технической сфере «У.М.Н.И.К.», проект «Разработка информационной

технологии дешифрирования аэрокосмических изображений на основе

частотных представлений». АВЦП «Развитие научного потенциала высшей школы» в 2006-2008 гг.,

проект РНП.2.2.1.1.3121

Область исследования. Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.17 «Теоретические основы информатики»:

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

п.7. Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания;

Положения, выносимые на защиту:

9. Метод прецедентного распознавания объектов на ИЗП на основе субполосного анализа и параллельные алгоритмы его реализации;

10. Метод компенсации аппаратных помех на основе субполосного анализа;

11. Программная реализация параллельных алгоритмов на основе технологии CUDA;

12. Результаты сравнительной оценки адекватности предлагаемого метода прецедентного распознавания объектов ИЗП.

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

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

Апробация результатов диссертационного исследования.

Результаты диссертационного исследования обсуждались на следующих научно-технических конференциях, школах и выставках: Международной молодежной конференции «Прикладная математика, управление и информатика», 2012, г. Белгород; Всероссийской молодежной конференции «Теория и практика системного анализа», 2012, г. Белгород; Первой и Второй Международной научно-технической конференции «Компьютерные науки и технологии», 2011 и 2009, г. Белгород; Молодежной школе параллельного программирования «Суперкомпьютерное моделирование и визуализация в научных исследованиях», 2010, г. Москва, МГУ им М.В. Ломоносова; Молодежной школе параллельного программирования «Суперкомпьютерные технологии и высокопроизводительные вычисления в образовании, науке и промышленности», 2010, г. Нижний Новгород, НГУ им Н.И. Лобачевского; Всероссийской выставке научно-технического творчества молодежи, 2009, г. Москва.

Результаты диссертационного исследования были представлены на всероссийском конкурсе «Эффективное использование GPU-ускорителей при решении больших задач», проводимом компанией Т-Платформы совместно с МГУ им М.В.Ломоносова в 2011 году. Представленная работа одержала победу в 2 этапах из 3.

Публикации. По теме диссертационного исследования опубликовано 15 печатных работ (из них 7 в журналах из списка ВАК РФ), а также получено 5 Свидетельств Роспатента РФ о государственной регистрации программы для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа изложена на 119 страницах основного текста, включающего 37 рисунков, 7 таблиц, список литературных источников из 109 наименований и 2 приложения.

Информационные процессы с изображениями земной поверхности

Темновой ток — является вредным следствием термоэлектронной эмиссии и «туннельного» эффекта и возникает в сенсоре при подаче потенциала на электрод, под которым формируется потенциальная яма. «Темновым» данный ток называется потому, что складывается из электронов, попавших в яму при отсутствии светового потока. Такие дефекты видны на темном фоне в виде светлых точек, т. н. белый дефект. Белые дефекты особенно проявляются при больших экспозициях. Основная причина возникновения темнового тока — это примеси в кремниевой пластине или повреждение кристаллической решётки кремния. Чем чище кремний, тем меньше темновой ток. На темновой ток оказывает влияние температура элементов камеры, электромагнитные наводки, как внешние, так и внутренние, от самой камеры. При увеличении температуры на 6-8 градусов, значение темнового тока удваивается;

Из-за шума, возникающего вследствие стохастической природы взаимодействия фотонов света с атомами материала фотодиодов сенсора. При движении фотона внутри кристаллической решётки кремния, вероятно, что фотон, «попав» в атом кремния, выбьет из него электрон, родив пару электрон-дырка, но сказать точно, сколько фотонов родит пары, а, сколько пропадет с какими-то другими эффектами нельзя. Электрический сигнал, снимаемый с сенсора, будет соответствовать количеству рождённых пар. Снимаемый сигнал с сенсора при заданных выдержке и диафрагме (интенсивности света) будет определять квантовая эффективность — среднее число рождаемых пар электрон-дырка;

Из-за наличия дефектных (не зарегистрированными датчиками) пикселей, которые возникают при производстве фотосенсоров (несовершенство технологии) и всегда находятся в одном и том же месте.

Для устранения их негативного влияния используются математические методы интерполяции, когда вместо дефектного «подставляется» либо просто соседний элемент, либо среднее по прилегающим элементам, либо значение, вычисленное более сложным способом. Естественно, что вычисленное значение отличается от фактического и ухудшает резкость конечного изображения. Этот же дефект вносит интерполяция, корректирующая конечное изображение, при использовании фильтра Байера;

Из-за гамма-коррекции. Гамма-коррекция может осуществляться в электронном тракте или в процессоре. Наш глаз имеет логарифмическую чувствительность к свету, а фотосенсоры — линейную, поэтому слабые сигналы усиливаются больше, чем сильные, чтобы изображение имело привычный для человека вид. Часто для этого (и для некоторых других целей) используют таблицы перекодировки, определяющие соответствие входного и выходного сигналов. На величину цифрового шума влияет [6, 11, 12]:

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

Выбранный производителем диапазон эквивалентной чувствительности сенсора. Эквивалентная чувствительность сенсора определяет коэффициенты усиления сигналов в цифровом фотоаппарате и отношение сигнал-шум. Темновой ток является главным фактором, ограничивающим предел чувствительности сенсора (ISO 400/800);

Время экспонирования. Темновой ток фотодиода при больших экспозициях сильно ухудшает отношение сигнал-шум. Чем больше время экспонирования, тем больше тепловой шум транзисторов электроники и хуже отношение сигнал-шум.

Импульсный шум проявляет себя в p–n структурах и в неметаллических резисторах. В отличие от других источников шумов, импульсные шумы обусловлены производственными дефектами, и их можно устранить, улучшив процессы производства. Эти шумы вызываются дефектами в переходе полупроводникового прибора (обычно в виде металлических примесей). Импульсные шумы проявляются как резкие всплески и сопровождаются дискретным изменениям уровня. Длительность шумовых импульсов колеблется от микросекунд до секунд. Импульсы появляются по непериодическому закону, и средняя скорость повторения изменяется от нескольких сот импульсов: в секунду до менее одного импульса в минуту. Вместе с тем у любого конкретного устройства амплитуда импульсных шумов фиксирована, так как она является функцией параметров дефекта перехода. Обычно эта амплитуда в 2- 100 раз превышает амплитуду тепловых шумов. Плотность распределения мощности импульсных шумов имеет зависимость вида 1/fn, где п обычно равно 2. Поскольку этот шум представляет собой явление, связанное с наличием тока, напряжение импульсных шумов будет наибольшим в высокоомной цепи, такой, как входная цепь операционного усилителя [31, 56, 57].

Меры идентичности на основе долей энергии, попадающих в заданные подобласти плоскости пространственных частот

В результате проведения вычислительных экспериментов и сравнения с современными методами прецедентного распознавания объектов на ИЗП было выявлено явное преимущество предлагаемого метода перед аналогами. На рисунке 3.2 показаны результаты распознавания объектов предлагаемым методом. При проведении исследования были взяты изображения различных классов: автомобили, деревья, дома, трава, вода. На исходном изображении выделялся объект интересующего класса, и при обработке осуществлялось сравнение этого объекта с другими участками изображения. Если программа распознаёт текущий участок как объект интересующего класса, то этот участок выделяется красным цветом. Исходные объекты имеют следующую нумерацию (рисунок 3.2): с 1 по 4 - автомобили; с 5 по 8 - деревья; с 9 по 11 - дома; с 12 по 14 - трава; с 15 по 18 - вода.

В работе представлены результаты распознавания различных объектов на ИЗП. Для оценки эффективности предлагаемой решающей функции были оценены вероятности ошибок распознавания первого и второго рода [40, 44, 45]: где Nо2 - количество объектов, ошибочно отнесенных к интересуемому классу распознавания; Nпол - количество объектов на снимке, которые относятся к классу распознавания; Nо1 - количество объектов, принадлежащих к классу распознавания, но не отнесенных к нему. а) Исходное изображение; б) результат распознавания автомобилей; в) результат распознавания деревьев; г) результат распознавания травы; д) результат распознавания воды; е) результат распознавания домов Вычислительные эксперименты другими методами производились в программной среде ENVI. На исходном изображении выделялся объект интересующего класса, и при распознавании осуществлялось сравнение этого объекта с другими участками изображения. Если программа ENVI относит текущий участок как объект интересующего класса, то этот участок выделяется красным, зеленым или синим цветом. При сравнении с другими методами обучение производилось в равных условиях по одному прецеденту. Обучающей выборкой служили повороты этого прецедента под различными углами до 2 с шагом /36. При распознавании объектов на цифровых растровых изображениях по одному прецеденту большинство методов показали высокое значение ошибок распознавания первого и второго рода. Из всех рассмотренных методов самые лучшие результаты показал прецедентный метод на основе субполосных представлений. При распознавании автомобилей ошибки распознавания оказались нулевыми, что говорит о том, что этот метод хорошо распознает объекты, имеющие форму. При распознавании деревьев и травы он показал ошибки распознавания второго рода 0,07 и 0,06 соответственно, т.е. он может эффективно распознавать и текстурные объекты. Что касается водных объектов, то данный метод единственный, который может правильно распознать реки и озера (особенно, когда присутствуют в воде волны). Методы параллелепипедов и минимального расстояния показали высокую ошибку распознавания второго рода. Метод максимального правдоподобия и расстояние Махалонобиса имеют в среднем одинаковые ошибки, которые также не могут быть удовлетворительными. Методы спектрального угла и двоичного кодирования показали высокие значения ошибок распознавания как первого, так и второго рода. При обучении нейронной сети требуется задавать множество прецедентов. Если задать всего один прецедент, то нейросеть отнесет к классу прецедента все фрагменты изображения. а) Исходное изображение; б) результат распознавания автомобилей методом параллелепипеда; в) результат распознавания деревьев методом параллелепипеда; г) результат распознавания травы методом параллелепипеда; д) результат распознавания воды методом параллелепипеда; е) результат распознавания домов методом параллелепипеда

Оценка эффективности распознавания объектов методом параллелипипеда: распознавание машин: P 1 = 0,P2 = 0,81 ; распознавание деревьев: P 1 = 0,P2 = 0,71 ; распознавание домов: P 1 = 0,3,P2 = 0,57 ; распознавание травы: P 1 = 0,3,P2 = 0,2 ; распознавание воды: P 1 = 0,75 ,P2 = 0 . Результаты распознавания по минимальному расстоянию представлены на рисунке 3.4. а) б) в) г) д) е) Рисунок 3.4 - а) Исходное изображение; б) результат распознавания автомобилей по минимальному расстоянию; в) результат распознавания деревьев по минимальному расстоянию; г) результат распознавания травы по минимальному расстоянию; д) результат распознавания воды по минимальному расстоянию; е) результат распознавания домов по минимальному расстоянию Оценка эффективности распознавания объектов методом распознавания по минимальному расстоянию: распознавание машин:

а) Исходное изображение; б) результат распознавания автомобилей с помощью расстояния Махаланобиса; в) результат распознавания деревьев с помощью расстояния Махаланобиса; г) результат распознавания травы с помощью расстояния Махаланобиса; д) результат распознавания воды с помощью расстояния Махаланобиса; д) результат распознавания домов с помощью расстояния Махаланобиса Оценка эффективности распознавания объектов с помощью расстояния Махаланобиса: распознавание машин: P 1 = 0,P2 = 0,36 ; распознавание деревьев: P 1 = 0,5,P2 = 0; распознавание домов: P 1 = 0,3,P2 = 0,4 ; распознавание травы: P 1 = 0,3,P2 = 0; распознавание воды: P 1 = 0,75 ,P2 = 0 .

Компенсация аппаратных искажений

Каждый из мультипроцессоров имеет определённые ресурсы. Так, есть специальная разделяемая память объемом 16 килобайт на мультипроцессор. Но это не кэш, так как программист может использовать её для любых нужд, подобно Local Store в SPU процессоров Cell. Эта разделяемая память позволяет обмениваться информацией между потоками одного блока. Важно, что все потоки одного блока всегда выполняются одним и тем же мультипроцессором. А потоки из разных блоков обмениваться данными не могут, и нужно помнить это ограничение. Разделяемая память часто бывает полезной, кроме тех случаев, когда несколько потоков обращаются к одному банку памяти. Мультипроцессоры могут обращаться и к видеопамяти, но с большими задержками и худшей пропускной способностью. Для ускорения доступа и снижения частоты обращения к видеопамяти, у мультипроцессоров есть по 8 килобайт кэша на константы и текстурные данные [104].

Мультипроцессор использует 8192-16384 (для G8x/G9x и GT2xx, соответственно) регистра, общие для всех потоков всех блоков, выполняемых на нём. Максимальное число блоков на один мультипроцессор для G8x/G9x равно восьми, а число warp — 24 (768 потоков на один мультипроцессор). Всего топовые видеокарты серий GeForce 8 и 9 могут обрабатывать до 12288 потоков единовременно. GeForce GTX 280 на основе GT200 предлагает до 1024 потоков на мультипроцессор, в нём есть 10 кластеров по три мультипроцессора, обрабатывающих до 30720 потоков. Знание этих ограничений позволяет оптимизировать алгоритмы под доступные ресурсы.

Видеочип получает ядро и создает копии для каждого элемента данных. Эти копии называются потоками (thread). Поток содержит счётчик, регистры и состояние. Для больших объёмов данных, таких как обработка изображений, запускаются миллионы потоков. Потоки выполняются группами по 32 штуки, называемыми warp ы. Warp ам назначается исполнение на определенных потоковых мультипроцессорах. Каждый мультипроцессор состоит из восьми ядер — потоковых процессоров, которые выполняют одну инструкцию MAD за один такт. Для исполнения одного 32-поточного warp а требуется четыре такта работы мультипроцессора (речь о частоте shader domain, которая равна 1.5 ГГц и выше) [9].

Мультипроцессор не является традиционным многоядерным процессором, он отлично приспособлен для многопоточности, поддерживая до 32 warp ов единовременно. Каждый такт аппаратное обеспечение выбирает, какой из warp ов исполнять, и переключается от одного к другому без потерь в тактах. Если проводить аналогию с центральным процессором, это похоже на одновременное исполнение 32 программ и переключение между ними каждый такт без потерь на переключение контекста. Реально ядра CPU поддерживают единовременное выполнение одной программы и переключаются на другие с задержкой в сотни тактов. Технология CUDA — это программно-аппаратная вычислительная архитектура NVIDIA, основанная на расширении языка Си, которая даёт возможность организации доступа к набору инструкций графического ускорителя и управления его памятью при организации параллельных вычислений. CUDA помогает реализовывать алгоритмы, выполнимые на графических процессорах видеоускорителей GeForce восьмого поколения и старше (серии GeForce 8, GeForce 9, GeForce 200), а также Quadro и Tesla.

С точки зрения программиста, графический конвейер является набором стадий обработки. Блок геометрии генерирует треугольники, а блок растеризации — пиксели, отображаемые на мониторе. Традиционная модель программирования GPGPU выглядит следующим образом:

Традиционная модель программирования GPGPU Чтобы перенести вычисления на GPU в рамках такой модели, нужен специальный подход. Даже поэлементное сложение двух векторов потребует отрисовки фигуры на экране или во внеэкранный буфер. Фигура растеризуется, цвет каждого пикселя вычисляется по заданной программе (пиксельному шейдеру). Программа считывает входные данные из текстур для каждого пикселя, складывает их и записывает в выходной буфер. И все эти многочисленные операции нужны для того, что в обычном языке программирования записывается одним оператором. Поэтому, применение GPGPU для вычислений общего назначения имеет ограничение в виде слишком большой сложности обучения разработчиков. Да и других ограничений достаточно, ведь пиксельный шейдер — это всего лишь формула зависимости итогового цвета пикселя от его координаты, а язык пиксельных шейдеров — язык записи этих формул с Си-подобным синтаксисом.

CUDA включает два API: высокого уровня (CUDA Runtime API) и низкого (CUDA Driver API), хотя в одной программе одновременное использование обоих невозможно, нужно использовать или один или другой. Высокоуровневый работает «сверху» низкоуровневого, все вызовы runtime транслируются в простые инструкции, обрабатываемые низкоуровневым Driver API (рисунок 4.9). Но даже «высокоуровневый» API предполагает знания об устройстве и работе видеочипов NVIDIA, слишком высокого уровня абстракции там нет

Разработка параллельных алгоритмов обработки изображений при прецедентном распознавании

Разделяемая память — это 16-килобайтный (в видеочипах нынешней архитектуры) блок памяти с общим доступом для всех потоковых процессоров в мультипроцессоре. Эта память весьма быстрая, такая же, как регистры. Она обеспечивает взаимодействие потоков, управляется разработчиком напрямую и имеет низкие задержки. Преимущества разделяемой памяти: использование в виде управляемого программистом кэша первого уровня, снижение задержек при доступе исполнительных блоков (ALU) к данным, сокращение количества обращений к глобальной памяти.

Память констант — область памяти объемом 64 килобайта (то же — для нынешних GPU), доступная только для чтения всеми мультипроцессорами. Она кэшируется по 8 килобайт на каждый мультипроцессор. Довольно медленная — задержка в несколько сот тактов при отсутствии нужных данных в кэше.

Текстурная память — блок памяти, доступный для чтения всеми мультипроцессорами. Выборка данных осуществляется при помощи текстурных блоков видеочипа, поэтому предоставляются возможности линейной интерполяции данных без дополнительных затрат. Кэшируется по 8 килобайт на каждый мультипроцессор. Медленная, как глобальная — сотни тактов задержки при отсутствии данных в кэше.

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

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

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

Разработка параллельных алгоритмов обработки изображений при прецедентном распознавании Прототип системы написан на языке C++ [25, 70, 60, 84] с использованием технологии CUDA. В качестве аппаратной платформы предполагается использование ЭВМ класса IBM PC с графическим процессором производства NVIDIA, поддерживающим технологию CUDA. В результате такого выбора аппаратно-программной платформы удалось реализовать кроссплатформенный программный продукт, максимально эффективно использующий современные массивно-параллельные архитектуры вычислительных устройств. Блок-схема параллельного алгоритма прецедентного распознавания объектов на ИЗП имеет вид

Ускорение, получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений, определялось величиной [23, 24]: S (и) = Т (п)/Т (и) (4.1) где величина n используется для параметризации вычислительной сложности решаемой задачи и понимается как количество входных данных задачи. Эффективность использования параллельным алгоритмом процессоров при решении задачи определялось соотношением [23, 24]: Е (п) = Т(п)/(рТ (и)) = S (п)/р (4.2) Величина эффективности определяет среднюю долю времени выполнения параллельного алгоритма, в течение которого процессоры реально используются для решения задачи.

Рисунок 4.10 – Зависимость времени вычислений на графическом процессоре NVIDIA от размерности изображения

101

Ускорение алгоритма прецедентного распознавания составило 131,13, а его эффективность - 0,68 (рисунок 4.10). Ускорение алгоритма компенсации аппаратных помех составило 182,17, эффективность равна 0,95.

Архитектура программной поддержки разработанных методов и алгоритмов прецедентного распознавания объектов на изображениях земной поверхности включает в себя следующие программные модули: - модуль компенсации аппаратных искажений; - модуль устранения теней объектов с изображения с помощью алгоритма парных регионов; - модуль оконтуривания фрагментов изображений, используя оператор Собеля; - модуль определение структуры объекта через отношение его длины к ширине; - модуль обучения по прецедентам на основе их субполосной обработки; - модуль распознавания по прецедентам на основе их субполосной обработки.

В качестве аппаратной платформы реализации программной поддержки прецедентного распознавания объектов на изображениях земной поверхности была выбрана ЭВМ класса IBM PC. В качестве операционной системы была выбрана система на базе ядра Linux 3.16. Были разработаны основные элементы интерфейса модулей программной поддержки, которые реализованы в консольном режиме. Программное обеспечение модулей компенсации аппаратных искажений является кроссплатформенным (межплатформенным) приложением и работает под управлением операционных систем (ОС) Linux [13, 14, 18, 85]. Модуль написан на языках программирования С/C++/CUDA C с применением библиотек BLAS, CUBLAS, Atlas, Lapack, OpenMP [5], программа трансляции кода GNU 4.9.

Программное обеспечение производит компенсацию аппаратных искажений на изображениях, устранение теней и оконтуривание фрагментов ИЗП, определение структуры объектов через отношение его длины к ширине, обучение и распознавание по прецедентам на основе их субполосной обработки. Вызов модуля осуществляется автоматически при запуске любого из модулей обработки изображений. Для этого достаточно в консоли bash ОС набрать команду “./run”. Входными данными являются растровые изображения в форматах jpeg, bmp, png. Входные данные располагаются в подкаталоге /bmp каталога размещения исполняемого файла модулей. Выходными данными являются растровые изображения в форматах jpeg, bmp, png. Выходные данные располагаются в подкаталоге /bmp каталога размещения исполняемого файла модулей. Для работы программного обеспечения требуется IBM совместимые ЭВМ со следующими минимальными характеристиками: