System and method for matching blocks in a sequence of images

• US 5,974,192 A
• Filed: 05/06/1996
• Issued: 10/26/1999
• Est. Priority Date: 11/22/1995
• Status: Expired due to Term

• Current Assignee: Comcast MO Group Incorporated (Comcast Corporation)
• Original Assignee: MediaOne Group Inc. (Comcast Corporation), U S West Inc.
• Inventors: Kundu, Amlan
• Primary Examiner(s): Tran, Phuoc
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US08/643,689
• Time in Patent Office: 1,268 Days
• Field of Search: 382/231, 382/233, 382/235, 382/236, 382/260, 382/261, 382/262, 382/254, 382/275, 348/607
• US Class Current: 382/260
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 7/231 using full search

Abstract

Blocks in frames of a video are matched to similar blocks across frames using qualitative characteristics of the pixels in the block. Pixels in a frame are categorized into two or more categories. In one embodiment, three pixel categories are: 1) quasi-constant (QC) pixels having intensity values that vary slowly (e.g., pictorial portions), 2) textured pixels characterized by many small edges and thin-line signals (e.g., texture portions), and 3) dominant-edge (DE) pixels characterized by few sharp and dominant edges (e.g., edge portions). Blocks in different frames are matched by minimizing a cost function that measures the mismatch between a block in a first frame and a plurality of candidate blocks in a second frame. In one embodiment, a cost function comprises a contrast component and a brightness component. The brightness component is determined as a function of the pixel categories. Block matching in sequential frames of a video enables a calculation of displacement or motion estimation in the video. Motion estimation is used, for example, in video compression to encode a reference frame and subsequent displacements of blocks in the frame. The present block-matching invention is also useful in pre-processing video images to minimize noise. Blocks (or even pixels) in a reference frame are matched to corresponding blocks (or pixels) in prior frame and subsequent frames. Various visual components (e.g., contrast, brightness, color) of the matched blocks are used to generate a modified visual component for the block in the reference frame. Noise and other defects are thereby significantly reduced.

Claims

1. In a computer comprising memory, a method for matching a block in a first frame to a block in a second frame, the method comprising the steps of:

receiving a first frame comprising a first block, the first block comprising pixels;

classifying each pixel in the first block into three or more pixel categories;

receiving a second frame comprising a plurality of candidate blocks, each candidate block comprising pixels;

classifying each pixel in each candidate block into the pixel categories; and

matching the first block to a candidate block as a function of the pixel categories,

wherein the matching step comprises minimizing a cost function that measures the mismatch between the first block and each candidate block, and

wherein the cost function comprises a contrast component and a brightness component, and the brightness component is determined as a function of the pixel categories.

2. In a computer comprising memory, a method for filtering a plurality of frames, said frames having a sequential order, the method comprising the steps of:

selecting a current frame from the plurality of frames;

selecting at least one frame having a lower sequential position in the sequential order relative to the current frame;

selecting at least one frame having a higher sequential position in the sequential order relative to the current frame;

determining for at least one pixel in the current frame, a related pixel in the at least one lower sequential position frame and a related pixel in the at least one higher sequential position frame; and

filtering the pixel in the current frame as a function of the related pixel in the at least one lower sequential position frame and the related pixel in the at least one higher sequential position frame, wherein the pixel in the current frame is filtered according to the equation;

space="preserve" listing-type="equation">P.sub.i (x,y)=α

·

P.sub.i-1,i (x,y)+β

·

P.sub.i+1,i (x,y)+(1--β

)·

P.sub.i (x,y)

where

P_i (x,y) is the (x,y)^th pixel value in the current frame I_i ;

P_i-1,i (x,y)^th pixel value in the current frame and is the motion-compensated version of the at least one lower sequential position frame I_i using I_i-1 ;

P_i+1,i (x,y) is the (x,y)^th pixel value in the at least one higher sequential position frame and is the motion-compensated version of the at least one lower sequential position frame I_i using I_i+1

and α and

β

are variables.

3. In a computer comprising memory, a method for filtering a plurality of frames, said frames having a sequential order, the method comprising the steps of:

selecting a current frame from the plurality of frames;

selecting at least one frame having a lower sequential position in the sequential order relative to the current frame;

selecting at least one frame having a higher sequential position in the sequential order relative to the current frame;

determining for at least one pixel in the current frame, a related pixel in the at least one lower sequential position frame and a related pixel in the at least one higher sequential position frame; and

filtering the pixel in the current frame as a function of the related pixel in the at least one lower sequential position frame and the related pixel in the at least one higher sequential position frame;

wherein the related pixel in the at least one lower sequential position frame and the related pixel in the at least one higher sequential position frame are determined from the pixel in the current frame, according to the following steps;

