Smokey the Quadcopter @smokeyquad - Tumblr Blog

Building a rope bridge with flying machines

Research from ETH Zurich demonstrates the construction of a human walkable bridge using flying drones working in unison:

The video shows quadrocopters autonomously assembling a rope bridge. This is part of a body of research in aerial construction, a field that addresses the construction of structures with the aid of flying machines. In this work, a rope bridge that can support the crossing of a person is built by quadrocopters, showing for the ﬁrst time that small ﬂying machines are capable of autonomously realizing load-bearing structures at full-scale and proceeding a step further towards real-world scenarios. Except for the required anchor points at both ends of the structure, the bridge consists exclusively of tensile elements and its connections and links are entirely realized by ﬂying machines. Spanning 7.4 m between two scaffolding structures, the bridge consists of nine rope segments for a total rope length of about 120 m and is composed of different elements, such as knots, links, and braids. The rope used for these experiments is made out of Dyneema, a material with a low weight-to-strength ratio and thus suitable for aerial construction. Of little weight (7 g per meter), a 4 mm diameter rope can sustain 1300 kg.

More Here

[Hat-Tip - samim]

Another nice graph that’s going in my diss writeup!

This shows the time spent on various parts of the target tracking program per frame of video given to it.

The values are in fractions-of-a-second, so to get frames-per-second you divide the values by 1.

1 / (approximate average of) 0.02 = ~50 frames per second, in this example.

Good news here -- MY part of the code (”detect”) is blazingly fast. The things which take the most time are the actual video capture itself, and displaying it on the screen at the end.

Running the code in ‘headless’ mode (no GUI) nets me around 150fps on my laptop!

The “preprocess” step could maybe be optimized -- this is where we flip the image if needed and convert it to the YUV colour space. All of our videos and live webcam input are stored (before compression) in the YUV 4:2:0 or YUV 4:2:2 pixel format -- meaning for every pixel it uses 4 bits for the luminance (brightness) and 2 bits for the two chroma channels. So, if we could get the images in raw YUV, rather than RGB, we don’t need to convert to greyscale or anything -- the pixel brightnesses will be every 3rd element in the image’s array.

OpenCV only wants to give us RGB (well, BGR) images though.

The capture stuff takes the longest as it’s a blocking operation where we ask the webcam (or ffmpeg library for reading videos from files) to prepare a frame, it thinks about it, uploads it via USB or similar to the computer, where it is then decoded -- and goes through the Video4Linux driver where it converts it to RGB, then OpenCV’s VideoCapture class, where it’s copied into memory for us.

We could shorten that loads by writing code that’s closer to the Pi’s camera (less levels of abstraction); using, instead of OpenCV’s library, Broadcom’s Multi-Media Abstraction Layer to get YUV420 frames from the camera.

Also, in the real world, the “render” and “output” stages will not be running, if we’re running it live on the Pi and using it to steer Smokey to a target. Reducing the time-spent-per-frame by about half:

Have yet to profile the code like this on the Pi. Will have to do that soon, before I get to the “analysis” section of my report ;)

Have you seen the Navio+ HAT for RasPi and RasPi2? It might make it easier and better for you. They have educational discounts of something like 30% and might even give you more as this is a very interesting project 😊

I have! It does look pretty cool! Next time I build a quad I think I might try and get one of those boards. I hope there's some flight control software that already exists that can make cool use of the pi's much faster processors and lots more memory.

Another project with the same goals as mine, from last year! Apparently it was successful at autonomous landing albeit a little slow at doing so. Looks like they never uploaded source code either, which is a shame -- interesting to see that their landing markers make use of colour; would like to see how accurate they are.

Wildly Oscillating PID Controllers Trapped In Trees

This week I made a breakthrough with the real, autonomous flight part of this project! I finally fixed the bug in my python multiwii communication library that was stopping me from sending proper control commands.

With that fixed, I can now inject RC pitch/yaw/roll/throttle channel data directly into the controller from the Pi via its’ USB link. As long as I update that data a few times a second (the specification says only once per second, but I had to send around 10 for it to be stable), my own crafted RC data overrides the RC channels received from my radio controller.

This is awesome, because I can arm the ‘copter and give it stick commands directly from code, and then enable the auto-level and GPS-hold modes whilst in-air.

