Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности

В статье рассматривается задача построения математического описания лексикографических кодов для расширенной реальности. Найдена формальная система проектирования кодов для надёжного и устойчивого распознавания зрительных образов. Для построения книги кодов использован классический...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Искусственный интеллект
Дата:	2014
Автор:	Гудаев, О.А.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2014
Теми:	Анализ и синтез коммуникационной информации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/85252
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности / О.А. Гудаев // Искусственный интеллект. — 2014. — № 2. — С. 51–74. — Бібліогр.: 15 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860259607288479744
author	Гудаев, О.А.
author_facet	Гудаев, О.А.
citation_txt	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности / О.А. Гудаев // Искусственный интеллект. — 2014. — № 2. — С. 51–74. — Бібліогр.: 15 назв. — рос.
collection	DSpace DC
container_title	Искусственный интеллект
description	В статье рассматривается задача построения математического описания лексикографических кодов для расширенной реальности. Найдена формальная система проектирования кодов для надёжного и устойчивого распознавания зрительных образов. Для построения книги кодов использован классический метод комбинаторики слов. У статті розглядається задача побудови математичного опису лексикографічних кодів для розширеної реальності. Знайдена формальна система проектування кодів для надійного та сталого розпізнавання зорових образів. Для побудови книги кодів використано класичний метод комбінаторики слів. In the article consider the task of constructing a mathematical description of lexicographical codes for augmented reality. Found a formal system to design codes for robust and stability to recognition of pattern images. To construct the code book used the classical method of combinatorics on words.
first_indexed	2025-12-07T18:53:36Z
format	Article
fulltext	ISSN 1561-5359 «Штучний інтелект» 2014 № 2 51 3Г УДК 004.942+004.93'1 О.А. Гудаев Донецкий национальный технический университет, Украина Украина, 83050, г. Донецк, пр. Богдана Хмельницкого, 84 Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности O.A. Gudayev Donetsk National Technical University, Ukraine Ukraine, 83050, c. Donetsk, Bogdana Khmelnitskogo av. Combinatorics on Equaffine Words for Design Lexicographic Codes of Augmented Reality О.О. Гудаєв Донецький національний технічний університет, Україна Україна, 83050, м. Донецьк, пр. Богдана Хмельницького, 84 Комбінаторика еквіаффінних слів для проектування лексикографічних кодів розширеної реальності В статье рассматривается задача построения математического описания лексикографических кодов для расширенной реальности. Найдена формальная система проектирования кодов для надёжного и устойчивого распознавания зрительных образов. Для построения книги кодов использован классический метод комбинаторики слов. Ключевые слова: расширенная реальность, лексикографический код, компьютерное зрение, зрительный образ, планарный маркер, комбинаторика слов, аффинное преобразование, сложность, монолитность, количество популяции. In the article consider the task of constructing a mathematical description of lexicographical codes for augmented reality. Found a formal system to design codes for robust and stability to recognition of pattern images. To construct the code book used the classical method of combinatorics on words. Key words: augmented reality, lexicographical code, computer vision, pattern image, planar marker, combinatorics on words, affine transformation, complexity, monolithic, population count. У статті розглядається задача побудови математичного опису лексикографічних кодів для розширеної реальності. Знайдена формальна система проектування кодів для надійного та сталого розпізнавання зорових образів. Для побудови книги кодів використано класичний метод комбінаторики слів. Ключові слова: розширена реальність, лексикографічний код, комп'ютерний зір, зоровий образ, планарний маркер, комбінаторика слів, афінне перетворення, складність, монолітність, кількість популяції. Введение Нашу жизнь трудно представить без одномерных штрих-кодов «1D». Они эффек- тивно используются в автоматизированных системах управления. Двухмерный штрих-код «2D» является планарным маркером. Он получил популярность с развитием искусственного интеллекта по направлению «Расширенная реальность» (Augmented Reality – AR) [1-3]. Гудаев О.А. «Искусственный интеллект» 2014 № 2 52 3Г В Имея строгое математическое описание графических 2D-маркеров можно спроекти- ровать большое многообразие новых AR-кодов с учетом особенности среды их функциони- рования: под водой и в воздухе, в космосе и в наномире. Существующие в мире 2D- маркеры созданы методом «сталкинга»: на основе коммерческой поддержки проектиро- вания информационных процессов. Технологи нативно переносят телекоммуникационные модели кодирования радиоканала в оптическую среду. Поэтому по своей наивности код ARTag уступает продуманным лексикографическим кодам ARGET и AprilTag [4], [5]. Использование в коде AprilTag процедуры вероятностного перебора, вместо комбинато- рики слов, исключает его из числа кодов обоснованных фундаментально. Из ожидаемого многообразия новых кодов остаётся один кандидат в «идеальный» 2D-маркер – это код ARGET [4], [6-8]. Представим краткое описание одномерного штрих-кода и двухмерного AR-кода группой моделей HS: {информационная, геометрическая, оптическая, компьютерная, логическая, кибернетическая}. Метамодель HS поможет мне сделать постановку за- дачи по теоретическому обоснованию проектирования лексикографических 2D-кодов. Метамодель HS-1 (ММ). Штрих-код «1D» – это одномерная дискретная струк- тура. Варьирования толщины линии штриха и толщины пробела задаёт информационное содержание кода. Информационная модель: последовательность чередования линий и пробелов – это последовательность битов. Геометрическая модель – отрезки линий различной толщины, фактически прямоугольные столбики. Оптическая модель – разли- чимые штрихи, не сливающиеся при изменении фокуса фотокамеры. Компьютерная модель – растровое изображение объектов контрастного цвета. Математическая модель – конечный вектор бинарных чисел. Логическая модель – упорядоченная слева на право последовательность однотипных элементов. Кибернетическая модель – высота столбика должна быть достаточной для надежного и точного считывания кода системой технического зрения. Кибернетическая модель не связана с содержанием кода и не определяет однородную структуру штрих-кода, то есть является метасвойством, которое используется автоматизированными системами для позиционирования. ММ HS-2. Сделаем строгое описание двухмерного маркера «2D» простым и по- нятным. Информационная модель – лексикографический код комбинаторики слов. Геометрическая модель – эквиаффинная форма конечной однородной структуры. Оптиче- ская модель – различимые плоские фигуры после проецирования и аффинных транс- формаций. Компьютерная модель – контрастное растровое изображение. Математическая модель – конечная двухмерная квадратная матрица бинарных чисел. Логическая модель – размещение в матрице упорядоченных построчно блоков последовательности битов, бинарного представления десятичного числа. Младший бит числа является первым элементом матрицы. Кибернетическая модель – зрительный образ обладает системными признаками для надежного и точного распознавания: популяцией за- крашенных ячеек [4], монолитностью [6], шаблоном фиксированных точек контура [7], геометрической сложностью [9]. Предметная область. В компьютерных системах расширенной реальности для разметки физической среды трехмерного пространства используют 2D-маркеры [3]. Привязка точек среды к компьютерной 3D-модели осуществляется с помощью пла- нарной системы маркеров ARGET [4]. Существуют маркерные и безмаркерные тех- нологии привязки. В работе рассматривается маркерный способ разметки среды. Планарный маркер – это «IP-адрес» трехмерной формы объекта. Рассмотрим природу цифровых зрительных образов расширенной реальности. Только некоторых зрительных образов. Исследование природы зрительного образа Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 53 3Г 2D-маркера проводится для выявления его семантических свойств. Некоторый образ можно охарактеризовать одной фразой из повседневной жизни человека: «Тень на стене отражает силуэт». Мерой глубины познания зрительных образов выберем сложность. Рассмотрим, как характеризуется природа сложности зрительных образов в естест- венной сфере. Первобытный инстинкт и любознательность порождают у человека интерпретацию увиденного силуэта. Сложный внутренний мир человека формирует образ на основе ассоциаций с материальным предметом, явлением или событием. Достоверно опознав природу игры теней, человек имеет правдоподобное суждение об объекте, который отбросил на стену силуэт. Объективно человек может заблуждаться, но градус эмоций может иметь всю палитру градации чувств. В противоположном случае в силуэте видится нечто неизвестное и неопределенное. Тогда образ целиком отражает виртуальную фантазию, синтезированную субъективно. Фактически, мнимый образ – это всегда надуманные переживания. Поэтому личностью эмоции всегда легко контролируются, так и не придавая смыслового значения силуэту. Основой формирования мнимого образа является художественное восприятие. В основе вос- приятия лежит классификация видов геометрической сложности фигур и их прочтения. Возможны такие градации сложности мнимого образа: банальная простота, какофония хаоса, нерегулярные или несимметричные формы, фракталы. Точно, это полный список оптических иллюзий, в отличие от гармонии опознанных объектов: композиции и золотого сечения. Рассмотрим теперь природу планарного маркера, как цифрового зрительного образа. Цифровой образ маркера не имеет эмоциональной составляющей «гармонии сфер». Как естественный прототип для изучения модели сложности маркеров подойдут виды мнимых образов. Мнимый образ цифрового маркера легко описать на формальном языке. Представим стену с нарисованным силуэтом в виде геометрической плоскости. Будем рассматривать участок стены, как замкнутую область двухмерного пространства. Параметрической моделью дискретной области будет прямоугольная матрица. Цвето- передача тени на стене – это контрастное черно-белое растровое изображение. Обозначив фон стены нулём, а цвет силуэта единицей, получим, что элементы матрицы прини- мают значения из диапазона {0, 1}. Сложность планарного маркера в технических системах расширенной реальности требует дальнейшего детального изучения. Постановка задачи. Надо выявить характеристики цифрового зрительного образа 2D-маркера, которые позволят спроектировать надежную систему передачи закоди- рованных сообщений по специфическому каналу связи. Особенностью канала является природа воздействия шумов внешней среды, а именно: размытие, затенение, засве- чивание, аффинное искажение, проективное искажение, частичное загораживание и слитие с фоном. Канал принадлежит к оптической среде. Технической особенностью канала является недоступность запроса на повторную передачу сообщений. Канал принадлежит к типу FEC. Планарный маркер может быть достаточно сложным для восприятия человеком, что, в сущности, и невозможно учесть, так как предназначен он для технических систем компьютерного зрения. Но, избавив цифровой образ маркера ARGET от навязчивой регулярности в виде рамки, занимающей 43,75% его площади, как в коде AprilTag, можно надеяться на эргономическое восприятие человеком создаваемого, по математическим канонам, кода. Зная характеристики природы планарных маркеров, можно комбинаторным перебором синтезировать сложные зрительные образы пригодные для построения надежной системы кодирования. Сложный зрительный образ  это код, объединение Гудаев О.А. «Искусственный интеллект» 2014 № 2 54 3Г В которого в систему кодирования возможно только лексикографическим способом. При построении лексикографического кода для расширенной реальности учитывается четыре аффинных вращения образа на прямой угол, что делает параметрическое простран- ство модели кода четырехмерным. Формальное описание модели кода  это эквиаффинные слова. Знание свойств эквиаффинных слов позволяет конструировать эффективные аппарат- ные алгоритмы распознавания [4], [6]. Например, в виде систолических автоматов [10]. Цель работы заключается в следующем: изучить некоторые общие характе- ристики эквиаффинных слов, как математических объектов однородной, планарной, квадратной среды; изучить комбинаторный подход в создании однозначных порождающих процедур множества эквиаффинных слов; изучить применение комбинаторики экви- аффинных слов в построении кода разметки трехмерного пространства. Миссия работы заключается в доказательстве утверждения: «В формальных системах принятия решений в однородной, двухмерной, квадратной среде для синтеза точной модели комбинаторным перебором 3/4 аксиоматических конфигураций быстро проверяется простым правилом и только 1/4 часть кандидатов должна быть подвергнута изучению характеристик». Сделанное краткое описание двухмерных маркеров требует детального рассмотрения. Геометрический образ. При аффинных преобразованиях площади всех фигур изменяются в одно и то же число раз. Средневековый арабский математик Сабит ибн Корра рассматривал аффинные преобразования, сохраняющие площадь, которые в дальнейшем стали называть эквиаффинными преобразованиями [11]. В римановой геометрии отображения, сохраняющие структуру, называются изометрией, а в аф- финной дифференциальной геометрии многообразий – это эквиаффинные отображения. Центроаффинное преобразование – это аффинное преобразование, сохраняющее начало координат. В работе рассматриваются четыре отображения маркера, полученные аффинным поворотом фигуры на прямой угол. Поэтому рассматриваемый в работе 2D-маркер – это экви, центро, прямо, аффинная плоская геометрическая фигура. Формальное отражение фигуры, с перечисленными математическими свойствами, будем в дальнейшем кратко называть «эквиаффинным словом». Порождение эквиаффинных слов. Утверждение 1. Любую закрашенную гео- метрическую фигуру на плоскости всегда можно вписать в квадратную область. На рис. 1а приведен зрительный образ, минимально описываемый прямоугольной областью, но который можно вписать в квадратную область (рис. 1б). Утверждение 2. Любую квадратную область на плоскости можно дискретизи- ровать равномерно по пространственным координатам абсциссы и ординаты на N рядов и N столбцов, равными частями. Получим объект однородной, планарной, квадратной среды. На рис. 1в показано наложение решётки на образ, а на рис. 1г по- казано введение нумерации пространственных ячеек. а) образ б) квадратная область в) однородная среда г) квадрат рядов, N=6 Рисунок 1 – Дискретизация зрительного образа Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 55 3Г Утверждение 3. Любую точку дискретной квадратной области с заданной ин- тенсивностью яркости цвета можно квантовать по амплитуде только эвристическим способом. Следствие из утверждения 3. Квантование цифрового изображения эври- стическим способом всегда приводит к неточности описания квадратной области с объективной погрешностью, что делает процедуру построения конечного множества точек области неоднозначной. В проектировании AR-кодов цвет заливки ячейки всегда определён однозначно. Утверждение 4. Осуществим квантование цвета точки на два уровня, эвристиче- ским правилом порогового разделения. Пусть уровень амплитуды меньший заданного глобального порога будет фоном. Обозначим уровень амплитуды типом a. Уровень амплитуды больший или равный пороговому значению будет признаком существо- вания графического объекта. Обозначим его типом b. Представление интенсивности яркости одноцветного изображения двумя уровнями значения амплитуды достаточно для опознавания морфологических признаков геометрической фигуры. Если глобальной порог 2550 :  PRPR задан для функции яркости цвета f , то бинаризация образа в виде матрицы  bayxG ,),(  будет задана формулой 1.       .),( , ;),( , ),( PRyxfb PRyxfa yxG (1) Утверждение 5. Цифровое монохромное изображение квадратной области на плоскости можно представить в формальном виде двухмерной квадратной матрицей G порядка N, с элементами, принимающими два типа значений  ba, . На рис. 2а по- казан зрительный образ формально представленный матрицей G (рис. 2б). Результат бинаризации матрицы G по формуле (1) показан на рис. 2в.              44424241 34333231 24232221 14131211 44 gggg gggg gggg gggg G x              aaab aaab bbab abba G x44 а) маркер AR-кода б) матрица G , порядка N=4 в) бинарная матрица Рисунок 2 – Матричная модель зрительного образа Утверждение 6. Последовательное размещение всех элементов матрицы G, в векторном виде, позиционно друг за другом, является символьным образом дискретной фигуры W и имеет длину 2N . Обозначим длину вектора символом K. Индекс по- зиции литер слова W связан с индексами элементов матрицы G линейной формулой 2. )1()1(  jNiNNk , (2) где Nji ,1,  . Например, матрицу 44xG представим вектором 16W :  1615141312111098765432116 wwwwwwwwwwwwwwwwW  Гудаев О.А. «Искусственный интеллект» 2014 № 2 56 3Г В В среде проектировщиков планарных систем маркеров ARTag, AprilTag сложилась традиция соответствия элементов вектора элементам матрицы: «последний элемент вектора 16W является первым элементом матрицы 44xG ».              1234 5678 9101112 13141516 44 wwww wwww wwww wwww G x (3) Для матрицы 44xG получим слова 16W «aaabaaabbbababba». Заменим в слове лите- ру a на символ «0», а литеру b на символ «1», получим представление слова бинарным число «0001000111010110». В десятичной системе исчисления слово 16W будет пред- ставлено натуральным числом P=4566. Утверждение 7. Произвольная конечная последовательность символов, имеющая длину K не кратную 2N , не может быть представлена на плоскости, как прообраз квадратной области. Числовой ряд  2,36,25,16,9,4 NK  . Утверждение 8. Произвольный образ W, имеющий длину K кратную любому натуральному числу в квадрате, обладает геометрическим гомоморфизмом, порождаемым прямоугольными аффинными вращениями относительно центра квадратной области. Такой образ назовём эквиаффинным словом. Утверждение 9. Эквиаффинное слово W имеет только четыре изоморфных под- образа TG , RG , BG , LG . Первый подобраз TG – это сама матрица G, а три оставшихся подобраза построены аффинным вращением матрицы G на угол кратный прямому углу (рис. 3). TG RG LG BG 90 rotateaf 90 rotateaf 90 rotateaf 90 rotateaf TG RG LG BG 90 rotateaf 90 rotateaf 90 rotateaf 90 rotateaf Рисунок 3 – Схема гомоморфизма подобразов эквиаффинного слова Особенностью формулы прямоугольного аффинного вращения является то, что индексы размещения элементов в матрице любых двух из четырёх подобразов связаны линейным алгебраическим выражением [4]. Например, индексы подобразов матрицы порядка 3 получены линейными перестановками:  123456789 987 654 321 wwwwwwwwwW www www www G TT             , Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 57 3Г  741852963 369 258 147 wwwwwwwwwW www www www G RR             ,  987654321 123 456 789 wwwwwwwwwW www www www G BB             ,  369258147 741 852 963 wwwwwwwwwW www www www G LL             . (4) Утверждение 10. Литеры эквиаффинного слова W, принимающие значение типа a, обозначим нулём, а литеры типа b заменим единицей. Тогда, подобраз эквиаффинного слова будет бинарным числом, которое можно представить в десятичной системе ис- числения натуральным числом P. Таким образом, гомоморфизм эквиаффинного слова W описывается четырьмя десятичными числами TP , RP , BP , LP . Утверждение 11. Диапазон десятичных чисел ]20[ KP  , описывающих подобразы эквиаффинных слов порядка N, ограничен, включительно, значением K2 . На рис. 4 показаны силуэты подобразов слова «3 288 264 899», порядка N=6. Рисунок 4 – Зрительные подобразы эквиаффинного слова Например, слово, порядка N=3, представленное числом P=4566 имеет подобразы: 0 градусов TP =4566; 90 градусов RP =19591; 180 градусов BP =27528; 270 градусов LP =57650. Утверждение 12. Конечное множество A эквиаффинных слов, порядка N, можно представить перечислением всех десятичных чисел TP первого подобраза GT. Утверждение 13. Пусть порождающая процедура множества A комбинаторно перебирает все десятичные числа P от нуля до K2 , с шагом увеличения на единицу. На каждом шаге итерации, десятичное число P представляется бинарным числом, к которому дописываются незначащие нули, увеличивающие размер бинарной после- довательности до 2N элементов. Бинарную последовательность заносят в матрицу G Гудаев О.А. «Искусственный интеллект» 2014 № 2 58 3Г В и для неё получают описания трех её подобразов PR, PB, PL. Однозначным условием быть числу P подобразом PT эквиаффинного слова, включаемого в множество A, является отсутствие среди чисел PR, PB, PL числа меньшего, чем P. Это условие является простой проверкой отсеивания повторения кандидатов. На рис. 5 показано размещение подобразов слова «3 288 264 899» на числовой оси. 0 3 млрд 12 млрд 52 млрд 68 млрд Рисунок 5 – Размещение подобразов на числовой оси Независимо от предлагаемой в утверждении 13 процедуры, успех работы в проектировании кода AprilTag повторил роботостроитель из университета Мичигана Эдвин Олсон (Edwin Olson) в 2010 году. Восемнадцать дней алгоритм Э. Олсона создаёт код. Алгоритм случайно, наугад, отбирает числа из конечного диапазона и лексикографическим способом формирует AR-код. На рис. 6 приведена схема разме- щения на числовой оси генерируемых кандидатов в код AprilTag. Процедура генерации кода берёт простое число P из справочника и заносится в книгу кодов. Создается случайное число приращения dP1. Кандидат P1 получается суммой чисел P и dP1. Процедура проверяет интегральные характеристики числа P1 и возможность его добавления в книгу кодов. Следующий кандидат P2 получается суммой чисел P1 и нового случайного числа приращения dP2. Затраты алгоритма на вычислительные ресурсы, на проверку характеристик и возможности добавления в книгу лексикогра- фических кодов, являются «космическими». Проблема «избыточности вычислений» возникает из-за того, что любые два числа-кандидата могут оказаться одним и тем же эквиаффинным словом, а для каждого из них проводится сложная интегральная проверка. Процедура полного комбинаторного перебора, предложенная в утверждении 13, выгодно отличается от случайной процедуры генерации AR-кодов AprilTag. dP1 dP2 dP3 0 P P2 P3 P4 ... 2K Рисунок 6 – Схема размещения случайных чисел кандидатов в AR-код Свойства эквиаффинных слов. В работе рассматривается следующая группа свойств эквиаффинных слов: популяция единиц (E), информационная сложность (D), монолитность (U), геометрическая сложность (S), показатель плавных структурных изменений группы слов (EQ), конфигурация опорных точек (F). Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 59 3Г Утверждение 14. Любое слово W характеризуется количеством элементов одного типа a или b. Если для слова суммируется количества литер типа b, то свойство называется популяцией единиц E(W):  1,0 ,)( 1321 1     iKK K i i wwwwwwwWE  (5) Например, для бинарного слова, длиной в девять литер, популяция единиц будет 3)"100000110(" 987654321  wwwwwwwwwE . В процессор Intel i5 введена инструкция POPCNT подсчета популяции единичных битов в 64-битном машинном слове, для задач обработки мультимедиа пакета SSE4.2. Утверждение 15. Информационная сложность двух бинарных слов W и 'W определяется по метрике Хемминга H. Метрика рассчитывается в два этапа. Сначала порождается новое слово XW применением побитовой операции суммы по модулю два над литерами слов W и 'W . Затем для нового слова XW вычисляется популяция единиц )( XWE , которая является метрикой Хемминга )'()',( WWEWWH  . Утверждение 16. Пусть для всех неповторяющихся пар подобразов TG , RG , BG , LG эквиаффинного слова вычислена метрика Хемминга: 1( , ),T RH W W ),(2 BT WWH , ),(3 LT WWH , ),(4 BR WWH , ),(5 LR WWH , 6 ( , ).B LH W W Все отношения iH показаны на рис. 7. TW TW RW RW LW LW BW BW 1H 2H 3H 4H 5H 6H iH – расстояние Хемминга Рисунок 7 – Отношения метрики Хемминга между подобразами Например, вычисление метрик iH для слова длиной в девять литер будет задано линейной алгебрологической формулой: 714213845526976839 1 )( wwwwwwwwwwwwwwwwwwWWEH RT  918273645546372819 2 )( wwwwwwwwwwwwwwwwwwWWEH BT  316293245586174879 3 )( wwwwwwwwwwwwwwwwwwWWEH LT  978471685542392613 4 )( wwwwwwwwwwwwwwwwwwWWEH BR  376491285582194673 5 )( wwwwwwwwwwwwwwwwwwWWEH LR  396897265584134271 6 )( wwwwwwwwwwwwwwwwwwWWEH LB  Утверждение 17. Минимальное значение iH , отличное от нуля, является ин- формационной сложностью D эквиаффинного слова: ),,,,,min( 654321 HHHHHHD  (6) Гудаев О.А. «Искусственный интеллект» 2014 № 2 60 3Г В В технических системах передачи данных приемлемым считается информа- ционная сложность, появляющаяся за счёт избыточности кода, больше одной четвёртой длины слова 4/KD  . Если одна из метрик iH будет равна нулю, то эквиаффинное слово обладает регулярностью повторения комбинаций литер и симметричностью вращения подобразов. На рис. 8 показаны образы, обладающие регулярностью и симметричностью, для квадратных матриц разного порядка. а) матрица 33 б) матрица 44 в) матрица 55 г) матрица 66 в) матрица 77 Рисунок 8 – Образы разного порядка, с информационной сложностью 0D Характеристика регулярности и симметричности, когда 0D , справедливо для равенства двух любых чисел TP , RP , BP , LP . Утверждение 18. Эквиаффинное слово обладает свойством монолитности U, если все элементы двухмерной матрицы G, принимающие значение b, в восьми- связной окрестности Мура, имеют одного соседа или более одного соседних элементов, принимающих значение b. Представим матрицу G графом, где вершина – это элемент, принимающие значение b, а дуги – это соседство вершин в окрестности Мура. Тогда граф монолитного образа имеет только связанные вершины, когда в нём отсутствуют изолированные вершины. Например, рассмотрим правила формирования соседства в квадратной матрице G порядка 6. Конфигурация соседства GU в окрестности Мура имеет восемь компо- нент для 22 )(N  ячеек:   61111111111111   i,j, g,g,g,g,g,g,g,g)(gU ,ji,ji,jii,ji,j,ji,ji,jiij G Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 61 3Г Конфигурация соседства Мура для ячеек матрице G расположенных по периметру, кроме угловых, имеет пять компонент в условиях для )(N 24  ячеек:   ;611221211111   j, ,g,g,g,gg)(gU jjjjjj G   ;611551516166   j, ,g,g,g,gg)(gU jjjjjj G   ;612122111111   i, ,g,g,g,gg)(gU ,ii,,i,i,ii G   .615155161616   i, ,g,g,g,gg)(gU ,ii,,i,i,ii G Конфигурация соседства Мура для угловых ячеек матрице G имеет три компо- ненты в четырех условиях для 43 ячеек:  ;,,)( 22122111 ggggU G   ;,,)( 62526161 ggggU G   ;,g,gg)(gU G 26251516   .,g,gg)(gU G 65565566  Общее количество отношений соседства 8M для всех ячеек матрице G вы- числяется по формуле: 43245288 2  )(N)(N(N)M (7) По формуле (7) для матрицы G порядка 6 получим 220 связей соседства. Если для матрицы G вычислять соседство грубой оценкой 28 N , то это на 23,6% больше связей, чем задано правилами GU . Проектирование решающих правил монолитности U основано на конфигурации соседства GU . Простой, но не эффективной, процедурой определения монолитности является циклическая обработка ячеек матрицы G, одним внешним и одним вложенным циклами. Пусть вложенный цикл заменяется логико-алгебраическим выражением, спроекти- рованным с учётом конфигурации GU , а внешний цикл реализуется типовым повторе- нием этого выражения, необходимое количество раз. Такой алгоритм определения монолитности относится к систолическому автомату. Общий вид автомата монолит- ности приведен на рис. 9. ЭП1 0..0 1 ЭП2 ЭП3 ЭПE ∑ … … G Рисунок 9 – Систолический автомат определения монолитности матрицы G Зная для матрицы G популяцию единиц E, нужно выполнить E итераций про- верки «кто твой сосед?». Архитектура систолического автомата – линейная сеть из элементарных процессоров ЭП, количеством E штук (рис. 10). Каждый процессор содержит K-решающих логических правил, основанных на конфигурации соседства GU . К процессору идет две шины данных. Первая шина – это значение ячеек матрицы G, а вторая шина это массив промежуточных значений u от предыдущего процессора в каскаде. Выход процессора – это шина массива промежуточных значений u. На первый процессор подается массив u содержаний все нули, кроме одной ячейки, в которой стоит единица. Ненулевая ячейка – это произвольный элемент матрицы G имеющий значения типа b, индекс которого надо знать заранее или предварительно обнаружить. Автомат, выполнив E итераций каскада, осуществит передачу сигнала «кто твой сосед?». В монолитной матрице G должно быть E связанных соседей. На выходе последнего процессора находится алгебраический сумматор элементов массива u, только для ячеек матрицы G типа b. Если сумма равна E, то матрица G монолитная. Гудаев О.А. «Искусственный интеллект» 2014 № 2 62 3Г В Рисунок 10 – Схемотехническая схема систолического автомата Реализация автомата на языке Паскаль для матрицы порядка 6, без тиражиро- вания, когда остается внешний цикл, приведена на рис. 11. u1:=1; u2:=0; u3:=0; ... u35:=0; u36:=0; for m:=1 to E do begin u2:=(g1 and u1) or (g3 and u3) or (g7 and u7) or (g8 and u8) or (g9 and u9); ... u36:=(g35 and u35) or (g29 and u29) or (g30 and u30); end; U:=(g1 and u1) + (g2 and u2) + (g3 and u3) + ... (g34 and u34) + (g35 and u35) + (g36 and u36); if U<>E then Continue; // Нет монолитного соседства Рисунок 11 – Листинг автомата монолитности эквиаффинного слова Переменные g1, g2, g3 и так далее – это биты эквиаффинного слова. Утверждение 19. Монолитность U эквиаффинного слова является естественным системным свойством, позволяющим однозначно провести пространственную сегмента- цию геометрической фигуры. Например, два кода AprilTag, не имеющих рамку по периметру, будут ошибочно сегментированы (рис. 12). В немонолитное эквиаффинное слово всегда требуется искусственно внести системный признак, объединяющий части геометрического образа в единое целое, что всегда приводит к уменьшению инфор- мационной и геометрической сложности слова. Монолитное слово простой и точный математический объект в рамках теории комбинаторики эквиаффинных слов. Немонолит- ное слово морфологически всегда иерархический объект, обладающий метауровнем, который описывает – как объединять части образа. Поэтому математическая модель немонолитного слова выходит за рамки теории комбинаторики эквиаффинных слов. Утверждение 20. Образ монолитного эквиаффинного слова G однозначно интер- претируется в системе графических объектов, если обладает достаточной геометрической сложностью S. Мерой геометрической сложности образа, с одинаковым значением популяции единиц E, является количества граней начертания геометрической фигуры в Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 63 3Г однородной дискретной среде прямоугольных ячеек. На рис. 13а приведен контур монолитного зрительного образа порядка 6, размеченного «колышками». Образ имеет 24 грани, что является числовым выражение сложности S. На рис. 13б приведен зри- тельный образ, размеченный прямоугольными областями. Количество областей Sz, равное восьми, является параметром геометрической сложности образа. Параметр предложен Э. Олсоном. Образ кода №1 Образ кода №2 Ошибка сегментации Код AprilTag Рисунок 12 – Немонолитные части кода AprilTag, без рамки, сливаются Пояснение к утверждению 20. Например, в расчёте параметра состояния культуры клеток используется формула компактности объекта, которая учитывает неровности краёв контура изображения клетки [12]. Компактность представляет меру сложности контура, как периметр обратно пропорциональный площади: Sq PSc 2  , (8) где P – это периметр объекта, а Sq – площадь объекта. Как показано в работе [12], большое численное значение компактности харак- терно объектам, имеющим грубый контур с большим числом изгибов. а) Учёт граней контура, S=24 б) Покрытие образа областями, Sz=8 Рисунок 13 – Визуализация критерия сложности образа Гудаев О.А. «Искусственный интеллект» 2014 № 2 64 3Г В Мера сложности Sc для фигур разного масштаба нормализуется площадью. Образы эквиаффинных слов, с одинаковым значением популяции закрашенных точек E, имеют одинаковую площадь, поэтому Sq можно убрать из формулы (8). Тогда фигура, у которой больший периметр P, более сложная. Критерий сложности Sc нарушается для двух геометрических образов с одинаковым периметром <Sq, P>. Например, для образа буквы «Т» и образа математического знака «+». Согласно критерию Олсона Э. сложность Sz фигуры на рис. 14а равна трём, а на рис. 14б равна пяти. Цифровой коллаж знака плюс – это две перекрещенные прямоугольные области с двенадцатью гранями, а графическая фигура буквы «Т» получается из знака плюс, перемещением горизонтальной области на край вертикальной области. Фигура буквы «Т» имеет восемь граней, а знака «+» двенадцать (рис. 15). Описание фигуры «Т» структурой данных займёт меньше памяти в компьютере и художнику надо начертить пером меньше отрезков. а) Образ буквы «Т», Sz=3 б) Образ знака «+», Sz=5 Рисунок 14 – Нарушение критерия сложности Sc а) Фигура «Т», сложность S=8 б) Фигура «+», сложность S=12 Рисунок 15 – Геометрическая сложность S фигур среды прямоугольных ячеек Критерий сложности Sz является неоднозначным. В книге кодов AprilTag [5], взятой из файла AprilTag36h9.txt, критерий устанавливает сложность образа не менее десяти (рис. 16). А для зрительного образа, с порядковым номером 1088 и цифровым значение P=65593069377, критерий нарушается для подобразов повернутых на 90 и 180 градусов, для которых Sz уже равно семи (рис. 17). Для исследования простых объектов W, конечного счётного множества нулей и единиц, В.И. Арнольд использовал процедуру «фрактального размножения», когда порождение элементов полного множества кандидатов осуществляется операцией Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 65 3Г «вычеты Ньютона» [13]. Критерий Арнольда: одно слово W сложнее другого 'W , если топология соответствующих полных множеств кандидатов, построенных операцией «вычетов Ньютона», структурно сложнее. Итеративная процедура построения мно- жества кандидатов требует полного перебора всех образов числового диапазона K, что является вычислительно затратным. Рисунок 16 – Сложность кода AprilTag №1088, N=6, D=9, Sz=10 Рисунок 17 – Сложность образа Sz снизилась до семи В логике геометрических образов законов функционирования автоматов [14] для числового значения оценки сложности использованной рекуррентной формы имеем формулу 10 0 /)(  mnkm , где k – число знаков в последовательности, порожденных применением рекуррентной формы F, а n – мощность алфавита, 0m – количество чисел, показывающих наименьший порядок рекуррентной формы, определяющей всю последовательность нулевого спектра )()( 00  m . По своей структуре формула (8) похожа на формулу сложности  . Утверждение 21. Формула подсчета количества граней S монохромного изобра- жения является линейной и логико-арифметической. Шесть логических правил первого порядка, по внешнему контуру и по внутреннему контуру фигуры, обнаруживают вертикальные и горизонтальные грани. На рис. 15 вдоль всего контура фигуры грани отмечены «колышками». Правила можно разбить на две подгруппы: обнаруживаю- щие одну грань, таких будет четыре правила, и обнаруживающих две грани, таких Гудаев О.А. «Искусственный интеллект» 2014 № 2 66 3Г В будет два правила. Количество граней равно количеству прямых углов, но для обнару- жения углов необходимо восемь правил. Для каждого правила можно составить булево выражение с литерами эквиаффинного слова. Посчитав количество истинных буле- вых выражений, получим меру геометрической сложности эквиаффинного слова S. Утверждение 22. Пусть элемент массива X(i,j) содержит литеру бинарного эквиаффинного слова W(k), где k=1+(i-1)N+(j-1), i,j=1, 2, 3...N. Пусть существует вспомогательный массив инвертированных значений литер эквиаффинного слова Y(i,j)=~X(i,j). Составим шесть правил обнаружения граней. Список первых четырех правил логики предикатов первого порядка для обнаружения одной грани: R2 ij: ij X(i,j)&Y(i-1,j)&Y(i,j+1) R3 ij: ij X(i,j)&Y(i+1,j)&Y(i,j-1) R4 ij: ij X(i,j)&Y(i,j-1)& X(i-1,j)&X(i-1,j-1) R5 ij: ij X(i,j)&Y(i-1,j+1)&X(i-1,j)&X(i,j+1) Для обнаружения двух граней используем следующие два правила: R1 ij: ij X(i,j)&Y(i,j-1)&Y(i-1,j) R6 ij: ij X(i,j)&Y(i,j+1)&X(i-1,j)&X(i-1,j+1) Утверждение 23. Правила R ij для первого и N-го столбцов, для первой и N-й строки могут обращаться только к индексам массива X. Поэтому в синтезированных новых правилах R'ij нужно заменить X(,) и Y(,) на константу  1,0 и сократить количество компонентов логических выражений. Правила логики предикатов второго порядка L описывают систему генерации правил логики предикатов первого порядка R'ij, в зависимости от размещения элемента в массиве X: Если i>1 и j>1 и i<N и j<N, то R'ij =R ij остаётся без изменений; Если i=1 и j=1, то Y(i-1,j)=Y(i,j-1)=Y(i-1,j+1)=1, а X(i-1,j)=X(i,j-1)=X(i-1,j+1)=X(i-1,j-1)=0; Если i=1 и j=N, то Y(i-1,j)=Y(i,j+1)=Y(i-1,j+1)=1, а X(i-1,j)=X(i,j+1)=X(i-1,j+1)=X(i-1,j-1)=0; Если i=N и j=1, то Y(i+1,j)=Y(i,j-1)=1, X(i,j-1)=X(i-1,j-1)=0; Если i=N и j=N, то Y(i+1,j)=Y(i,j+1)=Y(i-1,j+1)=1, X(i,j+1)=X(i-1,j+1)=0; Если i=1 и j>1 и j<N, то Y(i-1,j)=Y(i-1,j+1)=1, X(i-1,j)=X(i-1,j+1)=X(i-1,j-1)=0; Если i=N и j>1 и j<N, то Y(i+1,j)=1; Если j=1 и i>1 и i<N, то Y(i,j-1)=1; Если j=N и i>1 и i<N, то Y(i,j+1)=Y(i-1,j+1)=1, X(i,j+1)=X(i-1,j+1)=0. Введём переменную qi для логики предикатов второго порядка L: q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 {X(i,j),Y(i,j-1),Y(i-1,j),Y(i,j+1),Y(i+1,j),X(i-1,j),X(i-1,j-1),Y(i-1,j+1),X(i,j+1),X(i-1,j+1)} Тогда, аксиомы теории L имеют вид: R1'ij: qi L(“R1 ij”, q1, q2, q3); R2'ij: qi L(“R2 ij”, q1, q2, q4); R3'ij: qi L(“R3 ij”, q1, q5, q2); R4'ij: qi L(“R4 ij”, q1, q2, q6, q7); R5'ij: qi L(“R5 ij”, q1, q8, q6, q9); R6'ij: qi L(“R6 ij”, q1, q4, q6, q10). Утверждение 24. Геометрическая сложность S эквиаффинных слов одной популяции E=const, вычисляется линейной формулой: )''(2)''''( 615432 ijijijijijij RRRRRRS   , для i,j=1, 2, 3...N (9) Для уменьшения количество логических операций & в правилах R* ij можно вынести за скобки компонент X(i,j). В работе [9] показаны результаты вычисления геометрической сложности некоторых зрительных образов большого размера – матрица G порядка 36, когда слово W имеет длину K=1296 литер. Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 67 3Г Утверждение 25. Элементы множества A можно объединить в группы одним естественным способом. Если различать одинаковые значения литер iw типа a или b, на соответствующих позициях i, для всех эквиаффинных слов группы. Утверждение 26. Список позиций и тип фиксируемых значений определяет схожесть геометрических образов группы. Если фиксируемые литеры принимают только значение типа b, то они являются опорными точками геометрической фигуры. Для задания конфигурации опорных точек F достаточно перечислить только позиции литер i в эквиаффинном слове. Размер конфигурации F обозначим числом T. Маркеры расширенной реальности ARGET для матрицы 66G имеют четыре опорные точки  36,31,6,166 F .                      11 11 2345 789101112 131415161718 192021222324 252627282930 32333435 66 wwww wwwwww wwwwww wwwwww wwwwww wwww G                            11111111 11 11 11 11 11 11 11111111 123456 789101112 131415161718 192021222324 252627282930 313233343536 88 wwwwww wwwwww wwwwww wwwwww wwwwww wwwwww G Маркеры дополненной реальности ARTag, AprilTag имеют в действительности размер матрицы 88G порядка восьми. Цифровое содержание кода ARTag описывается немонолитным словом, размещаемым в матрице порядка шесть. Поэтому внутренняя часть образа, по периметру, окружено опорными точками:            6463626160595857 ,56494841403332252417169 ,87654321 88F Зрительный образ немонолитного кода ARTag пространственно больше по пло- щади на 77,8%, чем образ монолитного кода ARGET. Поэтому эту особенность всегда необходимо учитывать в определении геометрической сложности образов и сравнении объёмов передачи данных по оптическим каналам связи типа FEC. В определении монолитности U образа эквиаффинного слова для инициализации переменной u систолического автомата выбирается первая компонента множества F. Поэтому, для автомата не надо предварительно обнаруживать ненулевую ячейку. Следствие из утверждения 26. Предел информационной сложности D для группы слов, заданной опорными точками F, снижается до показателя K-T. Утверждение 27. Опорные точки F являются каркасом геометрической фигуры. Геометрическое подобие образов эквиаффинных слов группы является важным системным признаком в распознавании образов в системах технического зрения. Для кон- фигурации F, с небольшим количеством элементов 4/KT  , подобие визуально не различимо. Утверждение 28. Опорные точки F группы монолитных эквиаффинных слов являются силуэтом каркаса геометрических фигур. Свойство монолитности образа стягивает к опорным точкам, как к аттракторам, точки фигуры типа b. Поэтому конфигурации F для монолитной группы, с небольшим количеством элементов /10,T K уже имеет визуально различимое подобие силуэтов. Гудаев О.А. «Искусственный интеллект» 2014 № 2 68 3Г В Следствие 1 из утверждения 28. В системах технического зрения явно вы- раженный силуэт имеет характер системного признака, улучающего надежность и устойчивость в распознавании образа. Следствие 2 из утверждения 28. Явно выраженный силуэт образа обладает уникальным свойством, позволяющим пространственному методу детектора определять положение фигуры в аффинном пространстве. Пример А: силуэт квадрата порядком N будет различаться, если квадратная конфигурация опорных точек для монолитной группы будет F4={1, N, 1)1(  NN , NN  }. Опорные точки, размещенные по углам фигуры, из-за монолитности гео- метрического образа, будут формировать силуэт четырехугольника на проекции аффинного пространства, как показано в работе [6]. Пример Б: центростремительная конфигурация для матрицы порядка N=5 будет F1={13}. Радиальные лучи, расходящиеся из центра, будут формировать образ «звезды в небе». Пример В: исходя из положения элементов типа b в матрице G, можно опреде- лить решающее правило для построения динамической конфигурации F: всегда столбец по вертикали или строка по горизонтали должна иметь не менее двух элементов типа b. Силуэт таких фигур будет иметь очертание квадратной области. Пример Г: образы планарной системы маркеров ARTag имеют рамку цвета объекта. Образ маркера ARTag порядка N=5, имеем конфигурацию FN={1, 2, 3, 4, N, N+1, N+N, 12 N , N3 , 13 N , N4 , 14 N , NN  }. Теория проектирования лексикографических AR-кодов. Утверждение 29. Эквиаффинные слова множества A, одной популяции E, порядка N, характеризую- щиеся:  монолитностью U;  не пустой конфигурацией опорных точек F ;  не примитивной геометрической сложностью 0S ;  достаточной информационной сложностью, исключающей симметричность и регулярность подобразов 9D , образуют подмножество маркеров M, которые можно описать системой <N, E, D, U, S, F>. Так как множество A упорядочено по возрастанию десятичного числа PT, то множество M тоже упорядочено по возрастанию. На рис. 18 приведена экранная форма компьютерной программы исследования свойств эквиаффинных слов. Следствие 1 из утверждения 29. Подмножество маркеров M является списком кандидатов на построение кодового словаря искусственного языка роботов. Геометри- ческий образ маркера служит основой построения кода C – устойчивой и надежной подсистемы передачи сообщений оптическим путём в системах технического зрения и навигации машин. Теория комбинаторики эквиаффинных слов M стремится спроекти- ровать идеальный код C для расширенной реальности. Следствие 2 из утверждений 13 и 29. Подмножество маркеров M эквиаффинных слов A строится комбинаторным перебором. Поэтому множество M естественным путем упорядочено по возрастанию десятичного числа PT. Утверждение 30. Кодовый словарь C строится лексикографическим способом из кандидатов множества M. Комбинаторный перебор осуществляется в диапазоне 2K-T над всеми элементами множества M, которые составляют полный, не случайный список эквиаффинных слов A из диапазона 2K. Например, для кода ARGET, с задан- ной характеристикой <N=6, 66F , T=4>, количество кандидатов млрд 2.4232  , а для кода Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 69 3Г AprilTag млрд 7,68236  . Например, самое большое по размеру множество M, задан- ное системой <N=6, E=22, 9D , U, 28S , F={1, 6, 31, 36}>, имеет 44 107 134 элемента. Но самая большая книга кодов получается из множества с характеристикой E=21, содержащего 40 718 480 элементов. Рисунок 18 – Компьютерная программа анализа свойств маркеров M Утверждение 31. Результативность построения множества C, можно оценить количеством V получаемых лексикографических кодов. Количество V зависит только от стратегии алгоритма лексикографического построения, а не от полноты исходных данных. Чем больше величина V, тем больший объём сообщений можно закодиро- вать словарём C. Пояснение. Для эмерджентного эвристического алгоритма количество получаемых кодов V – случайная величина, ограниченная способностью решающих правил улавли- вать глобальные закономерности. Выявление решающих правил – трудная задача для гигантского количества элементов множества M. Величина V для эмерджентного поиска не превосходит результаты комбинаторного построения C. Эмерджентные лексико- графические алгоритмы, такие как для кода AprilTag, основанные на эвристических правилах, не дают возможности точно повторить результаты поиска книги кодов, так как используют шаги случайного перехода на итерациях подбора кандидатов. Поэтому эмерджентные лексикографические алгоритмы не приемлемы для построения точных моделей комбинаторики эквиаффинных слов. Утверждение 32. Для линейного комбинаторного перебора количество V получаемых лексикографических кодов C фиксированное. Результативность алгоритма комбина- торного перебора зависит только от порядка следования кандидатов множества M. Утверждение 33. Перебор с конца в начало множества M даёт большее ко- личество лексикографических кодов C. Возможно, в конце последовательности M, упорядоченной по возрастанию десятичного числа TP , находятся оригинальные, не похожие на другие, эквиаффинные слова. Гудаев О.А. «Искусственный интеллект» 2014 № 2 70 3Г В Гипотеза 1, следующая из утверждения 33: должна существовать линейная перестановка элементов множества M, которая увеличивает количество обнаруживаемых лексикографических кодов. Утверждение 34. Аффинный характер построения четырех изоморфных подобразов влияет на величину информационной сложности D. Аффинное вращение матрицы G на прямой угол задаёт планетарный характер манипуляция со строками и столбцами, что выявляет радиальную структуру образа эквиаффинного слова. Общая планетар- ная модель приведена на рис. 19а, где объект «1» – неподвижное солнце, а объекты «2» и «3» – это планеты. Планетарная модель пространственной структуры эквиаффинного слова для матрицы 66W порядка 6 приведена на рис. 19б. 1 2 3                      123456 789101112 131415161718 192021222324 252627282930 313233343536 66 wwwwww wwwwww wwwwww wwwwww wwwwww wwwwww W а) Общая модель б) Модель для эквиаффинного слова Рисунок 19 – Планетарная модель пространственной структуры Утверждение 35. Для дискретной квадратной матрицы G предполагаемые пла- нетарные орбиты, радиально расходящиеся от цента, можно представить наборами точек LG, размещенных по периметру квадрата (рис. 19б). Вложенные квадраты достигают границ матрицы G. Поэтому, максимальная величина удаления периметра квадрата от центра равна N/2 для чётных N. Например, для матрицы 66W имеем три планетарные группы:    .,,,)( ;,,,,,,,,,,,)( ; ,,,,,,,,, ,,,,,,,,,, )( 2221161566 1 292827262320171411109866 2 36353433323130252419 1813127654321 66 3 wwwwWLG wwwwwwwwwwwwWLG wwwwwwwwww wwwwwwwwww WLG             Утверждение 36. Структура эквиаффинного слова имеет иерархический вид. Имеем следующие уровни иерархии )(GLG j , для чётных N, описываемые наборами точек квадратного периметра, с приоритетом вложенности под номерами j=N/2, (N/2)-1, (N/2)-2 ... 1. Чем дальше периметр от центра матрицы G, тем больший вклад он делает в информационную сложность образа D, так как содержит большее коли- чество точек LG на уровне j, c учётом исключенных опорных точек F. Утверждение 37. Каждый периметр уровня структуры эквиаффинного слова имеет свою величину популяции ))(( GLGE j литер типа b. Можно переставить элементы множества M стратегией плавных структурных изменений, описываемых линейным показателем EQ. Например, для маркеров M, порядка N=6, числовой показатель плавных струк- турных изменений аффинного слова можно задать линейной формулой: 1 2 2( ) 1000000 ( ( )) 100 ( ( )). N N EQ G E LG G E LG G      (10) Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 71 3Г Например, для матрицы 66W формула (10) имеет вид: ))((100))((1000000)( 66 3 66 2 66   WLGEWLGEWEQ . Утверждение 38. Пусть кандидаты в маркеры M с одинаковым показателем EQ образуют группы Z1, Z2... Z . Последовательность групп Z упорядочена по возрастанию EQZ1<EQZ2< ... <EQZ. Элементы одной группы iZ вторично упорядочим по убыванию числа PT. Объединив упорядоченные группы iZ , по возрастанию показателя EQ, получим новое множество кандидатов ZM . Перебор с начала в конец множества ZM даёт большее количество лексикографических кодов C, чем обратный просмотр множества M, рассмотренный в утверждении 33. Компьютерный эксперимент, основанный на утверждении 38, полностью подтверждает гипотезу 1. Используя в формуле (10) множество кандидатов M: <N=6, E=21, 9D , U, 28S , F={1, 6, 31, 36}, )( 66WEQ > разбивается на 49 Z-групп. Гипотеза 2: оптимизация порядка следования групп iZ , объединяемых в мно- жество ZM , должна давать прирост количества V кодов C. Утверждение 39. Пусть оптимальный порядок задаётся конфигурацией O в виде списка индексов i групп Z . Конфигурацией O является однозначной комбинаторной моделью нового множества OM . Множество OM создаётся аналогично множеству ZM , из переставленных групп iZ . Утверждение 40. Процедура поиска оптимальной конфигурации O является эвристи- ческой. Эвристический алгоритм основан на «ручной» перестановке. На начальном шаге множество OM равно множеству ZM , и количество кодов равно ( ( )).ZV C M В цикле итераций переставляем первую группу в конец списка групп, затем строим множест- во OM и по нему находим лексикографический код )( OMC . Если количество кодов ))(( OMCV увеличилось или не изменилось ))(())(( ZO MCVMCV  , то на следующей итерации переставляем вторую группу в конец. Если уменьшилось количество кодов, то первая группа остаётся в начале, и переставляется в конец только вторая группа. Затем пробуем переставить третью группу и так далее, вплоть до последней группы Z. Пробуя поочередно переставлять группы iZ , получаем оптимальную конфигурацию O. Например, для кода ARGET, описываемого системой <N=6, E=21, 9D , U, 28S , F={1, 6, 31, 36}>, была получена оптимальная конфигурации O: {1, 2, 4, 6, 7, 8, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 36, 37, 38, 42, 44, 47, 3, 5, 9, 10, 14, 15, 19, 34, 35, 39, 40, 41, 43, 45, 46, 48, 49}. Компьютерный эксперимент по созданию кода ARGET подтвердил гипотезу 2, но увеличение количества лексикографических кодов V для множества MO незначи- тельное. Список 436-ти маркеров книги кодов ARGET приведен в [15]. Выводы В работе прояснена ситуация с представлением лексикографических кодов для расширенной реальности. Описаны логическая, кибернетическая, геометрическая и математическая модели зрительного образа 2D-маркера. Применен формальный подход комбинаторики слов для описания эквиаффинных форм 2D-маркера. Описаны важные свойства формы: информационная сложность, геометрическая сложность, монолит- ность. Все свойства применимы для семантического анализа растровых битональных изображений. Гудаев О.А. «Искусственный интеллект» 2014 № 2 72 3Г В В работе описана эффективная процедура построения книги лексикографических кодов размером 66 , которая быстро отбраковывает меньше 75% кандидатов. В мно- жестве A содержится 17 179 934 976 элементов из 68 719 476 736, что на 65 тысяч 792 чисел больше 25%. Причём, из чисел разницы, только 512 чисел имеют TP = RP = BP = LP . Реальный размер получен в ходе компьютерного эксперимента, который уточнил ожидаемую цифру в 3/4 элементов аксиоматической конфигурации эквиаффинного множества. Основываясь на изложенном материале, перспективным является исследование зрительных образов c разрешением 77 и 88 , что было пока не доступно со- временным изобретателям двухмерных штрих-кодов. В будущем, модель проектирования двухмерных дискретных структур для коммуникации в оптической среде послужит основой создания в новой среде нано- мира 3D-моделей DNA-оригами кода передачи FEC-сообщений. Список литературы 1. Шевченко А.И. Проектирование системы мониторинга учебного процесса дистанционного образования на базе технологий искусственного интеллекта / А.И. Шевченко, О.А. Гудаев, С.П. Некрашевич // Искусственный интеллект. – 2010. – № 1. – С. 11-20. 2. Гудаев О.А. Аффинные углы поворота плоскости маркера расширенной реальности ARGET, используемые в интеллектуальной обработке информации системой дистанционного образования / О.А. Гудаев, А.И. Шевченко // Интеллектуальный анализ информации (ИАИ-2009): Материалы IX Международной научной конференции имени Т.А. Таран, Киев, 19 - 22 мая 2009 г. : сб.тр. / ред. кол. : С.В. Сирота (гл. ред.) и др.  К. : Просвіта.  2009.  С. 87-93. 3. Гудаєв О.О. Організація зграєвої взаємодії в групах робототехнічних пристроїв з використанням графічної мови розширеної реальності ARGET / О.О. Гудаєв // Комп'ютерні науки та інженерія (CSE-2009): Матеріали III Міжнародної конференції молодих вчених, Львів, 14 -16 травня 2009 р.  Львів : Видавництво Національного університету "Львівська політехніка".  2009.  С. 125-128. 4. Гудаев О.А. Синтез и анализ предложений графического языка передачи сообщений в мобильных робототехнических системах с элементами расширенной реальности (ARGET) / О.А. Гудаев // Искусственный интеллект.  2006.  № 2.  С. 467-498. 5. Olson E. AprilTag: A robust and flexible visual fiducial system / Edwin Olson // In Proceedings of the IEEE International Conference on Robotics and Automation, 9-13 May 2011. – Shanghai, China : ICRA, 2011. – P. 3400-3407. 6. Гудаев О.А. Распознавание маркеров расширенной реальности ARGET робототехнической системой / О.А. Гудаев // Известия ТРТУ. Тематический выпуск «Интеллектуальные и много- процессорные системы».  Таганрог : Изд-во ТРТУ.  2006.  №16 (71).  C. 85-90. 7. Гудаев О.А. Сегментация аффинных проекций маркеров ARGET робототехнической системой / О.А. Гудаев // Искусственный интеллект.  2007.  № 4.  С. 580-586. 8. Гудаев О.А. Графический язык роботов ARGET / О.А. Гудаев // Системный анализ и информационные технологии (САИТ-2009): Материалы XI Международной научно-технической конференции, Киев, 26 - 30 мая 2009 г.  К. : УНК "ИПСА" НТУУ "КПИ".  2009.  С. 291-291. 9. Игнатов Ф.Ю. Сложность геометрического образа на примере алфавитно-цифровой последовательности / Ф.Ю. Игнатов, О.А. Гудаев // Материалы Международной научной молодежной школы 23 – 27 сентября 2013 : «Системы и средства искусственного интеллекта», Кацивели, АР Крым, Украина. – Донецк : ИПИИ МОН и НАН Украины «Наука і освіта». – 2013. – С. 112-116. 10. Янушкевич С.Н. Систолические алгоритмы синтеза арифметических полиномиальных форм k-значных функций алгебры логики / С.Н. Янушкевич // Автомат. и телемех.  1994.  № 12.  С. 128-142. 11. Зудина Т.В. Эквиаффинные отображения / Т.В. Зудина, С.Е. Степанов, И.Г. Шандра // Известия высших учебных заведений. Математика.  2007.  № 8. – С. 27-34. 12. Меркулова Е.В. Оценка функционального состояния клеток с использованием методов цифровой обработ- ки изображений / Е.В. Меркулова, А.А. Трибрат, И. Г. Герасимов // Наук. праці Донецького нац. техніч. унів. Сер. : Обчислювальна техніка та автоматизація. – Донецьк: ДонНТУ.  2006. – Вип. 106. – С. 145-149. Комбинаторика эквиаффинных слов для проектирования... «Штучний інтелект» 2014 № 2 73 3Г 13. Арнольд В.И. Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств / В.И. Арнольд // Публичная лекция 13 мая 2006 г. [Електронний ресурс]. – Режим доступу : http://mms.math-net.ru/meetings/2005/arnold.pdf. 14. Твердохлебов В.А. Геометрические образы законов функционирования автоматов / В.А. Твердохлебов. – Саратов : изд-во «Научная книга». – 2008. – 183 с. 15. КНИГА КОДОВ ARGET: 436 маркеров. [Електронний ресурс]. – Режим доступу : http://cawbot.com. References 1. Shevchenko A.I. Proektirovanie sistemy monitoringa uchebnogo processa distancionnogo obrazovanija na baze tehnologij iskusstvennogo intellekta / A.I. Shevchenko, O.A. Gudayev, S.P. Nekrashevich // Iskusstvennyj intellekt. – 2010. – № 1. – S. 11-20. 2. Gudayev O.A. Affinnye ugly povorota ploskosti markera rasshirennoj real'nosti ARGET, ispol'zuemye v intellektual'noj obrabotke informacii sistemoj distancionnogo obrazovanija / O.A. Gudayev, A.I. Shevchenko // Intellektual'nyj analiz informacii (IAI-2009): Materialy IX Mezhdunarodnoj nauchnoj konferencii imeni T.A. Taran, Kiev, 19 - 22 maja 2009 g. : sb.tr. / red. kol. : S.V. Sirota (gl. red.) i dr. – K. : Prosvіta. – 2009. – S. 87-93. 3. Gudayev O.A. Organizacija zgrajevoi vzajemodii v grupah robototehnichnyh prystroiv z vykorystannjam grafichnoi movy rozshyrenoi real'nosti ARGET / O.A. Gudayev // Komp'juterni nauky ta inzhenerija (CSE-2009): Materialy III Mizhnarodnoi konferencii molodyh vchenyh, Lviv, 14 -16 travnja 2009 r.  Lviv : Vydavnyctvo Nacional'nogo universytetu "Lvivs'ka politehnika".  2009.  S. 125-128. 4. Gudayev O.A. Sintez i analiz predlozhenij graficheskogo jazyka peredachi soobshhenij v mobil'nyh robototehnicheskih sistemah s jelementami rasshirennoj real'nosti (ARGET) / O.A. Gudayev // Iskusstvennyj intellekt.  2006.  № 2.  S. 467-498. 5. Olson E. AprilTag: A robust and flexible visual fiducial system / Edwin Olson // In Proceedings of the IEEE International Conference on Robotics and Automation, 9-13 May 2011. – Shanghai, China : ICRA, 2011. – P. 3400-3407. 6. Gudayev O.A. Raspoznavanie markerov rasshirennoj real'nosti ARGET robototehnicheskoj sistemoj / O.A. Gudayev // Izvestija TRTU. Tematicheskij vypusk «Intellektual'nye i mnogoprocessornye sistemy».  Taganrog : Izd-vo TRTU.  2006.  №16 (71).  S. 85-90. 7. Gudayev O.A. Segmentacija affinnyh proekcij markerov ARGET robototehnicheskoj sistemoj / O.A. Gudayev // Iskusstvennyj intellekt.  2007.  № 4.  S. 580-586. 8. Gudayev O.A. Graficheskij jazyk robotov ARGET / O.A. Gudayev // Sistemnyj analiz i informacionnye tehnologii (SAIT-2009): Materialy XI Mezhdunarodnoj nauchno-tehnicheskoj konferencii, Kiev, 26 - 30 maja 2009 g.  K. : UNK "IPSA" NTUU "KPI".  2009.  S. 291-291. 9. Ignatov F.Ju. Slozhnost geometricheskogo obraza na primere alfavitno-cifrovoj posledovatel'nosti / F.Ju. Ignatov, O.A. Gudayev // Materialy Mezhdunarodnoj nauchnoj molodezhnoj shkoly 23 – 27 sentjabrja 2013 : «Sistemy i sredstva iskusstvennogo intellekta», Kaciveli, AR Krym, Ukraina. – Doneck : IPII MON i NAN Ukrainy «Nauka і osvіta». – 2013. – S. 112-116. 10. Janushkevich S.N. Sistolicheskie algoritmy sinteza arifmeticheskih polinomial'nyh form k-znachnyh funkcij algebry logiki / S.N. Janushkevich // Avtomat. i telemeh.  1994.  № 12.  S. 128-142. 11. Zudina T.V. Jekviaffinnye otobrazhenija / T.V. Zudina, S.E. Stepanov, I.G. Shandra // Izvestija vysshih uchebnyh zavedenij. Matematika. – 2007. – № 8. – S. 27-34. 12. Merkulova E.V. Ocenka funkcional'nogo sostojanija kletok s ispol'zovaniem metodov cifrovoj obrabotki izobrazhenij / E. V. Merkulova, A. A. Tribrat, I. G. Gerasimov // Nauk. pracі Donec'kogo nac. tehnіch. unіv. Ser. : Obchisljuval'na tehnіka ta avtomatizacіja. – Donec'k: DonNTU. – 2006. – Vip. 106. – S. 145-149. 13. Arnol'd V.I. Slozhnost konechnyh posledovatel'nostej nulej i edinic i geometrija konechnyh funkcional'nyh prostranstv / V.I. Arnol'd // Publichnaja lekcija 13 maja 2006 g. [Elektronnij resurs]. – Rezhim dostupu : http://mms.math-net.ru/meetings/2005/arnold.pdf. 14. Tverdohlebov V.A. Geometricheskie obrazy zakonov funkcionirovanija avtomatov / V.A. Tverdohlebov. – Saratov : izd-vo «Nauchnaja kniga». – 2008. – 183 s. 15. KNIGA KODOV ARGET: 436 markerov. [Elektronnij resurs]. – Rezhim dostupu : http://cawbot.com. Гудаев О.А. «Искусственный интеллект» 2014 № 2 74 3Г В RESUME O.A. Gudayev Combinatorics on Equaffine Words for Design Lexicographic Codes of Augmented Reality The article discusses the construction of a mathematical description of the process of designing codes for Augmented Reality Systems. System based on Computer Vision, one of the problems of Artificial Intelligence. Was first proposed a detailed study of discrete structures, which formed the basis for message passing through an optical link. The purpose of this study is to examine the nature of the digital marker. The study involves a finite range of natural numbers. Including acting as a source for generating visual images. All variety of images describe equaffine words. Marker was presented a cellular automaton model. Machine was synthesized computing systolic architecture. Complexity architecture description has been overcome by using second-order predicate logic. Automaton model of the visual image was studied and expanded methods in combinatorics on words. Was studied the characteristics of the equaffine word: the count of population, the monolithic, information and geometric complexity, spatial structure. Received procedure for rapid generation of a plurality of images, with a given characteristic. Was studied strategy for obtaining code book lexicographic method. Was found optimal configuration combina- torics on words. Metamodel 2D digital image makes understandable the nature of the Augmented Reality marker. Found strategies and procedures of lexicographical codes extend applied aspects of the theory of combinatorics on words. Статья поступила в редакцию 03.04.2014.
id	nasplib_isofts_kiev_ua-123456789-85252
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-12-07T18:53:36Z
publishDate	2014
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Гудаев, О.А. 2015-07-23T12:44:41Z 2015-07-23T12:44:41Z 2014 Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности / О.А. Гудаев // Искусственный интеллект. — 2014. — № 2. — С. 51–74. — Бібліогр.: 15 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85252 004.942+004.93'1 В статье рассматривается задача построения математического описания лексикографических кодов для расширенной реальности. Найдена формальная система проектирования кодов для надёжного и устойчивого распознавания зрительных образов. Для построения книги кодов использован классический метод комбинаторики слов. У статті розглядається задача побудови математичного опису лексикографічних кодів для розширеної реальності. Знайдена формальна система проектування кодів для надійного та сталого розпізнавання зорових образів. Для побудови книги кодів використано класичний метод комбінаторики слів. In the article consider the task of constructing a mathematical description of lexicographical codes for augmented reality. Found a formal system to design codes for robust and stability to recognition of pattern images. To construct the code book used the classical method of combinatorics on words. ru Інститут проблем штучного інтелекту МОН України та НАН України Искусственный интеллект Анализ и синтез коммуникационной информации Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности Комбінаторика еквіаффінних слів для проектування лексикографічних кодів розширеної реальності Combinatorics on equaffine words for design lexicographic codes of augmented reality Article published earlier
spellingShingle	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности Гудаев, О.А. Анализ и синтез коммуникационной информации
title	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности
title_alt	Комбінаторика еквіаффінних слів для проектування лексикографічних кодів розширеної реальності Combinatorics on equaffine words for design lexicographic codes of augmented reality
title_full	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности
title_fullStr	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности
title_full_unstemmed	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности
title_short	Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности
title_sort	комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности
topic	Анализ и синтез коммуникационной информации
topic_facet	Анализ и синтез коммуникационной информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/85252
work_keys_str_mv	AT gudaevoa kombinatorikaékviaffinnyhslovdlâproektirovaniâleksikografičeskihkodovrasširennoirealʹnosti AT gudaevoa kombínatorikaekvíaffínnihslívdlâproektuvannâleksikografíčnihkodívrozširenoírealʹností AT gudaevoa combinatoricsonequaffinewordsfordesignlexicographiccodesofaugmentedreality

Комбинаторика эквиаффинных слов для проектирования лексикографических кодов расширенной реальности

Репозитарії

Схожі ресурси