AlgART / Тексты

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

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

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

ОГЛАВЛЕНИЕ

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

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

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

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

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

Для произвольного точечного множества 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) и обозначать lcark(P) множество всех таких точек p, принадлежащих P, что при сдвиге такой точки либо на +1, либо на −1 вдоль указанной координаты мы оказываемся в точке, не принадлежащей P:

lcark(P) = {p=(x1,x2,...,xk,...,xN): pP, но pright=(x1,x2,...,xk+1,...,xN)∉P или pleft=(x1,x2,...,xk−1,...,xN)∉P}

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

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

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

con(P) ∩ ZN = P

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

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

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

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

AB = {a+b: aA, bB}

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

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

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

νA = ν⋅A = {νr: aA}

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

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

Это следует из того, что для всякого выпуклого множества A среднее арифметическое любого набора его точек также принадлежит A, поэтому всякая сумма a1+a2+...+an = namean ∈ nA, где amean = (a1+a2+...+an)/n ∈ A.

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

con(nP) = ncon(P) = ncon(P)

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

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

Лемма Шапли — Фолкмана. Если P1, P2, ..., Pn — произвольные точечные множества в N-мерном пространстве RN и их количество n>N, то их можно перенумеровать таким образом, что будет верно равенство:

сon(P1) ⊕ сon(P2) ⊕ ... ⊕ сon(Pn) = сon(P1) ⊕ сon(P2) ⊕ ... ⊕ сon(PN) ⊕ PN+1 ⊕ ... ⊕ Pn

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

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

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

ncon(P) = Ncon(P) ⊕ (nN)⊗P.

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

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

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

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

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

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

— 4 вершины тетраэдра Рива. Тетраэдр целиком расположен внутри «столбика» 0≤xy≤1, поэтому очевидно, что 4 его вершины суть единственные целые точки тетрадра con(P): con(P)∩ZN=P. То есть P — Z-выпуклое множество. Далее, кратное Минковского PP=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-выпуклость любых кратных Минковского nP.

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

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

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

con(nP) = con(NP) ⊕ (nN)⊗C.

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

p = p' + c1 + c2 + ... + cnN,

где все сi принадлежат каркасу C и, следовательно, являются целыми, а p'con(NP). Точка p', равная разности целых точек p−(c1+c2+...+cnN), сама является целой, а в силу Z-выпуклости NP отсюда следует, что она принадлежит NP, т.е. p' = p1+p2+...+pN, где все pj принадлежат P. Таким образом, мы нашли представление точки p в виде суммы n точек

p = p1 + p2 + ... + pN + c1 + c2 + ... + cnN,

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

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

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

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

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

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

2-мерная теорема Z-выпуклости кратных Минковского. Для любого целочисленного множества P на плоскости R2, если множество P Z-выпуклое, то любое множество nP, где 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 можно представить в виде суммы q1+q2, где обе точки q1 и q2 суть какие-то из вершин A, B или C (и, следовательно, принадлежат P). Иначе говоря, p∈2⊗P. Доказательство закончено.

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

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

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

Доказательство этой теоремы вполне элементарно. Поскольку CQ, то очевидно, что (mkP) ⊕ (kC) ⊆ (mkP) ⊕ (kQ), т.е. достаточно доказать обратное включение. Пусть p ∈ (mkP) ⊕ (kQ). Тогда, тем более,

pcon(mkP) ⊕ con(kQ) = (mkcon(P)) ⊕ kcon(Q) = k ⋅ [mcon(P) ⊕ con(Q)]

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

pk ⋅ [mcon(P) ⊕ С] = (mkcon(P)) ⊕ kС = con(mkP) ⊕ kС

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

p = p' + c ∈ (mkP) ⊕ (kС),

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

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

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

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

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

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

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

