CN101739666B - One-dimensional Hartley transform and match tracing based image sparse decomposition fast method - Google Patents

Abstract

The invention discloses a one-dimensional Hartley transform and match tracing based image sparse decomposition fast algorithm. The algorithm comprises the following steps of: constructing a core atomic library, converting an original two-dimensional image into a one-dimensional real signal, sparsely decomposing the atoms in the atomic library into one-dimensional atoms, adopting the one-dimensional fast Hartley transform to realize the cross correlation operation of the image or image residual and the atoms, finding the best atom, and finally realizing the decomposition of the image. The algorithm has the advantages of realizing the fast sparse decomposition of the image and having good visual effect of the reconstructed image.

Description

A Fast Method for Image Sparse Decomposition Based on One-dimensional Fast Hartley Transform and Matching Pursuit

technical field

The invention relates to a fast method for sparse decomposition of matching and tracking images used in still image denoising, image recognition, image compression and the like.

Background technique

In the actual engineering application of digital image processing, the expression or decomposition of digital image is a key link. In 1994, Mallat et al proposed a matching pursuit (Matching Pursuit, matching pursuit) method for image sparse decomposition (BERGEAU F, MALLAT S. Matching pursuit of images. Proceedings of IEEE-SP. Piladel-phia, PA, USA, 1994.330-333 ). Since then, the application of sparse decomposition in the field of image processing has been continuously developed. In image sparse decomposition, the key to realize time-frequency search is to select which type of atoms to construct over-complete atomic library. For the over-complete atomic library, in order to better represent the image content, the researchers proposed the asymmetric atomic library, the two-dimensional Gabor atomic library, etc. At the same time, the newly developed Ridgelet, Curvelet, Bandelet, and Contourlet can also be used as atomic models to form an over-complete atomic library. Complete atomic library.

At present, researchers have proposed a variety of image sparse decomposition algorithms, such as image sparse decomposition based on matching pursuit, BP algorithm, MOF algorithm and BOB algorithm, among which the most commonly used method is image sparse decomposition based on matching pursuit. Like other image sparse decomposition algorithms, image sparse decomposition based on matching pursuit also has the problems of huge amount of calculation and slow operation speed. The study found that the main computation of image sparse decomposition based on matching pursuit is the matching operation of finding the best atom in the decomposition, that is, the inner product operation of image or image residual and atom. Because this inner product operation is an inner product operation in a high-dimensional space (the space dimension is the same as the image size), and it needs to be performed many times (the number of inner product operations in each step is the same as the number of atoms in the atomic library). Therefore, it is the key to improve the speed of image sparse decomposition based on matching pursuit to find a fast algorithm for inner product operation in image sparse decomposition. For this reason, researchers proposed to use genetic algorithm (Li Hengjian, Yin Zhongke, Wang Jianying. Image sparse decomposition based on quantum genetic algorithm [J]. Southwest Jiaotong University Journal. 2007, 42(1): 19-23) to improve its calculation speed , however, since the genetic algorithm is an optimization algorithm for local search, it is difficult to find the optimal time-frequency atom among all the atoms, resulting in a poor reconstructed image; other similar methods based on intelligent computing have similar problems (Li Hengjian , Yin Zhongke, Zhang Jiashu, Wang Jianying. Image sparse decomposition based on chaotic mutation particle swarm optimization algorithm [J]. Southwest Jiaotong University Journal. 2008, 43(4)509-513); A Fast Algorithm for Generating Atoms According to the Classification Properties of Atomic Structures (Hua Zexi, Yin Zhongke, Huang Xionghua. A Fast Algorithm for Atom Formation in Signal Decomposition on Overcomplete Library[J]. Journal of Southwest Jiaotong University, 2005, 40(3): 402 -405.), this method improves the calculation speed to a certain extent, but still requires a large number of high-dimensional inner product operations.; In order to find the best atom in the whole world, some scholars have proposed to use the Fast Fourier Transform (Fast Fourier Transform , FFT) to achieve cross-correlation operations to find the best atom, but the fast Fourier transform involves complex operations, and the real signal needs to be artificially added with imaginary variables, which increases the complexity of the calculation, and the calculation speed is limited; in the fast Fourier transform On the basis of the leaf transform algorithm, for one-dimensional real signals, Liu Hao et al. proposed a fast algorithm using Fast Hartley Transform (FHT) to realize matching pursuit (Liu Hao, Pan Wei. Fast Algorithm for Sparse Decomposition of Real Signals Based on FHT [J]. Journal of Southwest Jiaotong University. 2009, 44 (1)), this algorithm is superior to the matching pursuit fast algorithm based on fast Fourier transform in terms of calculation speed, and it is also a global search algorithm, which avoids the genetic algorithm It can only achieve the limitation of local optimal search, but it can only achieve one-dimensional real signal decomposition.

