This shows you the differences between two versions of the page.

integral_images [2011/04/26 13:55] 127.0.0.1 external edit |
integral_images [2013/03/11 13:45] (current) oestape |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | ====== Integral Images ====== | + | ====== Integral Images ====== |

- | [[wp>Integral image|Integral images]] are a fast way to compute the sum of a rectangular region of an image. The main advantage of this algorithm is that once the integral image is computed, we can evaluate the sum of any rectangular region in constant time (the size of the region does not affect the time to compute it), because we just have to add four points of the integral image. This allows to create fast filters to blur the image, find edges or detect many other features. It is equivalent to a [[wp>Convolution|convolution]] with a rectangular and uniform kernel, and it can be used as a rough and fast approximation to a [[wp>Gaussian blur|gaussian blur]]. The first application of this idea in computer vision was in the Viola-Jones (2004) face detector. | + | |

- | + | [[wp>Integral image|Integral images]] are a fast way to compute the sum of a rectangular region of an image. The main advantage of this algorithm is that once the integral image is computed, we can evaluate the sum of any rectangular region in constant time (the size of the region does not affect the time to compute it), because we just have to add four points of the integral image. This allows to create fast filters to blur the image, find edges or detect many other features. It is equivalent to a [[wp>Convolution|convolution]] with a rectangular and uniform kernel, and it can be used as a rough and fast approximation to a [[wp>Gaussian blur|gaussian blur]]. The first application of this idea in computer vision was in the Viola-Jones (2004) face detector. | |

- | {{processing>medium:IntegralImages|pogg}} | + | |

- | Usage: | + | |

- | *Move the mouse to change the size of the filter. Try moving in the X or Y direction separately
| + | |

- | *Press keys 'i' and 'u' to change the image | + | {{processing>medium:IntegralImages|pogg}} |

- | *Press keys 'm' and 'n' to change the filter | + | |

- | *Average | + | Usage: |

- | *Center-Surround
| + | |

- | *Vertical Edge | + | *Move the mouse to change the size of the filter. Try moving in the X or Y direction separately |

- | *Horizontal Edge | + | |

- | *Diagonal Edge | + | *Press keys 'i' and 'u' to change the image |

- | *Vertical Line | + | |

- | *Horizontal Line
| + | *Press keys 'm' and 'n' to change the filter |

- | *Press keys 'k' and 'j' to change the statistical measure: | + | |

- | *Mean | + | *Average |

- | *Standard deviation (StDev) | + | |

- | *Press 'Esc' to stop the applet (reload the page to start again) | + | *Center-Surround |

- | + | ||

- | If you don't have the Java plug-in you can [[http://www.youtube.com/watch?v=S0BuYWB5YVM|watch a video of it]] | + | *Vertical Edge |

- | + | ||

- | Using the **Mean** statistical measure, we get different effects depending on the shape of the filter: | + | *Horizontal Edge |

- | + | ||

- | The **Average** is a rectangle that blurs the image: the texture and noise disappears, but also the details of the image. This is similar to the Gaussian blur that you can find in Photoshop or the Gimp. | + | *Diagonal Edge |

- | {{ :baboon.png?300 |Original image}} | + | |

- | + | *Vertical Line | |

- | {{ :baboon_Integral_Images_Blur.png?300 |Blurred image}} | + | |

- | + | *Horizontal Line | |

- | The **Center-Surround** is an approximation to the [[wp>Difference of Gaussians]] (DoG) which is a useful operation to find edges and binarize the image. | + | |

- | + | *Press keys 'k' and 'j' to change the statistical measure: | |

- | If you use a small surround and a pixel for the center, you find the edges: | + | |

- | {{ :lena_Integral_Images_Edges.png?300 |Edges}} | + | *Mean |

- | + | ||

