Štruktúra a jej využite pre rozpoznávanie

Publikácie

Autori Názov
M. Bresler, D. Průša, V. Hlaváč Simultaneous Segmentation and Recognition of Graphical Symbols using a Composite Descriptor
In Walter G. Kropatsch, Fuensanta Torres, Geetha Ramachandran, editors, CVWW 2013: Proceedings of the 18th Computer Vision Winter Workshop, 2013, 16-23. ISBN 978-3-200-02943-9.
Abstrakt: This work deals with recognition of hand-drawn graphical symbols in diagrams. We present two contributions. First, we designed a new composite descriptor expressing overall appearance of symbols. We achieved rather favorable accuracy in classification of segmented symbols on benchmark databases, which is 98.93% for a database of flow charts, 98.33% for a database of crisis management icons, and 92.94% for a database of digits. Second, we used the descriptor in the task of simultaneous segmentation and recognition of graphical symbols. Our method creates symbol candidates by grouping spatially close strokes. Symbol candidates are classified by a multiclass SVM classifier learned on a dataset with negative examples. Thus, some portion of the candidates is filtered out. The joint segmentation and classification was tested on diagrams from the flowchart database. We were able to find 91.85% of symbols while generating 8.8 times more symbol candidates than is the number of true symbols per diagram in average.
Odkazy: BibTeX, Fulltext
P. Černo Grammatical Inference of Lambda Confluent Context Rewriting Systems
In Suna Bench, Frank Drewes, Rudolf Freund, Friedrich Otto, editors, Workshop on Non-Classical Models of Automata and Applications (NCMA), books@ocg.at, pages 85-100. Österreichisches Computer Gesellschaft, 2013.
Abstrakt: We introduce a general learning algorithm for inferring various restricted types of context rewriting systems, which are defined as string-rewriting systems extended by contexts. We show that, under certain conditions, it is possible to identify in the limit any target context rewriting system with minimal width of instructions from the set of positive and negative samples. In addition, we show that the learning algorithm works in polynomial time with respect to the size of the set of positive and negative samples when used on lambda-confluent context rewriting systems.
Odkazy: BibTeX, NCMA 2013, Presentation
P. Černo Grammatical Inference of Lambda Confluent Context Rewriting Systems
Submitted to Fundamenta Informaticae, 2014.
Abstrakt: Although a lot of methods have been proposed to learn regular languages, learning more complex language classes is still a challenging task. One attractive approach is to consider non-classical formalisms that provide alternative ways to represent interesting classes of languages and give rise to new promising learning techniques. To this end we use the so-called context rewriting systems, which are defined as string-rewriting systems extended by contexts, and propose a novel learning algorithm for inferring various restricted classes of context rewriting systems. We show that, under certain conditions, it is possible to identify in polynomial time (but not polynomial data) any target $\lambda$-confluent context rewriting system with minimal width of instructions from informant. We discuss the complexity of the learning algorithm, relate the considered language classes to Chomsky hierarchy and finally raise some open questions and further research directions.
Odkazy: Fulltext, Presentation
P. Hoffmann Power of S-kR-RRWW Automata
In Suna Bench, Frank Drewes, Rudolf Freund, Friedrich Otto, editors, Workshop on Non-Classical Models of Automata and Applications (NCMA), books@ocg.at, pages 163-178. Österreichisches Computer Gesellschaft, 2013.
Abstrakt: We study properties of single k-reversible restarting automata. We show that their power lies between GCSL and CSL. We show that their subclasses form an infinite hierarchy of classes of languages with respect to the reversibility level k and we also show that limiting types of allowed rewrites lowers the power of the model. Finally, we study the relation to SLT-R-automata.
Odkazy: BibTeX
P. Hoffmann Power of S-kR-RRWW Automata
Submitted to Fundamenta Informaticae, 2014.
Abstrakt: Single k-reversible restarting automata are a special version of restarting automata which can be effectively learned from samples. We show that their power lies between GCSL and CSL. We show that their subclasses form an infinite hierarchy of classes of languages with respect to the reversibility level k and we also show that limiting types of allowed rewrites lowers the power of the model. Finally, we study their relation to strictly locally testable restarting automata.
Odkazy: Fulltext
F. Mráz, F. Otto Lambda-Confluence Is Undecidable for Clearing Restarting Automata
In Stavros Konstantinidis, editors, CIAA 2013: 18th International Conference on Implementation and Application of Automata, 2013, LNCS 7982, pages 256-267
Abstrakt: Clearing restarting automata are based on contextual rewriting. A word w is accepted by an automaton of this type if there is a computation that reduces the word w to the empty word lambda by a finite sequence of rewritings. Accordingly, the word problem for a clearing restarting automaton can be solved nondeterministically in quadratic time. If, however, the contextual rewritings happen to be lambda-confluent, that is, confluent on the congruence class of the empty word, then the word problem can be solved deterministically in linear time. Here we show that, unfortunately, lambda-confluence is not even recursively enumerable for clearing restarting automata. This follows from the fact that lambda-confluence is not recursively enumerable for finite factor-erasing stringrewriting systems.
Odkazy: BibTeX, DOI
F. Mráz, F. Otto Ordered Restarting Automata for Picture Languages
In Viliam Geffert, Bart Preneel, Branislav Rovan, Július Štuller, AMin Tjoa, editors, SOFSEM 2014: Theory and Practice of Computer Science, 2014, LNCS 8327 , pages 431-442
Abstrakt: We introduce a two-dimensional variant of the restarting automaton with window size three-by-three for processing rectangular pictures. In each rewrite step such an automaton can only replace the symbol in the middle position of its window by a symbol that is smaller with respect to a fixed ordering on the tape alphabet. When restricted to one-dimensional inputs (that is, words) the deterministic variant of these ordered restarting automata only accepts regular languages, while the nondeterministic one can accept some languages that are not evencontext-free. We then concentrate on the deterministic two-dimensional ordered restarting automaton, showing that it is quite expressive as it can simulate the deterministic sgraffito automaton, and we present some closure and non-closure properties for the class of picture languages accepted by these automata.
Odkazy: BibTeX, DOI
I. Mrázová, M. Hrinčár Fast and Reliable Detection of Hockey Players
Procedia Computer Science, Complex Adaptive Systems, 2013, Vol. 20, pages 121–127
Abstrakt: Current popularity of augmented reality (AR) stems from its ability to enhance the perceived environment in realtime with additional information of semantic context, such as sports scores shown on TV during match broadcasting. Its other application areas range from industry and medicine to military, commerce and entertainment. Advanced AR technologies obviously rely on accurate, yet fast enough algorithms for multimedia processing and object recognition. In this paper, we will study the possibility of using convolutional neural networks (CNNs) for real-time detection of hockey players from video streams of broadcasted ice-hockey matches. Supporting experiments performed so far yield sufficient accuracy for this task (above 98.5%), while maintaining reasonable computational demands and acceptable robustness both with regard to noise and minor image transformations like translation, rotation and scaling.
Odkazy: BibTeX, DOI
I. Mrázová, M. Kukačka Image Classification with Growing Neural Networks
IJCTE - International Journal of Computer Theory and Engineering, 2013, Vol. 5, 422-427. ISSN 1793-8201
Abstrakt: Future multi-media technologies are expected to support efficient on-line processing of huge amounts of high-dimensional data without any special pre-processing. In this paper, we will introduce a new model of the so-called Growing Hierarchical Neural Networks (GHNN) applicable to image classification without requiring advanced domain-specific feature extraction techniques. It can be, moreover, supposed that the involved dynamic data-dependent adjustment of both the number and position of the neurons improves generalization. Experimental results obtained so far for two case studies on face and hand-written digit recognition show that local features detected automatically by GHNN-networks impact a transparent and compact representation of the extracted knowledge.
Odkazy: BibTeX, DOI
I. Mrázová, J. Pihera, J. Velemínská Can N-dimensional convolutional neural networks distinguish men and women better than humans do?
The 2013 International Joint Conference on Neural Networks, 2013, 1–8
Abstrakt: Convolutional neural networks (CNN) were able to beat human performance in various areas of 2D image recognition, e.g., in the German Traffic Sign competition run by IJCNN 2011. While the majority of classical image processing techniques is based on carefully pre-selected image features, CNNs are designed to learn local features autonomously. A growing availability of high-dimensional object data, e.g., from medicine or forensic analysis, thus motivated us to develop a new variant of the classical CNN model. The introduced N-dimensional convolutional neural networks (ND-CNN) enhanced with an enforced internal knowledge representation allow to process general N-dimensional object data while supporting adequate interpretation of the found object characteristics. Experimental results obtained so far for gender classification of 3D face scans confirm an extremely strong power of the proposed neural classifier. The developed ND-CNNs significantly outperformed humans (by 33%) while still allowing for a transparent representation of the face features present and detected in the data.
Odkazy: BibTeX, DOI
F. Otto, P. Černo, F. Mráz On the Classes of Languages Accepted by Limited Context Restarting Automata
RAIRO - Theoretical Informatics and Applications, 2014, Vol. eFirst, 1–24. ISSN 1290-385X
Abstrakt: In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the word w is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton families of languages, relating the classes of languages accepted by these automata in particular to the class GCSL of growing context-sensitive languages and to the class CRL of Church–Rosser languages.
Odkazy: BibTeX, DOI
F. Otto, F. Mráz Extended Two-Way Ordered Restarting Automata for Picture Languages
In Adrian-Horia Dediu, Carlos Martín-Vide, José-Luis Sierra-Rodríguez, Bianca Truthe, editors, LATA 2014: Language and Automata Theory and Applications, 2014, LNCS 8370 , pages 541-552
Abstrakt: We introduce a two-dimensional variant of the deterministic restarting automaton for processing rectangular pictures. Our device has a window of size three-by-three, in a rewrite step it can only replace the symbol in the central position of its window by a symbol that is smaller with respect to a fixed ordering on the tape alphabet, and it can only perform (extended) move-right and move-down steps. This automaton is strictly more expressive than the deterministic Sgraffito automaton, but its word problem can still be solved in polynomial time, and when restricted to one-dimensional input, it only accepts the regular languages.
Odkazy: BibTeX, DOI
F. Otto, F. Mráz Lambda-Confluence for Context Rewriting Systems
Submitted to TCS
Abstrakt: Clearing restarting automata and limited context restarting automata are particular types of context rewriting systems. A word w is accepted by such a system if there is a sequence of rewritings that reduces the word w to the empty word lambda, where each rewrite rule is extended by certain context conditions. If each rewrite step is strictly length-reducing, as for example in the case of clearing restarting automata, then the word problem for such a system can be solved nondeterministically in quadratic time. If, in addition, the contextual rewritings happen to be lambda-confluent, that is, confluent on the congruence class of the empty word, then the word problem can be solved deterministically in linear time. Here we show that lambda-confluence is decidable in polynomial time for limited context restarting automata of type R2, but that this property is not even recursively enumerable for clearing restarting automata. The latter follows from the fact that lambda-confluence is not recursively enumerable for finite factor-erasing string-rewriting systems.
M. Plátek, D. Pardubská, M. Lopatková On Complexity of Analysis by Reduction by Restarting Automata
Abstrakt: The paper provides linguistic observations as a motivation for a formal study of analysis by reduction. It concentrates on a study of the whole mechanism through a class of restarting automata with metainstructions using pebbles, and delete and shift operations. Four types of (in)finite sets defined by this automata are considered as linguistically relevant: basic languages on word forms marked with categories, proper languages on unmarked word forms, categorial languages on pure categories, and sets of reductions (reduction languages). A formal part of the paper is based on the relation between descriptional complexity of reductions, and the so called syntactic precedence in languages. The measures we are interested in are those measuring the number of pebbles, the number of deletions, and the number of word order shifts used in a single reduction step. We have obtained unbounded hierarchies for (all four types of) classes of finite languages considered here, as well as for Chomsky's classes of infinite languages. These measures show that the reduction features of Czech are very simple.
D. Průša, F. Mráz, F. Otto Comparing Two-Dimensional One-Marker Automata to Sgraffito Automata
In Stavros Konstantinidis, editors, CIAA 2013 : Conference on Implementation and Application of Automata, 2013, LNCS 7982 , pages 268-279
Abstrakt: We compare two types of automata for accepting picture languages to each other: the two-dimensional one-marker automaton and the sgraffito automaton. On the one hand, it is shown that deterministic sgraffito automata are strictly more powerful than deterministic two-dimensional one-marker automata. On the other hand, nondeterministic two-dimensional one-marker automata accept some picture languages that cannot be accepted by sgraffito automata. However, if nondeterministic two-dimensional one-marker automata were to accept all picture languages that are accepted by (deterministic) sgraffito automata, then the complexity classes NL (nondeterministic logarithmic space) and P (deterministic polynomial time) would coincide. Accordingly, it is likely that the classes of picture languages accepted by these two types of nondeterministic automata are incomparable under inclusion.
Odkazy: BibTeX, DOI
D. Průša, F. Mráz, F. Otto New Results on Deterministic Sgraffito Automata
In Marie-Pierre Béal, Olivier Carton, editors, DLT 2013 : Developments in Language Theory, 2013, LNCS 7907 , pages 409-419
Abstrakt: The deterministic sgraffito automaton is a two-dimensional computing device that allows a clear and simple design of important computations. The family of picture languages it accepts has many nice closure properties, but when restricted to one-row inputs (that is, strings), this family collapses to the class of regular languages. Here we compare the deterministic sgraffito automaton to some other two-dimensional models: the two-dimensional deterministic forgetting automaton, the four-way alternating automaton and the sudoku-deterministically recognizable picture languages. In addition, we prove that deterministic sgraffito automata accept some unary picture languages that are outside the class REC of recognizable picture languages.
Odkazy: BibTeX, DOI

Posledná úprava: Friday, 01/30/15