Ternary image templates for improved semantic compression

• US 5,832,115 A
• Filed: 01/02/1997
• Issued: 11/03/1998
• Est. Priority Date: 01/02/1997
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rosenberg, Jonathan David
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Chen, Wenpeng
• Application Number:
  US08/775,906
• Time in Patent Office: 670 Days
• Field of Search: 382/242, 382/199, 382/213, 382/243, 382/118, 382/190, 382/194, 382/195, 382/203, 382/205, 382/209, 382/221, 382/103, 348/586
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30201 Face
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

Abstract

A method and apparatus for carrying out rapid, block-based SAD search operations for facial ellipses in a CIF videophone image frame are disclosed. A set of search templates, each having an ellipse pattern with two concentric, contiguous perimeters is defined and a set of parameter values are calculated off line for each template: a predetermined subfactor, index number, number of pixels in its dithered perimeter pattern, and first and second match thresholds. The pixels in the lower portion of each perimeter in the pattern are thinned by dithering so as to emphasize the upper contour of the ellipse. Values of +2k for interior perimeter pixels and -2k for exterior pixels in the template are then added to corresponding +k edge pixels and -k non-edge pixels in each search position of the template on a thresholded binary edge map of the image frame. The sum is then normalized and the template and search position producing the best SAD match metric value is identified as a facial area, without requiring symmetry detection.

Claims

1. Apparatus for detecting edge contours approximating a given feature in a pixel matrix representing a given image frame, said apparatus comprising:

an edge detector for producing an edge map from the pixel matrix, said edge map having a first plurality of edge pixels and a second plurality of non-edge pixels, each pixel in one of said first and second pluralities of pixels having an assigned value of +k and each pixel in the other one of said first and second pluralities of pixels having an assigned value of -k;

a first feature template having a feature pattern including a first and a second feature contour, said first and second feature contours being contiguous with each other and having a plurality of pixels, each pixel in said first feature contour having an assigned value of -2k, each pixel in said second feature contour having an assigned value of +2k, and pixels in said first feature template outside said first and second feature contours having an assigned value of 0k; and

an array processor for calculating sum-and-absolute-difference values between a block of pixels in said first feature template and a corresponding block of pixels on said edge map corresponding to said block of pixels in said first feature template at a given location of said first feature template on said edge map, and for using said sum-and-absolute-difference values to calculate an estimated correlation between edge contours on said edge map and said feature contours in said first feature template as a match metric.

2. The apparatus of claim 1, further comprising:

a dithered portion in said first and second feature contours of each feature pattern, said dithered portion of said first and second feature contours, respectively, having contours that are farther from other pixels in said respective contours than pixels in a non-dithered portion of said respective contours.

3. The apparatus of claim 1 wherein said edge map includes background edges, said apparatus further comprising:

means for detecting said background edges; and

means for removing said background edges from said edge map before calculating said sum-and-absolute-difference values.

4. The apparatus of claim 1, further comprising:

means for calculating said estimated correlation between said edge contours on said edge map and said feature contours in said first feature template at a first and a second location of said first feature template on said edge map, respectively, said first location lacking at least some pixels from said corresponding block of pixels in said second location; and

means for determining which of said first and second locations is a best-match location, said best match location producing a best match metric indicating that said best-match location provides a closest correlation between said edge contours and said feature contours in said best-match location of said first feature template among said first and second locations of said first feature template on said edge map.

5. The apparatus of claim 4 further comprising:

template storage apparatus for storing said assigned values of said pixels in said first feature template off-line, said template storage apparatus being operatively connected to provide said assigned values to said array processor, said array processor being adapted for calculating on-line said sum-and-absolute-difference values and said estimated correlations between feature contours in said first feature template and edge contours in respective first and second edge maps produced from respective pixel matrixes representing respective first and second sequential image frames in an on-line sequence of image frames and for determining a respective best match metric for said first and second sequential image frames on-line.

