Patent US6571016B1 successfully refreshed from Google Patents.
US6571016B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Intra compression of pixel blocks using predicted mean
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-05-05
•
Granted: 2003-05-27
•
Expires: 2017-05-05
Abstract
Abstract An apparatus and method for encoding video frames is provided. The video frames are divided into blocks for encoding. Encoding of the video blocks utilizes motion detection, motion estimation and adaptive compression, to obtain the desired compression for a particular bit rate. Adaptive compression includes intra compression (without regard to other frames) and inter compression (with regard to other frames). Intra compression, inter compression with motion detection, and inter compression with motion estimation are performed on a block by block basis, as needed. Segmentation is provided to compare encoding of a block with encoding of its sub-blocks, and to select the best block size for encoding.
Inventors
- 👤 Sanjeev Mehrotra
- 👤 Albert S. Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 12:06
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/119; H03; H03M; H03M7/00; H03M7/30; H03M7/3082; H04N19/134; H04N19/146; H04N19/147; H04N19/189; H04N19/19; H04N19/48; H04N19/50; H04N19/503; H04N19/51; H04N19/593; H04N19/60; H04N19/61; H04N19/63; H04N19/90; H04N19/94; H04N19/96; H04N19/115
Claims Analysis
Total Claims: 55
Claim 1
Independent Claim
173 words
A method for encoding a video frame to be transmitted over a communications medium, the method comprising the steps of: obtaining a video frame; separating the frame into a plurality of blocks; encoding a plurality of blocks using inter compression; encoding the plurality of blocks using predictive intra compression; selecting better block compression between said steps of inter compression and intra compression for the plurality of blocks; wherein said steps of encoding of the plurality of blocks is performed on a block by block basis, to provide optimum compression of the video frame for a given bit rate; and wherein predictive intra compression comprises the steps of: obtaining pixel values that are adjacent to a first block in the plurality of blocks; predicting pixel values for the first block in the plurality of blocks from the obtained adjacent pixel values; calculating a distance between the predicted pixal values and the actual pixel values for the first block in the plurality of blocks; creating a residual from the calculated distance; and encoding the residual.
Claim 2
Independent Claim
173 words
A method for encoding a video frame to be transmitted over a communications medium, the method comprising the steps of: obtaining a video frame; separating the frame into a plurality of blocks; encoding a plurality of blocks using inter compression; encoding the plurality of blocks using predictive intra compression; selecting better block compression between said steps of inter compression and intra compression for the plurality of blocks; wherein said steps of encoding of the plurality of blocks is performed on a block by block basis, to provide optimum compression of the video frame for a given bit rate; and wherein predictive intra compression comprises the steps of: obtaining pixel values that are adjacent to a first block in the plurality of blocks; predicting pixel values for the first block in the plurality of blocks from the obtained adjacent pixel values; calculating a distance between the predicted pixal values and the actual pixel values for the first block in the plurality of blocks; creating a residual from the calculated distance; and encoding the residual.
Claim 3
Dependent Claim
26 words
The method for encoding a video frame, as recited in claim 1 , wherein the video frame has a dimension of 320 pixels by 240 pixels.
Claim 4
Dependent Claim
21 words
The method for encoding a video frame, as recited in claim 1 , wherein the communications medium is a computer network.
Claim 5
Dependent Claim
21 words
The method for encoding a video frame, as recited in claim 3 , wherein the computer network is an ethernet network.
Claim 6
Dependent Claim
28 words
The method for encoding a video frame, as recited in claim 3 , wherein the computer network comprises a POTS (plain old telephone service) connection between remote computers.
Claim 7
Dependent Claim
31 words
The method for encoding a video frame, as recited in claim 1 , wherein said step of obtaining a video frame comprises reading a video sequence to extract the video frame.
Claim 8
Dependent Claim
31 words
The method for encoding a video frame, as recited in claim 1 , wherein said step of obtaining a video frame comprises retrieving the video frame from a permanent storage device.
Claim 9
Dependent Claim
23 words
The method for encoding a video frame, as recited in claim 7 , wherein the permanent storage device is a hard disk drive.
Claim 10
Dependent Claim
22 words
The method for encoding a video frame, as recited in claim 7 , wherein the permanent storage device is an optical drive.
Claim 11
Dependent Claim
26 words
The method for encoding a video frame, as recited in claim 1 , wherein said step of obtaining a video frame is performed by a computer.
Claim 12
Dependent Claim
43 words
The method for encoding a video frame, as recited in claim 1 , wherein said step of separating the frame into a plurality of blocks comprises: separating the frame into a plurality of macroblocks; and separating the macroblocks into a plurality of blocks.
Claim 13
Dependent Claim
21 words
The method for encoding a video frame, as recited in claim 11 , wherein the macroblocks are of size 16×16 pixels.
Claim 14
Dependent Claim
21 words
The method for encoding a video frame, as recited in claim 11 , wherein the blocks are of size 8×8 pixels.
Claim 15
Dependent Claim
21 words
The method for encoding a video frame, as recited in claim 11 , wherein the blocks are of size 8×4 pixels.
Claim 16
Dependent Claim
42 words
The method for encoding a video frame, as recited in claim 1 , wherein inter compression motion estimation of a second block in the plurality of blocks with a second block having an identical spatial location, but in a different video frame.
Claim 17
Dependent Claim
48 words
The method for encoding a video frame, as recited in claim 15 , wherein said step of encoding the plurality of blocks using inter compression comprises comparing a second distance between the second block in the plurality of blocks with the second block in the different video frame.
Claim 18
Dependent Claim
43 words
The method for encoding a video frame, as recited in claim 16 , wherein the second distance comprises a squared error difference of pixel values between the second block in the plurality of blocks and the second block in the different video frame.
Claim 19
Dependent Claim
52 words
The method for encoding a video frame, as recited in claim 17 , wherein if the squared error is less than a predefined threshold, said step of encoding the plurality of blocks using inter compression comprises: creating a header having a motion vector of 0,0; and encoding the header using adaptive compression.
Claim 20
Dependent Claim
43 words
The method for encoding a video frame, as recited in claim 1 , wherein inter compression comprises performing motion estimation of a second block in the plurality of blocks with a second block having a different spatial location in a different video frame.
Claim 21
Dependent Claim
158 words
The method for encoding a video frame, as recited in claim 1 , wherein said step of encoding the plurality of blocks using inter compression comprises: searching for corresponding block within a different video frame whose difference to a second block in the plurality of blocks is minimum; calculating the difference between the second block in the plurality of blocks and the corresponding block in the different video frame; creating a second residual from said step of calculating the difference between the second second block in the plurality of blocks and the corresponding block in the different video frame; creating a motion vector for the second residual of corresponding to an offset between the corresponding block in the different video frame, and a second block in the different video frame having an identical spatial location to that of the second block in the plurality of blocks; and encoding the motion vector and the second residual using adaptive compression.
Claim 22
Dependent Claim
46 words
The method for encoding a video frame, as recited in claim 20 , wherein said step of searching is restricted to a predefined search area that surrounds the second block in the different video frame, but is less than the size of the different video frame.
Claim 23
Dependent Claim
40 words
The method for encoding a video frame, as recited in claim 20 , wherein if a corresponding block in the different video frame is not found, then encoding the second block in the plurality of blocks using predictive intra compression.
Claim 24
Dependent Claim
78 words
The method for encoding a video frame, as recited in claim 1 , wherein said step of obtaining adjacent pixel values comprises: a) obtaining pixel values across the top of the first block, if available; b) obtaining pixel values across a left side of the first block, if available; c) calculating a mean of the pixel values obtained in steps a) and b); and d) using the calculated mean as the predicted pixel values for the first block.
Claim 25
Dependent Claim
74 words
The method for encoding a video frame, as recited in claim 1 , wherein predictive intra compression comprises: a) obtaining pixel values across a top of the first block, if available; b) obtaining pixel values across a left side of the first block, if available; c) developing a training sequence from the pixel values obtained in steps a) and b); and d) using the training sequence to predict pixel values for the first block.
Claim 26
Dependent Claim
32 words
The method for encoding a video frame, as recited in claim 1 , wherein said steps of encoding the plurality of blocks are applied to different block sizes within a video frame.
Claim 27
Dependent Claim
43 words
The method for encoding a video frame, as recited in claim 1 , wherein the method further comprises the step of: segmenting the plurality of blocks into segmented blocks of different sizes, said step of segmenting for optimizing compression of the video frame.
Claim 28
Dependent Claim
76 words
The method for encoding a video frame, as recited in claim 1 , wherein said step of segmenting comprises: a) adaptively compressing a second block of a first size; b) adaptively compressing a plurality of sub blocks of smaller size, within the second block; c) comparing steps a) and b) to determine which block size provided optimum compression; and d) segmenting the first block according to step c) to obtain optimum compression for the first block.
Claim 29
Dependent Claim
28 words
The method for encoding a video frame, as recited in claim 27 , wherein steps b)-d) are performed recursively on selectively smaller sub blocks within the second block.
Claim 30
Independent Claim
130 words
A method for encoding a video frame, the method comprising: obtaining a video frame; encoding a plurality of blocks of the video frame using inter compression; encoding the plurality of blocks using predictive intra compression, wherein encoding the plurality of blocks using predictive intra compression comprises: obtaining pixel values that are adjacent to the first block in the plurality of blocks, predicting pixel values for the first block in the plurality of blocks from the obtained adjacent pixel values; calculating a distance between the predicted pixal values and the actual pixel values for the first block in the plurality of blocks; creating a residual from the calculated distance; and encoding the residual; and selecting better block compression between the inter compression and the intra compression for the plurality of blocks.
Claim 31
Independent Claim
130 words
A method for encoding a video frame, the method comprising: obtaining a video frame; encoding a plurality of blocks of the video frame using inter compression; encoding the plurality of blocks using predictive intra compression, wherein encoding the plurality of blocks using predictive intra compression comprises: obtaining pixel values that are adjacent to the first block in the plurality of blocks, predicting pixel values for the first block in the plurality of blocks from the obtained adjacent pixel values; calculating a distance between the predicted pixal values and the actual pixel values for the first block in the plurality of blocks; creating a residual from the calculated distance; and encoding the residual; and selecting better block compression between the inter compression and the intra compression for the plurality of blocks.
Claim 32
Dependent Claim
28 words
A method as recited in claim 29 , further comprising compressing the video frame using the selected block compressions for each of the blocks of the video frame.
Claim 33
Dependent Claim
148 words
A method as recited in claim 29 , wherein encoding the plurality of blocks using inter compression comprises: searching for a corresponding block within a different video frame whose difference to a second block of the plurality of blocks is a minimum; calculating the difference between the second block in the plurality of blocks and the corresponding block in the different video frame; creating a second residual from the calculating the difference between the second block in the plurality of blocks and the corresponding block in the different video frame; creating a motion vector for the second residual corresponding to an offset between the corresponding block in the different video frame, and a second block in the different video frame having an identical spatial location to that of the second block in the plurality of blocks; and encoding the motion vector and the second residual using adaptive compression.
Claim 34
Dependent Claim
31 words
A method as recited in claim 29 , wherein the encoding using inter compression and the encoding using predictive intra compression are applied to different block sizes within the video frame.
Claim 35
Dependent Claim
165 words
One or more computer readable media having stored thereon a plurality of instructions for encoding a video frame, wherein the instructions, when executed by a processor, cause the processor to perform acts comprising: encoding a block of a video frame using inter compression; encoding the block using predictive intra compression, wherein encoding the block using predictive intra compression comprises: obtaining pixel values that are adjacent to the block, predicting pixel values for the block from the obtained adjacent pixel values, calculating a distance between the predicated pixel values and the actual pixel values for the block, creating a residual from the calculated distance, and encoding the residual; identifying which of the encodings of the block results in a higher compression ratio for the block; selecting the encoding of the block that results in the higher compression ratio for the block; and repeating both of the encodings using inter compression and predictive intra compression, the identifying, and the selecting for additional blocks of the video frame.
Claim 36
Dependent Claim
165 words
One or more computer readable media having stored thereon a plurality of instructions for encoding a video frame, wherein the instructions, when executed by a processor, cause the processor to perform acts comprising: encoding a block of a video frame using inter compression; encoding the block using predictive intra compression, wherein encoding the block using predictive intra compression comprises: obtaining pixel values that are adjacent to the block, predicting pixel values for the block from the obtained adjacent pixel values, calculating a distance between the predicated pixel values and the actual pixel values for the block, creating a residual from the calculated distance, and encoding the residual; identifying which of the encodings of the block results in a higher compression ratio for the block; selecting the encoding of the block that results in the higher compression ratio for the block; and repeating both of the encodings using inter compression and predictive intra compression, the identifying, and the selecting for additional blocks of the video frame.
Claim 37
Dependent Claim
40 words
One or more computer readable media as recited in claim 33 , wherein the instructions further cause the processor to perform acts comprising compressing the video frame using the selected encodings for each of the blocks of the video frame.
Claim 38
Dependent Claim
41 words
One or more computer readable media as recited in claim 33 , wherein the instructions further cause the processor to perform acts comprising: separating the video frame into a plurality of macroblocks; and separating the macroblocks into the plurality of blocks.
Claim 39
Dependent Claim
124 words
One or more computer readable media as recited in claim 33 , wherein encoding the block using inter compression comprises: searching for a corresponding block within a different video frame whose difference to the block is smaller than other blocks within the different video frame; calculating the difference between the block and the corresponding block; creating a residual from the calculating the difference between the block and the corresponding block; creating a motion vector for the residual corresponding to an offset between the corresponding block in the different video frame, and a first block in the different video frame having an identical spatial location to that of the block in the video frame; and encoding the motion vector and the residual using adaptive compression.
Claim 40
Dependent Claim
35 words
One or more computer readable media as recited in claim 33 , wherein the encoding using inter compression and the encoding using predictive intra compression are applied to different block sizes within the video frame.
Claim 41
Independent Claim
92 words
A method comprising: encoding a block of a video frame using inter compression; encoding the block using predictive intra compression, wherein encoding the block using predictive intra compression comprises: obtaining pixel values that are adjacent to the block, predicting pixel values for the block from the obtained adjacent pixel values, calculating a distance between the predicated pixel values and the actual pixel values for the block, and creating a residual from the calculated distance, and encoding the residual; selecting the one of the encodings that results in better compression for the block.
Claim 42
Independent Claim
92 words
A method comprising: encoding a block of a video frame using inter compression; encoding the block using predictive intra compression, wherein encoding the block using predictive intra compression comprises: obtaining pixel values that are adjacent to the block, predicting pixel values for the block from the obtained adjacent pixel values, calculating a distance between the predicated pixel values and the actual pixel values for the block, and creating a residual from the calculated distance, and encoding the residual; selecting the one of the encodings that results in better compression for the block.
Claim 43
Dependent Claim
25 words
A method as recited in claim 38 , further comprising compressing the video frame using the selected encodings for the blocks of the video frame.
Claim 44
Dependent Claim
38 words
A method as recited in claim 38 , further comprising: separating the video frame into a plurality of macroblocks; and separating the macroblocks into a plurality of blocks, wherein the block is one of the plurality of blocks.
Claim 45
Dependent Claim
108 words
A method as recited in claim 38 , wherein encoding the block using inter compression comprises: searching for a corresponding block within a different video frame whose difference to the block is smaller than other blocks within the different video frame; calculating the difference between the block and the corresponding block; creating a second residual from the calculating the difference between the block and the corresponding block; creating a motion vector for the second residual corresponding to an offset between the corresponding block in the different video frame, and a first block in the video frame; and encoding the motion vector and the second residual using adaptive compression.
Claim 46
Dependent Claim
30 words
A method as recited in claim 38 , wherein the encoding using inter compression and the encoding using intra compression are applied to different block sizes within the video frame.
Claim 47
Independent Claim
119 words
A method comprising: analyzing each of a plurality of blocks of a video frame to determine whether inter compression or predictive intra compression results in better compression for the block; and selecting, for each of the plurality of blocks, the one of inter compression and predictive intra compression that results in better compression for the block; and encoding a first block of the plurality of blocks using predictive intra compression by: obtaining pixel values that are adjacent to the block, predicting pixel values for the block from the obtained adjacent pixel values, calculating a distance between the predicted pixel values and the actual pixel values for the block, creating a residual from the calculated distance, and encoding the residual.
Claim 48
Independent Claim
119 words
A method comprising: analyzing each of a plurality of blocks of a video frame to determine whether inter compression or predictive intra compression results in better compression for the block; and selecting, for each of the plurality of blocks, the one of inter compression and predictive intra compression that results in better compression for the block; and encoding a first block of the plurality of blocks using predictive intra compression by: obtaining pixel values that are adjacent to the block, predicting pixel values for the block from the obtained adjacent pixel values, calculating a distance between the predicted pixel values and the actual pixel values for the block, creating a residual from the calculated distance, and encoding the residual.
Claim 49
Dependent Claim
28 words
A method as recited in claim 43 , further comprising: separating the video frame into a plurality of macroblocks; and separating the macroblocks into the plurality of blocks.
Claim 50
Dependent Claim
39 words
A method as recited in claim 43 , wherein inter compression comprises performing motion estimation of a second block in the plurality of blocks with a second block, having an identical spatial location, but in a different video frame.
Claim 51
Dependent Claim
38 words
A method as recited in claim 43 , wherein inter compression comprises performing motion estimation of a second block in the plurality of blocks with a second block having a different spatial location, in a different video frame.
Claim 52
Dependent Claim
143 words
A method as recited in claim 43 , further comprising encoding a second block of the plurality of blocks using inter compression by: searching for a corresponding block within a different video frame whose difference to the block is smaller than other blocks within the different video frame; calculating the difference between the block and the corresponding block; creating a second residual from the calculating the difference between the block and the corresponding block; creating a second residual from the calculating the difference between the second block and the corresponding block; creating a motion vector for the second residual corresponding to an offset between the corresponding block and another block in the different video frame having an identical spatial location to that of the second block in the plurality of blocks; and encoding the motion vector and the second residual using adaptive compression.
Claim 53
Dependent Claim
35 words
A method as recited in claim 47 , wherein if a corresponding block in the different video frame is not found, then encoding the second block in the plurality of blocks using predictive intra compression.
Claim 54
Dependent Claim
88 words
A method as recited in claim 43 , further comprising: receiving another video frame; determining whether a block of the other video frame was compressed using inter compression or intra compression; decompressing the block of the other video frame based on at least one additional video frame if the block of the other video frame was compressed using inter compression; and decompressing the block of the other video frame independent of any additional video frames if the block of the other video frame was compressed using intra compression.
Claim 55
Dependent Claim
21 words
A method as recited in claim 49 , wherein the video frame and the other video frame are the same frame.
References Cited (Backward Citations)
US5351095A
Cited
US5155594A
Cited
US5557341A
Cited
US5144425A
Cited
US5512952A
Cited
US5414469A
Cited
US5227878A
Cited
US5418568A
Cited
US5596659A
Cited
US5576767A
Cited
US5502492A
Cited
US5585852A
Cited
US5453801A
Cited
US5473379A
Cited
US5694173A
Cited
US5521988A
Cited
US5537155A
Cited
US5673265A
Cited
US5560038A
Cited
US5604867A
Cited
US5623312A
Cited
US5623313A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-05-26 | 2006-11-25 | 2007-05-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-05-26 | 2010-11-25 | 2011-05-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-05-26 | 2014-11-25 | 2015-05-27 | $7700.00 | Window Closed / Lapsed |