Computational Imaging for Robust Sensing and Vision

In the early days of digital imaging, we were excited about having the images in numerical form and not being bound by the laws of physics. We had big ideas and quickly ran for their realization. However, we immediately reached the boundaries of the digital world: the computers of the day were too slow to process images, did not have enough memory, and the I/O was inadequate (from limited sensors to non-existing color printers).

Now has finally come the time when these dreams can be realized and computational color imaging has become possible, thanks to good sensors and displays, and racks full of general purpose graphical processing units (GPGPUs) with hundred of gigabytes of primary memory and petabytes of secondary storage. All this, at an affordable price.

Wednesday, 12 April 2017, Felix Heide gave a talk at The Stanford Center for Image Systems Engineering (SCIEN) with the title Capturing the “Invisible”: Computational Imaging for Robust Sensing and Vision. He presented three implementations.

One application is image classification. In the last couple of years we have seen what is possible with deep learning when you have a big Hadoop server farm and millions of users who provide large data sets they carefully label, creating gigantic training sets for machine learning. Felix Heide uses Bayesian inference to implement a much better system that is robust and fast. It better leverages the available ground-truth and uses proximal optimization to reduce the computational cost.

To facilitate the development of new algorithms, Felix Heide has created the ProxImaL Python-embedded modeling language for image optimization problems, available from www.proximal-lang.org.

OLED TVs are here

OLED displays for handheld devices have been around for a while, but large TVs have been rare due to manufacturing difficulties. LG group has been one of the few manufacturers. At the end of October, Panasonic has introduced a 65 inch 4K ultrahigh definition TV in Europe. It combines LG's OLED panel with Panasonic's image processing technology.

Despite a high price of 10,000€, the TVs are selling well. If in the past the rule was that your display can never be too bright, now the rule is that your display's gamut is never too big.

Link to article

Illusion of a dress

Earlier this week I wrote about color not being a physical phenomenon, but rather an illusion taking place in our mind. I also wrote about Hunt's problem of completing a wardrobe. Hunt's example is a motivation for colorimetry. When we can keep constant the illuminants and observers, we can use CIE colorimetry and a color management system to closely match color scenes involving ordinary dyes and pigments.

When we can control but not keep constant the illuminants, then we can still do a pretty good job at matching the appearance of colors in a reproduction by using a color appearance model. "Control the illuminant" means we have to know what it is, as Randall Munroe suggests in his xkcd cartoon on the dress.

When we do not know the illuminant, we can estimate it if there is an object in the scene whose color we know. In the dress picture sparking the Internet on 26 February, there is no reference object, no complexion is visible. In this sense, the xkcd cartoon is not a faithful abstraction of the problem at hand because it shows a lot of skin. We would need a second picture were the lady is not wearing the dress. Actually, a nude by itself is not sufficient and the lady should also hold a calibration target, at least the white side of a gray card.

Back in the late 80s and the 90s, Robert Hunt used to teach a course on color science at the RIT. After the course, Roy Berns used to take out Dr. Hunt for a dinner. One year, he took him to a fancy Italo-American restaurant. On the East coast, the fancier a restaurant was, the darker it was, because the cultural understanding was that for a romantic date people would be willing to pay a premium price, but would want a low light level.

As they entered the restaurant, they noticed that the light-bulbs were red and the whole restaurant was imbued in pink. When they sat down at the table, they felt extremely uncomfortable, because they were not able to decide whether the tablecloth was white or pink. After a long discussion and the desperate search for a reference white, Roy Berns finally remembered he had his business card in the wallet and he knew it was white. This allowed them to enjoy their dinner.

In their honor, we should introduce a so-called Hunt-Berns effect: Inability of the cognitive factor to decide on a set. Example: When in an environment with colored illumination the brightest object is not known a priori to be white, the cognitive part of chromatic adaptation fails because it is not possible to establish whether that object is white or has a hue similar to that of the illuminant. This is especially so, if the observer is knowledgeable about the Helson-Judd effect.

This would take care of the illuminant problem by having a second photograph of the lady, this time in the nude and with a white reference target. However, this would not necessarily explain the effect seen in the photograph.

It is pretty obvious from the photograph, that the dress is not Lambertian, therefore the geometric appearance has also to be measured. We would need a spectrogoniometer rather than a simple colorimetric device like a camera, whose white balancing algorithm can get completely duped when confronted with an unexpected target.

As everybody who ever tried to touch up a dent in a car with metallic paint knows, not all surfaces have a color made with a simple dye or pigment based colorant. If for example the color is based on pearlescence or iridescence, you cannot reproduce it on a photograph displayed on a screen. At the very least you need a movie. In this end, you have to examine the original.

Color reproduction is about reproducing an illusion. It will always be hard.

Tic-tac-toe patent 8,770,625 in color

As noted on lines 23 and 24 in column 4 of the printed version of patent 8,770,625,
the U.S. Patent Office procedure discourages the use of color drawings. This makes Fig. 4 a little hard to visualize for the non color scientist (there are no color figures in Wyszecki & Stiles), so here it is in color (right pane):

The invention is relatively simple. The general field is anti-counterfeiting as it applies to packaging. Professional counterfeiters have no problem faking ordinary measures like serial numbers and holograms, so the trick is to embed information that cannot easily be perceived by a counterfeiter, hence is omitted in the facsimile. Fortunately color does not exist in nature, it is just an illusion happening in our minds. Therefore, all we have to do is to create an illusion you can only perceive if you expect it.

