Re: [darktable-dev] possible bug in color look up table module

[Heiko Bauke]

Dear Johannes

Am 31.07.2017 um 04:18 schrieb johannes hanika:
yeah the solver sucks. 


I think I was able to fix it.  See 
https://github.com/rabauke/darktable/tree/fix_colorchecker


I implemented for darktable the approach to calculate the expansion 
coefficients which I outlined in an other e-mail before.  As explained 
in my very first e-mail on this topic the old version of the color look 
up table module caused strange color changes even if source and target 
colors where identical if the number of color patches is small.  My new 
version does no longer show this undesirable behavior.


Nevertheless, users may observe strong color changes if source and 
target colors differ even for minor adjustments of the target colors if 
the number of color patches is small, less than 5 let's say.  This, 
however, I would not consider a bug.  It is an intrinsic feature of the 
applied algorithm and has to be expected when interpolation is applied 
with very few grid points (color patches).  Possibly one should give in 
the user manual a warning/hint that the source colors in the color 
patches must be representative for the input image.  It is not 
sufficient to keep only those colors in the color checker that shall be 
adjusted.  This would lead usually to unintended strong color shifts.


I will test my code further and add some comments to the source code. 
Some error handling for the case that the coefficient matrix still 
becomes singular has to be included, too.  When I think the code is 
mature enough I will open a pull request.



Heiko


--
-- Number Crunch Blog @ https://www.numbercrunch.de
--  Cluster Computing @ http://www.clustercomputing.de
--   Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
--  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke
___
darktable developer mailing list
to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org

Re: [darktable-dev] possible bug in color look up table module

[Heiko Bauke]

Dear Roman,

Am 31.07.2017 um 17:45 schrieb Roman Lebedev:

I suspect you (or your editor) have run clang-format/etc on that file.
Don't do that.


mentioning  clang-format I remember I run clang-format on that file 
indeed.  I did to ensure that my changes are compatible with darktable 
coding style conventions.  I assumed running clang-format would affect 
only lines of code that have been touched by me.


I plan to write a fix for the color look up table module.  I will try to 
 keep the change set as small as possible when opening a pull request.



Heiko


--
-- Number Crunch Blog @ https://www.numbercrunch.de
--  Cluster Computing @ http://www.clustercomputing.de
--   Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
--  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke
___
darktable developer mailing list
to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org

Re: [darktable-dev] possible bug in color look up table module

[Heiko Bauke]

Dear Johannes,

Am 31.07.2017 um 04:18 schrieb johannes hanika:

oh, nice, thanks for looking into this!

i can't parse your diff, it has so many white space changes. could you
maybe fix it or explain what it does? is it just a special case for
the zero-patch case?

yeah the solver sucks. unfortunately eigen is written in c++, so i'm
hesitant to pull it in as a dependency.


in the color look up module we have to solve a linear system of size 
(N+4)x(N+4) where N is the number of color patches.  The problem is that 
for N<=4 the coefficient matrix A has rank N, not the full rank N+4. 
This means that the system has non-unique solutions.  Thus we have to 
pick a reasonable solution among the infinite set of solutions for N<=4. 
 I think the most reasonable solution is to set as many as possible 
coefficients to zero.  For the remaining coefficients, one can derive a 
smaller full-rank linear system.  This approach is numerically very 
stable and explained in more detail in the python prototype attached to 
this e-mail.


Assuming that all source colors are different, the (N+4)x(N+4) 
coefficient matrix has full rank and can be solved by various methods. 
LU-decomposition with partial pivoting but also numerical solution via 
singular value decomposition as implemented in the python script work 
quite well.  I also tried various variants of Newton iteration, which 
often also gives accurate results.  In the Newton iteration approach, 
one minimizes |A*x - b|, where x is the vector of unknowns and b the 
right-hand-side of the linear system.  For the Newton iteration, one has 
to find an approximate solution to a linear system of the form 2*A^2 * y 
= c.  I tried various methods for solving the latter equation.


The modified version of colochecker.c in my github repository deals only 
with the N=0 case.  The diffs may show an unreasonable large change set 
because my editor has automatically removed white spaces at the end of 
lines.



Heiko


--
-- Number Crunch Blog @ https://www.numbercrunch.de
--  Cluster Computing @ http://www.clustercomputing.de
--   Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
--  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke

___
darktable developer mailing list
to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# calculate interpolation coefficients as needed in
# the darktable color look up module 

# import math and plotting modules
import numpy as np
from pylab import *
from scipy.optimize import minimize, curve_fit
from scipy.linalg import *

