# US 10,123,036 B2 · Motion vector selection for video encoding > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,123,036 B2 - Document ID: US10123036B2 - Status: Granted - Kind: B2 - Application number: 14/318,105 - Filed: 2014-06-27 - Published: 2015-12-31 - Granted: 2018-11-06 - Earliest claimed: 2014-06-27 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Zahid Hussain; George Easton Scott, III; Shankar Narayan - Web page: https://patentgrep.com/patent/US10123036B2 ## CPC - H04N 19/52: by predictive encoding - 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 - H04N 19/139: Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability - H04N 19/176: the region being a block, e.g. a macroblock - H04N 19/19: using optimisation based on Lagrange multipliers - H04N 19/194: involving only two passes - H04N 19/43: Hardware specially adapted for motion estimation or compensation - H04N 19/436: using parallelised computational arrangements - H04N 19/56: Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search - H04N 19/567: Motion estimation based on rate distortion criteria - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract Various embodiments relating to selecting a motion vector in a hardware encoder are disclosed. In one example, a plurality of candidate predicted motion vectors are selected, and a plurality of motion searches are performed in an image region surrounding each candidate predicted motion vector to produce a plurality of resulting motion vectors, wherein each resulting motion vector has an initial cost score determined using a corresponding candidate predicted motion vector. After an actual predicted motion vector becomes available, the initial cost score of each resulting motion vector is re-scored using the actual predicted motion vector to produce an updated cost score, and video data is encoded using a motion vector selected from the plurality of resulting motion vectors based on the updated cost score of that motion vector. ## Claims ### Claim 1 A computing device comprising: a hardware pipelined video encoder configured to: select a plurality of candidate predicted motion vectors associated with video data to be encoded, perform a plurality of motion searches in an image region surrounding each candidate predicted motion vector to produce a plurality of resulting motion vectors, each resulting motion vector having an initial cost score determined using a corresponding candidate predicted motion vector, after an actual predicted motion vector, which was previously unavailable when the plurality of candidate predicted motion vectors were selected for the plurality of motion searches, becomes available due to completion of encoding of a block that includes the actual predicted motion vector, re-scoring the cost score of each resulting motion vector of the plurality of resulting motion vectors to determine an updated cost score for each resulting motion vector by using the actual predicted motion vector, and encode the video data using a motion vector selected from the plurality of resulting motion vectors based on the updated cost score. ### Claim 2 (depends on 1) The computing device of claim 1, wherein the initial cost score of a resulting motion vector is determined by using the corresponding candidate predicted motion vector in a rate-distortion function. ### Claim 3 (depends on 1) The computing device of claim 1, wherein the updated cost score of a resulting motion vector is determined by using the actual candidate predicted motion vector in the rate-distortion function. ### Claim 4 (depends on 1) The computing device of claim 1 wherein the hardware pipelined video encoder is further configured to select from the plurality of resulting motion vectors a subset of motion vectors having a lowest initial cost score as filtered motion vectors; after the actual predicted motion vector becomes available, re-score the initial cost score of each filtered motion vector in the subset using the actual predicted motion vector to produce the updated cost score; and encode the video data using a motion vector selected from the subset of filtered motion vectors based on the updated cost score of that filtered motion vector. ### Claim 5 (depends on 1) The computing device of claim 1, wherein two or more of the plurality of motion searches includes different search patterns. ### Claim 6 (depends on 1) The computing device of claim 1, wherein two or more of the plurality of motion searches includes different search regions. ### Claim 7 (depends on 1) The computing device of claim 1, wherein the plurality of candidate predicted motion vectors include one or more of a neighboring block of a same image frame, a same block of a temporally different image frame, a neighboring block of a temporally different image frame, and a zero motion vector. ### Claim 8 (depends on 1) The computing device of claim 1, wherein the hardware pipelined video encoder is further configured to: encode the video data using a reference index selected based on the motion vector having the lowest updated cost score. ### Claim 9 (depends on 1) The computing device of claim 1, further comprising: encode the video data using a block partition selected based on the motion vector having the lowest updated cost score. ### Claim 10 A storage machine holding instructions executable by a logic machine to: select a plurality of candidate predicted motion vectors associated with video data to be encoded; perform a plurality of motion searches in an image region surrounding each candidate predicted motion vector to produce a plurality of resulting motion vectors, each resulting motion vector having an initial cost score determined using a corresponding candidate predicted motion vector in a rate-distortion function; after an actual predicted motion vector, which was previously unavailable when the plurality of candidate predicted motion vectors were selected for the plurality of motion searches, becomes available due to completion of encoding of a block that includes the actual predicted motion vector, re-score the cost score of each resulting motion vector of the plurality of resulting motion vectors to determine an updated cost score for each resulting motion vector by using the actual predicted motion vector in the rate-distortion function calculation; and encode the video data using a motion vector selected from the plurality of resulting motion vectors based on the updated cost score. ### Claim 11 (depends on 10) The storage machine of claim 10, further holding instructions executable by the logic machine to: select from the plurality of resulting motion vectors a subset of motion vectors having a lowest initial cost score as filtered motion vectors; after the actual predicted motion vector becomes available, re-score the initial cost score of each filtered motion vector in the subset using the actual predicted motion vector to produce the updated cost score; and encode the video data using a motion vector selected from the subset of filtered motion vectors based on the updated cost score of that filtered motion vector. ### Claim 12 (depends on 10) The storage machine of claim 10, wherein two or more of the plurality of motion searches includes different search patterns, and wherein two or more of the plurality of motion search includes different search regions. ### Claim 13 (depends on 10) The storage machine of claim 10, wherein the plurality of candidate predicted motion vectors include one or more of a neighboring block of a same image frame, a same block of a temporally different image frame, a neighboring block of a temporally different image frame, and a zero motion vector. ### Claim 14 (depends on 10) The storage machine of claim 10, further holding instructions executable by the logic machine to: encode the video data using a reference index selected based on the motion vector having the lowest updated cost score; and encode the video data using a block partition selected based on the motion vector having the lowest updated cost score. ### Claim 15 On a computing device, a method for encoding a block of an image frame using a hardware pipelined video encoder, the method comprising: selecting a plurality of candidate predicted motion vectors; performing a plurality of motion searches in an image region surrounding each candidate predicted motion vector to produce a plurality of resulting motion vectors, each resulting motion vector having an initial cost score determined using a corresponding candidate predicted motion vector; selecting from the plurality of resulting motion vectors a subset of motion vectors having a lowest initial cost score as filtered motion vectors; after the actual predicted motion vector, which was previously unavailable when the plurality of candidate predicted motion vectors were selected for the plurality of motion searches, becomes available due to completion of encoding of a block that includes the actual predicted motion vector, re-scoring the cost score of each filtered motion vector to determine an updated cost score for each filtered motion vector in the subset by using the actual predicted motion vector; and encoding the block using a filtered motion vector selected from the filtered motion vectors of the subset based on the updated cost score. ### Claim 16 (depends on 15) The method of claim 15, wherein the plurality of candidate predicted motion vectors include one or more of a neighboring block of a same image frame, a same block of a temporally different image frame, a neighboring block of a temporally different image frame, and a zero motion vector. ### Claim 17 (depends on 1) The computing device of claim 1, wherein the plurality of candidate predicted motion vectors are selected from different, previously encoded blocks. ### Claim 18 (depends on 1) The computing device of claim 1, wherein each resulting motion vector has an initial cost score determined using a different candidate predicted motion vector in a cost score calculation, and wherein the updated cost score is determined for each resulting motion vector by using the actual predicted motion vector in place of the corresponding candidate predicted motion vector in the cost score calculation. ### Claim 19 (depends on 10) The storage machine of claim 10, wherein each resulting motion vector has an initial cost score determined using a different candidate predicted motion vector in the rate-distortion function, and wherein the updated cost score is determined for each resulting motion vector by using the actual predicted motion vector in place of the corresponding candidate predicted motion vector in the rate-distortion function. ### Claim 20 (depends on 15) The method of claim 15, wherein each resulting motion vector has an initial cost score determined using a different candidate predicted motion vector in a cost score calculation, and wherein the updated cost score is determined for each filtered motion vector by using the actual predicted motion vector in place of the corresponding candidate predicted motion vector in the cost score calculation.