Definitions for an image edge detector. More...

#include <jwsc/config.h>
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <assert.h>
#include <math.h>
#include <string.h>
#include <errno.h>
#include "jwsc/base/error.h"
#include "jwsc/math/constants.h"
#include "jwsc/vector/vector.h"
#include "jwsc/matrix/matrix.h"
#include "jwsc/matrix/matrix_fft.h"
#include "jwsc/matrix/matrix_conv.h"
#include "jwsc/matrix/matrix_util.h"
#include "jwsc/filter/2d.h"
#include "jwsc/prob/pmf.h"
#include "jwsc/image/edge.h"

Include dependency graph for edge.c:

Go to the source code of this file.

Data Structures
struct	Edge_list_f
	Linked list node containing an edge point. More...
struct	Gradient_f
	Gradient element detected using the partial derivative masks. More...
Typedefs
typedef struct Edge_list_f	Edge_list_f
	Linked list node containing an edge point.
Functions
static void	free_edge_list_f (Edge_list_f *edges)
static void	copy_edge_list_into_set_f (Edge_set_f set, Edge_list_f list)
	Copies a linked list of edge points as an edge into the set of edges.
static Edge_list_f *	merge_edge_lists_f (Edge_list_f left, Edge_list_f right)
	Merges two linked lists of edge points into one.
static Error *	create_gradient_map_f (Gradient_f **map_out, const Matrix_f m, float sigma)
	Creates a gradient map from a matrix.
static Gradient_f *	follow_gradient_f (int32_t grad_row_in_out, int32_t grad_col_in_out, float dir_x, float dir_y, Gradient_f **map, uint32_t num_rows, uint32_t num_cols, uint32_t padding)
	Get the next gradient along the specified gradient.
static Gradient_f *	get_maximal_along_gradient_f (int32_t grad_row_in_out, int32_t grad_col_in_out, Gradient_f **map, uint32_t num_rows, uint32_t num_cols, uint32_t padding)
	Non-maximal suppression.
static Edge_list_f *	follow_edge_right_f (float dir_x, float dir_y, int32_t grad_row, int32_t grad_col, Gradient_f **map, uint32_t num_rows, uint32_t num_cols, uint32_t padding, float thresh)
	Hysterisis to the right.
static Edge_list_f *	follow_edge_left_f (float dir_x, float dir_y, int32_t grad_row, int32_t grad_col, Gradient_f **map, uint32_t num_rows, uint32_t num_cols, uint32_t padding, float thresh)
	Hysterisis to the left.
static Edge_set_f *	get_edge_set_from_gradient_map_f (Gradient_f **map, uint32_t num_rows, uint32_t num_cols, uint32_t padding, float begin_thresh, float end_thresh)
	Uses non-maximal suppression and hysterisis to get the edge points from the image.
detect_image_edge_points
Detects edge points in each sample of an image.
Error *	detect_image_edge_set_f (Edge_set_f *edges_out, const Image_f img, float sigma, float begin_thresh, float end_thresh, uint32_t padding)
	Detects a set of edges in each sample of a single precision image.
Error *	DEPRECATED_detect_image_edge_set_f (Edge_set_f r_edges_out, Edge_set_f g_edges_out, Edge_set_f *b_edges_out, const Image_f img, float sigma, float begin_thresh, float end_thresh, uint32_t padding)
	Detects a set of edges in each sample of a single precision image.
detect_matrix_edge_points
Detects edge points in a matrix (single-sample image).
Error *	detect_matrix_edge_set_f (Edge_set_f *edges_out, const Matrix_f m, float sigma, float begin_thresh, float end_thresh, uint32_t padding)
	Detects a set of edges in a single precision matrix (single-sample image).
free_edge_set
Frees a set of edges.
void	free_edge_set_f (Edge_set_f *edges)
	Frees a set of single precision edges.
remove_short_edges
Removes edges with a number of points less than a specified minimum.
void	remove_short_edges_f (Edge_set_f *edges, uint32_t min_len)
	Removes single precision edges with a number of points less than a specified minimum.