It is also scary, because while my code is sending commands, I have no way of overriding them with my manual controller..! So if something goes wrong and it gets stuck on maximum throttle, I have to just hope that I can ctrl+c the code while I’m still logged into the Pi, or that the Pi crashes. I could probably do with a better failsafe -- maybe some kind of extra radio Tx/Rx pair that cuts the connection to the Pi when the signal is lost.

Anyway, on Monday I integrated my QuadTarget program with the flight controller controlling code. The multiwiid server takes control of the serial connection between flight controller and Pi, and my code connects to it via UDP sockets. This allows the normal MultiWiiConf GUI to send/receive data from the flight controller whilst I’m sending it commands -- great for debugging. The track_targets script creates a separate thread which continuously sends RC input data to the flight controller ever 100 milliseconds. The main thread of that script calls the QuadTarget binary and parses it’s standard output -- JSON-formatted data about any detected target and the pitch/roll/yaw/throttle values it wants to give.

The code ran, and the ‘copter successfully took off and steered itself, but some strange nuance of standard UNIX input/output buffering meant that despite QuadTarget was reportedly processing 20 frames of camera input a second, we only got data for roughly one frame per second..! And subsequently the quadcopter drifted off into a tree because it was acting on really, really old data.

Luckily that tree saved Smokey from flying into a river, and I retrieved ‘copter safe and sound!

With that lesson learned, I decided it was time to turn to simulation to work out all the bugs in my control code. I took the excellent PyQuadSim, an environment inside of the V-Rep robotics simulator, and added some extra Lua scripts to act as a TCP server and serve the RGB image data from the simulated bottom camera when a client asks for it. It’s a really really janky solution, but I was limited in terms of time. Now QuadTarget can track targets rendered inside of V-Rep! It runs slower than the Pi (under 10fps) because of the networking overhead, but it’s at least something.

The simulated quadcopter is given enough throttle to take off to start with, and then decreases throttle gradually until it lands somewhere again. QuadTarget sends the pitch/yaw demands to try and get it to keep the landing target centered in its vision.

I modified the environment a little, adding some extra textures to the landscape. This has turned it into a reasonably challenging environment to test both the vision and control code in, as there’s lots of potential “false target” textures.

What I discovered was that it tends to lag behind in its actions and always overshoots the target by quite a lot. It doesn’t help that the simulated ‘copter acts like a frictionless object, rather than gradually stopping when the pitch/yaw are centered. So I decided to try and implement a PID controller to allow it to predict where it should be in the future (derivative term) rather than just acting on past and present data.

I implemented the simplest possible PID algorithm. With gains set very low, it acts similarly to the old code (which just reverted back to center-values over a few frames when there were no targets), but even more sluggishly. It doesn’t take much for it to oscillate wildly or go completely wrong. So lots of tweaking to be done here...

That being said, I think adding this PID loop is the way to go!

I have made some awesome progress this week!

This video was recorded directly on the Raspberry Pi living on Smokey. It’s correctly detecting targets and giving a reasonable approximation of their distance away as well as vaguely correct angles (sometimes the angle is completely wrong, but it’s mostly okay and can at least be used to tell the ‘copter to turn clockwise/anti-clockwise or not). I have it running at a reasonable framerate -- having been testing it on much faster laptops, I forgot that I would be transferring my code to a 900MHz ARM processor. The first time I tested it on the Pi, I was getting a feeble ~3 frames per second. Nearly 20 frames/sec now, at an 800x600 resolution -- not bad! I was aiming for an >10fps framerate.

Things that I have done since last Friday:

Started a new C++ project from scratch, with a better idea of how the system should be designed.

Implemented the finite state machine pattern recognition method mentioned in the previous post (StateMachine class)

Written the loop which uses this to track Markers (TargetFinder::doTargetRecognition), and converts reasonable markers (ones that are square, not too small and not too large, roughly the same size and roughly the right distances apart) into Target objects.

Multi-level thresholding using fixed bins -- thresholding the input image at multiple fixed levels (using 3-5 bins has empirically been pretty good), if marker patterns are detected at *any* of those thresholds, then they’re incorporated into nearby marker objects that are agnostic about thresholds.

