Diskret Greens teorem

En diskret version av Greens teorem beskriver förhållandet mellan den dubbla integralen av en funktion för ett generaliserat rektangulärt område (ett område som bildas av en ändlig summering av rektanglar i planet) och en linjär kombination av en antiderivativ funktion som ges i hörnen av regionen. I denna mening kommer vi att överväga den populära versionen av den diskreta Greens teorem. [1] [2]

Satsen är uppkallad efter den brittiske matematikern George Green , på grund av likheten med hans sats, Greens sats: båda satserna beskriver förhållandet mellan integration över en kurva och integration över ett område som begränsas av en kurva. Teoremet presenterades först som en kontinuerlig förlängning av Wangs Integral Image Representation-algoritm 2007 vid ICCV International Conference on Computer Vision [1] och återpublicerades sedan av professor Doretto och kollegor [3] i en peer-reviewed tidskrift 2011.

Formulering

Antag att ƒ är en integrerbar funktion på R 2 -planet , så att:

F\left(x,y\right)\equiv \int _{0}^{y}\int _{0}^{x}f\left(u,v\right)\,du\, dv

är dess primitiva funktion . Låta vara ett generaliserat rektangulärt område. Då representerar vi satsen som: $D\subset R^{2}$

\iint _{D}f\left(x,y\right)\,dx\,dy=\sum _({\vec {x))\in \nabla \cdot D}\alpha _{D }\left({\vec {x}}\right)\cdot F\left({\vec {x}}\right),

där är uppsättningen av hörn för det givna området D , är en diskret parameter med möjliga värden {0, ±1, ±2}, som bestäms beroende på typen av hörn, som visas i bilden till höger. Denna parameter är ett specialfall av kurvans tendens [4] , som successivt bestäms genom att använda en ensidig diskontinuitet [5] av kurvan i hörnen av det givna området. $\nabla \cdot D$ $\alpha _{D}$

Detta teorem är en naturlig förlängning av den generaliserade areatabellalgoritmen. Denna sats utökar algoritmen i den meningen att regionen kan vara kontinuerlig och den kan bildas av ett (ändligt) antal rektanglar, medan den generaliserade regiontabellalgoritmen antar att regionen är en enda rektangel.

Den diskreta Greens teorem generaliserar också Newton-Leibniz-satsen .

Idé om beviset

För att bevisa teoremet kan du tillämpa formeln från algoritmen "Integral representation av bilder", som inkluderar rektanglarna som bildar detta område:

Den här bilden visar hur + \ - koefficienter för den ursprungliga funktionen tar bort varandra i rektanglar, förutom punkter som ligger i hörnen av detta område.

Exempel

Antag att funktionen ƒ ges i planet R 2 , då är F dess antiderivata funktion. Låt D vara området färgat grönt i följande figur:

Enligt satsen som är tillämplig på detta område erhålls följande uttryck:

\iint _{D}f\left(x,y\right)\,dx\,dy=F\left(J\right)-2F\left(K\right)+F\left(L\ höger)-F\vänster(M\höger)+F\vänster(N\höger)-F\vänster(O\höger)+F\vänster(P\höger)+F\vänster(Q\höger)-F\ vänster(R\höger).

Applikationer

Discrete Greens teorem används i datortillämpningar för att upptäcka objekt i bilder och snabbt beräkna dem, såväl som för effektiv beräkning av sannolikheter.

Generaliseringar

2011 föreslogs två generaliseringar till teoremet:

Ett tillvägagångssätt som föreslagits av Prof. Pham och kollegor: en generalisering av polygondomänsatsen med hjälp av dynamisk programmering [6] .
Ett tillvägagångssätt som föreslagits av matematikern Shahar: en generalisering av satsen till ett bredare spektrum av områden med användning av diskontinuitetsoperatorn [5] och metoden för sloped line integration [7] , med hjälp av vilken den diskreta Greens sats [8] formulerades .

Videoföreläsningar

En introduktion till den halvdiskreta kalkylen bakom teorin om diskreta Greens sats .

Se även

Greens teorem

Anteckningar

↑ 12 Wang, Xiaogang ; Doretto, Gianfranco; Sebastian, Thomas; Rittscher, Jens; Tu, Peter. "Shape and Appearance Context Modeling" (PDF) . i Proceedings of IEEE International Conference on Computer Vision (ICCV) 2007 . Utfasad parameter används |coauthors=( hjälp ) Arkiverad 16 juli 2011 på Wayback Machine
↑ Finkelstein, Amir (2010). "A Discrete Green's Theorem" . Wolfram demonstrationsprojekt . Arkiverad 12 november 2012 på Wayback Machine
↑ Doretto, Gianfranco; Sebastian, Thomas; Rittscher, Jens; Tu, Peter. "Utseendebaserad personåteridentifiering i kameranätverk: Problemöversikt och aktuella tillvägagångssätt" (PDF) . Journal of Ambient Intelligence and Humanized Computing, s. 1–25, Springer Berlin/Heidelberg, 2011 . Utfasad parameter används |coauthors=( hjälp ) Arkiverad 26 mars 2012 på Wayback Machine
↑ Finkelstein, Amir (2010). "Tendens av en kurva" . Wolfram demonstrationsprojekt . Arkiverad 24 september 2016 på Wayback Machine
↑ 1 2 Finkelstein, Amir (2010). "Friskiljning och tendens för en enskild variabel funktion" . Wolfram demonstrationsprojekt .
↑ Pham, Minh-Tri; Yanggao; Viet-Dung D. Hoang; Tat Jen Cham. "Snabb polygonal integration och dess tillämpning för att utöka Haar-liknande funktioner för att förbättra objektdetektering" (PDF) . Proc. från IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, CA, 2010 . Utfasad parameter används |coauthors=( hjälp ) Arkiverad 2 september 2011 på Wayback Machine
↑ Finkelstein, Amir (2010). "Utökad diskret Greens sats" . Wolfram demonstrationsprojekt . Arkiverad 20 november 2015 på Wayback Machine
↑ Shachar, Amir. "Om ett förhållande mellan den integrerade bildalgoritmen och kalkylen" (PDF) . arXiv:1005.1418v11[cs.DM], 2011 . (inte tillgänglig länk)