break_edges_at_corners
Breaks apart edges where the gradient direction changes significantly.
static void	recursively_break_edges_at_corners_f (Edge_set_f *edges, uint32_t i, float thresh, uint32_t num_avg)
	Finds the edge point with the largest gradient difference on either side, breaks the edge, and recurses on the two newly created edges.
void	break_edges_at_corners_f (Edge_set_f *edges, float thresh, uint32_t num_avg)
	Breaks apart single precision edges where the gradient direction changes significantly.
sample_edge_points
Randomly samples edge points from an array of them.
void	sample_edge_set_f (Edge_set_f *edges_out, const Edge_set_f edges_in, float p)
	Randomly samples single precision edge points from a set of them.
color_edge_set
Colors a set of edges in an image.
Error *	color_edge_set_f (Image_f *img_out, const Image_f img_in, const Edge_set_f edges, const Pixel_f pxl)
	Colors single precision set of edges in an image.
randomly_color_edge_set
Colors a set of edges in an image with randomly selected colors.
Error *	randomly_color_edge_set_f (Image_f *img_out, const Image_f img_in, const Edge_set_f *edges)
	Colors single precision set of edges in an image with randomly selected colors.
color_edge_points
Colors edge points in an image.
Error *	color_edge_points_f (Image_f *img_out, const Image_f img_in, const Edge_point_f pts, uint32_t num_pts, const Pixel_f pxl)
	Colors single precision edge points in an image.
randomly_color_edge_points
Colors edge points in an image with a randomly selected color.
Error *	randomly_color_edge_points_f (Image_f *img_out, const Image_f img_in, const Edge_point_f *pts, uint32_t num_pts)
read_edge_set
Reads a set of edges in ASCII format from a file.
Error *	read_edge_set_f (Edge_set_f *edges_out, const char fname)
	Reads a set of single precision edges in ASCII format from a file.
write_edge_set
Writes a set of edges in ASCII format to a file.
Error *	write_edge_set_f (const Edge_set_f edges, const char fname)
	Writes a set of single precision edges in ASCII format to a file.

Detailed Description

Definitions for an image edge detector.

Author:: Joseph Schlecht

License:: Creative Commons BY-NC-SA 3.0

The edge detection algorithm is a variation of the standard Canny algorithm: the image is convolved with the gradiant of Gaussian, then non-maximal suppression and hysterisis are applied to the resulting gradient map.

Definition in file edge.c.

Typedef Documentation

typedef struct Edge_list_f Edge_list_f

Linked list node containing an edge point.

Function Documentation

static void free_edge_list_f ( Edge_list_f * edges ) [static]

Parameters:

edges List of edges to free.

Definition at line 90 of file edge.c.

static void copy_edge_list_into_set_f	(	Edge_set_f *	set,
		Edge_list_f *	list
	)		`[static]`

Copies a linked list of edge points as an edge into the set of edges.

Definition at line 110 of file edge.c.

static Edge_list_f* merge_edge_lists_f	(	Edge_list_f *	left,
		Edge_list_f *	right
	)		`[static]`

Merges two linked lists of edge points into one.

At least one of the lists must have an element. The two lists are merged at their heads. So the order of the left list is tail-to-head and the order of the right is head-to-tail.

Definition at line 173 of file edge.c.

static Error* create_gradient_map_f	(	Gradient_f ***	map_out,
		const Matrix_f *	m,
		float	sigma
	)		`[static]`

Creates a gradient map from a matrix.

Definition at line 233 of file edge.c.

static Gradient_f* follow_gradient_f	(	int32_t *	grad_row_in_out,
		int32_t *	grad_col_in_out,
		float	dir_x,
		float	dir_y,
		Gradient_f **	map,
		uint32_t	num_rows,
		uint32_t	num_cols,
		uint32_t	padding
	)		`[static]`

Get the next gradient along the specified gradient.

Definition at line 327 of file edge.c.

static Gradient_f* get_maximal_along_gradient_f	(	int32_t *	grad_row_in_out,
		int32_t *	grad_col_in_out,
		Gradient_f **	map,
		uint32_t	num_rows,
		uint32_t	num_cols,
		uint32_t	padding
	)		`[static]`

