Все выпуски

text-align: justify;">Работа посвящена использованию регулярных выражений при распознавании рукописных математических текстов. Основная проблема в распознавании рукописных математических формул состоит в том, что эти тексты, как правило, состоят из большого числа маленьких фрагментов, расположенных в соответствии с некоторыми строгими правилами. Несмотря на то, что формальное определение синтаксиса математических текстов может вовлекать бесконтекстные грамматики и даже более сложные конструкции, на практике часто для успешного распознавания достаточно определения математического языка на базе регулярных выражений. Поскольку некоторые конструкции в математических текстах могут встречаться чаще других, мы вводим понятие взвешенного регулярного выражения. Веса в нём определяют предпочтение одних конструкций перед другими. В работе вводится математический аппарат для использования таких выражений при распознавании. В частности, доказываются теоремы о пересечении взвешенных множеств, задаваемых такими регулярными выражениями. Даются некоторые оценки сложности работы алгоритмов использующих такие регулярные выражения для распознавания.

text-align: justify;">The work is devoted to use of regular expressions at recognition of hand-written mathematic texts. The main problem in handwritten mathematical formula recognition is that these texts mainly consist of a large number of small fragments, arranged in accordance with some strict rules. Despite the fact that formal definition of syntax of mathematic texts can involve context-free grammars and even more complicated constructions, it frequently suffices definition of mathematical language on the base of regular expressions for successful recognition. Since some constructions can occur in mathematic texts frequently than other, we introduce the concept of the weighed regular expression. The weights determine preference of some constructions before other ones. In the work, mathematical tools for use of such expressions at recognition is introduced. Theorems about intersection of weighed sets defined by such regular expressions are proved. Some estimations are given to complexity of algorithms work using such regular expressions for recognition.

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

text-align: justify;">In this paper, it's proposed to use the extension $\mathcal{ALC}(GI)$ of description logic $\mathcal{ALC}$ for the formal description and structural analysis of images. Concepts and the roles of $\mathcal{ALC}(GI)$ are interpreted on an image graph and its subgraphs. The model of image in the form of multi-layered attribute graph is presented. It contains a layer of color segments, a layer of boundaries and a layer of skeletons. Each layer is a planar graph, layers are linked by means of “ancestor-descendant” relations. The transition from the pixel representation of an image to the graph one allows us to increase the effectiveness of image analysis. Examples of terminological axioms that define structural elements of an image and letters composed of them, as well as the results of an experiment of recognizing letters in a cursive handwritten text are presented.

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

text-align: justify;">The article deals with the problem of recognizing handwritten texts from raster images. A method to recover the sequence of records in a handwritten text is described, that will reduce the task of offline-recognition to the task of online-recognition. The method is based on finding the Eulerian path with the minimum weight in the handwritten symbol skeleton graph. Some numerical characteristics are considered as weights, they show the complexity of the transition from one edge to another through a common vertex. A table of all possible combinations of pairs is constructed for this purpose. If there isn't Eulerian path in the original graph, the path is searched with the minimum number of breaks. The definition of a virtual edge is introduced, the transition on it is the formation of a gap in the path. It is necessary to split edges into pairs and calculate the weights at the vertices of odd multiplicity. The pathfinding algorithm in the skeleton of a symbol is considered, it is based on the Fleury's algorithm of searching Eulerian path.