In a word, image sparse decomposition using matching pursuit method has achieved success in denoising of still images, image recognition and image compression, but it is still difficult to be promoted and industrialized at present, the main reason is that the matching of image sparse decomposition The amount of tracking calculation is huge, and the calculation time is unbearable under the existing conditions. Therefore, the research on fast image sparse decomposition algorithms has become a frontier research topic at home and abroad in recent years, which not only has important academic value, but also has broad potential application prospects.

Contents of the invention

The object of the present invention is to provide a fast method for image sparse decomposition based on one-dimensional fast Hartley transformation and matching pursuit, which has a fast speed for image sparse decomposition and good visual effect of reconstructed image.

The present invention solves its technical problem, and the adopted technical solution is: a fast method for image sparse decomposition based on one-dimensional fast Hartley transformation and matching pursuit, comprising the following steps:

(1) Formation of the core atomic library:

For the original image f with a size of M×N, the atomic library for sparse decomposition is constructed. The atom g _γ is defined by the parameter group γ=(θ, u, v, s _x , s _y ), where θ represents the rotation angle of the atom, u and v are the translation of the atom in the x and y directions respectively, s _x and s _y are the expansion and contraction of the atom in the x and y directions respectively; let u=M/2 and v=N/2 form a two-dimensional core atom library {g _γ′ }, where the parameter set γ′ is discretized as follows:

