Foundations of Image Analysis


I plan to divide the series into three episodes. This time I will introduce basic notions related to image processing. Those high-level algorithms will be included in later articles. (Actually, these articles are written mainly for the review of final exam ::>_<::)

Table of Contents

Pixel Distance Measure

Given some pixels as , and .

The pixel distance has some properties:

Basic distance functions:

  • Euclidean:
  • City-Block:
  • Chessboard:

Pixel Norm and general distance:

  • Norm:
  • (*) Distance:

Actually, we can find that

Define neighborhood by distance:

2-D Discrete Fourier Transform

Given an matrix (i.e. 2-D image), 2-D DFT can be defined as

2-D IDFT (Invert DFT) is defined as

We can also find that the 2-D DFT matrix for a image is

There are many 2-D DFT properties:

  • (*) Linear:
  • Scale:
  • (*) Translation:
  • (*) Convolution:
  • Rotation:

Classical Image Enhancement

Some basic gray-level transformation:

  • Negative
  • Log
  • Exponential:
  • Gamma Correction (exponential transform with )
  • Contrast Stretching
  • Bit-Plane Representation

Simple enhancement methods:

  • Histogram Equalization: contrast adjustment
  • Histogram Specification (or Histogram Matching)
  • Image Sharpening
    • Frequency domain: some high-pass filters (Butterworth, Gaussian … )
    • Spatial domain: spatial convolution by using gradient operator (Sobel, Laplace … )
  • Image Smoothing
    • Frequency domain: some low-pass filters (Butterworth, Gaussian …)
    • Spatial domain: spatial convolution (average filter, median filter, Multi-frame average … )
  • Pseudo Color: A mapping from gray to color

Classical Image Restoration

Image restoration is different from image enhancement. Though the result of both is the improvement of image quality, the aim of restoration is to find the original image from an exists low-quality image. To restore the original image, we usually want to find the model of image degradation.

A simple model of image degradation can be defined as a linear system

In this system, the degradation function H and additional noise N will affect original image F

Some common noise:

  • Gaussian noise
  • Uniform noise
  • Exponential noise
  • Impulse (salt-and-pepper) noise
  • Rayleigh noise
  • Periodic noise

Spatial domain filtering:

  • only suitable for additional noise
  • some common filter:
    • mean filters: arithmetic mean filter, geometric mean filter, harmonic mean filter, etc.
    • order statistic filters: median filter, max-and-min filters, midpoint filter, etc.
    • adaptive filters

Frequency domain filtering for periodic noise reduction:

  • Band-reject filters
  • Band-pass filters
  • Notch filters

Estimating the degradation function:

It is obvious that to restore the original image, we need the degradation model. In practice, the degradation function can be estimated by image observation, experimentation, modeling, etc. Among them, the modeling method utilizes prior knowledge to construct mathematical model that describe the degradation process.

Here we give an example of modeling method. We know that if there exists relative motion between camera and target objects, the produced image will be blurred, which is called “Motion Blur” phenomenon. Now we can deduce the corresponding degradation function.

Suppose we use a camera to take photos, the exposure time is . the relative motion can be described by the orthogonal two directions, which are defined as and . Now we take a blurry photo as

Use Fourier Transform, we can get the spectrum of as

Now that the spectrum is not related with time t, we can then deduce that

If we define the motion functions as and , then the system function becomes

Hence we can get the final model

Image Geometric Correction:

In practice, the given photo usually tend to be distorted. The aim of Geometric Correction is to eliminate this kind of distortion. The Correction often contain two steps

  • coordinate correction (spatial transformation)
  • intensity (gray value) estimation (gray value interpolation)

The first step, coordinate correction, transfer the input image to output , which means that we should construct a proper relationship between true grid coordinate and input distorted coordinate. The relationship can be represented as a polynomial equation. In this step, we usually choose a set of image control points to guarantee the correction quality.

Since the calculated correction coordinates tend to be float value in the target grid, we execute the second step to get the final output image. The bilinear interpolation is often used in this step, and the warp method is often backward instead of the forward one. The detailed description can be found in this image processing tutorial. Here we give some equations related to this kind of interpolation.

In this picture, P is the point that backward warp produced. To calculate the value of point P, we need to use neighbor red grid points . Now imagine that the image is a 3-D signal f(x,y), we first use 1-D interpolation column wise to calculate the value of and :

The factor is a weight of how much of a mix the output consists of between the two row-line values. Now we can find the value of P by interpolating row wise use and :

Actually, you can find another expression of bilinear interpolation on Wikipedia, they are completely equal.

