# US 11,909,993 B1 · Fractional motion estimation engine with parallel code unit pipelines > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,909,993 B1 - Document ID: US11909993B1 - Status: Granted - Kind: B1 - Application number: 17/390,749 - Filed: 2021-07-30 - Granted: 2024-02-20 - Earliest claimed: 2021-07-30 - Assignees: Meta Platforms, Inc. - Applicants: Meta Platforms, Inc. - Inventors: Kameswara Kishore Sriadibhatla; Yunqing Chen; Junqiang Lan; Adrian Stafford Lewis; Anil Muthiraparampil Sunil - Web page: https://patentgrep.com/patent/US11909993B1 ## CPC - H04N 19/436: using parallelised computational arrangements - H04N 19/119: Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks - H04N 19/43: Hardware specially adapted for motion estimation or compensation - H04N 19/52: by predictive encoding - H04N 19/523: with sub-pixel accuracy - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract A video encoder is disclosed. The video encoder comprises an integer level motion estimation hardware component configured to determine candidate integer level motion vectors for a video being encoded. The video encoder comprises a fractional motion estimation hardware component configured to receive the candidate integer level motion vectors from the integer level motion estimation hardware component and refine the candidate integer level motion vectors into candidate sub-pixel level motion vectors. The fractional motion estimation hardware component includes parallel pipelines configured to process coding units of a frame of the video in parallel across the parallel pipelines. ## Claims ### Claim 1 A system, comprising: an integer level motion estimation hardware component configured to determine candidate integer level motion vectors for a video being encoded; and a fractional motion estimation hardware component configured to: receive the candidate integer level motion vectors from the integer level motion estimation hardware component; divide the candidate integer level motion vectors from the integer level motion estimation hardware component into a plurality of groups, wherein each group of the plurality of groups corresponds to a different single row of coding units of the frame of the video; and process a group of the plurality of groups by one of a plurality of parallel row pipelines, wherein a parallel row pipeline is configured to process in parallel with other parallel row pipelines a different single row of coding units of the frame of the video, and wherein the plurality of parallel pipelines refine the candidate integer level motion vectors into candidate sub-pixel level motion vectors. ### Claim 2 (depends on 1) The system of claim 1, wherein the fractional motion estimation hardware component is further configured to compute a fractional motion vector and send the fractional motion vector to an inter prediction module of a mode decision module. ### Claim 3 (depends on 1) The system of claim 1, wherein a coding unit of the frame of the video comprises a largest coding unit that may be divided into smaller prediction units. ### Claim 4 (depends on 1) The system of claim 1, wherein in the event of data dependencies in processing the coding units across different rows of coding units of the frame of the video, the processing of a certain coding unit in a particular row and column is performed after the processing of another coding unit in a previous row and a particular column is finished by a different parallel pipeline. ### Claim 5 (depends on 1) The system of claim 1, wherein a parallel pipeline comprises parallel partition unit pipelines, and wherein a partition unit pipeline is configured to process in parallel with the other partition unit pipelines different partition units, and wherein the partition unit pipeline is configured to process a different set of partition units. ### Claim 6 (depends on 5) The system of claim 5, wherein a first parallel partition unit pipeline is configured to process partition units with the smallest partition unit shapes, and wherein a second parallel partition unit pipeline is configured to process partition units with the remaining larger partition unit shapes. ### Claim 7 (depends on 5) The system of claim 5, wherein a parallel partition unit pipeline comprises pipelined half pixel interpolation, quarter pixel interpolation, and one-eighth pixel interpolation for refining the candidate integer level motion vectors into the candidate sub-pixel level motion vectors. ### Claim 8 (depends on 7) The system of claim 7, wherein nine positions are searched in a half-pixel refinement, and wherein nine positions are searched in a quarter-pixel refinement, and wherein nine positions are searched in a one-eighth-pixel refinement. ### Claim 9 (depends on 8) The system of claim 8, wherein the half-pixel refinement comprises searching one integer-pixel search center pointed to by an integer motion vector and eight half-pixel positions in half pixel interpolation, and wherein the quarter-pixel refinement comprises searching one half-pixel position and eight quarter-pixel positions in quarter pixel interpolation, and wherein the one-eighth-pixel refinement comprises searching one quarter-pixel position and eight one-eighth-pixel positions in one-eighth pixel interpolation. ### Claim 10 A system, comprising: a processor configured to: determine candidate integer level motion vectors for a video being encoded; divide the candidate integer level motion vectors into a plurality of groups, wherein each group of the plurality of groups corresponds to a different single row of coding units of the frame of the video; and process a group of the plurality of groups by one of a plurality of parallel row pipelines, wherein a parallel row pipeline is configured to process in parallel with other parallel row pipelines a different single row of coding units of the frame of the video, and wherein the plurality of parallel pipelines refine the candidate integer level motion vectors into candidate sub-pixel level motion vectors; and a memory coupled to the processor and configured to provide the processor with instructions. ### Claim 11 A method of encoding a video, comprising: determining candidate integer level motion vectors for the video being encoded; and dividing the candidate integer level motion vectors into a plurality of groups, wherein each group of the plurality of groups corresponds to a different single row of coding units of the frame of the video; and processing a group of the plurality of groups by one of a plurality of parallel row pipelines, wherein a parallel row pipeline is configured to process in parallel with other parallel row pipelines a different single row of coding units of the frame of the video, and wherein the plurality of parallel pipelines refine the candidate integer level motion vectors into candidate sub-pixel level motion vectors. ### Claim 12 (depends on 11) The method of claim 11, further comprising computing a fractional motion vector and sending the fractional motion vector to an inter prediction module of a mode decision module. ### Claim 13 (depends on 11) The method of claim 11, wherein a coding unit of the frame of the video comprises a largest coding unit that may be divided into smaller prediction units. ### Claim 14 (depends on 11) The method of claim 11, wherein in the event of data dependencies in processing the coding units across different rows of coding units of the frame of the video, processing a certain coding unit in a particular row and column after the processing of another coding unit in a previous row and a particular column is finished by a different parallel pipeline. ### Claim 15 (depends on 11) The method of claim 11, wherein a parallel pipeline comprises parallel partition unit pipelines, and wherein a partition unit pipeline is configured to process in parallel with the other partition unit pipelines different partition units, and wherein the partition unit pipeline is configured to process a different set of partition units. ### Claim 16 (depends on 15) The method of claim 15, wherein a first parallel partition unit pipeline is configured to process partition units with the smallest partition unit shapes, and wherein a second parallel partition unit pipeline is configured to process partition units with the remaining larger partition unit shapes. ### Claim 17 (depends on 15) The method of claim 15, wherein a parallel partition unit pipeline comprises pipelined half pixel interpolation, quarter pixel interpolation, and one-eighth pixel interpolation for refining the candidate integer level motion vectors into the candidate sub-pixel level motion vectors. ### Claim 18 (depends on 17) The method of claim 17, wherein nine positions are searched in a half-pixel refinement, and wherein nine positions are searched in a quarter-pixel refinement, and wherein nine positions are searched in a one-eighth-pixel refinement. ### Claim 19 (depends on 18) The method of claim 18, wherein the half-pixel refinement comprises searching one integer-pixel search center pointed to by an integer motion vector and eight half-pixel positions in half pixel interpolation, and wherein the quarter-pixel refinement comprises searching one half-pixel position and eight quarter-pixel positions in quarter pixel interpolation, and wherein the one-eighth-pixel refinement comprises searching one quarter-pixel position and eight one-eighth-pixel positions in one-eighth pixel interpolation. ### Claim 20 (depends on 10) The system of claim 10, wherein in the event of data dependencies in processing the coding units across different rows of coding units of the frame of the video, the processing of a certain coding unit in a particular row and column is performed after the processing of another coding unit in a previous row and a particular column is finished by a different parallel pipeline.