AlgART / Тексты

Целочисленные точечные множества в Z^N: Z-выпуклость и оптимизация сумм Минковского

Даниэль Алиевский

Выражаю благодарность Константину Кобылкину за идею доказательства 2-мерной теоремы Z-выпуклости и Василию Алиевскому за помощь в поиске литературы

ОГЛАВЛЕНИЕ

• Используемые термины, обозначения и элементарные леммы
• Теорема Z-выпуклости кратных Минковского
• Теорема каркасных разложений для кратных Минковского
• Применение в оптимизации алгоритмов математической морфологии
• Об алгоритмах проверки условий теоремы каркасных разложений
• Приложение. Алгоритм проверки объединения выпуклых гипермногогранников (задача III)

Данная статья посвящена анализу свойств конечных дискретных целочисленных точечных множеств, состоящих из целых точек — элементов N-мерного пространства Z^N. Я предлагаю обобщение понятия выпуклости в обычном Эвклидовом пространстве R^N — понятие Z-выпуклости целочисленных множеств в Z^N. Я рассматриваю взаимосвязь Z-выпуклости и поведения кратных Минковского n⊗P=P⊕P⊕...⊕P для таких множеств P⊂Z^N и предлагаю эффективное усиление классической леммы Шапли — Фолкмана для случая кратных n⊗P — теорему каркасных разложений, позволяющую построить экономные разложения таких кратных в эквивалентные суммы Минковского со значительно меньшим числом и мощностью слагаемых. В заключение описывается применение таких разложений для оптимизации алгоритмов математической морфологии в области обработки изображений и многомерных матриц.

Используемые термины, обозначения и элементарные леммы

Мы будем рассматривать два типа точечных множеств: дискретные, т.е. состоящие из конечного числа точек N-мерного Эвклидова пространства R^N, и непрерывные, т.е. обычные замкнутые подмножества R^N (чаще всего гипермногогранники).

Точки, все координаты которых суть целые числа, мы будем кратко называть целые точки. Множество всех целых точек мы будем (как обычно) обозначать Z^N.

Как правило, рассматриваемые дискретные множества будут состоять из целых точек; такие множества мы будем называть целочисленными. Заметим также, что любое выпуклое множество в R^N является непрерывным.

Для произвольного точечного множества A будем обозначать con(A) выпуклую оболочку A.

Заметим, что выпуклая оболочка con(P) всякого дискретного точечного множества P является выпуклым гипермногогранником, причем его вершины обязательно принадлежат P (в частности, могут быть единственными элементами P).

Для произвольного дискретного точечного множества P будем называть каркасом P и обозначать car(P) множество всех вершин выпуклого гипермногогранника con(P). Очевидно, con(car(P)) = con(P).

Для произвольного целочисленного точечного множества P в N-мерном пространстве будем называть линейным каркасом P вдоль координаты k (k=1,2,...,N) и обозначать lcar_k(P) множество всех таких точек p, принадлежащих P, что при сдвиге такой точки либо на +1, либо на −1 вдоль указанной координаты мы оказываемся в точке, не принадлежащей P:

lcar_k(P) = {p=(x₁,x₂,...,x_k,...,x_N): p∈P, но p_right=(x₁,x₂,...,x_k+1,...,x_N)∉P или p_left=(x₁,x₂,...,x_k−1,...,x_N)∉P}

Линейный каркас, в отличие от обычного каркаса, содержит довольно много точек, и это понятие приложимо только к целочисленным точечным множествам.

Тот из линейных каркасов lcar_k(P) вдоль всех координат k, который содержит минимум элементов, назовем минимальным линейным каркасом P и обозначим просто lcar(P).

Целочисленное точечное множество P мы будем называть Z-выпуклым, если

con(P) ∩ Z^N = P

Иначе говоря, целочисленное точечное множество P называется Z-выпуклым тогда и только тогда, когда всякая целая точка, принадлежащая его выпуклой оболочке con(P), обязательно принадлежит самому P.

Z-выпуклость является естественным обобщением понятия выпуклости на случай дискретных множеств.

Заметим также, что множество всех целых точек, принадлежащих какому-нибудь выпуклому непрерывному точечному множеству (скажем, гиперсфере) — например, множество центров пикселов круга, «нарисованного» на плоском изображении традиционными графическими средствами, — всегда является Z-выпуклым. Это тривиальное следствие определения выпуклой оболочки как минимального выпуклого множества, содержащего данное множество.

Для произвольных точечных множеств A и B будем обозначать A⊕B их сумму Минковского, т.е. множество всех попарных сумм точек из A и B:

A⊕B = {a+b: a∈A, b∈B}

Если n — целое положительное число, то сумму Минковского n одинаковых слагаемых мы будем называть кратным Минковского и обозначать n⊗A:

n⊗A = A⊕A⊕...⊕A (n слагаемых)

Если ν — произвольное положительное число, то результат гомотетии произвольного точечного множества A в ν раз мы будем обозначать νA или ν⋅A:

νA = ν⋅A = {νr: a∈A}

Выпуклость, выпуклые оболочки и кратные Минковского удовлетворяют двум простым соотношениям, которые мы далее будем свободно применять.

Лемма C1. Если точечное множество A выпуклое, а n — целое положительное число, то n⊗A = nA.

Это следует из того, что для всякого выпуклого множества A среднее арифметическое любого набора его точек также принадлежит A, поэтому всякая сумма a₁+a₂+...+a_n = na_mean ∈ nA, где a_mean = (a₁+a₂+...+a_n)/n ∈ A.

Лемма C2. Если n — целое положительное число, то для любого точечного множества P имеем

con(n⊗P) = n⊗con(P) = n⋅con(P)

Второе равенство есть лемма C1. Допустим, p∈con(n⊗P). Тогда, по определению выпуклой оболочки, p принадлежит любому выпуклому множеству, являющемуся надмножеством n⊗P. Множество n⊗con(P) = n⋅con(P) является выпуклым (как и con(P)), при этом n⊗con(P)⊇n⊗P, поскольку con(P)⊇P. Следовательно, p∈n⋅con(P). Если же, наоборот, p∈n⋅con(P), то это значит p∈con(n⋅P) (равенство con(ν⋅P)=ν⋅con(P) очевидно для любого P и для любого положительного вещественного ν: гомотетия переводит выпуклую оболочку исходного множества в выпуклую оболочку результата гомотетии исходного множества). Следовательно, p∈con(n⊗P), поскольку n⊗P⊇n⋅P. Доказательство закончено.

Мы также будем пользоваться классической леммой Шапли — Фолкмана:

Лемма Шапли — Фолкмана. Если P₁, P₂, ..., P_n — произвольные точечные множества в N-мерном пространстве R^N и их количество n>N, то их можно перенумеровать таким образом, что будет верно равенство:

сon(P₁) ⊕ сon(P₂) ⊕ ... ⊕ сon(P_n) = сon(P₁) ⊕ сon(P₂) ⊕ ... ⊕ сon(P_N) ⊕ P_N+1 ⊕ ... ⊕ P_n

Иначе говоря, в сумме Минковского n выпуклых оболочек сon(P_i) произвольных точечных множеств можно выделить как минимум n−N слагаемых и заменить из исходными множествами P_i так, что при этом общая сумма Минковского не изменится.

В частном случае, когда все слагаемые суммы Минковского одинаковы, мы приходим к упрощенной формулировке этой леммы, которая нам и понадобится в дальнейшем.

Лемма Шапли — Фолкмана для кратных Минковского. Если P — произвольное точечное множество в N-мерном пространстве и целое число n больше N, то

n⊗con(P) = N⊗con(P) ⊕ (n−N)⊗P.

Теорема Z-выпуклости кратных Минковского

