Shadows and stuff

Oh! If anyone stumbles across this -- shortly after I got my dissertation marks back, I uploaded my code to GitHub.

https://github.com/owaindjones/shadows

I haven't uploaded the data to go with it (too much of it!) but we have kept backups within the university -- my supervisor knows where. Not wanting to spam her email address on tumblr, send me an ask if you want to get hold of the data.

I am planning to capture some more data soon; I'll focus on outdoors shadows. I'm thinking quadcopter aerial video in a grassy field on a sunny winter morning :D

My plan is to get ahold of a Matlab license and compare Lalonde & co's actual approach to an implementation more suited to moving video. I will also crowdsource the ground-truthing as much as I can.

I'M NOT DEAD.

I'm doing my writeup now!

Even with this blog, it's really difficult to describe my project from the beginning.

Also, because I'm using LaTeX, I keep getting distracted by how pretty it looks. Plus when I actually get the motivation to write things, I have to spend several hours debugging cryptic errors to find out why it's not compiling.

Having been fighting with the demons of machine learning and statistics for over a week, I'm coming to the definite conclusion that Lalonde & co.'s shadow detection methods do not work on my images. Whatsoever.

Any algorithm I train, be it a Multilayer Neural Net, a Support Vector Machine, a Random Forest, or just simple Logistic Regression, comes out with a high error rate (in the 90th percentile in all tests) and a slightly-better-than-chance rate of classifying edges correctly.

So, I concede defeat. For now...

But that's okay, because I at least know of plenty of reasons why I'm conceding defeat:

Noisy Images: This is the biggest problem, I think. The grain from the webcam images is quite large, and even when applying bilateral filtering and gaussian blur to the images, creates lots of false edges.

Bad Features: Whilst I've tried to generate edge features like Lalonde & co. are doing, there is the possibility that I have misinterpreted their paper. Looking at their source code offers no real help on this, because it's in Matlab and pretty obfuscated. I don't have a good way of detecting whether features are useful or not, bad the attribute selection and other tests in Weka. Weka doesn't think any of the features I try are significant. Again, I think my images have a lot of noise and that plays a major factor.

Too many false examples: 99% of my detected edges are labelled as background. This means any learning algorithm I put the features through is going to be pretty biased towards misclassifying everything as background. To counter this, I've enforced a ratio of 3 times as many background examples as there are shadow, penumbra and object examples. That improved the true positive rates for those classes, but they are still far too low. If I lower the ratio any more, it's going to create more false positives for the other classes.

Too many features / instances: I have, at time of writing, 36 features -- differences and mean values for both sides of an edge, plus the same for the edge normal as a whole, for each of the Hue, Saturation, Value, Red, Green and Blue channels of my images. I have roughly 4,000 edges per image, and over 20,000 edges in total (so 20,000 instances). This gives me huge files (my biggest was 150MB uncompressed, my smallest is 9MB gzipped) which are just comma separated values. My laptop does not like loading these, let alone doing anything with them..! And it's my understanding that too many useless features/statistically irrelevant instances could introduce a bunch of bias into my learning algorithms.

Bad ground truth data -- labelling these images by hand is hard. It's especially difficult to estimate visually where penumbra ends and shadow begins. The penumbra/shadow distinction in my images is probably inaccurate.

Edges are sampled wrong -- One more thing I'm going to try is counting penumbra as shadow, and ignoring object edges; only detecting shadow edges. I also need to ignore all the edges inside a shadow. Right now I'm classifying edges based on where their center point is, but I should be checking either end of the edge as well. If the center point OR one end point is in shadow, the edge could be counted as shadow edge, but if they're ALL in shadow, they're ignored. Same applies to background edges. I will try missing out the object class, but using object edges to classify things as background edges.

Lalonde & co's approach does not suit my data -- They do state in their paper that their approach works for outdoors scenes and only for shadows on the ground. They make the assumption that the images are from high-quality consumer digital cameras which have a lot higher resolution, less ISO noise and less artifacting than frames grabbed from a webcam feed. Their trained data all has shadows that are slightly bluer than their surroundings, due to outdoors lighting and sky colour. They also generate ground probabilities; which I can't do for mine -- my Kondo dataset has the camera angled downwards. Technically, everything is ground. There's no distant horizon or anything. They also are happy to spend several minutes processing a single, static image, which I don't want to do. I want a method that's vaguely realtime (maybe process an image every few seconds) -- which means taking shortcuts. My shadows are all softer, despite having much closer light sources, due to the angle of the lights. The penumbras create lots of wavy edges inside the actual penumbra, and there's also an absence of contours detected on the actual penumbra edge.

I'm still working on this approach, but my deadline for everything is Sunday. Then I'm only allowed to do a little bit of analysis to get some pretty graphs (of things failing), and then write up my report.

I think edges features are probably pretty good for shadows (when they're hard without too much penumbra) -- but there's a fine balance between too many edges and too few edges, for both training and classification. Edge features are good because they can be computed quickly as there's a lot less of them than, say, using sliding windows of pixels for generating features.

I'm also experimenting with a really simple grid-based approach which divides the image into NxN cells. It might be possible to get better features from that... And get at least an approximation of shadow shape. But it will be a lot more granular than if I could get good edges.

It is unfortunate that I haven't got any results worth training a classifier for and testing "in the wild" (so in OpenCV, outside of Weka, using unlabelled new examples from video frames I haven't extracted or ground truthed yet) so far. I think I could speed up my edges approach by coupling it with a simpler approach -- the simple thresholding approaches I wrote at the beginning of my project actually show better results than these networks are currently reporting -- higher accuracy, less false positives. They could be good for filtering out the majority of useless edges in an image / filtering out image regions that definitely aren't shadow.

If I do get something vaguely workable by Sunday, I will test combining a "weak" thresholding classifier with a "strong" (although actually probably weaker, right now) edge/cell classifier.

So as of tomorrow, I have 7 days left to experiment with code.

The last few weeks I have spent experimenting with edge detection techniques. Sometimes, edge detection is spot on and detects shadows and objects correctly. Mostly, it doesn't. Finding the right global parameters is a fruitless effort, as you can't do that in a robot in real-time and it's not very smart.

So, in these last 7 days, I plan to train either a Neural Network or a Support Vector Machine what shadow edges are.

My approach is inspired by Lalonde et. al.'s method of detecting ground shadows in photographs. They have a promising approach that works well for "consumer level" images -- photographs with noise and compression artefacts -- which is definitely what I need for my mobile robot images. The setbacks are that A) they are looking specifically at shadows cast onto the ground (I want to detect all shadows), and B) their approach is very computationally expensive.

My approach needs to run maybe several times a second, rather than once every few minutes.

Still, I have taken lots of good ideas from their approach, and am planning the following:

Take an image (video frame), perform some preliminary noise reduction somehow. Gaussian blurring helps, but also makes the edges I'm trying to detect softer. Bilateral filtering helps smooth out noise whilst preserving edges and textural information -- but it is a lot more expensive. This isn't part of my approach; it's a preprocessing step that is necessary for my own images, but with a cleaner, less noisy camera, may not be necessary.

Convert the image into the HSV colour space, to separate brightness from hue and saturation. I've tested other colour spaces that do this previously, and there wasn't really much difference between e.g. HSV and the L*ab or L-U-V spaces, so I'm sticking with HSV as conceptually it's the simplest to follow: one channel for hue, one for saturation, one for value.

Keep a copy of the original RGB image for later use.

Do the following, at three different scales (an image pyramid) -- Original image, half-size image, quarter-size image...

Run canny edge detection on the image per channel to detect all the edges -- and there will be a lot.

Detect the contours of these edges.

For each contour, generate normals for every line segment (so, the line segment rotated by 90 degrees). Ideally, I'd have normals spaced equally across the line, say every 10 pixels or something - but I'm not sure how to quantize a contour like that. Will experiment with that this evening.

For each normal, get a bunch of features. These features are things like RGB channel ratios, ratio of saturation to value, mean/standard deviations of every channel, plus local binary patterns for texture.

Feed these features into a SVM / Neural Net, and get its prediction (which will either be "True" or "False" -- in order to detect shadow/object/penumbra classes, three different SVMs/NNs need to be trained with the correct features). If the edge is True for shadow, paint that line onto a new black & white image.

Do the same for the other two image scales, then scale the outputs (without any filtering) to the original image size.

Compare the outputs; if pixels are marked as shadow edge in more than one scale, mark them as such, otherwise discard them. (Actually, this is something I will experiment with. The voting heuristic used might be important)

The output will hopefully be a bunch of edges directly correlating to edge/object/penumbra edges in the original image.

The challenge then is to fill those edges in. For this, I could do some dumber detection stuff -- one side of a shadow edge is going to be darker, for example. That side becomes a seed point for a flood fill algorithm. Objects are harder...

I've already got code that gets features for normals of ground truthed images. However, right now it only gets positive examples. I need to find a way of getting negative examples also. Then I'm going to train some NNs and some SVMs using scikit-learn. I spent Friday playing with Weka, which is a very neat but also very scary and I couldn't figure out how to tell it which of my data's columns was the label/classification it was meant to be learning.

Then, once I've found the best selection of features and the best machine learning algorithm to use, I will implement it in OpenCV C++ code.

Yesterday and today's work was a poster relating to my project.

The "Technical Details" / "Current processing pipeline" section in the bottom right quarter is what I plan to do in my remaining ~9 days of coding time I have left on my project.

More colour analysis!

Since I have a bunch of ground truthed images, I decided to see what the edges of shadows looked like on a graph.

What I'm doing here is:

Loading an image and its associated ground truth

Converting the image to the HSV colour space

Doing Canny edge detection three times on the ground truth - for shadows, penumbras and then objects.

Detecting the edge contours

Calculating the normals that make up the line segments of those contours (the line rotated 90 degrees), and creating a line of roughly 50 pixels that follows the origin and angle of that normal

Getting a list of pixel values for each of these lines, and plotting those values in line charts.

So now I have a profile for every shadow, penumbra and object edge in my image. I can check their numbers in the Value channel of the HSV colour space, to see if there's any trends.

I'm also calculating the overall mean value of the entire image -- for this example it's 153. It's shown on the graphs as a grey line (might be hard to see on the shrunk-down images on tumblr)

In this example, penumbras are important -- they dip below the mean value by about 30 when they become shadow.

Shadow stays at around 0 to 50.

The values of the object edges stays above the mean value; it's also all over the place though.

For this image, nearly ALL of the shadows are above the mean image saturation:

And penumbra hovers slightly above the mean:

Object saturation deviates more, but in this example dips below the mean. I think I should ignore the saturation of objects however.

What am I learning from this / What could it imply?

Shadows in this data set have value below the mean and saturation above the mean

Penumbras gradually dip below the mean value and hover on the mean line.

(I have more to say, but I've forgotten -- got distracted by analysing more images -- maybe will edit this later if I remember)

So far, my detection methods have involved a slew of adjustable 'magic numbers' for parameters. It's about time I make use of statistics generated from the images themselves -- like mean values. The mean hue/sat/value gets you a vague idea of the scene's light levels and background colour, and instead of thresholding shadows based on some global threshold or ratio, my code could say "this is a shadow because its gradient dips below the mean by over X amount, and it has a noticeable change in threshold.

These graphs are very noisy. Let's take single, random normals for shadow, penumbra and object edges:

Much clearer :)

I think I should be dealing with ratios and slope gradients when it comes to checking pixel values around these normals -- relative comparisons, as opposed to comparing against the global mean.

I hacked together some more graphing stuff in Python yesterday -- I wanted to see how pixel values changed across a line as it went in and out of a shadow.

This set of charts is showing the hue/saturation/value levels for a horizontal and vertical line (30 pixels long each) on one of my Kondo images.

The top-left graph shows the vertical profile, the bottom-right graph shows the horizontal profile. The horizontal profile is particularly interesting...

For this data set, one of my original hypotheses, that shadows have lower saturation than their surroundings, turned out to be completely wrong. In these images, possibly because the table is already a rich reddish surface, the saturation of shadows is actually higher than areas of no shadow. This is an assumption I've seen made in a bunch of the literature I've read about the characteristics of shadows -- that colour saturation tends towards being lower in shadow. Possibly this is true for outdoor shadows, but for these images is not true.

Here's another example:

(In this one, red = value, green = saturation and blue = hue)

The Pioneer datasets, where the carpet is greyer, has shadows with less saturation, in contrast.

I regret not thinking of doing this when I originally got my datasets -- it has helped me figure out the relationship between saturation and value better. How saturation and value interact in an image depends entirely on how colourful a surface onto which a shadow is being cast is.

The fact that they *do* change together does imply a relationship though -- so whilst naive chromacity-based approaches to detecting shadow based on global thresholds fail, ones using ratios and detecting edges (large changes in signal) without caring whether the signal is going up or down, do alright.

So, since mid-project demo I seem to have stagnated. I've been doing lots of work, just not making much progress, which is frustrating. Still, I think I'm over the worst of that now.

I was stuck debugging silly C++ things for days. On the plus side, I now have a better understanding of allocating resources when it comes to OpenCV, different ways of accessing image arrays etc. - so I now have less glitchy and faster code.

I also spent some time refactoring my code. When I encounter a language family I'm not familiar with (so, static typed OO stuff which is very fast but lets you do very dumb things a la C/C++), all my knowledge of design patterns and good practise goes out the window as I cobble together hacky solutions to things in this brand new language.

I realized last week that copying and pasting existing code and modifying single functions in them to create new programs was intensely suboptimal and have now moved a big chunk of code shared between programs -- stuff like debug output, logging performance info to files, saving images as PNGs, parsing command line arguments -- into another "utils" file which I include in new programs I write. I've been very frugal with preprocessor macros, having just learnt what I can do with them. Probably too frugal. I probably should be using nice cleanly namespaced classes, instead of global variables and macros defined in headers. Still, it works, it makes adding new program options real easy, and it's easy to change things and have those changes reflected across my different shadow detection approaches. +1 for macros which are dumb and lazily-evaluated and on a bigger project would probably come back to haunt me later :)

On the "actual work" side of things, I'm freaking out as I have 2 weeks left to try and produce something that detects shadows better than chance. My best approach so far is still converting images to HSV and thresholding based on value (with the assumption that saturation will change a little bit too). But that's not much better than random.

I'm now poring over the literature again and hopefully going to implement a dumber version of the method described by Lalonde & co. -- they describe "oversegmenting", where they detect loads of edges in an image (which I am doing now, inadvertently) and then remove the weaker edges. My plan is to:

Detect edges using a traditional edge detector (Canny? Sobel? I can test multiple methods; I'll put that through the harness)

Detect the contours of these edges

Following these contours, compare pixels from one side of the edge against pixels on the other side -- if one side's value (as in value from the HSV colourspace) is less than the average*, count it as a shadow and mark at pixel as a "seed point" for flood-filling in later.

*Average in this case meaning the mean hue/sat/value for an entire image, or possibly the cumulative mean of a rolling window of images in the image set -- since I'm dealing with sequences of images in motion, I ought to make use of the fact [assumption] that generally the background is going to remain the same for a few frames and change gradually.

I have a definite feeling of "I have no idea what I'm doing" right now... I've learnt about a bunch of techniques I can use, and their advantages and their setbacks... I need to find a workable combination that can work with my real-world images, which are:

Not static

Incredibly noisy

Full of soft shadows with lots of penumbra

So I do know what I'm doing, it just feels as though I don't ;)

Hopefully I'll have a breakthrough this week. I also have a poster to do before Thursday, and it'd be nice to show off okayish working detection on it by then..!

I've spent hours today making slides for my mid-project demo at the end of this week.

This awfully long image is how I originally planned my project to go (or rather, what my supervisor scribbled down for me as a suggestion, that I expanded on / made little changes to). I wanted to measure my progress, so today I found some Gantt chart software and copied the scribbly paper chart / things inside my own head, into a proper chart. I was starting to get a bit muddled and losing track of time, but I'm on week 7 of project now and I have around 6 weeks left to write and test shadow detection code, then a further 2 or 3 weeks to write up my report and clean up any code.

I'm about 2 weeks behind my original schedule, but that's okay -- things inevitably take longer than expected, or change priority. I spent longer implementing my test harness and ROC analysis stuff than I anticipated, but those two things are going to make the rest of my project much easier.

At some point in the next two weeks I have my mid-project demonstration. It's just a 10-minute presentation in which I can show off what I've done so far, but it has motivated me to think about my project's design in a more formal way.

During the next two weeks I want to implement some smarter shadow detection using chromacity (colours and colour ratios, not just brightness). That involves reading papers like this. That paper had some nice flowcharts in it showing their taxonomy and the order of their image processing chain, which inspired me to go make some charts of my own to describe my design.

I think formalizing my design with visual aids like flowcharts will keep me on track. I have a tendency to just jump into things without writing my ideas down; I can picture the design in my head, but I do not excel at putting these ideas onto paper.

Also, this week I added some timing information into my chains, so I can chart their performance against each other. Right now the two simple thresholding chains have very little difference in performance, the image chains themselves have much more of an impact (kondo1 and one_lamp are two of my real-life data captures and have much less images / ground truths. the artificialN sets have about 10x the number of images).

So the data captured from Kondo is better than that captured from the Pioneers:

Video, recorded at 15 frames per second (much smoother motion)

Less noise, brighter images with more colour saturation

Higher resolution (960x720)

However, due to the fact it was captured as video (which was my only option at the time), the input images have more artefacts from the image compression. That coupled with noise can make it difficult to figure out when shadows start and when they end...

^ Where's the penumbra of the shadow start and end? Where does the actual shadow start and end?

As I'm dealing with three 15fps videos that last around a minute each, I have to be more frugal with producing ground truths. I decided to extract images from the video streams based on key frames a minimum of 3 seconds apart each. This gets me around 20-30 images for each video. Which is a lot of ground truths to draw!

To make my life easier, I wrote my own tool for drawing ground truths... Using tools such as GIMP were proving to be too cumbersome for such a data set. I did look for programs specifically for drawing ground truths for image sets, but they either didn't do what I wanted or were way too hard to use.

As I wrote it in one night, it lets you paint by hand, but has no object manipulation -- you can't define a polygon around an object and then alter the points later (which would be incredibly useful).

I did try implementing edge following for the cursor, but it doesn't work very well for my images as they have way too many edges, even after noise removal:

So -- the result of all this is that I have some pretty wonky ground truths. They may not be that accurate. Because they're not 100% accurate, they're going to skew my ground truth comparisons and ROC curves -- any algorithms I try will look like they're performing worse than they are.

Luckily I have my 100% accurate ground truths for the synthetic image sets.

And, weirdly enough, I am getting some okay ROC curves with the simple greyscale thresholding:

Last Saturday I borrowed another robot for data capture. This little fella is called Kondo, a small humanoid robot owned by the department that my friend Christina is breathing life back into as part of her own final year project.

Robot's shuffling walk looks a little awkward here on the frictionless table surface, but the head bobbing looks great on the videos I captured using robot.

Here's robot's point of view.

Data capture was done by haphazardly taping a USB webcam to the front of Kondo. As you can see in this video, robot's shadow is being cast on the wall, which looks great in the data (woo, self-shadowing is just a small step away from self-awareness)... which is going to be intensely painful to carefully draw in when I do the ground truths for that video.

Here's a video of one of my rendered scenes I mentioned in the previous post. Very simple primitive shapes. Well, except for the monkey head. I love how there is actually a button in the Blender interface to create monkey heads...

Decided to make some artificial datasets for my project. CGI renderings where the camera moves through the scene, in which I can control the lighting perfectly and generate 100% accurate ground truths without having to colour them in by hand as with natural imagery.

Used Blender for the first time; it's like stepping into a jumbo jet cockpit. I've learnt how to use it enough for my purposes though. I now have a couple of artificial scenes and accompanying ground truth sets:

Got ground truths by disabling all textures, reflections etc., colouring all objects in a uniform grey that emitted grey light (so no shading) and still cast shadows. The shadows in the second image (ground truth) should all be pitch black without any fading in or out, but I've solved that issue by counting any pixel value that's not white (background colour) or value 153 (grey, object colour) as a shadow in my ground truth checking code.

Despite being artificial, these are still challenging environments, with fog, ambient occlusions, a mixture of soft and hard shadows, different types of lighting and colours, textured objects with highly contrasting patterns, glossy/shiney/mirrored surfaces, and completely dark areas (which are technically shadow, but I think they're unlikely to be detected as such by most of the detection methods I try next).

The simple thresholding tests I've been doing are therefore no better than they are on the real-world Pioneer images, with far too many false-positives for shadows...

The simplest artificial scene I made was simply a white background with grey cubes casting hard black shadows:

(In that scene, the input images double up as the ground truth images).

So yeah, more conclusive evidence that the dumbest approach to shadow detection is the dumbest. MORE GRAPHS NOW

(It's like cupcake sprinkles :D)

Last week and into this week I've spent writing my "test harness".

The purpose of the test harness is to:

Run a bunch of vision processing programs in sequence (a 'chain')

Run these programs in different sequences (multiple 'chains')

Test different possible combinations of values and command line arguments you could give these programs (within each chain!)

Spit out some statistics at the end (Receiver Operating Characteristic curves) and turn them into pretty graphs and display those graphs alongside the final images and the ground truth images to compare them with.

I've nearly nearly almost completed the test harness stuff now. I would say that I thought about it all carefully before I started writing code for it - and that would be a complete lie. Maybe I can pass it off in my writeup as 'evolutionary design'. Luckily, I chose to write it in Python, and design choices in python usually aren't much more effort than "hm, which of these modules do I import?"

I'm quite pleased with the test harness as it is now however. It does some neat stuff. What little design I did was to write the configuration file first, which became my software requirements. The configuration is done through a YAML file. To start off with, you define different sets of input images like this:

Then do the same thing with ground truths (define a set of ground truths for each of the input sets above).

At the end of the config file, you define the programs you want to use in chains, and then the chains themselves:

Here I'm defining the 'simple_test' chain, which runs a single program, 'simple_shadows', which is defined above. 'simple_shadows' does some very dumb thresholding stuff: converting input images to greyscale, any pixel with a brightness value less than an adjustable threshold (set by the '--shadow' command line argument) is marked as shadow. Any pixel brighter than the threshold set by '--object' is marked as an object, and the rest is marked as background (white colour).

The config file defines a list of different parameters to send to the '--shadow' and '--object' arguments of simple_shadows. The test harness builds a tree structure out of these arguments, to get all possible combinations of them. Then it 'flattens' that tree by following every branch of the tree until it hits the end, and all the nodes it's been through on the way become part of the list of arguments sent to the simple_shadows program.

With those two arguments having 8 and 7 different parameters to try respectively, the chain runs simple_test 56 times for every single input image (that has an associated ground truth). Multiply that by the 8 images I have that currently have ground truths, and the number of folders and output images equals a lot.

You would think that that is a bad thing because it's computationally expensive and uses up lots of memory/hard drive space, but no -- the 448 images in 56 folders spat out by the test harness take up a whopping 4MB of space, because they're just greyscale PNG images with 2 or 3 different shades each. And it takes a couple of seconds to run.

When the test harness is done, it runs a program to compare the output images of the chain against my ground truth images, and spits out a bunch of statistics into a CSV file per directory.

Those CSV files are read by another script that uses matplotlib to create graphs. Which in theory should look pretty, but I haven't quite figured out how to play matplotlib yet:

Urgh.

Couple of hours later, I'm getting graphs that look like this which show the results of my two chains so far. Apart from doing simple thresholding, I'm also testing out Otsu's thresholding method (plus different levels of gaussian blurring), which is a little smarter.

The 'simple_test' and 'otsu_test' chains combined (simple thresholding and Otsu's method) are still getting me some pretty crappy graphs:

But Otsu's method on its own at least gets results that are more consistent with ROC graphs:

I'm at a confusing standoff with my code, because I can't tell which part is wrong. ROC curves should have the false positive rate going up fairly consistently with the sensitivity, following that diagonal line. The steeper the slope, the better the algorithm's performance. However, I've got points all over the place, which shouldn't really happen. In the simple thresholding case, I could put it down to it just being really bad performing. Otsu looks more promising (true-positive rate is high, but so is false-positive rate), but those outliers are still bugging me.

Oh well. If all else fails, I can still eyeball the images ;)