Hate UML?

Draw sequence diagrams in seconds.
http://www.websequencediagrams.com

Exploiting perceptual colour difference for edge detection
Posted on: 2009-04-16 19:42:41

I once took computer vision class. Every algorithm we learned was done on grayscale images, as if it were 1950 and we couldn't afford those new fangled colour VDTs. I put up my hand and asked why we discard all of this lovely colour information. The prof answered that some people have tried it, but it doesn't give much benefit.

But in some situations, colour can be important. Here's an image in GIMP:

Green circle on red square

First, we convert to grayscale:

completely gray square

Umm......... I don't think we need to go any further here. 'Nuf said.

Traditional approaches for colour

Computer vision researchers use two approaches for dealing with colour. The first is to break the image into red, green, and blue images, do the algorithm three times, and combine the results. The second is to treat the RGB values as a vector and subtract the vectors to determine colour difference. These approaches can work, but they don't take into account human perception of colour.

The RGB values in an image have very little to do with how the human eye works. They have more to do with the voltage fired at phosphors in an 80's era CRT display than human vision. (Let's conveniently ignore the fact that LCDs have completely different properties. Everybody else does.)

To compare two colours, you have to first convert them to a different colour space. If you find yourself subtracting RGB values, you're doing it wrong.

Colour Difference

CIE Luv Colour SpacePeople can distinguish skin colours very well, so we can tell if a potential mate is healthy or not. This is more important than distinguishing different shades of green leaves, which would be mere distractions from the delicious bouquet of fruits hanging in trees. Describing the exact shade of an azure sky is simply not required for survival. We are hypersensitive to differences in yellows, reds, and oranges.

In 1915, Albert Munsell created a Colour Atlas, a book of colour paint samples. He came up with a way of logically arranging them that made sense to his eye. Each colour was indexed by hue, saturation, and value (also known as lightness). We still use his system today, and most of modern colour theory is based on Munsell's ideas.

The CIE is an international authority in charge of standardizing things to do with light and colour. In 1960 they created a mathematical arrangement of colour, and improved it in 1975. In this space, the more different two colours are, the farther apart they are in the drawing. The arrangement is not perfect, but the math is simple enough to work with. It's no good to create an international standard that nobody understands.

Finding outlines in images

Edge detection is usually the first step in any computer vision algorithm, because it converts an image into a black and white outline that is easier to work with.

  • You can count the vertical and horizontal edges and figure out if a photo is taken in a city or a forest. City buildings are often square.
  • You can treat it as a flat, physical object and figure out the center of gravity and angle of symmetry, and get some numbers that you can compare two images with, even if one is rotated or scaled.
  • You can mark strong intersecting edges as corners, and compare the locations of corners in two images to figure out how to line them up, or if they are the same object.

A nice, easy way to perform edge detection is to use the sobel operator:

Translation: We create two new images, Gx, and Gy. The pixels in the new images get their values from the difference in the values of the pixels around their corresponding position in the old image. In the Gx image, the differences are in the right to left direction. In the Gy image, the differences are in the up and down direction. After the two new images, are created, we combine them into one by adding the pixels together in a special way. We square the values, add them together, and take the square root. The result is the edge-detected image.

I like the sobel algorithm because it is easy to adapt to color difference. Instead of subtracting the pixel gray values, we subtract the two colours using the distance in L*u*v colour space, which is almost perceptually uniform.

Results

I implemented the two algorithms in 400 lines of C code. When the program is run with a given PNG image, it reads it and performs edge detection first on the grayscale version, and then on the colour version using colour differences. In both cases, the images are normalized so that the highest difference is white, and the lowest is black. Here are the results.

Note: The grayscale image appears blurred, and the colour one does not. This is an error in the blog entry and should be corrected later. The implementation blurs both versions before performing edge detection, to reduce noise.

Grayscale original
Traditional Edge Detection
Colour Original
Colour Edge Detection
Grayscale original
Traditional Edge Detection
Colour Original
Colour Edge Detection

Further Reading

Want more programming tech talk?
Add to Circles on Google Plus
Subscribe to posts

Post comment

Real Name:
Your Email (Not displayed):

Text only. No HTML. If you write "http:" your message will be ignored.
Choose an edit password if you want to be able to edit or delete your comment later.
Editing Password (Optional):

Jon Hohle

2009-04-16 21:45:52
In this example, the grayscale versions of both the house and Lena are blurred as well. I don't doubt your technique, but in this case, you are not comparing equivalent operations.

I don't have my grayscale Sobel implementation built, but I don't think it would be considerably different in the two examples provided. You're initial image (circle on flat background) would have been an interesting example of where grayscale edge detectors would fail completely vs. where your algorithm would work.

