Microsoft Word - 1077 Article Text, Copyedited.docx Adv Syst Sci Appl 2021; 02; 117-132 Published online at https://ijassa.ipu.ru. Mathematical Modeling of Color Printing Devices: Color Gamut Visualization and Colorimetric Measurements Regularization Dmitry V. Tunitsky* V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia E-mail: dtunitsky@yahoo.com Abstract: The article concerns a piecewise linear modeling of a vast range of color printing devices: various printers of different kind and nature, presses, etc. The central purpose is not a presentation of ready to use computational algorithms, or, moreover, accomplished software solutions. The point is to reveal some aspects of mathematical modeling, which could serve as both a guideline for creation of practical and robust engineer solutions and an example of nontrivial application of piecewise linear topology. Keywords: colorant space, reference space, piecewise linear model, singular faces, proper printing device, non-degenerate printing device, regular printing device 1. PRELIMINARIES Consider a stimuli space ℝ! of m colorants and a reference space ℝ" of n colors. In color management practice, the dimension of reference space n is always equal to three, n = 3, since any color can be described exactly by three real numbers who are the coordinates of this color in some color space, e.g., XYZ, Lab, etc. The dimension m of stimuli space can vary in accordance with the number of colorants the considered printing device uses. This dimension is called a dimension of a printing device. In most practical cases the dimension of printing device is either three, m = 3, or four, m = 4. In the first case we deal with a three-dimensional printing device and in the second case we deal with a four-dimensional printing device. Not all the combinations (x1,…,xm) of real numbers represent combination of colorants, because the amount xk, 1£k£m, of the k-th colorant is measured in percents and can vary from zero percents (do not put the colorant at all) to one hundred percents (put as much colorant as possible). A printing device renders a combination (x1,…,xm) of colorants into the corresponding color (y1, y2, y3). It means that a printing device can be described by a map F: Wm ® ℝ#, where Wm = {( x1, … , xm), 0£ x1, … , xm£100} is the m-dimensional colorants cube in the stimuli space ℝ! and F(x1, … , xm) = (y1, y2, y3) is the point, whose coordinates correspond to the color rendered by mixture of the colorants combination. We will call such a map a printing device. To find the value of this function we should with the printing device under consideration reproduce on a sheet of paper the patch formed by the colorants combination (x1,…,xm) and measure the color coordinates (y1, y2, y3) of this patch by a colorimetric measurement tool. The number of colorants combinations (x1,…,xm) in the colorants cube is infinite and of cause it’s impossible to print and measure all of them, since actually we can print and measure only the finite subset of such combinations. Consider a finite set {wi} Ì Wm, i.e., a * Corresponding author: dtunitsky@yahoo.com mW 118 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) mesh of fixed points wi, i=1,…,M, inside the colorants cube and a set {pi} Î ℝ# = {( y1, y2, y3), - ¥ < y1, y2, y3 <+ ¥} of the corresponding values pi, F(wi) = pi, i=1,…,M, in three-dimensional color space. Call this mesh function a measurement data for the printing device under consideration. Hence, a measurement data is a discrete map f: {wi} ® {pi} such that f(wi) = pi = F(wi) for i=1,…,M. For simplicity, we will restrict ourselves to the case of a regular mesh only. Recall its definition. Definition. Let Wm = [a1, b1] ´ … ´ [am, bm] be an m-dimensional rectangular parallelepiped with a1 < b1, …, am < bm. For k = 1,…,m consider finite sets Zk = {xk0 , …, xkM(k)}, ak = xk0 < … < xkM(k) = bk, of M(k)+1 real numbers. The product mesh {wi} = Z1 ´ … ´ Zm Ì Wm of M points, M = ( M(1)+1)…(M(m)+1), is called regular inside the m-dimensional parallelepiped . There are two principal problems of mathematical modeling of a printing device. Direct problem. To find a continuous map F: Wm ® ℝ# being a satisfactory approximation to a given discrete function f, i.e., to the measurement data of the printing device under consideration. We will call the solution of this problem a model of the printing device or for conciseness just a printing device described by the corresponding measurement data (see section 1). Inverse problem. To find a continuous map g: F(Wm) ® Wm, being an inverse map to F, i.e., the composition of the maps g and F should be the identical map of the set F(Wm), . The problem, naturally, involves description of the gamut, i.e., the image F(Wm) to the map F. Moreover, in case m>3 an inverse map should satisfy to some additional conditions, for example, the maximal (minimal) possible amount of the m-th colorant component xm. We will restrict our examination of these problems to the class of piecewise linear maps. Remind the necessary notions. A k-dimensional simplex is a convex hull of k+1 affinely independent points of an m-dimensional space ℝ! , where 0£k£m. The boundary of a k- dimensional simplex consists of faces with different dimensions: k-1, k-2, …, 0. One- dimensional faces are called edges, and zero-dimensional faces are called vertices. Definition. Suppose the colorants cube Wm is decomposed into a union of N, N>0, sets Dj, . This decomposition is called simplex if for j=1,…, N the set Dj, is an m-dimensional simplex and the intersection of any two simplexes Dj and Dk is either empty, Dj Ç Dk = Æ, or is a union of whole (m–1)-, (m–2)-, …, and 0-dimentional faces to these simplexes. Definition. A continuous map F: Wm ® ℝ#, is called piecewise linear if there exists a simplex decomposition of the m- dimensional colorant cube such that all the restrictions F½Dj : Dj ® ℝ# of the map F to tetrahedrons Dj are linear maps. In other words, F½Dj (x) = cj + Bjx, where x = ( x1, … , xm)T mW mW )( mWFIdgF =! ! Nj j mW ,...,1= D= ! Nj j mW ,...,1= D= mW MATHEMATICAL MODELING OF COLOR PRINTING DEVICES: COLOR GAMUT VISUALIZATION… 119 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) is an m-dimensional vector of colorants combination, Bj is a 3´m matrix, and cj is a three- dimensional vector, cj Î ℝ#, for j=1,…, N (cf. [1, sections 1.4 and 2.3]. Remark. Generally speaking, for real applications the formulated above notions of simplex decomposition of the colorants cube Wm and its piecewise linear map is not sufficient. Indeed, rather often a colorants limitations, for example, , where , should be applied to the colorants cube . Such limitations have practical sense. In particular, they allow to avoid putting too much of colorants to a sheet of paper. Moreover, sometimes several color limitations should be applied to the colorants cube. As a result in general case we will get not a cube decomposed into simplexes but a convex polyhedron decomposed into intact and truncated simplexes. Nevertheless all the constructions below actually are through in this general case. Therefore the reader, especially the one who is mostly interested in ideas rather than in technical details, can easily content himself with the case of cubes and simplexes only because in general case all the same ideas and methods are practiced. 2. DIRECT PROBLEM FOR THREE-DIMENSIONAL PRINTING DEVICES Firstly examine a problem of approximation for a three-dimensional printing device. Let a finite set {wi} Ì W3 of points wi, i=1,…, M, inside the colorants cube W3 be a regular mesh. Consider a discrete map f: {wi} ® {pi}, of measurement data, where pi = f(wi) = F(wi) for i=1,…, N. To approximate the given discrete map f by a continuous one F: W3 ® ℝ#, use a piecewise linear or, what is the same in three-dimensional case, a tetrahedral interpolation. We will mostly follow the text-book [2] in our constructions. By definition of a regular mesh, for k=1,2,3 there exist the one-dimensional meshes Zk = {xk0, … , xkM(k)}, ak = xk0 < … < xkM(k) = bk, of M(k)+1 real numbers such that {wi} = Z1 ´ Z2 ´ Z3 Ì W3 and M = (M(1)+1)(M(2)+1)(M(3)+1). It means that the three-dimensional colorants cube W3 can be decomposed into the union of the mesh parallelepiped cells Pi,j,k = [x1i-1, x1i] ´ [x2j-1, x2j] ´ [x3k-1, x3k], i=1,…,M(1), j=1,…,M(2), k=1,…,M(3). Inside each of these parallelepiped cells the continuous approximation F of the measurement discrete map f is constructed by the following way. Consider an arbitrary three-dimensional rectangular parallelepiped P = [a1, b1] ´ [a2, b2] ´ [a3, b3] = {(x1, x2, x3), a1£ x1£ b1, a2£ x2£ b2, a3£ x3£ b3}, where a1, b1, a2, b2, a3, and b3 are fixed real numbers. There is an obvious one-to-one correspondence of the 8 vertices to the rectangular parallelepiped P and the 8 vertices (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1) to the unit three-dimensional cube P1 = {(x1, x2, x3), 0£ x1£ 1, 0£ x2£1, 0£ x3£ 1}. Cx m i i £å =1 mC 100< mW ! )3(,...,1 )2(,...,1 )1(,...,1 ,, 3 Mk Mj Mi kjiW = = = P= 120 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Numerate all the 8 vertices of the rectangular parallelepiped P by means of the corresponding vertices of the unit cube P1, x000, x001, x010, x011, x100, x101, x110, x111. Apply the same numeration to the values of the discrete map f, i.e., put pijl = f(xijl) for i,j,l=0,1. Define the map F inside the rectangular parallelepiped P, yn = Fn(x1, x2, x3) = pn000 + rn1Dx1 + rn2Dx2 + rn3Dx3, where n, n=1,2,3, is the number of component of the map F in three-dimensional color space ℝ# and Dxi = (xi - xi0)/(xi1 - xi0) for i=1,2,3. The coefficients rni, i=1,2,3, are determined in correspondence with the following table (cf. [2, p. 70–72]). Table 1. Coefficients rni, i=1,2,3 The interpolation under consideration has pure geometrical sense. We decompose a three- dimensional rectangular parallelepiped into six tetrahedrons. These tetrahedrons are defined by the conditions in the second column of the table above. Inside each tetrahedron the map F is constructed by linear interpolation of the values pijl, i,j,l=0,1, of the discrete map f at the vertices to the tetrahedrons. Thus we have constructed the piecewise linear map F, being a solution to the direct problem of mathematical modeling for a three-dimensional printing device. In other words, we have constructed a piecewise linear model of a three-dimensional printing device. 3. DIRECT PROBLEM FOR FOUR-DIMENSIONAL PRINTING DEVICES Now consider a four-dimensional printing device, which is modelled in a way similar to the three-dimensional case. Let a finite set {wi} Ì W4 of points wi, i=1,…,M, of the colorants cube W4 be a regular mesh. The measurement data pi = f(wi) = F(wi), i=1,…, M, determines a discrete map f: {wi} ® {pi}, To approximate the discrete map f by a continuous map F: W4 ® ℝ#, use a piecewise linear or, which in four-dimensional case is the same, pentahedral interpolation. By definition of a regular mesh, for k=1,2,3,4 there exist the one-dimensional meshes Zk = {xk0 ,…, xkM(k)}, ak = xk0 < … < xkM(k) = bk, of M(k)+1 real numbers such that {wi} = Z1 ´ Z2 ´ Z3 ´ Z4 Ì W4 and M = (M(1)+1)(M(2)+1)(M(3)+1)(M(4)+1). It means that the four- dimensional colorants cube W4 can be decomposed into the union of the mesh of parallelepiped cells: , Pi,j,k = [x1i-1, x1i] ´ [x2j-1, x2j] ´ [x3k-1, x3k] ´ [x4k-1, x4k]. Inside each parallelepiped cell Pi,j,k the continuous approximation F of the discrete map f is constructed by the following way. No Conditions rn1 rn2 rn3 1 Dx1 ³ Dx2 ³ Dx3 pn100- pn000 pn110- pn100 pn111- pn110 2 Dx1 ³ D x3 ³ Dx2 pn100- pn000 pn111- pn101 pn101- pn100 3 Dx3 ³ Dx1 ³ Dx2 pn101- pn001 pn111- pn101 pn001- pn000 4 Dx2 ³ Dx1 ³ Dx3 pn110- pn010 pn010- pn000 pn111- pn110 5 Dx2 ³ Dx3 ³ Dx1 pn111- pn011 pn010- pn000 pn011- pn010 6 Dx3 ³ Dx2 ³ Dx1 pn111- pn011 pn011- pn001 pn001- pn000 ! )4(,...,1 )3(,...,1 )2(,...,1 )1(,...,1 ,,, 3 Ml Mk Mj Mi lkjiW = = = = P= MATHEMATICAL MODELING OF COLOR PRINTING DEVICES: COLOR GAMUT VISUALIZATION… 121 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Consider an arbitrary four-dimensional rectangular parallelepiped P = {(x1, x2, x3, x4), a1£ x1£ b1, a2£ x2£ b2, a3£ x3£ b3, a4£ x4£ b4}. There is an obvious one-to-one correspondence between the vertices of the parallelepiped P and the vertices (0,0,0,0), (0,0,0,1), (0,0,1,0), (0,0,1,1), (0,1,0,0), (0,1,0,1), (0,1,1,0), (0,1,1,1), (1,0,0,0), (1,0,0,1), (1,0,1,0), (1,0,1,1), (1,1,0,0), (1,1,0,1), (1,1,1,0), (1,1,1,1) of the unit four-dimensional cube P1 = {(x1, x2, x3, x4), 0£ x1£1, 0£ x2£1, 0£ x3£1, 0£ x4£1}. Numerate the vertices of the rectangular parallelepiped P by the corresponding vertices of the cube P1: x0000, x0001, x0010, x0011, x0100, x0101, x0110, x0111,x1000, x1001, x1010, x1011, x1100, x1101, x1110, x1111. Apply this numeration also to the values of the map f, i.e., put pijkl = f(xijkl) for i,j,k,l=0,1, and define the components of the map F on the parallelepiped P: yn = Fn(x1, x2, x3, x4) = pn000 + rn1D x1 + rn2D x2 + rn3D x3 + rn4D x4, where n=1,2,3, Dxi = (xi - xi0)/( xi1 - xi0) for i=1,2,3,4, and rni are determined by the table: Table 2. Coefficients rni, i=1,2,3,4 No Conditions rn1 rn2 rn3 rn4 1 Dx1 ³ Dx2 ³ Dx3 ³ Dx4 pn1000-pn0000 pn1100-pn1000 pn1110-pn1100 pn1111-pn1110 2 Dx1 ³ Dx2 ³ Dx4 ³ Dx3 pn1000-pn0000 pn1100-pn1000 pn1111-pn1101 pn1101-pn1100 3 Dx1 ³ Dx4 ³ Dx2 ³ Dx3 pn1000-pn0000 pn1101-pn1001 pn1111-pn1101 pn1001-pn1000 4 Dx4 ³ Dx1 ³ Dx2 ³ Dx3 pn1001-pn0001 pn1101-pn1001 pn1111-pn1101 pn0001-pn0000 5 Dx1 ³ Dx3 ³ Dx2 ³ Dx4 pn1000-pn0000 pn1110-pn1010 pn1010-pn1000 pn1111-pn1110 6 Dx1 ³ Dx3 ³ Dx4 ³ Dx2 pn1000-pn0000 pn1111-pn1011 pn1010-pn1000 pn1011-pn1010 7 Dx1 ³ Dx4 ³ Dx3 ³ Dx2 pn1000-pn0000 pn1111-pn1011 pn1011-pn1001 pn1001-pn1000 8 Dx4 ³ Dx1 ³ Dx3 ³ Dx2 pn1001-pn0001 pn1111-pn1011 pn1011-pn1001 pn0001-pn0000 9 Dx3 ³ Dx1 ³ Dx2 ³ Dx4 pn1010-pn0010 pn1110-pn1010 pn0010-pn0000 pn1111-pn1110 10 Dx3 ³ Dx1 ³ Dx4 ³ Dx2 pn1010-pn0010 pn1111-pn1011 pn0010-pn0000 pn1011-pn1010 11 Dx3 ³ Dx4 ³ Dx1 ³ Dx2 pn1011-pn0011 pn1111-pn1011 pn0010-pn0000 pn0011-pn0010 12 Dx4 ³ Dx3 ³ Dx1 ³ Dx2 pn1011-pn0011 pn1111-pn1011 pn0011-pn0001 pn0001-pn0000 13 Dx2 ³ Dx1 ³ Dx3 ³ Dx4 pn1100-pn0100 pn0100-pn0000 pn1110-pn1100 pn1111-pn1110 14 Dx2 ³ Dx1 ³Dx4 ³ Dx3 pn1100-pn0100 pn0100-pn0000 pn1111-pn1101 pn1101-pn1100 15 Dx2 ³ Dx4 ³ Dx1 ³ Dx3 pn1101-pn0101 pn0100-pn0000 pn1111-pn1101 pn0101-pn0100 16 Dx4 ³ Dx2 ³ Dx1 ³ Dx3 pn1101-pn0101 pn0101-pn0001 pn1111-pn1101 pn0001-pn0000 17 Dx2 ³ Dx3 ³ Dx1 ³ Dx4 pn1110-pn0110 pn0100-pn0000 pn0110-pn0100 pn1111-pn1110 18 Dx2 ³ Dx3 ³ Dx4 ³ Dx1 pn1111-pn0111 pn0100-pn0000 pn0110-pn0100 pn0111-pn0110 19 Dx2 ³ Dx4 ³ Dx3 ³ Dx1 pn1111-pn0111 pn0100-pn0000 pn0111-pn0101 pn0101-pn0100 20 Dx4 ³ Dx2 ³ Dx3 ³ Dx1 pn1111-pn0111 pn0101-pn0001 pn0111-pn0101 pn0001-pn0000 21 Dx3 ³ Dx2 ³ Dx1 ³ Dx4 pn1110-pn0110 pn0110-pn0010 pn0010-pn0000 pn1111-pn1110 22 Dx3 ³ Dx2 ³ Dx4 ³ Dx1 pn1111-pn0111 pn0110-pn0010 pn0010-pn0000 pn0111-pn0110 23 Dx3 ³ Dx4 ³ Dx2 ³ Dx1 pn1111-pn0111 pn0111-pn0011 pn0010-pn0000 pn0011-pn0010 24 Dx4 ³ Dx3 ³ Dx2 ³ Dx1 pn1111-pn0111 pn0111-pn0011 pn0011-pn0001 pn0001-pn0000 The interpolation under consideration has pure geometrical sense. We decompose a four- dimensional rectangular parallelepiped into 24 pentahedrons. These pentahedrons are defined by the conditions in the second column of the table above. Inside each tetrahedron the map F is constructed by linear interpolation of the values pikjl, i,j,k,l=0,1, of the discrete map f at the vertices to the pentahedrons. 122 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Thus we have constructed the piecewise linear map F, being a solution to the direct problem of mathematical modeling for a four-dimensional printing device. In other words, we have constructed a piecewise linear model of a four-dimensional printing device. 4. GAMUT DESCRIPTION FOR THREE-DIMENSIONAL PRINTING DEVICES Consider a piecewise linear model F: W3 ® ℝ# of a given three-dimensional printing device. For practical applications it is important to find in color space the gamut of the printing device, i.e., the image F(W3) of the piecewise linear map F. In particular, we need it to go on with the inverse problem. By definition of a piecewise linear map F, we have the simplex decomposition of the three-dimensional colorants cube W3 into the union of N, N>0, tetrahedrons Dj: . Each tetrahedron has four two-dimensional faces. These faces are triangles and each triangle belongs either to one or several tetrahedrons of the set {Dj}. In a standard way the faces of these tetrahedrons can be divided into two classes. Definition. Fix a tetrahedron Dl, l=1,…,N, and consider it’s two-dimensional face d, which is a triangle. The face d is called boundary if it doesn’t belong to any other tetrahedron of the set {Dj}. In other words, d Ì Dl, and d Ë Dk for k=1,…,l-1,l+1,…,N. The face d is called internal if there is a tetrahedron Dk from the set {Dj} such that d belongs to both Dl and Dk, i.e., d Í Dl Ç Dk. Denote the set of all the boundary faces of the colorants cube W3 by Q. Remark. The set Q of all the boundary faces doesn’t depend on the choice of the three- dimensional printing device, i.e., on the choice of the corresponding piecewise linear map F. Indeed, the union of all these faces always coincides with the boundary ¶W3 of the three- dimensional colorants cube: . Suppose the printing device under consideration is non-degenerate, i.e., the corresponding piecewise linear map F is non-degenerate. By definition, it means that all the restrictions F½Dj : Dj ® ℝ#, of the map F to tetrahedrons Dj are non-degenerate linear maps F½Dj (x) = cj + Bjx (see section 1). In other words, the determinant of the corresponding matrix Bj is either positive, det Bj > 0, or negative, det Bj < 0. Definition. Fix a number l, l=1,…,N, and consider two-dimensional internal face d of the tetrahedron Dl, which is a triangle. The internal face d is called singular if there exists a tetrahedron Dk from the set {Dj} such that d belongs to both Dl and Dk, d Í Dl Ç Dk, and the determinants of the corresponding matrixes Bl and Bk have different signs, i.e., det Bl × det Bk < 0. Denote the set of all the singular faces of the given three-dimensional printing device by S. Remark. On the contrary to the set Q of all the boundary faces, the set S of all the singular faces essentially depends on the choice of the three-dimensional printing device, i.e., on the choice of the corresponding piecewise linear map F. For example, for some printing devices this set is empty and for some it is not (see section 6). It is possible to describe the gamut boundary of a non-degenerate printing device in terms of boundary and singular faces. The following theorem is through. Theorem. For any non-degenerate three-dimensional printing device the boundary of the gamut is a subset of the images of all the boundary and singular faces, i.e., ! Nj jW ,...,1 3 = D= 3W¶= QÎ ! d d MATHEMATICAL MODELING OF COLOR PRINTING DEVICES: COLOR GAMUT VISUALIZATION… 123 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) ¶F(W3) Í F(Q) È F(S). This theorem can seem to be a pure abstract mathematical proposition. And, of course, it really is. But nevertheless, it does significantly more because it gives a strict mathematical ground for creation of a wide range of computational algorithms for practical approximation of color gamut boundaries of various three-dimensional printing devices. In particular, the author designed a variant of such an algorithm, which constructs a three-dimensional gamut boundary for any real color printing device with three colorants. As an input it takes a file with colorimetric measurements data of the printing device under consideration (see section 1), and as an output it constructs the color gamut boundary, i.e., the corresponding boundary of the three-dimensional body in a reference space of three colors. As it was said in the preface, the same details of computational algorithms are not presented in this article. Therefore, we will just give an example of what the designed algorithm does in practice. The picture below visualizes a piecewise linear approximation of the gamut boundary of a rather standard printing device with three colorants, which means that the stimuli space is three-dimensional in this case. In reference space the Lab coordinate system is chosen, and one colorants limitation is applied. Fig. 1. A piecewise linear approximation of the gamut boundary for a three-dimensional printing device The next picture gives another example of the output of the same algorithm, which is a visualized color gamut boundary. Here we handle exactly the same printing device as in the previous case but the colorants limitation is changed to the tighter one, namely to . 250 3 1 £å =i ix 150 3 1 £å =i ix 124 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) The way of visualization is also exactly the same, including angle of view, the scale, and the coordinate system. Fig. 2. Results of the algorithm for the same printing device with tighter colorants limitation 5. GAMUT DESCRIPTION FOR FOUR-DIMENSIONAL PRINTING DEVICES Consider a piecewise linear model F: W4 ® ℝ#, of a four-dimensional printing device. Definition. If the image of the boundary ¶W4 of the four-dimensional colorants cube coincides with the image of the whole cube W4, i.e., F(W4) = F(¶W4), then the four- dimensional printing device is called proper. Remark. From technological point of view, the assumption of a four-dimensional printing device to be proper is reasonable for most real four-dimensional printing devices. By definition of the piecewise linear map F, all the restrictions F½Dj : Dj ® ℝ#, of the map F to pentahedrons Dj are linear maps, i.e., F½Dj (x) = cj + Bjx, where Bj is a 3´4 matrix for j=1,…,N. Let Bji be the 3´3 matrix obtained by throwing away the i-th column from the 3´4 matrix Bj and put cj = ( det Bj1, - det Bj2, det Bj3, - det Bj4 ) for j=1,…, N. Definition. Consider the four-dimensional printing device corresponding to the piecewise linear map F. A vector field c on the colorants cube W4 is called the characteristic vector field of the printing device under consideration if c½Dj = cj for j=1,…, N . The four-dimensional printing device is non-degenerate if the corresponding characteristic vector field c is non- degenerate, i.e., cj ¹ 0 for all j=1,…,N. MATHEMATICAL MODELING OF COLOR PRINTING DEVICES: COLOR GAMUT VISUALIZATION… 125 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Remark. By definition, the characteristic vector field of any four-dimensional printing device is a four-dimensional piecewise constant vector field on the four-dimensional colorants cube W4. In this section we will describe the gamut of a proper non-degenerate four-dimensional printing device, i.e., the image F(W4) of the corresponding piecewise linear map F in color space. By definition of a piecewise linear map, we have the simplex decomposition of the four- dimensional colorants cube W4 into the union of N, N>0, pentahedrons Dj, . Each pentahedron has five three-dimensional faces. These faces are tetrahedrons and each tetrahedron either belongs to one or several pentahedrons of the set {Dj}. Definition. Fix a pentahedron Dl, l=1,…,N, and consider it’s three-dimensional face, which is a tetrahedron d. The face d is called boundary if it doesn’t belong to any other pentahedron of the set {Dj}. In other words, d Ì Dl, and d Ë Dk for k=1,…,l-1,l+1,…,N. Denote the set of all the boundary faces of the colorants cube W4 by Q. Remark. The set Q of all the boundary faces doesn’t depend on the choice of the four- dimensional printing device, i.e., on the choice of the corresponding piecewise linear map F. The union of all these faces always coincides with the boundary ¶W4 of the four-dimensional colorants cube, . On the boundary ¶W4 of the four-dimensional colorants cube W4 there exists the normal vector field n to this cube. Let dj, j=1,…,N, be a boundary face of the four-dimensional colorants cube W4 belonging to the pentahedron D j. Denote by nj the restriction of the normal vector field n to this face: nj = n½dj. Let dk and dl be boundary faces of the four-dimensional colorants cube W4 such that dk Ì Dk, dl Ì Dl for some pentahedrons Dk and Dl, k,l=1,…,N. By definition, these boundary faces are tetrahedrons. Suppose they have a two-dimensional face, which is a triangle d, in common, d = dk Ç dl. Definition. The triangle d is called a singular face of a non-degenerate four-dimensional printing device that is defined by the piecewise linear map F if the inner products (nk, ck) and (nl, cl) of the normal vector field n and the characteristic vector field c have different signs: (nk, ck) × (nl, cl) < 0. Denote the set of all the singular faces of the given four-dimensional printing device by S. Remark. The set Q of all the boundary faces doesn’t depend on the choice of a printing device. On the contrary, the set S of all the singular faces essentially depends on the choice of a four-dimensional printing device, i.e., on the choice of the corresponding piecewise linear map F. Moreover, a boundary face is a three-dimensional simplex, i.e., a tetrahedron, whereas a singular face is a two-dimensional simplex, i.e., a triangle. There is also a serious difference between three- and four-dimensional cases of printing devices. Indeed, in three-dimensional case the boundary faces are two-dimensional and in four-dimensional case – four-dimensional. An other important difference is the following: for most three-dimensional printing devices the set S of all the singular faces is empty, while for any four-dimensional printing devices the set S of all the singular faces is not empty. It is possible to describe the gamut boundary of a proper non-degenerate printing device in terms of singular faces only. The following theorem is through. Theorem. For any proper non-degenerate four-dimensional printing device the boundary of the gamut is a subset of the images of all the singular faces, i.e., ¶F(W4) Í F(S). All the remarks that were made in the previous section after the theorem about the gamut boundaries of the three-dimensional printing devices are entirely correct in the case described by the theorem under consideration. In particular, a wide range of algorithms that approximate ! Nj jW ,...,1 4 = D= 4W¶= QÎ ! d d 126 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) the color gamut boundary of any real color printing device with four colorants can be designed grounded on it. As in the case of three-dimensional stimuli space an input for this algorithm is a file with colorimetric measurements data of the printing device under consideration (see the previous section). And as an output this algorithm produces piecewise linear approximation of the color gamut boundary, i.e., the corresponding three-dimensional body boundary in a reference space of three colors. The following picture gives an example of such approximation. It shows the color gamut boundary in reference space of a rather standard printing device with four colorants (cyan, magenta, yellow, and black), which means that the stimuli space is four-dimensional. To be definite, call the measurement file of this device CMYK.dat. In reference space the Lab coordinate system chosen, and one colorants limitation is applied. Fig. 3. The color gamut boundary for a four-dimensional printing device The next picture gives another example of the algorithm output. Here we have exactly the same printing device as in the previous picture, which is described by measurement data from CMYK.dat file, but the colorants limitation is changed to a tighter one, namely to . The way of rendering is exactly the same, including angle of view, the scale, and the coordinate system. 250 4 1 £å =i ix 150 4 1 £å =i ix MATHEMATICAL MODELING OF COLOR PRINTING DEVICES: COLOR GAMUT VISUALIZATION… 127 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Fig. 4. Results of the algorithm for the same printing device with tighter colorants limitation 6. THREE-DIMENSIONAL REGULAR PRINTING DEVICES Consider a piecewise linear model F: W3 ® ℝ# of a three-dimensional printing device. Definition. The three-dimensional printing device is called regular if the piecewise linear map F is an injection. Lemma. Let a topological space W be compact and a map F, F: W ® F(W), be a continuous injection. Then there exists the unique continuous inverse map g = F-1: F(W) ® W. In other words, then the map F is a homeomorphism. Proof. See [3, ch. 2, § 8]. Remark. Since the three-dimensional cube W3 is a compact topological space the lemma under consideration gives a satisfactory approach to solution of the inverse problem of modeling of three-dimensional regular printing devices (see section 1). Important to note, that most of the three-dimensional printing devices are regular though sometimes singular printers are met. 128 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) By definition of a piecewise linear map, we have the simplex decomposition of the three- dimensional colorants cube W3 into the set of N, N>0, tetrahedrons Dj, , such that all the restrictions F½Dj : Dj ® ℝ#, of the map F to tetrahedrons Dj are linear maps, i.e., F½Dj (x) = cj + Bjx, where Bj is a 3´3 matrix, and x, cj are three-dimensional vectors for j=1,…, N. Definition. A three-dimensional printing device is called strictly non-degenerate if all the determinates of the matrixes Bj are of the same sign, i.e., det Bj × det Bj > 0 for all the indexes i,j=1,…,N. Remark. By definition of a singular face (see section 4), a three-dimensional printing device is strongly non-degenerate if and only if the set S of all its singular faces is empty, S = Æ. Any three-dimensional strongly non-degenerate printing device is non-degenerate. The inverse statement is false because there exist three-dimensional non-degenerate printing devices that are not strongly non-degenerate. There is an effective criterion of a three-dimensional printing device to be regular. Theorem. Let F: W3 ® ℝ# be a piecewise linear model of a three-dimensional printing device. This printing device is regular if and only if it is strongly non-degenerate and the restriction F½¶W3 : ¶W3 ® ℝ# of the map F to the boundary ¶W3 of the three-dimensional colorants cube W3 is an injection. By this theorem, the necessary condition of a three-dimensional printing device to be regular is its strong non-degeneracy. By definition, it means that all the determinates of the matrixes Bj of the piecewise linear map F have the same sign. Describe the scheme of an algorithmic approach to forcing a three-dimensional printing device to become strictly non- degenerate. At the first step count the number n+ of positive determinants and the number n- of negative determinants. For clarity, assume that n+ > n-. At the second step define a positive threshold e, e > 0, which is usually a small real number, and construct the error functional R, , where Rj = Rj(p1, … , pM) = 0 if det Bj ≥ e, and Rj = Rj(p1, … , pM) = (e - det Bj)2 if det Bj < e, j=1,…, N. Here p1, … , pM are the three-dimensional vectors in color space, forming the measurement data of the three-dimensional printing device under consideration (see section 1). By construction of the direct problem solution, all the determinants det Bj of the piecewise linear map F are third order polynomials with respect to measurement data p1,…, pM for j=1,…,N (see section 2). Hence, all the functions Rj are smooth for j=1,…,N and the error functional R = R(p1, … , pM) is smooth with respect to measurement data p1,…,pM too. At the third step minimize the error functional R with respect to measurement data p1,…,pM, i.e., R(p1, …, pM) ® min, by some minimization method. The resulting argument (p10, … , pM0) of the minimal value is the measurement data for regularized three-dimensional printing device. Remark. There are M three-dimensional vectors in measurement data. Therefore the total dimension of the space is 3M. Thus we have a 3M-dimensional non-convex minimization problem. By construction, the error functional R is not convex and can have more than one minimal point. ! Nj jW ,...,1 3 = D= å = == N j MjM ppRppRR 1 11 ),...,(),...,( MATHEMATICAL MODELING OF COLOR PRINTING DEVICES: COLOR GAMUT VISUALIZATION… 129 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) 7. FOUR-DIMENSIONAL REGULAR PRINTING DEVICES Consider a piecewise linear model F: W4 ® ℝ# of a four-dimensional printing device. Definition. The four-dimensional printing device is called regular if the following three conditions hold for the piecewise linear map F. (1) The color gamut F(W4) is homeomorphic to closed three-dimensional disk D3. (2) For any internal point p of the color gamut F(W4), p Î int F(W4), the pre-image F-1(p) is homeomorphic to a segment [a, b], a ni- for i=1,2,3 and n4+ < n4- . At the second step define a positive threshold e, e > 0, which is usually a small real number, and construct the error functional R, . Here Rji = Rji(p1, …, pM) = 0 if (-1)i+1det Bji ≥ e and Rj = Rj(p1, … , pM) = (e - det Bj)2 if (-1)i+1det Bji < e for i=1,2,3. For i=4 Rj4 = Rj4(p1, …, pM) = 0 if det Bji ≥ e and Rj = Rj(p1,…, pM) = (e - det Bj)2 if det Bji < e for j=1,…,N. In both cases p1, …, pM are the three-dimensional vectors in color space that form the measurement data of the four-dimensional printing device under consideration (see section 1). By construction of the piecewise linear map F, all the determinants det Bji are the third order polynomials with respect to measurement data vectors åå = = == 4 1 1 11 ),...,(),...,( i N j M i jM ppRppRR 130 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) p1,…,pM for j=1,…,N and i=1,2,3,4 (see section 3). Thence all the functions Rji are smooth for j=1,…,N, i=1,2,3,4, and the error functional R = R(p1, …, pM) is smooth with respect to measurement data vectors p1,…,pM too. At the third step minimize the error functional R with respect to measurement data p1,…,pM, i.e., R(p1, …, pM) ® min, by some minimization method. The resulting argument (p10, … , pM0) of the minimal value is the measurement data for regularized four-dimensional printing device. Remark. The dimension of the space of measurement data is 3M. Thus we obtain a 3M- dimensional non-convex minimization problem. By construction, the error functional R is not convex and can have more than one minimal point. Consider the measurement file CMYK.dat that we have used in the example of section 5. Direct calculations show that this printing device is not strictly non-degenerate. Indeed, the table below indicates that some coordinates of the characteristic vector field are positive whereas some are negative: Fig. 5. Distribution for coordinates of the characteristic vector field From geometrical point of view, it means that we have too many singular faces that lead to formation of redundant faces or singularities inside the color gamut. Visualization of these singularities can be seen in the picture below: Fig. 6. Singularities inside the color gamut MATHEMATICAL MODELING OF COLOR PRINTING DEVICES: COLOR GAMUT VISUALIZATION… 131 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) In particular, the singularities are the polyhedrons in white, magenta, yellow, and red. Therefore, it makes sense to implement the described above algorithmic scheme and apply the resulting tool to the measurement data from CMYK.dat file. The author have implemented such a tool and successfully applied it to force the data to become strictly non-degenerate. The table below shows that after the work of this tool the data became really strictly non-degenerate: Fig. 7. Distribution for coordinates after applying the algorithm From geometrical point of view, it means that all the redundant singular faces have been removed and, therefore, no singularities exist anymore. Visualization of color gamut of the printing device after forcing it to become strictly non-degenerated is given in the picture below: Fig. 8. The color gamut without singularities after applying the algorithm Indeed, no singularities are present anymore. 132 D.V. TUNITSKY Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) ACKNOWLEDGEMENTS This research was carried out with the support of the Russian Foundation for Basic Research under grant no. 20-01-00610 A and the Russian Scientific Foundation under grant no. 19-11- 00223. REFERENCES 1. Rurk C.P., Sanderson B.J. (1982) An Introduction to Piecewise Linear Topology. Springer–Verlag, Berlin–New York. 2. Kang H. (1997) Color technology for electronic imaging devices. SPIE: Bellingham, Washington. 3. Seifert H., Trelfall W. (1980) A Textbook in Topology. Algebraic Press, New York.