As described in patent 8,770,625, a number computed from the—possibly counterfeited—serial number on the package can be encoded positionally in a tic-tac-toe grid. The marking is just above the visual threshold, so the naive counterfeiter will reproduce the same pattern on all packages. The trained inspector can then quickly assert whether an actual positional code corresponds, for example, to the possibly fake serial number.

Patent 8,770,625 is relatively short with just three claims, but reducing it to practice is a little tricky, even when all the steps are disclosed in the patent. The difficult part is to design the tool to determine experimentally the visual thresholds for the print process being used and the light conditions under which the inspections are expected to happen. You need to be skilled in the art.

The above figure is a screen-shot of that tool. To implement it you need to write a spectral color management system with CIE colorimetry to simulate the press on the display and vision colorimetry to model what the actual human visual system perceives. The details of the controls are explained in patent 8,770,625.

Depending on your viewing conditions, the above color version of Fig. 4 might be under the visual threshold. If that is the case, in the figure below we crank up the saliency and decrease the background coverage, so you will see the encoding for sure. If you have aliasing problems, you can click on the figures to display them at the original resolution in which they were created eight years ago, early July 2006 (time flies).

Amorphous iridescence from 3D printer

The research group of Prof. Frank Scheffold at the University of Fribourg has succeed in creating iridescent plastic cylinders with a 3D printer.

Microscopic or nanoscopic structures can make an object appear to have color, without use of pigment. Examples in nature include butterfly wings and bird feathers, but these are ordered, crystalline structures. Using a high definition 3D printer, a research group at the University of Fribourg has produced a new amorphous (non-crystalline) material with interesting capabilities in this field. The material is an irregular network of microscopic plastic cylinders. It selectively reflects light in the infrared range, and also dramatically reduces transparency. The new class of material has a wide range of potential applications, from packaging, automobile paint, and cosmetics to the processing and transmission of optical signals.

Press release

Skin-Whitening

In Japanese culture a white skin is an important component of female aesthetics. In the old days, maikos applied a thick white base mask that was made with lead, but after the discovery that it poisoned the skin and caused terrible skin and back problems for the older geisha towards the end of the Meiji Era, it was replaced with rice powder.

At the end of 2007 it appeared that the cosmetics industry had finally invented a skin whitening product that is both safe and convenient, as we reported in this blog in a whiter shade of pale. Unfortunately it now appears this Rhododenol product is unsafe after all.

2,250 users of Kanebo Cosmetics Inc. skin-whitening cosmetics have reported developing serious symptoms such as white blotches on their skin. Serious effects of the products include depigmentation in an area of at least 5 cm and depigmentation in three or more areas of the body, as well as clearly visible depigmentation in parts of the face. In total, the company has received more than 100,000 inquiries in connection with the recall.

The product in question is named "Rhododenol." Kanebo earlier said it has been marketing cosmetics that use the ingredient as an active substance since 2008 via various retail outlets. The company said it has secured the cooperation of the Japanese Dermatological Association in getting a list of medical facilities which will treat the symptoms posted on the association's website. Kanebo Cosmetics Inc.'s voluntary recall of its skin-whitening line is likely to deal a crippling blow not only to its brand image but also to its parent Kao Corp. It will not be easy to restore the image of the damaged brand. The recall became more damaging due to Kanebo's delayed response.

Proofing a page for color discriminability problems based on color names

Now that there is a physiological basis for color categorization, we can ask ourselves what this is good for. We cannot eat it, but it might have considerable commercial value in United States Patent 8,456,694 issued two days ago on June 4, 2013. I am not a lawyer, but it appears that if you take two colors, determine their names, and then do anything with it, you might have to license this patent (but you can still keep your hippocampus ☺).

In large American corporations, when a new CEO start their new position, they often begin by putting their mark on the company's branding. They remodel their office and maybe even the HQ entrance, tweak the logo, design a new font, change the corporate palette, etc. These endeavors cost millions of dollars, but big corporations can afford it, especially when as a consequence other big corporations get motivated by the new branding to buy more widgets of the new CEO's company.

The only pity is that often this means that entire forests are wasted when the company has to reprint all its marketing collaterals. Around 2000, my employer at the time had a big warehouse in Campbell with product brochures, but fortunately our manager had been able to convince the company to deploy a document management system and print the marketing collaterals on demand, just when they were needed.

The hard problem came when a year later the CEO decided to change the color palette. Although all brochure chunks were stored digitally, when a brochure was produced by combining chunks with the old palette and chunks with the new palette, the resulting brochure looked inconsistent.

Colleagues Hui Chao and Xiaofan Lin quickly wrote code that could perform a wide range of graphical changes to the collaterals in the repository, and this writer wrote a few lines of code that would replace an old palette color with the perceptually nearest color in the new palette. Unfortunately, already the first test run demonstrated that this was a hack that did not work in practice. For example, many chicklets ended up having bright green text on orange background, something chromatically challenged people with color vision deficiencies could not read.

The solution that worked was to use a model to compute the names of the foreground and background colors, then change one of them to the nearest color in the new palette that was at least to color name categories away from the other color. This solution ended up being very good in practice and we wrote very efficient code that could process a large repository in a very short time.

I guess a sign of good engineering is to have the intuition for an unexpected solution before the scientists have worked out all the facts, …and we did not need nuclear bomb explosions.

Extending the printer gamut upwards

Full color printing started with cyan, magenta, and yellow. Then black was added to extend the gamut down in the shadows. Later spot colors were added to make the gamut wider (Hexachrome, Indichrome, etc.). Now Romain Rossier & Roger David Hersch are adding light fluorescent magenta and yellow to extend the gamut up in the light colors. They are presenting their work at the CIC 20^th Conference in Hollywood in the Friday afternoon session on Printing chaired by Jan Allebach. Of course, the slides are limited by the projector's gamut, so you need to be there and look at the actual prints.

Mobile color selection feedback

Commercial color print workflows sometimes require manual intervention to adjust colors, for example to change a background color or the color of rules. Instead of aborting the job, sometimes the color can be changed on the fly. Typically this is accomplished with a color selection tool running on a mobile device, such as a pad computer or a smart phone.

Mobile color selection tools can use the built-in motion sensors for input. For output, due to the limited available screen space, the systems just show a swatch and maybe a color name. We describe a new output design that is well-tailored to motion-sensor based input. Using the right user interface paradigm allows users to work more efficiently, thus cutting costs and increasing profits.

Sometimes a print job requires changing a solid color, for example when the halftoning algorithm creates an unexpected interference pattern (moiré) or when the color does not print well on the particular media. It is then necessary to abort the job and send it back to the client. Such an issue can delay a job for days, possibly causing problems with the service level agreement (SLA).

The previous generation devices like laptops and tablet computers used a graphical user interface (GUI) metaphor known as WIMP, for windows, icons, menus (or mice) and pointing devices. Current mobile devices like slates and smart phones, use a different GUI paradigm known as MPG, for multi-touch, physics and gestures.

As we move beyond WIMPs, the visual feedback metaphors are no longer adequate, because they are optimized for a mouse moving on a two-dimensional plane. Current mobile devices have built-in accelerometers and gyroscopes. With them, movement between points on a plane is replaced with roll, yaw, pitch, and translational movements in three-dimensional space (see this earlier post for an informative video). In this particular implementation, the GUI consists of a colored patch and the color term.

We can provide visual feedback for MPG color selection tools using a rivet metaphor. A rivet is a short metal pin or bolt for holding together two plates of metal, its headless end being beaten out or pressed down when in place. Here are two examples of rivets. Left: Round head. Right: flat head.

Regardless of how the MPG GUI maps the Tait–Bryan angles yaw, pitch and roll, as well as translational movements and acceleration into color specifications, either absolute or relative, we use the image of a rivet to provide feedback.

The rivet head provides feedback on the total available color gamut and the hue at the center of the edge towards the user indicates the currently selected hue correlate. The length of the cylindrical shaft indicates the currently selected lightness correlate. The shaft diameter indicates the chroma correlate.

We anticipate that the user can easily learn the correspondence between MPG input and the effect on the color selection process, thus providing a very effective tool.

The figure below shows the current state of the art for WIMP operating systems. The left window is from the Windows operating system, where the color selection tool has three panels. On the bottom right is a panel showing a patch with the currently selected color and the previous selection. On the bottom left are the RGB counts. The top left is the graphical color selection panel.

Regarding color selection tools in applications, they mostly use the tool provided by the operating system. One notable exception is the color selection tool in Photoshop. This application actually has two color selection tools, one simple and fast for the experienced user, and one more detailed for careful color selection. We describe first the simple tool at the left of the figure below and then the detailed tool at the right.

The simple tool has three panels: a sample patch (actually two: one each for foreground and background), a set of three sliders for RGB counts, and a complex graphical single point selection panel. The single point panel is a rectangle where the abscissa is a correlate for perceived hue. The ordinate is a correlate of saturation, which contains both lightness and chroma. This hue–saturation paradigm allows color specification through a single two-dimensional point, at a possibly increased cognitive cost.

The larger window at the right side of the above figure is Photoshop's detailed color selection tool. On the top right we note the split old and new color patches as in the Windows tool. The slider in the middle is used to select the hue, while the chroma and lightness are selected in the large square at the left. In this square, the abscissa is a correlate of chroma, while the ordinate is a correlate of lightness.

All these tools have evolved from the early days of color GUIs and are optimized for input on a two-dimensional surface with a mouse. The slider interfaces are actually older, when the early interactive graphics workstations had dials for data entry.

Like everywhere else in our lives, also on the print shop floor we transitioned from desktop and laptop computers to mobile devices like pads and smart phones. Parallel to this transition is the paradigm shift from WIMP to MPG GUIs and the visual feedback for three-dimensional input devices must be different from that for two-dimensional devices.

We use a feedback mechanism in the approximate shape of a rivet, which can change its location and orientation in space in accordance to user gestures. This mechanism changes its appearance according to the color being selected.

The rivet head represents the color gamut. It can be either a flat head showing the gamut in a chromaticity diagram, or a three-dimensional head showing the full gamut (with transparency to optionally mark the currently selected color). When users change the hue through a gesture, the rivet rotates along its symmetry axis, so that the currently selected hue is always pointed towards the user.

The shaft is used to represent chroma and lightness. The shaft length is proportional to the current selection's lightness and the shaft diameter is proportional to the current selection's chroma. The shaft itself is colored in the current selection's color.

Yaw, pitch, and roll, also known as Tait-Bryan angles, named after Peter Guthrie Tait and George H. Bryan, are a specific kind of Euler angles used to define the relative orientation of an object with respect to some reference orientation, usually a set of reference axes. The three angles specified in this formulation are defined as the roll angle, pitch angle, and yaw angle. Yaw, pitch and roll are used in mobile devices where the object in question is the handheld device itself.