Non-maximal suppression.

Definition at line 405 of file edge.c.

static Edge_list_f* follow_edge_right_f	(	float	dir_x,
		float	dir_y,
		int32_t	grad_row,
		int32_t	grad_col,
		Gradient_f **	map,
		uint32_t	num_rows,
		uint32_t	num_cols,
		uint32_t	padding,
		float	thresh
	)		`[static]`

Hysterisis to the right.

Returns:: The first edge point in the linked list of points making the edge found by hysterisis.

Definition at line 491 of file edge.c.

static Edge_list_f* follow_edge_left_f	(	float	dir_x,
		float	dir_y,
		int32_t	grad_row,
		int32_t	grad_col,
		Gradient_f **	map,
		uint32_t	num_rows,
		uint32_t	num_cols,
		uint32_t	padding,
		float	thresh
	)		`[static]`

Hysterisis to the left.

Returns:: The first edge point in the linked list of points making the edge found by hysterisis.

Definition at line 548 of file edge.c.

static Edge_set_f* get_edge_set_from_gradient_map_f	(	Gradient_f **	map,
		uint32_t	num_rows,
		uint32_t	num_cols,
		uint32_t	padding,
		float	begin_thresh,
		float	end_thresh
	)		`[static]`

Uses non-maximal suppression and hysterisis to get the edge points from the image.

Definition at line 603 of file edge.c.

Error* detect_image_edge_set_f	(	Edge_set_f **	edges_out,
		const Image_f *	img,
		float	sigma,
		float	begin_thresh,
		float	end_thresh,
		uint32_t	padding
	)

Detects a set of edges in each sample of a single precision image.

Smoothed partial derivative kernels, non-maximal suppression, and hysteresis are used to trace out the edge points from the input image.

Parameters:

edges_out	Result parameter. If *r_edges_out is NULL, an array of edge points is allocated; otherwise its space is re-used.
img	Image to get the edge points of.
sigma	Parameter for the Gaussian kernel used for smoothing and edge detection.
begin_thresh	Used when scanning the image to look for gradient magnitudes to follow under non-maximal suppression.
end_thresh	Once an edge is found under non-maximal suppression, it is followed (perpendicular to the gradient) until the gradient magnitude falls below this threshold.
padding	Amount of padding to use around the border of the image. The padding is created by extending the image.

Returns:

On success, NULL is returned. On error, an Error is returned and *[rgb]_edges_out are freed and set to NULL.

ERROR_INV_ARG Sigma is too small.

Definition at line 720 of file edge.c.

Error* DEPRECATED_detect_image_edge_set_f	(	Edge_set_f **	r_edges_out,
		Edge_set_f **	g_edges_out,
		Edge_set_f **	b_edges_out,
		const Image_f *	img,
		float	sigma,
		float	begin_thresh,
		float	end_thresh,
		uint32_t	padding
	)

Detects a set of edges in each sample of a single precision image.

Smoothed partial derivative kernels, non-maximal suppression, and hysteresis are used to trace out the edge points from the input image.

Parameters:

r_edges_out	Result parameter. If *r_edges_out is NULL, an array of edge points is allocated; otherwise its space is re-used.
g_edges_out	Result parameter. If *g_edges_out is NULL, an array of edge points is allocated; otherwise its space is re-used.
b_edges_out	Result parameter. If *b_edges_out is NULL, an array of edge points is allocated; otherwise its space is re-used.
img	Image to get the edge points of.
sigma	Parameter for the Gaussian kernel used for smoothing and edge detection.
begin_thresh	Used when scanning the image to look for gradient magnitudes to follow under non-maximal suppression.
end_thresh	Once an edge is found under non-maximal suppression, it is followed (perpendicular to the gradient) until the gradient magnitude falls below this threshold.
padding	Amount of padding to use around the border of the image. The padding is created by extending the image.

Returns:

On success, NULL is returned. On error, an Error is returned and *[rgb]_edges_out are freed and set to NULL.

