An image coloring problem
I doubt your features simplify the problem at all, but it's very easy to 6-color a planar graph: find and remove a vertex of minimum degree, color the remaining graph recursively, put back the removed vertex, and give it a color that's different from all of its neighbors.

If you maintain an array indexed by vertex degree, with a list of the vertices with that degree in each array cell, and move the vertices to different lists when a removal causes their degrees to change, then you can find the minimum degree vertex by scanning the array from low to high degrees, and the overall algorithm will be linear time.

This also has the advantage that it automatically and quickly takes care of the completely surrounded regions: they have degree one, so they're dealt with first.

I think the best known time bound for 4-coloring planar graphs is still larger — more specifically, $O(n^2)$ from the work of Robertson, Sanders, and Thomas in the mid-1990s. But there are more complicated methods for 5-coloring planar graphs in linear time; one relevant reference is the paper by Hagerup, Chrobak, and Diks in ICALP 1987, and another is by Frederickson in IPL 1984.