Кратные Минковского n⊗P для Z-выпуклых целочисленных множеств являются естественным аналогом понятия гомотетии n⋅P для обычных непрерывных геометрических фигур. Например, достаточно большой круглый объект, «нарисованный» на экране компьтера или растровом изображении, может быть описан целочисленным множеством P всех целых точек плоскости, лежащих внутри математического круга радиуса ρ и соответствующих центрам пикселов объекта. Если заменить P на n⊗P и «закрасить» все пикселы, центры которых соответствуют точкам из n⊗P, то круглый объект увеличится в n раз и будет близок к математическому кругу радиуса nρ. Правда, по мере увеличения n отклонение n⊗P от точного круга будет увеличиваться и может достигать ~n пикселов, однако относительная погрешность представления круга будет оставаться примерно на одном уровне, соответствующем погрешности пиксельного представления исходного круга радиуса ρ.

Это свойство кратных Минковского n⊗P — они увеличивают дискретную фигуру, примерно сохраняя ее форму — является следствием леммы C2, но лишь при условии, что множество n⊗P, как и само P, является Z-выпуклым. (Действительно, если это так, то n⊗P есть просто множество всех целых точек, лежащих внутри или на границе выпуклого гипермногогранника con(n⊗P), а по лемме C2 он совпадает с результатом гомотетии n⋅con(P).) Таким образом, возникает вопрос: являются ли Z-выпуклыми кратные Минковского n⊗P, если множество P Z-выпукло. В следующем разделе мы увидим, что этот вопрос является весьма важным для построения экономных разложений кратных Минковского вида n⊗P.

Соответствующее утверждение для обычной выпуклости в непрерывном случае очевидно: если множество A выпукло, то, разумеется, результат его гомотетии n⋅A тоже выпуклый. К сожалению, для Z-выпуклости в дискретном случае ситуация сложнее.

Контрпримером являются известные тетраэдры Рива, точнее, наборы их вершин. А именно, пусть число измерений N=3 и

P = {(0,0,0), (1,0,0), (0,1,0), (1,1,m)}, m — целое число ≥2

— 4 вершины тетраэдра Рива. Тетраэдр целиком расположен внутри «столбика» 0≤x, y≤1, поэтому очевидно, что 4 его вершины суть единственные целые точки тетрадра con(P): con(P)∩Z^N=P. То есть P — Z-выпуклое множество. Далее, кратное Минковского P⊕P=2⊗P состоит из 10 точек, из которых 6 имеют z-координату 0 — (0,0,0), (1,0,0), (2,0,0), (0,1,0), (1,1,0), (2,0,0) — 3 имеют z-координату m — (1,1,m), (2,1,m), (1,2,m) — и одна есть (2,2,2m). Однако, удвоенный тетраэдр 2⋅con(P)=con(2⊗P) содержит целую серию целых точек, имеющих координаты (1,1,0), (1,1,1), ..., (1,1,m), и все они, кроме первой и последней, не принадлежат 2⊗P. Значит, кратное Минковского 2⊗P не является Z-выпуклым.

Тем не менее, сформулированные ниже теоремы позволяют в большинстве случаев гарантировать Z-выпуклость любых кратных Минковского n⊗P.

Общая теорема Z-выпуклости кратных Минковского. Для любого целочисленного множества P в N-мерном пространстве R^N, если множество N⊗P Z-выпуклое, то любое множество n⊗P, где n>N, также Z-выпуклое.

Таким образом, если мы хотим удостовериться, что все кратные Минковского n⊗P являются Z-выпуклыми, то достаточно проверить этот факт для первых N кратных Минковского: P, 2⊗P, ..., N⊗P.

Доказательство опирается на лемму Шапли — Фолкмана для кратных Минковского. Пусть C=car(P) — каркас P, т.е. множество вершин выпуклой оболочки con(P). Так как C⊆P, то все точки C целые. Лемма Шапли — Фолкмана вместе с леммой C2 позволяет записать:

con(n⊗P) = con(N⊗P) ⊕ (n−N)⊗C.

Пусть теперь p — произвольная целая точка con(n⊗P). Предыдущее равенство позволяет представить эту точку в виде

p = p' + c₁ + c₂ + ... + c_n−N,

где все с_i принадлежат каркасу C и, следовательно, являются целыми, а p'∈con(N⊗P). Точка p', равная разности целых точек p−(c₁+c₂+...+c_n−N), сама является целой, а в силу Z-выпуклости N⊗P отсюда следует, что она принадлежит N⊗P, т.е. p' = p₁+p₂+...+p_N, где все p_j принадлежат P. Таким образом, мы нашли представление точки p в виде суммы n точек

p = p₁ + p₂ + ... + p_N + c₁ + c₂ + ... + c_n−N,

и все эти точки принадлежат P. Иначе говоря, p∈n⊗P. Поскольку p — произвольная целая точка con(n⊗P), то это доказывает, что множество n⊗P Z-выпуклое. Доказательство закончено.

На самом деле мы доказали несколько более сильное утверждение:

Теорема Z-выпуклости кратных Минковского для подпространств. Для любого целочисленного множества P в N-мерном пространстве R^N, если все точки P принадлежат какому-нибудь линейному подпространству (гиперплоскости) размерности M, где M≤N, а множество M⊗P Z-выпуклое, то любое множество n⊗P, где n>M, также Z-выпуклое.

Действительно, лемма Шапли — Фолкмана, примененная к этому подпространству, даст нам n−M слагаемых c_i, а рассуждение относительно точки p' здесь не меняется.

Предыдущая формулировка теоремы получается при M=N.

Для тривиального одномерного случая (N=1) эта теорема не подлежит улучшению, ибо N⊗P=P. Однако в двумерном случае эта теорема может быть усилена.

2-мерная теорема Z-выпуклости кратных Минковского. Для любого целочисленного множества P на плоскости R², если множество P Z-выпуклое, то любое множество n⊗P, где n>N, также Z-выпуклое.

Очевидно, нам достаточно доказать Z-выпуклость 2⊗P, ибо для бо́льших n мы можем сослаться на общую теорему Z-выпуклости.

Прежде всего заметим, что эта теорема верна для 3-точечного множества P, образующего вершины примитивного треугольника ABC, т.е. такого треугольника, который не содержит ни одной целой точки, помимо своих вершин. В этом случае 2⊗P состоит из 6 точек — вершин и середин сторон удвоенного треугольника 2⋅ABC=con(2⊗P), при этом никаких иных целых точек этот удвоенный треугольник не содержит. Чтобы убедиться в этом, достаточно сослаться на классическую формулу Пика. По этой формуле площадь любого многоугольника с целыми вершинами равна I+B/2−1, где I — число целых точек, лежащих строго внутри многоугольника и B/2 — число точек на границе многоугольника. Площадь исходного треугольника ABC по этой формуле равна ½ (I=0, B=3), следовательно, площадь удвоенного треугольника 2⋅ABC равна 4⋅½=2, а так как мы уже знаем 6 целых точек, лежащих на его границе, то единственными возможными значениями для I и B оказываются I=0, B=6. Впрочем, нетрудно доказать нужный нам факт независимо от формулы Пика, рассмотрев 4 треугольника, конгруэнтных ABC, из которых составлен удвоенный треугольник 2⋅ABC (серединный треугольник и три треугольника при вершинах): легко убедиться, что каждый из этих треугольников получается из исходного ABC аффинным преобразованием, все коэффициенты которого суть целые числа (и наоборот), поэтому в них не могут появиться какие-то новые целые точки, помимо 6 вершин этих 4 треугольников.

Теперь рассмотрим произвольное целочисленное точечное множество P. Триангулируем его выпуклую оболочку con(P) на примитивные треугольники. Это всегда возможно, кроме вырожденного случая, когда все точки лежат на одной прямой; но в этом случае мы можем сослаться на предыдущую теорему Z-выпуклости для подпространств (M=1). В остальных случаях вначале триангулируем выпуклую оболочку con(P) на какие-нибудь треугольники, что для выпуклого многоугольника вообще не составляет проблем. А затем будем разбивать каждый треугольник ABC, содержащий внутреннюю целую точку O (лежащую внутри, а не на границе), на три треугольника AOB, BOC, СOA, а каждый треугольник, содержащий целую точку O на границе, на два треугольника (скажем, если целая точка O лежит на стороне AB, то разобьем треугольника на треугольники AOC и BOC). Повторяя этот процесс, рано или поздно мы придем к разбиению con(P) на одни лишь примитивные треугольники.

