Overview
An integral image stores the sum above and left of each pixel, allowing fast box filters and region statistics.
CoreSource checked
Integral Image
Precomputes cumulative pixel sums so rectangular sums are answered in constant time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Image Processing
- Difficulty
- Intermediate
- Family
- Summed-Area Table
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
summed-area tablerectangular queryprefix sumconstant-time sum
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(pixels)
When to Use
- Use when image enhancement needs summed-area table.
- Use when the input matches the assumptions behind summed-Area Table.
When Not to Use
- Avoid when image noise, lighting, or scale breaks the algorithm's assumptions.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Precomputes cumulative pixel sums so rectangular sums are answered in constant time
- Uses summed-area table and rectangular query to guide the work.
- Produces processed image.
Use Cases
- Image enhancement
- Feature extraction
- Segmentation and motion analysis
Inputs
- Image or image sequence
- Kernel, threshold, or model parameters
Outputs
- Processed image
- Mask
- Feature map or motion field
Key Formulas (1)
Rectangle sum
sum = S(D) − S(B) − S(C) + S(A)
sum = S(D) - S(B) - S(C) + S(A)Combines four integral-image corners to get a rectangular sum.
Pseudocode
- 1.Normalize the image and choose border handling
- 2.Evaluate the local filter, statistic, model, or response for each relevant pixel or region
- 3.Threshold, rank, refine, or combine the responses
- 4.Return the mask, transformed image, feature set, or geometric estimate
Canonical Example
- Input
- a small grayscale image patch with a clear edge, corner, or region
- Output
- Processed image
- Explanation
- Integral Image applies summed-area table to produce processed image.
Implementation Notes
- Handle borders and pixel coordinate conventions consistently.
- Keep the summed-area table step separate enough to test independently.
- Keep coordinate conventions, border handling, and image normalization explicit in tests.
Common Pitfalls
- Applying operations in the wrong color space can distort the result.
- Test edge cases, not only clean examples.
- Thresholds tuned on one clean image can fail under different lighting, scale, blur, or noise.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow the source image beside masks, filters, or motion vectors produced by the algorithm.
Step 1 of 4: Normalize the image and choose border handling
image-processing-mechanismNotes
Integral Image should be used with the assumptions and tradeoffs of summed-Area Table in mind.
Sources (2)
What each reference supports for this entry.
Viola-Jones Object Detection
PaperReference for integral images and constant-time rectangular feature sums.
Open sourceComputer Vision: Algorithms and Applications
BookComputer-vision textbook support for Integral Image's feature, matching, flow, or multiscale image-analysis workflow.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsed byTemplate Matching
Integral images can accelerate windowed sums used in template and feature matching.
Related Algorithms
Tags
Image ProcessingPrefix SumRange QueryFiltering