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

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

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

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

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

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

Специальность 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.