На правах рукописи
Гаганов Виктор Александрович
Исследование и разработка программных
средств распознавания образов для решения
задачи трехмерного моделирования
в микроскопии
Специальность 05.13.11 – математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Москва – 2011
Работа выполнена в Учреждении Российской академии наук Институте прикладной математики имени М.В. Келдыша РАН.
Научный руководитель: кандидат физико-математических наук, доцент, Баяковский Юрий Матвеевич
Официальные оппоненты: доктор физико-математических наук, профессор, Карташев Владимир Алексеевич кандидат физико-математических наук, Ветров Дмитрий Петрович
Ведущая организация: Учреждении Российской академии на ук Институт вычислительной мате матики и математической геофизики Сибирского отделения РАН
Защита состоится «31» мая 2011 г. в 11 часов на заседании диссертационного совета Д 002.024.01 при Учреждении Российской академии наук Институте прикладной математики имени М.В. Келдыша РАН, расположенном по адре су: 125047, Москва, Миусская пл.,
С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В. Келдыша РАН.
Автореферат разослан « » 2011 г.
Ученый секретарь диссертационного совета, доктор физико-математических наук Т.А. Полилова
Общая характеристика работы
Объект исследования и актуальность работы С момента появления первого оптического микроскопа в конце XVI – начале XVII века это устройство плотно вошло в жизнь человека. Сейчас практически невозможно представить себе современное общество без этого изобретения. В данный момент оптические микроскопы находят применение в широком спектре приложений, начиная от рутинных медицинских и био логических исследований, заканчивая контролем качества на высокотехноло гичных производствах.
Распространение цифровых видеокамер во второй половине XX века при вело к появлению нового класса задач, связанных с оптическими микроскопа ми. Появление возможности захвата изображений в цифровом формате дало толчок развитию технологий автоматического улучшения и анализа изобра жений, полученных с помощью микроскопа1. Благодаря стремительному ро сту вычислительных мощностей процессоров круг задач по обработке и ана лизу изображений с микроскопа расширяется с каждым годом, ставя перед исследователями все новые и новые задачи.
В данной работе рассматривается одна из важнейших проблем в задачах автоматического анализа изображений, полученных с помощью оптического микроскопа, — задача построения трехмерной модели сцены, наблюдаемой с помощью микроскопа. Трехмерная модель сцены незаменима в таких при ложениях, как, например, анализ качества на производстве печатных плат, где требуются измерения различных показателей формы поверхности наблю даемого объекта. Стоит заметить, что реконструкция трехмерных моделей микрообъектов традиционными методами, такими как лазерное сканирова ние, является затруднительной из-за физических ограничений, налагаемых размерами объектов. Этот факт придает дополнительную актуальность ме тодам построения трехмерных моделей, которые оперируют непосредственно изображениями, полученными с помощью микроскопа.
Задача построения трехмерных моделей объектов по изображениям с микроскопа рассматривается в работе в двух формулировках.
Построение модели поверхности общего вида ке предполагается, что форма участка поверхности объекта, наблюда емого с помощью микроскопа, представима в виде карты глубины 2.
Юрковец Д. И. Программное обеспечение для количественного морфологического анализа струк тур по полутоновым изображениям // Кандидатская диссертация. ВМиК МГУ им. М.В. Ломоносова, Москва. 1998.
2 Картой глубины называется представление трехмерной модели в виде матрицы, в каждой ячей ке которой записано расстояние от некоторой фиксированной плоскости в трехмерном пространстве до поверхности объекта.
Тогда по набору изображений с микроскопа требуется построить трех мерную модель участка поверхности объекта.
Построение модели плоского участка поверхности объекта лагается, что наблюдаемый под микроскопом участок объекта плоский, и требуется оценить положение и ориентацию данного участка поверх Цель диссертационной работы Целью работы является исследование и разработка методов и алгорит мов построения трехмерных моделей объектов по изображениям с микроско па, а также создание на основе разработанных методов программной системы для построения трехмерных моделей микрообъектов.
Основные задачи
работы:
Исследование существующих алгоритмов построения трехмерных мо делей объектов по изображениям с микроскопа. Разработка метода по строения трехмерной модели участка поверхности объекта, который представим в виде карты глубины.
Разработка специализированного метода для оценки положения и ори ентации плоского участка поверхности объекта по набору изображений с микроскопа.
Верификация разработанных алгоритмов путем оценки качества их ра боты на реальных данных и сравнение предложенных методов с суще ствующими аналогами.
Разработка программной системы построения трехмерных моделей мик рообъектов с применением предложенных методов.
Научная новизна В рамках диссертации разработан новый метод построения трехмерных моделей участка поверхности объекта, который представим в виде карты глу бины. Отличительной чертой предложенного метода является его повышен ная устойчивость к ложным данным, часто возникающим в областях поверх ности объектов, которые не содержат текстуры, слабо освещенных областях поверхности и в местах присутствия бликов. В работе представлены резуль таты сравнительного анализа, подтверждающие, что предложенный метод позволяет добиться более устойчивых и точных результатов, чем существую щие аналоги.
В рамках решения задачи оценки положения и ориентации плоского участка поверхности объекта предложен новый метод для определения то го, можно ли считать замер положения участка сцены надежным. Также предложен метод, позволяющий определить, можно ли по набору трехмер ных замеров, содержащему ошибки измерения, осуществить надежную оцен ку положения и ориентации плоскости. Кроме того, предложенные методы позволяют сделать оценку положения и ориентации плоского участка поверх ности объекта более устойчивой к ошибкам в измерениях.
Практическая значимость Предложенный метод построения трехмерной модели участка поверхно сти объекта по изображениям с микроскопа существенно расширяет класс объектов, для которых применим данный подход. Существующие методы в основном ориентированы на работу с объектами, отражающие свойства по верхности которых близки к Ламбертовской модели. Предложенный метод позволяет строить корректные модели объектов, состоящих из таких матери алов, как металл и стекло, на поверхности которых возможно наличие бликов.
Также предложенный метод способен корректно моделировать объекты, на поверхности которых присутствуют области без текстуры, в то время как су ществующие методы ориентированы на работу с объектами, на поверхности которых видимая текстура присутствует повсеместно.
Разработанный метод определения положения и ориентации плоского участка поверхности объекта позволяет производить оценку плоскости даже при наличии во входных данных шумов и большого количества ошибочных измерений. Разработанный метод определения надежности оценки плоскости позволяет для любых входных данных определить, удалось ли по ним кор ректно оценить положение и ориентацию плоского участка поверхности объ екта.
На основе предложенных методов была создана программная система для моделирования поверхности алмазов и дефектов внутри алмазного сы рья. Данная система была интегрирована в программный продукт 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 статьи в рецензируемых журналах, рекомендованных ВАК [1, 2], две статьи в сборни ках трудов конференций [3, 4], а также тезисы доклада [5].
Структура и объем диссертации Диссертация состоит из введения, 4 глав, заключения и библиографии.
Общий объем диссертации составляет 133 страницы, включая 33 рисунка.
Библиография включает 73 наименования.
Содержание работы Во введении обоснована актуальность диссертационной работы, сфор мулированы цели и задачи, аргументирована научная новизна исследований, показана практическая значимость полученных результатов. Описана струк тура диссертации.
В первой главе приводится описание математической модели форми рования изображения и дается понятие области резкости, описываются базо вые принципы работы методов построения трехмерных моделей по изображе ниям с микроскопа и дается обзор существующих методов.
В первом разделе описывается модель формирования изображения и дается базовый принцип работы методов построения трехмерных моделей по изображениям с микроскопа.
Для понимания методов построения трехмерных моделей объектов по изображениям с микроскопа необходимо понимание принципов формирова ния изображений в реальных оптических системах. На рис. 1 а) изображена простейшая модель оптической системы – оптическая система с тонкой лин зой. За линзой находится поверхность сенсора, с помощью которого осуществ ляется считывание изображения. Все световые лучи, исходящие из точки сце ны и попадающие на линзу, сходятся в точке. При этом расстояния от точек и до линзы подчиняются т.н. уравнению тонкой линзы:
где — фокусное расстояние линзы. В случае если для какой-то точки точка схода преломленных линзой лучей не попадает на сенсор, который осуществляет считывание изображения, энергия лучей, исходящих из точки, рассеивается по небольшому участку поверхности сенсора (рис. 1 б).
Рис. 1. На рисунке a) изображена оптическая система и точка P, изображение которой попадает на сенсор с идеальным фокусом. На рисунке б) изображение точки P’ на сенсоре будет расфокусированным Размер участка поверхности сенсора, по которому рассеиваются лучи, исходящие из точки, пропорционален расстоянию от точки до поверх ности сенсора. Поэтому при получении фотографии сцены только некоторая часть сцены оказывается на фотографии в резкости. Эта часть сцены назы вается областью резкости, и чем дальше точка сцены находится от области резкости, тем более размытым будет выглядеть изображение этой точки на фотографии. Расстояние между самой близкой и самой дальней границами пространства, которые видны на изображении в резкости, называется глуби ной резкости.
Методы построения трехмерных моделей по изображениям с микроскопа используют информацию о степени размытия точки изображения для того, чтобы восстановить геометрию наблюдаемой сцены.
Во втором разделе дается обзор существующих методов построения трехмерных моделей по изображениям с микроскопа.
Методы построения трехмерных моделей объектов по изображениям с микроскопа делятся на два семейства: это методы семейства shape from focus (SFF) и методы семейства shape from defocus (SFD). При использовании ме тодов SFF для оценки положения некоторого участка наблюдаемой сцены происходит получение множества по-разному сфокусированных изображений сцены. После этого ищется изображение, на котором данный участок сцены виден в резкости, и положение области резкости оптической системы для най денного изображения принимается за оценку расстояния до данного участка сцены. Далее оценки расстояния для различных участков сцены комбиниру ются для получения трехмерной модели всей сцены целиком. Методы семей ства SFD моделируют степень резкости участка изображения как функцию расстояния до поверхности объекта. Затем по двум различно сфокусирован ным изображениям сцены формулируется обратная задача, решением кото рой является карта расстояний до поверхности сцены, которая полностью определяет трехмерную модель наблюдаемого участка сцены.
Достоинством методов семейства SFD по сравнению с методами SFF яв ляется то, что для построения трехмерной модели сцены необходимо получе ние всего двух изображений. Недостатком же методов SFD является необхо димость явного моделирования процесса формирования изображения сцены.
Поэтому зачастую методы SFD требуют сложной процедуры калибровки для настройки на конкретную оптическую систему и в целом менее устойчивы. В свою очередь методы семейства SFF не требуют никакой настройки на кон кретный объектив, что делает их универсальными и потому привлекательны ми. При этом точность реконструкции поверхности, которой можно добиться с использованием методов SFF, ограничена только величиной глубины рез кости оптической системы. Для оптических микроскопов величина глубины резкости может составлять 20 микрон и меньше, тем самым обеспечивается возможность проводить высокоточные измерения формы поверхности микро объектов. Именно поэтому в диссертационной работе рассматриваются мето ды семейства SFF.
Разработка методов трехмерной реконструкции семейства SFF началась еще в 80-х годах прошлого века. С тех пор было разработано большое коли чество алгоритмов SFF, но большинство из них работает по весьма схожей схеме.
Пусть у нас имеется оптический микроскоп, на котором установлена циф ровая камера. Предполагается, что у нас имеется возможность программно управлять фокусировкой микроскопа. Управление фокусировкой может до стигаться как за счет взаимного перемещения линз в микроскопе, так и за счет перемещения всей оптической системы или наблюдаемого образца с по мощью механической подвижки. Пусть с помощью микроскопа получен набор изображений сцены = {1,..., } с разными положениями области резко сти. Будем считать, что все изображения набора сделаны последовательно и положение области резкости для двух соседних изображений отличается на одинаковую величину, т.е. съемка ведется с регулярным шагом по положению области резкости. Тогда схема алгоритма SFF выглядит следующим образом:
1. Для каждого изображения из набора вычисляем меру резкости, тем самым получая карты значения меры резкости = {1,..., }. В ка честве меры резкости используются высокочастотные фильтры, кото рые реагируют на наличие резких деталей на изображении. Одной из наиболее популярных мер резкости является т.н. модифицированный оператор Лапласа 2. Для каждого проводим усреднение с помощью низкочастотного филь тра, чтобы ослабить влияние шумов камеры. Наиболее часто для усред нения значений меры резкости используется фильтр Гаусса: = * 3. Для каждого пикселя (, ) находим, на котором достигается макси мум величины меры резкости.
4. Положение центра области резкости оптической системы для изображе ния принимаем за оценку положения поверхности объекта в пикселе 5. В связи с тем, что построение трехмерной модели ведется с одного на правления обзора, для представления модели обычно используется так называемая карта глубины = {, }, в каждом пикселе которой со держится индекс изображения, соответствующий максимальному зна чению меры резкости.
В третьем разделе описываются основные недостатки существующих методов построения трехмерных моделей по изображениям с микроскопа се мейства SFF.
Слабой стороной существующих методов семейства SFF является ряд предположений, которые эти методы делают о поверхности объекта и об условиях съемки объекта. Понятно, что в случае, если на некотором участ ке поверхности объекта отсутствует текстура, то независимо от того, каким образом сфокусировано изображение, данный участок поверхности никогда не будет виден на изображении в резкости. Для таких участков поверхности оценка положения в трехмерном пространстве, полученная методами семей ства SFF, будет ошибочной. Также ошибочные оценки положения могут воз никать при неидеальных условиях съемки объекта. Видимая текстура на по верхности объекта может отсутствовать в слабо освещенных областях и при наличии на изображении объекта сильных бликов. Описанные выше эффек ты неизбежно возникают при работе с реальными микрообъектами, состоя щими из металлов, стекла и других недиффузных материалов. Для успешной работы с такими объектами требуются новые методы построения трехмерных моделей по изображениям с микроскопа, отличающиеся повышенной устой чивостью.
В четвертом разделе вводится понятие мультифокус-изображений, ко торые активно используются в работе для иллюстрации входных данных ал горитмов SFF.
Во второй главе предлагается новый метод построения трехмерных моделей по изображениям с микроскопа семейства SFF, отличающийся от существующих аналогов повышенной устойчивостью к ложным данным, ко торые возникают в областях поверхности объекта без текстуры, слабо осве щенных областях поверхности и в местах присутствия бликов.
В первом разделе дается введение в теорию Марковских случайных по лей (MRF), на которой основан предлагаемый автором метод; дается краткий обзор приложений компьютерного зрения, в которых успешно применяется данная теория.
Во втором разделе описывается разработанный метод построения трех мерных моделей по изображениям с микроскопа.
Основным отличием предлагаемого метода от существующих аналогов является то, что он основан на оптимизации функционала качества. В то вре мя как существующие методы решения задачи по сути являются локальны ми, предлагаемый метод ищет решение задачи через минимизацию функции энергии. Именно благодаря этому предлагаемый метод имеет более высокую устойчивость к ложным данным.
Будем считать, что карта глубины, которую необходимо построить по набору изображений = {1,..., }, представляет собой Марковское слу чайное поле. Входной набор изображений = {1,..., } в этом случае представляет собой наблюдаемые данные, тогда как представляет собой неизвестное нам состояние случайного поля, оценку которого нам требуется построить. По формуле Байеса имеем:
Это значит, что оценку максимальной апостериорной вероятности (MAP) для можно записать в виде Первое слагаемое в формуле (4) соответствует вероятности наблюдать вход ные данные при некой заданной конфигурации поля, а второе слагаемое соот ветствует априорной вероятности наблюдать некую заданную конфигурацию поля. Априорная вероятность конфигурации поля позволяет накладывать на итоговую оценку некоторые ограничения, такие как гладкость или кусочная гладкость, и, в сущности, отвечает за регуляризацию решения.
Для простоты запишем карту глубины в виде одномерного вектора = {1,..., }. Будем считать, что непосредственно зависимыми между собой являются только те элементы поля, которые соответствуют соседним пикселям в карте глубины. Обозначим как ( ) множество элементов поля, которые статистически зависят от. Множество ( ) для любого элемента, который не соответствует краевому пикселю карты глубины, содержит в себе 4 элемента – это соседние ячейки карты глубины сверху, снизу, слева и справа. При этом (4) можно записать следующим образом 3 :
где и — это унарные и парные потенциалы элементов поля соответствен но. Константа представляет собой вес парных потенциалов, и отвечает за силу регуляризации решения. Определив и и оптимизировав функцио нал в формуле (5), можно получить оценку карты глубины, которая является оценкой максимума апостериорной вероятности (MAP). Область допустимых значений каждого предлагается ограничить множеством {1, 2,..., }, где – количество изображений во входном наборе.
Рис. 2. Результаты работы методов Наира/Стюарта а) и предложенного метода б) для визуального сравнения. Видно, что в результатах работы метода Наира/Стюарта присут ствуют резкие скачки в карте глубины, которые отмечены эллипсами. Эти скачки связаны с наличием на входных изображениях сильных бликов. Видно, что в результатах предло женного метода они отсутствуют Рис. 3. Пример набора точек, полученных с помощью метода SFF для плоского участка по верхности реального объекта. На рисунках а) и б) можно видеть точки, которые образуют плоскость и большое количество ложных замеров с двух различных ракурсов Рис. 4. На рисунке а) изображены ROC-кривые классификации. Сплошной линией обозна чен предложенный метод, курсивом — метод на основе среднеквадратичного отклонения по окрестности пикселя. На рисунках б) и в) приведен пример результатов фильтрации, на рисунке б) изображены изначальные замеры, а на рисунке в) — результат фильтра ции. На рисунке в) синим обозначены верно классифицированные точки, принадлежащие плоскости, а красным обозначены ошибки классификации Рис. 5. Снимки экрана программы Oxygen Microscope Server. На рисунке a) приведено изображени камня и включений, размеченных в нем. На рисунке б) приведено изображе ние камня, выровненное относительно модели камня, построенной на сканере Унарный потенциал поля отвечает за правдоподобие, т.е. этот потенци ал должен быть тем меньше, чем больше вероятность наблюдать имеющийся набор изображений = {1,..., } при условии некоторой заданной конфи гурации поля. Поэтому для некоторого элемента поля значение унар ного потенциала ( ) должно быть большим при значениях, которые соответствуют нерезким изображениям. Обозначим как вектор значений {,1,...,, } меры резкости в пикселе, который соответствует элементу по ля. Вектор будем называть профилем меры резкости. Тогда предлагается рассчитывать унарный потенциал элемента поля по следующей формуле:
Величина представляет собой дисперсию шума в профиле меры резкости.
Величина ограничивает максимальное значение, которое может принимать потенциал ( ) и является одним из входных параметров алгоритма.
Парный потенциал в формуле (5) отвечает за регуляризацию результи рующей поверхности. Предлагаемая форма парного потенциала способству ет тому, чтобы поверхность была гладкой, но при этом за счет ограничения значения потенциала сверху значением, в некоторых местах поверхности допускаются сильные перепады глубины:
Коэффициент представляет собой квадрат отношения между размером пик селя изображений и величиной шага по фокусу между парой соседних изобра жений в наборе. Использование нормировочного коэффициента позволяет сделать разность ( )2 пропорциональной квадрату Евклидова рассто яния в трехмерном пространстве.
Величина представляет собой индикатор наличия сильной текстуры в окрестности элемента поля и рассчитывается следующим образом. Вычис лим матрицу, элемент (, ) которой равен максимальному значению меры резкости в пикселе (, ) среди всех изображений набора. Затем рассчитаем маску, каждый элемент которой равен 1, если соответствующий пиксель превосходит некоторый порог, и равен 0 в противном случае. После это го полученную таким образом маску предлагается отфильтровать с помощью математической морфологии операцией "открытие"с круглым структурным элементом радиуса. Затем полученную отфильтрованную маску предла гается записать в виде одномерного вектора, каждый элемент которого Boykov Y., Veksler O., Zabih R. Markov Random Fields with Efficient Approximations. Proc. Computer Vision and Pattern Recognition, 1998, pp. 648- является индикатором наличия существенной текстуры в окрестности соот ветствующего элемента поля. За счет такой формы предлагаемый парный потенциал допускает сильные перепады в карте глубины только в областях, где присутствует значительное количество текстуры. Величины и явля ются входными параметрами алгоритма.
Для оптимизации полученного функционала в формуле (5) предлагается использовать метод -expansion 4.
Тогда итоговый алгоритм выглядит следующим образом:
1. Для каждого изображения набора вычисляем меру резкости.
2. По картам меры резкости вычисляем для каждого пикселя изобра жения значение унарного потенциала ( ) с помощью формулы (6), тем самым получая трехмерный массив значений унарного потенциала 3. По картам меры резкости вычисляем карту наличия существенной 4. С помощью алгоритма -expansion осуществляем оптимизацию (5) с парным потенциалом в виде, задаваемом (7).
В третьем разделе приводится анализ разработанного метода и срав нение его с существующими аналогами на реальных данных.
Для оценки качества работы предлагаемого метода и сравнения мето да с существующими аналогами была собрана тестовая база из 27 наборов изображений с микроскопа. В качестве объектов для тестирования исполь зовались полупрозрачные природные минералы. Был разработан специаль ный программный инструмент, позволяющий вручную разметить эталонную карту глубины для набора изображений с микроскопа, с помощью которого были размечены эталонные карты глубины для всех наборов изображений из тестовой базы. Для сравнения результатов работы предложенного метода и существующих аналогов с эталоном использовалась следующая метрика:
где и — это результат оценки и эталонная карта глубины соответ ственно. Данная метрика представляет собой процент пикселей карты глуби ны, отличия от эталона в которых превосходят порог.
Boykov Y., Veksler O., Zabih R. Fast Approximate Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, v.23, n.11, pp. 1222-1239.
Таблица 1. Результаты сравнения предлагаемого метода с существующими аналогами В таблице 1 приведены результаты сравнения предложенного метода с методами Наяра 5 и методом Наира и Стюарта 6, который был дополнен постобработкой карты глубины с помощью медианного и гауссовского филь тров. При проведении сравнения входные параметры всех методов были на строены таким образом, чтобы давать оптимальный результат на собранной базе изображений. Параметр при сравнении был установлен равным двум глубинам резкости микроскопа, для того чтобы оценить процент грубых оши бок в результатах работы всех методов.
Из таблицы 1 видно, что процент грубых ошибок в предлагаемом методе приблизительно в два раза ниже, чем у лучшего из существующих аналогов, что делает его существенно более устойчивым. На рисунке 2 также приведены примеры результатов для визуального сравнения.
В третьей главе описывается предлагаемый метод определения поло жения и ориентации плоского участка поверхности объекта по набору изоб ражений с микроскопа.
В первом разделе дается обзор существующих методов построения плоскости по набору точек в трехмерном пространстве и приводится анализ устойчивости различных методов к ложным замерам.
Во втором разделе приводится схема предлагаемого метода оценки положения и ориентации плоского участка поверхности объекта по набору изображений с микроскопа и приводится описание нового метода обнаруже ния ложных замеров.
Для решения задачи оценки положения и ориентации плоского участка поверхности объекта алгоритм, описанный в прошлой главе, неприменим. За счет разработки специализированного алгоритма для решения этой задачи, который в явном виде учитывает то, что наблюдаемая поверхность являет ся плоской, можно получить оценку плоскости, которая обладает высокой точностью. Для того чтобы произвести оценку положения плоскости в трех мерном пространстве, достаточно трех точек. В случае когда точек больше трех, появляется возможность произвести усреднение, тем самым поднимая 5 Nayar S. K., Y. Nakagawa. Shape from focus, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, v.16, n.8, pp. 824-831.
6 Nair H.N., and Stewart C.V. Robust focus ranging, Proc. Computer Vision and Pattern Recognition, 1992, pp. 309-314.
точность оценивания. Также это позволяет обеспечить методу дополнитель ную устойчивость к ложным данным.
Предлагаемый для решения задачи оценки положения и ориентации плос кого участка поверхности объекта алгоритм выглядит следующим образом:
1. С помощью классического подхода SFF (С. 9) получить набор замеров для точек плоскости в трехмерном пространстве = {,, }, = 2. Произвести отбрасывание ложных замеров в полученном наборе с по мощью специальной процедуры фильтрации.
3. По отфильтрованным данным произвести оценку положения и ориента ции плоского участка поверхности объекта.
4. Произвести оценку надежности полученной оценки положения плоско На рисунке 3 изображен пример набора замеров в трехмерном простран стве, полученных после шага 1 данного алгоритма для реального набора вход ных данных. Видно, что входные данные содержат большое количество лож ных замеров. В сложных случаях количество ложных замеров может дохо дить до 95–97%, тем самым делая невозможным оценку положения плоскости по таким данным даже устойчивыми методами математической статистики.
Существующие методы фильтрации ложных замеров основаны на отбра сывании замеров по порогу на максимальное значение меры резкости либо на максимальное значение среднеквадратичного отклонения цвета в окрест ности пикселя. К сожалению, зачастую такие методы обнаружения ложных замеров не в состоянии обеспечить достаточное качество фильтрации. Для ре шения этой проблемы в работе предлагается алгоритм фильтрации ложных замеров, позволяющий отбросить большую часть ложных данных и сделать оценку плоскости возможной даже для сложных ситуаций. Предлагается схе ма для определения надежности оценки глубины на основе формы профиля меры резкости в пикселе = {1,..., }. На рис. 6 приведены примеры про филей меры резкости для различных областей. Понятно, что профиль, кото рый соответствует достаточно текстурированной, а следовательно, надежной области, имеет один главный пик и, возможно, несколько существенно более слабых пиков (рис. 6 a) и в), в то время как профиль ненадежной области имеет более случайную структуру и несколько сильных пиков, из которых затруднительно выбрать один главный (рис. 6 б).
В связи с тем, что сформулировать четкое правило, которое по профи лю меры резкости решает, надежный он или не надежный, в явном виде Рис. 6. Примеры профилей меры резкости. На рисунке а) изображен надежный профиль.
На рисунке (б) находится пример ненадежного профиля с большим количеством локаль ных максимумов, найти по которому наиболее резкое положение надежно не представляет ся возможным. На в) изображен еще один пример профиля, по которому можно надежно определить положение, несмотря на то что максимальное значение меры резкости в про филе меньше, чем в б) затруднительно, предлагается для этой цели использовать методы машинно го обучения. Для каждого точечного замера положения точки плоскости в пространстве определим набор признаков на основе профиля меры резкости, которые характеризуют поведение профиля меры резкости. Список призна ков приведен в таблице 2. В формулах таблицы вектор = {,..., } представляет собой вектор индексов всех локальных максимумов в профиле меры резкости, упорядоченный по убыванию величины максимумов.
Таблица 2. Список признаков, использованных для классификации профилей меры резко сти на надежные и ненадежные Обозначим функцию, которая вычисляет признаки из таблицы 2 как = (). Тогда итоговый вектор признаков для профиля меры резкости предлагается вычислять следующим образом:
где * обозначает свертку, а (.) — гауссовское ядро свертки.
Для описанного итогового набора признаков автором была собрана и вручную размечена обучающая выборка на основе реальных данных и постро ено решающее правило, которое классифицирует любой замер, полученный с помощью методов SFF, как надежный или ненадежный. Для построения ре шающего правила использовался алгоритм Gentle Ada Boost7. После отбрасы вания ложных замеров в соответствии с решающим правилом по отфильтро ванным данным строится плоскость с помощью адаптивного преобразования Хафа.
В третьем разделе описывается новый метод определения надежности оценки плоскости.
Надо заметить, что с помощью метода, описанного в прошлом разделе, можно построить наилучшую плоскость по абсолютно любому набору вход ных данных. Даже если, например, вся поверхность объекта пересвечена и не имеет видимой текстуры, описанный метод успешно построит по таким дан ным оптимальную плоскость. Это связано с тем, что локальная процедура фильтрации, основанная на наборе признаков (9), не в состоянии отбросить абсолютно все ложные замеры. Для того чтобы решить эту проблему, пред лагается новый метод определения надежности оценки плоскости.
Пусть у нас есть набор точек = {, = 1, } в трехмерном про странстве. Будем считать, что все точки из этого набора представляют собой случайные ошибки измерения. Традиционно для моделирования поведения ошибок измерения используется равномерное распределение, таким образом (), где — это область пространства, в которой расположены точки. В данном случае в качестве можно взять сферу, ограничивающую все точки из. Теперь зафиксируем в пространстве плоскость, которая про ходит через область, и обозначим через 0 множество точек, лежащих от зафиксированной плоскости на расстоянии, не большем некоторого заданно го порога. Тогда понятно, что каждая конкретная точка из принадлежит области 0 с вероятностью ( 0 ) = |0 |/|| и, таким образом, количе ство ложных замеров, попавших в окрестность плоскости, подчиняется бино миальному закону (|0 |/||, ). Тогда, если использовать в качестве основной гипотезы 0 тот факт, что точки из распределены равномерно, а в качестве критической статистики использовать, можно построить тест, проверяющий надежность плоскости, следующим образом. Найдем такое ко личество точек 0, что вероятность того, что 0 точек или более принадле жат зафиксированной окрестности плоскости 0 при условии 0, равна, и положим достаточно малым, например, равным 0.01. Тогда, если количе ство точек, которые попали в окрестность плоскости, превосходит 0, можно утверждать, что с большой вероятностью гипотеза 0 неверна и наблюдае мые точки имеют неравномерное распределение.
Эту идею предлагается применить для оценки надежности плоскости сле дующим образом. После построения итоговой оценки плоскости вычисляется Friedman, J., Hastie, T., Tibshirani, R Additive Logistic Regression: a Statistical View of Boosting, Stanford University Tech. Report, 1998.
количество точек, лежащих на расстоянии, не большем чем половина глу бины резкости от плоскости, и сравниваем это количество точек c 0, которое подсчитано описанным выше методом. Если > 0, то построенная плоскость считается надежной.
В четвертом разделе приводятся результаты анализа предлагаемого метода фильтрации ложных замеров и процедуры проверки надежности оцен ки плоскости.
В первом эксперименте оценивалось качество фильтрации ложных за меров предложенным методом с машинным обучением. Для этого на вруч ную размеченной тренировочной базе, собранной на реальных примерах, бы ли обучены два классификатора. Первый классификатор использовал для классификации замеров на надежные и ненадежные только максимальное значение меры резкости в профиле, а второй классификатор — признаки, описанные в формуле (9). На рис. 4 а) приведены ROC-кривые для обоих классификаторов. Оценка ошибок классификации осуществлялась методом скользящего контроля. По ROC-кривым видно, что при одинаковом уровне ложных срабатываний (false positives) предложенный классификатор обеспе чивает существенно большее количество правильно классифицированных на дежных замеров (true positives). На рисунках 4 б) и в) можно видеть пример работы предложенного алгоритма фильтрации.
Во втором эксперименте оценивалось качество работы предложенного теста для определения надежности плоскости. Для проведения эксперимента использовались обработанные прозрачные природные минералы с крупными плоскими гранями. Было снято несколько наборов фотографий, на которых грани минерала достаточно грязные и детали хотя бы на части их поверх ности различимы под микроскопом. Также было снято некоторое количество наборов фотографий, на которых грань практически не видна. К каждому из полученных наборов фотографий был применен описанный алгоритм постро ения плоскости, и для каждого набора вручную было установлено, удалось ли построить плоскость корректно. После ручной разметки к каждому из наборов был применен алгоритм автоматического определения надежности оценки плоскости.
Ручная классификация Общее количество Ошибки Таблица 3. Во второй колонке приведено общее количество надежно/ненадежно постро енных граней, участвовавших в эксперименте. В третей приведено количество ошибок автоматического определения надежности Статистика, демонстрирующая согласованность результатов ручной раз метки и результатов работы теста на надежность, приведена в таблице 3.
Как можно заметить, предложенный тест успешно обнаруживает ситуации, когда грани на изображениях видны слишком плохо, но при этом иногда он отбрасывает грани, по которым можно построить плоскость надежно.
В четвертой главе описывается интерфейс и функциональность про граммной системы Oxygen Microscope Server, в которую были встроены пред лагаемые алгоритмы, а также описывается программная реализация предло женных методов.
В первом и втором разделах описывается приложение, в которое внедрялись разработанные методы, а также интерфейс и функциональность программной системы Oxygen Microscope Server.
Программный продукт Oxygen Microscope Server предназначен для ана лиза алмазного сырья с помощью микроскопа, выставления включений 8 в алмазном сырье и уточнения модели поверхности алмаза с помощью микро скопа. На алмазообрабатывающих предприятиях продукт Oxygen Microscope Server применяется в рамках следующего цикла:
1. Алмазное сырье поступает на завод, после чего камни проходят стадию предварительной обработки и жестко крепятся на подставку, называе мую холдером (holder );
2. Закрепленные на подставке камни устанавливаются на специальный сканер, с помощью которого строится трехмерная модель поверхности 3. Камни переносятся под микроскоп, подключенный к компьютеру, на котором установлен продукт Oxygen Microscope Server, с помощью ко торого происходит разметка включений внутри камней и уточнение мо дели, построенной с помощью сканера. За счет использования holder модель камня остается зарегистрированной относительно фотографий, полученных с помощью микроскопа;
С помощью предложенного метода построения участка поверхно сти объекта, представимого в виде карты глубины, происходит уточнение модели камня в областях мелких каверн на поверхно сти, которые невозможно построить на сканере из-за физических С помощью разработанного метода оценки положения и ориента ции плоского участка поверхности объекта происходит уточнение модели в области больших плоских граней на поверхности камня, Включениями в алмазе называются различные дефекты/внутренние неоднородности, которые при попадании в ограненный камень существенно снижают его визуальное качество.
через которые происходит моделирование включений в камне. Это позволяет повысить точность расчета преломления в камне и по высить точность моделей включений.
4. Далее, после того как построены модель камня и модели включений внутри него, определяется оптимальный способ огранки камня и он гра На рисунке 5 можно видеть главное окно программного продукта Oxygen Microscope Server в двух различных режимах работы.
В третьем разделе описывается программная реализация разработан ной системы.
Разработанные в рамках диссертации методы были реализованы как часть подсистемы InclEngine. Помимо предложенных методов построения участ ка поверхности объекта, представимого в виде карты глубины, и оценки по ложения и ориентации плоского участка поверхности разработанная система включает в себя функциональность, предназначенную для моделирования включений различных типов внутри алмазного сырья. Суммарный объем ко да подсистемы составляет более 200000 строк кода на языке С++.
Подсистема InclEngine реализована в виде динамически подключаемой библиотеки (DLL). Доступ подсистемы к ресурсам Oxygen Microscope Server, таким как камера, микроскоп, модель камня и список включений, осуществля ется за счет интерфейсов автоматизации, предоставляемых Oxygen Microscope Server. За счет применения принципа инкапсуляции реализации методов, раз работанных в рамках диссертации, полностью изолированы от конкретных интерфейсов Oxygen Microscope Server и работают с ними через классы-посред ники. Благодаря этому разработанные методы могут быть легко повторно использованы в рамках других систем с другим аппаратным обеспечением и другими программными интерфейсами, без изменения кода самих методов.
В заключении представлены основные результаты работы. Основные результаты работы состоят в следующем:
1. На основе проведенного исследования были разработаны и программ но реализованы новые устойчивые алгоритмы моделирования участков, представимых в виде карты глубины, и плоских участков поверхности объекта, позволяющие существенно расширить класс объектов, к кото рым применимы методы построения трехмерных моделей по изображе ниям с микроскопа.
2. Произведен анализ разработанных методов и алгоритмов на реальных данных, который показывает, что предложенные методы позволяют стро ить трехмерные модели объектов точнее, чем существующие аналоги.
3. На базе разработанных алгоритмов реализован программный модуль для построения формы поверхности микрообъектов, позволяющий уско рить и автоматизировать производственный процесс в реальных прак тических приложениях.
Список публикаций 1. Гаганов В. А., Игнатенко А. В. Устойчивое построение трехмерных моде лей объектов по набору изображений с микроскопа // Информационные технологии в проектировании и производстве. 2009. Т. 4. С. 56–64.
2. Гаганов В. А., Игнатенко А. В. Реконструкция плоских объектов по изоб ражениям с микроскопа // Программные продукты и системы. 2009. Т. 3.
С. 78–82.
3. Гаганов В. А., Игнатенко А. В. Трехмерная реконструкция плоских граней прозрачных минералов по набору изображений с микроскопа // Труды конференции Графикон. 2008. С. 227–233.
4. Gaganov V., Ignatenko A. Robust Shape from Focus via Markov Random Fields // Proceedings of Graphicon Conference. 2009. Pp. 74–80.
5. Гаганов В. А., Игнатенко А. В. Трехмерная реконструкция плоских граней прозрачных объектов по набору изображений с микроскопа // Сборник трудов XV Международной конференции студентов аспирантов и молодых ученых «Ломоносов-2008». 2008. С. 58.