Connected Component Labelling


Pixel neighbourhoods and connectedness

Series: Connected Component Labelling:

  1. Pixel neighbourhoods and connectedness
  2. Connected Component Labelling
  3. Labelling connected components - Example

The idea of neighbourhoods of pixels and their connectedness is quite intuitive. But formalizing it's definition and knowing what it means "exactly" has its advantages. So here are the things you need to know about neighbourhoods and connectedness of pixels in an image.

What is a neighbourhood?

The neighbourhood of a pixel is the set of pixels that touch it. Simple as that. Thus, the neighbourhood of a pixel can have a maximum of 8 pixels (images are always considered 2D).

The orange pixels form the neighbourhood of the pixel 'p'.

Neighbourhoods of more specific nature exist for various applications. Here's a list of them:

4-neighbourhood

The neighbourhood consisting of only the pixels directly touching. That is, the pixel above, below, to the left and right for the 4-neighbourhood of a particular pixel.

Here, the orange pixels for the 4-neighbourhood of the pixel 'p'.

d-neighbourhood

This neighbourhood consists of those pixels that do not touch it, or they touch the corners. That is, the diagonal pixels.

The diagonal neighbourhood of the pixel 'p' is shown in orange.

8-neighbourhood

This is the union of the 4-neighbourhood and the d-neighbourhood. It is the maximuim possible neighbourhood that a pixel can have.

The 8 neighborhood

Connectivity

Two pixels are said to be "connected" if they belong to the neighbourhood of each other.

Connectivity of pixels

All the coloured pixels are "connected" to 'p'... or, they are 8-connected to p. However, only the green ones are '4-connected to p. And the orange ones are d-connected to p.

Now, if you have several pixels, they are said to be connected if there is some "chain-of-connection" between any two pixels.

Multiple connectivity

Here, lets say you're "bunch" or set of pixels is the white ones. Then, the pixels p1 and p2 are connected. There exists a chain of pixels which are connected to each other. However, the pixels p1 and p3 are not connected. The black pixels (which are not in your set) block the connectivity.

Connected components

Taking the idea of connectivity to the next level, we get to the idea of connected components. A graphic best serves to explain this idea:

Connected components

This image has two connected components. And these exist efficient algorithms that let you figure out the different connected components in an image easily.


More in the series

This tutorial is part of a series called Connected Component Labelling:

  1. Pixel neighbourhoods and connectedness
  2. Connected Component Labelling
  3. Labelling connected components - Example



OpenCV 3 Blueprints

Learn how to identify face expressions, fingerprints, setup automated camera traps, stabilize mobile video with gyroscopes and use the Android NDK

The book is packed with the fundamentals of computer vision and will get you started on just the right track.

Learn more about the book

Utkarsh Sinha created AI Shack in 2010 and has since been working on computer vision and related fields. He is currently at Carnegie Mellon University studying computer vision.