convolution vs. correlation

[Winnok De Vos]

Dear members of the ImageJ list,

While browsing through some image and signal analysis textbooks, I got a bit confused about the definition of convolution.
Defined as f(i,j)=Sum(Sum(w(x,y)*I(i-x,j-y))) but in ImageJ the Convolve operator appears to be implemented as f(i,j)=Sum(Sum(w(x,y)*I(i+x,j+y))), which I find to be the definition of correlation. While this shouldn't matter for symmetric kernels, it does for asymmetric kernels and also I wonder what the implications are for translating operations to frequency space. Is this typical for image processing  and could anyone explain the rationale for this?
My apologies if this a trivial question or if this question has already been addressed.
Many thanks in advance for a reply.
Sincerely
John.

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Walter O'Dell PhD]

hey John,

this set of my class notes should be helpful:
http://odell.radonc.med.ufl.edu/courses/BMEgradLab/ImgProcOutline3.html#conv

You are correct about the convolution equation being incorrect in ImageJ because it is missing the minus sign, and that this is thus image correlation.  But most normal people use convolution for filtering, such as applying a gaussian filter, which uses kernels that are symmetric, so it doesn't matter (as you acknowledge).

Convolution in the spatial (normal) domain is equivalent to multiplication in the frequency domain, so when you talk about convolution in the frequency domain it means using the minus sign (so true convolution and not correlation).  There is no easy equivalent of correlation in the frequency domain.

I think the bottom line is that the 2D convolution equation in imageJ is incorrect.  In my work, I have my own library of functions that includes convolution in 2D and 3D and I use the correct equation for those.

-Walter


On Feb 24, 2013, at 8:35 AM, Winnok De Vos wrote:

> Dear members of the ImageJ list,
>
> While browsing through some image and signal analysis textbooks, I got a bit confused about the definition of convolution.
> Defined as f(i,j)=Sum(Sum(w(x,y)*I(i-x,j-y))) but in ImageJ the Convolve operator appears to be implemented as f(i,j)=Sum(Sum(w(x,y)*I(i+x,j+y))), which I find to be the definition of correlation. While this shouldn't matter for symmetric kernels, it does for asymmetric kernels and also I wonder what the implications are for translating operations to frequency space. Is this typical for image processing  and could anyone explain the rationale for this?
> My apologies if this a trivial question or if this question has already been addressed.
> Many thanks in advance for a reply.
> Sincerely
> John.
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

Walter O'Dell, PhD
Assistant Professor, Dept. of Radiation Oncology
PO Box 100385
University of Florida
Gainesville, FL
352-273-9030
[hidden email]
http://odell.radonc.med.ufl.edu

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Cory Quammen]

[snip]

> Convolution in the spatial (normal) domain is equivalent to multiplication in the frequency domain, so when you talk about convolution in the frequency domain it means using the minus sign (so true convolution and not correlation).  There is no easy equivalent of correlation in the frequency domain.

The correlation theorem states that correlation in the frequency
domain is equivalent to multiplication of one signal's Fourier
transform with the complex conjugate of the Fourier transform of the
other function. See, for example,
http://ugastro.berkeley.edu/infrared/ir_clusters/convolution.pdf

[snip]

If you want ImageJ to perform a true convolution instead of a
correlation, all you have to do is flip the convolution kernel in all
dimensions. I believe you can do this in ImageJ with Image ->
Transform -> {Flip Horiztontally, Flip Vertically, and Flip in Z}

I hope that helps,
Cory

>
>
> On Feb 24, 2013, at 8:35 AM, Winnok De Vos wrote:
>
>> Dear members of the ImageJ list,
>>
>> While browsing through some image and signal analysis textbooks, I got a bit confused about the definition of convolution.
>> Defined as f(i,j)=Sum(Sum(w(x,y)*I(i-x,j-y))) but in ImageJ the Convolve operator appears to be implemented as f(i,j)=Sum(Sum(w(x,y)*I(i+x,j+y))), which I find to be the definition of correlation. While this shouldn't matter for symmetric kernels, it does for asymmetric kernels and also I wonder what the implications are for translating operations to frequency space. Is this typical for image processing  and could anyone explain the rationale for this?
>> My apologies if this a trivial question or if this question has already been addressed.
>> Many thanks in advance for a reply.
>> Sincerely
>> John.
>>
>> --
>> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>
>
> Walter O'Dell, PhD
> Assistant Professor, Dept. of Radiation Oncology
> PO Box 100385
> University of Florida
> Gainesville, FL
> 352-273-9030
> [hidden email]
> http://odell.radonc.med.ufl.edu
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

--
Cory Quammen
Research Associate
Department of Computer Science
The University of North Carolina at Chapel Hill

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Winnok De Vos]

Hi Walter

Thanks for the confirmation and documented reply.
In Matlab the conv2 command does the correct convolution, but the more dedicated imfilter command seems to perform correlation just like imageJ does. This is why I wondered whether it was more of a generic implementation in image processing.
Best

