Subject: Re: very slow operation with big convolve radius - msg#00033

Previous Message by Date: click to view message preview

Re: very slow operation with big convolve radius

yarrow@xxxxxxxxxxxxxxxxxxxxxx wrote: The problem seems to be that a huge chunk of the pixels are virtual pixels Virtual pixels are deadly slow and I'm not sure we could speed it up. If you are dealing with all interior pixels ImageMagick usually returns a direct pointer into memory. However with edge pixels ImageMagick must create an intermediate buffer and copy the virtual pixels one by one and then the image interior pixel with a memcpy(). Even with that a 50 x 50 neighborhood you are asking ImageMagick to copy 2500 pixels to a buffer for each pixel in the image. For even a 100x100 images thats 25 million copies and convolve operations. For a 1000x1000 image that 2.5 billion copies and convolve operations so you can see how ImageMagick might take a while to complete this operation on an even bigger image. The question is, do you really need a sigma of 50. Have you tried 0x3 for example? I do need a big sigma - this isn't a sharpening operation, using a small sigma, it's for larger scale contrast enhancement. (See my original post for a URL describing this technique) The virtual pixels aren't quite that bad - you only need to generate them when within 50 pixels of an edge, so they go up with the circumference of the image not the area. The easiest way I can see for improving virtual pixel speed is to pre-calculate the virtual pixels. At the start of the convolve operation, generate a new clone image that is (in this case) 50 pixels wider and taller than the original, and fill in the edges of the new images *once* with virtual pixels. Then, do the convolve, but use the cloned image + pixels as the source image, offset by +25,+25 - and then no new virtual pixels would be needed. Does that make sense? - Korny -- Kornelis Sietsma http://www.sietsma.com/korny korny@xxxxxxxxxxx goofey: korny yahoo: kornysietsma icq: 2039172 ph: 0421 079 693

Next Message by Date: click to view message preview

Re: very slow operation with big convolve radius

yarrow@xxxxxxxxxxxxxxxxxxxxxx wrote: The easiest way I can see for improving virtual pixel speed is to pre-calculate the virtual pixels. At the start of the convolve operation, generate a new clone image that is (in this case) 50 pixels wider and taller than the original, and fill in the edges of the new images *once* with virtual pixels. Then, do the convolve, but use the cloned image + pixels as the source image, offset by +25,+25 - and then no new virtual pixels would be needed. The overhead of creating a new image is immense for large images and it may be a wash with just accessing virtual pixels directly. However it is worth investigating. Keep in mind that there are 4 different algorithms for generating virtual pixels. Also if we knew an algorithm was selecting pixels in a prescribed fashion we could take advantage of spatial coherence. If you have time to experiment with your suggested algorithm, please post your timing results to this list. I might try - though I'm brand new to ImageMagick, and not sure I'm up to a change of this magnitude... I had to do a fair chunk of fiddling with cygwin just to get it building on my PC for the tests below. And I'd prefer not to have to do much more c fiddling - I'm a Java developer at heart :) </heresy> Oh no! I just checked and a sigma of 0x50 produces a kernel width of 353, not 50 (I'm using ImageMagick Q16 which produces different kernels than Q8 if the radius is 0). No wonder its taking for ever. To get a kernel width of 50 with ImageMagick Q16, use 0x6. That makes sense. But it's the gaussian radius of 50 that I wanted :-} On my system a 1900x1400 image convolved in 80 seconds. Internally UnsharpImage() calls GuassianBlurImage() which uses convolution. If I use BlurImage() instead which uses separatable filters it takes 4 seconds. I patched UnsharpImage() on my system to use BlurImage(), and the same command as before worked in about 30 seconds! Maybe this could be an option for the UnsharpImage function? Assuming BlurImage() is relatively close to GaussianBlurImage() of course. -Korny -- Kornelis Sietsma http://www.sietsma.com/korny korny@xxxxxxxxxxx goofey: korny yahoo: kornysietsma icq: 2039172 ph: 0421 079 693

