Теоретические и прикладные аспекты автоматизации технической подготовки производства цветных тканых узоров

Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

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

Теоретические и прикладные аспекты автоматизации технической подготовки производства цветных тканых узоров

Специальность: 05.13.06 - «Автоматизация и управление технологическими процессами и производствами (легкая промышленность)»,

БОРЗУНОВ ГЕОРГИЙ ИВАНОВИЧ

Москва - 2010

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Московский государственный текстильный университет имени А.Н. Косыгина» на кафедре информационных технологий и компьютерного дизайна

Официальные оппоненты: доктор технических наук Губин Виктор Владимирович

доктор технических наук, профессор Сапронов Михаил Иванович

доктор технических наук, профессор Юхин Сергей Семенович

Ведущая организация: ООО «МЕТРОТЕКС»

Защита состоится « 28 » декабря 2010 г. в 15.00 часов на заседании диссертационного совета Д 212.139.03 при Московском государственном текстильном университете имени А.Н. Косыгина по адресу: 119071, Москва, М. Калужская ул., 1

С диссертацией можно ознакомиться в библиотеке Государственного образовательного учреждения высшего профессионального образования «Московский государственный текстильный университет имени А.Н. Косыгина»

Автореферат разослан «____» ____________ 2010 г.

Ученый секретарь диссертационного совета

доктор технических наук Фирсов А. В.



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

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

Цель и задачи исследования. узор проектирование ткань

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

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

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

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

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

- разработана и исследована математическая модель ткацких переплетений, которая, обеспечивает систематизацию и классификацию ткацких переплетений;

- разработан метод автоматизированного построения рационального заправочного рисунка;

- разработаны теоретические основы расчета унифицированных схем проборок основ в ремиз;

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

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

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

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

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

- подготовлено и осуществлено внедрение программных реализаций основных теоретических результатов в Московском производственном камвольного объединении «Октябрь».

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

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

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

Научная новизна работы заключается в следующих результатах:

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

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

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

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

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

- разработан метод автоматизированного построения рационального заправочного рисунка;

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

- разработаны теоретические основы расчета унифицированных заправок основ в ремиз;

- предложен метод оптимизации сокращенных проборок основ в ремиз

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

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

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

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

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

- разработаны алгоритмы выделения раппортов точечных изображений;

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

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

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

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

- разработан метод минимизации необходимого количества схем проборок основ в ремиз;

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

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

Реализация результатов работы.

Разработанные алгоритмы реализованы в составе программного обеспечения САПР кареточных тканей "Логитрон 1002.СМ. Пакет прикладных программ для расчёта единых проборок основ в ремиз и оптимизации сокращенных проборок основ в ремиз внедрен в производство Московского производственного камвольного объединения «Октябрь». Внедрение и эффективность использования перечисленного выше программного обеспечения подтверждается актами и документами. Программный комплекс «Заправочный рисунок» используется в ГОУВПО «МГТУ им. А. Н. Косыгина» для разработки тканых узоров в курсовом и дипломном проектировании на кафедре ткачества и при проведении лабораторных занятий по курсу «Компьютерная обработка изображений» для студентов специальности № 23 004 00. Отдельные теоретические результаты работы и программные реализации алгоритмов используются на кафедре информационных технологий и компьютерного дизайна при подготовке и обновлении учебных курсов «Технологии программирования», «Компьютерная обработка изображений» и «Дискретная математика», а также в дипломном проектировании.

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

Основные результаты диссертационной работы докладывались и получили положительную оценку на международных и всероссийских научно-технических конференциях: ТЕКСТИЛЬ - (Москва, 1995,1998, 1999, 2001, 2002, 2004, 2008 гг., МГТУ им. А.Н. Косыгина), ПРОГРЕСС - (Иваново, 2005, 2008 гг., ИГТА), ПИКТЕЛ - (Иваново, 2003 г., ИГТА) на научных конференциях профессорско-преподавательского состава МГТУ им. А.Н. Косыгина, на Первой международной конференции «Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования» (Ижевск, 2009 г.).

Публикации.

Основные результаты работы отражены в 88 публикациях, в том числе 1 монография, 23 статьи в изданиях, рекомендованных ВАК РФ для публикации. На программный комплекс «Заправочный рисунок» имеется свидетельство о государственной регистрации №2006612092 в реестре программ для ЭВМ 16 июня 2006 г.

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

- структурную схему автоматизированной проектирования и технической подготовки производства тканых узоров;

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

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

- метод построения рационального заправочного рисунка;

- математическую модель ткацких переплетений и её применения для систематизации и классификации ткацких переплетений;

- теоретические основы расчета унифицированных заправок основ в ремиз и метод минимизации необходимого числа заправок основ в ремиз;

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

