Change of plan – from Scilab to Octave

OK, I started out on Scilab, but got frustrated! It’s too different to Matlab – which has its flaws, but at least I’m familiar with them. I’m always going to be annoyed by the 1-based indexing of Matlab, but I’ve learned to deal with it.

I’ve been using Matlab for the last 15 years at work, the syntax is built into my fingers. Using // for comments (the Scilab notation) felt bizarre! This despite me being a proficient C++ programmer who uses double-slash comments all the time – it’s just wrong in (what my mind was telling me was still) a Matlab script.

So I’ve turned to Octave for my home-based image-processing work. Octave was aimed at being more of a Matlab-clone from the start, whereas Scilab was designed as an open-source competitor, but doing things in its own way. Familiarity is a powerful motivator when tool selection is concerned!

Will this reduce the spam?

Thanks to Ignacio Segura I have a new anti-spambot measure. Users won’t notice it (unless they browse with CSS turned off, or other such unusualness). Hopefully this will mean that a) I don’t have to “disapprove” loads of comment span every day, and b) I can allow anonymous commenting without having to approve it before it becomes visible.

If this doesn’t work, then maybe I’ll use one of the more formally defined modules like Spamicide or Hidden CAPTCHA, although they seem to do much the same!

We’ll see….

Image processing #001a

Ioannis mentioned another edge detector he’s fond of using – so here’s a comparison.

To summarise, his method involves shifting the image 1 pixel to the right, and subtracting it from the original image. And then doing the same but shifting one pixel down instead.

This is equivalent to convolving with

[1 -1]

rather than

[1  0 -1]
[2  0 -2]
[1  0 -1]  

There’s two differences that are worth commenting on:

* Being an even length kernel means that the output is shifted by a half pixel, so the output has a peak which lines up slightly to one side of the edge transition.
* Being so small, the kernel has no noise-reducing properties. The Sobel kernel takes more pixels into it, performing some low-pass filtering, which reduces the noise response. This is of no matter if the image is already pre-low-pass-filtered before edge-detection.

To demonstrate this effect, here’s some samples. I’ve added some (alright, quite a lot of) Gaussian noise to the original image using ImageMagick:

`convert testkb.pgm -evaluate gaussian-noise 15 testkb_noisy.pgm`

[img_assist|nid=49|title=KB Noisy|desc=|link=none|align=none|width=640]

[img_assist|nid=51|title=testkb noisy sobel|desc=|link=none|align=none|width=640]

[img_assist|nid=52|title=testkb noisy simple|desc=|link=none|align=none|width=640]

The Sobel filter performs much better on noisy images. But there’s 6 additions and 2 shifts per pixel (and per dimension), and their corresponding memory/register reads+writes, compared to only 2 for the simple one. On the other hand, a Gaussian filter tends to be 5×5 at least, which means 25 full-multiplies (not simple shifts) and adds. So unless there’s a need for the Gaussian pre-filter, the Sobel wins performance-wise…

Next stop, detecting corners…

Image processing #001

Image processing

[img_assist|nid=42|align=right|width=128]

This is the first in a group of posts, during which I’m going to work through the development of an image processing system. I’m going to start at a very high level working with some classic image processing techniques. The plan as I write this is to work down to a complete implemenation on an FPGA. In the process I’m going to demonstrate how to link the high-level descriptions to check the performance of the low-level FPGA code. This is all based on things I’ve learned over 10 years of developing this sort of code in a real production environment. However, it’s all based on standard image-processing literature, so I shan’t be giving away any trade secrets!

First steps

Image processing is one of the most processing intensive applications around at the moment. A VGA webcam throws out 10 million pixels per second. If each of those pixels needs a few dozen operations applying to it, that’s a few hundred million operations per second (MOPS) required. Easy for a PC to manage, but embedded systems with a power budget of a couple of watts can’t use even an Atom processor (with its associated chipset). Another feature of image-processing is that it is often (at the lowest level) very parallelisable. The same thing happens to each pixel, and there’s no dependence from one pixel to the next. Lots of easy parallelism suits an FPGA implementation ideally.

Edges

The first stage of most image-processing systems is to reduce the data rate to something more manageable for a conventional microprocessor to pick up. Often the best way to do this is to extract the edges in the image – similar to what the human vision system does. A very simple edge detector is the Sobel detector – this involves applying a two simple sums to each pixel in the image, one to extract the horizontal components of edges and one for the vertical components. Diagonal lines will respond to both direction filters. The sums can be described in terms of the 8 pixels in a square around the target pixel – this means we can’t calculate the edge response in a single-pixel border around the image.

Doing the maths

The sum performed is to take the gray-scale pixel values that represent each of the outlying pixels and sum them thus:

h=top_left+2*top_middle+top_right-(bottom_left+2*bottom_middle+bottom_right)
v=top_left+2*middle_left+bottom_left-(top_right+2*middlle_right+bottom_right)

The total “edge magnitude” can be calculated by summing the squares of the horizontal and vertical responses:

e=v^2+h^2

Convolution

This is technically known as a convolution – a “mask” is used to define the sums:

 1  2  1
 0  0  0
-1 -2 -1

This is the horizontal edge detector described above. If you use those numbers in a matrix (which is what Scilab does), the vertical edge detector can be obtained by transposing the horizontal matrix.

Find some edges

Here’s a test image:

[img_assist|nid=45|title=Test image|link=popup|align=none|width=640|height=490]

The Scilab code to generate edge images is very simple:

cd websrc/Corners/code/scilab 
hs=[1 2 1; 0 0 0 ; -1 -2 -1]; // Mask for horizontal lines 
vs=hs'; // Vertical lines is just the transpose 
img=imread('../testkb.pgm'); // read the image 
v=filter2(vs, img); // Apply the filters 
h=filter2(hs, img); 
e=h.^2+v.^2; // Sum the squares to combine them 

The imshow command can be used to see the images v, h, and e. I used the imsave command to save them for the web. These are the vertical and horizontal responses:

[img_assist|nid=43|title=Edges|desc=Horizontal|link=popup|align=none|width=640|height=490]

[img_assist|nid=44|title=Edges|desc=Vertical|link=popup|align=none|width=640|height=490]
And the combined edge response:

[img_assist|nid=42|title=Edges|desc=Combined|link=popup|align=none|width=640|height=490]
Still a very recognisable image I think you’ll agree – this is the first stage in many image processing systems. Onwards to detecting corners next…

Code

All the code from this series is available via git from here

FPGA Q&A area on stack exchange

For those who don’t know Stack Overflow, I recommend having a look round. Web Forums (Fora?) done right. A sensible and easy way of rating questions and answers and questioners and answerers. For the right subjects, a goodly group of knowledgeable people answering them… But mainly on a software theme. Sadly (for me :) FPGAs and HDLs only come up occasionally (but I try and answer when I can). Enter Stack Exchange:

The best place (IMHO) for FPGA advice currently is Usenet. comp.arch.fpga and comp.lang.vhdl have a group of experts who are happy to help with well-asked questions. But the signal:noise ratio is dropping of late. My guess is that this is because new users tend to go for web forums which tend to be single vendor and don’t have the variety of experts that the newsgroups do. And, for some reason, they seem to attract poorly phrased questions.

Stackoverflow and its sister Stack Exchange are designed for the web forum generation, and do it well.

There’s a group up for creation on stack exchange related to FPGAs, but it needs a bunch more people to express interest before it can come into existence. I’d like to see it flourish, and if it comes to reality, I’ll be checking the questions regularly, and maybe posting a few of my own.

(Mind, I’ll always hang out on comp.arch.fpga as well though)

FPGAs and floating point

Altera’s newest DSP block is quite clearly designed to deal with double-precision floating-point numbers from the start. They are betting (quite rightly IMHO) that the future is going to move away from pure fixed-point implementations.

Now, floating-point is not a magic wand that will cure all your arithmetic problems. But it will make the implementation of a large variety of signal processing algorithms much more straightforward. Which means products can get to market faster. Which means more iterations. And faster iterations are good – you get to learn more about your product.

Xilinx don’t appear to have an answer for this. Which typifies the difference between the two companies. Altera have always been much more of the “push-button flow” kind of people. Xilinx expect you to get bit deeper and hack a bit more at the “bit-level” (only figuratively, but still lower level than Altera). Yes, they’ve stuck pretty GUIs on top of their tools, but underneath it all, you can tell its a real hackers environment. And that suits the fixed-point types well – they can demonstrate a bit-accurate line from their simulations right through to the device. And they’ll spend days and weeks tweaking their coefficients for optimum size and speed in their filters.

My feeling is that over the next couple of years, those that ignore the potential of floating-point may get left behind.

It’s happened in a large amount of the embedded world – when I started “real work”, fresh from university, my colleagues couldn’t envisage a day when floating-point would be a sensible for volume production items. The silicon area was too enormous. But along came IEEE754 (which for all its flaws, made it worth-while for companies to develop silicon IP to a standard) and Moore’s “law” push relentlessly on. A high-end embedded processor which can be had for under $5 has many kB of RAM, 1 or 2 MB of flash memory, which is about 80% of the die. And a processor core and a bag of peripherals for the rest. The FPU hardly figures in the die size!

Altera have it right – they’re going to open up a bunch of currently non-existent markets to the option of using FPGAs. Us “fixies” are going to have to keep up…

Make your own Drawdio without soldering

If you want to make your own Drawdio without doing any soldering, read on…

Circuit

This post will describe how to make a Drawdio like the one I made.

What you’ll need

Components:

Tools:

  • screwdriver for the terminal block
  • wire cutters/strippers. You can get away with scissors if you’re careful :)
  • paper

Making It

Start off cutting your terminal block to 2 rows of 8 screws. Bend the legs of your transistors like this and screw them into the bottom row of your terminal block. The BC558 goes on the left with the flat side uppermost. The BC548 goes on the right with the rounded side uppermost:

transistors

On the top row:

  • The red wire from the battery holder goes to the left-most screw (number 1)
  • The black wire from the battery holder goes to the right-most screw (number 6)
  • 10k resistor between the 3rd and 4th screws
  • the piezo sounder also goes between 3 and 4
  • 2n2 capacitor between 2 and 4
  • 2n2 capacitor between 3 and 5 It’s a bit of a fiddle getting more than one wire in the screw holes, but persevere – it’s doable!

Finally, to prepare the pencil – take two lengths of wire. One length goes from screw 5, the other end you need to wrap around a drawing pin and push into the pencil at the top. The other length you need to strip a longer length of insulation off (about 5 cm), wrap around the pencil where you hold it, and then cover it with aluminium foil to make a good contact for your hand. The other end of this piece of wire goes to screw 2.

Pencil with wire Pencil complete

Right, it’s done – put the batteries in, hold them pencil and touch the lead to your other hand. You should be rewarded with a squeaky noise :) Draw a blob on the paper, stick your finger on it and then draw lines radiating out from it. Get someone else to hold hands and then they can do the drawing. The possibilities are endless – have fun!