Tabell över summerad yta

Använda en summerad areatabell ( 2. ) av en magisk kvadrat av order-6 ( 1. ) för att summera en underrektangel av dess värden; varje färgad fläck framhäver summan inuti rektangeln för den färgen.

En summerad area-tabell är en datastruktur och algoritm för att snabbt och effektivt generera summan av värden i en rektangulär delmängd av ett rutnät. Inom bildbehandlingsdomänen är det också känt som en integrerad bild . Den introducerades till datorgrafik 1984 av Frank Crow för användning med mipmaps . Inom datorseende populariserades den av Lewis och gavs sedan namnet "integral bild" och användes framträdande inom ramen för Viola–Jones objektdetektering 2001. Historiskt sett är denna princip mycket välkänd i studien av flerdimensionella sannolikhetsfördelningsfunktioner, nämligen vid beräkning av 2D (eller ND) sannolikheter (area under sannolikhetsfördelningen) från respektive kumulativa fördelningsfunktioner .

Algoritmen

Som namnet antyder är värdet vid vilken punkt som helst ( x , y ) i tabellen för summerade arean summan av alla pixlar ovanför och till vänster om ( x , y ), inklusive:

$$I(x,y)=\summa _{\begin{smallmatrix}x'\leq x\\ y'\leq y\end{smallmatrix}}i(x',y')$$

där $i(x,y)$ är värdet på pixeln vid ( x , y ).

arealer kan beräknas effektivt i en enda passage över bilden, eftersom värdet i tabellen för summerade area vid ( x , y ) bara är:

$$I(x,y )=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)$$

(Noterat att den summerade matrisen beräknas från övre vänstra hörnet)

En beskrivning av beräkning av en summa i datastrukturen/algoritmen för summerade areatabellen

När den summerade areatabellen väl har beräknats kräver utvärdering av summan av intensiteter över ett rektangulärt område exakt fyra matrisreferenser oavsett areans storlek. Det vill säga notationen i figuren till höger, med ₀₀ A = ( x , y ) , ₀ B = ( x ₁ , y ) , ₀ C = ( x , y ₁ ) och D = ( x ₁ , y ₁ ) , summan av i ( x , y ) över rektangeln som sträcks av A , B , C och D är:

$$\sum _{\begin{smallmatrix }x_{0}<x\leq x_{1}\\y_{0}<y\leq y_{1}\end{smallmatrix}}i(x,y)=I(D)+I(A)- I(B)-I(C)$$

Tillägg

Denna metod utvidgas naturligtvis till kontinuerliga domäner.

Metoden kan även utökas till högdimensionella bilder. Om rektangelns hörn är $x^{p}$ med $p$ i $\{0,1\}^{d}$ , då summan av bildvärdena i rektangeln beräknas med formeln

$$\sum _{p\in \{0,1\}^{d}}(-1)^ {d-\|p\|_{1}}I(x^{p})$$

där $I(x)$ är integralbilden vid $x$ och $d$ bildens dimension. Notationen $x^{p}$ motsvarar i exemplet $d=2$ , $A=x^{(0,0)}$ , $B=x^{(1,0)}$ , $C=x^{(1,1)}$ och $D=x^{(0,1)}$ . I neuroimaging , till exempel, har bilderna dimensionen $d=3$ eller $d=4$ , när man använder voxels eller voxels med en tidsstämpel.

Denna metod har utvidgats till att omfatta en integrerad bild av hög ordning som i arbetet av Phan et al. som tillhandahöll två, tre eller fyra integrerade bilder för att snabbt och effektivt beräkna standardavvikelsen (varians), skevhet och kurtos för lokalt block i bilden. Detta är detaljerat nedan:

För att beräkna varians eller standardavvikelse för ett block behöver vi två integrerade bilder:

$$I(x,y)=\summa _{\begin{smallmatrix}x'\leq x\\ y'\leq y\end{smallmatrix}}i(x',y')$$

$$I^{2}(x,y)=\summa _{\begin{smallmatrix}x '\leq x\\y'\leq y\end{smallmatrix}}i^{2}(x',y')$$

Variansen ges av:

$$\operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.$$

Låt $S_{1}$ och $S_{2}$ beteckna summeringarna av block $ABCD$ av $I$ och $I ^{2}$ , respektive. $S_{1}$ och $S_{2}$ beräknas snabbt av en integrerad bild. Nu manipulerar vi variansekvationen som:

$${\ start{aligned}\operatörsnamn {Var} (X)&={\frac {1}{n}}\sum _{i=1}^{n}\left(x_{i}^{2}-2\ mu x_{i}+\mu ^{2}\right)\\[1ex]&={\frac {1}{n}}\left[\summa _{i=1}^{n}x_{i }^{2}-2\summa _{i=1}^{n}\mu x_{i}+\summa _{i=1}^{n}\mu ^{2}\right]\\[ 1ex]&={\frac {1}{n}}\left[\summa _{i=1}^{n}x_{i}^{2}-2\summa _{i=1}^{n }\mu x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{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 }}\right]\end{aligned}}$$

Där $\mu =S_{1}/n$ och ${\textstyle S_{2}=\summa _{i=1}^{ n}x_{i}^{2}}$ .

Liknande uppskattningen av medelvärdet ( $\mu$ ) och variansen ( $\operatorname {Var}$ ), som kräver integralbilder av bildens första respektive andra potens (dvs. $I,I^{2}$ ); manipulationer som liknar de som nämns ovan kan göras till bildernas tredje och fjärde potens (dvs. $I^{3}(x,y), I^{4}(x,y)$ .) för att erhålla skevhet och kurtos. Men en viktig implementeringsdetalj som måste hållas i åtanke för ovanstående metoder, som nämnts av F Shafait et al. är det med heltalsspill som inträffar för integralbilderna av högre ordning om 32-bitars heltal används.

Se även

• Prefix summa

externa länkar

• Summerad tabellimplementering i objektdetektering

Föreläsningsfilmer

• En introduktion till teorin bakom integralbildalgoritmen
• En demonstration av en kontinuerlig version av den integrerade bildalgoritmen, från Wolfram Demonstrations Project