Exhaustive Block Matching Algorithm

Hi all,

I'm trying to write the Exhaustive Block Matching Algorithm based on the pseudo-code written in this slide: http://inst.eecs.berkeley.edu/~ee290t/sp04/lectures/motion_estimation.pdf

I think I wrote my programme not correctly but don't know where I was wrong. Can anyone please help me? Thank you very much :(

[Jan]

It is very likely, that someone is assisting to solve the problems if you post the corresponding code and explain, what's going wrong. Currently the best answer is: "yes".

[lianjiang]

请问还有其他的pdf可以分享一下吗

Answer 1

[Qihan Gao]

Hi, a reply after nearly 10 years to the original question. Since I am learning this subject these days, I have modified the codes to get it work. Here are my modified codes.

%Extract the matrix of your image and doing rgb2ycbcr transformation
%Here we assume that the Y_ref and Y_predict are the Luminance plane matrix
%As in YCbCr/YUV dimension, 
%Cb and Cr carries less information that human sensors hard to detect
%Y_ref is the original first frame
%Y_predict is the original second frame
%N is the macroblock size
%R is the radius of pixels of the searching window
%Y_esitimate is the new second frame that the function produces from
%original first frame
%SAD is Sum of Absolute Difference
%Reson of using SAD not MAD is considering the total arithmetic operations
%Using SAD can reduce the computional complexity comparing to calculating MAD
function [Y_estimate SAD_counter] = Exhaustive_Search(Y_ref,Y_predict,N,R)
%SAD operations conunter
SAD_counter = 0;
[height width] = size(Y_ref);
for i = 1:N:height-N+1
    for j = 1:N:width-N+1
        %initialisation of SAD_min, the maximum value is 1xN^2 (after scaling)
        SAD_min = 1*N^2;
        for m = -R:1:R
            for n = -R:1:R    
                if ( i+m < 1 || i+m+N-1 > height || j+n < 1 || j+n+N-1 > width)  
                    continue;
                end
                SAD=sum(abs(Y_predict(i:i+N-1,j:j+N-1)-Y_ref(i+m:i+m+N-1,j+n:j+n+N-1)),'all');
                SAD_counter = SAD_counter+1;
                if (SAD < SAD_min)
                   SAD_min = SAD; Y_estimate(i:i+N-1,j:j+N-1) = Y_ref(i+m:i+m+N-1,j+n:j+n+N-1);
                end
            end
        end
    end
end

Answer 2

[Walter Roberson]

On one of the lines, you have a typing mistake.

[Tuan Nguyen]

I'm sorry about that since my English is not so good.

Answer 3

[Tuan Nguyen]

Oh I'm so sorry for forgetting posting my code. This is my matlab code written for exhaustive block matching algorithm

function motionVect = motionEst(f1,f2,N,R)
[height width] = size(f2);
figure,imshow(f2);
hold on;
for i = 1:N:height-N
    for j = 1:N:width-N
        MAD_min = 256;
        mvx = 0;
        mvy = 0;
        for k = -R:1:R
            for l = -R:1:R
                %MAD=sum(sum(abs(f1(i:i+N-1,j:j+N-1)-f2(i+k:i+k+N-1,j+l:j+l+N-1))));
                MAD = 0;
                for u = i:i+N-1
                    for v = j:j+N-1
                        if ((u+k > 0)&&(u+k < height + 1)&&(v+l > 0)&&(v+l < width + 1))
                            MAD = MAD + abs(f1(u,v)-f2(u+k,v+l));
                        end
                    end
                end
        MAD = MAD/(N*N);
                if (MAD<MAD_min)
                    MAD_min = MAD;
                    dy = k;
                    dx = l;
                end
            end
        end
        iblk = floor((i-1)/(N+1))+1;
        jblk = floor((j-1)/(N+1))+1;
        mvx(iblk,jblk) = dx;
        mvy(iblk,jblk) = dy;
        %figure, imshow(f2);
        %hold on;
        arrow([i j],[i+dy j+dx], 3);
    
    end
end

And this is the pseudo-code on which I based to write my code

http://s16.postimage.org/4e5q3vc03/EBMA_pseudocode.jpg

I have a doubt that there might be something wrong with the lines in my code which calculate MAD but I'm not so sure about that.

Can anyone please help me with this problem?

Thanks very much.

[Neda Azarmehr]

Hi

I am wondering what is N, R, and K on this code. Could anyone help me about it?

Regards, Neda

[Walter Roberson]

N is the block size. R is the search range. K is the current search location.

[Felipe Ayres]

aren't dy and dx switched?

[Anil Chowdary Tummala]

Hi

what is f1, f2, N, R, and K in this code

[Walter Roberson]

@Anil Chowdary Tummala

N is the block size. R is the search range. K is the current search location.

f1 is the first of the two blocks to be matched. f2 is the other block to be matched.

Answer 4

[beppo]

Hi, what is the arrow function at the very bottom? Also, is the code working or not? Thanks

[Walter Roberson]

https://www.mathworks.com/matlabcentral/fileexchange/278-arrow