Методы анализа формы изображений на основе непрерывного гранично-скелетного представления тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Рейер, Иван Александрович

• Рейер, Иван Александрович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Рейер, Иван Александрович

ВВЕДЕНИЕ.

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

1.1. Задача анализа формы изображений.

1.2. Граничные представления формы изображений.

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

1.4. Выводы.

ГЛАВА 2. НЕПРЕРЫВНОЕ ГРАНИЧНО-СКЕЛЕТНОЕ ПРЕДСТАВЛЕНИЕ ИЗОБРАЖЕНИЯ С КОНТРОЛИРУЕМОЙ ТОЧНОСТЬЮ.

2.1. Точность непрерывного гранично-скелетного представления.

2.2. Скелет области с кусочно-гладкой границей и скелетный граф.

2.3. Скелет полигональной области.

2.4. Аппроксимирующая полигональная область минимального периметра.

2.5. Базовый скелет полигональной области и его свойства.

2. б. Структура данных для реализации непрерывного гранично-скелетного представления.

2.7. Ачгоритм построения базового скелета полигональной области.

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

2.9. Выводы.

ГЛАВА 3. ШТРИХОВАЯ СЕГМЕНТАЦИЯ ИЗОБРАЖЕНИЯ.

3.1. Задача штриховой сегментации с учетом гладкости границы.

3.2. Задача штриховой сегментации с точки зрения непрерывного гранично-скелетного представления.

3.3. Определение типа соединения штрихов.

3.4. Алгоритм штриховой сегментации с учетом локальных свойств границы.

3.5. Применение алгоритма штриховой сегментации к прикладным задачам.

3.6. Выводы.

ГЛАВА 4. СРАВНЕНИЕ ФОРМЫ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ГОМЕОМОРФНОГО ПРЕОБРАЗОВАНИЯ.

4.1. Анализ формы на основе сравнения контуров объектов.

4.2. Построение гомеоморфного отображения.

4.3. Вычисление механической работы "элементарных " деформаций.

4.4. Вычисление минимальной работы трансформации.904.5. Пример сравнения контуров.

4.6. Применение сравнения контуров к прикладным задачам.

4.6.1 Задача распознавания печатных букв.

4.6.2 Задача идентификации вертолета по силуэту корпуса.

4.6.3 Задача распознавания лиц по линии профиля.

4.7. Выводы.

Введение диссертации (часть автореферата) на тему «Методы анализа формы изображений на основе непрерывного гранично-скелетного представления»

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

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

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

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

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

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

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

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

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

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

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

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

Решение задачи основывается на следующем подходе:

1) дискретно-непрерывное преобразование бинарного изображения в непрерывное гранично-скелетное представление. Исходное дискретное изображение вначале аппроксимируется непрерывным бинарным образом, т.е. некоторой фигурой, имеющей непрерывную границу. Эта аппроксимация может быть осуществлена неоднозначно в пределах точности, определяемой разрешающей способностью дискретного изображения. При аппроксимации границы дискретного образа непрерывной линией кривизна этой линии может очень сильно меняться при сохранении в нужных пределах точности аппроксимации границы. Это приводит к тому, что получаемые скелеты для непрерывных образов с близкой границей сильно различаются в смысле их топологической структуры. Для того чтобы выделить общие существенные структурные свойства всего множества таких скелетов, в работе вводится понятие "скелетного ядра" - множества точек, входящих в окрестность скелета любого непрерывного объекта, аппроксимирующего с заданной точностью исходный дискретный образ. В скелете каждого аппроксимирующего непрерывного объекта можно выделить так называемый «базовый скелет» - подмножество, аппроксимирующее с заданной точностью скелетное ядро. В работе приводится метод построения базового скелета для аппроксимирующей полигональной области. Таким образом, дискретно-непрерывное преобразование осуществляется по следующей схеме: граница растрового бинарного изображения аппроксимируется многоугольниками минимального периметра; строится непрерывный скелет полученной многоугольной фигуры; в полученном непрерывном скелете выделяется "базовый скелет".

2) сегментация скелета на отдельные структурные элементы (штрихи) с учетом гладкости и кривизны сопряженных элементов границы;

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

Новые научные результаты, выносимые на защиту:

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Рейер, Иван Александрович

4.7. Выводы

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

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

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

Заключение

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Рейер, Иван Александрович, 2004 год

1. Абламейко С.В., Лагуновский Д.М. Обработка изображений. Технология, методы, применение. Минск. Амалфея, 2000.

