Optimization of computational complexity of lossy compression algorithms for hyperspectral images

Abstract

In this paper, we consider the solution of the problem of increasing the speed of the algorithm for hyperspectral images (HSI) compression, based on recognition methods. Two methods are proposed to reduce the computational complexity of a lossy compression algorithm. The first method is based on the use of compression results obtained with other parameters, including those of the recognition method. The second method is based on adaptive partitioning of hyperspectral image pixels into clusters and calculating the estimates of similarity only with the templates of one of the subsets. Theoretical and practical estimates of the increase in the speed of the compression algorithm are obtained.

-

ε m ( A) = minε ( A) = A 1

2. Criteria for assessing the proximity of signatures

Let us consider some criteria for calculating similarity estimates:

A(ye ) = ye : ε mnt =M(ye )2 + M y2 − 2 ⋅ M yey ; A(ye ) = ye + ∆ye : ε mot =D ye + D y − 2 ⋅ cov(ye , y) , ∆ye = M y − M ye ; ( 2 ) A(ye ) =km ⋅ ye : ε st m

=M y2 − M2 (yey) M(ye )2 , km = M(yey) M(ye )2 ; A(ye ) = km ⋅ ye + ∆ye : ε mat =D y − cov2 (ye , y) D ye , km = cov(ye , y) D ye , ∆ye = M y − km ⋅ M ye .

In the above formulas, Μy , Μye , Μy2 , Μ(ye )2 denote the initial moments of the first and second orders of the current signature and template;

Μyey is the mixed covariance moment; Dy , Dye denote the dispersion of the signature and the template; cov(ye , y) is the correlation moment; ∆ye , km are the bias and the scale factor [1-3].

3. Recognition algorithm with self-learning

Based on the proximity estimates ( 2 ), in accordance with the recognition algorithm, for each template pixel ye and the current signature y , the value ε m (y, ye ) is calculated; among these values, the smallest one, ε min (y) is found. If this estimate is greater than a given threshold ε min (y) > δ , then a new template is formed on the basis of the signature description y . When ε min (y) < δ , the pixel is considered to be recognized and using the parameters obtained, a corresponding record in the output file is made. For all the similarity estimates ( 2 ), a template number must be assigned, which is recorded in a 2-byte field (or a 4-byte field if the number of templates exceeds 65536). The values ∆ye and km are given by real variables, which are recorded in 4-byte fields. Therefore, the length of the structures for writing the parameters depending on the similarity estimate used will be equal, respectively, to 2, 6, 6 and 10 bytes (or 4, 8, 8 and 12 bytes)..

4. Optimization of computations in the HSI compression algorithm

Let us consider two possibilities for increasing the speed of the compression algorithm under consideration. It follows from the recognition algorithm that the number of obtained templates depends on the threshold value δ , which in turn is determined by the error limited to a certain percentage σ of the current signature. Then the recognition and, therefore, the compression will be performed using an adaptive threshold δ =(0.01⋅σ )2 ⋅ Μy2 . From the analysis of formula ( 2 ), it follows that when compressing a HSI with a similarity estimate ε at , the number of templates will be m the smallest among all compression algorithms using the remaining proximity estimates. In turn, compression algorithms based on proximity estimates ε mst and ε mot have some advantages in terms of speed over the algorithm using the proximity estimate ε nt . Similarly, the greater the value σ , the m less templates will be obtained in the recognition process and thus the shorter the HSI compression time. Therefore, in order to reduce compression time required by more time-consuming algorithms, it is necessary to use the results of compression provided by faster compression algorithms. The modification of the compression algorithm in this variant consists in calculating the estimate of similarity only with the templates generated by the template of the high-speed algorithm. The second modification of the compression algorithm is based on the current clustering of signatures being recognized and forming own templates in each cluster. Therefore, if the current signature is assigned to a cluster, the similarity estimate will be formed on the basis of the templates of this cluster. The clustering is carried out in the space of the features, which can be easily obtained by calculating the initial moments of the first and second orders of the current pixels.

Let us estimate the computational complexity of recognition methods based on the proposed similarity estimates. Let the function describing the dependence of the number of templates used on the current number of the pixel being recognized be given by the formula v = [ f (u)] , with m = f (N ) , f (0) = 0 ,

where N is the number of pixels of the image, and m is the number of templates obtained during image compression. The function v = [ f (u)] is piecewise constant and, therefore, an increase in the number of templates per unit occurs during the compression of pixels with the numbers u = Ni . Hence, f (Ni ) − f (Ni−1) =1,and from this expression one can find the numbers of pixels Ni . Then the computational complexity of the HSI compression algorithm will be determined by the formula:

