Convolution kernels

[Knecht, David]

I am trying to understand how a convolution like a 2x2 mean filter  
actually works.  I presume it always starts in the upper left of the  
image.  It would then calculate the average of those first 4 pixels.  
I thought that the sliding window of the convolution resets as it  
moves so that you are always calculating from the original values of  
the image matrix as opposed to using the new calculated value from  
applying the convolution.  I ran a test to confirm, and to my surprise  
it appears that the convolution is applied continuously. Is that  
right?  Is this described somewhere in the documentation?  I would  
imagine that you could filter either way and it is just how the  
algorithm is implemented.  Also, is it described somewhere how imageJ  
handle the edges?  Dave

Dr. David Knecht
Department of Molecular and Cell Biology
Co-head Flow Cytometry and Confocal Microscopy Facility
U-3125
91 N. Eagleville Rd.
University of Connecticut
Storrs, CT 06269
860-486-2200
860-486-4331 (fax)

[Robert Dougherty]

Prof. Knecht,

Looking under the hood, the convolution code starts by making a copy  
of the image.  It then replaces each pixel of the original image by a  
computation made from the copy.  This is how it should be.  I wonder  
about your test methodology.  As for the edges, I had assumed zero-
padding, but it is actually more interesting.  The input image is  
effectively extended by duplicating the edge pixels outward,  
perpendicular to the image.  The corner areas are effectively filled  
with the value of the corner pixel.  Here is the code to get a pixel  
from location (x,y) to use in the convolution.  If x is outside the  
image, then x is replaced with the closest x that is part of the  
image, and similarly for y.

     private float getPixel(int x, int y, float[] pixels, int width,  
int height) {
         if (x<=0) x = 0;
         if (x>=width) x = width-1;
         if (y<=0) y = 0;
         if (y>=height) y = height-1;
         return pixels[x+y*width];
     }

Bob

On Feb 26, 2009, at 8:01 AM, David Knecht wrote:

> I am trying to understand how a convolution like a 2x2 mean filter  
> actually works.  I presume it always starts in the upper left of the  
> image.  It would then calculate the average of those first 4  
> pixels.  I thought that the sliding window of the convolution resets  
> as it moves so that you are always calculating from the original  
> values of the image matrix as opposed to using the new calculated  
> value from applying the convolution.  I ran a test to confirm, and  
> to my surprise it appears that the convolution is applied  
> continuously. Is that right?  Is this described somewhere in the  
> documentation?  I would imagine that you could filter either way and  
> it is just how the algorithm is implemented.  Also, is it described  
> somewhere how imageJ handle the edges?  Dave
>
> Dr. David Knecht
> Department of Molecular and Cell Biology
> Co-head Flow Cytometry and Confocal Microscopy Facility
> U-3125
> 91 N. Eagleville Rd.
> University of Connecticut
> Storrs, CT 06269
> 860-486-2200
> 860-486-4331 (fax)

Robert Dougherty, Ph.D.
President, OptiNav, Inc.
4176 148th Ave. NE
Redmond, WA 98052
[phone]
FAX [phone]
www.optinav.com
[hidden email]

[Knecht, David]

Hi BOb- To test, I took a 20x20 black image and put a single 255 white  
pixel in the middle.  Then I ran a 2x2 mean filter.  I would have  
predicted that only the pixels surrounding the white pixel would be  
affected since all the others are more than 2 pixels away.  I got a  
pattern of values of 12 up to that is 5 pixels high and wide.   Dave

On Feb 26, 2009, at 12:13 PM, Robert Dougherty wrote:

