# US 10,484,721 B2 · Method for motion estimation of non-natural video data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,484,721 B2
- Document ID: US10484721B2
- Status: Granted
- Kind: B2
- Application number: 14/659,122
- Filed: 2015-03-16
- Published: 2015-09-17
- Granted: 2019-11-19
- Earliest claimed: 2014-03-17
- Assignees: QUALCOMM Incorporated
- Applicants: QUALCOMM Incorporated
- Inventors: Krishnakanth Rapaka; Joel Sole Rojals; Li Zhang; Marta Karczewicz
- Web page: https://patentgrep.com/patent/US10484721B2

## CPC

- H04N 19/96: Tree coding, e.g. quad-tree coding
- H04N 19/198: {including smoothing of a sequence of encoding parameters, e.g. by averaging, by choice of the maximum, minimum or median value}
- H04N 19/52: by predictive encoding
- H04N 19/53: Multi-resolution motion estimation; Hierarchical motion estimation
- 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
- H04N 19/56: Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
- H04N 19/57: Motion estimation characterised by a search window with variable size or shape
- H04N 19/567: Motion estimation based on rate distortion criteria
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method for motion estimation for screen and non-natural content coding is disclosed. In one aspect, the method may include selecting a candidate block of a first frame of the video data for matching with a current block of a second frame of the video data, calculating a first partial matching cost for matching a first subset of samples of the candidate block to the current block, and determining whether the candidate block has a lowest matching cost with the current block based at least in part on the first partial matching cost.

## Claims

### Claim 1

A method for motion estimation of non-natural video data, the method comprising:
determining whether to skip motion estimation based only on a residual of a merge motion vector; and
responsive to determining not to skip motion estimation:
selecting a candidate block of a first frame of the non-natural video data for matching to a current block of a second frame of the non-natural video data, the candidate block being selected from a first diamond pattern surrounding a previous candidate block of the first frame of the non-natural video data, wherein the non-natural video data comprises computer-generated video data not captured through a camera having an optical system;
obtaining a previously calculated lowest matching difference value based on matching the previous candidate block of the first frame of the non-natural video data to the current block of the second frame of the non-natural video data;
calculating a first partial matching difference value of matching a first subset of samples of the candidate block to the current block;
estimating, based on the first partial matching difference value, a total matching difference value of matching the candidate block to the current block;
comparing the estimated total matching difference value of the candidate block to the lowest matching difference value of the previous candidate block;
determining, based on the comparison, whether the candidate block does not have a lowest matching difference value to the current block; and
selecting, in response to the candidate block not having the lowest matching difference value to the current block, a subsequent candidate block of the first frame of the non-natural video data for matching to the current block from a second diamond pattern that is at least one of horizontally or vertically displaced from the first diamond pattern.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
calculating an estimate of a matching difference value for matching the remaining samples of the candidate block to the current block based on the first partial matching difference value,
wherein the estimated total matching difference value is further based on the estimate of the matching difference value for matching the remaining samples.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
calculating a second partial difference value for matching a second subset of the samples of the candidate block to the current block;
updating the remaining samples of the candidate block by removing the second subset of samples of the candidate block;
refining the estimate of the matching difference value for matching the remaining samples via calculating a refined estimate for matching the updated remaining samples of the candidate block to the current block;
refining the estimated total matching difference value via summing the first partial difference value, the second partial difference value, and the refined estimate; and
determining whether the candidate block has the lowest matching difference value to the current block based at least in part on the refined estimated total matching difference value.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
selecting a previous candidate block of the first frame of the non-natural video data for matching to the current block;
calculating a previous total matching difference value for matching the previous candidate block to the current block;
determining that the candidate block does not have the lowest matching difference value to the current block when the refined estimated total matching difference value is greater than the previous total matching difference value; and
determining that the candidate block has the lowest matching difference value to the current block when the refined estimated total matching difference value is less than the previous total matching difference value.

### Claim 5 (depends on 2)