${\mathrm{<span\; class="notranslate">\; \&gamma;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&theta;</span>}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; \&pi;\&theta;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}{\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\frac{\mathrm{<span\; class="notranslate">\; sty</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\frac{\mathrm{<span\; class="notranslate">\; sty</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}}<span\; class="notranslate">\; )</span>$

Among them, 1≤θ′≤max(M, N), 0≤stx≤5log ₂ M-5, 0≤sty≤5log ₂ N-5, θ′, stx, and sty all take integers in the corresponding interval;

(2) Atom and image conversion:

Convert all atoms g _γ′ in the core atomic library formed in step (1) into one-dimensional atoms g′ _γ′ ; convert the original image f whose size is M×N into a one-dimensional signal f′;

(3) Initial decomposition of the image:

对应的参数组

和对应的匹配系数

将图像的一维信号f′减去最匹配原子

与匹配系数

的乘积，得到图像残差R_f′；The one-dimensional signal f' of the image obtained in step (2) and all the one-dimensional atoms g'_γ' are cross-correlated using the one-dimensional fast Hartley transform algorithm to obtain the one-dimensional signal f' and the overcomplete atomic library {g The matching coefficient p _γ of all one-dimensional atoms g′ _γ in _γ }, and record the one-dimensional atom with the largest absolute value of matching coefficient p _γ

Corresponding parameter group

and the corresponding matching coefficient

Subtract the best matching atom from the one-dimensional signal f' of the image

and matching coefficient

The product of , get the image residual R _f′ ;

(4) Image decomposition:

对应的参数组

和对应的匹配系数

其中i为图像分解的当前次数；将图像残差R_f′减去最匹配原子

与匹配系数

的乘积，得到更新后的图像残差R_f′；Use the one-dimensional fast Hartley transform algorithm to perform cross-correlation operation on the currently obtained image residual R _f′ and all one-dimensional atoms g′ _γ′ , and obtain the image residual R _f′ and the overcomplete atomic library {g _γ } The matching coefficient p _γ of each atom, and record the atom with the largest absolute value of the matching coefficient p _γ

Corresponding parameter group

and the corresponding matching coefficient

where i is the current number of image decompositions; the image residual R _f' is subtracted from the best matching atom

and matching coefficient

The product of , get the updated image residual R _f′ ;

Repeat the above image decomposition operation, when the image decomposition result meets the subsequent processing requirements, end the operation, and obtain the original image f matching tracking sparse decomposition result $\{(P_{{\mathrm{\&gamma;}}_i},{\mathrm{\&gamma;}}_i)=(P_{{\mathrm{\&gamma;}}_i},{\mathrm{\&theta;}}_i,u_i,v_i,{\mathrm{the\; s}}_{x_i},{\mathrm{the\; s}}_{{\mathrm{the\; y}}_i})|i=\mathrm{0,1,2},...,\mathrm{no}\},$ where n is the total number of image decomposition operations.

Compared with prior art, the beneficial effect of the present invention is:

1. The present invention converts its inner product operation with a group of atoms into a cross-correlation operation with an atom in the matching operation of finding the best atom for the image or image residual at each step, while reducing the number of operations, It also realizes one-by-one comparison of all atoms in the entire over-complete atomic library, and then selects the real best atom, which is a global optimal algorithm. Therefore, the reconstructed image of the present invention has good visual effect, and effectively overcomes the image sparse decomposition based on intelligent computing methods such as genetic algorithm due to local optimization, that is, to find the best atom (approximately optimal atom) in a part of randomly selected atoms. The resulting randomness problem. At the same time, the present invention adopts a one-dimensional fast Hartley transformation algorithm to realize the cross-correlation operation between images or image residuals and atoms, which not only improves the speed of image sparse decomposition, but also reduces the requirement for data storage capacity. Discrete Hartley Transform (DHT) is an integral transformation similar to Discrete Fourier Transform (DFT), which has most of the characteristics of DFT transformation, but the integral kernel of its positive and negative transformation is the same . The DHT transformation of the real function is still a real function, thus avoiding the complex operation in the transformation process, so the data storage capacity is only half of the FFT, and the fast Hartley transformation can adopt the structure of the FFT, which can guarantee a high computing speed , and its calculation volume is about half of that of FFT.

2. The present invention fixes the atomic position parameters u=M/2 and v=N/2 to form a core atomic library. The number of atoms in the core atomic library is far smaller than the overcomplete atomic library, which reduces the storage requirements of sparse decomposition and achieves A good balance between computation and storage is achieved. At the same time, the sparse decomposition effect and time can be kept unaffected. This is because the core atomic library contains all atoms of different shapes in the over-complete atomic library, and an atom in the core atomic library is taken out. A group of atoms with the same shape but different central positions in the over-complete atomic library can be obtained, and the atom with the largest absolute value of the matching coefficient is found in each group of atoms, and then the matching of the atoms with the largest absolute value of the matching coefficient of each group is compared The absolute value of the coefficient, and then find the atom with the largest absolute value of the matching coefficient, that is, find the best matching atom among all the atoms in the over-complete atom library, so the quality of image decomposition will not be reduced; the over-complete atom library The atoms in the non-core atomic library are only temporarily generated by translation in the cross-correlation operation, and the non-best matching atoms after comparison do not need to be stored and recorded, and the storage capacity required is small; moreover, since the translation of atoms requires almost no calculation, So the speed of the whole sparse decomposition process hardly changes.

3. The present invention converts the original image or image residual into a one-dimensional signal by extracting the end-to-end signal line by line. At the same time, the atoms in the core atom library are also extracted line-by-line and converted into a one-dimensional atom, which is used later. The one-dimensional fast Hartley transform provides the possibility for decomposition and cross-correlation operations, and saves data storage space, and at the same time, it will not affect the correlation of adjacent pixels, and the effect of image matching operations will not be affected.

In a word, as a global search optimal algorithm, the method of the present invention combines the structural characteristics of the overcomplete library, the matching pursuit technology and the one-dimensional fast Hartley transformation technology to convert the two-dimensional image into a one-dimensional real signal, and improves the sparse decomposition of the image. When the quality and visual effect of the reconstructed image are good, the speed of sparse decomposition is also improved. That is, a better balance is achieved in terms of solution quality and computational complexity.

The present invention will be described in further detail below in conjunction with the accompanying drawings and specific embodiments.

Description of drawings

Fig. 1 shows the original image used when decomposing an actual image by the method of the present invention, the final decomposed atom map, image residual and reconstructed image. Part a is a small block of 32×32 original image to be processed extracted from the standard Lena image (128×128); part b is a schematic diagram of the best matching atom obtained during the 30th image decomposition; Part c is the residual image after the 30th image decomposition; part d is the reconstruction result after the 30th image decomposition, that is, the reconstructed image.

Figure 2 shows the original image used when the same actual image in Figure 1 is decomposed by the matching pursuit image sparse decomposition algorithm based on genetic algorithm, and the final decomposed atom map, image residual and reconstructed image. Part a is the same image as part a in Figure 1; part b is the schematic diagram of the best matching atom obtained during the 30th image decomposition; part c is the residual image after the 30th image decomposition; d The sub-image is the result of reconstruction after the 30th image decomposition, that is, the reconstructed image.

Detailed ways

Example

A fast method for image sparse decomposition based on one-dimensional fast Hartley transform and matching pursuit, including the following steps:

(1) Formation of the core atomic library:

For the original image f with a size of M×N, the atomic library for sparse decomposition is constructed. The basic form of asymmetric atoms is expressed as follows:

$\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}$

A series of atoms g _γ can be obtained by performing rotation, translation and telescopic transformation on basic asymmetric atoms, thus forming an atomic library D={g _γ } _γ∈Γ .

${\mathrm{<span\; class="notranslate">\; g</span>}}_{\mathrm{<span\; class="notranslate">\; \&gamma;</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; g</span>}}_{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; u</span>}}{{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; v</span>}}{{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}}<span\; class="notranslate">\; )</span>$

