Цифровая геометрия - Digital geometry

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

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

Его основные области применения - компьютерная графика и анализ изображений .

Основные аспекты обучения:

• Построение оцифрованных представлений объектов с упором на точность и эффективность (либо посредством синтеза, см., Например, линейный алгоритм Брезенхема или цифровые диски, либо посредством оцифровки и последующей обработки цифровых изображений).
• Изучение свойств цифровых наборов; см., например, теорему Пика , цифровую выпуклость, цифровую прямолинейность или цифровую плоскостность.
• Преобразование оцифрованных представлений объектов, например (A), в упрощенные формы, такие как (i) скелеты, путем многократного удаления простых точек, так что цифровая топология изображения не изменяется, или (ii) медиальная ось, путем вычисления локальных максимумов в дистанционном преобразовании данного оцифрованного представления объекта или (B) в модифицированные формы с использованием математической морфологии .
• Восстановление «реальных» объектов или их свойств (площадь, длина, кривизна, объем, площадь поверхности и т. Д.) Из цифровых изображений.
• Изучение цифровых кривых, цифровых поверхностей и цифровых многообразий .
• Разработка алгоритмов отслеживания цифровых объектов.
• Функции в цифровом пространстве.
• Набросок кривой, метод рисования кривой по пикселям.

Трассировка кривой на треугольной сетке

Цифровая геометрия сильно перекликается с дискретной геометрией и может рассматриваться как ее часть.

Цифровое пространство

Двумерное цифровое пространство обычно означает двумерное сеточное пространство, которое содержит только целые точки в двумерном евклидовом пространстве. 2D-изображение - это функция в 2D-цифровом пространстве (см. Обработку изображений ).

В книге Розенфельда и Кака цифровая связь определяется как взаимосвязь между элементами цифрового пространства. Например, 4-связность и 8-связность в 2D. Также см. Возможность подключения пикселей . Цифровое пространство и его ( цифровая ) связность определяют цифровую топологию .

В цифровом пространстве независимо друг от друга были предложены непрерывная в цифровом виде функция (A. Rosenfeld, 1986) и постепенно меняющаяся функция (L. Chen, 1989).

Цифровая непрерывная функция означает функцию, в которой значение (целое число) в цифровой точке совпадает или отличается от своих соседей не более чем на 1. Другими словами, если x и y - две соседние точки в цифровом пространстве, | f ( x ) -  f ( y ) | ≤ 1.

Постепенно изменяется функция является функцией от цифрового пространства , чтобы где и действительные числа. Эта функция обладает следующим свойством: если х и у являются две соседние точки в , допустим , то , или . Таким образом, мы можем видеть, что постепенно изменяющаяся функция определяется как более общая, чем непрерывная в цифровом виде функция. ${\ displaystyle \ Sigma}$${\ displaystyle \ {A_ {1}, \ dots, A_ {m} \}}$${\ Displaystyle A_ {1} <\ cdots <A_ {m}}$${\ displaystyle A_ {i}}$${\ displaystyle \ Sigma}$${\ displaystyle f (x) = A_ {i}}$${\ displaystyle f (y) = A_ {i}}$${\ Displaystyle е (х) = А_ {я + 1}}$${\ displaystyle A_ {i-1}}$

Теорема расширения, относящаяся к вышеупомянутым функциям, была упомянута А. Розенфельдом (1986) и завершена Л. Ченом (1989). Эта теорема утверждает: Пусть и . Необходимое и достаточное условие существования постепенно изменялись расширение в это: для каждой пары точек и в , допустит , и у нас есть , где есть (цифровое) расстояние между и . ${\ Displaystyle D \ subset \ Sigma}$${\ displaystyle f: D \ rightarrow \ {A_ {1}, \ dots, A_ {m} \}}$${\ displaystyle F}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle D}$${\ displaystyle f (x) = A_ {i}}$${\ displaystyle f (y) = A_ {j}}$${\ Displaystyle | ij | \ Leq d (х, y)}$${\ Displaystyle д (х, у)}$${\ displaystyle x}$${\ displaystyle y}$

Смотрите также

• Вычислительная геометрия
• Цифровая топология
• Дискретная геометрия
• Комбинаторная геометрия
• Томография

Рекомендации

• А. Розенфельд, "Непрерывные" функции на цифровых изображениях, Письма распознавания образов, т.4, п.3, с. 177–184, 1986.
• Л. Чен, Необходимое и достаточное условие и эффективные алгоритмы для постепенно варьируемого заполнения, Chinese Sci. Бык. 35 (10), стр. 870–873, 1990.

дальнейшее чтение

• Розенфельд, Азриэль (1969). Обработка изображений компьютером . Академическая пресса. ISBN ???.
• Розенфельд, Азриэль (1976). Анализ цифровых изображений . Берлин: Springer-Verlag. ISBN   0-387-07579-8 .
• Розенфельд, Азриэль ; Как, Авинаш С. (1982). Цифровая обработка изображений . Бостон: Academic Press. ISBN   0-12-597301-2 .
• Розенфельд, Азриэль (1979). Языки изображений . Академическая пресса. ISBN   0-12-597340-3 .
• Chassery, J .; А. Монтанвер. (1991). Дискретная геометрия и анализ изображений . Гермес. ISBN   2-86601-271-2 .
• Kong, TY, и A. Rosenfeld (редакторы) (1996). Топологические алгоритмы обработки цифровых изображений . Эльзевир. ISBN   0-444-89754-2 . CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: дополнительный текст: список авторов ( ссылка )
• Восс, К. (1993). Дискретные изображения, объекты и функции в Zn . Springer. ISBN   0-387-55943-4 .
• Герман, Г.Т. (1998). Геометрия цифровых пространств . Бирхаузер. ISBN   0-8176-3897-0 .
• Marchand-Maillet, S .; Ю. М. Шараиха (2000). Двоичная обработка цифровых изображений . Академическая пресса. ISBN   0-12-470505-7 .
• Сойл, П. (2003). Морфологический анализ изображений: принципы и приложения . Springer. ISBN   3-540-42988-3 .
• Чен, Л. (2004). Дискретные поверхности и многообразия: теория дискретно-цифровой геометрии и топологии . SP Computing. ISBN   0-9755122-1-8 .
• Розенфельд, Азриэль ; Клетт, Рейнхард (2004). Цифровая геометрия: геометрические методы анализа цифровых изображений (серия Моргана Кауфмана в компьютерной графике) . Сан-Диего: Морган Кауфманн. ISBN   1-55860-861-3 .
• Чен, Л. (2014). Цифровая и дискретная геометрия: теория и алгоритмы . Springer. ISBN   978-3-319-12099-7 .

внешние ссылки

• Технический комитет IAPR по дискретной геометрии
• Сайт по цифровой геометрии и топологии
• Курс цифровой геометрии и математической морфологии (Ч. Кисельман)
• DGtal: набор инструментов для цифровой геометрии с открытым исходным кодом и библиотека алгоритмов