6. The apparatus of claim 5 further comprising:

edge storage apparatus operatively connected to said array processor for storing respective locations of said edge contours on said first edge map;

means for determining first and second sets of edge contours on said second edge map, said first set of edge contours being a set of edge contours having respective locations having moved more than a predetermined distance from corresponding edge-contour locations on said first edge map, and said second set of edge contours being a set of edge contours having respective locations having not moved more than said predetermined distance from said corresponding edge-contour locations on said first edge map; and

means for removing one of said first and second sets of edge contours from said second edge map before calculating said sum-and-absolute difference values for a location of said first feature template on said edge map.

7. The apparatus of claim 1, further comprising:

a second feature template having a feature pattern different from said feature pattern in said first feature template, said array processor being adapted to calculate sum-and-absolute difference values and an estimated correlation as a match metric for said second feature template at said given location on said edge map; and

normalizing means for normalizing each respective match metric produced by said estimated correlation calculated for each feature template and for comparing said respective normalized match metrics to determine which of said feature templates has a best match metric, said best match metric corresponding to a normalized match metric for a closest estimated correlation between edge contours in said location of said feature template on said edge map and feature contours in said feature template.

8. The apparatus of claim 7, further comprising:

subfactor storage apparatus for storing a respective subfactor for each feature template off-line, said subfactor storage apparatus being operatively connected to said normalizing means to provide said respective subfactors for use in normalizing said match metrics for comparing said normalized match metrics calculated for respective feature templates to determine on-line which of said feature templates has said best match metric for respective first and second edge maps produced from respective pixel matrixes representing respective first and second sequential image frames in an on-line sequence of image frames.

9. The apparatus of claim 7, further comprising:

reference storage apparatus for supplying said location of a feature template on a first edge map producing a best match metric for said first edge map as a last-best location, said first and second locations being locations on a second edge map including pixels corresponding to pixels in said last-best location on said second edge map, said first and second edge maps being produced from respective pixel matrixes representing respective first and second sequential image frames in a sequence of image frames, said first and second edge maps each having a respective best match metric.

10. The apparatus of claim 9, further comprising:

iteration control means for testing whether said best match metric for a given edge map exceeds a first minimum value, said array processor calculating sum-and-absolute-difference values for feature template locations on said second edge map not including said pixels corresponding to pixels in said last-best feature template location on said first edge map when said best match metric for said second edge map is less than said first minimum value.

11. The apparatus of claim 10, further comprising:

reference control means for determining whether said best match metric for said second frame exceeds a second minimum value, said second minimum value being lower than said first minimum value, said reference control means substituting said first frame for said second frame and substituting said last best location for a best location in said second frame when said best match metric for said second frame does not exceed said second minimum value.

12. Apparatus for providing a higher detail level to compression-coded pixels in a part of a given pixel matrix representing a video-image frame, said part including edge contours correlating with contours of a facial ellipse, said apparatus comprising:

an edge detector for producing an edge map from the pixel matrix, said edge map having a first plurality of edge pixels and a second plurality of non-edge pixels, each pixel in one of said first and second pluralities of pixels having an assigned value of +k and each pixel in the other one of said first and second pluralities of pixels having an assigned value of -k;

template storage apparatus for storing face templates, each of said face templates including an ellipse pattern having a first and a second ellipse contour, said ellipse contours being contiguous with each other, and each said ellipse contour having a plurality of pixels, each pixel in said first ellipse contour having an assigned value of -2k, each pixel in said second ellipse contour having an assigned value of +2k, and pixels in said face template outside said first and second ellipse contours having an assigned value of 0k;

