Задача о построении образов двумерной мозаики

УДК 519.1

САМЕР И.М. АЛЬШАЛАМЕ

ЗАДАЧА О ПОСТРОЕНИИ ОБРАЗОВ ДВУМЕРНОЙ МОЗАИКИ

Abstract: It is discussed the problem about building discrete images on the plane. This work is continuation of researches of the same author about creation of colour images with using given set of templates. Introducing notions homomorphity of template and its self-sufficienty for building basis of decisions of the main system of linear equations in the class of residues on the finite module. There are proved the set of statements about characteristics of some templates and about existence of decisions of the denoted system of equations.

Анотація: Розглядається задача про побудову дискретних образів на площині. Робота є продовженням досліджень того ж автора про створення кольорових зображень за допомогою заданої множини шаблонів. Вводяться поняття гомоморфності шаблона та його самодостатності для побудови базису розв&язків основної системи лінійних рівнянь у класі лишків за скінченним модулем. Доводиться низка тверджень про властивості деяких шаблонів та про існування розв&язків вказаної системи рівнянь.

Ключові слова: шаблон, кольорові дискретні зображення, лінійні рівняння, гомоморфність.

Аннотация: Рассматривается задача о построении дискретных образов на плоскости. Работа является продолжением исследований того же автора о создании цветных изображений с помощью заданного множества шаблонов. Вводятся понятия гомоморфности шаблона и его самодостаточности для построения базиса решений основной системы линейных уравнений в классе вычетов по конечному модулю. Доказывается ряд утверждений о свойствах некоторых шаблонов и существовании решений указанной системы уравнений.

Как уже отмечалось [1], в теории распознавания образов многие задачи сводятся к рассмотрению прямоугольного поля, разбитого на квадратные клетки, которые имеют различную раскраску, в совокупности представляя определенный образ. Обозначим такое поле p с числом клеток N = mn, где m - число горизонтальных последовательных клеток (строк), а n - число столбцов.

Определенному цвету поставим в соответствие число из множества Q = {0,1,...,K — 1} , а

Q соответствует всему множеству заданных цветов. Пусть имеется набор связных фигур, состоящих из клеток определенного цвета (не равных 0) и называемых шаблонами S ={sj,s2,...,sp} . Здесь под связной фигурой подразумевается множество клеток, каждая из которых имеет общую сторону хотя бы с одной клеткой из этого множества. Предполагается, что количество каждого типа шаблонов ограничено числом r (t), где t = 1,2,...,p. Часто возникает

вопрос, можно ли с помощью накладывания имеющихся в наличии шаблонов построить на чистом поле p (окрашенном в цвет 0) заданный образ (мозаику)? При этом, в зависимости от конкретной задачи, под операцией накладывания (сложения) может подразумеваться различное содержание. В общем виде операцию накладывания можно задавать бинарной таблицей. Решить задачу о мозаике означает найти, как при заданном способе накладывания красок построить заданный образ на плоскости p.

Так как шаблон можно накладывать любой стороной, а также поворачивать в плоскости на любой угол, кратный 90° то проще считать, что мы имеем дело с разными шаблонами, которые всегда располагаются фиксированным образом в пространстве.

Определение 1. Назовем меткой шаблона самую левую среди самых верхних клеток шаблона. Заполним все поле всеми возможными способами множеством различных шаблонов. Пусть каждому шаблону (точнее, его месту на плоскости ж) поставим в соответствие переменную

хг (г = 1,2,..,р), равную 0 или 1. Тогда задача о возможности построения необходимой мозаики на

поле ж при заданном множестве шаблонов £ =1^;,$2,...,sp} сводится к решению системы линейных уравнений

£ X = Ъ}.; ] = 1,2,..., N. (1)

Здесь сложение для каждой клетки происходит по заданной операции сложения, а г -й шаблон учитывается только тогда, когда его пересечение с ] -й клеткой не пусто.

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

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

Таблица 1. Пример накладывания цветов

О Белый Голубой Желтый Красный Синий

Белый Белый Голубой Желтый Красный Синий

Голубой Голубой Синий Красный Синий Красный

Желтый Желты й Красный Голубой Белый Голубой

Красный Красный Синий Белый Желты й Белый