Digitization in Image Analysis

To analyze digital image, the digital topology and digital geometry mechanism are often used.

There are some kinds of sampling grids:

  • (*) Rectangular grid: widely used, intuitive but having connectivity paradox
  • Triangle grid:
  • Hexagon grid: ,

The sampling points are located at the center of grid cells.

We can define the sampling efficiency by calculating the fraction of area between unit circle and covered cells.

  • Rectangular grid’s efficiency:
  • Triangle grid’s efficiency:
  • Hexagon grid’s efficiency:

The preimages and domain of the digitized set P are defined as:

  • Given a set of discrete points P, a set of consecutive points S that is digitized as P is called a preimage of P
  • The region defined by the union of all possible preimages S is called the domain of P

A suitable digitizing model should have the following characteristics:

  • The digitized result for a nonempty continuous set should be nonempty
  • The digitizing model should be as translation-invariant as possible
  • Given a set P, each of its preimages should be similar under certain criteria

Some common digitizing models:

  • The Square Box Quantization (SBQ)
  • Grid-Intersect Quantization (GIQ)

The Square Box Quantization:

In SBQ, there is a corresponding digitization box for any pixel . A pixel is in the digitized set of preimages if and only if , that is, its corresponding digitizing cell intersects .

The Grid-Intersect Quantization:

Given a thin object formed by continuous points, its intersection with the grid line is a real point . This point may satisfy or depending on that intersects the vertical grid lines or the horizontal grid lines. This point will be mapped to a grid point , where .

Comparison between GIQ and SBQ:

  • GIQ reduces the number of pixels in a digitized set
  • the area of the SBQ domain is smaller than the area of the GIQ domain
  • the shape of the GIQ domain appears to be more appropriate for the description of a curve

Digital Arcs:

In Euclidean geometry, the arc is a part of the curve between two points, while the chord is the straight line connecting any two points on the conic curve. A continuous straight line segment can often be viewed as a special case of an arc.

Given a set of discrete points and the adjacency between them, the digital arc from point p to point q is defined as the arc that satisfies the following conditions:

  • ,

  • , point has exactly two adjacent points in the arc , they are and

  • The endpoint (or ) has exactly one adjacent point in the arc , it is (or )

4-digit arcs or 8-digit arcs can be defined as above, depending on the difference in adjacency.

Digitized set:

Consider the continuous straight line segment in a square grid. Using GIQ, points intersecting the grid lines between are mapped to a set of discrete points . This set is called a digitized set of .

Digital Chords:

The digital arcs can be digital chords. The determination of the digital chord is based on the following principle: Given a digital arc , the distance between the continuous line and the sum of the segments can be measured using the discrete distance function and should not exceed a certain threshold.

It can be proved that given any two discrete points and in an 8-digit arc and any real point in continuous line segment , if there exists a point such that , then satisfies the property of the chord. Similarly, if there exists a point such that , then satisfies the property of the compact chord.

It can be proved that in the 8-digital space, the result of the line digitization is a digital arc that satisfies the properties of the chord. Conversely, if a digital arc satisfies the property of the chord, it is the result of digitizing the line segments.

Distance Transform:

Distance Transform (DT) is a special transform that maps a binary image into a gray-scale image. DT is a global operation, but it can be obtained by local distance computation.

DT computes the distance between a point inside a region and the closest point outside the region. In other words, the DT of a point in a region computes the nearest distance between this point and the boundary of the region. Given a set of points , a subset , and a distance function that satisfies the distance measure properties (e.g. , and ), then .

Given a set of points and one of its subsets , the distance transformation of satisfies some properties:

  • such that the discrete distance transform value at position satisfies the relationship .

  • (Also some other properties )

For the second property, since and are neighbors, is the length of the move between them. Therefore, for any point , the discrete transformation can be described as , where .

To calculate discrete distance map using masks, we consider a binary image of size , and assume the set of its border point is known. The discrete distance map is a matrix, which is denoted as , The value will be calculated iteratively until a stable is reached.

Before iteration () begin, the values of distance are firstly initialized as

Then, for iterations , the mask is positioned at a pixel , and the distance values are propagated from the pixel onto by using the updating formula:

Note that the implementation of this process can be sequential or parallel one.

Classical Image Edge Detection

This sub-section will introduce five kinds of Differential Edge Detector (DED).

Since the edge in an image corresponds to the discontinuity in an image, the differential edge detector is popularly employed to detect edges. The detailed classical edge detection methods can be found here.

