Video processing system for modifying a zone in successive images

• US 5,436,672 A
• Filed: 05/27/1994
• Issued: 07/25/1995
• Est. Priority Date: 05/27/1994
• Status: Expired due to Term

• Current Assignee: Evs International (Swiss) Sàrl
• Original Assignee: Symah Vision, SA
• Inventors: Rom, Hillel, Medioni, Gerard, Guy, Gideon
• Primary Examiner(s): Groody, James J.
• Assistant Examiner(s): Horvey, David E.
• Application Number:
  US08/249,348
• Time in Patent Office: 424 Days
• Field of Search: 348/578, 348/584, 348/585, 348/586, 348/590, 348/591, 348/563, 348/564, 348/565, 348/169-172, 382/10, 382/41, 382/57
• US Class Current: 348/591
• CPC Class Codes: H04N 5/272 Means for inserting a foreground image in a background image, i.e. inlay, outlay
• CPC Class Codes: H04N 5/2723 Insertion of virtual advertisement; Replacing advertisements physical present in the scene by virtual advertisement data processing systems or methods specially adapted for marketing G06Q30/02

Abstract

A method and an apparatus for substituting a representation of a target, identified by a set of points of interest stored in a memory, with a matching representation of a predetermined stored pattern in successive TV frames are described. The apparatus has a buffer for storing successive frames of a sequence, constituting a first in-first out memory having a length sufficient for storing all frames over a period of some seconds. Points of interest in each current frame are extracted and an attempt is made to find at least a subset of the extracted points of interest matching with a respective subset of the stored set. Global motion of the image between successive frames is evaluated and the location of the target in the frames following and preceding a frame in which the pattern is found is predicted. A target finder locates the target in the frames where it is found, based on the prediction. Each partial or complete representation of the target in each frame, where found, is replaced with a representation of the stored pattern after the stored pattern has been subjected to size and perspective transformation computed from a comparison between the points of interest in the representation of the target in the respective frame and the respective stored points of interest.

Claims

1. A method of modifying video images which belong to a sequence and which are mutually correlated, said method comprising the steps of:

storing a representation of a target to be replaced with a stored model in said images;

storing a plurality of successive ones of said images of said sequence in a buffer memory;

searching for the target in the stored images by pattern recognition until the target is found with reliability in at least one of said stored images;

carrying out reverse and forward predictions as to the location of the target in said stored images which precede and follow the image where the target is found, based on an evaluation of global changes of the stored images, whereby precise identification of the location of the target in a particular one of said images is achieved even when only part of the target is available within the particular image; and

replacing said target with a respective representation of the model.

2. A method of substituting a representation of a target, identified by a set of points of interest stored in a memory, with a matching representation of a predetermined stored pattern of same geometrical shape, in successive TV frames of a sequence of frames taken from a video camera, said method comprising the steps of:

(a) storing successive frames of said sequence in a buffer,

(b) extracting points of interest from each current frame of the sequence in turn and attempting to find at least a subset of said extracted points of interest from each current frame which matches with a respective subset of said stored set of points of interest,

(c) evaluating motion of said camera between each current frame where such a match is found and following and preceding frames in the sequence, based on a global comparison between contents of the frames;

(d) predicting locations of said target in said following and preceding frames in the sequence from the evaluated motion,

(e) automatically searching for said target in said following and preceding frames in said sequence using the predicted locations; and

(f) in each searched frame, replacing the representation of said target with a representation of said stored pattern after said stored pattern has been subjected to transformation computed from a comparison between a plurality of points of interest in said representation of the target in the respective frame and the stored points of interest.

3. Method according to claim 2, wherein said points of interest include corners and vertices in the representation of the target.

4. Method according to claim 3, wherein said points of interest are obtained by applying an operator using first derivatives of an image as represented by each frame, said method further comprising the steps of:

(b1) computing first spatial derivatives of a radiometric value I throughout the image and computing I²_x, I²_y and I_x I_y, where x and y designate a line scanning direction and direction orthogonal to the line scanning direction, respectively,

(b2) convolving I²_x, I²_y and I_x I_y with a box filter to obtain three substitute images n₁₁ n₂₂, n₁₂, and

(b3) starting from n₁₁, n₂₂ and n₁₂, computing a weight image and an isotropy image, comparing the weight image and the isotropy image with respective thresholds and retaining only those values in the weight image for which both the weight image and the isotropy image are higher than the respective thresholds.

