Метод и алгоритмы обработки изображений пространственных объектов на базе преобразования Хафа, инвариантные к преобразованиям вращения, масштабирования и переноса Морозовский Кирилл Валерьевич

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

Введение

1. Применение преобразования Хафа в задачах обработки изображений и 1.1 Обзор методов обработки изображений пространственных объектов 15

1.2 Реализация стандартного преобразования Хафа 18

1.3 Преобразование Радона и его связь с преобразованием Хафа 19

1.4 Преобразование Хафа для обнаружения прямой на плоскости

1.5 Модификации преобразования Хафа для обнаружения прямых на плоскости 26

1.5.1 Вероятностное преобразование Хафа 26

1.5.2 Прогрессивное вероятностное преобразование Хафа 28

1.5.3 Комбинированное преобразование Хафа 29

1.5.4 Случайное преобразование Хафа 30

1.5.5 Иерархическое преобразование Хафа 31

1.5.6 Адаптивное преобразование Хафа 33

1.6 Распознавание параметрически заданных форм с помощью 1.7 Обобщенное двумерное преобразование Хафа 38

1.8 Обобщенное трехмерное преобразование Хафа 40

1.9 Сегментация отсчетов объекта на сцене

1.9.1 Сегментация пространственно изолированных объектов на основе анализа связности их отсчетов

1.9.2 Сегментация пространственных объектов, основанная на параметризации отсчетов объекта 48

2. Модифицированное обобщенное трехмерное преобразование Хафа инвариантное к параметрам вращения и масштабирования 51

2.1 Модифицированное обобщенное трехмерное преобразование Хафа 51

2.1.1 Алгоритм распознавания изображений пространственных объектов на базе модифицированного обобщенного трехмерного преобразования Хафа 58

2.2 Комбинированное модифицированное обобщенное трехмерное преобразование Хафа 59

2.2.1 Алгоритм распознавания изображений пространственных объектов на базе комбинированного модифицированного обобщенного трехмерного преобразования Хафа 62

2.3 Формирование поля нормалей 63

2.4 Адаптивное модифицированное обобщенное трехмерное преобразование Хафа 65

2.5 Методика распараллеливания разработанных алгоритмов распознавания

2.5.1 Реализация модифицированного трехмерного обобщенного преобразования Хафа на графическом процессоре 69

2.5.2 Вычислительная оптимизация комбинированного преобразования Хафа

3. Оценка параметров пространственных объектов на базе преобразования Хафа 85

3.1 Оценка параметров вращения изображений пространственных объектов на базе преобразования Хафа 85

3.1.1 Алгоритм нахождения параметров вращения на базе преобразования Хафа 89

3.2 Определение параметров вращения на основе анализа окружностей на поверхности сферы с помощью преобразования Хафа 93

3.2.1 Алгоритм определения параметров вращения пространственных объектов на базе преобразования Хафа на основе анализа окружностей, на поверхности сферы 102

3.3 Оценки коэффициента масштабирования пространственных изображений

3.4 Методика распараллеливания алгоритмов определения параметров вращения пространственных объектов на базе графического сопроцессора 107

3.4.1 Вычислительная оптимизация первого алгоритма оценки параметров

3.4.2 Вычислительная оптимизация второго алгоритма оценки параметров

4. Экспериментальное исследование помехоустойчивости и быстродействия алгоритмов распознавания и оценки параметров пространственного объекта ... 114

4.1 Экспериментальное исследование помехоустойчивости модифицированного обобщенного преобразования Хафа при неизвестных параметрах вращения и масштабирования 115

4.2 Экспериментальное исследование помехоустойчивости комбинированного преобразования Хафа 120

4.3 Экспериментальная оценка помехоустойчивости разработанного первого алгоритма определения параметров вращения на базе преобразования Хафа 125

4.4 Экспериментальная оценка помехоустойчивости разработанного второго алгоритма определения параметров вращения на базе преобразования Хафа 134

4.5 Экспериментальная оценка помехоустойчивости, разработанного алгоритма оценки коэффициента масштабирования пространственного объекта на 4.6 Экспериментальное исследование быстродействия разработанных алгоритмов распознавания пространственных объектов и оценки параметров вращения пространственных объектов на базе технологии CUDA 139

