Содержание к диссертации
Введение
Глава 1. Анализ средств и методов обработки и формирования растровых изображений 9
1.1. Анализ применения растровых изображений в автоматизированных контролирующих системах 9
1.2. Анализ методов обработки растровых изображений 14
1.3. Анализ инструментальных средств обработки растровых изображений 23
1.4. Формулировка задачи исследования 41
Выводы к главе 1 42
Глава 2. Моделирование процесса обработки растровых изображений в автоматизированных контролирующих системах 44
2.1. Разработка модели процесса обработки растровых изображений в автоматизированных контролирующих системах 44
2.2. Исследование процесса обработки растровых изображений в автоматизированных контролирующих системах 47
2.3. Исследование средств повышения эффективности обработки растровых изображений 53
2.4. Структурно-функциональное моделирование адаптивной системы обработки растровых изображений 57
Выводы к главе 2 76
Глава 3. Разработка и исследование алгоритмов обработки растровых изображений 78
3.1. Принципы создания параллельных алгоритмов обработки растровых изображений в адаптивной системе обработки растровых изображений 78
3.2. Алгоритм линейной фильтрации растровых изображений 86
3.3. Алгоритм восстановления томографического среза 94
Выводы к главе 3 105
Глава 4. Реализация и исследование прототипа адаптивной системы обработки растровых изображений 106
4.1. Проектирование прототипа адаптивной системы обработки растровых изображений 106
4.2. Особенности реализации прототипа адаптивной системы обработки растровых изображений 113
4.3. Применение параллельного алгоритма линейной фильтрации в системе рентгеновского контроля 128
4.4. Применение параллельного алгоритма восстановления томографического среза в программно-аппаратном комплексе компьютерной томографии 134
Выводы к главе 4 139
Заключение 140
Литература 142
Приложение А. Реализация подсистемы визуализации прототипа адаптивной системы обработки растровых изображений .154
Приложение Б. Реализация параллельного алгоритма линейной фильтрации 158
- Анализ методов обработки растровых изображений
- Структурно-функциональное моделирование адаптивной системы обработки растровых изображений
- Алгоритм восстановления томографического среза
- Особенности реализации прототипа адаптивной системы обработки растровых изображений
Введение к работе
Актуальность работы. Автоматизированные системы визуального контроля технических объектов и управления технологическими процессами по его результатам широко распространены в различных областях промышленности. В частности, к ним относятся системы оптического контроля печатных плат и изделий микроэлектроники, а также неразрушающего контроля деталей и конструкций. Процессы визуального контроля в большинстве данных систем сводятся к анализу полутоновых растровых изображений структуры изделий, получаемых такими методами, как микрофотография, рентгенография, ультразвуковая эхолокация и т.д., на предмет выявления таких дефектов, как микротрещины, неоднородности структуры и другие.
Методы и алгоритмы решения задач визуального контроля в настоящее время разработаны достаточно хорошо как в теории, так и на практике. Программное обеспечение известных систем обработки изображений предусматривает выполнение основных функций: высокочастотной и низкочастотной фильтрации, изменения контраста, интенсивности, масштаба, цветокоррекции. Однако существующие программные системы дороги, не предусматривают расширения, несовместимы по аппаратной платформе с другими системами. Кроме того, с каждым годом растёт объём обрабатываемых изображений и появляются всё новые классы прикладных задач, в значительной мере расширяющих границы области применения подобных алгоритмов. В результате возникает ситуация, в которой существующие системы обработки растровых изображений не включают всех необходимых процедур или обладают недостаточным быстродействием. Зачастую для их эксплуатации требуются дорогостоящие специализированные вычислительные мощности с очень высокой скоростью обработки.
Таким образом, необходимость повышения скорости обработки растровых изображений в автоматизированных контролирующих системах, а также высокая стоимость и недостаточное быстродействие существующих систем определяют актуальность создания одновременно высокоэффективных и недорогих средств обработки растровых изображений.
Объектом исследования является процесс обработки и формирования растровых изображений в автоматизированных контролирующих системах.
Предметом исследования являются методы и алгоритмы обработки и формирования растровых изображений.
Целью исследования является повышение эффективности обработки и формирования растровых изображений в автоматизированных контролирующих системах с учётом ограниченной вычислительной мощности современных персональных компьютеров.
Для достижения поставленной цели были сформулированы и решались следующие основные задачи.
-
Анализ методов и средств обработки и формирования растровых изображений, используемых в автоматизированных контролирующих системах.
-
Разработка и исследование модели процесса обработки растровых изображений в автоматизированных контролирующих системах.
-
Исследование методов и возможностей решения задачи визуального контроля объектов по растровым изображениям на современных персональных компьютерах.
-
Разработка и исследование структурно-функциональной модели адаптивной системы обработки растровых изображений.
-
Разработка и исследование алгоритмов параллельной обработки данных (параллельных алгоритмов) для реализации методов обработки растровых изображений.
-
Разработка прототипа адаптивной системы обработки растровых изображений и анализ результатов его применения.
Методы исследования. В качестве основных средств теоретических исследований использовались методы системного анализа, математического моделирования, дискретной математики, математической статистики, цифровой обработки изображений, а также методы оценки эффективности алгоритмов.
Достоверность и обоснованность научных положений, результатов, выводов и рекомендаций, приведенных в диссертационной работе, достигается за счёт: корректного применения известного математического аппарата; непротиворечивости и воспроизводимости результатов, полученных теоретическим путём; соответствия результатов теоретических и экспериментальных исследований.
Научная новизна работы состоит в том, что:
предложена автоматная модель процесса обработки и формирования растровых изображений в автоматизированных контролирующих системах, отличительной особенностью которой является то, что она учитывает присутствие человека в системе, обеспечивая своевременное предоставление ему результатов применения операций обработки изображений;
предложены параллельные алгоритмы обработки растровых изображений, отличительной особенностью которых являются высокая степень параллелизма и способность выполняться на большинстве современных графических ускорителей;
предложен метод повышения эффективности обработки и формирования растровых изображений на современном персональном компьютере, отличительной особенностью которого является применение графического ускорителя и разработанных параллельных алгоритмов;
предложена структурно-функциональная модель адаптивной системы обработки растровых изображений, отличительной особенностью которой являются:
адаптация системы за счёт конфигурирования её подключаемыми модулями,
возможность автоматизации выбора алгоритма обработки на основании анализа доступного программного и аппаратного обеспечения. Практическая значимость работы заключается в том, что разработанные
теоретические положения реализованы в виде комплекса алгоритмов и программ, представляющего собой прототип адаптивной системы обработки растровых изображений, а также в результатах внедрения указанного комплекса в ФГБОУ ВПО «Госуниверситет — УНПК» и ЗАО «Научприбор».
Результаты диссертационного исследования внедрены в учебный процесс кафедры «Информационные системы» ФГБОУ ВПО «Госуниверситет —УНПК» в рамках дисциплин «Компьютерная графика» и «Компьютерная обработка данных» и в ЗАО «Научприбор» в системе рентгеновского контроля «Express Inspection» и программно-аппаратном комплексе компьютерной томографии.
В основу диссертационной работы положены результаты исследований, полученные автором в ходе работ по программе «УМНИК» (проект «Программный комплекс оперативной обработки цифровых снимков большого размера») и Государственному контракту №14.740.11.1258 «Программные средства оперативной обработки полутоновых растровых изображений большого размера», выполняемому по Федеральной программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг.
Апробация работы. Основные положения диссертационной работы докладывались на следующих конференциях: IV Международной научно-технической конференции «Информационные технологии в науке, образовании и производстве» (г. Орёл, 2010 г.); Международной научно-технической интернет-конференции «Информационные системы и технологии» (г. Орёл, 2011г.); XVI научной конференции преподавателей и сотрудников ФГБОУ ВПО «Госуниверситета — УНПК» (г. Орёл, 2011г.); II Международной научно-технической конференции «Компьютерные науки и технологии» (г.Белгород, 2011г.); Международной научно-практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития» (г.Одесса, 2011г.).
Положения, выносимые на защиту.
-
Модель процесса обработки и формирования растровых изображений в автоматизированных контролирующих системах.
-
Метод повышения эффективности обработки растровых изображений.
-
Модель адаптивной системы обработки растровых изображений.
-
Параллельный алгоритм линейной фильтрации растровых изображений.
-
Параллельный алгоритм восстановления томографического среза методом обратных фильтрованных проекций.
6. Прототип адаптивной системы обработки растровых изображений.
Структура и объем диссертации. Диссертационная работа изложена на
Анализ методов обработки растровых изображений
Не существует общепринятой точки зрения, где заканчивается обработка изображений и начинаются другие смежные области, например, анализ изображений и машинное зрение. Во всем диапазоне от обработки изображений до машинного зрения нет четких границ, тем не менее, можно различать в нем методы низкого, среднего и высокого уровня. Методы низкого уровня представляют собой только примитивные операции типа предобработки с целью уменьшения шума, повышения контраста или улучшения резкости изображений. Для низкоуровневых методов характерен тот факт, что на входе и выходе присутствуют изображения. Обработка изображений на среднем уровне охватывает такие задачи, как сегментация (разделение изображения на области или выделение на нем объектов), описание объектов и сжатие их в удобную для компьютерной обработки форму, а также классификация (распознавание) отдельных объектов. Для методов среднего уровня характерно наличие изображений только на входе, на выход же поступают признаки и атрибуты, извлекаемые из этих изображений (например, границы областей, линии контуров, отличительные признаки конкретных объектов). Наконец, высокоуровневая обработка включает в себя «осмысление» набора распознанных объектов [26, 63].
Низкий, средний и высокий уровни — это очень крупные классы методов обработки изображений. Для проведения их дальнейшего анализа нужно рассмотреть декомпозицию этих классов более детально [26, 35, 36, 59, 89, 93].
Изображение — это двумерное отображение наблюдаемой «сцены», возникающее в результате регистрации лучистой энергии, исходящей из наблюдаемой «сцены», с помощью некоторого устройства—сенсора. При этом предполагается, что регистрируемый сенсором сигнал возникает в результате взаимодействия источника «освещения» с элементами изображаемой сцены в условиях эффектов отражения и поглощения энергии этого источника. Слова «освещение» и «сцена» взяты в кавычки, чтобы подчеркнуть тот факт, что они носят значительно более общий характер, чем в привычной ситуации, когда источник видимого света освещает трёхмерную сцену объектов. Например, освещение может порождаться источником инфракрасного, рентгеновского и даже ультразвукового излучения. В роли элементов сцены могут выступать как видимые объекты, так и молекулы или скелет человека. Зафиксировав энергию, отражённую или пропущенную элементами сцены, сенсор генерирует набор выходных сигналов, каждый из которых пропорционален интегралу световой энергии, принятой соответствующим элементом сенсора. С помощью цифровой и аналоговой электроники эти выходные сигналы поочерёдно преобразуются в комплексный видеосигнал, который и представляет собой изображение сцены. Стоит заметить, что регистрация изображения может оказаться предельно простой, как в случае, когда исходное изображение уже представлено в цифровой форме. В общем случае стадия регистрации изображения включает некоторую предобработку, например, масштабирование.
За методами улучшения изображений стоит идея выявления плохо различимых деталей или просто подчеркивания интересующих характеристик на исходном изображении. Известным примером улучшения является усиление кон траста изображения. Важно иметь в виду, что улучшение качества — весьма субъективная область в обработке изображений.
Главная цель улучшения заключается в том, чтобы результат оказался более подходящим с точки зрения конкретного применения. Слово «конкретное» является здесь важным, поскольку оно с самого начала устанавливает, что методы улучшения в значительной степени проблемно ориентированы. Так, например, метод, являющийся весьма полезным для улучшения рентгеновских изображений, не обязательно окажется наилучшим для обработки снимков Марса, переданных космическим аппаратом.
Множество подходов к улучшению изображений разделяют на две большие категории: методы обработки в пространственной области (пространственные методы) и методы обработки в частотной области (частотные методы). Пространственные методы условно включают в себя две основные группы [35, 36, 41].
1. Улучшение зрительных характеристик: повышение контраста, четкости, выравнивание яркости по полю и т.д. [26, 41, 93]. Важно отметить, что речь здесь идет о качестве как о характеристике самого изображения (а не о мере близости к некоторому эталону [49]), то есть цель обработки — получение в каком-то смысле «удобного для наблюдения», «хорошего» изображения.
2. Препарирование: обработка изображения с целью выделения на нём некоторых существенных деталей или особенностей и подавления несущественных. В этом случае мы получаем сильно отличающееся от исходного изображение, которое более удобно для последующего анализа или визуальной интерпретации. К методам препарирования относятся преобразование яркостного среза, контрастное масштабирование, преобразование в псевдоцвета [27, 41].
Методы обработки в частотной области основываются на модификации сигнала, формируемого путем применения к изображению преобразования Фурье. К этим методам относится сглаживающая частотная фильтрация, частотное повышение резкости, гомоморфная фильтрация [26, 49-51, 93].
Как и при улучшении изображений, конечной целью восстановления является повышение качества изображения. Несмотря на пересечение областей применения методов обоих классов, улучшение изображений является в большей степени субъективной процедурой, в то время как процесс восстановления имеет в основном объективный характер. При восстановлении делается попытка реконструировать или воссоздать искажённое изображение, используя априорную информацию о явлении, которое вызвало ухудшение изображения [27, 49]. Поэтому методы восстановления основаны на моделировании процессов искажения и применении обратных процедур для воссоздания исходного изображения.
Решение этой задачи обычно включает разработку критериев качества, которые дают возможность объективно оценить полученный результат. Напротив, методы улучшения изображений в основном представляют собой эвристические процедуры, предназначенные для такого воздействия на изображение, которое позволит затем использовать преимущества, связанные с психофизическими особенностями зрительной системы человека. Например, процедура усиления контраста рассматривается как метод улучшения, поскольку в результате её применения изображение становится более приятным для глаза, тогда как процедура обработки смазанного изображения, основанная на применении обратного оператора, рассматривается как метод восстановления.
Методы восстановления изображений включают пространственное подавление шумов, частотное подавление шумов, фильтрацию методом минимизации среднего квадратического отклонения [26, 41, 93].
Структурно-функциональное моделирование адаптивной системы обработки растровых изображений
Структура предлагаемой адаптивной системы обработки растровых изображений представлена на рисунке 2.2. На наиболее высоком уровне эта система состоит из следующих компонентов.
Ядро адаптивной системы обработки растровых изображений координирует работу всех её подсистем при обработке команд пользователя. Получив очередную команду от подсистемы диалога с пользователем, она распознаёт её и посылает запросы соответствующим подсистемам для её обработки.
Подсистема визуализации изображений выполняет отображение одного или нескольких изображений, отвечает за оперативное обновление изображения при изменении параметров визуализации, а также отвечает за отображение некоторых элементов интерфейса пользователя (например, визуализация контура, задающего выделенную часть изображения).
Подсистема представления изображений в оперативной памяти задаёт представление растрового изображения, не зависящее от его исходного формата и используемое для реализации всех функций системы. Наличие в системе
Подсистема визуализации изображении единственного представления растровых изображений в оперативной памяти существенно облегчает разработку и расширение многих её подсистем. Например, для поддержки сохранения в различные форматы достаточно реализовать преобразование внутреннего представления в каждый из этих форматов. Это значительно проще, чем реализовывать преобразования для каждой пары поддерживаемых форматов.
Подсистема загрузки и сохранения изображений отвечает за загрузку и сохранение растровых изображений в различные цифровые форматы: BMP, JPEG, PNG, TIFF и т.д. При загрузке изображения она определяет его формат и загружает, преобразуя в единое внутреннее представление. Сохранение изображения осуществляется по обратной схеме: внутреннее представление преобразуется в требуемый выходной формат и сохраняется на внешнем носителе.
Подсистема фильтрации изображений отвечает за применение операций фильтрации, таких как изменение яркости, контрастности, пространственная линейная фильтрация, выделение контуров и т. д.
Подсистема диалога с пользователем обеспечивает взаимодействие с пользователем и предоставляет ему доступ к функциям системы.
Подсистемы загрузки фильтров, расширений интерфейса пользователя и цифровых форматов изображений используются для конфигурирования адаптивной системы обработки растровых изображений. Они отвечают за загрузку подключаемых модулей, их классификацию и внедрение в систему.
Базы данных фильтров, расширений интерфейса пользователя и цифровых форматов изображений содержат множество подключаемых модулей, расширяющих функциональность соответствующей подсистемы.
В предлагаемой адаптивной системе обработки растровых изображений принцип адаптивности реализуется за счёт её конфигурирования подключаемыми модулями, которое осуществляется в трёх направлениях:
формирование множества фильтров;
формирование множества диалогов пользовательского интерфейса;
формирование множества поддерживаемых форматов изображений.
В модели представлено три вида связей. Связи, обозначенные сплошной линией, соответствуют запросам, которые подсистемы модели посылают друг другу. Например, подсистема диалога с пользователем посылает в ядро системы запросы на обработку команд пользователя, ядро в свою очередь, классифицировав полученную команду, посылает запрос на её выполнение другой подсистеме и т. д.
Связи, обозначенные пунктирной линией, отражают движение информации об изображении в системе. Например, подсистема визуализации изображений посылает подсистеме представления изображений в оперативной памяти запрос с целью получения информации о визуализируемом изображении: размерах, глубине цвета, цвете пикселей и т. д. Связь между этими подсистемами, обозначенная пунктирной линией, соответствует получению этой информации.
Наконец, связи, обозначенные штрих-пунктирной линией, отражают перемещение в модели подключаемых модулей. Подсистемы загрузки фильтров, расширений интерфейса и цифровых форматов изображений обращаются к соответствующим базам данных, загружают из них в систему подключаемые модули и внедряют их в соответствующую подсистему.
Рассмотрим более подробные модели каждой подсистемы, выделенной в адаптивной системе обработки растровых изображений.
Представление изображения в оперативной памяти не должно зависеть от формата, из которого это изображение было загружено. Оно должно предоставлять доступ к пикселям изображения, а также к другим его параметрам: размерам, разрешающей способности, глубине цвета и т. д.
Как было показано в 2.2.2, обращение к пикселям изображения должно выполняться за константное время. Существуют различные методы представления растровых изображений в оперативной памяти, обеспечивающие такую оценку вычислительной сложности доступа к пикселям. Среди них представление линейным массивом байтов, двумерным массивом байтов, линейным массивом битов и многомасштабной пирамидой [1, 89, 93]. Каждый из этих способов имеет свои достоинства и недостатки. Для достижения высокой производительности, возможно, может понадобиться комбинировать указанные способы или изменять их в зависимости от решаемой задачи.
Чтобы обеспечить эту возможность подсистема представления изображения в оперативной памяти должна инкапсулировать используемый ею метод. То есть она должна предоставлять только интерфейс доступа к элементам изображения, не давая априорной информации о его внутреннем устройстве [88]. Таким образом, в качестве модели подсистемы представления изображения в оперативной памяти можно использовать множество предоставляемых ею операций:
чтение ширины и высоты изображения в пикселях;
чтение размера изображения в байтах;
чтение цвета пикселя по заданным координатам (ж, у);
установка цвета пикселя по заданным координатам (х,у);
чтение разрешающей способности изображения (количество пикселей на единицу длины);
чтение глубины цвета изображения;
создание изображения по заданным размерам, разрешающей способности и глубине цвета.
Структурная схема подсистемы визуализации изображений представлена на рисунке 2.3. Она состоит из следующих компонентов.
Модуль управления геометрией изображения. В процессе визуализации отображается не всё изображение, а некоторая его прямоугольная область, называемая далее областью отображения. Это необходимо для обеспечения возможности выполнения операций масштабирования и перемещения по изображению за 0(1), что соответствует требованиям к эффективности операций изменения параметров визуализации, сформулированным в 2.2.2. При перемещении по изображению область отображения смещается на соответствующий вектор (dx, dy), в процессе выполнения масштабирования с коэффициентом к— её размеры изменяются в к раз. Рассмотрим рисунок 2.4, наглядно иллюстрирующий данный принцип функционирования модуля управления геометрией изображения. В верхней части рисунка 2.4(a) представлено визуализируемое изображение и исходная область отображения, в нижней — соответствующее изображение, сформированное на экране дисплея. Рисунок 2.4(6) демонстрирует результат смещения изображения на вектор (dx,dy): размеры области отображения не изменились, однако произошло смещение её верхнего левого угла. Наконец, на рисунке 2.4(B) показан результат выполнения операции масштабирования с коэффициентом к: размеры области отображения изменились в к раз, а положение верхнего левого угла осталось неизменным.
Алгоритм восстановления томографического среза
В рамках разработки адаптивной системы обработки растровых изображений был создан параллельный алгоритм восстановления томографического среза методом обратных фильтрованных проекций. При этом рассматривалась круговая веерная схема получения проекций и трансмиссионная вычислительная томография [43, 71, 72].
Для реализации восстановления двумерного томографического среза был выбран именно этот метод, так как он является наиболее эффективным в вычислительном отношении, вследствие чего почти во всех коммерческих рентгеновских томографах используются варианты именно этого свёрточного алгоритма [8, 68]. Детальный анализ метода обратных фильтрованных проекций выходит за рамки данной работы, поэтому здесь он описан лишь в виде, доста точном для разработки параллельного алгоритма. Метод подробно рассмотрен в [43, 68, 102].
В методе фильтрованных обратных проекций сначала осуществляется одномерная фильтрация каждой проекции, после чего производится операция обратного проецирования, результатом которой является оценка искомого изображения. Суть операции обратного проецирования заключается в получении двумерной функции, называемой суммарным изображением, исходя из набора одномерных проекций. При обратном проецировании для каждой проекции р(Е,,у) находится так называемая обратная проекция b(x,y,v) (рисунок 3.5):
Смысл обратной проекции заключается в том, что одномерная проекция как бы «размазывается» на всю двумерную плоскость перпендикулярно оси проецирования. Таким образом, значение текущего отсчёта приписывается всем точкам, лежащим на прямой в неподвижной системе координат. Суммарное изображение получается суперпозицией всех обратных проекций [8].
Восстановление томографического среза на графическом ускорителе является темой многих работ последних лет [56, 82, 83, 105, 113, 117, 121]. Большинство из них посвящено выполнению восстановления методом фильтрованных обратных проекций на графическом ускорителе конкретной модели с применением специализированных программных средств (например, CUDA [ПО]).
В данной работе был разработан параллельный алгоритм, осуществляющий восстановление томографического среза размером N х N пикселей из М проекций, каждая из которых представляет собой массив из К значений. При этом созданный алгоритм работает в рамках модели, описанной в 3.1.2, и удовлетворяет сформулированным в 3.1.1 ограничениям.
Как и алгоритм линейной фильтрации, алгоритм восстановления томографического среза нужно рассматривать как с точки зрения взаимодействия центрального процессора с графическим ускорителем, так и с точки зрения вычислений, выполняемых на графическом ускорителе. Взаимодействие центрального процессора и графического ускорителя представлено алгоритмом 3.4.
Алгоритм, выполняемый каждым процессором графического ускорителя, представлен в виде процедуры BACKPROJECT и приведён ниже (см. алгоритм 3.5, страница 98). В нём предполагается, что в нашем распоряжении имеется М N2 процессоров и каждый процессор отвечает за обработку пары (проекция, пиксель). В алгоритме 3.5 используются следующие обозначения:
р — номер проекции;
row, column — координаты пикселя восстанавливаемого изображения;
projection[i][j] —значение j-ft ячейки проекции с номером г:
д — восстановленное изображение.
Первым действием алгоритма является вызов функции GET-VALUE, осуществляющей все необходимые вычисления. Причина выненесения этих вычислений в отдельную функцию приведена ниже.
Алгоритм 3.4 Взаимодействие ЦП и ГУ в процессе параллельного выполнения восстановления томографического среза
І: for і — 1 to М do
2: выполнить фильтрацию г-й проекции
3: ЄПСІ for
4: Выделить в разделяемой памяти графического ускорителя область размером в(МЙГ) для хранения проекционных данных.
5: Выделить в разделяемой памяти графического ускорителя область размером 0(iV2) для формирования восстановленного изображения.
6: Скопировать проекционные данные из оперативной памяти в память графического ускорителя.
7: Послать графическому ускорителю команду на выполнение восстановления томографического среза.
8: По окончании обработки скопировать восстановленное изображение из памяти графического ускорителя в оперативную память компьютера.
9: Освободить выделенную на графическом ускорителе память.
В первую очередь функция GET-VALUE осуществляет присваивание нуля переменной value (строка 2). Эта переменная хранит то значение, которое будет добавлено к интенсивности пикселя (row, column) восстановленного изображения в результате обратного проецирования проекции с номером р. Затем определяется положение (xs,ys) источника излучения в неподвижной системе координат, соответствующее проекции р (строки 3-4). Для этого сначала вычисляется величина у — угол поворота источника относительно оси абсцисс (см. рисунок 3.5). Для её нахождения используется формула где а —угол, на который осуществил поворот источник в процессе съёмки (на практике а Є [тг, 27г] [43]).
Алгоритм 3.5 Параллельный алгоритм восстановления томографического среза методом фильтрованных обратных проекций для М N2 процессоров
І: function GET-VALUE(P, row, column)
2: value — 0
3: "V — угол поворота, соответствующий проекции р
4: ж,, ys «— позиция источника для угла поворота "V
5: хр, г/р — координаты центра пикселя (raw, column)
6: I — прямая, проходящая через точки (хр, Ур) и (xs, ys)
7: if I пересекает линейку детекторов then
8: г 4— номер детектора, который пересекает прямая І
9: value і— projection\p][i]
10: ЄПОІ if
II: return value
12: end function
13: procedure BACKPROJECT(P, row, column) i4: v r- GET-VALUE(P, row, column) is: ATOMIC-ADD(g[row] [со/штт], v) 16: end procedure
После этого вычисляются координаты центра пикселя (row, column) (точка (хр,ур)) и строится прямая /, проходящая через точки (xs,ys) и (хр,ур). Если эта прямая пересекает линейку детекторов, значит, интенсивность пикселя (row, column) возымела влияние на проекцию р. В этом случае определяется номер детектора, который пересекает прямая I и в переменную value заносится значение соответствующей ячейки массива projection (строки 8-9). Если же прямая I не пересекается с линейкой детекторов, то излучение, прошедшее через пиксель (row, column), не было зафиксировано ни одним детектором при выполнении съёмки под углом у и значение переменной value останется равным нулю (см. рисунок 3.6). На этом выполнение функции GET-VALUE завершается.
Особенности реализации прототипа адаптивной системы обработки растровых изображений
В данном разделе описаны наиболее важные особенности реализации некоторых подсистем прототипа адаптивной системы обработки растровых изображений. Применение описанных в этом разделе приёмов обеспечивает выполнение приведённых в 2.2.2 требований к эффективности операций обработки растровых изображений.
Представление изображения в оперативной памяти реализовано с помощью класса Image (листинг 4.1) [89]. В нём предполагается, что для хранения интенсивности одного пикселя требуется 16 бит. Изображение представляется линейным массивом двухбайтных элементов, указатель на первый элемент которого хранится в поле dataPtr; для хранения размеров изображения используются поля width и height [81]. При этом для хранения указателя на массив пикселей используется специальный класс QSharedPointer [107]. Это сделано для обеспечения автоматического освобождения выделенной для хранения изображения памяти в момент уничтожения экземпляра класса Image. Кроме того, QSharedPointer осуществляет подсчёт ссылок, что позволяет избежать проблемы «висячих» указателей при копировании экземпляров Image. Интерфейс класса Image предоставляет различные варианты доступа к элементам изображения:
методы getPixel и setPixel позволяют читать и изменять цвет заданного пикселя;
метод pixels возвращает указатель, по которому можно обратиться ко всем пикселям изображения;
метод scanLine возвращает указатель на первый пиксель заданной строки.
Существуют две перегрузки метода pixels: константная (строка 28) и неконстантная (строка 29). Первая используется в операциях чтения, вторая —в операциях записи.
Оценим эффективность приведённой реализации. Как было сказано выше, чтение интенсивности пикселя по заданным координатам осуществляет метод getPixel (строка 20). Из его реализации видно, что сначала вычисляется позиция в линейном массиве пикселей, соответствующая переданным координатам. В классе Image изображение хранится в памяти построчно, поэтому искомая позиция равна абсциссе, к которой прибавлена ордината, умноженная на ширину строки изображения (строка 21). После вычисления позиции из функции возвращается соответствующее 16-битное значение линейного массива пикселей. Данная реализация, очевидно, имеет асимптотику 0(1). Метод setPixel (строка 20) реализован аналогично. Более того, оба рассматриваемых метода определены в объявлении класса Image, то есть в соответствии с правилами
Листинг 4.2. Реализация последовательной обработки пикселей языка C++ они являются встраиваемыми; при обращении к ним не будет осуществляться вызов функции, что повышает скорость их выполнения [40].
Недостатком методов getPixel и setPixel является то, что при каждом обращении к пикселю осуществляется одно умножение, одно сложение и одна операция индексации массива. Эта реализация является неэффективной при необходимости последовательного обращения ко всем пикселям изображения. Для того, чтобы преодолеть этот недостаток, методы pixels сделаны открытыми. Последовательная обработка всех пикселей может осуществляться так, как показано в листинге 4.2. В нём для обращения к очередному пикселю изображения осуществляется только операция разыменования указателя. Метод getSize класса Image возвращает количество пикселей, из которого состоит изображение.
Как показано в 1.3.2, современные дисплеи способны отображать 256 различных оттенков серого. Так как для хранения интенсивности пикселя изображения используется 16 бит, то возникает задача гамма-коррекции интенсивно-стей — преобразования значения интенсивности пикселя из 16-битного формата в 8-битный [22, 26]. В общем виде это преобразование можно описать с помощью функции f(is, min, max), которая отображает исходное значение интенсивности is с учётом порогов визуализации min и max в диапазон от 0 до 255, причём
Таким образом, перед выводом изображения интенсивность каждого пикселя должна быть преобразована с помощью функции /. При каждом изменении параметров тгп или max необходимо повторно осуществлять гамма-коррекцию и выводить изображение.
В процессе поиска наиболее эффективного способа реализации подсистемы визуализации изображений было разработано и исследовано несколько методов с использованием OpenGL [91].
Метод, основанный на использовании массива скорректированных значений, представляет собой следующую последовательность действий.
1. Для каждого значения интенсивности от 0 до 65535 вычисляется соответствующее значение функции / и сохраняется в массиве скорректированных значений тар.
2. С его помощью для каждого пикселя изображения определяется соответствующее значение, в результате в памяти формируется скорректированное изображение.
3. Командой OpenGL glRasterPos устанавливается позиция вывода изображения на экране дисплея.
4. Скорректированное изображение выводится командой glDrawPixels. Однако данный метод неэффективен, так как при его использовании преобразование интенсивностей пикселей осуществляется в оперативной памяти. Для повышения скорости гамма-коррекции необходимо добиться, чтобы оно осуществлялось видеокартой. Кроме того, можно выделить ещё один важный недостаток—использование команды glRasterPos. Как сказано в [122], эта команда устанавливает позицию вывода нижнего левого пикселя изображения. Если переданная ей точка выходит за границы видимого объёма, то позиция вывода изображения не определена. Это заставляет программиста обеспечивать постоянное отображение нижнего левого пикселя, что делает невозможным перемещение по изображению, если оно выходит за границы окна.
Избавиться от первого из указанных недостатков позволяет подход, основанный на задании таблицы отображения. OpenGL поддерживает набор простых математических операций, которые выполняются над пикселями в момент, когда они выводятся в буфер цвета. Задание типа преобразования осуществляется командой glPixelTransf ег. Одной из поддерживаемых этой командой операций является отображение цветов, которое активизируется вызовом glPixelTransferi с параметрами GL_MAP_COLQR и GL_TRUE. После этого отдельно для каждой компоненты цвета необходимо задать таблицу отображения, которая представляет собой одномерный массив, индексируемый исходным цветом и содержащий новые значения интенсивностей. Загрузка таблицы отображения осуществляется командой glPixelMap. Таким образом, если активировать отображение цветов и в качестве таблицы отображения использовать массив тар, то гамма-коррекция будет осуществляться видеокартой в процессе вывода на экран. Это существенно ускоряет процесс визуализации изображения, однако не решает проблему невозможности перемещения по изображению.
Как показали дальнейшие исследования, лучших результатов удается достичь, если применить метод, использующий текстурирование. Отображение цветов в OpenGL выполняется не только при прямом копировании пикселей в буфер цвета с помощью команды glDrawPixels, но и при создании текстуры командой glTexImage2D. Таким образом, если выводить изображения путём наложения текстуры на прямоугольник, имеющий размеры окна вывода, то путём изменения текстурных координат можно обеспечить масштабирование и перемещение по изображению при сохранении высокой скорости гамма-коррекции и вывода. Единственной проблемой является то, что отображение цветов текстуры осуществляется при её загрузке, то есть в буфере видеокарты хранится уже изменённая текстура. Следовательно, при изменении порогов визуализации необходимо осуществлять повторную загрузку текстуры.
