Spectral information recovery for compressed image restoration with nonlinear partial differential equation regularization

Joint Photographs Expert Group (JPEG) is widely used for image compression for images accessible via the Internet owing to good performance with moderate implementation complexity. JPEG uses the block-based discrete cosine transform (DCT) coding architecture, which suffers from block artifacts when the compression ratio is high. This can be seen in the blocking and ringing that exists in many JPEG images available via the Internet.

Briefly, aspects of the subject matter described herein relate to image restoration for compressed images. In aspects, image restoration is accomplished by recovering spectral information from data corresponding to a compressed image. The spectral information is recovered using an algorithm to search through a solution space of possible solutions while constraints are imposed on the solution space to trim undesirable solutions from the space. The algorithm may be iteratively applied to improve the quality of the recovered image.

This Summary is provided to briefly identify some aspects of the subject matter that is further described below in the Detailed Description. This Summary is not intended to identify key or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

The phrase “subject matter described herein” refers to subject matter described in the Detailed Description unless the context clearly indicates otherwise. The term “aspects” is to be read as “at least one aspect.” Identifying aspects of the subject matter described in the Detailed Description is not intended to identify key or essential features of the claimed subject matter.

The aspects described above and other aspects of the subject matter described herein are illustrated by way of example and not limited in the accompanying figures in which like reference numerals indicate similar elements and in which:

FIG. 1 is a diagram that generally represents finding a route using constraints according to aspects of the subject matter described herein;

FIG. 2 is a diagram plotting discrete cosine transform basis vectors with a partial enlargement of four of the basis vectors according to aspects of the subject matter described herein;

FIG. 3 illustrates a scheme of DC based low frequency AC prediction according to aspects of the subject matter described herein;

FIG. 4 is a block diagram illustrating exemplary components that may be included in an apparatus arranged in accordance with aspects of the subject matter described herein;

FIG. 5 is a flow diagram that generally represents one exemplary embodiment of actions that may occur in image restoration in accordance with aspects of the subject matter described herein; and

FIG. 6 is a flow diagram that generally represents another exemplary embodiment of actions that may occur in image restoration in accordance with aspects of the subject matter described herein

As mentioned previously, JPEG images often exhibit artifacts that are undesirable. Removing or diminishing these artifacts is a challenge. Image degradation may be formulated as follows:

g=Hf+n.   (1)

The vectors g and f denote the observed and the original images, respectively. H is a convolution matrix to model the blurring, and n represents random additive noise. Recovering the original signal f from the noisy signal g is a difficult challenge. To attempt to recover f, nonlinear regularization with partial differential equations (PDE) may be employed. Recovering f in this manner may preserve significant global features while smoothing unimportant data. Nonlinear regularization may involve functional minimization, variational approaches, oriented Laplacians, other techniques, some combination of the above, and the like.

In JPEG images, at least some of the distortion is caused by the quantization of coefficients. By using the compression standard and parsing data compressed via an algorithm such as JPEG, the quantization algorithm and its parameters can be ascertained. Image restoration may be performed by considering the recovery of spectral information. In order to achieve this, image recovery may be translated to route establishment in a high dimensional vector space that is spanned by all DCT coefficients. In one embodiment, total variation regularization may be used to obtain an initial estimate the route nodes. This route may then be refined using two spectral constraints. The first constraint is quantization bound, and the second one is a low-frequency AC coefficient limitation, which is obtained via a prediction method described herein.

In JPEG, block-based DCTs are used, where an image is divided into blocks with a fixed size for the discrete cosine transform. In addition, the transformed coefficients are quantized to scalar values, which can be scaled up to reconstruct an image in a decoder. Let the original image scan be is denoted as f. It consists of K×L blocks with block size equal to N×N.

a m,n is the (m,n)-th image block. The transform results of original block a m,n are expressed as A m,n

The symbol H stands for transform operator, while H −1 represents an inverse transform. Q[•] is quantization operator implemented on the transformed coefficients

 m,n =Q[Ha m,n ].  (4)

 m,n is the quantized version of the transformed coefficient block, a m,n , while the relevant decoded block is â m,n . The reconstruction in the JPEG standard can be expressed as follows:

â m,n H −1 Q[Ha m,n ].  (5)