m C = ∑ i ⋅ (Ni − Ni−1) ⋅ O(n) i=1 , ( 3 ) where O(n) is the complexity of obtaining the estimate of similarity of a pixel with the template. If we assume that f (u) is a linear function of (L), then C(L) = [N ⋅ (m + 1) / 2] ⋅ O(n) , since Ni − Ni−1 =Nm . However, as a rule, the number of templates increases faster at the initial stage of compression and slows down closer to the completion of the HSI pixel recognition process. If we take the parabola (P) u = N ⋅ v2 m2 as a function approximating the plot of the number of templates depending on the number of pixels processed, then it follows from the expression m ⋅ Ni N − m ⋅ Ni−1 N =1 that Ni − Ni−1 =N m2 ⋅ (2 ⋅ i − 1) . Hence, the computational complexity of the HSI compression algorithm in this case can be estimated by the value C(P) = [N ⋅ (m + 1) ⋅ (4 − 1 m) 6] ⋅ O(n) , and therefore, C(P) C(L) ≈ 4 3 . In the case of the cubic dependence (K) u = N ⋅ v3 m3 , the computational complexity is equal to C(K ) = [N ⋅ (m + 1) ⋅ (3 − 1 m) 4] ⋅ O(n) , and C(K ) C(L) ≈ 3 2 . For the proposed approximation functions, the computational complexity of the recognition algorithm is proportional to N (m + 1) and, therefore, if the number of templates is M > m , then while maintaining the same distribution law, the HSI compression time will increase by a factor of M m . Note that an increase in the HSI compression time does not depend on the distribution law.

5. Experimental research

Experiments on solving recognition problems were performed on the f100520t01p00-12 HSI file of the AVIRIS spectrometer based on 224 frequencies with wavelengths in the range from 365.9298 to 2496.236 nm. The original HSI was represented by a matrix of 813×2109 pixels with a resolution of 17.3 m. A two-byte format for representing the spectrum amplitude values was used. At the beginning, filtering (correction of values) of spectral images of the original HSI was performed. Its purpose was to replace the negative values of the signature with the data obtained by piecewise linear approximation with the closest positive values. Signatures with completely negative or positive component values were not adjusted. The number of pixels with completely negative values was 207055 of the total number 1714617 (≈12%).

By using compression with an adaptive threshold, calculated for the value σ = 2 for the similarity estimates listed in ( 2 ), we obtained 2582, 1841, 976 and 785 templates, respectively. Since it can be expected that the computational complexity of compression is proportional to the number of templates obtained in the course of recognition, the running time of the algorithm may vary up to 3.3 times when using different similarity estimates. Figure 1 shows the graphs of the number of templates used depending on the current number of a HSI pixel being recognized for various similarity estimates. Figure 2 shows the graphs of various functions a) - c) approximating the dependence of the number of templates used on the current number d). Figure 3 shows a histogram of the number of signatures recognized by each template when using the estimate ε st . It can be concluded from these graphs that m the bulk of the pixels is encoded on the basis of the first third of the templates. However, the remaining pixels will use in the coding almost the entire set of templates, which leads to an increase in the running time of the algorithm. When using a modification of the compression algorithm utilizing the results obtained in recognition with the estimate ε st , each signature will be compared on average m with only three templates. 12891 templates for the time ≈ 160 minutes. The execution time of the proposed compression algorithm for σ = 5 with the account of the time for obtaining clusters was ≈ 13 minutes, which corresponds to theoretical estimates. Figure 4 shows the plots of the number of templates used to obtain the same similarity estimate depending on the current HSI pixel number for various compression thresholds and their approximation by analytical functions.

6. Conclusion

Experiments performed on hyperspectral images have confirmed the estimates of the expected increase in the speed of the modified recognition algorithms based on self-learning recognition. It was established that the speed of the modified compression algorithms is more than an order of magnitude higher than their original counterparts. A further increase in speed can be achieved by parallelizing the computations at each step of the two-step compression algorithm proposed.

Acknowledgements

This work was supported by the Russian Science Foundation, project No. 16-11-00068.

References

[1] Lebedev L I 2018 Recognition and classification of objects in a hyperspectral image Proceedings of the 5th International Scientific Conference «Regional problems of remote sensing of the earth» (Krasnoyarsk: Siberian Federal University) 138 - 143

[2] Lebedev L I and Shakhlan A O 2018 Spatial analysis of hyperspectral images Proceedings of the 25th International Scientific Conference (Tomsk: Tomsk Polytechnic University) 150 - 153

[3] Lebedev L I 2013 Correlation - extreme contour recognition methods. Theoretical foundations: A study manual (Nizhny Novgorod: Nizhny Novgorod State University) p 113

[4] Tatarnikov V V , Pestunov I A and Berikov V B 2017 Centroid averaging algorithm for a clustering ensemble Computer Optics 41 ( 5 ) 712 - 718 DOI: 10.18287/ 2412 -6179-2017-41-5- 712 -718

[5] Myasnikov E V 2017 Hyperspectral image segmentation using dimensionality reduction and classical segmentation approaches Computer Optics 41 ( 4 ) 564 - 572 DOI: 10.18287/ 2412 -179- 2017-41-4- 564 -572

[6] Varlamova A A , Denisova A Y and Sergeev V V 2018 Earth remote sensing data processing technology for obtaining vegetation types maps Computer Optics 42 ( 5 ) 864 - 876 DOI: 10.18287/ 2412 -6179-2018-42-5- 864 -876