«Гаганов Виктор Александрович Исследование и разработка программных средств распознавания образов для решения задачи трехмерного моделирования в микроскопии Специальность 05.13.11 – математическое и программное ...»

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

Гаганов Виктор Александрович

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

средств распознавания образов для решения

задачи трехмерного моделирования

в микроскопии

Специальность 05.13.11 – математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель к. ф.-м. н.

Баяковский Ю.М.

Москва – 2011 2 Содержание

Введение Глава 1. Задача построения трехмерной модели по изображе­

ниям с микроскопа 1.1. Моделирование микрообъектов................ 1.1.1. Особенности изображений с микроскопа....... 1.1.2. Методы на основе изображений............ 1.2. Обзор существующих методов................. 1.2.1. Постановка задачи................... 1.2.2. Методы семейства SFD................. 1.2.3. Методы семейства SFF................. 1.2.4. Мера резкости...................... 1.2.5. Базовая схема методов SFF.............. 1.2.6. Уточнение модели.................... 1.2.7. Сравнение подходов SFF и SFD............ 1.3. Недостатки существующих методов семейства SFF..... 1.4. Мультифокус изображения................... 1.5. Заключение............................ Глава 2. Устойчивый метод построения поверхности произ­

вольной формы 2.1. Марковские случайные поля.................. 2.1.1. Оценка параметров поля................ 2.1.2. Теорема Хаммерсли-Клифорда............ 2.2. Предлагаемый метод...................... 2.2.1. Статистическая формулировка задачи........ 2.2.2. Функция правдоподобия................ 2.2.3. Структура поля..................... 2.2.4. Итоговая функция энергии.............. 2.2.5. Унарный потенциал................... 2.2.6. Парный потенциал................... 2.2.7. Оптимизация функционала.............. 2.2.8. Усреднение меры резкости............... 2.2.9. Итоговый алгоритм................... 2.3. Эксперименты.......................... 2.3.1. Тестовая базы для сравнения............. 2.3.2. Метрика для сравнения методов........... 2.3.3. Результаты сравнения................. 2.3.4. Визуальное сравнение результатов.......... 2.4. Заключение............................ Глава 3. Оценка положения и ориентации плоского участка

поверхности 3.0.1. Постановка задачи................... 3.1. Существующие методы оценки плоскости........... 3.1.1. Метод наименьших квадратов............. 3.1.2. Устойчивые методы оценки плоскости........ 3.1.3. M-estimators и медиана квадратов разностей.... 3.1.4. Методы на основе случайных выборок........ 3.1.5. Преобразование Хафа................. 3.1.6. Выводы

3.2. Метод оценки положения и ориентации плоскости...... 3.2.1. Схема предлагаемого метода............. 3.4.1. Оценка качества алгоритма фильтрации ложных за­ 3.4.3. Качество процедуры проверки надежности плоскости Глава 4. Программная реализация предложенных методов 4.1. Алмазообрабатывающая промышленность.......... 4.1.2. Построение трехмерной модели камня........ 4.1.3. Моделирование дефектов внутри камня и уточнение 4.2. Интерфейс и функциональность системы Oxygen Microscope 4.3. Детали реализации подсистемы InclEngine.......... 4.3.1. Взаимодействие реализованной подсистемы с Oxygen 4.3.2. Архитектура подсистемы: уточнение модели поверх­ 4.3.3. Архитектура подсистемы: моделирование включений 4.3.4. Замеры производительности разработанных алгорит­ Заключение Благодарности Литература Объект исследования и актуальность работы С момента появления первого оптического микроскопа в конце XVI – начале XVII века это устройство плотно вошло в жизнь человека. Сейчас практически невозможно представить себе современное общество без этого изобретения. В данный момент оптические микроскопы находят примене­ ние в широком спектре приложений, начиная от рутинных медицинских и биологических исследований, заканчивая контролем качества на высоко­ технологичных производствах.

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

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

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

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

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

Основные задачи

работы:

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

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

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

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

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

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

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

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

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

На основе предложенных методов была создана программная система для моделирования поверхности алмазов и дефектов внутри алмазного сы­ рья. Данная система была интегрирована в программный продукт Oxygen Microscope Server компании-заказчика Octonus Software Ltd. Данный про­ граммный продукт активно используется:

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

Антверпен (Бельгия);

в процессе подготовки и обучения специалистов по огранке алмазов в Геммологическом центре Московского государственного универси­ тета им. М.В. Ломоносова.

Апробация работы Основные результаты диссертации докладывались и обсуждались на:

18-ой международной конференции по компьютерной графике и ма­ шинному зрению «Graphicon’2008», Россия, Москва, 2008;

15-ой международной конференции студентов аспирантов и молодых ученых «Ломоносов-2008», Россия, Москва, 2008;

семинаре по компьютерной графике и мультимедиа под руководством Ю.М. Баяковского (ф-т ВМиК МГУ), Россия, Москва, 2009;

секции вычислительной математики и кибернетики научной конфе­ ренции «Ломоносовские чтения-2009», Россия, Москва, 2009;

19-ой международной конференции по компьютерной графике и ма­ шинному зрению «Graphicon’2009», Россия, Москва, 2009;

семинаре по компьютерной графике под руководством А.В.Игнатенко (ф-т ВМиК МГУ), Россия, Москва, 2010;

объединенном семинаре по робототехническим системам ИПМ им.

М.В. Келдыша РАН, МГУ им. М.В. Ломоносова, МГТУ им. Н.Э.

Баумана, ИНОТиИ РГГУ и отделения "Программирование"ИПМ им.

М.В.Келдыша РАН, Россия, Москва 2010.

Публикации Материалы диссертации опубликованы в 5 печатных работах: 2 ста­ тьи в рецензируемых журналах, рекомендованных ВАК [2, 3], две статьи в сборниках трудов конференций [4, 5], а также тезисы доклада [6].

Структура и объем диссертации Диссертация состоит из введения, 4 глав, заключения и библиографии.

Общий объем диссертации составляет 133 страницы, включая 33 рисунка.

Библиография включает 73 наименования.

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

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

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

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

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

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

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

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

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

Рис. 1.1. На рисунке (a) изображена оптическая система, и точка P изображение кото­ рой попадает на сенсор с идеальным фокусом. На рисунке (б) изображение точки P’ на сенсоре будет расфокусированным Размер участка поверхности сенсора, по которому рассеиваются лу­ чи, исходящие из точки, пропорционален расстоянию от точки до поверхности сенсора. Поэтому при получении фотографии сцены, только некоторая часть сцены, оказывается на фотографии в резкости. Эта часть сцены называется областью резкости, и чем дальше точка сцены находит­ ся от области резкости, тем более размытой будет выглядеть изображение этой точки на фотографии [9]. Расстояние между самой близкой и самой дальней границами пространства, которые видны на изображении в резко­ сти, называется глубиной резкости.

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

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

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

