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

НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК БЕЛАРУСИ , " • " '" " ИНСТИТУТ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ

УДК 681.3.01

ЛАГУНОВСКИЙ Дмитрий Михайлович

АЛГОРИТМЫ СЕГМЕНТАЦИИ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ АНАЛИЗА ЛОКАЛЬНЫХ СВОЙСТВ

05.13.16 - Применение вычислительной техники, математического моделирования и математических меюдив н научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата технических наук

МИНСК 1998

Работа выполнена в Институте технической кибернетики HAH Беларуси

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

профессор Лбламсйко C.B.

профессор университета г.Упсала (Швеция) Боргефорс Г.

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

доктор технических наук, профессор Садыхов Р.Х.

кандидат технических наук, доцент Краснопрошин В.В.

Оппонирующая организация: Научно-исследовательский институт

электронных вычислительных машин, г.Мин<

Защита состоится "3" марта 1998г. в 14.30 на заседании совета по защите диссерта! Д 01.04.01 при Институте технической кибернетики НАЛ Беларуси по адресу: 220(1 г.Минск, ул.Сурганова, 6.

С диссертацией можно ознакомиться в библиотеке Института технической киберпет) HAH Беларуси

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

Ученый секретарь

совета по защите диссертации

доктор технических наук

П.Н.Бибило

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

Актуальность

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

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

Связь работы с крупными научными программами, темами

Диссертационная работа выполнена в лаборатории обработки и распознавания ¡зображений Института технической кибернетики HAH Ьеларуси. Исследования по еме диссертации проводились в рамках следующих тем:

• "Разработка теоретических основ обработки и распознавания графических зображений в САПР", проблема 1.13.5, тема М.2.27, 1991-1993гг.;

• "Разработка методой распознавания и представления изображений в птеллектуальных системах", проблема 1.13.12, тема "Информационные технологии -О", 1994-1995гг.;

• "Создание теоретических основ разработки, применения и распознавания зображений с использованием методов искусственного интеллекта", тема Интеллект-17", 1996-2000гг.;

• Научно-исследовательские работы, выполненные Институтом технической ибернетики IIAH Беларуси "Разработка программного обеспечения обработки ифровых изображений ИМС" для НИКТП "Белмикросистсмы" НПО "Интеграл", в оответствии с договорами 211/9(1994г.), 211/11(1995г.), 312/5 (1996-1997гг.);

• Научно-исследовательские работы, выполненные Институтом технической кибернетики HAH Беларуси для Научно-исследовательского института точных приборов (г.Москва) в 1992-1994гг.

Цель и задачи исследования

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

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

• быстрого выделения перепадов яркости различного профиля на полутоновом изображении с получением контурного представления;

• быстрого растр-векторного преобразования контурного представления изображения с устранением разрывов контурной линии;

• выделения объектов прямоугольной формы на полутоновом изображении;

• обнаружения объектов цифрового изображения ИМС й оценки их параметров, построения стандартизованного описания объектов ИМС;

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

Научная новизна полученных результатов

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

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

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

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

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

Методы исследования

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

Трактнческая значимость полученных результатов

Результаты диссертационной работы в настоящий момент используются в грикладных системах обработки изображений. Алгоритмы и программный комплекс говышения качества полутоновых изображений земной поверхности и их еомегрических преобразований внедрены н используются в НИИ точных приборов г. Москва) для обработки реальных изображений земной поверхности. Алгоритмы ■бработки изображений ИМС и разработанный на их основе программный комплекс :спользуются в НИКТП "Белмикросистемы" НПО "Интеграл" для получеши эскиза опологии ИМС на основе полутоновых изображений их слоев. Алгоритм выделения бластей с заданной степенью однородности включен в систему обработки осмических снимков земной поверхности, разработанную в Центре по анализу зображений (г. Упсала, Швеция).

Экономическая значимость полученных результатов

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

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

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

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

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

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

• модифицированный быстрый алгоритм выделения перепадов яркосп различного профиля на зашумлениом полутоновом изображении с получениек контурного представления;

• алгоритм быстрого растр-векторного преобразования контурног< изображения и устранения разрывов контурной линии;

• алгоритм выделения объектов прямоугольной формы на полутонопо;! изображении;

• методика восстановления параметров объектов ИМС на основе цифровой изображения и их стандартизации;

• алгоритм выделения областей с заданной однородностью на многоканальны: цифровых изображениях земной поверхности;