5. Method according to claim 2, further including a preprocessing step comprising extracting relevant features from a model of the target, said preprocessing step including detecting triplets of points constituting stable bases and storing said triplets along with a pair of affine coordinates associated therewith.

6. A method according to claim 5, wherein said preprocessing step further includes:

manually designating in one frame, a pair of colors by pointing at a plurality of points separating the colors of said pair,

automatically selecting, as said points of interest, some other points in at least part of said frame which separate said colors, prior to extracting said relevant features including said points of interest.

7. An apparatus for substituting a representation of a target, identified by a set of points of interest stored in a memory, with a matching representation of a predetermined stored pattern of same geometrical shape, said substituting to take place in successive TV frames of a sequence of frames taken from a video camera, said apparatus comprising:

buffer means for storing successive frames of said sequence, said buffer means comprising a first in-first out memory having a length sufficient for simultaneously storing a predetermined plurality of said frames over a period of some seconds;

means for extracting points of interest in each current said frame of the sequence in turn and attempting to find at least a subset of the extracted points of interest matching with a respective subset of the stored set;

means for evaluating global motion between successive frames and for predicting a location of the target in the frames following and preceding a frame in which the pattern is found;

target finding means for precisely locating the target in the frames where it is found, based on the prediction;

replacer means for replacing a partial or complete representation of the target in each frame where it is found, with a representation of the stored pattern after the stored pattern has been subjected to size and perspective-transformation computed from a comparison between some at least of the points of interest in the representation of the target in the respective frame and the respective stored points of interest.

8. Apparatus according to claim 7, wherein said means for evaluating global motion of the image comprises means for smoothing the image in each frame in turn and computing estimates of a motion parameter.

9. Apparatus according to claim 7, wherein the means for evaluating global motion comprises means for computing the motion of a scene as seen by the camera between a previous frame and each current frame.

10. Apparatus according to claim 7, wherein said target finding means comprises:

an interest point operator for extracting said interest points on neighbourhoods;

a focus-of-attention sub-module for selecting the interest points most likely to be found in the target, based on color information;

a point matcher sub-module for finding a set of corresponding points between interest points in a stored model of the target and interest points found in each actual frame in turn;

a precise lock-in sub-module for finding a precise location of the target in the frame, from the correspondences given by said point matcher sub-module; and

a predictor sub-module for predicting the location of the target in any frame of order n, assuming that the target was found in another frame of the sequence, based on information received from the precise lock-in sub-module and from the means for evaluating global motion of the image.

14. Apparatus according to claim 7, further comprising obstacle detection means for comparing a stored model of the target and the target representation in each said frame, for warping the target representation to make it match the stored model, for computing differences and for communicating said differences to said replacer means as an obstacle map.

15. Apparatus according to claim 14, wherein said replacer means comprises means for warping said stored pattern for making it match the respective representation of said target and means for substituting all pixels in said respective representation, except those represented by said obstacle map, with corresponding pixels of the warped stored pattern.

16. A method of manipulating video images which belong to a sequence and which are mutually correlated, said method comprising the steps of:

storing a representation of a target to be identified in said images;

storing a plurality of successive ones of said images of said sequence in a buffer memory;

searching for the target in the stored images by pattern recognition until the target is found with reliability in one at least of said stored images;

carrying out reverse and forward predictions as to the location of the target in those of said stored images preceding and following the image where the target is found, based on an evaluation of global changes of the images, whereby precise identification of the location of the target in a particular one of said images is achieved even when only part of the target is available within the particular image.

11. Apparatus according to claim 16, further comprising an updater module for collecting data from other said means and interpolating information between said frames.

12. Apparatus according to claim 11, wherein said updater module comprises a circular buffer memory having a plurality of successive cells each storing attributes of one said frame, said attributes comprising at least one of:

a global motion transformation between the respective frame and a next frame, plus a measure of belief,

a transformation between the respective said frame and a next said frame, plus a measure of belief,

a flag representing the position of the respective said frame in a respective said sequence, and

a linked list of hypotheses, each containing a plurality of indications on edges of the target in image coordinates, plus a measure of belief.

13. Apparatus according to claim 11, wherein said means for evaluating global motion further include a sequence break detection sub-module for signalling sudden changes between successive said frames and communicating said changes to said updater unit for recordal among said attributes.