Search

Abstract Data compression algorithms tend to reduce information entropy, which is crucial, especially in the case of images, as they are data intensive. In this regard, lossless image data compression is especially challenging. Many popular lossless compression methods incorporate predictions and various types of pixel transformations, in order to reduce the information entropy of an image. In this paper, a block optimisation programming framework $$\Phi$$ Φ is introduced to support various experiments on raster images, divided into blocks of pixels. Eleven methods were implemented within $$\Phi$$ Φ , including prediction methods, string transformation methods, and inverse distance weighting, as a representative of interpolation methods. Thirty-two different greyscale raster images with varying resolutions and contents were used in the experiments. It was shown that $$\Phi$$ Φ reduces information entropy better than the popular JPEG LS and CALIC predictors. The additional information associated with each block in $$\Phi$$ Φ is then evaluated. It was confirmed that, despite this additional cost, the estimated size in bytes is smaller in comparison to the sizes achieved by the JPEG LS and CALIC predictors.

After a boom that coincided with the advent of the internet, digital cameras, digital video and audio storage and playback devices, the research on data compression has rested on its laurels for a quarter of a century. Domain-dependent lossy algorithms of the time, such as JPEG, AVC, MP3 and others, achieved remarkable compression ratios and encoding and decoding speeds with acceptable data quality, which has kept them in common use to this day. However, recent computing paradigms such as cloud computing, edge computing, the Internet of Things (IoT), and digital preservation have gradually posed new challenges, and, as a consequence, development trends in data compression are focusing on concepts that were not previously in the spotlight. In this article, we try to critically evaluate the most prominent of these trends and to explore their parallels, complementarities, and differences. Digital data restoration mimics the human ability to omit memorising information that is satisfactorily retrievable from the context. Feature-based data compression introduces a two-level data representation with higher-level semantic features and with residuals that correct the feature-restored (predicted) data. The integration of the advantages of individual domain-specific data compression methods into a general approach is also challenging. To the best of our knowledge, a method that addresses all these trends does not exist yet. Our methodology, COMPROMISE, has been developed exactly to make as many solutions to these challenges as possible inter-operable. It incorporates features and digital restoration. Furthermore, it is largely domain-independent (general), asymmetric, and universal. The latter refers to the ability to compress data in a common framework in a lossy, lossless, and near-lossless mode. COMPROMISE may also be considered an umbrella that links many existing domain-dependent and independent methods, supports hybrid lossless–lossy techniques, and encourages the development of new data compression algorithms.

A new algorithm is presented for detecting the local weak reflection symmetries in raster images. It uses contours extracted from the segmented image. A convex hull is constructed on the contours, and so-called anchor points are placed on it. The bundles of symmetry line candidates are placed in these points. Each line splits the plane into two open half-planes and arranges the contours into three sets: the first contains the contours pierced by the considered line, while the second and the third include the contours located in one or the other half-plane. The contours are then checked for the reflection symmetry. This means looking for self-symmetries in the first set, and symmetric pairs with one contour in the second set and one contour in the third set. The line which is evaluated as the best symmetry line is selected. After that, the symmetric contours are removed from sets two and three. The remaining contours are then checked again for symmetry. A multi-branch tree representing the hierarchy of the detected local symmetries is the result of the algorithm.

This paper proposes a new string transformation technique called Move with Interleaving (MwI). Four possible ways of rearranging 2D raster images into 1D sequences of values are applied, including scan-line, left-right, strip-based, and Hilbert arrangements. Experiments on 32 benchmark greyscale raster images of various resolutions demonstrated that the proposed transformation reduces information entropy to a similar extent as the combination of the Burrows–Wheeler transform followed by the Move-To-Front or the Inversion Frequencies. The proposed transformation MwI yields the best result among all the considered transformations when the Hilbert arrangement is applied.

The characterisation of geometric shapes produces their concise description and is, therefore, important for subsequent analyses, for example in Computer Vision, Machine Learning, or shape matching. A new method for extracting characterisation vectors of 2D geometric shapes is proposed in this paper. The shape of interest, embedded into a raster space, is swept several times by sweep-lines having different slopes. The interior shape’s points, being in the middle of its boundary and laying on the actual sweep-line, are identified at each stage of the sweeping process. The midpoints are then connected iteratively into chains. The chains are filtered, vectorised, and normalised. The obtained polylines from the vectorisation step are used to design the shape’s characterisation vector for further application-specific analyses. The proposed method was verified on numerous shapes, where single- and multi-threaded implementations were compared. Finally, characterisation vectors, among which some were rotated and scaled, were determined for these shapes. The proposed method demonstrated a good rotation- and scaling-invariant identification of equal shapes.

A new approach is proposed for lossless raster image compression employing interpolative coding. A new multifunction prediction scheme is presented first. Then, interpolative coding, which has not been applied frequently for image compression, is explained briefly. Its simplification is introduced in regard to the original approach. It is determined that the JPEG LS predictor reduces the information entropy slightly better than the multi-functional approach. Furthermore, the interpolative coding was moderately more efficient than the most frequently used arithmetic coding. Finally, our compression pipeline is compared against JPEG LS, JPEG 2000 in the lossless mode, and PNG using 24 standard grayscale benchmark images. JPEG LS turned out to be the most efficient, followed by JPEG 2000, while our approach using simplified interpolative coding was moderately better than PNG. The implementation of the proposed encoder is extremely simple and can be performed in less than 60 lines of programming code for the coder and 60 lines for the decoder, which is demonstrated in the given pseudocodes.

A new algorithm is presented for detecting the global reflection symmetry of geometric objects. The algorithm works for 2D and 3D objects which may be open or closed and may or may not contain holes. The algorithm accepts a point cloud obtained by sampling the object’s surface at the input. The points are inserted into a uniform grid and so-called boundary cells are identified. The centroid of the boundary cells is determined, and a testing symmetry axis/plane is set through it. In this way, the boundary cells are split into two parts and they are faced with the symmetry estimation function. If the function estimates the symmetric case, the boundary cells are further split until a given threshold is reached or a non-symmetric result is obtained. The new testing axis/plane is then derived and tested by rotation around the centroid. This paper introduces three techniques to accelerate the computation. Competitive results were obtained when the algorithm was compared against the state of the art.

Trees are natural objects, where deviations through the branches amplify geometric data for 3D representation and bring challenges to various applications dealing with 3D models, such as compression, visualization, symmetry detection, and radiative transfer simulation. This data article describes dataset of approximately symmetric 3D tree models with manually identified predominant symmetry plane in each tree model. Parameters for procedural tree synthesis were manually adjusted to produce approximately bilaterally symmetric trees which are grouped into species with distinct features. In the last step, each tree was manually annotated with approximate symmetry plane. This dataset contains geometric data of branches, manually defined parameters for tree synthesis method, point clouds, and a division plane with a score of bilateral symmetry strength. The generated trees can be used as benchmark data for verification of approximate reflectional symmetry detection methods. Additionally, generated 3D tree models can be used for other applications requiring pregenerated trees, such as compression of tree models, instancing, decimation methods, and radiative transfer simulation and modeling.