#include <sdet_contour.h>

Public Member Functions
	sdet_contour (float min_strength, int min_length, float min_jump, float max_gap=2.236068f)
	Save parameters and create workspace for detecting contours.
	~sdet_contour ()
	Free space allocated for detecting contours.
bool	FindNetwork (gevd_bufferxy &edgels, bool junctionp, const int njunction, const int junctionx, const int junctiony, vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_2d_sptr > &vertices)
	Trace the edgel locations to form a topological network (edges, vertices).
void	SubPixelAccuracy (vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_2d_sptr > &vertices, const gevd_bufferxy &locationx, const gevd_bufferxy &locationy)
	Use interpolation of the gradient to localize to sub-pixel accuracy.
void	InsertBorder (vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_2d_sptr > &vertices)
	Insert a border at the ROI boundary to support connected components.
void	BeSilent ()
void	BeTalkative ()
void	SetDebug ()
void	ClearDebug ()
Static Public Member Functions
static void	EqualizeSpacing (vcl_vector< vtol_edge_2d_sptr > &chains)
	apply a smoothing filter to edgel_chain(s).
static void	Translate (vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_2d_sptr > &vertices, float tx=0.5, float ty=0.5)
	computation is carried out in a zero origin ROI - translate back.
static void	ClearNetwork (vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_2d_sptr > &vertices)
	clear network storage (edges and vertices).
static void	SetEdgelData (gevd_bufferxy &grad_mag, gevd_bufferxy &angle, vcl_vector< vtol_edge_2d_sptr > &edges)
	Set edgel gradient and direction values from pixel arrays.
Static Public Attributes
static bool	talkative_ = false
static bool	debug_ = false
Protected Member Functions
int	FindChains (gevd_bufferxy &edgels, const int njunction, const int junctionx, const int junctiony, vcl_vector< vtol_edge_2d_sptr > &edges)
	internal routines.
int	FindJunctions (gevd_bufferxy &edgels, vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_2d_sptr > &vertices)
	Establish vertices; improve connectivity by jumping small gaps.
bool	move_junction (vtol_vertex_2d_sptr const &junction, int &index, vdgl_digital_curve_sptr const &dc)
	Move a junction to lie on the intersecting digital curve.
void	update_edgel_chain (vtol_edge_2d_sptr const &edge, const int old_x, const int old_y, vtol_vertex_2d_sptr &v)
	when a vertex position is moved, an edge's edgel chain must potentially be replaced.
bool	near_border (vtol_vertex_2d_sptr const &v)
	Determine if a vertex is in the border strip.
bool	DetectJunction (vtol_vertex_2d_sptr const &end, int &index, vtol_edge_2d_sptr &weaker, vtol_edge_2d_sptr &stronger, const int maxSpiral, const gevd_bufferxy &edgels)
	Detect a nearby vertex by carrying out a spiral search.
void	BreakChain (vtol_vertex_2d_sptr const &junction, int &index, vtol_edge_2d_sptr const &stronger, vtol_edge_2d_sptr &longer, vtol_edge_2d_sptr &shorter)
	Break a chain at a junction and form a "T".
void	LoopChain (vtol_vertex_2d_sptr const &junction, int &index, vtol_edge_2d_sptr const &chain, vtol_edge_2d_sptr &straight, vtol_edge_2d_sptr &curled)
	Break a single edge at junction and form a loop.
void	BreakCycle (vtol_vertex_2d_sptr const &junction, int &index, vtol_edge_2d_sptr const &stronger, vtol_edge_2d_sptr &split)
	Break a closed cycle and insert a vertex at junction.
vtol_vertex_2d_sptr	DetectTouch (vtol_vertex_2d_sptr const &end, const int maxSpiral)
	Detect nearby vertices by searching in a spiral pattern.
void	MergeEndPtTouchingEndPt (vtol_vertex_2d_sptr const &end1, vtol_vertex_2d_sptr const &end2, vtol_edge_2d_sptr &merge, vtol_edge_2d_sptr &longer, vtol_edge_2d_sptr &shorter)
	Connect an isolated endpoint to a nearby single vertex on a different edge.
bool	MergeEndPtTouchingJunction (vtol_vertex_2d_sptr const &endpt, vtol_vertex_2d_sptr const &junction, vtol_edge_2d_sptr &old_edge, vtol_edge_2d_sptr &new_edge)
	Connect an isolated endpoint to a nearby junction (2 or more edges).
bool	MergeEndPtsOfChain (vtol_vertex_2d_sptr const &endpt, vtol_vertex_2d_sptr const &other, vtol_vertex_2d_sptr &removed_vert)
	Connect an isolated endpoint to the other vertex on the same edge.
Static Protected Member Functions
static void	LookupTableInsert (vcl_vector< vtol_edge_2d_sptr > &set, vtol_edge_2d_sptr elmt)
	Lookup table operations for managing mutated vertices and edges.
static void	LookupTableReplace (vcl_vector< vtol_edge_2d_sptr > &set, vtol_edge_2d_sptr deleted, vtol_edge_2d_sptr inserted)
	replace an edge in a table indexed by vsol id.
static void	LookupTableRemove (vcl_vector< vtol_edge_2d_sptr > &set, vtol_edge_2d_sptr elmt)
	remove an edge from a table indexed by vsol id.
static void	LookupTableCompress (vcl_vector< vtol_edge_2d_sptr > &set)
	eliminate gaps in the table by removing empty entries.
static void	LookupTableInsert (vcl_vector< vtol_vertex_2d_sptr > &set, vtol_vertex_2d_sptr elmt)
	insert a vertex into a table indexed by vsol id.
static void	LookupTableReplace (vcl_vector< vtol_vertex_2d_sptr > &set, vtol_vertex_2d_sptr deleted, vtol_vertex_2d_sptr inserted)
	replace a vertex in a table indexed by vsol id.
static void	LookupTableRemove (vcl_vector< vtol_vertex_2d_sptr > &set, vtol_vertex_2d_sptr elmt)
	remove a vertex from a table indexed by vsol id.
static void	LookupTableCompress (vcl_vector< vtol_vertex_2d_sptr > &set)
	eliminate gaps in the table by removing empty entries.
Protected Attributes
float	minStrength
	class members.
int	minLength
float	minJump
float	max_gap
int	maxSpiral
vbl_array_2d< vtol_edge_2d_sptr > *	edgeMap
vbl_array_2d < vtol_vertex_2d_sptr > *	vertexMap
vcl_vector< vtol_vertex_2d_sptr >	test_verts_

Detailed Description

Definition at line 81 of file sdet_contour.h.

Constructor & Destructor Documentation

sdet_contour::sdet_contour	(	float	min_strength,
		int	min_length,
		float	min_jump,
		float	max_gap_in = `2.236068f`
	)

Save parameters and create workspace for detecting contours.

Each contour must have at least 1 pixel above min_strength, and its number of internal pixels must be above min_length. This is a heuristic hysteresis scheme that prunes weak or short isolated chains. To join a weaker contour to a stronger contour, a junction must have a change in response above min_jump on the stronger contour. This way, only strong junctions are detected.

Definition at line 113 of file sdet_contour.cxx.

sdet_contour::~sdet_contour ( )

Free space allocated for detecting contours.

Definition at line 163 of file sdet_contour.cxx.

Member Function Documentation

void sdet_contour::BeSilent ( ) [inline]

Definition at line 124 of file sdet_contour.h.

void sdet_contour::BeTalkative ( ) [inline]

Definition at line 125 of file sdet_contour.h.

void sdet_contour::BreakChain	(	vtol_vertex_2d_sptr const &	junction,
		int &	index,
		vtol_edge_2d_sptr const &	stronger,
		vtol_edge_2d_sptr &	longer,
		vtol_edge_2d_sptr &	shorter
	)		`[protected]`

Break a chain at a junction and form a "T".

Break the edge at given index, and create two subchains from it.

junction 0---------------o----------------------0 index nedgels-1 edge1 edge2

Definition at line 1018 of file sdet_contour.cxx.

void sdet_contour::BreakCycle	(	vtol_vertex_2d_sptr const &	junction,
		int &	index,
		vtol_edge_2d_sptr const &	stronger,
		vtol_edge_2d_sptr &	split
	)		`[protected]`

Break a closed cycle and insert a vertex at junction.

Break the cycle at given index, and create new cycle from/to and not including index pixel.

stronger (no vertex initially) ------------ | | | | 0-------0 junction | | | | | ------------ split - the new edge

Definition at line 866 of file sdet_contour.cxx.

void sdet_contour::ClearDebug ( ) [inline]

Definition at line 127 of file sdet_contour.h.

void sdet_contour::ClearNetwork	(	vcl_vector< vtol_edge_2d_sptr > *&	edges,
		vcl_vector< vtol_vertex_2d_sptr > *&	vertices
	)		`[static]`

clear network storage (edges and vertices).

Remove and delete all elements in global lists, and set the global lists to NULL.

Remove all digital chains of edges. Edges and vertices are removed with UnProtect().

Definition at line 2526 of file sdet_contour.cxx.

bool sdet_contour::DetectJunction	(	vtol_vertex_2d_sptr const &	endv,
		int &	index,
		vtol_edge_2d_sptr &	weaker,
		vtol_edge_2d_sptr &	stronger,
		const int	maxSpiral,
		const gevd_bufferxy &	edgels
	)		`[protected]`

Detect a nearby vertex by carrying out a spiral search.

The inputs are: endv, edgels, maxSpiral, and edgeMap.

The outputs are: index, weaker and stronger. endv is a vertex corresponding to a dangling end of an edge. i.) If the end vertex is bounding more than one edge, the routine returns false. ii.) Otherwise a spiral search is carried out around the end with a radius given by maxSpiral. Some of the nearby points on the edge connected to endv, are erased so that they are not found in the search. iii.) The edgel with maximum strength is found. If there is none, the routine returns false. iv.) The edge containing the found edgel is called "stronger" and the the location on that edge where the edgel was found is "index"

Definition at line 586 of file sdet_contour.cxx.

vtol_vertex_2d_sptr sdet_contour::DetectTouch	(	vtol_vertex_2d_sptr const &	endv,
		const int	maxSpiral
	)		`[protected]`

Detect nearby vertices by searching in a spiral pattern.

Detect touching another junction or end point, from an end point of a dangling chain by searching in a spiral pattern.

Find the neighboring vertex with the largest number of incident edges.

Definition at line 1301 of file sdet_contour.cxx.

void sdet_contour::EqualizeSpacing ( vcl_vector< vtol_edge_2d_sptr > & chains ) [static]

apply a smoothing filter to edgel_chain(s).

Make the spacing of the chain pixels nearly equal by smoothing their locations with the average filter [1 0 1]/2.

This will reduce square grid tessellation artefacts, and lead to more accurate estimation of the tangent direction, and local curvature angle, from finite differences in location. It is also useful to avoid weight artefacts in curve fitting caused by the periodic clustering of pixels along the chain. Truncating the float locations with int() will no longer map to the original pixels of the discrete chains.

Definition at line 2436 of file sdet_contour.cxx.

int sdet_contour::FindChains	(	gevd_bufferxy &	edgels,
		const int	njunction,
		const int *	junctionx,
		const int *	junctiony,
		vcl_vector< vtol_edge_2d_sptr > &	edges
	)		`[protected]`

internal routines.

Trace and collect pixels on thin contours, stronger pixels first, and favoring 4-connected over 8-connected.

link detected edgels and junctions into chains.

Thinning is not used, and so will avoid errors because of square grid tessellation. A chain can not cross itself. It can only touch itself or another chain, in which case a junction will be found later. The pixels of a chain include the 2 end points. End points and junctions are created in sdet_contour::FindJunctions. Return the number of chains found. Protected.

Definition at line 369 of file sdet_contour.cxx.

int sdet_contour::FindJunctions	(	gevd_bufferxy &	edgels,
		vcl_vector< vtol_edge_2d_sptr > &	edges,
		vcl_vector< vtol_vertex_2d_sptr > &	vertices
	)		`[protected]`

Establish vertices; improve connectivity by jumping small gaps.

Find junctions from end points touching at an interior point of a chain, with detectable jump in filter response.

Localize these junctions on the stronger contour to pixel accuracy, and break stronger chain into subchains. Also merge end points touching another end point or junction. Return the number of end points and junctions bounding all chains/cycles detected in sdet_contour::FindChains. Deletion/insertion to the network must be done completely, so that the connectivity links are updated. Protected.

Definition at line 1738 of file sdet_contour.cxx.

bool sdet_contour::FindNetwork	(	gevd_bufferxy &	edgels,
		bool	junctionp,
		const int	njunction,
		const int *	junctionx,
		const int *	junctiony,
		vcl_vector< vtol_edge_2d_sptr > *&	edges,
		vcl_vector< vtol_vertex_2d_sptr > *&	vertices
	)

Trace the edgel locations to form a topological network (edges, vertices).

Find network of linked edges and vertices, from 8-connected edge elements.

The contours must be less than 2 pixel wide, for example found from non maximum suppression. Isolated edgels and short segments are erased.

Definition at line 175 of file sdet_contour.cxx.