Пусть p — произвольная целая точка con(2⊗P)=2⋅con(P). Точка p/2 принадлежит какому-то из примитивных треугольников, образующих построенное выше разбиение con(P); пусть это будет треугольник ABC. Все вершины этого треугольника суть целые точки, принадлежащие con(P), следовательно, в силу Z-выпуклости P, все три вершины A, B, C суть элементы P. Поскольку теорема верна для примитивных треугольников, а точка p принадлежит удвоенному треугольнику 2⋅ABC, значит, p∈2⊗{A,B,C}, т.е. точку p можно представить в виде суммы q₁+q₂, где обе точки q₁ и q₂ суть какие-то из вершин A, B или C (и, следовательно, принадлежат P). Иначе говоря, p∈2⊗P. Доказательство закончено.

Теорема каркасных разложений для кратных Минковского

Теорема каркасных разложений для кратных Минковского, общая формулировка. Пусть P и Q — произвольные целочисленные точечные множества в N-мерном пространстве, C=car(Q) — каркас второго множества, т.е. множество вершин выпуклой оболочки con(Q), и пусть все кратные Минковского n⊗P для любого целого положительного n являются Z-выпуклыми. Тогда:

1. если con(P) ⊕ C = con(P) ⊕ con(Q), то (k⊗P) ⊕ (k⋅C) = (k⊗P) ⊕ (k⊗Q) для любого целого положительного k;
    
2. если 2⋅con(P) ⊕ C = 2⋅con(P) ⊕ con(Q), то (2k⊗P) ⊕ (k⋅C) = (2k⊗P) ⊕ (k⊗Q) для любого целого положительного k;
    
3. если 3⋅con(P) ⊕ C = 3⋅con(P) ⊕ con(Q), то (3k⊗P) ⊕ (k⋅C) = (3k⊗P) ⊕ (k⊗Q) для любого целого положительного k;
    
4. вообще, при любом целом m≥1, если m⋅con(P) ⊕ C = m⋅con(P) ⊕ con(Q), то (mk⊗P) ⊕ (k⋅C) = (mk⊗P) ⊕ (k⊗Q) для любого целого положительного k.

Доказательство этой теоремы вполне элементарно. Поскольку C⊆Q, то очевидно, что (mk⊗P) ⊕ (k⋅C) ⊆ (mk⊗P) ⊕ (k⊗Q), т.е. достаточно доказать обратное включение. Пусть p ∈ (mk⊗P) ⊕ (k⊗Q). Тогда, тем более,

p ∈ con(mk⊗P) ⊕ con(k⊗Q) = (mk⋅con(P)) ⊕ k⋅con(Q) = k ⋅ [m⋅con(P) ⊕ con(Q)]

(мы применили лемму C2). В силу условия теоремы, мы можем заменить здесь con(Q) на C и получить

p ∈ k ⋅ [m⋅con(P) ⊕ С] = (mk⋅con(P)) ⊕ k⋅С = con(mk⊗P) ⊕ k⋅С

т.е. p = p' + c, где p'∈con(mk⊗P), c∈k⋅С. Точка c здесь является целой, поскольку все точки каркаса C суть целые вершины con(Q), точка p изначально была целой (это точка целочисленного точечного множества), следовательно, точка p' тоже целая. А так как все кратные Минковского множества P, включая mk⊗P, являются Z-выпуклыми, то отсюда следует, что p'∈mk⊗P. Таким образом,

p = p' + c ∈ (mk⊗P) ⊕ (k⋅С),

что и требовалось доказать.

В случае P=Q эта теорема приобретает более обозримую и более сильную формулировку:

Теорема каркасных разложений для кратных Минковского, основная формулировка. Пусть P — произвольное целочисленное точечное множество в N-мерном пространстве, C=car(P) — его каркас, т.е. множество вершин выпуклой оболочки con(P), и пусть все кратные Минковского n⊗P для любого целого положительного n являются Z-выпуклыми. Тогда:

1. если con(P) ⊕ C = 2⋅con(P), то (k⊗P) ⊕ (k⋅C) = 2k⊗P для любого целого положительного k, причем указанное условие гарантированно выполнено при N = 1;
    
2. если 2⋅con(P) ⊕ C = 3⋅con(P), то (2k⊗P) ⊕ (k⋅C) = 3k⊗P для любого целого положительного k, причем указанное условие гарантированно выполнено при N ≤ 2;
    
3. если 3⋅con(P) ⊕ C = 4⋅con(P), то (3k⊗P) ⊕ (k⋅C) = 4k⊗P для любого целого положительного k, причем указанное условие гарантированно выполнено при N ≤ 3;
    
4. вообще, при любом целом m≥1, если m⋅con(P) ⊕ C = (m+1)⋅con(P), то (mk⊗P) ⊕ (k⋅C) = ((m+1)k)⊗P для любого целого положительного k, причем указанное условие гарантированно выполнено при N ≤ m.

Здесь добавлено, что «указанное условие гарантированно выполнено при N ≤ m» — это является непосредственным следствием леммы Шапли — Фолкмана для кратных Минковского.

Сформулируем еще одну простую теорему, касающуюся сумм вида P⊕P=2⊗P.

Теорема линейных каркасов. Пусть P — произвольное целочисленное точечное множество в N-мерном пространстве, L=lcar_k(P) — любой из его линейных каркасов (в частности, минимальный каркас lcar(P) — см. раздел «Используемые термины, обозначения и элементарные леммы»). Тогда P⊕P=P⊕L.

Допустим для определенности, что k=1, т.е. L есть линейный каркас вдоль первой координаты (доказательство совершенно аналогично для любой координаты). Разобьем множество P на цепочки точек S_i, в которых первая координата x₁ точки p = (x₁, x₂, ..., x_N) последовательно изменяется от одного значения x₁=x_min⁽ⁱ⁾ до другого значения x₁=x_max⁽ⁱ⁾ с шагом 1, причем при x₁=x_min⁽ⁱ⁾−1 и x₁=x_max⁽ⁱ⁾+1 мы уже оказываемся за пределами P:

S_i = {(x_min⁽ⁱ⁾, x₂, ..., x_N), (x_min⁽ⁱ⁾+1, x₂, ..., x_N), ..., (x_max⁽ⁱ⁾−1, x₂, ..., x_N)}, (x_max⁽ⁱ⁾, x₂, ...,x_N)},
S_i ⊆ P, но (x_min⁽ⁱ⁾−1, x₂, ..., x_N)∉P и (x_max⁽ⁱ⁾+1, x₂, ..., x_N)∉P

Очевидно, линейный каркас L состоит в точности из первых и последних точек всех таких цепочек (x_min⁽ⁱ⁾, x₂, ..., x_N) и (x_max⁽ⁱ⁾, x₂, ..., x_N), а число элементов в каждой цепочке есть ||S_i||=x_max⁽ⁱ⁾−x_min⁽ⁱ⁾+1.

Упорядочим всем такие цепочки по убыванию числа элементов, чтобы было ||S_i||≥||S_i+1|| для всех i. Поскольку

P = ∪ S_i,

то

P⊕P = ∪ (S_i⊕S_j),

причем в этом объединении по всем парам i и j можно считать, что i ≤ j и, следовательно, ||S_i|| ≥ ||S_j||. Но S_i и S_j суть простые одномерные цепочки точек, и в данном случае очевидно, что

S_i ⊕ S_j = S_i ⊕ {a^(j), b^(j)}