Синий Синий Красный Голубой Белый Красный

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

Если перенумеровать цвета с условием, что белый цвет=0, голубой=1, желтый=2, красный =3 и синий=4, то сложение цветов можно записать в виде бинарной таблицы.

Однако эта таблица обладает недостатками, самый главный из которых это то, что здесь сложение не удовлетворяет аксиоме ассоциативности. Например, (1(+ 2)0 3 = 3 ©3 = 2. С другой стороны, 1+(2+ 3)=1+0=1^2.

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

Самая простая задача о мозаике возникает для поля, состоящего из одной строки длины п , которую назовем задачей о линейной мозаике. Соответственно каждый шаблон состоит из последовательности I(1 < I < п) раскрашенных клеток и также называется линейным шаблоном. Еще одно упрощение состоит в том, что число цветов уменьшается до двух - это белый и черный цвет, то есть К = 2 и Q = {0,1} . Все шаблоны при этом одноцветны и состоят из l черных

смежных клеток. Метка шаблона здесь определяется однозначно. В данном поле все шаблоны с учетом поворота на 1800 имеют только два типа положения (если цветов больше двух) или один.

Пронумеруем клетки поля от 1 до п. Образом на таком поле будет произвольное множество черных клеток. Общее число образов (без учета пустого, окрашенного белым цветом)

равно 2п — 1. Множество типов шаблонов £ ={^1,52,...,эр} (эг ф Эу; 1 < г, у < р) будем задавать как множество чисел, где равно числу соответствующих черных клеток. Легко убедиться, что шаблон (г = 1,2,...,р) может разместиться на поле п — +1 способом, если двигать его

последовательно слева направо. Будем считать, что у нас есть п — +1 копий шаблона si, и

будем обозначать si (а) соответствующий шаблон, метка которого имеет координату а(а = 1,2,...,п — si +1). Пусть, например, п = 11, а £ = (3,5,7). Тогда на строке шаблон можно расположить 11-7+1=5 способами (рис. 1)

*3(4) sз(5)

Рис. 1. Размещение шаблона Если исходить из возможных координат метки шаблона, то можно записать уравнение каждого шаблона в виде:

^ ~ (а, а+1, а+ 2);

э2 ~ (а, а+1, а+ 2, а+3, а+4);

(а, а+1, а+ 2, а+3, а+ 4, а+ 5, а+6).

Таким образом, прежде чем строить систему уравнений (1), мы исходим из того, что у нас есть набор типов шаблонов £ = {^1,я2,...,эр} , имеется п — ^ +1 шаблонов типа 1, п — э2 +1

шаблонов типа 2 и т.д. Всего у нас должно быть N(5) = р(п +1) — ^шаблонов и

соответственно столько же переменных Ху (у = 1,2,...,N(5)), которые принимают значения 1 или 0

в зависимости от того, присутствуют они в решении или нет.

Рассмотрим на примере, как составляются уравнения для двух шаблонов. Пусть п = 9 , а

£ ={4,7} . Для первого шаблона необходимо 9-4+1=6 переменных, а для второго 9-7+1=3 переменных. Вместе получаем вектор X = {хг,х2,..., х9} , столько же компонент имеет вектор правых частей В = {ЪХ,Ь2,...,Ъ9} . На рис. 2 показано расположение всех шаблонов. Как видно из рисунка, в первом столбце принимают участие переменные х1 и х7 , что соответствует первой строке системы уравнений (2). Во втором столбце участвуют уже четыре переменных хг, х2, х3 и х4 , которые образуют вторую строку (2) и т.д.

Ь1 Ь2 Ь3 Ь4 Ь5 Ь6 B7 Ь8 Ь9

Рис. 2. Уравнение образа для п = 9 , £ = {4,7}

Складывая по столбцам соответствующие переменные, которые представляют все шаблоны, получаем систему линейных уравнений.

X1 + ...

x1 + x2 +. . .

x1 + x2 + x3 + . . .

x1 + x2 + x3 + x4 + . . .

x2 + x3 + x4 + x5..

+ х7.

+ X7 + X8 + X7 + X8 + X9

= Ь1 = 132 = Ь

+ х7 + х8 + х9 = Ь4

+ Х7 + Х8 + Х9 = Ь5

х3 + х4 + Х5 + Х6 + х7 + х8 + х9 = Ь6

Х4 + Х5 + Хб + Ху + х^ + Х9 = Ьу

х5 + Х6 + ■■■ + Х8 + Х9 = Ь8

Х6 + ■■■ + Х9 = Ь9

В работах [2-4] полностью решена задача о линейной мозаике для двух цветов и начаты исследования для линейных мозаик с числом цветов больше двух. В данной работе уточняются некоторые аспекты этой задачи для плоского поля ж и двух красок. Пусть задан образ, представленный на поле ж с размерами N = 30, где т = 5 и т = 6.

Рис. 3. Образ, составленный из 3-х типов шаблонов Несложно убедиться, что этот образ составлен с помощью 3-х типов шаблонов (на рис.3. справа). Поскольку шаблон можно накладывать любой стороной, а также поворачивать в плоскости на любой угол, кратный 900, будем считать два типа положений шаблона разными, если их нельзя совместить параллельным переносом. Очевидно, что таких типов не больше 8. Пронумеруем клетки поля от 1 до N сначала по первой строке, затем по второй и так до конца. Зная координату метки шаблона, можно однозначно расположить его на поле. Рассмотрим всевозможные положения указанных на рис. 3 шаблонов (рис. 4) (метка обозначена белым кружочком).

О О О я о о

О О о о о о

Рис. 4. Типы положений для каждого шаблона В нашем примере шаблон ^ имеет 4 вида положений, шаблон э2 - 8 видов, а 53 - только

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

шаблонов, т.е. £ = }, 1 < / < 13 . Если метку произвольного шаблона обозначить координатой а,