# the source colors
S=array([37.99, 13.56,  14.06,  # dark skin
 65.71, 18.13,  17.81,  # light skin
 49.93, -4.88,  -21.93, # blue sky
 43.14, -13.10, 21.91,  # foliage
 55.11, 8.84,   -25.40, # blue flower
 70.72, -33.40, -0.20,  # bluish green
 62.66, 36.07,  57.10,  # orange
 40.02, 10.41,  -45.96, # purple red
 51.12, 48.24,  16.25,  # moderate red
 30.33, 22.98,  -21.59, # purple
 72.53, -23.71, 57.26,  # yellow green
 71.94, 19.36,  67.86,  # orange yellow
 28.78, 14.18,  -50.30, # blue
 55.26, -38.34, 31.37,  # green
 42.10, 53.38,  28.19,  # red
 81.73, 4.04,   79.82,  # yellow
 51.94, 49.99,  -14.57, # magenta
 51.04, -28.63, -28.64, # cyan
 96.54, -0.43,  1.19,   # white
 81.26, -0.64,  -0.34,  # neutral 8
 66.77, -0.73,  -0.50,  # neutral 65
 50.87, -0.15,  -0.27,  # neutral 5
 35.66, -0.42,  -1.23,  # neutral 35
 20.46, -0.08,  -0.97   # black
])
S=reshape(S, (24, 3))

channel=1 # select a channel, (0, 1, 2) for (L, a, b)
# reduce number of color mappings for testing
# try N>4 for the nummerically instable cases
N=5
q=array(range(0, 24))
np.random.shuffle(q)
S=S[q[0:N], :] # random selection of original colors

# construct coefficient matrix

# the radial basis function
def kernel(a, b):
r2=dot(a-b, a-b)
return r2*log(r2) if r2>1e-12 else 0

A=zeros((N+4, N+4))
for i in range(0, N):
for j in range(0, N):
A[i, j]=kernel(S[i, :], S[j, :])
A[i, N+0]=A[N+0, i]=1
A[i, N+1]=A[N+1, i]=S[i, 0]
A[i, N+2]=A[N+2, i]=S[i, 1]
A[i, N+3]=A[N+3, i]=S[i, 2]

T=zeros((N+4))
T[0:N]=S[:, channel] + 10*randn(N)  # target color channel, start from original color and modify

# quadratic cost function to be minimized (A must be symetric)
def N2(x):
return norm(dot(A, x)-T)

# gradient of cost function
def dN2(x):
return 2*dot(A, dot(A, x)-T)

# jacobian of cost function
def ddN2():
return 2*dot(A, A)

# solve the linear system, treat special cases N=0, N=1, N=2, N=3, N=4
# extra, solve cases N>4 by different methods

# for N<=4 the linear system has rank N, i.e. less than the dimension
# of the coefficient matrix the linear 

Re: [darktable-dev] possible bug in color look up table module

[johannes hanika]

hi!

oh, nice, thanks for looking into this!

i can't parse your diff, it has so many white space changes. could you
maybe fix it or explain what it does? is it just a special case for
the zero-patch case?

yeah the solver sucks. unfortunately eigen is written in c++, so i'm
hesitant to pull it in as a dependency.

cheers,
 jo

On Fri, Jul 28, 2017 at 9:24 PM, Heiko Bauke  wrote:
> Dear Johannes,
>
> Am 12.07.2017 um 10:06 schrieb johannes hanika:
>>
>> sounds weird, will try to reproduce. the fitting of this function is
>> using a spline, which may be prone to ringing, in between the colours
>> you fixed. it has a linear part that fixes this issue for purely b/w,
>> but may lead to issues for b/w + single colour.
>
>
> I investigated this issue in more detail.  There are two problems with the
> color look up module.
>
> * The module does not deal properly with the border case that the user has
> removed all color fields from the UI.  In this case no color mappings are
> defined.  Thus the module should not alter the image.  This has been fixed
> in https://github.com/rabauke/darktable/tree/fix_colorchecker
>
> * In constructing the color mapping three linear systems of equations have
> to be solved with the same coefficient matrix but with different right hand
> sides (one system for each Lab color channel).  In the case, that all target
> color are identical to their source colors, these systems have the trivial
> solutions
>
> [0, ..., 0, 1, 0, 0]  for L-channel,
> [0, ..., 0, 0, 1, 0]  for a-channel,
> [0, ..., 0, 0, 0, 1]  for b-channel,
>
> which establish an identity mapping between source and target image. This
> has been described by you in more detail in
> http://www.darktable.org/2016/05/colour-manipulation-with-the-colour-checker-lut-module/
> The problem is that if there are only few (in particular less than four)
> source colors or if many target/source colors have vanishing Lab-channels
> (e.g. shades of gray) the coefficient matrix may become (close to) singular
> and the system may have non-unique solutions.  In this case the implemented
> singular-value-decomposition-based solver as implemented in the color look
> up table module gives a solution, which is not even close to the solutions
> mentioned above.
>
> I think one should modify the linear system solver to ensure that it always
> yields the vectors given above if these are valid solutions to the linear
> system.  In the case that these are not valid solutions (e.g. because source
> and target colors differ) but the system has non-unique solutions the solver
> should yield valid solutions which are close as possible to the vectors
> given above.
>
>
>
> Heiko
>
>
> --
> -- Number Crunch Blog @ https://www.numbercrunch.de
> --  Cluster Computing @ http://www.clustercomputing.de
> --   Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
> --  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke
> ___
> darktable developer mailing list
> to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org
>
___
darktable developer mailing list
to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org

