Exhaustive Block Matching Algorithm

33 views (last 30 days)
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 :(
  2 Comments
Jan
Jan on 1 Feb 2012
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
lianjiang on 15 Nov 2022
请问还有其他的pdf可以分享一下吗

Sign in to comment.

Accepted Answer

Qihan Gao
Qihan Gao on 29 Aug 2021
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

More Answers (3)

Walter Roberson
Walter Roberson on 1 Feb 2012
On one of the lines, you have a typing mistake.
  1 Comment
Tuan Nguyen
Tuan Nguyen on 7 Feb 2012
I'm sorry about that since my English is not so good.

Sign in to comment.


Tuan Nguyen
Tuan Nguyen on 7 Feb 2012
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
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.
  5 Comments
Anil Chowdary Tummala
Anil Chowdary Tummala on 10 Feb 2021
Hi
what is f1, f2, N, R, and K in this code
Walter Roberson
Walter Roberson on 10 Feb 2021
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.

Sign in to comment.


beppo
beppo on 22 Nov 2017
Hi, what is the arrow function at the very bottom? Also, is the code working or not? Thanks

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!