31
$\begingroup$

Is anyone aware of any research/papers/software for identifying a trail (as a line or point-to-point curve) in an image of a forest scene (from the perspective of the camera standing somewhere along the trail)?

I'm trying to find an algorithm that could take an image like:

alt text

and produce a mask, identifying a likely "trail", such as:

alt text

As you can see, the original image is a bit blurry, which is purposeful. The image source can't guarantee perfect focus, so I need to be able to handle a reasonable amount of noise and blurriness.

My first thought was to apply a Gaussian blur, and segment the image into blocks, comparing adjacent blocks looking for sharp color differences (indicating a trail "edge"). However, I quickly realized that shadows and other changes in lighting easily throws that off.

I was thinking about extracting SURF features, but I've only had success with SURF/SIFT when the image is perfectly clear and with consistent lighting.

I've also tried scaling the images and masks down to much smaller sizes (e.g. 100x75), converting them into 1xN vectors, and using them to train a FANN-based neural network (where the image is the input and the mask is the desired output). Even at such a small size, with 1 hidden layer with 75% the size of the input vector, it took 6 hours to train, and still couldn't predict any masks in the testing set.

Can anyone suggest any other methods or papers on the subject?

$\endgroup$
  • 1
    $\begingroup$ You didn't mention anything about it, but do you control the camera/image acquisition? People use vegetation index using near infrared images in similar situation (consider computing forest coverage from a satellite). If you have near infrared, the problem is straight forward to solve. $\endgroup$ – carlosdc Oct 18 '11 at 3:10
  • $\begingroup$ I do, somewhat. I'm taking images with a cheap monocular camera (webcam/cellphone camera), but I don't think they store infrared. $\endgroup$ – Cerin Oct 18 '11 at 13:13
  • $\begingroup$ Using multiple color filters that can differentiate between the spectra of vegetation and dirt would probably be helpful $\endgroup$ – endolith Oct 18 '11 at 14:43
  • $\begingroup$ I'm curious if you've tried a Bayesian approach to train and detect . I had an answer that I wrote a few days ago, but then deleted it because I thought you had dismissed it after trying. If you haven't considered that option yet, I'd be happy to undelete it. $\endgroup$ – Lorem Ipsum Oct 25 '11 at 20:18
  • $\begingroup$ @yoda, What do you mean by Bayesian approach? I'm only familiar with Bayesian as applied to discrete classification and logical networks. I'm not familiar with it being applied to CV. I don't remember seeing any posts by you. $\endgroup$ – Cerin Oct 26 '11 at 0:17
13
$\begingroup$

It may not be sufficient by itself, but since one of the problems has to do with lighting variations, a shadow removal pre-processing step may help. The technique I'm thinking of is described in the following paper:

"On the Removal of Shadows From Images", G. D. Finlayson, S. D. Hordley, C. Lu, and M. S. Drew, IEEE Pattern Analysis and Machine Intelligence (PAMI), Vol.28, No.1, Jan, 2006, pp.59-68. http://www.cs.sfu.ca/~mark/ftp/Pami06/pami06.pdf

The first part of the process produces an illumination invariant grayscale image, which is probably what you want in this case. Here's a shot of the example they give in the paper:

Shadow Removal
(source: datageist.com)

In fact, taking the process one step further to produce a "chromaticity" image may be what you need to cleanly distinguish between the live and dead leaves. Once again, an example from the paper:

Chromaticity
(source: datageist.com)

The catch, however, is that the camera needs to be calibrated first. Assuming that's possible, some combination of the representations they describe will probably make the other methods you're using more effective.

$\endgroup$
12
$\begingroup$

I don't believe you have enough information in the source image to produce the mask image. You might start by segmenting on color, i.e. green is not trail, gray/brown is. However, there are gray/brown regions on the "trail borders" that are not represented in your mask. (See the lower left quadrant of your source image.)

The mask you provide implies structural constraints not evident in the source image: for example, perhaps your trails are of fixed width - then you can use that information to constrain the preliminary mask returned by your pattern recognizer.

Continuing the topic of structure: Do trails merge with others? Are trails delineated with certain soil/gravel features? As a human (that is reasonably good at pattern recognition!), I'm challenged by the features shown in the lower left quadrant: I see gray/brown regions that I cannot discount as "trail". Perhaps I could do so conclusively if I had more information: a map and a coarsely-known location, personal experience on this trail, or perhaps a sequence of images leading to this point - perhaps this view is not so ambiguous if the recognizer "knows" what led to this scene.

A collection of images is the most interesting approach in my opinion. Continuing that line of thought: one image might not provide enough data, but a panoramic view might disambiguate the scene.

$\endgroup$
  • $\begingroup$ Yes, trails merge with others. And yes, trails are delineated by soil/gravel features in that those features should be distinct from the non-trail areas. I agree, that the image may be challenging in some sections, but I still think there's enough info to make a fairly good guess about where the trail is. Even though you're unfamiliar with this trail, it sounds like you had no problem with it (except for the lower-left-hand area, which is understandable). $\endgroup$ – Cerin Oct 14 '11 at 14:27
  • $\begingroup$ Indeed I can make a pretty good guess as the boundaries of the trail. But, I'm afraid I'm relying on more information than is presented in the source image. I "know" what a trail is - presumably because I've constructed a model or template of the salient features comprising a trail: through direct experience, or seeing well-defined trails in pictures, etc. To summarize: in recognizing the trail in the source image, I'm drawing on much more than what I observe in the source image. $\endgroup$ – Throwback1986 Oct 14 '11 at 15:56
  • $\begingroup$ There are some characteristics of the trail that a vision system might exploit: presumably we can assume the trail represents free, navigable space. Thus, tree, bush, and rock features can be classified as "not trail". Perhaps a texture analysis could assist discerning these? I'm not certain, though: the ground under the trees (mid to upper left) looks quite similar to the trail. $\endgroup$ – Throwback1986 Oct 14 '11 at 16:01
  • $\begingroup$ My first idea would have been to refer to the LU or Eigen transforms which give a high response when texture is very rough. However, here the main distinguishing feature between trail/non-trail seems to be color. So maybe converting it into HSV color space and making a mask from the pixels that have 'earthy' hue - brownish or ocher - would give a rough estimate. $\endgroup$ – AruniRC Oct 21 '11 at 10:30
12
$\begingroup$

There's no single algorithm that will magically detect trails in a random image. You will need to implement a machine learning based routine and "train" it to detect trails. Without going into too many details, here's a rough outline of what you would do in a supervised learning approach.

  1. You will need a set of "training examples", by which I mean several pictures of trails in different environments, in which you (the supervisor) have labeled what counts as "trail" and what's the background "forest". You break the images up into smaller sections (typically 8x8) and transform it to a "feature space" by taking the DCT (discrete cosine transform) of the blocks. The DCT of each block in this case gives you a 64 point "feature vector".
  2. Defining a feature space $\mathcal{X}$, set of features $\mathbf{x}$ (a subset of your 64 point feature vector), and a class space $\mathcal{Y}$ with classes $y_1=trail$ and $y_2=forest$, you calculate from your training sets:

    • the class conditional distributions
      • $\mathcal{P}_\mathcal{X|Y}(\mathbf{x}|trail)$, the conditional density for the features when the class is $trail$.
      • $\mathcal{P}_\mathcal{X|Y}(\mathbf{x}|forest)$, the conditional density for the features when the class is $forest$.
    • the class probabilities or the prior
      • $\mathcal{P}_\mathcal{Y}(trail)$, probability of finding a $trail$ in a block
      • $\mathcal{P}_\mathcal{Y}(forest)$, probability of finding a $forest$ in a block
  3. With this, you test your image (again, breaking it up into smaller pieces) and calculate the posterior probability. Using Bayes' decision theory, you'd define your binary (in this case) selection criteria something like

    $$\widetilde{y}_i(\mathbf{x})=\arg \max_{y_i}\quad \mathcal{P}_\mathcal{X|Y}(\mathbf{x}|y_i)\ \mathcal{P}_\mathcal{Y}(y_i)$$ where you assign each block to that class which has the highest posterior probability. This will result in your binary mask.

Note that this is a very simplified overview of the approach. There are several things to take into consideration and the most important of them is choosing the right set of features for your problem. You can also do more complicated things like use mixture models and kernel based density estimations, but all of that is too detailed and time consuming to write in an answer.

For a motivation and confirmation that this approach is worth trying, here's an example from something I did a long time ago as a course homework, which is very similar to what you're trying to achieve. The objective was to detect the animal from the background vegetation (left image). The figure on the right shows the binary mask obtained after "learning" to distinguish between the foreground and the background.

enter image description here enter image description here

To learn more about machine learning, you might want to look at a few text books. One of the well known and often recommended textbooks in the field is:

T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd Ed., Springer-Verlag (2008)

which is now available as a free PDF at the link provided. Another decent book is:

R. O. Duda, P. E. Hart and D. G. Stork, Pattern Classification, 2nd Ed., John Wiley & Sons (2001)

$\endgroup$
  • 1
    $\begingroup$ On that note, I would like to point out ml-class.org which is an excellent introduction to machine learning. $\endgroup$ – bjoernz Oct 26 '11 at 11:10
  • $\begingroup$ Interesting method. However, when you say the Py(trail) and Py(forest) are the "probability of finding a trail in the entire picture", do you mean probability of finding them in an 8x8 block, or the entire image? If the entire image, I'd imagine both of these would be 100%, since all of the training images will have both of these somewhere. $\endgroup$ – Cerin Oct 26 '11 at 13:46
  • $\begingroup$ @Cerin: Sorry, by Py(trail), I mean probability of finding it in a block. So that would be the total of all blocks that have trail by total number of blocks in the entire picture. I've edited it to correct that $\endgroup$ – Lorem Ipsum Oct 26 '11 at 14:15
  • $\begingroup$ How would you define the feature space X? Would you use something like K-Means clustering to reduce the dimensionality of the 64 point feature vectors to something like 10 features? $\endgroup$ – Cerin Oct 27 '11 at 21:45
  • $\begingroup$ @Cerin Yes, K-means is one of the common approaches to reduce the dimensionality. $\endgroup$ – Lorem Ipsum Oct 30 '11 at 6:24
9
$\begingroup$

Is this of any interest?

Real-time traversable surface detection by colour space fusion and temporal analysis

$\endgroup$
  • $\begingroup$ Yes, this seems to be very similar to my domain. Thanks. $\endgroup$ – Cerin Oct 17 '11 at 15:56
5
$\begingroup$

It looks like a problem for texture segmentation(not a color segmentation) There is a lot of methods,

they often using Gabor wavelets, like this http://note.sonots.com/SciSoftware/GaborTextureSegmentation.html

Superpixels based segmentation http://ttic.uchicago.edu/~xren/research/superpixel/

and similar graph cut segmentation http://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision

here is wiki overview http://en.wikipedia.org/wiki/Segmentation_(image_processing)

$\endgroup$
  • $\begingroup$ gabor texture segmentations seems to be nice! $\endgroup$ – nkint Jun 19 '12 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.