AlgART / Тексты
Теорема связности для параллельной скелетизации растрового изображения
Даниэль Алиевский
ОГЛАВЛЕНИЕ
- Введение
- Теорема связности: формулировка для скелетов 3x5
- Теорема связности: доказательство для скелетов 3x5
- Примеры алгоритмов скелетизации с апертурой зависимости 3x5
Традиционный подход к построению скелета (остова) растрового бинарного изображения основан на цикле итераций «истончения». А именно, на каждой итерации изображение немного «истончается», т.е. со всех сторон объектов, присутствующих на изображении, «снимается» однопиксельный граничный слой, если пока объект не превратится в набор тонких однопиксельных линий. Начиная с некоторой итерации на изображении остаются только тонкие однопиксельные линии, которые алгоритм скелетизации отказывается изменять («истончать») далее. С этого момента изображение перестает изменяться, и это служит критерием окончания цикла. Полученное изображение считается скелетом исходного изображения. Одно из важнейших применений скелетов — векторизация остова изображения, так как в системе тонких однопиксельных линий относительно легко распознать узловые точки и соединяющие их линии, которые можно аппроксимировать теми или иными кривыми.
В данной статье рассматривается фундаментальная проблема: связность скелета. Как правило, к скелетизирующему алгоритму предъявляется требование: один связный объект в результате скелетизации должен превратиться в связную систему тонких линий. Иначе говоря, алгоритм не должен «рвать» объект на несвязные части. Очевидно, достаточно гарантировать, что связность сохраняется на каждой итерации скелетизации. Мы сформулируем и докажем теорему связности, позволяющую механически (при помощи соответствующей переборной программы) гарантировать, что одна итерация скелетизации сохраняет связность. Теорема доказывается для случая параллельных алгоритмов обработки, т.е. допускающие параллельную обработку различных пикселов исходного изображения.
Введение
Будем считать, что бинарное изображение представлено битовой матрицей: каждый пиксел представлен элементом матрицы 0 или 1, причем нулевые элементы представляют «фон», а единичные — «объекты». Как правило, биты хранятся в упакованной форме, по 32 или 64 бита в одном машинном слове. Это важно для экономии памяти при обработке больших изображений.
В соответствии с «компьютерной традицией», будем считать, что ось x направлена вправо, а ось y вниз, т.е. «сверху» значит «в направлении уменьшения y». Мы часто будем использовать такие выражения, как «пиксел справа дважды сверху» по отношению к пикселу (x, y), подразумевая пиксел с координатами (x+1, y−2).
Говоря о «размерах» AxB матрицы, прямоугольной апертуры или окрестности, мы будем подразумевать, что горизонтальный размер равен A, а вертикальный размер равен B.
Если не оговорено противное, под связностью мы будем понимать 8-связность некоторого множества единичных пикселов. Иначе говоря, связной компонентой на изображении мы считаем такое множество единичных пикселов, что любые два его элемента можно соединить 8-связной цепочкой единичных пикселов из этого множества и в него больше нельзя добавить элементы без нарушения этого условия. При этом 8-связной цепочкой называется такая цепочка, в которой соседние пикселы являются соседями: обе их координаты отличаются не более чем на 1. (У одного пиксела может быть не более 8 таких единичных соседей.) Связная компонента является формализациией понятия «объект на изображении»
Данная статья посвящена следующей проблеме: удостовериться, что некий скелетизирующий алгоритм не нарушает связность, т.е. что после выполнения одной итерации алгоритма на месте одной связной компоненты в матрице, получаемой в результате итерации, не возникает двух или более связных компонент.
Существует достаточно простой способ гарантировать связность. Нужно построить алгоритм «истончения», принимающий решение об удалении (обнулении) конкретного граничного пиксела таким образом, чтобы в некоторой окрестности этого пиксела, например, 3x3 или 5x5, гарантировалось сохранение связности конфигурации внутри этой окрестности. Например, если 3x3-окрестность пиксела имеет вид
0 1 1
0 1 1
0 0 0
то очевидно, что обнуление центрального пиксела не нарушит связности: связная компонента изображения, содержавшая ее, остается связной компонентой. А в конфигурации
1 0 0
0 1 1
1 1 1
обнуление центрального пиксела приводит к «отрыву» левого верхнего пиксела от нижней половины, и есть риск, что связная компонента окажется разъединенной («разорванной») на две части.
Если есть алгоритм, принимающий решение об удалении конкретного пиксела, и этот алгоритм гарантирует, что в пределах окрестности определенного размера удаление центрального пиксела не нарушает связность, то мы можем последовательно, пиксел за пикселом, применить такой алгоритм ко всем пикселам изображения, всякий раз записывая результат (нулевой элемент) в исходную битовую матрицу. Поскольку на каждом шаге алгоритма связность не нарушается, то она не нарушается вообще.
Однако, такие последовательные алгоритмы обладают существенным недостатком: они принципиально медленные. За один шаг алгоритма модифицируется лишь один пиксел изображения, причем если пикселы хранятся упакованными в биты машинного слова, то отдельная операция коррекции пиксела «обходится» довольно дорого. Кроме того, такой алгоритм с трудом поддается распараллеливанию на многопроцессорных или многоядерных компьютерах.
В данной статье мы рассматриваем другой тип алгоритмов, которые естественно назвать параллельными. Мы называем параллельным алгоритм, преобразующий исходную битовую матрицу в результирующую битовую матрицу такого же размера, если результат преобразования в точке (x0, y0) является однозначной функцией от значений элементов исходной матрицы в некоторой апертуре, или окрестности точки (x0, y0) фиксированного размера (обычно 3x3, 3x5 или 5x5). Главное отличие от последовательного алгоритма: результат обработки зависит только от элементов исходной матрицы, но не зависит от пикселов результирующей матрицы (которые, возможно, были обнулены перед обработкой текущего пиксела). Параллельный алгоритм, во-первых, позволяет за одну машинную операцию обрабатывать все биты машинного слова, т.е. минимум 64 бита для большинства современных процессоров, причем такая операция обычно проще (эффективнее), чем доступ к отдельному биту в слове. Во-вторых, параллельный алгоритм, действительно, легко распараллеливается на многопроцессорных или многоядерных компьютерах: каждый процессор может обрабатывать свою часть матрицы. В итоге, ускорение по сравнению с простым последовательным алгоритмом на современных компьютерах может достигать сотен и даже тысяч раз.
Для параллельных алгоритмов поставленная проблема, т.е. доказательство связности получаемого скелета, становится нетривиальной. Например, в следующей конфигурации 3x5 нет очевидных причин, по которым нельзя удалить (обнулить) центральный пиксел — его удаление не нарушает связности конфигурации 3x5:
0 1 1
1 0 1
0 1 1
1 0 1
0 1 1
Однако, если допустить удаление центрального пиксела в любой такой конфигурации 3x5, то в более сложной конфигурации 3x7
0 1 1
1 0 1
0 X 1
1 0 1
0 X 1
1 0 1
0 1 1
центральный левый пиксел окажется «оторванным» и связная компонента распадется на две.
Теорема связности: формулировка для скелетов 3x5
Итак, мы рассматриваем некоторую операцию преобразования исходной битовой матрицы в результирующую битовую матрицу такого же размера, такую, что результат преобразования в точке (x0, y0) является функцией от значений элементов исходной матрицы в некоторой апертуре зависимости:
x0−a ≤ x ≤ x0+b,
y0−c ≤ y ≤ y0+d,
где a,b,c,d — некоторые неотрицательные константы (обычно 1 или 2). Эту операцию мы будем называть итерацией скелетизации. Если апертура имеет размеры AxB (A=a+b, B=c+d), то такой алгоритм мы будем называть скелетом AxB: например, при a=b=c=d=2 имеем скелет 5x5, при a=b=1, c=d=2 имеем скелет 3x5, при a=b=c=d=1 имеем скелет 3x3.
Неформально предполагается, что итерация удаляет (обнуляет) некоторые единичные элементы, находящиеся на границах «объектов» — связных компонент исходной матрицы.
Более того, мы будем неформально предполагать, что рассматриваемая итерация удаляет граничные пикселы конкретно с левого края объектов, не трогая «правые края». Это требование (формализованное ниже в виде «условия левого края») будет нужно для доказательства, но оно не ограничивает общность реальных алгоритмов. На практике обычно конструируются 4 отдельных алгоритма, удаляющих пикселы с левого, верхнего, правого и нижнего края объектов, совершенно идентичные с точностью до симметрии или поворота системы координат, и такие итерации применяются последовательно, обеспечивая равномерное «истончение» с разных сторон. Очевидно, достаточно доказать, что связность сохраняется в каком-то одном из 4 алгоритмов, и для определенности мы будем рассматривать алгоритмы «истончения слева».
Будем говорить, что итерация скелетизации сохраняет связность данной связной компоненты D исходной матрицы, если множество единичных пикселов в матрице — результате итерации, — лежащих внутри D, состоит не более чем из одной связной компоненты. Наоборот, будем говорить, что итерация разрушает связность данной связной компоненты D исходной матрицы, если множество единичных пикселов в матрице — результате итерации, — лежащих внутри D, состоит из двух или более связных компонент. Заметим, что полное уничтожение (обнуление) связной компоненты не считается ее разрушением.
Следующая теорема позволяет механически, путем соответствующей программы перебора, проверить, что тот или иной алгоритм скелетизации, выполняющий определенные «разумные» условия, сохраняет связность.
Теорема связности. Для определенного, заранее известного набора размеров Qxi x Qyi, i=1,2,...,M, верно следующее: при выполнении алгоритмом определенных предположений (перечисленных далее условий), если итерация разрушает связность какой-нибудь связной компоненты, то существует прямоугольная область матрицы одного из указанного набора размеров, такая, что после обнуления всех пикселов вне этого прямоугольника в исходной матрице итерация по-прежнему разрушает связность какой-нибудь связной компоненты.
Таким образом, располагая набором размеров Qxi x Qyi, мы можем написать программу-тест, которая по очереди протестирует все возможные конфигурации таких размеров, дополненные со всех сторон достаточным количеством нулевых пикселов (в соответствии с размерами апертуры зависимости: a нулевых столбцов матрицы слева, b нулевых столбцов справа, c нулевых строк сверху, d нулевых строк снизу), и для каждой такой конфигурации проверит, что алгоритм скелетизации не разбивает на части ни одную из связных компонент, присутствующих в исходной матрице. Если это так, то теорема связности позволит сделать вывод: данный алгоритм скелетизации никогда не нарушает связности связных компонент, и циклическое повторение таких итераций скелетизации позволяет получить корректный связный скелет (остов) любой связной компоненты произвольного размера. Полное количество возможных конфигураций битов размером Qxi x Qyi составляет 2Qxi x Qyi, и если эти размеры не слишком велики, то полную проверку можно произвести за обозримое время от нескольких секунд до нескольких суток.
Соответствующий набор размеров выясняется в процессе доказательства. При тех предположениях, которые мы сформулируем ниже, теорема выполняется для набора, состоящего из двух вариантов размеров 3x7 и 4x6, что означает необходимость проверки всего лишь 221+224 возможных конфигураций: при грамотной реализации это требует на современных компьютерах не более нескольких секунд.
Ниже приведен набор предположений (условий), которыми мы будем пользоваться.
Условие конечности. Мы рассматриваем матрицы только конечного размера и считаем, что размеры любой связной компоненты конечны: «за пределами» матрицы пикселы предполагаются равными нулю. (На практике, чтобы не замедлять алгоритм лишними проверками, матрица обычно фактически дополняется по краям нужным числом нулевых битов, т.е. на 1 справа и слева и на 2 сверху и снизу, в соответствии с размером окрестности из приведенного ниже условия зависимости от апертуры 3x5.) Конечность нам понадобится, чтобы в самом начале доказательства обеспечить существование цепочки L минимальной меры.
Условие левого края. Если единичный пиксел исходной матрицы обнуляется в результате итерации, то верно хотя бы одно из следующих утверждений:
- пиксел слева от него в исходной матрице был нулевым
- или оба пиксела слева сверху и слева снизу от него в исходной матрице были нулевыми.
Условие правой локальности. Если единичный пиксел исходной матрицы обнуляется в результате итерации, то верно хотя бы одно из следующих утверждений:
- результат итерации содержит единичного соседа в одной 5 позиций справа сверху, справа снизу, сверху или снизу от этого пиксела,
- или, быть может, этот единичный был изолированным пикселом, т.е. связной компонентой из 1 пиксела (все его 8 соседей в исходной матрице были нулевыми).
Условие нерасширения. Нулевой пиксел исходной матрицы всегда остается нулевым в результате итерации (соответственно, единичному пикселу результата всегда соответствует единичный пиксел в исходной матрице).
Условие зависимости от апертуры 3x5. Результат итерации скелетизации в точке (x0, y0) зависит, максимум, от окрестности 3x5: x0−1 ≤ x ≤ x0+1, y0−2 ≤ y ≤ y0+2.
Условие правой локальности здесь наименее тривиально: оно означает, что скелетизация не является «слишком сильной» и не пытается «срезать» за один раз более чем однопиксельный «слой» единичных пикселов с левой стороны объектов. Оговорка насчет изолированных пикселов позволяет включить в рассмотрение скелетизирующие алгоритмы, которые не только истончают «толстые» объекты, но и укорачивают свободные концы тонких линий вплоть до полного их исчезновения — сохраняя, впрочем, замкнутые циклы (кольцевые линии).
Условие левого края означает, что мы работаем только с левым краем объектов — не пытаемся, в частности, удалять внутренние пикселы больших объектов. Чтобы оценить, насколько «сильное» это условие, заметим: если это условие не выполнено, а также не выполнены аналогичные условия верхнего края, правого края и нижнего края, получаемые при симметриях или поворотах системы координат — иначе говоря, если все 4 алгоритма «истончения», удаляющих пикселы с левого, верхнего, правого и нижнего края объектов, не могут удалить пиксел из-за нарушения этого условия — то легко убедиться, что 3x3-окрестность данного пиксела в исходной матрице имеет один из следующих видов:
1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1
Во всех этих конфигурациях центральный пиксел лежит в каком-то смысле «глубоко внутри» большого единичного массива, и даже если у него есть нулевой диагональный сосед, то с неформальной точки зрения представляется гораздо разумнее вначале удалить смежного с этим нулевым пикселом соседа по горизонтали или вертикали, прежде чем пытаться обнулить центр. Действительно, из этих схем видно, что указанные соседи по горизонтали или вертикали (они выделены жирным шрифтом) ни в каком смысле не лежат на тонких однопиксельных линиях, которые хороший алгоритм скелетизации должен сохранять.
Условие нерасширения означает, что алгоритм не пытается добавлять единичные пикселы, т.е. это действительно «истончение», а не «расширение».
Условие зависимости от апертуры 3x5 ограничивает нас рассмотрением скелетизирующих алгоритмов, которые мы назвали выше «скелеты 3x5». (Естественно, соответствующие итерации для истончения сверху и снизу, получаемые из данной итерации симметрией или поворотом системы координат, окажутся скелетами 5x3.) Конечно, тем самым мы включаем в рассмотрение также все скелеты с меньшей апертурой зависимости, например, 3x4 или 3x3. При желании, можно сформулировать и доказать аналогичную теорему для бо́льших размеров апертуры зависимости, например, 5x5 или 5x7, что приведет к соответствующему увеличению размеров конфигураций Qxi x Qyi, подлежащих проверке. Но на практике вполне качественные скелетизирующие алгоритмы можно построить уже в рамках апертуры 3x5.
Разумеется, условия левого края, правой локальности и нерасширения можно проверить механически в соответствующей программе-тесте. Для условий левого края и нерасширения достаточно протестировать все возможные конфигурации пикселов 3x5 и проверить выполнение условия в случае изменения центрального пиксела. Для условия правой локальности достаточно проверить все возможные конфигурации 4x7, получаемые расширением базовой конфигурации 3x5 вправо, вверх и вниз на 1:
? ? ? ? ? ? ? ? ? n n ? ? x n ? ? n n ? ? ? ? ? ? ? ? ?
ибо 5 соседей пиксела “x”, поведение которых нуждается в проверке на соответствие условию правой локальности, помеченные выше буквой “n”, как и поведение самого пиксела “x”, полностью определяются пикселами указанной конфигурации 4x7. Тестирование всех 228 конфигураций 4x7, в отличие от проверки связности, практически не требует работы с отдельными битами и может быть выполнено на современных компьютерах за несколько секунд.
Вместо условия правой локальности можно сформулировать более слабое условие, которые является его непосредственным следствием и которое также можно механически проверить:
Условие локальности. Если итерация обнуляет некий единичный пиксел, то в результат итерации сохраняется хотя бы один единичный среди всех 8 соседей этого пиксела (за исключением единственной возможной ситуации, когда этот пиксел был изолированным, т.е. представлял собой связную компоненту из 1 пиксела).
В некоторых местах доказательства нам будет достаточно этого более слабого условия.
Теорема связности: доказательство для скелетов 3x5
Общие замечания
Предположим, итерация скелетизации разрушила связность некоей связной компоненты D. Очевидно, что в этом случае компонента содержит более 1 пиксела. Пусть эта связная компонента D сократилась до подмножества D', состоящего из двух (или более) связных подмножеств D'1, D'2, D'3, ... Чтобы доказать теорему, нам нужно либо прийти к противоречию, либо найти конкретную прямоугольную область (апертуру) Qx x Qy, такую, что после обнуления всех пикселов вне этого прямоугольника связность хотя бы одной связной компоненты по-прежнему разрушается.
Будем рассматривать 8-связные цепочки пикселов
Будем для краткости писать «цепочка AxB», имея в виду, что максимальная разница x-координат равна A, а максимальная разница y-координат равна B. Будем называть A шириной цепочки, а B высотой. Например, цепочка 2x0 — три последовательных пиксела по горизонтали, ширина 2, высота 0.
Введем следующее отношение порядка («выгодности») для цепочек.
- Будем считать, что одна цепочка выгоднее другой, если в ней меньше точек (N).
- Будем считать, что среди цепочек с равным числом точек выгоднее та, у которой меньше высота.
- Будем считать, что при равном числе точек и равной высоте более выгодна та цепочка, у которой центр тяжести расположен правее, т.е. та, у которой среднее арифметическое всех x-координат больше (не меньше, а именно больше).
Легко видеть, что «выгодность» цепочки и обратной ей цепочки LN,LN−1,...,L2,L1 одинаковы, т.е. одинаковы все указанные величины.
Введем для удобства какую-нибудь вещественную положительную меру цепочки, такую, что у более выгодных цепочек эта мера меньше, а если ни одна не выгоднее другой, то мера одинакова. Такую меру можно ввести благодаря конечности наших матриц («условие конечности»); один из возможных способов —
Выберем какую-нибудь цепочку пикселов
Введем следующую систему обозначений пикселов:
0равен 0 в исходной матрице, 0 в результате итерации (по полной исходной матрице); xравен 1 в исходной матрице, 0 в результате итерации; 1равен 1 в исходной матрице, 1 в результате итерации; -(знак минус)равен 1 в исходной матрице, неизвестно значение в результате итерации (т.е. либо “ x”, либо “1”);oнеизвестно значение в исходной матрице, 0 в результате итерации (т.е. либо “ x”, либо “0”);=неизвестно, чему равен, но одинаковое значение до и после итерации; .(точка)все остальные случаи (ничего не известно); Iто же, что 1, если мы уверены, что это первый элемент цепочки L1; Jто же, что 1, если мы уверены, что это последний элемент цепочки LN; iто же, что 1, если мы уверены, что эта точка принадлежит связной компоненте D'I (той же, что и L1); jто же, что 1, если мы уверены, что эта точка принадлежит связной компоненте D'J (той же, что и LN); I?I?I?и т.п.один из этой серии пикселов “ I” (L1), остальные “.”
Далее мы будем работать с некоторыми апертурами (прямоугольными областями) на исходной матрице и соответствующей ей матрице — результате итерации скелетизации. При этом мы будем ставить восклицательный знак ! справа от пикселов, находящихся в центральной области рассматриваемой апертуры, т.е. той области, в которой результат итерации скелетизации не зависит от пикселов вне апертуры. В силу условия зависимости от апертуры 3x5, это пикселы, удаленные как минимум на 1 от левого и правого края апертуры и как минимум на 2 от верхнего и нижнего края. Для минимальной апертуры 3x5 это единственный центральный пиксел.
Иногда вместо точки “.” мы будем ставить вопросительный знак “?”, чтобы отметить, какой пиксел мы в данный момент исследуем.
Заметим, что вариант, когда 0 превращается в 1, невозможен (условие нерасширения). Таким образом, следующие наборы вариантов являются взаимоисключающими:
“0” или “x” или “1”;
“0” или “−”,
“o” или “1”.
Заметим также, что “=” равносильно “0” или “1” и несовместимо с “x”.
Пользуясь введенными обозначениями, можно заменить условие левого края следующими утверждениями, которые мы обычно и будем применять на практике (первое из них является просто иной формулировкой условия левого края):
- P1: если пиксел “
x”, то слева от него “0” либо и слева сверху, и слева снизу “0”; - P2: если два пиксела один под другим оба “
−”, “1” или “x”, то оба пиксела справа от них суть “=” (иными словами, “0” или “1”). Очевидно, то же самое можно сказать про вертикальный ряд пикселов большей длины.
Также мы будем пользоваться следующими простыми леммами:
Лемма Sa. В случае горизонтальной цепочки “x x”, над и под левым “x” пикселы по P1 всегда “0”:
0 .
x x
0 .
Лемма Sb. Горизонтальная цепочка “x x x” невозможна — ибо в силу P1 над и под левым и центральным “x” придется поставить “0”, и условие правой локальности окажется нарушено для левого “x”.
Мы будем рассматривать различные прямоугольные области некоторого размера Qx x Qy, внутри которых, как правило, по предположению присутствуют пикселы из разных связных компонент D'K; мы будем также называть эти области апертурами. Мы будем обнулять пикселы в исходной матрице вне апертуры и проверять: может ли в результате итерации скелетизации из-за такого обнуления добавиться новая связь-цепочка, соединяющая разные связные компоненты, сохранившиеся после обнуления (т.е. может ли там быть связь, если мы знаем, что до обнуления связи не было). Если не может, значит, мы докажем теорему для случая размера области Qx x Qy и заодно обнаружим очередной размер Qxi x Qyi, который надо тестировать. Уточним это неформальное рассуждение.
Для краткости будем называть матрицу, которая получается из исходной матрицы после обнуления всех пикселов вне рассматриваемой апертуры Qx x Qy, обнуленной (в противоположность исходной).
Заметим, что пикселы типов “0” (в том числе “0!”), “x!” и “o!” обладают прекрасным свойством: они не могут изменить своего поведения ни при каких коррекциях других пикселов в матрице вне рассматриваемой апертуры. А именно, в результате итерации на обнуленной матрице они точно так же будут нулевыми.
Назовем забором любую 4-связную цепочку, состоящую из пикселов указанных типов “0” (в том числе “0!”), “x!” или “o!” , если такая цепочка обоими концами упирается в край апертуры, разбивая ее тем самым на две несвязные части. Подчеркиваем, что в отличие от цепочки L забор должен быть именно 4-связной цепочкой, т.е. такой, в которой смежные элементы отличаются на 1 только по одной координате — 4-связность обеспечивает разбиение апертуры на несвязные, в обычном 8-связном смысле, области. Будем говорить, что забор отгораживает или разделяет два пиксела A и B типа “1”, принадлежащие разным связным компонентам результата скелетизации D'A и D'B и лежащие в нашей апертуре, если эти два пиксела находятся по разные стороны забора. Вот пример:
. . . . 0 . . . . A . 0 . . . 1!o!x!o!. . 0 o!o!. x!1!. . . . . . B . . . . . . . .
Предположим, до итерации пикселы A и B, лежащие по разные стороны забора, были соединены какой-либо связью в рамках апертуры (8-связной цепочкой из пикселов типа “1”, “x”, “−”; в нашем примере это диагональная цепочка “A x! x! B”). Обозначим С' пересечение исходной связной компоненты D с этой апертурой (это уже не обязательно одна связная компонента). Далее, пикселы A и B принадлежат С' и при этом, по предположению, связаны между собой на исходной матрице в рамках апертуры; обозначим C связную компоненту С', содержащую эти пикселы.
Очевидно, забор разделяет компоненту C на две заведомо не связанные друг с другом части CA и CB: A принадлежит одной части CA, а B другой части CB. После итерации на обнуленной матрице, конечно, точка А может исчезнуть (если только она не лежит в центральной области, где результат итерации не зависит от пикселов вне апертуры). Но в этом случае, в силу условия локальности, у нее сохранится единичный сосед, также принадлежавший до итерации связной компоненте C (как и любой единичный сосед любого элемента C). Действительно, легко видеть, что исключительная ситуация, оговоренная в условии локальности, не имеет места: A не была изолированной одноточечной связной компонентой (напротив, в содержавшей ее связной компоненте C было не менее 3 пикселов A, B и пикселы соединявшей их цепочки). Причем сохранившийся единичный сосед не может оказаться на самом заборе: забор после итерации скелетизации состоит только из нулей как для исходной, так и для обнуленной матрицы. Не может он оказаться и по другую сторону забора, ибо забор 4-связен — соседние пикселы не могут лежать по разные стороны такого забора. То же самое справедливо в отношении точки B. Значит, после итерации (уже на обнуленной матрице) по обе стороны забора сохранятся либо сами пикселы А и B, либо их непосредственные соседи. До итерации эти пикселы входили в одну связную компоненту C, а после итерации оказались не связанными друг с другом.
Отсюда следует: если в случае исходной матрицы до итерации скелетизации пикселы A и B типа “1”, лежащие по разные стороны некоторого забора, были соединены какой-либо связью в рамках апертуры (8-связной цепочкой из пикселов типа “1”, “x”, “−”), то в случае обнуленной матрицы итерация скелетизации нарушает связность некоторой связной компоненты (а именно, связной компоненты C).
В последующих рассуждениях, обнаруживая забор, мы будем уточнять, какой связью были соединены A и B внутри апертуры, а именно, будем говорить, что забор рвет эту связь. Заметим, что если апертура содержит всю цепочку L = L1,L2,...,LN (чаще всего мы будем рассматривать именно такие апертуры), а пикселы A и B — либо сами L1 и LN, либо связаны с ними 8-связными цепочками единиц (“1”) в рамках нашей апертуры, то наличие связи очевидно — ее обеспечивает сама наша цепочка L.
Наша цель: показать, что во всех возможных вариантах цепочки L1,L2,...,LN либо получается противоречие с одним из предположенных выше условий (в частности, что эта цепочка самая выгодная), либо обнаруживается апертура некоторого размера Qx x Qy, в которой два пиксела типа “1” из разных связных компонент D'A и D'B разделены забором, но соединены 8-связной цепочкой из пикселов типа “1”, “x”, “−”. Это будет означать, что существует конфигурация Qx x Qy с нулевыми точками снаружи, в которой итерация нарушает связность. Запомнив набор размеров Qx x Qy, которые нам встретятся при обнаружении заборов, мы докажем теорему для этого набора размеров.
Разумеется, нет смысла отдельно запоминать размеры Q'x x Q'y, если мы и так включаем в набор какие-то размеры Qx x Qy, большие либо равные по обоим координатам (Q'x≤Qx, Q'y≤Qy) — конфигурации Q'x x Q'y будут протестированы среди конфигураций Qx x Qy, когда все дополнительные элементы равны 0.
Изучим возможные конфигурации цепочки L1,L2,...,LN. Очевидно, все элементы цепочки, кроме L1 и LN, лежат вне D'I, D'J и всех прочих компонент, иначе цепочка не была бы кратчайшей по числу элементов. Иначе говоря, в наших обозначениях они имеют тип “x”. По тем же причинам «внутренние» элементы цепочки
Отсюда следует, что если N≥5, то в точке L3 нарушается условие локальности: у такого пиксела после итерации нет соседей. Следовательно, можно считать, что N=3 или N=4. Разберем все возможные случаи.
Заметим: до этого момента мы не использовали условие правой локальности, а пользовались лишь общим (более слабым) условием локальности.
Случай, когда кратчайшая цепочка, соединяющая разные компоненты, имеет длину N=3
Пусть вначале самая выгодная цепочка, соединяющая разные связные компоненты D'I и D'J, имеет длину N=3 элемента.
Рассмотрим апертуру 3x5 с центром в точке L2. Возможны следующие варианты.
3.1) |y3−y1|=2. Для определенности будем считать, что y3=y1+2 — в противном случае перенумеруем цепочку в обратном порядке и переобозначим D'I и D'J.
Очевидно, для y2 есть лишь одна возможность y2=y1+1:
. . . I?I?I? . x!. J?J?J? . . .
(L1 и L3 могут пока занимать любое из 3 положений).
Высота нашей цепочки равна 2, так что мы вправе предполагать отсутствие трехэлементных цепочек 2x1 и 2x0, соединяющих разные связные компоненты (они были бы более выгодными).
Рассмотрим варианты. Слева от центра может быть “0”,“1”,“x”, справа также “0”,“1”,“x”, всего 9 вариантов: 3.1.1–9.
3.1.1–5) Пусть слева или справа “1” (5 вариантов: “1” и “0”, “1” и “x”, “0” и “1”, “x” и “1”, “1” и “1”).
Например, слева:
. . . I?I?I? 1 x!. J?J?J? . . .
Пиксел слева не может принадлежать одновременно обоим связным компонентам D'I (содержащей L1) и D'J (содержащей L3). Проведем от него цепочку к L3, если он принадлежит D'I, и к L1, если принадлежит любой другой связной компоненте. Эта цепочка 2x1, очевидно, выгоднее нашей по высоте. Совершенно аналогичен случай, когда “1” справа: цепочка от него либо к L1, либо к L3 соединяет разные связные компоненты и при этом выгоднее нашей.
3.1.6) Справа “0”, слева “0”. Сразу получается забор из 3 пикселов “0 x! 0”, разделяющий L1 и L3.
Заметим: пример забора, состоящего из центрального пиксела “x” и серии нулей “0” и рвущего исходную цепочку уже в конфигурации 3x5, также означает, что алгоритм скелетизации нарушает простейшее условие — удаление одного только центрального единичного пиксела не должно разрушать связность конфигурации 3x5. (Обратное не обязательно верно: если указанное условие нарушено, то, конечно, забор разрывает некую конфигурацию 3x5, но не очевидно, что разъединившиеся точки действительно сохранятся в результате итерации скелетизации, а в данной конкретной области полной матрицы — что при этом они попадут в разные связные компоненты.)
Выполнение указанного требования достаточно, чтобы гарантировать отсутствие подобных заборов, и его легко обеспечить уже на этапе построения алгоритма. Однако наше доказательство обходится без него.
Более сложные заборы, которые будут появляться далее для расширенных апертур, иллюстрируют более тонкие проблемы, когда удаление одного центрального пиксела, возможно, еще не приводит к потере связности, но параллельное удаление сразу серии пикселов может привести к этому.
3.1.7) Справа “x”, слева “x”: такая конфигурация невозможна по лемме Sb, так как мы предполагаем условие правой локальности.
3.1.8) Справа “0”, слева “x”. Применяем лемму Sa:
. . . 0 I?I? x x!0 0 J?J? . . .
Расширим апертуру влево до 4x5:
. - . . - 0 I?I? - x!x!0 - 0 J?J? . - . .
Минусы поставлены потому, что “0” на месте любого из них порождает разделяющий забор уже на этой апертуре 4x5, рвущий цепочку “L1 x! L3”. Но три левых минуса вступают в противоречие с P1.
3.1.9) Справа “x”, слева “0”. Применяем лемму Sa:
. . . . 0 . 0 x!x . 0 . . . .
Здесь L1 — это либо точка слева сверху, либо минус справа сверху; аналогично L3.
В силу условия правой локальности, одна их точек справа сверху или справа снизу (над или под правым “x”) является “1”. Эти ситуации разбираются совершенно аналогично, с точностью до симметрии по вертикали.
Для определенности, предположим первый вариант: точка справа сверху есть “1”. Тогда это “i”, ибо в противном случае (если эта единица входит в иную связную компоненту, нежели L1) для L1 остается лишь позиция слева сверху, и цепочка-«уголок» 2x1 от этой единицы до L1 оказывается более выгодной по высоте. Таким образом:
. . . . 0 i 0 x!x . 0 . . . .
Возможно, это “i” и есть L1, а может быть, L1 расположено слева сверху — для дальнейшего рассмотрения это неважно.
L3 не может располагаться справа снизу, ибо иначе вертикальная цепочка 0x2 от правого верхнего “i” до L3 окажется выгоднее, чем L1,L2,L3: у нее такая же высота, но центр тяжести расположен правее. Значит, L3 находится слева снизу:
. . . . 0 i 0 x!x J 0 . . . .
Более того, точка справа снизу (под правым “x”) вообще не может быть “1”, ибо если такая единица входит в ту же связную компоненту, что и L3, т.е. является “j”, то мы вновь получаем более выгодную вертикальную цепочку 0x2 “i x j” с центром тяжести, расположенным правее центра тяжести исходной цепочки, а если такая единица входит в иную связную компоненту, нежели L3, то мы получаем более выгодную по высоте цепочку-«уголок» от нее к L3. Таким образом, точка справа снизу есть “0” или “x”. Если “0”, то очевиден зигзагообразный забор уже на этой апертуре, рвущий исходную цепочку:
. . . . 0 i 0 x!x J 0 0 . . .
Остается предположить, что точка справа снизу есть “x”:
. . . . 0 i 0 x!x J 0 x . - .
Минус дважды снизу поставлен, ибо иначе образуется забор-«уголок» “0 x! 0 0” уже на этой апертуре, рвущий исходную цепочку “L1 x! L3”.
Но если этот минус на самом деле “x”, то слева от него, по P1, будет “0”, и мы получаем забор-«скобку» при расширении вниз до 3x7, рвущий цепочку “L1 x! L3”:
. . . . 0 i 0 x!x J 0!x 0 x!. . . . . . .
Так что остается рассмотреть случай, когда этот минус на самом деле “1”, т.е. “j”:
. . . . 0 i 0 x!x J 0 x . j .
Расширяем апертуру вправо до 4x5:
. . . . . 0 i . 0 x!x!= J 0 x . . j . .
Знак “=” дважды справа, поставленный по P2, не может быть единицей, т.е. “i”, ибо в этом случае мы приходим к диагональной цепочке “j x i”, имеющей ту же высоту 2, центр тяжести которой, очевидно, смещенм вправо относительно центра тяжести исходной цепочки — т.е. к более выгодной цепочке.
Значит, “=” дважды справа есть “0”, и мы видим тривиальный горизонтальный забор уже на этой апертуре “0 x! x! 0”, рвущий нашу цепочку:
. . . . . 0 i . 0 x!x!0 J 0 x . . j . .
3.2) |y3−y1|=1. Тогда |x3−x1| может быть равен только 2, иначе L1 и L3 соприкоснутся. Для определенности будем считать, что x3=x1+2 — в противном случае перенумеруем цепочку в обратном порядке и переобозначим D'I и D'J. Очевидно, для x2 есть лишь одна возможность x2=x1+1.
Наша цепочка имеет размеры 2x1.
Для y3 есть два варианта: y1−1 и y1+1. Для y2 тоже есть два варианта: y2=y1 или y2=y3. Всего 4 группы случаев. (Напомним, что мы ставим центр апертуры на точку L2.)
Но мы вначале отдельно рассмотрим случай, когда L1 и L3 находятся по разные стороны вертикального столбика из двух “x”, чтобы исключить далее его из рассмотрения. Обозначим этот случай цифрой 0.
3.2.0) Пусть два пиксела между L1 и L3, имеющие промежуточную x-координату и y-координаты, равные y1 и y3, оба содержат “x”. Сразу расширим апертуру до 3x6:
. . . . . . I?x!J? I?x!J? . . . . . .
Слева или слева сверху от нижнего “x!”, по P1, должен быть “0”. Второй из пикселов, обозначенных “I?”, очевидно, L1 — возможностей для “x” в левой колонке не остается.
В силу P2, справа от обоих “x!” допустимо либо “1”, либо “0”, т.е. “=”. Причем один из этих “=”, очевидно, L3, а второй “0” — ибо второй знак “=” находится как раз напротив L1, и если он на самом деле “1” (т.е. “j”), то мы получаем более выгодную по высоте цепочку 2x0, которую мы рассмотрим позже (3.3.1).
Таким образом, мы имеем одну из двух конфигураций:
. . . . . . . . . . . . 0 x!J или I x!0 I x!0 0 x!J . . . . . . . . . . . .
В обоих случаях очевиден зигзагообразный забор “0 x! x! 0”, рвущий исходную цепочку.
Теперь рассмотрим все 4 варианта расположения цепочки, исключая рассмотренные случаи вертикальной пары “x”, разделяющей L1 и L3. Это значит, что один из двух пикселов, расположенных между L1 и L3, равен “x” (это L2), а второй обязательно “0” (единицей он быть не может, иначе компоненты оказались бы связанными).
3.2.1, 3.2.2) Пусть y3=y1±1, y2=y1.
. . . . . . 0 0 J 0 - . I x!- или I x!- 0 - . 0 0 J . . . . . .
“0” слева сверху и слева снизу поставлены по P1, а “0” сверху или снизу — в силу предварительного разбора случая 3.2.0.
Минусы поставлены, ибо иначе очевиден тривиальный забор, рвущий исходную цепочку — «скобка» или «зигзаг». Но правый минус не может быть “x” в силу P2. Значит, правый минус на самом деле “1”, т.е. “j”: получаем более выгодную по высоте цепочку 2x0, которую мы рассмотрим позже (3.3.1).
3.2.3) Пусть y3=y1−1, y2=y3.
. . . . . . 0 x!J I 0 - . - .
Слева “0” поставлен по P1, а снизу “0” поставлен в силу предварительного разбора случая 3.2.0.
Минусы поставлены потому, что “0” на месте любого из них порождает разделяющий забор уже на этой апертуре 3x5, рвущий цепочку “L1 x! L3”.
Оба минуса не могут быть “1”, иначе компоненты оказались бы связанными.
Допустим, нижний минус на самом деле “x”. Тогда, по P1, слева от него “0”. Расширим вниз до 3x7:
. . . . . . 0 x!J I 0!- 0 x!. . . . . . .
Видим забор-«скобку» вокруг L1, рвущий цепочку “L1 x! L3”.
Остается допустить, что нижний минус на самом деле “1”, т.е. “i”, соответственно правый минус на самом деле “x”:
. . . . . . 0 x!J I 0 x . i .
Расширяем вправо до 4x5:
. . . . . . . . 0 x!J!. I 0 x = . i . .
Знак “=” поставлен в силу P2.
Если это “0”, то очевиден зигзагообразный забор “0 x! 0! x! 0” при расширении вниз до 4x6.
Если это “1”, т.е. “j”, то мы видим более выгодную цепочку 2x1 с центром тяжести, смещенным вправо относительно центра тяжести исходной цепочки.
3.2.4) Пусть y3=y1+1, y2=y3.
. - . I 0 -. 0 x!J . . . . . .
Разбирается абсолютно аналогично случаю 3.2.3, с точностью до вертикальной симметрии.
3.3) |y3−y1|=0, т.е. y1=y3. Тогда |x3−x1| может быть равен только 2, иначе L1 и L3 соприкоснутся. Для определенности будем считать, что x3=x1+2 — в противном случае перенумеруем цепочку в обратном порядке и переобозначим D'I и D'J. Очевидно, для x2 есть лишь одна возможность x2=x1+1.
Для y2 есть три варианта: y2=y1, y2=y1−1, y2=y1+1. (Напомним, что мы ставим центр апертуры на точку L2.)
3.3.1) Пусть y2=y1.
. . . 0 o . I x!J 0 o . . . .
Cлева сверху и слева снизу поставлены “0” по P1, а сверху и снизу “o”, ибо “1” соединила бы L1 и L3.
Очевидно, что при расширении вверх и вниз до 3x7 получим забор-«скобку» “0 o! x! o! 0”, рвущий исходную цепочку:
. . . . . . 0 o!. I x!J 0 o!. . . . . . .
3.3.2) Пусть y2=y1−1.
. . . . . . 0 x!. I 0 J . o .
Слева ставим “0” по P1.
Внизу (между I и J) ставим “0”, ибо “1” невозможен (компоненты оказались бы связанными), а “x” приведет к только что разобранному случаю 3.3.1 (забор при расширении до 3x7).
Дважды внизу стоит “o”, иначе компоненты оказались бы связанными.
Если это “0”, то очевиден забор-«уголок» уже на этой апертуре, рвущий исходную цепочку.
А если “x”, то слева от него, по P1, стоит “0”, и забор, рвущий исходную цепочку, возникает при расширении вниз до 3x7:
. . . . . . 0 x!. I 0!J 0 x!. . . . . . .
3.3.3) Пусть y2=y1+1.
. o . I 0 J 0 x!. . . . . . .
Разбирается абсолютно аналогично случаю 3.3.2, с точностью до вертикальной симметрии.
Разбор всех случаев, когда N=3, закончен.
Случай, когда кратчайшая цепочка, соединяющая разные компоненты, имеет длину N=4
Пусть теперь самая выгодная цепочка, соединяющая разные связные компоненты D'I и D'J, имеет длину N=4 элемента.
Так как по условию наша цепочка 1” не может быть соединен 3-элементной цепочкой (через пиксел типа “x”) или тем более 2-элементной цепочкой (т.е. быть соседом) одновременно с L1 и с L4, ибо иначе одна из этих двух цепочек соединит разные связные компоненты и будет при этом более выгодной.
Для определенности будем считать, что среднее звено цепочки L2–L3 направлено слева направо (по горизонтали или диагонали) или строго сверху вниз (по вертикали), т.е. либо x3>x2, либо x3=x2, но y3>y2. В противном случае перенумеруем цепочку в обратном порядке и переобозначим D'I и D'J.
С учетом сказанного, все возможные геометрии цепочки L описываются следующими четырьмя схемами, соответствующими четырем возможным направлениям звена L2–L3:
I?I?I? I?I?I? J?J?J?
I? . . J? . x . I?x . J? I?. x J?
I? x x J? . x . I?. x J? I?x . J?
I? . . J? J?J?J? J?J?J? I?I?I?
A B C D
Здесь “I?” и “J?” обозначают все возможные позиции концов цепочки L1 и L4, причем в группах C и D следует исключить по 2 случая, когда L1 и L4 оказываются соседями по диагонали.
Рассмотрим все эти группы вариантов.
4.A) Линия L2–L3 горизонтальна:
I? 0 . J? I? x x J? I? 0 . J?
Нули над и под левым “=” поставлены по лемме Sa. Условие правой локальности, примененное к левому “x”, требует считать, что либо над, либо под правым “x” стоит единица. Мы имеем максимум 3-элементные цепочки, ведущие от этой единицы как к L1, так и к L4, и одна из них будет более выгодной цепочкой, соединяющей разные связные компоненты.
4.B) Линия L2–L3 идет вертикально. Рассмотрим следующую апертуру 3x6:
. . . I?I?I? . x!= . x!= J?J?J? . . .
Знаки “=” поставлены по P2.
Ни справа, ни слева от наших двух “x” (L2 и L3) не может быть единиц, иначе мы получим максимум 3-элементные цепочки, ведущие от такой единицы как к L1, так и к L4, и одна из них будет более выгодной цепочкой, соединяющей разные связные компоненты. Значит, наши “=” на самом деле “0”, а слева мы имеем два “o”:
. . . I?I?I? o x!0 o x!0 J?J?J? . . .
Но P1 требует поставить “0” слева от одного из “o”, и мы получаем тривиальный горизонтальный забор в этой апертуре, рвущий исходную цепочку.
4.C) Линия L2–L3 идет вправо вниз. Рассмотрим апертуру 3x5 в центром в точке L3:
I?I?I?. I?x o J? I?0 x!J? J?J?J? . . .
Мы поставили слева “0” в силу P1. Мы поставили сверху “o”, так как “1” на этой позиции приводит к максимум 3-элементным цепочкам от этой единицы как к L1, так и к L4, и одна из них будет более выгодной цепочкой, соединяющей разные связные компоненты.
Применяя условие правой локальности к левому верхнему “x”, мы видим, что как минимум один из двух правых пикселов “I?” сверху действительно является единицей, причем именно типа “i” (из той же связной компоненты, что и L1) — в противном случае мы получим максимум 3-элементную цепочку от этой единицы к L1, соединяющую разные связные компоненты. Применяя условие правой локальности к “x!” (центру апертуры), мы видим, что как минимум один из четырех правых пикселов “J?” сверху действительно является единицей, причем именно типа “j” (из той же связной компоненты, что и L4) — в противном случае мы получим максимум 3-элементную цепочку от этой единицы к L4, соединяющую разные связные компоненты.
С этого момента нас уже не интересуют истинные позиции L1 и L4 — нам достаточно, что один из двух пикселов, обозначенных ниже “i?”, действительно имеет тип “i”, а один из четырех пикселов, обозначенных ниже “j?”, действительно имеет тип “j”:
i?i?. x o!j? 0 x j? . j?j? . . .
Допустим вначале, что правый “i?” на самом деле не “i”, а “o”. Тогда оставшийся “i?” (левый) обязан быть единицей:
i o . x o j? 0 x!j? . j?j? . . .
Но теперь, в силу P2, оба “o!” можно заменить на “0”:
i 0 . x 0 j? 0 x!j? . j?j? . . .
и мы видим забор-«уголок» уже на этой апертуре, рвущий цепочку “i x x! j”.
Таким образом, можно считать, что правый “i?” действительно “i”. В этом случае значение левого “i?” нам неважно, и мы поставим в этом месте точку:
. i . x o ? 0 x!j? . j?j? . . .
Вопросительный знак справа сверху не может быть “1”, ибо тогда это “i” и получается максимум 3-элементная цепочка оттуда до “j”. (Поэтому мы более не обозначем этот пиксел как “J?”.)
Если вопросительный знак справа сверху есть “0”, то при расширении апертуры вверх до 3x6 мы увидим забор “0 x! o! 0”, рвущий цепочку “i x! x! j”:
. . . . i . x o!0 0 x!j? . j?j? . . .
Остается допустить, что вопросительный знак справа сверху есть “x”:
. i . x o x 0 x!? . j?j? . . .
Новый вопросительный знак справа не может быть “1”, ибо тогда мы получим максимум 3-элементные цепочки, ведущие от этой единицы как к верхнему “i”, так и к “j”, и одна из них будет более выгодной цепочкой, соединяющей разные связные компоненты. (Поэтому мы более не обозначем этот пиксел как “J?”.)
Если этот новый вопросительный знак есть “0”, то мы видим тривиальный горизонтальный забор “0 x! 0” уже на этой апертуре, рвущий цепочку “i x! x! j.
Остается допустить, что новый вопросительный знак справа тоже есть “x”:
. i . x o x 0 x!x . j?j? . . .
Расширяем апертуру вправо до 4x5:
. i . . x o x . 0 x!x!= . j?j?. . . . .
Если знак “=”, поставленный по P2, есть “0”, то мы видим тривиальный горизонтальный забор “0 x! x! 0” уже на этой апертуре, рвущий цепочку “i x! x! j”.
Остается предположить, что это “1”:
. i . . x o x . 0 x!x!1 j?j?. . . . .
Мы видим максимум 3-элементные цепочки, ведущие от новой единицы справа как к верхнему “i”, так и к нижнему “j”, и одна из них будет более выгодной цепочкой, соединяющей разные связные компоненты.
4.D) Линия L2–L3 идет вправо вверх. Рассмотрим апертуру 3x5 в центром в точке L3:
. . . J?J?J? I?0 x!J? I?x o J? I?I?I?.
Эта ситуация разбирается абсолютно аналогично случаю 4.С, с точностью до вертикальной симметрии.
Разбор всех случаев, когда N=4, закончен.
Теорема доказана.
Примеры алгоритмов скелетизации с апертурой зависимости 3x5
Приведем пример параллельного алгоритма скелетизации, дающего достаточно качественные скелеты при апертуре зависимости 3x5 и удовлетворяющего всем условиям теоремы связности.
Для каждого пиксела с координатами (x0, y0) рассмотрим апертуру зависимости 3x5
a0 b0 c0 a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4
Таким образом, a0 есть элемент (x0−1,y0−2) исходной матрицы, b2 есть элемент (x0,y0) исходной матрицы.
Алгоритм вычисляет определенную логическую функцию
Полный алгоритм скелетизации последовательно применяет 4 итерации скелетизации слева, сверху, справа и снизу — при этом исходной матрицей для новой итерации является результат предыдущей итерации — до тех пор, пока битовая матрица не перестанет изменяться. Детали программной реализации такого алгоритма мы не приводим, но заметим, что в случае упакованного хранения битовых матриц (64 элемента в одном 64-битовом слове) любую логическую функцию ƒ можно вычислить, построив не более 3*5−1=14 вспомогательных матриц, получаемых из исходной сдвигом, и применив к ним и к исходной матрице традиционные побитовые операции, имеющиеся во всех процессорах и в большинстве языков программирования: побитовое «и», «или», «не». Это возможно благодаря тому, что описанный алгоритм параллельный, т.е. результат итерации в точке (x0, y0) зависит только от элементов исходной матрицы в апертуре зависимости. Таким образом, при вычислении итерации скелетизации можно обрабатывать все биты машинного слова одновременно, а при наличии нескольких процессоров или процессорных ядер можно любым удобным образом разбить матрицу на части и обработать эти части параллельно.
Остается описать необходимую функцию ƒ, обеспечивающую, с неформальной точки зрения, истончение объектов слева и удовлетворяющую условиям теоремы связности.
Я предлагаю логическую функцию
- если b2=0, то ƒ=02 (гарантируем условие нерасширения);
- иначе, если c2=0, то ƒ=1;
- иначе (мы уверены, что центральный пиксел единичный и справа от него тоже единица):
- если a2=0 (левый край, вероятная ситуация для истончения: удаления центрального пиксела), то:
- если a1=1 и если неверно, что b1=1 (т.е. b1=0), то ƒ=1 (это означает, что точка a1=1 сверху «отрывается» в
3x3-апертуре ); - иначе, если a3=1 и если неверно, что (b3=1 или (b4=1 и c3=1)), то ƒ=1 (это означает, что точка a3=1 снизу «отрывается» как в 3x3, так и в
3x5-апертуре ); - иначе, если b1=0 и c1=0 и b3=0 и c3=0, то ƒ=1 (это означает, что отрезок c2—b2 предствляет собой левое окончание тонкой однопиксельной линии, которую наш алгоритм уже не трогает — не пытается укорачивать);
- иначе ƒ=0 (удаляем центральный пиксел);
- если a1=1 и если неверно, что b1=1 (т.е. b1=0), то ƒ=1 (это означает, что точка a1=1 сверху «отрывается» в
- иначе ƒ=1 (воздерживаемся от истончения).
- если a2=0 (левый край, вероятная ситуация для истончения: удаления центрального пиксела), то:
Соответствующий алгоритм скелетизации (с добавлением 3 итераций, получаемых поворотами системы координат) мы назовем aлгоритм A. Такой алгоритм обеспечивает достаточно качественные скелеты, при этом никогда не пытается удалять единичный пиксел, если слева от него единица (это более сильное требование, чем сформулированное в теореме условие левого края). Иначе говоря, он не пытается «делать дырки». Однако, расплатой за такое сильное требование является возможное появление в окончательном скелете «толстых узлов» 2x3, 3x2 и даже 3x3 (единичных областей, которые невозможно «истончить» далее):
1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1
Если существование в скелете единичных областей 3x2, 2x3 и 3x3 является неприемлемым, то можно «усилить» приведенную выше функцию ƒ, добавив после проверки 1 следующую ветку:
- если a2=0... (то же самое);
- иначе, если a1=0 и a3=0 и b0=0 и b4=0 и при этом все 8 пикселов a0, a2, a4, b1, b3, c1, c2, c3 равны 1, то ƒ=0 (распознаем «проблемные» ситуации, приведенные на схеме выше, и в порядке исключения «делаем дырку» на месте присоединения левой горизонтальной линии в вертикальному массиву единичных пикселов);
- иначе ƒ=1 (как и раньше, воздерживаемся от истончения).
Полученный алгоритм мы назовем aлгоритм B.
Оба алгоритма A и B удовлетворяют всем условиям теоремы связности и не нарушают связность ни на одной конфигурации 3x7 или 4x6, что можно проверить соответствующими переборными программами. Таким образом, существует гарантия, что приведенные алгоритмы скелетизации сохраняют связность 8-связных компонент исходного изображения.
Что касается качества получаемых итоговых скелетов, справедливы следующие теоремы тонкости.
Теорема тонкости для алгоритма A. В окончательном скелете, получаемом алгоритмом A (с добавлением 3 итераций, получаемых поворотами системы координат), прямоугольные области 2x3, 3x2 и 3x3, заполненные единицами, могут появиться только в центре следующих конфигураций 4x5, 5x4 и 5x5:
1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 1
Иначе говоря, приведенные выше примеры плохих случаев являются единственно возможными, если говорить о возможных значениях соседних пикселов, окружающих заполненный единицами прямоугольник 2x3, 3x2 или 3x3. В частности, в окончательном скелете не могут сохраниться заполненные единицами прямоугольники размеров 2x4, 4x2, 3x4, 4x3 или бо́льшие.
Как и теорема связности, эта теорема доказывается тестирующей программой перебора. А именно, поведение пикселов в области 3x3, в случае итерации скелетизации слева, полностью определяется апертурой исходной матрицы 5x7:
? ? ? ? ? ? ? ? ? ? ? r r r ? ? r r r ? ? r r r ? ? ? ? ? ? ? ? ? ? ?
Мы обозначили буквой “r” значения пикселов в результате итерации скелетизации. Таким образом, достаточно перебрать 25*7=235 возможных битовых конфигураций, чтобы получить список всех центральных конфигураций 3x3, которые могут оказаться устойчивыми к итерации скелетизации слева хотя бы при каких-то конфигурациях окружающих пикселов. Конфигурацию 5x7, целиком состояющую из единиц и, очевидно, дающую в центре единичный квадрат 3x3, следует исключить из рассмотрения: если в итоговом скелете существует прямоугольник некоторого размера, заполненный единицами, то существует такой же прямоугольник с наименьшей x-координатой, и у него будет хотя бы один нулевой сосед. (Напоминаем, что пикселы за пределами матрицы мы считаем равными нулю, поэтому вырожденный случай бесконечной матрицы, заполненной единицами, мы не рассматриваем.) Тестирующая программа выполняет такой анализ для всех 4 вариантов итерации скелетизации слева, сверху, справа и снизу и получает два списка конфигураций 3x3: конфигурации из первого списка при определенном внешнем окружении могут оказаться устойчивыми ко всем 4 итерациям скелетизации, конфигурации же из второго списка заведомо невозможны в итоговом скелете, ибо разрушаются при всех вариантах внешнего окружения.
Конфигурации 3x3 из первого списка могут потребовать дальнейшего анализа, если мы не сумеем найти такого окружения 5x7 или 7x5, при котором не только центральная область 3x3, но и вся конфигурация в целом (будучи дополнена снаружи нулями) стабильна по отношению ко всем 4 итерациям скелетизации, т.е. представляет собой готовый пример стабильного окончательного скелета. В таком случае нет гарантии, что такая конфигурация 3x3 может действительно встретиться в итоговом скелете. В этой ситуации (сравнительно редкой на практике) тестирующая программа должна всеми возможными способами дополнить «проблемную» конфигурацию 3x3 до конфигурации 5x5 с тем же центром. Заметим: мы сразу можем сказать, что такая дополненная конфигурация 5x5 не может встретиться в итоговом скелете, если хотя бы одна из 9 ее под-областей 3x3 попала во второй список заведомо невозможных конфигураций 3x3. В противном случае, поведение пикселов в конфигурации 5x5, в свою очередь, полностью определяется апертурой исходной матрицы 7x9:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? r r r r r ? ? r r r r r ? ? r r r r r ? ? r r r r r ? ? r r r r r ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
в случае итерации скелетизации слева/справа или аналогичной апертурой 9x7 в случае итерации скелетизации сверху/снизу. Перебрав все возможные конфигурации такого размера, содержащие в центре все проверяемые конфигурации 5x5, мы либо отыщем искомый итоговый скелет, стабильный по отношению ко всем 4 итерациям скелетизации, либо убедимся, что все конфигурации 5x5, содержащие изучаемую центральную конфигурацию 3x3 (а значит, и сама центральная конфигурация 3x3) невозможны для итогового скелета, ибо разрушаются при всех вариантах внешнего окружения, либо, в свою очередь, обнаружим «проблемные» конфигурации 5x5: такие, что они сохраняются при всех вариантах окружения 9x7 или 7x9, но среди всех таких конфигураций 9x7 или 7x9 нет ни одной, представляющей собой (при дополнении снаружи нулями) готовый пример стабильного скелета. К счастью, реальная тестирующая программа показывает, что подобная ситуация не происходит для описанных выше алгоритмов A и B.
В случае алгоритма A описанное тестирование показывает, что единственные конфигурации 3x3, содержащие полностью единичную прямоугольную область 2x3 или 3x2, которые могут встретиться в итоговом скелете, суть
0 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1
Чтобы доказать теорему, тестирующая программа вновь должна дополнить эти конфигурации всеми возможными способами до конфигурации 5x5 с тем же центром, проверяя при этом, что ни одна из 9 ее под-областей 3x3 не попадает в список заведомо невозможных конфигураций 3x3. Заметим: сейчас мы можем включить в этот список также те конфигурации 3x3, которые были «проблемными» на первом этапе тестирования, если углубленный анализ путем дополнения до конфигураций 5x5 показал, что они все-таки невозможны в итоговом скелете. Как и ранее, перебираем все возможные конфигурации размера 7x9 или 9x7, получаемые дальшейшим расширением такой конфигурации 5x5, и получаем полный список всех возможных, невозможных и «проблемных» конфигураций 5x5, содержащих в центре одну из указанных пяти конфигураций 3x3. Реальная тестирующая программа не обнаруживает в этом случае «проблемных» конфигураций 5x5, а все возможные конфигурации 5x5, которые хотя бы при одном внешнем окружении устойчивы ко всем 4 итерациям скелетизации, действительно, содержат указанные в теореме конфигурации соседей единичного прямоугольника 2x3, 3x2 или 3x3.
Заметим: описанный алгоритм тестирования лишь иллюстрирует общую идею построения тестирующей программы. Буквальная реализация описанного метода на типичных современных компьютерах приведет к очень большому времени выполнения: каждую из конфигураций 5x5 можно дополнить до конфигурации 7x9 238~275 миллиардами способов, а таких конфигураций 5x5 придется проанализировать многие десятки тысяч. Однако, грамотная реализация тестирующей программы позволяет значительно сократить перебор и доказать теорему за несколько минут процессорного времени персонального компьютера.
Теорема тонкости для алгоритма B. В окончательном скелете, получаемом алгоритмом B (с добавлением 3 итераций, получаемых поворотами системы координат), не могут встретиться прямоугольные области 2x3, 3x2 или 3x3, заполненные единицами.
Эта теорема доказывается той же самой тестирующей программой перебора, что и теорема тонкости для алгоритма A. После изучения всех конфигураций 3x3 выясняется, что как целиком единичная конфигурация 3x3, так и конфигурации 3x3, содержащие целиком единичные прямоугольники 2x3 или 3x2, оказываются невозможными.
Таким образом, самая большая прямоугольная область, заполненная единицами, которая может существовать в результате алгоритма B, есть квадрат 2x2. Ниже приведен полный список всех возможных конфигураций 4x4, в центре которых может встретиться такой квадрат 2x2 (для краткости не приводятся конфигурации, которые можно получить из других конфигураций симметрией или поворотом системы координат):
1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0
Ноябрь 2010 г.
Комментарии по поводу статьи можно оставить на моем блоге, тема «Теорема связности»: .