The figure below illustrates the Tait-Bryan angles. They can be statically defined using a line of nodes constructed by the intersection of two non-homologous planes (for example XZ and xy are not homologous planes), unlike proper Euler angles which use homologous planes (for example XZ and xz).

This second kind of Euler angles is such as it is equivalent to three rotations composed with a different axis, z-y-x for example. There are therefore six possibilities of this kind (xyz, xzy, zxy, zyx, yzx, yxz). They behave slightly differently than Euler angles. In the zyx case, the two first rotations determine the line of nodes and the axis x, and the third rotation is around the axis x.

Because the line of nodes is the intersection of two non-homologous planes the pitch angle is measured from the horizontal plane instead of the vertical axis. Therefore this kind of construction would give a pitch equal to zero for an airplane flying horizontally while the first kind of Euler angles would assign it an angle of π/2.

Since this terminology originates in aeronautics, in this section we use an aircraft instead of a handheld mobile device, but the physics is the same. The concepts are shown in this figure:

Yaw, pitch and roll are used in aerospace to define rotations between a reference axis system (world frame) and a vehicle-fixed axis system (body frame), which in the context of an aircraft sometimes are called its heading, elevation and bank.

Consider an aircraft-body coordinate system (body frame) with axes XYZ which is fixed to the vehicle, rotating and translating with it. This intrinsic frame of the vehicle, XYZ system, is oriented such that the X-axis points forward along some convenient reference line along the body, the Y-axis points to the right of the vehicle along the wing, and the Z-axis points downward to form an orthogonal right-handed system.

Consider a second coordinate system (world frame) with axes xyz, aligned having x pointing in the direction of true north, y pointing to true east, and the z-axis pointing down, normal to the local horizontal direction.

Given this setting, the rotation sequence from xyz to XYZ is specified by and defines the angles yaw, pitch and roll as follows:

• right-handed rotation Ψ ∈ (-180, 180] about the z-axis by the yaw angle
• right-handed rotation θ ∈ [-90, 90] about the new (once-rotated) y-axis by the pitch angle
• right-handed rotation φ ∈ (-180, 180] about the new (twice-rotated) x-axis by the roll angle

The motion of an aircraft is often described in terms of rotation about these axes, so rotation about the X-axis is called rolling, rotation about the Y-axis is called pitching, and rotation about the Z-axis is called yawing.

The equivalent MPG feedback to the WIMP feedback in the above figures is shown on the top side of the figure below. In this example we use the flat head rivet metaphor from the right side of rivet figure above. It is obvious how to generalize to the three-dimensional gamut as mentioned earlier.

the user has selected a dull green

the user has rotated the hue towards yellow and increased both lightness and chroma

In this case the gamut is a chromaticity diagram, referring to a ZR-class HP display. Since CIELAB does not have a chromaticity diagram, we use the CIELUV space. For a most sophisticated feedback, a color appearance space like CIECAM02 could be used, rendered with transparency to show the position of the mark for the selected color. For a simpler feedback, the rivet could be displayed in a pure frontal projection, with a hue ribbon lining the flat head edge. In the higher figure above, the rivet is rotated along the symmetry axis so that the same green as in the color selection tool figures at the beginning is in the front.

The shaft is colored in this green, its diameter corresponds to the chroma and the length to the lightness.

The lower of the above figure shows what happens when the user moves the mobile device to select a yellow color. The head rotates so that yellow is now on front. The shaft is colored in this yellow and has become longer and thicker. The left and right sides of the figure are at the same scale.

In summary, I have described how the feedback for color selection tools for a WIMP GUI are not adequate for mobile devices, which make extensive use of MPG GUIs. I have presented a rivet metaphor that provides a much more ergonomic representation of the color selection tool's state. This radically new representation allows print shops to work faster and more reliably when they have to select or modify colors, thus preventing a disruption of the workflow.

Providing a commercial print workflow with superior tools will cut costs due to workflow exceptions and maximize the press owner's profits. A successful customer will buy additional presses from the vendor and use more consumables.

color consolidation

In a recent press release, Danaher Corporation on 2200 Pennsylvania Avenue, NW in Washington, D.C. announced that it purchased X-Rite for approximately $625 million. X-Rite had purchased Pantone and Gretag, and the latter had purchased Macbeth. Danaher already owns well-known brands like Tektronix, Fluke, Leica Microsystems, Beckman Coulter, Videojet, and Esco (a leader in industrial digital printing) among others.

Local optimization

I received a question about the paper Assessing color reproduction tolerances in commercial print workflow mentioned in a recent post. The interlocutor asks why I bother creating custom color scales, instead of just using the Farnsworth's 100 Munsell hues: the implementation would be much simpler.

I believe this question is a nice example of the difference between a color engineer and a color scientist. Let me explain:

Assessing color reproduction tolerances in commercial print workflow

The presentation of this paper was somewhat hasty, because I forgot to finish the slides. I only realized this while I was setting up my laptop and quickly thumbed through the slides. I only had the short time during the break to quickly assemble the presentation by copying chunks from the paper, while also trying to help Dr. Tastl who was having a problem getting PowerPoint to recognize the projector. I guess this is what happens when we are burnt out…

Why is Kodak near death while Fujifilm is thriving?

Fascinating perspective in The Economist. Here are some quotes:

Fujifilm, too, saw omens of digital doom as early as the 1980s. It developed a three-pronged strategy: to squeeze as much money out of the film business as possible, to prepare for the switch to digital and to develop new business lines.

Kodak had become a complacent monopolist. Fujifilm exposed this weakness by bagging the sponsorship of the 1984 Olympics in Los Angeles while Kodak dithered. The publicity helped Fujifilm’s far cheaper film invade Kodak’s home market.

Another reason why Kodak was slow to change was that its executives “suffered from a mentality of perfect products, rather than the high-tech mindset of make it, launch it, fix it,” says Rosabeth Moss Kanter of Harvard Business School, who has advised the firm.

Hindsight is always 20/20 but that last quote is reminiscent of the difference in business philosophy between Microsoft and Apple. One wonders what Steve Jobs might have said about that. We do know what Bob Lutz (former Vice Chairman of General Motors) thinks about Ivy League business schools and MBA spreadsheet-based business strategies.

Postscript: See the Comments below for additional perspective.

Greater detail makes HDR look good

HDR images are very pleasing, but have an unnatural look. Many of them remind me of the color rendering in Francis Ford Coppola's One from the Heart, filmed in the American Zoetrope studio, which produced also some of Wim Wender's movies with similar color rendering. The unnatural look comes from the dynamic range compression that is necessary to reproduce the images on media, I suspect mainly because the compression is only in luminance and not in chroma.

Regardless of the look, HDR images are very pleasing, and John McCann recently wrote the SPIE Newsroom article Human spatial processing accounts for dynamic range and color, in which he concludes:

At first, HDR imaging may have seemed best suited for improved recordings of scene radiances. However, glare limits the range of light that can be detected by cameras or the retina. All scene regions below middle gray are influenced, more or less, by the glare from the bright scene segments. Instead of accurate radiance reproduction, HDR imaging works well because it preserves the details in the scene's shadows. Spatial image processing preserves this information, but distorts accurate reproduction. Similarly, color constancy is the result of color comparisons of the entire scene.

Advising on color palettes

In the last couple of months I had been writing about the problem of selecting color palettes that are visually pleasing. I started with Mik Lamming's effort in bringing back to the office the colors that were sacrificed with the transition from mimeographs to Xerox copiers and from color-ribbon typewriters to IBM Selectrics. After a digression on the appearance of flamingos, I continued with the problem of selecting colors for VLSI design and illustration, showing the Meta-Palette and a set of other color selection tools.

Today I will step back a little and present a broader view. The problem of designing pleasing or harmonious palettes is as old as visual communication. In western culture a quantum leap occurred with Leonardo da Vinci's prolific work on color analysis and structure (leading to chiaroscuro), which continued with Michel Eugène Chevreul's simultaneous contrast (leading to Impressionism), and with Georges Vantongerloo's attempt to mathematically represent color palettes (leading to De Stijl and Bauhaus).

Essentially the Proto-Palette was just an evolution of this thread, made by a guy sitting in his office and talking to media designers. The fire test came around 1989, when it was decided that GlobalView's desktop would be in color. It turned out that the Proto-Palette tool (color harmony) was too regimented and the Digital Palette tool (palette database and color blending) needed a flexible user interface, so I integrated these tools, along with the earlier Meta-Palette and Maureen Stone's Color Tool.

This integrated set of tools allowed designers to start with a palette—for example, complexion—and add a contrasting color or changing a color lexically by adding a modifier like "muted." Codeveloping the color selection tools with the GlobalView GUI, all while the designers where working on the desktop (icons, etc.) proved to be very fruitful and efficient, leading to a paper at SPSE's 43rd Annual Conference (now IS&T). Since I had a full implementation, I gave a demo at the end of my presentation:

These tools were not the only game in town. At Tektronix, Jerry Murch and Joann Taylor were doing similar work. In Japan, Shigenobu Kobayashi had developed a system based on his Color Image Scale:

All this came together around 1993 with the release of Canon's Color Advisor, described in L. Lavendel and T. Kohler: The Story of a Color Advisor. In S. Sü̈sstrunk and A. Lakatos, editors, Sixth Color Imaging Conference: Color Science, Systems and Applications, volume 6, pages 228–229, Scottsdale (Arizona), November 1998.

As they describe in their paper, Larry Lavendel and Tim Kohler actually surveyed their potential users, instead of just working with a few designers like I did. This allowed them to take into account the semantic aspects and thus create a tool that is easy to use by anybody, as opposed to my tools, which were usable only by designers and researchers.

It is a pity, the Canon Color Advisor did not survive in the market, because nothing better was produced after it and it looks like with their Canon Color Agent, Larry and Tim were up to something even much more powerful.

In retrospect, Canon's Color Advisor was just too far ahead of time. When in 1991 Canon implemented their device independent color management system, they tried hard to fully integrate it into Windows. When Microsoft refused to cooperate, Canon's CEO Dr. Yamaji flew to Seattle to negotiate directly with Bill Gates.

Unfortunately the latter declared that Windows users will never create color documents, and all that was needed in Windows was a fixed palette of 16 colors for the GUI, with none required for documents. When Dr. Yamaji insisted, Gates declared that color would require an additional floppy disk in the upcoming release of Windows 3.1, and at 15 million copies to be sold, the cost for enabling managed color documents would be the astronomical sum of $15 millions.

Unfortunately this forced Canon to bury its Color Advisor in the printer driver for a post-processing step, instead of making it available during document creation. However, it did save Microsoft $15 millions, and I am sure they made good use of it.