ERROR_INV_ARG Sigma is too small.

Definition at line 775 of file edge.c.

Error* detect_matrix_edge_set_f	(	Edge_set_f **	edges_out,
		const Matrix_f *	m,
		float	sigma,
		float	begin_thresh,
		float	end_thresh,
		uint32_t	padding
	)

Detects a set of edges in a single precision matrix (single-sample image).

Smoothed partial derivative kernels, non-maximal suppression, and hysteresis are used to trace out the edge points from the input image.

Parameters:

edges_out	Result parameter. If *edges_out is NULL, an array of edge points is allocated; otherwise its space is re-used.
m	Matrix to get the edge points of.
sigma	Parameter for the Gaussian kernel used for smoothing and edge detection.
begin_thresh	Used when scanning the image to look for gradient magnitudes to follow under non-maximal suppression.
end_thresh	Once an edge is found under non-maximal suppression, it is followed (perpendicular to the gradient) until the gradient magnitude falls below this threshold.
padding	Amount of padding to use around the border of the matrix. The padding is created by extending the matrix.

Returns:

On success, NULL is returned. On error, an Error is returned and *edges_out are freed and set to NULL.

ERROR_INV_ARG Sigma is too small.

Definition at line 852 of file edge.c.

void free_edge_set_f ( Edge_set_f * edges )

Frees a set of single precision edges.

Parameters:

edges Set of edges to free.

Definition at line 905 of file edge.c.

void remove_short_edges_f	(	Edge_set_f *	edges,
		uint32_t	min_len
	)

Removes single precision edges with a number of points less than a specified minimum.

Parameters:

edges	Edge set to remove short edges from.
min_len	Minimum number of points for an edge. Edges with fewer points are removed.

Definition at line 936 of file edge.c.

static void recursively_break_edges_at_corners_f	(	Edge_set_f *	edges,
		uint32_t	i,
		float	thresh,
		uint32_t	num_avg
	)		`[static]`

Finds the edge point with the largest gradient difference on either side, breaks the edge, and recurses on the two newly created edges.

Parameters:

edges	Edge set to break apart.
i	The index in the edge set to recurse on.
thresh	If the dot product of the averaged vectors is less than this threshold, the edge is broken.
num_avg	Number of gradient vectors to average into one when computing the dot product.

Definition at line 1029 of file edge.c.

void break_edges_at_corners_f	(	Edge_set_f *	edges,
		float	thresh,
		uint32_t	num_avg
	)

Breaks apart single precision edges where the gradient direction changes significantly.

Parameters:

edges	Edge set to break apart.
thresh	If the dot product of the averaged vectors is less than this threshold, the edge is broken.
num_avg	Number of gradient vectors to average into one when computing the dot product.

Definition at line 1111 of file edge.c.

void sample_edge_set_f	(	Edge_set_f **	edges_out,
		const Edge_set_f *	edges_in,
		float	p
	)

Randomly samples single precision edge points from a set of them.

Parameters:

edges_out	Result parameter. If *edges_out is NULL, a set of edges is allocated; otherwise its space is re-used.
edges_in	Set of edges to sample from.
p	Bernoulli parameter; probability of sampling an edge point.

Note:: If *edges_out == edges_in, then edges_in is overwritten.

Definition at line 1147 of file edge.c.

Error* color_edge_set_f	(	Image_f **	img_out,
		const Image_f *	img_in,
		const Edge_set_f *	edges,
		const Pixel_f *	pxl
	)

Colors single precision set of edges in an image.

Parameters:

img_out	Result parameter. If *img_out is NULL, an image is allocated; otherwise its space is re-used.
img_in	Image to color the edge points on.
edges	Edge set to use.
pxl	Pixel to use for coloring the edge points.

Returns:

On success, NULL is returned. On error, an Error is returned and *img_out is freed and set to NULL.

Error_types::ERROR_INV_ARG Edge points indexed outside img_in. The file to read from is not formatted properly.

Definition at line 1278 of file edge.c.

Error* randomly_color_edge_set_f	(	Image_f **	img_out,
		const Image_f *	img_in,
		const Edge_set_f *	edges
	)

