METHOD FOR MEASURING THE SIMILARITY OF IMAGES/IMAGE BLOCKS

Abstract

The present application relates to a method for measuring the similarity of images/image blocks, which comprises: S1: acquiring two three-dimensional airspace images V and W; S2: decomposing the images V and W to obtain a plurality of sub-bands; S3: calculating a Laplacian probability corresponding to each high-frequency sub-band of V and W, weighting the high-frequency sub-hand; S4: marking two image blocks as X and Y, taking out data blocks corresponding to the image blocks X and Y, and calculating the statistics of the data blocks; S5: calculating the similarities of X and Yin each channel of each sub-band according to the statistics of the data blocks; S6: calculating an average value of the similarities of X and Y in each channel of each sub-band, and taking the average value as the similarity between X and Y.

Claims

1. A computer-implemented method for measuring a similarity of images/image blocks, comprising the following steps: S1: acquiring two three-dimensional airspace images, which are respectively marked as V and W; S2: decomposing the three-dimensional airspace images V and W by using a three-dimensional tight frame to obtain a plurality of sub-bands, wherein the sub-bands comprise a plurality of high-frequency sub-bands and low-frequency sub-bands; S3: calculating a Laplacian probability corresponding to each of the plurality of high-frequency sub-bands; using the Laplacian probability to weight each of the plurality of high-frequency sub-bands; S4: marking two image blocks to be measured for similarity as X and Y respectively taking out data blocks corresponding to the image blocks X and Y from each channel of the low-frequency and high-frequency sub-bands of three-dimensional airspace images V and W, and calculating statistics of the data blocks; S5: calculating the similarities of image blocks X and Y in each channel of each sub-band according to the statistics of the data blocks; S6: calculating an average value of the similarities of image blocks X and Y in each channel of each sub-band.

2. The method of claim 1, wherein the said decomposing the three-dimensional airspace images V and W by using a three-dimensional tight frame in step S2 comprises: when a first layer is decomposed, obtaining a first low-frequency sub-band and thirteen high-frequency sub-bands; and when a second layer is decomposed, performing characteristic extraction on the first low-frequency sub-band obtained from the first layer to obtain a second low-frequency sub-band and another thirteen high-frequency sub-bands.

3. The method of claim 2, wherein a three-dimensional rectangular coordinate system is constructed, with an X axis and a Y axis in the horizontal direction and a Z axis in the vertical direction, the thirteen high-frequency sub-bands in each layer have the characteristics of the three-dimensional airspace image in all directions: one high-frequency sub-band in each of the X, Y and Z directions, two high-frequency sub-bands in each of the ZY, XZ and YZ directions, and four high-frequency sub-bands in the XYZ direction.

4. The method of claim 3, wherein the decomposing the three-dimensional airspace images V and W by using a three-dimensional tight frame is to extract hierarchical characteristics of every group of eight data points in the three-dimensional airspace image; wherein the eight data are taken as eight vertices of a cuboid, and there are four data points on an upper surface and a lower surface of the cuboid, which come from two channels of each of the images respectively; when decomposing an n.sup.th layer by the three-dimensional tight frame, neighboring two data points have an interval of 2.sup.n−1−1 pixels; for each data point in the three-dimensional tight frame characteristic, according to the above interval requirement, eight data points can be obtained from the three-dimensional airspace image or the lower frequency sub-band of the previous layer, and calculated from the eight data points.

5. The method of claim 4, wherein the high-frequency sub-band comprises the change of the airspace image or the low-frequency sub-band of the previous layer in all directions, which is the difference of every combination of two data points in every group of eight data points in the three-dimensional airspace image, and a gradient information of the image is captured; while each point in the low-frequency sub-band is an average value of the group of eight data points, and the low-frequency sub-band is fuzzy.