On 25 Feb 2013, at 01:54, Walter O'Dell wrote:

hey John,

this set of my class notes should be helpful:
http://odell.radonc.med.ufl.edu/courses/BMEgradLab/ImgProcOutline3.html#conv

You are correct about the convolution equation being incorrect in ImageJ because it is missing the minus sign, and that this is thus image correlation.  But most normal people use convolution for filtering, such as applying a gaussian filter, which uses kernels that are symmetric, so it doesn't matter (as you acknowledge).

Convolution in the spatial (normal) domain is equivalent to multiplication in the frequency domain, so when you talk about convolution in the frequency domain it means using the minus sign (so true convolution and not correlation).  There is no easy equivalent of correlation in the frequency domain.

I think the bottom line is that the 2D convolution equation in imageJ is incorrect.  In my work, I have my own library of functions that includes convolution in 2D and 3D and I use the correct equation for those.

-Walter

> Dear members of the ImageJ list,
>
> While browsing through some image and signal analysis textbooks, I got a bit confused about the definition of convolution.
> Defined as f(i,j)=Sum(Sum(w(x,y)*I(i-x,j-y))) but in ImageJ the Convolve operator appears to be implemented as f(i,j)=Sum(Sum(w(x,y)*I(i+x,j+y))), which I find to be the definition of correlation. While this shouldn't matter for symmetric kernels, it does for asymmetric kernels and also I wonder what the implications are for translating operations to frequency space. Is this typical for image processing  and could anyone explain the rationale for this?
> My apologies if this a trivial question or if this question has already been addressed.
> Many thanks in advance for a reply.
> Sincerely
> John.
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

Walter O'Dell, PhD
Assistant Professor, Dept. of Radiation Oncology
PO Box 100385
University of Florida
Gainesville, FL
352-273-9030
[hidden email]
http://odell.radonc.med.ufl.edu

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Shall, Sydney]

Dear Dr O'Dell and everybody else,
I thank you for your clarification.
I would like to ask a small favour please.
I do not feel that I understand properly when it is appropriate to use
convolution in image processing.
Could you direct me to a suitable source of reading that is not too
advanced.
I work in Haematology and therefore I am usually concerned with cells,
most often from the bone marrow.
With many thanks,
Sydney Shall

On 25/02/2013 00:54, Walter O'Dell wrote:

> hey John,
>
> this set of my class notes should be helpful:
> http://odell.radonc.med.ufl.edu/courses/BMEgradLab/ImgProcOutline3.html#conv
>
> You are correct about the convolution equation being incorrect in ImageJ because it is missing the minus sign, and that this is thus image correlation.  But most normal people use convolution for filtering, such as applying a gaussian filter, which uses kernels that are symmetric, so it doesn't matter (as you acknowledge).
>
> Convolution in the spatial (normal) domain is equivalent to multiplication in the frequency domain, so when you talk about convolution in the frequency domain it means using the minus sign (so true convolution and not correlation).  There is no easy equivalent of correlation in the frequency domain.
>
> I think the bottom line is that the 2D convolution equation in imageJ is incorrect.  In my work, I have my own library of functions that includes convolution in 2D and 3D and I use the correct equation for those.
>
> -Walter
>
>
> On Feb 24, 2013, at 8:35 AM, Winnok De Vos wrote:
>
>> Dear members of the ImageJ list,
>>
>> While browsing through some image and signal analysis textbooks, I got a bit confused about the definition of convolution.
>> Defined as f(i,j)=Sum(Sum(w(x,y)*I(i-x,j-y))) but in ImageJ the Convolve operator appears to be implemented as f(i,j)=Sum(Sum(w(x,y)*I(i+x,j+y))), which I find to be the definition of correlation. While this shouldn't matter for symmetric kernels, it does for asymmetric kernels and also I wonder what the implications are for translating operations to frequency space. Is this typical for image processing  and could anyone explain the rationale for this?
>> My apologies if this a trivial question or if this question has already been addressed.
>> Many thanks in advance for a reply.
>> Sincerely
>> John.
>>
>> --
>> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>
> Walter O'Dell, PhD
> Assistant Professor, Dept. of Radiation Oncology
> PO Box 100385
> University of Florida
> Gainesville, FL
> 352-273-9030
> [hidden email]
> http://odell.radonc.med.ufl.edu
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

--
Professor Sydney Shall,
Department of Haematological Medicine,
King's College London,
Medical School,
123 Coldharbour Lane,
LONDON SE5 9NU,
Tel & Fax: [phone],
E-Mail: sydney.shall,
[correspondents outside the College should add; @kcl.ac.uk]
www.kcl.ac.uk

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Herbie-2]

Sydney Shall,

although it's one of my fields (linear systems theory) I'm not aware of
a good _and_ easy to grasp text in English, although it may exist. Of
course, there are very many text books dealing with linear systems
theory (in one and more dimensions) and I prefer the classic ones but
they are not written for people coming form fields like yours...

