WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


На правах рукописи

Шишков Илья Иванович

Обработка и формирование растровых изображений в автоматизированных контролирующих системах

05.13.06 – Автоматизация и управление технологическими процессами и производствами (промышленность)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Орёл – 2012

Работа выполнена на кафедре «Информационные системы»в федеральном государственном бюджетном образовательном учреждении высшего профессио­ нального образования «Государственный университет — учебно-научно-производ­ ственный комплекс».

Научный консультант: доктор технических наук, профессор Константинов Игорь Сергеевич

Официальные оппоненты: Иноземцев Александр Николаевич доктор технических наук, профессор, Тульский государственный университет, заве­ дующий кафедрой «Автоматизированные ста­ ночные системы» Тараканов Олег Викторович кандидат технических наук, доцент, Академия ФСО России, заведующий кафедрой «Информатика и вычислительная техника»

Ведущая организация: Федеральное государственное бюджетное об­ разовательное учреждение высшего профессионального образования «Тамбовский госу­ дарственный технический университет»

Защита состоится 22 мая 2012 г. в 13:00 часов на заседании диссертационного со­ вета Д 212.182.01 при ФГБОУ ВПО «Госуниверситет — УНПК» по адресу: 302020, РФ, г. Орёл, Наугорское шоссе, д. 29, аудитория 212.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Госуниверси­ тет — УНПК».

Автореферат разослан 20 апреля 2012 г.

Учёный секретарь диссертационного совета, кандидат технических наук, доцент Волков В. Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ



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

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

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

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

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

Целью исследования является повышение эффективности обработки и формирования растровых изображений в автоматизированных контролирующих системах с учётом ограниченной вычислительной мощности современных персо­ нальных компьютеров.

Для достижения поставленной цели были сформулированы и решались сле­ дующие основные задачи.

1. Анализ методов и средств обработки и формирования растровых изобра­ жений, используемых в автоматизированных контролирующих системах.

2. Разработка и исследование модели процесса обработки растровых изобра­ жений в автоматизированных контролирующих системах.

3. Исследование методов и возможностей решения задачи визуального кон­ троля объектов по растровым изображениям на современных персональных ком­ пьютерах.

4. Разработка и исследование структурно-функциональной модели адаптив­ ной системы обработки растровых изображений.

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

6. Разработка прототипа адаптивной системы обработки растровых изобра­ жений и анализ результатов его применения.

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

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

соответствия результатов теоретических и экспериментальных исследований.

Научная новизна работы состоит в том, что:

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

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

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

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

– адаптация системы за счёт конфигурирования её подключаемыми модулями, – возможность автоматизации выбора алгоритма обработки на основании ана­ лиза доступного программного и аппаратного обеспечения.

Практическая значимость работы заключается в том, что разработанные теоретические положения реализованы в виде комплекса алгоритмов и программ, представляющего собой прототип адаптивной системы обработки растровых изоб­ ражений, а также в результатах внедрения указанного комплекса в ФГБОУ ВПО «Госуниверситет — УНПК» и ЗАО «Научприбор».

Результаты диссертационного исследования внедрены в учебный процесс ка­ федры «Информационные системы» ФГБОУ ВПО «Госуниверситет — УНПК» в рамках дисциплин «Компьютерная графика» и «Компьютерная обработка данных» и в ЗАО «Научприбор» в системе рентгеновского контроля «Express Inspection» и программно-аппаратном комплексе компьютерной томографии.

В основу диссертационной работы положены результаты исследований, полу­ ченные автором в ходе работ по программе «УМНИК» (проект «Программный комплекс оперативной обработки цифровых снимков большого размера») и Го­ сударственному контракту №14.740.11.1258 «Программные средства оперативной обработки полутоновых растровых изображений большого размера», выполняемо­ му по Федеральной программе «Научные и научно-педагогические кадры иннова­ ционной России» на 2009–2013 гг.

Апробация работы. Основные положения диссертационной работы докла­ дывались на следующих конференциях: IV Международной научно-технической конференции «Информационные технологии в науке, образовании и производ­ стве» (г. Орёл, 2010 г.); Международной научно-технической интернет-конферен­ ции «Информационные системы и технологии» (г. Орёл, 2011 г.); XVI научной конференции преподавателей и сотрудников ФГБОУ ВПО «Госуниверситета — УНПК» (г. Орёл, 2011 г.); II Международной научно-технической конференции «Компьютерные науки и технологии» (г. Белгород, 2011 г.); Международной на­ учно-практической конференции «Научные исследования и их практическое при­ менение. Современное состояние и пути развития» (г. Одесса, 2011 г.).

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

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

