Automatic sketch generation

• US 6,845,171 B2
• Filed: 11/19/2001
• Issued: 01/18/2005
• Est. Priority Date: 11/19/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shum, Heung-Yeung, Chen, Hong, Xu, Ying-Qing
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): TUCKER, WESLEY J
• Application Number:
  US09/996,323
• Publication Number:
  US 20030095701A1
• Time in Patent Office: 1,156 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 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, comprising using a computer to perform the following process actions:

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;

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

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

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

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

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

2. The process of claim 1, wherein the each training image depicts a frontal view of a person'"'"'s face, and wherein the face depicted in each training image is approximately the same size and is centered about approximately the same point as the other training images.

3. The process of claim 1, wherein the process action of defining an average face shape, comprises the actions of:

identifying a prescribed set of feature points in each training image, said points marking the contours of a prescribed set of facial features;

creating a shape vector for each training image shape, wherein each element of each shape vector represents the location of one of the identified feature points and the order of the elements in each shape vector is identical; and

averaging the correspondingly-ordered elements from each shape vector to produce a meanshape vector which represents the average face shape of the training images.

4. The process of claim 3, wherein the process action of identifying a prescribed set of feature points in each training image, comprises the actions of:

for each facial feature of the prescribed set of facial features,

identifying the endpoints of the facial feature under consideration; and

identifying a prescribed number of equidistant points between the identified endpoints of the facial feature under consideration.

5. The process of claim 3, wherein the process action of defining a geometric transform function for each training image, comprises an action of defining the geometric transform function which when combined with the shape vector of the training image associated with the function produces the meanshape vector.

6. The process of claim 5, wherein the process action of training an active shape model, comprises an action of training the active shape model using the identified feature points to automatically locate said prescribed set of feature points in an arbitrary image of a person'"'"'s face.

7. The process of claim 1, wherein the process action of defining a sketch model, comprises the actions of:

identifying those lines that appear in every transformed training sketch;

including the lines identified as always appearing in the sketch model, and associate each with a designation that the line is of the type that always appears;

identifying those lines that do not appear in every transformed training sketch, but which when appearing in one of the transformed training sketches do so independent of the presence or absence of other lines;

including the lines identified as sometimes appearing independently in the sketch model, and associate each with a designation that the line is of the type that sometimes appears independently of the presence or absence of other lines;

identifying those lines that do not appear in every transformed training sketch, but which when appearing in one of the transformed training sketches do so only when one or more other lines are also present or absent; and

including the lines identified as sometimes appearing in the sketch model depending on the presence or absence of other lines, associating each with a designation that the line is of the type that sometimes appears but only when one or more other lines are also present or absent, and associating each with an indicator as to which lines are to be present and which absent to trigger the inclusion of the line.

8. The process of claim 7, wherein the process action of defining a sketch model, further comprises an action of characterizing each line included in the sketch model in terms comprising an on-off indicator, the line'"'"'s width, and a set of control points which define the shape and location of the line, and wherein said on-off indicator is used to indicate whether a line modeled in the sketch model is to appear in a sketch generated using the sketch model.

9. The process of claim 1, further comprising a process action of generating a sketch of a person'"'"'s face from an image of that person'"'"'s face, said generating action comprising the actions of:

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

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;

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

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

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

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.

10. The process of claim 9, wherein the input image depicts a frontal view of a person'"'"'s face, and wherein the face depicted in the input image is approximately the same size and is centered about approximately the same point as the training images.

11. The process of claim 9, wherein the process action of employing the active shape model to identify the shape and location of said prescribed set of facial features in the input image, comprises an action of identifying a prescribed set of feature points in the input image, said points marking the contours of a prescribed set of facial features.

12. The process of claim 11, wherein the process action of defining a geometric transform function for the input image, comprises the actions of:

creating a shape vector for the input image, wherein each element of the input image shape vector represents the location of one of the identified input image feature points and the order of the elements in the input image shape vector is identical to that of the training image shape vectors; and

defining the geometric transform function which when combined with the shape vector of the input image produces the meanshape vector.

13. The process of claim 9, wherein the process action of creating an expected sketch image, comprises the actions of for each pixel of the transformed input image:

determining the pixel in each transformed training image that best matches the transformed input image pixel under consideration;

