The Treasure Island Problem, Distance Transform (Algorithms)

I never wrote about image processing in my blog, and I’m ashamed of it because I just love it so much. I don’t want to tell that I’m particularly good in it, but I can tell it fascinates me. Friday, I came across the following problem:

[Treasure Island Problem, TIP] You are a pirate and you are in the Treasure Island. The Treause Island is a big, flat island, treasures are buried there but there are also traps, mines, trapping pits, etc. You have something like a treause map, which is a 2D array, an image in our case.  Each pixel of the image represents a nine feet long and nine feet wide pice of the island. Some places contain treasures (their pixels are marked with green on the map), other parcels contain traps or they are completely inaccessible, these pixels are red on the map. Suppose you know your current location on the image, you know exactly, which pixel belongs to your location. Your job is to find the shortest path between your position and a treasure, that doesn’t contain red pixels. The pixels are 8-connected (you are able to move in cardinal and diagonal directions), each cardinal step costs 1, each diagonal step cost sqrt(2).

So, I had to solve this problem for hundred of pirates (they were  on the same island and each pirate wanted to know the direction of the nearest treasure), and I was thinking of that maybe the distance transform can help to solve this problem. “The map labels each pixel of the image with the distance to the nearest obstacle pixel.” (http://en.wikipedia.org/wiki/Distance_transform) When the “obstacle pixels” are the treasures, then the distance map (== the result of the distance transform) gives a value for each pixel, which value is the distance of the nearest treasure. If you have a distance map, you have to examine the values of the neighboring pixels of your current location, and you have to move in the direction which satisfies the equation: dmap(myself)= cost + dmap(neighbor(dir)). (Be careful! It is not always the smallest value!)

The traps make the problem much harder. Without traps, we could use a two-pass DT algorithm in no time, with traps, it is not so simple. And think about, with traps, it is a whole different story. Let’s assume that we have a N x N Treasure Island. Without traps, the biggest possible distance value on the map is about sqrt(N). (We use the special distance function which is described in the text of the problem.) With traps, the biggest possible distance value is about N/2. (E.g. the famous zig-zag pattern, the odd lines are almost completely blocked, there is only one gate at the start or at the end of the line).  The traps can separate the different segments of the image, the modification of one pixel can cause that the treasures will be completely inaccessible from some segments.

So, how shall we solve the TIP? The following algorithm based linked pixel lists. The basic idea, that when we have a linked list which stores a set of special pixels,  then we can visit these pixels in O(n) time and we can construct the list of the set of their neighbors in also O(n) time. Examine the following operations, opA and opB:

Let S[n] the set of the pixels whose map values are “n”. So S[0] is the set of the green (== treasure) pixels. (We can read the whole image pixel by pixel, so we can construct the S[0] in O(k) time, where k is the number of the pixels of the image.) S[1] = opA(S[0]) and S[sqrt(2)] = opB(S[0]). It is trivial, but S[1+sqrt(2)] = opA(S[sqrt(2)]) + opB(S[1])) is a bit harder. It says we can produce the value 1 + sqrt(2) in two different ways and we have to create the union of the sets of the two different cases. Suppose, the linked lists are disjoint, then the union of sets means the concatenation of the corresponding linked lists, and we can perform it in O(1) time when we store pointers to the first and last elements of lists. Using disjoint linked pixel lists is the first idea.

The second idea is that we can store the pointers of the list links on an image, which has the same size than the original image (== imop, like imageOfPointers). We initialize the image with a magic value (f.e. -1), then we store the pointer of the pixel “k” at imop[k]. We have also an “EOL” (end of list) symbol (f.e. zero, it means the pixel points to itself). In this case, we can check in O(1) time, whether a pixel is an element of a list or not. (When its pointer is not (-1), then it belongs to a list.) Let’s assume, that we generate the S[k] sets in ascending order and the opA and opB check always whether a neighboring pixel is an item of an existing list or not. When it is, it has a smaller or equal value than k. (When it were not true, then it would belong to an S[j], j>k set and it would be inconsistency, because S[j] would be generated before S[k] and it is not an ascending order.) So the third idea, that we must generate the S[k] sets in ascending order.

The last idea is a cheat. It is pretty hard to decide which one is greater: 99 or 70sqrt(2). In other words, it is pretty hard to sort the “a + sqrt(b)” values in ascending order. It is too hard, so we don’t do it. The fourth idea, that we use the sqrt(2) = 1.5 approximation. It solves two problem: first, it makes the sorting trivial, second, there are no floating point values, we don’t need to struggle floating point numbers, it makes the whole algorithm faster. It causes about a 6,4 percent error, but personally I can live with that. (Actually I can live with much worse things.)

With these four ideas we can construct a nice O(n) algorithm to (approximately) solve the Treasure Island Problem. I could describe the whole algorithm step by step, but I don’t do it. I just insert here a picture, because a picture worth a thousand words. It shows the first steps of the algorithm which is performed on a small board:

When I will have time, I will attach the C++ implementation of the algorithm. Be patient and thank you for your attention. (A small note: I used the DT in my master’s thesis too. “If you have a hammer, everything looks like a nail.” Sad, but it is also valid for me.)

Advertisements

About vrichard86

I'm Richard and I'm an enthusiastic coder. I want to be better and I think a professional journal is a great self improvement tool. Welcome to my blog, to my hq, to my home on the web!
This entry was posted in Algorithms and tagged , , , . Bookmark the permalink.