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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА Ф-Т ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

. ОД. .. ..... - - " ; ^ ~

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

______________________________________" УДК681.3.513

ЮРКОВЕЦ Дмитрий Иванович

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ КОЛИЧЕСТВЕННОГО МОРФОЛОГИЧЕСКОГО АНАЛИЗА СТРУКТУР ПО ПОЛУТОНОВЫМ ИЗОБРАЖЕНИЯМ

05.13.11- Математическое и программное обеспечение вычислительных ____машин, комплексов и тетей

АВТОРЕФЕРАТ

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

Москва 1998

Работа выполнена на кафедре Автоматизации Систем Вычислительных Комплексов факультета ВМиК МГУ

Научные руководители:

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

доктор геолого-минералогических наук

Официальные оппоненты:

доктор физико-математических наук, ведущий научный сотрудник

кандидат физико-математических наук, старший научный сотрудник

Ведущая организация:

Государственный НИИ Авиационных Систем

Защита состоится 20 марта 1998 г. в 11 часов в ауд. 685 на заседании диссертационного совета Д 053.05.38 при факультете ВМиК МГУ по адрес} 119899, Москва, Воробьевы Горы, МГУ, факультет Вычислительной Математики и Кибернетики.

С диссертационной работой можно ознакомиться в библиотеке факультета ВМиК МГУ

Ю.М.Баяковский В.Н.Соколов

Д.В.Тюкавкин А.Е.Лукьянов

Автореферат разослан 19 февраля 1998 г.

Ученый секретарь диссертационного совета Д 053.05.38 кандидат физико-математических наук,

профессор Н.П.Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы -------------------

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

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

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

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

Цель работы

Целью представленной диссертационной работы являлось:

1. разработка программных средств для

• оценки извилистости поровых каналов с помощью анализа их полутоновых изображений,

• трехмерной реконструкции рельефа поверхности объекта по стереоизображениям,

• выполнения объемного совмещения цифровых моделей сопряженных поверхностей для оценки объемной пористости структуры;

2. создание автоматизированной системы цифровой обработки растровых электронно-микроскопических изображений на основе разработанных программных средств.

Научная новизна работы

• Впервые разработано программное средство для оценки сообщаемое™ и извилистости поровых каналов, представленных на полутоновых изображениях.

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

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

• На основе разработанных программных средств создана новая автоматизированная система цифровой обработки растровых электронно-микроскопических изображений. Данная автоматизированная система позволяет изучать ряд важных морфологических параметров микроструктуры (такие как коэффициент извилистости поровых каналов, объемная пористость и др.), которые не могли быть получены ранее.

Защищаемые положения

На "защиту выносятся следующие защищаемые положения:

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

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

3. Программное средство для объемного совмещения цифровых моделей --------сопряженных рельефов. Предложен новый итерационный "метод нахождения положения наилучшего сопряжения.

4. Автоматизированная система «СТЕРЕКОН» для количественного морфологического анализа микроструктур по растровым электронно-микроскопическим изображениям.

Практическая значимость работы

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

Апробация работы

Основные результаты работы докладывались на Всероссийских конференциях по растровой электронной микроскопии РЭМ-95, РЭМ-96, РЭМ-97. на международной конференции Графикон-97. ежегодной конференции Ломоносовские чтения 95.

Публикации

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

Структура и объем работы

Диссертация состоит из введения, пяти глав основного текста и заключения Объем диссертации - 144 страниц. Библиография включает 91 наименование Диссертация содержит 28 рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

В первой части настоящей главы рассматривается задача оценки коэффициента извилистости поровых каналов. Коэффициент извилистости Ки определяется как отношение длины пористого образца Ь в направлении фильтрации к минимальной длине извилистой линии тока жидкости или газа Ьк в этом образце. Таким образом:

Ки=1Лк (1)

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

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

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

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

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

различными углами. Стереометод является аналогом бинокулярного зрения — человека или животного.---------------------------------------------------------------------------------------------

Методика получения стереоизображений в РЭМ заключается в повторной съемке одного и того же участка поверхности, наклоненного под