то уравнения шаблонов, например, я, я2, я3, я4 и я13, будут иметь вид

я1(а) = (а, а + 2, а + п, а + п + 1, а + п + 2) ; я2(а) = (а, а + 1, а + 2, а + п , а + п + 2) ;

я3(а) = (а, а + 1, а + п, а + 2п, а + 2п + 1) ; (3)

я4(а) = (а, а + 1, а + п + 1, а + 2п, а + 2п + 1) ;

я5(а) = (а, а + п — 1, а + п, а + п + 1, а + 2п) .

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

таблицу таких положений для последнего шаблона я13 (рис. 5).

Рис. 5. Допустимые положения шаблона я13

Каждый шаблон можно поместить в минимальный прямоугольник размером Г Х гг . Тогда число допустимых положений шаблона равно (т — г +1)(п — ^ +1) = N(я{). Для шаблона

я13 такой минимальный прямоугольник имеет размеры 3х3, поэтому число допустимых положений

для него равно (5—3+1)(6—3+1)=12, что согласуется с рис. 5. Число положений всех шаблонов теперь легко подсчитать, оно равно

N (Я) = £ N (я) = £ (т — г +1)(п — ^ +1) =

^ г= . (4)

р р р

= р (т +1)(п +1) — (п +1) £ г —(т +1) £ ^

i=\\ i=\\ i=\\

Столько же необходимо и переменных х}- (] = 1, 2,..., N (я)). При составлении системы

уравнений (1) для плоского поля уже нельзя воспользоваться плоским представлением наложения шаблонов, как это было возможно для линейной мозаики (рис. 2). Здесь мы воспользуемся уравнениями шаблонов (3), подставляя вместо а всевозможные значения меток. Для примера рассмотрим поле ж, у которого N =34=12, а в качестве шаблонов возьмем шаблоны 1 и 3 из рис.

Согласно этим допустимым положениям в системе (6) должно участвовать 16 переменных. Если вместо параметра а подставить в (3) значения из рис. 6, то каждой переменной будет сопоставлен кортеж, определяющий уравнение соответствующего шаблона.

ss(a) S4(a)

Рис. 6. Допустимые положения шаблонов

(1, 3, 5, 6, 7), x2 ~ (2, 4, 6, 7, 8), x3 ~ (5, 7, 9, 10, 11), x4 ~ (6, 8, 10, 11, 12);

~ (1, 2, 3, 5, 7), x6 ~ (2, 3, 4, 6, 8), x7 ~ (5, 6, 7, 9, 11), x8 ~ (6, 7, 8, 10, 12);