Neil Dickson

2009-05-04 04:17:29
Actually, I've wondered about looking at what'd happen if one ignored the L component, only using hue and saturation information (like the opposite of going grayscale), since then it might be easier to deal with variations in lighting. It probably wouldn't work out perfectly, of course, since we tend to detect corners and edges on a single object by variations in lighting on it, but lighting issues can be a big problem in doing computer vision with images outside on a sunny day.

zahurul

2009-06-19 06:05:13
I have download the code and compiled as the direction. but I got a file named sobel. And I did not get any edge detected pic.. would you please help me ?? I am wating for ur reply.
Email
steve.hanov@gmail.com

Other posts by Steve

Yes, You Absolutely Might Possibly Need an EIN to Sell Software to the US How Asana Breaks the Rules About Per-Seat Pricing 5 Ways PowToon Made Me Want to Buy Their Software How I run my business selling software to Americans 0, 1, Many, a Zillion Give your Commodore 64 new life with an SD card reader 20 lines of code that will beat A/B testing every time [comic] Appreciation of xkcd comics vs. technical ability VP trees: A data structure for finding stuff fast Why you should go to the Business of Software Conference Next Year Four ways of handling asynchronous operations in node.js Type-checked CoffeeScript with jzbuild Zero load time file formats Finding the top K items in a list efficiently An instant rhyming dictionary for any web site Succinct Data Structures: Cramming 80,000 words into a Javascript file. Throw away the keys: Easy, Minimal Perfect Hashing Why don't web browsers do this? Fun with Colour Difference Compressing dictionaries with a DAWG Fast and Easy Levenshtein distance using a Trie The Curious Complexity of Being Turned On Cross-domain communication the HTML5 way Five essential steps to prepare for your next programming interview Minimal usable Ubuntu with one command Finding awesome developers in programming interviews Compress your JSON with automatic type extraction JZBUILD - An Easy Javascript Build System Pssst! Want to stream your videos to your iPod? "This is stupid. Your program doesn't work," my wife told me The simple and obvious way to walk through a graph Asking users for steps to reproduce bugs, and other dumb ideas Creating portable binaries on Linux Bending over: How to sell your software to large companies Regular Expression Matching can be Ugly and Slow C++: A language for next generation web apps qb.js: An implementation of QBASIC in Javascript Zwibbler: A simple drawing program using Javascript and Canvas You don't need a project/solution to use the VC++ debugger Boring Date (comic) barcamp (comic) How IE <canvas> tag emulation works I didn't know you could mix and match (comic) Sign here (comic) It's a dirty job... (comic) The PenIsland Problem: Text-to-speech for domain names Pitching to VCs #2 (comic) Building a better rhyming dictionary Does Android team with eccentric geeks? (comic) Comment spam defeated at last Pitching to VCs (comic) How QBASIC almost got me killed Blame the extensions (comic) How to run a linux based home web server Microsoft's generosity knows no end for a year (comic) Using the Acer Aspire One as a web server When programmers design web sites (comic) Finding great ideas for your startup Game Theory, Salary Negotiation, and Programmers Coding tips they don't teach you in school When a reporter mangles your elevator pitch Test Driven Development without Tears Drawing Graphs with Physics Free up disk space in Ubuntu Keeping Abreast of Pornographic Research in Computer Science Exploiting perceptual colour difference for edge detection Experiment: Deleting a post from the Internet Is 2009 the year of Linux malware? Email Etiquette How a programmer reads your resume (comic) How wide should you make your web page? Usability Nightmare: Xfce Settings Manager cairo blur image surface Automatically remove wordiness from your writing Why Perforce is more scalable than Git Optimizing Ubuntu to run from a USB key or SD card UMA Questions Answered Make Windows XP look like Ubuntu, with Spinning Cube Effect See sound without drugs Standby Preventer Stock Picking using Python Spoke.com scam Stackoverflow.com Copy a cairo surface to the windows clipboard Simulating freehand drawing with Cairo Free, Raw Stock Data Installing Ubuntu on the Via Artigo Why are all my lines fuzzy in cairo? A simple command line calculator Tool for Creating UML Sequence Diagrams Exploring sound with Wavelets UMA and free long distance UMA's dirty secrets Installing the Latest Debian on an Ancient Laptop Dissecting Adsense HTML/ Javascript/ CSS Pretty Printer Web Comic Aggregator Experiments in making money online How much cash do celebrities make? Draw waveforms and hear them Cell Phones on Airplanes Detecting C++ memory leaks What does your phone number spell? A Rhyming Engine Rules for Effective C++ Cell Phone Secrets