4.6.1 Экспериментальное исследование быстродействия модифицированного обобщенного преобразования Хафа на базе технологии CUDA 140

4.6.2 Экспериментальное исследование быстродействия комбинированного преобразования Хафа на базе технологии CUDA 143

4.6.3 Экспериментальное исследование быстродействия первого алгоритма оценки параметров вращения пространственных объектов на базе преобразования Хафа с помощью технологии CUDA 145

4.6.4 Экспериментальное исследование быстродействия второго алгоритма оценки параметров вращения пространственных объектов на базе преобразования Хафа с помощью технологии CUDA 146

4.7 Автоматическая сегментация органов тела человека по томографическим изображениям на базе модифицированного обобщенного трехмерного преобразования Хафа

• Модификации преобразования Хафа для обнаружения прямых на плоскости
• Алгоритм распознавания изображений пространственных объектов на базе модифицированного обобщенного трехмерного преобразования Хафа
• Определение параметров вращения на основе анализа окружностей на поверхности сферы с помощью преобразования Хафа
• Экспериментальное исследование помехоустойчивости комбинированного преобразования Хафа

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

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

Одним из распространенных методов, используемых для обработки изображений, является преобразование Хафа. Обобщенное трехмерное преобразование Хафа позволяет распознавать и обрабатывать произвольные пространственные объекты, в том числе и по их фрагментам. Распознавание пространственных объектов на основе обобщенного трехмерного преобразования Хафа ведется с помощью R-таблицы, описывающей геометрию пространственного объекта. Данное преобразование нечувствительно к нумерации отсчетов, описывающих контур (поверхность) данного пространственного объекта. Такой подход приемлем как в отношении сплошных пространственных объектов, так и в отношении групповых точечных объектов. Однако в ситуациях, когда пространственный объект повернут и масштабирован, размерность параметрического пространства, описывающего семейство параметров объекта, для преобразования Хафа значительно возрастает, что сказывается на возможности практической реализации метода.

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

Важнейшие результаты в области обработки изображений и распознавания образов получены отечественными научными школами академика Ю. И. Журавлева, В. А. Сойфера, Н. Г. Федотова, B. C. Титова, B. C. Кири-чука, Ю. Г. Васина, В. А. Утробина, В. В. Кондратьева, К. К. Васильева,

Ю. В. Визильтера, Е. М. Лунева, А. П. Горшкова, а также зарубежными авторами D. H. Ballard, O. J. Woodford, представителями школы Рочестерско-го университета.

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

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

1. Синтез метода обработки изображений пространственных объектов и их фрагментов на основе модификации обобщенного трехмерного преобразования Хафа, инвариантного к нумерации отсчетов, преобразованиям переноса, масштабирования, поворота.

2. Создание алгоритмов распознавания изображений пространственных объектов и их фрагментов на базе модифицированного обобщенного трехмерного преобразования Хафа.

3. Разработка алгоритмов оценки параметров поворота и масштабирования изображений пространственных объектов и их фрагментов на базе модифицированного обобщенного трехмерного преобразования Хафа.

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

5. Создание программного обеспечения для реализации предложенного метода.

Объектом исследования является система обработки пространственных объектов, а предметом исследования – методы обработки пространственных объектов и их фрагментов, заданных неупорядоченными отсчетами.

Соответствие паспорту специальности. Результаты исследования соответствуют пункту 5 «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях, разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений» и пункту 7 «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания» паспорта научной специальности 05.13.17 - Теоретические основы информатики.

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

Достоверность и обоснованность полученных в работе выводов доказываются использованием адекватного математического аппарата, широко применяемого для решения задач обработки изображений; результатами экспериментальной проверки данных теоретических исследований, их внедрением в опытно-конструкторские работы, выполняемые на предприятии ОАО «Марийский машиностроительный завод» в составе ОАО концерн ПВО «Алмаз-Антей»; внедрением в систему интраоперационной навигации; экспертизой программных средств при государственной регистрации программ для ЭВМ [13-15].

Научная новизна заключается в следующем:

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

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

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

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

10. Разработана методика повышения быстродействия при обработке изображений пространственных объектов на основе предложенных подходов путем распараллеливания вычислений.

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

