Ticket #1411 (closed enhancement: fixed)

Opened 9 years ago

Last modified 9 years ago

Speed up spatially varying convolution by interpolating over a specified block size

Reported by: rowen Owned by: rowen
Priority: normal Milestone:
Component: afw Keywords:
Cc: rhl, rowen, bick, jarvis Blocked By:
Blocking: Project: LSST
Version Number: 3.6.0
How to repeat:

not applicable

Description

My attempt to use linear interpolation by detecting the block size over which to convolve did not work. Somebody suggested simply specifying the block size over which to convolve and this seems like an excellent idea to me. Very simple and it should work. I hope to also support the piecewise constant approximation since it requires very similar code and parameters and will allow direct performance comparison with Andy Becker's HOTPANTS code.

Change History

comment:1 Changed 9 years ago by DefaultCC Plugin

  • Cc rhl, rowen, bick added

comment:2 Changed 9 years ago by rowen

To expand on "did not work": my test for whether linear interpolation was suitably accurate at a given scale almost always failed, so linear interpolation was rarely used. I could try a fancier test, but would prefer to try a simpler alternative.

comment:3 Changed 9 years ago by rowen

  • Status changed from new to assigned

comment:4 Changed 9 years ago by rhl

  • Cc jarvis added

How are you planning to confirm that the scale chosen is correct? This sounds like a dangerous option to me.

I'm surprised that, given the known functional form of the Kernel variation, you cannot figure out the interpolation scale without the expense that you are currently going to. What does Mike Jarvis do?

comment:5 Changed 9 years ago by rowen

  • Status changed from assigned to closed
  • Resolution set to fixed

I expect convolution over a spatial scale of 10 pixels should be safe and I doubt interpolating over larger scales is not likely to supply much additional speedup. Thus I have implemented it as stated. Martin wanted something fancier with kernels presenting their spatial scale and will make that a new ticket, but I do not plan to implement it for PT 1.1 and I doubt we need it at all.

Here are my timings on lsst8

afw ticket 1411:

-bash-3.2$ examples/timeSpatiallyVaryingConvolve.py $AFWDATA_DIR/871034p_1_MI
All kernels use a spatial model of a Polynomial2 of order 3

AnalyticKernel using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	33.85
2112	4644	11	11	142.92
2112	4644	19	19	418.49
AnalyticKernel using linear interpolation over 10 x 10 pixels
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	8.47
2112	4644	11	11	29.52
2112	4644	19	19	82.82
AnalyticKernel using linear interpolation over 20 x 20 pixels
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	6.11
2112	4644	11	11	25.60
2112	4644	19	19	75.52

SeparableKernel using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	16.57
2112	4644	11	11	45.07
2112	4644	19	19	103.94

LinearCombinationKernel with 5 Gaussian Basis Kernels using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	14.02
2112	4644	11	11	38.74
2112	4644	19	19	102.46
LinearCombinationKernel with 5 Gaussian Basis Kernels using linear interpolation over 10 x 10 pixels
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	8.16
2112	4644	11	11	27.26
2112	4644	19	19	72.75
LinearCombinationKernel with 5 Gaussian Basis Kernels using linear interpolation over 20 x 20 pixels
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	5.98
2112	4644	11	11	24.03
2112	4644	19	19	68.03

LinearCombinationKernel with Delta Function Basis using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	21.72
2112	4644	11	11	55.07
2112	4644	19	19	144.88
LinearCombinationKernel with Delta Function Basis using linear interpolation over 10 x 10 pixels
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	8.26
2112	4644	11	11	27.39
2112	4644	19	19	73.05
LinearCombinationKernel with Delta Function Basis using linear interpolation over 20 x 20 pixels
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	6.01
2112	4644	11	11	24.09
2112	4644	19	19	68.11

afw 3.6.0
I did not run interpolation tests since interpolation was rarely if ever used in afw 3.6.0
(the issue this ticket attempts to correct).

-bash-3.2$ python timeOldSpatiallyVaryingConvolve.py 
All kernels use a spatial model of a Polynomial2 of order 3

-bash-3.2$ python timeOldSpatiallyVaryingConvolve.py $AFWDATA_DIR/871034p_1_MI
All kernels use a spatial model of a Polynomial2 of order 3

AnalyticKernel using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	35.79
2112	4644	11	11	143.49
2112	4644	19	19	416.57

SeparableKernel using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	16.22
2112	4644	11	11	43.45
2112	4644	19	19	102.90

LinearCombinationKernel with 5 Gaussian Basis Kernels using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	21.13
2112	4644	11	11	50.76
2112	4644	19	19	119.59

LinearCombinationKernel with Delta Function Basis using no interpolation
ImWid	ImHt	KerWid	KerHt	Sec/Cnv
2112	4644	5	5	72.98
2112	4644	11	11	356.12
2112	4644	19	19	1062.69

Comments:

  • afw 3.6.0 has a specialization for delta function kernels but it is clearly not as fast as the Kreso algorithm for speeding up LinearCombinationKernels? by reducing the number of basis kernels. I removed that specialization in afw ticket 1411. (Kreso's algorithm was added in ticket #1437, which came after afw 3.6.0).
  • The speedup is not as large as I had hoped (except for LinearCombinationKernels made up of delta function basis, where Kreso's algorithm is providing most of the gin). I will run profiling to see what is going on. One known issue is that I reallocate space for many kernel images during the interpolation (because the current design of KernelImagesForRegion does not permit reusing existing kernel image memory). That could certainly be changed, but I want proof that it is a significant problem first, since it is a safety feature.
Note: See TracTickets for help on using tickets.