All this is old history. The notion of artists, designers, and scientists designing color palette selection tools is a concept of the second millennium. In this millennium, the process consists in crowd-sourcing large data corpora and using analytics to make inferences. The questions then are:

1. Is crowd-sourced data reliable?
2. Do the methods scale?
3. When do we get a modern color advisor?

Color Selection

Color harmonization for images

Typically when we begin a career in computational color science, we start from colorimetric color reproduction. As we explore the wide variety of device gamuts, we quickly progress to perceptual color reproduction. At the latest when we build shippable product, we have to progress to preferred color reproduction.

Meta-Palette

When we think about places we have never visited, we build on other information about the place—the stereotypes—we have gained from various information sources, like friends, movies, documentaries, books, and newspapers—or YouTube in this day and age. About the Silicon Valley, the stereotype is that of the young entrepreneur who drops out of college to start up a company and become a billionaire before the tender age of 25.

In reality, most technologists here are just gnomes that work hard to make a contribution to humanity. The difference to other places in the world is that we do have the opportunity to create billion dollar businesses in technology, but as for our personal lives, they tend to be very modest, both in monetary term as well as in terms of fame or peer recognition. After all, being charismatically challenged is one of the reasons for becoming a programmer.

When I moved to the Valley with a freshly minted doctorate in computational geometry, for three years I worked on design rule checking. The task was not easy, especially from the point of view of the group dynamics. The project was building the next generation workstation—called Dragon—using full custom VLSI design instead of the ECL bit-slice technology common at the time.

The bootstrap problem was that there were no tools to design chips of such complexity (the Dragon had four to eight processors with separate IFU and EU chips, plus bus arbiter, memory controller, floating point unit, display controller, etc.). We leaned on principles from UCB's Magic and Spice tools to create our own. The key difference was that to handle the complexity of Dragon (each chip had an individual designer using a 32-bit Dorado with 8 MB of RAM), the tools we were inventing were hierarchical.

Although at first doing a hierarchical design instead of a flat design looked like a stroke of genius because of the bit parallelism, in practice it was a fata morgana. Indeed, designers tended to use the hierarchical features as macros, and the design was flat. The cells just contained the repetitive geometry, the key logic being added on top flat above the hierarchy, globally across the chip.

Therefore, maintaining the hierarchical design rule checker was in large part an act of self-flagellation. Nevertheless, I was puzzled by the enormous amount of design rule violations I was seeing. The designers were the best of the best in the world; why would they do so many mistakes?

I was most puzzled by the very high incidence of using the wrong sex diffusion over wells. Originally the underlying technology was NMOS, but when I joined the project they had already switched to CMOS, and as the designers were learning the new technique, the sex of diffusion was one thing on which they were really focusing. Why did they err so frequently?

I decided to study the problem and talked to each designer asking them to explain me some layout created by a different designer. I quickly noticed, they were not able to read the layout: they had to physically deconstruct it in order to navigate it. In my view, this was a shortcoming of the layout editor and I thought I can fix it by using a more appropriate color scheme.

As I learned, the specific colors came from Carver Mead and Lynn Conway's book written at PARC. At that time the thickness of the layers on a chip was in the range of visible light, so when you looked at a chip under a microscope in transmission mode, you would see each layer in a different color, according to its thickness.

Since the whole point of Mead and Conway's design technique was to abstract from the physical reality, I thought this coloring was arbitrary and I could come up with a better coloring. However, I immediately found myself accused of anathema: the colors by religion must be red for polysilicon, green for diffusion, yellow for gates, and blue for metal! Never mind the wells were also yellow and there were two metal layers.

Wary of religious wars, I decided to learn about color so I could nudge the colors to make layout more readable. I contacted the color scientists in Gary Starkweather's group and Mik Lamming kindly lent me his copy of Wyszecki and Stiles, telling me it contained all I needed to know about color.

After reading about 150 pages, I learned enough to come up with a coloring scheme, which essentially consisted in nudging the colors so that poly and diffusion would try to preserve their lightness, while the metal layers would preserve their hue. This made the layout appear transparent, so one could follow a wire no matter what other wires were under or above it.

This concept of transparency in IC designs is different from that of real world transparency, because—for example—it must prevent large power or clock wires from hiding the layout under them.

At that time my assignment was to automate the printing of checkplots, so I integrated the new color scheme in the plotter driver. This is how the layout for an inverter looked with the old driver:

Although with the new color scheme the layout was much more readable, most of the designers were shocked about the radical change. I tried to compromise by sitting down with each designer and try to reach a compromise on the color scheme.

It was at this time that I realized some of the designers had serious color discrimination problems. Unfortunately, they declined to be tested for color vision deficiency, but I developed a strong suspicion that one designer was a dichromat and another was either a dichromat or seriously anomalous.

Anyway, due to the memory restrictions, the designers were driving the color displays in 8-bit mode and each workstation had both a color and a black-and-white display, because text was too fuzzy on the color displays of the time. I wrote a little graphical tool called Meta-Palette running on the black-and-white display that had a chromaticity diagram with a mark for each color map entry, whose RGB values I could change by simply dragging around the corresponding mark. With the designers, I then created a couple of consensus palettes, which I made user-selectable in the printer driver.

This is the same inverter layout as above rendered with one of the preferred color palettes:

The number of design errors dropped dramatically to a manageable number, but the intervention still had strong religious opposition.

I wrapped up my work in a technical report and moved on to greener pastures in the new Electronic Documents Lab (EDL):