Previous Message by Thread: click to view message preview

Re: very slow operation with big convolve radius

yarrow@xxxxxxxxxxxxxxxxxxxxxx wrote: The problem seems to be that a huge chunk of the pixels are virtual pixels Virtual pixels are deadly slow and I'm not sure we could speed it up. If you are dealing with all interior pixels ImageMagick usually returns a direct pointer into memory. However with edge pixels ImageMagick must create an intermediate buffer and copy the virtual pixels one by one and then the image interior pixel with a memcpy(). Even with that a 50 x 50 neighborhood you are asking ImageMagick to copy 2500 pixels to a buffer for each pixel in the image. For even a 100x100 images thats 25 million copies and convolve operations. For a 1000x1000 image that 2.5 billion copies and convolve operations so you can see how ImageMagick might take a while to complete this operation on an even bigger image. The question is, do you really need a sigma of 50. Have you tried 0x3 for example? I do need a big sigma - this isn't a sharpening operation, using a small sigma, it's for larger scale contrast enhancement. (See my original post for a URL describing this technique) The virtual pixels aren't quite that bad - you only need to generate them when within 50 pixels of an edge, so they go up with the circumference of the image not the area. The easiest way I can see for improving virtual pixel speed is to pre-calculate the virtual pixels. At the start of the convolve operation, generate a new clone image that is (in this case) 50 pixels wider and taller than the original, and fill in the edges of the new images *once* with virtual pixels. Then, do the convolve, but use the cloned image + pixels as the source image, offset by +25,+25 - and then no new virtual pixels would be needed. Does that make sense? - Korny -- Kornelis Sietsma http://www.sietsma.com/korny korny@xxxxxxxxxxx goofey: korny yahoo: kornysietsma icq: 2039172 ph: 0421 079 693

Next Message by Thread: click to view message preview

Re: very slow operation with big convolve radius

yarrow@xxxxxxxxxxxxxxxxxxxxxx wrote: The easiest way I can see for improving virtual pixel speed is to pre-calculate the virtual pixels. At the start of the convolve operation, generate a new clone image that is (in this case) 50 pixels wider and taller than the original, and fill in the edges of the new images *once* with virtual pixels. Then, do the convolve, but use the cloned image + pixels as the source image, offset by +25,+25 - and then no new virtual pixels would be needed. The overhead of creating a new image is immense for large images and it may be a wash with just accessing virtual pixels directly. However it is worth investigating. Keep in mind that there are 4 different algorithms for generating virtual pixels. Also if we knew an algorithm was selecting pixels in a prescribed fashion we could take advantage of spatial coherence. If you have time to experiment with your suggested algorithm, please post your timing results to this list. I might try - though I'm brand new to ImageMagick, and not sure I'm up to a change of this magnitude... I had to do a fair chunk of fiddling with cygwin just to get it building on my PC for the tests below. And I'd prefer not to have to do much more c fiddling - I'm a Java developer at heart :) </heresy> Oh no! I just checked and a sigma of 0x50 produces a kernel width of 353, not 50 (I'm using ImageMagick Q16 which produces different kernels than Q8 if the radius is 0). No wonder its taking for ever. To get a kernel width of 50 with ImageMagick Q16, use 0x6. That makes sense. But it's the gaussian radius of 50 that I wanted :-} On my system a 1900x1400 image convolved in 80 seconds. Internally UnsharpImage() calls GuassianBlurImage() which uses convolution. If I use BlurImage() instead which uses separatable filters it takes 4 seconds. I patched UnsharpImage() on my system to use BlurImage(), and the same command as before worked in about 30 seconds! Maybe this could be an option for the UnsharpImage function? Assuming BlurImage() is relatively close to GaussianBlurImage() of course. -Korny -- Kornelis Sietsma http://www.sietsma.com/korny korny@xxxxxxxxxxx goofey: korny yahoo: kornysietsma icq: 2039172 ph: 0421 079 693