← README · Section 4 1 · 2 · 3 · 4 · 한국어
c \in \lbrace R, G, B\rbrace$.
\mathrm{lum}(r, g, b) = 0.299r + 0.587g + 0.114b$.
The brightness used for finding lines is the brightness of the color laid on white, $L = \mathrm{lum}(A\cdot O_R + 1 - A, A\cdot O_G + 1 - A, A\cdot O_B + 1 - A)$.
A\cdot O + (1 - A)\cdot 1$ per channel. References: R9 ITU-R BT.601 · R1 Porter · Duff 1984k = \min(1, M / \max(w_0, h_0))$, $W = \max(1, \mathrm{round}(k\cdot w_0))$, $H = \max(1, \mathrm{round}(k\cdot h_0))$,
using the browser’s high-quality downscaling. $N = W\cdot H$. If the limit is 0 and the original exceeds 16 million pixels, a warning is shown.
0.001N$ pixels have $A < 0.98$, the picture is treated as transparent. Pixels with $A \le 0.02$ are empty.
s = \max(W, H) / 1000$ is the scale factor for picture size (multiplied into length reference values).
s^2$. References: a rule set by this program\mathrm{clamp}(x) = \min(1, \max(0, x))$, and $\mathrm{smoothstep}(a, b, x)$ is $t^2(3 - 2t)$ for $t = \mathrm{clamp}((x - a)/(b - a))$ (a descending curve when $a > b$).
t^2(3 - 2t) = 3t^2 - 2t^3$ with zero slope at both ends: 0 at 𝑡 = 0, 1 at 𝑡 = 1, slope 1.5 in the middle, so joining two thresholds with it changes the weight without jumps. References: R47 Ebert et al. 2003[a, b]$ written under $\mathrm{clip}$ means the value is clipped to that interval: $\min(b, \max(a, x))$.
[a, b]$. References: a rule set by this program\Delta E$ is CIE76 (Euclidean distance in Lab). Hue angle difference is $\Delta h = \min(d, 360^\circ - d)$ for $d = \lvert h_1 - h_2\rvert \bmod 360^\circ$.
\sqrt{\Delta L^{*2} + \Delta a^{*2} + \Delta b^{*2}}$ (CIE76) is used as the color difference. The angle difference is the shorter way around the circle. References: R7 CIE 2004 · R8 Mahy et al. 1994\eta_s$) become 0–1 as $\text{value}/100$.
t_{high}$ in 4.3, the shadow threshold in 4.7). References: a rule set by this program\mathrm{round}$ is the nearest integer (0.5 rounds up); $\lfloor x \rfloor$ · $\lceil x \rceil$ are floor · ceiling.
Math.round); floor and ceiling are the usual functions. References: a rule set by this programsRGB is linearized, then converted to Lab via XYZ (D65).
C_{lin}=\begin{cases}C/12.92 & C\le 0.04045\\ \left(\frac{C+0.055}{1.055}\right)^{2.4} & \text{otherwise}\end{cases}
\qquad
L^*=116f(Y)-16,\; a^*=500\,(f(X/X_n)-f(Y)),\; b^*=200\,(f(Y)-f(Z/Z_n))
Note — Why: sRGB values carry the display gamma, so they are not proportional to the amount of light. To measure color differences as people perceive them, the values are first returned to light amounts (linear values) and then taken through XYZ to Lab. How it works: The sRGB transfer function is inverted: a straight line (divide by 12.92) up to 0.04045, a 2.4-power curve above. Lab’s $L^*$ follows the cube root of $Y$ to imitate perceived lightness, and $a^*$ · $b^*$ are the red–green and yellow–blue opponent axes. References: R6 IEC 1999 · R7 CIE 2004
f(t)=\begin{cases}t^{1/3} & t>0.008856\\ 7.787\,t+16/116 & \text{otherwise}\end{cases}
Note — Why: The cube root has infinite slope near 0, so used as is it would blow up small noise in very dark colors. How it works: For $t \le (6/29)^3 \approx 0.008856$ it is replaced by the line $7.787t + 16/116$, which meets the cube root in value and slope (the CIE definition). References: R7 CIE 2004
From linear RGB to XYZ the sRGB (D65) matrix is used, with reference white $X_n = 0.95047,\ Y_n = 1,\ Z_n = 1.08883$.
Note — Why: Lab measures “how light and what color compared with white”, so it needs a reference white. How it works: These are the XYZ values of the sRGB white, the D65 illuminant, normalized to $Y_n = 1$. References: R7 CIE 2004 · R6 IEC 1999
\begin{pmatrix}X\\Y\\Z\end{pmatrix}=
\begin{pmatrix}0.4124564&0.3575761&0.1804375\\0.2126729&0.7151522&0.0721750\\0.0193339&0.1191920&0.9503041\end{pmatrix}
\begin{pmatrix}R_{lin}\\G_{lin}\\B_{lin}\end{pmatrix}
Note — Why: The three linear RGB primaries have fixed positions in XYZ, so one 3×3 matrix converts between them. How it works: The columns are the XYZ of the sRGB red · green · blue primaries (white point D65), and the middle row (𝑌) holds the luminance weights 0.2126 · 0.7152 · 0.0722. References: R6 IEC 1999
Linearization is precomputed as a 256-entry table of 8-bit values (𝐶 into bin $\mathrm{round}(255C)$). Chroma $C^* = \sqrt{a^{*2} + b^{*2}}$, hue angle $h = \mathrm{atan2}(b^*, a^*)$ (in degrees).
Note — Why: Rules that separate achromatic materials or check whether a shadow’s hue is close to the lit side need chroma and hue separately. Computing powers per pixel would be slow. How it works: These are polar coordinates in the $(a^*, b^*)$ plane: the distance from the origin is chroma $C^*$ and the angle is hue ℎ. An 8-bit input has only 256 values, so the linearization is precomputed in a table. References: R7 CIE 2004 · R10 Fairchild 2013
Lab → sRGB (when recovering, from a k-means center, the color of a tone that has no samples):
f_y=\frac{L^*+16}{116},\ f_x=f_y+\frac{a^*}{500},\ f_z=f_y-\frac{b^*}{200},\qquad
f^{-1}(t)=\begin{cases}t^3 & t^3>0.008856\\ (t-16/116)/7.787 & \text{otherwise}\end{cases}
Note — Why: A k-means center is a Lab value, so painting the color of a tone with no pixels into a layer requires converting back to sRGB. How it works: The forward formulas are inverted: $f(Y)$ comes from $L^*$, adding or subtracting $a^*$ · $b^*$ gives $f(X/X_n)$ · $f(Z/Z_n)$, and cubing (or inverting the linear part) undoes 𝑓. References: R7 CIE 2004
\begin{pmatrix}R_{lin}\\G_{lin}\\B_{lin}\end{pmatrix}=
\begin{pmatrix}3.2404542&-1.5371385&-0.4985314\\-0.9692660&1.8760108&0.0415560\\0.0556434&-0.2040259&1.0572252\end{pmatrix}
\begin{pmatrix}X_n f^{-1}(f_x)\\ f^{-1}(f_y)\\ Z_n f^{-1}(f_z)\end{pmatrix},\qquad
C=\begin{cases}12.92\,C_{lin} & C_{lin}\le 0.0031308\\ 1.055\,C_{lin}^{1/2.4}-0.055 & \text{otherwise}\end{cases}
Note — Why: Going from XYZ to linear RGB and then to gamma-encoded sRGB gives screen and file values. How it works: This is the inverse of the forward matrix followed by the sRGB encoding gamma (a line with factor 12.92 up to 0.0031308, a 1/2.4 power above). Values are clipped to 0–1 before the gamma because some Lab points lie outside the sRGB gamut. References: R6 IEC 1999 · R35 Strang 2016
($C_{lin}$ is clipped to 0–1 before applying the gamma.) The color comparison of the manual correction tools (4.17) uses Lab from the same formulas.
\mathrm{dilate}_r(f)(x, y) = \max f(x + i, y + j)$ (the maximum over $\lvert i \rvert, \lvert j \rvert \le r$; erosion takes the minimum; outside the picture is dropped from the window).
The 1-D sliding max / min split into rows and columns is computed with a monotonic deque, $O(1)$ per pixel. Closing is dilation then erosion; opening is erosion then dilation.
2r + 1$, repeating edge values outside the picture) three times horizontally and vertically.
One box pass has variance $((2r + 1)^2 - 1)/12 = r(r + 1)/3$, so three passes give $r(r + 1) = \sigma^2$, which solves to
$r = \max(1, \mathrm{round}((\sqrt{4\sigma^2 + 1} - 1)/2))$. If $\sigma < 0.3$, there is no blur.
n = 2r + 1$ has variance $(n^2 - 1)/12$, and cascaded independent blurs add variances. Three box blurs approach a Gaussian by the central limit theorem with variance $r(r + 1)$, so 𝑟 is the rounded positive root of $r^2 + r - \sigma^2 = 0$. A box blur costs a constant per pixel with running sums. References: R17 Wells 1986 · R14 Gonzalez · Woods 2018Inpainting: unknown pixels are visited in order of distance from known pixels (outer rings first) and filled with the average of the 8-neighbors already settled one ring further in.
$\displaystyle U(p)=\frac1{|\mathcal N_p|}\sum_{q\in\mathcal N_p}U(q),\qquad \mathcal N_p=\lbrace q\in 8\text{-nbr}(p):\ \text{ring}(q)<\text{ring}(p)\rbrace$
Distance transform (chamfer): two sweeps (top → bottom, bottom → top) with weight 1 for a horizontal · vertical step and $\sqrt 2$ for a diagonal step approximate the distance to the nearest marked pixel.
$\displaystyle d(p)=\min\big(d(p),\ d(q)+w_{pq}\big),\qquad w_{pq}\in\lbrace1,\sqrt2\rbrace$
Where it says “within so many steps”, it means the number of steps of a 4-neighbor breadth-first search (Manhattan distance).
M = \min(n, M_\max)$ samples are drawn (with replacement if $n > M_\max$); with k-means++ the first center is uniform and each next center is drawn with probability proportional to the squared distance $D(x)^2$ to the nearest center so far.
Assignment → mean update runs up to 18 times, stopping from the 4th iteration on when fewer than $0.001M$ samples change assignment. An empty cluster is moved to the farthest sample.
$M_\max$ is 50000 for region splitting, 40000 for the region graph of the color model, and 6000 for tones per material.
D(x)^2$, spreading the first centers so the expected error is within $O(\log k)$ of optimal. Distances are taken in perceptual Lab. References: R22 Lloyd 1982 · R23 Arthur · Vassilvitskii 2007 · R7 CIE 2004s \gets s + \mathtt{0x6D2B79F5}$, $t = (s \oplus s \gg 15) \cdot(s \mathbin{\vert} 1)$, $t \gets t \oplus(t + (t \oplus t \gg 7) \cdot(t \mathbin{\vert} 61))$, random number $= (t \oplus t \gg 14)/2^{32}$ (≫ is the unsigned right shift).
Value noise (pencil grain of the rough): a random number 𝑔 in $[-1, 1]$ at each grid point with spacing $\mathrm{cell}$, blended within a grid cell with $s_x = \mathrm{smoothstep}(0, 1, t_x)$, $s_y = \mathrm{smoothstep}(0, 1, t_y)$.
$\displaystyle n(x,y)=\big(g_{00}+(g_{10}-g_{00})s_x\big)(1-s_y)+\big(g_{01}+(g_{11}-g_{01})s_x\big)s_y$
x_0 = \lfloor x\rfloor,\ t_x = x - x_0$ (same vertically), $f = f_{00}(1 - t_x)(1 - t_y) + f_{10}t_x(1 - t_y) + f_{01}(1 - t_x)t_y + f_{11}t_x t_y$.
r = n / m$ (original cells / new cells) is at least 1, the area average of the original interval $[ir, (i + 1)r)$ covered by new cell 𝑖;
if below 1, linear interpolation at $x = (i + 0.5)r - 0.5$.
(i + 0.5)r - 0.5$. References: R14 Gonzalez · Woods 2018s_0 \dots s_{n-1}$ with $x = (n - 1)q / 100,\ k = \lfloor x\rfloor$, the value is $s_k + (s_{k + 1} - s_k)(x - k)$ (the median is $q = 50$). The standard deviation is the population standard deviation divided by 𝑛.
z = (a - \text{mean})/\text{standard deviation}$ (all 0 if the standard deviation is at most $10^{-6}$).
The brightness 𝐿 is closed with the line width limit 𝑤 (default $w_0 = \max(3, \mathrm{round}(4s))$, or the automatic setting below, or the set value).
\mathcal C=\mathrm{erode}_w(\mathrm{dilate}_w(L)),\qquad d=\mathcal C-L,\qquad
\mathrm{strength}=\min\!\left(\frac d{\mathcal C},\frac d{0.3}\right)\quad(\mathcal C>0.02,\ d>0)
Note — Why: A line is “darker than its surroundings and thinner than the pen”. Only brightness valleys narrower than the window must be picked to separate lines from wide dark paint (black clothes). How it works: Dilation then erosion (closing) fills dark valleys narrower than the window 𝑤 with the surrounding light values and leaves wide areas alone. The difference 𝑑 from the original (black top-hat) is the line depth; the smaller of the depth relative to the surrounding brightness and the absolute depth over 0.3 is used, so a strong line must be deep in both senses. References: R15 Soille 2003 · R14 Gonzalez · Woods 2018
The hysteresis thresholds come from the line sensitivity $\eta \in[0, 1]$ (default 0.5):
t_{high}=0.58-0.34\,\eta,\qquad t_{low}=0.45\,t_{high}
Starting from pixels with $\mathrm{strength} \ge t_{high}$, it grows into 8-neighbors with $\mathrm{strength} \ge t_{low}$, and pieces smaller than $\max(4, \mathrm{round}(6s))$ pixels are discarded.
$\mathrm{strength}$ is the smaller of “how dark compared with the surrounding bright paint ($\mathcal C$)” ($d/\mathcal C$) and “how dark in absolute terms” ($d/0.3$), so it filters both shallow bumps on dark paint and faint noise on bright paint.
Note — Why: A single threshold breaks lines at faint stretches between dark ones, and lowering it picks up noise as well. How it works: Hysteresis (as in Canny edge detection) starts from sure pixels above the high threshold and grows only into neighbors above the low one. Both thresholds fall linearly as line sensitivity 𝜂 rises; 0.58 · 0.34 · 0.45 and the minimum piece size were tuned on test pictures. References: R18 Canny 1986 · this program’s experiments (7.1)
Filling crossings: starting from lines, up to $w + 1$ steps, it grows into pixels not brighter than the starting line’s brightness $L_{ref}$ by 0.05 or more and with $L \le 0.5$.
Grown lumps that reach the end of the $w + 1$ steps (dark surfaces continuing beyond the line width) are discarded, and the rest are added to the lines.
Note — Why: Where several lines meet, the dark blob is wider than the window, the closing cannot fill it, and the line breaks. How it works: Growth from the line into dark pixels is limited to window size + 1 steps, and blobs that reach the limit (areas wider than the pen) are discarded, so only junctions are filled. 0.05 · 0.5 were set on test pictures. References: this program’s experiments (7.1)
Crisp lines:
d>0.02,\qquad \mathrm{strength}\ge 0.45,\qquad \frac{G_{1.5}(L)-L}d\ge 0.25
Note — Why: Backgrounds are often painted blurred like out-of-focus areas, so dark, crisp lines point to the character. How it works: A thin line loses much of its depth after a slight blur (σ = 1.5) as it mixes with the light surroundings, while an already blurred mark barely changes. So only lines that lose more than 25% of their depth count as crisp (the depth-of-field principle, section 5). References: R13 Hecht 2017 · this program’s experiments (7.2)
$G_\sigma$ is a Gaussian blur. The third condition means “a thin line that loses 25% or more of its depth when slightly blurred”.
The lines and their 1px 8-neighbors are $\mathrm{inMask}$, and the remaining pixels with $A > 0.02$ are $\mathrm{known}$.
Note — Why: Line pixels and their edges have unknown original colors, so they must be left out of color statistics and fills. How it works: The line plus one 8-neighbor ring (the anti-aliasing band) is unknown; the rest, if not practically empty, is known. References: a rule set by this program
Pen width: $\mathrm{strength}$ as above is computed with a generous window $R_b = \max(8, \mathrm{round}(12s))$, and in the distance transform 𝐷 (chamfer) of structures with $\mathrm{strength} \ge 0.5$,
the width $2D - 1$ ($\ge 1.8$) is counted at each 4-neighbor local maximum ($D(p) \ge$ the 𝐷 of its four neighbors, a center line). In the histogram ℎ (0–63) of widths rounded into 1px bins,
the width among $w = 2, \dots, 59$ with the largest sum of $h_k$ over $\lvert k - w \rvert \le \max(1, \mathrm{round}(0.2w))$ is the peak 𝑚,
and the $\lfloor 0.9(n - 1)\rfloor$-th value (one decimal) of the widths at most 3 times 𝑚, in ascending order, is the pen width $w_{90}$. It is not measured if there are fewer than 150 center points.
Note — Why: A small picture drawn with a thick pen has lines the default window cannot hold, so almost no lines are found; the picture’s pen width must be measured. How it works: In the distance transform of dark structures found with a wide window, local maxima are center lines and twice the value minus 1 is the width there. One pen concentrates on one width, so the peak of the histogram summed over a ±20% window is found, and the 90th percentile of widths up to three times the peak (excluding junctions · paint) is the pen width. References: R21 Borgefors 1986 · R14 Gonzalez · Woods 2018 · this program’s experiments (7.1)
w=\begin{cases}\min\big(16,\ \lceil w_{90}/2\rceil+1\big) & \lceil w_{90}/2\rceil+1\ \ge\ w_0+2\\ w_0 & \text{otherwise}\end{cases}
Note — Why: Other stages (background finding by line density) are tuned to the default window, so it is widened only when the measured pen clearly exceeds it, leaving other pictures unchanged. How it works: A square closing of radius 𝑤 fills valleys up to width $2w + 1$, so half the pen width + 1 holds the line. It is used only when at least 2 above the default, capped at 16. References: R15 Soille 2003 · this program’s experiments (7.1)
Pixels covered by lines must satisfy the normal compositing formula.
O_c=a\,K_c+(1-a)\,U_c
Note — Why: The line art is a normal (covering) layer, so the original must be “the line color laid over the color beneath by the alpha”. Solving this gives the line’s alpha and color. How it works: It is Porter–Duff over compositing per channel (ink covers a share 𝑎 of the pixel area). With the color beneath 𝑈 known, fixing either 𝐾 or 𝑎 solves for the other. References: R1 Porter · Duff 1984 · R2 Smith 1995
K = 0$): $a = \mathrm{clamp}(1 - \mathrm{lum}(O)/\mathrm{lum}(U))$ (0 if $\mathrm{lum}(U) \le 0.01$)
O = (1 - a)U$, so $a = 1 - O/U$; the three channels are combined into one lightness to reduce noise. References: R1 Porter · Duff 1984a = \mathrm{clamp}(\max_c(1 - O_c/U_c))$ (only channels with $U_c > 0.004$), $K_c = \mathrm{clamp}((O_c - (1 - a)U_c)/a)$
a \ge 1 - O_c/U_c$ in each channel, so the maximum is the minimal alpha, and 𝐾 is the compositing formula solved for 𝐾. References: R1 Porter · Duff 1984K^0$ = per-channel median of the original colors of line pixels with alpha 0.85 or more (the first bin where the cumulative count reaches half, in the 256-bin 8-bit histogram)The least-squares alpha given a line color 𝐾 (the 𝑎 minimizing $\sum_c (O_c - (aK_c + (1 - a)U_c))^2$; 0 if the denominator is at most $10^{-5}$)
$\displaystyle a(K)=\mathrm{clamp}\!\left(\frac{\sum_c (U_c-O_c)(U_c-K_c)}{\sum_c (U_c-K_c)^2}\right)$
\sum_c (O_c - U_c - a(K_c - U_c))^2$ is quadratic in 𝑎; setting its derivative to zero gives this normal-equation solution (one-variable least squares). When the denominator is near 0 (line color equals the color beneath) it cannot be solved and is set to 0. References: R43 Björck 1996 · R1 Porter · Duff 1984a(K^0) \ge 0.5$, the actual line color $K_c = \mathrm{clamp}((O_c - (1 - a)U_c)/a)$ is computed and inpainted over the whole line area ($\mathrm{inMask}$) to get a smooth line color $\tilde K$.
\tilde K$. References: R1 Porter · Duff 1984 · R20 Telea 2004\Delta E(\tilde K, K^0) \le 6$ and the residual of compositing with $K^0$ is at most 8/255 per channel, it is line art (base line color); otherwise it is color trace.
The color trace alpha is taken at or above the minimum alpha at which the original is reproduced exactly by a line color within 0–1.
$\displaystyle a_{min}=\max_c\left\lbrace\,1-\frac{O_c}{U_c}\ (U_c>0.004),\ \ \frac{O_c-U_c}{1-U_c}\ (O_c>U_c,\ U_c<0.996)\right\rbrace,\qquad a=\max(a(\tilde K),a_{min})$
The color trace color of that pixel is $K_c = \mathrm{clamp}((O_c - (1 - a)U_c)/a)$. $1 - O_c/U_c$ is the minimum alpha that keeps the line color from going below 0, and $(O_c - U_c)/(1 - U_c)$ the minimum alpha that keeps it from going above 1.
K = (O - (1 - a)U)/a$ is at least 0 only if $a \ge 1 - O/U$, and at most 1 only if $a \ge (O - U)/(1 - U)$ (when 𝑂 > 𝑈). With an alpha below the largest of these bounds no color can produce the original, so the larger of the least-squares alpha and this bound is used. References: R1 Porter · Duff 1984a(K^0)$ and $K^0$.
K^0$ and its least-squares alpha. 0.3% was set on test pictures. References: this program’s experiments (7.1)Pixels with alpha at most 0.02 are treated as not lines, and their restored color is reset to the original.
← README · Next: 4.5 Background