11. Метод обработки изображений пространственных объектов и их фрагментов на базе модифицированного обобщенного трехмерного преобразования Хафа.

12. Алгоритмы распознавания изображений пространственных объектов и их фрагментов на базе модифицированного обобщенного трехмерного преобразования Хафа.

3. Алгоритмы оценки параметров поворота и масштабирования изображений пространственных объектов и их фрагментов на базе модифицированного обобщенного трехмерного преобразования Хафа.

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

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

Реализация и внедрение. Теоретические и практические результаты диссертационной работы использованы в НИР, выполняемых в рамках Аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» по следующим проектам:

фундаментальные исследования проблемы навигации и управления транспортными средствами по 3D изображениям окружающего пространства на базе методов кватернионного анализа. Проект № 2.1.2/2204 (2009-2010 гг.);

фундаментальные исследования проблемы навигации и управления транспортными средствами по 3D изображениям окружающего пространства на базе методов кватернионного анализа № 2.1.2/10218 (2011 г.);

фундаментальные исследования проблемы обработки сплошных 3D изображений на базе методов кватернионного анализа для целей навигации и управления № 8.1013.2011 (2012 г.).

Результаты работы внедрены:

1. в научно-исследовательские и опытно-конструкторские работы, выполняемые на предприятии ОАО «Марийский машиностроительный завод» в составе ОАО концерн ПВО «Алмаз-Антей»;

2. в систему интраоперационной навигации, испытания которой проведены на базе Республиканской клинической больницы (г. Йошкар-Ола) и на базе Йошкар-Олинской городской больницы;

3. в учебный процесс Поволжского государственного технологического университета по направлениям «Радиотехника», «Инженерное дело в медико-биологической практике». Акты внедрения приведены в приложении к диссертационной работе.

Апробация полученных результатов. Основные результаты диссертационной работы обсуждались на X Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2012» (г. Курск, 2012 г.); Всероссийской молодежной конференции «Био-

технические, медицинские и экологические системы и комплексы» (г. Йошкар-Ола, 2012 г); Всероссийской конференции «Техническое зрение в системах управления - 2013» (г. Москва, 2013 г.); Всероссийской конференции «Техническое зрение в системах управления - 2014» (г. Москва, 2014 г.); XI Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2013» (г. Курск, 2013 г.); XI Международной конференции «Распознавание образов и анализ изображений – 2013»; XVI Всероссийской конференции «Математические методы распознавания образов» (г. Казань, 2013 г.).

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

Личный вклад соискателя. Все научные результаты, приведенные в диссертационной работе и сформулированные в положениях, выносимых на защиту, получены автором лично. Работы [1, 3, 4, 6, 7, 11, 12] опубликованы в соавторстве с научным руководителем, которому принадлежат формулировка концепции решаемой задачи и постановка цели исследований. Алгоритмы оценки параметров изображений пространственных объектов [5, 8-10], построение методики повышения быстродействия разработанных алгоритмов [2] предложены автором лично. Основной объем работ по написанию программ [13-15], их отладке, тестированию и интерпретации результатов экспериментов выполнен автором.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка использованной литературы из 111 наименований и приложений. Общий объем диссертации 195 страниц машинописного текста, содержит 156 рисунков.

Модификации преобразования Хафа для обнаружения прямых на плоскости

Основные трудности, возникающие при обработке пространственных изображений, связаны с неопределенностью относительно параметров смещения, вращения и масштабирования обрабатываемого объекта при неизвестной нумерации отсчетов на изображении, а также в случаях, когда в поле зрения находится только фрагмент объекта. Как видно из анализа существующих алгоритмов, методы, описанные в п. 1,8,10 чувствительны к преобразованию вращения; методы, описанные в п. 2,3,5,6,7,9 инвариантны к преобразованию вращения, но требует получения отсчетов на всей поверхности объекта. Методы в п. 11,12 определения параметров вращения инвариантны к нумерации отсчетов, однако не обладают возможностью обработки фрагментов объектов. Подход в п. 13 обладает инвариантностью к преобразованиям переноса, вращения и масштабирования, однако не способен обрабатывать фрагменты объектов.