разными углами (5-12°) по отношению к электронному зонду. Угол наклона изменяют механически с помощью гониометрического столика.

Для вычисления высот микрорельефа поверхности по РЭМ-стереоизображсниям (при увеличениях 500 раз и выше) используются следующие формулы:

Y — • у — ■ % — ~ (2)

2M cos a ' 2M ' 1M sin a

где X, Y. Z - пространственные координаты микрообъекта; хь х2, уь У: - плоские координаты объекта на левом и правом снимках; М - увеличение РЭМ снимка.

Биологами установлено, что мозг человека или животного обрабатывает стереоизображения за 3 основных этапа:

1. На каждом изображении выявляются какие-либо особенности (например, тени, яркие или цветные пятна и т.п.).

2. Для каждого такого элемента на первом изображении находится соответствующий аналог на втором.

3. Оценивается различие в выбранных парах аналогов. Чем больше различие - тем ближе находится объект к наблюдателю и наоборот.

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

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

Системы стсреообработки разделяются на два основных типа: корреляционные и контурные. В корреляционных в качестве объектов отождествления выступают отдельные пикселы на изображениях. Отождествление осуществляется по максимальному уровню корреляции окрестностей претендентов (рис. 1а). В контурных отождествляются связанные группы пикселов, выделенные по какому-либо признаку. Критерием отождествления является структурное сходство этих групп (например, одинаковое взаимное расположение и ориентация) (рис. 16).

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

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

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

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

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

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

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

кратчайшего канала внутри областей интереса; описания программной реа-7]изаТпнГи результатов'"практического применения метола.---------------- --------------------

б.

Гнс. I. Основные методы стсреообработкн: а - корре.чяционный подход, б - контурный подход.

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

Сегменты, которые от начала до конца пересекают в горизонтальном или вертикальном направлении оцифрованное изображение и удовлетво-

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

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

Среди всех возможных кратчайших линий, для каждой из областей интереса определяется самая короткая, по которой и вычисляется величина коэффициента извилистости.

Для нахождения областей интереса на полутоновых изображениях за основу был взят метод выделения краев по Лапласу. Данный метод осуществляется с помощью вычисления значения двумерной дискретной свертки с(х,у) функции яркости ^(ду) с Лапласианом функции Гаусса ЬоС(х,у).

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

Ян

1

8 ш ;

С =

чс

ш

"Ш'

где

е--«./»>-->

,, если 1 < х < Ы, 1 < у < М

е(х, у) = <

10, для остальных (х,у)

(3)

(4)

(5)

где С - матрица разбиения исходного полутонового изображения, С - результат свертки изображения с Лапласианом функции Гаусса, ст - константа, определяющая чувствительность фильтра к изменениям яркости и зависит от размеров матрицы разбиения исходного изображения, М и N -размеры матрицы разбиения изображения.

Метод Лапласа подразумевает нахождение второй производной функции яркости, при этом краями являются точки ее перехода через ноль. В зависимости от поведения второй производной функции яркости на выделяемых краях проведем разметку ограниченных ими областей. Разметка осуществляется таким образом, чтобы было верно следующее утверждение: пусть области А и Б имеют общую границу, область А отмечена значением ЫА, а область Б - Агб- Если при пересечении границы в направлении из области А в область Б знак второй производной меняется с положи-

\

тельного значения на отрицательное, тогда NA '* Л1/; если знак меняется с 'Птри!(атС1ЬН0ГП~На1Ю70ЖШНСЛЫ1Ы!Т,'ПЮЛ,^^~\Г;;.

Но окончании разметки области, отмеченные наименьшими значениями. будут соответствовать локально более темным участкам изображения Имея в 1зпд\ описанный ранее критерий для нахождения областей интереса. \часткн. помеченные наименьшими значениями, в первую очередь рассматриваются в качестве возможных областей интереса.

Разметка областей рассматривается как процесс маркировки вершин графа, построенного в соответствии со следующими правилами: / Kawe)nf<области А на исходном изображении, выделенной в результате его сегментации метопом Лапласа, соответствует единственная вершина графа сА.