Допустим для определенности, что k=1, т.е. L есть линейный каркас вдоль первой координаты (доказательство совершенно аналогично для любой координаты). Разобьем множество P на цепочки точек Si, в которых первая координата x1 точки p = (x1x2, ..., xN) последовательно изменяется от одного значения x1=xmin(i) до другого значения x1=xmax(i) с шагом 1, причем при x1=xmin(i)−1 и x1=xmax(i)+1 мы уже оказываемся за пределами P:

Si = {(xmin(i)x2, ..., xN), (xmin(i)+1, x2, ..., xN), ..., (xmax(i)−1, x2, ..., xN)}, (xmax(i)x2, ...,xN)},
SiP, но (xmin(i)−1, x2, ..., xN)∉P и (xmax(i)+1, x2, ..., xN)∉P

Очевидно, линейный каркас L состоит в точности из первых и последних точек всех таких цепочек (xmin(i)x2, ..., xN) и (xmax(i)x2, ..., xN), а число элементов в каждой цепочке есть ||Si||=xmax(i)xmin(i)+1.

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

P =  Si,

то

PP =  (SiSj),

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

SiSj = Si ⊕ {a(j), b(j)}

где a(j)=(xmin(j)x2, ..., xN) и b(j)=(xmax(j)x2, ..., xN) суть первая и последняя точки цепочки Sj. (Этот факт, касающийся сумм Минковского одномерных целочисленных множеств, легко проверяется непосредственно и является следствием того, что ||Si|| ≥ ||Sj||.) Таким образом,

PP = ij (SiSj) = ij (Si ⊕ {a(j), b(j)}) = PL.

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

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

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

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

nP = PC ⊕ 2C ⊕ ... ⊕ 2qCrC

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

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

PC ⊕ 2C ⊕ ... ⊕ 2qC = 2q+1P.

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

PC ⊕ 2C ⊕ ... ⊕ 2qCrC = 2q+1PrC = (2q+1r)⊗P ⊕ (rPrC) = (2q+1r)⊗P ⊕ 2rP = nP

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

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

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

nP = Plcar(P) ⊕ CC ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2qC ⊕ 2qCrC

или

nP = Plcar(P) ⊕ CC ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2qC ⊕ 2qC ⊕ 2q+1CrC

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

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

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

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

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

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

PPCC ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2qC ⊕ 2qCrC,
PPCC ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2qC ⊕ 2qC ⊕ 2q+1CrC

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

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

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

nP = Plcar(P) ⊕ lcar(P) ⊕ CCC ⊕ 2C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2qC ⊕ 2qC ⊕ 2qCrC,

или

nP = Plcar(P) ⊕ lcar(P) ⊕ CCC ⊕ 2C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2qC ⊕ 2qC ⊕ 2qC ⊕ 2q+1CrC,

или

nP = Plcar(P) ⊕ lcar(P) ⊕ CCC ⊕ 2C ⊕ 2C ⊕ 2C ⊕ ... ⊕ 2qC ⊕ 2qC ⊕ 2qC ⊕ 2q+1C ⊕ 2q+1CrC

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

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

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

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

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

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

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

a1x1a1+d1,
a2x2a2+d2,
. . .
aNxNaN+dN

где ai, di суть какие-то целые числа, di≥0 — длины ребер. Любой такой гиперпараллелепипед может быть представлен в виде суммы Минковского ~log2 ||P|| слагаемых (||P||=(d1+1)(d2+1)...(dN+1) — число элементов P):

P = {(a1, a2, ..., aN)} ⊕
k=0,1,... {(0, 0, ..., 0}, {2k, 0, ..., 0)} ⊕ {(0, 0, ..., 0}, {r1, 0, ..., 0)} ⊕
k=0,1,... {(0, 0, ..., 0}, {0, 2k, ..., 0)} ⊕ {(0, 0, ..., 0}, {0, r2, ..., 0)} ⊕
. . .
k=0,1,... {(0, 0, ..., 0}, {0, 0, ..., 2k)} ⊕ {(0, 0, ..., 0}, {0, 0, ..., rN)}

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

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

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

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

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

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

IP = (I c ⊕ −P) c,

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

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

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

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

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

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