(1, 2, 5, 9, 10), xl0 ~ (2, 3, 6, 11, 12), xn ~ (3, 4, 7, 11, 12), xl2 ~ (1, 2, 6, 9, 10); (2, 3, 7, 10, 11), xl4 ~ (3, 4, 8, 11, 12), xl5 ~ (2, 5, 6, 7, 10), xl6 ~ (3, 6, 7, 8, 11).

Теперь для каждой клетки Ъу(] = 1,2,... ,12) запишем уравнение, куда будут входить

переменные, кортежи которых содержат номер этой клетки. Получаем искомую систему.

Х1 +X5 +X9 +X12 = b1

+X2 +X5 +X6 +X9 +X10 +X12 +X13 +X15 = b2

Х1 +X5 +X6 +X10 +X11 +X13 +X14 +X16 = b3

+X2 +X6 +X11 +X14 = b4

x1 +x3 +X5 +X7 +X9 +X15 = b5

x1 +X2 +X4 +X6 +X7 +X8 +X10 +X12 +X15 +X16 = b6

+X2 +X3 +X5 +X7 +X8 +X11 +X13 +X15 +X16 = b7

+X2 +X4 +X6 +X8 +X14 +X16 = b8

+X3 +X7 +X9 +X12 = b9

+X3 +X4 +X7 +X10 +X11 +X13 +X14 +X16 = b11

+X4 +X8 +X11 +X14 = b12

Задавая образ в виде вектора Ъ = {ЪХ,b2,...,bN} , можно решать заданную систему. Чтобы

решение существовало и было единственным, необходимо чтобы определитель этой системы был равен 1 (mod 2).

Если же определитель равен 0 (mod 2), то на правые части системы (5) или на образ накладываются некоторые ограничения. В этом случае надо искать ранг системы и вопрос о поиске хотя бы одного её решения усложняется.

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

представим, что необходимо построить образ Ъ, у которого Ъа ° 1(шоё2)(1 <а< п), а для всех

j Фа bj °0(mod2) . Если при этом существует решение системы (6), то будем называть такой образ единицей и обозначать l(а) .

В нашей системе уравнений (5) положим x3 = x5 = x9 = x13 = x15 = 1, остальные xt = 0 . В результате получим b6 = 1, остальные bj = 0(j Ф 6). Таким образом, мы построили единицу, уравнение которой получим, если вместо xt подставим соответствующие шаблоны.

l(6) = [Si (5) + S2 (1) + S3 (1) + (2) + S5 (2)] (mod 2) . (6)

В этой системе можно получить только еще одну единицу /(7), если все координаты меток

шаблонов в (6) увеличим на 1. Это происходит по той причине, что мы не можем больше сдвигать

шаблоны, занятые в (6) ввиду ограниченности поля.

Будем говорить, что подмножество шаблонов S0 с S образует базис, если с его помощью

можно построить любую единицу l(а)(1 <а< N). Самым простым базисом есть шаблон,

состоящий из одной клетки. Для линейной мозаики одного шаблона с числом клеток, больше 1, для образования базиса недостаточно. Для двух шаблонов {S1,S2 } в [2] доказана теорема, что если

s1 + s2 < n + 2 и НОД (s1, s2) = 1, то они составляют базис решения для линейной мозаики.

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

Назовем шаблон s гомоморфным единице l(а) , если существует решение уравнения

Шаблон s называется самодостаточным для базиса, если существует решение уравнения (7) для любого 1 <а< N .

Утверждение 1. Если |S| ° 0(mod2) , то шаблон s не гомоморфен ни одной единице.

Это следует из того, что в (7) все операции в левой части приводят к результату 0(mod2) , что противоречит правой части.

Теорема 1. Линейный шаблон s = 2l + 1(l > 1) не гомоморфен ни одной единице. Доказательство. Построим для шаблона s систему уравнений (1) на поле p размером N = mXn . Число горизонтальных шаблонов, расположенных в каждой строке, равно n — s +1, а всех - m(n — s +1). Обозначим соответствующие переменные xk, где k = j + (i — 1) (n — s +1)

(1 < i < m; 1 < j < n — s +1). Число всех вертикальных шаблонов будет равно n(m — s +1).

