What you're describing is the Segmentation Problem. I'm sorry to say that it's actually an unsolved problem. But one method I would recommend for this is a Graph-Cut based algorithm. Graph-Cut represents the image as a graph of locally connected nodes. It subdivides connected components of the graph recursively such that the border between the two sub-components is of minimal length using the Max-flow-min-cut theorem and the Ford Fulkerson algorithm.
Essentially, you connect all of the water tiles into a graph. Assign weights to the edges in the graph which correspond to differences between the adjacent water tiles. I think in your case, all the weights could be 1. You will have to play with different weighting schemes to get a desirable result. You might have to add some weight that includes adjacency to coasts, for instance.
Then, find all the connected components of the graph. These are obvious seas/lakes and so on.
Finally, for each connected component, recursively subdivide the component such that the edges connecting the two new sub-components have minimum weight. Keep recursively subdividing until all the sub-components reach a minimum size (i.e like the maximum size of a sea), or if the edges cutting the two components have too high a weight. Finally, label all the connected components that remain.
What this will do in practice is cut the seas from each other at channels, but not accross big spans of oceans.
Here it is in pseudocode:
function SegmentGraphCut(Map worldMap, int minimumSeaSize, int maximumCutSize)
Graph graph = new Graph();
// First, build the graph from the world map.
foreach Cell cell in worldMap:
// The graph only contains water nodes
if not cell.IsWater():
continue;
graph.AddNode(cell);
// Connect every water node to its neighbors
foreach Cell neighbor in cell.neighbors:
if not neighbor.IsWater():
continue;
else:
// The weight of an edge between water nodes should be related
// to how "similar" the waters are. What that means is up to you.
// The point is to avoid dividing bodies of water that are "similar"
graph.AddEdge(cell, neighbor, ComputeWeight(cell, neighbor));
// Now, subdivide all of the connected components recursively:
List<Graph> components = graph.GetConnectedComponents();
// The seas will be added to this list
List<Graph> seas = new List<Graph>();
foreach Graph component in components:
GraphCutRecursive(component, minimumSeaSize, maximumCutSize, seas);
// Recursively subdivides a component using graph cut until all subcomponents are smaller
// than a minimum size, or all cuts are greater than a maximum cut size
function GraphCutRecursive(Graph component, int minimumSeaSize, int maximumCutSize, List<Graph> seas):
// If the component is too small, we're done. This corresponds to a small lake,
// or a small sea or bay
if(component.size() <= minimumSeaSize):
seas.Add(component);
return;
// Divide the component into two subgraphs with a minimum border cut between them
// probably using the Ford-Fulkerson algorithm
[Graph subpartA, Graph subpartB, List<Edge> cut] = GetMinimumCut(component);
// If the cut is too large, we're done. This corresponds to a huge, bulky ocean
// that can't be further subdivided
if (GetTotalWeight(cut) > maximumCutSize):
seas.Add(component);
return;
else:
// Subdivide each of the new subcomponents
GraphCutRecursive(subpartA, minimumSeaSize, maximumCutSize);
GraphCutRecursive(subpartB, minimumSeaSize, maximumCutSize);
EDIT: By the way, here's what the algorithm would do with your example with a minimum sea size set to around 40, with a maximum cut size of 1, if all the edge weights are 1:
By playing with the parameters, you can get different results. A maximum cut size of 3, for instance, would result in many more bays getting carved out from the main seas, and sea #1 would get subdivided in half north and south. A minimum sea size of 20 would result in the central sea getting divided in half as well.