classifying the pixel in the current frame into three or more pixel categories;

classifying each pixel in the at least one lower sequential position and at least one higher sequential position frames into the pixel categories;

matching the pixel in the second frame to a pixel in the first frame, and matching the pixel in the second frame to a pixel in the third frame as a function of the pixel categories, wherein the matching step comprises minimizing a cost function that measures the mismatch between the pixel in the current frame and each pixel in at least one of the at least one lower sequential position frame and the at least one higher sequential position frame, and wherein the cost function comprises a contrast component and a brightness component and the brightness component is determined as a function of the pixel categories.

4. In a computer comprising memory, a method for filtering a plurality of frames, said frames having a sequential order, the method comprising the steps of:

selecting a current frame from the plurality of frames;

selecting at least one frame having a lower sequential position in the sequential order relative to the current frame;

selecting at least one frame having a higher sequential position in the sequential order relative to the current frame;

determining for at least one pixel in the current frame, a related pixel in the at least one lower sequential position frame and a related pixel in the at least one higher sequential position frame; and

filtering the pixel in the current frame as a function of the related pixel in the at least one lower sequential position frame and the related pixel in the at least one higher sequential position frame, wherein the filtering step filters the brightness of the pixel in the current frame as a function of the brightness of the pixel in the at least one lower sequential position frame and the brightness of the pixel in the at least one higher sequential position frame.

5. In a computer comprising memory, a method for filtering a plurality of frames, said frames having a sequential order, the method comprising the steps of:

selecting a current frame from the plurality of frames;

selecting at least one frame having a lower sequential position in the sequential order relative to the current frame;

selecting at least one frame having a higher sequential position in the sequential order relative to the current frame;

determining for at least one pixel in the current frame, a related pixel in the at least one lower sequential position frame and a related pixel in the at least one higher sequential position frame; and

filtering the pixel in the current frame as a function of the related pixel in the at least one lower sequential position frame and the related pixel in the at least one higher sequential position frame, wherein the filtering step filters the contrast of the pixel in the current frame as a function of the contrast of the related pixel in the least one lower sequential position frame and the contrast of the related pixel in the at least one higher sequential position frame.

6. In a computer comprising memory, a method for matching a block in a first frame to a block in a second frame, the method comprising the steps of:

receiving a first frame comprising a first block, the first block comprising pixels;

classifying each pixel in the first block into three or more pixel categories;

receiving a second frame comprising a plurality of candidate blocks, each candidate block comprising pixels;

classifying each pixel in each candidate block into the pixel categories; and

matching the first block to a candidate block as a function of the pixel categories,

wherein the matching step comprises minimizing a cost function that measures the mismatch between the first block and each candidate block, and wherein the cost function comprises a contrast component and a brightness component, and the brightness component is determined as a function of the pixel categories, and wherein the contrast component is determined according to the equation;

space="preserve" listing-type="equation">D.sub.1 (x,y)=contrast.sub.(Candidate Block-First Block)

where

(Candidate Block-First Block) is a pixel-by-pixel intensity subtraction for the pixels in the candidate blocks and the pixels in the first block; and

contrast=0.416·

log(1+1ƒ

1), 1ƒ

1 being the absolute intensity value of a particular pixel (x,y).

7. In a computer comprising memory, a method for matching a block in a first frame to a block in a second frame, the method comprising the steps of:

receiving a first frame comprising a first block, the first block comprising pixels;

classifying each pixel in the first block into three or more pixel categories;

receiving a second frame comprising a plurality of candidate blocks, each candidate block comprising pixels;

classifying each pixel in each candidate block into the pixel categories; and

matching the first block to a candidate block as a function of the pixel categories,

wherein the matching step comprises minimizing a cost function that measures the mismatch between the first block and each candidate block, and wherein the cost function comprises a contrast component and a brightness component, and the brightness component is determined as a function of the pixel categories, and wherein the brightness component is determined according to the equations;

space="preserve" listing-type="equation">D.sub.2 (x,y)=1.00 when P.sub.0 (x,y)ε

E and P.sub.c (x,y)IQ;

or

space="preserve" listing-type="equation">D.sub.2 (x,y)=0.64 when P.sub.0 (x,y)ε

T and P.sub.c (x,y)IQ;

or

space="preserve" listing-type="equation">D.sub.2 (x,y)=0.64 when P.sub.0 (x,y)ε

T and P.sub.c (x,y)IE;

or

space="preserve" listing-type="equation">D.sub.2 (x,y)=0.00 otherwise.

where

the symbols E, Q, and T represent pixels in the dominant edge, quasi-constant, and textural pixel categories, respectively;

P₀ (x,y) denotes a pixel in the first block;

P_c (x,y) denotes a corresponding pixel in the candidate block; and

the symbol means vice versa.