An image coloring problem

Question

I have a large collection of microscopy images of cell cultures. Each image consists of $10^{10} \times 10^{10}$ pixels. These images have been "segmented", meaning that their pixels have been partitioned into disjoint sets (aka regions) corresponding either to the background or to individual cells. I'm looking for a reasonably efficient algorithm to assign "colors" to these regions so that no two adjacent regions have the same color, and the number of colors used is "small".

In principle, 4 colors should do, but the problem of finding a 4-coloring for a partition of a plane region into disjoint subregions is NP-hard.

Nevertheless, this statement (and the 4-color problem in general) applies to a more general situation (e.g. arbitrarily complex shapes) than the one I am dealing with, so I'm alert to the possibility that some features of this special case may make the problem reasonably tractable in practice.

First, typically most of the cell regions are in fact isolated (i.e. they are surrounded entirely by background), so the problem of assigning a color to them is trivial. Second, even when there are adjacent cell regions, these regions have relatively "well-behaved" shapes: they are basically roundish blobs, with no weird curlicues, etc. In fact, any two pixels in a cell region are connected by a taxicab-path consisting of pixels all belonging to the region. (By taxicab-path I mean one in which the Manhattan distance between adjacent pixels is always 1; i.e. each step along the path is either vertical or horizontal.) Also, there is some leeway on the exact boundary of these regions, so it may be acceptable to modify the segmentation algorithm in such a way that the resulting regions are more easily colorable.

I have not found any prior work on coloring that attempts to exploit the features described above, so I thought I'd ask here.

It may very well be that these features of my special case do not result in any simplification of the 4-coloring problem, in which case an algorithm that can efficiently produce a 5-coloring, or even a 6-coloring, would be adequate.

Thanks in advance for your suggestions,

kj

Answer 1

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.