Canny Edge Detection Applied with Java

Download Canny Edge Detector Java Source Code (CannyJava.zip)

Recently I had to implement the Canny edge detection algorithm in my Digital Image Processing class at ETS. I had seen the algorithm in use in some of our vision software for the SONIA Project, but I had never actually looked into the details of it until now.

The implementation of the Canny algorithm provides great insights into every aspect of classical spatial-domain digital image processing. It requires the application of lowpass filtering (gaussian blurring), gradient (first derivative) calculation and several iterative and recursive non-linear algorithms. 

Of course, edge extraction is not a trivial matter and there are no magical answers. There are several degrees of freedom in the parameters of the edge detector that determine which “edges” will be extracted from a given image.

Over the course of my implementation, I found several excellent resources which have helped me understand the algorithm. The two better ones are both from image processing lecture notes:

My initial implementation of the algorithm was done in MATLAB using the Image Processing Toolbox. I used this version of the algorithm to generate two movies showing the steps of the algorithm visually (see bottom of this post for the movies). They were generated by saving frames and creating a batch file with ImageMagick command invokations to add captions. The individual frames were then compiled into movies using VirtualDub.

After doing the MATLAB implementation, I went on to make a Java version to see what it would be like to build it from “scratch”, including a basic image processing library. I did not use a pre-defined image processing library, deciding instead to make a simple Matrix class that implemented all the operations required for image processing.

The Java library (MatrixF.java) implements the following operations over float-typed matrices:

  • Loading/Saving of MATLAB-compatible text-format matrices
  • Elementwise operations between matrices (+, -, kA, k-A, “.*”, “./”)
  • Logical operations between matrices, with or without constants (<=, <, ==, !=, >, >=, &&, ||)
  • Element-wise application of float functions (ie: Math.sin(), Math.exp(), myFloatMethod())
  • Spatial filtering using correlation (equivalent to MATLAB’s filter2() function)

After creating the MatrixF class, I implemented the Canny algorithm, as well as a contour segmentation algorithm using it. The result is in Canny.java.

The Canny algorithm implements the following steps in order:

  1. Gaussian blur with specified sigma value on source image
  2. Gradient magnitude and argument calculation using the Prewitt mask
  3. Gradient argument sectorization (quantization) over the 4 main directions (North/South, East/West, Northeast/Southwest, Northwest/Southeast)
  4. Non-maxima value supression on gradient magnitude (thinning of contours)
  5. Hysteresis thresholding of non-maxima-supressed pixels to extract contours (edge-linking)

Using all Float operations and no in-place processing of matrices, the speed gain is still about 16x between the Java version and the MATLAB version, which is significant 🙂 My version of hysteresis thresholding uses a processing list instead of straight recursion, to maximise efficiency and prevent stack overflows (thanks to Jean-François Im for the tips about that).

The example movies showing all steps of the Canny algorithm on two sample images are shown below. You can access the full resolution AVI files from the vimeo entries.


Fully-detailed Canny Edge Detection Animation on Whiz Burger Sign


Fully-detailed Canny Edge Detection Animation on I-5 Sign in Oregon

If you want to understand the Canny algorithm better, I encourage you to check-out the two references mentionned above and to try implementing the algorithm from scratch. There is a lot to be learned about image processing from this classic algorithm.

Download Canny Edge Detector Java Source Code (CannyJava.zip)

Supply and Demand Applied: Turmeric

I was browsing a Montreal indian market on Victoria Avenue in Côte-des-Neiges, trying to get some turmeric, curry leaves and Toor Dal. We had been out of turmeric for a couple days at home and we had forgotten to get it at the grocery store.

I couldn’t find a small bottle of turmeric in the store, so I asked around and was told the indian name for the spice was “Holdi”. I got back to the spice section and there I saw it. A bag of almost a kilo of turmeric for 3.29$. I reminded myself that I paid around 4$ the last time for a standard McCormick spice bottle at my grocery store and it hit me.

Supply and Demand, those are the words !

Demand profile on Victoria Avenue in Montreal

Victoria Avenue is the most multiethnic street in Montreal. Every possible ethnic group is represented on a 2km stretch between Queen Mary and Jean-Talon West. The store where I got the bulk turmeric caters to the needs of the neighborhood’s diverse population. Demand there is very high for the important spices (turmeric, cumin, curry leaves, green chilis, coriander, mustard seed, etc) used in both Indian and West-Indies cuisine.

Demand profile at IGA in Deux-Montagnes, Quebec

Deux-Montagnes has a 95% caucasian population and is a suburb to Montreal and Laval. The local IGA grocery store caters to people whose knowledge of Indian cuisine is mostly that of restaurants in Montreal (for those who actually know what it is altogether). Turmeric is always plentiful because the stock never goes down. Even curry powder practically never runs out while steak spice mixes and “italian spice” are very popular.

Effect of demand on price

Since the Marché Victoria store is an indian community food hub, demand is very high for all specialized items which are hard to find elsewhere for the local Indian ethnic groups. Prices are driven down because the necessities of daily cooking are an incentive to purchase a lot of these spices regularly.

Conversely, the Deux-Montagnes IGA sells turmeric as an exotic item with associated high price tag because it is seldom purchased. People generally do not know much use for turmeric except for its coloring properties in the few North-American recipes calling for it. As such, it is normal that the price conveys the exotism of the ingredient.

