9
$\begingroup$

We can write:

MorphologicalComponents[image] // Colorize

To assign a random set of colors to each component in some image. The example used for reference by Mathematica is a map of the United States: http://reference.wolfram.com/mathematica/ref/Colorize.html?q=Colorize&lang=en

My question is - is it possible to ask Mathematica to specify that any two adjacent colors should have some minimum threshold distance in in their hue or RGB values (e.g. http://en.wikipedia.org/wiki/File:Map_of_United_States_vivid_colors_shown.png)? I believe asking for a four-coloring of a map is computationally non-trivial, but are there any built-in routines, perhaps with the graph analytics packages in Mathematica, to allow for this?

Let's define two morphological components as adjacent if the line segments spanning the shortest distance between the two components fails to intersect any other morphological components. We can also include a distance $D$ cutoff for defining two components as adjacent. I'm certainly open to stricter definitions.

|improve this question
$\endgroup$
  • $\begingroup$ Related Stan Wagon's article library.wolfram.com/infocenter/Articles/1157 $\endgroup$ – Dr. belisarius Jul 10 '13 at 18:32
  • $\begingroup$ Can you elaborate more, what you exactly mean when you say adjacent color? Remember, that morphological components color objects which are not connected to each other. $\endgroup$ – halirutan♦ Jul 10 '13 at 20:01
  • $\begingroup$ @halirutan I've updated to question to offer a definition. Please let me know if you find issue with it. $\endgroup$ – SnowTrace Jul 10 '13 at 20:08
  • $\begingroup$ If you figure out how to build the adjacency graph, then you can use one of the several colouring functions from IGraph/M. Minimum colouring is also supported so you can get a 4-colouring that way. $\endgroup$ – Szabolcs May 1 '18 at 13:15
12
$\begingroup$

I believe asking for a four-coloring of a map is computationally non-trivial,

In theory, yes. [[Well, I should add that I think it has not been proven to be of non-polynomial time.]] But in practice, getting a 4-coloring can be done quickly. My book, Mathematica in Action has chapter 17 devoted to this topic. Kempe's 1879 method works fine almost always. If it does get stuck, as Heawood in 1892 pointed out is possible, one can just start over with a permutation of the graph. We have found this idea (only sketchily discussed here) works very well and has no problem 4-coloring the graph made from all 3300+ counties in the USA.

The code in Chapter 17 includes code to 4-color planar graphs and, slightly more complicated, planar maps (such as the Martin Gardner hoax from April Fools Day, 1975).

|improve this answer
$\endgroup$
  • $\begingroup$ Very nice... +1 $\endgroup$ – halirutan♦ Jul 11 '13 at 9:27
  • 3
    $\begingroup$ Stan, would you care to post some minimal example? $\endgroup$ – Yves Klett Jul 11 '13 at 9:53
  • 1
    $\begingroup$ Note sure how to post art on this site. Here is a PDF with some diagrams illustrating my points. $\endgroup$ – stan wagon Jul 12 '13 at 13:47
0
$\begingroup$

I'm not entirely sure, but I believe in general this is not possible, because you can construct situations where you cannot guarantee that you have enough colors with a certain distance from each other.

One very simply construction is the following

img = Binarize@
   Rasterize[
    PolarPlot[2 {Sin[20 t], Cos[20 t]}^2 + 2, {t, 0, 2 Pi}, 
     PlotPoints -> 100, MaxRecursion -> 5, Axes -> False, 
     PlotStyle -> AbsoluteThickness[2]], "Image", 
    ColorSpace -> "Grayscale"];
MorphologicalComponents[img] // Colorize

Mathematica graphics

In this construction you have the color in the middle of the circle needs virtually an unlimited amount of color which have the required minimum distance in color space. Additionally, you have to outside blue-greenish color which needs the same property and finally, every color on the circle as 2 neighbors for which you need to ensure the distance.

Taking this as starting point, you can easily think of more complicated constructs having far more neighboring colors. Since the rgb-cube (or whatever color-space representation you choose) is a finite volume, I believe in general you cannot always create a coloring with the required property.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Doesn't the four-color theorem guarantee us a solution where every border can be between two (simply connected and contiguous) countries of different colors? I'm not requiring that every border for a country requires a distinct pair of colors. $\endgroup$ – SnowTrace Jul 10 '13 at 20:55
  • 3
    $\begingroup$ A four-coloration of your example might be to color to two big components in the center and outside contour RED and BLUE respectively, and then to alternatively color the small ellipsoids YELLOW and GREEN going around the circle. That would satisfy my definition of "adjacent" where a "border" implies that a line can be drawn between two components without intersecting any other components. $\endgroup$ – SnowTrace Jul 10 '13 at 21:04
  • $\begingroup$ @SnowTrace Would you mind joining the chat? Maybe we can discuss this better there. $\endgroup$ – halirutan♦ Jul 10 '13 at 21:05
  • $\begingroup$ Hmm... I need a bit more reputation for that. If you can wait a bit, I'll join in later. $\endgroup$ – SnowTrace Jul 10 '13 at 21:09
  • $\begingroup$ @SnowTrace Try now. $\endgroup$ – halirutan♦ Jul 10 '13 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.