- алгоритмы двоичного и параллельного поиска минимального разбиения;

- математическую модель и метод оптимизации сокращенных проборок основ в ремиз;

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

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

Диссертационная работа состоит из введения, семи глав, общих выводов по работе, списка использованной литературы, содержащего 196 наименований, и приложений на 32 листах. Основная часть изложена на 320 страницах, содержит 96 рисунков, 12 таблиц. Общий объём диссертации - 352 страницы.

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

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

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

Различные подходы к построению цветных тканых узоров были предложены Ф. Донатом, О. С. Кутеповым, Г.Л., Б. Лунд-Иверсен, О.С. А. А. Мартыновой, Г. Л. Слостина, С. В. Малецкой. В настоящее время автоматизированные методы проектирования узоров для ремизного ткачество объединяются в системы автоматизированного проектирования (САПР). Примерами отечественных разработок могут служить следующие системы: «Логитрон 1002.СМ», «АРМ дессинатора» (МГТУ им. А.Н.Косыгина), «Дессинатор 2.0» (ГП ЦНИИЛКА), «Заправочный рисунок»). Среди зарубежных разработок наибольшее распространение получили системы: американская WeavePoint, канадская WeaveMaker Pro, испанская Fiberworks PCW Bronze, французская Lectra, NedGrhaphics. Современная тенденция развития САПР тканей заключается в том, что эти системы всё чаще ориентированы не только на проектирование (CAD - Computer-Aided Design - система автоматизированного проектирования), но и на генерацию управляющих программ управления ткацкими станками (CAM - Computer Aided Manufacturing - система автоматизированного производства). В другом направлении развивает интеграцию программ1ного обеспечения своей системы фирма «Лектра». В 2009 году эта фирма представила на российском рынке инновационную версию своей системы Kaledo, которая представляет собой дизайн-платформу для текстильной отрасли. Модуль KaledoTextile позволяет имитировать реалистичное изображение тканых материалов. Кроме того этот программный модуль содержит инструменты для создания тканных и трикотажных материалов со сложным рисунком. В работе С. В. Малецкой предлагается комплекс автоматизированных методов, совокупность которых может рассматриваться как автоматизированная система проектирования пестроткани. Функциональность этой системы обеспечивает автоматизированное построение узоров однослойных и двусторонних тканей, а также выполнение заправочных расчётов. Применение компьютеров позволило поставить и решить ряд новых задач, относящихся к различным аспектам проектирования тканей. В работах С. Д. Николаева, С. С. Юхина, Г. Н. Муратовой, А. В. Фирсова были предложены методы решения новых задач, реализация которых была бы невозможна без использования компьютерных технологий. Применение распределённых вычислений открывает перед исследователями новые возможности по расширению области применения автоматизированных. Однако, аффективное применение распределённых вычислений требует специального планирования и управления вычислительным процессом. В предложенной С.



Рис. 1. Структурная схема автоматизированной системы технической производства тканых узоров

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

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

В современной практике проектирования художественного оформления ремизных тканей исходные точечные изображения тканых рисунков чаще всего создаются дессинаторами (художниками) в среде графического редактора или получаются в результате либо цифрового фотографирования, либо сканирования твердых копий рисунков. Для определения задач, решение которых требуется для технической подготовки таких изображений с использованием технологии ремизного ткачества структурная схема автоматизированной системы (Рис. 1). Ниже описываются математические модели и алгоритмы, обеспечивающие решение задач, определенных этой схемой. Пусть точечное изображение представляется целочисленным двумерным массивом A[m][n], где n - ширина исходного рисунка, а m- высота.

Асимптотическая оценка временной сложности алгоритма Rpt1 в худшем случае оказывается равной T3(K)= O(K⁴). Для выделения раппортов изображений класса 2 был разработан Rpt2, который отличается от алгоритма Rpt1 тем, что в процессе его работы окно, выделяющее в качестве раппортов прямоугольные фрагменты изображения, не только принимает все возможные размеры, но размещается всеми возможными способами относительно изображения. Временная сложность алгоритма Rpt2 в худшем оказывается равной T5=O(K⁶). Оценки временной сложности Rpt1, Rpt2 явились основанием для разработки быстрых алгоритмов: Rpt3 - для выделения раппортов изображений класса 1 и Rpt4 - для выделения раппортов класса 2. Эти алгоритмы в отличии от простейших алгоритмов выполняют анализ изображения с помощью окна, имеющего форму горизонтальной полосы. Данные вычислительного эксперимента подтверждают результаты теоретического анализа: поиск раппорта с помощью алгоритма Rpt4 значительно (на 3 порядка) быстрее стандартного поиска раппорта с помощью алгоритма Rpt2.