Implemented the code that calculates the angle of a target -- this is still pretty much ripped from Neal’s original code (thanks Neal!) as it’s pretty standard trigonometry, finding the shortest angle in an isosceles triangle... but thinking in radians hurts my brain and it does glitch out occasionally, so I need to maybe re-think this part.

Picking the best target -- right now this is simply the biggest target, but when there are lots of false detections, the real target in the image may be a smaller one. I think I may need to get altitude from the flight controller, which would allow me to get an approximation of how big the real target should be given the ‘copter’s current distance from the ground.

Calculating the real distance -- knowing the focal length and sensor size of the Pi camera, the real size of the target, the image dimensions and the target dimensions both in pixels, the CameraModel class calculates how far away it thinks a target is. This is fairly accurate, having tested it (In the video, I was holding the ‘copter between 1 and 2 metres off the floor).

Persistent tracking of a known target between frames -- this is handled by the PersistentTarget class. The tracked targets tend to flicker in and out of existence due to camera motion, and can vary wildly in size when the camera exposure changes. The PersistentTarget is one that has a finite lifetime and “dies” if its’ information is not updated within a given timeout period (currently, 1 second). It gets updated with the information from the best detected target (if there is one) every frame, with a smoothing factor applied, so that falsely detected targets have less of an influence than correctly detected targets. When false detections occur, they tend to flicker all over the image and only last for one or two frames. The next thing to try is implement a similarity heuristic so the target is only updated by detected targets when they are acceptably similar in shape and angle, otherwise it dies. The one concern here is what if a falsely-detected target is persistent.

Determining flight controller stick commands based on the targets position in the image -- this is done by the Navigator class. This is shown by the green dots in the video. Again, this is updated by the persistent targets’ position and angle. If one isn’t detected, the controller’s pitch, roll and yaw (or rather, vertical, horizontal and rotation) values smoothly reset to centre values. The next step would be to implement this as a PID controller that takes into account framerate, barometer altitude and calculated distance of the target -- so that it’s more gentle on the pitch/roll commands when it’s high up in the air, and it won’t oscillate when trying to keep the target centred. Yaw commands are a little simpler, but need a similar PID controller that stops it from continuously reversing direction when the angle calculations go a little haywire (ie. reversing direction by 180 degrees every few frames).

When I first tested the code on the Pi, it was slooow. I ran my program through cachegrind, which showed me that most of the processing time was spent inside the StateMachine::step function. That was to be expected -- it’s called for every pixel in a row, plus some more when a target pattern is detected horizontally. So I simplified the code a little (converted all double-precision floats to single-precision ones, replaced with integers where possible), but that didn’t provide much of a performance boost. This code can behave massively differently on different CPU architectures! The Pi 2 has an armv7 CPU. Previously I was compiling for my Intel 64-bit laptops, which have loads of hardware optimizations for floating point calculations and vectorization. So does that ARM chip - VFP and NEON are both features of the CPU that can accelerate integer and floating point calculations. Despite the Arch Linux version running on my Pi being the “hard-float” variant, it wasn’t compiling my code with these optimizations by default. I had to tell the compiler to use VFP and NEON when compiling on Pi. That did speed stuff up a little over 2x - framerates going from 2-3fps to 8-10fps.

Possibly I could squeeze out some better performance with more compiler optimizations, but the root of the problem is still that StateMachine::step function. I added a row_step parameter -- allowing the target detector to skip every N rows (currently it only looks at every 4 rows) got me to just over 20fps with no appreciable loss in marker detection accuracy. Cool!

Annoyingly, I can’t get a particularly high camera resolution using the v4l2 Pi-Cam driver. I would like to get full 1080p, as I did some calculations and at that resolution I could track targets from almost 20 metres in the air. Right now I seem to be limited to 800x600 at most -- asking for a higher resolution and my program just sits there with 100% CPU usage but hanging, waiting on nonexistent video input... If I had time I would maybe get frames directly, without going through the extra abstraction of the Video4Linux camera driver. But that’s lots of low-level stuff I don’t have time to try.

So now I’m at that point where I can start working on the fun quadcopter-controlling bits. So here’s the loads of stuff I want to do next:

