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

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...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
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