где a^(j)=(x_min^(j), x₂, ..., x_N) и b^(j)=(x_max^(j), x₂, ..., x_N) суть первая и последняя точки цепочки S_j. (Этот факт, касающийся сумм Минковского одномерных целочисленных множеств, легко проверяется непосредственно и является следствием того, что ||S_i|| ≥ ||S_j||.) Таким образом,

P⊕P = ∪_i≤j (S_i ⊕ S_j) = ∪_i≤j (S_i ⊕ {a^(j), b^(j)}) = P⊕L.

Что и требовалось доказать.

Рассматриваемые теоремы позволяют строить очень экономные представления кратных Минковского вида n⊗P в виде равных им сумм Минковского — экономные как по числу слагаемых (порядка log n), так и по мощности слагаемых (большинство из них имеют вид k⋅C, т.е. число их элементов равно числу вершин выпуклой оболочки con(P)).

Например, первый случай теоремы каркасных разложений в основной формулировке (если выполнены все требуемые условия) позволяет представить любое кратное Минковского следующим образом.

1-е разложение кратных Минковского. Пусть P — произвольное целочисленное точечное множество, C=car(P), все кратные Минковского n⊗P являются Z-выпуклыми и верно con(P)⊕C=2⋅con(P) (последнее равенство гарантированно выполнено при N = 1). Тогда для любого целого n≥2

n⊗P = P ⊕ C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ rC

где q — какое-то целое неотрицательное число (~log n), а r — целое число из диапазона 0≤r<2^q+1.

Действительно, из формулировки первого случая теоремы непосредственно следует, что P⊕C=2⊗P, значит, P⊕C⊕2C=2⊗P⊕2C=4⊗P, значит, P⊕C⊕2C⊕4C=4⊗P⊕4C=8⊗P, и т.д. — вcе эти суммы равны кратным Минковского вида 2ⁱ⊗P. В общем случае

P ⊕ C ⊕ 2C ⊕ ... ⊕ 2^qC = 2^q+1⊗P.

Выберем в качестве q максимальное целое число, при котором 2^q+1≤n, и положим r=n−2^q+1 (это остаток от деления n на 2^q+1). Если r=0, то мы уже имеем искомое разложение. Если r>0, то в силу теоремы каркасных разложений для k=r и ассоциативности сложения по Минковскому

P ⊕ C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ rC = 2^q+1⊗P ⊕ rC = (2^q+1−r)⊗P ⊕ (r⊗P ⊕ rC) = (2^q+1−r)⊗P ⊕ 2r⊗P = n⊗P

Доказательство закончено.

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

2-е разложение кратных Минковского. Пусть P — произвольное целочисленное точечное множество, C=car(P), все кратные Минковского n⊗P являются Z-выпуклыми и верно 2⋅con(P)⊕C=3⋅con(P) (последнее равенство гарантированно выполнено при N ≤ 2). Тогда для любого целого положительного Тогда для любого целого n≥2

n⊗P = P ⊕ lcar(P) ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ rC

или

n⊗P = P ⊕ lcar(P) ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ 2^q+1C ⊕ rC

где q — какое-то целое неотрицательное число (~log n), а r — целое число из диапазона 0≤r<2^q+1. В случае n=2 разложение имеет вид 2⊗P = P ⊕ lcar(P), а в случае n=3 разложение имеет вид 3⊗P = P ⊕ lcar(P) ⊕ C.

Действительно, P ⊕ lcar(P) = P ⊕ P по теореме линейных каркасов, и это исчерпывает доказательство при n=2. Если n>2, то в силу второго случая теоремы каркасных разложений и ассоциативности сложения по Минковскому

P ⊕ P ⊕ C = 3⊗P (и это исчерпывает доказательство при n=3),
P ⊕ P ⊕ C ⊕ C = 3⊗P ⊕ C = P ⊕ (2⊗P ⊕ C) = 4⊗P,
P ⊕ P ⊕ C ⊕ C ⊕ 2C = 4⊗P ⊕ 2C = 6⊗P,
P ⊕ P ⊕ C ⊕ C ⊕ 2C ⊕ 2C = 6⊗P ⊕ 2C = 2⊗P ⊕ (4⊗P ⊕ 2C) = 8⊗P,

и так далее. В общем случае мы получим

P ⊕ P ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC = 2^q+2⊗P,
P ⊕ P ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ 2^q+1C = (2^q+2+2^q+1)⊗P.

Выберем в качестве q максимальное целое число, при котором 2^q+2≤n. Случаи n<4 уже рассмотрены выше, так что у нас получится q≥0. Положим r=n mod 2^q+1 — остаток от деления n на 2^q+1; тогда либо n=2^q+2+r, либо n=2^q+2+2^q+1+r. Если r=0, то мы уже имеем искомое разложение. Если r>0, то остается записать кратное 2^q+2⊗P в виде ((2^q+2−2r)⊗P)⊕(2r⊗P), использовать ассоциативность сложения по Минковскому и применить второй случай теоремы каркасных разложений для k=r, и мы получим, что либо первое, либо второе из выражений

P ⊕ P ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ rC,
P ⊕ P ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ 2^q+1C ⊕ rC

равно кратному Минковского n⊗P. Доказательство закончено.

Очевидно, все остальные случаи теоремы для разных m≥1 позволяют получить аналогичные разложения, тем менее экономные, чем больше m. Приведем в качестве примера без доказательства разложение для случая m=3:

3-е разложение кратных Минковского. Пусть P — произвольное целочисленное точечное множество, C=car(P), все кратные Минковского n⊗P являются Z-выпуклыми и верно 3⋅con(P)⊕C=4⋅con(P) (последнее равенство гарантированно выполнено при N ≤ 3). Тогда для любого целого положительного n≥2

n⊗P = P ⊕ lcar(P) ⊕ lcar(P) ⊕ C ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ 2^qC ⊕ rC,

или

n⊗P = P ⊕ lcar(P) ⊕ lcar(P) ⊕ C ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ 2^qC ⊕ 2^q+1C ⊕ rC,

или

n⊗P = P ⊕ lcar(P) ⊕ lcar(P) ⊕ C ⊕ C ⊕ C ⊕ 2C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2^qC ⊕ 2^qC ⊕ 2^qC ⊕ 2^q+1C ⊕ 2^q+1C ⊕ rC

где q — какое-то целое неотрицательное число (~log n), а r — целое число из диапазона 0≤r<2^q+1. В случаях n=2, n=3, n=4, n=5 (когда приведенные выше формулы потребовали бы отрицательного q) разложение имеет вид

2⊗P = P ⊕ lcar(P),
3⊗P = P ⊕ lcar(P) ⊕ lcar(P),
4⊗P = P ⊕ lcar(P) ⊕ lcar(P) ⊕ C,
5⊗P = P ⊕ lcar(P) ⊕ lcar(P) ⊕ C ⊕ C.

Наконец, если даже условия предыдущих разложений не выполнены, в частности, если множество P или его кратные Минковского не являются Z-выпуклыми, то для совершенно произвольного целочисленного точечного множества справедливо следующее простейшее разложение, непосредственно вытекающее из теоремы линейных каркасов:

Тривиальное разложение кратных Минковского. Пусть P — произвольное целочисленное точечное множество. Для любого целого положительного n

n⊗P = P ⊕ ((n−1) ⊗ lcar(P)).

Отметим также особый случай гиперпараллелепипеда, для которого существует эффективное разложение в сумму Минковского, даже если он не является кратным Минковского (например, длины его ребер взаимно просты). А именно:

Разложение гиперпараллелепипеда. Пусть P — целочисленный гиперпалаллелепипед с ребрами, параллельными координатным осям, т.е. множество всех целых точек (x₁, x₂, ..., x_N), лежащих в диапазонах

a₁ ≤ x₁ ≤ a₁+d₁,
a₂ ≤ x₂ ≤ a₂+d₂,
. . .
a_N ≤ x_N ≤ a_N+d_N

