Summed Area Table

Summed Area Table

A Summed Area Table (also known as an Integral Image) is an algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid. It was first introduced to the computer graphics world in 1984 for use in mipmaps but wasn't widely used in the computer vision community until its prominent use in the Viola and Jones robust real-time object detection framework twenty years later.

The Algorithm

As the name suggests, the value at any point (x,y) in the summed area table is just the sum of all the pixels above and to the left of (x,y), inclusive: [cite conference
first = Franklin
last = Crow
authorlink =
coauthors =
title = Summed-area tables for texture mapping
booktitle = SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques
pages = 207-212
year = 1984
url = http://www.soe.ucsc.edu/classes/cmps160/Fall05/papers/p207-crow.pdf
] [cite conference
first = Paul
last = Viola
authorlink =
coauthors = Jones, Michael
title = Robust Real-time Object Detection
booktitle = International Journal of Computer Vision
pages =
year = 2002
url = http://research.microsoft.com/~viola/Pubs/Detect/violaJones_IJCV.pdf
] sat(x,y) = sum_{x' le x,y' le y} i(x',y')

Moreover, the summed area table can be computed efficiently in a single pass over the image, using the fact that the value in the summed area table at (x,y) is just:

sat(x,y) = sat(x-1,y) + sum_{x' le x} i(x',y)

Once the summed area table has been computed, the task of evaluating any rectangle can be accomplished in constant time with just four array references. Specifically, using the notation in the figure at right, the value is just:

sum_{A(x) le x' le B(x), A(y) le y' le D(y)} i(x',y') = sat(A) + sat(C) - sat(B) - sat(D)

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Mipmap — In 3D computer graphics texture filtering, MIP maps (also mipmaps) are pre calculated, optimized collections of images that accompany a main texture, intended to increase rendering speed and reduce aliasing artifacts. They are widely used in 3D… …   Wikipedia

  • Image intégrale — Calcul de la somme des pixels dans une zone rectangulaire arbitrairement située dans une image numérique: seuls 4 accès à l image intégrale (A,B,C,D) sont nécessaires. Une image intégrale (ou summed area table) est une représentation sous la… …   Wikipédia en Français

  • Calculus — This article is about the branch of mathematics. For other uses, see Calculus (disambiguation). Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus  Derivative Change of variables …   Wikipedia

  • SAT — ist ein Begriff im Hinduismus, siehe Sat Chit Ananda Die Abkürzung SAT steht für: Satellit, davon abgeleitet auch für: Satellitenempfänger; Satellitenfernsehen; Körperschaften (Institutionen, Organisationen): Sat.1, einen privaten deutschen… …   Deutsch Wikipedia

  • SAT — agricult. abbr. Serum Agglutination Test abbr. SIM Application Toolkit (SIM, GSM) abbr. Standard AUTODIN Terminal (AUTODIN, Mil.) abbr. Summed Area Table (3D, MIP) acronym Satellite (Space) …   United dictionary of abbreviations and acronyms

  • Haar-like features — are digital image features used in object recognition. They owe their name to their intuitive similarity with Haar wavelets. Historically, working with only image intensities (i.e., the RGB pixel values at each and every pixel of image) made the… …   Wikipedia

  • SAT (disambiguation) — The abbreviations SAT, S.A.T., Sat., etc. may apply to several different topics:In educational testing: *The SAT standardized test for USA college admissions (SAT was originally an abbreviation for Scholastic Aptitude Test, but officially it is… …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • china — /chuy neuh/, n. 1. a translucent ceramic material, biscuit fired at a high temperature, its glaze fired at a low temperature. 2. any porcelain ware. 3. plates, cups, saucers, etc., collectively. 4. figurines made of porcelain or ceramic material …   Universalium

  • China — /chuy neuh/, n. 1. People s Republic of, a country in E Asia. 1,221,591,778; 3,691,502 sq. mi. (9,560,990 sq. km). Cap.: Beijing. 2. Republic of. Also called Nationalist China. a republic consisting mainly of the island of Taiwan off the SE coast …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”