System and method for low bandwidth video streaming for face-to-face teleconferencing

• US 7,184,602 B2
• Filed: 05/02/2003
• Issued: 02/27/2007
• Est. Priority Date: 05/02/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cohen, Michael, Liu, Zicheng, Wen, Zhen, Zheng, Ke
• Primary Examiner(s): Mancuso; Joseph
• Assistant Examiner(s): Bitar; Nancy
• Application Number:
  US10/428,989
• Publication Number:
  US 20040218827A1
• Time in Patent Office: 1,397 Days
• Field of Search: 348/14.12, 348/14.15, 382/243, 382/181, 382/224, 382/118, 382/276, 345/419
• US Class Current: 382/243
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06V 40/165 using facial parts and geometric relationships
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 7/147 Communication arrangements, e.g. identifying the communication as a video-communication, intermediate storage of the signals selecting H04Q

Abstract

A system and method for facilitating low bandwidth video image transmission in video conferencing systems. A target is acquired (video image of a person'"'"'s head) and processed to identify one or more sub-regions (e.g., background, eyes, mouth and head). The invention incorporates a fast feature matching methodology to match a current sub-region with previously stored sub-regions. If a match is found, an instruction is sent to the receiving computer to generate the next frame of video data from the previously stored blocks utilizing a texture synthesis technique. The invention is applicable for video conferencing in low bandwidth environments.

Claims

1. A computer-implemented process for low bandwidth transmission of images of a person talking, comprising the process actions of:

inputting a captured image of a person'"'"'s face;

finding said face in said image;

dividing said face into sub-images corresponding to facial features;

comparing each sub-image to a set of previously saved images;

if a sub-image is determined to be new, adding said sub-image to said set of previously saved images;

sending said sub-images determined not to be in said set of previously saved images to a receiver with instructions for saving;

if a sub-image is determined to be similar to sub-image in said set of previously saved images,

synthesizing a new image closely corresponding to the captured image of a person'"'"'s face; and

sending said receiver instructions for constructing said synthesized image from said set of saved images at said receiver.

2. The computer-implemented process of claim 1, further comprising the process actions of:

said receiver saving said sub-images determined not to be in said set of previously saved images to a set of saved images at said receiver; and

said receiver constructing a synthesized image resembling said captured input image from said set of images in said receiver set of saved images using said instructions.

3. The computer-implemented process of claim 1 wherein said process action of dividing said face into sub-images corresponding to facial features, comprises dividing said face into at least one of:

a sub-image encompassing eyes in the face;

a sub-image encompassing a mouth in the face;

a sub-image encompassing the face without the sub-images encompassing the eyes and the mouth; and

a background sub-image not including the face.

4. The computer-implemented process of claim 3 further comprising the process action of saving each of said sub-images with an image quality dependent on the perceptual importance of said sub-image.

5. The computer-implemented process of claim 4 further comprising the process action of ranking each sub-image in order of mouth sub-image, eye sub-image, face sub-image without eyes and mouth, and background, respectively, in order of most important to least important.

6. The computer-implemented process of claim 4 wherein said image quality is defined as the sum of the absolute difference of the pixel values between the captured image and the synthesized image.

7. The computer-implemented process of claim 6 wherein the most important sub-image is created with the smallest sum of the absolute difference of the pixel values between the captured image and the synthesized image.

8. The computer-implemented process of claim 1 wherein the process action of comparing each sub-image to a set of previously saved images, further comprises comparing each sub-image based on at least one image feature.

9. The computer-implemented process of claim 8 further comprising the process action of calculating said at least one feature.

10. The computer-implemented process of claim 1 wherein the process action of comparing each sub-image to a set of previously saved images, comprises the process actions of:

calculating an integral image for said sub-image

for each of said set of previously saved images in turn,

calculating an integral image of said previously saved image;

calculating a unary feature score for said integral image of said sub-image and a unary feature score for said integral image of said previously saved image;

assigning the absolute difference of the feature scores between the sub-image and previously saved image as the feature score for the sub-image and previously saved image under consideration; and

comparing said feature score to a threshold to determine whether or not the sub-image and previously saved image are similar or non-similar.

11. The computer-implemented process of claim 10 wherein said unary feature score of an integral image is the integral of the white regions minus the integral of the black regions of the integral image.

12. The computer-implemented process of claim 1 wherein the process action of comparing each sub-image to a set of previously saved images, further comprising the process action of:

constructing a classifier by training each of a plurality of cascaded classifier stages to identify non-similar image pairs and allow only similar pairs to pass on to the next classifier stage if present, wherein each classifier stage is designed to err on the side of false positives but to minimize false negatives.

13. The computer-implemented process of claim 12, further comprising the process action of:

using said trained classifier to identify non-similar and similar image pairs.

14. The computer-implemented process of claim 12 wherein the process action of constructing a classifier by training each of a plurality of cascaded classifier stages, comprises the process actions of:

determining whether pairs of training images are similar or non-similar using a pixel luminance difference technique;

training each stage of the classifier in turn by,

inputting pairs of said training images into the classifier as a whole,

for each pair of training images input into the stage under consideration,

choosing an arbitrary image feature;

calculating a feature score for each image of the pair of images,

taking the absolute difference of the feature scores of the pair of images;

comparing the absolute difference of the feature scores to a threshold to determine if the images are similar or non-similar; and

comparing the determination of whether the images are similar or non-similar using the feature scores to the determination of whether the images are similar or not based on pixel luminance differences to identify if the classifier stage determination is a false positive or a false negative, wherein a false positive is defined as the classifier stage determining the image pair is similar when the pixel luminance technique determined the image pair is non-similar, and wherein a false negative is defined as the classifier determining the image pair is non-similar when the pixel luminance technique determined the image pair is similar;

once all training image pairs have been input,

determining if the number of false positives is equal to or below a first prescribed acceptable percentage;

determining if the number of false negative is equal to or below a second prescribed acceptable percentage;

whenever the number of false positives is not equal to or below the first prescribed percentage or the number of false negatives is not equal to or below the second prescribed percentage, repeating the training process for the classifier stage under consideration using an additional arbitrary image feature; and

whenever the number of false positives is equal to or below the first prescribed percentage and the number of false negatives is equal to or below the second prescribed percentage, training the next classifier stage in the cascade if there is one, and if not designating the classifier as trained.

15. The computer-implemented process of claim 14 wherein the process action for determining whether pairs of images are similar or non-similar using a pixel luminance difference technique, comprises the process actions of:

comparing pairs of training images on a pixel by pixel basis to determine pixel luminance difference;

determining how many pairs of images have a specific pixel luminance difference for all possible pixel luminance differences;

designating a threshold defining if a pair of images are similar or non-similar based on the distribution of the pixel luminance differences; and

determining if each image pair is similar or non-similar by comparing said pixel luminance difference to said designated threshold.

16. The computer-implemented process of claim 15 wherein pairs of pixels are determined to be similar if they are at least a prescribed number of standard deviations less different than the mean difference of the luminance values between all pairs of images in a sequence from a single person'"'"'s face.

17. The computer-implemented process of claim 12 wherein the process action of constructing a classifier by training each of a plurality of cascaded classifier stages, comprises the process actions of:

given N pairs (P) of images and their similarity (S=0,1 for non-similar vs. similar), the ith pair and similarity is denoted (P_i,S_i),

initializing each pair'"'"'s weight,

$w_{i,0}=\frac{1}{N_S}<br><br><br><br>\mathrm{or}<br><br><br><br>\frac{1}{N_{\mathrm{NS}}}$

depending on the pair'"'"'s similarity, wherein N_S, N_NS=number of pairs annotated similar and non-similar;

for as many features F_j as needed,

(a) normalizing the weights to sum to 1;

(b) for all possible features F_j, finding a threshold T_j that minimizes the misclassifications =β

FN+FP, wherein the false negatives (FN) are penalized more than false positives (FP) by a factor of β

=5 and for each pair F_j(P_i)=1 (similar) if F_j returns a score with absolute value less than T_j, or 0 otherwise;

(c) for an error, e_j defined to be e_j=Σ

_iw_ij|F_j(P_i)−

S_i|, given all possible (F_j, T_j) choosing the one that minimizes e_j;

(d) setting the voting weight of F_j to be W_j=log [(1−

e_j)/e_j];

(e) summing the votes for each pair of images to classify it V=Σ

_j W_j F_j(P)/Σ

_j W_j;

(f) if V>

τ

then marking P as similar, otherwise marking P as non-similar where τ

is set to 0.5 or is lowered to allow more pairs to be marked similar until an accuracy test is passed;

(g) if the chosen feature(s) pass the FP test going on to the next stage of the cascade, otherwise;

(h) resetting all the weights to decrease the importance of the pairs that were properly classified w_ij+1=w_ij[e_j/(1−

e_j)]wherein the weights of misclassified pairs remain unchanged until normalization in process action (a);

(i) going to process action (a) and choosing an additional feature for this stage of the cascade, until either a given maximum false positive rate is achieved or all features are tested.

18. The computer-implemented process of claim 17 wherein the accuracy test is 0.98 times as accurate as the previous stage;

and wherein the FP test is 0.4 times lower the percentage of false positives.

19. The computer-implemented process of claim 12 wherein the process action of constructing a classifier is performed off-line.

20. The computer-implemented process of claim 12 wherein the process action of constructing a classifier is performed on-line while using said classifier to classify non-similar and similar image pairs.

21. The computer-implemented process of claim 20 wherein said process action of constructing a classifier uses less than the total set of possible features.

22. A system for transmitting and receiving a low bandwidth video stream, the system comprising:

a sender, comprising,

a module for face detection and tracking module which detects a face in an original input image,

a layer decomposition module that decomposes the detected face into regional sub-image layers,

an evaluation module that examines the regional sub-image layers to determine if each of the regional sub-image layers is new, or already present in a sender reference frame database by comparing them to sub-images in the sender reference frame database, and if no matches are found, adding the sub-image layer in question to the sender reference frame database,

a feature selection module that selects features to be used in comparing the regional sub-image layers to the sender'"'"'s reference frame database,

a synthesis module that receives the best matching images to the original input image in the reference frame database and wherein blocks from the best matches to the original input image are synthesized into an image most closely resembling the original input image, and

an encoding and transmission module that encodes new images and the instructions on how to synthesize the image and sends them to a receiver; and

a receiver, comprising,

a receiving and decoding module that receives and decodes said images and instructions sent from said sender;

a synthesis module that draws the respective images from a receiver reference frame database and synthesizes the image that resembles the original image input at the sender according to the sender'"'"'s synthesis instructions, and

a display module that displays said synthesized image at the receiver.

23. A computer-readable medium having computer-executable instructions for transmitting a low bandwidth video stream, said computer executable instructions comprising:

inputting a captured image of a person'"'"'s face;

finding said face in said image;

dividing said face into sub-images corresponding to facial features;

comparing each sub-image to a set of previously saved images;

if a sub-image is determined to be new, adding said new sub-image to said set of previously saved images;

sending said sub-images determined to be new to a receiver;

if a sub-image is determined to be similar to sub-image in said set of previously saved images,

synthesizing a new image closely corresponding to the captured image of a person'"'"'s face; and

sending said receiver instructions for constructing a synthesized image from said set of saved images at said receiver.

24. The computer-readable medium of claim 23 wherein said instruction for dividing said face into sub-images corresponding to facial features, comprises sub-instructions for dividing said face into at least one of:

a sub-image encompassing eyes in the face;

a sub-image encompassing a mouth in the face;

a sub-image encompassing the face without the sub-images encompassing the eyes and the mouth; and

a background sub-image not including the face.

25. The computer-readable medium of claim 23 wherein the instruction for comparing each sub-image to a set of previously saved images, further comprises a sub-instruction for:

constructing a classifier by training each of a plurality of cascaded classifier stages to identify non-similar image pairs and allow only similar pairs to pass on to the next classifier stage if present, wherein each stage is designed to err on the side of false positives but minimize false negatives.

26. The computer-readable medium of claim 25 further comprising an instruction for using said trained plurality of cascaded classifier stages for determining whether a sub-image is similar to a previously saved image.

27. The computer-readable medium of claim 23 wherein the instructions for constructing a synthesized image from said set of saved images at said receiver comprise a pointer to an image in said receiver'"'"'s set of previously saved images to be used.

28. The computer-readable medium of claim 27 wherein said instructions further comprise pixel offset information from which to extract said block from said previously saved image.

29. The computer-readable medium of claim 23 wherein the instruction for synthesizing a new image closely corresponding to the captured image of a person'"'"'s face, comprises sub-instructions for:

for all portions of the input captured image of a person'"'"'s face under consideration,

extracting at least one block from each image in the previously saved set of images that best matches one portion of the captured image of the person'"'"'s face; and

assembling said blocks into said synthesized image that resembles the input captured image of a person'"'"'s face under consideration.

30. The computer-readable medium of claim 29 wherein the instruction for synthesizing a new image closely corresponding to the input captured image of a person'"'"'s face, further comprises sub-instructions for:

if a block cannot be found in an image in the previously saved set of images that matches one portion of the captured image of the person'"'"'s face,

adding said block to said set of previously saved set of images; and

sending said block to a receiver to be added to said receiver'"'"'s set of previously saved images.

31. The computer-readable medium of claim 23 wherein the instruction for finding said face in said image, further comprising an instruction for:

extracting a rectangle closely indicating the face position and size.

32. The computer-readable medium of claim 31 wherein said rectangle changes slightly from input image to input image, and further comprising instructions to ensure said rectangle closely indicating the face position and size have the same size from one input image to the next.

33. The computer-readable medium of claim 32 wherein the instructions for ensuring said rectangle has the same size, comprises sub-instructions for:

averaging the sizes of the rectangle in the first few input images;

using said averaged rectangle size as the fixed rectangle size for all of the remaining input images that are processed; and

scaling each rectangle extracted from each input image so that the newly extracted rectangle has the same size as the averaged rectangle size.

34. The computer-readable medium of claim 29 wherein sub-instruction for extracting at least one block from each image in the previously saved set of images that best matches one portion of the captured image of the person'"'"'s face, further comprises sub-instructions for slightly extending each block so that it overlaps slightly with its neighboring blocks.