Личный вклад соискателя

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

Апробация результатов диссертации

Основные положения диссертационной работы докладывались и обсуждал ис на 2, 3 и 4-й Международных конференциях "Распознавание образов и обработк;

изображений" (Минск, 1993г., 1995г., 1997г.), на Международных конференциях "Visual Communications and Image Processing '94" (г. Чикаго, США, 1994г.), "Visual Communications and Image Processing '95" (Тайбэй, Тайвань, май 1995г.), 2 и 3-й Международных конференциях "Applications of Computer Systems" (г. Щецин, Польша, 1995г., 1996г.), 4-й Международной конференции "Computer Graphics and Image Processing" (г. Мачочице, Польша, 1996г.), Международном симпозиуме "Machine Vision Applications" (г. Токио, Япония, 1996г.), "Remote sensing in agriculture" (г.Иокиоиннен, Финляндия, 1996г.), 7-й Международной конференции "Computer Analysis of Images and Pattcrns" (г.Киль, Германия, 1997г.), Белорусской научно-технической выставке В1МТЕХ'97 (г.Хайдарабад, Индия, 1997г.).

Опублнкованность результатов

По материалам проведенных исследований опубликовано 18 научных работ. Из них: 1 статья в международном журнале, 8 статей в трудах международных конференций, 2 брошюры, 5 тезисов докладов на конференциях СНГ, 2 статьи в сборниках Института технической кибернетики HAII Беларуси.

Структура н объём диссертации

Диссертация состоит из введения, четырех глав и выводов, изложенных на 119 страницах, включая 70 иллюстраций, размещенных на 29 страницах. Список литературы насчитывает 164 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

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

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

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

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

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

Рис.1. Бинарные фрагменты и соответствующие им направления перепада яркости Полученное направление перепада яркости присваивается анализируемому пикселю. Если бинарному фрагменту соответствует значение НЕ_КРАЙ, пиксель

НЕ.КРАЙ

НЕ_КРЛЙ

НЕ_КРАЙ

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

Вычисление величины перепада яркости. Величина перепада яркости Я в пикселе с координатами (¡¿) изображения и оценивалась с помощью выражения &л = |иц иц+1|+ |и*,о-им+1|.

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

Определение контурной линии проводится путем проверки следующих условий:

• величина перепада яркости в пикселе должна быть локальным максимумом в направлении, перпендикулярном направлению перепада яркости в пикселе;

• различие между направлением перепада яркости в текущем пикселе и в предыдущем и в последующем пикселях вдоль линии контура должно быть меньше заданной пороговой величины (в проводимых исследованиях она равнялась 45°);

• значение величины перепада яркости в пикселе должно быть больше заданного минимального значения (для удаления малоконтрастных перепадов).

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

Таблица 1

Умножений/ делений Сложений/ вычитаний Сравнений

Свертка с 6 масками 5x5 150 144 9

Вычисление проекций градиента (2 маски 5x3 и 3x5) 33 28 3

Предлагаемый алгоритм - 4 42

Выделение прямых линий. Разработанный алгоритм выделения прямых линий состоит из следующих этапов:

1. Выделение линейных примитивов (ЛП). Контурная линия представляется в виде набора ЛП. Выделение линейных примитивов производится путем построения описания всех ЛГ1 на основе анализа контурной линии, в процессе которого

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

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

Линейные примитивы

Рнс.2. Построение описания ЛП

3. Устранение разрывов. Для снижения фрагментации прямых, обусловленной шумовыми разрывами контурной линии, производится операция устранения разрывов, базирующаяся на последовательном применении функции слияния прямых с различными значениями параметров. Основой функции является замена двух прямых 1-2 и 3-4 одной прямой 1-4 (гипотетической прямой), если сумма их отклонений от нее (рис.3.) не превосходит некоторой пороговой величины Т 0)1+О2<1)

Рис. 3. Устранение разрывов

Для быстрого поиска прямой-кандидата 3-4 для исходной прямой 1-2 используется последовательный отбор по ряду признаков, организованный таким образом, чтобы минимизировать суммарное время выполнения. Описание признаков, последовательности отбора и изменения параметров функции приведены в тексте диссертации.

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