J(x1, x2, ..., xN) = max (I(x1u1, x2u2, ..., xNuN) + uN+1) для всех точек p=(u1u2, ..., uNuN+1)∈P

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

J(x1, x2, ..., xN) = min (I(x1+u1, x2+u2, ..., xN+uN) − uN+1) для всех точек p=(u1u2, ..., uNuN+1)∈P

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

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

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

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

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

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

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

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

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

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

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

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

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

O(S⋅log ||P||)

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

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

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

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

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

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

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

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

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

псевдокаркас pcar(Qd) есть множество всех таких точек pQ, что для любой целой точки r = (r1, r2, ..., rN) из (небольшого) гиперкуба с центром в начале координат и длиной ребра 2d (в двумерном случае попросту квадрата 2d×2d) — т.е. такой точки, что для всех ее целых координат верно |ri|≤d — либо точка p+r, либо точка pr не принадлежат 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, 2Q, ..., NQ. Проверка Z-выпуклости единственного множества Q нужна также и в двумерном случае, если мы не знаем заранее «происхождение» множества Q, а это вполне вероятная ситуация для универсальной алгоритмической библиотеки.

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

a1(j)x1(j) + a2(j)x2(j) + ... + aN(j)xN(j)b(j), 0 ≤ j < L,

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

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

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

a1(j)x1(j) + a2(j)x2(j) + ... + aN(j)xN(j)kb(j)

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

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

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

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

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

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

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

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

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

a1(j)x1(j) + a2(j)x2(j) + ... + aN(j)xN(j)b(j)

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

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

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

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

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

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

Приведем алгоритм, решающий задачу Проверка объединения выпуклых гипермногогранников, сформулированную в предыдущем разделе. Это рекурсивный алгоритм, основанный на снижении числа измерений. Собственно алгоритм относительно несложен, но необходимость строгих и аккуратных формулировок делает изложение несколько громоздким.

Изложим вначале неформально основную идею этого алгоритма. Если QP (но QP), значит, внутри P есть некая «свободная область», не занятая гипермногогранниками Qi. Эта область, очевидно, сама является многогранной, и грани этой области суть невырожденные (N−1)-мерные гипермногогранники. Но эти грани суть не что иное, как грани или фрагменты граней исходных гипермногогранников P, Q1, Q2, ..., QM. Значит, нам достаточно проанализолвать каждую грань каждого из исходных гипермногогранников и убедиться, что в рамках этой грани не остается свободных (N−1)-мерных областей, «не охваченных» объединением Q=Q1Q2∪...∪QM. А эта задача совпадает с исходной задачей для (N−1)-мерного пространства.

Перейдем теперь в аккуратному изложению алгоритма.

Прежде всего заметим, что все рассматриваемые выпуклые гипермногогранники P и Qi суть замкнутые множества, и граница каждого из них состоят из конечного числа гипермногогранников (граней) меньшей размерности N−1. При этом граница каждого выпуклого гипермногогранника делит все пространство RN на три части: внутренность (открытое множество), собственно граница и бесконечная внешность (тоже открытое множество).

Обозначим P° внутренность гипермногогранника P и рассмотрим теоретико-множественную разность

D = P° \ Q = P° ∩ Q c = P° ∩ Q1 cQ2 c ∩ ... QM c

