Abstract:
The invention discloses a method for single-view hair modeling and portrait editing. The method is capable of 3D structure reconstruction for individual&#39;s hairstyle in an input image, and it requires only a small amount of user inputs to bring about a variety of portrait editing functions; after steps of image preprocessing, 3D head model reconstruction, 2D strands extraction and 3D hairstyle reconstruction, the method finally achieves portrait editing functions such as portrait pop-ups, hairstyle replacements, hairstyle editing, etc.; the invention discloses a method for creating a 3D hair model from a single portrait view for the first time, thereby bringing about a series of practical portrait hairstyle editing functions, of which the effect is superior to methods in the prior art, and having features such as simple interactions and highly efficient calculations.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of International Application No. PCT/CN2012/078202, filed on Jul. 5, 2012, which claims the priority benefit of Chinese Patent Application No. 201210207183.5, filed on Jun. 20, 2012, both of which are hereby incorporated by reference in their entireties. 
    
    
     TECHNICAL FIELD 
     The present invention relates to the field of image processing and, in particular, to a method for single-view hair modeling and portrait editing. 
     BACKGROUND 
     The background pertaining to the present invention is as follows: 
     I. Portrait Editing 
     Because a human portrait is a major component of photographs, as well as one of the image types of the greatest interest, portrait editing is of substantial application merits. 
     While there exist some portrait editing methods directly working in the two-dimensional (2D) image space such as face beautification (Leyvand, T., Cohen-Or, D., Dror, G., and Lischinski, D. 2008. Data-driven enhancement of facial attractiveness. ACM Trans. Graph. 27, 3, 38:1-38:9.), face swapping without giving source (Bitouk, D., Kumar, N., Dhillon, S., Belhumeur, P. N., and Nayar, S. K. 2008. Face Swapping: Automatically replacing faces in photographs. ACM Trans. Graph. 27, 39:1-39:8.), face enhancement (Joshi, N., Matusik, W., Adelson, E. H., and Kriegman, D. J. 2010. Personal photo enhancement using example images. ACM Trans. Graph. 29, 3, 12:1-12:15.), there is a trend recently in mapping 2D images to three-dimensional (3D) models for more complex applications, such as reshaping of human bodies (Zhou, S., Fu, H., Liu, L., Cohen-Or, D., and Han, X. 2010. Parametric reshaping of human bodies in images. ACM Trans. Graph. 29, 4, 126:1-126:10.), face swapping with source given (Dale, K., Sunkavalli, K., Johnson, M. K., Vlasic, D., Matusik, W., and Pfister, H. 2011. Video face replacement. ACM Trans. Graph. 30, 6, 130:1-130:10.), face component transfer (Yang, F., Wang, J., Shechtman, E., Bourdev, L., and Metaxas, D. 2011. Expression flow for 3D-aware face component transfer. ACM Trans. Graph. 30, 4, 60:1-60:10.), and face animations from large image collections (Shlizerman, I. K., Shechtman, E., Garg, R., and Seitz, S. M. 2011. Exploring photobios. ACM Trans. Graph. 30, 4, 61:1-61:9.), etc. 
     The specialized 3D model information may enable the portrait editing process to understand fundamentally intricate semantic information contained in an image, and better resolve numerous practical problems caused by ambiguities and occlusions in the destination image. 
     In view of these researches, the present invention has brought about many new portrait hairstyle editing functions by creating a strand-based 3D hair model for a person&#39;s portrait hairstyle. 
     II. Hair Modeling 
     Hair modeling is an extensively studied problem in computer graphics, see document below for a comprehensive survey (Ward, K., Bertails, F., Kim, T.-Y., Marschner, S. R., Cani, M.-P., and Lin, M. C. 2007. A survey on hair modeling: styling, simulation, and rendering. IEEE Transactions on Visualization and Computer Graphics 13, 2, 213-234.). The method according to the present invention is most related to image-based hair capture methods thereof, including “Paris, S., Briceno, H., and Sillion, F. 2004. Capture of hair geometry from multiple images. ACM Trans. Graph. 23, 3, 712-719.”, “Wei, Y., Ofek, E., Quan, L., and Shum, H.-Y. 2005. Modeling hair from multiple views. ACM Trans. Graph. 24, 3, 816-820.”, “Paris, S., Chang, W., Kozhushnyan, O. I., Jarosz, W., Matusik, W., Zwicker, M., and Durand, F. 2008. Hair photobooth: geometric and photometric acquisition of real hairstyles. ACM Trans. Graph. 27, 3, 30:1-30:9.”, and “Jakob, W., Moon, J. T., and Marschner, S. 2009. Capturing hair assemblies fiber by fiber. ACM Trans. Graph. 28, 5, 164:1-164:9”. These methods can reconstruct a full 3D model by utilizing multiple hair images taken from different viewpoints, after which the hair model can be rendered in computer graphic applications. Nevertheless, in an application scene of the method according to the present invention, the input is a single image without any knowledge about the hair 3D geometry or the lighting of the scene. Therefore, the method of the present invention aims at generating a plausible high-resolution strand-based hair model for portrait editing applications. 
     III. Single-View 3D Modeling 
     Single-view modeling is in general an ill-posed problem. Focusing on specific objects or scenes (Hoiem, D., Efros, A. A., and Hebert, M. 2005. Automatic photo pop-up. ACM Trans. Graph. 24, 3, 577-584.), a method of pop-up (pop-up) for outdoor photos containing ground, sky, and walls is proposed; “Rivers, A., Igarashi, T., and Durand, F. 2010. 2.5D cartoon models. ACM Trans. Graph. 29, 4, 59:1-59:7.” proposes a 2.5D modeling method for cartoon images which conducts smooth interpolation on a small number of cartoon images taken from different views to make it appears like a 3D object; “Oztireli, A. C., Uyumaz, U., Popa, T., Sheffer, A., and Gross, M. 2011. 3D modeling with a symmetric sketch. In Proceedings of SBIM, 23-30.” proposes a method that extracts a 2.5D model of a bilateral symmetric object from a simple user sketch. 
     SUMMARY 
     The present invention aims at providing a method for single-view hair modeling and portrait editing with respect to the inadequacy of the prior art. By reconstructing 3D hairstyle models in the portrait image, the method can achieve numerous interactive portrait editing functions which are hard to achieve by existing image editing methods, being of highly practical merits. 
     The goal of the present invention is accomplished by the following technical solutions: a method for single-view hair modeling and portrait editing, which includes steps as follows: 
     (1) image preprocessing: segmenting an image into four layers based upon sparse user strokes by adopting a Lazy-Snapping image segmentation method: human hair, human face, human body and background, calculating opacity values in the segmented human hair region by an alpha-matting method for better human hair segmentation, setting apart the foreground color of the segmented human hair region from its background color, and completing occluded portions in the human body region and the background region; 
     (2) 3D head model reconstruction: automatically locating facial feature points by an ASM method, estimating head transformation parameters and fitting a 3D head model by least squares optimization based on the feature points and a 3D head model database after PCA dimension reduction, and carrying out inverse texture mapping in accordance with the segmented human face region obtained by step (1), so as to obtain a texture image of the head model; 
     (3) 2D strands extraction: computing a 2D orientation field and its corresponding confidence map by using a Gabor kernel function within the hair region obtained in step (1), and obtaining a set of sparse 2D strand curves by tracing based on the 2D orientation field and the confidence map; 
     (4) 3D hairstyle reconstruction: carrying out energy optimization in conjunction with the fitted head model according to step (2), coherence among nearby strands and occlusion correlations among strands, solving and obtaining depth information of all 2D strands generated from step (3), volumizing according to the 3D strands so as to obtain an adequately dense 3D strand set around the head as a recovered hairstyle model, and sampling all strand vertices from an original image to obtain hair color values; 
     (5) synthesis and application: carrying out portrait editing applications as portrait pop-ups, hairstyle replacements and hairstyle editing by adopting reconstructed 3D information such as the human hairstyle model, the human head model and so on according to the aforementioned steps (1)-(4). 
     The beneficial effects of the present invention are: the invention guides the portrait editing process by reconstructing a 3D model for a portrait, effectively avoiding the effect of image ambiguities and occlusion; the invention proposes a 3D modeling method for a single-view intricate portrait hairstyle for the first time, which conveniently estimates credible 3D information of a hairstyle and synthesizes a structure for nonhair regions by creating a strand-based 3D hair model, thus being applied to numerous portrait editing applications by coupling with other single-view 3D modeling methods, and enabling related editing effects to conform to actual conditions. In contrast to similar existing portrait editing methods, the invention has more robust adaptability towards various hairstyle types, face orientations, body postures, and backgrounds from a portrait input. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram of segmenting an image through user interaction according to the present invention; 
         FIG. 2  is a diagram of calculating a 2D sparse orientation field for an image according to the present invention; 
         FIG. 3  is a diagram of iteratively refining a 2D sparse orientation field according to the present invention; 
         FIG. 4  is a comparison diagram of a sparse 2D strand curve extracted according to the present invention and a dense strand curve; 
         FIG. 5  is a diagram of a re-centering correction to a 2D strand curve location according to the present invention; 
         FIG. 6  is a rendered image of portrait pop-ups according to the present invention; 
         FIG. 7  is a rendered image of hairstyle replacement according to the present invention. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     The core technology of the invention is to conduct 3D reconstruction on hairstyle in a single-view portrait, and to apply it in various portrait editing applications such as hair modeling, portrait editing, etc. The method is mainly composed of five major steps as follows: image preprocessing, 3D head model reconstruction, 2D strands extraction, 3D hairstyle reconstruction, and synthesis and application. 
     I. image preprocessing: segment an image into four layers based upon sparse user strokes by adopting a Lazy-Snapping image segmentation method: human hair, human face (not occluded by hair), human body and background, calculate opacity values in a segmented human hair region by an alpha-matting method for better human hair segmentation, set apart the foreground color of the segmented human hair region from its background color, and complete occluded portions in the human body region and the background region; as shown in  FIG. 1 , this step is achieved by the following 3 sub-steps: 
     1.1 User-Assisted Image Segmentation 
     Due to the complexities of contents and shapes around its boundary of each layer in the image, there is no way to automatically segment these regions. Therefore, this method segments visible regions of each layer by adopting the Lazy-Snapping technique (Li, Y., Sun, J., Tang, C., and Shum, H. 2004. Lazy snapping. ACM Trans. Graph. 23, 3, 303-308.) where a user assists in indicating a few strokes, and obtains four layers R hair , R face , R body  and R background . 
     1.2 Matting of the Hair Region 
     Since hair is generally translucent and the hair region in an image often has a complicated boundary, the segmented hair region obtained from step 1.1 is approximately correct but not sufficiently accurate for the demand of this method. This method automatically improves a hair segmentation result with the following matting manipulations: 
     1) erode and dilate the hair region R hair  obtained from the image segmentation step assisted by the user to certain widths (the eroding and dilating widths of this method are both a width size of ten pixels, and obtain two new hair regions, R hair   erosion  and R hair   dilation ; 
     2) treat the hair regions R hair , R hair   erosion  and R hair   dilation  obtained from step (1) as a group of trimap, i.e., let the hair opacity of an outer region of the dilated R hair   dilation  be zero, let the hair opacity of an inner region of the eroded R hair   erosion  be one, and solve the hair opacity of a region inside R hair   dilation  and outside R hair   erosion , i.e., the hair boundary region, by the matting method (within the range of (0, 1)). This method adopts a closed-form matting method (Levin, A., Lischinski, D., and Weiss, Y. 2008. A closed-form solution to natural image matting. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 2, 228-242.) to solve and obtain hair opacity values A hair  in the entire image, a foreground color C hair   foreground  (i.e., the hair color without other regions&#39; colors in the image) and a background color C hair   background  (i.e., other regions&#39; colors in the image excluding the hair color) in the hair boundary region, which satisfies:
 
 A   hair   C   hair   foreground +(1− A   hair ) C   hair   background   =C   image ;
 
     3) treat a hair region with opacities obtained from step 2) as an improved hair segmentation result, and within the hair boundary region (the region inside R hair   dilation  and outside R hair   erosion ), treat the foreground color C hair   foreground  as a hair region color and treat the background color C hair   background  as a hair background region (i.e., other layers overlaying the hair at current location) color. 
     1.3 Completing Body and Background Regions 
     Usually, a human body and background will be occluded by the human body, the human hair, etc., when the user manipulates the portrait with interaction, such as rotating the view or changing the hairstyle, the occluded portions may become visible. In order to resolve the problem, this method fills the occluded portions of these two layers by adopting the PatchMatch method (Barnes, C., Shechtman, E., Finkelstein, A., and Goldman, D. B. 2009. PatchMatch: A randomized correspondence algorithm for structural image editing. ACM Trans. Graph. 28, 3, 24:1-24:11.). With respect to the body region, the user needs to interactively indicate a body boundary on the occluded locations. 
     II. 3D head model reconstruction: automatically locate facial feature points by the ASM (Active Shape Model) method, optimally estimate head transformation parameters and fitting a 3D model by least squares optimization based on the feature points and a 3D head model database after PCA (Principle Component Analysis) dimension reduction, and carry out inverse texture mapping in accordance with the segmented human face region obtained by step I, so as to obtain a texture image of a head model; 
     2.1 Localization of Image Facial Feature Points 
     Firstly, carry out the face recognition by adopting the Viola-Jones recognition algorithm, and approximately estimate the size of the human face region. 
     Automatically localize facial feature points of the human face region in the image, the process of which adopts the Active Shape Model (ASM) method (Milborrow, S., and Nicolls, F. 2008. Locating facial features with an extended active shape model. In Proceedings of ECCV&#39;08, Springer, 504-513.) to localize 73 facial feature points (n f =73), including 15 face silhouette feature points, 12 brow feature points (6 each for left and right), 16 eye feature points (8 each for left and right), 12 nose feature points and 18 mouth feature points (12 and 6 for internal silhouette and external silhouette respectively). 
     2.2 Head Model Fitting 
     Utilize the open Basel Face Model database as a head model database, where the coherence of all models thereof on topology structures (same vertex size, indices and connection relationships), and the model scales are normalized. Concatenate all vertices&#39; 3D coordinates of each head model in the database into one vector, S=[P x   1 , P y   1 , P z   1 , . . . , P x   v , P y   v , P z   v ], as one training data sample. Carry out a PCA analysis for all data, and obtain an average data vector  S , the first n p  pivot vectors and corresponding feature values λ (the result of this method let the pivot number n p  be 100). Given any coefficient vector β of the pivot vector, a corresponding head model data vector can be generated:
 
 S*= S +V·β;  
 
     Assume the portrait is in a weak perspective projection model, with respect to a projection matrix R, the manipulation of projecting a 3D point P 3D  onto a 2D image plane is P 2D =R·P 3D ; during the process of head model fitting, define an energy equation E including a feature point error E error  and a parameter penalty E coef  as follows: 
     
       
         
           
             
               E 
               = 
               
                 
                   
                     w 
                     error 
                   
                   ⁢ 
                   
                     E 
                     error 
                   
                 
                 + 
                 
                   
                     w 
                     coef 
                   
                   ⁢ 
                   
                     E 
                     coef 
                   
                 
               
             
             , 
             
               
 
             
             ⁢ 
             
               
                 E 
                 error 
               
               = 
               
                 
                   ∑ 
                   
                     k 
                     = 
                     0 
                   
                   
                     n 
                     f 
                   
                 
                 ⁢ 
                 
                   
                     w 
                     k 
                   
                   ⁢ 
                   
                     
                        
                       
                         
                           R 
                           · 
                           
                             ( 
                             
                               
                                 
                                   S 
                                   _ 
                                 
                                 
                                   ( 
                                   k 
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   V 
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                 · 
                                 β 
                               
                             
                             ) 
                           
                         
                         - 
                         
                           X 
                           k 
                         
                       
                        
                     
                     2 
                   
                 
               
             
             , 
             
               
 
             
             ⁢ 
             
               
                 
                   E 
                   coef 
                 
                 = 
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       0 
                     
                     
                       n 
                       p 
                     
                   
                   ⁢ 
                   
                     
                       ( 
                       
                         
                           β 
                           k 
                         
                         
                           λ 
                           k 
                         
                       
                       ) 
                     
                     2 
                   
                 
               
               ; 
             
           
         
       
     
     Where w k  is a weight of a corresponding feature point, X k  is the localized position of the feature point, and  S   (k)  and V (k)  are corresponding values of the feature point in the head model on an average model and on a feature vector respectively; with respect to a non-silhouette feature point, statically select a certain vertex in the head model as its corresponding point, i.e.:
 
 V   (k)   =V   index(k) ;
 
     However, with respect to the face outline, dynamically select a vertex in the current head model which is closest to the feature point as a corresponding model position of the feature point. 
     Optimize the energy term by the method of least squares, obtain a feature vector coefficient β when ∇ β E=0, and obtain its corresponding head model, which is the fitted result S fit . 
     During the fitting process, according to the current fitted result S fit , this method iteratively estimates a projection matrix R by least squares optimization, and fits a head model S fit  under the current projection matrix R. The iteration process in general will converge after 4-5 times. 
     2.3 Model Texture Reconstruction 
     By adopting a texture parametric UV coordinate of the head model, anti-aliasing texture map the segmented human face region R face  in step I onto the fitted head model S fit  in step 2.2, and generate a texture image I fit  of the visible part. Carry out the filling manipulation for the invisible part (i.e. a region that has not been anti-aliasing texture mapped) on I fit . Referring to a standard human face texture image I ref  in the Basel Face Model database, solve all invisible pixels on I fit  so that its Laplace operator value (ΔI (x,y) =4I (x,y) −I (x−1,y) −I (x+1,y) −I (x,y−1) −I (x,y+1) ) is consistent with that on I ref . 
     III. 2D strands extraction: compute a 2D orientation field and its corresponding confidence map by using a Gabor kernel function within the hair region obtained in step I, and obtain a set of sparse 2D strand curves by tracing based on the 2D orientation field and the confidence map; 
     3.1 Orientation Field Estimation 
     Similar to previous methods, this method uses a series of oriented filter functions {K θ } to carry out the filter manipulation for the hair region R hair  (whose boundary color is the extracted foreground hair color C hair   fore  during the matting process) obtained from the image preprocessing, where each filter function K θ  is used to detect a response value of the orientation corresponding to the angle θ. Let F(x,y,θ)=(K θ *I) (x,y)  represent the response value of K θ  at the pixel (x,y). Then the local orientation at the pixel (x,y) is {tilde over (θ)} (x,y) =argmax θ (F(x,y,θ)). 
     The filter function adopted by this method is composed of 32 even-symmetric Gabor Kernel functions with their orientations evenly spaced between [0,π]: 
     
       
         
           
             
               
                 
                   K 
                   θ 
                 
                 ⁡ 
                 
                   ( 
                   
                     u 
                     , 
                     v 
                   
                   ) 
                 
               
               = 
               
                 
                   ⅇ 
                   
                     
                       - 
                       
                         1 
                         2 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             
                               u 
                               ~ 
                             
                             2 
                           
                           
                             σ 
                             u 
                             2 
                           
                         
                         + 
                         
                           
                             
                               v 
                               ~ 
                             
                             2 
                           
                           
                             σ 
                             v 
                             2 
                           
                         
                       
                       ) 
                     
                   
                 
                 ⁢ 
                 
                   cos 
                   ⁡ 
                   
                     ( 
                     
                       
                         2 
                         ⁢ 
                         π 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           u 
                           ~ 
                         
                       
                       λ 
                     
                     ) 
                   
                 
               
             
             , 
             
               
 
             
             ⁢ 
             
               
                 u 
                 ~ 
               
               - 
               
                 u 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 cos 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 θ 
               
               + 
               
                 v 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 sin 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 θ 
               
             
             , 
             
               
 
             
             ⁢ 
             
               
                 
                   v 
                   ~ 
                 
                 = 
                 
                   
                     
                       - 
                       u 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     sin 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     θ 
                   
                   + 
                   
                     v 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     cos 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     θ 
                   
                 
               
               ; 
             
           
         
       
     
     Ideally, the parameters of the Gabor function should be proportional to the size of visible strand features in the image, the parameters used by this method are σ u =1.8, σ v =2.4, λ=4. 
     In addition to estimating the local orientation field {tilde over (θ)} (x,y) , this method calculates one confidence w (x,y)  at each pixel to represent the accuracy of the orientation field: 
     
       
         
           
             
               
                 w 
                 
                   ( 
                   
                     x 
                     , 
                     y 
                   
                   ) 
                 
               
               = 
               
                 
                   ∑ 
                   θ 
                 
                 ⁢ 
                 
                   
                     
                       dist 
                       ⁡ 
                       
                         ( 
                         
                           θ 
                           , 
                           
                             
                               θ 
                               ~ 
                             
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     · 
                     
                       
                         ( 
                         
                           
                             F 
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                                 , 
                                 θ 
                               
                               ) 
                             
                           
                           - 
                           
                             F 
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                                 , 
                                 
                                   
                                     θ 
                                     ~ 
                                   
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                       2 
                     
                   
                 
               
             
             ; 
           
         
       
     
     Where dist(θ 1 ,θ 2 ) indicates the angel between orientations. By thresholding the confidence, it is possible to discard unreliable orientation estimations and obtain a sparse but robust orientation field, so as to indicate orientation features of the hair region in the image, as shown in  FIG. 2 . 
     Due to the imperfections in input images, sometimes some unreliably estimated orientations may likely have relatively high confidence values. It is hard to distinguish such false positives from true strand features by thresholding. Experiments show that, a correct orientation result with high confidence usually has neighboring pixels with the same high confidence along this direction, while an incorrect orientation result with high confidence is usually isolated. In view of the above, this method adopts an iterative orientation field improving process to enhance the orientation field result and discard the influence of artifacts on the result. 
     After an initial orientation field result {tilde over (θ)} (x,y)  is obtained, use its corresponding confidence w (x,y)  as an input of next iteration, and re-estimate one new orientation field {tilde over (θ)}′ (x,y)  and its corresponding confidence w′ (x,y)  by using the same method. One to two iterations suffice for a common input image. The process can effectively filter out those high-confidence orientation estimations caused by image artifacts, resulting in a clean and reliable 2D orientation field, as shown in  FIG. 3 . 
     3.2 Strand Extraction 
     As shown in  FIG. 4 , after the sparse 2D orientation field is obtained from step 3.1, this method converts the orientation field into a set of geometric curves that correspond to individual hair strand structures. Since the input of the method is a single image under uncontrolled environment, recovering accurate 3D curves is almost impractical. Therefore, at this step the method extracts all geometric curves on the 2D image plane, resolves the correct topology for all hair strands intersecting with each other, and stores the local layering relationship to the corresponding curve vertices, as shown in  FIG. 5 . 
     Firstly, select a seed pixel within the hair region as a starting point of strand tracing; select the local maximum value point P of confidence on the confidence map as a seed point satisfying: 
     
       
         
           
             
               
                 
                   
                     w 
                     p 
                   
                   - 
                   
                     max 
                     ⁡ 
                     
                       ( 
                       
                         
                           w 
                           
                             p 
                             L 
                           
                         
                         , 
                         
                           w 
                           
                             p 
                             R 
                           
                         
                       
                       ) 
                     
                   
                 
                 
                   w 
                   p 
                 
               
               &gt; 
               ɛ 
             
             , 
             
               
 
             
             ⁢ 
             
               
                 
                   w 
                   P 
                 
                 &gt; 
                 
                   w 
                   high 
                 
               
               ; 
             
           
         
       
     
     Where w p     L    and w p     R    are near confidences sampled by the bilinear interpolation method in opposite directions along the line passing P and perpendicular to the local orientation {tilde over (θ)} P . Let w high =0.3, w low =0.05, ε=0.2 with respect to a regular image. 
     For any selected seed point P seed  and its local orientation {tilde over (θ)} P     seed   , this method simultaneously carries out strand tracing in both opposite directions. Similar to methods in the prior art, each step of strand tracing extends a curve forward along the direction V P  corresponding to the angle {tilde over (θ)} P  at the current location P:
 
 P   i+1   =P   i   +δv   P     i   ;
 
     Maintain one tracing status and one health point value for each strand tracing process: an initial health point of the tracing process is 5 when the process starts, and the current strand tracing process ends when the health point drops to 0. If the tracing status of current tracing step is “certain”, the tracing direction is determined by the local orientation field and the health point is refilled to 5; if the tracing status is “uncertain”, the tracing direction is estimated from the previous traced vertex so that the curvature of the curve is maintained, and the health point value is decreased by 1. At each step i of the tracing process, update the tracing status according to the following rules: 
     1) if i=0, initially set the tracing status to “certain”; 
     2) if w P     i   &lt;w low , change the tracing status to ‘uncertain”; 
     3) if w P     i   ≧w low  and arccos(v P     i   ·v P     i−1   )&gt;θ max , change the tracing status to “uncertain”; 
     4) if w P     i   ≧w low  and arccos(v P     i   ·v P     i−1   )≦θ max , change the tracing status to “certain”; 
     5) keep current tracing status otherwise. 
     If rule 3) is applicable, this method assumes that the current and all succeeding “uncertain” vertices are occluded by other strands, thus marking them as being occluded. 
     During the tracing process, simultaneously remove pixels along the strand curves from the list of seed pixels so that all strands will be traced only once, where the tracing step size δ is set to 75% of the pixel width and θ max =π/6. Trim “uncertain” vertices at both ends of each strand after tracing. 
     Because of possible error accumulation, a strand obtained by tracing in the above steps very likely drifts away from the true center of the curve in the image. This method performs a further re-centering correction after acquiring each traced vertex as follows: 
     For each 2D curve vertex P, sample in two opposite directions along the line passing P and perpendicular to the local orientation {tilde over (θ)} P  to obtain the near confidences w p     L    and w p     R   ; fit a tent function Λ(t) as follows: letting Λ(0)=w P , Λ(−1)=w P     L   , Λ(1)=w P     R   , then calculate argmax(Λ(t)) as an offset correction in the vertical direction. 
     Sample all 2D strand vertices generated in the step from corresponding locations in the image to obtain their color values. 
     IV. 3D hairstyle reconstruction: carry out energy optimization in conjunction with the fitted head model according to step II, depth coherence among nearby strands and occlusion correlations among strands, solve and obtain depth information of all 2D strands generated from step III, volumize according to the 3D strands so as to obtain an adequately dense 3D strand set around the head as a recovered hairstyle model, and sample all strand vertices from an original image to obtain hair color values; 
     4.1 Depth Estimation 
     Assume depths of the hairstyle near silhouette are all 0 (i.e., depths of the center of the head model); the depth of a strand covering the forehead is the depth of the location corresponding to the head model plus a hair thickness value; further solve depths of other strands between the two in the step, and keep the occlusion relationship obtained from the 2D strand extraction. 
     Define depth constraints in depth optimization process as follows: 
     1) depth constraints: constrain known depths on the forehead and the silhouette, etc.; the user may also manually specify the depth of some locations via a stroke-based tool; 
     2) strand constraints: maintain depth smoothness among nearby vertices along a strand, so as to prevent sharp angles; 
     3) neighbor constraints: maintain depth coherence among nearby strands with similar orientations. 
     Let P i  be the position of the ith vertex of a strand, Z(P i ) be the depth value thereof, respectively define energy terms according to the above constraints as: 
     
       
         
           
             
               
                 
                   E 
                   Z 
                 
                 ⁡ 
                 
                   ( 
                   
                     P 
                     i 
                   
                   ) 
                 
               
               = 
               
                 
                   ( 
                   
                     
                       Z 
                       ⁡ 
                       
                         ( 
                         
                           P 
                           i 
                         
                         ) 
                       
                     
                     - 
                     
                       
                         Z 
                         _ 
                       
                       ⁡ 
                       
                         ( 
                         
                           P 
                           i 
                         
                         ) 
                       
                     
                   
                   ) 
                 
                 2 
               
             
             , 
             
               
 
             
             ⁢ 
             
               
                 
                   E 
                   S 
                 
                 ⁡ 
                 
                   ( 
                   
                     P 
                     i 
                   
                   ) 
                 
               
               = 
               
                 
                   ( 
                   
                     
                       Z 
                       ⁡ 
                       
                         ( 
                         
                           P 
                           i 
                         
                         ) 
                       
                     
                     - 
                     
                       
                         
                           Z 
                           ⁡ 
                           
                             ( 
                             
                               P 
                               
                                 i 
                                 - 
                                 1 
                               
                             
                             ) 
                           
                         
                         + 
                         
                           Z 
                           ⁡ 
                           
                             ( 
                             
                               P 
                               
                                 i 
                                 + 
                                 1 
                               
                             
                             ) 
                           
                         
                       
                       2 
                     
                   
                   ) 
                 
                 2 
               
             
             , 
             
               
 
             
             ⁢ 
             
               
                 
                   
                     E 
                     N 
                   
                   ⁡ 
                   
                     ( 
                     
                       P 
                       i 
                     
                     ) 
                   
                 
                 = 
                 
                   ( 
                   
                     
                       Z 
                       ⁡ 
                       
                         ( 
                         
                           P 
                           i 
                         
                         ) 
                       
                     
                     - 
                     
                       
                         
                           ∑ 
                           
                             Q 
                             ∈ 
                             
                               N 
                               ⁡ 
                               
                                 ( 
                                 
                                   P 
                                   i 
                                 
                                 ) 
                               
                             
                           
                           
                               
                           
                         
                         ⁢ 
                         
                           
                             Z 
                             ⁡ 
                             
                               ( 
                               Q 
                               ) 
                             
                           
                           2 
                         
                       
                       
                          
                         
                           N 
                           ⁡ 
                           
                             ( 
                             
                               P 
                               i 
                             
                             ) 
                           
                         
                          
                       
                     
                   
                   ) 
                 
               
               ; 
             
           
         
       
     
     Where  Z (P i ) is a predefined depth value of P i , N (P i ) contains the neighbor vertices that are not on the same strand of P i  but have a similar orientation and the same occlusion flag. 
     Finally, solve for depth values of all the strand vertices by minimizing the energy E as follows:
 
 E=w   Z   E   Z   +w   S   E   S   +w   N   E   N ;
 
     Let w Z =5, w S =2, w N =1. Solve by using the biconjugate gradient method. 
     4.2 3D Strand Synthesis 
     Real hair occupies a volumetric region around the head. The 3D hair model generated in step 4.1 so far only include those visible regions from the input image, which roughly cover the outmost layer of the frontal half of the entire hair model. Due to the complex structures and widely different styles of real hairstyle, any assumption about what the invisible part of the hair looks like may not always hold. Therefore, the process aims at defining a hair volumetric region that: 1) compared to the original portrait hairstyle, does not add any hair strands when rendered from the original viewpoint; and 2) transitions smoothly from the frontal (visible) half to the rear (invisible) half. 
     Firstly, define three depth maps as follows: D front , D mid , and D back . Where the front depth map D front  is obtained by rasterizing the computed sparse 3D strands, then depth values at pixels covered by the 3D strands are uniformly diffused to the entire hair region. To calculate the D mid , first unite the original hair region with the hair region obtained by projecting the head model as an extended hair region, set depth values near the silhouette of the original hair region as a boundary condition, diffuse the depth values to the entire extended hair region, thus generating the middle depth map D mid . The back depth map D back  is generated by fixing depth values at the region boundary and pushing depth values of the internal region smoothly backward so that its depths reach outside the head and the entire region fully covers the rear half of the head. The three layered depths partitions the entire hair region into two closed halves, for any 3D point P(x,y,z), if D front (x,y)&lt;z&lt;D middle (x,y), or D middle (x,y)&lt;z&lt;D back  (x,y), it is conceived as inside the hairstyle model. 
     Similarly, propagate 3D orientations, color and opacity values of a strand from the three layers to the interior of the hairstyle model by the method of diffusion. For the 3D orientations, first convert them to structure tensors, and then diffuse them inward. For colors of nonhair regions in D mid  and D back , conceive the visible part as a source, likewise synthesize the image by using the PatchMatch method. With respect to the application of this method, it is unnecessary to fill all the internal regions, but only those sufficient to form a thick and seamless outer layer. 
     Unlike related work on hair capture, this method does not force all 3D hair strands to grow from the scalp as this may result in unnecessary discrepancies between the original image and the results re-rendered from the original viewpoint. Therefore, this method traces 3D strands from random locations sampled inside the hair model. During tracing, simultaneously keep a record of strand density within each voxel. Tracing terminates at the voxel whose strand density exceeds a given threshold. 
     V. Synthesis and application: conveniently carry out portrait editing and manipulations such as portrait pop-ups, hairstyle replacements and hairstyle editing by adopting reconstructed 3D information such as the human hairstyle model, the human head model and so on according to the aforementioned steps I to IV. 
     5.1 Portrait Pop-Ups 
     As shown in  FIG. 6 , recovering a subject from a single image is of great interest in interactive applications. However, due to the complexity of human hairstyle, the existing work focuses only on the facial region or adds some ad-hoc hair to the fitted head model. Nevertheless, by using the strand-based hair model in light of this method, it is possible to generate more vivid head avatars. 
     5.2 Hairstyle Replacement 
     As shown in  FIG. 7 , replacing an individual&#39;s hairstyle in a portrait allows the user to try on different hairstyles and to view possible actual effects. Give a source portrait image I src  and a target portrait image I dst , where the goal of this application is to replace the hairstyle in the target portrait image I dst  by the hairstyle in the source portrait image I src . First extract the hairstyle model and the head model from I src , and create a portrait pop-up model for I dst . By making use of the one to one vertex correspondence between the source portrait head model and the target portrait head model, calculate a transformation M T  of the heads from I src  to I dst  so as to compensate for changes in shapes and positions of the two. M T  includes two parts: a translation and rotation parameter computed during the head model fitting process, and a scaling parameter that aligns bounding boxes of the two head models. Then transform the hairstyle model extracted from I src  to a proper position in I dst  via M T . 
     To increase realism of the results, calculate a mutual ambient occlusion term for the transferred hair model and the target subject. To avoid darkening effects on the subject, this method excludes self occlusion and only considers mutual occlusion between the hair and the subject. 
     5.3 Hairstyle Editing 
     By utilizing the 3D hair model, it is possible to implement numerous tools that allow the user to edit a portrait hairstyle, such as adjusting color, smoothness, shininess, or adding geometric noises. The user may adjust hairstyle color or add color details on strand scales, where the smoothness modification is to simply filter the color along strand vertices. When editing hairstyle highlights, initially assume a single point light (simulating a camera-mounted flashlight) located at the camera and allow the user to modify its properties in real time. This method adopts the Marschner model (Marschner, S., Jensen, H. W., Cammarano, M., Worley, S., and Hanrahan, P. 2003. Light scattering from human hair fibers. ACM Trans. Graph. 22, 3, 780-791.) to add a highlight effect to the hairstyle.