2. Если две области А и В имеют общую границу, то соответствующие им вершины сА, ск соединены ребром. Если А и Б не граничат друг с другом, то соответствующие им вершины сА, Cßребром не соединяются.

3. Если для областей А и Б вторая производная по направлению перпендикулярному к их общей границе и направленная из А в Б меняет знак с отрицательного на положительный, то ребро направлено из вершины < ; в (wpmimy Сц. Если с положительного на отрицательный, то ребро нан/'ачлено tu с/; в с t

После »того выполняется собственно алгоритм маркировки: / Пусть \ LH'КНР ■ \. где У • общее число вершин в графе. 2 ("реон всех ненромаркнрованных вершин в графе найти те, в которые не входит ни поно ребро, ¡ибо те, в которые входят только ребра, ис-х<н>ищне и I промаркированных вершин.

3. Ныбранные вершины промаркировать значением МАРКЕР.

4. МАРКЕР- М. ll'Klü' - !

5. Если в п. 2 вершины не найдены, то переходим к п. 7.

С> ¡'.ели течение MAI'KEI' равно нулю, то завершаем работу алгоритма,

иначе переходи м к п 2 7. Выбрать непромаркированные вершины, в которые входят ребра, идущие из вершин промаркированных на предыдущем шаге. Н. Если таких вершин не найдено, то выбрать вершины графа, из которых выходит наибольшее количество ребер. V Про маркировать выбранные вершины значением МАРКЕР 1 П. А11РКЕР ■ - АIA РКЕР 1 111 /еренти к п. 6.

По окончании маркировки производится выбор областей интереса для дальнейшей обработки. Выбор осуществляется в соответствии со следующим алгоритмом:

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

2. Если в п. 1 сегменты найдены, то закончить работу.

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

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

Чтобы оптимизировать процесс поиска кратчайшей кривой предлагается свести данную операцию к модифицированной операции заполнения с «затравкой». Эта процедура хорошо известна из разделов машинной графики, связанных с визуализацией различных объектов на растровых устройствах. При этом предполагается заполнение одним фиксированным значением всех элементов растра внутри единой замкнутой области. Заполнение начинается с предварительно указанного элемента внутри этой области («затравки»).

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

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

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

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

.?. Если внутри области интереса отсутствуют незаполненные элемеп-Тпы, Шб^абопталгори^Ша Свершается,'иначе повторяются шаги 2-3.

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

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

1. Выбрать элемент с минимальным значением заполнения на нижней границе внутри области интереса в качестве текущего элемента. Если таких элементов несколько (несколько раз достигается минимальное значение), значит, найдено несколько кратчайших траекторий, и для каждой из них необходимо выполнить шаги 2-4. ..

2. Запомнить координаты текущего элемента. Среди 4-х., соседних элементов найти элемент с минимальным значением заполнения.

3. Выбрать этот элемент в качестве текущего.

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

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

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

Программное средство для трехмерной стереореконструкции в рамках корреляционного подхода состоит из следующих основных частей:

1. блока ректификации, предназначенного для компенсации взаимного разворота и смещения изображений;

2. блока отождествления соответствующих элементов на изображениях;

3. блока вычисления высот.

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

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

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

Основой предлагаемого метода ректификации является алгоритм оценки относительного вертикального смещения изображений.

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

где - ширина изображений в пикселах. В этом случае относительное смещение изображений определяется по формуле:

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

На основании вышеизложенных соображений, был построен следующий алгоритм ректификации:

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

2. Для левых фрагментов вычисляется величина относительного вертикального смещения б^.

3. Для правых фрагментов вычисляется.величина относительного вертикального смещения <5>(.

4. Если и» - ширина исходных изображений, то относительное смещение и разворот определяются по формулам (?) и (6) соответственно.

Алгоритм, положенный в основу блока поиска идентичных элементов, работает по иерархической схеме. На первом шаге матрицы исходных изображений уменьшаются до размера 4x4 элемента. Уменьшение размер-

(6)

(7)

2

ности выполняется с помощью усреднения значений яркостей, т.е. если ¡0=0..Ы-] - исходная матрица разбиения. то элементы матрицы, полеченной на первом шаге Кг-{г,,}. >,] = 0..3, вычисляются по формуле:

0':!>У'4-1 (г 4)^/4-1 ^ \ ^ : тп

А^"/16

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

Отождествление выполняется на основании поиска максимума величины корреляции локальных окрестностей пары элементов:

т п

где т,п - размеры окрестностей точек а и Ь по горизонтали и вертикали соответственно. ga(iJ), - уровни яркостей элементов, находящихся в /-ых столбцах иу-ых строках окрестностей а и Ь соответственно, ца,

¡.¡¡, - средние значения яркостей в этих окрестностях.

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

Процесс отождествления выполняется построчно, при этом для каждой строки осуществляется следующая рекурсивная последовательность действий (рис. 2):

1. Если олина хотя бы одной из строк равна 0, то завершить работу.

2. Если длина каждой из строк равна /, то отождествить их элементы и завершить работу.

3. Для каж дого элемента первой строки найти такой элемент второй строки, который, во-первых, имеет относительное смещение не больше с -соп.ч1 элементов, а во-вторых, величина корреляции с его окрестностью максимальна.

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

5. Отождествленная пара разбивает каждую из входных строк на две подстроки. Для подстрок левее только что зафиксированных элементов повторить шаги 1-4. Для подстрок правее только что зафиксированных элементов также повторить шаги 1-4.

Смысл этого алгоритма заключается в поэтапном отождествлении сначала самых «надежных» пар, затем чуть менее надежных, и т.д. до самых «ненадежных»

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

СТРОКА ЛЕВОГО ИЗОБРАЖЕНИЯ СТРОКА ПРАВОГО ИЗОБРАЖЕНИЯ

Максимальная корреляция

Рис. 2. Поиск идентичных элементов на очередных строках изображений

После того, как матрица параллаксов полностью сформирована, выполняется операция интерполирования значений для неотождествленных элементов (точнее элементов, для которых матрица информативности со-

держит значение МИ^ММТ). Пусть необходимо интерполировать значение параллакса для элемента (¡.¡). Это выполняется следующим образом:_____________

/. ("реОи всех посчитанных элементов (к, I) (у которых в матрице информативности записано значение не равное Х11Х_1\!Т), найти тот, который расположен ближе всего к интерполирх'емому элементу, т.е. для которого величина ^(¡-к)--(_/минимальна. Поместить в интерпо-

шруе.иый элемент (¡.¡} значение элемента (к,I) матрицы параллаксов. 2. Если Оля интерполируемого элемента существует несколько равноотстоящих самых близких посчитанных элементов, то выбирается тот, V которого величина ппралпакса минимальна.

На втором этапе процесса поиска идентичных элементов матрицы разбиений исходных изображений трансформируются в матрицы размерности 8\8 по аналогии с тем, как это делалось на 1-м шаге иерархической схемы. После этого создается новая карта информативности, всем элементам которой присваиваются значения МШШТ. Главным отличием от первого этапа является то. что карта параллаксов не создается заново, а строится на основании полученной на предыдущем шаге. Для этого, прежде всего, вес значения матрицы параллаксов умножаются на 2, после чего выполняется операция увеличения размерности до 8x8 элементов. Увеличения размерности матрицы параллаксов выполняется с помощью метода билинейной интерполяции, применяемой при изменении размеров изображений с устранением эффекта ступенчатости.

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

Последующие шаги иерархической схемы (для изображений 16x16. 32x32 и т.д. до К\Ы) выполняются аналогичным образом. Весь процесс отождествления выполняется за 1о£>^Ы шагов. Матрицы параллаксов и информативности. сформированные на последнем шаге считаются результатом работы алгоритма.

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

выборки самых достоверных (в соответствии с матрицей информативности) высот для всех обработанных стереопар.

Четвертая глава посвящена программному средству по объемному совмещению цифровых моделей рельефов сопряженных поверхностей.

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

Обозначим матрицу высот левого сопряженного рельефа ///,. а правого Нк:

\hf-lfi

0.Л1-1

М- 1.ЛГ-1 /

(11)

'а/- 1.ДГ-1 у

где для удобства без потери общности полагаем размеры М, N одинаковыми для обеих сопряженных поверхностей.

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

Дня проведения ректификации один из сопрягаемых рельефов заменяется своим зеркально-отраженным дополнением. Пусть для определенности это будет дополнение правого сопряженного рельефа (см. рис. 3). Таким образом:

//[=С(Я,) =

V 'м-1.лм

(12)

'м-1.0 у

а. б.

Рис. 3. Построение зеркального дополнения рельефа: а - исходный рельеф; б — его зеркально-отраженное дополнение.

Чтобы обеспечить более плотное прилегание рельефов друг к другу

при дальнейшем сопряжении, осуществляется их выравнивание по аппрок----------

симирующей плоскости, параметры которой вычисляются методом наименьших квадратов. Пусть необходимо вычислить параметры аппроксимирующей плоскости для левой сопряженной модели, заданной уравнением : z - А ■ х + В ■ у + С ' (13)

Искомые параметры A.B.C.D отыскиваются из условия минимизации квадратичной функции:

Д{А,В,С) = XEi, ~(A-i + B-j+C)) (14)

