Решение задачи о построении линейной мозаики
For the first time, the problem of sample – aided imagery construction on a rectangular field is studied in this paper. Cases of different linear samples are analyzed in succession; necessary and sufficient conditions are found for a set of samples to be a basis for certain system of linear equation...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2005 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84920 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение задачи о построении линейной мозаики / Г.А. Донец, Самер И.М. Альшаламе // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 15-24. — Бібліогр.: 1 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860248524672729088 |
|---|---|
| author | Донец, Г.А. Самер И.М. Альшаламе |
| author_facet | Донец, Г.А. Самер И.М. Альшаламе |
| citation_txt | Решение задачи о построении линейной мозаики / Г.А. Донец, Самер И.М. Альшаламе // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 15-24. — Бібліогр.: 1 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | For the first time, the problem of sample – aided imagery construction on a rectangular field is studied in this paper. Cases of different linear samples are analyzed in succession; necessary and sufficient conditions are found for a set of samples to be a basis for certain system of linear equations. Both one – colored and multi – colored samples are treated.
|
| first_indexed | 2025-12-07T18:40:20Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2005, № 4 15
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается задача постро-
ения образов в прямоугольном по-
ле с помощью определённого набо-
ра шаблонов. Последовательно
исследуется решение для линей-
ных шаблонов, находятся необхо-
димые и достаточные условия
того, чтобы некоторый набор
шаблонов представлял базис ре-
шения соответствующей систе-
мы линейных уравнений. Рассмот-
рены двуцветные и многоцветные
шаблоны.
Г.А. Донец, Самер И.М. Аль-
шаламе, 2005
ÓÄÊ 519.1
Ã.À. ÄÎÍÅÖ, ÑÀÌÅÐ È.Ì. ÀËÜØÀËÀÌÅ
ÐÅØÅÍÈÅ ÇÀÄÀ×È Î ÏÎÑÒÐÎÅÍÈÈ
ËÈÍÅÉÍÎÉ ÌÎÇÀÈÊÈ
Введение. В теории распознавания образов
есть много задач, решенных и нерешенных,
которые имеют дело с прямоугольным по-
лем, разбитым на квадратные клетки, кото-
рые имеют различную раскраску, в совокуп-
ности представляя определенный образ. Обо-
значим такое поле π с числом клеток N = mn,
где m – число горизонтальных последова-
тельных клеток (строк), а n – число столбцов.
Каждому цвету имеющихся красок поставим
в соответствие число, принадлежащее мно-
жеству Q = {0, 1,…, K – 1}. Пусть имеется
набор связных фигур, состоящих из клеток
определенного цвета (≠0) и называемых
шаблонами S = {s1, s2,..., sp}. Предполагается,
что количество каждых фигур ограничено
числом r(t), где t = 1, 2,…, p. Часто возникает
задача, можно ли с помощью накладывания
имеющихся в наличии шаблонов построить
на чистом поле π (окрашенном в цвет 0) за-
данный образ (мозаику)? При этом в зависи-
мости от конкретной задачи под операцией
накладывания может подразумеваться раз-
личное содержание. Известно, что в реально-
сти синий цвет, смешанный с жёлтым, дает в
результате зеленый, коричневатый и фиоле-
товый дают в совокупности черный и т. д. В
общем виде операцию накладывания можно
задавать бинарной таблицей. В частном слу-
чае таблица может отражать сложение чисел
по модулю К. В данной работе будет подра-
зумеваться только такая операция наклады-
вания шаблонов.
Поскольку шаблон можно накладывать
любой стороной, а также поворачивать в
Г.А. ДОНЕЦ, САМЕР И.М. АЛЬШАЛАМЕ
16 Теорія оптимальних рішень. 2005, № 4
плоскости на любой угол, кратный 90°, то будем считать два типа положений
шаблона разными, если их нельзя совместить параллельным переносом. Оче-
видно, что таких типов не больше восьми. Для каждого типа положения выде-
лим в шаблонах одну определяющую клетку, называемую меткой шаблона. Зная
координату на поле этой метки и тип положения шаблона, можно однозначно
расположить его в поле. Если шаблон st (t = 1,2,...,p) α раз (α ≥ 0) наложен на по-
ле β-м типом положения с координатами метки l = n(i – 1) + j (i = 1, 2,…, m; j =
1,2,…, n), то будем полагать ( ) α=β,t
lx . Мозаика всегда задается вектором
{ }NbbbB ,,, 21 K= , где ( )NiQbi ,,2,1, K=∈ .
Задача о возможности построения необходимой мозаики на поле π при за-
данном множестве шаблонов S ={s1, s2,…, sP} сводится к решению системы ли-
нейных уравнений
( ) ( ) NlKbx
P
t
l
t
l ,,2,1;mod
1 1
,
K=≡∑∑
= =β
β
(1)
при ограничениях
( ) ( ) pttrx
N
l
t
l ,,2,1;
1 1
,
K=≤∑∑
= =β
β
. (2)
В зависимости от видов и количества шаблонов возникает задача с огром-
ным количеством переменных, число которых в большинстве случаев намного
превышает число равенств и неравенств. Решение задачи зависит от искусства
определения ранга этой системы.
Линейная система для двух цветов. Рассмотрим линейную систему (1) без
неравенств (2) и множество шаблонов S = {s1, s2,…, sP}, где si – набор si клеток,
расположенных последовательно в одну строку (i = 1, 2,…, p). Будем называть
два положения шаблона двойственными, если они отличаются друг от друга пе-
рестановкой своих концов. Очевидно, что такие шаблоны имеют на поле π че-
тыре типа положений – два двойственных горизонтальных и два двойственных
вертикальных, т. е. β = 1, 2, 3, 4. В качестве метки шаблона выберем крайнюю
клетку для вертикальных положений. В зависимости от длины шаблонов
( )ptst ≤≤1 очевидны соотношения:
( ) ( )
0
2,1, == t
l
t
l xx для ;1 tsnj −+>
( ) ( )
0
4,3, == t
l
t
l xx для .1 tsmi −+> (3)
Отсюда вытекает, что число переменных, соответствует одному шаблону St,
учитывая двойственные положения, равно
)()1(2)1(2)1(2)( nmssnsmsN tttt +−=−+−= .
Если учесть все шаблоны, то число переменных в системе (1) даже для ма-
лых размеров поля π будет намного больше числа mn. Это означает, что многие
переменные являются зависимыми и выражаются через другие. Необходимо
придумать способ, чтобы отсеять такие переменные. Для этого представим, что
РЕШЕНИЕ ЗАДАЧИ О ПОСТРОЕНИИ ЛИНЕЙНОЙ МОЗАИКИ
Теорія оптимальних рішень. 2005, № 4 17
необходимо построить образ В, у которого ( ) ( )niiKbi ≤≤≡ ,mod1 , а для всех
ij ≠ ( )Kb j mod0≡ . Будем называть такой образ единицей. Очевидно, что для
решения этой задачи достаточно рассмотреть только горизонтальные положения
шаблонов и накладывать их только в первой строке. Для построения плоского
образа необходимо размножить результаты одной строки на все остальные.
Шаблоны будем задавать как последовательность цветов ( )st qqqs ,,, 21 K= , где
{ }0\Qqi ∈ , и sqq ≤1 . Самый тривиальный шаблон состоит из одной клетки
цвета 1. Очевидно, что если таких шаблонов достаточно много, то с его помо-
щью можно построить любой образ (мозаику).
Таким образом, приходим к необходимости изучения поставленной задачи
для простейшего поля, которым является строка из n клеток. Пусть K = 2, тогда
все шаблоны окрашены цветом 1, и существует только один тип положения ли-
нейного шаблона. В этом случае st есть число, задающее длину этого шаблона.
Будем говорить, что подмножество шаблонов SS ∈0 образует базис, если с
его помощью можно построить любую единицу ( )nibi ,,2,11 K== .
В работе [1] показано, что два числа s1 и s2 с условием s1+ s2 = n + 2 образу-
ют базис, если наибольший общий делитель НОД ( ) 1, 21 =ss . Там же приводится
алгоритм построения любой единицы. Покажем, как при этих условиях полу-
чить решение для произвольной правой части системы (1).
Для удобства изложения рассмотрим небольшой пример со следующими
параметрами: { } ,11,8,5 == nS { }nbbbB ,,, 21 K= .
Обозначим переменные для первого шаблона ( )11,,2,1 snixi −+= K , для
второго шаблона – ( )21,,2,1
2
snjx js −+=+ K , где i и j координаты в строке ме-
ток соответствующих шаблонов. Тогда система (1) примет вид
x1 + · · · · · · · + x9 · · · = b1
x1 + x2 + · · · · · · + x9 + x10 · · = b2
x1 + x2 + x3 + · · · · · + x9 + x10 + x11 · = b3
x1 + x2 + x3 + x4 + · · · · + x9 + x10 + x11 + x12 = b4
x1 + x2 + x3 + x4 + x5 + · · · + x9 + x10 + x11 + x12 = b5
· x2 + x3 + x4 + x5 + x6 + · · + x9 + x10 + x11 + x12 = b6 mod 2.
· · x3 + x4 + x5 + x6 + x7 + · + x9 + x10 + x11 + x12 = b7
· · · x4 + x5 + x6 + x7 + · + x9 + x10 + x11 + x12 = b8
· · · · x5 + x6 + x7 + · · + x10 + x11 + x12 = b9
· · · · · x6 + x7 + · · · + x11 + x12 = b10
· · · · · · x7 + · · · · + x12 = b11 (5)
Отметим особенности общей системы для двух шаблонов, которая делится
по столбцам на две подобные части. Левая часть состоит из s2 – 1 столбцов, в
каждом из которых ровно s1 – 1 переменных. Все столбцы одинаковы, но сдви-
Г.А. ДОНЕЦ, САМЕР И.М. АЛЬШАЛАМЕ
18 Теорія оптимальних рішень. 2005, № 4
гаются вниз ровно на одну позицию по отношению к предыдущему. Аналогич-
но, правая часть состоит из s1 – 1 столбцов, в которых ровно s2 – 1 переменных.
В системе отсутствует переменная
2sx . В строке s1 переменных первого
шаблона на одну больше, чем в предыдущей строке, а переменных второго шаб-
лона – одинаковое число. Тоже самое можно сказать о строке n + 2 – s1. Пусть
( )2mod0120 ≡≡ bb . Начиная со второй строки, прибавим к ней предыдущую по
mod 2. В результате получим новую систему, в которой все строки, за исключе-
нием вышеуказанных, будут иметь по одной переменной от каждого шаблона, а
в строках s1 и n + 2 – s1 ровно по одной переменной от первого шаблона. И доба-
вим в систему последнее уравнение из (5).
x1 + · · · · · · + x9 · · · = b0 + b1
· x2 + · · · · · · + x10 · · = b1 + b2
· · x3 + · · · · · · + x11 · = b2 + b3
· · · x4 + · · · · · · + x12 = b3 + b4
· · · · x5 · · · · · · = b4 + b5
x1 + · · · · x6 + · · · · · = b5 + b6 mod 2.
· x2 + · · · · x7 + · · · · = b6 + b7
· · x3 · · · · · · · · = b7 + b8
· · · x4 + · · · + x9 · · · = b8 + b9
· · · · x5 + · · · + x10 · · = b9 + b10
· · · · · x6 + · · · + x11 · = b10 + b11
· · · · · · x7 + · · · + x12 = b11 + b12 (6)
Для выделенных переменных получаем прямое решение
( )( )2mod545 bbx +≡ и ( )( )2mod873 bbx +≡ . Подставляя эти значения в остальные
уравнения, можно найти полное решение системы (6).
Теорема 1. Решением системы (6) есть
)2(mod)(
1
1∑
λ
=
−γγ +≡
j
i bbx , (7)
где ( )[ ]211 mod ssjs +≡γ , а ( )[ ]21
1
1 mod sssi +⋅=λ − .
Доказательство. Будем рассуждать по индукции. Для начального значения
1s
x получаем ( )[ ] 1mod 21
1
11 =+⋅=λ −
ssss и )2(mod)( 1111 −+≡ sss bbx , или для (6)
( )( )2mod545 bbx +≡ . Переменная x5 встречается в строке ниже на пять позиций.
Подставляя в это уравнение значение x5, получаем решение для x10. Для него
( )[ ] 2mod2 21
1
11 =+⋅⋅=λ −
ssss . Получаем ( ) ( )2mod1095410 bbbbx +++≡ . Под-
нимаясь на восемь позиций вверх, и подставляя значение x10, получаем решение
для x2. Таким образом, получаем последовательное движение либо вниз на s1
позиций (при этом индексы увеличиваются на s1), либо вверх на s2 позиций (при
РЕШЕНИЕ ЗАДАЧИ О ПОСТРОЕНИИ ЛИНЕЙНОЙ МОЗАИКИ
Теорія оптимальних рішень. 2005, № 4 19
этом индексы уменьшаются на s2). Но ( )[ ]2112 mod ssss +≡− , т. е. в классе выче-
тов получается каждый раз увеличение индекса на s1.
В результате выражение 1ts , если t пробегает все значения от 1 до s1 + s2 – 2,
пробегает все индексы переменных, а при 221 −+= sst получаем
( ) ( )[ ]2121211 mod1 sssssssi +≡−≡−+= .
Но у нас переменная
2sx отсутствует. А предыдущая переменная имела ин-
декс ( ) ( )[ ]211211 mod22 ssssssi +−≡−+= . Для примера это ( )13mod352 ≡⋅− ,
для него справедливо
( ) ( ) ( ) ( )2mod2mod 87
11
8
1
13 bbbbx
j
j
jj +≡+≡∑
≠
−
− ,
что совпадает с непосредственным равенством (6). Это и завершает доказатель-
ство теоремы.
Пример 1. Построение для этих решений образа ( )1,1,1,0,1,0,0,0,1,1,0=B
показано на рис. 1.
Согласно теореме имеем:
.1;1
;1;1;1
;0;1;0
;1;0;0
321131110611
651610919849
4312412117127627
21102109510545
=++==++=
=++==++==++=
=++==++==++=
=++==++==+=
bbxxbbxx
bbxxbbxxbbxx
bbxxbbxxbbxx
bbxxbbxxbbx
Напомним, что xj для j > 8 отвечают второму шаблону с метками j – 8.
1 2 3 4 5 6 7 8 9 10 11
x1, x6
x2
x3
x9
x11
x12
Поле 0 1 1 0 0 0 1 0 1 1 1 = mod 2
РИС.1. Построение образа В
Так решается проблема для двух шаблонов при заданных двух цветах. Если
221 +>+ nss , то некоторые образы построить невозможно. Если 221 +<+ nss ,
то появляется множество решений, ибо путем сдвига шаблонов, которые являются
базисом для 221 +=+ nss , можно получить базис для больших значений n.
Г.А. ДОНЕЦ, САМЕР И.М. АЛЬШАЛАМЕ
20 Теорія оптимальних рішень. 2005, № 4
Вопрос о числе шаблонов больше двух решается аналогично. Пусть задано
p шаблонов. Очевидно, что для них также должно выполняться условие
НОД ( ) 1s,,s,s P21 =K . (8)
Кроме того, система (5) должна всегда иметь n переменных, чтобы решение
было единственным. Но каждый шаблон может иметь n + 1 – st переменных.
Поэтому необходимо
( ) pnps
p
i
i +−=∑
=1
1 . (9)
Эти условия являются необходимыми. Вопрос о конкретном методе реше-
ния задачи для более двух шаблонов остается открытым.
Линейная система для более двух цветов. Если цветов более двух (K > 2),
то шаблоны могут быть окрашены не единственным цветом, и при этом двойст-
венные положения шаблонов могут играть существенную роль в построении
образов.
Прежде всего, возникает вопрос, может ли один шаблон (вместе с двойст-
венным положением) образовывать базис только накладыванием самого себя.
Рассмотрим сначала шаблон из двух клеток { }211 ,qqs = , где { }0\, 21 Qqq ∈ .
Двойственный шаблон { }122 ,qqs = . Для построения образа ( ),mod11 Kb ≡
( ) ( )1mod0 >≡ iKbi необходимо решить систему уравнений
( ) ( )
( ) ( )
K
qxqx
qxqx
mod
0
1
1
2
12
1
1
2
2
11
1
1
=+
=+
.
(10)
Здесь ( )1
1x и
( )2
1x – количество первых (вторых) шаблонов, метка которых
находится в первой клетке строки. Система имеет решение, если детерминант
системы
( )Kqq mod0det 2
2
2
1 ≡−= . (11)
Таким образом, если ( )Kqq mod02
2
2
1 ≡− , то существуют такие шаблоны
длиною 2 с соответствующей раскраской, которые позволяют накладыванием на
самого себя получить любую клетку строки с окраской 1. Путем сдвига можно
получить решение для базиса системы (1). Легко убедиться, что для K = 2, 3 та-
ких шаблонов не существует. Для произвольных простых K множество шабло-
нов имеет вид (i, j), где i = 1, 2,…, K – 1, а iKj −≠ . Тогда решение системы (11)
примет вид
РЕШЕНИЕ ЗАДАЧИ О ПОСТРОЕНИИ ЛИНЕЙНОЙ МОЗАИКИ
Теорія оптимальних рішень. 2005, № 4 21
( ) ( )
( ) ( )
K
qqqx
qqqx
mod
12
2
2
12
2
1
12
2
2
11
1
1
−−=
−=
−
−
.
(12)
Выражение 1−
d равно решению сравнения ( )Ktd mod1≡ , если оно существует.
Для составных K этого недостаточно, так как возможны случаи, когда усло-
вия (11) не выполняются.
Пример 2. Пусть K = 5. Тогда число шаблонов, которые представляют базис
с помощью накладывания на себя, равно четыре: S1 = (1, 2), S2 = (1, 3), S3 = (2, 4),
и S4 = (3, 4).
Покажем это для
а) S = (2, 4), детерминант системы (10) равен ( )5mod21242 22 −≡−=− ;
( ) ( ) ( ) ( ) ( ) ( )5mod224;5mod4122
12
1
11
1 ≡−⋅−=≡−=−⋅=
−−
xx .
б) S = (3, 4), детерминант системы (10) равен ( )5mod3743 22 +≡−=− ;
( ) ( ) ( ) ( ) ( )5mod224;5mod133
12
1
11
1 ≡−⋅−=≡⋅=
−−
xx .
На рис. 2 показаны накладывания шаблонов, подтверждающие эти результаты.
2 4 3 4
2 4 +
2 4 4 3
2 4 4 3
+ ↓
4 2 11 10
4 2
↓ ↓
16 20 Поле 1 0 = mod 5
4 2
↓
Поле 1 0 = mod 5
a б
РИС. 2. Наложение двойственных шаблонов
Однако для шаблонов большей длины аналогичный результат невозможен.
Г.А. ДОНЕЦ, САМЕР И.М. АЛЬШАЛАМЕ
22 Теорія оптимальних рішень. 2005, № 4
Лемма 1. Шаблон ( )sqqqs ,,, 211 K= для s > 2 не может представлять базис
наложением на себя.
Для доказательства этого распишем систему (10) для искомого базиса
( ) ( )
( ) ( )
( ) ( )
( ) ( )
K
qxqx
qxqx
qxqx
qxqx
s
s
s
s
mod
0
0
0
1
1
2
1
1
1
2
2
11
1
1
1
2
12
1
1
2
11
1
1
≡+
≡+
≡+
≡+
−
−
LLLLLLLL .
(13)
Пусть ( )2mod1≡s . Рассмотрим уравнение с номером
2
1+
=λ
s
,
( ) ( ) ( )Kqxqx mod02
1
1
1 ≡+ λλ .
Так как ( )Kq mod0≡λ , то ( ) ( ) ( )Kxx mod02
1
1
1 ≡+ . Подставляя ( ) ( )( )Kxx mod1
1
2
1 −≡ в
первое и последнее уравнение (13), придем к равенствам
( )( )
( )( )
K
qqx
qqx
s
s
mod
0
1
1
1
1
1
1
1
≡−
≡−
,
что невозможно.
Аналогично доказывается случай ( )2mod0≡s .
Лемма 2. Пусть ( )2mod1≡≡ Ks и задан шаблон ( )sqqqs ,,, 211 K= . Обозна-
чим
2
1+
=λ
s
. Система (13) имеет решение для ( ) ( ) ( )λ≠≡≡λ iKbKb i mod0,mod1 ,
если
а) ( ) ( )1,,2,1mod01 −λ=≡+ −+ KiKqq isi ;
б) НОД( Kq ,λ ) = 1.
Лемма легко доказывается конструктивным путём.
Пусть s > 2. Рассмотрим произвольный шаблон ( )ss qqqqs ,,,, 1211 −= K и ему
двойственный ( )1212 ,,,, qqqqs ss K−= .
Число положений в строке длиною n для каждого шаблона равно n + 1 – s.
Так как число уравнений равно числу клеток строки, то для однозначности ре-
шения системы (1) число переменных должно равняться числу уравнений, то
есть ( ) nsn =−+12 . Отсюда
1
2
+=
n
s . (14)
Таким образом, для любого шаблона единственный базис может существо-
вать только при условии (14), при этом строка поля должна содержать четное
РЕШЕНИЕ ЗАДАЧИ О ПОСТРОЕНИИ ЛИНЕЙНОЙ МОЗАИКИ
Теорія оптимальних рішень. 2005, № 4 23
число клеток. Составим соответствующую систему уравнений для определения
базиса. При этом переменные для шаблона s1 обозначим ix , а двойственные пе-
ременные ( )1≥− iyi .
.mod
0
0
0
0
0
1
1
2
1
2
21
2
11
2
1
2
1
2
122
2211121
2111221
111
K
qyqx
qyqyqxqx
qyqx
qyqyqxqx
qyqyqxqx
qyqx
nsn
nnsnsn
s
ss
ss
s
≡+⋅⋅+⋅⋅⋅
≡++⋅++⋅⋅
⋅⋅⋅⋅⋅⋅⋅⋅
≡⋅++⋅⋅⋅⋅
≡⋅+++⋅⋅++
⋅⋅⋅⋅⋅⋅⋅⋅
≡⋅++⋅⋅++
≡⋅⋅+⋅⋅⋅+
−−−−
−
−
(15)
Теорема 2. Система уравнений (15) для s = 3 имеет решение при условиях:
а) ( ) ( )Kqq mod0
2
31 ≡− ,
б) ( ) ( )Kqqq mod02
2
2
31 ≡−+ .
Для доказательства запишем матрицу системы (15) для s = 3, размерность
которой равна 4
13
2123
3212
31
00
00
qq
qqqq
qqqq
qq
A = .
Легко подсчитать, что ( ) ( )[ ] ( )Kqqqqq moddet 2
2
2
31
2
31 −+−≡A .
Если ( )Kmod0det ≡A , то должны выполняться условия (а, б) теоремы 2.
Зная значения Adet , можно найти значения ix и ( )3,2,1=iyi системы (15)
( )
( ) ( )
( )
( ) ( )
( )
( )
( ) ( )
( )
( ) ( )
( ).mod
][
;mod
][
;mod
][
;mod
][
2
2
2
3131
32
22
2
2
3131
313
2
2
1
2
2
2
3131
21
22
2
2
3131
2
2311
1
K
qqqqq
qq
yK
qqqqq
qqqq
y
K
qqqqq
qq
xK
qqqqq
qqqq
x
−+−
=
−+−
+−
=
−+−
−=
−+−
−+
=
Условия теоремы 2 могут не выполняться для составного K. Если для K = 5
существует 16 допустимых раскрасок шаблонов, которые образуют базис, то для
K = 4 таких шаблонов только 2, это s1 = (1, 2, 2) и s2 = (2, 2, 3).
Г.А. ДОНЕЦ, САМЕР И.М. АЛЬШАЛАМЕ
24 Теорія оптимальних рішень. 2005, № 4
Заключение. При построении базиса для системы (1) почти незначительную
роль играет число раскрасок шаблонов и образов. Существенную роль играет
размер шаблонов. Для s = 3 решение представляется громоздкими формулами.
Поэтому в дальнейшей работе необходимо либо упростить формулы, либо найти
другую формулу представления решения системы (1).
Г.П. Донець, Самер І.М. Альшаламе
РІШЕННЯ ЗАДАЧІ ПРО ПОБУДОВУ ЛІНІЙНОЇ МОЗАЇКИ
Розглядається задача побудови образів на прямокутному полі за допомогою деякого набору
шаблонів. Послідовно досліджуються випадки для лінійних шаблонів, знаходяться необхідні
та достатні умови для того, щоб деякий набір шаблонів представляв базис розв’язку відповід-
ної системи лінійних рівнянь. Розглянуто двокольорові та багатокольорові шаблони.
G.A. Donets, Samer I.M. Alshalame
SOLUTION OF THE PROBLEM ON LINEAR MOSAIC CONSTRUCTION
For the first time, the problem of sample – aided imagery construction on a rectangular field is stu-
died in this paper. Cases of different linear samples are analyzed in succession; necessary and suffi-
cient conditions are found for a set of samples to be a basis for certain system of linear equations.
Both one – colored and multi – colored samples are treated.
1. Донец Г.А., Самер И.М Альшаламе. Задача о дискретном построении образов //
Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН
Украины, 2004. – С. 117–122.
Получено 23.03.2005
|
| id | nasplib_isofts_kiev_ua-123456789-84920 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T18:40:20Z |
| publishDate | 2005 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Самер И.М. Альшаламе 2015-07-17T05:41:07Z 2015-07-17T05:41:07Z 2005 Решение задачи о построении линейной мозаики / Г.А. Донец, Самер И.М. Альшаламе // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 15-24. — Бібліогр.: 1 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84920 519.1 For the first time, the problem of sample – aided imagery construction on a rectangular field is studied in this paper. Cases of different linear samples are analyzed in succession; necessary and sufficient conditions are found for a set of samples to be a basis for certain system of linear equations. Both one – colored and multi – colored samples are treated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Решение задачи о построении линейной мозаики Solution of the problem on linear mosaic construction Article published earlier |
| spellingShingle | Решение задачи о построении линейной мозаики Донец, Г.А. Самер И.М. Альшаламе |
| title | Решение задачи о построении линейной мозаики |
| title_alt | Solution of the problem on linear mosaic construction |
| title_full | Решение задачи о построении линейной мозаики |
| title_fullStr | Решение задачи о построении линейной мозаики |
| title_full_unstemmed | Решение задачи о построении линейной мозаики |
| title_short | Решение задачи о построении линейной мозаики |
| title_sort | решение задачи о построении линейной мозаики |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84920 |
| work_keys_str_mv | AT donecga rešeniezadačiopostroeniilineinoimozaiki AT samerimalʹšalame rešeniezadačiopostroeniilineinoimozaiki AT donecga solutionoftheproblemonlinearmosaicconstruction AT samerimalʹšalame solutionoftheproblemonlinearmosaicconstruction |