Wyniki wyszukiwania - Biblioteka Nauki

1

The Practical Efficiency of Convolutions in Pattern Matching Algorithms

100%

Amir A. , Levy A. , Reuveni L.

Fundamenta Informaticae

|

2008

|

tom Vol. 84, nr 1

1-15

EN

Convolutions have proven to be an effective tool in asymptotically efficient pattern matching algorithms. This study attempts to find the type of problems where convolutions are inefficient in practice, and give possible solutions for the complex cases where the convolution method does not seem to aid realistic sized inputs.

2

Finding Patterns In Given Intervals

80%

Crochemore M. , Iliopoulos C. S. , Kubica M. , Rahman M. S. , Waleń T.

Fundamenta Informaticae

|

2010

|

tom Vol. 101, nr 3

173-186

EN

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

3

Morphological operations with subpixel resolution on digital images

80%

Reinoso O. , Sebastian J. M. , Aracil R. , Torres F.

Machine Graphics and Vision

|

2001

|

tom Vol. 10, No. 1

89-102

EN

In many defect inspection systems computer vision pattern matching techniques are applied. These techniques require the use of different morphological operations. In many situations, pattern images generated by classical morphological operations do not allow to detect defects in images. Small defects of pixel size can also be left unnoticed when using such pattern images. The purpose of this paper is to combine classical morphological operations with a linear interpolation process on digital images to generate these pattern images. It is possible to employ structuring elements of any size to carry out morphological operations on continuous signals. However, on gigital images or discrete signals, the size of the structuring element should be greater than pixel size. The approach described in this paper applies classical morphological operations on reconstructed images at subpixel level to generate [pattern images. In such circumstances, we can compare this procedure with the effect produced by the use of structuring elements smaller than pixel size.

4

Particle measurement in scanning electron microscopy images

80%

Cuesta-Frau D. , Hernández-Fenollosa M. A. , Vicedo-Payá J. , Jiménez-López F.

Machine Graphics and Vision

|

2006

|

tom Vol. 15, No. 3/4

321-328

EN

This paper describes the segmentation of nanoparticles of ZnO obtained by mechanical milling. Segmentation of objects in images is a common application of computer vision methods. In contrast to manual segmentation, these techniques are fast, objective, and accurate. We describe in this paper a method based on such techniques aimed at segmenting the particles in a microscopic image of ZnO in order to obtain an approximation of the grain size, and a measure of the homogeneity, in a non-supervised way. The images are obtained using scanning electron microscopy and then preprocessed to enhance the contrast and to reduce the noise. Next, an edge detection algorithm is applied to obtain the boundaries of the particles. Finally, the particles that satisfy a specific criterion are extracted and measured, and their measure is taken as an approximation of the particle size.

5

Data types and operations for striated toolmark identyfication

80%

Luchowski L. , Philipp M.

Archiwum Informatyki Teoretycznej i Stosowanej

|

1998

|

tom T. 10, z. 1-2

45-56

EN

Forensic investigators spend much of their time comparing toolmarks. Their work can benefit significantly from computer systems which will screen large numbers of toolmarks and identify potential matches for final confirmation by the human expert. This paper presents the data reduction and comparison techniques needed to represent and match striated toolmarks, which are an important class of forensic evidence.

PL

Eksperci kryminalistyki poświęcają wiele czasu na porównywanie śladów narzędzi. Znaczną pomocą w ich pracy mogą być systemy komputerowe, przeglądające duże zbiory śladów i wyszukujące potencjalne podobieństwa. Ostateczne potwierdzenie zgodności dwóch śladów pozostanie przy tym w gestii eksperta -- człowieka. Ważną klasę śladów narzędzi stanowią ślady prążkowe. Artykuł opisuje techniki redukcji i porównywania danych niezbędnych do reprezentacji i pasowania takich śladów.

6

Estimating a vascular network growth using random graphs

80%

Cha S. H. , Gargano M. L. , Chang S. , Quintas L. V. , Wahl E. M.

Machine Graphics and Vision

|

2008

|

tom Vol. 17, No. 1/2

91-103

EN

Vascular networks develop by way of angiogenesis, a growth process that involves the biological mechanisms of vessel sprouting (budding) and splitting (intussusception). Graph theory is excellently suited to model vascular networks and to analyze their properties (invariants). In particular, a random graph process model can simulate the development of a vascular network that has been modeled using graph theory. The renal glomerulus is one example of such a vascular network. Here the correlation between the invariants of this vascular network modeled as a graph and the mechanisms of the network growth using a random graph process are studied. It is proposed that the relative frequencies of sprouting and splitting during the growth of a given renal glomerulus can be estimated by the invariants (root distance, radius, and diameter) of the graph representing the renal glomerulus network. Experimental evidence has been given to support this conjecture.

7

The Weighted Suffix Tree: An Efficient Data Structure for Handling Molecular Weighted Sequences and its Applications

70%

Iliopoulos C. S. , Makris C. , Panagis J. , Perdikuri K. , Theodoridis E. , Tsakalidis A.

Fundamenta Informaticae

|

2006

|

tom Vol. 71, nr 2,3

259-277

EN

In this paper we introduce the Weighted Suffix Tree, an efficient data structure for computing string regularities in weighted sequences of molecular data. Molecular Weighted Sequences can model important biological processes such as the DNA Assembly Process or the DNA-Protein Binding Process. Thus pattern matching or identification of repeated patterns, in biological weighted sequences is a very important procedure in the translation of gene expression and regulation. We present time and space efficient algorithms for constructing the weighted suffix tree and some applications of the proposed data structure to problems taken from the Molecular Biology area such as pattern matching, repeats discovery, discovery of the longest common subsequence of two weighted sequences and computation of covers.

8

Determination of the Optimal Threshold Value and Number of Keypoints in Scale Invariant Feature Transform-based Copy-Move Forgery Detection

70%

Isnanto R. R. , Zahra A. A. , Santoso I. , Lubis M. S.

International Journal of Electronics and Telecommunications

|

2020

|

tom Vol. 66, No. 3

561--569

EN

The copy-move forgery detection (CMFD) begins with the preprocessing until the image is ready to process. Then, the image features are extracted using a feature-transform-based extraction called the scale-invariant feature transform (SIFT). The last step is features matching using Generalized 2 Nearest-Neighbor (G2NN) method with threshold values variation. The problem is what is the optimal threshold value and number of keypoints so that copy-move detection has the highest accuracy. The optimal threshold value and number of keypoints had determined so that the detection n has the highest accuracy. The research was carried out on images without noise and with Gaussian noise.

9

Comparison of methods for initializing EM algorithm for estimation of parameters of gaussian, multi-component, heteroscedastic mixture models

60%

Sokół R. , Polański A.

Studia Informatica

|

2013

|

tom Vol. 34, nr 1

49--73

EN

A basic approach to estimation of mixture model parameters is by using expectation maximization (EM) algorithm for maximizing the likelihood function. However, it is essential to provide the algorithm with proper initial conditions, as it is highly dependent on the first estimation (“guess”) of parameters of a mixture. This paper presents several different initial condition estimation methods, which may be used as a first step in the EM parameter estimation procedure. We present comparisons of different initialization methods for heteroscedastic, multi-component Gaussian mixtures.

PL

Algorytm EM (ang. expectation-maximization) jest szeroko stosowanym rozwiązaniem problemu estymacji parametrów mieszanin rozkładów prawdopodobieństwa poprzez maksymalizację wiarygodności. Istotne znaczenie dla działania algorytmu mają parametry początkowe, stanowiące pierwsze przybliżenie badanej mieszaniny. Publikacja przybliża kilka metod wyznaczania warunku początkowego dla iteracji algorytmu EM oraz porównuje ich skuteczność dla przypadku heteroscedastycznych, wieloskładnikowych mieszanin rozkładów normalnych.

10

Determination of the Optimal Threshold Value and Number of Keypoints in Scale Invariant Feature Transform-based Copy-Move Forgery Detection

60%

Isnanto, R. Rizal , Zahra A. A. , Santoso I. , Lubis M. S. , Isnanto, R. Rizal , Zahra A. A. , Santoso I. , Lubis M. S.

|

11

Self-Indexed Grammar-Based Compression

60%

Claude F. , Navarro G.

Fundamenta Informaticae

|

2011

|

tom Vol. 111, nr 3

313-337

EN

Self-indexes aim at representing text collections in a compressed format that allows extracting arbitrary portions and also offers indexed searching on the collection. Current self-indexes are unable of fully exploiting the redundancy of highly repetitive text collections that arise in several applications. Grammar-based compression is well suited to exploit such repetitiveness. We introduce the first grammar-based self-index. It builds on Straight-Line Programs (SLPs), a rather general kind of context-free grammars. If an SLP of n rules represents a text T[1, u], then an SLP-compressed representation of T requires 2n log2 n bits. For that same SLP, our self-index takes O(n log n) + n log2 u bits. It extracts any text substring of length m in time O((m+ h) log n), and finds occ occurrences of a pattern string of length m in time O((m(m + h) + h occ) log n), where h is the height of the parse tree of the SLP. No previous grammar representation had achieved o(n) search time. As byproducts we introduce (i) a representation of SLPs that takes 2n log2 n(1+o(1)) bits and efficiently supports more operations than a plain array of rules; (ii) a representation for binary relations with labels supporting various extended queries; (iii) a generalization of our self-index to grammar compressors that reduce T to a sequence of terminals and nonterminals, such as Re-Pair and LZ78.

12

Proces uczenia i rozpoznawania wzorców na przykładzie systemu śledzenia ruchów gałki ocznej

60%

Murawski K. , Żorski W.

Biuletyn Instytutu Automatyki i Robotyki

|

2012

|

tom R. 18, nr 33

17-28

PL

Przedstawiono metodę uczenia i rozpoznawania wzorców w systemie śledzenia ruchów gałki ocznej działającym w czasie rzeczywistym. Podstawowym zagadnieniem jest problem uczenia wzorców, który realizowany jest w oparciu o dynamicznie zarządzany zbiór wzorców. Zbiór wzorców jest adaptacyjny i w razie potrzeby nowy wzorzec może zostać do niego dodany, aby następnie ewoluować w procesie dobierania wzorców do obiektów. Jako metodę dopasowywania wzorców do obiektów zastosowano transformatę Hougha dla wzorców nieregularnych. W celu zagwarantowania wydajności proces dopasowywania wzorców jest realizowany na wstępnie zawężonym fragmencie obrazu wejściowego.

EN

This paper presents a method of patterns learning and matching in a real-time computer vision system designed for eye tracking. The main issue is the problem of patterns learning that requires creation of a set of patterns with some kind of dynamic management. The set of patterns is adaptive in that way that a new pattern can be added to the set and next undergoes an evolution during the process of matching. The Hough transform for irregular patterns play the role of the matching method. In order to guarantee the performance the process of patterns matching is carried out on a preliminary selected narrow fragment of the input image.

13

Hirschberg's algorithm for approximate matching

51%

Drozdek A.

Computer Science

|

2002

|

tom Vol. 4

91-100

EN

The Hirschberg algorithm was devised to solve the longest common subsequence problem. The paper discusses the way of adopting the algorithm to solve the string matching problem in linear space to determine edit distance for two strings and their alignment.

PL

Algorytm Hirschberga został podany w celu rozwiązania problemu najdłuższego wspólnego podciągu. Niniejszy artykuł prezentuje sposób zaadoptowania tego algorytmu do rozwiązania przy liniowych wymogach pamięciowych problemu wyszukiwania wzorca w celu znalezienia odległości edycyjnej dwóch tekstów i ich wyrównania.

14

Recognition of unknown scale objects

51%

Żorski W.

Biuletyn Wojskowej Akademii Technicznej

|

2008

|

tom Vol. 57, nr 4

197-207

EN

This paper presents an application of the Hough Transform to the task of identifying objects of unknown scale, e.g. within a scene in a robot vision system. The presented method is based on the Hough Transform for irregular objects, with a parameter space defined by translation, rotation and scaling operations. The high efficiency of the technique allows for poorquality or highly complex images to be analysed. The technique may be used in robot vision systems, identification systems or for image analysis, directly on grey-level images.

PL

Artykuł prezentuje zastosowanie transformaty Hougha do zadań identyfikacji obiektów o nieznanej skali, np. na scenie w systemie widzenia robota. Metoda wykorzystuje transformatę Hougha dla wzorców nieregularnych, z przestrzenią parametrów określoną przez operacje: translacji, obrotu i skalowania. Wysoka sprawność techniki pozwala na analizę obrazów o słabej jakości lub dużej złożoności. Technika może być przykładowo zastosowana w systemach widzenia robotów, do bezpośredniej analizy obrazów pozyskanych w poziomach szarości.

15

Implementacja procesu klasyfikacji danych z użyciem układów reprogramowalnych

51%

Botowicz J.

Pomiary Automatyka Kontrola

|

2008

|

tom R. 54, nr 8

532-535

PL

W artykule opisano różne problemy klasyfikacji danych oraz podano dziedziny w których mają one zastosowanie. Następnie przedstawiono architekturę systemu, w którym będzie możliwe zaimplementowanie podanych wcześniej przez innych autorów, sprawdzonych już algorytmów klasyfikacji danych i wsparcie ich działania poprzez specjalizowane układy sprzętowe. Podano wyniki (w postaci skuteczności klasyfikacji oraz zużycia zasobów) przykładowych modułów sprzętowych. Przedstawiony został również proces tworzenia modułu sprzętowego - od danych wejściowych poprzez wygenerowany kod źródłowy w języku opisu sprzętu, aż po konfigurację układu reprogramowalnego.

EN

In this article various classification problems was described and also their applications was depicted. Afterwards the hardware module architecture was introduced in which there is a possibility to implement previously described mature classification algorithms. The article contains results of testing hardware classification modules (classification precision and hardware resources usage). Finally, the complete process of module generation was presented (from examples of data, through source code in hardware description language to reconfigurable hardware configuration).

16

Wyszukiwanie podciągu w ciągu z zastosowaniem obiektów CRL

51%

Barański M. , Pelikant A.

Zeszyty Naukowe Wyższej Szkoły Informatyki

|

2013

|

tom Vol. 12, Nr 1

91--111

PL

Celem niniejszej pracy jest zaprezentowanie możliwości zastosowania mapowanych na elementy proceduralne Transact SQL klas obiektowych CLR tworzonych na platformie .NET w złożonych algorytmach przetwarzania. Przedstawione zostały podstawy teoretyczne algorytmów dopasowania łańcuchów dla alfabetów skończonych. Dla wprowadzonych alfabetów nieskończonych rozwiązania te nie mogą być w sposób prosty zmodyfikowane, dlatego zaproponowany został algorytm DTW (Dynamic Time Warping), który został oprogramowany z zastosowaniem reguł mapowania do obiektów rozszerzenia proceduralnego SQL. Przedstawiono elementy praktycznej realizacji praktycznej oraz dokonano omówienia wyników eksperymentu numerycznego dopasowującego gesty.

EN

The purpose of this work is to present the possibility to use mapped to the procedural elements Transact SQL CLR object classes that are created on the NET platform in a complex processing algorithms. There are presented theoretical algorithms for matching chains for finite symbol set alphabets. For introduced infinite symbol set alphabets solutions may not be easily modified, so it was proposed the algorithm DTW (Dynamic Time Warping), which was programmed using the mapping rules for procedural extension to SQL. There where shown elements of the practical implementation and the experimental results of matching gestures were discuss.

17

Application and comparison of modified classifiers for human activity recognition

51%

Dohnálek P. , Gajdoš P. , Peterek T. , Snášel V.

Przegląd Elektrotechniczny

|

2013

|

tom R. 89, nr 11

55-58

EN

In this paper, custom modifications of Orthogonal Matching Pursuit and Self Organizing Maps based classification algorithms are used and compared to standard and widely used classification techniques with applications to human activity recognition. Seven algorithms are compared in terms of their accuracy performance. The modifications are described in this paper and shown to perform better than commonly used classifiers. The results indicate that human activities can be successfully and reliably recognized even without data preprocessing.

XX

W artykule opisano klasyczne i rzadziej używane metody klasyfikacji danych używanych do rozpoznawania aktywności człowieka. Po równano szereg algorytmów oraz zmodyfikowano algorytm OMP w celu usunięcia ograniczeń.

18

On Algorithms for Indexing of K-line Diffraction Patterns

51%

Morawiec A. , Bieda M.

Archives of Metallurgy and Materials

|

2005

|

tom Vol. 50, iss. 1

47-56

EN

Thanks to the progress in computer control of electron microscopes and in microscope cameras there is a strong trend towards automatic analysis of electron diraction patterns. Such analysis allowed for creation of fully automatic orientation imaging — an important technique of investigation of polycrystalline materials. Two essential parts of the analysis are the indexing of the patterns and the determination of orientations. We are particularly concerned with systems using transmission electron microscopy (TEM) and Kikuchi patterns; with small solid angle covered by these patterns, indexing is a challenging problem. The indexing procedures are expected to be fast and reliable even in the presence of experimental errors in geometric parameters of the patterns. The first step towards optimal indexing is to formalize the problem. It is shown that indexing can be reduced to matching two sets of points: “Two point sets G and H are given. Determine a rotation carrying the largest subset of G to a position approximating a subset of H”. Some new algorithms solving this problem are proposed. They are based on the generalized Hough transform with the rotation space as the parameter space. In the simplest case, a pair of points - one point from each set — contributes to rotations along a curve in the rotation space. After contributions are made by all pairs, the cell in the rotation space which received the largest number of contributions is considered to represent the orientation of the crystallite. Once the orientation is known, one can easily assign Miller indices to reflections.

PL

Dzięki postępowi w komputerowym sterowaniu mikroskopami elektronowymi i unowocześnieniu kamer do tych mikroskopów istnieje silna tendencja do rozwijania automatycznej analizy elektronowych obrazów dyfrakcyjnych. Taka analiza pozwala na tworzenie w pełni automatycznych map orientacji — ważnej techniki badania materiałów polikrystalicznych. Dwiema istotnymi kwestiami w tej analizie jest indeksowanie obrazów dyfrakcyjnych i wyznaczanie orientacji. Szczególnym wyzwaniem jest indeksowanie obrazów dyfrakcyjnych Kikuchi’ego powstałych w transmisyjnym mikroskopie elektronowym. Procedury indeksujące powinny być szybkie i skuteczne nawet w przypadku błędów eksperymentalnych wpływających na parametry geometryczne tych obrazów. Formalne ujęcie problemu jest pierwszym krokiem do zoptymalizowania procedur indeksujących. Pokazano, że problem może zostać sprowadzony do porównania dwóch zbiorów punktów: „Dane sa dwa zbiory GiH. Zadaniem jest wyznaczenie obrotu, który przekształca najwiekszy podzbiór zbioru G w podzbiór zbioru H z pewnym błedem aproksymacji”. Zaproponowano nowe algorytmy rozwiązujące ten problem. Bazują one na uogólnionej transformacie Hougha z przestrzenią obrotów jako przestrzenia parametrów. W najprostszym przpadku, para punktów — po jednym z każdego zbioru — głosuje na obroty położone wzdłuż krzywej w przestrzeni obrotów. Po tym jak każda para „oddała” swój głos, przyjmuje sie, ze komórka w przestrzeni obrotów, która uzyskała najwiekszą liczbę głosów reprezentuje orientacje krystalitu. Jeżeli znana jest orientacja łatwo można przyporządkować refleksom indeksy Millera .

19

Wyszukiwanie przybliżone sekwencji DNA z użyciem indeksu FM

51%

Kawulok J.

Studia Informatica

|

2012

|

tom Vol. 33, nr 2A

493-506

PL

Artykuł opisuje nowy algorytm wyszukiwania przybliżonego zadanych fragmentów DNA w długich sekwencjach. Zgodnie z zaproponowanym podejściem poszukiwany fragment jest dzielony na nakładające się słowa, których pozycje w badanej sekwencji są wyznaczane przez użycie indeksu FM. Wykorzystując tak otrzymaną listę pozycji słów w sekwencji, poszukuje się połączeń spełniających założenie o dopuszczalnej maksymalnej liczbie różnic. Stworzony algorytm został poddany walidacji eksperymentalnej, której wyniki przedstawiono w artykule.

EN

This paper presents an algorithm for searching fragments of sequences in previously prepared DNA bases. The pattern is divided into words which overlap themselves. Their positions are found using FM-index, and they are used to search connections with each other under the assumption about a permissible maximum number of distinction.

20

Pattern matching algorithms in preparation of a 3D heart models

51%

Bernady G. , Gackowski A. , Kempny A. , Piórkowski A.

Journal of Medical Informatics & Technologies

|

2011

|

tom Vol. 17

313--319

EN

The CT2TEE is an online transoesophageal echocardiography (TEE) simulator [2] developed on the AGH University of Science and Technology. As a basis for the displayed real-time simulation it uses 3D models created by hand from the CT images. The aim of this paper is to present algorithms developed specifically for efficient editing and preparation of three-dimensional models of the heart for use in the CT2TEE simulator. A detailed description of proposed algorithms, their advantages and limitations, is provided.