en integrerad bild är där varje pixel representerar den kumulativa summan av en motsvarande ingångspixel med alla pixlar ovanför och till vänster om ingångspixeln. Det möjliggör snabb beräkning av summeringar över bild subregioner. Varje rektangulär delmängd av en sådan delregion kan utvärderas i konstant tid.
detta koncept introducerades av Viola & Jones och är också känt som Summed Area Table. Tillåt snabb beräkning av rektangulära bildfunktioner eftersom de möjliggör summering av bildvärden över alla rektangelbildregioner i konstant tid, dvs. beräkningskomplexitet av O(1) istället för O (n).
en integrerad bild definieras som
SAT-metoden har
- Rymdkomplexitet: O(M*N)
- tidskomplexitet för Intervallsummafråga: O( 1)
- tidskomplexitet för att uppdatera ett värde i matris: O (M*N)
- beräknar effektivt statistiken som medelvärde, standardavvikelse, etc i alla rektangulära fönster
integrerad Bildberäkning
snabb Områdesberäkning
summa = nedre höger + övre vänstra-övre högra-nedre vänstra
använder
- regionbaserad statistisk åtgärder t.ex. areasummor, kovarians, samverkansmatris
- texturmappning
- detektering av funktion-HAAR
- adaptiv tröskel
- stereokorrespondens
- begreppet integrerade bilder kan enkelt utvidgas till kontinuerlig domän (med gränser) och flerdimensionella bilder.
- O(1) bilateralt med konstanta rumsliga Filter
kod
class NumMatrix {
public:
vector<vector<int>> sat;
bool empty=true;
NumMatrix(vector<vector<int>> &img) {
int row = img.size();
if(row == 0) return;
int col = img.size();
if(col == 0) return;
empty = false;
sat = vector<vector<int>>(row + 1, vector<int>(col + 1));
for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
sat = sat + sat - sat + img;
}
int sumRegion(int row1, int col1, int row2, int col2) {
return empty? 0 : sat - (sat + sat - sat);
}
};