Re: [darktable-dev] possible bug in color look up table module

[Heiko Bauke]

Dear Johannes,

Am 12.07.2017 um 10:06 schrieb johannes hanika:

sounds weird, will try to reproduce. the fitting of this function is
using a spline, which may be prone to ringing, in between the colours
you fixed. it has a linear part that fixes this issue for purely b/w,
but may lead to issues for b/w + single colour.


I investigated this issue in more detail.  There are two problems with 
the color look up module.


* The module does not deal properly with the border case that the user 
has removed all color fields from the UI.  In this case no color 
mappings are defined.  Thus the module should not alter the image.  This 
has been fixed in https://github.com/rabauke/darktable/tree/fix_colorchecker


* In constructing the color mapping three linear systems of equations 
have to be solved with the same coefficient matrix but with different 
right hand sides (one system for each Lab color channel).  In the case, 
that all target color are identical to their source colors, these 
systems have the trivial solutions


[0, ..., 0, 1, 0, 0]  for L-channel,
[0, ..., 0, 0, 1, 0]  for a-channel,
[0, ..., 0, 0, 0, 1]  for b-channel,

which establish an identity mapping between source and target image. 
This has been described by you in more detail in
http://www.darktable.org/2016/05/colour-manipulation-with-the-colour-checker-lut-module/ 
The problem is that if there are only few (in particular less than four) 
source colors or if many target/source colors have vanishing 
Lab-channels (e.g. shades of gray) the coefficient matrix may become 
(close to) singular and the system may have non-unique solutions.  In 
this case the implemented singular-value-decomposition-based solver as 
implemented in the color look up table module gives a solution, which is 
not even close to the solutions mentioned above.


I think one should modify the linear system solver to ensure that it 
always yields the vectors given above if these are valid solutions to 
the linear system.  In the case that these are not valid solutions (e.g. 
because source and target colors differ) but the system has non-unique 
solutions the solver should yield valid solutions which are close as 
possible to the vectors given above.



Heiko


--
-- Number Crunch Blog @ https://www.numbercrunch.de
--  Cluster Computing @ http://www.clustercomputing.de
--   Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
--  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke
___
darktable developer mailing list
to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org

Re: [darktable-dev] possible bug in color look up table module

[Heiko Bauke]

Hi,

Am 12.07.2017 um 10:06 schrieb johannes hanika:

sounds weird, will try to reproduce. the fitting of this function is
using a spline, which may be prone to ringing, in between the colours
you fixed. it has a linear part that fixes this issue for purely b/w,
but may lead to issues for b/w + single colour.


I forgot to mention: A user may want to built his own color look up 
table from scratch.  For this purpose one would delete all color patches 
of the default settings first.  The color look up table module with no 
color patches should be a no-op.  However, the image becomes completely 
black if the  color look up table module is applied with an empty set of 
color lookups.



Heiko


PS: I am using a recent built of darktable from git master.

--
-- Number Crunch Blog @ https://www.numbercrunch.de
--  Cluster Computing @ http://www.clustercomputing.de
--   Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
--  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke
___
darktable developer mailing list
to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org

Re: [darktable-dev] possible bug in color look up table module

[johannes hanika]

heya,

sounds weird, will try to reproduce. the fitting of this function is
using a spline, which may be prone to ringing, in between the colours
you fixed. it has a linear part that fixes this issue for purely b/w,
but may lead to issues for b/w + single colour.

cheers,
-jo

On Tue, Jul 11, 2017 at 10:23 PM, Heiko Bauke  wrote:
> Hi,
>
> recently I became aware of some (to me) unexpected behavior of the color
> look up table module.
>
> To reproduce the (possible) bug:
>
> * Activate the color look up module with its standard parameters (which
> causes no color change to the image).
>
> * Remove successively all color patches by a right-click on the patch except
> gray shaded patches.
>
>
> Observed behavior:
>
> * The image color changes dramatically as soon as all color patches are
> removed except one colorful patch and the gray shaded patches.
>
>
> Expected behavior:
>
> The image should not be affected by the color look up table module as long
> as the source color of each patch equals the target color.
>
>
> I am not sure if this actually is a bug.  Possibly just my expectation is
> wrong.  May be some of the darktable core developers can comment on this.
> In case that this is an actual bug I will open a ticket.
>
>
> Regards,
>
> Heiko
>
>
> --
> -- Number Crunch Blog @ https://www.numbercrunch.de
> --  Cluster Computing @ http://www.clustercomputing.de
> --   Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
> --  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke
> ___
> darktable developer mailing list
> to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org
>
___
darktable developer mailing list
to unsubscribe send a mail to darktable-dev+unsubscr...@lists.darktable.org