I'm wondering if there is a fast algorithm for finding the minimum energy/cost line that crosses a n by m field of discrete values. So for example the darkest line that crosses a bitmap. This seems easy enough to brute force by trying every slope intercept combination at some increment but is it possible to do better? And what about in the case of a 3 dimensional field with a plane intersecting it. Does that change anything?
It seems to me like there might be some kind of trick using the Gaussian pyramid...
Fast algorithm for finding minimum energy line
Moderators: phlip, Moderators General, Prelates

 Posts: 310
 Joined: Wed Jul 01, 2009 3:03 am UTC
Re: Fast algorithm for finding minimum energy line
Are you trying to find a minimal path from one point to another or are you specifically looking for a straight line?
In the minimal path case this strikes me as very similar to Problem 18 from Project Euler (and problem 67), you could apply the same algorithm but using minimal values rather than maximal ones.
In the second case I'm not sure how you would go about it short of brute forcing it. You might be able to identify low value areas and then bias your algorithm in favour of intersecting those.
In the minimal path case this strikes me as very similar to Problem 18 from Project Euler (and problem 67), you could apply the same algorithm but using minimal values rather than maximal ones.
In the second case I'm not sure how you would go about it short of brute forcing it. You might be able to identify low value areas and then bias your algorithm in favour of intersecting those.
 Xeio
 Friends, Faidites, Countrymen
 Posts: 5101
 Joined: Wed Jul 25, 2007 11:12 am UTC
 Location: C:\Users\Xeio\
 Contact:
Re: Fast algorithm for finding minimum energy line
I'm assuming Dijkstra's algorithm would be something like what you want. Assuming pathing is what you're trying to do.
Re: Fast algorithm for finding minimum energy line
The trivial solution is a line that crosses the darkest corner only. It is very unlikely that another line will cross more of the image with less lightness encountered. If this is not acceptable, how much of the plane must it cross? Does the distance the line spends over a pixel count, or only the fact that it crosses that pixel?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: Fast algorithm for finding minimum energy line
somebody already took it wrote:I'm wondering if there is a fast algorithm for finding the minimum energy/cost line that crosses a n by m field of discrete values. So for example the darkest line that crosses a bitmap.
Are you trying to do something like this? (a cool picture resizing method without distortion)
For a path going down across a bitmap, with each step going vertically or diagonally down own pixel at a time, you can use a simple dynamic programming technique to essentially try all paths at the same time. As zed0 already said, if you want only straight lines, then this doesn't work. In that case you will probably want something like a Simulated Annealing algorithm to find a good but not necessarily optimal line. This would also apply to the 3D case to find a suitable flat plane through a cuboid.
 eta oin shrdlu
 Posts: 451
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: Fast algorithm for finding minimum energy line
The "bruteforce" algorithm you suggest is essentially the Hough transform (or the related Radon transform); this is not really a "fast" algorithm, but it is one of the standard linedetection methods. Each pixel "votes" on all the lines passing through it, in this case with a vote strength depending on how dark it is. Lines with a lot of votes are good candidates.

 Posts: 310
 Joined: Wed Jul 01, 2009 3:03 am UTC
Re: Fast algorithm for finding minimum energy line
zed0 wrote:Are you trying to find a minimal path from one point to another or are you specifically looking for a straight line?
A straight line.
WarDaft wrote:The trivial solution is a line that crosses the darkest corner only. It is very unlikely that another line will cross more of the image with less lightness encountered. If this is not acceptable, how much of the plane must it cross? Does the distance the line spends over a pixel count, or only the fact that it crosses that pixel?
The line must cross the entire plane. If it simplifies things here we can say we are looking for the maximum energy line instead.
I'm interested in algorithms with any variation of the other details of how lines cross pixels.
I like the variation where the line is said to cross the pixel in each column that contains the longest length of line (and if there are multiple such pixels it is the topmost of them).
Not a bad idea.jaap wrote:Simulated Annealing
eta oin shrdlu wrote:The "bruteforce" algorithm you suggest is essentially the Hough transform (or the related Radon transform); this is not really a "fast" algorithm, but it is one of the standard linedetection methods.
Is there any indication that it is the fastest possible algorithm for solving the problem?
 eta oin shrdlu
 Posts: 451
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: Fast algorithm for finding minimum energy line
I don't really know (this isn't my field). However, I think it is considered useful in highnoise images, but if the image is sufficiently clean there are probably faster local methods.somebody already took it wrote:eta oin shrdlu wrote:The "bruteforce" algorithm you suggest is essentially the Hough transform (or the related Radon transform); this is not really a "fast" algorithm, but it is one of the standard linedetection methods.
Is there any indication that it is the fastest possible algorithm for solving the problem?

 Posts: 310
 Joined: Wed Jul 01, 2009 3:03 am UTC
Re: Fast algorithm for finding minimum energy line
If anyone's interested I figured out a way to things speed up a bit without resorting to local search methods.
It is possible to prune lines that exceed the energy of the minimum energy line found so far without having to look at every pixel on them. I'm not sure if this will improve the worst case time complexity but it should provide a substantial improvement for the average case.
Furthermore, we can get even better results using a recursive pruning approach where we recursively divide the image in half, and then prune the lines in the right half that exceed the energy of the extension of the minimum energy line in the left half into the right half.
I'll be happy to elaborate this further upon request.
It is possible to prune lines that exceed the energy of the minimum energy line found so far without having to look at every pixel on them. I'm not sure if this will improve the worst case time complexity but it should provide a substantial improvement for the average case.
Furthermore, we can get even better results using a recursive pruning approach where we recursively divide the image in half, and then prune the lines in the right half that exceed the energy of the extension of the minimum energy line in the left half into the right half.
I'll be happy to elaborate this further upon request.
Who is online
Users browsing this forum: No registered users and 6 guests