1.1.2. Методы на основе изображений Описанный эффект глубины резкости является серьезной преградой для использования традиционных методов построения трехмерных моде­ лей по изображениям при моделировании микрообъектов. Методы стереоре­ конструкции [7, 8] требует два и более изображения сцены, полученных с разных точек зрения. Эти методы находят соответствия между точками на изображениях и с помощью процедуры триангуляции получают трех­ мерную модель сцены. Методы стереореконструкции способны получить точную модель сцены при условии, что на поверхности объектов сцены присутствует большое количество видимой текстуры. Именно поэтому при­ менение стереореконструкции при моделировании микрообъектов затруд­ нительно, из-за того, что большая часть сцены трехмерного объекта на изображениях видна не в резкости, и видимая текстура на изображениях размыта.

Методы на основе согласования цветов [10–12], которые строят модель исходя из предположения, что цвета проекций каждой точки поверхности объекта должны отличаться для разных изображений незначительным об­ разом, тоже не применимы из-за эффекта глубины резкости. Методы фо­ тометрического стерео [13, 14] также не позволяют обеспечить достаточ­ ную точность реконструкции нормалей поверхности объекта для размытых участков входного изображения.

Наиболее подходящими методами для построения трехмерных моде­ лей микрообъектов являются методы трехмерной реконструкции по фоку­ сировке [9, 15–21]. Точка трехмерной сцены выглядит на изображении тем более размыто, чем больше расстояние от этой точки до области резко­ сти (см. ст. 14). Поэтому понятно, что по степени размытости точки на фото-изображении, можно судить о том, насколько велико расстояние от области резкости до данной точки в трехмерном пространстве. А значит и осуществить построение трехмерной модели поверхности объекта.

1.2. Обзор существующих методов Методы реконструкции трехмерных моделей объектов по фокусировке делятся на два семейства: это методы семейства shape from focus (SFF) и методы семейства shape from defocus (SFD). Методы SFF [9, 15–17] для оцен­ ки положения в трехмерном пространстве некоторого участка сцены полу­ чают множество по-разному сфокусированных изображений сцены. После этого ищется изображение, на котором данный участок сцены виден в рез­ кости и положение области резкости оптической системы для найденного изображения сцены принимается за оценку расстояния до данного участка сцены. Далее оценки расстояния для различных участков сцены комбини­ руются для получения трехмерной модели всей сцены.

Методы семейства SFD [18–21] моделируют степень резкости участка изображения как функцию расстояния до поверхности объекта. Затем, по двум или более по-разному сфокусированным изображениям сцены, фор­ мулируется обратная задача, решением которой является карта расстояний до поверхности сцены, которая полностью определяет трехмерную модель сцены.

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

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

Не ограничивая общности будем считать, что управление фокусиров­ кой достигается за счет перемещения оптической системы относительно наблюдаемого объекта в направлении, параллельном оптической оси мик­ роскопа. В случае если управление фокусировкой достигается за счет вза­ имного перемещения линз в оптической системе микроскопа, фотографи­ ями с разными настройками фокуса будут иметь разное увеличение, что может быть скомпенсированно, как показано в [22].

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

ниченна двумя плоскостями в пространстве является оправданным упро­ щением. Для реальных объективов состоящих из нескольких линз, область резкости может быть не плоской. Однако как показано в работе [22] кривиз­ на области резкости может быть скомпенсирована за счет предварительной калибровки с помощью плоского калибровочного шаблона, расположенно­ го перпендикулярно оптической оси микроскопа.

Тогда по такому набору изображений требуется построить трехмер­ ную модель наблюдаемого участка объекта. В связи с тем, что съемка всех изображений ведется с одного направления, для представления трех­ мерной модели объекта удобно использовать карту глубины. То есть для представления трехмерной модели объекта можно использовать матрицу = {, }, размеры которой равны размеру изображений набора.

1.2.2. Методы семейства SFD Методы семейства shape from defocus [18–21, 23] моделируют степень резкости участка изображения как функцию расстояния до поверхности объекта. По двум или более по-разному сфокусированным изображениям сцены, формулируется обратная задача, решением которой является карта глубины, которая полностью определяет трехмерную модель сцены.

Для иллюстрации данной идеи рассмотрим один из первых методов shape from defocus, который был описан Пентландом в работе [23]. В сво­ ей работе Пентланд предложил использовать для построения трехмерной модели сцены пару изображений, то есть = {1, 2 }. В методе предло­ женном Пентландом оба изображения сцены сфокусированы одинаково.

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

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

1 Стоит заметить, что в связи с тем, что для микрообъектов получение изображения, на кото­ ром вся сцена видна в резкости, невозможно из-за физических ограничений, данный метод применим только для макрообъектов где (, ) представляет собой двумерный Гауссиан, параметр пред­ ставляет собой степень размытия участка сцены, а * обозначает операцию свертки. В данной формуле - идеально сфокусированная текстура поверхности участка сцены. В связи с тем, что в методе, предложенном Пентландом, первое изображение получается с полностью закрытой диа­ фрагмой можно можно считать, что = 1.

Обозначим небольшой участок изображений 1 и 2 с центром в точек (0, 0 ) как 1 и 2. Тогда понятно, что 2 (, ) = 1 (, ) * (,, ).

Если рассмотреть Фурье-образы участков 2 и 1 имеем, что:

Благодаря тому, что свертка в пространственной области соответству­ ет умножению в частотно-временной области можно перенести 1 в левую часть равенства (1.3) и тем самым получить уравнение для поиска.

Тогда алгоритм построения карты глубины можно записать следую­ щим образом:

1. Каждое из входных изображений 1, 2 разбивается равномерно на небольшие блоки (размером, например, 10x10 пикселей) 2. Для каждой пары соответствующих блоков рассчитывается преобра­ зование Фурье 3. Далее для каждого блока с помощью уравнения (1.3) вычисляется степень размытия 4. Далее для каждого блока степени размытия ставится в соответствие расстояние от центра области резкости изображения 1. Это может быть сделано исходя из известных параметров модели линзы, как предлагается в работе [23] Существует большое количество различных алгоритмов SFD. Боль­ шинство из них могут быть разбиты на две группы - локальные и глобаль­ ные. Примером локального алгоритма является описанный выше алгоритм Пентланда. Локальные алгоритмы [19, 21, 23, 24] разбивают входные изоб­ ражения на набор небольших блоков и далее путем сравнения степени раз­ мытия пары соответствующих блоков строят оценку карты глубины для наблюдаемой сцены.