Рис. 2. Пример применения алгоритма Rpt4.

Следующим этапом предварительной обработки изображений согласно предлагаемой структурной схеме является переход от недопустимо большой палитры цветов исходного изображения к палитре, содержащей меньшее число цветов (например, 10 - 20 цветов). Результаты исследования средств графических редакторов общего назначения свидетельствуют о том, при понижении числа цветов до 8 сохраняются основные цвета, определяющие колористическое решение и основные структурные особенности изображения. Экспериментальные исследования метода усечённого блочного кодирования показали, что этот метод может применяться для получения потенциально допустимых изображений в сочетании с другими методами редукции цвета. Понижение физической глубины цвета за счёт редукции разрядов 4-х разрядов в большинстве случаях несущественно изменяет восприятия изображения (см. рис. 3). Для эффективного понижения числа цветов изображений предлагается комплексный подход - методика, состоящая из следующих шагов:

1. Определяется, является ли исходное изображение тёмным или светлым. Для этого исходное изображение должно быть преобразовано, например, в формат HSB, разделено на каналы H, S, B. Затем для канала B стоится гистограмма и определяется среднее значение. Если среднее значение меньше 128, то имеет место тёмное изображение; иначе исходное изображение является светлым.

Рис. 3. Исходные изображения (слева) и изображения после заполнения нулями 4 младших разрядов

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

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

4. Выделяются n - наиболее часто встречающихся (основных) цветов, которые после сортировки занимают первые позиции в отсортированном массиве.

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

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

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

.

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

.



Поставим в соответствие каждому элементу матрицы m_i,j (здесь i - номер строки матрицы, j - номер её столбца), представляющей собой цветной узор, вершину графа a_i,j. Соединим ребрами весом 1 все вершины, соответствующие неравным элементам одного и того же столбца указанной матрицы и весом 0 -- все вершины, соответствующие неравным элементам одной и той же строки. Полученный граф назовем графом структуры точечного изображения. На рис. 4 приводится граф структуры цветного узора, заданного матрицей C₁.

Таблица 1 Таблица 2

Цвет утка	Переплетение
3	0	0	0	0	1	1
3	0	0	0	0	1	1
2	0	0	1	1	0	0
2	0	0	1	1	0	0
1	1	1	0	0	0	0
1	1	1	0	0	0	0
Цвет основы	1	1	2	2	3	3

Цвет утка	Переплетение
3	0	0	1
3	0	0	1
2	0	1	0
2	0	1	0
1	1	0	0
1	1	0	0
Цвет основы	1	2	3

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

Рис. 4. Граф структуры изображения, заданного матрицей C₁.

Будем называть суграфом часть графа, которая получается из исходного графа после удаления некоторых рёбер при сохранении всех вершин исходного графа. Для определения условий существования правильной раскраски выделим из графа структуры G изображения суграф G0, содержащий все ребра с весом 0 и только эти рёбра, а также суграф G1, содержащий все ребра с весом 1 и только эти рёбра. Рассмотрим объединение суграфов G₀ и G₁ и их композиции, вид которых определяется выражениями 1- 4:

G₀₀ =(G₀°G₁) U ((G₀°G₁)Ч (G₀°G₁)) U..U ((G₀°G₁)°(G₀°G₁)°...° (G₀ ° G₁))

G₀₁ = G₀ U (G₀° (G₁° G₀)) U..U (G₀° (G₁° G₀) ° ... ° (G₁° G₀)) (2)

G₁₀ = G₁ U (G₁° (G₀° G₁)) U..U (G₁° (G₀° G₁) ° ... ° (G₀° G₁)) (3)

G₁₁ = (G₁°G₀) U ((G₁°G₀)°(G₁°G₀))U..U ((G₁°G₀)°(G₁°G₀)° ... ° (G₁° G₀)) (4)

Построение графов G₀₀, G₀₁, G₁₀, G₁₁ основано на использовании алгоритма транзитивного замыкания Уоршелла. С учётом размерности матриц A₀, A₁ временная сложность алгоритма Уоршелла оценивается как T_4,2=O(m³Чn³), а при m=n T_4,2=O(m⁶). Для существования правильной раскраски графа структуры изображения необходимо выполнение следующих двух утверждений:

1. Любая вершина i структурного графа может быть окрашена в цвет 1 тогда и только тогда, когда для любой вершины j того же графа справедливо, что дуга (i,j) не принадлежит одновременно G₁₀ и G₁₁.

2. Любая вершина i структурного графа может быть окрашена в цвет 0 тогда и только тогда, когда для любой вершины j того же графа справедливо, что дуга (i,j) не принадлежит одновременно G₀₀ и G₀₁.

