НАУКА и ОБРАЗОВАНИЕ

В.И. Левин, д-р техн. наук, проф., Пензенский технологический институт

Теория автоматов в задачах анализа сложных изображений

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

♦ 1. В работе [1] изложен математический аппарат так называемой непрерывной логики (НЛ) и описаны простейшие случаи его применения, связанные с информатикой: геометрическое моделирование, принятие приближенных решений, оптимизация и др. Существует также много других задач из области информатики и информационных технологий, которые эффективно решаются с помощью аппарата НЛ или его обобщений [1]. В частности, когда объект исследования сложный (высокоразмерный), весьма эффективным оказывается применение аппарата логических определителей. Надо заметить, что при исследовании сложных объектов “наивное” моделирование простых объектов [1] в терминах НЛ не применимо и приходится искать специальные, достаточно мощные модели для получения адекватного непрерывно-логического описания объекта. Одной из наиболее результативных моделей такого рода является конечный динамический автомат [2-4].

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

Суть этой проблемы состоит в том, чтобы по имеющемуся изображению в виде совокупности визуальных объектов в пространстве данной размерности формальным путем вычислить характеристики взаиморасположения объектов, по которым можно было бы анализировать указанное изображение для более полного понимания.

♦ 2. Рассмотрим произвольное N-мерное евклидово пространство Е^N, заполненное N-мерными объектами, с общим числом объектов n. Объекты считаются “взаимопроникающими” (пересекающимися), т.е. заполнение любым объектом любой области  не препятствует нахождению в  другого объекта. Положение каждого объекта в пространстве Е^N полностью определено. Очевидно, что изображение P, получающееся в результате взаимодействия всех имеющихся объектов пространства Е^N, можно представить в виде объединения изображений

                                                             (1)

где  - изображение пересечений k различных объектов, включающее изображения P(i₁, i₂,… i_k) всех возможных конкретных комбинаций (i₁, i₂,… i_k) k пересекающихся объектов, т.е.

                             (2)

где P₀ — псевдоизображение в некоторой области  пространства E^N, не содержащее ни одного объекта; P₁ - изображение в другой области  пространства E^N, в которой имеются только одиночные, не пересекающиеся с другими объекты; P₂ - изображение в третьей области  пространства Е^N, в которой имеются только попарно пересекающиеся объекты, и т.д. и Р_n - изображение в области  пространства E^N, содержащей только пересечение всех n объектов.

Ясно, что

                    (3)

В свою очередь,

                     (4)

где  - область пространства E^N, в которой имеется пересечение только конкретного набора k объектов J=(i₁,…, i_k).

Задача 1 состоит в том, чтобы найти области , соответствующие изображениям Р_k в виде пересечений любого фиксированного числа k неконкретизированных объектов . Задача 2 состоит в том, чтобы найти области , соответствующие изображениям P_k(J) в виде пересечений J=(i₁,…, i_k) любого числа к конкретных объектов . Задача 2 является более детализированной, из ее решения всегда можно получить решение задачи 1, используя формулу (4). Задачи 1, 2 назовем задачами анализа изображения Р.

♦ 3. Сформулированные задачи для пространств E^N различной размерности N можно интерпретировать следующим образом.

1) Пространство Е¹, т.е. прямая. Для него объектами являются заданные на прямой интервалы, причем допустимо пересечение интервалов по 2, по 3 и т.д. вплоть до n (n - общее число интервалов). Требуется найти участки прямой . на которых пересекается ровно k любых интервалов,  (задача 1), либо найти участки прямой , на которых пересекается ровно k конкретных интервалов  (задача 2).