6. The method of claim 5, wherein the operation of calculating a Laplacian probability corresponding to each high-frequency sub-band in step S3 comprises an image V is an RGB color image, and the two-dimensional resolution thereof is set as n.sub.1 rows and n.sub.2 columns, accordingly V∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3; an i.sup.th sub-band of the three-dimensional tight frame characteristics of the image V is represented by V.sub.i(V.sub.i∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3), wherein V.sub.i,j(V.sub.i,j∈R.sup.n.sup.1.sup.×n.sup.2) represents a j.sup.th (j=1, 2, 3) channel of V.sub.i, and V.sub.i,j is stacked into a vector by column to obtain v.sub.i,j(v.sub.i,j∈R.sup.n.sup.1.sup.n.sub.2); V.sub.i,j has the mean value of: ${\mu }_{V_{i,j}}=\frac{\underset{k=1}{\overset{n_1{n}_2}{.Math.}}{v}_{i,j}\left[k\right]}{n_1{n}_2},$ where, v.sub.i,j[k] indicates a k.sup.th element in v.sub.i,j, and n.sub.1n.sub.2 is the number points of v.sub.i,j; assuming that the data points in V.sub.i,j conforms to Laplace distribution, then the standard deviation of V.sub.i,j is: ${\sigma }_{V_{i,j}}=\sqrt{2}.Math.\frac{\underset{k=1}{\overset{n_1{n}_2}{.Math.}}.Math.v_{i,j}\left[k\right]-{\mu }_{V_{i,j}}.Math.}{n_1{n}_2},$ where, |.Math.| represents an absolute value; the standard deviation of V.sub.i,j is equal to √{square root over (2)} times of the average value of the absolute value of the midpoint of V.sub.i,j after centralization; a standard deviation or a local standard deviation of a w.sub.1×w.sub.2 window with a center being a point V.sub.i,j[m, n] in V.sub.i,j is calculated: ${\hat{\sigma }}_{V_{i,j}}\left[m,n\right]=\sqrt{2}.Math.\underset{\hat{m}=m-.Math.w_1/2.Math.}{\overset{\hat{m}=m+.Math.w_1/2.Math.}{.Math.}}\underset{\hat{n}=n-.Math.w_2/2.Math.}{\overset{\hat{n}=n+.Math.w_2/2.Math.}{.Math.}}\frac{.Math.V_{i,j}\left[\hat{m},\hat{n}\right].Math.}{w_1{w}_2},$ where, V.sub.i,j[{circumflex over (m)}, {circumflex over (n)}] represents a point in an {circumflex over (m)}.sup.th row and an {circumflex over (n)}.sup.th column of V.sub.i,j, {circumflex over (σ)}.sub.V.sub.i,j represents a standard deviation of each local window of V.sub.i,j; the local standard deviation is substituted into a Laplacian probability model, and the Laplacian probability of V.sub.i,j is estimated as P.sub.i,j: $P_{i,j}\left[m,n\right]=\frac{1}{\sqrt{2}.Math.{\sigma }_{V_{i,j}}}\exp \left(-\frac{\sqrt{2}.Math..Math.{\hat{\sigma }}_{V_{i,j}}\left[m,n\right]-{\mu }_{V_{i,j}}.Math.}{{\sigma }_{V_{i,j}}}\right),$ where, P.sub.i,j[m, n] is the point of an m.sup.th row and an n.sup.th column in P.sub.i,j; similarly, the Laplacian probability distribution of each channel of each sub-band of image W can be obtained.

7. The method of claim 6, wherein the statistics of the data block in S4 comprise a mean, a variance, a horizontal autocorrelation and a vertical autocorrelation.

8. The method of claim 7, wherein the mean, variance, horizontal autocorrelation and vertical autocorrelation have following calculation methods: image V and W are RGB color images, and they have same resolutions; the two-dimensional resolutions of the images are set to be n.sub.1 rows and n.sub.2 columns, i.e., V,W∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3; V.sub.i(V.sub.i∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3) represents an i.sup.th sub-band of the three-dimensional tight frame characteristic of the image V, and V.sub.i,j(V.sub.i,j∈R.sup.n.sup.1.sup.×n.sub.2) represents the j.sup.th(j=1, 2, 3) channel of V.sub.i; W.sub.i(W.sub.i∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3) represents an i.sup.th sub-band of the three-dimensional tight frame characteristic of the image W, and W.sub.i,j(V.sub.i,j∈R.sup.n.sup.1.sup.×n.sub.2) represents the j.sup.th(j=1, 2, 3) channel of V.sub.i; image blocks in a row p.sub.1 and a column p.sub.2 are taken out from V.sub.i,j and W.sub.i,j and are recorded as X.sub.i,j(X.sub.i,j∈R.sup.p.sup.1.sup.×p.sup.2) and Y.sub.i,j(Y.sub.i,j∈R.sup.p.sup.1.sup.×p.sup.2) respectively, and X.sub.i,j and Y.sub.i,j are stacked into vectors by column to obtain x.sub.i,j and y.sub.i,j(x.sub.i,j,y.sub.i,j∈R.sup.p.sup.1.sup.p.sup.2); the data block X.sub.i,j has a mean value of: ${\mu }_{X_{i,j}}=\frac{\underset{k=1}{\overset{p_1{p}_2}{.Math.}}{x}_{i,j}\left[k\right]}{p_1{p}_2},$ where x.sub.i,j[k] represents a k.sup.th element in x.sub.i,j; the mean value μ.sub.Y.sub.i,j of the data block Y.sub.i,j can be calculated in a similar way; the data block X.sub.i,j has a variance of: ${\sigma }_{X_{i,j}}^2=\frac{\underset{k=1}{\overset{p_1{p}_2}{.Math.}}{\left(x_{i,j}\left[k\right]-{\mu }_{X_{i,j}}\right)}^2}{p_1{p}_2},,$ the variance σ.sub.Y.sub.i,j.sup.2 of the data block Y.sub.i,j can be calculated in a similar way; the data block X.sub.i,j has a horizontal autocorrelation of: $\begin{array}{c}{p}_{X_{i,j}\left(0,1\right)}=\frac{\mathrm{��}\left\{\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m,n+1\right]-{\mu }_{X_{i,j}}\right)\right\}}{{\sigma }_{X_{i,j}}^2}\\ =\frac{\underset{m}{.Math.}\underset{n}{.Math.}\left[\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m,n+1\right]-{\mu }_{X_{i,j}}\right)\right]}{p_1\left(p_2-1\right).Math.{\sigma }_{X_{i,j}}^2},\end{array}$ where E{.Math.} represents the calculation of expected value, and X.sub.i,j[m,n] represents the value of the m.sup.th row and the n.sup.th column in X.sub.i,j; the horizontal autocorrelation of X.sub.i,j is equal to the average value of the product of every group of two points in the left and right in X.sub.i,j after centralization, divided by the variance of X.sub.i,j; the data block X.sub.i,j has a vertical autocorrelation of: $\begin{array}{c}{p}_{X_{i,j}\left(1,0\right)}=\frac{\mathrm{��}\left\{\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m+1,n\right]-{\mu }_{X_{i,j}}\right)\right\}}{{\sigma }_{X_{i,j}}^2}\\ =\frac{\underset{m}{.Math.}\underset{n}{.Math.}\left[\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m+1,n\right]-{\mu }_{X_{i,j}}\right)\right]}{\left(p_1-1\right)p_2.Math.{\sigma }_{X_{i,j}}^2},\end{array}$ the vertical autocorrelation of X.sub.i,j is equal to the average value of the product of every two points in the upper and lower in X.sub.i,j after centralization, divided by the variance of X.sub.i,j; the horizontal autocorrelation ρ.sub.Y.sub.i,j.sub.(0,1) and vertical autocorrelation ρ.sub.Y.sub.i,j.sub.(1,0) of Y.sub.i,j can be calculated in a similar way.

