---

find_register.c File Reference

Registration of a pair of overlapping images. More...

#include <stdint.h>
#include "sadie.h"
#include "proto.h"
#include <math.h>
#include <sys/time.h>

Compounds
struct	bandroi
	Sums of pixel values within a rectangular region of interest (ROI) (limited to a single band and interval). More...
struct	dim_range
	Represents a range of indicies, e.g., within a particular image dimension (bands, lines, pixels, etc.). More...
struct	mheap
	A fixed-size ordered queue (a heap structure) of goodness of fit values. More...
struct	mpos
	The goodness of fit metric value from matching images, with their positions. More...
struct	overlap
	Represents the overlap interval between two images. More...
struct	regimage_pyramid
	A pyramid of images, ordered by resolution. More...
struct	regparam
	Registration parameters for a particular downsampled image resolution. More...
struct	regparam_pyramid
	A collection of settings for registering images at various resolutions. More...
struct	xydisplace
	Forward or backward displacement both horizontal and vertical. More...
Typedefs
typedef dim_range	Dim_range_t
	Represents a range of indicies, e.g., within a particular image dimension (bands, lines, pixels, etc.).
typedef bandroi	Bandroi_t
	Sums of pixel values within a rectangular region of interest (ROI) (limited to a single band and interval).
typedef overlap	Overlap_t
	Represents the overlap interval between two images.
typedef xydisplace	Xydisplace_t
	Forward or backward displacement both horizontal and vertical.
typedef mpos	Mpos_t
	The goodness of fit metric value from matching images, with their positions.
typedef mheap	Mheap_t
	A fixed-size ordered queue (a heap structure) of goodness of fit values.
typedef regparam	Regparam_t
	Registration parameters for a particular downsampled image resolution.
typedef regparam_pyramid	Regparam_pyramid_t
	A collection of settings for registering images at various resolutions.
typedef regimage_pyramid	Regimage_pyramid_t
	A pyramid of images, ordered by resolution.
Enumerations
enum	regerr_t {   REGERR_OK = 0, REGERR_EMPTY, REGERR_MISMATCH, REGERR_BADPARAM,   REGERR_NOLAP, REGERR_TOOSMALL }
	Error codes for registration failures. More...
Functions
regimage_pyramidp_t	make_regpyramid (const IMAGE *full_img, size_t levs, uint32_t ratio)
	Create a pyramid of progressively downsampled images.
bandroip_t	copy_bandroi (bandroip_t dest, const bandroip_t src)
	Copy the details of one single-band region of interest to another.
long double	product_bandroi (bandroip_t s, bandroip_t t)
	Compute the sum of the products of the pixel values in two identical ROIs.
void	clip_overlap (long int off, uint32_t ssize, uint32_t tsize, overlapp_t lap)
	Determine the ovelap interval in a particular dimension (lines or pixels).
void	shift_ranges (long int delta, uint32_t limit, dim_rangep_t old, dim_rangep_t all, dim_rangep_t sub, dim_rangep_t add)
	Shift the index range covered by a rectangular ROI in a single dimension.
void	maximize_r (const bandroip_t search, const bandroip_t target, long double ss_target, int i, int j, const xydisplacep_t apriori, mheapp_t matches)
	Compute the classic product-moment correlation coefficient, r, then use Fisher's z-transformation to compute a t-value from this (to get a goodness of fit index that's independent of the degrees of freedom, which in this case are determined by the sizes of the regions of interest).
void	find_optima (const IMAGE *search_img, const IMAGE *target_img, const regparamp_t prm, const xydisplacep_t apriori, const overlapp_t xlap, const overlapp_t ylap, mheapp_t matches)
	Find the maximum goodness of fit values in a set of image overlaps.
void	FIND_REGISTER (IMAGE *img1, IMAGE *img2, int est_x_off, int est_y_off, int *x_off, int *y_off, PIXEL *bias_adj, PIXEL *gain_adj)
	Determine the best registration offsets of two overlapping images.

---

Detailed Description

Registration of a pair of overlapping images.

Given a pair of images that are known to overlap, we want to register them exactly, so that within the overlapping area each pixel in one image represents the same physical location as a pixel in the other. We handle only the simplest case, where the two images already have identical spatial scales, are undistorted relative to some common coordinate plane, and are not rotated relative to each other. There's even some a priori information about the the relative displacement of one image relative to the other, so we simply search all possible relative positions in the neighborhood of this initial suggestion and accept the one that yields the best value of some goodness-of-fit function.

Author:

University of Arizona Digital Image Analysis Lab

Date:

2003

Version:

$Id$

---

Typedef Documentation

typedef struct overlap Overlap_t

Represents the overlap interval between two images. The interval is on a single image dimension (pixels, lines, etc.); an offset from the image origin and a length (less than the image size in that dimension) are the basis of this representation.

typedef struct regimage_pyramid Regimage_pyramid_t

A pyramid of images, ordered by resolution. The image in ilevel[0] is at the highest resolution, those in ilevel[1] to ilevel[nlevels-1] are downsampled to progressively lower resolutions.

typedef struct regparam_pyramid Regparam_pyramid_t

A collection of settings for registering images at various resolutions. The parameters in plevel[0] are for the highest resolution, those in plevel[nlevels-1] for the lowest.

---

Enumeration Type Documentation

enum regerr_t

