Monday, December 8, 2014

Analyze: Pixel connectivity



In a previous post [Link], we were able to measure a distance between two points or the length of a sample by counting the number of pixels thanks to Analyze > Analyze Particles... . However, the result is directly dependent of the pixel connectivity...

1- How is a line drawn ?

Drawing a line with a computer consists of converting the formula f(x)=a *x + b  (a function existing in a continuous/analog world) in a set of pixels (a discrete system) leading to an approximation of the drawing line as shown in Fig. 1.

Fig.1: The red line drawn between the two red points is converted in a series of black pixels in an image Thus, this is only an approximation of the red line.

The way the pixels series is drawn influences the line path. In Fig.1, adjacent pixels are connected by their edges or by their corners. This type of connectivity is called "chessboard" or 8-connectivity corresponding to the move of the king in chess.

Fig.2: 4-connectivity

In Fig.2, the pixels are only connected by their edges. This is a "Manhattan","city-block", "North-South-East-West", or 4-connectivity. This is summarized in Fig. 3.

The main parameter is the pixel connectivity which can be 4, 8, or mixed.

[TODO]
Fig 3: 4-, 8-, and mixed-connectivity.

Note: The Bresenham algorithm [Wikipedia] is one of the drawing algorithms.
Depending of the pixel connectivity used in the drawing algorithm, the number of pixels required to go from the starting point A(0,0) to the end point B(20,5) is different.

Euclidean distance: sqrt( (20-0)^2+(5-0)^2) = 20.61
8-connectivity: 21 pixels
4-connectivity: 26 pixels

The 8-connectivity system gives a good estimation of length in our example especially because the line is short. However, for longer distances, it will underestimate the real length...

Note: In mathematics,
The euclidean distance corresponds to the L2 norm of the vector AB.
  • D = ( x 0 - x 1 ) 2 + ( y 0 - y 1 ) 2
In 4-connectivity [Wikipedia], the distance - L1-norm -  is equal to:
  • D = |x0 – x1| + |y0 - y1|
In 8-connectivity [Wikipedia], the formula is:
  • D = max(|x0 – x1|,|y0 - y1|)


Now, the question is:
How can we weight the pixel count to get a good evaluation of the length?

<<  TOC : PreviousNext: Weighting factors >>

2. Other crazybiocomputing posts

Further readings are available in ...
  • Analysis Series  [Link]
  • Image Processing TOC [Link]

No comments:

Post a Comment