We consider an important technology of linear algebra, aimed at reducing the size of files intended for storing images and transmitting them over the network. The technology involves the use of elements of tensor analysis based on singular decomposition. A feature of the technology used is the representation of the image by the matrix triad, which includes the tensor core and a pair of unitary matrices containing right and left singular vectors, respectively. Compression is achieved by one recurrent procedure, which involves lowering the rank of the triad to the level of allowable errors while maintaining the original image size. The compression algorithm is an iterative procedure with control of the Frobenius norm by the error matrix of the deviation of the original and the approximation matrix, which ensures the permissible value specified by the designer. The article establishes the basic features of the algorithm, in particular, convergence in a finite number of steps. This technology may be part of some hybrid technology based on different compression methods. The simulation was carried out on typical digital images, confirms the productivity of the procedure, the results obtained are compared with other types of decompositions according to the criteria of the signal-to-noise ratio, the standard error, and visual assessment of perception. Discusses the use of developed technology to store information belonging to big data.
In medical practice, non-invasive research methods are widely used, the main advantages of which are the visibility and accuracy of the measurements. Such methods include ultrasound diagnostics, computed and magnetic resonance imaging, radiography and others. The result of the study is shown in the images, the increase of which inevitably causes the problem of storage and transmission of measurement data to the end-user. A natural approach to solving this problem is image compression.
Compression is a popular technique for converting images to a form that is convenient for transmission over wired and wireless communication channels and also for their storage [1]. To date, several effective techniques have been developed based on different approaches. The most commonly used are considered hybrid techniques, including several compression methods, such as JPEG, JPEG2000. The main difference between the two is the replacement of low-performance transforms, such as Huffman and discrete-cosine, with more efficient arithmetic coding and wavelet transform, respectively. Analysis of the development of these methods shows the possibility of replacing individual stages of the method with more effective ones. The main goal of such methods is to improve the compression and recovery performance of images and minimize distortion. The best compression is achieved in the algorithms that involve losses, where frequency separation of the image components is assumed.
One of the effective methods that appeared at the end of the last century is vector quantization. The method assumes a high correlation between the individual elements of the image. However, there are some computational difficulties associated with the definition of a code word. The main output, as in the previously developed methods, is the discarding of several codewords, provided that it does not give significant distortion to the final product. A possible drop option can be constructed using the leastsquares method.
The study aim is to study the possibility of linear algebra methods for compressing medical images. 2
There are many works in which the well-known method of linear algebra is applied, which assumes decomposing in singular values (svd), in which the image is decomposed into a matrix triad. By discarding small singular values, the computational cost of presenting the result can be reduced. Currently, there is an increase in work related to the use of singular decomposition in the interests of medical research. The state of the issue of the use of singular decomposition in science and technology is presented in [2]. So, in the work of [3], a singular decomposition is proposed for the detection of brain tumors. The method uses a comparison of the measured parameter with its threshold value. However, there are some problems associated with the application of svd.
In [4], the use of singular decomposition together with the vector quantization algorithm for image compression is proposed, which, in the authors' opinion, seems to be the best technique compared to the discrete cosine transform, which also uses the application of the transform to individual image blocks. The number of vectors involved in quantization is determined by the rank of the matrix. The method involves the elimination of unnecessary (exceeding the rank of the image matrix) computational operations with small singular numbers when the image is restored. Block quantization helps to reduce computational costs when applying singular decomposition to the entire image.
The authors of [5] propose a hybrid compression method based on the sharing of singular decomposition and the Karhunen-Loeve transform. Since the KarhunenLoeve transform is applied to the entire image, the quality of the reconstructed image when packaged by the singular decomposition of small blocks is higher. The size of large blocks is determined by the bit distribution and is constant for the selected image. Switching between compression methods is proposed to implement the largest functional, determined by the transmission rate and distortion at this speed.
Three schemes for the use of singular decomposition were studied in terms of the quality of the compression and the computational complexity of these processes are presented in [6]. It is noted here that those algorithms that allow you to adaptively choose the size of the block to which the singular value decomposition is applied have greater efficiency.
One of the modern trends in the field of processing large data, which should include the image, is the use of tensor networks. The use of tensor networks is used to construct an image compression algorithm proposed in [7]. The image is transformed into the n-dimensional tensor of the real keta coefficients, which determines the quantum state represented by the matrix products. Visual information is represented by the state of a truncated matrix of multiplications. The method is rather complicated due to the uncertainty of finding important values in the matrices of multiplications. To overcome the resulting uncertainty, the authors of [7] propose the construction of a set of tables, the closest table is found by a genetic algorithm.
The method of representation of images based on the singular decomposition of a high order is proposed in [10]. Unlike the usual representation of a tensor by a set of singular values and right and left unitary matrices, orthogonal functions of one variable are used. When scaling images, the main tensor core retains its shape, while the function matrices expand by a given scale factor, the missing elements of the orthogonal function are complemented by the cubic interpolation method. To compress the method must be supplemented by some means.
Compression of hyperspectral images based on the Tucker decomposition is presented in [11]. Following this method, the image is decomposed into three matrices of nuclei and three transformation matrices. The optimal decomposition, which assumes a high compression ratio and a signal-to-noise ratio, is achieved by the blockcoordinate descent method, which allows a compressed image to be obtained. To eliminate the dependence of the compression effect on the choice of initial values of the matrices, an algorithm of compressive sensitivity is used. The result set is used for onward transmission. Noises are removed except small singular values from the matrices symbolizing the tensor core.
A parallel computation method using the Tucker decomposition to compress scientific data is proposed in [10]. The composition of various methods for image processing proposed in [11, 12] is also useful.
Image transmission via the communication channel is compressed. A unit of information in digital images is a pixel, and the entire set of image pixels is conveniently represented by a numeric matrix, so it is natural to apply matrix methods to compress images. The greatest interest among the methods of working with matrices with real values is attracted by the tensor representation in the form of a triple of matrices, one of which is diagonal and pairs of orthogonal matrices.
The matrix А Rmn of real values is algebraically represented by a threedimensional tensor in the form of a bilinear form, obtained from the well-known one, represented by the product of three matrices in the form of a singular decomposition of the form
A MNT ,
(
Image compression size shrinks by grouping or dropping part of the pixels. If the grouping algorithms allow you to restore the quality of images, then discarding several pixels leads to a loss of its quality when scaled. Drop pixels in the compression process occurs based on signs of repeatability or frequency. Then the problem of compression is reduced to the definition of a triplet of smaller matrices.
The resulting matrices are sequences of numbers, so the compression process is similar to the coding process, where the input n-dimensional vector xRn is converted by the encoder into a code word (x) of a smaller size l = n / K (l < n), where K is the compression ratio. The discarding of a part of the information is a source of image distortions, which, as a result of compression, with identical image sizes, is evaluated by various criteria, the most common among them are the average square of errors, the signal-to-noise ratio, and visual criteria. The average error square is written as where M, N are the vertical and horizontal dimensions of the image, or the signal-tonoise ratio is represented by the formula emse 1 M N 2
(xij ) xij ,
MN i1 j1 Rs / w 20log10 (xmax ) , emse where xmax is the maximum pixel value of the image, R s / w is the representation of the signal-to-noise ratio.
The purpose of the paper is to determine the matrices M, N and the kernel of the
tensor D, which satisfy the specified image quality defined by formulas (
A Aˆ e
p q Aˆ i mi nTj .
i1 j1
p q
lim iminTj 0 ,
qpNM , i1 j1
(
Proof. Using the property for unitary transformations (formula 5.7 out of [9]), we obtain the representation
then 4
Let the image A be possible to represent the original in the form (
E Ei1 A (1m1n1 ... imini ) Ei imini .
Since for the applied decomposition, (
It is assumed that the image signal x displayed by the grayscale color model is a
numeric matrix, which is further decomposed into the kernel = (1, …, N) and the
codebook D. The codebook is a memory of coefficients (x) = (M, N) D, which
remain unchanged during transformations, encoding implies a reduction in the size of
the core relative to the original size with permissible distortions. A threshold c is
preliminarily set, according to which the distortions are considered permissible. The
coding system iteratively selects the size of the kernel ˆ that satisfies the specified
threshold according to the selected quality criterion, for example (
If necessary, the compressed image can be restored by the inverse transform, if it is provided for by the compression algorithm. In this case, the dictionary is also available to the decoder. Decoding is the inverse mapping of the code word to the input vector. In loss algorithms, the original image is not restored.
The size of the dictionary is determined by the set of codewords L, using binary coding. The size of the code word is V = log2L, bit. To simplify the computing system, the matrix of images is pre-divided into submatrices, with which it is convenient to perform calculations. The minimum size of the image blocks is 88 pixels. When a block of information is compressed by K times, the code word is also reduced by K times.
The simulation was carried out on a personal computer with an image of 384384
pixels. The reference image was previously divided into sub-images of 88 pixels.
Then, the procedure (
p x (x) iminiT E xˆ E .
i1 e E
F
S M p p N Tp 2 .
(
6
The proposed algorithm was estimated for the original image obtained as a result ultrasound examination of the abdominal cavity, the view of which is shown in Fig.2.
Algorithm (
Comparison data are presented in Table 1. Here R is the rank of a compressed matrix, K is the compression ratio. 0.1 0.3 0.5 0.7 0.9
Analysis of the obtained results allows you to confirm the performance of the algorithm. Acceptable image quality was maintained by reducing the size of the decomposition core matrix by 200 times. Low compression ratios were obtained because of additional conversion of the reconstructed image to the format JPEG. Better compression can be achieved by preserving the triad of transformation matrices in numerical form, using, for example, the TXT format. The best image quality when visually evaluating the quality of compression is obtained at small values of , as it should be. The proposed algorithm is useful for compressing medical images. 7
The study showed the effectiveness of using singular decomposition for storing and transmitting in the network medical images typical of non-invasive research methods. As a result of the study, it has been found that matrix methods based on decompositions that can be combined with other methods, such as grouping, traditionally used in hybrid compression methods, are quite effective for image compression. Higher image quality is achieved by increasing the accuracy of the truncated description approaching the original image. The developed algorithm has the property of adaptability. Further research is planned to be devoted to searching methods for finding the unknown tensor core for given unitary matrices M, N.