Automatic sketch generation

• US 7,039,216 B2
• Filed: 11/24/2004
• Issued: 05/02/2006
• Est. Priority Date: 11/19/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shum, Heung-Yeung, Chen, Hong, Xu, Ying-Qing
• Primary Examiner(s): Bali, Vikkram
• Assistant Examiner(s): TUCKER, WESLEY J
• Application Number:
  US10/997,401
• Publication Number:
  US 20050100243A1
• Time in Patent Office: 524 Days
• Field of Search: 382/100, 382/118, 382/190, 382/202, 382/203, 382/201, 382/215, 382/293
• US Class Current: 382/100
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 2207/20081 Training; Learning
• CPC Class Codes: G06T 2207/30201 Face
• CPC Class Codes: G06T 7/149 involving deformable models, e.g. active contour models
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions

Abstract

An example-based facial sketch system and process that automatically generates a sketch from an input image depicting a person'"'"'s face. Sketch generation is accomplished by first training the system using example facial images and sketches of the depicted faces drawn with a particular style by a sketch artist. The trained system is then used to automatically generate a facial sketch that simulates the artist'"'"'s style from an input image depicting a person'"'"'s face. Nonparametric sampling and a flexible sketch model are employed to capture the complex statistical characteristics between an image and its sketch.

Claims

1. A computer-implemented process for generating a sketch of a person'"'"'s face from an image of the person'"'"'s face, comprising:

a training step comprising,

an inputting step for inputting a set of training images each of which depicts a person'"'"'s face,

a drawing step for drawing a set of training sketches each representing a respective face depicted in the training images,

an identifying step for identifying a prescribed set of points in each training image, said points marking the contours of a prescribed set of facial features,

a teaching step for teaching an active shape model module using the identified feature points to automatically locate said prescribed set of points in an arbitrary image of a person'"'"'s face,

a computing step for computing a meanshape vector by forming a separate shape vector for each training image from the identified feature points of that image and averaging the corresponding elements of each shape vector, wherein each shape vector has identically ordered elements,

a defining step for defining a geometric transform function for each training image which warps that image so that the identified feature points in vectorized form equals the meanshape vector,

a warping step for warping each training image and its corresponding sketch using the geometric transform function associated with the training image to create transformed versions thereof, and

a second defining step for defining a sketch model comprising a set of lines representative of the lines found in the transformed training sketches; and

a sketch generating step comprising,

a second inputting step for inputting an image of a person'"'"'s face,

an employing step for employing the active shape model to locate said prescribed set of facial feature points in the input image,

a third defining step for defining a geometric transform function for the input image which warps the input image so the located feature points thereof in vectorized form equals the meanshape vector,

a second warping step for warping the input image using the geometric transform function associated with the input image to create a transformed input image,

a creating step for employing a non-parametric sampling module to create an expected sketch image from the transformed input image as well as the transformed training images and sketches,

a fitting step for fitting the lines defined in the sketch model to the expected sketch image to create a transformed input image sketch comprising those lines of the sketch model that correspond to facial features found in the expected sketch image, and

an applying step for applying an inverse of the input image geometric transform function to the transformed input image sketch to unwarp the sketch such that the shape and location of the lines making up the sketch match the shape and location of corresponding facial features in the input image.

2. The process of claim 1, wherein the creating step for creating an expected sketch image, comprises:

an ascertaining step for ascertaining the value of a prescribed pixel characteristic of the pixel under consideration and those of other pixels in a prescribed neighborhood surrounding the pixel under consideration;

for each of the transformed training images,

a second identifying step for identify the pixels in a prescribed search block in the transformed training image under consideration which is centered on the pixel corresponding in location to the transformed input image pixel currently under consideration,

for each pixel identified as being in the search block,

a second ascertaining step for ascertaining the value of the prescribed pixel characteristic of each of the pixels in a neighborhood of pixels centered on the search block pixel under consideration, wherein the neighborhood of pixels in the transformed training image is of the same size as the prescribed pixel neighborhood associated with the transformed input image,

a second computing step for computing the difference in the prescribed pixel characteristic values between each pixel in the neighborhood associated with the transformed input image pixel under consideration and the correspondingly situated pixels of the neighborhood of pixels centered on the search block pixel under consideration in the transformed training image currently under consideration, and

an averaging step for averaging the computed differences and designate the average difference a candidate for the overall difference associated with the transformed input image pixel under consideration, and

a third identifying step for identifying the smallest candidate overall average difference and designate the search block pixel associated with smallest candidate average difference as the pixel of the transformed training image currently under consideration that best matches the transformed input image pixel currently under consideration;

for each pixel designated to be the best matching,

a third computing step for computing a value indicative of the likelihood that the designated best matching pixel actually corresponds to the transformed input image pixel currently under consideration based on the distance separating the location of the designated best matching pixel in the transformed training image under consideration and the location of the transformed input image pixel currently under consideration relative to the separation distances computed between the designated best matching pixels of other transformed training images and the transformed input image pixel currently under consideration, and

