Abstract:
The present invention relates to an image deformation method. An image deformation method using a deformation axis according to the present invention includes deforming the deformation axis based on deformation energy of points according to a deformation of at least one deformation axis including a plurality of points predetermined with respect to an image to be deformed; and deforming the image using a plurality of segments of the deformation axis divided based on points of the deformed deformation axis. According to the present invention, an image deformation method using a deformation axis is performed based on a freeform deformation axis (FDA) that is independent from a type of an original object and thus, may be more advantageous and may be utilized in combination with various types of deformation methods. Deformation of an image may be performed intuitively and in real time and thus, may be easily used by general users.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority to and the benefit of Korean Patent Application Nos. 10-2012-0145990 and 10-2013-0081882 filed in the Korean Intellectual Property Office on Dec. 14, 2012 and Jul. 12, 2013, the entire contents of which are incorporated herein by reference. 
       TECHNICAL FIELD 
       [0002]    The present invention relates to an image deformation method, and more particularly, to a method of correcting an image by deforming a shape and thereby advancing to creating an animation. 
       BACKGROUND ART 
       [0003]    A method of using a skeleton is most well known as a method of deforming a two-dimensional (2D) image or a three-dimensional (3D) image. The method of using a skeleton is suitable for creating an animation due to an easy execution method and a simple calculation, but has difficulty in obtaining a skeleton structure of an image and also has difficulty in being accessed by a general user. 
         [0004]    As another method, a freeform deformation (FFD) method is performed through deforming a space including a shape to be deformed. However, in this case, many control points are required and a method of using a physics based simulation requires a relatively large amount of calculation. 
         [0005]    Currently, many researches to solve a shape deformation issue by concluding the shape deformation issue as an energy minimization issue are being conducted through a geometrical approach, but a linearity of a proposed algorithm or a processing rate and stability still remain as an issue. 
       SUMMARY OF THE INVENTION 
       [0006]    The present invention has been made in an effort to provide an intuitive image deformation method to a user. More particularly, an exemplary embodiment proposes a method of deforming an image based on a freeform deformation axis (FDA). 
         [0007]    An exemplary embodiment of the present invention provides an image deformation method using a deformation axis, the method including: deforming the deformation axis based on deformation energy of points according to a deformation of at least one deformation axis including a plurality of points predetermined with respect to an image to be deformed; and deforming the image using a plurality of segments of the deformation axis divided based on points of the deformed deformation axis. 
         [0008]    The deforming of the deformation axis may deform the deformation axis based on the deformation energy of points calculated using a length of a segment of the deformation axis divided based on the plurality of points. 
         [0009]    The deforming of the deformation axis may deform the deformation axis based on the deformation energy of points calculated using Laplacian coordinates about the plurality of points. 
         [0010]    The deforming of the deformation axis may deform the deformation axis to minimize the deformation energy of points in the case of deforming the image. 
         [0011]    The image deformation method using the formation axis may further include generating an intermediate shape that is figures formed along the deformation axis and surrounding a portion of the deformation axis. The deforming of the image may deform the image by deforming the intermediate shape. 
         [0012]    The intermediate shape may be configured as a plurality of offset curves having a predetermined interval with respect to the deformation axis. 
         [0013]    The intermediate shape may include a plurality of offset points that is positioned on a normal line with respect to the plurality of segments of the deformation axis and has a predetermined interval. 
         [0014]    The deforming of the image may deform the intermediate shape based on a before-deformation width and an after-deformation width of the intermediate shape. 
         [0015]    The deforming of the image may determine a thickness of the intermediate shape that is deformed based on a change in a length of a segment of the deformation axis according to the deformation of the intermediate shape. 
         [0016]    The deformation of the image may be performed based on a change in a position of a rotation control point using a fixing control point or the rotation control point set with respect to the deformation axis. 
         [0017]    The deforming of the image may deform the image using a linear blend skinning (LBS) weight assigned to each segment of the deformation axis with respect to each point of the image. 
         [0018]    The image deformation method using the formation axis may further include assigning the LBS weight to each segment of the deformation axis with respect to each point of the image. 
         [0019]    The assigning of the LBS weight may assign the LBS weight using a bounded biharmonic weights (BBW) scheme. 
         [0020]    Another exemplary embodiment of the present invention provides an image deformation method using a deformation axis, the method including: receiving, from a user, a reference axis that is a reference of image deformation; deforming the deformation axis based on deformation energy of points in the case of deforming the deformation axis including a plurality of points predetermined with respect to an image according to the reference axis; and deforming the image using a plurality of segments of the deformation axis divided based on points of the deformed deformation axis. 
         [0021]    Still another exemplary embodiment of the present invention provides an image deformation apparatus using a deformation axis, the apparatus including: an intermediate shape generator configured to generate an intermediate shape that is figures formed along at least one deformation axis including a plurality of points predetermined with respect to an image to be deformed, and surrounding a portion of the deformation axis; a deformation axis deformer configured to deform the deformation axis based on deformation energy of the points according to the deformation of the deformation axis; and an image deformer configured to deform the image through deforming the intermediate shape using a plurality of segments of the deformation axis divided based on points of the deformed deformation axis. 
         [0022]    Yet another exemplary embodiment of the present invention provides an image deformation apparatus using a deformation axis, the apparatus including: a deformation axis deformer configured to deform the deformation axis based on deformation energy of points according to deformation of at least one deformation axis including a plurality of points predetermined with respect to an image to be deformed; and an image deformer configured to deform the image using a plurality of segments of the deformation axis divided based on points of the deformed deformation axis. 
         [0023]    The image deformer may deform the image using an LBS weight assigned to each segment of the deformation axis with respect to each point of the image. 
         [0024]    The image deformation apparatus using the formation axis may further include an LBS weight assigner configured to assign the LBS weight to each segment of the deformation axis with respect to each point of the image. 
         [0025]    The LBS weight assigner may assign the LBS weight using a BBW scheme. 
         [0026]    According to exemplary embodiments of the present invention, an image deformation method using a deformation axis is performed based on a freeform deformation axis (FDA) that is independent from a type of an original object and thus, may be more advantageous and may be utilized in combination with various types of existing deformation methods. Deformation of an image may be performed intuitively with small calculation cost and in real time and thus, may be easily used by general users 
         [0027]    The foregoing summary is illustrative only and is not intended to be in any way limiting. In addition to the illustrative aspects, embodiments, and features described above, further aspects, embodiments, and features will become apparent by reference to the drawings and the following detailed description. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0028]      FIG. 1  is a flowchart illustrating an image deformation method using a deformation axis according to an exemplary embodiment of the present invention. 
           [0029]      FIG. 2  is a flowchart illustrating in detail an operation of deforming the deformation axis in the image deformation method using the deformation axis according to an exemplary embodiment of the present invention. 
           [0030]      FIG. 3  is a flowchart illustrating an intermediate shape generation operation in the image deformation method using the deformation axis according to an exemplary embodiment of the present invention. 
           [0031]      FIG. 4  is a flowchart illustrating in detail an intermediate shape generation operation in the image deformation method using the deformation axis according to an exemplary embodiment of the present invention. 
           [0032]      FIG. 5  is an exemplary diagram illustrating an example of generating the intermediate shape in the image deformation method using the deformation axis according to an exemplary embodiment of the present invention. 
           [0033]      FIG. 6  is a flowchart illustrating in detail an image deformation operation in the image deformation method using the deformation axis according to an exemplary embodiment of the present invention. 
           [0034]      FIG. 7  is an exemplary diagram illustrating an example of deforming an image in the image deformation method using the deformation axis according to an exemplary embodiment of the present invention. 
           [0035]      FIGS. 8 through 10  are exemplary diagrams illustrating an example of the image deformation method using the deformation axis according to an exemplary embodiment of the present invention. 
           [0036]      FIG. 11  is a block diagram illustrating an image deformation apparatus using a deformation axis according to an exemplary embodiment of the present invention. 
           [0037]      FIG. 12  is a flowchart illustrating a linear blend skinning (LBS) weight assignment operation in an image deformation method using a deformation axis according to another exemplary embodiment of the present invention. 
           [0038]      FIG. 13  is a flowchart illustrating in detail the LBS weight assignment operation in the image deformation method using the deformation axis according to another exemplary embodiment of the present invention. 
           [0039]      FIG. 14  illustrates an example of assigning a weight about each portion of a deformation axis by applying a bounded biharmonic weights (BBW) scheme to each point of an image. 
           [0040]      FIG. 15  is a block diagram illustrating an image deformation apparatus using a deformation axis according to another exemplary embodiment of the present invention. 
       
    
    
       [0041]    It should be understood that the appended drawings are not necessarily to scale, presenting a somewhat simplified representation of various features illustrative of the basic principles of the invention. The specific design features of the present invention as disclosed herein, including, for example, specific dimensions, orientations, locations, and shapes will be determined in part by the particular intended application and use environment. 
         [0042]    In the figures, reference numbers refer to the same or equivalent parts of the present invention throughout the several figures of the drawing. 
       DETAILED DESCRIPTION 
       [0043]    The following description simply exemplifies a principle of the invention. Accordingly, even though not clearly described or illustrated in the present specification, those skilled in the art may configure the principle of the invention and may invent a variety of apparatuses included in the concept and scope of the invention. All of the conditional terminologies and exemplary embodiments enumerated in the present specification are clearly intended only for the purpose of understanding the concept of the invention, in principle. Accordingly, the invention should not be understood to be limited to the exemplary embodiments and states particularly enumerated as above. 
         [0044]    The aforementioned objects, features, and advantages will become further obvious through the following detailed description which is associated with the accompanying drawings and accordingly, those skilled in the art may easily implement the technical spirit of the invention. When it is determined that the detailed description related to a related known function or configuration may make the purpose of the present invention unnecessarily ambiguous in describing the invention, the detailed description will be omitted herein. Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. 
         [0045]      FIG. 1  is a flowchart illustrating an image deformation method using a deformation axis according to an exemplary embodiment of the present invention. Referring to  FIG. 1 , the image deformation method according to the present exemplary embodiment includes an operation of deforming a deformation axis S 100  and an image deformation operation S 200 . 
         [0046]    In the case of deforming an image, the operation of deforming the deformation axis S 100  deforms the deformation axis based on deformation energy of points according to deformation of at least one deformation axis including a plurality of points predetermined with respect to the image. 
         [0047]    In the present exemplary embodiment, the deformation axis (freeform deformation axis (FDA)) is an axis that is a reference of deformation of the image desired to be deformed, and may be determined based on an input of a user or according to a predetermined algorithm, and may be formed as a curve having various thicknesses. The deformation axis may be determined based on a freeform drawn by the user and may be determined to be approximate to a central axis of an object. 
         [0048]    An image deformation method according to an exemplary embodiment of the present invention is performed through deforming a called intermediate shape that uses the deformation axis as an axis through deformation of the deformation axis, instead of deforming an image of an actual object. The intermediate shape indicates figures that are formed along the deformation axis and surround a portion of the deformation axis. The intermediate shape may have various thickness values according to the deformation axis, and the intermediate shape is deformed based on the deformation axis. 
         [0049]    Accordingly, referring to  FIG. 3 , the image deformation method according to the present exemplary embodiment may further include an intermediate shape generation operation S 50 . 
         [0050]    As described above, the intermediate shape generation operation S 50  generates the intermediate shape that uses the deformation axis as the axis, and the image deformation operation S 200  deforms the image through deforming the intermediate shape. 
         [0051]    Further describing in detail the intermediate shape generation operation S 50  with reference to  FIG. 4 , the intermediate shape generation operation S 50  according to the present exemplary embodiment includes a deformation axis input operation S 52 , a segmental point determination operation S 54 , a B-spline curving operation S 56 , and an offset use intermediate shape generation operation S 58 . 
         [0052]    The deformation axis input operation S 52  receives an axis that is a reference of deformation with respect to an object image by the user or receives, as the deformation axis, a central axis that is extracted according to a predetermined algorithm, for example, an algorithm of extracting a central axis of the object image. 
         [0053]    The segmental point determination operation S 54  determines segmental points with respect to the received deformation axis. The segmental points are positioned on the determined deformation axis and have a predetermined interval. Further detail segmentation for deformation of the image may be performed at intervals of the segmental points, and an amount of calculation for the image deformation may be adjusted. The segmental points may be formed at identical intervals, or may be formed at various intervals based on a curvature of the deformation axis or a property of the object. 
         [0054]    The B-spline curving operation S 56  forms a curve using the determined segmental points. A B-spline curve is in a smooth shape compared to a Hermite curve or a Bezier curve and is a curve defined so that a primary derived function and a secondary derived function of both end points may continue when three-dimensionally indicating a curve. In the present exemplary embodiment, the B-spline curve forms a mixed divisional polynomial curve based on the segmental points. That is, in the present exemplary embodiment, the deformation axis may be obtained by deforming the received deformation axis to a spline curve in a further smooth shape according to an input of the user or the predetermined algorithm through the B-spline curving operation S 56 . 
         [0055]    The offset use intermediate shape generation operation S 58  generates the intermediate shape through a plurality of points or lines having a predetermined interval with respect to the curve determined in the B-spline curving operation S 56 . 
         [0056]    In the present exemplary embodiment, the offset use intermediate shape generation operation S 58  may form the intermediate shape to be in a rectangular grating according to the deformation axis. That is, each of the points of the deformation axis has a predetermined interval and has an offset point positioned on a normal line with respect to each segment divided based on segmental points of the deformation axis. The offset use intermediate shape generation operation S 58  may generate, as the intermediate shape, the rectangular grating configured using a line that connects each offset point. 
         [0057]    The offset use intermediate shape generation operation S 58  may generate the intermediate shape through two offset curves having a predetermined interval with respect to the deformation axis. An offset curve may be defined using two parameters. A smooth curve with respect to both sides of the deformation axis may be obtained based on a distance from the deformation axis and a distance along the deformation axis. The offset use intermediate shape generation operation S 58  generates the intermediate shape of a mesh structure through offset curves of both sides. 
         [0058]    Describing with reference to  FIG. 5 , the intermediate shape generation operation S 50  according to the present exemplary embodiment receives a deformation axis drawn by a user ( 510 ), and determines segmental points with respect to the received deformation axis ( 520 ). 
         [0059]    The intermediate shape generation operation S 50  generates a B-spline curve using the determined segmental points ( 530 ) and generates an intermediate shape using a predetermined offset by using the generated B-spline curve as the deformation axis ( 540 ). 
         [0060]    Hereinafter, the operation of deforming the deformation axis S 100  will be further described with reference to  FIG. 2 . Referring to  FIG. 2 , in the present exemplary embodiment, the operation of deforming the deformation axis S 100  includes an image deformation input operation S 110 , a segment length input operation S 120 , a Laplacian coordinates input operation S 130 , a deformation energy calculation operation S 140 , and a deformation axis deformation operation S 150 . 
         [0061]    The image deformation input operation S 110  is an operation of receiving deformation of an image desired to be deformed by the user. In the present exemplary embodiment, as described above, the image deformation input operation S 110  generates the intermediate shape that uses the deformation axis as an axis, and the image deformation operation S 200  deforms the image through deforming the intermediate shape and thus, receives deformation of the deformation axis formed in the intermediate shape generation operation S 50 . 
         [0062]    The intermediate shape includes a contour of a target image desired to be deformed and is a further simplified image. Accordingly, in the present exemplary embodiment, to deform the image through deforming the intermediate shape indicates to deform the intermediate shape in correspondence to the target image. 
         [0063]    Referring to  FIG. 8 , in the present exemplary embodiment, the deformation of the image may be performed based on control points set with respect to the deformation axis. The control points may include a fixing control point to limit a position/rotation and a rotation control point to limit only a position. In the present exemplary embodiment, the image deformation may be performed through the fixing control point and the rotation control point. That is, the image deformation input operation S 110  inputs a deformation  80  of the image by selecting and moving a rotation control point  83  that the user desires to deform with respect to a fixing control point  81  set with respect to an axis. 
         [0064]    The image deformation method according to the present exemplary embodiment uses, as an input, x and y coordinates about points of the deformation axis and uses, as an output, x and y coordinates about a position of a rotation control point that minimizes distortion of a curve. A curve of the deformation axis may be represented as a graph (V, E). Here, V denotes a set of n points and E denotes set of m segments that are divided into points. 
         [0065]    As described above, the image deformation method according to the present exemplary embodiment is based on minimizing deformation energy according to deformation of an image. In minimizing energy, image deformation is performed through minimizing deformation energy of the deformation axis and thus, is simple compared to other methods of considering the overall deformation energy of the image. In the present exemplary embodiment, the deformation energy according to the deformation of the deformation axis may be calculated based on a segment length and Laplacian coordinates. 
         [0066]    Therefore, the operation of deforming the deformation axis S 100  according to the present exemplary embodiment deforms the deformation axis based on deformation energy of points calculated using a length of a segment of the deformation axis divided based on a plurality of points and Laplacian coordinates about the plurality of points. The deformation axis may be deformed to minimize the deformation energy of points in the case of deforming the image. Hereinafter, each operation for calculating the deformation energy will be further described in detail. 
         [0067]    The segment length input operation S 120  receives the length of the segment divided based on the plurality of points of the aforementioned deformation axis. The operation of deforming the deformation axis S 100  according to the present exemplary embodiment is to maintain a length of each segment during the deformation and the length of each segment may be expressed as Equation 1. 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                       ∈ 
                       E 
                     
                   
                    
                   
                     
                        
                       
                         
                            
                           
                             
                               v 
                               i 
                             
                             - 
                             
                               v 
                               j 
                             
                           
                            
                         
                         - 
                         
                            
                           
                             
                               v 
                               i 
                               0 
                             
                             - 
                             
                               v 
                               j 
                               0 
                             
                           
                            
                         
                       
                        
                     
                     2 
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     1 
                   
                   ] 
                 
               
             
           
         
       
     
         [0068]    Here, v 0  denotes coordinates of a point before deformation and v denotes coordinates of a point on a curve of the deformation (matrix) after deformation. 
         [0069]    Equation 1 may be expressed again as Equation 2. 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                       ∈ 
                       E 
                     
                   
                    
                   
                     
                        
                       
                         
                           ( 
                           
                             
                               v 
                               i 
                             
                             - 
                             
                               v 
                               j 
                             
                           
                           ) 
                         
                         - 
                         
                           e 
                            
                           
                             ( 
                             
                               
                                 v 
                                 i 
                               
                               , 
                               
                                 v 
                                 j 
                               
                             
                             ) 
                           
                         
                       
                        
                     
                     2 
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
         [0070]    Here, 
         [0000]    
       
         
           
             
               
                 e 
                  
                 
                   ( 
                   
                     
                       v 
                       i 
                     
                     , 
                     
                       v 
                       j 
                     
                   
                   ) 
                 
               
               = 
               
                 
                   
                     
                       l 
                       
                         i 
                         , 
                         j 
                       
                     
                     ~ 
                   
                   
                     l 
                     
                       i 
                       , 
                       j 
                     
                   
                 
                  
                 
                   ( 
                   
                     
                       v 
                       i 
                     
                     - 
                     
                       v 
                       j 
                     
                   
                   ) 
                 
               
             
             , 
           
         
       
     
         [0000]    {tilde over (l)}{tilde over (l i,j )} denotes a length of a segment (i, j) before deformation, and l i,j  denotes a length of a segment after deformation. 
         [0071]    Equation 2 may be expressed in a form of a matrix as Equation 3. 
         [0000]      ∥ HV−e ( V )∥ 2   [Equation 3]
 
         [0072]    Here, H denotes an m×n matrix. 
         [0073]    Therefore, the segment length input operation S 120  according to the present exemplary embodiment receives a calculation result of the segment length according to the aforementioned equation. 
         [0074]    The Laplacian coordinates input operation S 130  receives Laplacian coordinates of the deformation axis. 
         [0075]    Laplacian coordinates δ i  about each point v i  is expressed through a difference between the point v i  and the average coordinates of neighboring points thereof. 
         [0076]    That is, the Laplacian coordinates are expressed as Equation 4. 
         [0000]                ( v′   i )= v′   i −( v′   i−1   +v′   i+1 )/2  [Equation 4]
 
         [0077]    Here, v′ i−1  and v′ i+1  denote neighboring points of the point v i  and L denotes an Laplacian operator. It indicates a position of a point between neighboring points. The operation of deforming the deformation axis S 100  according to the present exemplary embodiment is to maintain Laplacian coordinates during the deformation and the deformation energy may be expressed as Equation 5. 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       i 
                       ∈ 
                       V 
                     
                   
                    
                   
                     
                        
                       
                         
                           ℒ 
                            
                           
                             ( 
                             
                               v 
                               i 
                               ′ 
                             
                             ) 
                           
                         
                         - 
                         
                           δ 
                           i 
                         
                       
                        
                     
                     2 
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     5 
                   
                   ] 
                 
               
             
           
         
       
     
         [0078]    Here, δ i  denotes Laplacian coordinates about the point v i  and δ i =v i −(v′ i−1 v′ i+1 )/2. Equation 5 may be expressed in a form of a matrix as shown in Equation 6. 
         [0000]      ∥ LV− δ( V )∥ 2   [Equation 6]
 
         [0079]    Here, V includes a position about each of points on the deformation axis and L denotes an (m−1)×n Laplacian matrix. δ denotes a vector on the Laplacian coordinates. 
         [0080]    Therefore, the Laplacian coordinates input operation S 130  according to the present exemplary embodiment receives Laplacian coordinates about each of points according to the aforementioned equation. 
         [0081]    The deformation energy calculation operation S 140  calculates deformation energy of the deformation axis using the received segment length and Laplacian coordinates. To control the image deformation according to the present exemplary embodiment, a condition for limiting a position of a point and a segment length may be assigned. The deformation energy according to the position deformation of all of the points on the deformation axis according to the present exemplary embodiment to which the above condition is applied is expressed as shown in Equation 7. 
         [0000]        w   e   ∥HV−e ( V )∥ 2   +w   l   ∥LV− δ( V )∥ 2   +w   p   ∥C   p   V−U∥   2   +w   e   ∥C   e   V−W∥   2   [Equation 7]
 
         [0082]    Here, ∥C p V−U∥ denotes an item for limiting the position of the point. In this instance, C p  denotes a point-indexing matrix for limiting the position and U includes target positions of points. 
         [0083]    ∥C e V−W∥ denotes an item for limiting the segment length. In this instance, C e  denotes a point-indexing matrix for limiting the segment length and W denotes a position of a target segment. 
         [0084]    w e  denotes a weight about the segment length and w l  denotes a weight about Laplacian coordinates. w p  denotes a weight about a position. The deformation energy calculation operation S 140  calculates a deformation position about all of the points through minimizing a sum of deformation energies of Equation 7. 
         [0085]    According to an exemplary embodiment of the present invention, weights of Equation 7 may be variable. In particular, the weight w l  about Laplacian coordinates may be variable according to Laplacian coordinates. Here, according to an increase in the weight w l , a position of a point corresponding to the corresponding Laplacian coordinates is relatively less deformed. According to a decrease in the weight w l , a position of a point corresponding to the corresponding Laplacian coordinates is relatively greatly deformed. Accordingly, as a result, in the deformation axis, a portion corresponding to the great weight w l  is relatively less bent and a portion corresponding to the small w l  is relatively greatly bent. 
         [0086]    Meanwhile, Equation 7 may be reconverted in a form of Equation 8. 
         [0000]    
       
         
           
             
               
                 
                   min 
                    
                   
                     
                        
                       
                         
                           A 
                            
                           
                               
                           
                            
                           V 
                         
                         - 
                         
                           b 
                            
                           
                             ( 
                             V 
                             ) 
                           
                         
                       
                        
                     
                     2 
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     8 
                   
                   ] 
                 
               
             
           
         
       
     
         [0087]    Here, 
         [0000]    
       
         
           
             
               
                 
                   
                     A 
                     = 
                     
                       ( 
                       
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 e 
                               
                                
                               H 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 l 
                               
                                
                               L 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 p 
                               
                                
                               
                                 C 
                                 p 
                               
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 e 
                               
                                
                               
                                 C 
                                 e 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                   , 
                 
               
               
                 
                   
                     b 
                      
                     
                       ( 
                       V 
                       ) 
                     
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 e 
                               
                                
                               
                                 e 
                                  
                                 
                                   ( 
                                   V 
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 l 
                               
                                
                               
                                 δ 
                                  
                                 
                                   ( 
                                   V 
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 p 
                               
                                
                               U 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 w 
                                 e 
                               
                                
                               W 
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0000]    In the present exemplary embodiment, the deformation energy is a nonlinear least square method and b is dependent to V and a matrix is dependent only to an initial shape. In the present exemplary embodiment, an energy minimization issue may be solved using a repetitive Gauss Newton method. 
         [0088]    To use the repetitive Gauss Newton method, Equation 7 may be expressed as Equation 9. 
         [0000]    
       
         
           
             
               
                 
                   
                     min 
                     
                       V 
                       
                         k 
                         + 
                         1 
                       
                     
                   
                    
                   
                     
                        
                       
                         
                           A 
                            
                           
                               
                           
                            
                           
                             V 
                             
                               k 
                               + 
                               1 
                             
                           
                         
                         - 
                         
                           b 
                            
                           
                             ( 
                             
                               V 
                               k 
                             
                             ) 
                           
                         
                       
                        
                     
                     2 
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     9 
                   
                   ] 
                 
               
             
           
         
       
     
         [0089]    V k  denotes coordinates of a point through k repetitions and V k+1  denotes coordinates desired to be obtained through subsequent repetition. 
         [0090]    Equation 9 is provided in a form of a standard linear least square method and a solution thereof is given by Equation 10. 
         [0000]        V   k+1 =( A   T   A ) −1   A   T   b ( V   k )  [Equation 10]
 
         [0091]    Equation 10 may be expressed again as Equation 11. 
         [0000]        V   k+1   =Gb ( V   k )  [Equation 11]
 
         [0092]    Here, G=(A T A) −1 A T  and may be expressed again as Equation 12. As described above, A may be dependent only to the initial shape and G may be recalculated before deformation. 
         [0093]    In repetitive execution, b is calculated through coordinates V k  of a point calculated through a previous repetition. Accordingly, only δ(V k ) and e(V k ) need to be calculated for each repetition. 
         [0094]    e(V k ) may be calculated through the following Equation 12. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       e 
                        
                       
                         ( 
                         
                           
                             v 
                             i 
                             k 
                           
                           , 
                           
                             v 
                             j 
                             k 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           
                             l 
                             
                               i 
                               , 
                               j 
                             
                           
                           ~ 
                         
                         
                            
                           
                             
                               v 
                               i 
                               k 
                             
                             - 
                             
                               v 
                               j 
                               k 
                             
                           
                            
                         
                       
                        
                       
                         ( 
                         
                           
                             v 
                             i 
                             k 
                           
                           - 
                           
                             v 
                             j 
                             k 
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
                       for 
                        
                       
                           
                       
                        
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                     
                     ∈ 
                     E 
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     12 
                   
                   ] 
                 
               
             
           
         
       
     
         [0095]    To calculate Laplacian coordinates δ(V k ), initial Laplacian coordinates are required. When deformation is absent in a difference between a plurality of sets of coordinates, a deformation energy item for a simple rotation of the object needs to be “0, but deformation energy for instantaneous calculation is not “0” and v i  belonging to V is rotatable. Here, Laplacian coordinates δ(V k ) about v i  are expressed as Equation 13. 
         [0000]      δ( v   i   k )= R   i   k δ( v   i   0 )  [Equation 13]
 
         [0096]    Here, δ(v i   0 ) denotes initial Laplacian coordinates and R i   k  is calculated through a minimization process of the following Equation 14. 
         [0000]    
       
         
           
             
               
                 
                   
                     R 
                     i 
                     k 
                   
                   = 
                   
                     arg 
                      
                     
                         
                     
                      
                     
                       
                         min 
                         
                           R 
                           i 
                           k 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             
                               ( 
                               
                                 i 
                                 , 
                                 j 
                               
                               ) 
                             
                             ∈ 
                             E 
                           
                         
                          
                         
                           
                              
                             
                               
                                 
                                   R 
                                   i 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       v 
                                       j 
                                       0 
                                     
                                     - 
                                     
                                       v 
                                       i 
                                       0 
                                     
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 ( 
                                 
                                   
                                     v 
                                     j 
                                     k 
                                   
                                   - 
                                   
                                     v 
                                     i 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                              
                           
                           2 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     14 
                   
                   ] 
                 
               
             
           
         
       
     
         [0097]    The deformation with the minimum deformation energy is performed through a process of differentiating all of the coefficients of R i   k  and making a sum thereof become “0”. Equation 14 may be deformed to Equation 15. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       R 
                       i 
                       k 
                     
                     = 
                     
                       
                         ∑ 
                         
                           
                             ( 
                             
                               i 
                               , 
                               j 
                             
                             ) 
                           
                           ∈ 
                           E 
                         
                       
                        
                       
                         
                           ( 
                           
                             
                               v 
                               j 
                               k 
                             
                             - 
                             
                               v 
                               i 
                               k 
                             
                           
                           ) 
                         
                          
                         
                           
                             ( 
                             
                               
                                 v 
                                 j 
                                 0 
                               
                               - 
                               
                                 v 
                                 i 
                                 0 
                               
                             
                             ) 
                           
                           T 
                         
                          
                         
                           D 
                           i 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     Here 
                     , 
                     
                       
                         D 
                         i 
                       
                       = 
                       
                         
                           ( 
                           
                             
                               ∑ 
                               
                                 
                                   ( 
                                   
                                     i 
                                     , 
                                     j 
                                   
                                   ) 
                                 
                                 ∈ 
                                 E 
                               
                             
                              
                             
                               
                                 ( 
                                 
                                   
                                     v 
                                     j 
                                     0 
                                   
                                   - 
                                   
                                     v 
                                     i 
                                     0 
                                   
                                 
                                 ) 
                               
                                
                               
                                 
                                   ( 
                                   
                                     
                                       v 
                                       j 
                                       0 
                                     
                                     - 
                                     
                                       v 
                                       i 
                                       0 
                                     
                                   
                                   ) 
                                 
                                 T 
                               
                             
                           
                           ) 
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                      
                     
                         
                     
                      
                     15 
                   
                   ] 
                 
               
             
           
         
       
     
         [0000]    and may be calculated in advance. 
         [0098]    The operation of deforming the deformation axis S 100  according to the aforementioned present exemplary embodiment calculates the deformation energy of all of the points on the deformation axis through the aforementioned process (S 140 ) and deforms the deformation axis by determining a position for minimizing the deformation energy (S 150 ). 
         [0099]    Hereinafter, the operation of deforming the image using the deformed deformation axis (S 200 ) will be described. 
         [0100]    The image deformation operation S 200  deforms the image using a plurality of segments of the deformation axis divided based on points of the deformed deformation axis. That is, the image deformation operation S 200  deforms an intermediate shape based on a before-deformation width and an after-deformation width of the intermediate shape. 
         [0101]    Referring to  FIG. 6 , the image deformation operation S 200  includes a segment length input operation S 210  and an intermediate shape thickness determination operation S 220 . The segment length input operation S 210  receives lengths of a plurality of segments of the deformation axis divided based on points of the deformed deformation axis. 
         [0102]    Referring to  FIG. 7 , the intermediate shape thickness determination operation S 220  compares the received length of after-deformation segment and length of before-deformation segment and increases a thickness of the intermediate shape when the length of segment is decreased, and decreases the thickness when the length of segment is increased. That is, to consider the before-deformation width and the after-deformation width of the intermediate shape in the present exemplary embodiment is to maintain widths of the deformed intermediate shape and an original intermediate shape, and the thickness is determined based on a change in the length of the segment of the deformation axis. 
         [0103]    The image deformation method using the deformation axis according to the present exemplary embodiment may deform a shape through the intermediate shape with respect to each axis by combining a plurality of axes  92  and  93  as illustrated in  FIG. 9 . As illustrated in  FIG. 10 , the image deformation method may form an image having a shape according to an axis drawn by a user, instead of deforming the axis. 
         [0104]    In an image deformation method according to another exemplary embodiment of the present invention, the image deformation operation S 200  may deform an image by applying a linear blend skinning (LBS) to an image according to a deformed deformation image, instead of deforming the image using the intermediate shape as described above. 
         [0105]    The LBS is also referred to as skeletal subspace deformation (SSD) and is an image deformation method that has been typically utilized for a skeleton based animation and a method of deforming a given shape according to an influence power of each skeleton. The LBS method enables an overlapping portion such as a joint to be smoothly deformed by appropriately mixing a weight of each point of the shape with respect to each skeleton. 
         [0106]    According to an exemplary embodiment of the present invention, to apply the LBS to the image according to the deformed deformation axis, the aforementioned intermediate shape generation operation S 50  of  FIG. 3  is replaced with an LBS weight assignment operation S 60  of  FIG. 12 . The LBS weight assignment operation S 60  assigns an LBS weight to each portion of the deformation axis with respect to each point of the image and the image deformation operation S 200  deforms the image according to the LBS weight of each point. 
         [0107]      FIG. 13  is a flowchart illustrating in detail the LBS weight assignment operation S 60 , and includes a deformation axis input operation S 52 , a segmental point determination operation S 54 , a B-spline curving operation S 56 , and an LBS weight assignment operation S 68 . The deformation axis input operation S 52 , the segmental point determination operation S 54 , and the B-spline curving operation S 56  are the same as described above with reference to  FIG. 4  and thus, a description relating thereto will be omitted. 
         [0108]    The LBS weight assignment operation S 68  assigns the LBS weight about each segment of the deformation axis with respect to each point of the image. To assign the LBS weight about each segment of the deformation axis with respect to each point of the image, a user may designate appropriate weight values and weight values may be automatically calculated. For example, a bounded biharmonic weights (BBW) method and the like may be used to automatically calculate the weight values. 
         [0109]      FIG. 14  illustrates an example in which a weight about each portion of the deformation axis is assigned by applying a BBW method to each point of a monkey image. Referring to  FIG. 13 , whether each point of the image has a great weight compared to a predetermined portion of the deformation axis is expressed in colors. For example, as illustrated in  FIG. 14 , points of a torso have a great weight compared to a deformation axis of a torso side and points of an arm have a great value compared to a deformation axis of an arm side. 
         [0110]    Hereinafter, an image deformation apparatus  10  for performing the image deformation method using the deformation axis according to an exemplary embodiment of the present invention will be described with reference to  FIG. 11 . 
         [0111]    Referring to  FIG. 11 , the image deformation apparatus  10  using the deformation axis according to the present exemplary embodiment includes an intermediate shape generator  50 , a deformation axis deformer  100 , and an image deformer  200 . 
         [0112]    The intermediate shape generator  50  generates an intermediate shape that uses the deformation axis as an axis (S 50 ). 
         [0113]    In the case of deforming an image, the deformation axis deformer  100  deforms the deformation axis based on deformation energy of points according to a deformation of at least one deformation axis including a plurality of points predetermined with respect to the image. 
         [0114]    The image deformer  200  deforms the image using a plurality of segments of the deformation axis divided based on points of the deformation axis (S 200 ). As described above, image deformation according to the present exemplary embodiment is performed through deforming the intermediate shape that uses the deformation axis as the axis, instead of deforming an image of an actual object. 
         [0115]    The above each configuration is to perform an operation of the image deformation method using the deformation axis and the intermediate shape according to the aforementioned exemplary embodiment corresponding to each configuration and thus, a further detailed description relating thereto will be omitted. 
         [0116]    Hereinafter, an image deformation apparatus  20  for performing the image deformation method using the deformation axis according to another exemplar embodiment of the present invention will be described with reference to  FIG. 15 . 
         [0117]    Referring to  FIG. 15 , the image deformation apparatus  20  using the deformation axis according to the present exemplary embodiment includes an LBS weight assigner  60 , a deformation axis deformer  100 , and an image deformer  210 . 
         [0118]    The LBS weight assigner  60  assigns an LBS weight about each segment of the deformation axis with respect to each point of the image. 
         [0119]    In the case of deforming the image, the deformation axis deformer  100  deforms the deformation axis based on deformation energy of points according to deformation of at least one deformation axis including a plurality of points predetermined with respect to the image. 
         [0120]    The image deformer  210  deforms the image using the LBS weight of each point of the image according to the deformed deformation axis. 
         [0121]    The above each configuration is to perform an operation of the image deformation method using the deformation axis and the LBS weight according to the aforementioned exemplary embodiment corresponding to each configuration and thus, a further detailed description relating thereto will be omitted. 
         [0122]    Meanwhile, the image deformation method using the deformation axis of the present invention may be configured in a form of a computer-readable code in computer-readable media. The computer-readable media includes all the types of recording devices storing data readable by a computer system. 
         [0123]    Examples of the computer-readable media may include ROM, RAM, CD-ROM, magnetic tapes, floppy disks, optical data storage devices, and the like. The computer-readable media may be distributed over a computer system connected through a network and thereby a computer readable code using a distributive scheme may be stored and executed. Functional programs, codes, and code segments for realizing the present invention may be easily inferred by programmers in the art. 
         [0124]    As described above, the exemplary embodiments have been described and illustrated in the drawings and the specification. The exemplary embodiments were chosen and described in order to explain certain principles of the invention and their practical application, to thereby enable others skilled in the art to make and utilize various exemplary embodiments of the present invention, as well as various alternatives and modifications thereof. As is evident from the foregoing description, certain aspects of the present invention are not limited by the particular details of the examples illustrated herein, and it is therefore contemplated that other modifications and applications, or equivalents thereof, will occur to those skilled in the art. Many changes, modifications, variations and other uses and applications of the present construction will, however, become apparent to those skilled in the art after considering the specification and the accompanying drawings. All such changes, modifications, variations and other uses and applications which do not depart from the spirit and scope of the invention are deemed to be covered by the invention which is limited only by the claims which follow.