2) Пространство Е₂, т.е. плоскость. Для него объектами являются заданные на плоскости прямоугольники, стороны которых параллельны осям координат, причем допустимо пересечение прямоугольников по 2, по 3,..., по n (n — общее число прямоугольников). Выбор в качестве взаимодействующих объектов на плоскости именно прямоугольников, очевидно, не ограничивает общности рассмотрения, так как любую плоскую фигуру можно представить с любой степенью точности с помощью вписанных в нее "плотно упакованных" прямоугольников. Требуется найти области на плоскости , в которых пересекаются ровно k любых прямоугольников,  (задача 1), либо найти области на плоскости  в которых пересекается k конкретных прямоугольников  (задача 2).

3) Пространство Е³, т.е. трехмерное пространство. Здесь объектами являются заданные в нем прямые параллелепипеды со сторонами, параллельными осям координат. Допустимо пересечение параллелепипедов по 2, по 3,..., по n (n - общее число параллелепипедов). Выбор в качестве объектов в трехмерном пространстве прямых параллелепипедов не ограничивает общности, поскольку любой трехмерный объект можно представить с любой степенью точности посредством вписанных в него "плотно упакованных" прямых параллелепипедов. Требуется найти области  в пространстве Е³, в которых пересекается ровно k  параллелепипедов, безразлично каких,  (задача 1), либо найти области  в Е³, в которых пересекается k конкретных параллелепипедов  (задача 2).

4) Пространства E^N, , т.е. четырехмерное и более высокоразмерные пространства. Для них задачи 1, 2 совершенно аналогичны задачам для пространств E¹, E², E³ и имеют такой же содержательный смысл, но не имеют той же наглядной геометрической интерпретации. При этом в качестве объектов берутся N-мерные прямые параллелепипеды со сторонами, параллельными N осям координат.

♦ 4. Будем рассматривать общий случай задач 1, 2 анализа изображения P в пространстве E^N произвольной размерности N. Согласно (1), произвольное изображение P складывается из изображений пересечения  ровно к любых различных объектов, причем области  существования пересечений P_k для различных k, согласно (3), не пересекаются. В соответствии с этим введем систему двоичных функций , в пространстве E^N:

                                                       (5)

Как видно из (5), произвольная k-я функция f_k(x) принимает значение 1 в области , где существует пересечение P_k, и значение 0 в других областях, где это пересечение отсутствует. Поэтому функцию f_k(x) естественно назвать k-й обыкновенной спектральной функцией изображения P(1), а совокупность всех таких функций f(x)={f₀(x),…, f_n(x)} - обыкновенным спектром указанного изображения. Аналогично, согласно (2), произвольное пересечение Р_k складывается из пересечений P_k(i₁,…, i_k) ровно k различных, конкретно определенных объектов i₁,…, i_k, причем области  существования пересечений P_k(i₁,…, i_k) для различных комбинаций объектов (i₁,..., i_k), согласно (4), не пересекаются. В соответствии с этим введем систему двоичных функций , в пространстве E^N, определяемых в виде

                    (6)

Из (6) видим, что произвольная k-я функция  равна 1 в области , где существует пересечение P_k(i₁,..., i_k), и равна 0 в других областях, где это пересечение отсутствует. В соответствии с этим данную функцию назовем k-й маркированной спектральной функцией изображения Р [точнее, k-й спектральной функцией, маркированной конкретной k-местной комбинацией изображаемых объектов (i₁,..., i_k)]. Совокупность всех таких функций для всевозможных комбинаций объектов по 1, по 2,..., по n назовем маркированным спектром изображения P и обозначим G(x). Таким образом, в отличие от обыкновенного спектра, отдельные спектральные функции которого выделяют области пространства с изображением пересечения того или иного числа объектов (безотносительно к составу пересекающихся объектов), в маркированном спектре отдельные спектральные функции выделяют области пространства, где изображено пересечение конкретных комбинаций объектов. Однако и те и другие обладают свойством индикации областей со всеми возможными типовыми фрагментами заданного изображения. Это подсказывает идею решения задач 1 и 2 анализа изображения, рассматриваемую в следующем пункте.

