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

г Г о ОД

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

Кондукова Екатерина Владимировна

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

ШРИФТОВ

Специальность 05.13.12 — Системы автоматизации

проектирования (промышленность)

АВТОРЕФЕРАТ

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

Санкт-Петербург 1998

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

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

докторант кафедры ГПС СПбГТУ, главный конструктор ЦНИ СПбГТУ А. М. Коновалов

Официальные оппоненты: доктор технических наук,

профессор А. М. Яшин; кандидат технических наук, доцент Ю. А. Гатчин

Ведущая организация — Санкт-Петербургская

картографическая фабрика ВСЕГЕИ

Защита состоится 17 марта 1998 года в 16 часов на заседании диссертационного совета К.063.38.28 при . Санкт-Петербургском государственном техническом университете по адресу: 195251, Санкт-Петербург, Политехническая ул., 29, I учебный корпус, ауд. 439

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

Автореферат разослан ", (6 Ученый секретарь диссертационного совета Н. М. Чесноков

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

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

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

Работа выполнена в рамках реализации комплексного проекта "Создание комплекса специализированного инжиниринга полиграфии" Федеральной программы "РОССИЙСКАЯ ИНЖИНИРИНГОВАЯ СЕТЬ ТЕХНИЧЕСКИХ НОВОВВЕДЕНИЙ" и является составной частью научно-исследовательских работ Центра наукоемкого инжиниринга при Санкт-Петербургском государственном техническом университете.

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

В рамках поставленной цели решаются задачи исследования и реализа-

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

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

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

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

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

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

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

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

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

- На основе разработанных алгоритмов создано программное обеспече-

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

- В качестве инструментального средства поддержки шрифтов разработан интерпретатор Туре 1.

- Сформированы базы данных моделей символов алфавита и матриц сходства символов, входящие в состав САПР-Ш.

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы были доложены и обсуждены на двух научно-технических конференциях: на III Санкт-Петербургской международной конференции "Региональная информатика - 94" и на IV Санкт-Петербургской международной конференции "Региональная информатика - 95".

Публикации. По теме диссертации опубликованы шесть печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 100 наименований и семи приложений. Она содержит 145 страниц основного машинописного текста, 55 рисунков на 43 страницах и 8 таблиц.

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

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

Первая глава посвящена организации подготовки изданий с использованием заказных шрифтов. Рассмотрены назначение и структура настольных издательских систем, способы представления графической и текстовой информации. Основное внимание уделено шрифтам: от традиционных определений и классификаций до методов описания компьютерных шрифтов и построения шрифтового формата. Обоснован выбор формата Adobe Туре 1 в качестве базового шрифтового формата для САПР-Ш. Рассмотрено проек-

тирование шрифтов в традиционной полиграфии.

Проведен анализ современного состояния дел на рынке редакторов шрифтов, среди которых рассмотрены программы FontGen V, Ares FontMon-ger, система FontLab 2.5 и ее более простая версия FontLab 2.0 Lite.

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

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

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

В процессе работы САПР-Ш оперирует с информацией, содержащейся в трех базах данных БД1, БД2 и БДЗ.

База данных БД1 содержит описания моделей всех символов заданного алфавита. База данных БД2 содержит матрицы сходства примитив-штрихов моделей символов алфавита.

Каждая матрица сходства имеет вид:

где {ПШху} — у-ковый примитив-штрих символа х;

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

База данных БДЗ содержит матрицы топологии символов, где указаны координаты вершин скелетов моделей в адресном пространстве графемы с указанием положения их относительно характерных линий графемы (линии шрифта, левого и правого полей и т.д.).

Для решения поставленной задачи САПР-Ш выполняет следующую по-

следовательность процедур:

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

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

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

- составление модели символа-эталона с использованием скелетизации;

- выделение вершин скелета и описаний примитив-штрихов скелета путем сравнения символа-эталона с моделью из БД1;

- составление таблицы толщин штрихов символа-эталона;

- генерация описаний скелетов других символов алфавита по матрицам сходства из БД2;

- корректировка описаний скелетов других символов с учетом матриц топологии из БДЗ;

- составление описаний новых символов с учетом таблиц толщин штрихов в формате Туре 1.

В заключительной части первой главы обоснован выбор среды (Microsoft Windows) и языка программирования (C/C++) как базовых для разработки программного обеспечения.

Во второй главе поставлена задача анализа графем в САПР-Ш, которая приводит к разработке алгоритмов векторизации и скелетизации растровых образов, реализации и исследовании этих алгоритмов, а также разработке специализированных баз данных, содержащих формализованное описание символов алфавита.

В связи с тем, что работа в САПР-Ш ведется с форматом Adobe Туре 1, сформулированы требования к реализации системы, предъявляемые форматом Туре 1 и языком описания страницы PostScript; а именно, при разработке и реализации алгоритмов анализа графем необходимо учитывать следующие специфические черты формата Adobe Туре 1: замкнутость всех контуров символа; отсутствие пересечений линий контуров; правило заполнения областей, образуемых контурами; требование максимально простого описания контура командами языка; использование в качестве графических примитивов отрезков прямых и кривых Безье третьей степени.

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

на вход системы (см. рис. 1).

Исходные изображения графем представляются в виде прямоугольного_____________

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

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

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

Изображение представляется в виде прямоугольной матрицы элементов, каждый из которых может принимать значение "О" или " 1" (черно-белое изображение). Пространственное квантование изображения состоит в том, что значения интенсивности изображения измеряются в узлах некоторой дискретной сетки. В квадратной сетке точка имеет 4 или 8 соседей (с учетом диагональных направлений). Множество соседей называется окрестностью точки. На основе соседства определена связность точек.

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

Изображение символа\ I векторной форме (ВФ)] (CharStrinqs)

Интерп Ту[ зетатор )е 1

/

Шрифт в формате Adobe Туре 1

\

Рис. 1. Схема этапов обработки символьных объектов

точек сформулированы критерии для нахождения точек границы объекта.

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

последовательность точек Р[0], Р[1] .. Р[п], обладающую следующими свойствами:

- Р[0] = Р[п], так как каждая линия контура замкнута.

- Некоторые точки могут повторяться несколько раз (кратные точки).

- Характеристикой цепочки в каждой точке (Р[/]) является так называемый цепной код (CC[/D, — целое число от 0 до 7, определяющее номер соседа, следующего за данной точкой в цепочке Р[/-1]). СС[/] определяет направление выхода из точки P\j\, a C[j-1] — входа в нее. Направление из P\j\ в Р[/-1] обозначается RETCQj] = (СС[/-1]+4) mod 8.

- Для каждой точки P\j\ все соседние с ней внутренние точки (если есть) находятся слева от линии Р[/-1] - Р[/\ - Р[/+1]. Это обеспечивает разделение внутренних и внешних контуров.

Разработан следующий алгоритм обхода:

1. Найти любую точку границы Р[-1]. Она имеет хотя бы одного 0-соседа (на изображении объекта). Вычислить СС[-2] — направление из этого 0-соседа в Р[-1]. Присвоить J = -1.

2. Определить следующую точку цепочки Р[/+1]. Для этого проверить соседние с P[j] точки границы объекта, находящиеся от Р[/] по направлению CCN: CCN уменьшается от RETCC[¡\-\ до RETCC\j\. Первая найденная точка есть Р[/'+1]. Если CCN = RETCQj], то Р[/] — концевая точка, т.е. Р[/+1] = Р[/-1].

3. Присвоить ССТ/1 = CCN, 7 = 7+1.

4. Если Р[/\ * Р[0] вернуться к п. 2.

Иначе:

Если RE'ÍCCy] * ССЩ — считать обход законченным.

В противном случае — вернуться к п. 2

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

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

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

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

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

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

1. За исходное (/Л/1) принимается изображение всего объекта, для которого необходимо получить скелет.

2. Присваивается side = сверху. DelUnits = 0.

3. Выделяются границы объекта 1М\. Создается изображение IM2, содержащее только точки границ объекта. Создается копия 1МЪ изображения IM2.

4. На 1М\ удаляются точки объекта, расположенные со стороны side. Это точки, имеющие 0-соседа в 4-окрестности на IM1 с соответствующей стороны. Количество удаленных точек прибавляется к DelUnits.

5. Производится обход линий границ с помощью алгоритма обхода и определяются кратные точки. Если точка P\j\ — кратная и еще не была восстановлена, то она восстанавливается в IM 1, a DelUnits уменьшается на 1.

6. За исходное принимается изображение IM 1.

7. Повторяются п.п. 3-5 для side = снизу, слева и справа.

8. Если при выполнении п.п. 3-5 для всех четырех сторон не была удалена ни одна точка, т.е. DelUnits = 0, то полученное изображение есть скелет исходного. Если же была удалена хотя бы одна точка (DelUnits > 0), процесс повторяется снова с п. 2.

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

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

Помимо понятия цепного кода CC[i] в точке Р[г], введено понятие разностного кода в точке P[i], который обозначен как £>С[г]. Точка, в которой DC не равен 0, названа NZP— ненулевая точка. Соответственно, точки с нулевым DC названы ZP. Для каждой NZP Р[г] введено понятие парной суммы .РЗД. Последовательность NZP точек, ограниченную двумя ZP точками, названа ненулевым сегментом NZS, а последовательность ZP точек — ZS.

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

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

Кривую Безье В= В(г), где I — параметр, 0 < t < 1, можно записать в виде

В(0 = (1 - ifВ{0]+i(l - о2Bill+г2(1 - г)В[2]+г3ВД,

где контрольные точки В[1] и В[2] определяют форму кривой, В[0], В[3] — концевые точки. Если В[0], В[1], В[2], В[3] лежат на одной прямой, то кривая вырождается в отрезок прямой В[0]—В[3].

Приведен вывод уравнения метода наименьших квадратов при следующих предположениях и обозначениях: точки РИ,у—0, ..., к образуют последовательность точек сегмента, к — длина сегмента; /'[О] — начальная точка, Р[к] — конечная точка; В(0) = В[0] = Р[0] = {х0, уо}, В(1) = В[3] = Р[к] =

{хз.З'з}; Ц1) = к — длина сегмента; в точке кривой P\j\ t - j/k.

Тогда для координаты х: Ex=Ex(xux2)-> min:

fa,*, + bx2 +си - О

U где

[ох, +а2х2 + с2х = 0

где

Ь=Ы<Ш

}=0 о у«о

К К

си=i>(oH(o); =I

;=о о

п А_/1

к

v _£i>l£2A '

a(a2 ~ 6

Аналогично для координаты >>.

В четвертой главе проанализирован опыт разработки и применения системы анализа графем в САПР-Ш.

Рассмотрены особенности реализации системы анализа графем в САПР-Ш: реализованные алгоритмы, состав комплекса программных модулей и организация данных, интерфейс с оператором. Объем разработанного программного обеспечения блоков обработки растровых образов и интерпретатора Туре 1 составляет свыше 7000 строк на языке C/C++, что совместно с блоками организации интерфейса соответствует объему загрузочного модуля около 160 Кбайт.

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

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

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

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

- Получаемые в результате векторизации кодированные последовательности команд формирования символов (СИагЭ^тяз) соответствуют требованиям формата Туре 1.

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

- Правила 1 - 6 выделения критических точек и метод сегментации дают хорошие результаты при определении точек излома и плавных переходов кривой в прямую при оптимальном значении для параметра отношения длин Ы1АТ= 1,7.

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

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

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

Рассмотрена реализация интерпретатора Туре 1 и проанализирован опыт его эксплуатации, на основании чего сделан вывод об эффективности применения в САПР-Ш подсистемы поддержки шрифтов, разработанной на его основе.

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

Рассмотрено применение разработанной системы анализа графем в составе автоматизированного рабочего места дизайнера.

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

ЗАКЛЮЧЕНИЕ

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

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

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

3. Для выбранного определения 8-связности и 4-связности и с учетом требований выбранного формата Adobe Туре 1 сформулирован критерий для нахождения контуров изображения как множества точек объекта, имеющих 0-соседа в 4-окрестности и 1-соседа в 8-окрестности, который не имеет 0-соседа в 4-окрестности.

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

ограничениями, вытекающими из требований формата Adobe Туре 1.

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

6. Разработан алгоритм сегментации линий контуров, основанный на базе цепного и разностного кодов, который удовлетворяет требованиям формата Adobe Туре 1.

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

8. В качестве инструментального средства разработан интерпретатор Туре 1 и показана эффективность применения в САПР шрифтов созданной на его основе подсистемы поддержки шрифтов.

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

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

Основное содержание диссертации опубликовано в следующих работах:

1. Кондукова Е. В., Коновалов А. М. Настольная издательская система в интегрированном опытном производстве. //В сб. Интегрированные опытные производства как средство развития систем комплексной автоматизации.—Л.: ЛДНТП, 1991, с. 29-31.

2. Кондукова Е. В., Сергеев В. А. Технология подготовки технической документации в гибком интегрированном производстве. //В сб. Тезисы докладов Второй всесоюзной научно-технической конференции "Ресурсо-, энергосберегающие и наукоемкие технологии в машино- и приборостроении". —

М., 1991, с. 102- 103.

3. Кондукова Е. В. Алгоритмические и программные средства системы автоматизированного проектирования шрифтов. — Проблемы информатизации, 1994, вып. 3-4, с. 61—62.

4. Kondukova Е. V. Algorithmic and Software Tools of Computer Aided Design Fonts System. — The III St. Petersburg International Conference "Regional Informatics - 94". Proceedings of the Conference. St. Petersburg, 1994, p. 249 - 250.

5. Кондукова E. В. Обработка контуров графем в системе автоматизированного проектирования шрифтов. //В сб. IV Санкт-Петербургская Международная Конференция "Региональная информатика - 95": Труды конференции. — СПб., 1995, с. 170 - 177.

6. Kondukova Е. V. Processing of Glyphs Outlines in a Computer Aided Design Fonts System.— The IV St. Petersburg International Conference "Regional Informatics - 95". Proceedings of the Conference. Saint Petersburg, 1995, p. 138- 145.