assigning a pixel characteristic value to each pixel of the transformed training images determined to be best matching that indicates the likelihood said best matching pixel corresponds to the transformed input image pixel currently under consideration;

computing a weighted average of the pixel characteristic values of the pixels in the transformed training sketch associated with the pixels determined to be best matching for a prescribed number of those best matching pixel 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 pixel; and

assigning the weighted average pixel characteristic 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.

14. The process of claim 13, wherein the prescribed pixel characteristic is pixel intensity.

15. The process of claim 13, wherein the prescribed number of the transformed training images pixels designated as best matching that are employed in computing the weighted average equal approximately 25% of the number of transformed training images.

16. The process of claim 9, wherein the process action of fitting the lines defined in the sketch model to the expected sketch image, comprises the actions of:

attempting to match the lines defined in the sketch model to the facial features the lines represent in the expected sketch image; and

whenever a sketch model line is found in the expected sketch image, modifying the sketch model line such that the line corresponds in shape and position to the corresponding feature of the expected sketch image.

17. The process of claim 9, wherein the process action of defining a sketch model comprises the action of modeling a person'"'"'s face exclusive of the person'"'"'s hair, the process further comprising the actions of:

identifying the location of pixels outlining the person'"'"'s hair as depicted in the input image; and

adding one or more lines representing the outline of the person'"'"'s hair to the sketch of the person depicted in the input image.

18. The process of claim 9, wherein the process action of defining a sketch model comprises the action of modeling a person'"'"'s face exclusive of the person'"'"'s ears, the process further comprising the actions of:

identifying the location of pixels outlining each of the person'"'"'s ears as depicted in the input image; and

adding one or more lines representing the outline of the person'"'"'s ears to the sketch of the person depicted in the input image.

19. A system for generating a sketch of a person'"'"'s face from an image of the person'"'"'s face, comprising:

a general purpose computing device trained to generate a sketch of a person'"'"'s face from an image of the person'"'"'s face, said training comprising inputting a set of training images each of which depicts a person'"'"'s face, drawing a set of training sketches each representing a respective face depicted in the training images, and executing a training computer program comprising a set of program modules that direct the computing device to,

identify a prescribed set of points in each training image, said points marking the contours of a prescribed set of facial features,

train 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,

compute 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,

define 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,

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

define a sketch model comprising a set of lines representative of the lines found in the transformed training sketches; and

a sketch generating computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input an image of a person'"'"'s face,

employ the active shape model to locate said prescribed set of facial feature points in the input image,

define 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,

warp the input image using the geometric transform function associated with the input image to create a transformed input image,

employ 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,

fit 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,

apply 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.

20. The system of claim 19, wherein the program module for creating an expected sketch image, comprises sub-modules that for each pixel of the transformed input image:

ascertain 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,

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,

ascertain 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,

compute 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

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

identify 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,

compute 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

designate 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;

identify 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;

compute 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

assign 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.

21. The system of claim 20, wherein the prescribed pixel characteristic is pixel intensity.

22. The system of claim 20, wherein the prescribed neighborhood is a square neighborhood having a size of 7×

7 pixels.

23. The system of claim 20, wherein the size of the prescribed search block is 5×

5 pixels.

24. The system of claim 20, wherein the prescribed number of the transformed training image pixels designated as best matching that are employed in computing the weighted average equal approximately 25% of the number of transformed training images.

25. The system of claim 19, 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:

selecting a previously unselected line defined in the sketch model;

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,

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

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

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,

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,

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

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

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, 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,

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, 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,

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

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

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.

26. A computer-readable medium having computer-executable instructions 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:

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;

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

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;

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

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

27. The computer-readable medium of claim 26, further comprising an instruction for generating a sketch of a person'"'"'s face from an image of that person'"'"'s face, said generating instruction comprising sub-modules for:

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

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;

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

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

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

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.

28. The computer-readable medium of claim 27, 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 instruction for fitting the lines defined in the sketch model to the expected sketch image, comprises sub-modules for:

selecting a previously unselected line defined in the sketch model;

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,

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,

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

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

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, 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,

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,

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

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

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, 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,

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, 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,

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,

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

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

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, characterizing the line in terms comprising an on-off indicator that is set to the off mode.