Все выпуски

Работа посвящена связи параллельных и последовательных вычислений. С одной стороны, рассматривается класс словарных предикатов, основанных на последовательных вычислениях, ограниченных по памяти константами и имеющих полиномиальную временную сложность. С другой стороны, рассматривается класс словарных предикатов, вычислимых на параллельных альтернирующих машинах за логарифмическое время. Доказано совпадение соответствующих классов. Предложено направление использования полученных результатов для взаимного преобразования и сочетания вычислений на молекулярных биоподобных последовательных машинах и параллельных вычислениях на векторно-матричных компьютерах. Предполагаемые области применения: обработка изображений в реальном масштабе времени для задач управления, анализ больших текстов и других больших данных.

В работе предлагается для формального описания и структурного анализа изображений использовать расширение $ \mathcal{ALC}(GI)$ дескрипционной логики $ \mathcal{ALC} $. Концепты и роли логики $ \mathcal{ALC} (GI)$ интерпретируются на графе изображения и его подграфах. Описана модель изображения в виде многослойного атрибутивного графа. Граф изображения содержит слой цветовых сегментов, слой границ, слой скелетонов. Каждый слой представляет собой планарный граф, слои связаны между собой отношениями «предок-потомок». Переход от пиксельного представления изображения к графовому позволяет существенно увеличить эффективность его анализа. Приведены примеры предметных терминологических аксиом, определяющих структурные элементы изображения и составленные из них буквы, а также результаты эксперимента, проведенного на задаче распознавания букв в слитном рукописном тексте.

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

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

Рассматривается задача распознавания рукописных текстов с растровых изображений. Описывается метод восстановления последовательности записи рукописного текста, который позволит свести задачу offline-распознавания к задаче online-распознавания. Метод заключается в поиске эйлерова пути с минимальным весом в графе скелета рукописных символов. В качестве весов рассматриваются некоторые числовые характеристики, отражающие сложность перехода из одного ребра в другое через общую вершину. Для этого строится таблица всевозможных комбинаций пар. При отсутствии в исходном графе эйлерова пути выполняется поиск пути с минимальным числом разрывов. Для разбиения ребер на пары и вычисления весов в вершинах нечетной кратности вводится понятие виртуального ребра, переход по которому означает образование разрыва в пути. Рассматривается алгоритм поиска пути в скелете символа, основанный на алгоритме Флери поиска эйлерова пути.

Рассматриваются задача классификации текстурных изображений и проблема уменьшения пространства признаков. Предлагается редукция задачи многоальтернативной классификации до бинарной одномерной задачи, в которой допустимо использовать байесовский подход c одномерными оценками распределений. Вводится гипотеза о бета-распределении значений признаков для одного класса. Параметры распределения оцениваются методом моментов. Для оценки четырех параметров требуются аналитические выражения и статистические оценки первых четырех моментов этого распределения. После оценки параметров осуществляется проверка гипотезы о распределении по критерию Пирсона. Экспериментально установлено, что модель бета-распределения в большинстве случаев применима к оценке распределений значений признаков. Сделан вывод о необходимости такой проверки для каждой обучающей выборки. В работе также предлагается по результатам оценки степени пересечений оцененных распределений классов оценивать эффективность признака. Рассматривается взаимная корреляция выбранных признаков. Вводится способ оценки информативности признаков, основанный на минимуме средней вероятности ошибки для одного признака и взаимной некоррелированности для системы признаков. На основе алгоритма оценки информативности строится система признаков для каждой пары классов. Формулируется алгоритм классификации, который использует полученные системы признаков и принимает решение на основе оценки плотности моделью бета-распределения на этапе бинарной задачи. Кроме того, cформулированный алгоритм объединяет результаты частных бинарных решений и принимает окончательное решение в задаче классификации.

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