Work out how to reduce the false markers detected! In video frames with high variance, there are a lot of false markers because the noise creates a lot of potentially valid patterns. Looking at a running average and variance and using that to determine the distribution of the threshold bins may help here.

Fix Smokey! My last flight resulted in a bit of a warped frame and two of the motors have been knocked out of alignmment. Needs some expanding foam or something to fill in the holes where EPP foam has been ripped out.

Fix my code for commanding my flight controller. Currently I can request data from my MultiWii controller, but it seems to ignore controller commands. I think my checksums are wrong or something. So I think writing a c++ library I can use in my vision code but also from Python would be good.

Write a high-level flight controller based on different “behaviours” -- it should be able to program GPS waypoints on the MultiWii controller, and detect when it’s reached the last one -- assuming the last one is a landing target, it should then be able to switch to “precision land” mode which will tighten up the PIDs, switch on the vision processing stuff and put it into accelerometer/barometer/altitude hold mode. Then it can use the joystick commands generated by the Navigator class to gently guide the ‘copter over the target and slowly reduce the altitude until the last recorded distance is 1 meter or less.

Figuring out whether it really is safe to land at this point (ie. reduce the throttle to its minimum and then completely switch off the motors after a short period / disarm the ‘copter) is something that needs figuring out. To start with I think it should just stop sending the FC commands, allowing me to resume control manually with a radio controller.

Tweak the PIDs on smokey by hand to find values that are good for precision landing (and tighten them up generally as currently she drifts all over the place in the gentlest of breezes). I also need to test out the GPS waypointing.

(Bearing in mind I now have 3 weeks left to do all this!)

This week I have been busy driving everywhere, preparing for and subsequently going for a job interview at the National Oceanographic Center... exciting! Now that’s out of the way, I spent this Friday sinking my teeth into my diss again.

I realized at the start of the week that thinking of the pattern-recognition code inside my target tracker as a Finite State Machine might help me untangle the messy boolean logic used to determine whether a pattern of pixels is a valid horizontal line in a marker.

The valid pattern can be considered as seven distinct states:

Before the marker: Either an area of white pixels, or the start of a row.

Start of the marker: The first black pixels.

Left-hand white area before the central circle

The central black circle

Right-hand white area

Right-hand black area

Outside the marker, or the end of a row.

A valid pattern must transition through all of these states one at a time, in that order. If the machine successfully gets to the last state, it spits out a Marker object which contains the position of the start and end pixels, the row of the image it was found in, and various pixel counts. After that, it returns to state 1.

If the state machine doesn’t make it to state 7, it also resets to state 1. This happens when the transition rules for moving from one state to another are not met. For instance, to move from state 3 (left white side) to state 4 (central black region), the pixel count for state 3 must be approximately the same as the count for state 2 -- so the black and white patterns are roughly the same.

The video above shows the machine working on a pixel-by-pixel basis, starting from the simplest possible image and working on increasingly difficult images. Given reasonable input, this now works - it finds targets in white areas of images pretty well. Badly thresholded images such as the last two images will create either no targets or many many false positives. Garbage in, garbage out. This shows how important thresholding is.

This is me starting from scratch; but the algorithm is working and will have much less overhead than the Java version once I’ve implemented it in C++. Today I implemented it in Python and it is very very slow (I am displaying the algorithm progress on screen every pixels and recording it to a video, though).

I’m pretty happy with this way I’ve come up of debugging it; looking literally at how the algorithm works on a pixel by pixel, step-by-step level. I’m definitely a fan of visual intuition.

The algorithm now only has one parameter for empirical tweaking; tolerance. This is how much the ratio of black-to-white within a marker is allowed to differ for a marker to still be valid. Values of 0.7 seem to work pretty well on natural imagery that has been thresholded well, such as webcam imagery. This is a parameter that could be automatically adjusted in real-time; supervisor has suggested “opening up” any parameters to begin with and making the tolerances more strict to reduce false-positives up until we stop detecting full targets.

Goal of the algorithm should be to, over time, increase tolerance to near 0.1 until there are 3-6 markers detected. Any less and tolerance should be decreased a little, any more and it should be increased again. We’re only expecting 3 markers for a target, but a really good input image will also have the smaller target detected, meaning a total of 6 markers.

