# Presentation: 486425

## HPM – A Humanlike Automatic Landmarking Algorithm

- Sam Chen
- 11/19/08

## Seminar

**Seminar** is, generally, a form of _[academic](http://en.wikipedia.org/wiki/Academic)__ instruction, either at a __[university](http://en.wikipedia.org/wiki/University)__ or offered by a commercial or professional organization. It has the function of bringing together small groups for recurring meetings, focusing each time on some particular subject, in which _everyone present is requested to actively participate. This is often accomplished through an ongoing _[Socratic dialogue](http://en.wikipedia.org/wiki/Socratic_method)__ with a seminar leader or instructor, or through a more formal presentation of research. _

## Why Need Landmarking

- To provide feedback information on INR accuracy to control system
- To verify if the system meets INR requirements

## Why Humanlike?

- Human eye/brain system is the best image processing system.  It automatically adjusts to changes in intensity, color, texture to identify land and sea.  It uses global information instead of local only.  In practice, when RPM autolandmarking fails to work, human operator sometimes can still perform landmarking successfully

## How to Landmark?

- By aligning a template with certain known features such as land/sea boundary, bright spots etc. to their corresponding party in the image

## How to align?

- Usually use a maximization process by moving the landmark template to the location such that a function defined by the template and the corresponding image part (meaning under the template) takes maximum value, i.e., they match each other.

## What Functions to Use?

- Because we are matching two features (in digital world two vectors) we can use normalized cross correlation or cross covariance
- The definitions are slightly different from those in statistics

## Definition of Normalized Cross Correlation

- For two vectors u and v, their (non-centered) normalized cross correlation is the inner product of u and v divided by the L2 norm of u and the L2 norm of v
- Geometrically, it is the cosine of the angle between the two vectors – when the two vectors are parallel, their normalized cross correlation = 1.

## Definition of Cross Covariance

- Only the inner product in the numerator

## Example of Correlation Maximization matching

- Assume we have a landmark template
-    1  2  and an image  4  8  8  8
-    1  1                          4  8  8  8
-                                    4  4  8  8
-                                    4  4  8  8
-    where is the match?
-     4*(1 2 1 1) = (4 8 4 4)

## Underlying Assumption for Image Correlation Maximization

- The feature image does not change over time
- 1 2  will not match 2 3 3 3
-    1 1                         2 3 3 3
-                                  2 2 3 3
-                                  2 2 3 3
-    exactly (normalized cross correlation will never be 1)

## Advantage and Disadvantage of Normalized Correlation Maximization

- It is a real pattern matching – the two vectors must be close to parallel.  Bright spots will reduce the match
- Landmark template must from real image but illumination may change by season and time of the day
- If we only have map based landmark templates, they will not correlate to image well leading to wrong location

## Underlying Assumption for Cross Covariance Maximization

- Coastline has the highest overall contrast

## Advantage and Disadvantage of Cross Covariance Maximization

- It can use segments of coastline from map without intensity as templates
- Because it maximizes the sum of intensity, edge of bright spots becomes attractors.  In order to remove such bright spots, elaborate cloud detection algorithm needs to be introduced.  However, that algorithm needs good attitude.  Which comes first? Chicken or Egg?

## What are The Key Considerations of This Algorithm

- Human eyes examines the whole image to get an idea what looks like land and what looks like sea before determining locally the land/sea boundary
- There are three and only three different pixels: land, sea, cloud (can not see through)
- Human defines a cloud pixel as one which blocks the view of land or sea.  If the pixel looks like a land pixel, it is a land pixel.  Human PM operator does not care about scientific definition of cloud
- Coastline is long and connected

## Histogram Clustering

- Calculate histogram of neighborhood image
- Find peaks and valleys of the histogram
- Three clusters only
- Set pixels between two valleys to intensity at the peaks
- All pixels beyond the second valley are to be treated as cloud pixels

## Find Coastline (Edge Detection)

- Differentiate the three-intensity image using Sobel Operator to get a Sobel image
- Set all cloud pixels and their immediate neighbors to intensity zero
- Using a threshold to make the Sobel image a 0/1 image
- Clean up the image (to be discussed later)

## Correlation

- Correlate digital chip (a 0/1 image to be defined later) with the 0/1 Sobel image chip          image
-    0 0 1         0 0 0 0 1 0
-    0 0 1         0 0 0 0 1 0
-    1 1 1         0 0 1 1 0 1
-                     0 1 0 0 0 0
-                     0 1 0 0 0 0

## Definition of Digital Chip

- A landmark template of coastline from a map is a set of vectors connecting base points
- The template is laid on top of an image according to navigation information
- Set any pixel containing one or more points from the template as 1 and set the rest to zero
- This creates a digital chip

## Subpixel Accuracy 

- After correlating digital chip to 0/1 Sobel image, one can only get accuracy at line/pixel level
- We need to overcome digitization error when generating digital chip

## Interpolation NOT Recommended

- The image data is not smooth
- The Sobel image, which is the derivative of a discontinuous function with sharp peaks, is not suitable for interpolation

## Perturbation to The RescueAn Example

- Suppose that you have a digital voltmeter with a resolution of 1 v
- You want to measure a DC voltage of 10.3 v accurately
- You add a sequence of perturbations to the voltage you want to measure and get a sequence of results: 10, 10, 11,10, 10, ...
- You average the results

## Perturbation in HPM

- After laying landmark template to image according to navigation information, perturb the location by fractional line and pixel
- Use the same way to create a digital chip which may or may not be the same as the original one
- The number of different chips are small (compare to the number of perturbations)

## Perturbation in HPM

- Calculate correlation for each different digital chip
- Average over the number of perturbations to get subpixel accuracy
- Perturbation can be a uniformly distributed random number from -1 to 1 or deterministic -1, -0.9, -0.8,...

## Some test Results

- Original image
- Sobel image
- Histogram
- Segmented image
- Sobel of segmented image

## Original image

## Sobel Image

## Histogram

## DefuziedImage

## Sobel from DefuziedImage

## What’s Next

- Test on images with more clouds and those current RPM will misidentify
- Test other channels
- Improve histogram segmentation algorithm
- Write codes to eliminate small closed curves on the right side using topological methods.