Device, method and digital video encoder of complexity scalable block-matching motion estimation utilizing adaptive threshold termination

Claim 2

A complexity scalable device for estimating a frame-to-frame motion vector of an image block of pixels to be encoded with adaptive threshold termination, comprising: A) a dynamic threshold selector, operably coupled to receive a quantization stepsize QP, for dynamically determining a threshold value in accordance with a predetermined scheme based on the quantization stepsize QP; and B) an adaptive motion vector determiner, operably coupled to receive an original block, a reference frame, and the threshold value, for utilizing the threshold value to adaptively estimate the frame-to-frame motion vector.

Claim 3

The complexity scalable device of claim 1 wherein the predetermined scheme includes dynamically determining a threshold value T according to a linear function of a form: T=a*QP+b where a and b are one of: A) monotonically non-increasing preselected functions of a predetermined processing quota PQ; and B) predetermined constants/variables.

Claim 4

The complexity scalable device of claim 1 wherein the adaptive motion vector determiner includes: A) a block-matching motion estimation unit, operably coupled to receive an original block of pixels to be encoded, a reference frame, an output signal from a comparator, for searching for a motion vector of the original block in the reference frame, in accordance with a predetermined search scheme and matching error criterion, and generating a matching error and relative shifts of the matching block with respect to the original block at each search point; B) the comparator, operably coupled to the dynamic threshold selector and the block-matching motion estimation unit, for comparing the threshold value and the matching error, and when the matching error is less than the threshold, generating a signal to a latch and the block-matching motion estimation unit to terminate the operation of the block-matching motion estimation unit for the image block of pixels; and C) the latch, operably coupled to the comparator and the block-matching motion estimation unit, for passing matching block position shifts from the block-matching motion estimation unit as a motion vector upon receiving the signal from the comparator.

Claim 5

The complexity scalable device of claim 1 wherein the device is implemented utilizing one of: A) a microprocessor; and B) a digital signal processor C) a dedicated hardware.

Claim 6

A complexity scalable device in a digital video encoder for estimating a frame-to-frame motion vector of an image block of pixels to be encoded from a reference video frame with adaptive threshold termination, comprising: A) a dynamic threshold selector, operably coupled to receive a quantization stepsize, for determining a threshold value; B) a block-matching motion estimation unit, operably coupled to receive an original block of pixels to be encoded, a reference frame/frame buffer, an output signal from a comparator, for searching for a motion vector of the original block in the reference frame, in accordance with a predetermined search scheme and matching error criterion, and generating a matching error and relative shifts of the matching block with respect to the original block at each search point; C) a comparator, operably coupled to the threshold selector and the block-matching motion estimation unit, for comparing the threshold and the matching error, and when the matching error is less than the threshold, generating a signal to a latch and the block-matching motion estimation unit to terminate the operation of the block-matching motion estimation unit for this block; D) a latch, operably coupled to the comparator and the block-matching motion estimation unit, for passing the matching block position shifts from the block-matching motion estimation unit as a motion vector upon receiving the signal from the comparator.

Claim 7

A complexity scalable device in a digital video encoder for estimating a frame-to-frame motion vector of an image block of pixels to be encoded from a reference video frame with adaptive threshold termination, comprising: A) a dynamic threshold selector, operably coupled to receive a quantization stepsize, for determining a threshold value; B) a block-matching motion estimation unit, operably coupled to receive an original block of pixels to be encoded, a reference frame/frame buffer, an output signal from a comparator, for searching for a motion vector of the original block in the reference frame, in accordance with a predetermined search scheme and matching error criterion, and generating a matching error and relative shifts of the matching block with respect to the original block at each search point; C) a comparator, operably coupled to the threshold selector and the block-matching motion estimation unit, for comparing the threshold and the matching error, and when the matching error is less than the threshold, generating a signal to a latch and the block-matching motion estimation unit to terminate the operation of the block-matching motion estimation unit for this block; D) a latch, operably coupled to the comparator and the block-matching motion estimation unit, for passing the matching block position shifts from the block-matching motion estimation unit as a motion vector upon receiving the signal from the comparator.

