DOC PREVIEW
UW-Madison ECE 734 - Performance Enhancement of Video Compression Algorithms with SIMD

This preview shows page 1-2-3-4-5-6-38-39-40-41-42-78-79-80-81-82-83 out of 83 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 83 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

C(k) = 1 otherwiseFigure 4.4.5 Part of Predicted frame (5) with block size of 8 x 8Figure 4.4.6 Part of Predicted frame (5) with block size of 16x16The task to be performed by the search algorithm is to find the best match for a block in the current frame in the next frame. A typical block size is 8x8 or 16x16 pixels. The quality of match found will depend on the value of Mean Absolute Error, more commonly known as MAE between the blocks. This is the average absolute pixel-wise difference between two blocks, reference block in the current frame and probable match found in the next frame. The matching block is figured out on the basis of the magnitude of the value of its mean error. Smaller the magnitude better is the match. The displacement of the block with the minimum MAE is taken as the motion vector.Formula for MAE is given by:Figure 2.1.3 Example path for convergence of Three Step Search2.2 Motion Compensation and Image SubtractionPerformance Enhancement ofVideo Compression Algorithmswith SIMDReport Submitted By:Shamik ValiaSaket Jamkar1 IntroductionVideo Compression algorithms have a large number of applications ranging from VideoConferencing to Video on Demand to Video phones. Video Compression standards (suchas the MPEG -1, 2, 4, 7) and Teleconferencing standards (such as the H.2XX) are vitalalgorithms used in these and other multimedia applications, whose performance is verycritical given the high data rates that are common for video applications. The timingconstraints with such high data rates can be challenging enough even for custom Video-codecs and overwhelming for some of the state-of-the-art superscalar processors.Performing these operations real-time isn’t easy on most platforms if image resolutions ofacceptable quality are desired.The algorithms, however, consist of repetitive and regular operations by nature, whichcould benefit greatly from the use of some architectures that are better able to performsuch repetitive tasks efficiently. In recent years, general purpose microprocessors havealso been endowed with functional units capable of Single Instruction Stream MultipleData Stream (SIMD) operation. This project attempts to study the speedup achievable forthe most critical parts of these algorithms by utilizing the Streaming SIMD Extensions 2from the Intel Pentium 4 processors. We also deal with the improvement schemes for theDCT algorithm on the SSE2 architecture.2 Basic steps used in Video CompressionThe Video Compression algorithm utilized in numerous standards (such as MPEG 1, 2H.263) usually consists of the following steps:1. Motion Estimation2. Motion Compensation and Image Subtraction3. Discrete Cosine Transform4. Quantization5. Run Length Encoding6. Entropy Coding – Huffman CodingWe examine each of these steps in greater detail in this section.2.1 Motion EstimationMotion estimation is the process of calculating motion vectors by finding matchingblocks in the future frame corresponding to blocks in the current frame. Motionestimation helps in detecting the temporal redundancy. Various search algorithms havebeen devised for estimating motion. The basic assumption underlying these algorithms isthat only translational motion can be compensated for Rotational motion and zoomingcannot be estimated by using block based search algorithms. It is known to be the mostcrucial and computationally intensive process in the video compression algorithm.Figure 2.1.1 Search region (-p, p)Since most of the video streams have a frame rate ranging from 15 to 30 frames persecond, there is never a very large motion of any object between two successive frames.Therefore most search algorithms search for matching block in the neighborhood of theposition of the current block in the next frame. The region where matching block issearched for is called the search region. Search region around a block is shown in thefigure 2.1.1.The choice for the value of p will depend upon the type of broadcast that has to be sent.For fast-moving videos such as sports events a higher value of p such as 16 or 32 may bePSearch Region (-p,p)Current blockused. On the other hand for broadcasts with less motion such as a news-telecast a smallervalue of p such as 4 or 8 may be used.Figure 2.1.2 Motion vector and best matchThe task to be performed by the search algorithm is to find the best match for a block inthe current frame in the next frame. A typical block size is 8x8 or 16x16 pixels. Thequality of match found will depend on the value of Mean Absolute Error, morecommonly known as MAE between the blocks. This is the average absolute pixel-wisedifference between two blocks, reference block in the current frame and probable matchfound in the next frame. The matching block is figured out on the basis of the magnitudeof the value of its mean error. Smaller the magnitude better is the match. Thedisplacement of the block with the minimum MAE is taken as the motion vector.Formula for MAE is given by:Next we explain the two search algorithms that were used in this project.u,v(x,y)(x+u,y+v)MAE = (1/MN) | C(x+k,y+l) – R(x+I+k,y+j+l)|2.1.1 Full SearchFull search is an exhaustive search algorithm. Full search is the simplest method to findthe motion vector for each block; in it the MAE(i,j) is found at each point in the searchregion. Thus a search for the match block is made in the complete (-p, +p) range in thefuture frames for every block of the current frame. For each motion vector, there are (2p) 2 search locations. At each search location (i,j) wecompare N x M pixels. Each pixel comparison requires three operations, namely: asubtraction, an absolute value calculation and an addition. We ignore the cost ofaccessing the pixels C(x + k, y + l) and R(x + i + k, y + j + l). Thus the total complexityper block is (2p) 2 x MN x 3 operations. For a picture resolution of I x J, and a picture rateof F pictures/second, the overall complexity is IJF/MN x (2p) 2 x MN x 3 operations persecond.But this makes it a very intensive method computationally. CPU time for full search is thehighest of all the algorithms. At the same time the accuracy of Full search is also highestand the best match for every block in the current frame is always found. Full search,therefore is a benchmark for comparison of the quality of a search algorithm, which


View Full Document

UW-Madison ECE 734 - Performance Enhancement of Video Compression Algorithms with SIMD

Documents in this Course
Load more
Download Performance Enhancement of Video Compression Algorithms with SIMD
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Performance Enhancement of Video Compression Algorithms with SIMD and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Performance Enhancement of Video Compression Algorithms with SIMD 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?