Быстрый предварительный поиск и группировка параллельных линий. Для быстрого определения пар параллельных линий, которые являются противолежащими сторонами прямоугольника, отрезок преобразуется в точку с координатами Э, Ь, Б, где Б - наклон линии, Ь - длина и О - расстояние от серединного перпендикуляра до начала координат. Это позволяет легко обнаружить все пары противолежащих параллельных линий на изображении. Для определения того, какие из них формируют четырехугольник, выдвигается предварительная гипотеза на основе выделенных параллельных линий.

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

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

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

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

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

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

а) б)

Рис. 4. Обработка изображений металлических проводников: а - исходное изображение, б - результат обработки

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

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

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

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

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

Каждая из разработанных технологий обработки изображений ИМС сопровождается в тексте диссертации описанием программ, а также результатами

б) в)

Рис. 5. Обработка изображений металлических проводников: а - исходное изображение, б - С лой!, в -Слой2

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

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

1=)

а)

б)

Рис.6. Результат выделения прямоугольников: а - исходное полутоновое изображение, б- выделенные прямоугольники

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

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

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

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

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

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

За алгоритмом релаксации следуют несколько стадий фильтрации. Первая из «к - удаление "точек роста", которые были помещены в области неоднородной фкости. Следующий шаг фильтрации - бинарная фильтрация, предназначенная для /даления одиночных шумовых пикселей и сглаживания границ полей. Последний лаг — удаление "ошибочно распознанных" полей, если их форма сильно искажена шбо оно сформировано несколькими соединенными полями. Приблизительный шапазон значений площади сельскохозяйственных полей известен априори. Если эбласть не попадает в границы такого диапазона, являясь слишком малой либо фезмерно большой, она удаляется из рассмотрения. Большинство "ошибочно распознанных" полей удаляется благодаря именно этой операции. Результат обработки приведен на рис.7.

Рнс.7. Выделение сельскохозяйственных полей: а - исходное изображение, б -результат выделения

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

ЗАКЛЮЧЕНИЕ

Результаты, полученные в диссертации, можно сформулировать следующим |бразом:

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

а)

б)

сложности, так как это позволит повысить скорость обработки и расширить область применения алгоритмов обработки изображений.

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

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

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

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

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

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

Научная значимость и новизна результатов подтверждается в 18 опубликованных работах по теме диссертации. Кроме того, результаты диссертационной работы были внедрены н НИИ точных приборов (г.Москва), а также в системе обработки изображений ИМС, используемой в НИКТП "Белмикросистемы" НПО "Интеграл" (г.Минск).

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Лбламейко С., Лагуновский Д. Выделение контуров объектов полутоновых изображений на основе локальной бинаризации: Тез. докл. 2-й научн.-техн. конф. СНГ "Распознавание образов и анализ изображений",- Минск, 1993,- С.193-195.

2. Лбламейко С., Лагуновский Д. Алгоритм поворота цифрового изображения вокруг произвольной точки: Тез. докл. 2-й научн.-техн. конф. СНГ "Распознавание образов и анализ изображений".- Минск.- 1993.- С.196-198.

3. Лбламейко С., Лебедев В., Лагуновский Д. Автоматический анализ и контроль изображений.- Минск: Ин-т техн. кибернетики АНБ, 1993.- 103с.

4. Ablameyko S.,' Lagunovsky D. Aerial images: from straight lines to rectangles, SPIE Proceedings on Visual Communication and Image Processing, vol.2308, 1994, pp.20402048.

5. Ablameyko S., Lagunovsky D. Rectangle-shaped object detection in aerial images, SPIE Proceedings on Visual Communication and Image Processing, vol.2501, 1995, pp. 15661574.

6. Ablameyko S., Lagunovsky D. New possibilities of thresholding in edge detection// Автоматизация обработки и распознавания изображений,- Минск: Ин-т техн. кибернетики АНБ, 1995.- С.173-177.

7. Lagunovsky D. Straight line extraction by clustering// Автоматизация обработан и распознавания изображений.- Минск: Ин-т техн. кибернетики АНБ, 1995.-С.178-183.

8. Lagunovsky D. Fast rectangle detection algorithm: Тез. докл. 3-й Междунар. конф. "Распознавание образов и анализ изображений",- Минск, 1995.- Т.З.- С.99-104.

9. Лагуновский Д., Абламейко С., Кутас М., Белоус А. Построение топологии интегральных схем по цифровым изображениям: Тез. докл. 3-й Междунар. конф. "Распознавание образов и анализ изображений",- Минск, 1995,- Т.2,- С.176-180.

10. Lagunovsky D., Ablameyko S., Kutas M. Extraction of integrated circuit topology from digital image, Proc. of the 2nd Int.Conf." Application of computer systems", Szczecin, Poland, 1995, pp.197-201.

11. Lagunovsky D., Ablameyko S. Fast straight line extraction in aerial images, Pattern Recognition and Image Analysis, vol.6., 1996, pp. 627-633.

12. Lagunovsky D. Detection of agricultural fields in remote sensed images, Report of Center for Image Analysis, Uppsala, Sweden, No21.,1996, 15p.

13. Lagunovsky D., Pettersson A., Walter F. Detection of agricultural fields in satellite images, Reports of Finnish Geodesic Institute, No 96:4, 1996, pp. 63-67.

14. Lagunovsky D., Ablameyko S., Kutas M. Extraction of Topological Features of Integrated Circuit From Grey-Scale Image, Proc. International Workshop on Machine Vision Applications, Tokyo, Japan, 1996, pp. 271-274.

15. Lagunovsky D., Borgefors G. Detection of agricultural fields in multispectral satellite images, Proc. of the 3rd Int.Conf. "Application of computer systems", Szczecin, Poland, 1996, pp. 43-47.

16. Lagunovsky D., Borgefors G., Walter F., Petterson A. Extraction of homogenous areas in multispectral images, Proc. of 4th Int.Conf. "Patlern recognition and Information Processing", Minsk, Belarus, 1997, pp. 103-108.

17. Lagunovsky D., Ablameyko S. Fast line and rectangle detection by clustering and grouping, Lecture Notes in Computer Sciences, Vol.1296, Springer, 1997, pp.503-510.

18. Lagunovsky D., Ablameyko S. A system for topology extraction from integrated circuit image, Proc. of Belarussian scientific and technical exhibition BIMTEX'97, Hyderabad, India, 1997, pp. 74-77.

РЕЗЮМЕ

диссертационной работы Лагуновского Дмитрия Михайловича "Алгоритмы сегментации полутоновых изображений на основе анализа локальных свойств"

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

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

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

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

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

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

РЭЗЮМЕ

дыссергацыйнай працы Лагуноускага Дзмпрыя М^хайлав1ча

"Алгарытмы сегментацьн паутонавых вщарысау шляхам аналЬа лакальных

уласхцвасцей"

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

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

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

Распрацаваны алгарытм растр-вектарнага пераутварэння, ям дазваляе атрымаць значны выигрыш у часе апрацоум; распрацаваны алгарытм распазнавання аб'ектау прамавугодьнай формы, яю мае высокую вышчальную эфектыунасць, дасягнутую за кошт мипм1зацьй колькасщ аперацый пошука прамых для фарм1равання нрамавуголынкау;

Распрацаваны алгарытм выдзялсння абласцей дадзенай ступет аднароднасщ на шматкапальных л1чбавых вщарысах зямной паверхш, ям адрозшваецца высокай ступенью ¡мавернасш атрышпваемых вышкау, дасягнутай за кошт распрацаванага алгарытма раздзельнай апрацоум вщарысау, што адпавядаюць розным каналам, а таксама за кошт методыю аб'яднання атрыманай шфармацьп у адным вщарысе.

Вышга дысертацыйнай працы зараз выкарыстоуваюцца у астэмах апрацоую вщарысау 1 могуць таксама быць выкарыстаны 1 у ¡ншых сютэмах.

SUMMARY

of the thesis "Algorithms of grey-scale image segmentation on the basis of the local property analysis" by Lagunovsky Dmitry Mikhailovich

Keywords: grey-scale image, multichannel image, pixel, image segmentation, edge detection, raster-to-vector transform, image processing.

The dissertation is devoted to fast object extraction in the image as well as automated processing of integrated circuit (1C) images and remote sensed images. The aim of work is development and application of segmentation algorithms for grey-scale images, which have high processing speed and suitable quality of result.

Fast edge detection algorithm for different edge profiles in the grey-scalc image is characterised by smaller computational complexity as well as opportunity of preliminary detection of edge pixels;

Algorithm of raster-to-vector transform allows to achieve an essential reduction of computational time; algorithm of rectangle-shaped object detection has high computing efficiency, achieved by the minimisation of amount of search operations in line search procedure;

Algorithm of extraction of areas with a given degree of homogeneity in multichannel remote sensed image has high reliability caused by the developed algorithm of separate channel processing of the images and by technique of joining of the obtained information in one image.

The results of thesis are already implemented in practise and can be used in different image processing systems to be developed.