Claim 8

The complexity scalable device of claim 5 wherein the predetermined scheme includes dynamically determining a threshold value T according to a linear function of a form: T=a*QP+b where a and b are one of: A) monotonically non-increasing preselected functions of a predetermined processing quota PQ; and B) predetermined constants/variables.

Claim 9

A digital video encoder comprising: A) a block-matching motion estimator with adaptive threshold termination which estimates a motion vector of a original block to be coded from a reference frame; the said motion estimator comprising: A1) a dynamic threshold selector, operably coupled to receive the quantization stepsize from a rate control unit and, where selected, a predetermined processing quota from a host, for determining a threshold value; A2) a block-matching motion estimation unit, operably coupled to receive an original block of pixels to be encoded, a reference frame, an output signal from a comparator, for searching for a motion vector of the original block in the reference frame, in accordance with a predetermined search scheme and matching error criterion, and generating a matching error and relative shifts of the matching block with respect to the original block at each search point; A3) a comparator, operably coupled to the dynamic threshold selector and the block-matching motion estimation unit, for comparing the threshold value and the matching error, and when the matching error is less than the threshold, generating a signal to a latch and the block-matching motion estimation unit to terminate the operation of the block-matching motion estimation unit for this block; A4) a latch, operably coupled to the comparator and the block-matching motion estimation unit, for passing the matching block position shifts from the block-matching motion estimation unit as a motion vector to a motion-compensated predictor upon receiving the signal from the comparator; B) video coding means, operably coupled to receive the input block/video frames, an output of a rate control unit, and a motion vector from the block-matching motion estimator with adaptive threshold termination, for encoding the difference between the original block and motion-compensated prediction block using the motion vector to provide a prediction error block; C) a variable length encoder, operably coupled to the video coding means, for encoding the prediction error block and the motion vector generated by the block-matching motion estimator; D) an output buffer, operably coupled to the variable-length encoder, for receiving binary bits from the variable length encoder and outputting binary bits to the channel; E) a rate control unit, operably coupled to the output buffer, for monitoring the fullness of the buffer and outputting a quantization stepsize to the quantizer of the video coding means and the block-matching motion estimation unit.

Claim 10

A digital video encoder comprising: A) a block-matching motion estimator with adaptive threshold termination which estimates a motion vector of a original block to be coded from a reference frame; the said motion estimator comprising: A1) a dynamic threshold selector, operably coupled to receive the quantization stepsize from a rate control unit and, where selected, a predetermined processing quota from a host, for determining a threshold value; A2) a block-matching motion estimation unit, operably coupled to receive an original block of pixels to be encoded, a reference frame, an output signal from a comparator, for searching for a motion vector of the original block in the reference frame, in accordance with a predetermined search scheme and matching error criterion, and generating a matching error and relative shifts of the matching block with respect to the original block at each search point; A3) a comparator, operably coupled to the dynamic threshold selector and the block-matching motion estimation unit, for comparing the threshold value and the matching error, and when the matching error is less than the threshold, generating a signal to a latch and the block-matching motion estimation unit to terminate the operation of the block-matching motion estimation unit for this block; A4) a latch, operably coupled to the comparator and the block-matching motion estimation unit, for passing the matching block position shifts from the block-matching motion estimation unit as a motion vector to a motion-compensated predictor upon receiving the signal from the comparator; B) video coding means, operably coupled to receive the input block/video frames, an output of a rate control unit, and a motion vector from the block-matching motion estimator with adaptive threshold termination, for encoding the difference between the original block and motion-compensated prediction block using the motion vector to provide a prediction error block; C) a variable length encoder, operably coupled to the video coding means, for encoding the prediction error block and the motion vector generated by the block-matching motion estimator; D) an output buffer, operably coupled to the variable-length encoder, for receiving binary bits from the variable length encoder and outputting binary bits to the channel; E) a rate control unit, operably coupled to the output buffer, for monitoring the fullness of the buffer and outputting a quantization stepsize to the quantizer of the video coding means and the block-matching motion estimation unit.

Claim 11