a designating step for designating whether the pixel in the transformed training sketch associated with the best matching pixel under consideration has a pixel value indicative of a black pixel or a white pixel;

a fourth identifying step for identifying a prescribed number of the transformed training image pixels designated as best matching which exhibit the highest likelihood values that the best matching pixel actually corresponds to the transformed input image pixel currently under consideration;

a fourth computing step for computing a weighted average of the pixel values of the pixels in the transformed training sketches associated with the best matching pixels identified as exhibiting the highest likelihood values, wherein the weight associated with each transformed training sketch pixel value involved is based on the likelihood value assigned to the corresponding best matching pixels; and

an assigning step for assigning the weighted average pixel value as the pixel value of a pixel in the expected sketch image corresponding in location to the transformed input image pixel currently under consideration.

3. The process of claim 1, wherein each line included in the sketch model is characterizing in terms comprising an on-off indicator used to indicate whether a line modeled in the sketch model is to appear in a sketch generated using the sketch model, the line'"'"'s width, and a set of control points which define the shape and location of the line, and wherein the program module for fitting the lines defined in the sketch model to the expected sketch image, comprises sub-modules for:

a selecting step for selecting a previously unselected line defined in the sketch model;

a determining step for determining the line type of the currently selected line, wherein the selected line is one of (i) a first type that appears in every transformed training sketch, (ii) a second type that does not appear in every transformed training sketch, but which when appearing in one of the transformed training sketches does so independent of the presence or absence of other lines, or (iii) a third type that does not appear in every transformed training sketch, but which when appearing in one of the transformed training sketches does so only when one or more other lines are also present or absent;

whenever it is determined that the selected line is of the first type,

for each pixel location associated with the line as it would appear in a sketch,

a second identifying step for identifying the pixel in the expected sketch image that best matches a prescribed pixel characteristic of the pixel location under consideration and which resides in the vicinity of a location corresponding to that of the line pixel, and

a re-assigning step for reassigning the location of the line pixel under consideration to match that of the expected sketch image pixel that best matches the selected pixel, and

a characterizing step for characterizing the resulting line with reassigned pixel locations in terms comprising an on-off indicator that is set to the on mode, the line'"'"'s width, and a set of control points which define the shape and location of the line as reflected by the reassigned pixel locations;

whenever it is determined that the selected line is of the second type,

a second determining step for determining whether the facial feature represented by the line appears in the expected sketch image,

whenever the facial feature appears in the expected sketch image,

for each pixel location associated with the line as it would appear in a sketch,

a third identifying step for identifying the pixel in the expected sketch image that best matches a prescribed pixel characteristic of the pixel location under consideration and which resides in the vicinity of a location corresponding to that of the line pixel, and

a second re-assigning step for reassigning the location of the line pixel under consideration to match that of the expected sketch image pixel that best matches the selected pixel, and

a second characterizing step for characterizing the resulting line with reassigned pixel locations in terms comprising an on-off indicator that is set to the on mode, the line'"'"'s width, and a set of control points which define the shape and location of the line as reflected by the reassigned pixel locations, and

whenever the facial feature does not appear in the expected sketch image, a third charactering step for characterizing the line in terms comprising an on-off indicator that is set to the off mode; and

whenever it is determined that the selected line is of the third type,

a third determining step for determining whether the facial features represented by those lines upon which the inclusion of the line under consideration depends are present or absent,

whenever the lines upon which the inclusion of the line under consideration depends are not present or absent, a third characterizing step of characterizing the line in terms comprising an on-off indicator that is set to the off mode,

whenever the lines upon which the inclusion of the line under consideration depends are present or absent,

for each pixel location associated with the line as it would appear in a sketch,

a fourth identifying step for identifying the pixel in the expected sketch image that best matches a prescribed pixel characteristic of the pixel location under consideration and which resides in the vicinity of a location corresponding to that of the line pixel, and

a third reassigning step for reassigning the location of the line pixel under consideration to match that of the expected sketch image pixel that best matches the selected pixel, and

a fourth characterizing step for characterizing the resulting line with reassigned pixel locations in terms comprising an on-off indicator that is set to the on mode, the line'"'"'s width, and a set of control points which define the shape and location of the line as reflected by the reassigned pixel locations.

4. A computer-implemented process for training a computer using a set of training images each of which depicts a person'"'"'s face to generate a sketch of a person'"'"'s face from an image of that person'"'"'s face, said computer-executable instructions comprising:

a drawing step for drawing a training sketch of the face of each person depicted in a training image, each of said training sketches comprising a plurality of lines that represent and correspond in location to facial features of the person depicted in the associated training image;

a defining step for defining an average face shape which represents the average shape and location of a prescribed set of facial features depicted in the training images;

a warping step for warping each training image and its corresponding sketch so as to conform them to the average face shape, thereby creating a set of transformed training images and a corresponding set of transformed training sketches;

a training step for training an active shape model using the training images to automatically identify the shape and location of said prescribed set of facial features in an arbitrary image depicting a person'"'"'s face; and