В отличии от локальных алгоритмов глобальные алгоритмы [18, 20] не осуществляют разбиение сцены на блоки. Глобальные алгоритмы SFD фор­ мулируют обратную задачу, записывая зависимость между полученными изображениями 1, 2 и неизвестной картой глубины где - представляет собой функцию, которая моделирует процесс фор­ мирования изображения, а 1 и 2 представляют собой настройки фокуси­ ровки и диафрагмы для пары входных изображений. Исходя из формулы (1.4) глобальные методы SFD решают обратную задачу и тем самым полу­ чают целевую карту глубины.

1.2.3. Методы семейства SFF В отличии от методов семейства SFD, методы SFF [9, 15, 21, 22, 24] для оценки положения в трехмерном пространстве некоторого участка сце­ ны получают множество по-разному сфокусированных изображений сце­ ны. После этого ищется изображение, на котором данный участок сцены виден в резкости и положение плоскости резкости оптической системы для найденного изображения сцены принимается за оценку положения данного участка сцены в трехмерном пространстве. Для определения того, на каком Рис. 1.3. Схематичная иллюстрация принципа работы алгоритмов семейства shape from focus. На графике справа горизонтальная ось соответствует номеру картинки, а верти­ кальная - значению меры резкости изображении некоторый участок сцены виден наиболее четко используется т.н. мера резкости (см. рис 1.3). Далее оценки для различных участков сцены комбинируются для получения трехмерной модели всей сцены.

Таким образом в случае методов семейства SFF набор входных изоб­ ражений = {1,..., } состоит из большого количества входных изоб­ ражений, потому как для получения корректной оценки геометрии сцены требуется, чтобы каждый участок наблюдаемой сцены был виден в резко­ сти хотя бы на одном из входных изображений. Обычно набор изображе­ ний получается путем сканирования сцены с равномерным шагом (см.

рис 1.3). То есть каждое изображение +1 отличается от изображения положением плоскости резкости на некоторый шаг, одинаковый для всех изображений.

1.2.4. Мера резкости Методы семейства SFF опираются на поиск наиболее резкого изобра­ жений некоторого участка сцены среди набора фотографий = {1,..., }.

Для того чтобы осуществить такой поиск алгоритмам SFF требуется чис­ ленная мера, для измерения того, насколько резким выглядит участок изоб­ ражения в окрестности пикселя (0, 0 ). Такая численная мера называется мерой резкости. В работах по методам SFF предлагается ряд различных мер резкости [25, 26].

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

В работе Наяра [25] предлагается в качестве меры резкости использо­ вать дискретный аналог т.н. модифицированного оператора Лапласа:

Для расчета вторых производных по дискретной картинке использует­ периментальным путем было показано, что добавление модулей в формулу (1.5) улучшает качество работы меры резкости по сравнению с обычным оператором Лапласа.

В работе Кроткова [26] предлагается в качестве меры резкости исполь­ зовать следующий оператор:

Данный оператор представляет собой модуль градиента в точек изоб­ ражения и называется оператор Тененград. Для вычисления производных первого порядка в формуле (1.6) в работе [26] используется свертка с ядра­ ми и, задаваемыми следующей формулой:

На рис. 1.4 можно видеть пример результата расчет меры резкости Тененград для изображения природного минерала.

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

1.2.5. Базовая схема методов SFF После того как введено понятие меры резкости можно описать базо­ вую схему работы методов семейства SFF. Разработка методов трехмерной реконструкции семейства SFF началась еще в 80х годах прошлого века. С тех пор было разработано большое количество алгоритмов SFF, но боль­ шинство из них используют следующую схему, предложенную в одной из первых работы по методам семейства SFF [25] Рис. 1.4. Изображение природного минерала, полученное с помощью оптического мик­ роскопа, и мера резкости Тененград, рассчитанная по этому изображению. Можно за­ метить, что значения меры резкости больше в областях изображения, на которых при­ сутствуют четкие детали.

1. Для каждого изображения из набора вычисляем меру резкости, тем самым получая карты значения меры резкости = {1,..., }.

2. Для каждого проводим усреднение значений меры резкости с целью подавления шумов 3. Для каждого пикселя (, ) находим, на котором достигается мак­ симум величины меры резкости 4. Положение плоскости резкости оптической системы для изображения принимаем за оценку положения поверхности объекта в пикселе Второй шаг алгоритма является необходимым, для того, чтобы пода­ вить колебания в значениях меры резкости, возникающие из-за шума каме­ ры. Шумы во входных изображениях неизбежно оказывают сильное вли­ яние на значения меры резкости, потому как большинство мер резкости основаны на высокочастотных фильтрах, которые чувствительны к шуму.

В работе Наяра [25] перед выполнением шага 3), который заключается в поиске максимального значения меры резкости в пикселе (0, 0 ),пред­ лагается осуществить усреднение значений меры резкости по квадратному окну размера с центром в пикселе (0, 0 ). Это эквивалентно обработке карт меры резкости низкочастотным box-фильтром с ядром размера.

Рис. 1.5. Пример усреднения меры резкости с помощью Гауссовского фильтра. На ри­ сунке a) можно видеть изображение меры резкости, а на рисунке б) можно видеть результат обработки меры резкости фильтром Другим популярным методом усреднения меры резкости является усред­ нение значений меры резкости с помощью фильтра Гаусса [16] (см. рис 1.5).

Фильтр Гаусса превосходит box-фильтр потому что его отклик является поворотно-инвариантным. Также при использовании фильтра Гаусса веса значений меры резкости убывают по мере удаления от (0, 0 ) что позволя­ ет обеспечить более высокую точность по сравнению с box-фильтром.

В работе [22] предлагается использовать для усреднения меры резко­ сти расчет среднеквадратичного отклонения меры резкости по окну с цен­ тром в пикселе (0, 0 ) где - среднее по окрестности, в которой ведется расчет. Плюсом та­ кой схемы является заниженный отклик меры резкости в областях с плав­ ными перепадами яркости изображения, которые обычно соответствуют сильно размытой текстуре.

1.2.6. Уточнение модели Большое количество работ по SFF посвящено уточнению модели, полу­ чаемой с помощью описанной базовой схемы. Главным недостатком описан­ ной базовой схемы является необходимость производить усреднение меры резкости по окну в окрестности пикселя (0, 0 ).

В работе [15] авторы показали, что усреднение меры резкости по окну размером x с помощью методов, описанных ранее, соответствует пред­ положению о том, что наблюдаемая сцена в окрестности (0, 0 ) является плоской и данная плоскость перпендикулярна оптической оси. В случае ес­ ли участок поверхности имеет более сложную форму, или даже является плоскостью, которая не перпендикулярна оптической оси, усреднение меру резкости в окрестности пикселя (0, 0 ) приводит к ухудшению точности оценки формы поверхности объекта.

Для решения данной проблемы авторы [15] предложили следующий алгоритм. На первом шаге происходит построение модели объекта с помо­ щью базовой схемы SFF. Обозначим как трехмерную матрицу, значения которой определяются по формуле (,, ) = (, ). То есть в ячейке (,, ) находится значение меры резкости изображения в пикселе (, ) без усреднения. Пусть оценка глубины, полученная с помощью базовой схемы в пикселе (0, 0 ) равна 0. В этом случае авторы работы [15] пред­ лагают осуществлять уточнение следующим образом.

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

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

Данная идея развивается в работах [17, 27, 28]. В работе [28] пред­ лагается для моделирования участка поверхности в окрестности пикселя (0, 0 ) использовать более сложную модель чем плоскость, а именно функ­ цию, представляющую собой выход трехслойной нейронной сети. В работе [27] предлагается для каждого пикселя карты глубины искать оптималь­ ную поверхность общего вида в окрестности (0, 0, 0 ) с помощью метода динамического программирования. Эти подходы позволяют еще больше по­ высить локальную точность получаемой модели по сравнению с [15].

В работе [29] рассматривается еще одна из проблем, которая связана с использованием усреднения по небольшому окну с центром в (0, 0 ) - это краевые эффекты. В случае если у наблюдаемой сцены в окрестности точки (0, 0 ) проходит граница объекта, либо имеется сильный перепад глубины на поверхности объекта, то усреднение по окну также приводит к серьезной потери точности. Причем ни одна из обобщенных моделей поверхности [17, 27, 28] не в состоянии корректно обработать данную ситуацию.

Авторы [29] для решения этой проблемы предлагают использовать сле­ дующий метод. Пусть помимо изначального набора изображений с разной фокусировкой = {1,..., } у нас имеется еще и изображение на ко­ тором вся сцена видна в резкости (изображение с максимально закрытой диафрагмой). Тогда для усреднения значений меры резкости предлагается использовать следующий адаптивный метод где (, ) - одномерный Гауссиан с центром в нуле. Благодаря взве­ шиванию значений меры резкости с помощью формулы (1.11) достигается эффект адаптивного усреднения. Точки изображения, цвет которых суще­ ственно отличается от цвета пикселя (0, 0 ) имеют низкий вес при усред­ нении. В связи с тем, что обычно в областях резкого перепада глубины и на границах объекта происходит резкая смена цвета данный метод поз­ воляет добиться существенного улучшения точности работы метода SFF в областях резких перепадов глубины, даже при использовании довольно большого значения размера окна R. Данную идею можно также сочетать с использованием взвешивания функцией Гаусса в зависимости от рассто­ яния до пикселя (0, 0 ).

В работе [22] для решения проблемы краевых эффектов предлагает­ ся использовать уменьшение размер окна усреднения. При условии, что в окрестности точки (0, 0 ) на изображении находятся резкая граница авторы [22] предлагают использовать размер окна в два раза меньшей чем базовый.

1.2.7. Сравнение подходов SFF и SFD Основным достоинством методов семейства SFD является тот факт, что для построения трехмерной модели сцены методам этого семейства требуется всего два изображения сцены. Данный факт позволяет осуществ­ лять трехмерную реконструкцию быстро, и даже производить трехмерную реконструкцию для динамических сцен [24]. Методам семейства SFF для корректной работы требуется получить большой набор изображений сце­ ны, что делает их не применимыми для динамических сцен. Однако для огромного количества приложений, таких как например дефектоскопия, где наблюдаемый объект статичен, данное ограничение не играет столь большой роли.

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

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

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

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

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

Методы уточнения трехмерной модели [15, 17, 27, 28] также не в состо­ янии улучшить качество обработки областей без текстуры. Данные методы опираются на результат работы базовой схемы SFF как на первое прибли­ жение, и если это первое приближение было ошибочным, то ошибочным будет и результат уточнения получаемый с помощью этих методов. Метод с адаптивным взвешиванием, предложенный в [29] позволяет сделать размер окна достаточно большим без существенного ухудшения точности получа­ емой трехмерной модели. Однако данный метод все же не в состоянии кор­ ректно обрабатывать нетекстурированные области произвольного размера.

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

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

Описанная проблема существенно ограничивает применимость мето­ дов семейства SFF для моделирования объектов реального мира. В работе [22] для решения данной проблемы предлагается процедура фильтрации ложных замеров. Авторы работы предлагают обработать изображение, на котором вся сцена видна в резкости, с помощью меры резкости, и затем применить к этому изображению усреднение. Далее итоговое усредненное изображение преобразуется в маску ненадежных замеров по следующей формуле где - порог на значение меры резкости, который подбирается вруч­ ную. После получения карты глубины с помощью базовой схемы SFF авторы работы [22] предлагают отбросить все замеры в карте глубины, которые соответствуют нулям в и провести интерполяцию для получе­ ния итоговой карты глубины. Несмотря на то, что в оригинальном методе предлагается использовать для отброса ложных замеров изображе­ ние данный метод можно применять даже в случае, если получение невозможно из-за физических ограничений. В данном случае следует ис­ пользовать в формуле (1.12) вместо величину (1,..., ), которая представляет собой матрицу, в каждой ячейке которой находится максимум значений меры резкости в данном пикселе по всем изображениям входного Стоит заметить, что локальная процедура фильтрации с помощью пра­ вила (1.12) не позволяет обеспечить отброс всех ложных замеров. В процес­ се фильтрации будет отброшена часть верных замеров, и неизбежно будет пропущена часть ложных замеров.

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

Рисунок 1.6 иллюстрирует проблему ложных замеров при работе ме­ тодов SFF с объектами реального мира. На рисунках а) и б) приведена пара входных изображений из набора = {1,..., }, состоящего из изображений. При получении данного набора производилось сканирование небольшого участка поверхности природного минерала. В центральной ча­ сти поверхности, видимой на изображениях с микроскопа, имеется углуб­ ление. Данное углубление освещено хуже, чем остальная поверхность объ­ екта, поэтому при получении изображений области вне углубления были частично засвечены.

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

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

В качестве такого компактного представления будут использоваться так называемые мультифокус-изображения. Алгоритмы синтеза мультифо­ кус-изображений [31–35] получают на вход набор изображений, на каждом из которых в резкости видна лишь незначительная часть сцены, а на вы­ ходе выдают изображение, на котором все участки сцены видны в резко­ сти. Некоторые методы построения мультифокус-изображений опираются на методы семейства SFF [31].

На рисунке 1.7 приведен пример мультифокус изображения для участ­ ка поверхности природного минерала. Мультифокус изображение было по­ лучено методом [31]. Видно, что на мультифокус-изображении видна в рез­ кости сразу вся сцена целиком, в то время как на входных изображениях (рис. 1.7,а-д) в резкости виден лишь небольшой срез сцены.

Рис. 1.7. На рисунках (а-д) приведены изображения из входного набора, состоящего из 100 изображений, а на рисунке е) приведено мультифокус-изображение, рассчитанное по этому набору 1.5. Заключение В данной главе была описана актуальная для многих приложений за­ дача построения трехмерной модели микрообъектов по изображениям с микроскопа. Обзор традиционных методов построения трехмерных моде­ лей объектов по изображениям свидетельствует о том, что оптимальными методами для решения этой задачи являются методы семейств shape from focus (SFF) и shape from defocus (SFD). Также приведенный сравнительный анализ подходов SFF и SFD показывает что для задачи моделирования микрообъектов по изображениям больше пригоден метод SFF из-за того факта, что он не использует прямого моделирования процесса формирова­ ния изображения, что делает его более стабильным и универсальным.

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

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

Устойчивый метод построения поверхности Для решения проблемы неустойчивости существующих методов shape предлагается новый метод. Как было отмечено в предыдущей from focus главе большинство существующих методов SFF локальны по своей приро­ де. Ключевым отличием предлагаемого метода SFF от существующих ана­ логов является тот факт, что метод ищет решение задачи SFF с помощью глобальной минимизации функционала качества, называемого функцией энергией.

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

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

Для построения функции энергии, с помощью которой решается зада­ ча SFF используется теория Марковских случайных полей (MRF).

2.1. Марковские случайные поля Многие задачи машинного зрения могут быть успешно сформулирова­ ны в терминах теории Марковских случайных полей [36–40]. Теория Мар­ ковских случайных полей позволяет строить оценки различных простран­ ственно-переменных величин по изображениям, при этом накладывая на эти величины определенные априорные ограничения. В качестве таких про­ странственно переменных величин могут выступать, например, значение диспаритета, в задаче стереореконструкции [37] и интенсивность изображе­ ния, в задаче подавления шума на изображениях [38].

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

в случае если для любого = 1, верно, что где - подмножество элементов которое является соседями, то случайная величина = {1,..., } является Марковским случайным по­ лем. Говоря другими словами представляет собой Марковское случайное поле в случае если плотность вероятности для элемента зависит только от его непосредственных соседей, задаваемых множеством.

Марковское случайное поле может выступать в качестве модели в за­ даче стереореконструкции, тогда неизвестное нам = {1,..., } пред­ ставляет собой вектор, в который собраны значения диспаритета для всех пикселей первого изображения стереопары [37]. При этом каждое при­ нимает значения от 0 до значения, где представляет собой мак­ симальный допустимый диспаритет. В случае решения задачи подавления шума на полутоновом изображении в качестве = {1,..., } выступает вектор значений реальной интенсивности пикселей без шума и каждое принимает значения от 0 до 255.

2.1.1. Оценка параметров поля Зачастую в большинстве приложений нет возможности наблюдать, или как-то непосредственно измерить неизвестное нам состояние Марков­ ского поля = {1,..., }. Будем считать, что вместо этого у нас есть некоторое наблюдение = {1,..., }. При этом будем считать, что нам известна функция правдоподобия иметь наблюдение при условии состояния поля. Функция ( | ) отвечает за моделирование шумов и зависимости наблюдаемых данных от неизвестного нам состояния системы. Например для задачи устранения шу­ ма на изображении в качестве наблюдения выступает исходное зашум­ ленное изображение. А в качестве модели шума ( | ) можно выбрать например Гауссовское распределение Принимая во внимание модель наблюдений которая задается с по­ мощью формулы (2.2) можно записать формулу Байеса и тогда можно построить оценку максимума апостериорной вероятно­ сти для неизвестного нам максимизируя вероятность (^|). Если лого­ рифмировать правую часть (2.4) и взять ее со знаком минус то описанную оценку можно получить путем Первое слагаемое выражения в правой части (2.4) можно разложить следующим образом исходя из (2.2) Однако со вторым слагаемым формулы (2.5) в общем случае никако­ го упрощающего разложения сделать нельзя. И в общем случае оценка неизвестного состояния = {1,..., } путем минимизации (2.5) пред­ ставляет собой крайне сложную задачу. Однако в случае если допустить, что представляет собой Марковское случайное поле, минимизация (2.5) становится осуществимой.

2.1.2. Теорема Хаммерсли-Клифорда Пожалуй самым главным результатом теории Марковских случайных полей для приложений компьютерного зрения является теорема Хаммер­ сли-Клифорда [41]. Пусть у нас имеется граф =,. Количество вершин данного графа равно и каждой вершине графа поставлена в соответствие случайная величина. Ребра графа соответствуют множе­ ствам соседей. То есть из вершины, которая соответствует выходит | | ребер, которые идут в вершины, которые соответствуют соседям.

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

Таким образом с учетом формул (2.7) и (2.6) можно переписать (2.5) в виде Таким образом для случая Марковского случайного поля формулу (2.5) можно существенно упростить. И для определенных видов функции правдоподобия ( | ) и графа =, существуют эффективные ме­ тоды [36, 37, 39, 41–43] поиска минимума (2.8).

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

2.2. Предлагаемый метод 2.2.1. Статистическая формулировка задачи Для построения метода SFF с использованием теории Марковских слу­ чайных полей сформулируем задачу SFF в терминах математической ста­ тистики. Будем считать, что карта глубины, которую нам необходимо построить по набору изображений, представляет собой Марковское слу­ чайное поле. Набор входных изображений = {1,..., } в этом случае представляет собой наблюдаемые данные, тогда как представляет собой неизвестное нам состояние случайного поля, оценку которого нам требует­ ся построить. Будем считать что каждый элемент карты глубины может принимать значения из набора {1,..., }, то есть каждому пикселю карты глубины в результате решения должен быть приписан индекс одного из изображений из набора. Тогда по формуле Байеса имеем Использование входных изображений в качестве наблюдений напря­ мую при построении трехмерных моделей по фокусу является неудобным.

Также как и все существующие методы SFF предлагается отказаться от использование входных изображений напрямую, и вместо этого исполь­ зовать карты меры резкости = {1,..., } (см. ст. 23). Тогда формулу (2.9) можно будет записать как Исходя из формулы (2.10) оценку максимальной апостериорной веро­ ятности (MAP) для карты глубины можно записать в виде 2.2.2. Функция правдоподобия Для того, чтобы успешно оптимизировать функционал (2.11) необхо­ димо в первую очередь осуществить упрощение первого слагаемого форму­ лы, которое отвечает за правдоподобие решения. Для того, чтобы сделать это предлагается ввести предположение о том, что значения меры резко­ сти в некотором пикселе (0, 0 ) зависят статистически только от значения глубины 0 в данном пикселе, но не зависят от значений глубины во всех остальных пикселях карты глубины. Будем называть вектор в котором расположены по порядку значения меры резкости в пиксе­ ле (0, 0 ) профилем меры резкости в пикселе (0, 0 ). Тогда при условии сделанного предположения можно разложить (|) как где каждый из членов (^, |, ) представляет собой вероятность на­ блюдать заданный профиль меры резкости при условии определенного зна­ чения глубины (, ).

2.2.3. Структура поля Для того, чтобы осуществить разложение второго члена в формуле (2.11) нам необходимо определить множества соседей для Марковского по­ ля, состояние которого нам необходимо оценить. На рис. 2.1 изображена предлагаемая структура графа =, который определяет множе­ ства соседей для элементов поля.

Граф представляет собой регулярную решетку, вершины которой со­ ответствуют пикселям карты глубины. Каждый пиксель карты глубины соединен ребрами со своими непосредственными соседями по горизонта­ ли и вертикали. То есть у угловых пикселей карты глубины имеется два соседа, у граничных пикселей карты глубины имеется по три соседа, а у Рис. 2.1. На рисунке изображена структура графа соседей Марковского случайного поля для решения задачи SFF. Зеленые отметки на графе указывает на клики в графе размера один и два пикселей карты глубины, которые не примыкают к границам имеется по четыре соседа. То есть для не граничного пикселя карты глубины, = При такой структуре соседей Марковского поля исходя из формулы (2.7) () может быть записано следующим образом где,1 () и,2 () представляют собой потенциалы клик размера один и два соответственно. Потенциалы клик более высокого порядка в формуле (2.14) отсутствуют в связи с тем, что максимальный размер кли­ ки, задаваемой графом, который изображен на рисунке 2.1, равен двум.

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

Потенциал клик второго порядка зависит сразу от пары соседних зна­ чений карты глубины. То есть,2 () =,2 (,,, ) где (, ) и (, ) являются соседями в графе. Данный потенциал заключает в себе апри­ орную вероятность наблюдать конкретную конфигурацию пары соседних элементов карты глубины. В связи с тем, что форма многих объектов при­ родного происхождения и объектов, сделанных человеком, зачастую не яв­ ляется абсолютно случайной, потенциал клик второго порядка можно ис­ пользовать для учета априорной информации о форме поверхности объек­ та. Например для гладких объектов значения глубины в соседних пикселях не должны отличаться друг от друга слишком сильно. Поэтому в отличии от потенциала клик первого порядка в предлагаемом методе,2 () не равен нулю и будет учитываться при минимизации (2.11). Таким образом 1 Стоит заметить, что это не является ограничением предлагаемого метода. В случае если предла­ гаемый метод применяется к задаче, для которой присутствует априорная информация о вероятности наблюдать определенные значения карты глубины в некоторых пикселях эта информация может быть учтена без изменения метода 2.2.4. Итоговая функция энергии С учетом допущений, сделанных в прошлых двух подразделах, запи­ шем итоговую функцию для оптимизации (2.11) в более удобном виде. Для простоты обозначений запишем карту глубины в виде одномерного век­ тора = {1,..., }. Также поставим в соответствие каждому элементу профиль меры резкости соответствующего ему пикселя карты глубины.

Исходя из (2.13) можно записать ln( (|)) как сумму Величины ( ) в формуле (2.16) принято называть унарными потен­ поля [37]. Унарный потенциал поля заключает в себе информацию циалами о правдоподобии 2.

Исходя из (2.15) можно записать ln( ()) как сумму где - соседи. Величины, (, ) называются парными потен­ поля [37] и заключают в себе априорную информацию о форме циалами поверхность объекта, трехмерную модель которого нам требуется постро­ ить. С учетом (2.16) и (2.17) можно переписать (2.11) как 2 В случае если в приложении имеется априорная информация о вероятности наблюдать опреде­ ленные значения карты глубины в некоторых пикселях то данную информацию можно также включить в унарный потенциал путем простого суммирования Функция () называется функцией энергии. Величина в формуле в (2.18) представляет собой вес парных потенциалов и определяет силу регуляризации решения. Определив унарные и парные потенциалы, а затем оптимизировав функцию энергии в формуле (2.18) можно получить оценку карты глубины (2.19), которая является оценкой максимума апостериорной вероятности.

2.2.5. Унарный потенциал Так как унарный потенциал отвечает за правдоподобие, он должен быть тем меньше, чем больше вероятность наблюдать имеющийся набор входных данных при условии некоторой заданной конфигурации поля. Ис­ ходя из упрощающего предположения, сделанного в разделе 2.2.2 унарный потенциал ( ) должен иметь вид где = {1,..., } - профиль меры резкости в пикселе, который соот­ ветствует. То есть унарный потенциал элемента поля не должен зави­ сеть от значений меры резкости в каких-то других пикселях изображения, кроме пикселя, который соответствует. Простейший пример унарного по­ тенциала, который можно применить при решении задачи SFF выглядит следующим образом где это индекс максимального элемента в профиле меры резко­ сти. При использовании унарного потенциала вида (2.21) функция энергии (2.18) будет штрафовать карту глубины на величину 1, в случае если она проходит не через точку с максимальным значением меры резкости в пик­ селе, который соответствует. В случае если карта глубины проходит через максимум меры резкости в пикселе, который соответствует то за данный пиксель карты глубины будет получать нулевой штраф.

Рис. 2.2. Примеры модельных профилей меры резкости для иллюстрации недостатков унарного потенциала из формулы (2.21). Профиль на рисунке а) имеет один ярко вы­ раженный главный пик слева, а также один менее значительный пик справа. Профиль на рисунке б) имеет практически случайную структуру Однако потенциал, задаваемый формулой (2.21) не является оптималь­ ным. На рисунке 2.2 изображены два примера профилей меры резкости.

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

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

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

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

Модельный профиль меры резкости на рисунке 2.2 б) иллюстриру­ ет еще одну проблему простейшего унарного потенциала (2.21). Профиль, изображенный на рисунке 2.2 б) имеет практически случайную структуру.

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

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

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

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

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

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

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

Также в нижней части рисунка 2.4 а) отмечена горизонтальная линия, для которой иллюстрируются значения унарного потенциала. На рисунке 2. б) приведено изображение значений унарного потенциала по данной ли­ нии. Ось на рисунке 2.4 б) соответствует оси на изображении а). Ось на рисунке 2.4 б) соответствует глубине. Белый цвет на рисунке 2.4 б) значению унарного потенциала, равному, а черный цвет соответствует нулевому значению унарного потенциала.

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

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

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

Таким образом без использования возможностей парного потенциала ме­ тод основанный на (2.18) превращается в обычный локальный метод SFF, который в каждой точке ищет наиболее резкое изображение поверхности объекта.

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

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

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

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

В работе [37] описываются парные потенциалы, которые больше соот­ ветствуют предположению о кусочной гладкости поверхности.

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

Дополнительно стоит отметить, что парные потенциалы в формулах (2.24) и (2.25) ограниченны сверху величиной. Данное ограничение необ­ ходимо для того, чтобы в областях резких перепадов глубины на объекте, или в области границы объекта, парный потенциал не накладывал на пе­ репад глубины слишком большой штраф. Парные потенциалы, которые ограничивают штраф сверху таким образом называются сохраняющими [40] 4. Если отказаться от использования ограничения сверху зна­ скачки чения парных потенциалов (2.24) и (2.25) то области сильных перепадов глубины на реальном объекте будут сглаживаться, что будет приводить к ошибкам [37].

Парный потенциал предлагаемый автором для решения задачи SFF ос­ новывается на (2.25). Причина, по которой данный вид парного потенциала предпочтительней чем (2.24) проиллюстрирована на следующем модельном примере.

4 Стоит заметить, что обобщенная модель Потса также является парным потенциалом, сохраня­ ющим скачки Рис. 2.5. Иллюстрация проблем в поведении парного потенциала, задаваемого форму­ лой (2.24) при реконструкции трехмерных моделей гладких поверхностей. Черно-белый фон представляет собой значения унарного потенциала. Красными линиями отмечены различные решения, которые имеют штраф, накладываемый парным потенциалом, та­ кой же как и зеленое решение, которое является оптимальным Пусть имеется одномерная задача оценки формы поверхность объекта и ее решение осуществляется путем минимизации функционала Пусть элементы вектора = {1,..., } принимают значения из мно­ жества {1,..., }. Пусть унарные потенциалы ( ) принимают значения в соответствии с изображением на рисунке 2.5. На модельном примере из рисунка 2.5 унарные потенциалы в левой и правой частях картинки имеют ярко выраженный минимум, в то время как унарные потенциалы по цен­ тру картинки не отдают предпочтения ни какому конкретному значению Понятно, что желаемым результатом оценки является кривая, кото­ рая в левой и правой частях картинки проходит через области минимума унарных потенциалов, а в центральной области гладко связывает левую и правую части. В частности минимум обоих частей формулы (2.26), при использовании парного потенциала (2.24), достигается, если связать левую и правую части с помощью прямой линии. Данное решение изображено на рисунке 2.5 зеленой линией. Однако стоит заметить, что существует множество решений, которые обладают точно таким-же штрафом парного потенциала, как и оптимальное зеленое решение. Эти решения изображены на рисунке красными линиями. Поэтому в случае если во входных данных, через которые рассчитывается унарный потенциал, будет присутствовать шум, то выбор между этими различными вариантами решения будет за­ висеть исключительно от того как будет распределен шум на конкретном примере. Именно эта нестабильность потенциала (2.24) делает более пред­ почтительным для использования в задаче SFF потенциала (2.25).

Исходя из приведенных выше доводов парный потенциал, предлагае­ мый в работе, имеет следующий вид Коэффициент представляет собой квадрат отношения между раз­ мером пикселя изображений, и шагом по глубине между парой соседних изображений в наборе = {1,..., }. Использование нормировочного ко­ эффициента позволяет сделать разность ( )2 пропорциональной квадрату Евклидова расстояния в трехмерном пространстве.

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

Рис. 2.6. На рисунке приведен пример расчета карты наличия сильной текстуры на реальном примере. На рисунке а) приведено мультифокус-изображение поверхности природного минерала, а на рисунке б) приведена карта наличия сильной текстуры, рассчитанная описанным методом Индикатор наличия сильной текстуры в окрестности элемента поля рассчитывается следующим образом. Вычислим матрицу, элемент (, ) которой равен максимальному значение меры резкости в пикселе (, ) сре­ ди всех изображений набора. После этого рассчитаем маску, каждый элемент которой равен 1 если соответствующий пиксель превосходит некоторый порог, и равен 0 в противном случае. После этого полученную таким образом маску предлагается отфильтровать с помощью математиче­ ской морфологии операцией "открытие"с круглым структурным элемен­ том радиуса. После этого полученную отфильтрованную маску предла­ гается записать в виде одномерного вектора, каждый элемент которого является индикатором наличия существенной текстуры в окрестности со­ ответствующего элемента поля. За счет такой формы предлагаемый парный потенциал допускает сильные перепады в карте глубины только в областях, где присутствует значительное количество текстуры. Величи­ ны и являются входными параметрами алгоритма. На рисунке 2. приведен пример расчета карты наличия сильной текстуры для реального примера.

2.2.7. Оптимизация функционала В прошлых разделах были определены унарный и парный потенциалы ( ) и, (, ). Таким образом функция энергии из (2.18) теперь пол­ ностью определена и теперь необходимо определить, как функцию энергии данного типа оптимизировать. Оптимизация функций энергии вида (2.18) является темой активных исследований. Как показано, например, в работе [37] поиск точного минимума функции энергии вида (2.18) в общем случае представляет собой NP-hard задачу.

Однако, несмотря на то что поиск точного минимума данной энергии не представляется реальным, с учетом мощностей современных компью­ теров, существуют и активно развиваются методы приближенного поиска минимума (2.18). К таким алгоритмам относятся метод Iterated Conditional [45], методы семейства Belief Propagation (BP) [46], метод Tree­ Modes (ICM) Reweighted Message Passing (TRW) графов - expansion и - swap [37]. Каждый из упомянутых методов обладает своими достоинствами и недостатками.