Thus, the atom g _γ can be defined by the parameter group γ=(θ, u, v, s _x , s _y ), where θ represents the rotation angle of the atom, u and v are the translation of the atom in the x and y directions respectively, and s _x and s _y are respectively the expansion and contraction of atoms in the x and y directions; let u=M/2 and v=N/2 form the core atomic library {g _γ′ }, where the parameter group γ′ is discretized as follows:

${\mathrm{<span\; class="notranslate">\; \&gamma;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&theta;</span>}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; \&pi;\&theta;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}{\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>\frac{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\frac{\mathrm{<span\; class="notranslate">\; sty</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\frac{\mathrm{<span\; class="notranslate">\; sty</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}}<span\; class="notranslate">\; )</span>$

Among them, 1≤θ′≤max(M, N), 0≤stx≤5log ₂ M-5, 0≤sty≤5log ₂ N-5, θ′, stx, and sty all take integers in the corresponding interval.

In the overcomplete atom library, the parameters θ, s _x and s _y define the shape of an atom, while the parameters u and v define the center position of an atom. If different atoms in the atomic library have the same parameters θ, s _x , s _y and different parameters u, v, the characteristics of such atoms are the same in all aspects, only the position of the center point is different. Theoretically, it is absolutely necessary for such different atoms to be included in the atomic library, but from the point of view of practical calculation, it is not necessary at all for the atomic library to contain many such atoms. It violates the meaning of the good structure definition of the atomic library (first, the atomic library should contain as many atoms as possible in order to achieve the purpose of sparse decomposition and obtain a good effect of sparse decomposition; second, the atomic library should try to may not contain similar atoms to meet storage and computation requirements). Therefore, in an atomic library with a good structure, the parameters u and v should be constant, and u=M/2, v=N/2. In this way, the size of the atomic library will be greatly reduced, which is suitable for the requirements of general computer memory. During the sparse decomposition, a good balance between computation and storage is achieved.

(2) Atom and image conversion:

Convert all atoms g _γ′ in the core atomic library formed in step (1) into one-dimensional atoms g′ _γ′ ; convert the original image f whose size is M×N into a one-dimensional signal f′;

The two-dimensional image array is extracted row by row to form a one-dimensional array, which is convenient for subsequent decomposition and cross-correlation operations with one-dimensional fast Hartley transform, and saves data storage space. At the same time, it will not affect the correlation of adjacent pixels, and the effect will be better in image matching operations.

(3) Initial decomposition of the image:

和对应的匹配系数将图像的一维信号f′减去最匹配原子与匹配系数

的乘积，得到图像残差R_f′；The one-dimensional signal f' of the image obtained in step (2) and all the one-dimensional atoms g'_γ' are cross-correlated using the one-dimensional fast Hartley transform algorithm to obtain the one-dimensional signal f' and the overcomplete atomic library {g The matching coefficient p _γ of all one-dimensional atoms g′ _γ in _γ }, and record the one-dimensional atom with the largest absolute value of matching coefficient p _γ Corresponding parameter group

and the corresponding matching coefficient Subtract the best matching atom from the one-dimensional signal f' of the image and matching coefficient

The product of , get the image residual R _f′ ;

(4) Image decomposition:

对应的参数组

和对应的匹配系数

其中i为图像分解的当前次数；将图像残差R_f′减去最匹配原子与匹配系数的乘积，得到更新后的图像残差R_f′；The image residual R _f′ obtained in the current step and all one-dimensional atoms g′ _γ′ are cross-correlated using the one-dimensional fast Hartley transform algorithm to obtain the image residual R _f′ and the overcomplete atomic library {g _γ } The matching coefficient p _γ of each atom in , and record the atom with the largest absolute value of the matching coefficient p _γ

Corresponding parameter group

and the corresponding matching coefficient

where i is the current number of image decompositions; the image residual R _f' is subtracted from the best matching atom and matching coefficient The product of , get the updated image residual R _f′ ;

Repeat the above image decomposition operation, when the image decomposition result meets the subsequent processing requirements, end the operation, and obtain the original image f matching tracking sparse decomposition result $\{(P_{{\mathrm{\&gamma;}}_i},{\mathrm{\&gamma;}}_i)=(P_{{\mathrm{\&gamma;}}_i},{\mathrm{\&theta;}}_i,u_i,v_i,{\mathrm{the\; s}}_{x_i},{\mathrm{the\; s}}_{{\mathrm{the\; y}}_i})|i=\mathrm{0,1,2},...,\mathrm{no}\},$ where n is the total number of image decomposition operations.

In the image sparse decomposition, the process of finding the best atom is to calculate the component of the image f or the residual R _f′ of the image on the corresponding atom g _γ′ , that is, to calculate the inner product <R _f′ , g _γ′ >, which has An atom g _γ′ of the parameters θ, s _x , s _y , u takes the value [0, M-1], and v takes the value [0, N-1], then the atom needs to be compared with the image or image residual value as M ×N inner product <R _f′ , g _γ′ > calculation, so M×N inner product <R _f′ , g _γ′ > calculation can be converted into a cross-correlation operation of R _f′ and g _γ′ . Although theoretically speaking, such a conversion hardly changes the calculation amount, but the calculation efficiency is greatly improved. Since the fast Hartley transform can be used to quickly realize the cross-correlation calculation, we use the fast Hartley transform to further improve the above algorithm. Such improvement will not affect the effect of image sparse decomposition at all, but it can greatly improve the sparseness. speed of decomposition. Because in general, using the fast Hartley transform algorithm to realize the cross-correlation operation can increase the calculation speed by 2 to 3 orders of magnitude.

The one-dimensional fast Hartley transformation of the present invention realizes that cross-correlation operation is an existing algorithm, and its principle is as follows: the discrete Hartley (DHT) transformation of the finite long real sequence x (n) that length is L is defined as:

$x^h\left(k\right)=\mathrm{DHT}\left[x\left(\mathrm{no}\right)\right]=\underset{\mathrm{no}=0}{\overset{L-1}{\mathrm{\&Sigma;}}}x\left(\mathrm{no}\right)\mathrm{cas}\frac{2\mathrm{\&pi;nk}}{N},$ where k=0,1,...,L-1

Extract the parity of the signal, and consider the periodicity to obtain the fast operation method of DHT, fast Hartley transform:

${\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; cos</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; L</span>}}\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; sin</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; L</span>}}\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; L</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>$