Colors single precision set of edges in an image with randomly selected colors.

Parameters:

img_out	Result parameter. If *img_out is NULL, an image is allocated; otherwise its space is re-used.
img_in	Image to color the edge points on.
edges	Edge set to use.

Returns:

On success, NULL is returned. On error, an Error is returned and *img_out is freed and set to NULL.

Error_types::ERROR_INV_ARG Edge points indexed outside img_in. The file to read from is not formatted properly.

Definition at line 1329 of file edge.c.

Error* color_edge_points_f	(	Image_f **	img_out,
		const Image_f *	img_in,
		const Edge_point_f *	pts,
		uint32_t	num_pts,
		const Pixel_f *	pxl
	)

Colors single precision edge points in an image.

Parameters:

img_out	Result parameter. If *img_out is NULL, an image is allocated; otherwise its space is re-used.
img_in	Image to color the edge points on.
pts	Edge points to use.
num_pts	Number of elements in pts.
pxl	Pixel to use for coloring the edge points.

Returns:

On success, NULL is returned. On error, an Error is returned and *img_out is freed and set to NULL.

Error_types::ERROR_INV_ARG Edge points indexed outside img_in. The file to read from is not formatted properly.

Definition at line 1381 of file edge.c.

Error* randomly_color_edge_points_f	(	Image_f **	img_out,
		const Image_f *	img_in,
		const Edge_point_f *	pts,
		uint32_t	num_pts
	)

Parameters:

img_out	Result parameter. If *img_out is NULL, an image is allocated; otherwise its space is re-used.
img_in	Image to color the edge points on.
pts	Edge points to use.
num_pts	Number of elements in pts.

Returns:

On success, NULL is returned. On error, an Error is returned and *img_out is freed and set to NULL.

Error_types::ERROR_INV_ARG Edge points indexed outside img_in. The file to read from is not formatted properly.

Definition at line 1445 of file edge.c.

Error* read_edge_set_f	(	Edge_set_f **	edges_out,
		const char *	fname
	)

Reads a set of single precision edges in ASCII format from a file.

The first line of the file must contains the number of edges, the second has the total number of edge points and the following lines have the number of points in each edge followed by the actual points. For example,

 num_rows=100
 num_cols=100
 num_edges=2
 total_num_points=5
 num_pts=3
 col=0 row=0 dcol=1 drow=1 mag=1
 col=9 row=8 dcol=4 drow=1 mag=1
 col=1 row=2 dcol=2 drow=1 mag=1
 num_pts=2
 col=9 row=8 dcol=4 drow=1 mag=1
 col=1 row=2 dcol=2 drow=1 mag=1

Parameters:

edges_out	Result parameter. If *edges_out is NULL, an edge set is allocated; otherwise its space is re-used.
fname	Name of the file to read from.

Returns:

On success, NULL is returned. On error, an Error is returned and *edges_out is freed and set to NULL.

ERROR_INV_ARG The file to read from is not formatted properly.
ERROR_IO Could not read from fname.

Definition at line 1504 of file edge.c.

Error* write_edge_set_f	(	const Edge_set_f *	edges,
		const char *	fname
	)

Writes a set of single precision edges in ASCII format to a file.

The first line of the file contains the number of edges, the second has the total number of edge points and the following lines have the number of points in each edge followed by the actual points. For example,

 num_rows=100
 num_cols=100
 num_edges=2
 total_num_points=5
 num_pts=3
 col=0 row=0 dcol=1 drow=1 mag=1
 col=9 row=8 dcol=4 drow=1 mag=1
 col=1 row=2 dcol=2 drow=1 mag=1
 num_pts=2
 col=9 row=8 dcol=4 drow=1 mag=1
 col=1 row=2 dcol=2 drow=1 mag=1

Parameters:

edges	Edge set to write.
fname	Name of the file to write to.

Returns:

On success, NULL is returned. On error, an Error is returned.

ERROR_IO Could not read from fname.

Definition at line 1624 of file edge.c.

Data Structures

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation