Monthly Archives: October 2010

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)