Search

Ovaj rad opisuje postupke pretvaranja slike u nizove različitim algoritmima. Isti su zatim komprimirani korištenjem nekih od alata za kompresiju te su uspoređeni dobiveni rezultati. Objašnjeni su algoritmi Hilbertove krivulje, Z krivulje, pretvaranja slike po redovima, stupcima i dijagonali. Za kompresiju su implementirani postupci Zlib, 7zip i Bzip2. Analizirani su i uspoređeni rezultati istraživanja te je opisana najbolja kombinacija algoritma pretvaranja slike u niz i alata kompresije., This thesis describes the process of converting an image into strings using different algorithms. These are then compressed using some compression tools, and the achieved results are compared. Hilbert space-filling curve, Z-order curve, row-wise, column-wise, and diagonal-wise converting image into a string is explained. For compression Zlib, 7zip, and Bzip2 are implemented. The research results were analyzed and compared, and described the best combination of the image-to-string converting algorithm and compression tool.

Modern microprocessors offer a rich memory hierarchy including various levels of cache and registers. Some of these memories (like main memory, L3 cache) are big but slow and shared among all cores. Others (registers, L1 cache) are fast and exclusively assigned to a single core but small. Only if the data accesses have a high locality, we can avoid excessive data transfers between the memory hierarchy. In this paper we consider fundamental algorithms like matrix multiplication, K-Means, Cholesky decomposition as well as the algorithm by Floyd and Warshall typically operating in two or three nested loops. We propose to traverse these loops whenever possible not in the canonical order but in an order defined by a space-filling curve. This traversal order dramatically improves data locality over a wide granularity allowing not only to efficiently support a cache of a single, known size (cache conscious) but also a hierarchy of various caches where the effective size available to our algorithms may even be unknown (cache oblivious). We propose a new space-filling curve called Fast Unrestricted (FUR) Hilbert with the following advantages: (1) we overcome the usual limitation to square-like grid sizes where the side-length is a power of 2 or 3. Instead, our approach allows arbitrary loop boundaries for all variables. (2) FUR-Hilbert is non-recursive with a guaranteed constant worst case time complexity per loop iteration (in contrast to O(log(grid-size)) for previous methods). (3) Our non-recursive approach makes the application of our cache-oblivious loops in any host algorithm as easy as conventional loops and facilitates automatic optimization by the compiler. (4) We demonstrate that crucial algorithms like Cholesky decomposition as well as the algorithm by Floyd and Warshall by can be efficiently supported. (5) Extensive experiments on runtime efficiency, cache usage and energy consumption demonstrate the profit of our approach. We believe that future compilers could translate nested loops into cache-oblivious loops either fully automatic or by a user-guided analysis of the data dependency.

Over the past few years, Deep learning (DL) has revolutionized the field of data analysis. Not only are the algorithmic paradigms changed, but also the performance in various classification and prediction tasks has been significantly improved with respect to the state-of-the-art, especially in the area of computer vision. The progress made in computer vision has produced a spillover in many other domains, such as biomedical engineering. Some recent works are directed towards surface electromyography (sEMG) based hand gesture recognition, often addressed as an image classification problem and solved using tools such as Convolutional Neural Networks (CNN). This paper extends our previous work on the application of the Hilbert space-filling curve for the generation of image representations from multi-electrode sEMG signals, by investigating how the Hilbert curve compares to the Peano- and Z-order space-filling curves. The proposed space-filling mapping methods are evaluated on a variety of network architectures and in some cases yield a classification improvement of at least 3%, when used to structure the inputs before feeding them into the original network architectures.

Although many fast methods exist for constructing a k NN-graph for low-dimensional data, it is still an open question how to do it efficiently for high-dimensional data. We present a new method to construct an approximate k NN-graph for medium- to high-dimensional data. Our method uses one-dimensional mapping with a Z-order curve to construct an initial graph and then continues to improve this using neighborhood propagation. Experiments show that the method is faster than the compared methods with five different benchmark datasets, the dimensionality of which ranges from 14 to 784. Compared to a brute-force approach, the method provides a speedup between 12.7:1 and 414.2:1 depending on the dataset. We also show that errors in the approximate k NN-graph originate more likely from outlier points; and, it can be detected during runtime, which points are likely to have errors in their neighbors.

