Close

Nelder-Mead in the desert

A project log for Where's my Christmas Light?

Quickly identifying individual LEDs in a randomly distributed arrangement

Danny HavenithDanny Havenith 05/29/2016 at 15:570 Comments

OK. Just so you know, this project isn't dead. It's just moving in its own pace, that's all...

There are some problems though. As I wrote in a previous log, the OpenCV algorithm used to detect the LEDs in an image has many parameters, and no set of parameters seemed right in all circumstances. A logical next step was to try an optimization algorithm such as Nelder-Mead to find the right arguments.

Nelder-Mead is a relatively simple method to find the maximum (or minimum) value of a function. It does not require the derivative of the function, which makes it applicable in a large number of cases. In essence, for a function that takes two inputs, applying Nelder-Mead consists of walking a triangle downslope across the solution landscape. The triangle may grow or shrink and it uses some tricks to jump out of local puddles. For more than 2 parameters, the triangle becomes a simplex, a figure that can be described by n+1 points in an n-dimensional space.

Nelder Mead over Banana function. Image by wikipedia editor Simiprof.

Any optimization needs a cost function with n inputs and one output, the cost. For a cost function, I chose the absolute difference between the actual number of LEDs and the detected number. I experimented with different inputs, zooming in on the following three parameters:

I just needed to tweak the algorithm to only search in positive values, which is easy just square the proposed inputs before using them in opencv, and then: Let it rip!

Not.

With the settings as chosen above, the NM algorithm could not find any combination of parameters that detected any LEDs, it would just quickly shrink the "triangle" on a set of parameters that resulted in zero LEDs found.

The problem was that the parameter space consists largely of big areas where the algorithm can't find any LEDs at all. If all the points on the NM simplex have the same cost (in this case the maximum cost of finding zero LEDs), the algorithm will just shrink the simplex until it is so small that the algorithm concludes that there is no better solution to be found. So we have a large "flat" desert area where nothing is found, with a small valley somewhere, but the simplex just never walks close to the valley.

There are several ways around this. The first way is to first go hunting for the valley. This can be done for instance by sampling random points in the parameter space, or a grid of points, until a point is found with a lower cost than the other points. As soon as we have a simplex with at least 1 lower point, it will start to walk into that valley.

A second option is to artificially create random hills in the "flat" part of the space. This can be done by adding a random value to the cost when the cost is at its maximum. As a result, the simplex will go wandering around in the parameter space and it might just stumble upon the real valley. This is the option that I chose first, because it was easy to implement. This actually works, if the NM algorithm gets enough time (iterations) to walk around, but it means that my desktop PC needs in the order of seconds to find a suitable parameter set, which is long, considering I want the final algorithm to run on a phone.

A third option is to find an initial set of parameters which may be close to a best solution in most cases and use those as a starting point for NM. This requires some experimenting and tweaking and that is where I'm currently at.

Discussions