Tabela z sumą powierzchni

Używając tabeli zsumowanych obszarów ( 2. ) magicznego kwadratu rzędu 6 ( 1. ), aby zsumować podprostokąt jego wartości; każdy kolorowy punkt podkreśla sumę wewnątrz prostokąta tego koloru.

Tabela o zsumowanych obszarach to struktura danych i algorytm do szybkiego i wydajnego generowania sumy wartości w prostokątnym podzbiorze siatki. W przetwarzania obrazu jest również znany jako obraz integralny . Został wprowadzony do grafiki komputerowej w 1984 roku przez Franka Crowa do użytku z mipmapami . W wizji komputerowej został spopularyzowany przez Lewisa, a następnie nadano mu nazwę „obraz integralny” i wyraźnie wykorzystano w nim Ramy wykrywania obiektów Violi – Jonesa w 2001 r. Historycznie zasada ta jest bardzo dobrze znana w badaniu wielowymiarowych funkcji rozkładu prawdopodobieństwa, a mianowicie w obliczaniu prawdopodobieństw 2D (lub ND) (obszar pod rozkładem prawdopodobieństwa) na podstawie odpowiednich skumulowanych funkcji dystrybucji .

Algorytm

Jak sama nazwa wskazuje, wartość w dowolnym punkcie ( x , y ) w tabeli z sumowanym obszarem jest sumą wszystkich pikseli powyżej i na lewo od ( x , y ), włącznie:

$${\ Displaystyle I (x, y) = \ suma _ {\ rozpocząć {mała macierz} x '\ równoważnik x \\ y'\leq y\end{małamacierz}}i(x',y')}$$

gdzie ${\ Displaystyle i (x, y)}$ jest wartością piksela w ( x , y ).

Tablicę zsumowanych obszarów można skutecznie obliczyć w jednym przejściu przez obraz, ponieważ wartość w tabeli zsumowanych obszarów w ( x , y ) to po prostu:

$${\ Displaystyle I (x, y )=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)}$$

(Zauważono, że zsumowana macierz jest obliczana od lewego górnego rogu)

Opis obliczania sumy w strukturze/algorytmie tabeli o sumowanych obszarach

Po obliczeniu tabeli zsumowanych obszarów ocena sumy natężeń na dowolnym prostokątnym obszarze wymaga dokładnie czterech odniesień do tablicy, niezależnie od rozmiaru obszaru. Oznacza to, że zapis na rysunku po prawej stronie ma ₀₀ A = ( x , y ) , ₀ B = ( x ₁ , y ) , ₀ C = ( x , y ₁ ) i D = ( x ₁ , y ₁ ) , suma z i ( x , y ) nad prostokątem rozpiętym przez A , B , C i D to:

$${\ Displaystyle \ suma _ {\ rozpocząć {mała macierz }x_{0}<x\leq x_{1}\\y_{0}<y\leq y_{1}\end{małamacierz}}i(x,y)=I(D)+I(A)- I(B)-I(C)}$$

Rozszerzenia

Ta metoda jest naturalnie rozszerzona na domeny ciągłe.

Metodę można również rozszerzyć na obrazy wielowymiarowe. Jeśli $w$ prostokąta są z ${\ Displaystyle p}$ { $\ Displaystyle \ {0,1 \} ^ {d}}$ to suma wartości obrazu zawartych w prostokącie są obliczane za pomocą wzoru

$${\ Displaystyle \ suma _ {p \ w \ {0,1 \} ^ {d}} (-1) ^ {d-\|p\|_{1}}I(x^{p})}$$

gdzie ${\ displaystyle I (x)}$ jest obrazem całkowym w $displaystyle$ obrazu i $d} .$ Notacja ${\ Displaystyle x ^ {p}}$ odpowiada w przykładzie ${\ Displaystyle d = 2}$ , ${\ Displaystyle A = x ^ {(0,0)}}$ , ${\ Displaystyle B = x ^ {(1,0)}}$ , $= x ^ {(1,1)}}$${\ Displaystyle D=x^{(0,1)}}$ i re . Na $wokseli$ w neuroobrazowaniu obrazy mają wymiar $wokseli$ gdy używa się ze znacznikiem

