Paper Implementation: ‘A Simple Algorithm for Metamer Mismatch Bodies’
In color imaging, metamer mismatch bodies are an important concept for quantifying metameric failure for a change in observer or a change in illumination.
This post discusses an open source Python implementation of the paper ‘A Simple Algorithm for Metamer Mismatch Bodies’ (Centore, 2016). The paper is notable for providing a clear psuedocode and matlab implementation of the algorithm, making it more accessible than ever before.
I hope to further the accessibility trend by re-implementing the algorithm in Python 3 and SciPy. You can dive right into the code here.
The same linear programming/spherical sampling based algorithm for metamer mismatch bodies appears to have been described independently by Mackiewicz, Rivertz, and Finlayson 2017 in the proceedings of CIC 25.
Background
In color imaging, the problem of camera color correction is as follows:
Given a camera RGB response to an unknown spectral signal, what XYZ response would a CIE standard observer have to the same signal?
Unless the camera response functions are linear transformations of the observer response functions this problem will be ill-posed (Luther, 1927). In practice there could be many XYZs for any camera RGB and you must use heuristics to choose one. Most commonly, a least squares linear fit is used to map camera RGB responses to a XYZ value. This is known as ‘linear color correction’ (Finlayson, 2000).
The set of all possible XYZs corresponding to a single camera RGB is a 3D convex set called a Metamer Mismatch Body (MMB).
Stated simply, the set of all light beams that appear as a single color to one observer, may appear as many colors to a second observer; and the convex set of colors seen by the second observer is a MMB.
The situation, as artfully illustrated (assume a fixed illumination):
The MMB is the “image” of the metamer set through the second observer’s response functions. The metamer set is the “pre-image” of the MMB.
MMBs were first described in Wyszecki, 1958 as “c.m.f-ellipsoids”
The ability to compute MMBs proved to be very useful in camera color correction. In Wyszecki and Stiles, 1967 it was proposed that the centroid of the MMB could be used to re-establish a 1:1 color mapping between observers.
The center of the MMB was then used as a solution to the camera color correction problem in Finlayson and Morovic, 2000.
A Simple Algorithm for Metamer Mismatch Bodies:
In his paper, Centore lays out a detailed linear programming approach for computing MMBs induced by a change of observer, a change in scene illumination, or both. The algorithm determines a sampling of points on the surface of the MMB at a user specified resolution as well as the surface reflectance functions of the associated metamer set.
The key, high level points of this paper are:
- The MMB is a convex set.
- Linear Programming can be used to minimize or maximize a linear objective function over any convex set.
- The linear form of a direction vector can be used as an objective function that when minimized or maximized over a convex set yields points on the surface of the convex set, in that direction (see: Appendix)
- Therefore: a random sampling of direction vectors can be used in a linear programming problem to find a random sampling of points on the surface of the MMB.
My own psuedocode of the problem in standard linear programming form:
Code
The algorithm itself takes SciPy and Numpy as its only dependencies. Centore notes: “In 2016, when ready-made software for linear programming and convex hulls is readily available, implementation is much easier than it was in Allen and Wyszecki’s day”.
The python library at https://www.colour-science.org/ has built in tools for standard CIE observers and illuminants which makes testing this algorithm out relatively quick and easy. A full example can be found here
A fast and open source python routine for computing MMBs opens the door for further open source python implementations of many scene re-lighting and color correction algorithms. I’d like to take this and extend into an a python implementation of ‘Metamer constrained colour correction’ from Finlayson, 2000.
Appendix: The Objective Function
A key ingredient to this marriage of colorimetry and linear programming is the objective function associated with each arbitrary direction. This was a new concept to me so it’s worth elaborating on.
We seek a function that when maximized or minimized over a convex set returns a point on the surface of that convex set.
In a normed vector space, every vector V is associated with a dual function V* which is known as the ‘co-vector’ or ‘linear form’ of V (Koenderink, 1990).
Consider an arbitrary 2D euclidian vector [x , y]. The linear form is `F(a, b) = ax + by`. This function accepts as input a 2D vector [a, b] and returns a scalar representing where [a, b] projects onto [x, y]. In essence, it tells us how far along [a,b] is in direction [x,y] (Bachman, 2012).
If the linear form of a direction vector were to be maximized against all the points in a convex set, it would return the point that is furthest in that direction. This point would be on the surface of the set.
Pictured: two direction vectors reveal the minimum and maximum points of a convex set in those directions.
By choosing enough random direction vectors and maximizing their linear forms against the convex set, we can sample the points on the surface of the convex set.
References
[1] Paul Centore, The Geometry of Colour, 2017
[2] M. Mackiewicz, H. Rivertz and G. Finlayson, “Metamer mismatch volumes using spherical sampling,” Proceedings of the 25th Color and Imaging Conference, 2017
[3] R. Luther, Aus dem Gebiet der Farbreizmetrik (On color stimulus
metrics) Zeitschrift für technische Physik 8, 1927. Translated by Rolf G. Kuehni 2009. Commentary by Michael H. Brill, 2010.
[4] G. Wyszecki, “A Measure for the Total Difference of Two Sets of Color-Mixture Functions”, Journal of the Optical Society of America, vol 49, issue 8, 1959
[5] G. Wyszecki and W. S. Stiles, Color Science: Concepts and methods, Quantitative Data and Formulae, 1st ed. John Wiley & Sons, 1967
[6] G. Finlayson & P. Morovic, “Metamer constrained colour correction,” Journal of Imaging Science and Technology, 2000
[7] J. Koenderink, Solid Shape, MIT Press, pages 75–77, 1990
[8] D. Bachman, A Geometric Approach to Differential Forms, 2nd ed. Birkhauser, page 27, 2012
