een integrale afbeelding is waarbij elke pixel de cumulatieve Som vertegenwoordigt van een overeenkomstige invoerpixel met alle pixels boven en links van de invoerpixel. Het maakt een snelle berekening van sommaties over beeldsubregio ‘ s mogelijk. Elke rechthoekige deelverzameling van een dergelijk deelgebied kan in constante tijd worden geëvalueerd.
dit concept werd geïntroduceerd door Viola & Jones en is ook bekend als ‘Summed Area Table’. Sta een snelle berekening van rechthoekige afbeeldingsfuncties toe, omdat ze de optelling van afbeeldingswaarden over elke rechthoekige afbeeldingsregio in constante tijd mogelijk maken, d.w.z. computationele complexiteit van O (1) in plaats van O (n).
Een Integraal Beeld wordt gedefinieerd als
De SAT-methode heeft
- Ruimte Complexiteit: O(M*N)
- Tijd Complexiteit voor Bereik Som Query: O(1)
- Tijd Complexiteit voor het Bijwerken van een Waarde in de Matrix: O(M*N)
- Efficiënt berekent de statistieken zoals gemiddelde, standaarddeviatie, etc in een rechthoekig venster
Integraal Beeld Berekening
Snelle Berekening
Sum = rechts Onderaan + links boven — boven-rechts — onder-links
Toepassingen
- regio gebaseerde statistische metingen zoals oppervlaktesommen, covariantie, Co-occurrence matrix
- Texture mapping
- detectie van feature — haar
- adaptieve drempel
- stereo-correspondentie
- het concept van integrale afbeeldingen kan gemakkelijk worden uitgebreid tot continue domeinen (met behulp van limieten) en multidimensionale afbeeldingen.
- O(1) bilateraal met constante ruimtelijke Filters
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);
}
};