В области обработки изображений одним из широко применяемых преобразований, позволяющих сформировать достаточную статистику для распознавания объекта, является преобразование Хафа. Это преобразование применяется во многих областях [53-58]. Важнейшим достоинством преобразования Хафа является возможность выделения объектов произвольной формы на фоне шумов даже по отдельным фрагментам. Кроме этого структура преобразования Хафа обеспечивает возможность применения параллельных вычислений при его реализации. В связи с этим представляет интерес возможность применения преобразования Хафа для обработки изображений пространственных объектов. 1.2 Реализация стандартного преобразования Хафа

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

Преобразование Хафа было введено P.V.C. Hough в патенте США №3069654 от 18 декабря 1962 года [60]. В нем автор исследовал прохождение частиц в пузырьковой камере. В ней заряженные частицы создают следы на своем пути следования, этот след состоит из мелких пузырьков. Он предложил каждый путь частицы аппроксимировать отрезками некоторых прямых, причем каждый такой отрезок представляется своим угловым коэффициентом. Сохраняя полученные угловые коэффициенты по порядку можно представить сложный путь движения частиц.

Таким образом, именно P.V.C. Hough был представлен подход, в преобразовании сложного объекта - следа движения заряженной частицы - в некотором ранжированном наборе параметров. Основной смысл преобразования Хафа заключается в сопоставлении параметров уравнения кривой с точками на изображении. Каждая кривая, заданная параметрически, имеет некоторое количество параметров (прямая на плоскости - два параметра, окружность - три параметра, эллипс - четыре параметра). Тогда параметрически заданные кривые отличаются друг от друга только значением параметров. Распознавание в этом случае заключается в определение значения параметров заданных кривых.

Каждый параметр кривой имеет область определения. Так, например, угол наклона w прямой лежит в диапазоне от 0 до 360 градусов (1.1), а длина перпендикуляра R (1.1), опущенная на прямую от начала координат измеряется от нуля до фактических размеров изображения (1.1). xcos(w) + ysin(w) = R, (1.1) где w - угол между положительным направлением оси Ох и направлением перпендикуляра, опущенного на прямую из начала координат, R - длина этого перпендикуляра. В общем случае, двухмерная кривая описывается как: F(ava2,a3 ай,х,у) = 0, (1.2) где ах,а2,аъ ап - параметры этой кривой, х, у -координатные переменные. Можно говорить о том, что параметры кривойах,а2,аъ ап (1.2) определяют семейство состояний объекта. Учитывая ошибки и недостаток памяти при реализации непрерывных состояний объекта, принимают дискретную структуру, описывающую эти состояния.

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

