Развитие и применение математических методов в задачах автоматизации обработки дискретных изображений

Актуальность темы

диссертации. Во многих автоматизированных технических системах, в системах управления технологическими процессами, системах проектирования объектов имеют дело с графическими представлениями реальных объектов /2, 15, 37, 44, 46, 48, 56, 59, 110, 111/. Характерными примерами являются: представление плана и профиля железнодорожных узлов, станций, участков движения поездов/1, 14, 22, 26/- автоматизированные системы резки плоских материалов /48, 56, 110, 111/, которые могут быть использованы в машиностроении (при изготовлении металлических деталей автомобильного, железнодорожного, воздушного транспорта), в легкой промышленности (при проектировании и изготовлении лекал одежды, обуви), в сервисных предприятиях (для производства изделий с узорами, орнаментом, изделий гравировки). Объектами исследования в таких системах являются контурные бинарные рисунки (начерченные от руки, технические чертежи, фотоснимки и т. д.). Процесс использования графических объектов в этих системах можно разбить на три этапа.

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

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

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

В существующих системах проектирования и изготовления макетов изображений ввод рисунка происходит в основном при помощи дигитайзеров при активном участии оператора /45, 35, 36, 37, 48/. В современных дизайнерских системах рисунки подготавливают «вручную» в мощных графических редакторах /34/. Это, во-первых, резко снижает степень автоматизации системы в целом, что отражается на производительности систем, во-вторых, из-за небольшого числа считываемых точек, теряется точность изготовления изделий. Поэтому для создания автономной (независимой от мощных графических редакторов) системы автоматического изготовления изделий по контурным рисункам необходимо, во-первых, для ввода рисунков в компьютер использовать скоростные устройства типа сканера, ПЗС-камеры /110, 111/, во-вторых, создать комплекс программ автоматической обработки рисунка (этапы 2 и 3) к технологической подготовке изготовления изделия.

Для разработки такого комплекса программ необходимо приспособить, усовершенствовать известные, разработать новые эффективные методы и алгоритмы обработки бинарных контурных рисунков. В теории обработки изображений и распознавания образов существуют множество методов предварительной обработки рисунков. Одни из них носят универсальный характер и, следовательно, не эффективны при обработке специфического класса бинарных контурных растровых рисунков, другие нельзя применить к таким рисункам без модификации и усовершенствования. Кроме того, необходимы эффективные методы восстановления исходной кривой по растровому образу аппроксимацией простыми непрерывными линиями, в частности, линейно-круговой аппроксимацией. Последнее обстоятельство связано с тем, что большинство станков с ЧПУ «умеют» резать по прямой и дуге окружности /2, 46, 48, 56/.

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

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

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

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

Для реализации этой цели ставятся следующие задачи.

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

2. Развитие известных численных методов и разработка новых алгоритмов аппроксимации растровых кривых.

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

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

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

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

Научная новизна работы состоит в следующем.

1. Для бинарных контурных растровых рисунков:

— разработаны методы улучшения дискретизации контура, выделения угловых точек;

— усовершенствован метод сглаживания границ контура;

— модернизированы алгоритмы обхода границ контуров, утончение контура.

2. При анализе известных методов линейной и круговой аппроксимации методом наименьших квадратов:

— получена формула для коэффициента прямой линии при аппроксимации МНК с критерием минимума суммы квадратов расстояний от точек до прямой;

— доказана теорема о линеаризации задачи круговой аппроксимации МНК;

— в частном случае получен прямой метод вычисления параметров окружности.

3. Разработан новый метод деления пополам при линейно-круговой сегментации растровых контуров, основанный на новой идее.

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

5. Разработан комплекс программ автоматизации технологической подготовки рисунка к лазерной резке на станках с ЧПУ.

Практическая ценность. Результаты диссертации могут быть применены:

— при расчетах планов и профилей сортировочных горок;

— в машиностроении (для изготовления металлических деталей автомобильного, железнодорожного транспорта);

— в легкой промышленности (при проектировании и изготовлении лекал одежды, обуви).

— в сервисных предприятиях (для производства изделий с узорами, орнаментом, изделий гравировки);

— в системах обработки изображений и распознавания образов.

Реализация основных результатов работы. Результаты диссертации применены в автоматизированной системе управления лазерным раскройным комплексом «Узор», разработанной в ЮРГУЭС.

Эти комплексы внедрены в научно-производственной фирме «ОПТЭКС» при МГТУ им. Баумана, на предприятиях ОАО «РОСБЫТСОЮЗ» (МБОН РСФСР).

Система «Узор» демонстрировалась на ВДНХ СССР. Коллектив разработчиков награжден серебряной медалью выставки «Научно-техническое творчество молодежи» .

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

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

— на семинаре в ВЦ РГУ;

— на семинаре кафедры геометрии РГУ;

— на научно-практических конференциях ЮРГУЭС (1990 — 2001 г. г.).

— на международной научно-технической конференции «Новые материалы и технологии на рубеже веков», ПТУ, Пенза, 2000 г.;

— на Первом всероссийском симпозиуме по прикладной и промышленной математике (осенняя сессия), Сочи, декабрь 2001 г.;

— на межвузовской научно-технической конференции «Управление в технических, социально-экономических и медико-биологических системах», ЮР-ГТУ, Новочеркасск, 2001 г.;

— на IV всероссийской научно-технической конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», ТРТУ, июль 1998 г.;

— на III международной научно-технической конференции «Наука-сервису», государственная академия сферы быта и услуг (ГАСБУ), 27−30 мая 1998 г.;

— на международной научно-технической конференции «Математика в индустрии», ТГПИ, июнь — июль 1998 г.;

— на Втором всероссийском симпозиуме по прикладной и промышленной математике (зимняя сессия), Йошкар-Ола, декабрь. 2001 г.;

— на международной научно-технической конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики», НИИ ПМА КБНЦ РАН, Нальчик, декабрь 2001 г.;

— на межвузовской научно-технической конференции «Управление в технических, социально-экономических и медико-биологических системах», ЮР-ГТУ, Новочеркасск, апрель 2002 г.

Публикации. Основные результаты диссертации опубликованы в 16 печатных работах, 10 из них без соавторов.

Структура диссертации. Диссертация состоит из введения, 4 глав, заключения, 121 наименования библиографических источников, 3 приложений. Материалы изложены на 155 стр., содержат 42 рисунка.

Выводы четвертой главы.

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

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

Впервые получены следующие результаты:

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

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

3. На основе теории в-линий удалось полностью математически решить практическую задачу устранения зазора при резке лазерным лучом.

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

ЗАКЛЮЧЕНИЕ

Основные результаты работы.

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

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

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

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

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

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

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

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

Поставленная задача устранения зазора является новой. В теории е-линий зазор рассматривается как е-полоса вокруг кривой, также вводятся понятия е-линии контура, 8-сводимости контуров, отношение похожести контуров. В теории выведены уравнения е-линий, формулы длины, кривизны е-линий. Доказана теорема о регулярности е-линий для контуров класса С2, теоремы о похожих контурах в различных классах контуров. На основе теории е-линий удалось полностью математически решить практическую задачу устранения зазора при резке лазерным лучом. Алгоритмы построения е-линий позволяют автоматизировать процесс технологической подготовки резки по £-линиям, состоящим из отрезков и дуг окружностей.

5. Разработан комплекс программ, реализующих алгоритмы и методы рассмотренные в диссертации. Комплекс программ апробирован на реальном рисунке и использован в автоматизированной системе лазерной резки плоских изделий (из дерева, пластмассы, металла) «Узор», внедренной в производство.

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

Общая оценка полученных результатов.

Результаты п. 1 имеют различную значимость. Наиболее значимыми являются: 1) метод сглаживания границ контура, поскольку в такой постановке задача сглаживания, не решалась- 2) метод выделения угловых точек, так как впервые эта задача решалась при помощи аппроксимации- 3) решение экстремальной задачи улучшения дискретизации контура вероятностным методом. Частные значения имеют решения остальных задач, так как в них модернизированы известные алгоритмы, хотя модернизация приводит только к улучшению их характеристик.

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

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

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

Теоретическая значимость. Теоретическое значение имеют: 1) сравнительный анализ между различными видами МНК- 2) новые формулы для коэффициентов аппроксимирующих прямой и окружности- 3) теорема 3.1, устанавливающая эквивалентность двух видов постановки задачи круговой аппроксимации МНК, которая позволяет линеаризовать нелинейную задачу в общей постановке. Особое теоретическое значение имеет теория s-линий, которая является теоретической базой решения практической задачи устранения зазора. Самостоятельное теоретическое значение для дифференциальной геометрии имеют лемма 4.4, теоремы 4.1 — 4.7.

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

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

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

3. Исследовать более детально вопросы оценки точности восстановления кривой.

4. Исследовать вопросы масштабирования при резке изделий.

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