Some parameters to describe an edge:

  • location (center): where the maximum gray discontinuity occur
  • direction: the direction across the discontinuity
  • strength (magnitude): the difference along the edge direction
  • mean value: the mean of gray value on edge
  • slope: the degree of tilt on the edge direction

Points which lie on an edge can be detected by:

  • detecting local maxima or minima of the first derivative
  • detecting the zero-crossing of the second derivative

the 1st derivative:

which can be described as a mask [-1 1], or [-1 0 1] (centered about ).

the 2nd derivative:

which can be described as a mask [1 -2 1].

Actually, we usually use gradient to do image edge detection.

The gradient is a vector which has certain magnitude and direction, which is defined as:

Its magnitude and direction:

We can estimate the gradient with finite differences (the 1st difference):

If we let , then the gradient can be written as:

Moreover, we usually use 2nd derivative to do edge detection.

There are two operators in 2D that correspond to the second derivative: Laplacian and Second directional derivative. In this kind of method, we can find the zero-crossing of the second derivative to detect edge points. Similar to gradient method, the 2nd derivative can be estimated by using 2nd differences.

In practice, various kinds of edge detection operator are used to do edge detection:

  • gradient operator (the 1st difference): Roberts, Prewitt, Sobel
  • 2nd derivative (the 2nd difference): Laplacian, Marr
  • optimal operator: Canny
  • non-differential edge operator: SUSAN

In pixel-coordinate notation, corresponds to the direction and to the negative direction. In this way, the 1st differences can be written as:

The mask of them can be and respectively.

Now we are going to see some gradient operator, consider of a grid.

Robert operator:

This approximation can be implemented by the following masks:

Note that the Robert edge detection operator gives the approximation: at , at .

Prewitt and Sobel operator:

Now consider of the arrangement of pixels about the pixel (i,j)

The partial derivatives can be computed as

From this form, we get the Prewitt and Sobel operator:

  • Prewitt c = 1
  • Sobel c = 2

The masks of this type can be implemented as the following masks:

Now let us take a look at the 2nd derivative operator.

The Laplacian:

Laplacian operator is very famous. It is defined as . We can use the 2nd difference to approximate it.

This is a template of mask that has 4-connection. To expand it, we can rotate it by and then add by itself, which produce another type of template which covers 8-neighbor. These two types of masks can be implemented as the following masks:

Some properties of the Laplacian:

  • (*) It is an isotropic operator (rotation has no effect on Laplacian)
  • It is cheaper to implement (one mask only)
  • (*) It does not provide information about edge direction
  • (*) It is more sensitive to noise (differentiates twice)
  • It produce the edge with double pixel wide

Marr operator:

The process of Marr is simple, which is called Laplacian-of-Gaussian (LoG). First, we use Gaussian smoothing (low-pass filter) to remove noise of input image. Then, we calculate Laplacian value by using Laplacian operator. Note that these two steps can be combined together and then provide LoG mask.

The low-pass Gaussian filter is

It can be shown that

hence we deduce the total filter as

The complete derivation of this final LoG form can be found here. Though we can use Mathematica to do this directly by .

Then we can plot it using Mesh (set )

Now let us consider of optimal operator. There are some criteria for optimal edge detection:

  • the optimal detector must minimize the probability of false positives, as well as that of false negatives
  • the edges detected must be as close as possible to the true edges
  • the detector must return one point only for each true edge point

Canny is almost the most widely used edge detector in computer vision. It has shown that the 1st derivative of the Gaussian closely approximates the operator that optimizes the product of signal-to-noise ratio and localization. The process of Canny:

  • Gaussian smoothing
  • Compute the gradient magnitude and direction
  • Apply non-maxima suppression
  • Apply hysteresis thresholding/edge linking

Now we introduce Canny step by step, the detailed introduction can be found in this BLOG.

After Gaussian smoothing, we should compute the gradient of it:

Then we can compute the magnitude image by and direction .

Non-maxima suppression:

  • Broad ridges must be thinned so that only the magnitudes at the points of greatest local change remain
  • All values along the direction of the gradient that are not peak values of a ridge are suppressed
  • Non maximum suppression requires us to divide the grid of pixels into 8 sections

Here we give the explanation of grid division. We know that the 8-connection grid has 4 directions. The edge direction angle is rounded to one of four angles representing vertical, horizontal and the two diagonals (, , and ). An edge direction falling in each color region will be set to a specific angle values.

Double thresholding:

The output of non-maxima suppression still contains the local maxima created by noise, consider of two kinds of threshold:

  • low threshold: some noisy maxima will be accepted too
  • high threshold: true maxima might be missed