Error codes for registration failures. Enumeration values: REGERR_OK  no error (zero, to make if (!err) tests work) REGERR_EMPTY  unexpected null data structure REGERR_MISMATCH  image pyramid depth or resolution mismatch REGERR_BADPARAM  corrupt search parameters REGERR_NOLAP  no overlap between the images REGERR_TOOSMALL  the overlap area is too small

---

Function Documentation

void clip_overlap (  long int    off, uint32_t    ssize, uint32_t    tsize, overlapp_t    lap )

Determine the ovelap interval in a particular dimension (lines or pixels). Parameters: off  the displacement of the second image relative to the first. ssize  the first image length in this dimension. tsize  the second image length. lap  set to the newly-computed overlap interval.

bandroip_t copy_bandroi (  bandroip_t    dest, const bandroip_t    src )

Copy the details of one single-band region of interest to another. Equivalent to a bitwise copy of one ROI stucture to another, but with some sanity checks. Parameters: dest  the destination ROI (details overwritten). src  the source ROI, containing valid ranges and sums to copy. Returns: the destination ROI.

void find_optima (  const IMAGE *    search_img, const IMAGE *    target_img, const regparamp_t    prm, const xydisplacep_t    apriori, const overlapp_t    xlap, const overlapp_t    ylap, mheapp_t    matches )

Find the maximum goodness of fit values in a set of image overlaps. Given a pair of images at a suggested overlap position, examine all the other overlap positions close to this, and identify the positions that maximize the goodness of fit index, t. Note that the search ROI is not the same as the search pattern: the former is a substantial part of one of the images, identical in size to the target ROI; the latter is a (generally much smaller) set of coordinate pairs, each pair defining a potential overlap position for the two images. The search order, outwards from the center of the pattern, reduces the maximum length of the chains of updating operations needed by the algorithm. Use any previously recorded optima in the heap structure that matches points to, replacing them or leaving them in place as necessary. Parameters: search_image  the image within which to move a search ROI. target_image  contains a fixed ROI to match with the search ROI. prm  points to the registration search parameter structure. apriori  points to the structure defining the a priori position. xlap  defines the horizontal overlap interval in the images. ylap  defines the vertical overlap interval in the images. matches  a heap structure recording the optimal match positions.

void FIND_REGISTER (  IMAGE *    img1, IMAGE *    img2, int    est_x_off, int    est_y_off, int *    x_off, int *    y_off, PIXEL *    bias_adj, PIXEL *    gain_adj )

Determine the best registration offsets of two overlapping images. Starting with some a priori values, search various possible horizontal and vertical offsets for the combination that give the best goodness of fit index between the ovelapping areas of the images. Determine the offset and bias correction once the accurate offsets are available. Parameters: img1  the first input image. img2  the second input image. est_x_off  the estimated x-offset of the second image. est_y_off  the estimated y-offset of the second image. x_off  the actual x-offset of the second image. y_off  the actual y-offset of the second image. bias_adj  the bias adjustment for the second image. gain_adj  the gain adjustment for the second image.

regimage_pyramidp_t make_regpyramid (  const IMAGE *    full_img, size_t    levs, uint32_t    ratio )

Create a pyramid of progressively downsampled images. Assumes the images at different levels in the pyramid are related to each other by a fixed downsampling ratio. Parameters: full_img  a pointer to the full-resolution (level 0) SADIE image. levs  the number of levels in the pyramid. ratio  the ratio between resolutions in adjacent pyramid levels. Returns: the newly-created pyramid, or NULL on failure.

void maximize_r (  const bandroip_t    search, const bandroip_t    target, long double    ss_target, int    i, int    j, const xydisplacep_t    apriori, mheapp_t    matches )

Compute the classic product-moment correlation coefficient, r, then use Fisher's z-transformation to compute a t-value from this (to get a goodness of fit index that's independent of the degrees of freedom, which in this case are determined by the sizes of the regions of interest). Use one of the standard textbook formulae, computing a covariance term from all the values in both search and target ROIs, and correcting this by the previously computed variance terms for each ROI. Update the queue of optimum t-values and their locations if necessary. Parameters: search  a particular search region of interest. target  the one invariant target region of interest. ss_target  the sum of squares for the target ROI. i  the current search pattern column (pixel) index. j  the current search row (line) index. apriori  estimate of the relative overlap of the two images. matches  priority queue of previously determined r-value maxima.

long double product_bandroi (  bandroip_t    s, bandroip_t    t )

Compute the sum of the products of the pixel values in two identical ROIs. Parameters: s  the first single-band rectangular ROI. t  the second single-band rectangular ROI. Returns: the sum of the products of corresponding pixel values.

void shift_ranges (  long int    delta, uint32_t    limit, dim_rangep_t    old, dim_rangep_t    all, dim_rangep_t    sub, dim_rangep_t    add )

Shift the index range covered by a rectangular ROI in a single dimension. Given a previously established range of indices for an ROI in a single dimension (e.g., pixels or lines), and a relative displacement for this range, determine the new range for the ROI as a whole, and two secondary ranges: the range whose values must be subtracted to update the ROI, and the range whose values must be added. The actual additions and subtractions happen elsewhere. Parameters: delta  the relative displacement of the range. limit  clip the ranges to fit in the interval [0..@a limit). old  the previously established ROI range to be shifted. all  the complete ROI range after shifing. sub  the subrange whose values must be subtracted in the update. add  the subrange whose values must be added in the update.

---