Відкрити головне меню

Дискретна теорема Гріна

У диференціальному численні існує дискретна версія теореми Гріна, яка описує відношення між подвійним інтегралом функції для узагальненої прямокутної області D (область, яка утворюється з скінченого додавання прямокутників на площині) й лінійної комбінації похідної функції, заданої в кутах області. У цьому значенні ми будемо дивитись більш відому версію дискретної теореми Гріна.[1][2]

Теорема названа на честь британського математика Джорджа Гріна, із-за схожості з його теоремою, теоремою Гріна: дві теоремі описують зв'язок між інтегруванням по кривій і інтегруванням по області, обмеженій кривою.

ІсторіяРедагувати

Теорема була вперше представлена як неперервне продовження алгоритму Ванга «Інтегральне представлення зображення», у 2007 році на Міжнародній конференції ICCV[1], а потім знову була видана професором Doretto і його колегами[3] у рецензованому журналі у 2011 році.

ТеоремаРедагувати

 
визначення  

Припустимо що ƒ є інтегровною функцією на площині R2, так що:

 

є її похідна функції. Нехай   — прямокутна область. Тоді представимо теорему як:

 

де   — множина кутів заданої області D ,   є дискретним параметром з можливими значеннями {0, ±1, ±2}, які визначаються залежно типу кута, як показано на малюнку праворуч. Цей параметр є приватним випадком прагнення кривої[4], яка послідовно визначається за допомогою одностороннього розриву[5] крива у кутах заданої області.

Ця теорема є природним продовженням алгоритму таблиці узагальненої області. Ця теорема розширює алгоритм в у тому сенсі, цо область може буди неперервною і вона може бути сформована з (скінченого) числа прямокутників, тоді як в алгоритмі таблиці узагальненої області передбачається, що область є єдиним прямокутником.

Дискретна теорема Гріна також узагальнює теорему Ньютона-Лейбніца.

ДоведенняРедагувати

Для доведення теореми можна задіяти формулу з алгоритму «Інтегрального представлення зображення» яка включає в себе прямокутники, які утворюють цю область:

 

Це зображення показує, як + \ — коефіцієнти першочергової функції скорочуються у прямокутниках, окрім точок які знаходяться у кутах цієї області.

ПрикладРедагувати

Припустимо, що функція ƒ, задана на площині R2 , тоді F є її похідною функцією. Нехай D — це, область, позначена зеленим на наступному малюнку:

 

згідно з теоремою, задіяною у цій області, виходить наступний вираз:

 

ДодатокРедагувати

Дискретна теорема Гріна в комп'ютерних програмах зі знаходження об'єктів на зображеннях і їх швидкого обчислення, а також у інтересах ефективного розрахунку ймовірностей.

УзагальненняРедагувати

У 2011 році були запропоновані способи узагальнення до теореми:

  • Спосіб, запропонований професором Фам і його колегами: узагальнення теореми полігональних областей за допомогою динамічного програмування[6].
  • Підхід, запропонований математиком Шахар: узагальнення теоремі на більш широкий спектр областей за допомогою оператора розриву[5] і методу інтегрування похилої лінії[7] за допомогою яких і була сформована дискретна теорема Гріна[8].

Див. такожРедагувати

ПриміткиРедагувати

  1. а б Wang, Xiaogang; Doretto, Gianfranco; Sebastian, Thomas; Rittscher, Jens; Tu, Peter. Shape and Appearance Context Modeling. in Proceedings of IEEE International Conference on Computer Vision (ICCV) 2007. Архів оригіналу за 16 липень 2011. Процитовано 8 червень 2013. 
  2. Finkelstein, Amir (2010). A Discrete Green's Theorem. Wolfram Demonstrations Project. 
  3. Doretto, Gianfranco; Sebastian, Thomas; Rittscher, Jens; Tu, Peter. Appearance-based person reidentification in camera networks: Problem overview and current approaches. Journal of Ambient Intelligence and Humanized Computing, pp. 1–25, Springer Berlin / Heidelberg, 2011. 
  4. Finkelstein, Amir (2010). Tendency of a Curve. Wolfram Demonstrations Project. 
  5. а б Finkelstein, Amir (2010). Detachment and Tendency of a Single Variable Function. Wolfram Demonstrations Project. 
  6. Pham, Minh-Tri; Yang Gao; Viet-Dung D. Hoang; Tat-Jen Cham. Fast Polygonal Integration and Its Application in Extending Haar-like Features to Improve Object Detection. Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, CA, 2010. Архів оригіналу за 2 вересня 2011. Процитовано 8 червня 2013. 
  7. Finkelstein, Amir (2010). Extended Discrete Green's Theorem. Wolfram Demonstrations Project. 
  8. Shachar, Amir. On a Relation Between the Integral Image Algorithm and Calculus. arXiv:1005.1418v11[cs.DM], 2011. [недоступне посилання з травень 2019]

ЛітератураРедагувати

Відео лекціїРедагувати