Re: what robots see

Wolf Kirchmeir wrote:

Michael Olea wrote:
Wolf Kirchmeir wrote:

Michael Olea wrote:
Wolf Kirchmeir wrote:

Curt Welch wrote:
[...]
http://stardustathome.ssl.berkeley.edu/

They need help finding needles in a haystack. ...

[... Notes on image parsing...]

Thanks for the explanation, some of which is beyond me, eg the general
concept of probabilities I get, but haven't a clue on how it would be
implemented.

Well, that is one of the hard parts - a good probability model is crucial to
an industrial strength image parser. It is also an active field of intense
research.

The particle track detector problem has some similarities with another
problem that has received much attention: tracking roads in satellite
images (e.g. Geman and Jedynak). My first thought was to use a roughly
similar approach. I would start by modeling track geometry. First of all
these tracks, unlike roads, are straight. So we are looking for linear
structures. The next question is what is the distribution of track lengths.
We know that tracks will occur over a range of scales because a) cursory
inspection tells us that, and b) we expect a priori that we have particles
of a range of sizes. Further, the range of track lengths is bounded by the
size of the images on the upper end, and by image resolution on the lower
end. Can we say anything more about the distribution? We don't want to bias
our results, so one thought is to use a "non informative prior", that is,
to treat all lengths within this range as a priori equally likely. That is
in itself a bias, though, and maybe not the best choice. Another approach
is to choose a prior distribution that better models our expectations (e.g.
large tracks are less frequent than small ones), but still choose a prior
with high variance. Whatever prior we choose is not likely to have a strong
effect in this case because other factors (e.g. luminance contrasts across
track/background boundaries) are likely to outweigh whatever weak (high
variance) prior we assume.

The next aspect of track geometry I would want to model is the relationship
between track length and track width. If we took a single width, say half
way along the length of the track, then there is some joint probability
distribution P(length, width). Intuitively we can expect wider tracks to be
longer, but we do not expect a rigid relationship. We could model it as a
probability distribution over length to width ratios P(length/width).

Next I would consider how track width varies over the length of the track. I
would expect that the track narrows as we move from track start to track
end. As a first cut I would go with a linear relationship
deltaWidth/deltaLength, which again would not be a rigid rule but have some
probabilistic distribution. Further, this scaling might vary as a function
of track length, so we might look for P(dw/dl|length), the conditional
distribution of scaling given track length.

Finaly, because of the particle collection process, there might be a bias in
prefered direction with respect to some coordinate system. So the track
geometry model might include a distribution over the angle the track makes
with some coordinate axis.

So this is our basic track geometry probability model:
o Tracks are straight
o There is a distribution over track lengths
o There is a distribution over track length to reference-point width
o There is a distribution over the rate of change of track width with length
o There is a distribution over track direction

To make the model quantitative rather than just qualitative we need to
estimate the distributions from a truthed data set (and any background
knowledge we can bring to bear).

So much for track geometry; next up is the question of luminance profiles.
For this problem luminance gradients seem to be a good indicator of track
boundaries. In other scene analysis problems more subtle features, like
texture, are needed. The basic idea here is to design a filter (or a set of
filters) that have a strong reponse to particle tracks (or particle track
boundaries) and a weak reponse off the track. We could take two approaches:
1) look for "bar-detector" type filters that model the luminance profile
across a track (perpendicular to its length), or 2) look for
"edge-detector" type filters that have a strong reponse to track/background
boundaries. Or we might include both types of filter. Either way, since we
are looking for tracks at different scales, we will want filters at
different scales - multi-resolution analysis (an efficient way to do this
is to use a wavelet transform). Conceptualy, we construct a new image from
the original by computing the reponse of a filter at each point in the
image (the reason I say "conceptualy" is because in practice there is no
need to do this one filter at a time - the wavelet transform allows us to
do this much more efficiently). What we need now are the probability
distributions P_on(y = phi(x)) and P_off(y = phi(x)), where y is the
response of filter phi, and P_on (y) is the probability of response y when
we are "on track" and P_off(y) is the probability of response y when we are
"off track". It is the ratio P_on()/P_off() over all values of y (quantized
over some range) that determines the effectiveness of the filter. For
effective filters we do not need strong priors (low variance) for the
geometric model. The task is easy. If the filters are not effective then we
do need strong priors - the task is hard. If the filters are not diagnostic
at all then the task is impossible. My sense is that in this case the task
is easy.

We need one more piece of information, an estimate of the fraction of images
that contain particle tracks, which we get from the truthed data set. Now
we have every thing we need to compute the proability that a given image
contains a track, and to generate a "most probable parse" of a given image
into track and background subregions of the image. Becuase tracks do not
"nest" (we do not have tracks within tracks) the parse trees are shallow -
a root node for the entire image and a child node for each hypothesized
track.

That's it in a nutshell. I hope that gives you some idea (short of sketching
an actual parsing algorithm) how it would be implemented.


Geman and Jedynak, (1996). An Active Testing Model for Tracking Roads in
Satellite Images. Available at:
http://citeseer.ist.psu.edu/138582.html

-- Michael

.

Relevant Pages

  • Re: different priors (flat, uniform, etc)
    ... integrating the probability along the whole range of values ... that such nuisance parameter is allowed to take. ... A "prior distribution" is a Bayesian term, and means, basically, ...
    (sci.stat.math)
  • Re: Isnt the Frequentist a subset or special case of Bayesianist?
    ... >> where the prior can be anything, ... > There is a fundamental difference between Bayesian and frequentists ... > are also random variables and have a probability distribution. ...
    (sci.stat.math)
  • Re: Bayes theorem for probability densities
    ... The books where I'm studing resolve the problem using Bayes theorem ... You have stated the prior distribution pfor the parameter a, it is 1 with probability 1/2 and 2 with probability 1/2. ...
    (sci.stat.math)
  • Re: different priors (flat, uniform, etc)
    ... integrating the probability along the whole range of values ... that such nuisance parameter is allowed to take. ... A "prior distribution" is a Bayesian term, and means, basically, ...
    (sci.stat.math)
  • Re: Pigeons, People, and Priors
    ... the variance of the probability generator go to zero you have a continuum ... a random-interval 60 s schedule is not. ... The Exponential Distribution ... I probably should have used the phrase "statistical learning theory" rather ...
    (comp.ai.philosophy)