Пусть графы G₁₀, G₁₁, G₀₀, G₀₁ представляются в памяти компьютера в виде матриц смежности вершин A10, A11, A00, A01, в которых наличие дуги (i,j) обозначается 1 на пересечении строки со столбцом соответствующей матрицы. Все эти матрицы являются квадратными с числом строк и числом столбцов равным mn= mЧn, где m - число строк в матрице цветного изображения, а n - число столбцов в этой матрице. Следующий шаг анализа точечного изображения состоит в определении матрицы эскиза переплетения D, размерность которой совпадает с размерностью матрицы, с помощью которой было определено исходное изображение. В этой матрице элементы могут принимать следующие значения: элементы равные 0, определяют позицию, которую в переплетении может занимать только уточное перекрытие; элементы равные 1 соответственно определяют позицию, в которой может размещаться только основное перекрытие; элементы равные E₁₆ (шестнадцатиричное значение) определяют позицию, в которой могут располагаться уточное или основное перекрытия; наконец, элементы равные F₁₆ определяют позицию коллизии, т. е. позицию в которой не может быть ни уточного, ни основного перекрытия. При наличии коллизий возникает задача рациональной коррекции исходного рисунка за счёт изменения цвета одной или нескольких точек этого рисунка. Справедливо следующее утверждение. В изображении имеет место коллизия, если в графе структуры изображения существует вершина i, для которой найдутся вершины j и k, соединённые с вершиной i с вершинами четырьмя маршрутами:

((i, p₁, 0), (p₁, p₂, 1),... ,(p_2m-2, p_2m-1,0), (p_2m-1, p_2m, 1), (p_2m, k,0)); (5)

((i, q₁, 0), (q₁, q₂, 1), … ,(q_2n-2, q_2n-1,0), (q_2n-1, k , 1)); (6)

3) ((i, v₁, 1), (v₁, v₂, 0), … , (v_2s-2, v_2s-1,1), (v_2s-1, v_2s, 0), (v_2s, j, 1)); (7)

4) ((i, w₁, 1), (w₁, w₂, 0), … ,(w_2t-2, w_2t-1, 1), (w_2t-1, j , 0)). (8)

При наличии в графе маршрутов (5-6) можно выделить два цикла нечётной длины, один из которых начинается и заканчивается рёбрами с весом 0, а другой начинается и заканчивается рёбрами с весом 1:

((a_3,1, a_3,3, 0) (a_3,3, a_2,3, 1) (a_2,3, a_2,2, 0) (a_2,2, a_3,2, 1) (a_3,2, a_3,1, 0)); (7)

((a_3,1, a_1,1, 1) (a_1,1, a_1,2, 0) (a_1,2, a_2,2, 1) (a_2,2 a_2,1, 0) (a_2,1, a_3,1, 1)). (8)

Таким образом, для выполнения необходимого условия существования ткацкого переплетения, обеспечивающего выработку заданного рисунка необходимо отсутствие в графе структуры рисунка запрещённых фигур: циклов нечетной длины проходящих через оду и ту же вершину в соответствии с (7,6). На основании этого подхода разработаны алгоритмы Bsf и DelCycles, обеспечивающие устранение из графа структуры изображения всех запрещённых фигур при близком к минимальному количестве удаляемых рёбер. На рис. 5 приводится раппорт изображения, граф структуры которого содержит запрещённые фигуры, а на рис. 6 раппорт того же изображения после удаления запрещённых фигур с помощью алгоритмов Bsf и DelCycles. Сравнение рис. 5 и рис. 6 показывает, что изображения на этих рисунках практически совпадают. Вычислительный эксперимент подтвердил эффективность разработанных алгоритмов и одновременно их большую временную сложность: O(m3Чn3). Для расширения диапазона практически решаемых задач такая временная сложность требует использования методов параллельного программирования.

Рис. 5. Исходное изображение Рис.6. Изображение без запрещенных фигур

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

