snibgo's ImageMagick pages

Convolution

blah.

blah

This page assumes that %IMDEV%convert is built with my process modules, and has FFTW, and is an HDRI (floating-point) build. It is also Q32, though this is probably not important.

References

Methods

The basic idea of convolution is fairly simple. We start with two images: a source and a kernel. Each pixel in the result is a weighted average of pixels near the corresponding source pixel, where the kernel defines the weighting.

Explanations of convolution often ignore colour and transparency. This page considers both.

Methods:

  1. "-morphology convolve"
  2. "-convolve"
  3. shift-multiply-add
  4. multiply in frequency domain

Sample inputs

Source images:

toes.png

toes.pngjpg
%IM%convert ^
  toes.png ^
  ( toes_holed.png ^
    -alpha extract ^
    -negate ^
    -morphology erode disk:4 ^
  ) ^
  -compose CopyOpacity -composite ^
  cnv_toes_t.png
cnv_toes_t.png

Kernels:

Code Kernel Enlarged kernel
%IM%convert ^
  -size 20x20 ^
  label:L ^
  -auto-level ^
  -threshold 50%% ^
  -trim +repage ^
  -negate ^
  cnv_kl.png

set bpDO_CIRCLE=1
set bpCIRC_X=0
set bpCIRC_Y=11

set bpDO_CROSS=1
set bpCROSS_X=3
set bpCROSS_Y=5

call %PICTBAT%blockPix ^
  cnv_kl.png

"X" and "O" are possible origins.

cnv_kl.png cnv_kl_bp.png
%IM%convert ^
  cnv_kl.png ^
  -transparent Black ^
  cnv_klt.png

call %PICTBAT%blockPix ^
  cnv_klt.png
cnv_klt.png cnv_klt_bp.png
%IM%convert ^
  -size 9x9 xc:black +antialias ^
  -fill white -draw "line 0,0 8,8" ^
  gradient: ^
  -compose Multiply -composite ^
  cnv_kl2.png

set bpCIRC_X=0
set bpCIRC_Y=0

set bpCROSS_X=4
set bpCROSS_Y=4

call %PICTBAT%blockPix ^
  cnv_kl2.png
cnv_kl2.png cnv_kl2_bp.png
%IM%convert ^
  -size 1x9 gradient: ^
  ( +clone -negate ) ^
  ( +clone -fill White -colorize 100 ) ^
  -combine ^
  cnv_kl3.png

set bpCIRC_X=0
set bpCIRC_Y=0

set bpCROSS_X=0
set bpCROSS_Y=4

call %PICTBAT%blockPix ^
  cnv_kl3.png

set bpDO_CIRCLE=0
set bpDO_CROSS=0
cnv_kl3.png cnv_kl3_bp.png

Impulse images (for source or kernel):

Code Kernel Enlarged kernel
%IM%convert ^
  xc:White ^
  cnv_imp1.png

call %PICTBAT%blockPix ^
  cnv_imp1.png
cnv_imp1.png cnv_imp1_bp.png
%IM%convert ^
  xc:White ^
  -bordercolor Black -border 1 ^
  cnv_imp2.png

call %PICTBAT%blockPix ^
  cnv_imp2.png
cnv_imp2.png cnv_imp2_bp.png
%IM%convert ^
  -size 3x3 xc:Black ^
  -fill White ^
  -draw "point 0,0 point 2,2" ^
  cnv_imp3.png

call %PICTBAT%blockPix ^
  cnv_imp3.png
cnv_imp3.png cnv_imp3_bp.png

Coloured impulse images (for source or kernel):

Code Kernel Enlarged kernel
%IM%convert ^
  xc:#02e ^
  cnv_cimp1.png

call %PICTBAT%blockPix ^
  cnv_cimp1.png
cnv_cimp1.png cnv_cimp1_bp.png
%IM%convert ^
  xc:#02e ^
  -bordercolor Black -border 1 ^
  cnv_cimp2.png

call %PICTBAT%blockPix ^
  cnv_cimp2.png
cnv_cimp2.png cnv_cimp2_bp.png
%IM%convert ^
  -size 3x3 xc:Black ^
  -fill #02e ^
  -draw "point 0,0" ^
  -fill #e02 ^
  -draw "point 2,2" ^
  cnv_cimp3.png

call %PICTBAT%blockPix ^
  cnv_cimp3.png
cnv_cimp3.png cnv_cimp3_bp.png
%IM%convert ^
  -size 3x3 xc:None ^
  -fill #02e ^
  -draw "point 0,0" ^
  -fill #e02 ^
  -draw "point 2,2" ^
  cnv_cimp4.png

call %PICTBAT%blockPix ^
  cnv_cimp4.png
cnv_cimp4.png cnv_cimp4_bp.png

Blurring kernels:

Code Kernel Enlarged kernel
%IM%convert ^
  cnv_imp2.png ^
  -blur 0x1 -auto-level ^
  cnv_blr2d.png

call %PICTBAT%blockPix ^
  cnv_blr2d.png
cnv_blr2d.png cnv_blr2d_bp.png
%IM%convert ^
  cnv_blr2d.png ^
  -crop 1x3+1+0 +repage ^
  cnv_blr1d.png

call %PICTBAT%blockPix ^
  cnv_blr1d.png
cnv_blr1d.png cnv_blr1d_bp.png

Kernels as strings