2. Метод повышения эффективности обработки растровых изображений.

3. Модель адаптивной системы обработки растровых изображений.

4. Параллельный алгоритм линейной фильтрации растровых изображений.

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

6. Прототип адаптивной системы обработки растровых изображений.

Структура и объем диссертации. Диссертационная работа изложена на 160 страницах и состоит из введения, четырёх глав, заключения, списка литера­ туры из 122 наименований и 2 приложений; содержит 4 таблицы и 26 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

При проведении анализа установлено, что во многих автоматизированных контролирующих системах растровые изображения и методы их обработки игра­ ют важную роль в интерпретации результатов контроля. В различных системах применяются изображения совершенно разных размеров: от 320200 пикселей до 16001200 пикселей. При этом максимальный размер применяемых изображений постоянно растёт.

Также проведённый анализ выявил, что в современных автоматизированных контролирующих системах применяются как специализированные форматы циф­ ровых изображений (например, радиометрический формат IS2), так и цифровые форматы общего назначения (JPEG, BMP, PNG, TIFF и т. д.).





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

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

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

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

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

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

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

Формально она определяется пятёркой Q, , , q0, f, где Q — множество со­ стояний, — входной алфавит, Q Q — множество переходов, q0 Q — начальное состояние, f Q — конечное состояние.

Множество состояний Q предлагаемой модели содержит 4 состояния, которые пронумерованы числами от 1 до 4. Начальным состоянием q0 является состояние 1, конечным состоянием f — состояние 4. Входным алфавитом предлагаемой моде­ ли являются различные операции обработки изображений: З — загрузка, С — со­ хранение, П — изменение параметров визуализации, В — визуализация, Ф — филь­ трация, О — окончание обработки. Таким образом, Q = {1, 2, 3, 4}, q0 = 1, f = 4, = {З, С, П, В, Ф, О}. Множество переходов приведено в таблице 1.

Таблица 1. Таблица переходов модели процесса обработки растровых изображений в автомати­ зированных контролирующих системах Символ З С П В Ф О Состояние 1 3 — — — — 2 3 2 3 — 3 3 — — — 2 — — 4 — — — — — — Важной особенностью предлагаемой модели является наличие в ней такой операции, как визуализация. Более того, в ней используется предположение о том, что результаты применения любой операции обработки изображений визуализи­ руются сразу после завершения её выполнения. Это связано с тем, что в данной работе рассматриваются автоматизированные, а не автоматические контролиру­ ющие системы. Следовательно, в них обязательно присутствует человек, который должен иметь возможность сразу же оценить результаты применения последней операции и принять решение о дальнейшем направлении обработки изображений.

Поэтому переходы из состояния 2 по символам «З», «П» и «Ф» осуществляются в состояние 3, из которого есть только один переход — обратно в состояние 2 по символу «В».

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

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

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

Таблица 2. Требования к эффективности операций обработки растровых изображений в авто­ матизированных контролирующих системах Операция Асимптотическая оценка вычислительной сложности Фильтрация O(S log S) Визуализация O(P ) Изменение параметров визуализации O(1) Загрузка O(S log S) Сохранение O(S log S) При разработке этих требований учитывался тот факт, что в рамках дан­ ной работы исследуется повышение скорости обработки растровых изображений при сохранении качества и функциональности. Поэтому для некоторых операций были выбраны менее жёсткие требования по сравнению с теоретически возмож­ ными. Например, для загрузки растрового изображения независимо от формата нужно обработать каждый его пиксель минимум один раз. Следовательно, вы­ числительная сложность операции загрузки имеет нижнюю оценку (S). Если в качестве требования к эффективности операции загрузки взять оценку O(S), то ей не будут удовлетворять методы загрузки изображений, сжатых, например, методом LZW, который требует O(S log S) операций. Следовательно, использова­ ние оценки O(S) в качестве требования к вычислительной сложности операции загрузки невозможно без ограничения функциональности.

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

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

Однако графические ускорители накладывают следующие ограничения на предназначенные для них алгоритмы:

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