В работе [45] приводится сравнительный анализ сходимости и каче­ ства результатов этих методов на реальных данных из пяти различных за­ дач машинного зрения. Метод ICM представляет в основном исторический интерес, в связи с тем, что по сути является простейшим итерационным методом локальной минимизации. Для того, чтобы данный метод сошелся корректно ему требуется очень точное локальное приближение, которое в большинстве случаем затруднительно получить. В соответствии со срав­ нительным анализом в [45] метод BP по сравнению с методами на основе разрезов графов и методом TRW сходится крайне медленно и зачатую ми­ нимум, к которому он сходится, обладает существенно большей энергией, чем результаты работы методов - expansion, - swap и TRW. Также авторы работы отмечают, что на их тестовых данных алгоритм - swap практически никогда не достигает минимумов лучше, чем - expansion и зачастую сходится медленнее.

Из оставшейся пары методов - expansion и TRW для решения задачи SFF предлагается использовать первый метод. В соответствии со сравне­ нием в работе [45] метод TRW сходится существенно дольше, чем метод -expansion. Однако минимумы к которым он сходится зачастую имеют меньшую энергию, чем результаты - expansion. Однако авторы работы [45] отметили следующий факт. Несмотря на то, что минимумы к которым сходится TRW обладают меньшей энергией чем минимумы - expansion ка­ чественно результаты работы этих алгоритмов практически неотличимы.

Для большинства тестовых задач авторы [45] имели эталонный результат, полученный путем ручной или автоматической разметки 5. В соответствии с замерами, приведенными в [45] результаты алгоритмов - expansion и TRW зачастую имеют существенно меньшую энергию, чем эталон. Поэто­ му ошибки в результатах этих методов связаны не с качеством минимиза­ ции функционала, а скорее с несовершенством модели задаваемая энергией (2.18).

Поэтому из соображений компромисса между вычислительной слож­ ностью и качеством результата в данной работе используется алгоритм 5 Для задачи стереореконструкции, например, проводилось сравнение с результатами лазерного сканирования - expansion. Несмотря на то, что из-за формы парного потенциала, пред­ ложенного в (2.27), функция энергии (2.18) является нерегулярной [37] ал­ горитм -expansion по прежнему применим для минимизации, как было показано в [48].

2.2.8. Усреднение меры резкости Как можно заметить, предлагаемый метод, в отличии от существу­ ющих аналогов [9, 15, 21, 22, 24], не использует усреднение меры резко­ сти. В то время как существующие методы сначала осуществляют усред­ нение меры резкости по окну, унарные потенциалы в предлагаемом ме­ тоде рассчитываются напрямую по изначальным картам меры резкости Данная особенность связана с тем, что в формуле энергии (2.18) фи­ гурирует сумма всех унарных потенциалов ( ). Поэтому предлагаемый метод осуществляет неявное усреднение значений меры резкости по всей поверхности итоговой карты глубины в процессе решения оптимизаци­ онной задачи (2.19).

Однако усреднение меры резкости в предлагаемом методе можно ис­ пользовать при условии что есть необходимость ускорить работу алгорит­ ма. Пусть нам требуется построить трехмерную модель участка поверхно­ сти микрообъекта, наблюдаемый с помощью микроскопа. Путь величина глубины резкости оптической системы составляет 10 микрон, а размер пик­ селя на изображении составляет один микрон 6.

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

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

2.2.9. Итоговый алгоритм С учетом выкладок и замечаний приведенных в данном разделе ито­ говый алгоритм SFF на основе Марковских случайных полей выглядит следующим образом. Пусть у нас имеется набор входных изображений = {1,..., }, полученный в результате сканирования поверхности на­ блюдаемого объекта с регулярным шагом 1. Для каждого изображения набора вычисляем меру резкости 2. При наличии возможности осуществляем уменьшение карт меры рез­ кости как описано в 2.2. 3. По картам меры резкости вычисляем для каждого пикселя изоб­ ражения значение унарного потенциала ( ) с помощью формулы (2.22), тем самым получая трехмерный массив значений унарного по­ 4. По картам меры резкости вычисляем карту наличия существенной текстуры в соответствии с написанным в 2.2. 5. С помощью алгоритма -expansion осуществляем оптимизацию (2.18) с парным потенциалом в виде, задаваемом (2.27) 2.3. Эксперименты 2.3.1. Тестовая базы для сравнения В отличии от задачи стереореконструкции [7] для тестирования мето­ дов shape from focus не существует стандартной тестовой базы изображе­ ний. Поэтому для оценки качества работы предлагаемого метода и срав­ нения метода с существующими аналогами автором была собрана тесто­ вая база из 27 наборов изображений с микроскопа. Для создания тестовой базы использовался микроскоп Leica Z6 APOA, с установленной на него камерой разрешения 1280x1024. Все изображения для экспериментов бы­ ли получены в градациях серого. Сканирование объектов производилось с максимальным увеличением, глубина резкости для которого на данном микроскопе составляет 15 микрон. Величина пикселя изображения, для максимального увеличения, в данной системе составляет порядка 2 мик­ рон. Шаг между соседними изображениями наборов по фокусу был равен половине глубины резкости. В каждом из тестовых наборов содержалось от 50 до 200 изображений.

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

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

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

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

Поэтому в такие области отмечались вручную и результаты работы алго­ ритмов в этих областях не учитывались.

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

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

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

2.3.3. Результаты сравнения Для сравнения на встроенном языке сценариев MATLAB был реализо­ ван предложенный алгоритм, алгоритм Наяра [9] и доработанный алгоритм Наира и Стюарта [22]. Алгоритм Наира и Стюарта частично опирается на фотографию сцены с большой глубиной резкости, на которой сцена цели­ ком видна в резкости. Например, на базе фотографии сцены подбирается размер окна для усреднения меры резкости. При сильном увеличении мик­ роскопа получить качественную фотографию сцены с большой глубиной резкости не представляется возможным. Поэтому при реализации исполь­ зовались только те особенности алгоритма, которые не опираются на фо­ тографию сцены с большой глубиной резкости. Также алгоритм Наира и Стюарта был дополнен процедурой постобработки карты глубины, описан­ ной в [30].

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

Таблица 2.1. В данной таблице приводятся результаты сравнения предлагаемого метода с существующими аналогами С помощью каждого из алгоритмов были реконструированы поверхно­ сти объектов для всех тестовых наборов из базы. Для каждого тестового набора результаты работы алгоритмов сравнивались с эталоном по метри­ ке (2.28). Далее для каждого из алгоритмов значение метрики усреднялось по всем наборам, для получения средней ошибки алгоритмов. В таблице 2. приведены полученные таким образом средние ошибки для трех реализо­ ванных алгоритмов. Видно, что предлагаемый алгоритм в среднем дает более стабильные результаты, чем существующие аналоги и практически в два раза превосходит метод Наира и Стюарта по количеству грубых оши­ бок в результирующей карте глубины.

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

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

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

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

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