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

Имеет дело с оцифрованными моделями или изображениями объектов 2D или 3D евклидова пространства.

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

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

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

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

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

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

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

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

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

В цифровом пространстве независимо были предложены цифровая непрерывная функция (А. Розенфельд, 1986) и постепенно меняющаяся функция (Л. Чен, 1989).

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

Постепенно меняющаяся функция — это функция из цифрового пространства туда, где и — действительные числа. Эта функция обладает следующим свойством: Если x и y — две соседние точки в , предположим , то , или . Итак, мы видим, что постепенно меняющаяся функция определяется как более общая, чем непрерывная в цифровом виде функция. ${\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 f(x)=A_{i+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 |i-j|\leq d(x,y)}$ ${\displaystyle d(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

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

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

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

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

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

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

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

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