Fast algorithm for finding minimum energy line

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

somebody already took it
Posts: 310
Joined: Wed Jul 01, 2009 3:03 am UTC

Fast algorithm for finding minimum energy line

Postby somebody already took it » Tue Aug 02, 2011 2:37 am UTC

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...

User avatar
zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

Re: Fast algorithm for finding minimum energy line

Postby zed0 » Tue Aug 02, 2011 7:48 am UTC

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.

User avatar
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

Postby Xeio » Tue Aug 02, 2011 3:04 pm UTC

I'm assuming Dijkstra's algorithm would be something like what you want. Assuming pathing is what you're trying to do.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Fast algorithm for finding minimum energy line

Postby WarDaft » Tue Aug 02, 2011 4:39 pm UTC

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.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Fast algorithm for finding minimum energy line

Postby jaap » Tue Aug 02, 2011 5:19 pm UTC

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.

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Fast algorithm for finding minimum energy line

Postby eta oin shrdlu » Tue Aug 02, 2011 9:02 pm UTC

The "brute-force" 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 line-detection 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.

somebody already took it
Posts: 310
Joined: Wed Jul 01, 2009 3:03 am UTC

Re: Fast algorithm for finding minimum energy line

Postby somebody already took it » Wed Aug 03, 2011 2:20 am UTC

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 top-most of them).

jaap wrote:Simulated Annealing
Not a bad idea.

eta oin shrdlu wrote:The "brute-force" 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 line-detection methods.

Is there any indication that it is the fastest possible algorithm for solving the problem?

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Fast algorithm for finding minimum energy line

Postby eta oin shrdlu » Wed Aug 03, 2011 9:36 pm UTC

somebody already took it wrote:
eta oin shrdlu wrote:The "brute-force" 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 line-detection methods.

Is there any indication that it is the fastest possible algorithm for solving the problem?
I don't really know (this isn't my field). However, I think it is considered useful in high-noise images, but if the image is sufficiently clean there are probably faster local methods.

somebody already took it
Posts: 310
Joined: Wed Jul 01, 2009 3:03 am UTC

Re: Fast algorithm for finding minimum energy line

Postby somebody already took it » Mon Sep 26, 2011 11:09 pm UTC

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.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests