Abstract Large binary images are used in many modern applications of image processing. For instance, they serve as inputs or target masks for training machine learning (ML) models in computer vision and image segmentation. Storing large binary images in limited memory and loading them repeatedly on demand, which is common in ML, calls for efficient image encoding and decoding mechanisms. In the paper, we propose an encoding scheme for efficient compressed storage of large binary images based on chain codes, and introduce a new single-pass algorithm for fast parallel reconstruction of raster images from the encoded representation. We use three large real-life binary masks to test the efficiency of the proposed method, which were derived from vector layers of single-class objects – a building cadaster, a woody vegetation landscape feature map, and a road network map. We show that the masks encoded by the proposed method require significantly less storage space than standard lossless compression formats. We further compared the proposed method for mask reconstruction from chain codes with a recent state-of-the-art algorithm, and achieved between $$12\%$$ 12 % and $$33\%$$ 33 % faster reconstruction on test data.

The paper introduces a new method to describe the surfaces of voxelised solids. It operates in three stages: a hierarchical linked list of chain code sequences is created first; the linked lists are pruned; and, finally, the content of the data structure is stored. The method uses chain codes from either a three- or nine-symbols alphabet. In the first case, two chain code symbols are needed to access the next face, while, in the second case, this is done by one symbol. The pair of chain codes from the three-symbols alphabet, or the individual symbol from the nine-symbols alphabet are considered as tokens. The sets of tokens are, in both cases, extended by two tokens, indicating the beginning and ending of the list. The method processes solids of any shape, including those containing holes, cavities, or multiple components existing in the same voxel space. Edge-connectivity is permitted. The method was compared against the method proposed by Lemus et al., which is designed for solids without holes. Although supporting a broader set of voxelised solids, the proposed method generates sequences of tokens that are, on average, up to 10% shorter. Since the information entropy of the sequences of tokens produced by the proposed method is also smaller, the obtained sequences are more compressible, as confirmed by applying gzip and bzip2 data compressors.

A new method for encoding a sequence of integers, named Binary Adaptive Sequential Coding with Return to Bias, is proposed in this paper. It extends the compressing pipeline for chain codes’ compression consisting of Burrows Wheeler Transform, Move-To-Front Transform, and Adaptive Arithmetic Coding. We also explain when to include the Zero-Run Transform into the above-mentioned pipeline. The Zero-Run Transform generates a sequence of integers corresponding to the number of zero-runs. This sequence is encoded by Golomb coding, Binary Adaptive Sequential Coding, and the new Binary Adaptive Sequential Coding with Return to Bias. Finally, a comparison is performed with the two state-of-the-art methods. The proposed method achieved similar compression efficiency for the Freeman chain code in eight directions. However, for the chain codes with shorter alphabets (Freeman chain code in four directions, Vertex Chain Code, and Three-OrThogonal chain code), the introduced method outperforms the referenced ones.

We present a framework for multi-objective optimization of fruit tree pruning within a simulated environment, where pruning is performed on a virtual tree model, and its effects on tree growth are observed. The proposed framework uses quantitative measures to express the short-term and long-term effects of pruning, for which potentially conflicting optimization objectives can be defined. The short-term objectives are evaluated on the pruned tree model directly, while the values of long-term objectives are estimated by executing a tree growth simulation. We demonstrate the concept by using a bi-objective case, where the estimated light interceptions of the pruned tree in the current and the next season are used to define separate optimization objectives. We compare the performance of the multi-objective simulated annealing and the NSGA-II method in building the sets of non-dominated pruning solutions. The obtained Pareto front approximations correspond to diverse pruning solutions that balance between optimizing either objective to different extents, which indicates a potential for new applications of the multi-objective pruning optimization concept.

This paper introduces a new lossy approach for compression of cartoon images. The image is firstly partitioned into regions of roughly the same colour. The chain codes are then determined of all regions. The sequence of the obtained chain code symbols is transformed with the Burrows-Wheeler Transform, Move-To-Front transform, and compressed with Run-Length Encoding. In the final step, an arithmetic encoder may be used to compress the obtained binary stream additionally. The proposed algorithm is asymmetric, meaning that the decompression does not reverse all the steps of the compression procedure. The experimental results have shown that the described method produces considerably better compression ratios than JPEG, JPEG2000, WebP, SPIHT, PNG, and two of the algorithms specialised in compression of cartoon images: the algorithm using quad-tree, and RS-LZ algorithm.

In the paper, we present a method for space-efficient representation of geometric tree models, which are provided as skeletons with radii attached to individual branch segments. The proposed approach uses a new differential 3D chain code to encode orientation changes of consecutive branch segments, which allows optimizing chain code generation for increased compressibility while maintaining control over the model reconstruction error. The presented method is the first to encode the complete branching geometry including the branch radii and provides level-of-detail construction directly from the chain code. It is demonstrated that by using interpolative encoding of the resulting tree descriptors and radii sequences, the storage requirements for geometric description of a mixed all-aged forest can be reduced to less than 15 percent of its raw size while preserving the structural fidelity of tree models.

This paper describes the use of graph analysis for spatial networks. The use of community detection algorithms for detecting communities- groups of similar objects within networks of land cover objects to determine the land use is evaluated. Land cover to land use transformation requires some knowledge to merge land cover objects. Community detection algorithms merge objects of the formed spatial network into communities. Community detection algorithms are efficient analysis tool for spatial graphs and can identify land use communities but with different characteristics, although spatial networks with topological relationships between objects can cause some problems.

As the data acquisition capabilities of Earth observation (EO) satellites have been improved substantially in the past few years, large amount of high-resolution satellite images are downlinked continuously to ground stations. Such amount of data increases rapidly beyond the users' capability to access the images' content in reasonable time. Hence, automatic and fast interpretation of a large data volume is a computationally intensive task. Recently, approximate nearest neighbour search has been used for content-based image retrieval in sub-linear time. Kernelized locality sensitive hashing (KLSH) is a well-known approximate method, which has recently shown promising results for fast remote sensing image retrieval. This paper proposes a novel parallelization of KLSH using Graphical Processing Units (GPU), in order to perform fast parallel image retrieval. The proposed method was tested on high-dimensional feature vectors from two satellite-based image datasets, where an average speedup of 20 times was achieved.

ABSTRACT Traversing voxels along a three dimensional (3D) line is one of the most fundamental algorithms for voxel‐based applications. This paper presents a new 6‐connectivity integer algorithm for this task. The proposed algorithm accepts voxels having different sizes in x, y and z directions. To explain the idea of the proposed approach, a 2D algorithm is firstly considered and then extended in 3D. This algorithm is a multi‐step as up to three voxels may be added in one iteration. It accepts both integer and floating‐point input. The new algorithm was compared to other popular voxel traversing algorithms. Counting the number of arithmetic operations showed that the proposed algorithm requires the least amount of operations per traversed voxel. A comparison of spent CPU time using either integer or floating‐point arithmetic confirms that the proposed algorithm is the most efficient. This algorithm is simple, and in compact form which also makes it attractive for hardware implementation.

This paper introduces a new algorithm for constrained Delaunay triangulation, which is built upon sets of points and constraining edges. It has various applications in geographical information system (GIS), for example, iso‐lines triangulation or the triangulation of polygons in land cadastre. The presented algorithm uses a sweep‐line paradigm combined with Lawson's legalisation. An advancing front moves by following the sweep‐line. It separates the triangulated and non‐triangulated regions of interest. Our algorithm simultaneously triangulates points and constraining edges and thus avoids consuming location of those triangles containing constraining edges, as used by other approaches. The implementation of the algorithm is also considerably simplified by introducing two additional artificial points. Experiments show that the presented algorithm is among the fastest constrained Delaunay triangulation algorithms available at the moment.

Abstract Voxel traversing along a line in a uniformly divided voxel space is frequently needed in different applications of computer graphics. The paper presents a new integer one‐pass algorithm for this problem. In 2D, the proposed approach is based on a modification of the well‐known Bresenham algorithm. The algorithm is then extended in 3D where a special case may occur. It is characterized by a simple discriminator. A derivation for this discriminator given in the paper confirms that all calculations can be realized using only integer arithmetic. In this way, the accumulation of rounding errors is completely eliminated, and a robust and compact implementation can be easily achieved. One of the main advantages of the proposed algorithm is that it visits 1–3 voxels during each iteration thus assuring its efficiency. The algorithm has been compared with other algorithms for voxel traversing by measuring spent CPU time. For comparison, Cleary & Wyvill's, Amanatides & Woo's, and Code‐based algorithm have been used. The proposed algorithm is faster than the referenced algorithms.

Site visibility analysis is an important research topic with many applications in Geographical Information Systems. This paper introduces a new paradigm in terrain guarding, called k-guarding. K-guarding is a generalization of the classic guarding problem where, instead of only one guard, each surface patch is guarded by at least k guards. Afterwards, two optimization problems based on k-guarding are defined: an optimum k-guarding, and a constrained k-guarding. There are three heuristic approaches—k-greedy add, k-stingy drop, and k-reverse greedy—that are proposed as a solution to the above-mentioned optimization problems. The first two are known approaches adapted to k-guarding, while k-reverse greedy is a new, original heuristic. The heuristics are compared using actual topographic surfaces. It is shown that our approach (k-reverse greedy) gives on average the best near optimum solutions. The most surprising finding of the experiments is that the combination of heuristics introduced here yields even better results.

In this article, a new algorithm for determining differences between two sets of polygons is considered. It has been proven that it is enough to test only the polygon edges to perform the comparison. The algorithm works in two steps. First, the polygon edges are initialised into a data structure and equal edges are eliminated by a simple criterion. In the second part, the algorithm analyses the remaining edges and prepares a report about the detected differences. To speed-up the geometric search, the algorithm uses a combination of a uniform space subdivision and binary searching trees. It has been shown that the algorithm is numerically stable, and works well with a limited set of non-simple polygons from a land cadastre. The algorithm's time complexity is O (n log n), and space complexity O(n), where n is the common number of edges in both sets of polygons. This is been confirmed by experiments using data sets from the land cadastre.

This paper introduces a new algorithm for constructing a 2D Delaunay triangulation. It belongs to the class of incremental insertion algorithms, which are known as less demanding from the implementation point of view. The most time consuming step of the incremental insertion algorithms is locating the triangle containing the next point to be inserted. In this paper, this task is transformed to the nearest point problem, which is solved by a two-level uniform subdivision acceleration technique. Dependencies on the distribution of the input points are reduced using this technique. The algorithm is compared with other popular triangulation algorithms: two variants of Guibas, Knuth, and Sharir's incremental insertion algorithm, two different implementations of Mücke's algorithm, Fortune's sweep-line algorithm, and Lee and Schachter's divide and conquer algorithm. The following point distributions are used for tests: uniform, regular, Gaussian, points arranged in clusters, and real data sets from a GIS database. Among all tested algorithms, the divide and conquer approach turns out to be the best. The proposed algorithm is the second fastest except for input points with highly non-uniform distribution. As implementation of the algorithm is simple, it represents an attractive alternative to other Delaunay triangulation algorithms used in practice.

Many enterprises experience difficulty in training people to work with expensive equipment, which is needed for carrying out profitable work tasks (e.g., production line robots). Similar problems are found when work is of a complex and safety-critical nature (e.g., nuclear environments, explosive placement, surgery). A common problem faced by educational institutions concerns the limited availability of expensive robotics equipment, with which students in the didactic program can work, in order to acquire valuable "hands on" experience. This paper describes a method of education and training involving off-line usage of virtual reality environments for task planning. When tasks are developed to the satisfaction of the trainee, they are exported to remote physical hardware, via the Internet, for real-world execution. Development of the system and the training experiments is discussed, along with some of the issues raised for telerobotics and solutions to the problem of detecting collisions in the virtual world. The approach has been shown to be viable, and increases the education and training possibilities for key workers while maintaining a low cost of ownership. The downtime of mission critical equipment is minimized while the gaining of valuable experience is maximized.

There are a number of initiatives aimed at the introduction of the digital age to the Arab world. A leading company in this area is Sakhr Software, who have just launched their programme (SakhrMedia) to support the learning process in local educational institutions. The objective is to meet the greater requirement of computerising both the techniques and the knowledge which has thus far been developed alongside traditional platforms. In this regard efforts have been made to computerise Arabic typography and language (often referred to as Arabisation). This is vitally important not just to meet everyday needs, but also to harmonise for the Arab audience interaction with worldwide accepted application packages, as well as the Internet. The purpose of this paper is to revisit the digitising process (sometimes called rasterisation) of the most valued aspects of a language, its character set. Using a geometric modelling approach, a computer system has been developed to extract and store features of Arabic fonts. Such a process lends itself to fast reconstruction and rendering of characters, and for text recognition techniques. The discussion provides an insight into the workings of the system, with view to assisting the digitisation process for Arabic.

The desire to computerise and accurately represent contours of characters has seen an increased emphasis as more and more applications endeavour to seek benefits from the digital form. The latter lends itself to be exploited by fast processors and the resulting output to be displayed not just on electronic devices such as computer monitors and laser printers, but also on numerically controlled machines. These in practice are used to generate desired outlines on paper, metal, plastic or wood by means of cutting and engraving. The process of computerising font outlines, however, embodies the common problems of domain change approximations and truncations. In the case under consideration, the capturing phase is best undertaken by means of mathematical splines, where a series of spline segments are connected together to form a computer model of the original. The digitisation phase of representing the modelled image on a finite resolution output device tends to be the more dominant concern. This is not just because of the transformation process (going from semi-continuous to discrete form), but also because the resulting image needs to embrace the distinct features of a font, has to be aesthetically acceptable, and requires to be in a form which is legible. This paper attempts to address some of the concerns encountered by modern typographers. It reports on a development of an interactive system to facilitate a feature-based design approach. This uses geometric constraints to express spatial relationships within, and between, font features.

Decomposing a simple polygon into simpler components is one of the basic tasks in computational geometry and its applications. The most important simple polygon decomposition is triangulation. Different techniques for triangulating a simple polygon were designed. The first part of the paper is an overview of triangulation algorithms based on diagonal insertion. In the second part, we present algorithms based on Delaunay triangulation. The basic ideas and approach for each algorithm are presented. Finally, some representative algorithms are compared by efficiency.

The paper considers an efficient approach to traversing a uniformly‐subdivided space pierced by a line segment. A voxel, as the basic constituent element of the uniformly subdivided space, is restricted to having the form of a cube. The algorithm works in two steps. In the first step, the so‐called Bresenham voxels are identified and, by comparing their position codes, their type of connectivity is determined. To achieve the required connectivity between neighbouring voxels, the second step of the algorithm is applied to find the missing voxels. In this way, the algorithm efficiently switches between face‐, edge‐ and vertex‐connectivity. Although the algorithm works with oating‐point precision, it is extremely computationally efficient, and tests of speed compared with the Müller, Cleary & Wyvill, Amanatides & Woo, and Zemčik algorithms are described.