♦ 5. Так как все объекты в пространстве E^N есть N-мерные прямые параллелепипеды в E^N со сторонами, параллельными N осям координат, то пересечение любого числа k объектов  также является N-мерным прямым параллелепипедом в E^N со сторонами, параллельными N осям координат. Поэтому любое неконкретизированное Р_k либо конкретизированное P_k{i₁,..., i_k) по составу пересечение k объектов можно спроектировать на все оси координат х₁,..., x_N:

                      (7)

          (8)

где P_k(x) - проекция пересечения объектов Р_k на ось x_i, a  — проекция пересечения объектов Р_k(i₁,.., i_k) на ту же ось. Различие между этими проекциями то же, что и в исходных пересечениях: в проекции Р_k(х_i) указывается только число k объектов в исходном пересечении, а в проекции  дается еще конкретный перечень (i₁,..., i_k) объектов в пересечении. Любое пересечение Р_k, согласно (2), состоит в общем случае из  разнесенных в пространстве пересечений Р_k(i₁,.., i_k) конкретных объектов (i₁,.., i_k), . Поэтому проекция пересечения Р_k на любую ось также состоит в общем случае из  разнесенных вдоль этой оси проекций на нее пересечений Р_k(i₁,.., i_k) (которые тоже делимы):

В этом второе различие между проекциями (7) и (8). Сходство между ними в следующем: имеется однозначное соответствие любого пересечения объектов Р_k(i₁,.., i_k) и его проекций и однозначное соответствие любого пересечения объектов Р_k и его проекций при отсутствии в общем случае однозначного обратного соответствия. Однако в случае N=1 (т.е. в одномерном пространстве) имеется взаимооднозначное соответствие между пересечениями объектов и их проекциями на единственную в этом случае ось.

Введенные проекции пересечений N-мерных объектов - обыкновенные Р_k(х_r) и маркированные  - являются уже одномерными объектами, с которыми значительно проще работать. Для них общие N-мерные спектральные функции - обыкновенные (5) и маркированные (6) — переходят в соответствующие спектральные функции от одной переменной:

                    (9)

            (10)

Согласно (9), k-я функция f_k(х_r) принимает значение 1 в той части  оси x_r где существует проекция Р_k(х_r) пересечения Р_k, и значение 0 в других частях, где эта проекция отсутствует. Поэтому функцию f_k(х_r) можно назвать k-й обыкновенной одномерной спектральной функцией проекции Р_k(х_r) пересечения Р_k на ось х_r. Аналогично, согласно (10), k-я функция  равна 1 в той части  оси х_r где существует проекция  пересечения Р_k(i₁,.., i_k), и равна 0 в других частях, где эта проекция отсутствует. Поэтому функцию  можно назвать k-й маркированной одномерной спектральной функцией проекций  пересечения Р_k(i₁,.., i_k) на ось х_r.

Совокупность всех функций  назовем обыкновенным одномерным спектром изображения Р (1) вдоль оси х_r N-мерного пространства . Аналогично совокупность всех функций ,  назовем маркированным одномерным спектром изображения Р (1) вдоль оси х_r N-мерного пространства .

Введенные одномерные спектры обладают свойством индикации участков соответствующих осей N-мерного пространства, на которых имеется проекция рассматриваемого пересечения объектов в этом пространстве. Отсюда следует, что задачи 1 и 2 анализа изображения в N-мерном пространстве целесообразно пытаться решить путем их сведения либо к анализу одномерных спектров проекций этого изображения на все N осей пространства, либо просто к вычислению одномерных спектров вдоль параллельных прямых, пересекающих изображение.

♦ 6. Реализацию идеи, высказанной в п. 5, начнем с задач анализа изображений в одномерном пространстве, т.е. на прямой. Задача 1 в этом случае состоит в следующем. На оси x задано изображение P в виде совокупности n одномерных объектов - замкнутых интервалов  (рис. 1).

Рис. 1.