> Prof. Knecht,
>
> Looking under the hood, the convolution code starts by making a copy  
> of the image.  It then replaces each pixel of the original image by  
> a computation made from the copy.  This is how it should be.  I  
> wonder about your test methodology.  As for the edges, I had assumed  
> zero-padding, but it is actually more interesting.  The input image  
> is effectively extended by duplicating the edge pixels outward,  
> perpendicular to the image.  The corner areas are effectively filled  
> with the value of the corner pixel.  Here is the code to get a pixel  
> from location (x,y) to use in the convolution.  If x is outside the  
> image, then x is replaced with the closest x that is part of the  
> image, and similarly for y.
>
>    private float getPixel(int x, int y, float[] pixels, int width,  
> int height) {
>        if (x<=0) x = 0;
>        if (x>=width) x = width-1;
>        if (y<=0) y = 0;
>        if (y>=height) y = height-1;
>        return pixels[x+y*width];
>    }
>
> Bob
>
> On Feb 26, 2009, at 8:01 AM, David Knecht wrote:
>
>> I am trying to understand how a convolution like a 2x2 mean filter  
>> actually works.  I presume it always starts in the upper left of  
>> the image.  It would then calculate the average of those first 4  
>> pixels.  I thought that the sliding window of the convolution  
>> resets as it moves so that you are always calculating from the  
>> original values of the image matrix as opposed to using the new  
>> calculated value from applying the convolution.  I ran a test to  
>> confirm, and to my surprise it appears that the convolution is  
>> applied continuously. Is that right?  Is this described somewhere  
>> in the documentation?  I would imagine that you could filter either  
>> way and it is just how the algorithm is implemented.  Also, is it  
>> described somewhere how imageJ handle the edges?  Dave
>>
>> Dr. David Knecht
>> Department of Molecular and Cell Biology
>> Co-head Flow Cytometry and Confocal Microscopy Facility
>> U-3125
>> 91 N. Eagleville Rd.
>> University of Connecticut
>> Storrs, CT 06269
>> 860-486-2200
>> 860-486-4331 (fax)
>
> Robert Dougherty, Ph.D.
> President, OptiNav, Inc.
> 4176 148th Ave. NE
> Redmond, WA 98052
> [phone]
> FAX [phone]
> www.optinav.com
> [hidden email]

Dr. David Knecht
Department of Molecular and Cell Biology
Co-head Flow Cytometry and Confocal Microscopy Facility
U-3125
91 N. Eagleville Rd.
University of Connecticut
Storrs, CT 06269
860-486-2200
860-486-4331 (fax)

[Robert Dougherty]

Dave,

I can reproduce your results, but I have to enter 2 for the radius,  
which produces a 5x5 kernel.   Entering 1 gives a 3x3 kernel, and  
anything less than 1 gives an interesting 1x1.  I don't know how to  
get a 2x2 mean without a shift.  If a shift is OK, you could convolve  
with

1 1 0
1 1 0
0 0 0

Bob

On Feb 26, 2009, at 11:33 AM, David Knecht wrote:

> Hi BOb- To test, I took a 20x20 black image and put a single 255  
> white pixel in the middle.  Then I ran a 2x2 mean filter.  I would  
> have predicted that only the pixels surrounding the white pixel  
> would be affected since all the others are more than 2 pixels  
> away.  I got a pattern of values of 12 up to that is 5 pixels high  
> and wide.   Dave
>
>

[jmutterer]

David,

As Bob pointed out, the parameter value that you enter in the dialog of the
"Mean..." filter is the radius of the filter, not the diameter. The mean
filter uses circular kernels instead of square kernels. From the RankFilters
source code:
"Radius = 0.5 includes the 4 neighbors of the pixel in the center, "
010
111
010

"radius = 1 corresponds to a 3x3 kernel size."
111
111
111

For radius 2, the kernel used look like :
01110
11111
11111
11111
01110

etc.

Sincerely,
Jerome.

>
> On Thu, Feb 26, 2009 at 8:33 PM, David Knecht <[hidden email]>wrote:
>
>> Hi BOb- To test, I took a 20x20 black image and put a single 255 white
>> pixel in the middle.  Then I ran a 2x2 mean filter.  I would have predicted
>> that only the pixels surrounding the white pixel would be affected since all
>> the others are more than 2 pixels away.  I got a pattern of values of 12 up
>> to that is 5 pixels high and wide.   Dave
>>
>>
>> On Feb 26, 2009, at 12:13 PM, Robert Dougherty wrote:
>>
>>  Prof. Knecht,
>>>
>>> Looking under the hood, the convolution code starts by making a copy of
>>> the image.  It then replaces each pixel of the original image by a
>>> computation made from the copy.  This is how it should be.  I wonder about
>>> your test methodology.  As for the edges, I had assumed zero-padding, but it
>>> is actually more interesting.  The input image is effectively extended by
>>> duplicating the edge pixels outward, perpendicular to the image.  The corner
>>> areas are effectively filled with the value of the corner pixel.  Here is
>>> the code to get a pixel from location (x,y) to use in the convolution.  If x
>>> is outside the image, then x is replaced with the closest x that is part of
>>> the image, and similarly for y.
>>>
>>>   private float getPixel(int x, int y, float[] pixels, int width, int
>>> height) {
>>>       if (x<=0) x = 0;
>>>       if (x>=width) x = width-1;
>>>       if (y<=0) y = 0;
>>>       if (y>=height) y = height-1;
>>>       return pixels[x+y*width];
>>>   }
>>>
>>> Bob
>>>
>>> On Feb 26, 2009, at 8:01 AM, David Knecht wrote:
>>>
>>>  I am trying to understand how a convolution like a 2x2 mean filter
>>>> actually works.  I presume it always starts in the upper left of the image.
>>>>  It would then calculate the average of those first 4 pixels.  I thought
>>>> that the sliding window of the convolution resets as it moves so that you
>>>> are always calculating from the original values of the image matrix as
>>>> opposed to using the new calculated value from applying the convolution.  I
>>>> ran a test to confirm, and to my surprise it appears that the convolution is
>>>> applied continuously. Is that right?  Is this described somewhere in the
>>>> documentation?  I would imagine that you could filter either way and it is
>>>> just how the algorithm is implemented.  Also, is it described somewhere how
>>>> imageJ handle the edges?  Dave
>>>>
>>>> Dr. David Knecht
>>>> Department of Molecular and Cell Biology
>>>> Co-head Flow Cytometry and Confocal Microscopy Facility
>>>> U-3125
>>>> 91 N. Eagleville Rd.
>>>> University of Connecticut
>>>> Storrs, CT 06269
>>>> 860-486-2200
>>>> 860-486-4331 (fax)
>>>>
>>>
>>> Robert Dougherty, Ph.D.
>>> President, OptiNav, Inc.
>>> 4176 148th Ave. NE
>>> Redmond, WA 98052
>>> [phone]
>>> FAX [phone]
>>> www.optinav.com
>>> [hidden email]
>>>
>>
>> Dr. David Knecht
>> Department of Molecular and Cell Biology
>> Co-head Flow Cytometry and Confocal Microscopy Facility
>> U-3125
>> 91 N. Eagleville Rd.
>> University of Connecticut
>> Storrs, CT 06269
>> 860-486-2200
>> 860-486-4331 (fax)
>>
>
>

[Knecht, David]

That explains it.  It should have been pretty obvious since it says  
radius, but I was thinking that entering 2 was 2x2 since I had been  
reading about 2x2 kernels. Thanks- Dave

On Feb 26, 2009, at 6:30 PM, Jerome Mutterer wrote:

> David,
>
> As Bob pointed out, the parameter value that you enter in the dialog  
> of the
> "Mean..." filter is the radius of the filter, not the diameter. The  
> mean
> filter uses circular kernels instead of square kernels. From the  
> RankFilters
> source code:
> "Radius = 0.5 includes the 4 neighbors of the pixel in the center, "
> 010
> 111
> 010
>
> "radius = 1 corresponds to a 3x3 kernel size."
> 111
> 111
> 111
>
> For radius 2, the kernel used look like :
> 01110
> 11111
> 11111
> 11111
> 01110
>
> etc.
>
> Sincerely,
> Jerome.
>
>
>>
>> On Thu, Feb 26, 2009 at 8:33 PM, David Knecht  
>> <[hidden email]>wrote:
>>
>>> Hi BOb- To test, I took a 20x20 black image and put a single 255  
>>> white
>>> pixel in the middle.  Then I ran a 2x2 mean filter.  I would have  
>>> predicted
>>> that only the pixels surrounding the white pixel would be affected  
>>> since all
>>> the others are more than 2 pixels away.  I got a pattern of values  
>>> of 12 up
>>> to that is 5 pixels high and wide.   Dave
>>>
>>>
>>> On Feb 26, 2009, at 12:13 PM, Robert Dougherty wrote:
>>>
>>> Prof. Knecht,
>>>>
>>>> Looking under the hood, the convolution code starts by making a  
>>>> copy of
>>>> the image.  It then replaces each pixel of the original image by a
>>>> computation made from the copy.  This is how it should be.  I  
>>>> wonder about
>>>> your test methodology.  As for the edges, I had assumed zero-
>>>> padding, but it
>>>> is actually more interesting.  The input image is effectively  
>>>> extended by
>>>> duplicating the edge pixels outward, perpendicular to the image.  
>>>> The corner
>>>> areas are effectively filled with the value of the corner pixel.  
>>>> Here is
>>>> the code to get a pixel from location (x,y) to use in the  
>>>> convolution.  If x
>>>> is outside the image, then x is replaced with the closest x that  
>>>> is part of
>>>> the image, and similarly for y.
>>>>
>>>>  private float getPixel(int x, int y, float[] pixels, int width,  
>>>> int
>>>> height) {
>>>>      if (x<=0) x = 0;
>>>>      if (x>=width) x = width-1;
>>>>      if (y<=0) y = 0;
>>>>      if (y>=height) y = height-1;
>>>>      return pixels[x+y*width];
>>>>  }
>>>>
>>>> Bob
>>>>
>>>> On Feb 26, 2009, at 8:01 AM, David Knecht wrote:
>>>>
>>>> I am trying to understand how a convolution like a 2x2 mean filter
>>>>> actually works.  I presume it always starts in the upper left of  
>>>>> the image.
>>>>> It would then calculate the average of those first 4 pixels.  I  
>>>>> thought
>>>>> that the sliding window of the convolution resets as it moves so  
>>>>> that you
>>>>> are always calculating from the original values of the image  
>>>>> matrix as
>>>>> opposed to using the new calculated value from applying the  
>>>>> convolution.  I
>>>>> ran a test to confirm, and to my surprise it appears that the  
>>>>> convolution is
>>>>> applied continuously. Is that right?  Is this described  
>>>>> somewhere in the
>>>>> documentation?  I would imagine that you could filter either way  
>>>>> and it is
>>>>> just how the algorithm is implemented.  Also, is it described  
>>>>> somewhere how
>>>>> imageJ handle the edges?  Dave
>>>>>
>>>>> Dr. David Knecht
>>>>> Department of Molecular and Cell Biology
>>>>> Co-head Flow Cytometry and Confocal Microscopy Facility
>>>>> U-3125
>>>>> 91 N. Eagleville Rd.
>>>>> University of Connecticut
>>>>> Storrs, CT 06269
>>>>> 860-486-2200
>>>>> 860-486-4331 (fax)
>>>>>
>>>>
>>>> Robert Dougherty, Ph.D.
>>>> President, OptiNav, Inc.
>>>> 4176 148th Ave. NE
>>>> Redmond, WA 98052
>>>> [phone]
>>>> FAX [phone]
>>>> www.optinav.com
>>>> [hidden email]
>>>>
>>>
>>> Dr. David Knecht
>>> Department of Molecular and Cell Biology
>>> Co-head Flow Cytometry and Confocal Microscopy Facility
>>> U-3125
>>> 91 N. Eagleville Rd.
>>> University of Connecticut
>>> Storrs, CT 06269
>>> 860-486-2200
>>> 860-486-4331 (fax)
>>>
>>
>>

Dr. David Knecht
Department of Molecular and Cell Biology
Co-head Flow Cytometry and Confocal Microscopy Facility
U-3125
91 N. Eagleville Rd.
University of Connecticut
Storrs, CT 06269
860-486-2200
860-486-4331 (fax)