9. The method of claim 8, wherein the step S5 is as below: the similarity between the mean values of the data block X.sub.i,j and the data block Y.sub.i,j is: $s_{\mathrm{mean}}\left(X_{i,j},Y_{i,j}\right)=\frac{2{\mu }_{X_{i,j}}{\mu }_{Y_{i,j}}+c_1}{{\left({\mu }_{X_{i,j}}\right)}^2+{\left({\mu }_{Y_{i,j}}\right)}^2+c_1},$ where, c.sub.1 represents a small constant; the similarity between the variances of the data block X.sub.i,j and the data block Y.sub.i,j is: $s_{\mathrm{var}}\left(X_{i,j},Y_{i,j}\right)=\frac{2{\sigma }_{X_{i,j}}{\sigma }_{Y_{i,j}}+c_2}{{\left({\sigma }_{X_{i,j}}\right)}^2+{\left({\sigma }_{Y_{i,j}}\right)}^2+c_2},$ where, c.sub.2 represents a small constant; the similarity between the horizontal autocorrelations of the data block X.sub.i,j and the data block Y.sub.i,j is:
s.sub.hor(X.sub.i,j,Y.sub.i,j)=1−0.5(|ρ.sub.X.sub.i,j.sub.(0,1)−ρ.sub.Y.sub.i,j.sub.(0,1)|) the similarity between the vertical autocorrelations of the data block X.sub.i,j and the data block Y.sub.i,j is:
s.sub.ver(X.sub.i,j,Y.sub.i,j)=1−0.5(|ρ.sub.X.sub.i,j.sub.(1,0)−ρ.sub.Y.sub.i,j.sub.(1,0)|) where, |.Math.| means to find an absolute value.

10. The method of claim 9, wherein the similarity between image blocks X and Y is: $\mathrm{sim}\left(X,Y\right)=\frac{1}{\#I\#J}\underset{i=1}{\overset{\#I}{.Math.}}\underset{j=1}{\overset{\#J}{.Math.}}{s}_{\mathrm{mean}}\left(X_{i,j},Y_{i,j}\right)s_{\mathrm{var}}\left(X_{i,j},Y_{i,j}\right)s_{\mathrm{hor}}\left(X_{i,j},Y_{i,j}\right)s_{\mathrm{ver}}\left(X_{i,j},Y_{i,j}\right),$ where, #I is the number of sub-bands of the three-dimensional tight frame that is being used, and #J is the number of channels of each sub-band.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0069] FIG. 1 is a flow chart of a method for measuring similarity of images/image blocks according to Example 1.

[0070] FIG. 2 is a schematic diagram of feature extraction of a three-dimensional tight frame.

[0071] FIG. 3 is an example diagram of data points of a three-dimensional tight frame.

DETAILED DESCRIPTION OF EMBODIMENTS

[0072] The drawings are for illustration only, and should not be construed as the limitation of this patent.

[0073] In order to better illustrate the present example, some parts in the drawings may be omitted, enlarged or reduced, and do not represent the actual product size.

[0074] For those skilled in the art, it should be appreciated that some well-known structures in the drawings and their descriptions may be omitted.

[0075] Next, the technical solution of the present application will be further explained with reference to the drawings and examples.

EXAMPLE 1

[0076] This example provides a method for measuring the similarity of images/ image blocks. As shown in FIG. 1, the method includes the following steps:

[0077] S1, acquiring two three-dimensional airspace images, which are respectively marked as V and W;

[0078] S2, decomposing the three-dimensional airspace images V and W by using a three-dimensional tight frame to obtain a plurality of sub-bands, wherein the sub-bands comprise high-frequency sub-bands and low-frequency sub-bands;

[0079] in the step of decomposing the three-dimensional airspace images by using the three-dimensional tight frame, when a first layer is decomposed, obtaining one low-frequency sub-band and thirteen high-frequency sub-bands, wherein thirteen high-frequency sub-hands are the characteristics of the three-dimensional airspace image in all directions: one high-frequency sub-band in each of the X, Y and Z directions, two high-frequency sub-bands in each of the XY, XZ and YZ directions, and 4 high-frequency sub-bands in the XYZ direction.

[0080] From decomposition of a second layer, characteristic extraction is performed based on the low-frequency sub-bands of the previous layer, and one low-frequency sub-band and thirteen high-frequency sub-bands are obtained in each layer decomposition, i.e., when the three-dimensional airspace image is decomposed into n layers, one low-frequency sub-band and 13n high-frequency sub-bands can be obtained.

[0081] As shown in FIG. 2, the essence of decomposing the three-dimensional airspace image by using the three-dimensional tight frame is to extract hierarchical characteristics of every eight data points in the three-dimensional airspace image; 8 data are taken as eight vertices of a cuboid, and there are four data points on the upper surface and the lower surface of the cuboid, which come from two channels of the image respectively; when decomposing the n.sup.th layer of the three-dimensional tight frame, the interval between adjacent data points is 2.sup.n−1−1 pixels.

[0082] For each data point in the three-dimensional tight frame characteristic, according to the above interval requirements, eight data points can be obtained from the three-dimensional airspace image or the lower frequency sub-band of the upper layer, and calculated from the 8 data points.

[0083] As shown in FIG. 3, taking point al as an example, the values corresponding to the positions of a1 in the low-frequency and high-frequency sub-bands are calculated, and it is necessary to obtain eight data points corresponding to a1 from the three-dimensional airspace image or the low-frequency sub-band of the upper layer: a1, a2, a3, a4, b1, b2, b3, b4, b5. The high-frequency and low-frequency information at al position is calculated as follows:

[0084] the high frequency information in X direction is: (a2−a1)/8;

[0085] the high frequency information in Y direction is: (a3−a1)/8;

[0086] the high frequency information in Z direction is: (b1−a1)/8;

[0087] the high frequency information in XY direction is (a4−a1)/8 and (a2−a3,/8

[0088] the high frequency information in XZ direction is (b2−a1)/8 and (a2−b1),/8;

[0089] the high frequency information in YZ direction is (b3−a1)/8 and (a3−b1);/8

[0090] the high frequency characteristics in XYZ direction are (b4−a1)/8, (a4−b1)/8, (b2−a3)/8 and (a2−b3);/8

[0091] the low frequency information is (a1+a2+a3+a4+b1+b2+b3+b4)/8.

[0092] S3, calculating a Laplacian probability corresponding to each high-frequency sub-band of V and W; using the Laplacian probability to weight the high-frequency sub-band, that is, using the Laplacian probability and corresponding channel information thereof for dot multiplication.

[0093] After feature extraction of a three-dimensional airspace image by a three-dimensional tight frame, one low-frequency sub-band and several high-frequency sub-bands will be obtained. Firstly, the Laplacian probability distribution of each channel of each high-frequency sub-band is calculated and the probability distribution and its corresponding channel information are used to weight, that is, the Laplacian probability is used to dot multiply the three-dimensional tight frame characteristics.

[0094] The operation of calculating a Laplacian probability corresponding to each high-frequency sub-band is as below:

[0095] an image V is an RGB color image, and the two-dimensional resolution thereof is set as n.sub.1 rows and n.sub.2 columns, i.e., V∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3;

[0096] an sub-band of the three-dimensional tight frame characteristics of the image V is represented by V.sub.i(V.sub.i∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3), wherein V.sub.i,j(V.sub.i,j∈R.sup.n.sup.1.sup.×n.sup.2) represents a j(j=1, 2, 3).sup.th channel of V.sub.i, and V.sub.i,j is stacked into a vector by column to obtain V.sub.i,j(v.sub.i,j∈R.sup.n.sup.1.sup.n.sup.2);

[0097] the mean value of V.sub.i,j is:

[00012]${\mu }_{V_{i,j}}=\frac{\underset{k=1}{\overset{n_1{n}_2}{.Math.}}{v}_{i,j}\left[k\right]}{n_1{n}_2}$

[0098] where, v.sub.i,j[k] indicates a k.sup.th element in v.sub.i,j, and n.sub.1n.sub.2 is the number points of v.sub.i,j;

[0099] assuming that the data points in V.sub.i,j conforms to Laplace distribution, then the standard deviation of V.sub.i,j is:

[00013]${\sigma }_{V_{i,j}}=\sqrt{2}.Math.\frac{\underset{k=1}{\overset{n_1{n}_2}{.Math.}}.Math.v_{i,j}\left[k\right]-{\mu }_{V_{i,j}}.Math.}{n_1{n}_2}$

where, |.Math.| represents an absolute value;

[0100] the standard deviation of is equal to V.sub.i,j is equal to √{square root over (2)} times of the average value of the absolute value of the midpoint of V.sub.i,j after centralization;

[0101] a standard deviation (a local standard deviation) of a w.sub.1×w.sub.2 window with a center being a point V.sub.i,j[m, n] in V.sub.i,j:

[00014]${\hat{\sigma }}_{V_{i,j}}\left[m,n\right]=\sqrt{2}.Math.\underset{\hat{m}=m-.Math.w_1/2.Math.}{\overset{\hat{m}=m+.Math.w_1/2.Math.}{.Math.}}\underset{\hat{n}=n-.Math.w_2/2.Math.}{\overset{\hat{n}=n+.Math.w_2/2.Math.}{.Math.}}\frac{.Math.V_{i,j}\left[\hat{m},\hat{n}\right].Math.}{w_1{w}_2}$

[0102] where, V.sub.i,j[{circumflex over (m)}, {circumflex over (n)}] represents a point in a {circumflex over (m)}.sup.th row and a {circumflex over (n)}.sup.th column of V.sub.i,j, {circumflex over (σ)}.sub.V.sub.i,j is a standard deviation of each local window of {circumflex over (σ)}.sub.V.sub.i,j;

[0103] the local standard deviation is substituted into a Laplacian probability model, and the Laplacian probability of V.sub.i,j is estimated as P.sub.i,j;

[00015]$P_{i,j}\left[m,n\right]=\frac{1}{\sqrt{2}.Math.{\sigma }_{V_{i,j}}}\exp \left(-\frac{\sqrt{2}.Math..Math.{\hat{\sigma }}_{V_{i,j}}\left[m,n\right]-{\mu }_{V_{i,j}}.Math.}{{\sigma }_{V_{i,j}}}\right)$

[0104] where, P.sub.i,j[m, n] is the point of an m.sup.th row and an n.sup.th column in P.sub.i,j;

[0105] similarly, the Laplacian probability distribution of each channel of each sub-band of image W can be obtained.

[0106] S4: marking two image blocks to be measured for similarity as X and Y, respectively taking out data blocks corresponding to the image blocks X and Y from each channel of the low-frequency and high-frequency sub-bands of V and W, and calculating the statistics of the data blocks: a mean, a variance, a horizontal autocorrelation and a vertical autocorrelation.

[0107] The calculation methods of a mean, a variance, a horizontal autocorrelation and a vertical autocorrelation are as follows:

[0108] image V and W are RGB color images, and the resolutions of the two images are the same; let the two-dimensional resolutions of the images be n.sub.1 rows and n.sub.2 columns, i.e., V,W∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3;

[0109] an i.sup.th sub-band of the three-dimensional tight frame characteristic of the image V is represented using V.sub.i(V.sub.i∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3), and V.sub.i,j(V.sub.i,j∈R.sup.n.sup.1.sup.×n.sup.2) represents the j(j=1,2,3).sup.th channel of V.sub.i;

[0110] an sub-band of the three-dimensional tight frame characteristic of the image W is represented using W.sub.i(W.sub.i∈R.sup.n.sup.1.sup.×n.sup.2.sup.×3), and W.sub.i,j(W.sub.i,j∈R.sup.n.sup.1.sup.×n.sup.2) represents the j(j=1,2,3).sup.th channel of V.sub.i;

[0111] image blocks in a row p.sub.1 and a column p.sub.2 are taken out respectively from V.sub.i,j and W.sub.i,j and are recorded as X.sub.i,j(X.sub.i,j∈R.sup.p.sup.1.sup.×p.sup.2) and Y.sub.i,j(Y.sub.i,j∈R.sup.p.sup.1.sup.×p.sup.2) respectively, and X.sub.i,j and Y.sub.i,j are stacked into vectors by column to obtain x.sub.i,j and y.sub.i,j(x.sub.i,j,y.sub.i,j∈R.sup.p.sup.1.sup.p.sup.2);

[0112] a mean value of the data block X.sub.i,j is:

[00016]${\mu }_{X_{i,j}}=\frac{\underset{k=1}{\overset{p_1{p}_2}{.Math.}}{x}_{i,j}\left[k\right]}{p_1{p}_2}$

[0113] where x.sub.i,j[k] represents the k.sup.th element in x.sub.i,j; similarly, the mean value μ.sub.Y.sub.i,j of the data block Y.sub.i,j can be calculated;

[0114] the variance of the data block X.sub.i,j is:

[00017]${\sigma }_{X_{i,j}}^2=\frac{\underset{k=1}{\overset{p_1{p}_2}{.Math.}}{\left(x_{i,j}\left[k\right]-{\mu }_{X_{i,j}}\right)}^2}{p_1{p}_2}$

[0115] similarly, the variance σ.sub.Y.sub.i,j.sup.2 of the data block Y.sub.i,j can be calculated;

[0116] the horizontal autocorrelation of the data block X.sub.i,j is:

[00018]$\begin{array}{c}{\rho }_{X_{i,j}\left(0,1\right)}=\frac{\mathrm{��}\left\{\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m,n+1\right]-{\mu }_{X_{i,j}}\right)\right\}}{{\sigma }_{X_{i,j}}^2}\\ =\frac{\underset{m}{.Math.}\underset{n}{.Math.}\left[\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m,n+1\right]-{\mu }_{X_{i,j}}\right)\right]}{p_1\left(p_2-1\right).Math.{\sigma }_{X_{i,j}}^2}\end{array}$

[0117] where E{.Math.} represents the calculation of expected value, and X.sub.i,j[m, n] represents the value of the m.sup.th row and the n.sup.th column in X.sub.i,j;

[0118] the horizontal autocorrelation of X.sub.i,j is equal to the average value of the product of every two points in the left and right in X.sub.i,j after centralization, divided by the variance of X.sub.i,j;

[0119] the vertical autocorrelation of the data block X.sub.i,j is:

[00019]$\begin{array}{c}{p}_{X_{i,j}\left(1,0\right)}=\frac{\mathrm{��}\left\{\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m+1,n\right]-{\mu }_{X_{i,j}}\right)\right\}}{{\sigma }_{X_{i,j}}^2}\\ =\frac{\underset{m}{.Math.}\underset{n}{.Math.}\left[\left(X_{i,j}\left[m,n\right]-{\mu }_{X_{i,j}}\right)\left(X_{i,j}\left[m+1,n\right]-{\mu }_{X_{i,j}}\right)\right]}{\left(p_1-1\right)p_2.Math.{\sigma }_{X_{i,j}}^2}\end{array}$

[0120] the vertical autocorrelation of X.sub.i,j is equal to the average value of the product of every two points in the upper and lower in X.sub.i,j after centralization, divided by the variance of X.sub.i,j;

[0121] similarly, the horizontal autocorrelation ρ.sub.Y.sub.i,j.sub.(0,1) and vertical autocorrelation ρ.sub.Y.sub.i,j.sub.(1,0) of Y.sub.i,j can be calculated.

[0122] S5: calculating the similarities of X and Y in each channel of each sub-band according to the statistics of the data blocks;

[0123] The similarities, i.e., mean similarity, variance similarity, horizontal autocorrelation similarity and vertical autocorrelation similarity, between the corresponding statistics of two image blocks on each sub-band channel are calculated, and these four similarities are multiplied to get the similarity of two image blocks on each channel.

[0124] The similarity between the mean values of the data block X.sub.i,j and the data block Y.sub.i,j is:

[00020]$s_{\mathrm{mean}}\left(X_{i,j},Y_{i,j}\right)=\frac{2{\mu }_{X_{i,j}}{\mu }_{Y_{i,j}}+c_1}{{\left({\mu }_{X_{i,j}}\right)}^2+{\left({\mu }_{Y_{i,j}}\right)}^2+c_1}$

[0125] where, c.sub.1 represents a small constant;

[0126] the similarity between the variances of the data block X.sub.i,j and the data block Y.sub.i,j is:

[00021]$s_{\mathrm{var}}\left(X_{i,j},Y_{i,j}\right)=\frac{2{\sigma }_{X_{i,j}}{\sigma }_{Y_{i,j}}+c_2}{{\left({\sigma }_{X_{i,j}}\right)}^2+{\left({\sigma }_{Y_{i,j}}\right)}^2+c_2}$

[0127] where, c.sub.2 represents a small constant;

[0128] the similarity between the horizontal autocorrelations of the data block X.sub.i,j and the data block Y.sub.i,j is:

s.sub.hor(X.sub.i,j,Y.sub.i,j)=1−0.5(|ρ.sub.X.sub.i,j.sub.(0,1)−ρ.sub.Y.sub.i,j.sub.(0,1)|)

[0129] the similarity between the vertical autocorrelations of the data block X.sub.i,j and the data block Y.sub.i,j is:

s.sub.ver(X.sub.i,j,Y.sub.i,j)=1−0.5(|ρ.sub.X.sub.i,j.sub.(1,0)−ρ.sub.Y.sub.i,j.sub.(1,0)|)

[0130] where, |.Math.| means to find an absolute value.

[0131] S6: calculating an average value of the similarities of X and Y in each channel of each sub-band as the similarity between X and Y.

[0132] Then, the similarity of each channel is averaged to obtain the similarity of the final two image blocks.

[0133] The similarity between image blocks X and Y is:

[00022]$\mathrm{sim}\left(X,Y\right)=\frac{1}{\#I\#J}\underset{i=1}{\overset{\#I}{.Math.}}\underset{j=1}{\overset{\#J}{.Math.}}{s}_{\mathrm{mean}}\left(X_{i,j},Y_{i,j}\right)s_{\mathrm{var}}\left(X_{i,j},Y_{i,j}\right)s_{\mathrm{hor}}\left(X_{i,j},Y_{i,j}\right)s_{\mathrm{ver}}\left(X_{i,j},Y_{i,j}\right)$

[0134] where, #I is the number of sub-bands of the three-dimensional tight frame that is being used, and #J is the number of channels of each sub-band.

[0135] In this embodiment, a three-dimensional tight frame is used to extract three-dimensional features of color images, and statistics on three-dimensional features (such as a mean value, a variance, etc.) are calculated, and the similarity between images or image blocks in the statistics of the three-dimensional tight frame characteristics is calculated as the similarity between images or image blocks.

[0136] The three-dimensional tight frame characteristics make better use of the correlation information between each channel of color images, which is conducive to improving the accuracy of image block similarity measurement and ultimately improving the quality of image inpainting.

[0137] The terms used to describe the positional relationship in the drawings are only used for illustration, and should not be construed as a limitation of this patent.

[0138] It should be appreciated that, implementations of the method described in this specification can be implemented in other types of digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them.

[0139] Obviously, the above examples of the present application are only examples for clearly explaining the present application, and are not limitations on the embodiments of the present application. For those of ordinary skill in the field, other changes or changes in different forms can be made on the basis of the above description. It is not necessary and impossible to exhaust all the embodiments here. Any modification, equivalent substitution and improvement within the spirit and principle of the present application should be included within the scope of protection of the claims of the present application.