Эти интервалы могут взаимодействовать между собой, образуя различные пересечения. В результате изображение P распадается, согласно (1), на изображения: P₀ в области  на оси x, не

содержащее ни одного интервала; Р₁, в области  содержащее только любые одиночные, непересекающиеся с другими интервалы; Р₂ в области , содержащее только попарно пересекающиеся интервалы, ..., Р_n в области , содержащей только пересечение всех n интервалов. Задача заключается в нахождении областей , на оси x, содержащих изображения Р_k, , в виде пересечения любого фиксированного числа k неконкретизированных (т.е. любых) интервалов.

Будем интерпретировать точки оси x как моменты времени. Тогда задаче 1 с заданной системой интервалов можно поставить в соответствие математическую модель в виде конечного автомата без памяти (рис. 2) с n двоичными входами , на которые подаются единичные импульсы 1(a_i, b_i) (по одному на каждый вход), существующие во временных интервалах (a_i, b_i), соответствующих заданным интервалам .

Рис. 2.

Этот автомат имеет один двоичный выходу, , на котором реализуется фундаментальная симметрическая булева функция  индекса  n входных переменных x₁,…, x_n. Таким образом, выходная переменная автомата выражается через его входные переменные в виде

Как известно [4], фундаментальная симметрическая булева функция =1 только тогда, когда p любых ее аргументов равны 1, и =0 в остальных случаях. Таким образом, выходная переменная автомата-модели y=1 только тогда, когда p любых его входных переменных x, равны 1. Это означает, что на выходе этого автомата единичные импульсы вырабатываются в тех временных интервалах, в которых на его входах действует одновременно (пересекается) p входных единичных импульсов. Таким образом [см. определения (5), (9)], автомат-модель (см. рис. 2) с реализуемой булевой функцией  вырабатывает на выходе обыкновенную одномерную спектральную функцию f_p(x) одной переменной x, отмечающую своими единичными значениями те области оси x, в которых пересекается p из и заданных интервалов . Варьируя значение индекса p функции  автомата-модели от 0 до n, получим обыкновенный одномерный спектр f(x)={f₀(x), f₁(x),…, f_n(x)}, составляющие которого есть функции, отмечающие области оси x, в которых пересекается любое возможное число  заданных интервалов [a_i, b_i]. Это и есть решение задачи 1 анализа изображения в одномерном пространстве. В соответствии с изложенным алгоритм решения этой задачи таков.

Шаг 1. Построение математической модели задачи 1 с заданной системой интервалов  виде конечного автомата без памяти с двоичными входами x₁,..., x_n и выходом y и реализуемой на выходе фундаментальной симметрической булевой функцией входов  с переменным индексом  с воздействиями на входах i в виде единичных импульсов x_i(t)=1[a_i, b_i], действующих во временных интервалах (a_i, b_i), соответствующих интервалам, заданным по условию задачи (см. рис. 2).

Шаг 2. Вычисление динамических процессов  на выходе построенного автомата-модели, соответствующих всем возможным значениям индекса p реализуемой автоматом функции . Это вычисление ведется по следующей формуле теории динамических автоматов [4]:

                            (11)

где  - булево отрицание дизъюнкции, а  - конъюнкция и дизъюнкция НЛ, т.е. операции min и max [1]. Здесь А' и В' - следующие логические определители ранга r, составленные соответственно из моментов а_i, изменений сигналов 0 → 1 и моментов b_i изменений сигналов 1 → 0 во входных воздействиях автомата-модели:

раскрываемые по формуле (34) [1]. В формуле (11) 1 (А, В) означают единичные импульсы в интервалах (А, В), а 0 (-,-) - нулевые паузы в промежуточных интервалах.

Шаг3. Интерпретация динамических процессов , на выходе автомата-модели как обыкновенных спектральных функций  с соответствующими значениями индекса p. Каждая функция f_p(x) есть функция одной переменной x, отмечающая своими единичными значениями те области , оси x, где пересекается p из n заданных интервалов . Таким образом, получаем решение задачи 1 в виде

                                       (12)

