# Best Guess Rectangle

I am using openCV to find a particular object, and am trying to find a way to make it locate the object consistently. The object's location will be determined by taking 30 frames and trying to find the best guess based on where it is found in each of the 30 frames. Both the camera and object are (mostly) stationary (the object can move slightly, but optimally it will be stationary during the 30 frames).

This image demonstrates what I'm looking for. I know that the green box may not truly be what would be calculated, I just threw it in there to demonstrate. The red boxes are the guesses on each frame, and the green one is what I'm trying to calculate. Are there any known formulas/algorithms for this, or any references on where to start?

Note

I initially tried to just calculate the mode along the X-axis (ignoring width) (with each estimate rounded so that there would be some similarity), and picking a random rectangle whose x value was in that range for X but that was not giving me a very good estimate.

• Can you post an example set of actual rectangle coordinates? Otherwise, everyone who wants to implement a solution has to create random test data first – Niki Estner Apr 3 '14 at 7:16

I must admit I haven't worked on anything like this before, but looking at your data it seems to me that computing the median of e.g. the lower left corner point of all rectangles (i.e. taking x and y dimensions into account) should get rid of outliers. After having removed outliers from your data, you could simply try to average the remaining rectangles. Obviously, such an approach requires some heuristic tweaking, but it may be worth a try.

I just tried Matt's approach (just taking the 1D medians of the top/left/bottom/right X and Y values) and the results seem pretty good. See plot below of 20 realizations of various random rectangles.

scilab CODE ONLY BELOW

function r = getRect(t,l,b,r)
large =  [1 1 0 0]*rand(1,1,'normal')*abs(t-b) + [0 0 1 1]*rand(1,1,'normal')*abs(l-r);
small =  [1 1 0 0]*rand(1,1,'normal')*5 + [0 0 1 1]*rand(1,1,'normal')*5;

noise = small;
if (rand(1,1,'uniform') < 0.2) then
noise = large;
end
r = [t l b r] + noise;
endfunction

for p = 1:20;

N = 20;

x_points = [2 2 4 4 2];
y_points = [1 3 3 1 1];

subplot(5,4,p)
RR= [];
for n=1:N
R = getRect(10,10,100,50);
RR = [RR; R];
plot(R(x_points),R(y_points),'r');
end

RRm = median(RR,'r');

xset("thickness",4)
plot(RRm(x_points),RRm(y_points),'g');
xset("thickness",1)
end;

• The example image that I posted may not be fully accurate, because in general, bad guesses will be in a lower y direction than the correct one (though not all will be, the majority of outliers will be lower than the target) – Dan Drews Apr 2 '14 at 21:03
• OK, but the median will probably still get rid of them, or is there something I don't see? – Matt L. Apr 2 '14 at 21:04
• Say that 8 of them are clearly below the target (but wide-spread enough in the x-direction that they should be seen as outliers), 2 clearly are above, and 5 are on target. The result would be 7 on/above the target and 8 below, so the median value would be the "highest" point below the target wouldn't it? Unless there's some form of 2-dimensional median that I could use? – Dan Drews Apr 2 '14 at 21:07
• Yes, you must also consider the x-direction and compute a median to eliminate outliers. As far as I know there are (several) definitions of a multidimensional median, but I guess you could get away with computing two one-dimensional medians. But again, I haven't tried it myself ... – Matt L. Apr 2 '14 at 21:12