The Canny/Devernay algorithm ============================ Version 1.0 - October 10, 2017 by Rafael Grompone von Gioi and Gregory Randall Introduction ------------ This is an implementation of Canny/Devernay's sub-pixel edge detector. This code is part of the following publication and was subject to peer review: "A Sub-Pixel Edge Detector: an Implementation of the Canny/Devernay Algorithm" by Rafael Grompone von Gioi and Gregory Randall, Image Processing On Line, 2017. DOI:10.5201/ipol.2017.216 http://dx.doi.org/10.5201/ipol.2017.216 Files ----- README.txt - This file COPYING - GNU AFFERO GENERAL PUBLIC LICENSE Version 3 Makefile - Compilation instructions for 'make' devernay.c - Devernay module ANSI C89 code (peer reviewed) devernay.h - Devernay module ANSI C89 header (peer reviewed) devernay_cmd.c - Command line interface for Devernay, ANSI C89 io.c - Input/Output functions for command interface, ANSI C89 io.h - Input/Output functions header, ANSI C89 image.pgm - Test image in PGM format image.asc - Test image in ASC format image_out.txt - Expected result for the test image as an TXT file image_out.pdf - Expected result for the test image as a PDF file image_out.svg - Expected result for the test image as a SVG file The files 'devernay.c' and 'devernay.h' were subject to peer review as part of the acceptance process of the IPOL article and are the official version of Devernay. Compiling --------- Devernay is an ANSI C89 Language program and can be used as a module to be called from a C language program or as an independent command. In the distribution is included a Makefile file with instructions to build the command line program 'devernay'. A C compiler must be installed on your system as well as the program 'make'. Devernay only uses the standard C library so it should compile in any ANSI C89 Language environment. In particular, it should compile in a Unix like system. The compiling instruction is just make from the directory where the source codes and the Makefile are located. If the compilation needs to be made manually, the usual command to do it is: cc -o devernay devernay_cmd.c io.c devernay.c -lm To verify a correct compilation you can apply Devernay to the test image 'image.pgm' and compare the result to the provided ones. This can be done by executing: make test Running the Command Line Interface ---------------------------------- The simplest Devernay command execution is just devernay (use ./devernay if the command is not included in the current path). That should print Devernay version number and a description of the command line interface, including the available options. The input image formats handled are PGM (in its two versions, ASCII and Binary) and the ASC format (as defined by the CImg Library and as described below). A typical execution would be: devernay image.pgm -t output.txt That should give the result as an TXT file 'output.txt' which consists of two columns of real numbers in ASCII format (the numbers are separated by a space). Each row corresponds to a contour point, the first column gives the x coordinate and the second row gives the y coordinate. Contour points of consecutive rows are part of the same curve, they are chained. Each curve is ended by a row "-1 -1", which mark the end of the curve or chain. A new chain may start on the next row. Then end of the file indicates that no more curves are present. For closed curves, the first point of the curve is repeated again as the last point of the chain. The following is an example of output: 9 5.57116 10 5.73102 11 6.64051 11.9352 8 12.0939 9 11.9844 10 11.4029 11 10 12.0179 9 12.119 8 11.9399 6.62612 11 5.65646 10 5.51349 9 5.62126 8 7 6.54667 8 5.68361 9 5.57116 -1 -1 2.09193 5 2.17282 4 3 2.7223 4 2.13559 5 1.99507 -1 -1 It corresponds to two curves, each one ended by a "-1 -1" row. The first one is a closed curve described by 16 points. Please note that the list has 17 points, but the first and last are the same, "9 5.57116", indicating a closed curve. The second curve is an open curve described by five points. Note that one of the two coordinates is always an integer. This is due the modified Devernay sub-pixel correction, in which the sub-pixel interpolation is always performed along the vertical or horizontal axis, but not both; thus, one of the two coordinates is not interpolated and remain an integer. For easy visualization of the result, the command line interface can also provide the output in PDF and SVG file formats: devernay image.pgm -p output.pdf will produce the PDF file 'output.pdf' and devernay image.pgm -g output.svg will produce the SVG file 'output.svg'. Using all these options will generate TXT, PDF and SVG outputs: devernay image.pgm -p output.pdf -t output.txt -g output.svg Note that the line width used in the PDF and SVG output is arbitrary. The default value is 1.3 (in pixel units) but can be modified with the -w option. By using a smaller value, the sub-pixel accuracy of the result is better appreciated: devernay image.pgm -p output.pdf -w 0.5 The width value can be set to zero: devernay image.pgm -p output.pdf -g output.svg -w 0 In this case, the PDF and SVG standards determine different behavior. In PDF, a zero width means that the software rendering the PDF will choose the smallest possible line width that can be rendered in the current device. This is useful to see details but it is not recommended for figures to be distributed as the rendering is device dependent. In SVG, however, line with zero width are not drawn. The Canny/Devernay algorithm depends on three parameters: sigma, th_low, th_high. The default value of these parameters is zero for the three of them. Their value can be modified individually using the -s, -l and -h options of the command line interface. For example: devernay image.pgm -p output.pdf -s 1 -l 5 -h 15 will set the standard deviation of the Gaussian filtering to 1, the low gradient threshold to 5 and the high gradient threshold to 15. The ASC file format ------------------- The ASC image file format was defined by the CImg Library (http://cimg.eu/). It is a simple ASCII format allowing to store 4D arrays of floating point values (and not just integer as in PGM). In addition, multiple channels and multiple frames are possible; the command line interface of Devernay, however, only handles a single gray level frame. The main reason to include this file format as a possible input is to be able to use floating point images in a simple way. As an example, the file 'image.asc' in this distribution contains the same image as 'image.pgm' but in ASC file format. To explain the ASC file format, the following is an example of a 6x6 floating point gray-level in ASC format: 6 6 1 1 0.0022 0.1119 0.9455 1.7084 0.9455 0.1119 0.1119 1.7270 5.8871 7.4892 5.8871 1.7270 0.9455 5.8871 9.6757 9.9586 9.6757 5.8888 1.7084 7.4892 9.9586 9.9999 9.9586 7.4934 0.9455 5.8871 9.6757 9.9586 9.6757 5.8888 0.1119 1.7270 5.8888 7.4934 5.8888 1.7271 An ASC file consists of a simple header followed by the data, all written as numbers in ASCII format. The header is just four integer numbers separated by spaces and ending in a new line. The four numbers of the header correspond to the size of each of the 4 dimensions X, Y, Z and C and in that order: X is the width of the image; Y is the height of the image; Z is the number of frames; C is the number of channels. For single frame and single channel (as in the example above and as required by Devernay), Z=1 and C=1. The header is followed by the data written in standard ASCII floating point notation. Any format accepted by the standard C function scanf is valid; for example: 0, 692315, 0.34230295282, -30.3423, +45, 1e10, 5E4, 3.14e-34. The numbers should be separated by any combination of spaces, tabs, or end-of-line. The order of the numbers is important. The pixels have coordinates (x,y,z,c), with 0 <= x < X and 0 <= y < Y and 0 <= z < Z and 0 <= c < C. The pixel (x,y,z,c) will be stored at position x + y*X + z*X*Y + c*X*Y*Z. Thus, the first number following the header corresponds to pixel (0,0,0,0) which is the upper left pixel of the first channel of the first frame. The second value is the second pixel on the same row (1,0,0,0) and the following values complete the first row (up to X-1,0,0,0). Then comes the second row of the first channel of the first frame, from (0,1,0,0) to (X-1,1,0,0). Then the following rows and so on until the last row of the frame, (0,Y-1,0,0) to (X-1,Y-1,0,0). This would complete the image if only one frame and one channel are present (as required in Devernay and as in the example above). In multiple frame and multiple channel (Z>1 and/or C>1), the next values will store, in the same way, the first channel of the second frame. When all the frames are complete, the same procedure will be done for the values of the second channel, and so on. Copyright and License --------------------- Copyright (c) 2016-2017 Rafael Grompone von Gioi and Gregory Randall This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program. If not, see . Thanks ------ We would be grateful to receive any comment, especially about errors, bugs, or strange results.