To answer your question in short with an example:
Imagine a conventional over-head or slide projector. Imagine further
that it has perfect optics and that we can neglect optic diffraction.
Then, we can assume that a point on the slide becomes a point on the
projection screen. If we de-focus the projector optics, then _every_
point on the slide becomes a (small) light disc on the screen. In this
case the so-called point-response of the system (the projector) is this
disc (that can be described as a mathematical two-dimensional function).
If we know a system's point-response -- that may be of arbitrary shape
(and may even show negative values, which is impossible with our
projector example, because light intensity is always positive) -- and
wish to know how the output of this system with regard to its input
signal (image), which in our example is the slide, then we have to
replace _every_ point of the input signal by the system's point-response.

Replacing _every_ point of the input signal (image) by the system's
point-response gives you the output signal (image), provided the system
can fully be described by a single point-response.
The latter is true for so-called linear and space-invariant systems.
Optical systems, such as a projector, are linear (except for
pathologically high light intensities) but they need not be
space-invariant. Imagine that a projector works sharper at the image
center i.e. it has a smaller point-response at the center than at the
imaging periphery, then you are confronted with a typical space-variant
system that needs, in principle a continuum of point-responses for its
exact description.

Now, if you deal with linear and space-invariant systems that are
described by their point-response, you can formalize the "replacement of
every point of the input by the point-response" by an integral of a
product of two functions (input and point-response). This integral is
called the convolution integral and it describes the replacement
operation and the summing up of all the replaced points by the
point-response in the output.

In essence the whole convolution operation can easily be imagined or
visually exemplified and you need not care about the mathematical
formulation in the first place.

HTH

Herbie
____________________________________
On 25.02.13 11:22, Shall, Sydney wrote:

> Dear Dr O'Dell and everybody else,
> I thank you for your clarification.
> I would like to ask a small favour please.
> I do not feel that I understand properly when it is appropriate to use
> convolution in image processing.
> Could you direct me to a suitable source of reading that is not too
> advanced.
> I work in Haematology and therefore I am usually concerned with cells,
> most often from the bone marrow.
> With many thanks,
> Sydney Shall
>
> On 25/02/2013 00:54, Walter O'Dell wrote:
>> hey John,
>>
>> this set of my class notes should be helpful:
>> http://odell.radonc.med.ufl.edu/courses/BMEgradLab/ImgProcOutline3.html#conv
>>
>>
>> You are correct about the convolution equation being incorrect in
>> ImageJ because it is missing the minus sign, and that this is thus
>> image correlation. But most normal people use convolution for
>> filtering, such as applying a gaussian filter, which uses kernels that
>> are symmetric, so it doesn't matter (as you acknowledge).
>>
>> Convolution in the spatial (normal) domain is equivalent to
>> multiplication in the frequency domain, so when you talk about
>> convolution in the frequency domain it means using the minus sign (so
>> true convolution and not correlation). There is no easy equivalent of
>> correlation in the frequency domain.
>>
>> I think the bottom line is that the 2D convolution equation in imageJ
>> is incorrect. In my work, I have my own library of functions that
>> includes convolution in 2D and 3D and I use the correct equation for
>> those.
>>
>> -Walter
>>
>>
>> On Feb 24, 2013, at 8:35 AM, Winnok De Vos wrote:
>>
>>> Dear members of the ImageJ list,
>>>
>>> While browsing through some image and signal analysis textbooks, I
>>> got a bit confused about the definition of convolution.
>>> Defined as f(i,j)=Sum(Sum(w(x,y)*I(i-x,j-y))) but in ImageJ the
>>> Convolve operator appears to be implemented as
>>> f(i,j)=Sum(Sum(w(x,y)*I(i+x,j+y))), which I find to be the definition
>>> of correlation. While this shouldn't matter for symmetric kernels, it
>>> does for asymmetric kernels and also I wonder what the implications
>>> are for translating operations to frequency space. Is this typical
>>> for image processing and could anyone explain the rationale for this?
>>> My apologies if this a trivial question or if this question has
>>> already been addressed.
>>> Many thanks in advance for a reply.
>>> Sincerely
>>> John.
>>>
>>> --
>>> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>>
>> Walter O'Dell, PhD
>> Assistant Professor, Dept. of Radiation Oncology
>> PO Box 100385
>> University of Florida
>> Gainesville, FL
>> 352-273-9030
>> [hidden email]
>> http://odell.radonc.med.ufl.edu
>>
>> --
>> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>
>
>

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Prodanov Dimiter]

Hi,

This is indeed the case. ImageJ compute correlations and not convolutions in the spatial dommain.
As noted previously for symmetric kernels this doesn't matter.
For non-symmetric kernels (antis-symmetric f.e.) you have to reflect the kernel along X and Y and apply it as usual.

Best regards,

Dimiter

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html