Tip:
Highlight text to annotate it
X
Hello everyone,
today we will consider a semi-discrete approach to calculus.
This theory forms a combination between discrete and continuous math,
and it also is a theory behind a continuous version of the Integral Image algorithm,
which is a common algorithm in both computer vision and computer graphics communities.
The Integral Image algorithm was introduced in the context of computer vision by Viola and Jones in 2001;
It aims at efficient detection of objects and faces in an image.
My name is Amir Shachar. I am a a mathematics researcher at the Hebrew University, Jerusalem, Israel.
Let us begin with an application.
Given an image of some happy and talented young musicians, say we wish to detect their faces.
Well, our camera does it quite quickly nowadays..
But how does it do it?
Well, we won't get into the full details of the Integral Image algorithm; but generally speaking, it uses tools from computer learning,
and compares sums of rectangles in the image to those found in previously studied faces.
A decisive stage of the algorithm includes calculation of the sums of many rectangles in the image.
And here comes a trick that saves a lot of computation time, and enables our cameras to detect faces in real time:
Given an image, we refer to it as a function in the plane R^2,
whose value at each point is simply the numerical value of the image's intensity at the matching point,
Assuming that the image has been interpolated into a pseudo-continuous domain.
Next, we consider the given function's antiderivative,
whose value at a given point is simply the double integral of the original function over the axis-aligned rectangle defined by the point and the origin.
Here we can see why we ought to use the antiderivative.
Given that we pre-calculated the antiderivative, then now given a rectangle over which we wish to integrate the given function,
we can do it in an efficient fashion, by alternately adding and subtracting values of the antiderivative at the corners of the domain,
and then – via the inclusion-exclusion principle – we get the original function's integral over the given domain.
This formula is an extension of Newton-Leibniz's axiom to the plane,
and we will refer to it as the Integral Image formula.
Back in 2007, a paper was published at the important conference ICCV, by a group of computer vision researchers, namely:
*** (from MIT), Doretto, Sebastian, Rittscher and Tu,
where an interesting fact was pointed out.
Suppose we wish to calculate the double integral over a finite unification of rectangles,
Then we could apply the Integral Image formula for each of the rectangles separately,
however there is a more efficient way to do it,
because notice that for example at *THIS* corner the coefficients of the antiderivative deduct eachother,
it is unnecessary to evaluate its value there.
Hence, a more efficient approach would be,
a traversal upon only the corners of the original domain, omitting the corners of its subrectangles.
So here's a formula for efficiently calculating the integral of the function over the given rectangular domain.
This is a special case of the version of the Discrete Green's Theorem suggested by *** and his colleagues.
Here is a general formulation of the theorem:
The double integral of a function over a finite union of rectangles,
can be efficiently calculated via a linear combination of the antiderivative at the domain's corners,
where the coefficient, alpha_D, is determined according to the corner's type.
Let us now consider theoretical aspects of the Discrete Green's Theorem.
Let us try to answer the question: how is the discrete Green's theorem related to other theorems in calculus?
Both single and multivariable calculus can be thought of as "descendents" of the derivative,
in the sense that many fundamental theorems in calculus somehow involve the derivative.
For example – Green's Theorem involves the derivative in quite a straight forward manner.
Now, if we take a look at the Discrete Green's Theorem, the derivative is not very obviously embedded in the formulation of the theorem.
In fact, the only place where the derivative might appear is hiddenly, at the parameter alpha_D.
However, this theory suggests that this parameter is most naturally defined via a simpler operator than the derivative,
using this operator, the "Detachment" operator - the limit of the sign of dy.
This operator is formed via a combination of continuous math (calculus) and discrete math (the sign function).
Using it, we can introduce interesting facts for single and multivariable functions.
For example, we can apply this operator to extend the Discrete Green's Theorem to more general types of domains:
Generally speaking, the idea is to divide the given domain into a rectangular domain (for whom the Discrete Green's Theorem is applied), and all the rest.
To do it, we use a new integration method in the plane.
Given a curve, the "Slanted Line Integral" over it is calculated via two parts:
the continuous part is the double integral over the domain bounded by the given curve and two axis-aligned lines,
and the discrete part is a special linear combination of the antiderivative at key points over the edge of the mentioned domain.
This integration method naturally extends the one used in the Discrete Green's Theorem,
and is characterized by interesting properties, such as linearity and negativity.
Back to single variable functions,
There are "many" differentiable functions,
And even "more" continuous functions;
And the new pointwise operator, the "Detachment", sgn(dy), is defined even for discontinuous functions.
Thus, this operator can be thought of, to some extents, as an extension to the sign of the derivative.
Using this operator, semi-discrete analogies can be formulated to familiar theorems in single variable calculus.
For example, a semi-discrete analog to the Mean Value Theorem,
where a trade-off is made between the quantity of information that the theorem suggests and the amount of functions for whom the theorem holds with respect to Lagrange's Mean Value Theorem.
For example, this theorem does not require differentiability of the function in the interval, but a weaker condition.
Thank you for attending this lecture.
To summarize, in this lecture we depicted a novel, semi-discrete pointwise operator (the "Detachment"), and a novel integration method over curves in the plane.
I would be glad to hear of your opinion regarding those ideas, and to cooperate in research.
You may contact me via my personal page, www.amir-f.com, where you can also find links to my papers and other lectures.
I will be happy to hear from you! -amir :) �