Преобразование Радона, показывает, как описать функцию с точки зрения ее проекций. Отображение функции на проекцию является преобразованием Радона. Обратное преобразование Радона соответствует восстановлению функции из проекций. Прямое преобразования Радона имеет вид: R{I}{R,(p) = j I(Rco$(p- s$in(p,R$m(p+ sco$(p)dxdy (1.3) R с проекцией вдоль линии c{R, р), где / - плоское изображение, х,у - координаты на изображении, R, ср - параметры прямых, относительно которых определяются проекции,R{i} - прямое преобразование Радона. Преобразование Радона получило широкое распространение благодаря его использованию в компьютерной томографии, а также для моделирования процессов получения проекций исходного объекта. Преобразование Радона также может быть использовано для обнаружения форм. Переопределим преобразование Радона как: R{I}(R, p)= J I(x,y)dxdy=jl(x,y)S(xcosip+ysmip-R)dxdy (1.4) (x,y)inCl(R,(p) RR

Теперь можно интерпретировать преобразование Радона следующим образом: оно обеспечивает отображение пространства изображений, в параметрическое пространство, охватываемое параметрами p = (R, p). Функция, заданная в этом параметрическом пространстве, содержит пики для тех р, для которых соответствующие формы с(р) присутствуют в изображении. Обнаружение изображения заданной формы сводиться к решению задачи обнаружения пиков.

Авторы в [61] выделяли два метода обнаружения кривой: первый соответствует преобразованию Радона, второй представляет собой преобразование Хафа, которое за счет ранних работ стало очень популярным. Многие авторы отмечали, что преобразование Хафа и Радона тесно связаны между собой.

Алгоритм распознавания изображений пространственных объектов на базе модифицированного обобщенного трехмерного преобразования Хафа

При обработке реальных изображений параметры р и у/, характеризующие направление нормали к поверхности объекта в данной точке, могут меняться в широких пределах из-за изменения параметров вращений наблюдаемого изображения. В результате значения углов а{с) , /?(с) и расстояния r(с) для наблюдаемого (сигнального) изображения при данных р и у/ будут отличаться от аналогичных параметров исходного изображения (рисунок 2.1, a).

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

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

Для индексации -таблицы воспользуемся подходом, основанным на использовании в качестве аргументов номеров отсчетов эталонного изображения. В качестве заносимых в R-таблицу данных предлагается использовать значение расстояние от данной точки до центра формы г и значение угла w между нормалью и направлением на центр формы, который не зависит от параметров вращений (рисунок 2.2). Поскольку при сканировании трехмерных объектов количество и порядок следования отсчетов могут изменяться, то при распознавании необходимо выполнять полный перебор взаимных комбинаций отсчетов эталонного и наблюдаемого изображений. При размерности эталона N3 и размерности сигнального изображения Nc общее количество комбинаций составит

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

Для аналитического описания процесса заполнения аккумуляторного массива воспользуемся алгеброй кватернионов при описании вращений [94]. Положение вектора Опт в трехмерном пространстве при заданной нормали г/т и угле wn можно описать в виде ощт = rnbz { рт )ьу {т ) bz {wn )ІЬ: {wn )ь; {m X { pm ), (2.1) где bz{ pm) = cos pm+ksin pm , by(l//m) = COSl//m + jsini//m , (wB) = coswB+JtsinwB ,i, j , к - мнимые единицы. Для представления окружности, описываемой концом вектора Опт, также воспользуемся описанием вращения вокруг нормали г]т на угол (р, ре [0,2л-): 0П,М=ЬМ0ПХ( Р) , (2.2) где bm{ p) = cos p+7]msm p. Значение индекса Стп{ р) аккумуляторного массива в котором производится накопление, определяется суммированием вектора Опт{ р) со значением координаты т -й точки поверхности: Стп ( р) = ixm + jym + kzm + Опт{ р), п = 0,1,...,N3 -1, т = ОД,..., Ne-1, ре [0,2л"). (2.3) В простейшем случае в точках с координатами Стп{ р) выполняется инкремент значений аккумуляторного массива: 4cmM) = A(cJ pj)+l. (2.4) При необходимости накопление в аккумуляторном массиве может производиться с учетом интенсивностей перепадов яркости в каждой точке поверхности, т.е. 4cJ p)) = A{cJ p))+j(ixm + jym + kzm). (2.5) При вращении обрабатываемого изображения происходит аналогичное вращение аккумуляторного массива, однако величина максимального отсчета при этом не меняется, что позволяет выполнять распознавание трехмерного изображения независимо от его ориентации. Поскольку при обработке происходит сопоставление каждой точки эталонного изображения с каждой точкой наблюдаемого объекта, результат обработки не будет зависеть от нумерации отсчетов, а также возможна обработка и принятие решений по отдельным фрагментам наблюдаемого изображения. Если неизвестен масштаб изображения, то при заполнении аккумуляторного массива необходимо выполнять инкремент элементов массива вдоль образующей конуса, описываемой вектором, проходящим под углом w относительно нормали (рисунок 2.4). Длина образующей определяется возможным диапазоном изменения масштаба обрабатываемого изображения. Координаты точек, в которых инкрементируется содержимое аккумуляторного массива, определяется соотношением: Cmn{ p) = iXm + jym+kzm+ цОп,т{ Р), и = 0,1,...,ЛГэ-1, m = 0,l,...,iVc-l, jue\jumili,jumj, рє[0,2ж). (2.6) где ju m и jumaK- минимальное и максимальное значения масштаба изображения. Рисунок 2.4 - Принцип голосования в аккумуляторном массиве при неизвестных параметрах вращения и масштабирования изображения

При наличии шума на изображении параметры центра формы определяются с некоторыми погрешностями, что вызывает «размывание» пика в аккумуляторном массиве. Дополнительные погрешности возникают из-за дискретности аккумуляторного массива. Одним из подходов к устранению влияния этих факторов является сглаживание аккумуляторного массива за счет применения низкочастотной фильтрации. В простейшем случае может использоваться фильтр скользящего квазисреднего [95,96], работа которого описывается соотношением

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

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

Для оценки параметров вращения воспользуемся подходами, заложенными в классическом преобразовании Хафа. При определении параметров вращения [8,42-44,50-52,104,105] исходными данными являются координаты точек эталонного и обрабатываемого изображений. На их базе могут быть рассчитаны векторы нормалей к поверхности объекта, которые вращаются аналогично объекту и нечувствительны к преобразованиям переноса и масштабирования. Методика расчета полей нормали объекта представлена в п. 2.3. При определении параметров вращения необходимо оценить четыре неизвестных параметра: три параметра - координаты оси вращения и четвертый - угол поворота. Согласно выражениям (3.5-3.6) свободным параметром преобразования Хафа будет угол вращения. Исходными данными для определения параметров вращения будут координаты векторов нормалей к поверхности эталонного и повернутого объектов.

Для свободного параметра необходимо задать пределы его изменения. На рисунке 3.1 показаны возможные направления векторов оси вращения т7 и т2, рассчитываемые на основе данных о направлениях нормалей исходного объекта v , отсчетов нормалей повернутого объекта V и угла поворота а. Для однозначного выбора направления оси вращения диапазон изменения угла а задается в пределах от 0 до 180. Расположение оси вращения Поскольку каждый вектор нормали отсчета исходного объекта сравнивается с каждым вектором нормали вращаемого объекта, рассматриваемый вариант преобразования Хафа не чувствителен к нумерации отсчетов.

При расчете координат осей вращения для очередного вектора нормали исходного объекта и вектора нормали вращаемого объекта находят координаты оси вращения при некотором угле а.

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

Поскольку неизвестными являются четыре параметра вращения, то и аккумуляторный массив должен быть четырехмерным, что затрудняет реализацию данного метода. Однако, поскольку вектор оси вращения является нормированным, то для его представления достаточно знания двух его компонентов, а третий может быть вычислен с точностью до знака. В связи с этим предложено использовать трехмерный аккумуляторный массив A[my,mz,a] , содержащий координаты оси вращения по осям у, z и значение угла поворота. После выделения пика в аккумуляторном массиве A[my,mz,(X] находятся его индексы. Поскольку знание координат пика в аккумуляторном массиве не позволяет непосредственно определить знак третьего компонента вектора оси вращения, необходимо повторно провести расчеты координат осей вращения. Если получаемые при этом индексы совпадают с найденными ранее, то рассчитанные значения координат оси вращения и угла поворота принимают в качестве результатов оценки параметров вращения.

Алгоритм нахождения параметров вращения на базе преобразования Хафа С учетом изложенного Алгоритм 1 нахождения параметров вращения на базе преобразования Хафа будет включать следующие этапы: 1. Расчет векторов нормали исходного и вращаемого объекта. 2. Для данного вектора нормали отсчета исходного объекта - v . 3. Для данного вектора нормали отсчета вращаемого объекта - V. 4. Для некоторого угла вращения а векторов нормали отсчета исходного объекта и вращаемого объекта. 5. Расчет в соответствии с (3.5,3.6) координат оси вращения. 6. Если ось вращения существует и ее длина равна единице, то инкрементируется элемент аккумуляторного массива А[ту,mz,]. 7. Нахождение индексов пика в аккумуляторном массиве A[my,mz,]. 8. Повтор пунктов 1 - 6 и поиск соответствия индексов оси вращения индексам пика в аккумуляторном массиве. 9. Конец На рисунке 3.2 представлен алгоритм оценки параметров вращения на базе преобразования Хафа. Одним из достоинств преобразования Хафа является возможность оценивать свойства структуры по его фрагменту. Алгоритм обработки изображения в этом случае аналогичен представленному на рисунке 3.2, но вращаемый объект может задаваться отдельным фрагментом.

Повышение помехоустойчивости алгоритма и уменьшение погрешности оценки параметров вращений возможно за счет проверки качества совмещения исходного изображения с обрабатываемым изображением, подвергнутым обратному преобразованию вращения. Мерой качества выступает величина суммарной погрешности совмещения нормалей эталонного и обрабатываемого изображений, вычисляемая по формуле: S = "і min(Vlo6noB - v. )2, j = 0,1,..., N -1 (3.7) !=0 J J где /V - количество отсчетов вектор нормалей повернутого объекта, v пов от.пов г Г Г J 1 вектор нормали вращаемого объекта, повернутого относительно найденных координат оси вращения т на угол (-a), vj - вектор нормали исходного объекта. Таким образом, найденные оценки параметров вращения проверяются сопоставлением полей нормалей вращаемого и исходного объектов. Так как значения параметров вращения находят с некоторыми погрешностями, обусловленными действием шума и дискретностью аккумуляторного массива, величина S будет всегда больше нуля. В связи с этим необходимо ввести порог, при превышении которого будет приниматься решение о неудовлетворительном качестве совмещения и, соответственно, о неверной оценке параметров вращений. Если в аккумуляторном массиве выделяется несколько пиков, то для оценки параметров выбирается пик, обеспечивающий минимальное значение S.

Экспериментальное исследование помехоустойчивости комбинированного преобразования Хафа

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

Автоматическая сегментация органов тела человека по томографическим изображениям на базе модифицированного обобщенного трехмерного преобразования Хафа

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

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

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

Первым этапом, необходимым для формирования модели является выделение в срезах томограммы контурных точек. Для этого строится гистограмма распределения яркостей (рисунок 4.54) и формируются локально-однородные по яркости области (рисунок 4.55). После сегментации по яркости производиться выделение контуров оператором Превитта для двух различных порогов ti и t2 (рисунок 4.56 а и б). После выделения контуров производится их сегментация путем анализа связности отсчетов. Предполагается, что принадлежащие контуру точки находятся на расстоянии, не превышающем некоторую величину, и прослеживаются от точки к точке в пределах некоторого окна. На первом этапе случайным образом выбирается точка, принадлежащая некоторому контуру. Для данной точки находятся N ее ближайших соседей в пределах некоторого строба. Для каждой из найденных точек контура аналогичным образом определяются следующие N ближайших точек, также в пределах некоторого строба. Этот процесс повторяется, пока на некотором участке плоскости не будут локализованы все точки контура. Для одного снимка последовательно выделяются несколько контуров.

Для удаления несущественных контуров сегментация контуров производится с двумя окнами: первое окно [7,7] второе окно [5,5] (рисунок 4.58). Размер окна определяет область относительно рассматриваемой точки, в которой ищутся ее соседи при прослеживании контура изображения.

Среди оставшихся контуров производится селекция по критерию замкнутости и по количеству точек. Результирующее изображение (рисунок 4.59) формируется по критерию присутствия контурных точек в обоих изображениях на рисунке 4.58. Это позволяет выявить разрывы в контурах и удалить незамкнутые контуры из результирующей сцены.

Для выделения точек, принадлежащих отдельным органом, воспользуемся комбинированным преобразованием Хафа. Для его реализации необходимо построить R-таблицу искомого органа. Для этого обработаем серию плоских изображений томограмм с заранее выделенным контуром искомого органа (левой почки). На рисунке 4.61 представлено эталонное точечное поле левой почки. Задача сегментации состоит в автоматическом выделении данного точечного поля в точечном поле, представленном на рисунке 4.60.

Поэтому для вычисления нормалей строится октодерево - древовидная структура трехмерного пространства в котором у каждого внутреннего узла восемь «потомков» [110] (рисунок 4.62). Каждый узел в октодереве делит пространство на восемь новых подузлов (потомков). Центральная точка узла октодерева является «центром» разделения пространства для этого узла. В свою очередь каждый новый подузел можно разделить еще на восемь подузлов. Такое итерационное разделение сцены позволяет сгруппировать отсчеты. Далее, задавая шаг изменения координат по трем осям, вычисляют координаты узлов в октодереве. Первоначально октодерево представляет собой трехмерный массив, каждый элемент которого содержит координаты границы данного узла, массив отсчетов сцены, попавших в данный узел и ссылки на восемь потомков узла. При дальнейшем делении узла на потомки, отсчеты узла заносятся в массивы потомков данного узла. Такое разделение точек сцены позволяет быстро находить точки ближайшие к рассматриваемому отсчету при вычислении вектора нормали.