UoL CS Notes
Menu

Shapes & Connectivity

ELEC319 Lectures

Pixels, Neighbours & Connectivity

$N_4$ Connectivity
Each pixel has 4 pixels directly around it.
$N_8$ Connectivity
This includes diagonally adjacent pixels, so all pixels surrounding a pixel.

Structuring Element

This is a mask that can be used to define pixel neighbours:

  • It is a small matrix of odd index.
  • 1s in the matrix define pixels that are neighbours.

This type of structuring element is called flat.

  • SEs don’t have to be square.
  • SEs don’t have to be symmetrical.
  • Non-flat SEs contain values that are non-binary.

Structuring Element Uses

They are used to probe large images for specific shapes:

  • Therefore you should choose a SEs template to match the shape you want to find in the main image.

The size of the SE determines the detection scale:

  • Smaller SE size, will discover more small features.

Distance Between Two Pixels

Given two pixels $p=(x_1,y_1)$ and $p_2(x_2,y_2)$:

  • Chessboard distance:

    \[\max(\lvert x_1-x_2\rvert, \lvert y_1-y_2\rvert)\]

  • Cityblock Distance (Manhattan Distance):

    \[\lvert x_1-x_2\rvert+\lvert y_1-y_2\rvert\]

    This assumes 8-connectivity.

  • Euclidean Distance

    \[\sqrt{(x_1-x_2)^2(y_1-y_2)^2}\]

Distance Transform

For this transform we calculate:

  • The distance between each pixel not in the SE mask and the nearest pixel in the mask.

Connected Component Labelling

This is also known as region extraction. The idea is to:

  1. Group pixels into components based on pixel connectivity.
    • All pixels in a connected component share the same pixel intensity.
    • This could be $N_4$ or $N_8$.
  2. Label each pixel with a colour or greyscale.

Two-Pass Equivalence Class Resolution

This is a two-pass algorithm:

  1. Scan the image (row-wise or column-wise), one pixel at a time:
    1. When encountering a foreground pixel, look at the previously scanned, neighbour pixels (with 8-connectivity):
      • If any of the neighbours have a label assigned, assign the same label to the pixel.
      • If neighbouring pixels have more than one labels assigned, pick one arbitrarily.
      • Otherwise, assign a new label.
    2. Every time a label is added, add that label to the equivalence table as a new row.
    3. If two neighbouring pixels represent the same region, add them to the same row.
    4. Continue until all pixels are covered.
  2. Assign new labels for the rows of the equivalence table:
    1. Scan the image pixel-by-pixel again, new labels to consolidate existing labels.

Shapes

A shape is an image region that can be defined using a set of finite boundary points.

Geometrical Features

The geometry of a region can be characterised in many ways:

Area
The number of pixels covered by the region.
Centroid
The position of the geometrical centre of the region
Major/Minor Axis
The length of the major/minor axis of an ellipse that has the same second moments as the region.
Eccentricity
The eccentricity of the ellipse is the ratio of the distance between the foci of the ellipse and its major axis.
Orientation
The orientation of the ellipse.
Euler Number
The number of holes within the region
Inscribed Radius
The radius of the largest cirlce that is contained by the region
Circumscribed Radius
The radius of the smallest circle that contains the region.

Some features that are dependent of a regions distribution of intensity are:

Centre of Mass
The position of the centre of the region.
  • Weighted by the intensities of the pixels.
  • Often the centre of mass’s displacement from the centroid is of interest.
Image Moments (Statistical)
Mean, variance, skewness.

We can define types of shapes by using correlations between these features.