| Authors |
Title |
|
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. |
|
Abstract: 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. |
|
Links: 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. |
|
Abstract: 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. |
|
Links: BibTeX, NCMA 2013, Presentation |
|
P. Černo |
Grammatical Inference of Lambda Confluent Context Rewriting Systems |
|
Submitted to Fundamenta Informaticae, 2014. |
|
Abstract: 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. |
|
Links: 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. |
|
Abstract: 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. |
|
Links: BibTeX |
|
P. Hoffmann |
Power of S-kR-RRWW Automata |
|
Submitted to Fundamenta Informaticae, 2014. |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: BibTeX, DOI |
|
F. Otto, F. Mráz |
Lambda-Confluence for Context Rewriting Systems |
|
Submitted to TCS |
|
Abstract: 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 |
|
Abstract: 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 |
|
Abstract: 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. |
|
Links: 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 |
|
Abstract: 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. |
|
Links: BibTeX, DOI |
Czech 
Slovak 