Obraz integralny

Obraz integralny to obraz, w którym każdy piksel reprezentuje skumulowaną sumę odpowiedniego piksela wejściowego ze wszystkimi pikselami powyżej i na lewo od piksela wejściowego. Umożliwia szybkie obliczanie podsumowań w podregionach obrazu. Każdy prostokątny podzbiór takiego podregionu można obliczyć w czasie stałym.

pojęcie to zostało wprowadzone przez Viola & Jonesa i jest również znane jako Summed Area Table. umożliwiają szybkie obliczanie prostokątnych funkcji obrazu, ponieważ umożliwiają sumowanie wartości obrazu nad dowolnym prostokątnym obszarem obrazu w stałym czasie, np. złożoność obliczeniowa O(1) zamiast O (n).

Obraz całkowy definiuje się jako

https://computersciencesource.files.wordpress.com/2011/05/sxyeq.png

https://computersciencesource.files.wordpress.com/2011/05/sxyeq.png

równanie do obliczania całki w pikselach (x, y)

metoda SAT ma

  • złożoność przestrzeni: O(M*N)
  • złożoność czasowa dla zapytania o sumę zakresu: O(1)
  • złożoność czasowa do aktualizacji wartości w macierzy: O (M*N)
  • efektywnie oblicza statystyki, takie jak średnia, odchylenie standardowe itp. w dowolnym oknie prostokątnym

technika obliczeniowa

szybkie obliczanie powierzchni

obliczanie powierzchni prostokątnego podregionu obrazu

suma = prawy dolny + lewy górny-prawy górny – lewy dolny

zastosowania

  • statystyka oparta na regionie mierzy np. sumy powierzchniowe, kowariancję, macierz współwystępowania
  • mapowanie tekstur
  • wykrywanie funkcji — haar
  • próg adaptacyjny
  • korespondencja stereo
  • pojęcie obrazów całkowych można łatwo rozszerzyć na domenę ciągłą (za pomocą limitów) i obrazy wielowymiarowe.
  • o(1) dwustronny ze stałymi filtrami przestrzennymi

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);
}
};

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.