где X c = RN \ X означает теоретико-множественное дополнение множества X до всего эквлидова пространства RN. Про эту разность D можно сказать следующее.

  1. Множество D является непустым тогда и только тогда, когда QP. Докажем это. Очевидно, что при Q=P оно пусто. Пусть QP. По предположению, QP, значит, есть какая-то точка p, принадлежащая одновременно замкнутому множеству P и открытому множеству Q c. Точка p принадлежит либо границе P, либо внутренности P°. Во втором случае это значит, что pD; в первом случае, по определению границы, в любой окрестности p найдется какая-нибудь точка p', принадлежащая внутренности P°. Рассмотрим, в частности, такую окрестность, которая целиком содержится в Q c (она всегда существует в силу открытости Q c), и выберем в ней какую-нибудь точку p'∈P°. Очевидно, p'∈D. В обоих случаях мы нашли точку, принадлежащую D. Таким образом, из QP следует, что D непусто.

  2. Множество D (когда оно непусто) является открытым — ведь это пересечение конечного числа открытых множеств.

  3. Множество D (когда оно непусто) является гипермногогранником, точнее, внутренностью гипермногогранника, являющегося замыканием D (мы предполагаем, что гипермногогранники суть замкнутые множества, содержащие свою границу). Это верно для любой теоретико-множественной разности гипермногогранников: вычитая гипермногогранник из гипермногогранника, мы снова получаем гипермногогранник (с точностью до точек границ). В общем случае, конечно, D уже не является выпуклым.

  4. Пусть D непусто. Обозначим его границу ∂D; одновременно ∂D есть граница гипермногогранника — замыкания D. Как и всякая граница гипермногогранника, ∂D есть объединение конечного числа (N−1)-мерных (лежащих в (N−1)-мерных линейных подпространствах RN) гипермногогранников-граней Δ1, Δ2, ...:

    D = Δ1 ∪ Δ2 ∪ ...

    Без ограничения общности все эти гипермногогранники-грани можно считать выпуклыми (ибо каждый невыпуклый гипермногогранник есть объединение конечного числа выпуклых) и при этом истинно (N−1)-мерными, т.е. не принадлежащими линейным подпространствам с меньшим числом измерений. Для выпуклого гипермногогранника такая «истинная (N−1)-мерность» равносильна тому, что он имеет ненулевой (N−1)-мерный объем.

  5. Каждый из (N−1)-мерных гипермногогранников Δ1, Δ2, ... на всем своем протяжении «вплотную примыкает» к внутренности D, т.е. каждая его точка в любой своей окрестности содержит точки из D — это следует из определения границы и из того, что множество D является открытым.

  6. Каждый из (N−1)-мерных гипермногогранников Δ1, Δ2, ..., как и вся граница ∂D, является подмножеством объединения границ открытых множеств, пересечением которых является D, т.е. объединения границ всех гипермногогранников P, Q1, Q2, ..., QM. (Очевидно, граница пересечения конечного числа открытых множеств есть подмножество объединения границ этих множеств: это элементарно доказыватся рассмотрением какой-нибудь точки такой границы.)

  7. Если D непусто, то среди всех граней всех гипермногогранников P, Q1, Q2, ..., QM существует минимум одна грань Φ одного из этих гипермногогранников, к которой открытое множество D «подходит вплотную» на протяжении некоторой невырожденной (N−1)-мерной области. Выражаясь более строго, у этой грани существует некое подмножество Γ, являющееся истинно (N−1)-мерным выпуклым гипермногогранником, в окрестности каждой точки которого имеются также точки из открытого множества D. Докажем это. Возьмем какую-нибудь грань Δi. Эта грань есть подмножество объединения всех граней всех гипермногогранников P, Q1, Q2, ..., QM:

    Δi ⊆ Φ1 ∪ Φ2 ∪ ...

    где Φ1, Φ2, ... суть все грани этих гипермногогранников, причем они сами являются выпуклыми (N−1)-мерными гипермногогранниками (ведь они суть грани выпуклых N-мерных гипермногогранников). Следовательно,

    Δi = (Δi∩Φ1) ∪ (Δi∩Φ2) ∪ ...

    Каждое из множеств Δi∩Φ1, Δi∩Φ2, ..., будучи пересечением двух выпуклых гипермногогранников, есть либо пустое множество, либо истинно (N−1)-мерный выпуклый гипермногогранник, либо выпуклый гипермногогранник меньшего числа измерений (т.е. содержащийся в линейном подпространстве с меньшим числом измерений). Очевидно, что хотя бы один из этих выпуклых гипермногогранников Γ=Δi∩Φk будет истинно (N−1)-мерным — иначе мы не смогли бы получить в качестве их объединения истинно (N−1)-мерное выпуклое множество Δi; — соответствующая ему грань Φk и есть искомая грань Φ. (Последнее утверждение действительно очевидно из соображений (N−1)-мерного объема, но его можно формально доказать проще, рассмотрев (N−1)-мерное линейное подпространство, являющееся продолжением гипермногогранника Δi. В терминах этого (N−1)-мерного Эвклидова пространства, выпуклый гипермногогранник Δi имеет непустую внутренность, следовательно, хотя бы одно из выпуклых множеств Δi∩Φ1, Δi∩Φ2, ..., объединением которых он является, тоже обязано иметь непустую внутренность. Оно и будет истинно (N−1)-мерном гипермногогранником Δi∩Φk.)