Price comparison

  • Bulk turmeric: 3.29$ (on special) for 0.910kg  = 3.62$ / kg
  • McCormick turmeric: 4.99$ for 0.045kg = 110.88$ / kg

The grocery store spice is 30x more expensive for the same product than the bulk spice bought at the ethnic market. Food for thought.

Conclusion

Next time you don’t know what to do with turmeric, make dal ! It’s a tasty dish of lentils full of protein. Here’s a link to a recipe for yellow dal on the Route 79 blog.

HP4195A interface software for Prologix GPIB/USB Adapter

NOTE: this entry has been superseded by a project page ! Click here for the new location.

Download program here (DL4195A_1.0.zip, Win32 binary + sources)

While I was doing my Analog Filter Design (ELE430) class at Ecole de technologie supérieure, we had to use the Agilent/HP 4195A Network/Spectrum Analyzer in the lab to plot filter frequency responses. One problem I encountered was that the GPIB slave on it was a Centronics (parallel-port printer) adapter connected to a LaserJet printer, which meant we could not directly access the data internal to the instrument. We could only plot it on paper.

To solve this problem and get access to the full 400 points of data memory for each HP4195A channel, I wrote the DL4195A utility (which stands “DownLoad 4195A”). The program requires a Prologix GPIB-USB Controller to connect to the instrument. This GPIB-USB adapter appears as a virtual COM Port and supports all GPIB bus operations. I strongly recommend it. The program is written in Python and uses the PySerial library.

The program has the following features:

  • Downloads both internal registers (A and B) from the HP4195A
  • Supports all HP4195A Network and Spectrum modes
  • Outputs data as a TSV (tab-separated text file) compatible with Excel
    • Output file uses same headings as a HP4195A Hardcopy
    • Data is available with full instrument precision
  • Auto-detects available serial ports (COM1-COM128)
  • Does NOT affect measurement setup
Below are some screenshots, including some Excel graphs made with captured data from a live HP4195A. A sample file (DL4195A_output_sample.tsv) shows the format of the data.
If you find any bugs or have any suggestions, please do not hesitate to contact me. I give NO WARRANTY on the fitness of this program for any purpose, but it has worked well for me and some of my colleagues. Sources are included in the archive.

Download program here (DL4195A_1.0.zip, Win32 binary + sources)

MergeBOM 2.0 facilitates parts ordering

Download the program (MergeBOM_2.0.zip)

During my design work, I often have to order parts for both prototypes and small production runs. This task is usually done using a combination of Excel and a lot of Cut & Paste. I have always felt that a lot of time was wasted in trying to merge together different BOMs (Bill Of Materials) made with different tools. This is especially true if you have to order from multiple distributors and for multiple projects at the same time.

Since I’m the kind of guy who likes to automate and streamline tedious processes, I came up with the MergeBOM program to solve this problem in my workflow. The program is written in the portable Python language and uses Tkinter (Tcl/Tk) for its GUI, so it runs on every platform that has a Python interpreter (Windows, Linux/X11, *BSD/X11, MacOS X).

The idea is simple: MergeBOM reads standard CSV or TSV BOM files, combines the parts with the same ordering number and then outputs one CSV file per distributor. Thus, you get a single list that can easily be used with every distributor’s Text File Import feature. You can also use the resulting files in Excel to match with other parts of your flow.

The features of MergeBOM are as follows:

  • Simple GUI interface with built-in documentation
  • CSV and TSV BOM files reading in “Qty/Part Number/Distributor” format
  • Merging of quantities from loaded BOM files for identical part numbers
  • Single BOM file output with merged parts for each distributor
  • Multiplying of BOM quantities for multiple orders of a same design
  • Handling of Digikey “Project References” to track source project for each part
  • Handling of multiple parts per line-item (ie: connector and plug)
  • Loading/Saving of task lists to replicate an order
  • Text file previewing
  • Warning window for malformed data identification
  • Portable single-file execution on all platforms
Download the program (MergeBOM_2.0.zip) and see for yourself 🙂

I’m sharing MergeBOM free of charge in the hopes it might be useful to other users. Sources are included in the archive, as well as a Windows executable so that you don’t have to install Python to use it. Please read the instructions by clicking on the “Instructions…” button before asking questions about how to use it 🙂 

This program is especially well-suited to BOM editing with EAGLE and the BOM-AM series of BOM scripts, since it can output CSV file with any column order and handles arbitrary parts databases. I have also used this program successfully with BOMs generated from Altium DXP and Orcad.

New Tentech.ca website

Welcome to the new tentech.ca website, back online after a hiatus of more than 3 years, during which I was working on my EE degree at ETS and the SONIA project. This site is meant to be a repository of interesting information with electronics projects, technical articles, as well as freely available software.

“Entreprises Ten Tech” is my electronics design consulting business that has been running since mid-2003. I am no longer actively seeking consulting contracts since I have preferred regular employment recently because of family concerns :). I have produced several useful pieces of freeware and open-source/open-hardware projects since 1996 and I enjoy sharing my work. I will also try to bring back some of my more interesting projects from the 1996-2003 period online. This site is also to be a focal point for my current projects, both personal and professional.

I hope you enjoy the information contained within and I encourage you to also visit my friends’ and colleague’s sites.