Пусть дан раппорт сатина 5/2, содержащий пять нитей основы и пять нитей утка. Поставим в соответствие каждой i-ой нити основы из раппорта переплетения вершину Oi, а каждой j-ой нити утка из того же раппорта вершину Y_j, где i=l,2, ...,5, а j= 1,2,... ,5. Соединим звеньями (неориентированными рёбрами) каждую вершину Оi - с вершиной O_i+1 (i=l,2,... ,4) и каждую вершину Y_j с вершиной Y_j+1 (j =l,2,.. .,4), а также O₅ с O₁ и Y₅ с Y₁. Соединим дугой (ориентированным ребром) каждую вершину О_i с вершиной Y_j только в случае, когда i-ая нить основы перекрывает в пределах раппорта j-ую нить утка. Полученный граф назовем графом структуры данного ткацкого переплетения или просто структурным графом (рис. 7). Любому представлению раппорта ткацкого переплетения однозначно соответствует некоторый граф структуры ткацкого переплетения. Разным представлениям одного и того же переплетения соответствуют изоморфные структурные графы. Пусть основным циклом называется минимальный по длине цикл, который не содержит повторяющихся вершин и проходит по неориентированному ребру (звену), соединяющему две смежные вершины из множества О, затем по ориентированному ребру, соединяющему вершину из множества О с вершиной из множества Y, далее по неориентированным ребрам (звеньям), соединяющим вершины из множества Y и, наконец, по ориентированному ребру (против направления ребра), идущему из некоторой вершины, принадлежащей множеству Y, в исходную вершину из множества О. Аналогично определяется уточный цикл.

Рис. 6. Граф структуры сатина 5/2.

Например, в графе, приведенном на рис. 6, цикл, проходящий по вершинам О₁, О₂, Y₃, Y₂, Y₁, О₁ , является основным. Уточный цикл в этом графе проходит по тем же вершинам, но в другой последовательности: Y₂, Y₃, О₂, О₃, О₄,Y₂. Сравнение длины основных и уточных циклов структурных графов приводит к общепринятой классификации ткацких переплетений. Так, главным переплетениям соответствуют однородные структурные графы со степенью вершин, равной трем, и одинаковой длиной всех основных или уточных циклов. Назовем такие графы главными структурными графами. Главные структурные графы, имеющие основные и уточные циклы, равные четырем, соответствуют полотняным или саржевым переплетениям. При длине основных или уточных циклов более четырех главные структурные графы представляют сатиновые переплетения. Разницу в длине основного и уточного циклов в главных структурных графах, имеющих одинаковое число вершин, можно использовать для оценки равномерности размещения основных перекрытий в соответствующих ткацких переплетениях. Получаемый в результате анализа точечных изображений эскиз переплетения в сочетании с технологическими ограничениями на R[M][N], позволяет отсечь недостроенные варианты R[M][N], завершение которых не приводит к желаемому результату. Это делает возможным для заданного тканого узора применение конструктивного перебора вариантов переплетений определяемых R[M][N], с целью выбора переплетения, в максимальной степени удовлетворяющего технологическим требованиям. Для реализации этого подхода был предложен алгоритм WEAVE, генерирующий матрицы R в два этапа: выполняется построение первого варианта матрицы R, удовлетворяющего заданным ограничениям; конструктивное перечисляются все последующие решения. При невозможности построить первый вариант матрицы R, определяются неверно заданные ограничения. Функция weave621 осуществляет проверку соответствия рабочих данных заданным ограничениям, weave622 корректировку рабочих данных после определения очередного элемента R. Функция weave621 осуществляет проверку соответствия рабочих данных заданным ограничениям, weave622 - коррекцию рабочих данных при записи в W нового элемента, weave623 - коррекцию рабочих данных при обратном движении.

//Начало псевдокода алгоритма

weave620(); //Восстановление рабочих данных

////////////***** Построение первого решения *******/////////////

