Methods for encoding digital video for decoding on low performance devices

Abstract

A video encoder encodes the video stream frame by frame. An encoding process generally includes receiving a video frame, subdividing the video frame into uniform pixel blocks, comparing a selected pixel block with the corresponding pixel block in a previous decoded video frame to determine which blocks have changed, copying changed pixel blocks into a contiguous memory block, and adding a preamble block, compressing the blocks. This process may be repeated for each frame using a different size pixel block to determine and select a pixel block size that results in the smallest encoded frame.

1 - 24 . (canceled)  
   
   
       25 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding a video stream by: 
 receiving a current video frame of the video stream;    subdividing the current video frame into uniform blocks of a selected block size, and comparing the blocks to corresponding blocks of a decoded version of a preceding video frame to determine whether any of the blocks of the current video frame are sufficiently unchanged from the preceding frame to be discarded;    optionally repeating said subdividing or said comparing, or combinations thereof, using at least one additional block size, wherein the current video frame is capable of being separately subdivided or compared, or combinations thereof, to the preceding video frame using multiple block sizes;    selecting from the multiple block sizes a uniform block size that is capable of producing a relatively better video frame compression result; and    encoding the video frame in the video stream with the block size selected by said selecting.    
   
   
       26 . An article of manufacture as claimed in  claim 25 , wherein the instructions, if executed, further result in encoding different frames using different block sizes for multiple frames of the video stream.  
   
   
       27 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding a video stream by: 
 receiving a current video frame of the video stream;    determining which of multiple possible uniform block sizes produces a relatively better result for encoding the current video frame, wherein the uniform block sizes are used to subdivide or compare, or combinations thereof, the current video frame or a preceding video frame, or combinations thereof, to determine whether any blocks of the current video frame are sufficiently unchanged to be discarded;    compressing the current video frame using at least in part the block size determined to produce the relatively better result; and    storing the compressed video frame in conjunction with an indication of the block size.    
   
   
       28 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding video by: 
 dividing a video frame into blocks according to a uniform or nearly uniform block size;    identifying changed blocks by comparing one or more blocks to a corresponding block in a decoded version of a previous frame;    copying changed blocks into a contiguous or nearly contiguous block of memory; and    adding a preamble block.    
   
   
       29 . Article of manufacture as claimed in  claim 28 , the preamble block being capable of indicating one or more blocks that are included in the contiguous or nearly contiguous block of memory.  
   
   
       30 . Article of manufacture as claimed in  claim 28 , the preamble block being capable of indicating a block size used to encode the video frame.  
   
   
       31 . Article of manufacture as claimed in  claim 28 , the preamble block being capable of varying in size from frame to frame.  
   
   
       32 . Article of manufacture as claimed in  claim 28 , said identifying comprises determining a luminance difference from a corresponding block in an encoded version of the previous frame.  
   
   
       33 . Article of manufacture as claimed in  claim 28 , the luminance difference comprising a predefined threshold value.  
   
   
       34 . Article of manufacture as claimed in  claim 28 , wherein the instructions, if executed, further result in encoding video by compressing at least in part the contiguous or nearly contiguous memory block using an LZW type compression algorithm.  
   
   
       35 . Article of manufacture as claimed in  claim 28 , wherein the instructions, if executed, further result in encoding video by compressing at least in part the contiguous or nearly contiguous memory block using an LZW type compression process, the compression process comprising a zLIB type process.  
   
   
       36 . Article of manufacture as claimed in  claim 28 , wherein the instructions, if executed, further result in encoding video by compressing at least in part the contiguous or nearly contiguous memory block using an LZW type compression process, the compression process comprising an LZO type process.  
   
   
       37 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding video by: 
 encoding a video frame using a first uniform or nearly uniform block size to create a first encoded frame;    encoding the same or nearly the same video frame using a second uniform or nearly uniform block size to create a second encoded frame;    comparing a size of the first encoded frame to a size of the second encoded frame; and    selecting the uniform or nearly uniform block size that results in a smaller encoded frame.    
   
   
       38 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding a video stream by: 
 representing video frames wherein the video frames are encoded using multiple block sizes; and    representing preamble blocks including bitmaps of the encoded video frames or indicators indicating the block size used to encode the video frames in the video stream, or combinations thereof.    
   
   
       39 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in decoding a video stream by: 
 receiving a video frame encoded using multiple block size detection;    decompressing the received video frame;    determining a block size used to encode the video frame;    determining which blocks are present in the encoded video frame;    copying one or more blocks present in the encoded video frame into a display area; and    displaying the video frame.    
   
   
       40 . An article of manufacture as claimed in  claim 39 , wherein one or more key frames are utilized to decode a sequence of frames starting at a location other than a beginning of the sequence.  
   
   
       41 . An article of manufacture as claimed in  claim 39 , wherein one or more key frames are utilized to decode a sequence of frames starting at a location other than a beginning of the sequence, one or more of the key frames being utilized to seek forward or backward, or combinations thereof, within the sequence of frames.  
   
   
       42 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding a video stream by: 
 subdividing a current video frame into uniform or nearly uniform blocks of a selected size;    identifying one or more blocks of the current video frame that differ by at least a minimum extent from one or more corresponding blocks in a decoded version of a preceding video frame;    subdividing or comparing, or combinations thereof, wherein the current video frame is subdivided or compared, or combinations thereof, to the preceding video frame using a one or more block sizes; and    selecting from the multiple block sizes a block size that produces a relatively better video compression result.    
   
   
       43 . An article of manufacture as claimed in  claim 42 , wherein the instructions, if executed further result in encoding a video stream by encoding the video frame using one or more of the block sizes.  
   
   
       44 . An article of manufacture as claimed in  claim 43 , said selecting utilizing an output of said encoding.  
   
   
       45 . An article of manufacture as claimed in  claim 43 , wherein one or more of multiple frames of the video stream are utilized to generate an encoded video stream in which different frames are encoded using different block sizes.  
   
   
       46 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding a video frame by: 
 providing a decoded preceding video frame;    subdividing the video frame into one or more blocks, wherein at least one or more of the blocks comprises at least one pixel;    identifying the blocks of a current video frame that differ by at least a minimum extent from one or more corresponding blocks in a decoded preceding video frame;    creating a map of locations of the identified blocks identified by said identifying in the video frame;    arranging the map or the identified blocks, or combinations thereof, in a contiguous or nearly contiguous block of memory; and    compressing the data in the contiguous or nearly contiguous block of memory.    
   
   
       47 . A method for encoding video, comprising: 
 dividing one or more frames of video into one or more blocks according to a predetermined block size;    identifying changed blocks by comparing a block in a present frame to a corresponding block in an encoded version of a previous frame;    if the present frame is a key frame, identifying one or more blocks that were not identified by said identifying changed blocks as being changed blocks in the key frame;    copying one or more of the blocks identified as changed to a contiguous or nearly contiguous memory; and    compressing the contiguous or nearly contiguous memory.    
   
   
       48 . A method as claimed in  claim 47 , further comprising adding one or more preamble blocks to the contiguous or nearly contiguous memory, the preamble blocks being capable of identifying the blocks that are included in the contiguous or nearly contiguous memory.  
   
   
       49 . A method as claimed in  claim 47 , wherein an encoded key frame contains sufficient information to allow a full frame, or nearly a full frame, to be decoded by using the key frame and one or more preceding encoded frames.  
   
   
       50 . A method as claimed in  claim 47 , wherein an encoded key frame contains all, or nearly all, the pixels not encoded in one or more preceding frames.  
   
   
       51 . A method as claimed in  claim 47 , wherein a key frame is associated with one or more preceding frames.  
   
   
       52 . A method as claimed in  claim 47 , wherein a key frame is associated with one or more succeeding frames.  
   
   
       53 . An apparatus for encoding video, comprising: 
 means for dividing one or more frames of video into one or more blocks according to a predetermined block size;    means for identifying changed blocks by comparing a block in a present frame to a corresponding block in an encoded version of a previous frame;    means for identifying one or more blocks that were not identified by said means for identifying changed blocks as being changed blocks in the key frame if the present frame is a key frame;    means for copying one or more of the blocks identified as changed to a contiguous or nearly contiguous memory; and    means for compressing the contiguous or nearly contiguous memory.    
   
   
       54 . An apparatus as claimed in  claim 53 , further comprising means for adding one or more preamble blocks to the contiguous or nearly contiguous memory, the preamble blocks being capable of identifying the blocks that are included in the contiguous or nearly contiguous memory.  
   
   
       55 . An apparatus as claimed in  claim 53 , wherein an encoded key frame contains sufficient information to allow a full frame, or nearly a full frame, to be decoded by using the key frame and one or more preceding encoded frames.  
   
   
       56 . An apparatus as claimed in  claim 53 , wherein an encoded key frame contains all, or nearly all, the pixels not encoded in one or more preceding frames.  
   
   
       57 . An apparatus as claimed in  claim 53 , wherein a key frame is associated with one or more preceding frames.  
   
   
       58 . An apparatus as claimed in  claim 53 , wherein a key frame is associated with one or more succeeding frames.  
   
   
       59 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in encoding video by: 
 dividing one or more frames of video into one or more blocks according to a predetermined block size;    identifying changed blocks by comparing a block in a present frame to a corresponding block in an encoded version of a previous frame;    if the present frame is a key frame, identifying one or more blocks that were not identified by said identifying changed blocks as being changed blocks in the key frame;    copying one or more of the blocks identified as changed to a contiguous or nearly contiguous memory; and    compressing the contiguous or nearly contiguous memory.    
   
   
       60 . An article of manufacture as claimed in  claim 59 , wherein the instructions, if executer, further result in encoding video by adding one or more preamble blocks to the contiguous or nearly contiguous memory, the preamble blocks being capable of identifying the blocks that are included in the contiguous or nearly contiguous memory.  
   
   
       61 . An article of manufacture as claimed in  claim 59 , wherein an encoded key frame contains sufficient information to allow a full frame, or nearly a full frame, to be decoded by using the key frame and one or more preceding encoded frames.  
   
   
       62 . An article of manufacture as claimed in  claim 59 , wherein an encoded key frame contains all, or nearly all, the pixels not encoded in one or more preceding frames.  
   
   
       63 . An article of manufacture as claimed in  claim 59 , wherein a key frame is associated with one or more preceding frames.  
   
   
       64 . An article of manufacture as claimed in  claim 59 , wherein a key frame is associated with one or more succeeding frames.  
   
   
       65 . A method for decoding video, comprising: 
 decoding one or more frames associated with a key frame and inserting the data of the one or more decoded frames into a working frame; and    decoding the key frame and inserting the data of the decoded key frame into the working frame.    
   
   
       66 . A method as claimed in  claim 65 , wherein said decoding one or more frames associated with the key frame occurs prior to said decoding of the key frame.  
   
   
       67 . A method as claimed in  claim 65 , wherein said decoding one or more frames associated with the key frame occurs after said decoding of the key frame.  
   
   
       68 . An apparatus for decoding video, comprising: 
 means for decoding one or more frames associated with a key frame and inserting the data of the one or more decoded frames into a working frame;    means for decoding the key frame and inserting the data of the decoded key frame into the working frame.    
   
   
       69 . A method as claimed in  claim 68 , wherein said means for decoding one or more frames associated with the key frame decodes the one or more frames prior to said means for decoding the key frame decodes the key frame.  
   
   
       70 . A method as claimed in  claim 68 , wherein said means for decoding one or more frames associated with the key frame decodes the one or more frames after said means for decoding the key frame decodes the key frame.  
   
   
       71 . An article of manufacture comprising a storage medium having instructions stored thereon that, if executed, result in decoding video by: 
 decoding one or more frames associated with a key frame and inserting the data of the one or more decoded frames into a working frame; and    decoding the key frame and inserting the data of the decoded key frame into the working frame.    
   
   
       72 . An article of manufacture as claimed in  claim 71 , wherein said decoding one or more frames associated with the key frame occurs prior to said decoding of the key frame.  
   
   
       73 . An article of manufacture as claimed in  claim 71 , wherein said decoding one or more frames associated with the key frame occurs after said decoding of the key frame.