где a_i, d_i суть какие-то целые числа, d_i≥0 — длины ребер. Любой такой гиперпараллелепипед может быть представлен в виде суммы Минковского ~log₂ ||P|| слагаемых (||P||=(d₁+1)(d₂+1)...(d_N+1) — число элементов P):

P = {(a₁, a₂, ..., a_N)} ⊕
⊕ ∑_k=0,1,... {(0, 0, ..., 0}, {2^k, 0, ..., 0)} ⊕ {(0, 0, ..., 0}, {r₁, 0, ..., 0)} ⊕
⊕ ∑_k=0,1,... {(0, 0, ..., 0}, {0, 2^k, ..., 0)} ⊕ {(0, 0, ..., 0}, {0, r₂, ..., 0)} ⊕
. . .
⊕ ∑_k=0,1,... {(0, 0, ..., 0}, {0, 0, ..., 2^k)} ⊕ {(0, 0, ..., 0}, {0, 0, ..., r_N)}

(первое слагаемое состоит из 1 элемента, все прочие из 2 элементов). Знак суммирования ∑ здесь означает сумму Минковского, и каждое такое суммирование ведется до тех тех пор, пока сумма чисел s=1+2+...+2^k не станет больше либо равна половине соответствующей длины ребра d_i/2. Затем остаток r_i выбирается равным d_i−s.

Это разложение является следствием аналогичного разложения сплошного одномерного сегмента, которое является частным случаем приведенного выше 1-го разложения при N=1, P={0,1} (множество из двух точек 0 и 1), и того факта, что сумма Минковского ортогональных одномерных целочисленныз сегментов дает указанный гиперпараллелепипед.

Применение в оптимизации алгоритмов математической морфологии

Обширный класс алгоритмов обработки изображений и трехмерных воксельных моделей опирается на операции математической морфологии. Операции математической морфологии, в свою очередь, являются комбинациями базовых операций дилатации и эрозии, имеющих два операнда: растр I (обычно 2- или 3-мерный) и структурный элемент, или шаблон P. Например, последовательное выполнение дилатации и эрозии с одинаковым шаблоном представляет собой закрытие, а последовательное выполнение эрозии и дилатации — открытие; эти операции позволяют подавить соответственно негативный и позитивный импульсный шум на изображении. Арифметическая поэлементная разность между дилатацией и эрозией на небольшой шаблон — это градиент Бойхера, позволяющий выявить границы объектов. Арифметическая разность между изображением и результатом его открытия на шаблон большого размера позволяет устранить неравномерность фона (освещенности). Существует множество других применений этих операций.

В терминах данной работы, шаблон в этих операциях является целочисленным точечным множеством: это набор центров пикселов или вокселей, описывающих структурный элемент. Как правило, шаблон является целочисленной аппроксимацией геометрической фигуры достаточно простой формы: прямоугольника, восьмиугольника, круга, эллипса, в 3-мерном случае параллелепипеда, сферы или эллипсоида. Форма шаблона может подбираться в зависимости от объектов, которые присутствуют на изображении, подлежащем обработке. Чаще всего наилучшие результаты обработки получаются для шаблона в форме круга (в 3-мерном случае сферы).

Изображение или воксельный растр в простейшем (бинарном) случае может, как и шаблон, рассматриваться как целочисленное точечное множество: это битовая матрица, каждый элемент которой содержит 1, если в этой точке присутствует какой-то объект, или 0, если эта точка соответствует фону. Точечное множество в этом случае состоит из всех точек, для которых элемент матрицы с такими же координатами равен 1. В этом случае дилатация растра I на шаблон P по определению представляет собой сумму Минковского I⊕P, а эрозия — парную ей операцию разность Минковского I⊖P, которая проще всего определяется через сумму Минковского следующим образом:

I ⊖ P = (I ^c ⊕ −P) ^c,

где X ^c = Z^N \ X означает теоретико-множественное дополнение множества X до всего целочисленного пространства Z^N (в терминах растра это означает замену 0 на 1 и наоборот, а также предположение, что за пределами матрицы мы имеем бесконечную область, заполненную единичными элементами), а −P есть множество, центрально-симметричное по отношению к P относительно начала координат. (Приведенное определение соответствует вполне конкретной модели продолжения растра за пределами имеющейся матрицы, а именно, продолжению нулями. На практике обычно более удобны иные модели, например, периодическая по всем координатам, но их рассмотрение выходит за рамки данной работы.)

В более сложной ситуации изображение или трехмерный растр является полутоновым, т.е. соответствующая матрица может содержать другие числа, отличные от 0 и 1. Обычно ее элементы описывают яркость пикселов или вокселей. С математической точки зрения можно считать, что такой растр I — это некая функция I(x₁, x₂, ..., x_N), принимающая вещественные значения и определенная для целых аргументов из некоторой прямоугольной области 0≤x_i<n_i, где n_i суть размеры изображения по каждой координате. В этом случае дилатация и эрозия проще всего определяются через увеличение на 1 числа пространственных измерений. Приведем это определение.

Прежде всего введем ограничение: будем считать, что все значения функции I(x₁, x₂, ..., x_N) суть целые числа. В практических приложениях так чаще всего и бывает (яркость пиксела или вокселя представлена целым числом небольшой разрядности). А если это не так, то всегда можно умножить все элементы матрицы на достаточно большую целую константу M и округлить до ближайшего целого числа, а после выполнения всех операций поделить результат на M (все рассматриваемые ниже операции дистрибутивны по отношению к умножению значений функции на скаляр) — таким образом мы получим приближение к исходной функции с любой желаемой точностью. Ограничившись рассмотрением целых значений I, мы избежим многословных оговорок — и, что гораздо важнее, сможем воспользоваться доказанными выше теоремами.

Рассмотрим двумерный случай. Для всякого растра I=I(x, y) обозначим I⁺ трехмерное точечное множество, состоящее из всех точек (x,y,z) с целыми координатами, для которых x и y лежат в пределах матрицы (0≤x<n₁, 0≤y<n₂) и при этом z≤I(x, y). Иначе говоря, это объемная фигура, находящаяся под графиком функции I(x, y). Тогда, по определению, дилатация I на целочисленное точечное множество-шаблон P — это такой растр J, что J⁺ есть сумма Минковского I⁺ ⊕ P, а эрозия I на шаблон P — это такой растр J, что J⁺ есть разность Минковского I⁺ ⊖ P. Трехмерный и общий N-мерный случаи рассматриваются аналогично. Целочисленность значений I позволяет нам не выйти за рамки класса целочисленных точечных множеств в Z^N+1.

Заметим, что в этом определении шаблон P является (N+1)-мерным точечным множеством: трехмерным для двумерного изображения, четырехмерным для трехмерного воксельного растра и т.д. Для многих применений вполне можно считать, что дополнительная координата у всех точек P равна нулю, и тогда получится естественное обобщение дилатации и эрозии бинарных изображений — например, дилатация двумерной битовой матрицы на круг P⊂Z² идентична дилатации этой же матрицы, рассматриваемой как полутоновая (со значениями 0 и 1), на трехмерное точечное множество P' = {p'=(x,y,0): (x,y)∈P}. Однако существуют приложения, где даже для двумерного растра весьма полезно рассмотреть действительно трехмерное множество P. В частности, это алгоритм выравнивания фона, который получается, если вычесть из изображения результат открытия на очень большой шаблон, имеющий форму трехмерного шара или усеченного параболоида вращения; этот метод называется в литературе, соответственно, “Rolling Ball” или “Sliding Paraboloid” и дает значительно лучшие результаты, чем открытие на «плоский» круг. В случае трехмерного растра, соответственно, следует рассматривать 4-мерную гиперсферу и 4-мерный гиперпараболоид.

Увеличение числа измерений, хотя и полезно для математического изучения задачи, не означает повышения алгоритмической сложности задачи. Действительно, приведенное выше определение дилатации эквивалентно следующему: функция J есть дилатация I на шаблон P, если для каждой точки (x₁, x₂, ..., x_N) имеем