- | Binarization of the image (converting it to black and white) is an important operation previous to blob analysis or shape description (see [[Shape Descriptors for Tabletops|my Master's Thesis]]). Usually one can use a threshold to decide if a pixel is white or black, but this threshold is very sensitive to lighting. In the following example you should use one threshold for the center and a different one for the corners, because the letters in the center are lighter than the background in the corners: | + | *Standard deviation (StDev) |

- | {{ :dictionary.png?300 |Non-uniform lighting}} | + | |

- | + | *Press 'Esc' to stop the applet (reload the page to start again) | |

- | {{ :dictionary_Threshold.png?300 |Thresholded image}} | + | |

- | + | ||

- | To overcome this, we can "subtract" the surround (using an on-center off-surround filter) and then we can binarize without problems: | + | |

- | {{ :dictionary_Integral_Images_DoG.png?300 |On-Center Off-Surround}} | + | If you don't have the Java plug-in you can [[http://www.youtube.com/watch?v=S0BuYWB5YVM|watch a video of it]] |

- | + | | |

- | {{ :dictionary_Integral_Images_DoG_Threshold.png?300 |Thresholded image}} | + | |

- | + | ||

- | The neurons in our retina perform a similar operation called [[wp>Lateral inhibition]] (a neuron response is inhibited by the response of the lateral ones). You can experience this effect in several optical illusions. [[wp>Grid illusion|Herman grid illusion]]: if you look at the grid you can see black spots in the crossings of the white lines (even if they are not there). [[wp>Match bands]]: you can see darker and lighter lines in the edges between the vertical lines (called overshot), even if the vertical lines are flat: | + | Using the **Mean** statistical measure, we get different effects depending on the shape of the filter: |

- | {{ :Match_bands.png?300 |Match bands}} | + | |

- | + | ||

- | Both effects can be simulated with the Center-Surround filter: | + | |

- | {{ :Match_bands_Integral_Images.png?300 |Match bands simulation}} | + | The **Average** is a rectangle that blurs the image: the texture and noise disappears, but also the details of the image. This is similar to the Gaussian blur that you can find in Photoshop or the Gimp. |

- | + | ||

- | [[wp>Hybrid_image|Hybrid images]] is another optical illusion that can be explained by the lateral inhibition. These images change depending on the viewing distance. Using center-surround filters of different sizes we have the same effect: | + | {{ :baboon.png?300 |Original image}} |

- | + | | |

- | {{ :albert-einstein-marilyn-monroe.jpg |Einstein-Marilyn Monroe optical illusion }} | + | |

- | + | ||

- | {{ :einstein-marilyn_close.png | Einstein-Marilyn Monroe high pass (close)}} | + | {{ :baboon_Integral_Images_Blur.png?300 |Blurred image}} |

- | + | | |

- | {{ :einstein-marilyn_far.png | Einstein-Marilyn Monroe band pass (far)}} | + | |

- | + | ||

- | Other shapes of filters are useful to find edges or lines in the image | + | The **Center-Surround** is an approximation to the [[wp>Difference of Gaussians]] (DoG) which is a useful operation to find edges and binarize the image. |

- | {{ :Lines.png?300 |Original image}} | + | |

- | + | ||

- | {{ :Lines_Integral_Image_Vertical.png?300 |Vertical filter}} | + | |

- | + | If you use a small surround and a pixel for the center, you find the edges: | |

- | {{ :Lines_Integral_Image_Horizontal.png?300 |Horizontal filter}} | + | |

- | + | {{ :lena_Integral_Images_Edges.png?300 |Edges}} | |

- | {{ :Lines_Integral_Image_Diagonal.png?300 |Diagonal filter}} | + | |

- | + | ||

- | We can use the [[wp>Standard deviation]] or **StDev** instead of the Mean. This statistical descriptor is useful to assess how much texture a region of the image has: | + | |

- | {{ :Textures.png?300 |Original image}} | + | Binarization of the image (converting it to black and white) is an important operation previous to blob analysis or shape description (see [[Shape Descriptors for Tabletops|my Master's Thesis]]). Usually one can use a threshold to decide if a pixel is white or black, but this threshold is very sensitive to lighting. In the following example you should use one threshold for the center and a different one for the corners, because the letters in the center are lighter than the background in the corners: |

- | + | ||

- | {{ :Textures_StDev.png?300 |Standard deviation}} | + | {{ :dictionary.png?300 |Non-uniform lighting}} |

- | + | | |

- | =====References===== | + | |

- | *P. Viola and M. J. Jones, “Robust real-time face detection,” International Journal of Computer Vision 57 (2004): 137–154. | + | |

- | + | {{ :dictionary_Threshold.png?300 |Thresholded image}} | |

+ | | ||

+ | |||

+ | |||

+ | To overcome this, we can "subtract" the surround (using an on-center off-surround filter) and then we can binarize without problems: | ||

+ | |||

+ | {{ :dictionary_Integral_Images_DoG.png?300 |On-Center Off-Surround}} | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :dictionary_Integral_Images_DoG_Threshold.png?300 |Thresholded image}} | ||

+ | | ||

+ | |||

+ | |||

+ | The neurons in our retina perform a similar operation called [[wp>Lateral inhibition]] (a neuron response is inhibited by the response of the lateral ones). You can experience this effect in several optical illusions. [[wp>Grid illusion|Herman grid illusion]]: if you look at the grid you can see black spots in the crossings of the white lines (even if they are not there). [[wp>Match bands]]: you can see darker and lighter lines in the edges between the vertical lines (called overshot), even if the vertical lines are flat: | ||

+ | |||

+ | {{ :Match_bands.png?300 |Match bands}} | ||

+ | | ||

+ | |||

+ | |||

+ | Both effects can be simulated with the Center-Surround filter: | ||

+ | |||

+ | {{ :Match_bands_Integral_Images.png?300 |Match bands simulation}} | ||

+ | | ||

+ | |||

+ | |||

+ | [[wp>Hybrid_image|Hybrid images]] is another optical illusion that can be explained by the lateral inhibition. These images change depending on the viewing distance. Using center-surround filters of different sizes we have the same effect: | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :albert-einstein-marilyn-monroe.jpg |Einstein-Marilyn Monroe optical illusion }} | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :einstein-marilyn_close.png | Einstein-Marilyn Monroe high pass (close)}} | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :einstein-marilyn_far.png | Einstein-Marilyn Monroe band pass (far)}} | ||

+ | | ||

+ | |||

+ | |||

+ | Other shapes of filters are useful to find edges or lines in the image | ||

+ | |||

+ | {{ :Lines.png?300 |Original image}} | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :Lines_Integral_Image_Vertical.png?300 |Vertical filter}} | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :Lines_Integral_Image_Horizontal.png?300 |Horizontal filter}} | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :Lines_Integral_Image_Diagonal.png?300 |Diagonal filter}} | ||

+ | | ||

+ | |||

+ | |||

+ | We can use the [[wp>Standard deviation]] or **StDev** instead of the Mean. This statistical descriptor is useful to assess how much texture a region of the image has: | ||

+ | |||

+ | {{ :Textures.png?300 |Original image}} | ||

+ | | ||

+ | |||

+ | |||

+ | {{ :Textures_StDev.png?300 |Standard deviation}} | ||

+ | | ||

+ | |||

+ | |||

+ | =====References===== | ||

+ | |||

+ | *P. Viola and M. J. Jones, “Robust real-time face detection,” International Journal of Computer Vision 57 (2004): 137–154. | ||

+ | | ||

+ | |||

~~DISCUSSION|Comments~~ | ~~DISCUSSION|Comments~~ |