The method of claim 2, further comprising calculating a motion vector bit value for matching the candidate block to the current block, wherein the estimating the total matching difference value further comprises summing the first partial difference value, the estimate of the matching difference value for matching the remaining samples, and the motion vector bit value.

### Claim 6 (depends on 1)

The method of claim 1, further comprising performing a modified initial search, wherein the first and second diamond patterns are located within an initial search area that is a sub-portion of an entire search area.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
determining a first distance between the candidate having the lowest matching difference value and the current block;
determining a second distance between a predictor and the current block; and
determining whether to perform a refinement search or a full search with error approximation based on the difference between the first and second distances.

### Claim 8

A device for motion estimation of non-natural video data, the device comprising:
a memory configured to store the non-natural video data, the non-natural video data comprising video data not captured through a camera having an optical system; and
a processor in communication with the memory and configured to:
determine whether to skip motion estimation based only on a residual of a merge motion vector; and
responsive to determining not to skip motion estimation:
select, from a first diamond pattern surrounding a previous candidate block of a first frame of the non-natural video data, a candidate block of the first frame of the non-natural video data for matching to a current block of a second frame of the non-natural video data;
obtain a previously calculated lowest matching difference value based on matching the previous candidate block of the first frame of the non-natural video data to the current block of the second frame of the non-natural video data;
calculate a first partial matching difference value of matching a first subset of samples of the candidate block to the current block;
estimate, based on the first partial matching difference value, a total matching difference value of matching the candidate block to the current block;
compare the estimated total matching difference value of the candidate block to the lowest matching difference value of the previous candidate block;
determine whether the candidate block does not have a lowest matching difference value to the current block based on the comparison; and
select, in response to the candidate block not having the lowest matching difference value to the current block and from a second diamond pattern that is at least one of horizontally or vertically displaced from the first diamond pattern, a subsequent candidate block of the first frame of the non-natural video data for matching to the current block.

### Claim 9 (depends on 8)

The device of claim 8, wherein the processor is further configured to:
calculate an estimate of a matching difference value for matching the remaining samples of the candidate block to the current block,
wherein estimating the total matching difference value is further based on the estimate of the matching difference value for matching the remaining samples.

### Claim 10 (depends on 9)

The device of claim 9, wherein the processor is further configured to:
calculate a second partial difference value for matching a second subset of the samples of the candidate block to the current block;
update the remaining samples of the candidate block by removing the second subset of samples of the candidate block;
refine the estimate of the matching difference value for matching the remaining samples via calculating a refined estimate for matching the updated remaining samples of the candidate block to the current block;
refine the estimated total matching difference value via summing the first partial difference value, the second partial difference value, and the refined estimate; and
determine whether the candidate block has the lowest matching difference value to the current block based at least in part on the refined estimated total matching difference value.

### Claim 11 (depends on 10)

The device of claim 10, wherein the processor is further configured to:
select a previous candidate block of the first frame of the non-natural video data for matching to the current block;
calculate a previous total matching difference value for matching the previous candidate block to the current block;
determine that the candidate block does not have the lowest matching difference value to the current block when the refined estimated total matching difference value is greater than the previous total matching difference value; and
determine that the candidate block has the lowest matching difference value to the current block when the refined estimated total matching difference value is less than the previous total matching difference value.

### Claim 12 (depends on 9)

The device of claim 9, wherein the processor is further configured to:
calculate a motion vector bit value for matching the candidate block to the current block,
estimate the total matching difference value via summing the first partial difference value, the estimate of the matching difference value for matching the remaining samples, and the motion vector bit value.

### Claim 13 (depends on 8)

The device of claim 8, wherein the processor is further configured to perform a modified initial search, wherein the first and second diamond patterns are located within an initial search area that is a sub-portion of an entire search area.

### Claim 14