параллельные потоки выполняются на графическом ускорителе группами размером от 32 потоков в каждой; в рамках одной группы все потоки должны вы­ полнять одну последовательность инструкций; несоблюдение этого правила ведёт к существенному снижению производительности;

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

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

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

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

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

Структура и качество снимков влияет также на скорость их обработки. То есть на основании анализа структуры и качества исходного изображения можно выбирать наиболее быстрый метод, обеспечивающий требуемое качество обработ­ ки. Например, рассмотрим зависимость выбора метода выделения границ объ­ ектов от структуры обрабатываемого изображения. Предположим, что входное изображение является бинарным и на нём изображено небольшое число крупных объектов. Тогда для выделения их границ достаточно применить поиск в ширину, обрабатывающий каждый пиксель один раз. Если же входное изображение име­ ет б ольшую глубину цвета, то определение границ объектов не так тривиально и необходимо применять более сложные методы, требующие неоднократного обра­ щения к каждому пикселю изображения. Таким образом, в данном случае анализ качества входного изображения, а именно глубины цвета, позволяет выбрать бо­ лее быстрый метод выделения границ.

Параллельную обработку растровых изображений можно осуществлять, только если на используемом компьютере установлено соответствующее обору­ дование. Если это не так, она будет производиться на центральном процессоре.

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

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

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

На рисунке 2 приведена разработанная в рамках диссертационного исследо­ вания структурно-функциональная модель адаптивной системы обработки раст­ ровых изображений, для каждой подсистемы которой созданы соответствующие структура и функциональная модель.

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

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

формирование множества фильтров;

формирование множества диалогов пользовательского интерфейса;

формирование множества поддерживаемых цифровых форматов изображе­ ний.

Каждому из этих направлений в модели соответствует база данных подключае­ мых модулей.

В модели представлено три вида связей. Связи, обозначенные сплошной ли­ нией, соответствуют запросам, которые подсистемы модели посылают друг другу.

Например, подсистема диалога с пользователем посылает в ядро системы запро­ сы на обработку команд пользователя, ядро в свою очередь, классифицировав полученную команду, посылает запрос на её выполнение другой подсистеме и т. д.

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

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

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

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

Параллельная обработка растровых изображений с использованием графи­ ческого ускорителя может быть реализована двумя путями. Во-первых, парал­ лелизм может заключаться в распределении выполняемой операции между цен­ тральным процессором и графическим ускорителем, которые будут параллельно выполнять требуемые вычисления. Кроме того, так как сам графический уско­ ритель поддерживает организацию произвольных параллельных вычислений, вся операция целиком может быть распараллелена на нём. Следовательно, из множе­ ства существующих моделей параллельных вычислений необходимо выбрать две:

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

В качестве первой из них было выбрано взаимодействие посредством обмена сообщениями с использованием распределённой памяти (рисунок 3). В качестве модели параллельных вычислений отдельно на графическом ускорителе была вы­ брана модель взаимодействия через общую память с использованием гибридной памяти (рисунок 4).

Рис. 3. Модель параллельных вычислений на Рис. 4. Модель параллельных вычислений от­ центральном процессоре и графическом уско­ дельно на графическом ускорителе рителе В качестве меры оценки времени работы параллельных алгоритмов было вы­ брано число циклов параллельного доступа к общей памяти как наиболее дли­ тельная и часто используемая операция.

В соответствии со сформулированными выше принципами был разработан алгоритм линейной фильтрации растровых изображений. Он осуществляет пре­ образование растрового изображения f размером M N пикселей с помощью фильтра размером m n по формуле a b g(x, y) = w(s, t) · f(x + s, y + t), (1) s=-a t=-b где g(x, y) — отклик фильтра;

m = 2a + 1, n = 2b + 1 (a, b N {0});

w(s, t) — коэффициент маски фильтра;

f(x, y) — пиксель обрабатываемого изображения.

При этом были разработаны последовательный алгоритм взаимодействия центрального процессора и графического ускорителя и параллельный алгоритм, выполняемый каждым процессором графического ускорителя (алгоритм 1). Алго­ ритм 1 предполагает, что имеется M · N процессоров; в нём используются обозна­ чения из формулы 1; параметр процедуры p задаёт порядковый номер процессора.

