Задача о дискретном построении образов
In this paper the problem of sample-aided discrete color imagary construction within rectangular field of vision in studied. It is shown that this problem can be reduced to solution of the modulo k residual system of linear algebraic eqations. Here solution is offered for the case of k = 2 and linea...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2004 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2004
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84910 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Задача о дискретном построении образов / Г.А. Донец, Альшаламе Самер // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 117-122. — Бібліогр.: 1 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859947398712786944 |
|---|---|
| author | Донец, Г.А. Альшаламе Самер |
| author_facet | Донец, Г.А. Альшаламе Самер |
| citation_txt | Задача о дискретном построении образов / Г.А. Донец, Альшаламе Самер // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 117-122. — Бібліогр.: 1 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | In this paper the problem of sample-aided discrete color imagary construction within rectangular field of vision in studied. It is shown that this problem can be reduced to solution of the modulo k residual system of linear algebraic eqations. Here solution is offered for the case of k = 2 and linear samples.
|
| first_indexed | 2025-12-07T16:15:01Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2004, № 3 117
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются задачи пост-
роения дискретных цветных изо-
бражений на прямоугольном поле
зрения с помощью множества за-
данных шаблонов. Задачи сводят-
ся к решению системы линейных
алгебраических уравнений в конеч-
ных классах вычетов mod k. При-
водится решение задачи для k = 2
и линейных шаблонов.
Г.А. Донец, Альшаламе Самер,
2004
ÓÄÊ 519.1
Ã.À. ÄÎÍÅÖ,. ÀËÜØÀËÀÌÅ ÑÀÌÅÐ
ÇÀÄÀ×À Î ÄÈÑÊÐÅÒÍÎÌ
ÏÎÑÒÐÎÅÍÈÈ ÎÁÐÀÇÎÂ
Введение. Эта задача в том или ином виде
может встречаться в разных областях, где
используется прямоугольная метрика. Пусть
задано прямоугольное поле π, состоящее из
N = mn клеток, где m – число строк, а n –
число столбцов. Имеется множество шабло-
нов S = {s1, s2,..., sp}, где st (t = 1, 2,..., p) –
связная фигура из таких же клеток; r(t) –
количество таких фигур. Каждой клетке
шаблона соответствует число, которое при-
надлежит множеству Q = {0, 1, 2,..., k-1}.
Следует отметить, что каждая клетка шабло-
на окрашена цветом Qq ∈ . Задано множест-
во раскрасок B поля π, которое называется
множеством образов (мозаик). Если на поле
наложить какой-либо шаблон, то цвета соот-
ветствующих клеток приобретут цвет, рав-
ный сумме прежнего цвета и цвета клеток
шаблона по mod k. Можно накладывать не-
сколько шаблонов на одно место. Задача со-
стоит в том, чтобы на чистом поле (окра-
шенном в цвет 0) с помощью ограниченного
мно- жества шаблонов получить любой за-
данный образ.
В каждом шаблоне типа st может быть вы-
делена одна клетка, которая фиксирует по-
ложение шаблона на поле в горизонтальном
(или вертикальном) положении. Если шаб-
лон st зафиксирован λ раз на клетке
l = n(i – 1) + j, ( njmi KK ,2,1,,,2,1 == ), то
обозначим
( ) λ=t
x1 , в противном случае
( )
01 =t
x . Если шаблон накладывается на поле
в вертикальном состоянии, то ему будет со-
Г.А. ДОНЕЦ, АЛЬШАЛАМЕ САМЕР
118 Теорія оптимальних рішень. 2004, № 3
ответствовать переменная ( )t
y1 . Тогда задача сводится к решению таких mn
уравнений:
( )∑
=
≡+
p
t
l
t
l
t
l kbyx
1
)()(
)(mod , l = 1, 2,..., N. (1)
В общем виде эта задача довольно сложная, так как число переменных в ней
значительно превышает число уравнений. Поэтому возникают проблемы с опре-
делением ранга системы, что во многом зависит от типов шаблонов.
Здесь решается простая задача для набора двух типов прямолинейных шаб-
лонов как последовательности клеток, окрашенных цветом 1, длиной st (t = 1, 2)
и множества Q = {0, 1}. Будем считать выделенной клеткой в каждом шаблоне
самую крайнюю левую клетку (самую крайнюю верхнюю в вертикальном по-
ложении). Кроме уравнения (1) можно вывести несколько зависимостей между
шаблонами, если их накладывать на поле различными способами.
Нетрудно показать, что все вертикальные положения линейных шаблонов
являются линейно зависимыми от горизонтальных шаблонов. Если взять α гори-
зонтальных шаблонов длиной β, то это эквивалентно β вертикальным шаблонам
длиной α. Если имеются горизонтальные шаблоны любой длины от 2 до n – 1, то
можно всегда выразить с их помощью любую единицу в строке, начиная с пер-
вого и кончая последним столбцом. В качестве исходной будем всегда брать
первую строку. Тогда любая клетка в ней имеет номер l = 0 + j = j.
Если сложить по mod 2 шаблон длиной d + 1 и xj = 1 с шаблоном длиной d,
xj+1 = 1, то получим единицу в j-й клетке. Многократно повторяя это в следую-
щих строках, получаем вертикальный шаблон любой длины.
Следует отметить, что достаточно уметь получать единицу с помощью ли-
нейных горизонтальных шаблонов в любой клетке строки, чтобы построить лю-
бой образ на поле. Наименьший набор шаблонов, который позволяет предста-
вить единицу в любой клетке строки, называется базисом. Самым тривиальным
базисом является один шаблон S = {1}. Для двух шаблонов длиной s1 и s2, как
было указано, базис может составлять набор S = {d, d+1} (d > 0). Если один из
шаблонов по длине больше чем 1
2
+
n
, то появляются ограничения на пере-
движение этого шаблона вдоль строки, и базис может не существовать для не-
которых единиц. Поэтому для такого базиса необходимо, чтобы
1
2
,2 21 +
<<
n
ss . На рис. 1 это показано для S = {4, 3}, а внизу указан номер
соответствующей единицы.
Для s1 = 2 в качестве второго шаблона можно взять ( )1122 ≥+= kks . В
этом случае сделать единицу для любого l = j можно с помощью нескольких
шаблонов первого типа и одного шаблона второго типа. Для а) ( )012 ≥+= iil –
ЗАДАЧА О ДИСКРЕТНОМ ПОСТРОЕНИИ ОБРАЗОВ
Теорія оптимальних рішень. 2004, № 3 119
1
2
3
4
5
6
7
РИС. 1. Базис для шаблонов S = {4,3} и n = 7
это ( )ippxp <≤+= 012 и )(2 kpipxp ≤<= ; для б) il 2= – это
( )ippxp <≤+= 012 и )(2 kpipxp ≤≤= . Если nk <+12 , то используя
сдвиг, можно построить единицы и для остальных клеток. Для произвольных
двух типов шаблонов при 31 ≥s такие зависимости выводятся сложнее. Можно
сказать, что для любого n существет пороговое значение длин двух шаблонов,
когда существует ровно один базис, а для других значений базис либо не суще-
ствует, либо их несколько.
В качестве примера рассмотрим два шаблона s1 = 5, s2 = 13 и n = 16. Здесь
91
2
16
2 =+
>s . Составим систему уравнений типа (1).
x1 + …………………………………………………+ x14 = b1
x1 + x2 + ……………………………………………..+ x14 + x15 = b2
x1 + x2 + x3 +…………………………………………+ x14 + x15 + x16 = b3
x1 + x2 + x3 + x4 + …………………………………..+ x14 + x15 + x16 + x17 = b4
x1 + x2 + x3 + x4 + x5 + ……………………………..+ x14 + x15 + x16 + x17 = b5
..................................................................................................................
x5 + x6 + x7 + x8 + x9 +………….+ x14 + x15 + x16 + x17 = b9 (2)
x6 + x7 + x8 + x9 + x10 +……+ x14 + x15 + x16 + x17 = b10
.........................................................................................
x8 + x9 + x10 + x11 + x12 + ...... + x14 + x15 + x16 + x17 = b12
x9 + x10 + x11 + x12 + ..... + x14 + x15 + x16 + x17 = b13
x10 + x11 + x12 + ............. + x15 + x16 + x17 = b14
x11 + x12 + ...................... + x16 + x17 = b15
x12 + .............................. + x17 = b16
Г.А. ДОНЕЦ, АЛЬШАЛАМЕ САМЕР
120 Теорія оптимальних рішень. 2004, № 3
При заданных параметрах первый шаблон может принимать значение
1
)1( =ix для i = 1, 2,..., 12, а второй 1
)2( =ix для i = 1, 2, 3, 4. Чтобы не иметь дело с
верхними индексами, обозначим переменные для первого шаблона x1, x2,..., x12, а
переменные для второго шаблона – x14, x15, x16, x17. Здесь x13 пропущено из сооб-
ражений, которые раскроются позже.
Систему данных уравнений можно решать, исходя из общих позиций, ис-
пользуя известные методы решения [1]. Однако можно воспользоваться тем, что
имеем дело со специфической системой уравнений. Здесь правые части могут
быть произвольными, но нас интересует вопрос о существовании базиса для
этих шаблонов. Поэтому будем решать систему полагая, что в правых частях
находятся все нули, кроме одного значения njb j ≤≤≡ 1),2(mod1 . Очевидно, в
таком случае правые части уравнений линейно независимы. Имеем систему
уравнений с n уравнениями и n неизвестными. Важной особенностью этой сис-
темы есть условие s1 + s2 = n + 2. Так как число переменных для первого шабло-
на равно n + 1 – s1 = s2 – 1, то по аналогии число неизвестных для второго шаб-
лона равно s1 – 1. Поэтому в (s1 – 1)-й и s1-й строках система имеет одинаковые
количество переменных второго шаблона, а для первого шаблона – разное, от-
личающееся на одно. Складывая эти уравнения, получаем решение
( ) )2(mod
111 1 sss bbx +≡ − . В данной системе, складывая четвертое и пятое уравне-
ния, получаем ( ) )2(mod545 bbx +≡ . Если теперь подставить значение x5 в самое
нижнее уравнение (это будет 9-е), то, складывая его с десятым уравнением, по-
лучаем решение x10 = x5 + b10 + b9 (b4 + b5 + b9 + b10) (mod 2). Продолжая этот
процесс дальше, получаем решение для x15. Возвращаясь в самое верхнее урав-
нение (второе) и складывая его с первым, получаем решение для x2. В общем
случае, делая k шагов, находим значение
( ) )2(mod
1
1111 ∑
=
−+=
k
i
isisks bbx , (3)
где 1rs - положительный вычет по mod (s1 + s2), 1≥r . Выражение ks1 должно про-
бегать все значения индексов переменных от 1 до n + 1, если k пробегает после-
довательно все значения от 1 до 121 ⋅+ ss . Для последнего значения должны по-
лучить )(mod)1( 2121211 sssssss +≡−=−+ . Это возможно только в случае, если
НОД (s1, s1 + s2) = НОД (s1, s2) = 1. Если это не так, то найдется такое d > 1, что s1
= αd и s2 = βd. Тогда для k = β + α + 1 получим )1(11 +β+α= ss xx , что приведет к за-
висимости между значениями правых частей, а это недопустимо, то есть система
не имеет решения. Тем самым доказана
Теорема 1. Два разных числа s1 и s2 с условием s1+ s2 = n + 2 (n > 3) образу-
ют базис, если НОД(s1, s2) = 1.
ЗАДАЧА О ДИСКРЕТНОМ ПОСТРОЕНИИ ОБРАЗОВ
Теорія оптимальних рішень. 2004, № 3 121
Пусть в правой части ),0(1 jibb ij ≠== . Обозначим t1 (соответственно t2)
наименьшее (соответственно наибольшее) решение из двух уравнений в поло-
жительных вычетах [ ])mod( 211 ssjxs += или [ ])mod()1( 211 ssjxs ++= . Тогда по-
лучаем решение
≤≤
=
,случаяхостальныхв,0
;tttесли,1
x 21
k (4)
где [ ])mod( 211 sskts +=
В данном примере пусть b3 = 1. Тогда
)5(.0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0
.17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
.13,8,3,16,11,6,1,14,9,4,17,12,7,2,15,10,51
=
=
=
x
t
ts
Здесь t1 = 8, t2 = 15. Соответственно для 8 < t < 15 получаем x4 = x9 = x14 = x1 =
= x11 = x16 = 1. Остальные xi = 0. Это решение показано на рис.2. При этом пред-
полагалось, что для всех переменных, начиная с x14, место положения левой
клетки на 13 значений переменных меньше индекса.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
x1
x4
x6, x11
x9
x14
x16
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
РИС. 2. Решение системы для b3 = 1
Если s1 + s2 > n + 2, то число уравнений будет больше числа переменных и
система не всегда имеет решения. Если s1 + s2 < n + 2, то число переменных бу-
дет больше числа уравнений и система может иметь много решений. В этом
случае n можно уменьшить до необходимого, чтобы применить условие теоре-
мы 1, а решения для новых правых клеток поля можно получить путем сдвига
решений, полученных для левой части поля.
Г.А. ДОНЕЦ, АЛЬШАЛАМЕ САМЕР
122 Теорія оптимальних рішень. 2004, № 3
Если в правой части системы (2) стоят произвольные значения bj, то реше-
ние можно получать, складывая решения для каждого bj = 1. После этого уда-
лить из решения лишние значения, чтобы 10∨=ix . То же самое можно сделать,
используя полученные общие результаты (5) для всех значений bj = 1.
Г.А. Донець, Альшаламе Самер
ЗАДАЧА О ДИСКРЕТНІЙ ПОБУДОВІ ОБРАЗІВ
Розглядаються задачі побудови дискретних кольорових зображень на прямокутному полі зо-
ру за допомогою множини заданих шаблонів. Задачі зводяться до розв’язування системи лі-
нійних алгебраїчних рівнянь в скінченних класах лишків за mod k. Наводиться розв’язок для k
= 2 та лінійних шаблонов.
G.A. Donets, Sammer Al’shallamme
PROBLEM OF DISCRETE IMAGARY CONSTRUCTION
In this paper the problem of sample-aided discrete color imagary construction within rectangular
field of vision in studied. It is shown that this problem can be reduced to solution of the modulo k
residual system of linear algebraic eqations. Here solution is offered for the case of k = 2 and linear
samples.
1. Кривый С. Л. О некоторых методах решения и критериях совместности систем
линейных диофантовых уравнений в области натуральных чисел // Кибернетика и
системный анализ. – 1999. – № 4. – С. 12–36.
Получено 03.06.2004
|
| id | nasplib_isofts_kiev_ua-123456789-84910 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T16:15:01Z |
| publishDate | 2004 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Альшаламе Самер 2015-07-16T19:07:15Z 2015-07-16T19:07:15Z 2004 Задача о дискретном построении образов / Г.А. Донец, Альшаламе Самер // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 117-122. — Бібліогр.: 1 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84910 519.1 In this paper the problem of sample-aided discrete color imagary construction within rectangular field of vision in studied. It is shown that this problem can be reduced to solution of the modulo k residual system of linear algebraic eqations. Here solution is offered for the case of k = 2 and linear samples. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Задача о дискретном построении образов Problem of discrete imagary construction Article published earlier |
| spellingShingle | Задача о дискретном построении образов Донец, Г.А. Альшаламе Самер |
| title | Задача о дискретном построении образов |
| title_alt | Problem of discrete imagary construction |
| title_full | Задача о дискретном построении образов |
| title_fullStr | Задача о дискретном построении образов |
| title_full_unstemmed | Задача о дискретном построении образов |
| title_short | Задача о дискретном построении образов |
| title_sort | задача о дискретном построении образов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84910 |
| work_keys_str_mv | AT donecga zadačaodiskretnompostroeniiobrazov AT alʹšalamesamer zadačaodiskretnompostroeniiobrazov AT donecga problemofdiscreteimagaryconstruction AT alʹšalamesamer problemofdiscreteimagaryconstruction |