# US RE45,014 E1 · Methods for motion estimation with adaptive motion accuracy > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US RE45,014 E1 - Document ID: USRE45014E1 - Status: Granted - Kind: E1 - Application number: 11/984,661 - Filed: 2007-11-20 - Granted: 2014-07-15 - Earliest claimed: 1999-07-27 - Assignees: Sharp Kabushiki Kaisha - Applicants: Jordi Ribas-Corbera; Jiandong Shen - Inventors: Jordi Ribas-Corbera; Jiandong Shen - Web page: https://patentgrep.com/patent/USRE45014E1 ## Abstract Methods for motion estimation with adaptive motion accuracy of the present invention include several techniques for computing motion vectors of high pixel accuracy with a minor increase in computation. One technique uses fast-search strategies in sub-pixel space that smartly searches for the best motion vectors. An alternate technique estimates high-accurate motion vectors using different interpolation filters at different stages in order to reduce computational complexity. Yet another technique uses rate-distortion criteria that adapts according to the different motion accuracies to determine both the best motion vectors and the best motion accuracies. Still another technique uses a VLC table that is interpreted differently at different coding units, according to the associated motion vector accuracy. ## Claims ### Claim 1 A fast-search adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of: (a) searching a first set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V1 to find a best motion vector V2 using a first criteria; (b) searching a second set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V2 to find a best motion vector V3 using a second criteria; (c) searching a third set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V3 to find said best motion vector of said macroblock using a third criteria; and (d) wherein at least one of said first criteria, said second criteria, and said third criteria is a rate-distortion criteria. ### Claim 2 (depends on 1) The method of claim 1, said step of searching a first set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V1 to find a best motion vector V2 further comprising the step of searching a first set of eight motion vector candidates in a grid of ½-pixel resolution of square radius 1 centered on V1 to find a best motion vector V2. ### Claim 3 (depends on 1) The method of claim 1, said step of searching a second set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V2 to find a best motion vector V3 further comprising the step of searching a second set of eight motion vector candidates in a grid of ⅙-pixel resolution of square radius 1 centered on V2 to find a best motion vector V3. ### Claim 4 (depends on 1) The method of claim 1 further comprising the steps of using V2 as the motion vector for the macroblock if V2 has the smallest rate-distortion cost and skipping step (c) of claim 1. ### Claim 5 (depends on 1) The method of claim 1, said step of searching a third set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V3 to find said best motion vector of said macroblock further comprising the step of searching a third set of eight motion vector candidates in a grid of ⅙-pixel resolution of square radius 1 centered on V3 to find said best motion vector of said macroblock. ### Claim 6 (depends on 1) The method of claim 1, said step of searching a third set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V3 to find said best motion vector of said macroblock further comprising the step of skipping motion vector candidates of said third set of motion vector candidates that have already been tested. ### Claim 7 (depends on 1) The method of claim 1 further wherein said step of searching said first set of motion vector candidates further comprises the step of searching said first set of motion vector candidates using a first filter to do a first interpolation, said step of searching said second set of motion vector candidates further comprises the step of searching said second set of motion vector candidates using a second filter to do a second interpolation, and said step of searching said third set of motion vector candidates further comprises the step of searching said third set of motion vector candidates using a third filter to do a third interpolation. ### Claim 8 (depends on 1) The method of claim 1, said step of searching a second set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V2 to find a best motion vector V3 further comprising the steps of: (a) searching three candidates of ⅓-pel accuracy V2 and a ½-pel location with the next lowest rate-distortion cost if V2 is at the center; (b) searching four vector candidates of ⅓-pel accuracy that are closest to V2 if V2 is a corner vector; and (c) determining which of two corners has lower rate-distortion cost and searching four vector candidates of ⅓-pel accuracy that are closest to a line between said corner with lower rate-distortion cost, if V2 is between two corners vectors. ### Claim 9 An adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of: (a) searching a first set of motion vector candidates in a grid centered on V1 using a first criteria to find a best motion vector V2 using a first filter to do a first interpolation; (b) searching a second set of motion vector candidates in a grid centered on V2 using a second criteria to find a best motion vector V3 using a second filter to do a second interpolation; and (c) searching a third set of motion vector candidates in a grid centered on V3 using a third criteria to find said best motion vector of said macroblock using a third filter to do a third interpolation; (d) wherein at least one of said first criteria, said second criteria, and said third criteria is a rate-distortion criteria. ### Claim 10 (depends on 9) The method of claim 9 wherein said step of searching using a first filter to do a first interpolation further comprises using a simple filter to do a coarse interpolation. ### Claim 11 (depends on 9) The method of claim 9 wherein said step of searching using a first filter to do a first interpolation further comprises using a simple filter to do a coarse interpolation and said step of searching using a second filter to do a second interpolation further comprises using a complex filter to do a fine interpolation. ### Claim 12 (depends on 11) The method of claim 11 wherein said step of searching using a third filter to do a third interpolation further comprises using a complex filter to do a fine interpolation. ### Claim 13 (depends on 9) The method of claim 9 wherein said step of searching using a first filter to do a first interpolation further comprises using a bilinear filter to interpolate the reference frame by 2×2. ### Claim 14 (depends on 9) The method of claim 9 wherein said step of searching using a first filter to do a first interpolation further comprises using a bilinear filter to interpolate the reference frame by 2×2 and said step of searching using a second filter to do a second interpolation further comprises using a cubic filter to do a fine interpolation. ### Claim 15 (depends on 14) The method of claim 14 wherein said step of searching using a third filter to do a third interpolation further comprises using a cubic filter to do a fine interpolation. ### Claim 16 An adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of: (a) searching at a first motion accuracy for a first best motion vector of said macroblock; (b) encoding said first best motion vector and said first motion accuracy; (c) searching for at least one second best motion vector of said macroblock at an at least one second motion accuracy; (d) encoding said at least one second best motion vector and said at least one second motion accuracy; and (e) selecting the best motion vector of said first and at least one second best motion vectors using rate-distortion criteria. ### Claim 17 (depends on 16) The method of claim 16 wherein said step of selecting the best motion vector using rate-distortion criteria further comprises the step of said rate-distortion criteria adapting according to the different motion accuracies to determine both the best motion vectors and the best motion accuracies. ### Claim 18 (depends on 16) The method of claim 16, said step of searching for at least one second best motion vector at an at least one second motion accuracy further comprising the step of searching for at least one second best motion vector of said macroblock at an at least one second motion accuracy that is finer than said first motion accuracy. ### Claim 19 (depends on 16) The method of claim 16 wherein said step of selecting the best motion vector using rate-distortion criteria further comprises the step of using rate-distortion criteria of the type “distortion+L*Bits” to select the best motion vector. ### Claim 20 An adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of: (a) searching at a motion accuracy for a best motion vector of said macroblock using rate-distortion criteria; (b) encoding said motion accuracy using a code from a VLC table that is interpreted differently at different coding units according to the associated motion vector accuracy; and (c) encoding said best motion vector in the respective accuracy space. ### Claim 21 A system for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said system comprising: (a) a first encoder for searching a first set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V1 using a first criteria to find a best motion vector V2; (b) a second encoder for searching a second set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V2 using a second criteria to find a best motion vector V3; and (c) a third encoder for searching a third set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V3 using a third criteria to find said best motion vector of said macroblock; (d) wherein at least one of said first criteria, said second criteria, and said third criteria is a rate-distortion criteria. ### Claim 22 (depends on 21) The system of claim 21 wherein said first, second, and third encoders are a single encoder. ### Claim 23 A fast-search adaptive motion accuracy search method for estimating motion vectors in motion-compensated video coding by finding a best motion vector for a macroblock, said method comprising the steps of: (a) searching a first set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V1 to find a best motion vector V2; (b) searching a second set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V2 to find a best motion vector V3; (c) searching a third set of motion vector candidates in a grid of sub-pixel resolution of a predetermined square radius centered on V3 to find said best motion vector of said macroblock, and (d) using V2 as the motion vector for the macroblock if V2 has the smallest rate-distortion cost and skipping step (c). ### Claim 24 (depends on 1) The method of claim 1, wherein said first criteria, said second criteria, and said third criteria are all rate-distortion criteria. ### Claim 25 (depends on 9) The method of claim 9, wherein said first criteria, said second criteria, and said third criteria are all rate-distortion criteria. ### Claim 26 (depends on 21) The system of claim 21, wherein said first criteria, said second criteria, and said third criteria are all rate-distortion criteria. ### Claim 27 A method of performing, at a video encoder, motion-compensated video encoding of an input image having respective frames each of which is decomposed into blocks, comprising: searching, block by block, for a motion vector that represents an amount of movement from a corresponding position of a reference frame in an objective current block for each of the blocks decomposed from a frame of the input image, compensating a motion using the motion vector, the motion vector having fractional accuracy expressed by 1/N pel (where N is an integer ≧2), encoding the accuracy of the motion vector and the motion vector, wherein encoding the accuracy is performed separately from encoding the motion vector, said encoding the motion vector step encoding the motion vector for each block on a block-by-block basis, said searching and said compensating steps are performed by selecting a filter from a plurality of interpolation filters according to the accuracy, wherein the accuracy is set on a frame basis such that the same accuracy is used for every motion vector in a frame but a different accuracy can be used for a different frame. ### Claim 28 A method of decoding, at a video decoder, motion-compensated coded data obtained by encoding an image frame block-by-block, comprising: decoding a motion vector that represents an amount of movement from a corresponding position of a reference frame in an objective current block for each of the blocks included in the coded data obtained, decoding an accuracy of the motion vector, the motion vector having fractional accuracy expressed by 1/N pel (where N is an integer ≧2), compensating a motion using the accuracy and the motion vector, said decoding the accuracy step being performed separately from said decoding the motion vector step, said decoding the motion vector step being performed on a block-by-block basis, said motion compensation step being performed by selecting a filter from a plurality of interpolation filters according to the accuracy, wherein the accuracy is set on a frame basis such that the same accuracy is used for every motion vector in a frame but a different accuracy can be used for a different frame.