Алгоритм 1 Параллельный алгоритм линейной фильтрации для M · N процес­ соров 1: procedure Linear-Filter(p) p 2: y M 3: x p - y · M 4: sum 5: for s -a to a do 6: for t -b to b do 7: if 0 x + s M - 1 then 8: if 0 y + t N - 1 then 9: sum sum + w(s, t) · f(x + s, y + t) 10: end if 11: end if 12: end for 13: end for 14: g(x, y) sum 15: end procedure В реальной системе число процессоров обычно меньше, чем число пикселей обра­ батываемого изображения. Для решения этой проблемы была разработана моди­ фикация алгоритма 1, в которой каждый процессор последовательно выполняет линейную фильтрацию нескольких пикселей.

В процессе анализа алгоритма 1 было оценено количество осуществляемых им обращений к разделяемой памяти. Чтение интенсивности пикселя обрабатыва­ емого изображения, которое хранится в общей памяти, осуществляется в строке 9.

Эта операция находится внутри двух вложенных циклов for, которые выполняют m и n итераций соответственно. Следовательно, алгоритм 1 осуществляет O(nm) операций чтения общей памяти и одну операцию записи в общую память, осу­ ществляемую в строке 14. Таким образом, время работы алгоритма 1 оценивается как O(nm).

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

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

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

Алгоритм 2 Параллельный алгоритм восстановления томографического среза методом фильтрованных обратных проекций для M · N2 процессоров 1: procedure Backproject(p, row, column) 2: value 3: угол поворота, соответствующий проекции p 4: xs, ys позиция источника для угла поворота 5: xp, yp координаты центра пикселя (row, column) 6: l прямая, проходящая через точки (xp, yp) и (xs, ys) 7: if l пересекает линейку детекторов then 8: i номер детектора, который пересекает прямая l 9: value projection[p][i] 10: end if 11: Atomic-Add(g[row][column], value) 12: end procedure Как и для метода линейной фильтрации, для метода восстановления томогра­ фического среза были разработаны последовательный алгоритм взаимодействия центрального процессора с графическим ускорителем и параллельный алгоритм, выполняемый каждым процессором графического ускорителя (алгоритм 2). В по­ следнем предполагается, что в нашем распоряжении имеется M · N2 процессоров, и каждый процессор отвечает за обработку пары (проекция, пиксель). В нём ис­ пользуются следующие обозначения:

p — номер проекции;

row, column — координаты пикселя восстанавливаемого изображения;

projection[i][j] — значение j-й ячейки проекции с номером i;

g — восстановленное изображение;

Atomic-Add — операция атомарного инкремента.

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

При его анализе было оценено количество осуществляемых им обращений к разделяемой памяти. В процессе своего выполнения алгоритм 2 выполняет не бо­ лее одного чтения из разделяемой памяти. Это происходит в строке 9 в случае срабатывания проверки в строке 7. Процедура Atomic-Add в процессе своего вы­ полнения осуществляет одно чтение и одну запись в разделяемую память. Таким образом, оценка времени работы алгоритма 2 составляет O(1).

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

В четвёртой главе описана реализация и исследование прототипа адаптив­ ной системы обработки растровых изображений.

Архитектура прототипа адаптивной системы обработки растровых изобра­ жений соответствует разработанной структурно-функциональной модели (рису­ нок 2).

В процессе поиска средств реализации каждой из подсистем прототипа про­ водился анализ языков программирования и программных библиотек и осуществ­ лялся обоснованный выбор тех из них, которые позволяют создавать наиболее эффективные реализации. В результате для реализации прототипа адаптивной системы обработки растровых изображений был выбран язык программирования C++ и программные библиотеки OpenGL, Qt и CUDA.

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

Особенности реализации методов фильтрации растровых изображений с по­ мощью CUDA описаны на примере реализации разработанного параллельного алгоритма линейной фильтрации (см. алгоритм 1). Важнейшей её особенностью является выбор типа памяти для хранения ядра фильтра, входного и выходно­ го изображений. CUDA предоставляет несколько типов памяти для хранения пользовательских данных: локальную, разделяемую, глобальную, текстурную и константную. Каждый из них обладает своими преимуществами и накладывает определённые ограничения на механизмы доступа. Для хранения ядра фильтра, входного и выходного изображений обоснованно выбраны типы памяти, обеспечи­ вающие наиболее эффективный механизм доступа к ним.