Interestingly enough -- the original Java implementation “refined targets vertically” by scanning a whole bunch of columns, which makes sense - to get the true height you need to . Turns out on my test images it actually works better if only the central column of the marker is scanned vertically. You still get targets that are an accurate height.

This is the mean and standard deviation pixel intensities for all of my markers (normalized, each of them autocropped and scaled to 512x512).

Another nice visual way of analyzing them, I feel.

The colour map used is cold -> hot, so cold values are lower. Interesting to note that the standard deviation of the white areas is lower than for the black areas. I think that’s because white paper can be quite a “glary” surface, so white becomes bright white whereas the black rings on the marker can fluctuate a lot more in their darkness.

The two plots underneath are for randomly-sampled background areas of the sample images -- no such pattern discovered.

Bit more analysis of the markers (and not-markers).

Hypothesis: the mean and median ‘pixel intensity delta’ values would have an identifiable trend that followed the visual peaks and dips seen in the original chart, for all of the markers. This turned out to be wrong -- the second graph there shows no identifiable trend. Hmmm.

Second hypothesis: The pattern of peaks and troughs in the original graph, plotted on just marker pixel intensities, would not be seen in the backgrounds of the images. The first chart shows this to be true -- lots of noise with no pattern that I can see.

Third hypothesis: Using otsu thresholding on *just* the markers (simulating a “local threshold” on the source images) would yield good results, where the target markers retain their general shape despite variance in illumination, noise and perspective skewing. The metapixel generated above shows the thresholded markers to be pretty consistent. I should probably find out how to get that as a percentage...

nice idea here: field full of sensors, very cheap ones that can't transmit data very far because they don't have the power. send in mobile robots to poll them all for data! the authors suggested using GPS, but if that's not accurate enough -- a good time to do some visual target tracking! :)

Cascade Classifiers

Since I have collected a reasonable database of markers (positive samples) and background images (negative samples), I tried my hand at training a Cascade Classifier yesterday and today. It took several days of training in total. I chose to use Local Binary Patterns for the features as opposed to Haarlets as they are supposedly a few times faster, since they only use integer math.

It kinda works. Cascade classifiers have been used traditionally for face detection with pretty high accuracy. However, to get a good classifier that can cope with all the variations in lighting, noise, backgrounds etc. -- you need a lot of training examples -- plenty of positive ones, but also loads of negative ones, so you don’t have too many false positives. Then you have to find a balance between the two so you don’t end up with too few true positives.

This works pretty well with targets at a specific distance/size, as seen in this video:

Annoyingly, no matter what scale markers I train the classifier with, it refuses to detect them under a certain size. That size happens to be above the size that most of the targets in my flight videos are -- so the point at which tracking the targets would be most useful (above the target, but still fairly high up in the air), it doesn’t detect them at all! This also prevents us from being able to scale down the images to make it process faster.

There are also false positives occasionally; it likes to detect anything circular as a target, including the shadows of quadcopter. It really likes detecting close-up images of grass as dozens of targets.

It’s also prohibitively long in training and requires lots of carefully curated training data. And whilst I’m getting a good 30/40 frames per second with my laptop’s webcam (the webcam being the limiting factor here rather than classifier performance), I am testing this on a 3.3GHz 8-thread intel CPU, not the tiny 1GHz ARM chip on the Pi. Running on 720p mp4 videos it drops down to ~20fps -- the videos were recorded at 49fps, so that’s just under half-real-time.

So the cascade classifier experiment was a brief success, but not really feasible for this project.

It’s nice to have a tracker that *will* track targets some of the time though -- as a baseline for the control system, should I not get anything better working by end of diss!

Hurray! Graph!

Now I have a huge database of video framegrabs annotated with where the markers are, I was able to do a little full-dataset analysis.

The graph above plots the difference in Y values (Y as in the luminance channel of the YUV colour space) for every marker in every image. Which at this point is over 1,500 markers. The values are also smoothed a little using exponential mean smoothing again with an alpha value of 0.5, and every marker has been normalized to be a width of 128 pixels. Values are taken from the central row of the image (height divided by 2), so this graph shows the horizontal cross section of every marker in the dataset.