void sdet_contour::InsertBorder	(	vcl_vector< vtol_edge_2d_sptr > &	edges,
		vcl_vector< vtol_vertex_2d_sptr > &	vertices
	)

Insert a border at the ROI boundary to support connected components.

Insert virtual edges and vertices to enforce closure of the regions beyond the rectangular image border.

The location of the border is at 3 pixels away from the real image border, because of kernel radius in convolution and non maximum suppression. Virtual border of image should be inserted after sdet_contour::FindChains() and sdet_contour::FindJunctions().

JLM - February 1999 Modified this routine extensively to move the border to the actual image ROI bounds. Chain endpoints are extended to intersect with the border. These changes were made to support region segmentation from edgels.

Definition at line 2096 of file sdet_contour.cxx.

void sdet_contour::LookupTableCompress ( vcl_vector< vtol_edge_2d_sptr > & set ) [static, protected]

eliminate gaps in the table by removing empty entries.

Eliminate empty holes in the lookup table.

Definition at line 2652 of file sdet_contour.cxx.

void sdet_contour::LookupTableCompress ( vcl_vector< vtol_vertex_2d_sptr > & set ) [static, protected]

eliminate gaps in the table by removing empty entries.

As above for vertices.

Definition at line 2672 of file sdet_contour.cxx.

void sdet_contour::LookupTableInsert	(	vcl_vector< vtol_edge_2d_sptr > &	set,
		vtol_edge_2d_sptr	elmt
	)		`[static, protected]`

Lookup table operations for managing mutated vertices and edges.

Insert topology object in 2-way lookup table, using Id and dynamic array.

insert an edge into a table indexed by vsol id.

Protect it in the network.

Definition at line 2588 of file sdet_contour.cxx.

void sdet_contour::LookupTableInsert	(	vcl_vector< vtol_vertex_2d_sptr > &	set,
		vtol_vertex_2d_sptr	elmt
	)		`[static, protected]`

insert a vertex into a table indexed by vsol id.

As above for vertices.

Definition at line 2598 of file sdet_contour.cxx.

void sdet_contour::LookupTableRemove	(	vcl_vector< vtol_edge_2d_sptr > &	set,
		vtol_edge_2d_sptr	elmt
	)		`[static, protected]`

remove an edge from a table indexed by vsol id.

Remove topology object from 2-way lookup table leaving an empty hole.

Also remove object from the network.

Definition at line 2633 of file sdet_contour.cxx.

void sdet_contour::LookupTableRemove	(	vcl_vector< vtol_vertex_2d_sptr > &	set,
		vtol_vertex_2d_sptr	elmt
	)		`[static, protected]`

remove a vertex from a table indexed by vsol id.

As above for vertices.

Definition at line 2643 of file sdet_contour.cxx.

void sdet_contour::LookupTableReplace	(	vcl_vector< vtol_edge_2d_sptr > &	set,
		vtol_edge_2d_sptr	deleted,
		vtol_edge_2d_sptr	inserted
	)		`[static, protected]`

replace an edge in a table indexed by vsol id.

Replace deleted by inserted in 2-way lookup table.

Also remove object from the network.

Definition at line 2609 of file sdet_contour.cxx.

void sdet_contour::LookupTableReplace	(	vcl_vector< vtol_vertex_2d_sptr > &	set,
		vtol_vertex_2d_sptr	deleted,
		vtol_vertex_2d_sptr	inserted
	)		`[static, protected]`

replace a vertex in a table indexed by vsol id.

As above for vertices.

Definition at line 2621 of file sdet_contour.cxx.

void sdet_contour::LoopChain	(	vtol_vertex_2d_sptr const &	junction,
		int &	index,
		vtol_edge_2d_sptr const &	chain,
		vtol_edge_2d_sptr &	straight,
		vtol_edge_2d_sptr &	curled
	)		`[protected]`

Break a single edge at junction and form a loop.

Break the chain at given index, and create a loop.

This case occurs when the junction is caused by a chain touching itself

straight junction 0-------------------0-------- | | curled | | ---------

Definition at line 1123 of file sdet_contour.cxx.

bool sdet_contour::MergeEndPtsOfChain	(	vtol_vertex_2d_sptr const &	endpt,
		vtol_vertex_2d_sptr const &	other,
		vtol_vertex_2d_sptr &	removed_vert
	)		`[protected]`

Connect an isolated endpoint to the other vertex on the same edge.

Merge 2 end points of a same chain creating a cycle.

