The Seams of Death

The Seams of Death is this problem I've been working with on and off for the past few months, getting more or less nowhere. "Seams" is what the problem is about, and "Death" is how I feel when I'm getting nowhere. But it's a really cool problem, so I can't hate the problem itself. If there are any interested mathematicians reading this, any tips or a solution would be fantastic! So, the problem:

Seam carving is a cool semi-intelligent algorithm for scaling images. Let's say you want to reduce an image's width but not the height. If you just scale it regularly, the features will be compressed; if you crop it, you will just lose some from the edges. Seam carving instead removes a seam, a string of pixels from the top row to the bottom row, each connected either vertically or diagonally to the next. In particular, it removes the seam of lowest energy (for some predefined energy function like contrast or color or something more complex).

This problem is not actually about carving itself. Rather, I'm interested in finding the total number of such vertical seams in an image (say of width w and height h). An exact closed form solution, not a bound. It's not hard to construct a decent bound. If the edges didn't exist, then for each pixel we'd have 3 ways to go to the next row-down to the right, down to the left, and straight down. Starting from any of the top pixels, then, we'd get (w*3^(h-1)).

It's also not hard to construct a recurrence/algorithm to recursively/dynamically calculate the count. Most simply, you could just start at the bottom and fill upwards. For instance, for a 3x5 image:

5 8 9 8 5

2 3 3 3 2

1 1 1 1 1

The sum of the top row is 35, so that is the number of seams in the image.

But I want an actual equation, or at least a sum that I can evaluate in sub-linear time. It turns out that counting the paths that fall of the edges is not as simple as I thought it would be. In computer science, edge cases are always important, but for this particular question, the edges are the entire problem. :P