Digital Video Processing (EE392J)Department of Electrical EngineeringStanford UniversityProblem Set No. 2Issued: January 24, 2007Due: January 31, 2007 (in class)Reading: Chapter 6, except skip Sections 6.4.6 and 6.5Problem l. Briefly describe the three basic components of a motion estimation algorithm. Please limit your answer totwo or three sentences description for each of the three components.Problem 2. Briefly answer Problem 6.1. Please limit your answer to one paragraph or one table.Problem 3. Consider the signal sc(x, y, t) defined over the entire 3-D space (x, y, t), where sc(x, y, t) is generatedfrom one image by translational motion with uniform (constant) velocities of vxand vyalong the horizontal andvertical directions, respectively. Suppose sc(x, y, 0) = x + y + xy.(a) Determine sc(x, y, t).(b) The optical flow equation (or optical flow constraint) is based on the assumption that the intensity of a point in avideo signal remains constant along its motion trajectory. Show that the optical flow equation (below) is satisfied forall points (x, y, t) of the signal sc(x, y, t).vx(x, y, t)∂sc(x, y, t)∂x+ vy(x, y, t)∂sc(x, y, t)∂y+∂sc(x, y, t)∂t= 0 (1)(c) What is the spatio-temporal frequency spectrum of sc(x, y, t)? Provide both a mathematical expression (in termsof sc(x, y, 0) or its Fourier transform) as well as a geometrical interpretation.Problem 4. Block-matching motion estimation algorithms use a variety of search strategies to find the best match-ing block, where these strategies trade off motion estimation accuracy for reduced computational complexity. In thisproblem assume that the sum of absolute differences (SAD) criterion is used to determine the best match and thatcomputing the SAD between two sets of N pixels,Pi=1toN|ai− bi| requires N operations. Assume the blocksizeis 16 × 16 pixels, the frame size is N1× N2pixels (N1and N2are integer multiples of 16), and the search range is+/-15 pixels horizontally and vertically. Also assume that the number of operations required for a 16 × 16 block on theboundary of the frame is equal to the number of operations required for a 16 × 16 block in the interior of the frame.(a) Determine the number of operations required to compute the motion between the luminance component of eachframe when performing full search over all integer motion vectors in the search range.(b) Determine the number of operations required to compute the motion between the luminance component of eachframe when performing 4-step search (log search) over all integer motion vectors in the search range.(c) Determine the number of operations required for (a) and (b) in the case of CIF video (N1= 352, N2= 240, 30frames/sec) and HDTV video (N1= 1280, N2= 720, 60 frames/sec).Problem 5. Block-Matching Motion EstimationThe goal of this Matlab-based exercise is to develop a block-based motion estimation algorithm to compute the mo-tion between a pair of images. The images are available on the Problem Set webpage off of the course webpagewww.stanford.edu/class/ee392j/ . A summary of useful Matlab operations and commands, as well as suggestions forwriting your programs, are given on pages 3 and 4 of this handout. It is strongly recommended that you read thesesuggestions, as they may save you a lot of time.(a) Read the two images into Matlab and perform a color space conversion from RGB to YIQ using the color spaceconversion equation 1.4.3 given on page 18 of the text. Display and turn in separate images for each of the Y, I, and Qcomponents (you many find imagesc and subplot commands useful). Comment on the information contained in eachcolor component.(b) In the remainder of this problem we estimate the motion using only the luminance component of each frame. Whyis computing motion using only the luminance component usually sufficient for estimating motion for a color videosequence? When does this approach fail?(c) Design a block-matchingmotion estimation algorithm that partitions the current frame into nonoverlapping16×16-pixel blocks, and for each block determine the best-matching block in the previous frame based on the sum of absoluteerror (SAE) criterion. Determine the best-matching block by performing a full-search over all integer motion vectorswithin the search range, where the search range is +16/-15 pixels in the horizontal and vertical directions of the pre-vious frame. You may limit your algorithm to only estimate the motion of the 16 × 16-pixel blocks that are in theinterior of the image, i.e. you do not have to estimate the motion of the 16 × 16-pixel blocks on the boundary of theimage. Plot the estimated 2-D motion vector field using quiver plot, and turn in a copy of this plot.(d) Compute the motion-compensated (MC) prediction of the current frame by using the computed motion vectors toappropriately translate the blocks from the previous frame. Turn in an image of the MC-prediction. How does theMC-prediction compare to the original current frame? What is the peak signal-to-noise ratio (PSNR) (equation 1.5.6in the text) between the MC-prediction and the original current frame (only use pixels in interior blocks to computethe PSNR)?(e) Instead of using full search to determine the best matching block, you can use another method, for example a four-step logarithmic search. Briefly describe one advantage and one disadvantage of using four-step logarithmic searchinstead of full search. Note that this part of the problem only requires a written answer, specifically we are not askingyou to redesign your motion estimation algorithm using four-step log search.Include in your problem set solutions copies of your Matlab programs. The programs should include sufficientcomments to enable one to easily follow your program.Save copies of your programs as they may be useful for your final project.Some Useful Matlab TipsThe following contains some Matlab tips that may be useful for people who are new to Matlab as well as Matlabexperts who are new to processing images. A list of matlab topics for which help is available can be found by typinghelp at the Matlab prompt. Help for a particular command can be found by typing help command, and M-files canbe searched for a particular keyword with lookfor.Some useful matlab commands:diary To save text of Matlab session into a filewhos To view current variables in a sessionimread To read in an image file. You may need to convert the input image to double.imwrite To write out an image filefread To read