Worth Reading

J. Ponce, et al. Dataset Issues in Object Recognition
comment: this paper provides a very good review of part-based objection recognition algorithms and it reveals some problems of existing algorithms: the dataset they use tend to be oversimplified. And it points some more difficult real world dataset for further research.

Mardia. Multivariate Analysis.

Exercise 3.3.3

CG Final Project: Augmented Reality

To simply the project, Dr. Eraldo let us to use Camera Calibration Toolbox for MATLAB and its dataset for the experiment, so we can use the calibration results directly. The toolbox works fine, but a tricky problem drove me crazy.

The basic idea is using the calibration results to:
(1) set up the OpenGL intrinsic parameters for the camera
(2) use the extrinsic parameters to pose the camera.

For problem (1), I tried to use ARToolkit's argConvGLcpara2 function to convert it into OpenGL projection matrix format. Then, I use the simplified version, using glFrustum instead.
Suppose the width and height of the image is 640, 480 and the focus length is 600, then we can safely set the frustum as
glFrustum(-320,320,-240,240,600, 100000);

Note that ARLib use a different unit! It normalize everything by the focal length. I spend a hell lot of time to figure this out.

This simplification works for modern cameras, whose skewness and aspect ratio and central deviation is very small.

For problem (2), it seems easy to load the GL_MODELVIEW matrix with some calculation. But with the data output from the Camera Calibration Toolbox, no existing formulations are right.

It's because that in this TOOLBOX, the camera coordinate system is different from OpenGL, where the z-axis is pointing on the opposite direction of the camera. So anther transformation should be considered to reverse z-axis and y-axis. I simply pull out a paper and worked out all the math to manually calculate the relationship between the view point, view direction and up vector to solve the problem.

A pitfall that bothered me a whole weekend.

This question looks easy at the first glance, the problem is that I worked out two paradox solutions. Fortunately, I figured it out with the help of Ray Vikson in Google group sci.math:

******************************************************Wei
Question: x1, x2, x3 are I.I.D. samples from normal distribution
N(0,cosi^2).

y1=x1+x2, y2=x2+x3, then what is the conditional distribution of y1
given y2, i.e. p(y1|y2)?

I work out two solutions, but they contradicts, can anybody help me to
figure out why?

Solution1:

Given y2=a, then x2=a-x3, so y1=x1+a-x3. So given y2=a, it's easy to
verify that y1 is still a normal distribution
N(a,2*cosi^2).

Solution2:

vector [x1 x2 x3]' is a multivariate normal distribution and its mean
is [0, 0, 0]' and covariance:
| cosi^2 0 0 |
S= | 0 cosi^2 0 |
| 0 0 cosi^2 |

vector [y1 y2]'= A * [x1 x2 x3]'

A is a matrix
| 1 1 0 |
| 0 1 1 |

So, according to the theorem (Mardia, Multivariate Analysis, 3.2.1,
3.2.4) , a linear transformation of multivariate normal distribution
is still a normal distribution and it's mean and variance matrix can
be obtained by:

mean=A* [0,0,0]'=[0,0,0]';

variance=A*S*A'
| 2* cosi^2 cosi^2 |
= | cosi^2 2*cosi^2|

And given y2=a, y1 is still a normal distribution, and the mean and
covariance is

mean = u1 + Sigma21 * invert(Sigma 22 ) * (a -u 2) = 0 + 1/2 * (a
-0)=1/2 a?????? which is not equal to solution 1???

And the same problem happened with the variance matrix.

How could this happen? And which solution is right?

Please help.

Thanks

*************************************************Ray Vickson
et's eliminate the constant cosi^2, because it serves no useful
purpose (and anyway it is not clear whether this should be cos(i^2) or
cos(i)^2); thus, take Xi ~ N(0,1). Starting from the multivariate
distribution of (X1,X2,X3) and using standard methods (I used moment-
generating functions, but there are other ways) we get the
multivariate distribution of (Y1,Y2) as
f(y1,y2) = C*exp(-(1/6)[y1,y2]M[y1,y2]'), where [y1,y2]' = column
vector and M is the matrix M = [[2,-1],[-1,2]] (that is, row(1) =
[2,-1] and row(2) = [-1,2]). The variance-covariance matrix is [[2,1],
[1,2]], whose inverse is (1/3)M. We have C = sqrt(3)/(6*pi). The
conditional distribution of Y1, given Y2 = y2 is f(y1|y2) = f(y1,y2)/
f_Y2(y2), where f_Y2(y2) = integral(f(y1,y2) dy1, y1=-inf..inf) = exp(-
y2^2/4)/(2*sqrt(pi)), so we get f(y1|y2) = exp(-(2y1 - y2)^2/12)/
sqrt(3*pi). This gives E(Y1|Y2=y2] = y2/2 and var(Y1|Y2=y2) = 3/2
(letting Maple 9.5 do all the computations).

So, Solution 2 appears to be correct. This leaves the question: what
is wrong with Solution 1? That is a good question, and I don't see the
answer at the moment. I am pretty sure that Solution 2 is OK because
it's obtained using known, well-proved formulas applied in a detailed
step-by-step manner.

R.G. Vickson

*************************************************Wei

Thanks. Ray. I think I figure out this problem now.

Solution 1 is flawed, the reason is:

given y2=a, x2=a-x3, so y1= x1+a-x3. No problem, but this time the
distribution of x3 is not N(0,1) anymore. It's p(x3|y2=a) and the
variance is bounded somehow by this condition, and the conditional
distribution of x3 is like N(0,1/2). p(x1|y2=a) is still N(0,1)
because x1 and y2 are independent.

So y1 is NOT what I assumed.

Thank you. This paradox bothered me for a whole day!
***************************************Ray Vickson
Of course! I could kick myself for not seeing it. This is yet another
instance showing how careful one must be when using probability
arguments, and that is why the detailed, long-winded approach is
sometimes the best.
R.G. Vickson

Worth Reading

Probabilistic Automata: Vidal et al., IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 27, NO. 7, JULY 2005

Presentation Paper for Formal Language class.

comment: The probabilistic extensions of NFA and CFG is reviewed in this paper. It's extensive and well organized.
The extension to Tree Automata is difficult to catch. Actually, considering the data that NFA or even Turing Machine accepts are 'strings', or sequence of characters, as aba and baa are considered different. But this structure is simple.
So how about adding stronger structure to it? Like tree structure? So the trees formed by characters (labels as called in the paper) will be processed by an Automata.
For a classical automata, characters in the string are eaten one by one, and the Automata changes its state correspondingly. For a tree automata, every subtree is eaten first before a new node can be eaten, and because the number of subtrees can vary between the nodes, so the dimension of the domain of transition functions is variable accordingly.

The paper Using Regular Tree Automata as XML schemas provides a good example of its application to parse XML documents (which is indeed instances of tree data). Although tree automata is interesting, I don't think it extends much on NFA, because every tree corresponds a string by ordered traversing.

Worth Reading

Ariadna Quatoni et al. Conditional Random Fields for Object Recognition

comment: Conditional Random Field with Hidden Variables. They use Conditional Random Field for Object Classification in an ad-hoc way. The result and methods are still preliminary.

Fast ND multidimensional gaussian mixture random generator

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=17489&objectType=file

After fixing a small bug in the code, I found this program works well to generate multidimensional mixture-gaussian distribution.

L. Greengard and V. Rokhlin, A Fast Algorithm for Particle Simulations. 1987
comment: A super clear paper on Particle Simulations. After you read this paper, you can clearly see that KDE is actually a special case of this algorithm.

Worth Reading

William T. Freeman and Edward H. Adelson. The Design and Use of Steerable Filters. IEEE PAMI
comment: Kinda old, but nice tutorial for steerable filters and Gaussian derivative filters.

Jerry Jun Yokono, Tomaso Poggio. Oriented Filters for Object Recognition: an empirical study.
Jerry Jun Yokono, Tomaso Poggio. Rotation Invariant Object Recognition from One Training Example. Tech Report 2004.

comment: Using dominant orientation information to achieve rotation invariant.

Cat downstairs

Worth Reading

Stephen Della Pietra, Vincent Della Pietra, John Lafferty. Inducing Features of Random Fields. PAMI. 1997

This paper is quite theoretic and uses several important theorems of Mathematical Analysis. Well written and very readable.

page 4. Proof of proposition 1 and proposition 2 is not so straightforward as declared in the paper. So I just work it through step by step and here is the scanned version of my manuscript.
It's interesting to see in proposition 2 that the problem can be simplified into Bernoulii model.

Is there anyway that we can share our comments for papers?


Appendix I DUALITY. Lemma 4


4.b Auxiliary functions, Lemma3. One should notice the following theorem in Analysis:
For any compact set S and a sequence A in S, A must have a cluster point in S.

In proof of Proposition 5: because the sequence q^k belong to Q, so its cluster point must belong to the closure of Q.

Since Improved iterative Scaling algorithm is based on a bound function A(r,q), I strongly doubt that they could find an even better boundary function and further improve the convergence speed for the algorithm and I doubt that this problem could have already been solved somewhere in the optimization context.