a second defining step for defining a sketch model comprising a set of lines representative of the lines found in the transformed training sketches.

5. The process of claim 4, further comprising a generating step for generating a sketch of a person'"'"'s face from an image of that person'"'"'s face, comprising:

an employing step employing the active shape model to identify the shape and location of said prescribed set of facial features in the input image;

a third defining step for defining a geometric transform function for the input image which when applied to the input image warps the image so that said prescribed set of facial features correspond in shape and location to the average face shape;

an applying step for applying the input image geometric transform function to warp the input image to create a transformed version thereof;

a creating step for creating an expected sketch image using non-parametric sampling from the transformed input image as well as the transformed training images and sketches;

a fitting step for fitting the lines defined in the sketch model to the expected sketch image to create a transformed input image sketch comprising those lines of the sketch model that correspond to facial features found in the expected sketch image; and

a second applying step for applying an inverse of the input image geometric transform function to the transformed input image sketch to unwarp the sketch such that the shape and location of the lines making up the sketch match the shape and location of corresponding facial features in the input image.

6. The process of claim 5, wherein each line included in the sketch model is characterizing in terms comprising an on-off indicator used to indicate whether a line modeled in the sketch model is to appear in a sketch generated using the sketch model, the line'"'"'s width, and a set of control points which define the shape and location of the line, and wherein the fitting step for fitting the lines defined in the sketch model to the expected sketch image, comprises:

a selecting step for selecting a previously unselected line defined in the sketch model;

a determining step for determining the line type of the currently selected line, wherein the selected line is one of (i) a first type that appears in every transformed training sketch, (ii) a second type that does not appear in every transformed training sketch, but which when appearing in one of the transformed training sketches does so independent of the presence or absence of other lines, or (iii) a third type that does not appear in every transformed training sketch, but which when appearing in one of the transformed training sketches does so only when one or more other lines are also present or absent;

whenever it is determined that the selected line is of the first type,

a second determining step for determining whether the facial feature represented by the line appears in the expected sketch image,

whenever the facial feature appears in the expected sketch image,

for each pixel location associated with the line as it would appear in a sketch,

an identifying step for identifying the pixel in the expected sketch image that best matches a prescribed pixel characteristic of the pixel location under consideration and which resides in the vicinity of a location corresponding to that of the line pixel, and

a reassigning step for reassigning the location of the line pixel under consideration to match that of the expected sketch image pixel that best matches the selected pixel, and

a characterizing step for characterizing the resulting line with reassigned pixel locations in terms comprising an on-off indicator that is set to the on mode, the line'"'"'s width, and a set of control points which define the shape and location of the line as reflected by the reassigned pixel locations,

whenever the facial feature does not appear in the expected sketch image, a second characterizing step for characterizing the line in terms comprising an on-off indicator that is set to the off mode; and

whenever it is determined that the selected line is of the second type,

a third determining step for determining whether the facial feature represented by the line appears in the expected sketch image,

whenever the facial feature appears in the expected sketch image,

for each pixel location associated with the line as it would appear in a sketch,

a second identifying step for identifying the pixel in the expected sketch image that best matches a prescribed pixel characteristic of the pixel location under consideration and which resides in the vicinity of a location corresponding to that of the line pixel, and

a second reassigning step for reassigning the location of the line pixel under consideration to match that of the expected sketch image pixel that best matches the selected pixel, and

a third characterizing step for characterizing the resulting line with reassigned pixel locations in terms comprising an on-off indicator that is set to the on mode, the line'"'"'s width, and a set of control points which define the shape and location of the line as reflected by the reassigned pixel locations, and

whenever the facial feature does not appear in the expected sketch image, a fourth characterizing step for characterizing the line in terms comprising an on-off indicator that is set to the off mode; and

whenever it is determined that the selected line is of the third type,

a fourth determining step for determining whether the facial features represented by those lines upon which the inclusion of the line under consideration depends are present or absent as indicated,

whenever the lines upon which the inclusion of the line under consideration depends are not present or absent as indicated, a fifth characterizing step for characterizing the line in terms comprising an on-off indicator that is set to the off mode,

whenever the lines upon which the inclusion of the line under consideration depends are present or absent as indicated,

a fifth determining step for determining whether the facial feature represented by the line appears in the expected sketch image,

whenever the facial feature appears in the expected sketch image,

for each pixel location associated with the line as it would appear in a sketch,

a third identifying step for identifying the pixel in the expected sketch image that best matches a prescribed pixel characteristic of the pixel location under consideration and which resides in the vicinity of a location corresponding to that of the line pixel, and

a third reassigning step for reassigning the location of the line pixel under consideration to match that of the expected sketch image pixel that best matches the selected pixel, and

a sixth characterizing step for characterizing the resulting line with reassigned pixel locations in terms comprising an on-off indicator that is set to the on mode, the line'"'"'s width, and a set of control points which define the shape and location of the line as reflected by the reassigned pixel locations, and

whenever the facial feature does not appear in the expected sketch image, a seventh characterizing step for characterizing the line in terms comprising an on-off indicator that is set to the off mode.