Реализация параллельного алгоритма линейной фильтрации растровых изоб­ ражений была применена в системе рентгеновского контроля «Express Inspection», разработанной ЗАО «Научприбор». Эта система изначально поддерживала линей­ ную фильтрацию растровых изображений, которая выполнялась последователь­ ным алгоритмом на центральном процессоре. После внедрения параллельного алгоритма было проведено экспериментальное исследование повышения эффек­ тивности линейной фильтрации. Для этого измерялось время выполнения этой операции с помощью параллельного и последовательного алгоритмов.

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

На основании этих рассуждений был разработан план экспериментального исследования повышения эффективности выполнения линейной фильтрации за счёт применения параллельного алгоритма, в соответствии с которым был сфор­ мирован набор тестовых изображений, для каждого из которых было выполнено 200 прогонов параллельного и последовательного алгоритмов линейной фильтра­ ции. Для полученных серий значений с помощью критерия Пирсона была прове­ рена гипотеза о нормальности распределения генеральной совокупности (уровень значимости 0,05), которая не была отвергнута ни для одной из них. После этого были найдены оценки параметров нормального распределения: выборочная сред­ няя x и выборочное среднее квадратическое отклонение (СКО).

Анализ полученных значений показал, что для последовательного алгорит­ ма выборочное СКО изменяется от 3 до 30 мс, для параллельного — от 2 до 5 мс.

Найденные выборочные средние представлены на логарифмической шкале на ри­ сунке 5, график их отношения, отражающий снижение времени выполнения ли­ нейной фильтрации, приведён на рисунке 6. Из последнего графика видно, что применение параллельного алгоритма линейной фильтрации позволяет снизить время её выполнения минимум в 12 раз. Снижение скорости роста отношения вы­ борочных средних на промежутке (222, 224) объясняется недостатком процессоров графического ускорителя.

Рис. 5. Натуральные логарифмы выборочных Рис. 6. Снижение времени выполнения линей­ средних времени выполнения последователь­ ной фильтрации растровых изображений, вы­ ного и параллельного алгоритмов линейной званное применением параллельного алгорит­ фильтрации ма Прототип адаптивной системы обработки растровых изображений был ис­ пользован в качестве основы программного обеспечения программно-аппаратного комплекса компьютерной томографии, разрабатываемого лабораторией специаль­ ного программного обеспечения Госуниверситета — УНПК. В частности, в этом программно-аппаратном комплексе была применена реализация параллельного алгоритма восстановления томографического среза, разработанного в рамках дан­ ного диссертационного исследования (см. алгоритм 2). Для оценки повышения эф­ фективности этой операции было проведено экспериментальное исследование по плану, аналогичному тому, который использовался для исследования повышения эффективности линейной фильтрации.

В результате проведённого эксперимента гипотеза о нормальности распреде­ ления не была отвергнута ни для одной из полученных серий. Анализ найденных оценок параметров нормального распределения показал, что для последовательно­ го алгоритма выборочное СКО изменяется от 17 до 970 мс, а для параллельного — от 22 до 30 мс. Найденные выборочные средние представлены на логарифмиче­ ской шкале на рисунке 7, график их отношения, отражающий снижение времени выполнения восстановления томографического среза, приведён на рисунке 8. Из приведённых графиков видно, что применение параллельного алгоритма восста­ новления томографического среза позволяет снизить время её выполнения мини­ мум в 7 раз.

Рис. 7. Натуральные логарифмы среднего Рис. 8. Снижение времени выполнения восста­ времени выполнения исследуемых алгоритмов новления томографического среза, вызванное восстановления томографического среза применением параллельного алгоритма В заключении сформулированы основные результаты работы.

В приложениях приведены программные реализации разработанных алго­ ритмов.

Основные результаты работы. В ходе выполнения диссертационного ис­ следования получены следующие результаты.

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

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

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

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

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

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

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

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

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

10. Проведены исследования прототипа адаптивной системы обработки раст­ ровых изображений, которые показали его эффективность при решении задач об­ работки растровых изображений. В частности, происходит сокращение времени выполнения линейной фильтрации в 12 раз, а восстановления томографического среза — в 7 раз.

11. Результаты проведённых исследований внедрены в промышленных раз­ работках (система досмотрового рентгеновского контроля «Express Inspection» и программно-аппаратный комплекс компьютерной томогра­ фии на ЗАО «Научприбор») и в учебном процессе (дисциплины «Компьютерная графика» и «Компьютерная обработка данных» на кафедре «Информационные системы» ФГБОУ ВПО «Госуниверситет — УНПК»).