Предположим теперь, что QP, и пусть Φ — указанная выше грань, а Γ — указанный выше истинно (N−1)-мерным выпуклый гипермногогранник (Γ⊆Φ). Рассмотрим сечение всей конструкции гиперплоскостью U, расположенной параллельно грани Φ рядом с ней с той стороны, где к ней «вплотную примыкает» открытое множество D. Рассмотрим сечения всех гипермногогранников P, Q1, Q2, ..., QM этой гиперплоскостью, т.е. (N−1)-мерные гипермногогранники PU, Q1U, Q2U, ..., QMU. По мере приближения U к Φ эта гиперплоскость рано или поздно пересечет открытое множество D — ведь оно вплотную примыкает к Φ «на протяжении» целого (N−1)-мерного гипермногогранника Γ. В этот момент мы обнаружим, что для этих гипермногогранников имеет место неравенство PUQU (здесь QU=(Q1U)∪(Q2U)∪...∪(QMU)), причем разность этих множеств (PU) \ (QU) будет иметь положительный (N−1)-мерный объем (более формально, в терминах линейного подспространства U оно будет иметь непустую внутренность). Более того, так будет и в предельном положении, когда U совпадет с продолжением грани Φ — даже в предельном положении эта разность будет содержать в качестве подмножества, как минимум, непустой истинно (N−1)-мерным выпуклый гипермногогранник Γ. Т.е. в предельном положении мы имеем

lim PU ≠ lim QU = (lim Q1U) ∪ (lim Q2U) ∪ ... ∪ (lim QMU)

Если же, наоборот, Q=P, то очевидно, что для любого положения гиперплоскости U PU=QU, и то же самое, конечно, верно для предельного состояния обоих пересечений:

lim PU = lim QU

Чтобы наши предельные переходы были вполне строгими, конечно, нужно быть уверенными, что все упомянутые множества (гипермногогранники) меняются непрерывно. Для достижения этого уровня строгости достаточно рассмотреть все возможные точки пересечения всех наборов из N гиперплоскостей, являющихся продолжениями всех граней всех гипермногогранников P, Q1, Q2, ..., QM. Этих точек конечное количество, и мы можем найти среди них ту, которая находится на минимальном ненулевом геометрическом расстоянии h>0 от предельного положения lim U, т.е. от продолжения грани Φ. Очевидно, в процессе предельного перехода можно считать, что гиперплоскость U уже находится к продолжению грани Φ ближе, чем на расстоянии h, и тогда можно быть уверенными, что в процессе дальнейшего приближения U к Φ в изменении фигур наших пересечений PU, Q1U, Q2U, ..., QMU уже не будет никаких особенностей — изменение этих фигур будет описываться непрерывными, более того, линейными функциями.

