Motion estimation/compensation for screen capture video

• US 7,224,731 B2
• Filed: 06/28/2002
• Issued: 05/29/2007
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Mehrotra, Sanjeev
• Primary Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US10/186,473
• Publication Number:
  US 20040001544A1
• Time in Patent Office: 1,796 Days
• Field of Search: 375/240.16, 375/240.24, 375/240.15, 375/240.08, 382/242, 382/103, 382/236, 382/284, 715/781
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/105 Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/557 Motion estimation characterised by stopping computation or iteration based on certain criteria, e.g. error magnitude being too large or early exit
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

The present invention relates to motion estimation and compensation. For example, a screen capture encoder performs motion estimation that is adapted to screen capture video in various respects. For example, the motion estimation uses a distortion measure based upon the count of equal/unequal pixels in two regions, sub-samples the distortion measure to speed up motion estimation, and/or uses a search pattern that prioritizes types of motion common in screen capture video. Or, a screen capture decoder performs motion compensation that is adapted to screen capture video in various respects. For example, the decoder performs the motion compensation for pixels with different values at corresponding locations in a current frame and a reference frame, but not for all pixels of the current frame. Alternatively, an encoder/decoder performs the motion estimation/compensation to compress/decompress other kinds of content.

Claims

1. A screen capture encoder comprising:

a screen capture module for recording plural images of a computer desktop environment in operation as plural screen capture frames, the plural screen capture frames including a current screen capture frame;

a frame buffer for storing a reference screen capture frame; and

a motion estimation module adapted to screen capture video, the motion estimation module for estimating motion from the reference screen capture frame for one or more regions of pixel values in the current screen capture frame, wherein the estimating comprises for a current region of pixel values among the one or more regions of pixel values in the current screen capture frame;

searching for a candidate motion vector for the current region of pixel values in the current screen capture frame according to a motion vector search pattern, wherein the current region of pixel values is at a location (x, y) in the current screen capture frame, and wherein the motion vector search pattern prioritizes motion vectors characteristic of motion in screen capture video such that the motion vectors characteristic of motion in screen capture video are evaluated before other motion vectors;

evaluating the candidate motion vector for the current region of pixel values, wherein the candidate motion vector indicates a displacement location (Δ

x+x, Δ

y+y) of a reference frame region of pixel values in the reference screen capture frame, wherein the evaluating the candidate motion vector comprises;

comparing the current region at the location (x, y) in the current screen capture frame with the reference frame region at the displacement location (Δ

x+x, Δ

y+y) in the reference screen capture frame; and

computing a distortion measure based at least in part upon the comparing, wherein the distortion measure measures a difference between the current region and the reference frame region using identical pixel value matching criteria; and

selecting a final motion vector for the current region of pixel values based at least in part on the evaluating.

2. The screen capture encoder of claim 1 further comprising:

a segmenter for separating palettized content and continuous tone content in intra pixel values in the current screen capture frame following motion estimation, the intra pixel values having different values at corresponding locations in the reference screen capture frame and the current screen capture frame.

3. The screen capture encoder of claim 2 further comprising:

a first encoding module for encoding the continuous tone content; and

a second encoding module for encoding the palettized content.

4. The screen capture encoder of claim 1 wherein the motion vectors characteristic of motion in screen capture video include pure horizontal motions vectors and pure vertical motion vectors.

5. The screen capture encoder of claim 1 wherein the distortion measure is Hamming distance.

6. The screen capture encoder of claim 1 wherein the motion estimation module sub-samples the distortion measure.

7. The screen capture encoder of claim 1 wherein the motion vector search pattern is for a search area comprising the entire reference screen capture frame.

8. The screen capture encoder of claim 1 wherein the motion estimation module sets boundaries for the one or more regions of pixel values based on detected value changes.

9. The screen capture encoder of claim 1 wherein one or more two-dimensional motion motion vectors including the final motion vectors parameterize the motion.

10. A screen capture decoder comprising:

a buffer for storing a reference screen capture frame; and

