Sum of absolute transformed differences
Encyclopedia
Sum of absolute transformed differences (SATD) is a widely used video quality
metric used for block-matching in motion estimation
for video compression. It works by taking a frequency transform, usually a Hadamard transform
, of the differences between the pixels in the original block
and the corresponding pixels in the block being used for comparison. The transform itself is often of a small block rather than the entire macroblock. For example, in x264
, a series of 4×4 blocks are transformed rather than doing the more processor-intensive 16×16 transform.
(SAD), both due to its increased complexity and the fact that SAD-specific MMX and SSE2
instructions exist, while there are no such instructions for SATD. However, SATD can still be optimized considerably with SIMD
instructions on most modern CPUs. The benefit of SATD is that it more accurately predicts quality from both the standpoint of objective and subjective metrics. As such, it is often used in video compressors, either as a way to drive and estimate distortion explicitly, such as in the Theora
(since 1.1 alpha2) encoder, as an optional metric used in wide motion searches, such as in the Microsoft
VC-1
encoder, or as a metric used in sub-pixel refinement, such as in x264.
Video quality
Video quality is a characteristic of a video passed through a video transmission/processing system, a formal or informal measure of perceived video degradation...
metric used for block-matching in motion estimation
Motion estimation
Motion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another; usually from adjacent frames in a video sequence. It is an ill-posed problem as the motion is in three dimensions but the images are a projection of the 3D scene onto a 2D...
for video compression. It works by taking a frequency transform, usually a Hadamard transform
Hadamard transform
The Hadamard transform is an example of a generalized class of Fourier transforms...
, of the differences between the pixels in the original block
Macroblock
Macroblock is an image compression component and technique based on discrete cosine transform used on still images and video frames. Macroblocks are usually composed of two or more blocks of pixels. In the JPEG standard macroblocks are called MCU blocks....
and the corresponding pixels in the block being used for comparison. The transform itself is often of a small block rather than the entire macroblock. For example, in x264
X264
x264 is a free software library for encoding video streams into the H.264/MPEG-4 AVC format. It is released under the terms of the GNU General Public License.-History:...
, a series of 4×4 blocks are transformed rather than doing the more processor-intensive 16×16 transform.
Comparison to other metrics
SATD is slower than the sum of absolute differencesSum of absolute differences
Sum of absolute differences is a widely used, extremely simple algorithm for measuring the similarity between image blocks. It works by taking the absolute difference between each pixel in the original block and the corresponding pixel in the block being used for comparison...
(SAD), both due to its increased complexity and the fact that SAD-specific MMX and SSE2
SSE2
SSE2, Streaming SIMD Extensions 2, is one of the Intel SIMD processor supplementary instruction sets first introduced by Intel with the initial version of the Pentium 4 in 2001. It extends the earlier SSE instruction set, and is intended to fully supplant MMX. Intel extended SSE2 to create SSE3...
instructions exist, while there are no such instructions for SATD. However, SATD can still be optimized considerably with SIMD
SIMD
Single instruction, multiple data , is a class of parallel computers in Flynn's taxonomy. It describes computers with multiple processing elements that perform the same operation on multiple data simultaneously...
instructions on most modern CPUs. The benefit of SATD is that it more accurately predicts quality from both the standpoint of objective and subjective metrics. As such, it is often used in video compressors, either as a way to drive and estimate distortion explicitly, such as in the Theora
Theora
Theora is a free lossy video compression format. It is developed by the Xiph.Org Foundation and distributed without licensing fees alongside their other free and open media projects, including the Vorbis audio format and the Ogg container....
(since 1.1 alpha2) encoder, as an optional metric used in wide motion searches, such as in the Microsoft
Microsoft
Microsoft Corporation is an American public multinational corporation headquartered in Redmond, Washington, USA that develops, manufactures, licenses, and supports a wide range of products and services predominantly related to computing through its various product divisions...
VC-1
VC-1
VC-1 is the informal name of the SMPTE 421M video codec standard, which was initially developed as a proprietary video format by Microsoft before it was released as a formal SMPTE standard video format on April 3, 2006...
encoder, or as a metric used in sub-pixel refinement, such as in x264.
See also
- Hadamard transformHadamard transformThe Hadamard transform is an example of a generalized class of Fourier transforms...
- Motion compensationMotion compensationMotion compensation is an algorithmic technique employed in the encoding of video data for video compression, for example in the generation of MPEG-2 files. Motion compensation describes a picture in terms of the transformation of a reference picture to the current picture. The reference picture...
- Motion estimationMotion estimationMotion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another; usually from adjacent frames in a video sequence. It is an ill-posed problem as the motion is in three dimensions but the images are a projection of the 3D scene onto a 2D...
- Rate-distortion optimization
- Sum of absolute differencesSum of absolute differencesSum of absolute differences is a widely used, extremely simple algorithm for measuring the similarity between image blocks. It works by taking the absolute difference between each pixel in the original block and the corresponding pixel in the block being used for comparison...