This report was sort of a kitchen sink, focusing more on the system integration aspects than on the color problems in rendering logical circuits for VLSI design. Therefore, I later doubled up with a shorter report just on the color problem:

I never submitted them anywhere because I immediately went on to tackle the more general problem of selecting colors for creating electronic documents. I used the same implementation strategy as for the VLSI design tool. However, the illustrator Gargoyle was used mostly in full color mode (24 bits), so to edit the colors by dragging marks in chromaticity diagrams I had to copy the colors into a hash table (metaphor: apply turpentine), noting that a typical 512 pixel square image typically contains only 26,000 different colors and most often less than 256.

After editing the colors in the color map I had to write them back into the Gargoyle data structure (metaphor: apply fixative). This is shown in the video at the top of this post.

Despite eloping to EDL, I did not escape the religious color wars. When I implemented the Xerox Color Encoding Standard as a color management system, I carefully optimized the inner loops so that managed color would render faster than unmanaged color, assuming it would be generally adopted by the Cedar community.

However, despite the efforts of my more charismatic colleagues to explain colorimetric color reproduction, generally the idea that a device-independent colorimetric color specification would be a good universal solution for portable color documents, the general belief was that any device RGB values specified by an author were the holy untouchable truth.

The idea that a printer produced a different color appearance for the same device coordinates than a display monitor was considered to be a failure of the printer designers. The religious fervor was so strong, that many people preferred to manually gamut-map color one by one by modifying color values in a simulation of the print, rather than accept color management and its automatic gamut mapping by algorithm.

Despite this fervor, most people did not really understand the concept of gamut mapping, let alone additive and subtractive color. Encouraged by the unexpected success of the flamingo movie, yet unable to defend my work in a talk, I decided to do a video explaining my work and then let people watch the video. This is the video at the top of this post.

In summary, Meta-Palette is an interactive tool to edit a color palette colorimetrically. To achieve device independence, I implemented a color management system (CMS) based on the Xerox Color Encoding Standard. Since device independent color was not generally accepted at the time, I did not use the CMS to just match color across devices, but to simulate how the same device coordinates are rendered across devices.

With this, you might just think I was a moron who lacked the persuasive skills to evangelize device independent color reproduction. This is not so. Half a decade later, Adobe created PostScript Level 2 (PS2) with colorimetric color reproduction. PS2 being device independent, you would expect that color would be encoded in a device independent colorimetric manner. However, based on the feedback from its professional users during the design and implementation phase, Adobe stored the color data in the input device coordinates, along with the devices profile.

The reason the printer's gamuts were so limited was because the inks and toners still had toxicity problems, especially liquid electrophotography.

It would take a decade for printers to achieve a gamut comparable to that of a CRT display monitor. This progress, however, did not bring a renaissance of colorimetric color reproduction. Instead, it brought sRGB, where the same device coordinates are sent to every device. In retrospect, the skeptics of yore were right.

As for colorimetric color reproduction, it has achieved full maturity with ICC version 4. However, mostly due of its ignorance of workflow, managed color is still a nightmare almost 30 years later.

The appearance of a Flamingo

Once upon a time, a day came when the management at Xerox PARC decided to hold elaborate Open Lab events to share our knowledge and achievements in pursuit of synergies. In the color project we had just finished building a research lab, and our director instructed us to better have a good demo in the Gray Lab, justifying is construction.

In fact, we had achieved quite a bit of notoriety, because we had it painted in gray, which was taken as a joke by our colleagues, who expected us building a colorful room. We even had it painted twice, because the first time, when we instructed the painting company to add pure black to white base and nothing else because we needed a spectrally flat color, they thought they were smarter than us and mixed a multitude of pigments to match the gray Munsell Sheet of Color we gave them as the standard.

When they called us upon finishing their job, their boss proudly held the Munsell Sheet against the wall, but we could see immediately that something was fishy, because the wall had a different color where it was hit by the light from the hallway (the lamps in the room were D50 simulators). We simply showed them their spectrum and they had to repaint the lab at their expense.

Other than the instruments and display monitors, the lab was completely bare, as to avoid contaminating the retina during psychophysics experiments. On the side we had also a small room completely painted in black with a spectroradiometer for the measurements. All lamps were D50, so we did not have to wait to adapt our visual system, and could reset it anytime by staring at a wall.

The announcement of the Open Lab event came with a big surprise: all the other team members would be on sabbatical or vacation that week, so I would have to set up the demo all by myself, including dealing with the crowd.

After some reflection, I concluded this was an impossible task, because all the other demos were very high concept. I decided to instead shoot a video in the lab and then just put in the door to the lab a cart with a big TV and a U-matic tape player. The question now was what experiment could I tape to demonstrate the need for a gray lab?

One Sunday I surveyed the offices of my colleagues working in graphics and imaging, in search of an error possibly due to inaccurate color evaluation. Of course each office had pictures of Utah teapots showing off the occupant's algorithms, but I noticed that images of flamingos were quite common. I was amazed all these flamingos were of a vivid pink, unlike the vermilion I remembered from a zoo visit when I was a child.

So I thought I drive to Marine World/Africa U.S.A., which had just moved from Redwood City (now the site of Oracle) to Vallejo, get a flamingo feather, measure it, and achieve a perfectly matching reproduction on our monitors and printers, showing off the importance of chromatic adaptation and cross-device color reproduction.

My plan was to keep a professional Betacam in my office and just opportunistically record material, so I could make up a story at the end depending on what I was able to gather. When I showed the first drafts to my colleagues, they educated me that when Americans think of flamingos, they do not think of the bird at all, but instead they think of pink plastic lawn flamingos.

