Цифровая Топология

В классической геометрии точка на плоскости имеет бесконечно много соседей, но компьютер не может обработать бесконечное множество. В компьютере каждая точка плоскости имеет не бесконечно много, но только 4 или 8, в любом случае, конечное число соседей, как кафель на стене.
Растровая матрица описывает локальное конечное множество, где работают другие законы расстояний, площадей, связей и ограничений, в отличие от знакомых нам 2000 лет законов аналитической геометрии. Торжество растровой графики подвигло создание и внедрение нового мышления, которое получило название Цифровая Геометрия или Цифровая Топология (от греческого topos = место).
Без этого мышления невозможно создать профессиональный базис для развития технологий растровой графики.

Пионер и большой авторитет в области Цифровой Топологии – Профессор Владимир Ковалевский www.kovalevsky.de/PublicationsE.htm
Ковалевский исследовал новые проблемы связей и ограничений растровых областей. Он описал новый подход и разработал аксиоматику локально конечных пространств. С помощью клеточной топологии (Cellular Topology) он разработал базовые алгоритмы растровой графики.
Важно: Без базовых знаний Цифровой Геометрии невозможно создание хороших и эффективных программ работы с растровыми Изображениями.

Каждый Пиксел x, y , не находящийся на краю Изображения, имеет четырех соседей первого класса и 4-х соседей 2-го класса. С первыми имеется общий край (забор), со вторыми – только одна точка (угол). Соседей первого класса называют соседской 4-кой, всех соседей обоих классов называют соседской 8-кой. Понятно, что Pixel x,y может сломать забор с одним из своих соседей и с этим участком создать новую область. Однако, это сложно сделать с соседом 2-го класса. Основная аксиома: Элементы 2D-растра нельзя рассматривать, как набор точек, а лишь только, как прямоугольную область, аналогично прямоугольным участкам земли или кафелю в ванной или полю на шахматной доске.

Проблема 8-ки соседей

В Изо1 господствуют соседские 4-ки с четкими отношениями. Изо2 показывает, что 4 единицы также взаимосвязаны через угол, а значит 8-ка соседей воспринимается также, как и 4-ка соседей. Мы воспринимаем эти 4 единицы, как своеобразную область площадью 4, которая разделяет две области, заполненных нулями, не замечая никаких противоречий. Противоречие заключается в отсутствие симметрии между нулями и единицами. Если единицы соединены друг с другом через углы, то нули никак не могут быть соединены через углы, иначе фон смешается с передним планом, что противоречит логике.

Существует две возможности разрешения противоречия:
1) не допускать понятия 8-ки соседей, хотя интуитивно 8-ка должна существовать. Т.е. требуется, чтобы 4-ка соседей должна быть взаимосвязана, как в Изо4.
Плюс: Математически корректно, без противоречий сохраняется симметрия между передним планом и фоном.
Минус: Все диагональные линии должны быть двойными, как в Изо4.

2) принять 8-ку соседей, как данность, но только для переднего плана. На фоне действует только понятие 4-ки соседей.
Плюс: Соответствует визуальной интуиции.
Минус: Асимметрия – единицы и нули не равнозначны. Это означает, что инверсное распределение переднего плана и фона, как в Изо3, ведет к логическому хаосу и должно быть запрещено.

Растр = Клеточный Комплекс из 3D-, 2D-, 1Dи 0D- Клеток

8-ка соседей имеет минимум одну общую точку - угол участка, в то время как 4-ка соседей имеет 2 общие точки и общую границу – забор между участками.
Определения «Граница» и «Угол» дополняются, систематизируются и уточняются через определение «Клетки»:
Для начала необходимо отказаться от наивного представления, что Растр является набором равных и подобных элементов – Пикселей и Вокселей.
Растр (= Клеточный Комплекс), на самом деле, строится на 4-х различных типах Клеток:
- 3-х мерные (= объемные) Клетки = 3D-Cells = Куб или Воксел (Voxel)
- 2-х мерные (= плоскостные) Клетки = 2D-Cells = Кафель или Пиксел (Pixel)
- 1-но мерные (= линейные) Клетки = 1D-Cells = Трещина – Крэк ( engl. cracks )
- 0- мерные (= точечные) Клетки = 0D-Cells = Угол – Точка – Поинт  ( engl. points )

Окаймление: Любая Клетка окаймляется исключительно Клетками нижних размерностей.
Воксель окаймляется не соседними Вокселями, а Пикселями, Крэками и Поинтами.
Пиксель окаймляется не соседними Пикселями, а Крэками и Поинтами.
Крэки окаймляются не соседними Крэками, а Поинтами.

Примеры:
Один Воксел окаймлен 6-ю Пикселами, 12-ю Крэками, 8 Поинтами.
Один Пиксел окаймлен 4-мя Крэками, 4-мя Поинтами.
Один Крэк окаймлен 2-мя Поинтами.

Далее мы ограничимся 2D-Растром, с клеточными типами Пиксел, Крэк и Поинт, хотя все определения имеют смысл и для Вокселной Графики.