J(x₁, x₂, ..., x_N) = max (I(x₁−u₁, x₂−u₂, ..., x_N−u_N) + u_N+1) для всех точек p=(u₁, u₂, ..., u_N, u_N+1)∈P

Аналогично, функция J есть эрозия I на шаблон P, если для каждой точки (x₁, x₂, ..., x_N) имеем

J(x₁, x₂, ..., x_N) = min (I(x₁+u₁, x₂+u₂, ..., x_N+u_N) − u_N+1) для всех точек p=(u₁, u₂, ..., u_N, u_N+1)∈P

(Заметим: эти формулы предполагают, что мы не вышли за пределы матрицы. Для краев изображения эти операции могут быть доопределены различными способами, дающими различные модели продолжения растра; мы здесь не будем их рассматривать.)

Таким образом, очевидно, что дилатация и эрозия произвольной матрицы могут быть вычислены за S||P|| операций типа «взятие максимума/минимума из двух чисел», где S — число элементов матрицы растра, а ||P|| — число элементов в шаблоне P. Причем для (N+1)-мерного шаблона из него можно перед этим исключить все точки, имеющие одинаковый набор младших координат u₁, u₂, ..., u_N, кроме той, у которой добавочная координата u_N+1 имеет максимальное значение: они не сказываются на результате. Иначе говоря, при фактическом вычислении дилатации/эрозии плоского изображения на трехмерный шаблон нас в действительности интересует только верхняя поверхность этого шаблона.

Простейший алгоритм, реализующий «в лоб» приведенные формулы, может быть реализован очень эффективно благодаря распараллеливанию на многих ядрах и применению векторных инструкций вроде системы команд SSE современных процессоров. Тем не менее, в случае больших шаблонов P его производительность быстро становится неудовлетворительной. Например, дилатация даже небольшого трехмерного растра 512×512×512 вокселей на сферу радиуса r (точнее, на множество всех целых четырехмерных точек вида (x,y,z,0), для которых x²+y²+z²≤r²), требует порядка r³/2 миллиардов операций, что при больших r дает чрезвычайно большое время, несмотря на прекрасную низкоуровневую оптимизацию.

К счастью, дилатация и эрозия, определенные, как описано выше, обладают ассоциативностью по отношению к сложению шаблонов по Минковскому: дилатация I на сумму Минковского P⊕Q равна результату последовательной дилатации I вначале на шаблон P, а затем на шаблон Q, а эрозия I на сумму Минковского P⊕Q равна результату последовательной эрозии I вначале на шаблон P, а затем на шаблон Q. (Это является очевидным следствием приведенного определения через увеличение числа измерений, а также определения разности Минковского как I ⊖ P = (I ^c ⊕ −P) ^c.) В частности, дилатация или эрозия на кратное Минковского вида n⊗Q эквивалентна последовательному выполнению n дилатаций или эрозий на шаблон Q.

Если большой шаблон P является целочисленной аппроксимацией выпуклой фигуры A, то, как правило, максимальная точность такой аппроксимации (т.е. минимально возможная погрешность <0.5) не является принципиальной для алгоритма обработки. Например, результат открытия на круг или сферу большого радиуса с целью выделить фон изображения практически не изменится, если вместо большого круга мы возьмем другое точечное множество, близкое по форме к кругу. Между тем, в начале раздела «Теорема Z-выпуклости кратных Минковского» мы видели, что кратные Минковского вида n⊗Q, где Q есть целочисленная аппроксимация уменьшенной фигуры A⋅n⁻¹, являются неплохой аппроксимацией для исходной фигуры — при условии, что уменьшенная фигура A⋅n⁻¹ не является слишком маленькой, т.е. содержит достаточное количество целых точек, а также при условии, что множество Q и все его кратные Минковского n⊗Q являются Z-выпуклыми. Таким образом, мы можем сформулировать следующий алгоритм.

Приближенная дилатация/эрозия на гомотетичные фигуры. Пусть A — некоторая выпуклая непрерывная N-мерная фигура, и мы хотим выполнить дилатацию/эрозию растра I на шаблон, являющийся целочисленной аппроксимацией фигуры вида ρA для произвольного ρ>0. Выберем такое α>0, чтобы целочисленное точечное множество Q=(αA)∩Z^N давало достаточно точную аппроксимацию формы фигуры αA, например, порядка 10%, но при этом оставалось по возможности небольшим (в случае круга или сферы это означает выбор радиуса порядка 10). Для произвольного ρ>0:

1. если ρ≥α, выполним дилатацию/эрозию на множество n⊗Q, где n=⌊ρ/α⌋ (целая часть ρ/α) — согласно сказанному выше, это требует n последовательных шагов дилатации/эрозии на шаблон Q;
2. если ρ/α не есть целое число, то выполним дилатацию/эрозию предыдущего результата на шаблон Q'=((ρ−nα)A)∩Z^N, являющийся целочисленной аппроксимацией уменьшенной фигуры (ρ−nα)A.

Здесь предполагается, что размерность растра равна N, если это простой бинарный растр (битовая матрица), либо N−1, если мы рассматриваем полутоновое изображение — см. выше определение дилатации и эрозии через увеличение числа пространственных измерений. Таким образом, в случае 3-мерных воксельных моделей размерность N равна 4, хотя для практических задач часто достаточно шаблонов, в которых 4-я координата всегда равна 0 (т.е. по существу трехмерных множеств).

Приведенный алгоритм можно использовать только при условии, что шаблон Q и все его кратные Минковского n⊗Q являются Z-выпуклыми (см. начало раздела «Теорема Z-выпуклости кратных Минковского»). Z-выпуклость самого шаблона Q следует из выпуклости исходной фигуры A и выбора Q как множества всех целых точек фигуры αA — такое множество Z-выпукло по построению. Что касается кратных n⊗Q, то теорема Z-выпуклости кратных Минковского дает эффективные критерии проверки этого обстоятельства. В частности, в двумерном случае это гарантируется автоматически.

Этот алгоритм, в отличие от предыдущего, требует числа операций O(S⋅(ρ/α)||Q||), где S — число элементов матрицы растра. Эта величина пропорциональна геометрическому размеру шаблона ρ, а не количеству элементов, которое обычно растет как ρ^N (или ρ^N−1, если N-е измерение добавлено «искусственно» в рамках приведенного выше определения дилатации/эрозии (N−1)-мерного растра).

Однако этот результат может быть еще значительно улучшен. А именно, достаточно воспользоваться одним из разложений кратного Минковского n⊗Q, описанных в разделе «Теорема каркасных разложений для кратных Минковского», и для вычисления дилатации или эрозии растра на шаблон n⊗Q выполнить последовательность дилатаций или эрозий на все элементы такого разложения. В итоге мы получаем алгоритм, требующий

O(S⋅||Q||) + O(S⋅||car(Q)|| log n)

операций, то есть почти не зависящий от размера шаблона (число точек в каркасе car(Q) обычно намного меньше числа точек в исходном шаблоне Q). В частном случае, когда желаемый шаблон P является гиперпараллелепипедом, можно упростить алгоритм и непосредственно применить разложение для гиперпараллелепипеда, приведенное в конце того же раздела и обеспечивающее число операций

O(S⋅log ||P||)

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

Об алгоритмах проверки условий теоремы каркасных разложений

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

1. проверить, является ли Z-выпуклым заданное N-мерное целочисленное точечное множество Q и все его кратные Минковского n⊗Q;
2. построить по заданному целочисленному точечному множеству Q его каркас car(Q), т.е. множество точек — вершин выпуклой оболочки con(Q);
3. проверить для некоторого целого m (обычно это 1, 2 или 3) основное условие теоремы каркасных разложений:
   m⋅con(Q) ⊕ car(Q) = (m+1)⋅con(Q).

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