An apparatus for motion estimation of non-natural video data, comprising:
means for determining whether to skip motion estimation based only on a residual of a merge motion vector;
means for selecting, from a first diamond pattern surrounding a previous candidate block of a first frame of the non-natural video data, a candidate block of the first frame of the non-natural video data for matching to a current block of a second frame of the non-natural video data, wherein the non-natural video data comprises video data not captured through a camera having an optical system;
means for obtaining a previously calculated lowest matching difference value based on matching the previous candidate block of the first frame of the non-natural video data to the current block of the second frame of the non-natural video data;
means for calculating a first partial matching difference value for matching a first subset of samples of the candidate block to the current block;
means for estimating, based on the first partial matching difference value, a total matching difference value of matching the candidate block to the current block;
means for comparing the estimated total matching difference value of the candidate block to the lowest matching difference value of the previous candidate block;
means for determining whether the candidate block does not have a lowest matching difference value to the current block based on the comparison; and
means for selecting, in response to the candidate block not having the lowest matching difference value to the current block and from a second diamond pattern that is at least one of horizontally or vertically displaced from the first diamond pattern, a subsequent candidate block of the first frame of the non-natural video data for matching to the current block.

### Claim 15 (depends on 14)

The apparatus of claim 14, further comprising:
means for calculating an estimate of a matching difference value for matching the remaining samples of the candidate block to the current block,
wherein estimating the total matching difference value is further based on the estimate of the matching difference value for matching the remaining samples.

### Claim 16 (depends on 15)

The apparatus of claim 15, further comprising:
means for calculating a second partial difference value for matching a second subset of the samples of the candidate block to the current block;
means for updating the remaining samples of the candidate block by removing the second subset of samples of the candidate block;
means for refining the estimate of the matching difference value for matching the remaining samples via calculating a refined estimate for matching the updated remaining samples of the candidate block to the current block;
means for refining the estimated total matching difference value via summing the first partial difference value, the second partial difference value, and the refined estimate; and
means for determining whether the candidate block has the lowest matching difference value to the current block based at least in part on the refined estimated total matching difference value.

### Claim 17 (depends on 16)

The apparatus of claim 16, further comprising:
means for selecting a previous candidate block of the first frame of the non-natural video data for matching to the current block;
means for calculating a previous total matching difference value for matching the previous candidate block to the current block;
means for determining that the candidate block does not have the lowest matching difference value to the current block when the refined estimated total matching difference value is greater than the previous total matching difference value; and
means for determining that the candidate block has the lowest matching difference value to the current block when the refined estimated total matching difference value is less than the previous total matching difference value.

### Claim 18 (depends on 15)

The apparatus of claim 15, further comprising means for calculating a motion vector bit value for matching the candidate block to the current block, wherein the means for estimating the total matching difference value further comprises means for summing the first partial difference value, the estimate of the matching difference value for matching the remaining samples, and the motion vector bit value.

### Claim 19 (depends on 14)

The apparatus of claim 14, further comprising means for performing a modified initial search, wherein the first and second diamond patterns are located within an initial search area that is a sub-portion of an entire search area.

### Claim 20

A non-transitory computer readable storage medium having stored thereon instructions that, when executed, cause a processor of a device configured for motion estimation of non-natural video data to:
determine whether to skip motion estimation based only on a residual of a merge motion vector;
select, from a first diamond pattern surrounding a previous candidate block of a first frame of the non-natural video data, a candidate block of the first frame of the non-natural video data for matching to a current block of a second frame of the non-natural video data, wherein the non-natural video data comprises video data not captured through a camera having an optical system;
obtain a previously calculated lowest matching difference value based on matching the previous candidate block of the first frame of the non-natural video data to the current block of the second frame of the non-natural video data;
calculate a first partial matching difference value for matching a first subset of samples of the candidate block to the current block;
estimate, based on the first partial matching difference value, a total matching difference value of matching the candidate block to the current block;
compare the estimated total matching difference value of the candidate block to the lowest matching difference value of the previous candidate block;
determine whether the candidate block does not have a lowest matching difference value to the current block based on the comparison; and
in response to the candidate block not having the lowest matching difference value to the current block, select, from a second diamond pattern that is at least one of horizontally or vertically displaced from the first diamond pattern, a subsequent candidate block of the first frame of the non-natural video data for matching to the current block.