Well, so much for a naive boy from the Alps. There was not enough time for a different demo, so I stared at my hours of video sequences and made up this movie:

Appearance Of A Flamingo

View more videos from Giordano Beretta

[If there is a problem with the above stream or you have a slow connection, you can download the movie from this link. If you stream from this link, there will be a buffering delay due to the slow connection.]

Unfortunately, the original U-matic cassette is no longer available, and my VHS copy is all gummed up. Unlike U-matic, VHS does not have SMPTE time code and the signal bandwidth is very narrow, so it took me 2 months of conditioning the tape and attempting replays, until I got most of the frames.

I would have loved to have Peter Schnorf's digital video editor having lost video frame protection, because I would just have run the digitization process a few times and the system would assemble the complete video.

I used a semiprofessional VHS player and first split the signal in separate luma and chroma components. I then adjusted each signal to fill its gamut and after analog-to-digital conversion denoised each signal. Since the signal is pretty bad, I did not try to do any enhancements, as they would amplify the defects: I simply transformed the digital video stream into MPEG-4 using Quicktime.

In the VHS device gamut of the YIQ color space, very little of the bandwidth is allocated to the magenta region, therefore the flamingos look terrible in the movie, washed out and like followed by a ghost.

An now a lame flamingo joke: Why do flamingos stand on one leg?

If they would lift also the other leg, they would fall over.

More on combatting bit rot with steganography

Last December First, I wrote about the story behind the data glyph technology and the preservation of digital images (here is the link). As it happens, at the Electronic Imaging Symposium two weeks ago, two papers presented recent progress on this technology.

Gaurav Sharma's presentation disclosed an extension of Tom Holladay's rotated dots from grayscale to full color. The authors were particularly concerned about the æsthetic quality of the images with the added payload. They conclude in their paper:

In this paper, we present a high capacity image barcode scheme for applications that require both high capacity and pleasing visual appearance of the encoded region. The scheme combines orientation modulation based data encoding on per-channel basis and color separation. We demonstrate that significant performance improvements can be obtained in terms of embedding rates by sacrificing image fidelity in favor of embedding robustness. Our simulation and experimental results indicate that dot orientation modulation based data embedding can achieve high embedding rates and well suited for per-colorant channel based data encoding in printed documents.

Link to the paper: http://dx.doi.org/10.1117/12.872215. Citation: Orhan Bulan, Basak Oztan and Gaurav Sharma, "High capacity image barcodes using color separability", Proc. SPIE 7866, 78660N (2011); doi:10.1117/12.872215.

Robert Ulichney's presentation described a system specifically for solving the image bit rot problem. The method presented was grayscale, so the payload would not be in the image's halftoning, but in a logo or other monochrome ornamental artifact.

The novelty is that the halftoning method is not Tom Holladay's rotated dots but a new algorithm called stegatones. Compared to the rotated dots, which allow a binary code, stegatones consist of 1-bit to 3-bit carriers, thus allowing a much higher capacity payload. The authors conclude:

We have improved on the scheme reported earlier for hardcopy image backup by embedding metadata into a steganographic halftone object. The advantages of this approach are:

• a better æsthetic presentation of the photo archive
• the elimination of the need to solve the complex OCR problem
• a more compact representation of the color tiles and metadata
• a layout for which auto-alignment is easier and thus the data is more recoverable

Building on the original motivation to use an analog hardcopy means of long-term image storage, our solution transcends hardware obsolescence by requiring any means of scanning the data coupled with the recovery software. While we can predict that hardware for reading digital storage media will likely not be available decades from now, some means of hardcopy scanning will be. So our strategy shifts the need to archive recovery hardware, to archiving recovery software. Long term recovery then depends on the availability of generic source code that includes means to read the accompanying stegatone.

Unfortunately the authors do not address the requirement to preserve a system capable of running the recovery software, so we are still stuck in the PhotoCD problem.

Link to the paper: http://dx.doi.org/10.1117/12.872612. Citation: Robert Ulichney, Ingeborg Tastl and Eric Hoarau, "Analog image backup with steganographic halftones", Proc. SPIE 7866, 78661I (2011); doi:10.1117/12.872612

If you missed the conference, you can easily read the two papers after downloading them from the two links above. However, you would have missed the conversation in the hall after Ulichney's talk. Actually, Elvis had already left the building, when a conversation started with Reiner E. from Rochester and Keith K. from Kihei.

We were wondering how far back this and the related technologies go. Reiner now has the date: 1982. During his first visit to the DGaO Conference (Deutsche Gesellschaft für angewandte Optik e.V.) he was getting a 'free ride' for operating the slide projector.

The talk contained the following: since digital storage is too expensive and cumbersome :-) and since it is always better to store in human readable form, since all other forms will disappear over time: create a system that stores digital in a human readable format. Data was from some satellite images (or other high quality imaging system).

Each data pixel (M > N bit) was converted to a N bit signal, where the N bits will be used as human readable signal and directly converted into an 'explicit' halftone. Meaning each pixel will get its own halftone cell with the corresponding number of elements set to "on". Since M > N, we have a many-to-one map and thus will create an M bit lookup-table for the explicit halftones, where the M_i,j that map to N_i have the identical number of 'on' bits, but in different spatial arrangement. Such a system was known in the digital field, but Reiner is not sure about the name. It is a less than optimal system for information density.