why is median of a sequence of images slower than mean

[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]

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

[c_joerg]

Thanks for response…

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.

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]

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.

[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.

[c_joerg]

I am splitting the post into a separate topic.

Thanks…

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]

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.

[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]

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.

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]

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.)

[c_joerg]

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….

[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]

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

[c_joerg]

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.

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…

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.