Для каждой, выбранной произвольно грани Φ и для каждого из двух возможных направлений приближения гиперплоскости U нет больших проблем вычислить указанное предельное значение всех гипермногограников lim PU, lim Q1U, lim Q2U, ..., lim QMU, как в виде системы неравенств (это получается почти автоматически), так и в виде набора вершин (координаты этих вершин получаются решением систем линейных уравнений, т.е. могут быть представлены в виде рациональных чисел неограниченной точности). Нужно просто взять в качестве U продолжение грани Φ, но аккуратно исключить из списка пересечений PU, Q1U, Q2U, ..., QMU те гипермногогранники, которые прикасаются к этой гиперплоскости своим внешним краем со стороны, противоположной движению U. (В процессе движения U они давали пустое пересечение с U, и только в предельном положении «внезапно» получили непустые пересечения с U в виде куска своей поверхности — в предельном переходе этих пересечений не было.) Координаты вершин нам пригодятся, чтобы убедиться, что гиперплоскость действительно пересекает гипермногогранник (есть вершины, лежащие по разные стороны от нее) либо касается его (некоторые вершины лежат на гиперплоскости, а остальные лежат по одну сторону). Очевидно, гипермногогранники, которые не имеют общих точек с гиперплоскостью U, можно вообще не рассматривать.

Таким образом, мы приходим к той же самой задаче для гипермногогранников меньшей размерности

lim PU, lim Q1U, lim Q2U, ..., lim QMU.

Достаточно лишь ввести какую-нибудь декартову систему координат на предельной гиперплоскости lim U и пересчитать в эту систему все координаты вершины и коэффициенты систем неравенств — они при этом останутся рациональными числами. (На самом деле в практическом алгоритме этот шаг можно опустить и продолжать работать в исходной системе координат, запомнив, что мы решаем задачу в рамках выбранного подпространства lim U.)

Если мы рекурсивно решим такую (N−1)-мерную задачу для всех таких наборов гипермногогранников, рассматривая по очереди приближение гиперплоскости U с каждой из двух сторон к каждой из граней Φ каждого из гипермногогранников P, Q1, Q2, ..., QM, то мы либо в какой-то момент обнаружим непустую разность D = P° \ Q, и это будет значить, что QP, либо получим положительный ответ (совпадение гипермногогранников) для всех подзадач, и это будет значить, что Q=P. В одномерном случае дальнейшая рекурсия не нужна: задача решается «в лоб» простой сортировкой вершин.

Кстати, легко заметить, что в действительности нет смысла проверять оба возможных направления приближения гиперплоскости U к грани Φ. Если это грань одного из гипермногогранников Qi, то нет смысла рассматривать ту сторону грани, с которой находится сам гипермногогранник Qi: там «ближайшая окрестность» Φ уже «занята» этим гипермногогранником, так что там нет смысла искать открытое множество D = P° \ Q. Наоборот, если это грань гипермногогранника P, то нет смысла приближать гиперплоскость U «снаружи» P, ибо там мы всегда имеем пустые пересечения PU и QU. Более того, можно заметить, что грани гипермногогранника P вообще можно не тестировать — граница ∂D непустого множества D не может состоять исключительно из кусков выпуклого гипермногогранника P, в ней непременно должны встретиться также куски граней гипермногогранников Qi (исключением могла бы стать ситуация, когда все Qi лежат целиком вне P, но по условию мы имеем QP).

Этот алгоритм, конечно, относительно трудоемкий, особенно при большом числе измерений (N=4) и большом числе граней у выпуклой оболочки con(Q). Однако, в принципе ничто не мешает ограничить его по времени выполнения некоторым лимитом, и если время выполнения слишком велико, то отказаться от решения задачи III и выбрать то из разложений, для которого условие теоремы каркасных разложений mcon(Q) ⊕ car(Q) = (m+1)⋅con(Q) для данной размерности гарантировано. Кроме того, можно поддерживать специальную базу данных разных вариантов множества Q (ведь на практике постоянно применяются одни и те же множества-шаблоны) и хранить в этой базе результаты выполненного анализа. При построении базы данных можно «позволить себе» достаточно долго работающие алгоритмы и использование специализированных компьютеров, более мощных, чем обычно.

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

  Главная     О Боге и не только     Библия     М. Анкудинов     AlgART Libraries     WebWarper  
Hot at AlgART: HTML для чайников | Trinity for non-Christians | Диалог с Богом | Religion and Geometry