The reconstructed image g is composed of K×L decoded blocks. As the result of quantization error, both blocking and ringing artifacts may exist in the reconstructed image g when the compression ratio is high

Spectral information (A m,n ) recovery may be used to compensate the quantization error.

For each N×N block in an image, the DCT coefficients matrix A m,n can be regarded as a vector in N 2 -dimensional vector space N 2 . According to the quantization rule, the high dimensional vector space is divided into numerous sub-spaces by quantization intervals of coefficients, and one typical vector may be chosen to represent all vectors within one sub-space. The quantization is equivalent to the behavior of locating A m,n and outputting the typical vector  m,n . Since  m,n is prior knowledge on the original DCT coefficients A m,n , the recovery question turns to in what ways the initial state  m,n can approach to A m,n in a bounded high dimensional space.

FIG. 1 is a diagram that generally represents finding a route using constraints according to aspects of the subject matter described herein. The cube 105 is part of a bounded sub-space. The circles in the cube represent possible states of A. The filled in circles represent the determined recovery route from A to Â. The original DCT coefficient vector is denoted as A, and the quantized coefficient vector is Â. In order to determine A from Â, a recovery route is built. In one embodiment, minimizing the distance between A and  by iteration may produce a group of estimated nodes à i , which can form a near-optimal recovery route. However, minimization of the distance may be impractical because the original coefficient vector A may be unavailable in the decoder.

Besides the initial route construction, the pruning of the sub-space will restrict the recovery route from deviation. For example, if it is perceived that the destination is impossible to locate in hyperspace ψ (i.e., the back side of the surface β in FIG. 1 which meets the cube edges at points BCDE), the recovery route can be expanded only in the feasible space φ other than the whole space. Furthermore, if the estimated route bumps into the surface β, the relevant end node is reflected back to the feasible space φ.

To search for a route, at least two problems exist: how to construct recovery route and how to prune the sub-space. In one embodiment, space pruning is combined with the route node decision. And the recovery route construction is treated as solving the following optimization with space constraints:

Min E ( f ), s.t. Ha m,n εU 2 m,n , while U 2 m,n ⊂U 1 m,n ⊂ N 2 .  (7)

E(f) is an objective function for minimization, and U 2 m,n is the space constraint on N 2 -dimensional vector space N 2 . To solve this constrained optimization problem, the dynamic adjustment is implemented in both spatial and spectral domains because the signal f and the sub-space U 2 m,n are in different domains. The near-estimated route nodes are selected by an iterative minimization algorithm in spatial domain first. Once the result of the iteration goes outsides the feasible space U 2 m,n , the outranging entries of the result will be modified to the typical value.

The division between feasible space and unavailable space is a space pruning problem, which is realized by several constraints. In one embodiment, two constraints are used for space pruning. After the first constraint is applied, the space N 2 is shrunk to U 1 m,n . After the second constraint is applied, U 1 m,n is further shrunk to U 2 m,n . In other embodiments, more space constraints for space pruning may be introduced to clip the space to U x m,n (x≧3).

Route Construction

In one embodiment, minimization may be solved with partial differential equations (PDE's). In a PDE-based solution, the signals are iteratively regularized with the evolution time going by, so that step-wise route construction can be implemented. In one embodiment, total variation based algorithms may be used for image processing. In other embodiments, other PDE-based algorithms mentioned previously may be applied. One exemplary total variation (TV) regularization that may be used as a dynamic adjustment scheme in the spatial domain is:

The first part of equation 8 above is a total variation item for regularization, while the second part of the formula is a fidelity term, which prevents an iterative solution from unacceptable deviation. With the two constraints mentioned previously, the fidelity term may be discarded. The dynamic adjustment may be calculated by solving the Euler-Lagrange equation and assigning evolution time dt.

f i+1 ={tilde over (f)} i +{tilde over (f)} t i ·dt.   (9)

f i+1 is the result of i+1 time iterations, while {tilde over (f)} i is the reconstruction image from estimated route nodes {Ã m,n,i } K×L in the i-th step. The partial differential of {tilde over (f)} i on evolution time t is denoted as f t i , which is indicated by equation 10 below:

Constraining the Route

As mentioned previously, the final destination A m,n is constrained to be inside a sub-space U 1 m,n , which is defined as:

U 1 m,n ={Aε N 2 |Bl i,j m,n ≦A i,j <Bh i,j m,n , i,j εN},

where Bl i,j m,n =Â i,j m,n −Δl i,j,q , Bh i,j m,n =Â i,j m,n +Δu i,j,q .  (11)

 i,j m,n stands for the (i,j)-th entry of a typical vector  m,n . Δl i,j,q and Δu i,j,q are the distances from the typical vector to the lower bound Bl i,j m,n in and upper bound Bh i,j m,n of quantized interval in the (i, j) coordinate.

For further space pruning, an AC prediction method based on DC coefficients may be used as described below. In this algorithm, when four neighboring blocks only have DC components left after quantization, DC components of these blocks are utilized to predict three low frequency AC coefficients denoted as Ā i,j k,l . After predication, the allowable evaluation range of the AC coefficients reduces to the new bounded scope. As the result, the sub-space U 1 m,n is clipped to sub-space U 2 m,n , which is more constrained as indicated by equation 12 below:

U 2 m,n ={Aε N 2 |A i,j ε[Bl i,j m,n ,Bh i,j m,n ], i,j= 1,2 and ( i,j )≠(1,1)}.  (12)

Where, the lower bound and upper bound in A i,j dimension are modified as:

The typical vector of U 2 m,n is specified as:

During route construction, the estimated route nodes are bounded in sub-space U 2 m,n . In case the iterative result of regularization goes outside the space limitation in one coordinate, the relevant entry will be corrected to typical vectors as:

The symbol S is a correction operator in terms of space constraints. A is the near-estimated route node, and à m,n is the estimated route node for the next step regularization.

DC Based Low-Frequency AC Prediction

With the increase of quantization intervals, not only the texture and edge information are effaced but also the gradual variation in smooth area vanishes. For the blocks with gradual variation, the low frequency AC coefficients (A 1,2 , A 2,1 , A 2,2 ) may contain valuable gradient information due to the properties of these three AC coefficients.

FIG. 2 is a diagram plotting discrete cosine transform basis vectors with a partial enlargement of four of the basis vectors according to aspects of the subject matter described herein. For an 8×8 discrete cosine transform, the corresponding basis vectors of the DCT coefficient A i,j are denoted as C i,j , and all basis vectors {C i,j } 8×8 are represented in FIG. 2 (e.g., within the square 200 ). The basis vectors in the square 205 are shown in an enlarged view. Basis vector C 1,1 (i.e. vector 215 ) includes the average level of a block. Basis vector C 1,2 (i.e., vector 216 ) includes horizontal decrease variation information. Basis vector C 2,1 (i.e., vector 217 ) includes vertical decrease variation information. Basis vector C 2,2 (i.e., vector 218 ) includes diagonal variation information. These basis vectors cover the basic directional information and level information of a block. The elements of these basis matrices follow the following rules:

The absolute values of the four corner elements are equivalent, and the sub-matrix {hacek over (C)} i,j formed by four corner elements may be used to describe the variation property of the corresponding original basis C 1,1 . For example, {hacek over (C)} 1,2 and {hacek over (C)} 2,1 show the decrease trend in horizontal and vertical directions respectively; {hacek over (C)} 2,2 exhibits the variation along diagonal direction. And all these four sub-matrices can be written as the product of one constant scalar and a 2×2 Hadamard transform basis. This can be used to build a bridge between the low frequency DCT coefficients and the Hadamard transform coefficients. Once a 2×2 matrix composed of pixels at a distance is obtained, the predicted low frequency coefficients can be calculated by a scaling operation and a Hadamard transform. The gradient information may be expressed by the difference among the DC components of the neighboring blocks in smooth area. Therefore, the variation of DC may be used to simulate the variation within a patch with the size same of image block, because the DC difference of neighboring blocks can be taken as the difference of pixel values in a distance of block's size.

FIG. 3 illustrates a scheme of DC based low frequency AC prediction according to aspects of the subject matter described herein. When the quantized DCT coefficients of four neighboring blocks (positions (k, l), (k, l+1), (k+1, l) and (k+1, l+1), 305 , 302 , 303 , and 304 , respectively) only have DC components ( 306 , 307 , 308 and 309 , respectively) that are non-zero, these four blocks are likely within a smooth variation area. The prediction of the three low frequency AC coefficients of (k, l)-th block may be determined by:

1. Obtaining the diagonal DC components ( 306 , 307 , 308 and 309 ) of the four neighboring blocks to form a 2×2 matrix ( 310 ); 2. Applying a Hadamard transform (HT) to the matrix 310 to construct a “HT matrix 311 ; and 3. Scaling the HT matrix 311 as desired by multiplying each entry of the HT matrix by distinct scaling factors to create a scaled matrix 313 that is used to predict the three low frequency AC coefficients ( 314 , 315 , and 316 ) corresponding to the DC component 306 of the upper left block (i.e., block 305 ).

A mathematical expression of the AC prediction algorithm may be described by the following equation:

As can be seen above, in one embodiment, compressed image restoration may be treated as a DCT coefficients recovery problem. The recovery procedure may be modeled as the construction of a route, which starts from the quantized coefficients node and terminates at the original transformed coefficients node in an N 2 -dimensional vector space. Using a partial differential equation diffusion method, total variation regularization may be used to realize stepwise route node selection. In addition, two constraints on high dimensional vector space may be used to restrict the route within the feasible space. The first constraint relates to the quantization operation, while the second constraint relates to a property of the discrete cosine transform.

FIG. 4 is a block diagram illustrating exemplary components that may be included in an apparatus arranged in accordance with aspects of the subject matter described herein. The apparatus 405 is only one example of a suitable environment and is not intended to suggest any limitation as to the scope of use or functionality of aspects of the subject matter described herein. Neither should the apparatus 405 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the apparatus 405 .

Aspects of the subject matter described herein are operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with aspects of the subject matter described herein include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microcontroller-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

Aspects of the subject matter described herein may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, and so forth, which perform particular tasks or implement particular abstract data types. Aspects of the subject matter described herein may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

Computer-readable media as described herein may be any available media that can be accessed by a computer and includes both volatile and nonvolatile media, and removable and non-removable media. By way of example, and not limitation, computer-readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile discs (DVDs) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by the computer 110 .

Communication media typically embodies computer-readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer-readable media.

Turning to FIG. 4 , the apparatus 405 may include a decoder 410 , a constrainer 415 , an optimizer/route finder 420 , and a user interface 425 . The components illustrated in FIG. 4 are exemplary and are not meant to be all-inclusive of components that may be needed or included. In other embodiments, the components or functions described in conjunction with FIG. 4 may be included in other components or placed in subcomponents without departing from the spirit or scope of aspects of the subject matter described herein.

The decoder 410 is operable to receive data corresponding to a first image and to determine a compression algorithm used to create the data. For example, the decoder 410 may be operable to determine that the data corresponds to a JPEQ image that has been compressed using a JPEQ compression algorithm. The decoder 410 may also be able to determine relevant characteristics about the compression algorithm such as block size and the like.

The constrainer 415 is operable to provide one or more constraints regarding a set of allowable solutions in creating a second (e.g., restoration) image from the data. The set of allowable solutions may include spectral components (e.g., coefficients) related to the second image. As described previously, two separate constraints may be used to trim the set of allowable solutions. The constrainer 415 may operate to predict one or more AC components using DC components from four adjoining blocks as described previously.

The optimizer/route finder 420 is operable to find a solution in the set of allowable solutions via an iterative function. The optimizer/route finder 420 is further operable to receive constraints from the constrainer 415 in conjunction with finding the solution. The solution corresponds to the restoration image that is determined to be the closest to the original image by the iterative function at a particular iteration. For an example of an iterative function, see equations 9 and 10 above.

The user interfaced 425 may display a restoration image provided by the other components and may be used to specify parameters such as how many iterations are to be performed by the optimizer/router finder 420 .

FIGS. 5-6 are flow diagrams that general represent actions that may occur in image restoration in accordance with aspects of the subject matter described herein. For simplicity of explanation, the methodology described in conjunction with FIGS. 5-6 are depicted and described as a series of acts. It is to be understood and appreciated that aspects of the subject matter described herein are not limited by the acts illustrated and/or by the order of acts. In one embodiment, the acts occur in an order as described below. In other embodiments, however, the acts may occur in parallel, in another order, and/or with other acts not presented and described herein. Furthermore, not all illustrated acts may be required to implement the methodology in accordance with aspects of the subject matter described herein. In addition, those skilled in the art will understand and appreciate that the methodology could alternatively be represented as a series of interrelated states via a state diagram or as events.

FIG. 5 is a flow diagram that generally represents one exemplary embodiment of actions that may occur in image restoration in accordance with aspects of the subject matter described herein. At block 505 , the actions begin.

At block 510 , data corresponding to a compressed image is obtained. For example, referring to FIG. 4 , the decoder 410 may obtain data that corresponds to a compressed image. The data may be created via a lossy compression algorithm that utilizes a set of discrete coefficients during compression. One such exemplary algorithm is the JPEG algorithm although aspects of the subject matter described herein may also be applied to other algorithms that use discrete coefficients.

After the data is obtained, a second image may be constructed from the data. In constructing the second image, spectral information may be recovered by performing the actions indicated in blocks 515 - 525 .

At block 515 , regularization is performed on the data. For example, referring to FIG. 4 , the optimizer/route finder 420 may use partial differential equations to find a route though the vector space shown in FIG. 1 . The regularization may utilize an iterative function where at least some values of the function are dependent on (e.g., input from) values computed in (e.g., output from) a previous iteration.

At block 520 , constraints are enforced. For example, referring to FIG. 4 , the constrainer 415 may impose constraints on the route chosen by the optimizer/route finder 420 . These constraints may be enforced during the route finding process to limit the solution space available to the regularization.

At block 525 , a determination is made of whether a further iteration of the regularization algorithm is needed or desired. If a further iteration is to be performed, the actions continue at block 515 ; otherwise, the actions continue at block 530 . For example, referring to FIG. 4 , depending on configuration data entered via the user interface 425 or otherwise, the optimizer/route finder 420 may perform another iteration of the route finding algorithm to attempt to find a better image recovery for the compressed image.

At block 530 , the recovered image is optionally displayed. For example, referring to FIG. 4 , the user interface 425 may be used to display the image obtained from the compressed data.

At block 535 , other actions may optionally be performed as desired.

FIG. 6 is a flow diagram that generally represents another exemplary embodiment of actions that may occur in image restoration in accordance with aspects of the subject matter described herein. At block 605 , the actions begin.

At block 610 , data corresponding to a compressed image is obtained. For example, referring to FIG. 4 , the decoder 410 may obtain data that corresponds to a compressed image. The data may be created via a lossy compression algorithm that utilizes a set of discrete coefficients during compression.

At block 615 , nodes are selected to minimize a function. The nodes represent possible solutions to the function. For example, referring to FIG. 4 , the optimizer/route finder 420 may use partial differential equations to find nodes on the vector space shown in FIG. 1 .

At block 620 , the solution is constrained based on coefficients found in four neighboring blocks data. For example, DC components may be used to predict AC components as described previously. For example, referring to FIG. 4 , the constrainer 415 may examine neighboring blocks and compute AC components as described previously. In calculating the AC components a Hadamard transform matrix may be used as described previously.

At block 630 , the solution space may be constrained based on other constraints. For example, the solution space may be constrained based on equation 11 above.

At block 635 , a determination is made of whether a further iteration is needed or desired. If a further iteration is to be performed, the actions continue at block 615 ; otherwise, the actions continue at block 640 . For example, referring to FIG. 4 , depending on configuration data entered via the user interface 425 or otherwise, the optimizer/route finder 420 may perform another iteration of the node selection algorithm to attempt to find a better image recovery for the compressed image.

At block 535 , other actions may optionally be performed as desired.

As can be seen from the foregoing detailed description, aspects have been described related to image restoration for compressed images. While aspects of the subject matter described herein are susceptible to various modifications and alternative constructions, certain illustrated embodiments thereof are shown in the drawings and have been described above in detail. It should be understood, however, that there is no intention to limit aspects of the claimed subject matter to the specific forms disclosed, but on the contrary, the intention is to cover all modifications, alternative constructions, and equivalents falling within the spirit and scope of various aspects of the subject matter described herein.