# US 2021/0344928 A1 · Codec > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0344928 A1 - Document ID: US20210344928A1 - Status: Published application - Kind: A1 - Application number: 17/378,464 - Filed: 2021-07-16 - Published: 2021-11-04 - Earliest claimed: 2017-01-04 - Assignees: Blackbird PLC - Applicants: Blackbird plc - Inventors: Stephen Streater - Web page: https://patentgrep.com/patent/US20210344928A1 ## CPC - H04N 19/137: Motion inside a coding unit, e.g. average field, frame or block difference - H04N 19/53: Multi-resolution motion estimation; Hierarchical motion estimation - H04N 19/119: Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks - H04N 19/159: Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction - H04N 19/172: the region being a picture, frame or field - H04N 19/513: Processing of motion vectors - H04N 19/521: {for estimating the reliability of the determined motion vectors or motion vector field, e.g. for smoothing the motion vector field or for correcting motion vectors} - H04N 19/86: involving reduction of coding artifacts, e.g. of blockiness - H04N 19/433: characterised by techniques for memory access - H04N 19/55: Motion estimation with spatial constraints, e.g. at image or region borders - H04N 19/56: Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract As may be implemented with one or more embodiments, a video stream is divided into a key frame and subsequent chunks of frames including a key frame and Delta (Dx) frames constructed from adjacent frames by dividing the frame into Motion Regions representing groups of pixels, determining a pixel group in an Earlier and later frame that is a best match for a pixel group in a Motion Region of a Current frame, and determining motion vectors for best matches for the Motion Regions and/or by intra-frame compression. A bitstream may be built such that as x increases, motion vector and other data relating to a combination of Dx frames is represented by data that is less than all the data in the combination of Dx frames and increases at a lower rate than the quantity of frames in Dx compared to the quantity of frames in Dx 1. ## Claims ### Claim 1 A computer-implemented method for encoding a video stream comprising: dividing the video stream into: a first Key frame, and subsequent chunks each comprising 2n frames, where n is an integer greater than one, each chunk including a Key frame and 2n−1 Delta (Dx) frames, where x is a positive integer from 1 to n, and denotes the level of the Delta frame, and where 2x−1 denotes the number of Delta frames at level x in the chunk; the method including the step of constructing Dx level frames from adjacent Earlier and Later Dy frames, where y0; wherein the constructing step includes: dividing the frame into Motion Regions representing groups of pixels; determining a pixel group in an Earlier (E) Dy frame and in a later (L) Dy frame that is a best match for a pixel group in a Motion Region of a Current (C) Dx frame; and determining motion vectors for the best matches for the Motion Regions, the method including building a bitstream wherein motion vector data is represented by a quantity of data in the bitstream, the method further comprising correcting inaccuracies by determining, for each neighborhood comprising a predetermined number of pixels, the difference in grey scale value of adjacent pixels in each direction, such that (i) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in three or four directions, no difference is permitted between predicted and actual pixel values, and any difference is corrected; (ii) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in 2 directions, a maximum value of difference is permitted between predicted and actual pixel values before a correction is applied, wherein said maximum can vary between 1 and 16 greyscales; and (iii) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in one or zero directions, a larger difference than in two directions is permitted before a correction is applied. ### Claim 2 (depends on 1) The method of claim 1, wherein the predetermined number of pixels is 2, 3, 4 or 5 pixels. ### Claim 3 (depends on 1) The method of claim 1, wherein during encoding, Key frame compression comprises intra-frame compression, wherein as x increases, information on Dx frames also includes inter-frame compression from respective Dy frames. ### Claim 4 (depends on 1) The method of claim 1, wherein determining said best match includes, for each frame: determining Small Frames derived from averaging pixels in respective frames, comparing groups of pixels in the Small Frames of said E Dy frame and said L Dy frame to establish candidate motion vectors to map onto Small Motion Regions of the Small C Dx Frame, wherein said comparing step includes: for each motion vector tested, comparing pixels, with the motion vector applied, in the Small Frames of the E Dy frame and of the L Dy frame, with the Small Motion Region in the Small C Dx Frame, iteratively, until a best match can be identified, iteratively for each Small Motion Region in the C Dx Frame. ### Claim 5 (depends on 4) The method of claim 4, wherein candidate motion vectors are established by searching: in concentric squares, or in a diamond pattern, until no better match is found for two or more consecutive searches. ### Claim 6 (depends on 4) The method of claim 4, wherein said best match is determined by: applying candidate motion vectors to pixels in candidate groups of pixels of said Small Frame version of the E Dy frame and the Small Frame version of the L Dy frame to predict pixel values in a Small Motion Region of said Small C Dx Frame; comparing said predicted values with actual pixel values in said Small Motion Region of said Small C Dx Frame; determining differences between said predicted and actual pixel values to establish an Error value; determining a Significance of each Error value, wherein the Significance is a function of the Error value and summing said Significances, wherein the respective best matches for the pixel groups in the Small Frame version of the E Dy frame and the pixel groups in the Small Frame version of the L Dy frame are the motion vectors which give the smallest sum of Significances. ### Claim 7 (depends on 6) The method according to claim 6, wherein the motion vectors are further refined by analyzing versions of the E Dy, C Dx and L Dy frames at increasing resolution until the motion vectors are pixel accurate. ### Claim 8 (depends on 4) The method of claim 4, wherein said best match is determined by: applying candidate motion vectors between groups of pixels in the E Dy frame and corresponding groups of pixels in the L Dy frame, to predict pixel values in a Motion Region of said C Dx frame, thereby avoiding sending motion vectors for said C Dx frame in the bitstream. ### Claim 9 (depends on 7) The method of claim 7, wherein said candidate motion vectors for groups of pixels in the E Dy frame to the Motion Region in the C Dx frame are equal to said candidate motion vectors from the Motion Region in the C Dx frame to the group of pixels in the L Dy frame. ### Claim 10 (depends on 6) The method of claim 6, wherein said Significance is an increasing function of the absolute value of the error, with a gradient that increases as the error approaches a predetermined maximum allowed error per pixel, and falls where the error exceeds a maximum allowed error per pixel. ### Claim 11 (depends on 6) The method of claim 6, wherein if the estimate for the Motion Region based on the E Dy frame and the L Dy frame has an error greater than a predetermined value, the respective predictor is not used, wherein as x increases within a chunk, the allowable error between predicted and actual Motion Region values is an increasing function of x. ### Claim 12 (depends on 1) The method of claim 1 further comprising: assigning differences between estimated and actual pixel values as 0, −1 or +1, where: 0 corresponds to a difference of approximately 0, −1 corresponds to a significant negative difference, and +1 corresponds to a significant positive difference, wherein a significant difference corresponds to a desired picture quality, where high values provide lower picture quality; re-assigning to zero each pixel whose sign is different to any adjacent pixel, deriving a value from the number of remaining positive or negative values at or near a Motion Region edge; rejecting the motion vector and corresponding predictive group of pixels from the E Dy frame or the L Dy frame for this Motion Region as a poor match if this value exceeds a threshold. ### Claim 13 (depends on 1) The method of claim 1, the method further including a method of decoding a video stream, wherein said Dx frames are encoded and decoded by referencing Transition Tables and Context; each Context code word giving its own distribution within its Transition Table. ### Claim 14 (depends on 1) The method of claim 1, wherein if one of the relevant groups of pixels from an E Dy frame or an L Dy frame touches the edge of its frame, and the other of the E Dy frame or the L Dy frame predictors suggests that the said predictor group of pixels on the edge should be off its screen and thus is Suspicious, then the E Dy frame or the L Dy frame group of pixels with the Suspicious component is excluded from the prediction of the Motion Region in the C Dx frame. ### Claim 15 (depends on 1) The method of claim 1, wherein respective Key and Delta frames from respective chunks are stored together such that Key frames are stored in a Key frame file, D1 frames are stored in a Delta 1 frame file, and so on until Dx frames, for the greatest value of x in the chunk, are stored in a Dx frame file. ### Claim 16 A non-transitory machine-readable medium having instructions that, when executed, cause a method for encoding a video stream to be performed, the method comprising: dividing the video stream into: a first Key frame, and subsequent chunks each comprising 2n frames, where n is an integer greater than one, each chunk including a Key frame and 2n−1 Delta (Dx) frames, where x is a positive integer from 1 to n, and denotes the level of the Delta frame, and where 2x−1 denotes the number of Delta frames at level x in the chunk; constructing Dx level frames from adjacent Earlier and Later Dy frames, where y0; wherein the constructing includes: dividing the frame into Motion Regions representing groups of pixels; determining a pixel group in an Earlier (E) Dy frame and in a later (L) Dy frame that is a best match for a pixel group in a Motion Region of a Current (C) Dx frame; determining motion vectors for the best matches for the Motion Regions; and building a bitstream wherein motion vector data is represented by a quantity of data in the bitstream, the method further comprising correcting inaccuracies by determining, for each neighborhood comprising a predetermined number of pixels, the difference in grey scale value of adjacent pixels in each direction, such that (i) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in three or four directions, no difference is permitted between predicted and actual pixel values, and any difference is corrected; (ii) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in 2 directions, a maximum value of difference is permitted between predicted and actual pixel values before a correction is applied, wherein said maximum can vary between 1 and 16 greyscales; and (iii) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in one or zero directions, a larger difference than in two directions is permitted before a correction is applied. ### Claim 17 (depends on 16) The non-transitory machine-readable medium of claim 16, the non-transitory machine-readable medium having instructions that, when executed, cause a method of decoding a video stream to be performed, wherein said Dx Delta frames are encoded and decoded by referencing Transition Tables and Context; each Context code word giving its own distribution within its Transition Table. ### Claim 18 A device including a camera, a processor and a non-transitory machine-readable medium having instructions that, when executed by the processor, encode a video stream captured by the camera, wherein the video stream is divided into: a first Key frame, and subsequent chunks each comprising 2n frames, where n is an integer greater than one, each chunk including a Key frame and 2n−1 Delta (Dx) frames, where x is a positive integer from 1 to n, and denotes the level of the Delta frame, and where 2x−1 denotes the number of Delta frames at level x in the chunk; the instructions, when executed by the processor, constructing Dx level frames from adjacent Earlier and Later Dy frames, where y0; wherein the constructing includes: dividing the frame into Motion Regions representing groups of pixels; determining a pixel group in an Earlier (E) Dy frame and in a later (L) Dy frame that is a best match for a pixel group in a Motion Region of a Current (C) Dx frame; determining motion vectors for the best matches for the Motion Regions; and building a bitstream, wherein motion vector data is represented by a quantity of data in the bitstream, the non-transitory machine-readable medium having instructions that, when executed by the processor, correct inaccuracies by determining, for each neighborhood comprising a predetermined number of pixels, the difference in grey scale value of adjacent pixels in each direction, such that (i) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in three or four directions, no difference is permitted between predicted and actual pixel values, and any difference is corrected; (ii) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in 2 directions, a maximum value of difference is permitted between predicted and actual pixel values before a correction is applied, wherein said maximum can vary between 1 and 16 greyscales; and (iii) if the difference is no greater than 1, or no greater than 2, or no greater than 3 grey scale values in one or zero directions, a larger difference than in two directions is permitted before a correction is applied. ### Claim 19 (depends on 18) The device of claim 18, wherein the instructions, when executed by the processor, decode a video stream, wherein said Dx Delta frames are encoded and decoded by referencing Transition Tables and Context; each Context code word giving its own distribution within its Transition Table. ### Claim 20 (depends on 18) The device of claim 18, wherein the device is a mobile phone or a personal computer. ### Claim 21 (depends on 19) The device of claim 19, wherein the device is a mobile phone or a personal computer.