<=U j=о

Аналогично осуществляется поиск параметров аппроксимирующей плоскости методом наименьших квадратов для правой сопряженной модели (точнее, для ее зеркально отраженного дополнения).

После того, как вычисляются параметры аппроксимирующей плоскости, производится коррекция матриц высот HL и HRC. Для матрицы HL элементы пересчитываются следующим образом (для HrC аналогично): /,", = - (А-! + B- j + С) (15)

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

Далее производится компенсация взаимного смещения и разворота рельефов друг относительно друга.

Процесс начинается с уменьшения детализации рельефов в раз, где К = const. Каждая из матриц высот IIL и IIr уменьшается в 2К раз по горизонтали и в 2К раз по вертикали, а их значения вычисляются с помощью усреднения высот нескольких соседних элементов.

Для уменьшенных матриц высот выполняется ortepaîow "подгонки". Она осуществляется следующим образом:

1. Присвоить х : = О, V : ~ О

2. Вычислить следующие значения: Dfx-1, у-}), Dfx, у-1), D(x+1, у-1), D(x-/, у), Dfx+l, у), D(x-1, у+1), D(x, у+]), D(x+1, у+1), по формуле

ЛГ-1ЛГ-1 _

, J .I

-ZiX,:,. : :,.,:)! ™

1-1) j-и

3. Пусть D(x ~a, у~Ь) - минимальное среди вычисленных значений. Тогда, если D(x+a, y+b) D(x,y), то присвоить х: ~х +а, у:=у+Ь и перейти к п. 2, иначе, присвоить xc6ew: - х, усдтг:=у и завершить работу.

Алгоритм "подгонки" отыскивает взаимное смещение рельефов перебором. Благодаря тому, что разрешения матриц высот сильно уменьшены. их взаимный сдвиг невелик, что позволяет использовать форсированный поиск положения максимального совпадения. Форсированный поиск подразумевает, что начальное приближение взаимного смещения находится в небольшой локальной окрестности от искомого смещения. Причем эта локальная окрестность содержит единственный минимум весовой функции О (17). Благодаря этому, алгоритм движется в направлении уменьшения весовой функции до тех пор, пока не достигнет ее минимального значения.

По окончании "подгонки" производится операция устранения взаимного разворота по следующему алгоритму:

1. Пусть а: 0.

2. Вычислить значения Ща - Ла), Ща + Ла), по формуле

Я,)(/,Л - НоЦ-~ЧНСЛ)(/.Л

(17)

¡-О О

где На1(а, Е) - матрица, полученная в результате поворота матрицы Е, на угол а.

3. Если Ща - Ла) < Ща + Ла) Ща), то присвоить а а - Л а и перейти к п. 2. Если Ща + А а) < Ща - Ла) Ща), то присвоить аа + Ла и перейти к п. 2. Иначе присвоить ар„:^= а и завершить работу.

В данном алгоритме угол Да выбирается исходя из следующего соотношения:

А а = --(18)

М

