why is median of a sequence of images slower than mean

Questions and postings pertaining to the usage of ImageMagick regardless of the interface. This includes the command-line utilities, as well as the C and C++ APIs. Usage questions are like "How do I use ImageMagick to create drop shadows?".
Post Reply
c_joerg
Posts: 6
Joined: 2017-11-30T06:59:54-07:00
Authentication code: 1152

why is median of a sequence of images slower than mean

Post by c_joerg »

I’m wondering, why the calculation of a median of 3 images takes so much more time than mean. Now I understand a little bit more about it.

How is the intensity calculated? Just by (R+G+B) /3?
What about the ambiguities? Only a red, green or blue pixel could have the same intensity…
snibgo
Posts: 12159
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: median of a sequence of images operating pixel-by-pixel

Post by snibgo »

Median takes longer than mean because median populates an array with pixel values, sorts it, and chooses the middle value. Mean simply adds, and divides by the number of images.

Intensity is usually calculated according to the current "-intensity" setting. See http://www.imagemagick.org/script/comma ... #intensity
snibgo's IM pages: im.snibgo.com
c_joerg
Posts: 6
Joined: 2017-11-30T06:59:54-07:00
Authentication code: 1152

Re: median of a sequence of images operating pixel-by-pixel

Post by c_joerg »

Thanks for response…
snibgo wrote: 2017-11-30T07:28:55-07:00 Median takes longer than mean because median populates an array with pixel values, sorts it, and chooses the middle value. Mean simply adds, and divides by the number of images.
I know how to calculate a median. A median of 3 is not a big thing but probably always a sort routine is using and there is no optimization for small medians.
snibgo wrote: 2017-11-30T07:28:55-07:00 Intensity is usually calculated according to the current "-intensity" setting. See
If I just call

Code: Select all

convert i1.jpg i2.jpg i3.jpg -evaluate-sequence median result.jpg
‘Rec709Luminance’ is used?
snibgo
Posts: 12159
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: median of a sequence of images operating pixel-by-pixel

Post by snibgo »

Ah, sorry, I was wrong. For sorting pixels, median doesn't use "-intensity" but a fixed formula:

Code: Select all

return(0.212656*pixel->red+0.715158*pixel->green+0.072186*pixel->blue);
EDIT: On sorting, yes, this always happens, even when there is only one image.
snibgo's IM pages: im.snibgo.com
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: median of a sequence of images operating pixel-by-pixel

Post by anthony »

It probably should be using -intensity.

also rather than necro-posting you should have started a new post.
I am splitting the post into a separate topic.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
c_joerg
Posts: 6
Joined: 2017-11-30T06:59:54-07:00
Authentication code: 1152

Re: why is median of a sequence of images slower than mean

Post by c_joerg »

anthony wrote: 2017-11-30T16:35:25-07:00 I am splitting the post into a separate topic.
Thanks…

snibgo wrote: 2017-11-30T09:04:19-07:00 EDIT: On sorting, yes, this always happens, even when there is only one image.
It can’t be only the sorting on the median processing…
As I said before, I’m doing a lot of image processing in ‚MATLAB‘ for time lapse. On most parts a got similar runtimes between ‚MATLAB‘ and ‘ImageMagick’. But on the median processing there is a big difference.
For a median of three images (4000*3000) I need with 'MATLAB' 3.5s and with ‘ImageMagick’ 13s.
Just for Info, how I do the Median processing in MATLAB

Code: Select all

image_1=imread('IMG_0001.tif');
image_2=imread('IMG_0002.tif');
image_3=imread('IMG_0003.tif');

image_1=double(image_1);
image_2=double(image_2);
image_3=double(image_3);

G(:,:,1) = (image_1(:,:,1)*0.212656 + image_1(:,:,2)*0.715158 + image_1(:,:,3)*0.072186);
G(:,:,2) = (image_2(:,:,1)*0.212656 + image_2(:,:,2)*0.715158 + image_2(:,:,3)*0.072186);
G(:,:,3) = (image_3(:,:,1)*0.212656 + image_3(:,:,2)*0.715158 + image_3(:,:,3)*0.072186);


%G=int32(G*1000.0);
%G=uint8(G);
med=median(G,3);
%ind1=med==G(:,:,1);
ind2=med==G(:,:,2);
ind3=med==G(:,:,3);
ind2=repmat(ind2,1,1,3);
ind3=repmat(ind3,1,1,3);


Result=image_1;
Result=not(ind3).*Result + ind3.*image_3;
Result=not(ind2).*Result + ind2.*image_2;
Result=uint8(Result);

imwrite(Result,'Result_M.tif','tif')
snibgo
Posts: 12159
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: why is median of a sequence of images slower than mean

Post by snibgo »

Yes, IM takes about 80 times as long to find the median of 3 4000x3000 images, compared to finding the mean.

I don't know why the difference is so great. True, the mean calculation is trivial: at each pixel we add the values of the channels of the images, and at the end we divide by the count of the images. For median we copy the values of the channels of the images to an array, then sort the array which involves (at each comparison) calculating the grayscale value of two pixels, then copy the mid-array pixel to the result.

How many comparison are needed when sorting 3 elements? Perhaps 6. So we do 12 floating-point calculations of the form gray=a*red + b*green + b*blue for every pixel. Your Matlab code seems to do that only once per pixel.
snibgo's IM pages: im.snibgo.com
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: why is median of a sequence of images slower than mean

Post by fmw42 »

There are more optimal ways to compute the median than what IM does. Search Google for "fast median filter". See for example https://nomis80.org/ctmf.pdf
c_joerg
Posts: 6
Joined: 2017-11-30T06:59:54-07:00
Authentication code: 1152

Re: why is median of a sequence of images slower than mean

Post by c_joerg »

fmw42 wrote: 2017-12-06T20:05:56-07:00 There are more optimal ways to compute the median than what IM does. Search Google for "fast median filter".
I don’t think the median code is the problem. In the MATLAB code, just 0,7s(20%) of the time is for the median.
snibgo wrote: 2017-12-06T18:55:20-07:00 How many comparison are needed when sorting 3 elements? Perhaps 6. So we do 12 floating-point calculations of the form gray=a*red + b*green + b*blue for every pixel. Your Matlab code seems to do that only once per pixel.
The MATLAB Code gives me same result as the convert.

If I understand the code correctly:
1) From the 3 RGB pictures I calculate 3 gray pictures.
2) The median goes only over the 3 gray pictures.
3) If the median from pixel 1 comes from gray picture 1, than the RGB values from picture 1 copied to the result

Step 3 takes more time than median calculation. I think this part needs the most time.
snibgo
Posts: 12159
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: why is median of a sequence of images slower than mean

Post by snibgo »

c_joerg wrote:In the MATLAB code, just 0,7s(20%) of the time is for the median.
Yes. Your Matlab implementation converts image to grayscale, then finds the median. IM doesn't make the images gray, so needs to do that within the comparison function that is called by the sort function. (The code is in statistic.c.)
snibgo's IM pages: im.snibgo.com
c_joerg
Posts: 6
Joined: 2017-11-30T06:59:54-07:00
Authentication code: 1152

Re: why is median of a sequence of images slower than mean

Post by c_joerg »

snibgo wrote: 2017-12-07T00:47:52-07:00 IM doesn't make the images gray, so needs to do that within the comparison function that is called by the sort function. (The code is in statistic.c.)
Not???
http://www.imagemagick.org/Usage/layers ... e-sequence

The "-evaluate-sequence Median" will look for the pixel which has an intensity of the middle pixel from all the images that are given.
Intensity => 0.212656*pixel->red+0.715158*pixel->green+0.072186*pixel->blue

That is for each position it collects and sorts the pixel intensity from each of the images. Then it will pick the pixel that falls in the middle of the sequence.
The key point is that each pixel will come completely from one image, and sorted by intensity. You will never get a mix of values, producing a color mixed from different images. The exact color of each pixel will come completely from one image.
That is what I’m doing in the MATLAB code and the Result is similar to convert median….
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: why is median of a sequence of images slower than mean

Post by anthony »

The command line discards the source images, basically as it only has a single image list, so results of a image process replaces the source image list.
However the imagemagick library does not have that restriction. The results are returned as a completely separate image list, preserving the source images, for the calling program to do with as they like.

What this means is that IM will not simply convert the source images to intensity greyscale but process them as given.
Also the fuction does not return a intensity value but the full color pixel with the median intensity!

NOTE: Imagemagick design criterion was never specifically 'speed' but 'correctness' first. If a faster way can be used then programmers will implement it when they have time and inclination. But correctness was always first.

It is opensource and if you feel inclined you are welcome to try and add or fix things.
I did for a long time, and in the process influenced a lot of the direction IM has taken. But I have moved on now.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: why is median of a sequence of images slower than mean

Post by anthony »

I have updated IM Examples, adding a actual example for median
Its not a great example, but it does the job.
http://www.imagemagick.org/Usage/layers ... seq_median
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
c_joerg
Posts: 6
Joined: 2017-11-30T06:59:54-07:00
Authentication code: 1152

Re: why is median of a sequence of images slower than mean

Post by c_joerg »

anthony wrote: 2017-12-07T16:23:57-07:00 Also the fuction does not return a intensity value but the full color pixel with the median intensity!
Yes of course. The intensity value is only for sort of median. On the end I want to have a full color picture. That’s exact what my MATLAB code is doing. And again my result is similar to convert.
anthony wrote: 2017-12-07T16:23:57-07:00 NOTE: Imagemagick design criterion was never specifically 'speed' but 'correctness' first. If a faster way can be used then programmers will implement it when they have time and inclination. But correctness was always first.
Yes, I understand this…
anthony wrote: 2017-12-07T16:23:57-07:00 It is opensource and if you feel inclined you are welcome to try and add or fix things.
My intention is to remove fast objects from time-lapse videos. For one video I have to call median at least 1000 times. So it’s a big difference if a call is 3,5s or 13s

Right now I can live with my MATLAB code. But I think a solution with ‘ImageMagick’ could be more common.
Post Reply