# Normalized Cuts and Image Segmentation J. Shi and J. Indian Institute of Science, Bangalore....

date post

05-Oct-2020Category

## Documents

view

0download

0

Embed Size (px)

### Transcript of Normalized Cuts and Image Segmentation J. Shi and J. Indian Institute of Science, Bangalore....

Image Registration

Soma Biswas

Department of Electrical Engineering,

Indian Institute of Science, Bangalore.

Definition

Registration is the determination of a geometrical

transformation that aligns points in one view of an object

with corresponding points in another view of that object

Applications:

Mosaicing: Align several images into a single

composition that represents part of a 3D scene, eg.

remote sensed images

Build 3D Model from Images

Medical Images: Combine the two registered

images by producing a reoriented version of one

view that can be “fused” with the other.

2 MR

SPECT registered

Transformation

3

Relates the position of features in two images

Rigid

translations and rotations

preserve all distances

Preserve the straightness of lines and all nonzero angles between straight lines

Affine

Also allows scaling and shearing

Preserves the straightness of lines

Allows angles between lines to change

curved

Allows the mapping of straight lines to curves

perspective

The parallelism of lines need not be preserved

Registration algorithms

4

Method used to find the transformation

Landmark based

Intensity based

Information theory based

Registration using basis functions

Registration using splines

Physics based

Elastic, Fluid, Optical flow, etc.

Point/Landmark based

5

Identifying corresponding points in the images and inferring the image transformation

Types of landmarks

Extrinsic

artificial objects attached to the patient

Intrinsic

internal anatomical structures: fiducial points,

To be reliable, they must lie in clearly discernible features, (fiducial features)

Displacement in the determination of the fiducial point - fiducial localization error (FLE).

The transformation that aligns the corresponding fiducial points will then interpolate the

mapping from these points to other points in the views

Computing the average or “centroid” of each set of points translation

Rotated this point set about the new centroid until the sum of the squared distances between each corresponding point pair is minimized

Point-based Method

6

fiducial registration error

Point-based, rigid registration

7

Point-based, registration – with scaling

8

Point-based registration: Nonisotropic scaling

9

Surface-based

10

Method

Extracting corresponding surfaces

Computing the transformation by minimizing some measure of

distance between the two surfaces

Algorithms used

The “Head and Hat” Algorithm

The Iterative Closest Point Algorithm

Registration using crest lines

Disparity Functions

Search for the transformation that minimizes some disparity function or metric

between the two surfaces X and Y

Distance between two feature sets A and B is normally defined as the minimum

distance between a point in A and a point in B

d(A,B) is small if one pair of points in these two sets are close

Hausdorff distance from A to B

11

12

13

14

ICP

15

Insights

16

Details

17

assume closest points correspond

Algorithm

18

Init the error to ∞

Calculate correspondence

Calculate alignment

Apply alignment

Update error

If error > threshold

Intensity Based Method

Calculates a transformation between two images using the pixel values alone.

Registration transformation is determined by iteratively optimizing some “similarity

measure” calculated from all pixel values.

Reference Image: A

Target Image: B is iteratively transformed to

Similarity measures are invariably calculated for the set of pixels in the overlapping

region which is a function of T and so changes with iteration

Similarity Measures: Image Subtraction

If images being registered are identical, except for misalignment

SSD = 0, for correct registration, and will increase with registration error

If A and B differ only by Gaussian noise, SSD is the optimal measure

Eg. Serial registration of MR images, images identical except for small changes due to

disease progression or response to treatment

Problems: non-gaussian noise, if small number of pixel intensity change by large

amount

19

Similarity Measure

Intensities in images A and B are linearly related, CC can be shown to the ideal

similarity measure

20

Similarity Measure

Ratio-Image Uniformity (RIU): initially devised for registration of multiple PET

images of the same subject

For each estimate of the registration transformation, a ratio image R s calculated

R: divide each pixel in A by each pixel in B’.

Uniformity determined by calculating normalized std of R

Algorithm iteratively determines the transformation T that minimizes the normalized

std, i.e. maximizes uniformity

21

Joint Histogram

n-dim, n is the number of images used to generate it

Axis is intensity in each image

Value at each point: no. of pixels with that combination of intensities

Joint histogram normalized: estimate of joint probability distribution function (pdf) of

intensities in the n images

22

23

Joint Entropy

Shannon entropy widely used as a measure of information

Describes the average information supplied by a set of symbols {s} whose

probabilities are given by {p(s)}

If all symbols s have equal probability, then entropy will be at maximum.

If one symbol has a probability of 1 and all others have a probability of zero, then

entropy will have a minimum value.

Images correctly aligned -> joint histograms have tight clusters, surrounded by large

dark regions -> clusters disperse as the images become less well registered.

Tight clusters in the histograms represent a small number of symbols s having high

probabilities P(s) & Surrounding dark regions in the joint histogram represent

large numbers of symbols with probability zero.

- As the clusters disperse, the high intensity regions of the joint histogram become less

intense, and previously dark regions in the histograms become brighter

Misregistration results in an increase in histogram entropy.

Entropy of the PDF calculated from images A and B’ should be iteratively minimized

to register these images

24

25

*View more*