♦ 7. Перейдем к задаче 2 анализа изображения в одномерном пространстве. Ее формулировка такова. На оси x задано то же изображение Р в виде системы n интервалов , что и в задаче 1 (см. рис. 1). Изображение Р, согласно п. 6, распадается на изображения Р_k  с ровно k пересекающимися интервалами (любыми), . В свою очередь, Р_k, согласно (2), распадаются на изображения P_k(i₁,…, i_k) возможных конкретных комбинаций (i₁,…, i_k) k пересекающихся интервалов

                    (13)

Задача состоит в нахождении областей ,  на оси x, содержащих изображения,

 в виде пересечения k конкретных интервалов (i₁,…, i_k). Как и при решении задачи 1 (см. п. 6), интерпретируем ось x как временную ось, а заданную систему интервалов — как систему единичных импульсов 1(a_i, b_i) в соответствующих временных интервалах. Тогда задаче 2 с заданной системой интервалов можно поставить в соответствие математическую модель в виде конечного автомата без памяти (рис. 3), имеющего ту же структуру, что и автомат-модель для задачи 1 (см. рис. 2): n двоичных входов  на которые подаются указанные единичные импульсы 1(a_i, b_i) (по одному на каждый вход), и один двоичный выход y, , но другую реализуемую на выходе функцию входов

             (14)

Рис. 3.

Первая скобка в формуле (14) есть булева конъюнкция, вторая — отрицание булевой дизъюнкции. Функция  равна 1 только тогда, когда  и равна 0 в остальных случаях. Таким образом, выходная переменная автомата-модели y = 1 только тогда, когда ровно k его конкретных входных переменных  равны 1.Это означает, что на выходе данного автомата единичные импульсы вырабатываются только в тех временных интервалах, в которых на его входах действуют одновременно (пересекаются) k конкретных входных единичных импульсов . Таким образом, в соответствии с определениями (6), (10) автомат-модель, представленный на рис. 3, с реализуемой булевой функцией  вырабатывает на выходе одномерную маркированную спектральную функцию  одной переменной x, отмечающую своими единичными значениями ту область оси x, в которой пересекается к конкретных интервалов  из n заданных интервалов .

Варьируя конкретный состав  переменных функции  автомата-модели и их число , получим одномерный маркированный спектр , составляющие которого — это функции, отмечающие области оси x, в которых пересекается конкретный по составу и числу набор из заданных интервалов [a_i, b_i]. Это и есть решение задачи 2 анализа изображения в одномерном пространстве. Алгоритм решения этой задачи, согласно изложенному, следующий.

Шаг 1. Построение математической модели задачи 2 с заданной системой интервалов , в виде конечного автомата без памяти с двоичными входами x₁,…, x_n и выходом y и реализуемой на выходе булевой функцией  вида (14), с воздействием на входах i в виде единичных импульсов x_i(t)=1(a_i, b_i), действующих во временных интервалах (a_i, b_i) соответствующих интервалам, заданным по условию задачи (рис. 3). С учетом явного выражения (14) реализуемой в автомате-модели булевой функции блок-схема этого автомата (см. рис. 3) может быть конкретизирована и представлена как структурная схема, показанная на рис. 4.

Рис. 4.

Шаг 2. Вычисление динамических процессов  на выходе построенного автомата-модели, соответствующих всем возможным значениям индекса k реализуемой автоматом функции , , и всем возможным наборам входных переменных  по k. Это вычисление ведется по формулам теории динамических автоматов с использованием метода последовательных подстановок [4]:

Здесь  — логические определители (ЛО) ранга r, составленные из моментов a_i, изменений сигнала 0 → 1 и моментов b_i изменений сигнала 1 → 0, во входных воздействиях автомата модели:

                            (15)

раскрываемые по формуле (34) [1], а  — сложные ЛО (т.е. ЛО от ЛО) ранга r.

                                (16)

раскрываемые по той же формуле.

Шаг З. Интерпретация процессов , на выходе автомата-модели как маркированных спектральных функций , с соответствующими значениями индекса k и наборами переменных  по k. Каждая функция  есть функция одной переменной x, отмечающая своими единичными значениями те области  оси x, где пересекается ровно k конкретных интервалов из n заданных интервалов , а именно . Таким образом, при решении задачи 2 для ЛО  в соответствии с (16), вычисляемых по формуле (34) [1] и при конкретизации ЛО, согласно (15), получим: при k=1

При k=2

при k=3

……………………………………………………..

при заданном k

♦ 8. Теперь рассмотрим задачи анализа изображений в двумерном пространстве, т.е. на плоскости. Задачи 1, 2 в этом случае формулируются следующим образом. На плоскости в декартовой системе координат (x, y) задано изображение Р в виде совокупности n плоских объектов — прямоугольников со сторонами, параллельными осям координата x, y (рис. 5). Каждый i-й прямоугольник задается четырьмя параметрами (a_i, b_i, c_i, d_i), где [a_i, b_i] — интервал, являющийся проекцией прямоугольника на ось x; [c_i, d_i] — интервал, являющийся его проекцией на ось y. Прямоугольники, в соответствии с их заданными границами, могут взаимодействовать друг с другом, образуя различные пересечения.

Рис. 5.

В итоге изображение Р, согласно (1), распадается на изображения: P0 области  на плоскости, не содержащее ни одного прямоугольника; Р₁, в области , содержащее только одиночные, не пересекающиеся с другими прямоугольники (любые); Р₂ в области , содержащее только попарно пересекающиеся прямоугольники (любые); ... Р_n в области , содержащее только пересечение всех n прямоугольников. Задача 1 состоит в нахождении областей , и, на плоскости, содержащих изображения , в виде пересечения любого фиксированного числа k неконкретизированных (т.е. любых) прямоугольников. Изображения Р_k можно разбить в соответствии с (13) на изображения P_k(i_i,..., i_k) возможных конкретных комбинаций (i_i,..., i_k) к пересекающихся прямоугольников. Тогда задача 2 сводится к нахождению областей , и, на плоскости, содержащей изображения , в виде пересечения k конкретных прямоугольников i_i,..., i_k.

Для решения обеих задач применим метод сечений. Проведем некоторое число сечений изображения (см. рис. 5) прямыми, параллельными одной из осей, например оси х. Каждое такое сечение j вдоль соответствующей прямой x_j содержит полную информацию о характере изображения вдоль этой прямой, конкретно о прямоугольниках  (и их взаимодействии между собой), которые пересекаются с этой прямой, и о пустых областях между прямоугольниками. Эта информация представляется совокупностью всех интервалов [a_i, b_i] — проекций на ось x всех пересекаемых прямой x_j прямоугольников i. Например, на рис. 5 сечение у пересекает прямоугольники 1 и 2, которые не взаимодействуют между собой (не пересекаются), поэтому вся информация об этих прямоугольниках, содержащаяся в данном сечении, — это пара непересекающихся интервалов на оси x: интервал [a₁, b₁] — проекция на ось x прямоугольника 1 и интервал [a₂, b₂] — проекция на ось x прямоугольника 2. Аналогично сечение j - 1 пересекает прямоугольники 1, 2, 3, причем 2 и 3 взаимодействуют (пересекаются); вся информация об этих прямоугольниках в данном сечении — три интервала на оси x: изолированный [a₁, b₁] — проекция прямоугольника 1 и пара пересекающихся [a₂, b₂] и [a₃, b₃] - проекции пересекающихся прямоугольников 2, 3. Далее, сечение j+2 не пересекается ни с одним прямоугольником и поэтому содержит информацию только о пустых областях, не заполненных прямоугольниками, и т.д.

Выделим некоторое сечение j плоского изображения, проведенное вдоль прямой x_j (см. рис. 5). Так как это сечение есть одномерное изображение, его анализ можно выполнить методами, изложенными в пп. 6, 7. В результате получим обыкновенный одномерный спектр плоского изображения Р вдоль секущей прямой x_j.

где f_k(x_j) — k-я обыкновенная спектральная функция изображения Р вдоль прямой х_j принимающая значение 1 в той области  прямой x_j, где есть проекция пересечения Р_k ровно k прямоугольников (любых) и 0 в других областях. Аналогично получим маркированный одномерный спектр плоского изображения Р вдоль секущей прямой x_j

где  - k-я маркированная одномерная спектральная функция изображения Р вдоль прямой x_j, принимающая значение 1 в той области  прямой x_j, где есть проекция пересечения P_k(i_i,..., i_k) ровно k конкретных прямоугольников (i₁-го,..., i_k-го) и значение 0 в других областях. Объединив одномерные спектры вдоль всех секущих прямых х_j получим соответствующие полные двумерные спектры:

                                                                 (17)

                                                               (18)

Вычислив по формуле (17) обыкновенный спектр f(x, y) плоского изображения Р, найдем тем самым решение задачи 1. Аналогично, вычислив по формуле (18) маркированный спектр G(x, у) изображения Р, найдем решение задачи 2. Заметим, что в общем случае формулы (17), (18) и получаемые по ним решения задач 1, 2 являются приближенными, так как при большом расстоянии между секущими прямыми x_j, часть информации о двумерных изображениях при объединении их одномерных составляющих теряется. Чтобы этого не произошло и решение было точным, достаточно провести по одной секущей на каждом участке, на котором изображение неизменно. Такие участки расположены между соседними точками появления новых или исчезновения старых прямоугольников, т.е. точками с ординатами

где  — упорядоченные по возрастанию ординаты с₁..., с_n, d₁,,..., d_n горизонтальных границ всех n прямоугольников изображения.

Отсюда следует, что для получения точного решения задач 1 и 2 достаточно провести не более М=2_n+1 секущих прямых.

♦ 9. Задачи 1 и 2 анализа изображения в трехмерном пространстве формулируются и решаются аналогично соответствующим плоским задачам. При этом за объекты в трехмерном изображении принимают прямые параллелепипеды со сторонами, параллельными осям координат x, у, z. Решение задач получаем методом сечения, в качестве секущих выбираем плоскости, параллельные какой-либо одной координатной плоскости: x—у, x—z или у—z. В результате трехмерная задача сводится к набору соответствующих плоских задач, решаемых по методике, которая приведена в п. 8, и затем объединяемых по формулам типа (17), (18), что дает решение исходной задачи. Аналогично, т.е. понижением размерности пространства с помощью метода сечений, решаются задачи 1 и 2 анализа изображения в пространствах произвольной размерности N.

* * *

Представленные задачи анализа изображении в пространствах различной размерности, эффективно решаемые с помощью автоматного моделирования в сочетании с аппаратом НЛ, свидетельствуют о пользе применения данного метода при решении многих других задач передачи и переработки информации, таких, как распознавание образов, анализ сцен, синхронизация параллельно работающих объектов и т.д.

Список литературы

1. Левин В.И. Непрерывная логика и ее применение // Информационные технологии, 1997. №1. С. 17—22.

2. Левин В.И. Введение в динамическую теорию конечных автоматов. Рига: Зинатне, 1975. 376 с.

3. Левин В.И. Динамика логических устройств и систем. М. Энергия, 1980. 224 с.

4. Левин В.И. Теория динамических автоматов. Пенза: Изд-во Пен7з. гос. техн. ун-та, 1995. 408 с.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ №8. 1997

ИНТЕЛЛЕКТУАЛЬНЫЕ СИТЕМЫ