Лекция 0. Основные понятия и определения

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

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

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

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

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

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

Под образом понимается некоторое множество изображений, объеди­няемых некоторыми общими свойствами.

Только материально существующее изделие и графическое изображе­ние геометрического объекта позволяют человеку воспринять информа­цию, которую несут в себе рассмотренные понятия. Техническая доку­ментация и графическое изображение тесно связаны отношением подчи­ненности. так как последнее является специальным элементом первого. Геометрический объект как математическая модель доступен человеку лишь косвенно через изображение, и, хотя математическое выражение ax+by+cz+d=0 представляет плоскость, оно воспринимается только после преобразования в сознании человека.

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

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

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

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

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

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

Каждое из этих направлений (кроме последнего) имеет относи­тельно длительную историю развития, хотя их сходство привлекло внимание лишь недавно. Связь распознавания и обработки изображе­ний была впервые осознана благодаря возможности осуществления та­ких преобразований изображения, в результате которых упрощается задача его классификации. Осознание существования связей между этими двумя направлениями и машинной графикой произошло позднее. Интеграции направлений способствует и их активное практическое использование, например, в современной индустриальной технологии и системе стандартов CALS (Continuous Acquisition and Life-cycle Support – непрерывная информационная поддержка жизненного цикла продукта) объединяют различные средства автоматизации проектирования, производства, испытаний и контроля объектов, для чего необходимо решение ряда трудоемких и сложных задач, в том числе формообразование объекта; визуальный контроль объекта на соответствие заданным стандартам и на правиль­ность выполнения операций при сборке; идентификация и манипулиро­вание объектами; сборка объектов, выполняемая роботом под визуаль­ным контролем и др.

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

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

Пусть G - грамматика, L(G) - порождаемый ею язык, a - ис­пользуемое в G множество терминальных символов, из которых могут быть построены. описания объектов из некоторого класса объектов, то есть структура каждого объекта представляется цепочкой терминаль­ных символов Х, принадлежащей множеству всех цепочек , которые можно построить из . Тогда задача лингвистического распознавания заключается в выяснении за конечное число шагов, принадлежит или нет произвольная цепочка множеству L(G).

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

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

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

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