endpt o------------------ o---- | other \ | ------------

The removed vertex is the either endpt or other, depending on the direction of the edge

Definition at line 1357 of file sdet_contour.cxx.

void sdet_contour::MergeEndPtTouchingEndPt	(	vtol_vertex_2d_sptr const &	end1,
		vtol_vertex_2d_sptr const &	end2,
		vtol_edge_2d_sptr &	merge,
		vtol_edge_2d_sptr &	longer,
		vtol_edge_2d_sptr &	shorter
	)		`[protected]`

Connect an isolated endpoint to a nearby single vertex on a different edge.

Merge two different chains by inserting a link from end1 to end2 end1 and end2 are touching according to the predicate DetectTouch end1 and end2 are each incident to a single, different edge.

shorter gap longer 0-------------o o----------------------0 end1 end2

Definition at line 1431 of file sdet_contour.cxx.

bool sdet_contour::MergeEndPtTouchingJunction	(	vtol_vertex_2d_sptr const &	endpt,
		vtol_vertex_2d_sptr const &	junction,
		vtol_edge_2d_sptr &	old_edge,
		vtol_edge_2d_sptr &	new_edge
	)		`[protected]`

Connect an isolated endpoint to a nearby junction (2 or more edges).

Merge an isolated end point into a nearby junction.

------------ | | endpt | | O 0-----------o 0 junction 0 | | | ----------------------

Definition at line 1601 of file sdet_contour.cxx.

bool sdet_contour::move_junction	(	vtol_vertex_2d_sptr const &	junction,
		int &	index,
		vdgl_digital_curve_sptr const &	dc
	)		`[protected]`

Move a junction to lie on the intersecting digital curve.

Refine the intersection position to double precision

Definition at line 696 of file sdet_contour.cxx.

bool sdet_contour::near_border ( vtol_vertex_2d_sptr const & v ) [protected]

Determine if a vertex is in the border strip.

The strip supports the edge detection kernel

Definition at line 1283 of file sdet_contour.cxx.

void sdet_contour::SetDebug ( ) [inline]

Definition at line 126 of file sdet_contour.h.

void sdet_contour::SetEdgelData	(	gevd_bufferxy &	grad_mag,
		gevd_bufferxy &	angle,
		vcl_vector< vtol_edge_2d_sptr > &	edges
	)		`[static]`

Set edgel gradient and direction values from pixel arrays.

Set the orientation at each edgel on all digital curves to a continuous orientation value, which is consistent with C.

Rothwell's EdgeDetector. That is theta = (180/M_PI)*atan2(dI/dy, dI/dx)

Definition at line 2540 of file sdet_contour.cxx.

void sdet_contour::SubPixelAccuracy	(	vcl_vector< vtol_edge_2d_sptr > &	edges,
		vcl_vector< vtol_vertex_2d_sptr > &	vertices,
		const gevd_bufferxy &	locationx,
		const gevd_bufferxy &	locationy
	)

Use interpolation of the gradient to localize to sub-pixel accuracy.

Insert subpixel accuracy into the pixels on the edges/vertices.

Truncating float locations with int(xy) should map to the original pixel locations. No interpolation is done at junctions of 3 or more contours, so a junction can have location error up to 1-2 pixel, tangential to the strong contour.

Definition at line 2020 of file sdet_contour.cxx.

void sdet_contour::Translate	(	vcl_vector< vtol_edge_2d_sptr > &	edges,
		vcl_vector< vtol_vertex_2d_sptr > &	vertices,
		float	tx = `0.5`,
		float	ty = `0.5`
	)		`[static]`

computation is carried out in a zero origin ROI - translate back.

Translate all the pixels in the edges and vertices by (tx, ty).

If the image is extracted from an ROI, a translation of (roi->GetOrigX(), roi->GetOrigY()) must be done to have coordinates in the reference frame of the original image. Add 0.5 if you want to display location at center of pixel instead of upper-left corner.

Definition at line 2484 of file sdet_contour.cxx.

void sdet_contour::update_edgel_chain	(	vtol_edge_2d_sptr const &	edge,
		const int	old_x,
		const int	old_y,
		vtol_vertex_2d_sptr &	v
	)		`[protected]`

when a vertex position is moved, an edge's edgel chain must potentially be replaced.

old_x and old_y is the original end position. It is possible that the vertex can move up to 4 pixels. The new position is the location of v. Edgels are added from the end of the old digital_curve to the new vertex position.

Definition at line 724 of file sdet_contour.cxx.