Monday, October 26, 2020

The Revolving Door between Color Science and the English Department

Past Hue Angles columns have featured examples of career changes from color science to other areas. (See Issue #250 [2011] on Terry Benzschawel’s transition to Wall Street quant and Issue #475 [2016] on Mike Stokes’s transition to data privacy.) 

In this article, I describe Suguru Ishizaki’s transition from color science to an English department. Such experiences can inspire hope for successful career transitions in the field of color science even in the current job crisis.

Ishizaki’s contribution to color science is heralded by his 1994 Color Imaging Conference paper [1], also extended in a successive paper [2]. He undertook the prodigious task of coloring sub-areas on a color-coded map or chart so that each sub-area, subject to spatial induction from its neighbors, would match an intended color in the key to the chart. The task is hard because every time you change a sub-area color, you must also change the neighboring areas to preserve all the color matches with the key. The process is iterative and multi-dimensional. To my knowledge, Ishizaki’s is the first and only attempt to capture and control such complicated and inter-dependent conditions for asymmetric matches. (Usually investigators look at only a center field as influenced by a single surround, and do not ask the matching question.)

Starting with this work (which led to his Ph.D. at the MIT Media Lab), Ishizaki built a career, alternately in academia and industry, based on a broader over-arching theme of human communication through design. He started at the Design School at Carnegie Mellon University (CMU), then worked at Qualcomm on early mobile applications, and ended up at CMU’s English Department, where he is now an Associate Professor. Dr. Ishizaki’s current research area is Technology-Enhanced Learning for writing and Computer-Assisted Rhetorical Analysis [3].

Several people I know started as English majors and ended up in color science. Bob Karpowicz, who became a product manager at Datacolor, had an undergraduate English major. Mike Tinker (who became an expert in color digital cinema at Sarnoff) started from a B.A. in English literature; then, as a graduate student in English, he wrote a computer program that recognized writers by their word patterns. That wasn’t accepted as a thesis topic, so Tinker pursued another topic to a Ph.D. in English with a minor in computer science. 

And I myself was an undergraduate English major, though this is unacknowledged on my diploma due to a binary choice being given to me on graduation day. (How English departments have changed since then!)

But whereas in all these cases the door of the English department was marked “Exit,” Dr. Ishizaki found a door marked “Enter.” I hope someday that he returns to color science to continue the career he started and that nobody else can match. Or perhaps someone else will continue his pivotal work.

[1] Ishizaki, S. Adjusting simultaneous contrast for dynamic information display. Proceedings of IS&T and SID's Color Imaging Conference, Scottsdale, 1994: pp 137- 140. 

[2] Ishizaki, S. Color adaptive graphics: what you see in your color palette isn’t what you get! CHI ’95: Conference Companion on Human Factors in Computing Systems. May 1995, pp. 300-301.

[3] https://design.cmu.edu/people/courtesy-appointment/suguru-ishizaki


Michael H. Brill

Datacolor


Monday, August 24, 2020

Why Colors Show Up as Icons in Mathematics

 In eerie resonance with Euclid’s definition of a point as “that which has no part,”  J. Lettvin’s Colors of Colored Things begins with the following: “Judgment of color (including brightness) seems not to depend on extension [… Redness] is like nothing else but itself, it cannot be decomposed or described, but only exhibited; it is a simple.” [1]  Lettvin goes on to discuss (in his unique way) the familiar complications of how vision transforms stimuli into color, but he retains the view that the judgment of color is a simple. I will now look at some implications of this idea.

Color as a simple is readily added to a geometrical object, and the color icons enrich the meaning. Examples range from traffic signals to the stylized footprints in an Arthur Murray dance studio. But mathematics offers some particularly interesting morsels. Three come to mind. One of these, the four-color map problem has been described in an earlier Hue Angles [2]. Another shows up in the title of Arthur Loeb’s book Color and Symmetry [3], in which permutations of color coding in a pattern enrich the geometric symmetries incurred by such operations as glides and reflections. Now I want to introduce you to a third, perhaps less familiar example, the road-coloring problem.

 

The road-coloring problem involves a network with directed paths between pairs of vertices. Under some surprisingly general conditions, it is possible to color-code the paths so that, given a destination vertex, a single set of instructions in the form of a sequence of color choices will bring you from any source vertex to the same destination vertex. The Wikipedia article on the road-coloring problem sets the context: “In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from.”  You start with a graph with numbered vertices and colored arrows between the vertices. The arrows are like one-way streets: the instructions (a sequence of path colors) assume you are always going in the direction of the arrow you’re on. To convince yourself that this behavior is possible, try the exercise based on the eight-vertex graph in Ref. [4]. 

 

The road-coloring problem started as a conjecture by Benjamin Weiss in 1970, but it took 38 years to prove. The proof came from Avraham Trahtman, a 63-year-old Israeli former security guard (who was a mathematician in his earlier life in the USSR) [5]. Trahtman [6] proved not only that the nominated graphs all had coloring sequences with the desired property, but also that one’s mathematical life can peak long after one’s teens and twenties.

 

Encouraged by checking the eight-vertex graph in Ref. 4, I wondered if I could make a simpler graph with only three nodes that had the same property. In the figures I show here, three nodes support two possible solutions, but I had to allow the possibility of paths from a node to itself. 

  


Drawing of two three-vertex road-coloring solutions (author, 2013).  The medium is felt marker on flip-chart paper, photographed in a cool-white-fluorescent-lit office.  Not surprisingly, the “red” looks very orange. My apologies, but I hope the idea is clear.


In the case of my first graph, if you live at vertex 1, all you have to tell your visitor is “take the red arrow from where you are to the next vertex (in the direction indicated by the arrow), and that will be node 1. That’s what I mean by the instruction R1 from anywhere (i.e., from vertex 1, 2, or 3). Similarly, if you live at vertex 2, your instruction is “take the green path one step from wherever you are.” If you live at vertex 3, your instruction is “take the blue path.” Because the arrows are like one-way streets, you must always go in the direction of the arrow you choose. 

 

In the second graph, there are still only three vertices, but the paths involve two steps and not just 1. Starting from vertex 1, 2, or 3, if you take two R steps, you end up at vertex 1. I denote that action as RR1, etc. But notice that I use only two colors of path instead of three (as in my first graph). There is a tradeoff between the number of colors and the length of the instruction string. 

 

What use is the road-coloring problem (now a theorem)? It serves very well in the theory of automata. To quote Weifu Wang [7], “When the automaton is running and encounters an error, and if the road coloring conjecture is true, the automaton can always follow a certain sequence and go back to the previous correct state, regardless of what error it encountered.” I think the “correct state” is the address of the person giving the instructions, and the “error state” is where the presumed visitor is when he gets instructions. It’s a little confusing to call the direction “back” when you’re proceeding forward along the arrows to get there. But synchronizing a move to an earlier known state seems the key to the application.

 

One place not to use the road-coloring theorem is in an Arthur Murray dance studio. Imagine giving a color-sequence instruction set to a bunch of dancers and have them all pile on top of each other when they (synchronously) reach the home vertex.

 

[1] J. Y. Lettvin, MIT RLE QPR 87, 1967, p. 193,  dspace.mit.edu/bitstream/handle/1721.1/55670/RLE _QPR_087_XIV.pdf   

[2] M. H. Brill, http://hueangles.blogspot.com/2013/03/

[3] A. Loeb, Color and Symmetry, Wiley, 1971.

[4] https://en.wikipedia.org/wiki/Road_coloring_theorem

[5] http://usatoday30.usatoday.com/tech/science/mathscience/2008-03-20-road-coloring-problem-solved_n.htm

[6] A. N. Trahtman, The Road Coloring Problem. Israel Journal of Mathematics, Vol. 172, 51–60, 2009

[7] W. Wang, The Road Coloring Problem. (2011). https://math.dartmouth.edu/~pw/M100W11/weifu.pdf

.

Michael H. Brill

Datacolor