2. Буренков Д.С., Храпов П.В. Физическая модель гладкой трансформации контуров // Труды межд. конф. Трафикон-2001", Нижний Новгород, 2001. С. 199-202.

3. Введение в контурный анализ и его приложения к обработке изображений. Под ред. Фурмана Я.А. -М.: ФИЗМАТЛИТ, 2002.

4. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 2. М.: Наука, 1989. С. 5-72.

5. Иванов Д., Кузьмин Е. Эффективный алгоритм построения остова растрового изображения//Труды межд. конф. "Графикон-98", Москва, 1998. С. 65-68.

6. Катыс Г.П. Обработка визуальной информации. М.: Машиностроение, 1990.

7. Лагно Д., Соболев А. Модифицированные алгоритмы Форчуна и Ли скелетизации многоугольной фигуры // Труды межд. конф. "Графикон-2001", Нижний Новгород, 2001. С. 120-125.

8. Местецкий Л.М. Непрерывный скелет бинарного растрового изображения // Труды межд. конф. "Графикон-98", Москва, 1998.

9. Местецкий Л.М., Рейер И.А. Поиск ключевых слов в рукописном контексте. Математические методы распознавания образов // Тезисы докладов 9-й Всероссийской конференции (ММРО-9), Москва, 1999, С. 213-215.

10. Местецкий Л.М., Рейер И.А. Распознавание формы растровых бинарных изображений плоских фигур с использованием морфинга контуров границы // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2000, С. 111-112.

11. Местецкий JI.M., Рейер И. А. Распознавание формы растровых бинарных изображений плоских фигур с использованием морфинга контуров границы // Искусственный интеллект. Журнал НАН Украины, 2000, №2, С. 401-406.

12. Местецкий JI.M., Рейер И.А. Построение скелета области с кусочно-гладкой границей на основе полигональной аппроксимации // Доклады X Всероссийской конференции "Математические методы распознавания образов" (ММРО-Ю), Москва, 2001, С. 252-256.

13. Местецкий JI.M., Рейер И.А. Программное обеспечение для работы с непрерывнымгранично-скелетным представлением дискретных изображений // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2002, С. 137-138.

14. Местецкий JI.M., Рейер И.А. Непрерывное скелетное представление изображения с контролируемой точностью // Труды 13-й международной конференции по компьютерной графике и машинному зрению "Графикон-2003", Москва, 2003, С. 246-249.

15. Местецкий JI.M., Рейер И.А., Седерберг Т.У. Анализ рукописного текста на основенепрерывного гранично-скелетного представления // Искусственный интеллект. Журнал НАН Украины, 2002, №2, С. 501-509.

16. Петровцева М.А., Рейер И.А. Язык гранично-скелетного представления бинарных изображений // Труды 13-й международной конференции по компьютерной графике и машинному зрению "Графикон-2003", Москва, 2003, С. 228-234.

17. Прэтт У. Цифровая обработка изображений. Кн. 1,2.- М.: Мир, 1982.

18. Рейер И.А. Сегментация штрихов и их соединений при распознавании рукописного текста // Труды 9-й международной конференции по компьютерной графике и машинному зрению "Графикон-99", Москва, 1999, С. 151-155.

19. Рейер И.А. Распознавание формы объектов с использованием морфинга контуров границы // Математические методы распознавания образов. Тезисы докладов 9-й Всероссийской конференции (ММРО-9), Москва, 1999, С. 222-223.

20. Рейер И.А. Сравнение формы объектов с использованием морфинга контуров ^ границы // Труды 10-й международной конференции по компьютерной графике имашинному зрению "Графикон-2000", Москва, 2000, С. 179-180.

21. Старовойтов В.В. Локальные геометрические методы цифровой обработки и анализа изображений.- Минск: Институт технической кибернетики НАН Беларуси, 1997.

22. Ту Д., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

23. Фор А. Восприятие и распознавание образов. М.: Машиностроение, 1989.

24. Albano A. Representation of digitized contours in terms of conic arcs and straight-line segments // Comput. Gr. and Image Proc. 1974. - Vol. 3, No. 1. - P. 23-33.

25. Arcelli C., Sannity di Baja G. A width-independent fast thinning algorithm // IEEE Trans,on PAMI. 1985. - Vol. 7, No. 4. - P. 463-474.

26. Attali D., Sannity di Baja G., and Thiel E. Pruning discrete and semicontinuous skeletons // Proc. of 8th ЮАР, San Remo, September 1995.

27. Badi'i F., Peikari B. Functional approximation of planar curves via adaptive segmentation // Int. J. Syst. Sci. 1982. - Vol. 13, No. 6. - P. 667-674.30