Важно: Растровая Графика является не только набором однотипных элементов (типа Пиксел) – она должна рассматриваться, как иерархия элементов, которые окаймляются или нет.

Важное следствие: нельзя кодировать границы между Пикселами вместе с этими Пикселами в одной единственной Матрице – для этого требуются 3 дополнительные Матрицы:
1. Матрица вертикальных Крэков;
2. МатрицагоризонтальныхКрэков;
3. МатрицаПоинтов.

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

Пример 1 : светлый Объект на темном Фоне:

0 означает черный 5 означает высокий и 4 несколько ниже уровень яркости. Все Пиксели > 0 должны принадлежать Объекту.

C2 = Матрица C2-Клеток = Пиксельная Матрица: на переднем плане равномерная область площадью 2, окруженная Фоном. C1V = Матрица вертикальных C1-Клеток = Матрица вертикальных Крэков: кодирует левые и правые границы области. C1H = Матрица горизонтальных C1-Клеток = Матрица горизонтальных Крэков: кодирует 2 крыши и 2 пола области. C0 = Матрица C0-Клеток = Матрица Углов: кодирует 3 верхние точки крыши и 3 нижние точки пола.

Пример 2: серое Изображение B с порогом s = 2:

        1030           0010              00110              0010            00110
B =  1456;  C2 = 0111;  C1V = 01001;  C1H = 0101;  C0 = 01111;
        1300           0100              01100               0011           01111
                                                                          0100           01100

Индексирование Матриц

Четыре матрицы C2, C1V, C1H, C0 заменяют соглашение о равноправии соседских 4-к или 8-к. Когда одна C0-Клетка находится между двумя C2-Клетками, соединенными через угол и содержащими единицы – то эти Клетки соединены, а если содержат нули, то разъединены. Пример: Пиксели 1,2,3,4,5 соединены вместе, так как существует путь через C0-Клетки от 1 до 5 Пиксела. Они образуют одну область. Однако, Пиксели Pixel 6,7,8 и 9 находятся в растре не связанными, так как они не соединены C0-Клетками.

Проблема 1: Так как Графическая Карта обычно работает с C2-Матрицами в памяти, C0-Клетки невидимы, и мы можем лишь следовать свей интуиции предполагая, что в верхнем примере все Пиксели от 1 до 9 связаны. (Интуитивное соглашение соседской 8-ки).

Проблема 2: Следуя теории, необходимы непомерные объемы памяти под 4-е матрицы для полного и последовательного кодирования границ области.
Решение: Создавать матрицы, которые абсолютно необходимы и не всегда все четыре. Как правило, это только C2-Матрица и для Цепного Кода (Chain-Code – см ниже) C1V-Матрица.
C0-Матрицу обычно заменяют на соглашение о равноправии соседских 4-ки или 8-ки. Если соглашения нет, то по умолчанию используется равноправие 8-ки.

Проблема 3: неравное количество колонок и строк. Для кодирования Крэков и Поинтов на правой и нижней границах используются дополнительные колонки и строки в C1V- и C1H-Матрицах и C0-матрица аналогично.
Решение: стереть последние колонку и строку (т.е. сравнять с Фоном). При этом не возникнет никаких ограничений на правой и нижней границах и можно опустить дополнительные колонки и строки в C1V, C1H и C0, так как они все равно содержат только нули.

Если установлено какое-то единство соседей (4-ки или 8-ки), то каждая из 4-х матриц содержит одинаковое количество информации. Мы можем каждую из матриц получить из другой матрицы. Это разумно, если мы хотим видеть границы областей. C1V-, C1H- и C0-матрицы можно также, как C2-матрицы загрузить в Видео-память Графической Карты и сразу увидеть корректные границы областей.

Старый Цепной Код = Freeman Code: неверный, но популярный 

Пример

Код Фримана = Цепной Код с 8-ю направлениями популярен с 1970-го года. Он кодирует Пиксельную Цепь через x- и y- координаты – стартовый Пиксел и затем цепь по 8-ми направлениям к его последователям. Код направлений: от 0 по часовой стрелке с шагом 45 градусов: 000,001,010,011,100,101,110,111.

Плюс Кода Фримана: низко редундантное кодирование границ областей через цепочку Пикселей.

Проблема: Цепочки Пикселей противоречат принципу Окаймления и поэтому фундаментально не подходят для кодирования границ областей по следующим причинам:

Пример: Окаймление четырёхугольника 3x4 через Код Фримана Проблема 1: Пиксел имеет площадь, но правильные границы должны быть бесконечно тонкими линиями. Проблема 2: Правильная граница области лежит между внутренней и внешней цепочкой Пикселей. Непонятно какая из двух цепочек точнее представляет границу. Проблема 3: Непонятно - что должна означать внутренняя и внешняя граница небольшой области – типа граница одного единственного Пиксела. Проблема 4: Непонятно – где должна проходить внешняя граница области, если она лежит на границе Изображения.

Вывод: Код Фримана устарел и должен быть повсеместно заменен на Цепной Код -
Chain Code - Crack Code с 4-мя направлениями.