Операция поворота матриц высот является одной из важнейших в алгоритме поиска взаимного разворота и выполняется с использованием билинейной интерполяции значений.

По окончании операций «подгонки» и компенсации взаимного разворота алгоритм переходит к следующему шагу иерархической схемы. На этом этапе используются матрицы высот, уменьшенные в 22(К )) раз. В качестве начальных приближений сдвига и разворота используются значения, полученные на предыдущем шаге. Увеличивая постепенно детализацию и выполняя операцию "подгонки", в конечном счете в хсЛ!Ц.,, уа)виг получается от носительный сдвиг рельефов, а в арС1 - их относительный разворот.

На основании полученных значений относительного сдвига матриц высот сопряженных участков рельефов производится их наложение друг на друга. Для этого, прежде всего, матрица Яд1 подвергается операции сдвига на хсоаи, усми. элементов по горизонтали и вертикали соответственно. Далее выполняется операция поворота матрицы на угол ар„.

После этого производится операция поэлементного вычитания. В результате получается новая матрица Е, которая необходима для оценки объ-_________________

емной пористости:

/•■• //;-//: 09)

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

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

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

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

Пятая глава посвящена программной реализации автоматизированной системы обработки РЭМ-изображений. созданной на основе описанных ранее программных средств. Данная глава содержит общее описание системы морфологического анализа РЭМ-изображений «СТЕРЕКОН», ее возможностей, и некоторых специфических особенностей, обусловленных ориентацией на обработку РЭМ-изображений.

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

Для обеспечения наибольшего удобства взаимодействия оператора с ПО. а также максимально эффективного использования аппаратных возможностей ЭВМ, система ориентирована на работу в среде операционных систем Microsoft Windows 95/NT. Хотя созданное ПО в первую очередь предназначается для обработки изображений, полученных в РЭМ в нем имеется возможность работы с другими источниками визуальной информации. В частности, предусмотрена возможность ввода изображений с любого источника телевизионного сигнала, драйвер которого соответствует спецификации MSVideo.

Аппаратной базой для созданной системы явились растровый электронный микроскоп "Hitachi S-800", соединенный с персональной ЭВМ семейства IBM PC. Сопряжение ЭВМ с РЭМ осуществляется с помощью высокоскоростного интерфейса ввода/вывода. Интерфейс предусматривает передачу данных между компьютером и микроскопом, кроме того, через него осуществляется внешнее управление отклоняющей системой РЭМ. В настоящей главе представлено подробное описание того, каким образом осуществляется взаимодействие с РЭМ. В частности рассматриваются алгоритм временной калибровки операции взаимодействия с интерфейсом при работе в многозадачной ОС. Кроме того, приведен алгоритм управления вводом изображения с одновременной предварительной обработкой.

ПО разработано с использованием ООЯП С++ и может рассматриваться как совокупность взаимодействующих объектов, представляющих различные элементы предлагаемой системы по обработке и анализу изображений. Большинство объектов предназначены для организации взаимодействия с внешней по отношению к ПО средой (ОС, устройствами ввода/вывода й т.п.). Часть объектов этого типа являются экземплярами классов. входящих в стандартную библиотеку MFC (Microsoft Foundation Classes) или их производных классов. Разработка функционального наполнения ПО потребовала создания дополнительной библиотеки из почти 100 классов, призванных создать новый уровень абстракции по отношению к программному интерфейсу ОС, а также реализовать различные алгоритмы по обработке и анализу изображений.

В главе подробно рассмотрены наиболее важные из этих классов. В частности дано описание параметризированного класса CRawImage. представляющего матрицу элементов изображения и обеспечивающего выполнение над ним различных действий. Другой важный класс - CBmpImage. Класс предназначен для создания объектов, выполняющих интерфейсную функцию между экземплярами клайса CRawImage и ОС. Класс CConvolver - базовый абстрактный класс для организации эффективного вычисления дискретной двухмерной свертки изображения CRawImage с произвольным

ядром. Объекты данного класса используются, в частности, при проведении сегментации изображения методом^Папласа для вычислении коэффи------------