for(J=1; J < = M; J++) { for(I=N; I > 0; I--) {If(D[I][J]==0xE) {

// Проверка возможности присвоения R нулевого значения

K=0;if(weave621()){R[I][J]=K;weave622();goto etka2;}

// Проверка возможности присвоения R единичного значения

K=1; if(weave621()){ R [I][I]=K; weave622(); go to metka2;}

///////////**** Переход на новую ветвь***////

// поиск элемента R, который можно изменить

for(J2=1; J2 < = J; J2++) { for(I2=N; I2 > 0; I2-- ) {

If((D[I2][J2]==0xE)){ if(R[I2][J2]==0) {

K=1; if(weave621()){R[I2][I2]=K; weave623(); go to metka1; }}

// проверка возможности размещения нулевых значений

else{ K=0; if(weave621()){ R[I2][I2]=K;weave623(); go to metka1;}} //end else

}// end of If((D[I2][J2]==0xE))

// Проверка возможности присвоения R нулевого значения

metka1: K=0; if(weave621()) { R[I][J]=K; weave622(); go to metka2;}

// Проверка возможности присвоения R единичного значения

K=1; if(weave621()) { R[I][I]=K; weave622(); go to metka2;}

if((J2==J)&&(I2==I)) stop; //неверны исходные данные

} } //evd of for(J2=1; J2 < = J; J2++)

stop; // неверны исходные данные

metka2:} } // end of for(I=N; I > 0; I--)

Use R; // Получено решение

///////////***** Конец построения первого решения *******////

//////***Начало генерации остальных решений**///////

flag = true; while(flag){flag = false; for(J=1; J2 < = M; J++) { for(I= N; I > 0; I--) {If(D[I][J]==0xE) {

// Проверка возможности присвоения R единичного значения

If(R[I][J]==0) {K=1; if(weave621()) { R[I][I]=K; weave623(); flag = true;

USE R; go to metka3;} // Получено решение

}//end of If(R[I][J]==0)

// Проверка возможности присвоения R нулевого значения

K=0; if(weave621()) { R[I][J]=K; weave623();}} //end of If(D[I][J]==0xE)

}} flag = false; metka3: } // end of while(flag)

///////////////******** Конец псевдокода алгоритма *******////////////

Для определения матриц, которым соответствуют однослойные переплетения, предлагается метод, основанный на анализе графов структуры переплетений:

1. Из графа структуры ткацкого переплетения G(O, Y, U), заданного множествами вершин O, Y и множеством рёбер U, удаляются неориентированные рёбра:U₁ = U\ {{ O_i, O_i+1 }, i = (l,2,..., n-1)}\ { О_п , О₁ }\{{ Yj, Y_j+I }, j =1,2,..., т-- 1}\{ Y_m , Y₁}. При этом G(O, Y, U) граф U превращается в двудольный ориентированный граф G₁(O, Y, U₁), где множество рёбер состоит из дуг, соединяющие одну из вершин множества O с некоторой вершиной из множества Y: U₁ = {(O_i, Y_j)}.

2. Затем множество дуг U₁ графа G₁(O, Y, U₁) пополняется дугами вида (Y_j, O_i), если в U₁ нет дуги вида (O_i, Y_j): E= U₁ { (Y_j, O_i) | (O_i, Y_j) U₁ }.

В результате пополнения множества рёбер граф G₁(O, Y, U₁) превращается в ориентированный граф Q(O, Y, E. Такой граф Q здесь и ниже будем называть графом связности переплетения, соответствующего графу структуры переплетения G, из которого был получен граф Q. В памяти компьютера граф Q может быть представлен в виде модифицированной матрицы смежности, в которой элементы могут принимать следующие значения: элемент равный -1, стоящий на пересечении i-той строки и j-того столбца(a_ij==-1), определяет наличие в графе Q(O,Y,E) дуги, идущей из вершины O_i в вершину Y_j, элемент равный +1, стоящий на пересечении i-той строки и j-того столбца (a_ij==1), означает дугу, идущую из вершины Y_j в вершину O_i.

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

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

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

Минимальное число ремизок, необходимых для выработки k заданных тканей по единой проборке, равно числу классов эквивалентностей r= |X/q|, где X. - множество нитей основы; q= q₁?q₂? …?q_k; qi(i=1, 2, …, k) - эквивалентности на X, сопряженные с проборками, обеспечивающими выработку заданных тканей. Пусть заданы проборки, необходимые для выработки k тканей, которые определяют сопряжённые эквивалентности q₁, q₂, …, q_k на множестве нитей основы X. Пусть ткацкий станок имеет m ремизок. Тогда, вычислительная схема алгоритма построения унифицированной проборки, обеспечивающей выработку всех k тканей, состоит из шагов:

1. Положить .q=q1;

2. Положить i=1; .

3. Выполнить q =q?qi;

4.. Если [X/q]>m, то единой проборки не существует, стоп.

5. Выполнить i++;.

6. Если i<k, то перейти к п.3;

7. Единая проборка определяется эквивалентностью q, СТОП.

Как видно из приведенного описания алгоритма, в результате решение задачи по данному алгоритму либо получается единая проборка для выработки заданных тканей, либо доказывается, что такой проборки не существует. Если в результате применения рассмотренного выше алгоритма было установлено, что при заданных условиях унифицированная проборка не существует, возникает задача поиска разбиения заданного множества сопряжённых эквивалентности q₁, q₂, …, q_k на минимальное число непересекающихся подмножеств при условии, для каждого подмножества существует унифицированная проборка. Ниже приводится псевдокод алгоритма решения этой задачи, в котором используются обозначения: s - число сопряженных эквивалентностей; n - число нитей основы в заправке; m - число доступных ремизок, X={x₁, x₂ ,…, x_n} - множество нитей основы в заправке; E={e₁, e₂, …, e_s} - множество сопряженных эквивалентностей, каждая из которых (e_i) разбивает множество X на непустые и непересекающиеся классы или подмножества Xⁱ₁, Xⁱ₂, …, Xⁱ_k (X/e_i={Xⁱ₁, Xⁱ₂, …, Xⁱ_ki}) т. о., что все нити основы одного класса Xⁱ_j (j=1, 2, …, ki) могут быть пробраны в одну ремизку; |X/e_i | - число подмножеств в разбиении X/e_i ; pⁱ_j - эквивалентность равная пересечению всех эквивалентностей, которые составляют подмножество Eⁱ_j. (j=1, 2, …, ti), принадлежащее разбиению E/q_i. Любое разбиение q_i называется допустимым; если оно разбивает множество E на такие непустые и непересекающиеся классы, что ???Eⁱ_j ?E/q_i:|X/pⁱ_j|?m. Допустимое разбиение q_i ?Q, состоящее из минимального числа подмножеств множества E, называется минимальным допустимым разбиением и обозначается qmin. Ниже приводится обобщенное описание алгоритма решения этой задачи;

1. Пусть допустимое разбиение qr есть разбиение множества E на s классов (такое разбиение всегда является допустимым), переменная r принимает значение равное числу классов в текущем допустимом разбиении r=s, а текущее разбиение qi множества E состоит из единственного класса, и переменная ri принимает значение равное числу классов в этом разбиении: ri=1.

2. Если ri< r, то с помощью функции FC(qi) проверяется, является ли разбиение qi допустимым. Если разбиение qi является допустимым (FC(qi)==1) , то выполняется переход к п.3; иначе, т. е. при FC(qi)==0 - переход к п. 4.

3. Запоминаются новые значения qr=qi и r=ri.

4. Для получения нового варианта разбиения qi?Q используется функция FQ, которая возвращает в качестве своего значения либо число классов и описание нового разбиения, либо нуль, если все возможные варианты разбиения уже перечислены: ri=FQ(qi).

5. Если ri=0, то выполняется переход к п.6; иначе - переход к п.2.

6. Поиск завершается и в качестве решения принимается разбиение qr, состоящее из r непересекающихся и непустых подмножеств:qmin=qr. Стоп.

В шестой главе рассматриваются методы повышения эффективности распределённых вычислений.

Естественной математической моделью, на основании которой решается задача балансировки вычислительной нагрузки является взвешенный граф. В этом графе вершины соответствуют подзадачам, вес вершин моделирует временную сложность подзадач, а вес рёбер моделирует объём передаваемой информации. Задача эффективного планирования вычислений состоит в разбиения вершин графа на непересекающиеся подмножества с максимально близкими значениями суммарных весов вершин подмножеств при минимальном значении суммы весов ребер, соединяющих вершины, принадлежащие разным подмножествам. При этом каждое подмножество вершин ставится в соответствие некоторому процессору. В данной работе анализируются спектральные, графические и многоуровневые методы разделения таких графов. Далее описывается разработка базовых алгоритмов конструктивного перечисления разбиений множеств создание на их основе метода оптимального разделения взвешенных графов. Алгоритм Eq2_1, последовательно генерирует варианты разбиения множества в порядке монотонного возрастания числа подмножеств, и для управления его работой используются два новых параметра: ns и nf. Значение параметра ns определяет начальное (минимальное) значение числа подмножеств в генерируемых разбиениях, а значение параметра nf - конечное (максимальное) значение числа подмножеств в генерируемых разбиениях. Использование алгоритма Eq2_1 обеспечивает возможность генерации разбиений не подряд, а выборочно, что позволяет использовать при поиске минимальных разбиений схему двоичного поиска. Ниже приводится алгоритм двоичного поиска минимальных разбиений EQ3_1, в котором значение i-той координаты вектора pChi определяет номер класса, включающего в себя i-тый элемент разбиваемого множества.

1. Пусть исходное множество X содержит n элементов. Положить ns=1, nf=n, P=(0,0,0,…,0), где P - характеристический вектор.

2. Положить np=nf. Используя алгоритм EQ2_1, выполнить поиск допустимого разбиения множества X на np частей. Если найден характеристический вектор допустимого разбиения pChi, то выполнить: {P= pChi; nf--;} иначе решения не существует, стоп.

3. Выполнить np= (nf + ns)/2. Здесь деление выполняется нацело, т. е. с отбрасыванием остатка. Используя алгоритм EQ2_1, выполнить поиск допустимого разбиения множества X на np частей. Если найден характеристический вектор допустимого разбиения pChi, то выполнить: P= pChi; иначе перейти к п.5.

4. Положить nf = np; если ns < nf, то перейти к п. 3; иначе P - характеристический вектор минимального разбиения множества X, стоп,

5. Если ns < nf, то выполнить ns= np+1; иначе P - характеристический вектор минимального разбиения множества X, стоп,

6. Выполнить np= (nf + ns)/2. Деление выполняется нацело. Используя алгоритм EQ2_1, выполнить поиск допустимого разбиения множества X на np частей. Если найден характеристический вектор допустимого разбиения pChi, то выполнить: { P= pChi и перейти к п. 4;} иначе перейти к п. 5.

Использование алгоритма EQ3_1 обеспечивает уменьшение временной сложности решения данной задачи в 2 -3 раза. На основе алгоритма EQ2_1 впервые разработана вычислительная схема параллельного поиска минимального разбиения (алгоритм EQ4_1).:

1. Пусть n - число элементов в исходном множестве X; p - число процессоров, доступных для выполнения поиска; fp[n] -вектор активных процессоров: nsp[i], nfp[i]- соответственно начальное (минимальное) и конечное (максимальное) числа подмножеств в разбиениях при поиске, который реализуется с использованием i - того процессора; pChi[i], np[i] - характеристический вектор разбиения, удовлетворяющем заданным ограничениям, и текущее число подмножеств в этом разбиении; icp - номер процессора, с использованием которого найдено минимальное разбиение; i, ii, - управляющие параметры циклов; k - рабочая переменная; ms[i] - сообщение i - того процессора о завершении его работы; pChiMin, npMin - характеристический вектор минимального разбиения и число подмножеств в этом разбиении.

2. Центральный процессор определяет диапазоны поиска nsp[i], nfp[i] для p процессоров, передает им эти значения и активизирует их работу: icp =p; fp[]= (0, 0, …, 0); pChiMin =(1, 2, …, n); k =n/p; nsp[0]=1; nfp[0]=k-1;

for(i=1;i< p;i++) { nsp[i]+= k; nfp[i]+=k; передать nsp[i], nfp[i] процессору P[i]; fp[i] =1; активизировать P[i]}

3. Активизированные процессоры осуществляют параллельный поиск минимального разбиения: Parallel Start for(ii=1;ii< p;ii++) { P[ii]: np[ii]= nsp[ii]; P[ii]: while (np[ii]<= nfp[ii]&& fp[ii] ==1) {Выполнить EQ2_1; if(pChi[ii] - удовлетворяет заданным ограничениям) {передать центральному процессору ms[ii]=1 и pChi ; } } P[ii]: if (fp[ii] ==1) { передать центральному процессору сообщение о завершении поиска ms[ii]=0; стоп [ii];}}

Parallel End

4. Центральный процессор, получив сообщение о завершении поиска от ii - того процессора выполняет действия: while(fp[i]! =(0, 0, …, 0)) { Читать ms[ii]; if(ms[ii]==0) { for(i=0;i<=ii;i++) fp[i] =0;}else { Читать pChi[ii]; if(npMin > np[ii]) {icp=ii; npMin = np[ii]; pChiMin = pChi[ii]; } if (ii<n-1){for(i=ii+1;i<n;i++) fp[i] =0; }} Стоп, в pChiMin размещается характеристический вектор минимального разбиения, а в npMin - число подмножеств в минимальном разбиении. Результаты экспериментальной оценки временной сложности алгоритма EQ4_1, что по сравнению с алгоритмом EQ3_1 в среднем он обеспечивает в среднем ускорение более чем в 2 раза.

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

На основе предложенных математической модели структуры цветных точечных изображений и алгоритмов расчета рационального заправочного рисунка были разработаны программы, эффективная работа которых в составе САПР тканей «Логитрон 1002М», подтвердила правильность теоретических результатов данной работы. Построенные с учетом производственных условий Московского производственного камвольного объединения «Октябрь» модели свойств тканей, обеспечили рациональный выбор параметров строения проектируемых тканей и расчет заправочных параметров тканей, вырабатываемых с использованием унифицированных схем проборок основ в ремиз. Использование унифицированных проборок в условиях производства Московского производственного камвольного объединения «Октябрь» позволило вырабатывать ткани, переходя от одного рисунка к другому без выполнения операции проборки новой основы в ремиз и заправки этой основы, осуществляя лишь её привязку. Построенные с учетом производственных условий Московского производственного камвольного объединения «Октябрь» модели свойств тканей, обеспечили рациональный выбор параметров строения проектируемых тканей и расчет заправочных параметров тканей, вырабатываемых с использованием унифицированных схем проборок основ в ремиз. Таким образом, практическое применение в производственных условиях программных реализаций основных теоретических результатов (математических моделей алгоритмов и основанных на них методов) полностью подтвердило правильность данной работы.



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

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

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

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

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

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

6. Разработаны теоретические основы расчета унифицированных заправок основ в ремиз.

7. Разработан алгоритм конструктивного перечисления вариантов разбиения множества при монотонном возрастании числа подмножеств.

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

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

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

...