Watershed is a widespread technique for image segmentation. Many researchers apply the method implemented in open source libraries without a deep understanding of its characteristics and limitations. In the review, we describe benchmarking outcomes of six open-source marker-controlled watershed implementations for the segmentation of 2D and 3D images. Even though the considered solutions are based on the same algorithm by flooding having O(n)computational complexity, these implementations have significantly different performance. In addition, building of watershed lines grows processing time. High memory consumption is one more bottleneck for dealing with huge volumetric images. Sometimes, the usage of more optimal software is capable of mitigating the issues with the long processing time and insufficient memory space. We assume parallel processing is capable of overcoming the current limitations. However, the development of concurrent approaches for the watershed segmentation remains a challenging problem.
Watershed is a widely used image segmentation algorithm. Most researchers understand just an idea of this method: a grayscale image is considered as topographic relief, which is flooded from initial basins. However, frequently they are not aware of the options of the algorithm and the peculiarities of its realizations. There are many watershed implementations in software packages and products. Even if these packages are based on the identical algorithm–watershed, by flooding their outcomes, processing speed, and consumed memory, vary greatly. In particular, the difference among various implementations is noticeable for huge volumetric images; for instance, tomographic 3D images, for which low performance and high memory requirements of watershed might be bottlenecks. In our review, we discuss the peculiarities of algorithms with and without waterline generation, the impact of connectivity type and relief quantization level on the result, approaches for parallelization, as well as other method options. We present detailed benchmarking of seven open-source and three commercial software implementations of marker-controlled watershed for semantic or instance segmentation. We compare those software packages for one synthetic and two natural volumetric images. The aim of the review is to provide information and advice for practitioners to select the appropriate version of watershed for their problem solving. In addition, we forecast future directions of software development for 3D image segmentation by watershed.
Focused Ion Beam Scanning Electron Microscopy (FIB-SEM) tomography provides a stack of images that represent serial slices of the sample. These images are displaced relatively to each other, and an alignment procedure is required. Traditional methods for alignment of a 3D image are based on a comparison of two adjacent slices. However, such algorithms are easily confused by anisotropy in the sample structure or even experiment geometry in the case of porous media. This may lead to significant distortions in the pore space geometry, if there are no stable fiducial marks in the frame. In this paper, we propose a new method, which meaningfully extends existing alignment procedures. Our technique allows the correction of random misalignments between slices and, at the same time, preserves the overall geometrical structure of the specimen. We consider displacements produced by existing alignment algorithms as a signal and decompose it into low and high-frequency components. Final transformations exclude slow variations and contain only high frequency variations that represent random shifts that need to be corrected. The proposed algorithm can operate with not only translations but also with arbitrary affine transformations. We demonstrate the performance of our approach on a synthetic dataset and two real FIB-SEM images of natural rock.
Matrix multiplication is an important operation for many engineering applications. Sometimes new features that include matrix multiplication should be added to existing and even out-of-date embedded platforms. In this paper, an unusual problem is considered: how to implement matrix multiplication of 32-bit signed integers and fixed-point numbers on DSP having SIMD instructions for 16-bit integers only. For examined tasks, matrix size may vary from several tens to two hundred. The proposed mathematical approach for dense rectangular matrix multiplication of 32-bit numbers comprises decomposition of 32-bit matrices to matrices of 16-bit numbers, four matrix multiplications of 16-bit unsigned integers via outer product, and correction of outcome for signed integers and fixed point numbers. Several tricks for performance optimization are analyzed. In addition, ways for block-wise and parallel implementations are described. An implementation of the proposed method by means of 16-bit vector instructions is faster than matrix multiplication using 32-bit scalar instructions and demonstrates performance close to a theoretically achievable limit. The described technique can be generalized for matrix multiplication of n-bit integers and fixed point numbers via handling with matrices of n/2-bit integers. In conclusion, recommendations for practitioners who work on implementation of matrix multiplication for various DSP are presented.
Various types of tomography are widely employed in oil and gas industry for studying structure of rocks. Using X-ray or FIB-SEM tomography, a 3D model of a core sample is constructed for mathematical simulations of fluid flow in porous media and evaluation of physical characteristics of rock. Since images have various defects and distortions, there is a problem of selection of a fragment with the best quality from the initial 3D image. At the moment this operation is made manually on the basis of an expert's opinion and takes significant time. In this paper, we investigate applicability of existing non-reference quality metrics for evaluation of tomographic images and propose the approach for visualization of spatial change of 3D image quality. The method includes the construction of central cross-section; plotting graphs of quality and similarity measures for each slice over the cross-section; generation of combined heat map of quality of cubic fragments with various size. The proposed approach significantly accelerates and makes less subjective selection of the best region for further simulations in digital rock workflow. The choice of colour scale is considered to facilitate the analysis of graphical information for people with colour vision deficiency.