snibgo's ImageMagick pages

Sparse hald cluts

.. and completing them.

This page arose from a forum question, Color correct an altered image with the unaltered version. It builds on material in Editing with hald cluts.

When an image has been edited or processed, changing tones and color balance, we may want to find an equivalent transformation so we can make corresponding changes to other images.

We can find that colour transformation through a number of methods, such as gain and bias etc. A more accurate method is to create a 3D clut (aka hald clut), populating each entry defined by a colour in the "from" image with the corresponding colour in the "to" image.

The problem then becomes: we have a list of 3D clut coordinates (the "from" colours) and the values at those coordinates (the "to" colours). This is a sparse hald clut, and we want to populate the other values.

So, we find the hald clut that transforms from one image to another image. To do that, we use two lists of colours, combined into a single "transformation image". These lists show important colours in the "from" image, and the corresponding colours in the "to" image.

Sample inputs

We will generally start from two versions of an image, the same size, visually similar to each other, but with some colour variation.

set SRC_FROM=toes.png
set SRC_TO=toes_alt.png
%IM%identify %SRC_FROM% 
%IM%identify %SRC_TO% 
toes.png PNG 267x233 267x233+0+0 16-bit sRGB 320KB 0.000u 0:00.000
toes_alt.png PNG 267x233 267x233+0+0 16-bit sRGB 340KB 0.000u 0:00.000

How different are these images?

%IM%compare -metric RMSE %SRC_FROM% %SRC_TO% NULL: 
2904.78 (0.0443241)

From these two images, we will make a list of "from" colours, and a list of corresponding "to" colours. The process will then create a hald-clut that will transform each "from" colour to its "to" colour, and other colours will be transformed in a reasonable way.

Making the transformation image

The two colour lists are represented by single image, Nx2 pixels, which we call a transformation image. Row 0 is the "from" colours; row 1 is the "to" colours minus the "from" colours.

How do we create a transformation image from the two input images? We show three methods.

1. Make transformation from entire images

We can simply split the "from" image into rows, append the rows sideways, and that becomes row 0 of the transformation image. Similarly, the "to" image is split into rows that are appended, then subtract row 0, and this becomes row 1 of the transformation image. So if the "from" and "to" images contain 35 million pixels, the transformation image will be 35000000x2 pixels, and this large image will be processed for every pixel in the hald clut.

%IMDEV%convert ^
  ( %SRC_FROM% -crop 0x1 +repage +append ) ^
  ( %SRC_TO% -crop 0x1 +repage +append ) ^
  -define compose:clamp=off ^
  ( -clone 0-1 ^
    -compose MinusDst -composite ^
  ) ^
  -delete 1 ^
  -append ^
  +depth ^
  -define "quantum:format=floating-point" ^
  +write info: ^
toes.png PNG 62211x2 32-bit sRGB 0.125u 0:00.127

This Nx2 result, shc_xf1.miff, can be used by the process module to populate the hald clut. But the Shepard's method takes over five hours. The Voronoi method is faster, at seven minutes, but slightly less accurate. This is because input pixels with the same colour correspond to output pixels that have different colours, and the Voronoi method uses just one of these, with no averaging.

2. Make transformation from subsampled images

Resizing the images reduces the data volume, and provides averaging of both the "from" and the "to" colours.

%IMDEV%convert ^
  ( %SRC_FROM% -resize "30x30>" -crop 0x1 +repage +append ) ^
  ( %SRC_TO% -resize "30x30>" -crop 0x1 +repage +append ) ^
  -define compose:clamp=off ^
  ( -clone 0-1 ^
    -compose MinusDst -composite ^
  ) ^
  -delete 1 ^
  -append ^
  +depth ^
  -define "quantum:format=floating-point" ^
  +write info: ^
toes.png PNG 780x2 32-bit sRGB 0.126u 0:00.123

We could "-scale" instead of "-resize", but that wouldn't average any values.

3. Make transformation from frequent colours

If we have cartoon images, where most pixels are one of a relatively small number of colours, we can concentrate on those.

set SRC_FROM_C=toes_cart.png
set SRC_TO_C=toes_cart_alt.png

First, find the most frequent unique colours. Stop counting when a colour accounts for less than 0.01% of the image, or when the colours found so far account for 99.99% of the image.

call %PICTBAT%colProp %SRC_FROM_C% x.csv 0.01 99.99 . shc_freq1.png

if ERRORLEVEL 1 goto error

%IM%identify shc_freq1.png 
shc_freq1.png PNG 5x1 5x1+0+0 16-bit sRGB 292B 0.000u 0:00.000

If hundreds of colours were found, we could reduce them by eliminating colours that are within 0.05% of any preceding colour.

call %PICTBAT%fuzzyUnique shc_freq1.png shc_freq2.png 0.05

if ERRORLEVEL 1 goto error

%IM%identify shc_freq2.png 
shc_freq2.png PNG 5x1 5x1+0+0 16-bit sRGB 292B 0.000u 0:00.000

We could use either shc_freq1.png or shc_freq2.png as row 0 of the transformation image.

Here are the shc_freq2.png colours:

%IM%convert ^
  shc_freq2.png ^
  -scale 2000%% ^

This has found a set of "from" colours. We need the corresponding set of "to" colours. We can't simply repeat the procedure on the "to" image, because colour-changes may have rearranged the order of the most frequent colours.

Instead, the script fromToCols.bat loops through the "from" colours. At each one, it makes a mask that is white where SRC_FROM_C is that colour; otherwise it is black. It uses this mask as opacity to SRC_TO_C and scales it, so we have the mean colour of SRC_TO_C pixels that correspond to the SRC_FROM_C colour. It writes a Nx2 image of the "from" colours and "to" colours.

(This script performs multiple image reads for each "from" colour, so is slow, and is a candidate for turning into a process module.)

call %PICTBAT%fromToCols ^
  %SRC_FROM_C% %SRC_TO_C% 1 ^
  shc_freq1.png ^

call %PICTBAT%minusRow2 ^
  shc_xf3.png ^

%IM%convert ^
  shc_xf3.png ^
  -scale 2000%% ^

We also make a "b" version, from shc_freq2.png.

call %PICTBAT%fromToCols ^
  %SRC_FROM_C% %SRC_TO_C% 1 ^
  shc_freq2.png ^

call %PICTBAT%minusRow2 ^
  shc_xf3b.png ^

%IM%convert ^
  shc_xf3b.png ^
  -scale 2000%% ^

Process module

The module sphaldcl (for SParse HALD CLut) replaces the last image in the current list (the transformation image, size Nx2), with a hald clut.

Option Description
Long form
h N haldlevel N Level of hald, eg 8 for hald:8.
Default = 8.
m string method string Method for populating clut, one of:
    identity the "no-change" clut;
    shepards Shepard's interpolation;
    voronoi Voronoi interpolation;
Default = identity.
p N power N Power parameter for Shepard's. A positive number.
Default = 2.
n N nearest N Just use N nearest colours.
0 means use them all, no limit.
Default = 0.
v verbose Write some text output to stderr.

(Ideally, there would also be 3D triangulation.)

For the identity method, the contents of the transformation image are irrelevant. But it must be in the list, it must have a height of two pixels, and will be replaced by the identity clut.

The Voronoi method sets each output pixel to the nearest sample value.

The basic Shepard's method (see Wikipedia: Inverse distance weighting) is: given sample values ui at locations Li, where i = 0, 1, 2, ... N-1, we want to find the interpolated value u at the general location L. ui is given, and u is calculated, for each of the three colour channels. Each output pixel will be the weighted sum of all the samples.

We have a function di that gives the distance between two locations. In the colour cube, the coordinates are (r,g,b) so:

di = sqrt ((dr2+dg2+db2)/3)

... where:

dr = L.r - Li.r
dg = L.g - Li.g
db = L.b - Li.b

We divide by three so the distance is in the range 0.0 to 1.0. We also have a function for the weight wi assigned to a sample, according to its distance from location L:

wi = 1 / dip

If di==0 for some i, then u=ui.

Otherwise, u is the sum of the products of sample weights times sample values, divided by the sum of the weights:

u = sum(wi*ui) / sum(wi)

Verify process module

Create identity hald cluts, and compare them to "hald:H" versions.

%IMDEV%convert hald:4 shc_h4.miff

%IMDEV%convert ^
  -size 1x2 xc: ^
  -process 'sphaldcl haldlevel 4 method identity' ^

%IM%compare -metric RMSE shc_h4.miff shc_h4p.miff NULL: 
0 (0)
%IMDEV%convert hald:8 shc_h8.miff

%IMDEV%convert ^
  -size 1x2 xc: ^
  -process 'sphaldcl haldlevel 8 method identity' ^

%IM%compare -metric RMSE shc_h8.miff shc_h8p.miff NULL: 
0 (0)

They are the same, which verifies the process module is mapping between 2D and 3D in the same way as IM.

Make the hald cluts

%IMDEV%convert ^
  shc_xf2.miff ^
  -process 'sphaldcl method shepards power 6 v' ^

And make the two versions for method 3. Don't bother to show them.

%IMDEV%convert ^
  shc_xf3.miff ^
  -process 'sphaldcl method shepards power 6 v' ^

%IMDEV%convert ^
  shc_xf3b.miff ^
  -process 'sphaldcl method shepards power 6 v' ^

Use the hald cluts

%IMDEV%convert ^
  %SRC_FROM% ^
  shc_hc2.png ^
  -hald-clut ^
  +depth ^
%IMDEV%convert ^
  %SRC_FROM_C% ^
  shc_hc3.png ^
  -hald-clut ^
  +depth ^
%IM%compare -metric RMSE %SRC_TO% shc_clutted2.png NULL: 
365.404 (0.00557571)

The completed hald has re-created SRC_TO within 1% RMSE.

%IM%compare -metric RMSE %SRC_TO_C% shc_clutted3.png NULL: 
59.5531 (0.000908723)
%IMDEV%convert ^
  %SRC_FROM_C% ^
  shc_hc3b.png ^
  -hald-clut ^
  +depth ^
%IM%compare -metric RMSE %SRC_TO_C% shc_clutted3b.png NULL: 
59.5531 (0.000908723)

The cartoon has been recreated very accurately. This is not surprising, as it contains only few colours.

Increasing performance

Increasing the accuracy

Increasing the accuracy of the transformation is possible, though at the expense of processing time.

Application: tweaking and pinning colours


Application: non-RGB colorspaces



For convenience, .bat scripts are also available in a single zip file. See Zipped BAT files.


rem %1 "from" image
rem %2 "to" image
rem %3 percentage tolerance
rem %4 Nx1 some colours in %1
rem makes %5, Nx2, with corresonding colours in %2.
@rem CAUTION: This assumes SRC_FROM has pixels within given tolerance
@rem   of each colour in COLS_FROM.
@rem If this isn't true, we get bad colours in the second row.

@if "%2"=="" findstr /B "rem @rem" %~f0 & exit /B 1

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 ftc

set SRC_FROM=%1
set SRC_TO=%2
set PC_TOL=%3
set COLS_FROM=%4
set COLS_TO=%5

set TMPOUT=%TMPDIR%ftc_tmp_out.miff

set TMP_SRC_FROM=%TMPDIR%ftc_tmp_src_from.miff
set TMP_SRC_TO=%TMPDIR%ftc_tmp_src_to.miff
set TMP_COLS_FROM=%TMPDIR%ftc_tmp_cols_from.miff

%IM%convert %SRC_TO% %TMP_SRC_TO%

set WW=
for /F "usebackq" %%L in (`%IM%identify ^
  -format "WW=%%w\nHH=%%h\n" ^
  %SRC_FROM%`) do set %%L
if "%WW%"=="" exit /B 1

set CW=
for /F "usebackq" %%L in (`%IM%identify ^
  -format "CW=%%w\nCWm1=%%[fx:w-1]\nCH=%%h\n" ^
  %COLS_FROM%`) do set %%L
if "%CW%"=="" exit /B 1

for /L %%I in (0,1,%CWm1%) do (
  echo %%I

  if %%I==0 (
    set sOUT=%TMPOUT%
  ) else (
    set sOUT=%TMPOUT% +swap +append %TMPOUT%

  %IM%convert ^
    %TMP_SRC_FROM% ^
    ^( %TMP_COLS_FROM% -crop 1x1+%%I+0 +repage -scale "%WW%x%HH%^!" ^) ^
    -compose Difference -composite ^
    -grayscale RMS -threshold %PC_TOL%%% -negate ^
    %TMP_SRC_TO% ^
    +swap ^
    -alpha off -compose CopyOpacity -composite ^
    -scale "1x1^!" ^
    -alpha off ^

%IM%convert ^
  %TMPOUT% ^
  -append ^

call echoRestore

endlocal & set ftcOUTFILE=%OUTFILE%


%IMDEV%convert ^
  %1 ^
  -define compose:clamp=off ^
  -crop "x1" +repage ^
  ( -clone 0-1 ^
    -compose MinusDst -composite ^
  ) ^
  -delete 1 ^
  -append ^
  +depth ^
  -define "quantum:format=floating-point" ^

All images on this page were created by the commands shown, using:

%IM%identify -version
Version: ImageMagick 6.9.5-3 Q16 x86 2016-07-22
Copyright: Copyright (C) 1999-2015 ImageMagick Studio LLC
Visual C++: 180040629
Features: Cipher DPC Modules OpenMP 
Delegates (built-in): bzlib cairo flif freetype jng jp2 jpeg lcms lqr openexr pangocairo png ps rsvg tiff webp xml zlib

To improve internet download speeds, some images may have been automatically converted (by ImageMagick, of course) from PNG to JPG.

Source file for this web page is sphaldcl.h1. To re-create this web page, execute "procH1 sphaldcl".

This page, including the images, is my copyright. Anyone is permitted to use or adapt any of the code, scripts or images for any purpose, including commercial use.

Anyone is permitted to re-publish this page, but only for non-commercial use.

Anyone is permitted to link to this page, including for commercial use.

Page version v1.0 13-August-2017.

Page created 13-Aug-2017 14:51:02.

Copyright © 2017 Alan Gibson.