It can be seen that the DHT of a sequence of L=2 ^K (K=1, 2, ...) length can be converted into the DHT of 2 parity sampling sequences of L/2 points, and the DHT of each L/2 length sequence can be converted into The DHT of 2 L/4 length sequences can be decomposed successively, and finally can be decomposed into the DHT of a sequence of length 2. Just as the one-dimensional fast Fourier transform can greatly speed up the discrete Fourier transform, the one-dimensional fast Hartley transform can greatly speed up the discrete Hartley transform. In each butterfly unit of the fast Hartley transform, 3 real additions and 2 real multiplications are required, while each butterfly unit of the one-dimensional fast Fourier needs 6 real numbers in total due to complex operations Addition and 4 times of real number multiplication, it can be seen that the one-dimensional fast Hartley transform is faster than the fast Fourier transform.

Let r(n) be the circular cross-correlation of x(n) and y(n), let R ^h (k) be the DHT of r(n), then there is the following DHT circular cross-correlation theorem:

${\mathrm{<span\; class="notranslate">\; R</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; e</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; o</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>$

$r\left(\mathrm{no}\right)=\mathrm{IDHT}\left[R^h\left(k\right)\right]=\frac{1}{N}\mathrm{DHT}\left[R^h\left(k\right)\right],$ where n=0,1,...,L-1

Through the above DHT cyclic cross-correlation theorem, the cross-correlation operation can be quickly realized, so that the inner product operation <R _f′ , g _γ′ > between the image or image residual and a class of atoms can be transformed into an image or image residual and an atom A cross-correlation operation of (that is, a cross-correlation operation of R _f' and g _γ' ), the one-dimensional fast Hartley transform technique is used to realize this cross-correlation operation.

Simulation

Effect of the present invention can be verified by the following simulation experiment results:

The simulation experiment of the method of the present invention and the genetic algorithm is carried out under the same environment (computer software and hardware configuration). In view of the randomness of the genetic algorithm, for the reference value of the experimental data, all the data of the genetic algorithm below are the average value of 20 experiments.

Fig. 1 is the original image used when the method of the present invention performs a simulation experiment on an actual image, the final decomposed atom map, image residual and reconstructed image. Part a is a small block of 32×32 original image to be processed extracted from the standard Lena image (128×128); part b is a schematic diagram of the best matching atom obtained during the 30th image decomposition; Part c is the residual image after the 30th image decomposition; part d is the reconstruction result after the 30th image decomposition, that is, the reconstructed image.

Figure 2 shows the original image used in the simulation experiment of the same actual image in Figure 1 using the matching pursuit image sparse decomposition algorithm based on genetic algorithm, the final decomposed atom map, image residual and reconstructed image. Part a is the same image as part a in Figure 1; part b is the schematic diagram of the best matching atom obtained during the 30th image decomposition; part c is the residual image after the 30th image decomposition; d The sub-image is the result of reconstruction after the 30th image decomposition, that is, the reconstructed image.

Comparing the c subgraph in Fig. 1 and the c subgraph in Fig. 2, it can be seen that the visual effect of the image residual obtained by the algorithm of the present invention is not good. The energy of the image residual is minimized. It shows that the algorithm of the present invention better approximates or approximates the original image under the same number of image decompositions.

Comparing the sub-graph d of Figure 1 and the sub-graph d of Figure 2, it can be seen that under the same number of image decompositions, the reconstructed image visual effect of the matching pursuit image sparse decomposition algorithm based on the genetic algorithm is not very good, and there are some blurs unclear. The visual effect of the reconstructed image by the method of the invention is better than that of the reconstructed image based on the genetic algorithm-based matching pursuit image sparse decomposition algorithm.

The following table 1 is the PSNR of the reconstructed image of the algorithm of the present invention and the matching pursuit algorithm of the genetic algorithm under different image decomposition times (the algebra and the number of individuals of the genetic algorithm test are selected as 40, 21 respectively)

Table 1

It can be seen from Table 1 that under the same image decomposition times, the PSNR of the reconstructed image by the method of the present invention is higher than that of the genetic algorithm. When the number of times of image decomposition was 10 times, the PSNR value of the reconstructed image by the method of the present invention was 2.2161dB higher than that of the genetic algorithm; 5.7381dB higher. And with the increase of image decomposition times, the PSNR of the method of the present invention is more obvious than that of the genetic algorithm.

Table 2 below shows the completion time of image decomposition under different PSNR conditions.

Table 2

The method of the present invention increases PSNR value along with image decomposition number of times and also increases, and the image decomposition times corresponding to each 5 PSNR values of two kinds of algorithms in table 2 is 10,30,50,70,90 successively; And genetic algorithm is in with the present invention When the image decomposition times of the method are the same, the same PSNR value in the above table can be achieved by increasing the algebra and the number of individuals.

As can be seen from Table 2, the method of the present invention is faster than the speed of the genetic algorithm. When the PSNR value was 20.0314, the method of the present invention improved about 15% in image decomposition speed than the genetic algorithm. When the PSNR value was 32.0138, the method of the present invention Compared with the genetic algorithm, the method improves the image decomposition speed more than 1 times. And along with the raising of PSNR value, the speed of the inventive method improves more obviously,

Table 3 below shows the PSNR of reconstructed images at different decomposition speeds.

table 3

The method of the present invention also correspondingly increases along with the increase of the number of times of image decomposition and the completion time of decomposition, the image decomposition times corresponding to the respective 5 decomposition completion time values of the two kinds of algorithms in Table 2 are 10, 30, 50, 70, 90; The genetic algorithm realizes the same decomposition completion time value in the above table by adjusting the algebra and the number of individuals in the test under the same situation that the number of times of image decomposition is the same as that of the method of the present invention.

As can be seen from Table 3, under the same situation of completion time of image decomposition, the PSNR value of the reconstructed image by the method of the present invention is higher than that of the genetic algorithm. The aspect ratio is 0.3019dB higher, and when the decomposition time is 561.0184 seconds, the method of the present invention is 1.0991dB higher than the genetic algorithm in terms of PSNR of the reconstructed image. And as the image decomposition time increases, the PSNR value of the reconstructed image by the method of the present invention increases more obviously.

The number of repeated operations n of the image decomposition of the method of the present invention depends on the requirement of the peak signal-to-noise ratio (PSNR) of the reconstructed image in subsequent processing. When the PSNR requirement is high, the number of repeated operations n of the decomposition is more, and vice versa. For an M×N original image, if the subsequent processing is image compression, the number of repeated operations n is generally less than 2M or 2N; if the subsequent processing is image denoising, the number of repeated operations n is generally greater than M or N, but generally less than 2M or 2N.

Claims (1)

1. the image sparse based on quick hartley transform of one dimension and match tracing decomposes fast method, and its step is as follows:

(1) formation of the former word bank of core:

To size is the original image f of M * N, the former word bank that the structure Sparse Decomposition is used, atom g _γBy parameter group γ=(θ, u, v, s _x, s _y) definition, wherein θ represents the anglec of rotation of atom, and u, v are respectively the translation of atom on x, y direction, s _x, s _yBe respectively atom stretching on x, y direction; Make u=M/2 and v=N/2 form the former word bank { g of core of two dimension _{γ '}, parameter group γ ' discretize by the following method wherein:

${\mathrm{\&gamma;}}^{\&prime;}=(\mathrm{\&theta;},\frac{M}{2},\frac{N}{2},s_x,s_y)=(\frac{{\mathrm{\&pi;\&theta;}}^{\&prime;}}{\max (M,N)},\frac{M}{2},\frac{N}{2},2^{\frac{\mathrm{sty}}{5}},2^{\frac{\mathrm{sty}}{5}})$

Wherein 1≤θ '≤max (M, N), 0≤stx≤5log ₂M-5,0≤sty≤5log ₂N-5, all round numbers on respective bins of θ ', stx, sty;

(2) atom and image transform:

With all the atom g in the former word bank of core of (1) step formation _{γ '}Convert one dimensional atom g ' to _{γ '}With size is that the original image f of M * N converts one-dimensional signal f ' to;

(3) the initial decomposition of image:

(2) are gone on foot the one-dimensional signal f ' and all one dimensional atom g ' of the image that obtains _{γ '}Adopt the quick hartley transform algorithm of one dimension to do computing cross-correlation, obtain one-dimensional signal f ' and over-complete dictionary of atoms { g _γIn all one dimensional atom g ' _γMatching factor p _γ, and record matching factor p _γThe one dimensional atom of absolute value maximum

The corresponding parameters group

Matching factor with correspondence

The one-dimensional signal f ' of image is deducted matched atoms With matching factor

Product, obtain image residual error R _{F '}

(4) picture breakdown:

To the current image residual error R that obtains _{F '}With all one dimensional atom g ' _{γ '}Adopt the quick hartley transform algorithm of one dimension to do computing cross-correlation, obtain image residual error R _{F '}With over-complete dictionary of atoms { g _γIn the matching factor p of each atom _γ, and record matching factor p _γThe atom of absolute value maximum

The corresponding parameters group

Matching factor with correspondence

Wherein i is the current number of times of picture breakdown; With image residual error R _{F '}Deduct matched atoms

With matching factor

Product, the image residual error R after obtaining upgrading _{F '}

Repeat above picture breakdown operation, when the picture breakdown result satisfied subsequent treatment and requires, end operation obtained the result of original image f match tracing Sparse Decomposition $\{(P_{{\mathrm{\&gamma;}}_i},{\mathrm{\&gamma;}}_i)=(P_{{\mathrm{\&gamma;}}_i},{\mathrm{\&theta;}}_i,u_i,v_i,s_{x_i},s_{y_i})|i=\mathrm{0,1,2},...,n\},$ Wherein n is the total degree of picture breakdown operation.

Images