Список работ, опубликованных по теме диссертации в изданиях, рекомендованных ВАК при Минобрнауки России 1. Шишков, И. И. Разработка универсальной программной библиотеки вос­ становления томографического среза [Текст] / И. И. Шишков // Информационные системы и технологии. — 2010. — №3(59). — Орёл: ОрёлГТУ. — С. 58–62.

2. Шишков, И. И. О проблеме визуализации изображений в информацион­ ной системе компьютерной томографии [Текст] / И. И. Шишков, С. В. Терентьев // Фундаментальные и прикладные проблемы техники и технологии. — 2010. — №3(281). — Орёл: ОрёлГТУ. — С. 94–98. (личное участие 50%) 3. Шишков, И. И. [Текст] Линейная фильтрация растровых изображений с использованием графического ускорителя / И. И. Шишков // Информацион­ ные системы и технологии. — 2011. — №6(68). — Орёл: Госуниверситет — УНПК. — С. 19–26.

Монографии 4. Шишков, И. И. Оперативная обработка растровых изображений большого размера. Модели, алгоритмы и программные средства [Текст] / И. И. Шишков, И. С. Константинов, С. С. Мозгов. — LAP LAMBERT Academic Publishing GmbH & Co. KG, 2012. — 108 с. — ISBN: 978-3-8473-1835-4. (личное участие 33%).

Список работ, опубликованных по теме диссертации в материалах конференций 5. Шишков, И. И. Об особенностях разработки программной библиотеки вос­ становления томографического среза [Текст] / И. И. Шишков // «Информацион­ ные технологии в науке, образовании и производстве»(ИТНОП). Материалы IV Международной научно-технической конференции. — 2010. — Орёл: ОрёлГТУ. — Т. 2. — С. 198–202.

6. Шишков, И. И. К вопросу об оперативной обработке растровых изображе­ ний большого размера [Текст] / И. И. Шишков, А. А. Митин // «Информацион­ ные технологии в науке, образовании и производстве»(ИТНОП). Материалы IV Международной научно-технической конференции. — 2010. — Орёл: ОрёлГТУ. — Т. 3. — С. 194–197. (личное участие 50%).

7. Шишков, И. И. Способы сокрытия реализации инструментальных средств создания прикладных программ [Текст] / И. И. Шишков // «Информационные си­ стемы и технологии 2011». Материалы международной научно-технической интер­ нет-конференции. — 2011. — Орёл: Госуниверситет — УНПК. — Т. 2. — С. 110–113.

8. Шишков, И. И. Использование шаблонов проектирования в одной из за­ дач разработки инструментальных средств создания элементов графического ин­ терфейса пользователя [Текст] / И. И. Шишков // «Информационные системы и технологии». Материалы международной научно-технической интернет-конфе­ ренции. — 2011. — Орёл: Госуниверситет — УНПК. — Т. 2. — С. 114–119.

9. Шишков, И. И. Архитектура программного комплекса оперативной обра­ ботки цифровых снимков большого размера [Текст] / И. И. Шишков // Компью­ терные науки и технологии: сборник трудов Второй Международной научнотех­ нической конференции. — 2011. — Белгород: ООО «ГиК». — С. 697–701.

10. Шишков, И. И. Использование современных графических ускорителей для повышения эффективности обработки растровых изображений [Текст] / И. И. Шишков // Сборник научных трудов SWorld. По материалам международ­ ной научно-практической конференции «Научные исследования и их практиче­ ское применение. Современное состояние и пути развития 2011». — 2011. — Одесса:

Черноморье. — Т. 3. — С. 40–41.

Свидетельства о регистрации программ для ЭВМ 11. Шишков, И. И. Модуль формирования изображения среза методом филь­ трованных обратных проекций, производящий вычисления на графическом про­ цессоре // И. И. Шишков, И. С. Константинов, С. С. Мозгов и др. — Свидетельство о государственной регистрации программы для ЭВМ №2011611433, зарегистриро­ вано в Реестре программ для ЭВМ 14 февраля 2011 г. (личное участие 30%).

ЛР ИД №00670 от 05.01.2000 г.

Подписано к печати 16.04.2012 г.

Усл. печ. л.1,00 Тираж 100 экз.

Заказ №1Полиграфический отдел ФГБОУ ВПО «Госуниверситет — УНПК» 302030, г. Орёл, ул. Московская,






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.