Computer Vision : Part 2

Perceptual psychologists have spent decades trying to understand how the human visual system works and many research work have been published in this area. Just like how we humans perceive the three-dimensional structure of the world around us with the help of Eye + Brain, a computer vision algorithm today which is based on how a (human eye + Brain) works can perceive and interpret any 3 dimensional image.

Many scientist have utilised the way human eye + brain works and have applied the same theory to satellite imagery analysis which cannot be perceived by human eye. Eg. Satellite imagery, radar scans, medical scans, multi-spectral images.

As seen in the previous post - the image data is first saved in geometrical shapes that can be easily understood by the computer and then it is processed and optimised for better quality.

Once the image is optimized “Feature detection and matching” is performed on the data.

“Feature detection and matching” is an essential component of computer vision algorithm which we will explore in detail today.

Feature Detection and matching  can be grouped into the following 3 steps:

          

Feature Key Points and Patches: The first kind of feature that you may notice (in the below picture) 

are specific locations in the images, such as mountain peaks, building corners, doorways, or

interestingly shaped patches of snow ( as seen below) These kinds of localized feature are often called 

key point features or interest points (or even corners) and are often described by the appearance

of patches of pixels surrounding the point location

Feature Edges: Statistically speaking edges occur at boundaries between regions of different colour. 

Edges are derived after locating the key feature points.

  Straight lines: Edges are then grouped into longer curves and straight line segments, which can
  be directly matched or analysed to find vanishing points

Now lets examine each step in great detail:

Feature Key Points and Patches:

As seen below there are  4 steps under feature key points and patches.

Feature Detection:  Discovering or finding feature / image locations that can help you reliably find correspondence with other images is called as Feature Detection.

Outline of Algorithm of “Feature Detection” from the book.
Reference : http://szeliski.org/Book/drafts/SzeliskiBook_20100903_draft.pdf

1. For comparing two image patches, i.e., their (weighted) summed square difference should be estimated.

Where I0 and I1 are the two images being compared, u = (u; v) is the displacement vector,
Variation in position of image = u

2. When performing feature detection, we do not know which other image locations the

Feature will end up being matched against. Therefore, we can only compute how stable this

Metric is with respect to small variations in its position _u by comparing an image patch against

Itself, which is known as an auto-correlation function or auto-correlation surface

Variation in position = u

3. Approximation of Auto correlation surfaces using Taylor series expansion

4. There will be uncertainties in the auto-correlation surface matrix. While Anandan and Lucas and Kanade (1981) were the first to analyse the uncertainty structure of the auto-correlation matrix,

Forstner (1986) and Harris and Stephens. (1988) were the first to propose using local maxima in rotationally invariant scalar measures derived from the auto-correlation matrix to locate key points for the purpose of sparse feature matching.

Find local maxima above a certain threshold and report them as detected feature.

Feature Description:

After detecting features (key points), we must determine which Features come from corresponding locations in different images.

What does the Feature descriptors do?

     1.The local motion around each feature point detected is estimated, simple error Matrix like sum of squared differences is calculated to adjust inaccuracies.

     2. Help in stitching images together

4 Types of feature descriptors:

To read more about the mathematics of the 4 types of feature detectors I would recommend the same book

Reference of the post is from the below book

http://szeliski.org/Book/drafts/SzeliskiBook_20100903_draft.pdf

Feature Matching:

1.Once the features are extracted and their descriptors are identified, the next step is to establish feature matches between the images.
2.Select a matching strategy
 3.Devise efficient data structures and algorithms to perform matching as quickly as possible

Select a matching strategy: This depend on the context in which the matching is being performed.

If we are matching features of 2 images that are overlapping it is easy for us to match the features, but it is difficult to do the same when images are in a clutter.

Euclidean distance is used for matching. The simplest matching strategy is to set a threshold (maximum distance) and to return all matches from other images within the threshold. A threshold that is too high can result in false positives and a threshold that is small can result in false negatives.

Feature Tracking

Finding features in all candidate images and then matching them to corresponding location in subsequent images is a long process.

If the features are being tracked over longer sequences, their appearances can undergo vast changes. You then have to decide if you have to continue matching against originally detected patch or re-sample each subsequent frame at the matching location. This is a complicated process.

In order to fix this issue Shi and Tomasi (1994) have come up with Affine Motion Model for feature tracking.

Shi and Tomasi (1994) first compare patches in neighbouring frames using a translational model and then use the location estimates produced by this step to initialize an affine registration between the patch in the current frame and the base frame where a feature was first detected.

Edges:

Qualitatively, edges occur at boundaries between regions of different colour, intensity, or

Texture.

A reasonable mathematical approach is to define an edge as a location of rapid intensity variation.

Think of an image as a height field. On such a surface, edges occur at locations of steep slopes, or equivalently, in regions of closely packed contour lines (on a Topographic map).

Unfortunately taking derivate created noise in the data

Gaussian is the only separable circularly symmetric filter and hence today Gaussian model is used by several edge detecting algorithms.

Convolution of the image using horizontal and vertical derivatives using Gaussian kernel function

Edge detection methods: As seen below there are 3 methods of edge detection.

Scale selection and blur estimation: example

Combined edge detection: example

Edge Linking:

After detecting edges they can be linked into chains and straight lines.

From the above figure it is very clear that a lot of data scientist have worked really hard to make the machine think like a human being.

Lines

Approximation of the curve obtained above by extracting linear descriptions from the curve

Approximating the curve as a poly line.

There are 4 types of approximating algorithm.

Finally the Image feature is now recognized and detected !
The next step is Image segmentation which we will cover in my next post!