### Claim 21 (depends on 20)

The non-transitory computer readable storage medium of claim 20, further having stored thereon instructions that, when executed, cause the processor to:
calculate an estimate of a matching difference value for matching the remaining samples of the candidate block to the current block,
wherein estimating the total matching difference value is further based on the estimate of the matching difference value for matching the remaining samples.

### Claim 22 (depends on 21)

The non-transitory computer readable storage medium of claim 21, further having stored thereon instructions that, when executed, cause the processor to:
calculate a second partial difference value for matching a second subset of the samples of the candidate block to the current block;
update the remaining samples of the candidate block by removing the second subset of samples of the candidate block;
refine the estimate of the matching difference value for matching the remaining samples via calculating a refined estimate for matching the updated remaining samples of the candidate block to the current block;
refine the estimated total matching difference value via summing the first partial difference value, the second partial difference value, and the refined estimate; and
determine whether the candidate block has the lowest matching difference value to the current block based at least in part on the refined estimated total matching difference value.

### Claim 23 (depends on 22)

The non-transitory computer readable storage medium of claim 22, further having stored thereon instructions that, when executed, cause the processor to:
select a previous candidate block of the first frame of the non-natural video data for matching to the current block;
calculate a previous total matching difference value for matching the previous candidate block to the current block;
determine that the candidate block does not have the lowest matching difference value to the current block when the refined estimated total matching difference value is greater than the previous total matching difference value; and
determine that the candidate block has the lowest matching difference value to the current block when the refined estimated total matching difference value is less than the previous total matching difference value.

### Claim 24 (depends on 21)

The non-transitory computer readable storage medium of claim 21, further having stored thereon instructions that, when executed, cause the processor to:
calculate a motion vector bit value for matching the candidate block to the current block, estimate the total matching difference value via summing the first partial difference value, the estimate of the matching difference value for matching the remaining samples, and the motion vector bit value.

### Claim 25 (depends on 20)

The non-transitory computer readable storage medium of claim 20, further having stored thereon instructions that, when executed, cause the processor to perform a modified initial search, wherein the first and second diamond patterns are located within an initial search area that is a sub-portion of an entire search area.

### Claim 26 (depends on 1)

The method of claim 1, wherein the second diamond pattern and the first diamond pattern are the same size.

### Claim 27 (depends on 26)

The method of claim 26, wherein the second diamond pattern is displaced from the first diamond pattern with a step size of four.

### Claim 28 (depends on 8)

The device of claim 8, wherein the second diamond pattern and the first diamond pattern are the same size.

### Claim 29 (depends on 28)

The device of claim 28, wherein the second diamond pattern is displaced from the first diamond pattern with a step size of four.

### Claim 30

A device for motion estimation of non-natural video data, the device comprising:
a memory configured to store the non-natural video data, the non-natural video data comprising video data not captured through a camera having an optical system; and
a processor in communication with the memory and configured to:
select, from a first diamond pattern surrounding a previous candidate block of a first frame of the non-natural video data, a candidate block of the first frame of the non-natural video data for matching to a current block of a second frame of the non-natural video data;
obtain a previously calculated lowest matching difference value based on matching the previous candidate block of the first frame of the non-natural video data to the current block of the second frame of the non-natural video data;
calculate a first partial matching difference value of matching a first subset of samples of the candidate block to the current block;
estimate, based on the first partial matching difference value, a total matching difference value of matching the candidate block to the current block;
compare the estimated total matching difference value of the candidate block to the lowest matching difference value of the previous candidate block;
determine whether the candidate block does not have a lowest matching difference value to the current block based on the comparison;
select, in response to the candidate block not having the lowest matching difference value to the current block and from a second diamond pattern that is at least one of horizontally or vertically displaced from the first diamond pattern, a subsequent candidate block of the first frame of the non-natural video data for matching to the current block;
determine a first distance between the candidate having the lowest matching difference value and the current block;
determine a second distance between a predictor and the current block; and
determine whether to perform a refinement search or a full search with error approximation based on the difference between the first and second distances.