циента извилистости поровых каналов. Эффективность вычисления свертки повышена за счет перехода из пространственной области в частотную. В связи с этим вводится класс СБре^гит. представляющий комплексный спектр Фурье изображения. Методы класса обеспечивают выполнение быстрых прямых и обратных преобразований Фурье, а также основных операций над спектрами: маскирование, преобразование в действительные значения. произведение, сложение, вычитание и т.д.

Рассматриваются классы С8е§теГа(ог, ССйаппеМпскг, СТоПиоз^ЕяНта^г. предназначенные для сегментации изображения, поиска кратчайшего канала и вычисления коэффициента извилистости поровых каналов. Ректификация изображений реализована в рамках класса СКссиПса1ог. В свою очередь стереореконструкция выполняется методами класса СЮКссогЫгпсюг. Для сопряжения объемных цифровых моделей рельефов используются экземпляры класса ССоп^айг.

В конце главы рассматривается класс СЗЕМБсаппег, который предназначен для реализации взаимодействия с РЭМ.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты работы состоят в следующем: 1 Разработано программное средство для вычисления коэффициента извилистости поровых каналов по полутоновому изображению;

2. Разработано программное средство для трехмерной реконструкции рельефов по стереоизображениям;

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

4. На основе разработанных программных средств создана автоматизированная система морфологического анализа РЭМ-изображений «СТЕРЕ-КОН».

Основные положения диссертации отражены в работах:

1. Соколов В.Н., Лебедев A.A., Юрковец Д.И., и др . // Метод трехмерной реконструкции микрорельефа поверхности твердых тел по их РЭМ-стереоизображениям. Изв. АН Сер. Физ., 1995, т. 59, N2, с. 28-34.

2. Соколов В.Н., Юрковец Д.И., Мельник В.Н., Разгулина О.В., // Новый метод компьютерного анализа микроструктуры твердых тел по их РЭМ изображениям. Тезисы докладов XVI Российской конференции ЭМ'96. Черноголовка. Изд. АК "Богородский Печатник", 1996, с. 32.

3. Соколов В.Н., Юрковец Д.И., Мельник В.Н. // Анализ РЭМ-стереоизображений. Изв. АН Сер. Физ., 1996, т.60, N2, с. 55-64.

4. Соколов В.Н., Юрковец Д.И., Разгулина О.В. // Метод трехмерной реконструкции структуры горных пород по их РЭМ-стереоизображениям. Сб. «Компьютерные аспекты в научных исследованиях и учебном процессе», м:уМГУ, 1996, с. 18-20.

5. Соколов В Н., Юрковец Д.И., Разгулина О.В. // Метод трехмерной реконструкции структуры горных пород по их РЭМ-стереоизображениям. Тез. докладов ежегодной научной конф. «Ломоносовские чтения», М.: МГУ. 1996, с. 103-104.

6. Соколов В.Н., Юрковец Д.И., Разгулина О.В. // Определение коэффициента извилистости поровых каналов с помощью компьютерного анализа РЭМ-изображений. Изв. АН Сер. Физ., 1997, т. 61, N10, с. 1898-1903.

7. Соколов В.Н., Юрковец Д.И., Разгулина О.В., Мельник В.Н. // Использование Фурье-анализа РЭМ-изображений для получения морфологических характеристик микроструктуры. Тезисы X Российского Симпозиума РЭМ'97, Черноголовка, Изд. АК "Богородский Печатник", 1997, с.38.

8. Соколов В.Н.. Юрковец Д.И., Разгулина О.В., Мельник В.Н. // Метод количественного анализа микроструктуры твердых тел по РЭМ-изображениям. Заводская лаборатория, 1997, N9, с. 31-35.

9. Юрковец Д.И. // Алгоритмы для оценки морфологических характеристик микроструктуры по РЭМ-изображениям. Труды международной конференции Graphicon'97, М.: МГУ, 1997, с. 162-169.

10. Sokolov V.N., Mel'nik V.N. , Yurkovets D.I. // Analysis of SEM stereoimages. Proc. IX Russian Symposium on scanning electron microscopy and analytical methods of solids investigations, Chernogolovka, Bogorodskii pechatnik, 1995, pp. 145-146.