I expected there to be a lot of noise, as the markers vary hugely. What is pleasing to see is that there is a visible profile of what a marker looks like within the chart! The peaks and dips correspond to where the black and white areas are. These are fairly pronounced, standing out from the noise, so I think there’s a fair chance that some simple local histogram-based thresholding might help the original algorithm.

I’m also training a Local Binary Pattern Cascade Classifier with all my markers, it’s on stage 12 of 20, having been running overnight. If it produces a classifier that actually works, that’ll be the next blog post I think...

More flying

Yesterday was another nice and sunny day so I took Smokey out for another flight. Since the last flight I’ve attached a wide angle lens to the downwards-facing camera. This makes it easier to see the targets as the ‘copter gets closer to the ground, but it does add some more perspective distortion as well as some more glare, due to there being another sheet of glass between the camera and the outside world.

This flight I definitely got the highest I’ve been so far!

Which resulted in some nice photos of Aber from above...

The last crash took a chunk out of one propeller, got scratches all over my laptop screen and had one of the nuts keeping the props on go flying off into the ether, so I only got a 5 minute flight. It was pretty windy, so it was really hard trying to fly around the landing target.

I also spent today making a program for annotating the markers of targets within images. Using vlc to watch all my previous recordings, I paused on good frames and took framegrabs of the targets. This netted me several hundred images of targets, plus a few dozen more without any targets in them.

Annotating the images by hand using my script, I have over 1,100 individual markers. There’s a little bit of human error here, dragging rectangles over hundreds of images is not going to be perfect. I wrote another script to extract the markers from the images and automatically crop them where possible, cutting out any extra white-space around the targets. That was pretty easy to do using just Otsu thresholding, which it turns out works pretty awesomely when just the targets are being thresholded!

The appearance of the markers varies hugely, in colour and shape and contrast and sharpness. I did a nice mosaic of a representative sample of the extracted targets using metapixel. This was a pretty intuitive way of analyzing the target marker variance. I will go over them and make some proper graphs and get some empirical data next though.

But for now, more pretty pictures!

If it’s a quick evening’s hacking, I might try and train a Haar or Local Binary Pattern Cascade Classifier and see how good/fast it is. I reckon it’s going to be far too expensive to run on the Pi, but it’d be interesting to try a model-based approach.

Today I’ve been extracting pictures of targets from all of the recorded videos so far. I’ve tried to keep a representative sample -- targets are seen at all angles, in both indoors and outdoors lighting conditions, from a number of heights. Some are obscured or go off the image, some are perfectly centered, most are a balance between.

What I’ve noticed it that there is a huge amount of variation -- even just a few milliseconds later the target looks vastly different, due to the camera’s own exposure compensation, or the effects of motion blur, or reflective properties of the paper that the targets are printed on. Shadows create problems, as does general noise. In some images the targets have a “halo” around them, which makes detecting the (real) edges more difficult!

Next thing to do is get a whole bunch of data on it! Histograms and the like. Let’s see if the target markers make an identifiable pattern in the image histogram / horizontal plots of the pixel intensities, and whether there’s any other cues we can use, like less variations in colour over the target surface.

Fork of http://sourceforge.net/projects/mjpg-streamer/

I want to replace Smokey’s front-facing camera with a USB webcam. That way I could use it as a First-Person View (FPV) camera connected to the Pi, and I could also get better synchronized video (front cam synchronized with bottom cam) if I didn’t have to manually start recording on the cyclops camera I’m currently using. mjpg-streamer looks like it can simultaneously stream MJPEG-encoded video to file as well as over UDP, and since it was designed for use on low-powered embedded devices should run quite nicely on the Pi.

Recording as MJPEG format may also be a better solution for recording video from the bottom camera -- despite taking up more space and bandwidth, there will be less compression artifacts than with H.264 and the ability to decode any frame will be useful for capturing stills from the video stream, making it more like a simulated live feed, which is what I wanted.

Vision algorithms

I’ve been studiously working hard on the target tracking code side of things this week, as well as looking in more detail at the videos I recorded in my previous flights.

Almost got the original algorithm to run correctly, but I’m stuck on some weird bug that stops it from expanding targets vertically after it’s found them horizontally. So, having spent a whole day trying different things to try and fix it to no avail, I started from scratch, rewriting my own version of the algorithm.

