et integreret billede er, hvor hvert billedpunkt repræsenterer den kumulative sum af et tilsvarende inputpunkt med alle billedpunkter over og til venstre for inputpunktet. Det muliggør hurtig beregning af summeringer over billedsubregioner. Enhver rektangulær delmængde af en sådan underregion kan evalueres i konstant tid.
dette koncept blev introduceret af Viola & Jones og er også kendt som Summed Area Table. Tillad hurtig beregning af rektangulære billedfunktioner, da de muliggør summering af billedværdier over ethvert rektangelbilledområde i konstant tid, dvs. beregningskompleksitet af O (1) i stedet for O(n).
et integreret billede er defineret som
SAT-metoden har
- Rumkompleksitet: O (M*N)
- tidskompleksitet for rækkevidde Sum forespørgsel: O(1)
- tidskompleksitet for at opdatere en værdi i matricen: O (M*N)
- beregner effektivt statistikken som middelværdi, standardafvigelse osv. i ethvert rektangulært vindue
integreret Billedberegning
hurtig arealberegning
Sum = nederst til højre + øverst til venstre — øverst til højre — nederst til venstre
bruger
- regionbaseret statistisk måler f.eks. arealsummer, kovarians, Co-forekomst matrice
- Teksturkortlægning
- detektion af feature — HAAR
- adaptiv tærskel
- stereokorrespondance
- konceptet med integrerede billeder kan let udvides til kontinuerligt domæne (ved hjælp af grænser) og flerdimensionelle billeder.
- O(1) bilateralt med konstante rumlige filtre
kode
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);
}
};