For this reason, a more effective scheme is to use two threshold:

  • a low threshold
  • a high threshold
  • usually

Use these two threshold, and we will get two thresholded images and , then we link them into contours:

  • Now we want to link the edges in into contours because there are gaps in this map

  • Look in when a gap is found
  • By judging the 8 neighbors in , gather edge points from until the gap has been bridged to an edge in

After the thresholding, the edge linking is also done!

SUSAN:

The idea of SUSAN edge detector is simple, detailed introduction can be found here. We can find that this method need not to calculate gradient, which is easy to implement. The SUSAN edge finder has been implemented using circular masks to give isotropic responses. The mask is placed at each point in the image and, for each point, the brightness of each pixel within the mask is compared with that of the nucleus, and then determine the comparison by:

where is the position of the nucleus, is the position of any other point within the mask. is the brightness difference threshold, is the output of the comparison.

This process will be done for each pixel in the mask, and a running total of is made by

This total is just the number of pixels in the USAN, which gives the USAN’s area.

Then, is compared with a fixed threshold (the geometric threshold), which is set to . The edge response is then created by using the following rule:

In practice, a more stable and sensible equation to calculate is

Classical Image Segmentation

Formal definition of image segmentation:

A segmentation of the grid for a uniformity prediction is to partition into disjoin non-empty subsets such that:

  • The union of all is the entire :
  • For all and (), it has
  • Every region is a connected component
  • Given a uniform measure , it has and

We mainly concentrate on the following segmentation methods:

  • (*) Thresholding segmentation
  • Region growing
  • Region splitting and merging
  • (*) Watershed transformation
  • Clustering methods
  • (*) Partial Differential Equation (PDE) methods: snake, level-set
  • Graph Cut

The detailed segmentation tutorial can be found here and here.

Thresholding segmentation:

Thresholding is the simplest and most commonly used method of segmentation. Given a single threshold :

This equation describes the simple mechanism of 2-class segmentation. The multi-class version is similar to this.

Actually, thresholding segmentation can be classified into three types:

  • pixel dependent method (global thresholding)
  • region dependent method (local thresholding)
  • coordinate dependent method (dynamic thresholding)

The discussion of thresholding segmentation is mainly about the selection of threshold . I’m not going to show details of these three types of thresholding methods, one can find lots of material about them using Google.

Watershed:

The main goal of watershed segmentation algorithm is to find the “watershed lines” in an image in order to separate the distinct regions. To imagine the pixel values of an image is a 3D topographic chart, where x and y denote the coordinate of a plane, and f(x,y) denotes the height of the point (x,y).

The algorithm starts to pour water in the topographic chart from the lowest basin to the highest peak. In the process, we may detect some peaks disjointed the catchment basins, which is called “dam”.

Before the watershed algorithm, we first calculate the gradient image of original image . Let , denotes the coordinate in the local regional minima of . Denote as the set of coordinates in the catchment basin associated with the position . Let denotes the set of coordinates that

The value is the threshold of gray value.

Now we start the watershed algorithm:

  • Find the minimum and maximum value of as min and max.
  • Assign the coordinate of min into . The topography will be flooded in integer flood increments from n = min+1
  • Compute , which produce a binary image
  • Let , which is the union of the flooded catchment basins at stage n
  • set n = n+1
  • Derive the set of connected components (CC) in denoting as
  • For each connect component , there are three conditions
    • If is empty, is incorporated into to form
    • If contains only one CC, is incorporated into to form
    • If contains more than one CC, find the points of ridge(s) and set them as “dam”
  • Construct , and then set n = n+1
  • Repeat step 6 to 8 until n reaches max+1

The details of watershed can be found here, which is the slides given by Desok Kim.

Active Contour Based Segmentation:

This kind of method is very famous, which utilizes partial differential equation to find contours of objects. I’m not going to explain the detailed algorithm in this article, but written another one, which contains the explanation about some classical active contour methods (e.g. Snake and Level-Set). Here and here are some good materials.

The advantages of active contour based methods:

  • easier to describe objects
  • sub-pixel precision
  • easier to combine various of information (e.g. prior, motion information)
  • utilize strong mathematical tools: PDE, calculus of variations, etc.

Graph Cuts:

Segmentation with Graph Cuts is another interesting method. The goal is to segment the main objects out of an image. A graph-based approach makes use of efficient solutions of the max-flow/min-cut problem between source and sink nodes in directed graphs. Here is a tutorial about this method.