I have taken the central idea of the original algorithm -- looking at ratios of black to white pixels horizontally across an image, then refining vertically. Where mine differs is the pre-processing -- the original version needed binary thresholding so it would only get a version of the image with either white or black pixels, which made it a lot simpler to count the white/black regions.

However, this was far from optimal -- I could either try and empirically find a reasonable threshold that works across different environments, or use Otsu’s thresholding, or an adaptive method. Otsu’s method worked well for webcam input, but it turns out that the actual targets in the image were more washed out than the surrounding field, so all we got was a white patch with no visible markers!

The input image makes it look as though the grass doesn’t vary much in brightness, and the bright surface of the target and the dark patches of the target itself should stand out nicely from the background. Applying Otsu’s thresholding tells a much different story however! Thresholding based on the histogram of individual frames obviously doesn’t work on these types of natural images.

This kind of image also makes the original algorithm run very slowly, due to getting clogged up with all the potential areas it’s detected the start of markers in (the red and blue patches in the second image), which it begins to refine before ultimately rejecting them for not being target-like.

However, it should still be possible to detect the edges of these targets, regardless of how much or little contrast there is in the image. Here’s a plot of the pixel intensities of the corner of a target within a video frame. You can see how the target itself has a pretty noticeable change in intensity, which also varies a lot less than the pixel values surrounding it.

By getting the current pixel value subtracted from an exponential moving average (smoothed by an alpha value) of the previous pixels in the row, we get a delta value which can be used to detect the rising and falling edges of brightness values in that row of the image. Simple edge detection and image smoothing combined in one step!

Delta values greater than a given threshold (to be determined manually for now) are considered the start of a change in state -- positive deltas mean we’re going into an area of white pixels, negative deltas mean the pixels have become quite a lot darker, and therefore we’re going into an area of black pixels.

Keeping track of where these dark/light areas are, we can then look for the very specific light/dark patterns that the targets have, and we only need to do some boolean logic and do some simple pixel counting:

So I’ve implemented that so far. It runs quicker than the original algorithm. There’s no thresholding step needed beforehand, which means the algorithm can take a colour image in the YUV colourspace, which is what camera and video frames are sent by as default. No conversion to RGB and further conversion to greyscale and further thresholding needed, meaning we cut out three O(n) loops already.

Trying to keep all the math in integers or floats (instead of doubles) wherever possible to keep it fast, as well.

How does it work, so far?:

Not very well. It’s almost finding the targets -- denoted by the rainbow colours. I have some problem with the boolean logic part of it however, hence why the tops and bottoms of targets stay red, bits are completely the wrong pattern, and the white region of the image is grey (indicating no change).

Detecting the edges was easy, detecting whether they were rising or falling was also easy (just check whether the delta value is positive or negative) -- but then checking whether we’re in a region of white or black *after* a sudden change, I seem to be getting the logic wrong.

For comparison, here’s the original algorithm, almost-working (different colour scheme here, but the colour parts of the right hand image nonetheless show it correctly identifying the horizontal bits, just not the verticals).

Otsu thresholding works well on the webcam images, probably because I am always sticking the target right in front of them on a bright phone screen, and therefore they are of high contrast. However, that not-finding-the-tops-and-bottoms of targets problem still persists, so the original algorithm never actually finds any targets!

I am still optimistic that I’ll find a magic solution by combining my code with the original code. At least mine is fast in its nonfunctioning way -- asking my laptop to run at 800MHz speed, my algorithm still doesn’t hit 10% CPU usage, and is still processing webcam frames as fast as the camera will let! Which bodes well for running it on the Pi.

On another positive note, looking at my last flight video, I seem to have mostly solved the frame-skipping-whilst-recording problem. Still get occasional dropouts, but now the extra timing info means [most, sane video decoders] interpolate the missing frames instead of outright skipping them, and the video stays the right time.

pyMultiWii - Handles the MultiWii Serial Protocol to send and receive data from boards.

Oh maan! I also found a multiwii serial parsing library for Python that’s better than my own. For reading data they should be functionally equivalent but this looks like it can successfully send commands with payloads too, which I’ve had trouble with. Arming and disarming quadcopters from code, brave!

Trending Blogs

Recently Viewed Blogs

Smokey the Quadcopter