a motion compensation module adapted to screen capture video, the motion compensation module for compensating for motion from the reference screen capture frame for one or more regions of pixel values in a current screen capture frame, wherein the compensating comprises for a current region of pixel values a location (x, y) among the one or more regions of pixel values in the current screen capture frame;

receiving and processing a final motion vector that specifies a displacement for the current region of pixel values, the final motion vector calculated at a screen capture encoder based on an evaluation of one or more candidate motion vectors for the current region of pixels, wherein the evaluation comprises, for a given one of the one or more candidate motion vectors;

comparing the current region at the location (x, y) in the current screen capture frame with a reference frame region at a displacement location (Δ

x+x, Δ

y+y) in the reference screen capture frame; and

computing a distortion measure based at least in part upon the comparing, wherein the distortion measure measures a difference between the current region and the reference frame region using identical pixel value matching criteria;

wherein the one or more candidate motion vectors are evaluated according to a motion vector search pattern, and wherein the motion vector search pattern prioritizes motion vectors characteristic of motion in screen capture video such that the motion vectors characteristic of motion in screen capture video are evaluated before other motion vectors;

wherein each of the reference and the current screen capture frames is an image recorded from at least part of a computer desktop environment in operation.

11. The screen capture decoder of claim 10 wherein the decoder uses the motion compensation module for less than all pixel values of the current screen capture frame.

12. The screen capture decoder of claim 10 further comprising:

a frame assembler for assembling the current screen capture frame based at least in part upon the one or more regions, palettized content in intra pixels following motion estimation, and continuous tone content in the intra pixels following motion estimation.

13. The screen capture decoder of claim 12 further comprising:

a first decoding module for decoding the continuous tone content; and

a second decoding module for decoding the palettized content.

14. The screen capture decoder of claim 10 wherein the motion vector search pattern is for a search area comprising the entire reference screen capture frame.

15. The screen capture decoder of claim 10 wherein one or more two-dimensional motion vectors including the final motion vector parameterize the motion.

16. A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method comprising:

searching for a candidate motion vector for a current frame region of pixel values in a current screen capture frame according to a motion vector search pattern, wherein the current screen capture frame is recorded from a computer desktop environment in operation, wherein the current frame region is at a location (x, y) in the current screen capture frame, and wherein the motion vector search pattern prioritizes motion vectors characteristic of motion in screen capture video such that the motion vectors characteristic of motion in screen capture video are evaluated before other motion vectors;

evaluating the candidate motion vector for the current frame region, wherein the candidate motion vector indicates a displacement location (Δ

x+x, Δ

y+y) of a reference frame region of pixel values in a reference screen capture frame wherein the evaluating the candidate motion vector comprises;

comparing the current frame region at the location (x, y) in the current screen capture frame with the reference frame region at the displacement location (Δ

x+, Δ

y+y) in the reference screen capture frame; and

computing a distortion measure based at least in part upon the comparing, wherein the distortion measure measures a difference between the current frame region and the reference frame region using identical pixel value matching criteria;

selecting a final motion vector for the current frame region; and

encoding the current frame region with the final motion vector.

17. The computer-readable medium of claim 16 wherein the identical pixel value matching criteria are used for less than all pixel values in the current frame region.

18. The computer-readable medium of claim 16 wherein the identical pixel value matching criteria comprises Hamming distance.

19. The computer-readable medium of claim 16 wherein the motion vectors characteristic of motion in screen capture video include pure horizontal motion vectors and pure vertical motion vectors.

20. The computer-readable medium of claim 16 wherein a frame buffer stores the reference screen capture frame.

21. The computer-readable medium of claim 16 wherein the current frame region is defined by a boundary box, and wherein dimensions and location of the boundary box are based on locations of changed pixels in the current screen capture frame.

22. In a computer system, a method of motion estimation comprising:

in a motion estimation module adapted to screen capture video, for each of one or more motion vectors for a current frame region in screen capture video, computing a count of differing pixel values, each of the one or more motion vectors specifying a different reference frame region in the screen capture video, wherein the screen capture video comprises plural images recorded from a computer desktop environment in operation as plural screen capture frames, the plural screen capture frames including the current frame region, and wherein the computing the count of differing pixel values for each of the one or more motion vectors includes,

comparing multiple-bit pixel values at each of one or more corresponding locations in the current frame region and the different reference frame region specified by the motion vector; and

for each of the one or more corresponding locations, incrementing the count of differing pixel values based upon whether the compared multiple-bit pixel values are equal or not equal;

selecting a final motion vector for the current frame region, wherein the selecting is based at least in part upon the computing the differing pixel value count; and

encoding the current frame region with the final motion vector.

23. A computer-readable medium having stored thereon computer-executable instructions for causing a computer system programmed thereby to perform the method of claim 22.

24. The method of claim 22 wherein the one or more corresponding locations are less than all locations in the current frame region and the different reference frame region specified by the motion vector.

25. The method of claim 22 wherein the multiple-bit pixel values are for palettized screen content.

26. The method of claim 22 wherein the multiple-bit pixel values are for continuous tone screen content.

27. A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method of motion estimation from a reference frame to a current frame, the method comprising:

in a motion estimation module adapted to screen capture video, for each of one or more candidate motion vectors for a current frame region,

selecting the candidate motion vector according to a prioritized motion vector search pattern adapted to screen capture video that prioritizes plural pure horizontal motion vectors and plural pure vertical motion vectors above all other motion vectors; and

computing a distortion measure for the selected candidate motion vector;

selecting a final motion vector for the current frame region; and

encoding the current frame region with the final motion vector.

28. The computer-readable medium of claim 27 wherein screen capture video includes the reference frame and the current frame.

29. A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method comprising:

in a motion estimation module adapted to screen capture video, evaluating a candidate motion vector for a current frame region of pixel values in a current screen capture frame, wherein the current screen capture frame is an image recorded from a computer desktop environment in operation, wherein the current frame region is at a location (x, y) in the current screen capture frame, wherein the candidate motion vector indicates a displacement location (Δ

x+x, Δ

y+y) for a reference frame region of pixel values in a reference screen capture frame, and wherein the evaluating includes computing a sub-sampled pixel value distortion measure for the candidate motion vector;

selecting a final motion vector for the current frame region; and

encoding the current frame region with the final motion vector.

30. The computer-readable medium of claim 29 wherein the method further comprises:

for each of one or more additional candidate motion vectors, repeating the evaluating, each of the evaluated motion vectors having a sub-sampled distortion measure that satisfies a threshold, and wherein the selecting the final motion vector is based at least in part upon computation of a non-sub-sampled distortion measure for at least one of the evaluated motion vectors.

31. A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method comprising:

using segmentation data to identify one or more unchanged pixels between a current screen capture frame and a reference screen capture frame, wherein the current screen capture frame is an image recorded from a computer desktop environment in operation;

performing motion compensation for one or more regions of the current screen capture frame, wherein the motion compensation comprises, for each of the one or more motion compensated regions;

receiving one or more motion vectors; and

calculating motion compensated pixel values; and

assembling the current screen capture frame based at least in part upon the one or more identified unchanged pixels and the one or more motion compensated regions.

32. The computer-readable medium of claim 31 wherein the method further comprises decoding intra pixel data of the current screen capture frame, wherein the assembling is further based at least in part upon the decoded intra pixel data.

33. A method comprising:

comparing pixel values at corresponding locations in a current screen capture frame and a reference screen capture frame to identify pixels in the current screen capture frame with changed values;

creating a bounding box around a group of the pixels in the current screen capture frame with changed values;

performing motion estimation for the bounding box, thereby determining motion data for the bounding box relative to the reference screen capture frame;

comparing the bounding box with a predicted bounding box to identify intra pixels within the bounding box not predicted by the motion estimation; and

encoding the intra pixels using intra compression.

34. A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform the method of claim 33.