Tip:
Highlight text to annotate it
X
Hello everyone,
today we will depict a theorem that naturally extends the integral image algorithm to more general types of domains.
Here's my name, and let's begin.
Given a function over the plane, we define its cumulative distribution function at a given point,
as the double integral of the original function over the rectangle defined by that point and the origin.
The cumulative distribution function is then used for efficient evaluation of integrals over rectangles in the image,
by alternately adding and subtracting its values at the corners of the rectangle.
We will refer to this formula as the "integral image formula".
Back in 2007, *** and his colleagues noticed an interesting fact.
Given a union of rectangles over which we wish to integrate the given function,
then a naive approach would be to apply the integral image formula to each of the rectangles separately.
However, since there are deductions along the corners of the rectangle, a more efficient approach would be,
a traversal upon only the corners of the original domain, omitting corners in the interior.
This formula is named: "the Antiderivative Formula".
It states that the double integral of a function over a finite unification of rectangles can be evaluated
via a linear combination of the cumulative distribution function at the corners,
where the parameter alpha_D is uniquely determined according to the corner's type.
The Antiderivative Formula is illustrated in this demonstration.
Given the unification of rectangles colored in blue,
then watch how alternately adding and subtracting the cumulative distribution function's values at the corners of the domain
finally results with the double integral over the given domain.
Our aim will now be to extend the Antiderivative Formula to more genereal types of domains,
by introducing an integration method that results with an "automated" division of the domain
into a unification of rectangles, over whom the Antiderivative Formula is applied,
and "all the rest" – over whom the double integral of the original function is evaluated separately.
As we saw in a previous lecture, classification of corners is most naturally performed
via an inquiry of the curve's one-sided detachments at the point.
Once the corner is classified,
the parameter alpha_D is determined.
We extend this idea to more general types of points and curves.
This vector is the curve's tendency indicator vector at a given point.
Here we can see how the the tendency indicator vector at the pink point at the center
is related to the curve's position with respect to that point.
We will now give an intuition to the term of tendency of a curve.
Tendency is a pointwise operator that agrees with the parameter alpha_D from the Antiderivative Formula.
To calculate it, we place a right angle at the point where the tendency is to be evaluated,
such that the quadrant that the angle defines is contained in the left hand-side of the curve;
the tendency of the curve is the number alpha_D of that right angle.
For example, here the tendency is -1;
and here, since there are 3 such right angles on the left hand-side and two of them deduct each other,
and we remain with a tendency of +1.
Another examples:
in both these cases the tendencies are zeroed due to deductions.
Note that in case the curve is slanted,
then its tendency is independent of the curve's orientation.
Here we see some other cases of curves and their tendencies.
Note that tendency has a deep relationship with the tendency indicator vector –
and in fact, it can be naturally defined via this tool.
So here we see the definition of the curve's tendency (positive and negative stand for +1 and -1 respectively)
according to the curve's tendency indicator vector at the point.
Now we will introduce a new integration method that is based on the term of tendency,
and in turn will enable to extend the Antiderivative Formula to more general types of domains.
Generally speaking, the line integral of a function over a given curve is defined by selecting points on the curve,
evaluating the function's values at these points,
and then taking the limit of the evaluated expression as the number of selected points approaches infinity in a proper way.
The definition of the Slanted Line Integral is of a different nature:
this integration method is taking place not only over the curve,
but also by the domain bounded by the curve and two lines which are parallel to the axes,
such that the domain is to the left hand-side of the curve (this domain will be called "the curve's positive domain").
If we try to define the slanted line integral of a function's cumulative distribution function over the curve
simply as the integral of the given function over the positive domain of the curve,
Then additivity wouldn't hold:
notice that the term to the left includes the integral of the function over the rectangle,
which is not included in the term to the right.
So how can we resolve this problem?
Well, assuming that our curve is uniformly tended
(that is, its tendency indicator vector is constant for each interior point),
and that it is contained in another given curve,
then we can add to the definition a special linear combination of the cumulative distribution function
at key points of that domain.
The coefficients are determined according to the curve's tendencies.
Thus, this integration method combines between continuous math (the double integral over the domain)
and discrete math (the linear combination).
So now we see why the above definition succeeds where the previous definition fails:
given a curve, if we choose to perform the slanted integration over the entire curve,
or as a summation of its subcurves,
then the Antiderivative Formula assures that the results are identical,
since the integral over the missing rectangle equals the linear combination of the cumulative distribution function.
The slanted line integral over a unification of uniformly tended curves equals, by definition,
to the sum of the slanted line integral over each of the subcurves.
You can explore this integration method at Wolfram Demonstrations Project,
and view more of its properties, such as linearity, at the preprint.
Using the slanted line integral, when applied to a closed, simple and continuous curve,
we can now naturally extend the Antiderivative Formula to more general types of domains.
Given such a closed curve, first let us divide it into uniformly tended subcurves:
first the negatively tended subcurves,
and now the positively tended.
We highlight the points that separate between the uniformly tended curves that we chose.
Black or green points stand for a zero and positive tendency of the curve at the points, respectively.
And now we will calculate the slanted integral over the curve via the sum of the slanted integrals over its uniformly tended subcurves..
Notice that the coefficients at B_3 and B_4 deduct each other, hence this vertex is colored in black
– to denote that the coefficient of the cumulative distribution function there is zeroed.
Finally, the slanted line integral has covered the domains colored in orange, and the "miracle" is that..
the values of the cumulative distribution function we added
are equal exactly to the integral of the original function over the missed rectangle, according to the Antiderivative Formula!
Thus, this equation sums up to be the double integral of the original function over the given domain.
This is a special case of the..
.. extended Antiderivative Formula,
that states the relationship between the double integral of a function over a domain,
and the slanted line integral of its cumulative distribution function over the edge of the domain.
More complicated cases are illustrated at Wolfram Demonstrations Project.
Thank you for attending this lecture.
Please find my email address attached,
and feel free to contact me to discuss this research.
Make sure you subscribe, as there will be more detailed video lectures uploaded soon.
You can visit the theory's page at Wolfram, and view a preprint.
Thank you