an array processor for calculating sets sum-and-absolute-difference values between a block of pixels in each of said face templates and a corresponding block of pixels on said edge map corresponding to said block of pixels in each face template at a given location of said face template on said edge map, for using said sets of sum-and-absolute-difference values to calculate respective estimated correlations between edge contours on said edge map and said ellipse-contours in each face template in a first location on said edge map as a respective first match metric for said respective face template, for using said sets of sum-and-absolute-difference values to calculate respective estimated correlations between edge contours on said edge map and said ellipse-contour pixels in each face template in a second location on said edge map as a second match metric for said respective face template, for determining which of said first and second locations is a best-match location for each face template, said best match location producing a best match metric indicating that said respective best-match location has a closest correlation between said edge contours and said ellipse contours in said respective template, and for determining a best-match face template by comparing respective best match metrics produced by respective best-match locations of said face templates on said edge map;

normalizing means for normalizing said best-match metric calculated for each template before determining said best-match face template;

a coder for encoding pixels in said video image frame; and

control means for locating facial pixels in a part of said image pixel matrix corresponding to edge pixels in said edge map that correspond to pixels in said ellipse pattern of said face template on said location on said edge map producing said best match metric, said coder being responsive to said control means for providing a higher detail level for said facial pixels.

13. The apparatus of claim 12, further comprising:

reference control means for determining whether said best match metric in a second frame exceeds a minimum value, and for substituting a first frame for said second frame and substituting a last-best face location in said first frame determined by said best-match metric for said first frame when said best match metric of said second frame does not exceed said minimum value.

14. The apparatus of claim 12, further comprising:

an encoder for providing an output signal including an encoded compressed video image and a face-reference location code for each image frame for controlling post-filtering of said compressed video image when said image is decoded, said face-reference location code indicating where said facial pixels are located.

15. A method for detecting edge contours approximating a given feature in a pixel matrix representing a given image frame, said method comprising the steps of:

producing an edge map having a first plurality of edge pixels and a second plurality of non-edge pixels, each pixel in one of said first and second pluralities of pixels having an assigned value of +k and each pixel in the other one of said first and second pluralities of pixels having an assigned value of -k;

defining a feature template having a feature pattern including a first and a second feature contour, said first and second feature contours being contiguous with each other and each of said feature contours having a plurality of pixels, each pixel in said first feature contour having an assigned value of -2k, each pixel in said second feature contour having an assigned value of +2k, and pixels in said feature template outside said first and second feature contours having an assigned value of 0k; and

calculating sum-and-absolute-difference values between a block of pixels in said feature template and a corresponding block of pixels on said edge map corresponding to said block of pixels in said feature template at a given location of said feature template on said edge map, and using said sum-and-absolute-difference values to calculate an estimated correlation between edge contours on said edge map and feature contours in said feature template as a match metric.

16. The method of claim 15, further comprising the step of selecting a value of k to assure an integer result from the match-metric calculation an to prevent overflow in the co-processor.

17. The method of claim 15, wherein the largest and most detailed template (i, j) is defined in said defining step in accordance with:

##EQU18##

18. The method of claim 15, further comprising the step of subtracting said edge map from each template to form a respective occupancy matrix having pixel values between 0k and ±

3k.

19. The method of claim 15, further comprising the step of evaluating the estimated correlation at each position of each template using a respective match metric that is a function of the total number of edge/exterior-pattern pixels and non-edge/interior-pattern pixels in the occupancy matrix computed for a location of a template.

20. The method of claim 15, further comprising the step of normalizing said sum of pixels in the occupancy matrix to a match metric expressed as a percentage of the total number of interior and exterior pattern pixels in the given template.

21. The method of claim 15 wherein said sum of pixels in the occupancy matrix is calculated as S-kXY, where:

##EQU19##

22. The method of claim 21, wherein said calculation is implemented as a motion compensation "mc" command operating on template pixels T_i,j and edge map pixels M_i,j.

23. The method of claim 21, further comprising the steps of:

converting S-kXY to a match-metric percentage value for a given level of precision "v" by multiplying (S-kXY) by a "divfactor" to calculate a multiplication product; and

correcting the result by shifting the multiplication product rightward by "v" spaces;

##EQU20##