Video image processing

• US 5,086,480 A
• Filed: 10/05/1990
• Issued: 02/04/1992
• Est. Priority Date: 05/06/1987
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Sexton, Graham G.
• Primary Examiner(s): Razavi, Michael
• Application Number:
  US07/594,670
• Time in Patent Office: 487 Days
• Field of Search: 358/126, 358/135, 358/136, 382/9, 382/18, 382/34, 382/56
• US Class Current: 382/171
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: G06V 40/167 using comparisons between temporally consecutive images
• CPC Class Codes: H04N 19/20 using video object coding
• 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 19/94 Vector quantisation

Abstract

A video coder automatically identifies the head area from a head against a background scene.

Identification involves: storing several frames of an image training sequence (1); taking the difference between adjacent frames (2); for all the picture elements (pels) represented by each set of difference data, thresholding the pels against a luminance threshold (3); applying median filtering to the data sets thus obtained (4); then clustering the data sets (5); determining the minimum rectangle which will contain all the remaining non-zero pels represented by each set (6); generating a border of finite thickness around the rectangles (7); generating a head codebook from the pels of the original frames of the image that correspond to the pels represented by the respective sets of data that fall within the respective borders (8), similarly generating a background codebook; and finally generating a composite codebook.

Claims

1. A method of identifying an object against a background within an image array, comprising the steps of:

a) comparing, using vector comparison, each of a plurality of identically shaped, two-dimensional sub-arrays into which the image array is notionally divided as to object and background, with a plurality of vectors from a set,

each said set including a subset comprising a plurality of members of said set associated with the object, and

b) in the event of substantial similarity, labeling that sub-array as corresponding to the object, wherein said plurality of vectors are taken from a codebook which includes a second subset of vectors associated with said object within an image array and a subset of vectors associated with the background with an image array, wherein each vector of each subset has an associated flag indicating which of the object or the background that vector is associated with, so that each sub-array may be labelled as corresponding to the object or to the background by the flag.

2. A method according to claim 1 in which the location of the object is identified by finding within the image array the greatest concentration of sub-arrays labelled as corresponding to the object.

3. A method of detecting a plurality of different objects, according to any one of claim 1 or 2, in which the set includes members associated with each such object.

4. A method of detecting a human head within a video image, employing the method of any one of claims 1 or 2 or 3.

5. A method of encoding a video image signal for transmission comprising the steps of

a) identifying an area of the video image corresponding to an object of visual importance, using a method according to any one of claims 1 or 2, and

b) modifying the spatial allocation of coding data so as to preferentially favour that area,

whereby a greater degree of visual importance may be attributed to that area of the image.

6. A method of encoding a video image signal comprising the steps of:

a) identifying an area of the video image corresponding to an object of visual importance by repeatedly

i) comparing a sub-array of the image with vectors from a set including members associated with the object, and

ii) in the event of substantial similarity, labeling that sub-array as corresponding to the object; and

b) modifying the spatial allocation of coding data in favor of that area, whereby a degree of visual importance may be attributed to that area of the image;

wherein the video image signal is encoded so as to update the area corresponding to the object at a higher rate than other areas.

7. A method of generating a set of vectors for use in a method of identifying a moving object by repeatedly

i) comparing a sub-array of the image with vectors from a set including members associated with the object, and

ii) in the event of substantial similarity, labeling that sub-array as corresponding to the object;

and

said method of generating a set of vectors comprising the steps of;

a) identifying an area of the image corresponding to at least a part of the object, and

b) generating vectors from video-data representing that area of the image, in which the areas of the image corresponding to the object are identified by analyzing the difference between a pair of temporally separated image frames, whereby the object is detected by its movement.

8. An image analyser for identifying an object against a background within an image, comprising vector quantisation means arranged to compare sub-arrays of an image array with vectors from a codebook and select therefrom the most similar vector to each such sub-array, the codebook comprising a subset of vectors associated with the object and a subset of vectors associated with the background, each such vector having an associated flag indicating to which subset it belongs, whereby the analyser may identify the object form the flags of the vectors selected for the sub-arrays.

9. An image analyser according to claim 8, further comprising clustering means for determining the position of a boundary to enclose a given proportion of those sub-arrays flagged as corresponding to the object, whereby the image analyser may identify the position and spatial extent of the object.

10. A coder for encoding video image signals comprising:

a) an image analyser according to any one of claims 8 or 9 arranged to identify an object within an image, and

b) an encoder arranged to preferentially allocate video encoding data to the area of the image corresponding to the object.

11. A coder according to claim 10, in which the encoder is arranged to encode the unquantised image.

12. A coder according to claim 11, in which the coder is a discrete cosine transform encoder.

13. A coder according to claim 10, further comprising:

c) motion analysis means arranged to detect motion of the position of the identified object between temporally separated image frames, and to predict therefrom the position of the object in a subsequent image frame,

whereby the encoder may be a motion compensated DPCM encoder.

14. A coder arranged to employ a method encoding a video image signal comprising the steps of:

a) identifying an area of the video image corresponding to an object of visual importance by repeatedly

i) comparing a sub-array of the image with vectors from a set including members associated with the object, and

ii) in the event of substantial similarity, labeling that sub-array as corresponding to the object; and

b) modifying the spatial allocation of coding data in favor of that area, whereby a degree of visual importance may be attributed to that area of the image.

15. A coder according to claim 14, also arranged initially to generate vectors of the said subsets of the said codebook, further comprising identification means for identifying an area of the image corresponding to the object or to the background, whereby the respective vectors may be generated from data derived from the said area.

16. A coder according to claim 15 in which the identification means is arranged to anlyse the difference between a pair of temporally separated image frames to identify areas of the image corresponding to the object.

17. A coder according to claim 16, in which the identification means comprises:

a) means for generating from a pair of frames of the image array elements within a notional two dimensional field, the value of each position within the field indicating whether the difference between the luminance levels of the picture elements at corresponding positions in the two frames lies above or below a threshold; and

b) clustering means for determining the centre of gravity within the said field of those array elements indicating a deference above the threshold and determining the position of a boundary about the centre of gravity which encloses a given proportion of those array elements,

whereby all picture elements lying within a boundary so determined are identified as belonging to an area of the image corresponding to the object.

18. A coder according to claim 17 which means further comprises filtering means for median filtering the array elements within the notional two dimensional field prior to the determination of the centre of gravity.

19. A coder according to claim 17, wherein said boundary about the centre of gravity is of a finite number of elements in thickness.

20. A coder according to claim 17, wherein said boundary about the centre of gravity is of rectangular shape.

21. A coder according to claim 20, wherein the rectangular shaped boundary is centred upon the centre of gravity and each side of the rectangle is moved inward, if possible, until it abuts at least one of those array elements indicating a difference above the threshold.