Metoda ta została rozszerzona na obraz integralny wysokiego rzędu, jak w pracy Phan et al. który dostarczył dwa, trzy lub cztery integralne obrazy do szybkiego i wydajnego obliczania odchylenia standardowego (wariancji), skośności i kurtozy lokalnego bloku na obrazie. Jest to szczegółowo opisane poniżej:

Aby obliczyć wariancję lub odchylenie standardowe bloku, potrzebujemy dwóch obrazów całkowych:

$${\ Displaystyle I (x, y) = \ suma _ {\ rozpocząć {mała macierz} x '\ równoważnik x \\ y'\leq y\end{małamacierz}}i(x',y')}$$

$${\ Displaystyle I ^ {2} (x, y) = \ suma _ {\ rozpocząć {mała macierz} x '\leq x\\y'\leq y\end{małamacierz}}i^{2}(x',y')}$$

Wariancja jest dana przez:

$${\ Displaystyle \ nazwa operatora {Var} (X) = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} (x_ {i} - \ mu) ^ {2}.}$$

Niech ${\ Displaystyle S_ {1}}$ i ${\ Displaystyle S_ {2}}$ oznaczają sumy bloku ${\ displaystyle ABCD}$ i ${\ displaystyle I}$ i ${\ displaystyle I ^{2}}$ odpowiednio. ${\ displaystyle S_ {1}}$ i ${\ displaystyle S_ {2}}$ są obliczane szybko przez obraz całkowy. Teraz manipulujemy równaniem wariancji jako:

$${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {Var} (X) & = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} \ lewo (x_ {i} ^ { 2}-2\mu x_{i}+\mu ^{2}\right)\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{ n}x_{i}^{2}-2\suma _{i=1}^{n}\mu x_{i}+\suma _{i=1}^{n}\mu ^{2}\ prawo]\\[1ex]&={\frac {1}{n}}\lewo[\suma _{i=1}^{n}x_{i}^{2}-2\suma _{i= 1}^{n}\mu x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\suma _{i=1 }^{n}x_{i}^{2}-2\mu \sum _{i=1}^{n}x_{i}+n\mu ^{2}\right]\\[1ex]& ={\frac {1}{n}}\left[S_{2}-2{\frac {S_{1}}{n}}S_{1}+n\left({\frac {S_{1} }{n}}\right)^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-{\frac {S_{1}^{ 2}}{n}}\prawo]\end{wyrównane}}}$$

Gdzie ${\ Displaystyle \ mu = S_ {1}/n}$ i ${\ textstyle S_ {2} = \ suma _ {i = 1} ^ { n}x_{i}^{2}}$ .

Podobnie jak w przypadku szacowania średniej ( $i$ wariancji ( $) , która wymaga integralnych obrazów$ pierwszej i drugiej potęgi obrazu (tj. ${\ Displaystyle I, ja ^ {2}}$ ); manipulacje podobne do opisanych powyżej można wykonać na trzeciej i czwartej potędze obrazków (tj. $dla uzyskania$ i kurtozy. Ale jeden ważny szczegół implementacji, o którym należy pamiętać w przypadku powyższych metod, jak wspomniał F Shafait i in. jest przepełnieniem liczb całkowitych występującym dla obrazów całkowych wyższego rzędu w przypadku użycia 32-bitowych liczb całkowitych.

Zobacz też

• Suma prefiksu

Linki zewnętrzne

• Implementacja tablicy sumarycznej w wykrywaniu obiektów

Filmy z wykładami

• Wprowadzenie do teorii stojącej za integralnym algorytmem obrazu
• Demonstracja ciągłej wersji algorytmu integralnego obrazu z projektu Wolfram Demonstrations