Bei einem integralen Bild repräsentiert jedes Pixel die kumulative Summe eines entsprechenden Eingabepixels mit allen Pixeln oberhalb und links des Eingabepixels. Es ermöglicht eine schnelle Berechnung von Summationen über Bildunterregionen. Jede rechteckige Teilmenge eines solchen Teilbereichs kann in konstanter Zeit ausgewertet werden.
Dieses Konzept wurde von Viola & Jones eingeführt und wird auch als summierte Flächentabelle bezeichnet. ermöglichen eine schnelle Berechnung von rechteckigen Bildmerkmalen, da sie die Summierung von Bildwerten über einen beliebigen rechteckigen Bildbereich in konstanter Zeit ermöglichen, d.h. Berechnungskomplexität von O (1) anstelle von O (n).
Ein integrales Bild ist definiert als
Die SAT-Methode hat
- Raumkomplexität: O (M * N)
- Zeitkomplexität für die Bereichssummenabfrage: O (1)
- Zeitkomplexität zum Aktualisieren eines Werts in der Matrix: O (M * N)
- Berechnet effizient die Statistiken wie Mittelwert, Standardabweichung usw. in jedem rechteckigen Fenster
Integrale Bildberechnung
Schnelle Flächenberechnung
Summe = Unten rechts + oben links – oben rechts – unten links
Verwendet
- regionsbasierte statistische misst z.B. Flächensummen, Kovarianz, Co-occurrence Matrix
- Texture Mapping
- Erkennung von Feature — HAAR
- adaptive threshold
- Stereo correspondence
- Das Konzept der integralen Bilder kann leicht auf kontinuierliche Domäne (unter Verwendung von Grenzwerten) und mehrdimensionale Bilder erweitert werden.
- O(1) Bilateral mit konstanten räumlichen Filtern
Code
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);
}
};