Sadly, IM commands that use kernels need strings, not images. Moreover, kernels have only one channel, and the weighting is binary: each element is considered either entirely present or entirely absent. (Why these restrictions? I don't know. Simplicity, perhaps.) Values of 0.0 correspond to black, and 1.0 (unlike most of IM) correspond to white.

We can convert an image to a kernel string with my process module img2knl.

for /F "usebackq" %%L in (`%IMDEV%convert ^
  cnv_kl.png ^
  -process img2knl ^
  NULL:`) do set KNL_KL=%%L

echo %KNL_KL% 
7x12:1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,1,1,1,1,1 
for /F "usebackq" %%L in (`%IMDEV%convert ^
  cnv_klt.png ^
  -process img2knl ^
  NULL:`) do set KNL_KLT=%%L

echo %KNL_KLT% 
7x12:1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,-,-,-,-,-,1,1,1,1,1,1,1 

knl2img

The script knl2img.bat does the inverse, creating a kernel image from a kernel string. It works by convolving an impulse image with the kernel. The impulse image is the same size as the kernel, black except for one white pixel at same position as the origin of the kernel.

knl2img only works for single kernels, and uses "-morphology convolve" so treats kernel values "-" as "0", so the result will be fully opaque. See also the bash script kernel2image, probably written by Anthony Thyssen, which is more sophisticated.

Code Kernel Enlarged kernel
call %PICTBAT%knl2img ^
  "%KNL_KL%" cnv_kl_inv.png

call %PICTBAT%blockPix ^
  cnv_kl_inv.png
cnv_kl_inv.png cnv_kl_inv_bp.png

Method: shift-multiply-add

The script convolveSMA.bat correlates an image by first principles. For each pixel in the kernel, it multiplies the image by that kernel pixel, then adds this, offset by the coordinates in the kernel, to the result so far.

The operation is commutative, ie gives the same result when we swap the roles of image and kernel. [No it isn't, because of the kernel origin.]

As it runs convert and save two image files for every kernel pixel, this isn't fast. For fastest speed, put the smaller image (usually the kernel) second. The other way round is massively slower.

The resulting image is larger than the source. If the inputs are WxH and wxh, the output is (W+w-1)x(H+h-1).

Simple examples, with "O" marking the kernel origin:

Blurring kernels:

call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_blr1d.png ^
  cnv_sma_b1d.png 0 0
cnv_sma_b1d.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_blr1d.png ^
  cnv_sma_b1dk.png 0 0 knl
cnv_sma_b1dk.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_blr2d.png ^
  cnv_sma_b2d.png 0 0
cnv_sma_b2d.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_blr2d.png ^
  cnv_sma_b2dk.png 0 0 knl
cnv_sma_b2dk.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_blr2d.png ^
  cnv_sma_b2d1.png 1 1
cnv_sma_b2d1.png

Other kernels:

call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_imp1.png ^
  cnv_sma1.png 0 0
cnv_sma1.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_cimp3.png ^
  cnv_sma2.png 0 0
cnv_sma2.png
call %PICTBAT%convolveSmaBp ^
  cnv_cimp3.png cnv_kl3.png ^
  cnv_sma3.png 0 0
cnv_sma3.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_cimp3.png ^
  cnv_sma4.png 1 1
cnv_sma4.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_blr2d.png ^
  cnv_sma5.png 0 0 none
cnv_sma5.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_blr2d.png ^
  cnv_sma6.png 1 1 none
cnv_sma6.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl2.png cnv_kl3.png ^
  cnv_sma7.png 0 0 none
cnv_sma7.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_kl3.png ^
  cnv_sma8.png 0 0 none
cnv_sma8.png
call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_kl3.png ^
  cnv_sma9.png 0 0 knl
cnv_sma9.png
%IM%convert ^
  cnv_kl3.png ^
  -rotate -90 ^
  cnv_kl3r.png

call %PICTBAT%convolveSmaBp ^
  cnv_kl3.png cnv_kl3r.png ^
  cnv_sma10.png 0 0 none
cnv_sma10.png

The simple examples above illustrate:

Convolutions of photographs:

call %PICTBAT%convolveSMA ^
  toes.png cnv_kl.png cnv_tkl.png . . knl
cnv_tkl.png
rem call %PICTBAT%convolveSMA ^
rem   cnv_kl.png toes.png cnv_tkl2.png . . knl
cnv_tkl2.png
call %PICTBAT%convolveSMA ^
  toes.png cnv_klt.png cnv_tklt.png . . knl
cnv_tklt.png

Enlarging the image by the size of the kernel is, in general, a reasonable action. The image might be a solid-colour rectangle and the kernel might be a blurring filter, so we would expect the result to be larger (in the same way that adding a shadow extends the image).

However, we may want to crop the image to the size of the source. The crop offsets will be the kernel origin.

%IM%convert ^
  cnv_tkl.png ^
  -crop 267x233+3+5 +repage ^
  cnv_tkl_c1.png
cnv_tkl_c1.png
%IM%convert ^
  cnv_tkl.png ^
  -crop 267x233+0+11 +repage ^
  cnv_tkl_c2.png
cnv_tkl_c2.png

The kernel doesn't take full effect until the entire kernel is over the image. In cnv_tkl.png, the left-most and right-most 6 columns, and top and bottom 11 rows, are dark. If we trimmed all these off, the result would be smaller than either the source or the kernel. It would be (W-w+1)x(H-h+1) pixels.

A workaround is to extend the image with -distort SRT 0 and a viewport, and virtual pixel edge, which is the default. For simplicity, we extend the width by twice the kernel width, and the height by twice the kernel height.

Extend the source image.

call %PICTBAT%getImgWH toes.png src_dims
call %PICTBAT%getImgWH cnv_kl.png knl_dims

set sFMT=sVP=^
%%[fx:%src_dims_WW%+2*%knl_dims_WW%]x^
%%[fx:%src_dims_HH%+2*%knl_dims_HH%]-^
%knl_dims_WW%-^
%knl_dims_HH%


for /F "usebackq" %%L in (`%IM%identify ^
  -format "%sFMT%" ^
  xc:`) do set %%L

echo sVP=%sVP%

%IM%convert ^
  toes.png ^
  -define distort:viewport=%sVP% ^
  -distort SRT 0 +repage ^
  cnv_toes_ext.png

echo sVP=%sVP% 
sVP=281x257-7-12 
cnv_toes_ext.png

Convolve the extended source.

call %PICTBAT%convolveSMA ^
  cnv_toes_ext.png cnv_kl.png cnv_tkl_e.png . . knl
cnv_tkl_e.png

Crop the convolution.

set /A OFFS_X=%knl_dims_WW%+0
set /A OFFS_Y=%knl_dims_HH%+11

%IM%convert ^
  cnv_tkl_e.png ^
  -crop ^
    %src_dims_WW%x%src_dims_HH%+%OFFS_X%+%OFFS_Y% ^
  +repage ^
  cnv_tkl_ec.png
cnv_tkl_ec.png

The result is the same size as the source, with no edge effects.

We may create a wrapper around convolveSMA.bat that first extends the source, and lastly crops the result. It needs to know the kernel origin.

Instead of convolving and then cropping to an offset that represents the kernel origin, we could instead first roll the kernel to place the origin top-left, then convolve, and then the final crop doesn't need an offset. [But this seems to change the nature of the blur?? blah]

Method: -morphology convolve

Commands:

-convolve {kernel}. An old form of -morphology convolve {kernel}.

-morphology convolve {kernel}. This never changes the alpha channel. Processes "-" and "0" in a kernel string in the same way.

(These are different.)

-morphology correlate {kernel}

%IM%convert ^
  toes.png ^
  -convolve %KNL_KL% ^
  cnv_kl_c1.png
cnv_kl_c1.pngjpg
%IM%convert ^
  toes.png ^
  -morphology convolve %KNL_KL% ^
  cnv_kl_mc1.png
cnv_kl_mc1.pngjpg
%IM%convert ^
  toes.png ^
  -define "convolve:scale=^!" ^
  -morphology convolve %KNL_KL% ^
  cnv_kl_mc2.png
cnv_kl_mc2.pngjpg

Scaling a kernel

IM can scale kernels with:

-define convolve:scale={kernel_scale}[!^] [,{origin_addition}] [%]

The normalisation flags "^" and "!" are applied first. Then values are multiplied by {kernel_scale}, and finally {origin_addition} is added to just the value at the origin. There is no facility for adding a number to all the kernel values.

The flags "^" and "!" tell IM to normalize the kernel. If the values are all positive (possibly including zero), the flags do the same thing: they scale the values to add to +1.0. Likewise, if the values are all negative (possibly including zero), both flags scale the result so they add to -1.0.

When the kernel has both positive and negative values, the flags operate differently. "^" scales the positive values to add to +1.0 and independently scales the negative values to -1.0. The overall kernel will then add to 0.0.

By contrast, the "!" flag first adds the values. If they already add to zero, it operates as "^", independently scaling positive and negative values so they add to +1.0 and -1.0, and the overall kernel adds to 0.0. If the values don't already add to zero, it scales both positive and negative values together so the overall sum is +1.0.

Examples with the "^" flag:

%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^^" ^
  -morphology Convolve 4x1:0,2,3,8 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from 0 to 0.615385
Forming a output range from 0 to 1 (Normalized)
 0:         0  0.153846  0.230769  0.615385
%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^^" ^
  -morphology Convolve 4x1:0,-2,-3,-8 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from -0.615385 to 0
Forming a output range from -1 to 0 (Sum -1)
 0:         0 -0.153846 -0.230769 -0.615385
%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^^" ^
  -morphology Convolve 4x1:0,-2,-3,8 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from -0.6 to 1
Forming a output range from -1 to 1 (Zero-Summing)
 0:         0      -0.4      -0.6         1
%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^^" ^
  -morphology Convolve 4x1:0,-2,-3,5 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from -0.6 to 1
Forming a output range from -1 to 1 (Zero-Summing)
 0:         0      -0.4      -0.6         1

Examples with the "!" flag:

%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^!" ^
  -morphology Convolve 4x1:0,2,3,8 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from 0 to 0.615385
Forming a output range from 0 to 1 (Normalized)
 0:         0  0.153846  0.230769  0.615385
%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^!" ^
  -morphology Convolve 4x1:0,-2,-3,-8 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from -0.615385 to 0
Forming a output range from -1 to 0 (Sum -1)
 0:         0 -0.153846 -0.230769 -0.615385
%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^!" ^
  -morphology Convolve 4x1:0,-2,-3,8 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from -1 to 2.66667
Forming a output range from -1.66667 to 2.66667 (Normalized)
 0:         0 -0.666667        -1   2.66667
%IM%convert xc: ^
  -define showkernel=1 ^
  -define "convolve:scale=^!" ^
  -morphology Convolve 4x1:0,-2,-3,5 ^
  NULL: 
Kernel "User Defined" of size 4x1+1+0 with values from -0.6 to 1
Forming a output range from -1 to 1 (Zero-Summing)
 0:         0      -0.4      -0.6         1

-define convolve:showkernel=1

-define morphology:showkernel=1

-bias {value}[%] an old form of -define convolve:bias={value}.

-define convolve:bias={value} Adds {value} to the output of the convolution.

We sometimes want a kernel to sum to one or zero.

Zero-sum:

-define convolve:scale=50%\!  -define convolve:bias=50%

If the kernel origin is not specified in the string, it defaults to the mid-coordinate. When the dimension is odd, this is simply the middle pixel:

%IM%convert ^
  xc: ^
  -define convolve:showkernel=1 ^
  -morphology Convolve 3x3:1,2,3,4,5,6,7,8,9 ^
  NULL: 
Kernel "User Defined" of size 3x3+1+1 with values from 1 to 9
Forming a output range from 0 to 45 (Sum 45)
 0:         1         2         3
 1:         4         5         6
 2:         7         8         9

However, when the dimension is even, this is the coordinate to the up-and-left of the centre lines. I'm not sure if this is wise, for FFT transformations.

%IM%convert ^
  xc: ^
  -define convolve:showkernel=1 ^
  -morphology Convolve 4x4:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ^
  NULL: 
Kernel "User Defined" of size 4x4+1+1 with values from 1 to 16
Forming a output range from 0 to 136 (Sum 136)
 0:         1         2         3         4
 1:         5         6         7         8
 2:         9        10        11        12
 3:        13        14        15        16

Drawing icons

Create an icon.

%IM%convert ^
  -size 100x100 xc:None ^
  -fill #02e ^
  -draw "polygon 50,0 0,99 99,99" ^
  -fill #f80 ^
  -draw "circle 30,70 5,70" ^
  cnv_col_knl.png
cnv_col_knl.png

Create points for the origins of icons.

set sPOINTS=^
point 100,100 ^
point 300,120 ^
point 320,120 ^
point 320,220 ^
point 400,375 ^
point 500,25

%IM%convert ^
  -size 600x400 xc:Black ^
  -fill White ^
  -draw "%sPOINTS%" ^
  -fill #808080 ^
  -draw "point 120,250" ^
  -fill #f00 ^
  -draw "point 500,200" ^
  -fill #00f ^
  -draw "point 500,300" ^
  -fill gray(4%%) ^
  -draw "rectangle 201,301,205,305" ^
  cnv_points.png
cnv_points.png

Create text files of the kernel.

call %PICTBAT%img2knl4f ^
  cnv_col_knl.png cnv_col_knl.dat

[No image]

Convolve with these text kernel files.

%IM%convert ^
  cnv_points.png -alpha off ^
  ( -clone 0 ^
    -morphology Convolve @cnv_col_knl_R.dat ) ^
  ( -clone 0 ^
    -morphology Convolve @cnv_col_knl_G.dat ) ^
  ( -clone 0 ^
    -morphology Convolve @cnv_col_knl_B.dat ) ^
  ( -clone 0 ^
    -morphology Convolve @cnv_col_knl_A.dat ) ^
  -delete 0 ^
  -channel RGBA -combine ^
  cnv_icons.png
cnv_icons.png

Where icons overlap, their values (in all four channels) are added.

Where a point isn't white, the values in the icon are reduced.

Colouring pixels in cnv_points.png makes no difference; it doesn't change colours in the result. Non-white pixels in cnv_points.png reduce kernel values in all channels by the same proportion.

We encapulate this in a script, convolveMC.bat. Blah. This writes four text files from the kernel, convolves with them, and combines the results.

Method: convolve by FFT

We can convolve a source image by:

  1. Fourier-transform both the image and the kernel into complex images;
  2. multiply these complex images together;
  3. inverse-transform back to ordinary images.

"-complex multiply" needs the real-and-imaginary form of FFT, so we use "+fft" and "+ift".

"-complex multiply" needs the four inputs (i.e. two complex images) to have the same dimensions. "+fft" would make its input square, with the dimension being a multiple of 2, if it wasn't already. But that would result in two different sizes being used, so we extend the source and kernel images to the same square dimension, before we transform them.

What should that dimension be? It should be the maximum dimension of the source and kernel, plus one if that isn't divisible by 2. This source (toes.png) is 267x233. The kernel (cnv_kl.png) is 7x12. The maximum dimension is 267, which isn't divisible by 2, so we use 268.

[An alternative: maximum of (W+w-1) and (H+h-1), 273 and 244, so max is 273, plus 1 is 274.]

By default, "+fft" normalises the result by dividing by W*H. We could override this default by blah, but instead for this example we multiply the result by W*H = 268*268 = 71824.

A blurring kernel should generally be normalised so the pixels sum to 1.0, so the overall intensity of the result will be that of the source. The kernel cnv_kl.png has 29 white pixels and the rest are black, so it sums to 29. So we normalise in this example by dividing the kernel by 29.

Instead of dividing the kernel by 29, we could divide the source by 29 or the result by 29. The effect would be the same.

Note that multiplying by W*H and dividing by the sum of the kernel is the same as dividing by the mean of the kernel after it has been extended.

[Explain the roll. After extending the kernel, we roll it to place the kernel origin at image coordinate 0,0, the top-left corner.]

%IMDEV%convert ^
  -gravity Center ^
  -background Black ^
  ( toes.png ^
    -extent 274x274 ^
    +fft ^
  ) ^
  ( cnv_kl.png ^
    -evaluate Divide 29 ^
    -extent 274x274 ^
    -roll -137-137 ^
    +fft ^
  ) ^
  -complex multiply ^
  +ift ^
  -evaluate Multiply 71824 ^
  cnv_cf1.png
cnv_cf1.pngjpg

We need to crop. As with the shift-multiply-add method, no crop entirely removes the edge effect. blah

Crop the convolution.

%IM%convert ^
  cnv_cf1.png ^
  -crop 267x233+2+21 ^
  +repage ^
  cnv_cf1_c.png
cnv_cf1_c.png

As before, we can extend the source by twice the width and height of the kernel. But the image needs to be square, with the dimension a multiple of two.

267+2*7 = 281
233+2*12 = 257

The largest of these is 281, so we will use 282 as the dimension. The viewport offsets will be half the number of added pixels:

(282-267)/2 = 7
(282-233)/2 = 24

For the crop offsets, we add the kernel origin. [Wrong. It's more complex?]

7 + 3 = 10
24 + 5 = 29
%IMDEV%convert ^
  -background Black ^
  ( toes.png ^
    -define distort:viewport=282x282-7-24 ^
    -distort SRT 0 +repage ^
    +write cnv_cf2_t.png ^
    +fft ^
  ) ^
  ( cnv_kl.png ^
    -evaluate Divide 29 ^
    -gravity Center ^
    -extent 282x282 ^
    -roll -141-141 ^
    +fft ^
  ) ^
  -complex multiply ^
  +ift ^
  -evaluate Multiply 79524 ^
  cnv_cf2.png
cnv_cf2_t.pngjpg cnv_cf2.pngjpg

Crop the convolution.

%IM%convert ^
  cnv_cf2.png ^
  -crop 267x233+10+29 ^
  +repage ^
  cnv_cf2_c.png
cnv_cf2_c.png

Method summary

[Table: methods horizontally, kernels vertically.]

Kernel Methods
morphology convolve shift-multiply-add FFT complex multiply

Inverse operations

Given an image, and the result from a correlation (or convolution) of that image, what kernel made that result from that image?

A more difficult question: given the result from a correlation (or convolution), what is the "best" image we can make from it?

Kernel scripts

We could use some kernel scripts:

Applications

Performance

Scripts

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

convolveSMA.bat

rem Given images %1 (source) and %2 (kernel),
rem convolves %1 with %2 by shift-multiply-add.
rem Output to %3.
rem Uses HDRI, so images may contain negative values.
rem %4, %5 kernel origin [default: central coordinate]
rem %6 is one of
rem   none: no normalisation of output
rem   knl: normalises output by dividing by sum of (colours times alphas) in kernel.
rem   src: normalises output by dividing by sum of (colours times alphas) in source.
rem %7 is one of
rem   none  no extension of source
rem   str   where str is an IM virtual-pixel setting, first extend the source.

rem Bias?
rem Option to rotate.

rem FIXME: this is wrongly named.
rem the convolution rotates the kernel by 180 degrees.
rem So this is the correlation. ??

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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 csma

set KERNEL=%2

if not "%3"=="" if not "%3"=="." set OUTFILE=%3

set KO_X=%4
if "%KO_X%"=="." set KO_X=

set KO_Y=%5
if "%KO_Y%"=="." set KO_Y=

rem echo KO_X=[%KO_X%] KO_Y=[%KO_Y%]

set NORMALISE=%6
if "%NORMALISE%"=="." set NORMALISE=
if "%NORMALISE%"=="" set NORMALISE=none

set EXT_METH=%7
if "%EXT_METH%"=="." set EXT_METH=
if "%EXT_METH%"=="" set EXT_METH=none


set nNORM=99
if /i %NORMALISE%==none set nNORM=0
if /i %NORMALISE%==knl set nNORM=1
if /i %NORMALISE%==src set nNORM=2
if %nNORM%==99 (
  echo Bad normalise [%NORMALISE%]
  exit /B 1
)

set TMP_EXT=.miff
set TMP_IN=csma_in%TMP_EXT%
set TMP_OUT=csma%TMP_EXT%
set TMP_PXL=csma_pix%TMP_EXT%
set TMP_KNL=csma_knl%TMP_EXT%
set TMP_PXL_C=csma_pix_c%TMP_EXT%
set TMP_PXL_A=csma_pix_a%TMP_EXT%

set SRC_WW=
for /F "usebackq" %%L in (`%IM%identify ^
  -format "SRC_WW=%%w\nSRC_HH=%%h" ^
  %INFILE%`) do set %%L
if "%SRC_WW%"=="" exit /B 1

set K_WW=
for /F "usebackq" %%L in (`%IM%convert ^
  %KERNEL% ^
  +write %TMP_KNL% ^
  ^( +clone -background Black -alpha Background -alpha off ^
     -scale "1x1^!" ^
     +write %TMP_PXL_C% +delete ^) ^
  ^( +clone -alpha extract ^
     -scale "1x1^!" ^
     +write %TMP_PXL_A% +delete ^) ^
  -format "K_WW=%%w\nK_HH=%%h\nK_WH=%%[fx:w*h]\nK_Wm1=%%[fx:w-1]\nK_Hm1=%%[fx:h-1]" ^
  info:`) do set %%L
if "%K_WW%"=="" exit /B 1


%IM%convert %TMP_PXL_C% txt:

:: FIXME: for even-numbers, more sensible to simply divide by 2?
if "%KO_X%"=="" set /A KO_X=(%K_WW%-1)/2
if "%KO_Y%"=="" set /A KO_Y=(%K_HH%-1)/2

set /A ROLL_X=-%KO_X%
set /A ROLL_Y=-%KO_Y%

set sX=
set sY=
if %ROLL_X% GEQ 0 set sX=+
if %ROLL_Y% GEQ 0 set sY=+
set sROLL=-roll %sX%%ROLL_X%%sY%%ROLL_Y%

if "%sROLL%"=="-roll +0+0" set sROLL=

echo %0: sROLL=%sROLL%

:: FIXME: We should normalise here.

if not "%sROLL%"=="" %IM%convert ^
  %TMP_KNL% ^
  %sROLL% ^
  %TMP_KNL%

set sEXT=

if /I not "%EXT_METH%"=="none" (

  set sFMT=sVP=^
%%[fx:%SRC_WW%+2*%K_WW%]x^
%%[fx:%SRC_HH%+2*%K_HH%]-^
%K_WW%-^
%K_HH%

  for /F "usebackq" %%L in (`%IM%identify ^
    -format "!sFMT!" ^
    xc:`) do set %%L

  echo %0: sVP=!sVP!

  set sEXT=^
-virtual-pixel %EXT_METH% ^
-define distort:viewport=!sVP! ^
-distort SRT 0 +repage

  echo %0: sEXT=!sEXT!
)

%IMDEV%convert ^
  %INFILE% ^
  %sEXT% ^
  %TMP_IN%

if ERRORLEVEL 1 exit /B 1

%IM%identify %TMP_IN%

set REAL_HDRI=-define compose:clamp=off -define quantum:format=floating-point +depth

%IMDEV%convert ^
  -size %SRC_WW%x%SRC_HH% xc:None ^
  %REAL_HDRI% ^
  %TMP_OUT%


:: TMP_PXL is a running total of the sum of the kernel pixels.
::
%IMDEV%convert ^
  -size 1x1 xc:None ^
  %REAL_HDRI% ^
  %TMP_PXL%

for /L %%J in (0,1,%K_Hm1%) ^
do for /L %%I in (0,1,%K_Wm1%) ^
do %IMDEV%convert ^
      -define compose:clamp=off ^
      %TMP_OUT% ^
      ^( %TMP_IN% ^
        ^( %TMP_KNL% ^
          -crop 1x1+%%I+%%J +repage ^
          ^( +clone ^
             %TMP_PXL% ^
             %REAL_HDRI% ^
             -compose Plus -composite ^
             +write %TMP_PXL% ^
             +delete ^
          ^) ^
          -scale "%SRC_WW%x%SRC_HH%^!" ^
        ^) ^
        %REAL_HDRI% ^
        -channel RGBA ^
        -compose Multiply -composite ^
        +channel ^
        -repage +%%I+%%J ^
      ^) ^
      %REAL_HDRI% ^
      -background Black ^
      -compose Plus -layers merge ^
      +repage ^
      %TMP_OUT%

%IM%identify %TMP_OUT%

set OUT_WW=
for /F "usebackq" %%L in (`%IM%identify ^
  -format "OUT_WW=%%w\nOUT_HH=%%h" ^
  %TMP_OUT%`) do set %%L
if "%OUT_WW%"=="" exit /B 1


:: FIXME: instead of normalising at the end, quicker to normalise before extending.

if %nNORM%==1 (
  %IMDEV%convert ^
    %TMP_OUT% ^
    ^( %TMP_PXL% +write txt: -scale "%OUT_WW%x%OUT_HH%^!" ^) ^
    -channel RGB ^
    %REAL_HDRI% ^
    -compose DivideSrc -composite ^
    +channel ^
    %OUTFILE%
) else if %nNORM%==2 (
  echo nNORM==2 NYI
  exit /B 1
) else (
  %IMDEV%convert ^
    %TMP_OUT% ^
    %OUTFILE%
)


call echoRestore

@endlocal & set csmaOUTFILE=%OUTFILE%& set csmaKO_X=%KO_X%& set csmaKO_Y=%KO_Y%

convolveSmaBp.bat

rem Calls convolveSMA but output (%3) is a "blockPix" of inputs and output.

@if "%3"=="" exit /B 1

@setlocal

@call echoOffSave

call %PICTBAT%convolveSMA %1 %2 %3 %4 %5 %6 %7

if ERRORLEVEL 1 exit /B 1

set bpDO_CIRCLE=0
set bpDO_CROSS=0

call %PICTBAT%blockPix %1 csb_src.miff

set bpDO_CIRCLE=1
set bpCIRC_X=%csmaKO_X%
set bpCIRC_Y=%csmaKO_Y%

call %PICTBAT%blockPix %2 csb_knl.miff

set bpDO_CIRCLE=0

call %PICTBAT%blockPix %3 csb_out.miff

%IM%convert ^
  -gravity center ^
  -background None ^
  -pointsize 30 ^
  csb_src.miff ^
  pango:"⊛" ^
  csb_knl.miff ^
  pango:"⇒" ^
  csb_out.miff ^
  +append ^
  %3

if ERRORLEVEL 1 exit /B 1

call echoRestore

endlocal

convolveMC.bat

rem Given images %1 (source) and %2 (kernel),
rem convolves %1 with %2 by "-morphology convolve".
rem Output to %3.
rem Uses HDRI, so images may contain negative values.
rem %4, %5 kernel origin [default: central coordinate]
rem %6 is one of
rem   none: no normalisation of output
rem   knl: normalises output by dividing by sum of (colours times alphas) in kernel.
rem   src: normalises output by dividing by sum of (colours times alphas) in source.

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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 cmc

set KERNEL=%2

if not "%3"=="" if not "%3"=="." set OUTFILE=%3

set KO_X=%4
if "%KO_X%"=="." set KO_X=

set KO_Y=%5
if "%KO_Y%"=="." set KO_Y=

rem echo KO_X=[%KO_X%] KO_Y=[%KO_Y%]

set NORMALISE=%6
if "%NORMALISE%"=="." set NORMALISE=
if "%NORMALISE%"=="" set NORMALISE=none

set nNORM=99
if /i %NORMALISE%==none set nNORM=0
if /i %NORMALISE%==knl set nNORM=1
if /i %NORMALISE%==src set nNORM=2
if %nNORM%==99 (
  echo Bad normalise [%NORMALISE%]
  exit /B 1
)

set sSCALE_K=
if %nNORM%==1 (
  set sSCALE_K=-define "convolve:scale=^^^!"
)

echo sSCALE_K=[%sSCALE_K%]

set TMP_EXT=.miff
set TMP_IMG=cmc%TMP_EXT%
set TMP_PXL=cmc_pix%TMP_EXT%
set TMP_KNL=cmc_knl%TMP_EXT%
set TMP_PXL_C=cmc_pix_c%TMP_EXT%
set TMP_PXL_A=cmc_pix_a%TMP_EXT%


set IMG_WW=
for /F "usebackq" %%L in (`%IM%identify ^
  -format "IMG_WW=%%w\nIMG_HH=%%h" ^
  %INFILE%`) do set %%L
if "%IMG_WW%"=="" exit /B 1

set K_WW=
for /F "usebackq" %%L in (`%IM%convert ^
  %KERNEL% ^
  +write %TMP_KNL% ^
  ^( +clone -background Black -alpha Background -alpha off ^
     -scale "1x1^!" ^
     +write %TMP_PXL_C% +delete ^) ^
  ^( +clone -alpha extract ^
     -scale "1x1^!" ^
     +write %TMP_PXL_A% +delete ^) ^
  -format "K_WW=%%w\nK_HH=%%h\nK_Wm1=%%[fx:w-1]\nK_Hm1=%%[fx:h-1]" ^
  info:`) do set %%L
if "%K_WW%"=="" exit /B 1

:: FIXME: for even-numbers, more sensible to simply divide by 2?
if "%KO_X%"=="" set /A KO_X=(%K_WW%-1)/2
if "%KO_Y%"=="" set /A KO_Y=(%K_HH%-1)/2

set sX=
set sY=
if %KO_X% GEQ 0 set sX=+
if %KO_Y% GEQ 0 set sY=+
set sORIG=%sX%%KO_X%%sY%%KO_Y%

call %PICTBAT%img2knl4f %KERNEL% cmc_knl.dat . %sORIG%

%IM%convert ^
  %INFILE% -alpha off ^
  ( -clone 0 ^
    -channel R -separate +channel ^
    %sSCALE_K% ^
    -morphology Convolve @cmc_knl_R.dat ) ^
  ( -clone 0 ^
    -channel G -separate +channel ^
    %sSCALE_K% ^
    -morphology Convolve @cmc_knl_G.dat ) ^
  ( -clone 0 ^
    -channel B -separate +channel ^
    %sSCALE_K% ^
    -morphology Convolve @cmc_knl_B.dat ) ^
  ( -clone 0 ^
    -channel A -separate +channel ^
    %sSCALE_K% ^
    -morphology Convolve @cmc_knl_A.dat ) ^
  -delete 0 ^
  -channel RGBA -combine ^
  %OUTFILE%

call echoRestore

@endlocal & set cmcOUTFILE=%OUTFILE%& set cmcKO_X=%KO_X%& set cmcKO_Y=%KO_Y%

knl2img.bat

rem Given %1 a quoted kernel string 
rem  or name of text file, prefixed with "@",
rem makes image %2 of that kernel.
rem %3 is optional scale parameter, format:
rem   {kernel_scale}[!^] [,{origin_addition}] [%]
rem %4 is post-processing, eg "-auto-level".

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

@setlocal enabledelayedexpansion

rem @call echoOffSave

call %PICTBAT%setInOut %1 k2i

set qKNL=%1
set sKNL=%~1
set OUTFILE=%2

set SCALE=%~3
if "%SCALE%"=="." set SCALE=

set sPOST=%~4
if "%sPOST%"=="." set sPOST=


if "%SCALE%"=="" (
  set sSCALE=
) else (
  set sSCALE=-define "convolve:scale=%SCALE%"
)

if "%sPOST%"=="." set sPOST=

echo sSCALE=%sSCALE%  sPOST=%sPOST%

if "%IM32f%"=="" call %PICTBAT%setIm8

:: We use an impulse image, same size as kernel,
:: black but with white pixel at kernel origin.

:: Sample showkernel output:
::   Kernel "Blur" of size 41x1+20+0 with values from 0 to 0.0796737
:: But "User defined" (two words).

set WW=
set IS_FIRST=1
for /F "usebackq tokens=* eol=: delims= " %%A in (`%IM32f%convert ^
  xc: ^
  -define convolve:showkernel^=1 ^
  -morphology convolve:0 %qKNL% ^
  NULL: 2^>^&1`) do if !IS_FIRST!==1 (
  set SIZE=%%A
  set IS_FIRST=0
)

for /F "tokens=1-4 eol=: delims=x+ " %%A in ("%SIZE:*size =%") do (
  set WW=%%A
  set HH=%%B
  set X=%%C
  set Y=%%D
)

if "%WW%"=="" exit /B 1
if %WW% LSS 0 exit /B 1
if %WW% GTR a exit /B 1
if %WW% GTR A exit /B 1

echo %0: %WW%x%HH%+%X%+%Y%

%IM32f%convert ^
  -size %WW%x%HH% xc:Black ^
  -fill White -draw "point %X%,%Y%" ^
  -define convolve:showkernel^=1 ^
  %sSCALE% ^
  -morphology convolve %qKNL% ^
  %sPOST% ^
  %OUTFILE%

call echoRestore

@endlocal & set k2iOUTFILE=%OUTFILE%

img2knl4.bat

rem Given %1, an image with RGBA channels,
rem creates four kernel strings,
rem writing to environment variable prefix %2, suffixed _R, _G, _B and _A.
rem
rem CAUTION: Do not use this with large kernels, eg > 100 pixels.

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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 i2k

set N=0
set sR=
for /F "usebackq" %%L in (`%IMDEV%convert ^
  %INFILE% ^
  -channel RGBA ^
  -separate ^
  +channel ^
  -process img2knl ^
  NULL:`) do (
  if !N!==0 set sR=%%L
  if !N!==1 set sG=%%L
  if !N!==2 set sB=%%L
  if !N!==3 set sA=%%L
  set /A N+=1
)

if "%sR%"=="" exit /B 1

call echoRestore

endlocal & set i2kOUTFILE=%OUTFILE%& set %2_R=%sR%& set %2_G=%sG%& set %2_B=%sB%& set %2_A=%sA%

img2knl4f.bat

rem Given %1, an image with RGBA channels,
rem creates four kernel strings,
rem writing to text files prefix %2, suffixed _R, _G, _B and _A.
rem %3 is list of channels to extract, any of RGBA any case.
rem %4 is string to insert before the colon.
rem
rem FIXME: When "-process img2knl" can insert text before the colon, use that instead of chStrs.

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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 i2kf

set OUTPREF=%~dpn2
set OUTEXT=%~x2

set CHAN=%3
if "%CHAN%"=="." set CHAN=
if "%CHAN%"=="" set CHAN=RGBA

set BEF_COL=%~4
if "%BEF_COL%"=="." set BEF_COL=

call %PICTBAT%getrgba %CHAN%

if %rgbaR%==1 (
  %IMDEV%convert ^
  %INFILE% ^
  -channel R ^
  -separate ^
  +channel ^
  -process img2knl ^
  NULL: >%OUTPREF%_R%OUTEXT%

  if not "%BEF_COL%"=="" chStrs /p0 /m1 /i%OUTPREF%_R%OUTEXT% /f":" /t%BEF_COL%:
)

if %rgbaG%==1 (
  %IMDEV%convert ^
  %INFILE% ^
  -channel G ^
  -separate ^
  +channel ^
  -process img2knl ^
  NULL: >%OUTPREF%_G%OUTEXT%

  if not "%BEF_COL%"=="" chStrs /p0 /m1 /i%OUTPREF%_G%OUTEXT% /f":" /t%BEF_COL%:
)

if %rgbaB%==1 (
  %IMDEV%convert ^
  %INFILE% ^
  -channel B ^
  -separate ^
  +channel ^
  -process img2knl ^
  NULL: >%OUTPREF%_B%OUTEXT%

  if not "%BEF_COL%"=="" chStrs /p0 /m1 /i%OUTPREF%_B%OUTEXT% /f":" /t%BEF_COL%:
)

if %rgbaA%==1 (
  %IMDEV%convert ^
  %INFILE% ^
  -channel A ^
  -separate ^
  +channel ^
  -process img2knl ^
  NULL: >%OUTPREF%_A%OUTEXT%

  if not "%BEF_COL%"=="" chStrs /p0 /m1 /i%OUTPREF%_A%OUTEXT% /f":" /t%BEF_COL%:
)

dir %OUTPREF%*

call echoRestore

@endlocal

getImgWH.bat

set %2_WW=
for /F "usebackq" %%L in (`%IM%identify ^
  -format "%2_WW=%%w\n%2_HH=%%h\n%2_Wm1=%%[fx:w-1]\n%2_Hm1=%%[fx:h-1]" ^
  %1`) do set %%L

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 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2015 ImageMagick Studio LLC
License: http://www.imagemagick.org/script/license.php
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

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


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 25-September-2016.

Page created 21-Aug-2017 19:14:41.

Copyright © 2017 Alan Gibson.