With increasing demands of virtual reality (VR) applications, efficient VR rendering techniques are becoming essential. Because VR stereo rendering has increased computational costs to separately render views for the left and right eyes, to reduce the rendering cost in VR applications, we present a novel traversal order for tile-based mobile GPU architectures: Z 2 traversal order. In tile-based mobile GPU architectures, a tile traversal order that maximizes spatial locality can increase GPU cache efficiency. For VR applications, our approach improves upon the traditional Z order curve. We render corresponding screen tiles in left and right views in turn, or simultaneously, and as a result, we can exploit spatial adjacency of the two tiles. To evaluate our approach, we conducted a trace-driven hardware simulation using Mesa and a hardware simulator. Our experimental results show that Z 2 traversal order can reduce external memory bandwidth requirements and increase rendering performance.

With the pervasiveness of location-based services (LBS), spatial data processing has received considerable attention in the research of database system management. Among various spatial query techniques, index structures play a key role in data access and query processing. However, existing spatial index structures (e.g., R-Tree) mainly focus on partitioning data space or data objects. In this paper, we explore the potential to construct the spatial index structure by learning the distribution of the data. We design a new data-driven spatial index structure, namely learned Z-order Model (ZM) index, which combines the Z-order space filling curve and the staged learning model. Experimental results on both real and synthetic datasets show that our learned index significantly reduces the memory cost and performs more efficiently than R-Tree in most scenarios.

Image encryption is an important field in multimedia security. This paper proposes a new encryption technique for gray scale images using Logistic map and Z-order curve. The key stream generated for this algorithm not only depends on the chaotic map but the original image. In this technique the original image is scrambled using Z-order curve. Then this scrambled image is encrypted using the random matrix generated using the logistic map. Experimental results and security analysis shows that the proposed method has high security and can resist various types of attacks.

BayeSys is an MCMC-based program that can be used to perform Bayesian model comparison for problems with atomic models. To sample distributions with more than one parameter, BayeSys uses the Hilbert curve to index the multidimensional parameter space using one very large integer. While the Hilbert curve maintains locality well, computations to translate back and forth between parameter coordinates and Hilbert curve indexes are time-consuming. The Z-order curve is an alternative SFC with faster transformation algorithms. This work presents an efficient bitmask-based algorithm for performing the Z-order curve transformations for an arbitrary number of parameter space dimensions and integer bit-lengths. We compare results for an exponential decay separation problem evaluated using BayeSys with both the Hilbert and Z-order curves. We demonstrate that no appreciable precision penalty is incurred by using the Z-order curve, and there is a significant increase in time efficiency.

We revisit the generation of balanced octrees for adaptive mesh refinement (AMR) of Cartesian domains with immersed complex geometries. In a recent short note [Hasbestan and Senocak, J. Comput. Phys. vol. 351:473-477 (2017)], we showed that the data-locality of the Z-order curve in hashed linear octree generation methods may not be perfect because of potential collisions in the hash table. Building on that observation, we propose a binarized octree generation method that complies with the Z-order curve exactly. Similar to a hashed linear octree generation method, we use Morton encoding to index the nodes of an octree, but use a red-black tree in place of the hash table. Red-black tree is a special kind of a binary tree, which we use for insertion and deletion of elements during mesh adaptation. By strictly working with the bitwise representation of the octree, we remove computer hardware limitations on the depth of adaptation on a single processor. Additionally, we introduce a geometry encoding technique for rapidly tagging the solid geometry for refinement. Our results for several geometries with different levels of adaptations show that the binarized octree generation outperforms the linear octree generation in terms of runtime performance at the expense of only a slight increase in memory usage. We provide the current AMR capability as open-source software., submitted to Journal of Computational Physics

We propose an extension to the Morton codes used for spatial sorting of scene primitives. The extended Morton codes increase the coherency of the clusters resulting from the object sorting and work better for non-uniform distribution of scene primitives. In particular, our codes are enhanced by encoding the size of the objects, applying adaptive ordering of the code bits, and using variable bit counts for different dimensions. We use these codes for constructing Bounding Volume Hierarchies (BVH) and show that the extended Morton code leads to higher quality BVH, particularly for the fastest available BVH build algorithms that heavily rely on spatial coherence of Morton code sorting. In turn, our method allows to achieve up to 54% improvement in the BVH quality especially for scenes with a non-uniform spatial extent and varying object sizes. Our method is easy to implement into any Morton code based build algorithm as it involves only a modification of the Morton code computation step.

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R2) or the skip octree (for point data in Rd, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined “box”-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.

We present a new type of search trees, called Skip trees, which are a generalization of Skip lists. To be precise, there is a one-to-one mapping between the two data types which commutes with the sequential update algorithms. A Skip list is a data structure used to manage data bases which stores values in a sorted way and in which it is insured that the form of the Skip list is independent of the order of updates by using randomization techniques. Skip trees inherit all the proeprties of Skip lists, including the time bounds of sequential algorithms. The algorithmic improvement of the Skip tree type is that a concurrent algorithm on the fly approach can be designed. Among other advantages, this algorithm is more compressive than the one designed by Pugh for Skip lists and accepts a higher degree of concurrence because it is based an a set of local updates. From a practical point of view, although the Skip list should be in the main memory, Skip trees can be registered into a secondary or external storage. Therefore we analyse the ability, of Skip trees to manage data bases in comparison with B-trees.

Massive Geo-Spatial image data play an increasing important role in mapping, resource and environmental research recently, usually it is stored on external storage for its massive data volume within some image files or spatial database, where image storage organization is still a major bottleneck of range query performance. In contrast to the one-dimensional data, the multi-dimensional data such as Geo-spatial image is far more complex, since there is no obvious storage method that serves all purposes. The image data blocks are stored as separate documents on external storage. Due to the external hard disk storage facility is one-dimensional, and the spatial order of image blocks has a direct impact on the performance of range queries. Several Space Filling Curves (SFC) have been proposed, and the most prominent ones include the Z-order (also known as Morton encoding), the Gray code and Hilbert's curve. In fact the multidimensional interval in range queries can be transformed into several one-dimensional intervals. The preserving spatial proximity in SFC help the image blocks keep possible spatial proximity if it is stored according to SFC. Our previous storage experiment has shown that node sequencing distance in curve for each two spatial adjacent nodes is essential for range query performance, especially for distributed system. In the analysis of Hilbert's curve, we find that Hilbert's curve has high frequency distribution of short sequencing distance in curve for each two spatial adjacent nodes, it is very conducive to efficient regional access, while there exists some super large sequencing distance for spatial adjacent nodes, and those nodes leads to Hilbert curve's average adjacent node distance is larger than ordinary sequence and Z-line order. According to the above experiment, we present a novel geo-spatial storage method based on Hilbert SFC in this paper, and the method use the benefits of Hilbert SFC such as recursive attribute and preserving proximity, but have some adjustments to Hilbert SFC. We stored additional 2(n−1) specific nodes in n-th curve according to our definition, and this method lead to good query performance than existing method. The merit of this method is that it can be used in massive geo-spatial image and has the balance of retrieval efficiency and storage overhead.

In this paper we propose a new architecture based on Z-order curve and kd-tree that can efficiently handle issues related to update messages distribution to interested entities locations in a three-dimensional (3D) virtual environments where locations are described in terms of 3D coordinates. We also aim to minimize the number of routing hops in distribution of update messages, especially when updates are forwarded to a specific range of users/entities in the virtual environment. Our results are promising and show improvements in both of the objectives.

An algorithm for constructing a linear quadtree having a full leaf set from a raster image is investigated. This is based on methods similar to those developed by Lauzon et al. 1 for handling two-dimensional run-encoded quadtrees. It examines pixels in Morton scan order, allowing the largest possible nodes to be generated in order of increasing Morton address. It has been designed for use with disc-based images and quadtrees, and is able to cope with the very large images characteristic of geographic information processing. The algorithm is compared to that of Shaffer and Samet 2 , and is found to be faster and to require less disc space for the output quadtree.

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R^2) or the skip octree (for point data in R^d, with constant d>2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location and approximate range queries., 12 pages, 3 figures. A preliminary version of this paper appeared in the 21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 296-305

Grabmayer, Endrullis, Hendriks, Klop, and Moss [C. Grabmayer, J. Endrullis, D. Hendriks, J.W. Klop, and L.S. Moss. Automatic sequences and zipspecifications. In Proceedings of the 2012 27th Annual IEEE/ACM Symposium on Logic in Computer Science, pages 335–344. IEEE Computer Society, 2012] developed a method for defining automatic sequences in terms of ʼzip specificationsʼ and proved that a sequence is automatic [J.-P. Allouche and J. Shallit. Automatic Sequences. Cambridge University Press, 2003] iff it has a zip specification where all zip terms have the same arity. This paper begins by investigating a similar definitional scheme for the higher-dimensional counterpart of automatic sequences, automatic arrays. In the course of establishing the results required for this machinery, we find an isomorphism–closely related to the z-order curve [G.M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. International Business Machines Company, 1966]–between a final coalgebra for arrays and the standard final coalgebra for sequences. This isomorphism preserves automaticity properties: an array is k,l-automatic iff its corresponding sequence is kl-automatic. The former notion of automaticity (k,l-automatic, note the comma) is defined for arrays as in [J.-P. Allouche and J. Shallit. Automatic Sequences. Cambridge University Press, 2003], and the latter notion is the standard notion of automaticity for sequences. It also provides a convenient way to translate between stream zip specifications and array zip specifications.