3
$\begingroup$

I detect points in images with an algorithm. The only parameter is a threshold T that I can modify at each image. Such images are from a continuous video, so each one is only slightly different from the previous one. I don't know a priori how many points I get for a determined threshold, as it also depends on the content of the processed image. The whole system needs at least 20 points to continue running, but the more points I have, the more complex the process is, therefore the slower the application. I have made a scheme to represent this:

problem visual representation

I need to maintain nb over 20 and if possible under 50 to avoid over-computation. I determined an "ideal" value at 40. I begin with T = 30, but it's only empirical. Usually, T = 10 gets too many points and T = 60 too little.

My question: How do I filter T depending on past values nb, in order to keep nb around 40 for each new image?

I precise I'm really not an expert in filtering, as you may have guessed. I'm not even sure it's a filter I need here.

EDIT: as requested in comments, here is a plot of nb for five different thresholds. Content is always the same (fixed camera), therefore variations are mostly due to camera noise.

evolution of nb on different images, for five different thresholds

$\endgroup$
  • 1
    $\begingroup$ Assuming you held the threshold constant, does the number of points change slowly or quickly as you go from image to image? It would be interesting to see a plot of nb on the y axis and images on the x axis for a few different thresholds. $\endgroup$ – Jim Clay Mar 30 '12 at 16:25
  • 1
    $\begingroup$ Also, how expensive is the thresholding operation? Would doing two thresholds per image, for instance, be unacceptable? $\endgroup$ – Jim Clay Mar 30 '12 at 17:06
  • $\begingroup$ I am confused because your plot shows no correlation between T and nb. Do you merely want a function that takes a real number and maps it to another under 50, and preferably around 40? $\endgroup$ – Emre Mar 30 '12 at 18:28
  • $\begingroup$ @JimClay: I added a graph to answer your question. The process is quite heavy, so it is not possible to test different thresholds on an image. $\endgroup$ – Stéphane Péchard Apr 2 '12 at 13:02
  • $\begingroup$ @Emre: the first plot actually is more a draw than a plot :-) it does not show nb(T), the green line is just the target I would like to stay close to. $\endgroup$ – Stéphane Péchard Apr 2 '12 at 13:04
2
$\begingroup$

In your plot of nb vs. image it appears that there is some high-frequency "noise" (no surprise there), and that the windowed mean is surprisingly stable. For the purposes of this answer I am going to assume that the high-frequency noise is fairly representative of the general case, but that there will also be some slow-to-medium trends as well. It seems like there would have to be if the images are changing. The frame rate should generally be faster than the changes, though, so the trends should be relatively slow.

Normally I would suggest a low-frequency filter to get rid of the high-frequency "noise", but in this case I don't think that would be wise. For any given image the next image is very likely to be highly correlated, so I think it makes sense to adjust somewhat if an image has a large change in nb. I suggest two different solutions.

1) Use a simple moving average of the past n nb values. Performance is obviously important in this application, and a moving average is computationally cheap. A moving average gives some stability, which is important given the high-frequency noise, but also is responsive to changes in the data. You can trade responsiveness for stability by decreasing or increasing n.

Once you have the nb moving average you use that to produce the "error" which is your target nb minus the moving average nb. Thus, if the average nb is too low, the error is positive, if the average nb is too high, the error is negative. You use the error to adjust the threshold. Typically the new threshold would be

$threshold = threshold - \alpha * error$

$\alpha$ needs to be determined either by analysis of your problem or by empirically testing. You substract the error result from the threshold because a positive error means you need nb to go up, which means that you need the threshold to go down.

2) Use a PID controller. The PID controller would produce a threshold value for every image, and use the target nb vs. actual nb error (similar to the moving average error except it's an instantaneous error, not an average) to update its threshold for the next image.

The "integral" portion of the controller will give you stability, while the proportional/derivative part will give you responsiveness. You would need to make sure that the loop itself is stable, and test the constants on different videos, but this would be a very powerful way of adjusting the threshold. It also offers the possibility of making your app smarter by changing the loop constants dynamically, if needed.

Solution 1 is easier to implement and is a little cheaper computationally, solution 2 is more powerful but also more complicated. I would see if the moving average is good enough. If it is, great, if not, implement the PID controller.

EDIT: Tried to make the two solutions a little clearer.

$\endgroup$
  • $\begingroup$ Thanks for this, it will help to smooth the values over time. Now I need to find a way to stay close to a determined nb value (40 in my case). $\endgroup$ – Stéphane Péchard Apr 3 '12 at 9:35
  • $\begingroup$ @StéphanePéchard Added some explanation to solution 1. $\endgroup$ – Jim Clay Apr 3 '12 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.