Patent Publication Number: US-9848210-B2

Title: Error concealment method using spatial interpolation and exemplar-based image inpainting

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit under 35 USC 119A of Korean Patent Application No. 10-2014-0183393 filed on Dec. 18, 2014, Korean Patent Application No. 10-2014-0183394 filed on Dec. 18, 2014 and Korean Patent Application No. 10-2014-0183395 filed on Dec. 18, 2014 in the Korean Intellectual Property Office, the entire disclosure of which is incorporated herein by reference for all purposes. 
     BACKGROUND 
     The following description relates to an error concealment method. 
     Most image coding techniques such as H.264, MPEG-4, and HEVC (H.265) use variable length coding and spatial and motion prediction methods. 
     In compressed images generated by using the methods, some of transmitted data may be lost in a communication environment. Accordingly, in order to minimize damage due to an error occurring in a communication channel, when the error occurs, an error concealment method has been researched. 
     The error concealment method is a method of maximally restoring damaged blocks by using information on adjacent blocks which are normally restored. The error concealment method is largely divided into a spatial error concealment (SEC) method and a temporal error concealment (TEC) method. The SEC method is a method of interpolating the damaged blocks by using pixel values of peripheral blocks which are correctly decoded on the assumption that there is no sudden change in brightness among adjacent pixels in a spatial area. 
     SUMMARY 
     In one general aspect, there is provided an error concealment method using spatial interpolation and exemplar-based image inpainting including: receiving an image including a source area and a restoration area to be restored by means of a decoder; determining a target patch in which a target pixel having the highest priority is at the center among pixels positioned in a boundary area of the restoration area by means of the decoder; and performing restoring by exemplar-based image inpainting for the target patch based on a difference between the target patch and the final source patch of the source area or performing spatial interpolation for the target pixel by means of the decoder. 
     In another general aspect, there is provided an error concealment method including: determining a target pixel having the highest priority among pixels positioned in a boundary area of a restoration area in an image including a source area and the restoration area to be restored by means of a decoder; and performing directional interpolation or neighbor interpolation by comparing a gradient amplitude of the target pixel and a threshold value by means of the decoder, wherein the threshold value is determined according to image complexity of the boundary area. 
     In yet another general aspect, there is provided an error concealment method for performing an error concealment using an exemplar-based image inpainting, the method including: determining a final source patch based on whether a target patch in which a pixel positioned in a boundary area of a restoration area is at the center is matched with a boundary of a candidate source patch positioned in the source area in an image including a source area and the restoration area to be restored and restoring the target patch by using the final source patch by means of a decoder. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The above and other aspects, features and other advantages of the example will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings, in which: 
         FIGS. 1A and 1B  illustrate an example of an image which is inpainted; 
         FIG. 2  illustrates an example of a flowchart for a method of determining a source patch for restoring a target patch; 
         FIGS. 3A through 3C  illustrate an example for describing an area of the target patch and the source patch; 
         FIG. 4  illustrates an example of a flowchart for an error concealment method using exemplar-based image inpainting; 
         FIG. 5  illustrates an example of an image in which spatial interpolation is required; 
         FIG. 6  illustrates an example of a flowchart for an adaptive spatial interpolation method; 
         FIG. 7  illustrates an example of a reference for quantizing an angle of a target pixel; 
         FIGS. 8A and 8B  illustrate an example of performing directional interpolation for the target pixel; 
         FIGS. 9A and 9B  illustrate an example of performing neighbor interpolation for the target pixel; and 
         FIG. 10  illustrates an example of a flowchart for an error concealment method using spatial interpolation and exemplar-based image inpainting. 
     
    
    
     Throughout the drawings and the detailed description, unless otherwise described, the same drawing reference numerals will be understood to refer to the same elements, features, and structures. The relative size and depiction of these elements may be exaggerated for clarity, illustration, and convenience. 
     DETAILED DESCRIPTION 
     The following detailed description is provided to assist the reader in gaining a comprehensive understanding of the methods, apparatuses, and/or systems described herein. Accordingly, various changes, modifications, and equivalents of the systems, apparatuses and/or methods described herein will be suggested to those of ordinary skill in the art. Also, descriptions of well-known functions and constructions may be omitted for increased clarity and conciseness. 
     The presently described examples will be understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The drawings are not necessarily drawn to scale, and the size and relative sizes of the layers and regions may have been exaggerated for clarity. 
     It will be understood that, although the terms first, second, A, B, etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first element could be termed a second element, and, similarly, a second element could be termed a first element, without departing from the scope of the example. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items. 
     As used herein, the singular forms “a,” “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises,” “comprising,” “includes” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. 
     Before starting detailed explanations of figures, components that will be described in the specification are discriminated merely according to functions mainly performed by the components or conventionally carried out according to common knowledge of related technical fields. That is, two or more components which will be described later can be integrated into a single component. Furthermore, a single component which will be explained later can be separated into two or more components. Moreover, each component which will be described can additionally perform some or all of a function executed by another component in addition to the main function thereof. Some or all of the main function of each component which will be explained can be carried out by another component. Accordingly, presence/absence of each component which will be described throughout the specification should be functionally interpreted. 
     The following description relates to an error concealment method used by an apparatus (decoder) of receiving an image through a wireless network and the like and restoring the image. In more detail, the following description relates to a spatial interpolation method for spatial error concealment (SEC). The following description may be applied even to any case where the SEC is required in an image received by the decoder. For example, the following description may be applied even to a case where an error occurs in a received intra (I) frame. 
     The following description largely includes three restoring methods. (1) The first method is an error concealment method  200  applying exemplar-based inpainting. The image inpainting has been used as a method for restoring an image in which a specific portion is cut without relating an original error concealment method. In the exemplar-based inpainting of the image inpainting method, a patch having the highest priority is first restored by setting a patch based on each pixel with respect to each pixel placed on the boundary of the area to be restored and calculating a priority thereof. (2) The second method is an adaptive spatial interpolation method  300  using indirection information of the pixel. (3) The third method is an error concealment method  400  using the exemplar-based inpainting or the adaptive spatial interpolation. Hereinafter, the following description will be described in sequence. 
     1. Error Concealment Applying Exemplar-Based Image Inpainting 
     Exemplar-Based Image Inpainting 
     First, an exemplar-based image inpainting method will be described.  FIG. 1  illustrates an example of an image which is inpainted.  FIGS. 1A and 1B  illustrate a source area Φ, a restoration area Ω, and a boundary area δΩ which borders the source area Φ in the restoration area Ω. The restoration area Ω means an area in which the image is damaged and thus needs to be restored and the source area Φ means an area which is not damaged.  FIG. 1A  illustrates an example of a target patch to be restored in the image.  FIG. 1B  illustrates an example of a target patch and a source patch using for restoring the target patch. 
     The decoder determines a target patch ψ p  to be restored in the boundary area δΩ and finds a source patch ψ q  to be used for restoring the corresponding patch in the source area Φ. Thereafter, the decoder restores the target patch by using the source patch. The decoder gradually performs restoration inward in the boundary area until the restoration area Ω is fully restored. 
     The decoder may determine a priority for the patch which is first restored in the restoration area Ω. The decoder may determine a restoring order for the patch according to the priority of the pixel included in the patch. The decoder may determine a pixel having the highest priority among pixels in the boundary area δΩ and first restore the patch including the corresponding pixel. 
     Like the following Equation 1, a priority P(p) for a pixel p in the restoration area Ω may be calculated by the product of confidence C(p) of the pixel p and a gradient function D(p) of the pixel p.
 
 P ( p )= C ( p ) D ( p )  [Equation 1]
 
     C(p) is a ratio of confidential pixels in the entire pixels in the patch ψ p . The confidential pixels mean pixels positioned in the remaining area except for the restoration area Ω in the area illustrated in  FIG. 1 . The following Equation 2 is an equation calculating C(p). D(p) corresponds to the strength of a gradient in p. The following Equation 3 is an equation calculating D(p). 
     
       
         
           
             
               
                 
                   
                     C 
                     ⁡ 
                     
                       ( 
                       p 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           q 
                           ∈ 
                           
                             
                               Ψ 
                               p 
                             
                             ⋂ 
                             
                               ( 
                               
                                 ℐ 
                                 - 
                                 Ω 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         C 
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                     
                     
                        
                       
                         Ψ 
                         p 
                       
                        
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 2, I means the entire area including the source area and the restoration area. I−Ω means an area except for the restoration area Ω in the entire area. |Ψ p | means the number of pixels of the target patch ψ p . C (q) has a value of 1 if q is in the source area Φ and q has a value of 0 if q is in the restoration area Ω. 
     
       
         
           
             
               
                 
                   
                     D 
                     ⁡ 
                     
                       ( 
                       p 
                       ) 
                     
                   
                   = 
                   
                     
                        
                       
                         
                           ∇ 
                           
                             I 
                             p 
                             ⊥ 
                           
                         
                         · 
                         
                           n 
                           p 
                         
                       
                        
                     
                     α 
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     3 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 3, ∇I p   ⊥  is isophote of the pixel p. In Equation 3, ∇ is a gradient operator and ⊥ is an orthogonal operator. In Equation 3, n p  is a normal vector for δΩ in the pixel p and α is a normalized parameter (255 in a gray-level image). 
     In summary, the decoder may determine the priority of the pixel p based on (i) how many confidential pixels are included in the patch to be restored and (ii) how much the gradient of the image is strong in a central pixel of the patch to be restored. 
     For convenience of description, in  FIG. 1 , it is assumed that p among the pixels in the restoration area Ω has the highest priority. Accordingly, in  FIGS. 1A and 1B , Ψ p  corresponds to the target patch. The target patch Ψ p  is a patch area having the pixel P at the center. The patch means a basic unit in which restoring is performed in the image. 
     The decoder needs to determine the most similar source patch Ψ   q   the target patch Ψ p  in which p is included at the center in the source area ψ. Hereinafter, the most similar source patch Ψ   q   is called the final source patch. The decoder determines which candidate source patch is the final source patch Ψ   q   among at least one candidate source patch similar to the target patch Ψ p  in the source area ψ. 
     In  FIG. 1B , two candidate source patches are illustrated as an example. In  FIG. 1B , a candidate source patch Ψ q′  in which a pixel q′ is at the center and a candidate source patch Ψ q″  in which a pixel q″ is at the center are illustrated. 
     The decoder may determine the final source patch Ψ   q   by using an equation such as the following Equation 4. 
     
       
         
           
             
               
                 
                   
                     
                       Ψ 
                       
                         q 
                         _ 
                       
                     
                     = 
                     
                       arg 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           min 
                           
                             
                               Ψ 
                               
                                 q 
                                 ^ 
                               
                             
                             ∈ 
                             Φ 
                           
                         
                         ⁢ 
                         
                           d 
                           ⁡ 
                           
                             ( 
                             
                               
                                 Ψ 
                                 
                                   p 
                                   ^ 
                                 
                               
                               , 
                               
                                 Ψ 
                                 
                                   q 
                                   ^ 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     4 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 4, Ψ {circumflex over (p)}  is an area positioned in the source area Φ in Ψ p . That is, Ψ {circumflex over (p)} =Ψ p ∩Φ. Ψ {circumflex over (q)}  means an area having a shape such as Ψ {circumflex over (p)}  in Ψ q . d(Ψ {circumflex over (p)} ,Ψ {circumflex over (q)} ) is a sum of squared difference (SSD) of corresponding pixels in Ψ {circumflex over (p)}  and Ψ {circumflex over (q)} . For example, in  FIG. 1B , the candidate source patch Ψ q′  has a smaller SSD value than that of Ψ q″ , the decoder determines Ψ q′  as the final source patch Ψ   q   . Thereafter, the decoder restores the target patch Ψ p  based on the final source patch Ψ   q   . 
     Meanwhile, the decoder may use another value other than the aforementioned SSD in order to find the final source patch Ψ   q   . The decoder may search the final source patch Ψ   q   based on a mean-squared error (MSE) and a side matching distortion (SMD). The related description will be described. 
     An area positioned in the restoration area Ω in the target patch Ψ p  is called Ψ {tilde over (p)} . An area corresponding to Ψ {tilde over (p)}  in the source patch is called Ψ {tilde over (q)} . The decoder may perform inpainting by replacing Ψ {tilde over (p)}  with Ψ {tilde over (q)} . 
     The decoder may determine the final source patch for a target patch having a next priority and restore the target patch having the next priority. As such, the decoder may determine the source patch of the source area Φ with respect to all the target patches in the restoration area Ω and restore the target patch by a method of attaching the determined source patch to the corresponding target patch. 
     Method of Determining Source Patch 
       FIG. 2  illustrates an example of a flowchart for a method  100  of determining a source patch for restoring a target patch. 
     In a method  100  of determining the source patch, the decoder first calculates a priority for a pixel which belongs to the boundary area δΩ of the restoration area Ω ( 110 ). The priority may be determined by using the aforementioned Equation 1. The decoder determines the pixel p having the highest priority among pixels included in the boundary area δΩ and determines the target patch Ψ p  in which the pixel p is at the center ( 120 ). 
     Thereafter, the decoder searches the source patch for using the target patch Ψ p  for restoring. Meanwhile, the decoder may search the source patch by limiting a partial area other than the entire source area Φ. In this case, the decoder may set a search window S p  to search the source patch ( 130 ). 
     Setting of Area for Searching Source Patch 
     The decoder searches the source patch Ψ q  corresponding to the target patch Ψ p  in the source area Φ. The decoder may uniformly limit an area for searching the source patch. In order to limit the area for searching the source patch, the decoder may use a search window having a finite size. The decoder may limit a range of the search window for finding the source patch by using the following Equation 5.
 
 S   p ={( u,v )| u ε[ x − s,x + s ], v ε[ y − s,y + s ]}  [Equation 5]
 
     In Equation 5, p is a pixel having the highest priority determined by Equation 1, (x, y) is a coordinate of p, and S p  is a search area having a size of (2s+1)×(2s+1). The searching may be performed only in S p . s is a parameter for setting the size of the search area. S may use an appropriate value according to a size of the search area. 
     The decoder searches the source patch in the entire source area Φ or a predetermined search window S p  as described above. The decoder calculates a mean-squared error (MSE) distortion value and a side matching distortion (SMD) value between the target patch Ψ p  and the candidate source patch (for example, Ψ q′  and Ψ q″  in  FIG. 1B ) in the search range ( 140 ). 
     Finally, the decoder determines a patch having the smallest value obtained by adding the MSE distortion value and the SMD value among the candidate source patches as the final source patch Ψ   q   ( 150 ). Hereinafter, a process of determining the final source patch will be described in detail. 
       FIG. 3  illustrates an example for describing an area of the target patch and the source patch. In  FIG. 3 , the patch has a grid shape including a plurality of squares. In  FIG. 3 , one square configuring the grid corresponds to one pixel. 
       FIG. 3A  illustrates an example of an area including the restoration area Ω and the source area Φ as illustrated in  FIG. 1 . In  FIG. 3A , the restoration area Ω having the square shape is illustrated at the lower right side and the remaining area of  FIG. 3A  corresponds to the source area Φ. In  FIG. 3A , the restoration area Ω includes the boundary area δΩ contacting the source area Φ. The boundary area δΩ is constituted by pixels outside the restoration area Ω. 
       FIG. 3A  illustrates the target patch Ψ p  in which one pixel p positioned in the boundary area δΩ is at the center. It is assumed that the pixel p currently has the highest priority among the pixels in the boundary area δΩ. The upper left side of  FIG. 3A  illustrates one source patch Ψ q  in which the pixel q is at the center in the source area Φ. The source patch Ψ q  illustrated in  FIG. 3A  corresponds to one candidate source patch. Hereinafter, a process of determining the most appropriate final source patch Ψ   q   by comparing the target patch Ψ p  and the source patch Ψ q  will be described. 
     The method of determining the source patch described below is used based on the MSE and the SMD. The SMD is used in a boundary matching algorithm (BMA) of H.264. The existing SMD is used in a regular boundary, but the SMD will be used even in an irregular boundary in the following description. 
     First, a specific area which is a parameter used in the MSE distortion operation and the SMD operation to be described below will be described. 
       FIG. 3B  is an example illustrating the target patch Ψ p  and the source patch Ψ q  in  FIG. 3A . In  FIG. 3B , an area positioned in the source area Φ of the target patch Ψ p  area is represented as Ψ {circumflex over (p)}  and an area corresponding to Ψ {circumflex over (p)}  in the source patch Ψ q  is represented as Ψ {circumflex over (q)} . In  FIG. 3B , Ψ {circumflex over (p)}  and Ψ {circumflex over (q)}  are represented by the shadow. In  FIG. 3B , an area positioned in the restoration area Ω of the target patch Ψ p  area is represented as Ψ {circumflex over (p)}  and an area corresponding to Ψ {tilde over (p)}  in the source patch Ψ q  is represented as Ψ {tilde over (q)} . 
       FIG. 3C  is another example illustrating the target patch Ψ p  and the source patch Ψ q  in  FIG. 3A . In  FIG. 3C , an inner boundary area positioned in the restoration area Ω at the target patch Ψ p  is represented as B p   in . In  FIG. 3C , an area corresponding to B p   in  in the source patch Ψ q  is represented as B q   in . B p   in  corresponds to the area which belongs to the target patch Ψ p  in the boundary area δΩ. In  FIG. 3C , B p   in  and B q   in  are represented by a dashed line. Meanwhile, in  FIG. 3C , the boundary which borders the target patch Ψ p  in the source area Φ is represented as B p   out . B p   out  may be referred to as an outer boundary area of the target patch Ψ p . 
     The MSE distortion value d mse  may be defined as the following Equation 6. 
     
       
         
           
             
               
                 
                   
                     d 
                     mse 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           n 
                           = 
                           1 
                         
                         N 
                       
                       ⁢ 
                       
                         
                           ( 
                           
                             
                               
                                 Ψ 
                                 
                                   p 
                                   ^ 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 n 
                                 ) 
                               
                             
                             - 
                             
                               
                                 Ψ 
                                 
                                   q 
                                   ^ 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 n 
                                 ) 
                               
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     6 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 6, Ψ {circumflex over (p)}  is an area positioned in the source area Φ in the target patch Ψ p  and Ψ {circumflex over (q)}  is an area corresponding to Ψ {circumflex over (p)}  in the source patch Ψ q . That is, Ψ {circumflex over (q)}  has the same shape as Ψ {circumflex over (p)} . In Equation 6, N is the number of pixels of Ψ {circumflex over (p)} . In Equation 6, Ψ {circumflex over (p)} (n) and Ψ {circumflex over (q)} (n) are gray levels for n-th pixels of Ψ {circumflex over (p)}  and Ψ {circumflex over (q)} , respectively. 
     The SMD d smd  may be defined as the following Equation 6. 
     
       
         
           
             
               
                 
                   
                     d 
                     smd 
                   
                   = 
                   
                     
                       1 
                       K 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         K 
                       
                       ⁢ 
                       
                         
                           ( 
                           
                             
                               
                                 B 
                                 p 
                                 out 
                               
                               ⁡ 
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                             - 
                             
                               
                                 B 
                                 q 
                                 
                                   i 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   n 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     7 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 7, B p   in  is an inner boundary area which belongs to the restoration area Ω in the target patch Ψ p  as described in  FIG. 3C . In Equation 7, B p   out  is an outer boundary area positioned outside the restoration area Ω in the target patch Ψ p . In other words, B p   out  is an area which belongs to the source area Φ in the target patch Ψ p  and contacts the inner boundary area. B q   in  is an area corresponding to B p   in  in the source patch Ψ p . In addition, K is the number of pixels of B p   out . 
     As described above, the decoder may perform an operation of finding the source patch for restoring the target patch through the aforementioned Equation 4. The decoder may search the source patch by using d mse  and d smd  instead of the SSD value. The decoder may calculate a target patch distortion value d(Ψ p ,Ψ q ) as the following Equation 8 by using d mse  and d smd .
 
 d (Ψ p ,Ψ q )=α· d   mse +(1−α)β· d   smd   [Equation 8]
 
     In Equation 8, α may be calculated as the following Equation 9 as a weighting factor. In Equation 8, β has a value of 0≦β≦3 as a weighting factor for the SMD. When β is set as 1, a weight is determined in proportion to the number of pixels used in d mse  and d smd , and when β is set as 0, d smd  is not influenced. 
     
       
         
           
             
               
                 
                   α 
                   = 
                   
                     N 
                     
                       N 
                       + 
                       K 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     9 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 9, N is the number of pixels of Ψ {circumflex over (p)}  used in the d mse  calculation and K is the number of pixels of B p   out  used in the d smd  calculation. 
     In the case of a color image having three color components such as RGB, the target patch distortion value d(Ψ p ,Ψ q ) becomes a value obtained by adding the target patch distortion value to each color component as the following Equation 10. 
     
       
         
           
             
               
                 
                   
                     d 
                     ⁡ 
                     
                       ( 
                       
                         
                           Ψ 
                           p 
                         
                         , 
                         
                           Ψ 
                           q 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         c 
                         = 
                         1 
                       
                       3 
                     
                     ⁢ 
                     
                       
                         d 
                         c 
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             Ψ 
                             p 
                           
                           , 
                           
                             Ψ 
                             q 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     10 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 10, d c (Ψ p ,Ψ q ) means the target patch distortion value for the c-th color component among a plurality of color components. 
     The decoder determines the final source patch Ψ   q   for the target patch Ψ p  finally using the target patch distortion value d(Ψ p ,Ψ q ) calculated based on d mse  and d smd . The following Equation 11 corresponds to an equation for determining the final source patch Ψ   q   . 
     
       
         
           
             
               
                 
                   
                     Ψ 
                     
                       q 
                       _ 
                     
                   
                   = 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         min 
                         
                           q 
                           ∈ 
                           
                             S 
                             p 
                           
                         
                       
                       ⁢ 
                       
                         d 
                         ⁡ 
                         
                           ( 
                           
                             
                               Ψ 
                               p 
                             
                             , 
                             
                               Ψ 
                               q 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     11 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 11, S p  corresponds to the search area. The search area may be the entire source area Φ, but may also be a search area limiting the range as described in Equation 5. The decoder calculates the target patch distortion value d(Ψ p ,Ψ q ) for the pixel p existing in S p  and selects a patch having the smallest target patch distortion value as the final source patch Ψ   q   . 
     Error Concealment Method 
       FIG. 4  illustrates an example of a flowchart for an error concealment method  200  using exemplar-based image inpainting. The error concealment method  200  uses exemplar-based image inpainting based on the aforementioned method  100  of determining the source patch. 
     The decoder first receives an image including a restoration area Ω to be restored and a source area Φ without data loss ( 210 ). Thereafter, the final source patch is determined through the aforementioned method  100  of determining the source patch. 
     The decoder determines a target patch Ψ p  in which a pixel p having the highest priority is at the center among pixels of the boundary area δΩ ( 220 ). The decoder may set the search window S p  if necessary ( 230 ). When the decoder sets the search window S p , the decoder calculates an MSE distortion value and a SMD value between a candidate source patch Ψ q  and a target patch Ψ p  which exist in the search window S p  ( 240 ). 
     When the decoder does not set the search window S p , the decoder calculates an MSE distortion value d mse  and a SMD value d smd  between a candidate source patch Ψ q  and a target patch Ψ p  which exist in the source area Φ ( 240 ). 
     The decoder determines a patch having the smallest value obtained by adding the MSE distortion value d mse  and the SMD value d smd  among the candidate source patches as the final source patch Ψ   q   ( 250 ). In the process  250 , the MSE distortion value and the SMD value may use the weight described in Equation 8. 
     The decoder restores the target patch Ψ p  by using the final source patch Ψ   q   ( 260 ). In this process, the decoder may replace the Ψ {tilde over (p)}  area of the target patch Ψ p  with the Ψ {tilde over (q)}  area of the final source patch Ψ   q   . 
     The decoder determines whether restoration for the restoration area Ω is completed (270). When the restoration is not completed, the decoder performs the restoration for the remaining restoration area. The decoder restores the corresponding target patch by determining the next target patch in the restoration area Ω. In order to the next target patch, the decoder excludes the target patch Ψ p  just restored in the restoration area Ω. ( 280 ), determines the pixel p having a high priority in the remaining area, and determines the next target patch Ψ p  ( 220 ). Thereafter, the decoder repeats the processes  230  to  270 . 
     2. Adaptive Spatial Interpolation Method 
     An adaptive spatial interpolation method corresponding to the second error concealment method will be described.  FIG. 5  illustrates an example of an image in which spatial interpolation is required. The image of  FIG. 5  includes a source area Φ, a restoration area Ω, and a boundary area δΩ which borders the source area Φ in the restoration area Ω. The source area Φ means an area in which restoration is not required in the received image and the restoration area Ω means an area in which the restoration is required in the received image. That is, the restoration area Ω is an area in which an error occurs in an image data delivery process and thus accurate data are not received. Hereinafter, a spatial interpolation method for the restoration area Ω will be described. 
       FIG. 6  illustrates an example of a flowchart for an adaptive spatial interpolation method  300 . 
     The decoder determines a target pixel to be restored among pixels in the restoration area Ω ( 310 ). The decoder determines priorities for the pixels in the restoration area Ω and may determine a pixel having the highest priority as the target pixel. The priority for the pixel may be determined by using the aforementioned Equation 1. 
     The decoder calculates a gradient amplitude A of the determined target pixel. The gradient amplitude of the pixel may be calculated by using the following Equation 12. Equation 12 is a gradient amplitude of a pixel having a coordinate (x, y).
 
 A ( x,y )=√{square root over ( G   h   2 ( x,y )+ G   v   2 ( x,y ))}  [Equation 12]
 
     In Equation 12, G h (x,y) is a horizontal gradient component of the target pixel and G v (x,y) is a vertical gradient component of the target pixel. When the received image is a color image, the final gradient amplitude becomes a value obtained by adding a value obtained by calculating Equation 12 to each color component of the target pixel. 
     Thereafter, the decoder compares the gradient amplitude A of the target pixel and a threshold value T A  ( 330 ). When the gradient amplitude A of the target pixel is equal to or smaller than the threshold value T A , the decoder performs neighbor interpolation for the target pixel ( 350 ). When the gradient amplitude A of the target pixel is larger than the threshold value T A , the decoder performs directional interpolation for the target pixel ( 340 ). The threshold value T A  may be calculated by the following Equation 13. 
     
       
         
           
             
               
                 
                   
                     T 
                     A 
                   
                   = 
                   
                     
                       m 
                       A 
                     
                     - 
                     
                       
                         σ 
                         A 
                       
                       2 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     13 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 13, m A  is an average of a gradient amplitude A(x,y) for the pixels in the boundary area δΩ and σ A  is a standard deviation of the gradient amplitude A(x,y) for the pixels in the boundary area δΩ. That is, complexity of the boundary area influences the threshold value. 
     When the gradient amplitude of the pixel is larger than the threshold value T A , the corresponding pixel is classified as an edge pixel. When the gradient amplitude of the pixel is equal to or smaller than the threshold value T A , the corresponding pixel is classified as a homogeneous pixel. As a result, the decoder performs the directional interpolation for the edge pixel and the neighbor interpolation for the homogeneous pixel. 
     Directional Interpolation 
     Directional interpolation  340  will be described. 
     A directional interpolation process  340  includes calculating an angle of the target pixel ( 341 ), determining the closest pixels (a first pixel and a second pixel) to the target pixel p among pixels in the source area Φ based on the calculated angle direction ( 342 ), and determining a value of the target pixel p based on the determined first pixel and second pixel ( 343 ). 
     The angle θ(x,y) of the target pixel p represents directionality of the target pixel p and is calculated by the following Equation 14 with respect to p which is the edge pixel. It is assumed that p has a coordinate (x, y).
 
θ( x,y )=arctan( G   c   /G   h )  [Equation 14]
 
     In Equation 14, G h  is a horizontal gradient component of the pixel and G c  is a vertical gradient component of the pixel. The angle θ(x,y) of the target pixel p has a value of 0 to π. The calculated angle θ(x,y) of the pixel may be uniformly quantized. 
       FIG. 7  illustrates an example of a reference for quantizing an angle of a target pixel. In  FIG. 7 , each straight line may be expressed by the following Equation 15. 
     
       
         
           
             
               
                 
                   
                     
                       a 
                       i 
                     
                     = 
                     
                       
                         
                           2 
                           ⁢ 
                           i 
                         
                         16 
                       
                       ⁢ 
                       π 
                     
                   
                   , 
                   
                     
                       b 
                       i 
                     
                     = 
                     
                       
                         
                           
                             2 
                             ⁢ 
                             i 
                           
                           - 
                           1 
                         
                         16 
                       
                       ⁢ 
                       π 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     15 
                   
                   ] 
                 
               
             
           
         
       
     
     In  FIG. 7 , b i  corresponds to a reference line for determining the angle of the pixel and a i  means angle for quantizing the angle in a predetermined range. For example, when the calculated result θ(x,y) of Equation 14 has a value between b i  and b i+1 , the decoder determines a final angle of the pixel as a i . 
       FIG. 8  illustrates an example of performing directional interpolation for the target pixel p.  FIG. 8A  is an example for a process of determining a pixel in the source area Φ for performing directional interpolation based on the target pixel p.  FIG. 8B  is an example illustrating a result in which the target pixel p is interpolated. In  FIG. 8 , a white area at the center is the restoration area Ω. In  FIG. 8 , a block expressed by a black color, an oblique line, or a regular pattern represents a part of the source area Φ. It is assumed that the angle (quantized result) of the pixel p is a 6 . 
       FIG. 8A  illustrates the target pixel p in the restoration area Ω and two pixels {circumflex over (p)} 1  and {circumflex over (p)} 2  in the source area Φ. {circumflex over (p)} 1  is called a first pixel and {circumflex over (p)} 2  is called a second pixel. 
     {circumflex over (p)} 1  is the closest pixel which meets in the source area Φ while moving in a direction 3π/4 of the angle a 6  in the target pixel p. {circumflex over (p)} 2  is the closest pixel which meets in the source area Φ while moving in an opposite direction −π/4 of the angle a 6  in the target pixel p. The decoder may use an algorithm of finding the first pixel {circumflex over (p)} 1  and the second pixel {circumflex over (p)} 2  based on the target pixel p as various heuristic methods. 
     Thereafter, the decoder calculates distances from the target pixel p to the first pixel {circumflex over (p)} 1  and the second pixel {circumflex over (p)} 2 , respectively. The distance calculation of the pixel is performed through the following Equation 5. A distance from the target pixel p to the first pixel {circumflex over (p)} 1  is called a first distance {circumflex over (d)} 1  and a distance from the target pixel p to the second pixel {circumflex over (p)} 2  is called a second distance {circumflex over (d)} 2 . 
     When a coordinate of the pixel {circumflex over (p)} i  positioned in the source area is ({circumflex over (x)} i ,ŷ i ) and a coordinate of the target pixel p is (x, y), the distance from the target pixel p to {circumflex over (p)} i  is as the following Equation 16.
 
 {circumflex over (d)}   i =√{square root over (( {circumflex over (x)}   i   −x ) 2 +( ŷ   i   −y ) 2 )}  [Equation 16]
 
     The decoder calculates the pixel value  p  for the target pixel p by using a distances from the first pixel value and the second pixel value to each pixel. The decoder may calculate the pixel value  p  for the target pixel p by using the following Equation 17. As a result, the target pixel p has  p  which is an interpolated value.  FIG. 8B  illustrates an example in which the target pixel p has the interpolated value  p . 
     
       
         
           
             
               
                 
                   
                     p 
                     _ 
                   
                   = 
                   
                     
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           2 
                         
                         ⁢ 
                         
                           
                             
                               p 
                               i 
                             
                             ^ 
                           
                           ⁡ 
                           
                             ( 
                             
                               
                                 D 
                                 ^ 
                               
                               - 
                               
                                 
                                   d 
                                   i 
                                 
                                 ^ 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           2 
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               D 
                               ^ 
                             
                             - 
                             
                               
                                 d 
                                 i 
                               
                               ^ 
                             
                           
                           ) 
                         
                       
                     
                     = 
                     
                       
                         
                           
                             
                               p 
                               1 
                             
                             ^ 
                           
                           ⁢ 
                           
                             
                               d 
                               2 
                             
                             ^ 
                           
                         
                         + 
                         
                           
                             
                               p 
                               2 
                             
                             ^ 
                           
                           ⁢ 
                           
                             
                               d 
                               1 
                             
                             ^ 
                           
                         
                       
                       
                         
                           
                             d 
                             1 
                           
                           ^ 
                         
                         + 
                         
                           
                             d 
                             2 
                           
                           ^ 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     17 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 17, {circumflex over (D)} is a value obtained by adding {circumflex over (d)} 1  and {circumflex over (d)} 2 . 
     Neighbor Interpolation 
     Hereinafter, in  FIG. 6 , a neighbor interpolation process ( 350 ) for the homogeneous pixel will be described.  FIG. 9  illustrates an example of performing neighbor interpolation for the target pixel p.  FIG. 9A  is an example illustrating pixels in the source area Φ for performing neighbor interpolation based on the target pixel p and  FIG. 9B  is an example illustrating a result in which the target pixel p is interpolated. In  FIG. 9 , a white area at the center is the restoration area Ω. In  FIG. 9 , a block expressed by a black color, an oblique line, or a regular pattern represents a part of the source area Φ. 
     The neighbor interpolation is an interpolation method using a pixel adjacent to the target pixel p. For example, the neighbor interpolation may use a neighboring pixel adjacent to the target pixel p as illustrated in  FIG. 9A .  FIG. 9A  illustrates neighboring pixels {circumflex over (p)} 3 , {circumflex over (p)} 4 , {circumflex over (p)} 1 , and {circumflex over (p)} 2  positioned at the top, the bottom, the left side, and the right side of the target pixel p, respectively. The pixel value  p  of the target pixel p may be determined as an average of values of neighboring pixels of the target pixel p among the pixels in the source area Φ. 
     In  FIG. 9A , pixels adjacent to the target pixel p in the source area Φ are {circumflex over (p)} 1  and {circumflex over (p)} 3 . Accordingly, the pixel value  p  of the target pixel p becomes an average of the pixel value of {circumflex over (p)} 1  and the pixel value of {circumflex over (p)} 3 .  FIG. 9B  illustrates an example in which the target pixel p has the pixel value  p  interpolated through neighbor interpolation. 
     Referring back to  FIG. 6 , after the directional interpolation ( 340 ) or the neighbor interpolation ( 350 ) for the target pixel is completed, the decoder determines whether restoring for the entire restoration area Ω is completed. When the restoring for the entire restoration area Ω is not completed, the process of  FIG. 6  is repeated again. In this case, the restoration area Ω becomes an area except for the target pixel p in the existing restoration area Ω and the source area Φ becomes an area of adding the target pixel p to the existing source area Φ. 
     After interpolation for the previous target pixel is completed, the decoder determines the next target pixel and repeats the process of  FIG. 6 . As described above, the decoder may determine the next target pixel as the pixel having the highest priority among the pixels in the restoration area Ω except for the previous target pixel. Meanwhile, the decoder may determine the next target pixel as the pixel (that is, a pixel adjacent to the target pixel interpolated by a predetermined reference) positioned around the interpolated target pixel. 
     3. Error Concealment Method Using Spatial Interpolation and Exemplar-Based Image Inpainting 
     Finally, the third error concealment method will be described. The third method is an error concealment method based on the error concealment method  200  and the adaptive spatial interpolation method  300  using the aforementioned exemplar-based image inpainting. 
       FIG. 10  illustrates an example of a flowchart for an error concealment method using spatial interpolation and exemplar-based image inpainting. The decoder receives an image including the source area Φ and the restoration area Ω to be restored. 
     The decoder determines a target patch having the highest priority in the boundary area δΩ like the aforementioned exemplar-based image inpainting. That is, the decoder determines a pixel (a target pixel) having the highest priority in the boundary area δΩ by using Equation 1. As described above, the target patch is a patch in which the target pixel is at the center. The decoder determines the target patch in which the target pixel having the highest priority is at the center among the pixels positioned in the boundary area δΩ ( 420 ). This process is the same as the aforementioned process  220  in  FIG. 4 . 
     Thereafter, the decoder determines a patch having the smallest difference from the target patch among candidate source patches in the source area Φ as the final source patch ( 430 ). This process is the same as the aforementioned process  250  in  FIG. 4 . A target patch distortion value d(Ψ p ,Ψ q ) calculated in Equation 8 may be used to determine the final source patch. d(Ψ p ,Ψ q ) means the difference between the target patch and the final source patch. 
     The decoder compares a threshold value T h  and the target patch distortion value d(Ψ p ,Ψ q ) for the final source patch. The decoder compares the target patch distortion value d(Ψ p ,Ψ q ) and the threshold value T h  as the following Equation 18 to determine whether the exemplar-based image inpainting or the adaptive spatial interpolation is performed with respect to the target patch.
 
If  d (Ψ p ,Ψ q )&lt; T   h Ψ {tilde over (p)} =Ψ {tilde over (q)} //Image inpainting(patch)
 
Else  p= p   //Spatial interpolation(pixel)  [Equation 18]
 
     When d(Ψ p ,Ψ q ) is smaller than the threshold value T h , the decoder performs the image inpainting for the target patch Ψ p  by using the final source patch ( 450 ). The process  450  corresponds to the error concealment method  200  using the exemplar-based image inpainting of  FIG. 4 . 
     When d(Ψ p ,Ψ q ) is equal to or larger than the threshold value T h , the decoder performs the adaptive spatial interpolation for the target pixel p ( 460 ). The decoder determines that an appropriate source patch enough to restore the target patch Ψ p  does not exist. The process  460  corresponds to the adaptive spatial interpolation method  300  of  FIG. 6  described above. 
     When the target pixel is positioned at an edge of a complicated image, the target patch distortion value d(Ψ p ,Ψ q ) is increased and when the target pixel is in the homogeneous image area, the target patch distortion value d(Ψ p ,Ψ q ) has a small value. Accordingly, it is preferred that the threshold value T h  is determined based on complexity of the target patch. 
     The complexity of the target patch may be determined by calculating the gradient amplitude for the Ψ {circumflex over (p)}  area like the following Equation 19. 
     
       
         
           
             
               
                 
                   
                     A 
                     m 
                   
                   = 
                   
                     
                       1 
                       N 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                           ∈ 
                           
                             Ψ 
                             
                               p 
                               ^ 
                             
                           
                         
                       
                       ⁢ 
                       
                         A 
                         ⁡ 
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     19 
                   
                   ] 
                 
               
             
           
         
       
     
     Equation 19 is an average of values obtained by adding gradient amplitude to the pixels which belong to Ψ {circumflex over (p)}  included in the source area Φ in the target patch. Here, N is the number of pixels of Ψ {circumflex over (p)} . 
     The threshold value T h  may be set in proportion to A m . For example, the threshold value T h  may also be adaptively set like the following Equation 20. 
     
       
         
           
             
               
                 
                   
                     T 
                     h 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               T 
                               
                                 m 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 n 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               for 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 A 
                                 m 
                               
                             
                             &lt; 
                             
                               T 
                               
                                 m 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 n 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               A 
                               m 
                             
                             , 
                           
                         
                         
                           
                             
                               for 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 T 
                                 
                                   m 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   i 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   n 
                                 
                               
                             
                             ≤ 
                             
                               A 
                               m 
                             
                             ≤ 
                             
                               T 
                               
                                 ma 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 x 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               T 
                               
                                 ma 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 x 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               for 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 A 
                                 m 
                               
                             
                             &gt; 
                             
                               T 
                               
                                 ma 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 x 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     20 
                   
                   ] 
                 
               
             
           
         
       
     
     In Equation 20, T min  is a lower threshold value used for adaptively setting the threshold value T h . T max  is an upper threshold value used for adaptively setting the threshold value T h . 
     The decoder determines whether restoring is completed in all the pixels in the restoration area Ω ( 470 ). When the restoration area Ω to be restored remains, the source area Φ is updated ( 480 ), and the process of  FIG. 10  is repeated again. 
     The decoder adds the corresponding target pixel to the corresponding source area Φ when performing the adaptive spatial interpolation just before the source area Φ is updated. Alternatively, when the image inpainting is performed just before ( 450 ), the decoder adds the corresponding target patch Ψ p  to the source area Φ. On the contrary, the decoder excludes the corresponding target pixel or the target patch from the restoration area Ω. This is as described in  FIGS. 4 and 5 . 
     A number of examples have been described above. Nevertheless, it will be understood that various modifications may be made. For example, suitable results may be achieved if the described techniques are performed in a different order and/or if components in a described system, architecture, device, or circuit are combined in a different manner and/or replaced or supplemented by other components or their equivalents. Accordingly, other implementations are within the scope of the following claims.