Обозначим соответствующие переменные yv, где v = j + n(i — 1) (1 < i < m — s +1; 1 < j < n).

Рассмотрим матрицу Л(т1,т2) специального вида, которая обладает следующими свойствами:

- число её столбцов равно т2;

- в г -м столбце (1 < ] < т2) первые г — 1 элементов равны 0, затем следует т1 единиц, а дальше до конца опять нули.

Пусть т1 = 5, т2 = 4 . Тогда матрица Л (5,4) имеет вид

А(5,4) =

(1 0 0 0 ^

V 0 0 0 1)

Число строк в такой матрице равно т1 + т2 — 1, поэтому в ней всегда т1 — 1 строк

зависимы. Если т2 < т1, то строки от т2 до т1 состоят из одних единиц.

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

Это легко достигнуть, если заметить, что начиная с (т1 +1)-й строки слева появляются нули. Поэтому, если к і -й строке (1 < і < т1) , в которой справа есть нули, добавить все строки с

номером і(шодт1), то получим необходимое заполнение единицами.

В нашем примере строки 4 и 5 (от т2 до т1) уже состоят из единиц. Если к первой строке добавить строку 6 ° 1(шоё5), то получим все единицы и так до 3-й строки.

Если рассматривать систему уравнений А(т2, т1)X = С, где X и С векторы размерности (т2 + т1 — 1) , то после образования единиц в первых т1 строках получим разбиение

правых частей на т1 классов:

IС ° IС °... ° IС

і=1 (шоё ) і=2 (шоё ) і=0 (шоё т]_)

(шоё 2).

Введем понятие индексной функции от двух аргументов:

Щ2) = (Щ1 — 1)(п2 — 5 + 1) ,

где 5 - длина шаблона.

Обозначим ^ =(хь+2, ■■■, хр+ щ—5+1 ), (1 </&<т) ;

Ъ=( У^ Уу+ 2,■■■, Уп п—5+1), (1 < ] < п),

где /3 = ф(г, т), У =ф(], п) .

Запишем уравнение (1) для первой строки поля. В наших обозначениях это

А(я, пЦГ + Епа( = Ь ; Ь = ^..^Ьп).

Введем для удобства символические векторы-столбцы:

Тогда система (1) запишется в клеточном виде:

ЕтЛ + А (я, т — я + 1)Х = В.

Воспользуемся леммой 1 о свойствах матриц Л (т1,т2) для получения одинаковых

элементов (Гг в первой и второй клеточных строках. Для этого в первой клеточной строке сложим

все клеточные строки матрицы А(я,т — я +1) с номером 1(шоёя), а во второй все строки с номером 2(шоё я). Здесь сложение подразумевается как сложение соответствующих матриц.

После этого в первых двух клеточных строках получим во всех обычных строках 5 X I У,= к.

При всех этих преобразованиях в векторе Л будут складываться переменные хі, но матрицы А (я, п) в первых двух клеточных строках не изменяются. В общем виде получим

Здесь2Х,22 - векторы, полученные сложением переменных хг во время предыдущих

операций. Аналогично С1 и С2 получены от сложения элементов правых частей, при этом ни один элемент не принадлежит обоим этим векторам. Если применить равенство (9), то получим разбиение элементов вектора Ь на 5 равных по сумме частей. Если бы линейный шаблон был гомоморфен единице, то какое-нибудь Ьг = 1, а все остальные равны нулю. Но тогда равенство (9) никогда бы не выполнялось. Это противоречие и подтверждает справедливость теоремы.

Относительно других шаблонов с нечетным числом клеток получены положительные результаты об их гомоморфности. Некоторые из них даже являются самодостаточными для базиса решения системы (1). Эти результаты будут освещены в последующих публикациях.

Полученные результаты вместе с результатами [4] позволяют полностью решать задачу о построении дискретных образов на плоскости для заданных цветных шаблонов. Если для системы сравнений (1) не очень легко найти обратную матрицу (для соответствующей подматрицы порядка ранга системы), то можно решать задачу поиска самодостаточного шаблона, в крайнем случае

п(т+я—1)

А (я, п) + К ■ Еп = С1;

А (я, п) 2 Г + К • Еп = Сг.

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

СПИСОК ЛИТЕРАТУРЫ