Прежде всего, будем для простоты считать, что наше множество Q является истинно N-мерным, т.е. его элементы не принадлежат какому-нибудь линейному подпространству меньшего числа измерений. (Очевидно, в этом случае то же самое справедливо для выпуклой оболочки con(Q).) Этот факт можно проверить простым и эффективным алгоритмом — например, добавляя точки из Q по одной и проверяя, лежит ли новая точка в линейном подпрострастве, определяемом предыдущими точками, до тех пор, пока число размерностей подпространства не достигнет N (если достигнет, значит, множество Q является истинно N-мерным). Если множество Q оказалось подмножеством какого-то линейного подпространства, то можно спроектировать все множество как минимум на одну из координатных гиперплоскостей (убрать одну из координат) и перейти к той же самой задаче для меньшего числа измерений.

Займемся вначале проверкой Z-выпуклости. Прежде всего заметим, что чаще всего исходное множество Q не случайно, а является целочисленной аппроксимацией некоторой геометрической фигуры, например, круга или эллипсоида. Если строить такую аппроксимацию простейшим образом, как предложено в предыдущем разделе (алгоритм «Приближенная дилатация/эрозия на гомотетичные фигуры»), то есть как пересечение исходной непрерывной фигуры и Z^N (множество всех целых точек, принадлежащих фигуре), то Z-выпуклость Q является следствием выпуклости исходной фигуры — а для невыпуклых фигур, наоборот, мы почти наверняка получим не-Z-выпуклое множество.

Это означает, что в двумерном случае N=2, благодаря двумерной теореме Z-выпуклости, мы вообще можем обойтись без специального алгоритма для задачи I: если множество Q по построению Z-выпуклое, то все его кратные n⊗Q тоже Z-выпуклые.