The complexity scalable device of claim 7 wherein the predetermined scheme includes dynamically determining a threshold value T according to a linear function of a form: T=a*QP+b where a and b are one of: A) monotonically non-increasing preselected functions of a predetermined processing quota PQ; and B) predetermined constants/variables.

Claim 12

A complexity scalable method in a digital video encoder for estimating the frame-to-frame motion vector V of an original image block of pixels to be encoded from a reference video frame with adaptive threshold termination, the method comprising the steps of: A) initializing the motion vector V with (0,0) and a value E min with E(0,0), where E(0,0) is the matching error between the original block and the matching block at the same location of the original block. B) determining a threshold value T in terms of a function of a quantization stepsize QP in accordance with a predetermined scheme; C) Comparing E min to T and where E min is less than T, terminating the process; D) computing a matching error E according to the predetermined matching error criterion between the original block and a matching block at a next search location in the reference frame according to a predetermined search method; E) comparing E to T and where E is less than T, terminating the process; F) where E is greater than or equal to T, comparing E with E min ; G) Where E is greater than or equal to E min , proceeding to step I; H) where E is less than E min , replacing E min with E and replacing V with the relative position shifts of the matching block with respect to the original block; I) determining whether the matching block is a last search block for the predetermined search method; J) where the matching block is the last search block for the predetermined search method, terminating the process and outputting the contents of the motion vector memory as a final motion vector of the block; K) where the matching block fails to be the last search block for the predetermined search method, recycling to step C.

Claim 13

A complexity scalable method in a digital video encoder for estimating the frame-to-frame motion vector V of an original image block of pixels to be encoded from a reference video frame with adaptive threshold termination, the method comprising the steps of: A) initializing the motion vector V with (0,0) and a value E min with E(0,0), where E(0,0) is the matching error between the original block and the matching block at the same location of the original block. B) determining a threshold value T in terms of a function of a quantization stepsize QP in accordance with a predetermined scheme; C) Comparing E min to T and where E min is less than T, terminating the process; D) computing a matching error E according to the predetermined matching error criterion between the original block and a matching block at a next search location in the reference frame according to a predetermined search method; E) comparing E to T and where E is less than T, terminating the process; F) where E is greater than or equal to T, comparing E with E min ; G) Where E is greater than or equal to E min , proceeding to step I; H) where E is less than E min , replacing E min with E and replacing V with the relative position shifts of the matching block with respect to the original block; I) determining whether the matching block is a last search block for the predetermined search method; J) where the matching block is the last search block for the predetermined search method, terminating the process and outputting the contents of the motion vector memory as a final motion vector of the block; K) where the matching block fails to be the last search block for the predetermined search method, recycling to step C.

Claim 14

The method of claim 9 wherein the predetermined scheme includes dynamically determining a threshold value T according to a linear function of a form: T=a*QP+b where a and b are one of: A) monotonically non-increasing preselected functions of a predetermined processing quota PQ; and B) predetermined constants/variables.

Claim 17

The method of claim 11 wherein the predetermined scheme includes dynamically determining a threshold value T according to a linear function of a form: T=a*QP+b where a and b are one of: A) monotonically non-increasing preselected functions of a predetermined processing quota PQ; and B) predetermined constants/variables.

Claim 18

The method of claim 11 wherein the adaptive motion vector determiner includes: A) searching, by a block-matching motion estimation unit, utilizing an original block of pixels to be encoded, a reference frame, and an output signal from a comparator, for a motion vector of the original block in the reference frame, in accordance with a predetermined search scheme and matching error criterion, and generating a matching error and relative shifts of the matching block with respect to the original block at each search point; B) comparing, by the comparator, the threshold value and the matching error, and when the matching error is less than the threshold, generating a signal to a latch and the block-matching motion estimation unit to terminate the operation of the block-matching motion estimation unit for the image block of pixels; and C) passing, by the latch, matching block position shifts from the block-matching motion estimation unit as a motion vector upon receiving the signal from the comparator.

Claim 19

The method of claim 11 wherein the method is implemented utilizing one of: A) a microprocessor; and B) a digital signal processor; C) a dedicated hardware.