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

Теорема названа в честь британского математика Джорджа Грина, из-за сходства с его теоремой, теоремой Грина: обе теоремы описывают связь между интегрированием по кривой и интегрированием по области, ограниченной кривой. Теорема была впервые представлена как непрерывное продолжение алгоритма Ванга «Интегральное представление изображений», в 2007 году на Международной конференции по компьютерному видению ICCV [1], а затем вновь была опубликована профессором Doretto и его коллегами [3] в рецензируемом журнале в 2011 году.

Формулировка

править
 
определение  

Предположим что ƒ является интегрируемой функцией на плоскости R2, так что:

 

является её первообразной функцией. Пусть   — обобщенная прямоугольная область. Тогда представим теорему как:

 

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

Эта теорема является естественным продолжением алгоритма таблицы обобщённой области. Эта теорема расширяет алгоритм в том смысле, что область может быть непрерывной и она может быть сформирована из (конечного) числа прямоугольников, тогда как в алгоритме таблицы обобщённой области предполагается, что область является единым прямоугольником.

Дискретная теорема Грина также обобщает теорему Ньютона-Лейбница.

Идея доказательства

править

Для доказательства теоремы можно применить формулу из алгоритма "Интегрального представление изображений", которая включает в себя прямоугольники, образующие данную область:

 

Это изображение показывает, как + \ — коэффициенты первоначальной функции взаимно сокращаются в прямоугольниках, кроме точек расположенных в углах данной области.

Пример

править

Предположим что функция ƒ, задана на плоскости R2 , тогда F является её первообразной функцией. Пусть D — это область, окрашенная зелёным на следующем рисунке:

 

Согласно теореме, примененимой к данной области, получается следующее выражение:

 

Приложения

править

Дискретная теорема Грина используется в компьютерных приложениях по обнаружению объектов на изображениях и их быстрого вычисления, а также в интересах эффективного расчета вероятностей.

Обобщения

править

В 2011 году были предложены два обобщения к теореме:

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

Видео лекции

править

См. также

править

Примечания

править
  1. 1 2 Wang, Xiaogang. "Shape and Appearance Context Modeling" (PDF). in Proceedings of IEEE International Conference on Computer Vision (ICCV) 2007. Архивировано из оригинала (PDF) 16 июля 2011. Дата обращения: 17 июня 2011. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка) Источник. Дата обращения: 17 июня 2011. Архивировано из оригинала 16 июля 2011 года.
  2. Finkelstein, Amir (2010). "A Discrete Green's Theorem". Wolfram Demonstrations Project. Архивировано 12 ноября 2012. Дата обращения: 17 июня 2011. Источник. Дата обращения: 17 июня 2011. Архивировано 12 ноября 2012 года.
  3. Doretto, Gianfranco. "Appearance-based person reidentification in camera networks: Problem overview and current approaches" (PDF). Journal of Ambient Intelligence and Humanized Computing, pp. 1–25, Springer Berlin / Heidelberg, 2011. Архивировано из оригинала (PDF) 26 марта 2012. Дата обращения: 17 июня 2011. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка) Источник. Дата обращения: 17 июня 2011. Архивировано из оригинала 26 марта 2012 года.
  4. Finkelstein, Amir (2010). "Tendency of a Curve". Wolfram Demonstrations Project. Архивировано 24 сентября 2016. Дата обращения: 29 сентября 2017. Источник. Дата обращения: 29 сентября 2017. Архивировано 24 сентября 2016 года.
  5. 1 2 Finkelstein, Amir (2010). "Detachment and Tendency of a Single Variable Function". Wolfram Demonstrations Project.
  6. Pham, Minh-Tri. "Fast Polygonal Integration and Its Application in Extending Haar-like Features to Improve Object Detection" (PDF). Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, CA, 2010. Архивировано из оригинала (PDF) 2 сентября 2011. Дата обращения: 17 июня 2011. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка) Источник. Дата обращения: 17 июня 2011. Архивировано из оригинала 2 сентября 2011 года.
  7. Finkelstein, Amir (2010). "Extended Discrete Green's Theorem". Wolfram Demonstrations Project. Архивировано 20 ноября 2015. Дата обращения: 29 сентября 2017. Источник. Дата обращения: 29 сентября 2017. Архивировано 20 ноября 2015 года.
  8. Shachar, Amir. "On a Relation Between the Integral Image Algorithm and Calculus" (PDF). arXiv:1005.1418v11[cs.DM], 2011. (недоступная ссылка)