Правда, задача II в указанной ситуации (построение каркаса), родственная задаче I, алгоритмически не проще ее. Однако следует заметить, что в эффективных разложениях кратных Минковского, описанных выше в разделе «Теорема каркасных разложений для кратных Минковского», каркас C=car(Q) можно с успехом заменить любым другим множеством C', являющимся надмножеством истинного каркаса C и подмножеством исходного Q: C⊆C'⊆Q. (Очевидно, если такое разложение справедливо для каркаса C, то тем более оно справедливо для C', поскольку сумма Минковского надмножеств является надмножеством сумм Минковского слагаемых.) А это значит, что на практике мы вполне можем ограничиться каким-нибудь множеством C', достаточно близким к истинному каркасу и являющимся его надмножеством. Например, для этого подойдет псевдокаркас pcar(Q, d), где d есть какое-нибудь небольшое целое положительное число, который мы определим следующим образом:

псевдокаркас pcar(Q, d) есть множество всех таких точек p∈Q, что для любой целой точки r = (r₁, r₂, ..., r_N) из (небольшого) гиперкуба с центром в начале координат и длиной ребра 2d (в двумерном случае попросту квадрата 2d×2d) — т.е. такой точки, что для всех ее целых координат верно |r_i|≤d — либо точка p+r, либо точка p−r не принадлежат Q.

Т.е. псевдокаркас состоит из всех таких элементов Q, которые не являются серединами достаточно коротких отрезков с концами — элементами Q. Очевидно, настоящий каркас есть подмножество псевдокаркаса — вершина выпуклого многогранника не может быть серединой никакого отрезка, концы которого приналежат многограннику, иначе она не была бы вершиной. Однако уже при сравнительно маленьких d псевдокаркас слабо отличается от истинного каркаса: большая часть точек из множества Q, являющейся аппроксимацией непрерывной фигуры, которые не являются вершинами выпуклой оболочки, скорее всего, окажутся серединой какого-нибудь короткого отрезка с концами из Q и не попадут в такой псевдокаркас. Скажем, уже при d=1 из множества Q исключаются все «внутренние» точки, имеющие симметричную пару соседей вдоль одной из координатых осей или по диагонали — остаются только точки «границы» фигуры, да и то не все, ибо внутренние точки «плоских» участков границы (параллельных осям координат либо наклоненных по отношению к ним на 45°) тоже исключаются. Таким образом, разложение суммы Минковского, где каркас заменен псевдокаркасом, может обеспечить сравнимую эффективность. При этом очевидно, что алгоритм построения псевдокаркаса весьма тривиален и эффективен (при малых d): это просто последовательное тестирование каждой точки из Q для всех точек гиперкуба r.

Таким образом, в двумерном случае для большинства практических применений мы можем обойтись как без проверки Z-выпуклости (задача I), так и без нетривиального алгоритма построения каркаса (задача II). Остается задача III, но ее можно не решать, если ограничиться 2-м разложением кратных Минковского, для которого соответствующее условие 2⋅con(Q)⊕C=3⋅con(Q) в двумерном случае гарантировано. Таков простейший путь, подходящий, если наши задачи ограничиваются двумя измерениями и нет возможности применить менее тривиальные алгоритмы вычислительной геометрии, о которых пойдет речь далее.

В случае большего числа измерений N≥3 при решении задачи I мы полагаемся на общую теорему Z-выпуклости, но теперь эта теорема требует от нас явной проверки Z-выпуклости, как минимум, первых N кратных Минковского: Q, 2⊗Q, ..., N⊗Q. Проверка Z-выпуклости единственного множества Q нужна также и в двумерном случае, если мы не знаем заранее «происхождение» множества Q, а это вполне вероятная ситуация для универсальной алгоритмической библиотеки.

Очевидно, задача I сводится к алгоритму построения выпуклой оболочки con(Q) произвольного многомерного точечного множества Q, точнее, получению системы L неравенств вида

a₁^(j)x₁^(j) + a₂^(j)x₂^(j) + ... + a_N^(j)x_N^(j) ≤ b^(j), 0 ≤ j < L,

описывающих гиперполупространства, пересечением которых является эта выпуклая оболочка (эти гиперполупространства соответствуют L граням гиперполиэдра con(Q)). Напомним, что мы считаем множество Q истинно N-мерным, т.е. не лежащим в каком-нибудь линейном подпространстве полного пространства R^N.

Очевидно также, что эту задачу достаточно решить только для исходного множества Q и не нужно решать для кратных Минковского 2⊗Q, ..., N⊗Q, поскольку по лемме C2 выпуклая оболочка кратного Минковского con(k⊗Q) получается простой гомотетией выпуклой оболочки con(Q) (это соответствует умножению на k коэффициентов b^(j)).

Располагая такой системой неравенств, можно, например, перебрать все целые точки минимального гиперпараллелепипеда (с ребрами, параллельными осями координат), содержащего все множество k⊗Q, и прямой проверкой убедиться, что каждая целая точка, удовлетворяющая всем неравенствам

a₁^(j)x₁^(j) + a₂^(j)x₂^(j) + ... + a_N^(j)x_N^(j) ≤ kb^(j)

т.е. принадлежащая выпуклой оболочке con(k⊗Q) = k⋅con(Q), также принадлежит самому множеству k⊗Q — это и будет означать Z-выпуклость k⊗Q.

Существует ряд классических алгоритмов построения выпуклых оболочек наборов точек в N-мерном пространстве — достаточно выполнить поиск в Google. Среди наиболее известных можно назвать метод «заворачивания подарка», описанный, вместе с некоторыми другими алгоритмами, в книге: F. Preparata, M. Shamos, “Computational Geometry: An introduction”, 1985 (есть перевод на русский язык: Ф. Препарата, М. Шеймос, «Вычислительная геометрия: Введение», 1989 г.). Более того, как правило, эти алгоритмы одновременно позволяют решать задачу II — построить каркас car(Q), т.е. выделить те элементы Q, которые являются вершинами выпуклой оболочки. И даже если алгоритм выдает на выходе лишь набор коэффициентов a_i^(j) и b^(j), описывающих гиперплоскости граней выпуклой оболочки, то можно за O(L⋅||Q||) простых операций (||Q|| — число элементов Q) получить каркас car(Q): нужно для каждой точки Q проверить, что она принадлежит одновременно как минимум N гиперплоскостям (ибо вершины выпуклого N-мерного гипермногогранника инцидентны минимум N граням).

Обратим внимание на следующие обстоятельства.

Прежде всего, заметим, что выпуклая оболочка описанного чуть выше псевдокаркаса C'=pcar(Q, d) совпадает с искомой выпуклой оболочкой con(Q), ибо con(car(Q))=con(Q) и при этом car(Q)⊆C'⊆Q. То есть при решении задачи построения выпуклой оболочки и поиска каркаса car(Q) можно предварительно построить псевдокаркас pcar(Q, d) для какого-нибудь небольшого d (как уже говорилось, это весьма тривиальный и эффективный алгоритм), а затем вместо исходного Q решать задачу для найденного псевдокаркаса pcar(Q, d). Если множество Q является целочисленной аппроксимацией некоторой непрерывной фигуры — именно такие ситуации характерны для применений для оптимизации алгоритмов математической морфологии — то такая замена является существенной и очевидной оптимизацией всех последующих вычислений, поскольку число точек в псевдокаркасе намного меньше числа точек в исходном множестве (в идеальном случае близко к числу вершин искомой выпуклой оболочки).

Далее, обратим внимание, что в рассматриваемой области применений точечное множество, для которого нужно найти выпуклую оболочку, является небольшим — особенно с учетом предыдущего замечания. Идея алгоритма приближенной дилатации/эрозии, описанного в предыдущем разделе, предполагает как раз выбор небольшого множества Q (по числу элементов ||Q||), с тем чтобы минимизировать вклад первого слагаемого O(S⋅||Q||) в общее время расчета дилатации/эрозии. Таким образом, нет никакого смысла «гнаться» за оптимальными алгоритмами построения выпуклой оболочки Q, можно легко «позволить себе» неоптимальные, но простые алгоритмы, требующие, скажем, O(||Q||³) и даже большего числа операций — это все равно очень мало по сравнению с дилатацией/эрозией даже единственного большого растра на шаблон Q. Например, для практически важных размерностей пространства N = 2, 3, 4 вполне подойдет алгоритм «заворачивания подарка» из упомянутой выше книги «Вычислительная геометрия», и при желании его даже можно упростить (ценой замедления).

Третье и весьма важное замечание связано с ограниченной точностью комьютерного представления целых и вещественных чисел. Целью алгоритма в нашем случае является проверка условий теорем, которые позволят затем применять данное разложение кратных Минковского для данного множества Q для самых различных растров. В этой ситуации весьма нежелательно опираться на «приближенные» результаты, которые, пусть и с малой вероятностью, могут оказаться неверными в силу ошибок округления. Поэтому представляется целесообразным использовать реализации алгоритмов, применяющие то или иное представление целых и рациональных чисел с бесконечной точностью. При этом целые числа бесконечной точности представляются в виде массива машинных слов, имеющего произвольную длину (например, в языке Java для этого предусмотрен специальный тип данных BigInteger). Рациональные числа рассматриваются как пара целых чисел бесконечной точности, представляющих числитель и знаменатель — арифметические операции над такими рациональными числами легко реализуются через операции над числителем и знаменателем. Алгоритмы, которые мы рассматриваем в этом разделе, не нуждаются в использовании иррациональных чисел, поэтому наши задачи можно решить абсолютно достоверно. Кстати, алгоритмы построения выпуклой оболочки, включая получение каркаса car(Q), как правило, могут быть выражены с использованием одних только целых чисел бесконечной точности, поскольку координаты всех точек исходного множества суть целые числа.

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

Перейдем теперь к задаче III. Сумма Минковского m⋅con(Q) ⊕ car(Q) представляет собой объединение нескольких выпуклых гипермногогранников, полученных из гипермногогранника m⋅con(Q) параллельным переносом на все вектора, содержащиеся во втором слагаемом car(Q). Очевидно, эта сумма Минковского всегда является подмножеством (m+1)⋅con(Q), надо лишь выяснить, совпадает ли она с этим множеством. Если мы располагаем алгоритмами для решения задач I и II, то, учитывая предыдущее замечание и начальное предположение об истинной N-мерности множества Q, мы видим, что достаточно научиться решать следующую общую задачу:

Проверка объединения выпуклых гипермногогранников. Дан выпуклый N-мерный гипермногогранник P и M выпуклых гипермногогранников Q₁, Q₂, ..., Q_M. (Как всегда, мы предполагаем, что каждый гипермногогранник есть замкнутое множество, т.е. содержит свою границу.) Далее, каждый из этих гипермногогранников является истинно N-мерным, т.е. не принадлежит никакому линейному подпространству R^N с числом измерений, меньшим N. Для каждого из гипермногогранников нам известна система неравенств вида

a₁^(j)x₁^(j) + a₂^(j)x₂^(j) + ... + a_N^(j)x_N^(j) ≤ b^(j)

описывающих гиперполупространства, пересечением которых он является, а также перечень координат всех вершин, причем координаты вершин и коэффициенты в неравенствах являются рациональными числами (с использованием компьютерного представления, обеспечивающего бесконечную точность, т.е. в виде пары целых чисел неограниченной точности, представляющих числитель и знаменатель). Требуется выяснить, верно ли, что объединение Q=Q₁∪Q₂∪...∪Q_M совпадает с гипермногогранником P, т.е. Q=P — при этом заранее известно, что Q⊆P.

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

Кроме того, требование Q⊆P, хотя и выполняется в нашей задаче, в принципе может быть легко снято. Действительно, если Q содержит хоть одну точку q, не принадлежащую P, то это же верно для какого-нибудь из Q_i: q∈Q_i, но q∉P. В силу выпуклости гипермногогранника P это значит, что как минимум одна вершина какого-то гипермногогранника Q_i не принадлежит P: достаточно взять то гиперполупространство (из гиперполустространств, пересечением которых является P), которому не принадлежит выбранная точка q, и двигать соответствующую гиперплоскость в сторону увеличения гиперполупространства, пока не будет достигнута какая-нибудь вершина Q_i. Поскольку по предположению мы знаем все вершины гипермногогранников, то проверка, что Q_i содержит точки вне P, вполне тривиальна — достаточно проверить все вершины Q_i. Выполнив такую проверку для всех Q_i, мы убедимся, либо что Q содержит точки вне P, т.е. Q≠P, либо что Q⊆P. (Для сравнения, противоположная задача — проверка наличия точек P, не принажлежащих Q — далеко не столь тривиальна, ибо множество Q не является выпуклым.)

В многомерном случае поставленная задача выглядит довольно сложной, особенно если пытаться решать ее «в лоб», т.е. разрабатывать алгоритм для явного вычисления объединения произвольных выпуклых гипермногогранников с получением невыпуклого гипермногогранника-результата. Однако, эта задача уже решена, причем даже в более общей универсальной постановке: разработана библиотека алгоритмов, поддерживающая понятие многомерного гипермногогранника и умеющая выполнять с ними операции объединения, пересечения и разности, получая в качестве результатов новые гипермногогранники. Эти алгоритмы описаны в статье “The Extended Convex Differences Tree (ECDT) Representation for n-Dimensional Polyhedra”, Ari Rappoport, 1991 (эту статью нетрудно найти в Google). Такую библиотеку можно применить к данной задаче, получив качественное и эффективное решение — правда, возможно, придется адаптировать существующую реализацию для обеспечения вычислений бесконечной точности.

Вместе с тем я предлагаю специализированный алгоритм, рассчитанный на решение именно указанной выше задачи. Этот алгоритм вынесен в Приложение: см. далее.

Приложение. Алгоритм проверки объединения выпуклых гипермногогранников (задача III)

Январь–апрель 2013 г.

  Главная     8-й День творения     М. Анкудинов     AlgART Libraries