Number of islands on a map

Question

I've got a map (a picture on a computer) and I'd like to count the islands (whatever the size). I've thought of x and y projections before counting 1D values but it only works for small numbers and not for specific dispositions. Is there a known and efficient algorithm to do that? Thanks.

Is the map some pixel image with one value for land and one for water? In this case, you might want to count connected components. This can be done with a modified search algorithm, like depth-first search or breadth-first search. For each pixel that is land that is not yet marked, do a search and mark everything connected. The amount of iterations is the amount of connected components. — Aziuth, Feb 24 '16 at 17:09
Maybe share an image. Maybe say what OS and what tools you are familiar with and have available. Maybe say how you intend to use the answer - e.g. simple number needed, or some further calculations are necessary... — Mark Setchell, Feb 24 '16 at 17:14
I don't know if it'll be helpful, but I'm thinking [Battleship](https://en.wikipedia.org/wiki/Battleship_(game)) :) — 500 - Internal Server Error, Feb 24 '16 at 18:02
@Mark Setchell: An example can be downloaded at http://dl.free.fr/bcEAI5SBy where pixels are listed with only a value (more than 4000 is the sea, less than 50 is earth). I'm using Windows 7 (but I can use Ubuntu too) and I only want to be able to count the number of separated islands. I can use many different tools, I just want a general algorithm. — Romain Michard, Feb 25 '16 at 09:28
Mmmmm... quel beau format de fichier! Where can I see the dimensions please? Can you get it in a more conventional image format at all? I am guessing it is 128x128? — Mark Setchell, Feb 25 '16 at 09:32
@Romain Michard: If you use tools, you don't need an algorithm. If not, again, go with a search algorithm and modify it: https://en.wikipedia.org/wiki/Breadth-first_search (replacing graph nodes by pixels with a neighborhood) — Aziuth, Feb 25 '16 at 09:57
@biziclop: As far as I understand, flood-fill is usually either based on DPS or BFS and therefore basically the same. Am I wrong? In any case, complexity is linear. — Aziuth, Feb 25 '16 at 10:45
@Aziuth You're right, they're both essentially the same, but floodfill can further exploit the fact that we're talking about a 2D grid: you can use scanline fill for example. — biziclop, Feb 25 '16 at 10:50

Mark Setchell · Answer 1 · 2016-02-25T09:54:31.253

Updated Answer

Ok, it seems you don't really have a map, you just have a list of 16384 numbers each representing land or sea but no indication of the size of the image it corresponds to - which isn't going to help you determine the adjacency of any pieces of land!

As there are 16,384 values, let's see what the factors are that could give that size:

1x16,384
2x8,192
...
32x512
64,256
128x128

I tried each of hose by putting a simple PGM format header on the front and converting the result to a JPG but nothing looks recognisable so I can't do anything till you tell me how the file works - with width and height.

{ echo P2; echo 128 128 ; echo 65535; tr " " "\n" < ~/Desktop/image_raw.txt; } | convert PGM:- -auto-level map.jpg

Original Answer

ImageMagick will do that for you quite easily using "Connected Components Analysis". It is installed on most Linux distros and is available for OSX and Windows.

As you haven't provided a map, let's use this one of Hawaii.

Just at the command-line without any programming, you can run:

convert hawaii.png -colorspace gray -negate -threshold 10% \
   -define connected-components:verbose=true               \
   -define connected-components:area-threshold=100         \
   -connected-components 8 -auto-level output.png

Output

Objects (id: bounding-box centroid area mean-color):
  0: 1303x892+0+0 633.0,443.3 1072404 srgba(0,0,0,1)
  7: 273x307+956+489 1074.8,639.4 47500 srgba(255,255,255,1)
  5: 163x132+825+330 898.1,395.2 12978 srgba(255,255,255,1)
  3: 145x116+509+188 580.6,251.7 9895 srgba(255,255,255,1)
  1: 117x96+210+79 271.3,124.5 8407 srgba(255,255,255,1)
  4: 139x56+702+291 769.9,317.9 5598 srgba(255,255,255,1)
  6: 71x61+752+353 787.5,381.5 3087 srgba(255,255,255,1)
  2: 58x72+119+121 147.3,157.1 2407 srgba(255,255,255,1)

That tells you there are 7 islands - one line per island plus one for the whole image = the first one.

I can box them in like this:

convert hawaii.png -stroke red -fill none -strokewidth 1 \
  -draw "rectangle 956,489 1229,796"                     \
  -draw "rectangle 825,330 988,462"                      \
  -draw "rectangle 509,188 654,304"                      \
  -draw "rectangle 210,79 327,175"                       \
  -draw "rectangle 702,291 841,347"                      \
  -draw "rectangle 752,353 823,414"                      \
  -draw "rectangle 119,121 177,193"                      \
  boxed.png

It's a 128x128 image and I don't really know if it's a good example. — Romain Michard, Feb 25 '16 at 12:27
I like your Hawaii example, it's exactly what I mean. OK for the command-line instructions. What I'd prefer is to understand what (and how) is done, the algorithm I have to implement. The goal is to program an FPGA that can acquire the map and has to count how many islands there are. I'd really want to understand the needed algorithm. (by the way: how to change line in a comment?) — Romain Michard, Feb 25 '16 at 12:42
There is a good example here https://en.wikipedia.org/wiki/Connected-component_labeling — Mark Setchell, Feb 25 '16 at 12:53
And an implementation in C by me here... http://stackoverflow.com/a/27930239/2836621 — Mark Setchell, Feb 25 '16 at 12:55
And when you get a proper image, just run it through the very first one of code in my answer here to get a JPEG out of it. — Mark Setchell, Feb 25 '16 at 12:56
It's exactly what II want. I'm not english and couldn't think about the word "blob" but now it's clear. Thank you for your help. — Romain Michard, Feb 25 '16 at 14:46

Number of islands on a map

1 Answers1