Книги по разным темам Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 82 |

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

Соседние пары определяют конечную разность третьего порядка.

Если конечные разности второго порядка не равны нулю (для целочисленних значений координат точек конечные разности должны быть больше 1), то не исключено, что пары отрезков цифровых прямых являются частью дуги цифровой кривой. Вообще, через три точки, определенные парой отрезков, можно провести много кривых. Тем не менее, как уже отмечалось, длины высот сегментов дуг кривых, которые соотвествуют отрезкам вписанной ломаной линии, не должны превышать значения дискретности пространства d. Таким образом, для того чтобы считать пары отрезков цифровых прямых T T, n-1 n T T частью дуги цифровой кривой, необходимо n n+установить существование кривой, которая проходит через точки T, T, T, такой, для которой выполняется условие:

n-1 n n+(h

n-1 n Кривизну плоской кривой обычно отождествляют с Рис. 5 Оценка величины отклонения кривизной соприкасающейся окружности [7].

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

На основании приведенных соображений можно сформулировать следующее определение:

Под дугой цифровой кривой в двумерном дискретном пространстве дискретности d будем понимать такую последовательность отрезков цифровых прямых, что через конечные три XII-th International Conference "Knowledge - Dialogue - Solution" точки каждой пары соседних отрезков можно провести такую окружность, что высота сегментов этой окружности для соседних отрезков не превышает d.

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

Построив окружность в соответствии с определением дуги цифровой кривой по точкам T,T,T, n-1 n n+сделаем оценку величины отклонения конца каждого такого отрезка от направления линии предшествующего отрезка (рис. 5). Величиной отклонения может служить длина отрезка T T' при n+условии, что l(Tn'')l(T,T ). Определим сначала длину отрезка Tn - высоты треугольника T T T. Как n n+1 2 n-1 n n+уже было отмечено, максимальное расстояние между точками линий дуги кривой и соответствующего отрезка цифровой прямой SR = d. В то же время SR = OT 1 1 n-1 - OT cos = r - r cos = r(1- cos ). Длина n-высоты (T T T ) Tn = OT cos 2 = r - r cos = r(1- cos 2) = 2r(1- cos2 ). Tn / SR = 2(1 + cos n-1 n n+1 2 n - OT n 2 ); или Tn = 2(1 + cos ) SR. Если SR d и 30, то высота треугольника (T T T ) Tn 3,85.

2 1 1 n-1 n n+1 2 d Нетрудно видеть, что максимальное отклонение T T' = 2 T R 7. 7d. (4) n+1 n Это означает, что для того, чтобы рассмотренная пара отрезков могла быть отнесена к дуге цифровой кривой необходимо, чтобы величина максимального отклонения Tn' не превышала бы 7.7d. Минимальная величина отклонения T T' > d, поскольку n+при меньшем значении отклонения направления отрезков T T и T T n-1 n n n+неотличимы, и пара отрезков разных Рис.6 Сегментация объектов с использованием направлений превращается в один отрезок предлагаемых методов прямой. Величина отклонения d < g = T T' n n+< 7.7d также является значением второй конечной разности на сегменте контура T T T, в точке T при n-1 n n+1 n условии, что данный сегмент есть частью дуги кривой.

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

Заключение Рассмотрено построение образа отрезка цифровой прямой, как частного случая растущей пирамидальной сети [5] с учетом концептуальной модели опознавания и памяти [4].

Предложено определение дуги цифровой кривой как последовательности отрезков цифровых прямых [3].

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

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

итература [1] Kovalevsky V.A. Applications of Digital Straight Segments to Economical Image Encoding, In Proceedings of the 7th International Workshop, DGCIТ97, Montpellier, France, December 3-5, 1997, Springer 1997, Р. 51-62.

[2] Вишневский В.В., Калмыков В.Г. Структурный анализ цифровых контуров изображений как последовательностей отрезков прямых и дуг кривых. // Искусственный интеллект 4Т2004, Институт проблем искусственного интеллекта НАНУ - Донецк: "Наука и образование" 2004 С.450-Neural and Growing Networks [3] Власова Т.М., Калмыков В.Г. Алгоритм и программа распознавания контуров изображений как последовательности отрезков цифровых прямых // Математичн машини системи. - 2005. -№4 С.84-[4] Рабинович З.Л. О естественных механизмах мышления и интеллектуальных ЭВМ // Кибернетика и системный анализ. - 2003. -№5 С.82-[5] Гладун В.П. Планирование решений. - Киев: Наукова думка, 1987. - 167с.

[6] Макаров И.П. Дополнительные главы математического анализа. - Москва: Просвещение, 1968.

[7] Корн Г. и Корн Т. Справочник по математике для научных работников и инженеров. - Москва: Наука, Информация об авторе Владимир Калмыков - старший научный сотрудник, кандидат технических наук, Институт проблем математических машин и систем, просп. акад. Глушкова 42, 03680, Киев 187, Украина;

e-mail: kvg@immsp.kiev.ua ТЕХНОЛОГИИ КОМПРЕССИИ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ Николай Б. Фесенко Abstract: The>

Keyword: semantics, abundance, compression, graphical information, decompression,>

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

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

XII-th International Conference "Knowledge - Dialogue - Solution" Виды информационной По вероятности повторения По составу избыточности распределения порядковая смешанная однородная позиционная групповая повторения По элементу избыточности по форме размещения По принципу сжатия символьная объектная линейная по содержанию (семантическая ) 2D по форме организации 2.5D 3D По происхождению По степени связности целенаправленная систематическая сильно связанная случайная несвязанная слабо связанная порождающая зависимая Рис.1 Классификация информационной избыточности.

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

Neural and Growing Networks Основные виды избыточности[2] близки для символьной и графической форм представления информации. При этом для каждого вида избыточности существуют свои модели сжатия. Моделирование в той или иной степени отражает возможность предсказания вероятности наступления возможных событий. По вероятности повторения, когда разные события имеют разные вероятности своего появления, то имеет место избыточность распределения. Если несколько одинаковых событий могут следовать друг за другом, то имеет место избыточность повторения. Избыточность порядка появляется тогда, когда наступление определенных событий можно предсказать в зависимости от некоторого порядка следования. Повторение группы событий приводит к групповой (цепочной) избыточности. Возможность учета вероятности появления определенных событий в некоторых позициях потока событий определяет позиционную избыточность. Вероятность близости значений соседних пикселей графического изображения, как и их пространственных производных, характеризует пространственную избыточность по форме размещения: линейную, 2D, 2.5D, 3D. По составу реже встречается однородная избыточность, чаще - смешанная. По элементу избыточности проявляется символьная и объектная. По принципу сжатия будем различать избыточность по форме организации размещения, или расположения символа или образа, и семантическую, или смысловую избыточность по содержанию. По происхождению выделим целенаправленную, или преднамеренную избыточность, случайную, порождающую и систематическую. По степени связности отметим несвязанную, или независимую избыточность, и зависимую, которая может быть как слабо связанной, так и сильно. Из проведенного анализа и классификации избыточности следует, что менее других исследован семантический аспект избыточности.

Разновидности семантической избыточности Проведем анализ видов семантической избыточности и выполним их классификацию для определения задач по созданию технологии семантической компрессии графической информации (рис.2).

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

Анализ и классификация технологий сжатия графической информации С целью систематизации проведем анализ и общую классификацию технологий сжатия графической информации (рис.3). По форме представления графической информации будем различать растровую, векторную, программную, текстовую, мультимедийную и комбинированную формы представления. Растровая форма характеризуется значительной пространственной избыточностью. Тип избыточности векторной формы зависит от большого числа факторов и не обладает достаточной универсальностью для создания общих формальных подходов к ее устранению [2]. Среди форматов векторной графики выделим два: CDR (CorelDRAW) и DXF (AutoCAD), которые являются стандартами для соответствующих графических пакетов. Помимо растровых, векторных, текстовых форматов, разработаны также смешанные форматы, или метафайловые. Например, форматы ESP (Encapsulated PostScript) и CGM (Computer Graphics Metafile) позволяют хранить растровые, векторные и текстовые данные. Универсальные файлы данных UDF (Universal Data File) охватывают различные структуры данных и могут входить в состав документов, реализованных в других форматах.

Pages:     | 1 |   ...   | 9 | 10 | 11 | 12 | 13 |   ...   | 82 |    Книги по разным темам