Feng Jin, Huaxiang Lu

Peak Analysis of Grayscale Image: Algorithm and Application

Peak Analysis of Grayscale Image:

Algorithm and Application

Jin Feng1, Huaxiang Lu1

1 Institute of Semiconductor, Chinese Academy of Sciences,
P.O. box 912, Haidian District, Beijing 100083, China
{jinfeng, luhx}@red.semi.ac.cn

Abstract
Considered as topographic reliefs, grayscale images can be decomposed into a number of peaks
that can be stored in the data structure of a tree. This decomposition is called the peak analysis
of grayscale images in this paper. Its mathematical definition and its fast algorithm based on
the watershed transform are both presented. Due to its intuitive definition, there is a wide range
of applications for the peak analysis. One of them is to measure the quantum dots in the AFM
photos. The segmentation result proves to be very accurate and insensitive to noise to some
degree.

1 Introduction

By using mathematical morphology methods, grayscale images can be decomposed

into a tree structure. The tree representation of the original image can greatly facilitate
the analysis of the image, including the aspects of image filter, image segmentation,
pattern recognition and so on.
Jones [2] constructs a binary component tree (BCT) whose nodes correspond to
connected components of the level sets of an image, linked by inclusion between
successive levels. Then a filter is defined to decide if a node on the tree should be
removed or preserved, according to the so-called attribute signature extracted from
the branch containing the node. In virtue of the new filter, a new method of image
segmentation is presented.
Braga-Neto and Goutsias [3] first presents the notion of the level-k connectivity of
a grayscale image and thus the level-k connected components of a gray level image.
By iteratively extracting the connected components of the grayscale image with in-
creasing value of k, a tree of connected components can be constructed. The authors
refer this structure as grayscale component tree (GCT).
The two preceding trees are different in the content of their nodes, one with binary
components whereas the other with gray level components. However, they are iso-
morphic [3]. Notice that the so-called GCT is actually a kind of binary decomposition.
Therefore the depth of both trees generally equals the image gray level (e.g., 256).
In this paper, we propose a new notion of grayscale image decomposition. We use
the peaks (or connected gray level images) as the basis of the deposition, and link the
peaks to form a tree according to the inclusion of the nonzero domain of the peaks.
The constructed tree is essentially a gray level decomposition of the image, com-

24
International Journal of Information Technology, Vol. 12 No. 2 2006

pletely distinct from the BCT and GCT. Therefore the constructed tree is not isomor-
phic with the already-existing trees and the depth of the tree is much smaller (typi-
cally 6-7).
The paper is organized as follows. The basic concepts of the peak, peak analysis
and peak tree construction will be detailed in Section II. In Section III, the fast algo-
rithm of peak analysis based on Watershed Transform is proposed. In Section IV, we
discuss the application of peak analysis on the measure of the quantum dots on atomic
force microscopy (AFM) photos, especially focusing on some problems during the
post process of each peak and in the search of the tree.

2 Peak Analysis

This section is comprised with three parts. First, some basic concepts are introduced.
After that the definition of Peak Analysis of the graylevel image is presented. And the
data structure storing the peaks is proposed in the third part.

2.1 Definition of Peak

First we need the following basic concepts and definitions in image processing and
mathematical morphology:
1) Grayscale image f: Ζ 2 → ℜ ,where Z is the set of integers while R the set of
real numbers. And let FUN denote the set of all the grayscale images.
{ }
2) The binary adjacency relative Γ ⊂ ( Z 2 , Z 2 ) of the elements on the definition
domain of f, namely if two points x1, x 2 are adjacent ⇔ (x1, x 2) ∈ Γ . In addi-
tion if two region E1 , E2 are adjacent ⇔ ∃x1 ∈ E1 , x 2 ∈ E 2 , x1,x2 are adja-
cent.
3) Level set of grayscale image f at the height of h ∈ ℜ :
{ }
LS h ( f ) = x ∈ Ζ 2 | f ( x ) ≥ h
4) Region E ⊂ Ζ is connected ⇔ ∀x ∈ Ε, ∀y ∈ Ε , ∃a path p ⊂ E , p connects
2

x and y.
5) Connected components. ∀X ⊂ Ζ 2 ∃Y1 , Y2 , Y3 ,... ⇒ X = ∪Yi where ∀i, Yi is a
connected region, and ∀j ≠ i , Yi and Y j are not adjacent. Yi are the connected
components of X.
6) Reconstruction. ∀E ⊂ X , the reconstruction of X from E is
REC X (E ) = ∪Yk ,where Yk is the connected component of X, and Yk ∩ E ≠ Φ .
7) Grayscale image f ∈ FUN is a peak ⇔ ∀t1 , t2 ∈ ℜ, t1 < t2 →
LSt1 ( f ), LSt 2 ( f ) are both connected regions, and LSt1 ( f ) ⊇ LSt 2 ( f ) .
Fig 1 and Fig 2 show two examples of peaks. In Fig 1, (a) is the 3D view of the
grayscale image, (b) is its profile. From (c) we can find that after the peak 1 and 2

25
Feng Jin, Huaxiang Lu
Peak Analysis of Grayscale Image: Algorithm and Application

were cut off from the original image, the residual plateau was also a peak. Therefore
this grayscale image contains three peaks in all. Fig 2 illustrates a volcano, which is
just a single peak according to the definition of the peak, as shown in Fig 2(c).

(a) (b) (c)

Fig 1 Grayscale image containing three peaks. (a) is the 3D view; (b) is its profile view; (c)
decomposition of (a) into peaks

(a) (b) (c)

Fig 2 Volcano peak. (a) is the 3D view of the volcano; (b) is its profile view; (c) shows that the
whole volcano contains only one peak

2.2 Peak Analysis of Grayscale Images

First we need the following definitions:

Def I: Regional maximum. Connected region E is the regional maximum of gray-
scale image f ⇔ (1) ∃h, ∀x ∈ E , f ( x) = h ; (2) ∀x ∈ Ζ 2 , x ∉ E , ∃y ∈ E , and x,y are
adjacent → f ( x) < f ( y )
Def II: Top hat peak. Let RM(f) denote the set of all the regional maximum of
f. ∀Ei ∈ RM ( f ) , then we can derive that:

{ }
∃hmin = inf h | ∀E j ∈ RM ( f ), j ≠ i, → E j ∉ REC LS h ( f ) ( Ei ) (1)
Let grayscale image fi be defined as:
⎧ f ( x) − hmin x ∈ RECLS h ( f ) ( Ei )
fi ( x) = ⎨
⎩ 0 others
It can be easily seen that fi is a peak. Therefore we call fi the top hat peak of f below
the regional maximum Ei. And we denote the set of all the top hat peaks of f as TP(f).

26
International Journal of Information Technology, Vol. 12 No. 2 2006

Def III: Peak Analysis. Peak Analysis is defined as the process of the iterative ex-
traction of TP(f) from f until it contains no top hat peaks. Following is the description
of the process:
Peak Analysis(f)
Let t=1; f (1) = f ;
While f (t ) ≠ CONSTANT
Extract TP ( f (t ) ) ,
rewrite it as TP (t ) ( f ) for simplicity.
f (t +1) = f (t ) − ∑ f i (t ) , where f i(t ) ∈ TP (t ) ( f )
i
t = t + 1;
end while;
end.
Finally we denote PA( f ) = ∪TP (t ) ( f ) , which is right the Peak Analysis of f.

2.3 Tree Representation of Peak Analysis

First we need the following definition:

1) The non-zero domain of grayscale image f: NZD ( f ) = {x ∈ Ζ 2 | f ( x) > 0}
∀ Grayscale image f, PA( f ) its Peak Analysis, which has the following properties:
1) f = ∑∑ f i(t ) ,where f i(t ) ∈ TP (t ) ( f ) ,
t i

2) ∀t , ∀i, j , i ≠ j → NZD ( f i(t ) ) ∩ NZD( f j(t ) ) = Φ ,

3) ∀t1 , t 2 , t1 < t 2 , ∀i , j , NZD ( f i(t1 ) ) ∩ NZD ( f i(t 2 ) ) ≠ Φ →
NZD ( f i(t1 ) ) ⊂ NZD ( f i(t 2 ) ),
Therefore the peak analysis of a grayscale image can be naturally represented by a
tree structure, on which whether Node A is the parent of Node B depends on whether
NZD(A) contains NZD(B) immediately. Here Containing immediately means if
NZD ( f i(t1 ) ) ⊂ NZD ( f j(t 2 ) ) , then
~( ∃t3 , k , NZD ( f i(t1 ) ) ⊂ NZD ( f k(t 3 ) ) ⊂ NZD ( f j(t 2 ) ) , where t1 < t3 < t2 ).
Fig 3 is an example of Peak Analysis. For the sake of simplicity, the grayscale image
is shown as a 1D function. Fig 3(a) is the original pattern, and Fig 3(b) shows the
decomposed peaks of 3(a). And the tree constructed from the Peak Analysis is shown
in Fig 3(c), where nodes on the same horizontal line t are extracted at the same step t
of the analysis, namely belonging to TP(t).

27
Feng Jin, Huaxiang Lu
Peak Analysis of Grayscale Image: Algorithm and Application

(a) (b) (c)

Fig 3 An example of Peak Analysis. (a) 1D profile of the original image; (b) its peaks; (c) the
tree to store the result of the analyzed peaks

3. Algorithm to Extract the Top Hat Peak

It is quit difficult to design the algorithm of Peak Analysis based on its definition.
The Watershed Transform, however, is proved to be suitable for solving this problem.
In this section, we will briefly introduce the Watershed Transform, on which we will
design our implementation algorithm of Peak Analysis.

3.1 Watershed Transform

Watershed Transform was first proposed in 1979[4] and soon becomes a widely used
technology in image segmentation [5]. Its basic notion derives from the concepts of
Catchment basins and watershed from topography. The most famous example is the
great divide in America [1]. When a raindrop falls on the east of the divide, it will
finally flow to the Atlantic; on the west, to the Pacific. Taken a grayscale image as a
topographic relief, Watershed Transform converges the positions from where a rain-
drop will flow to the same valley into the same region (Catchment basins), while the
lines where Catchment basins touch each other are called the watershed, see Fig 4
from [1].

Fig 4 Minimum, Watershed and Catchment basin

28
International Journal of Information Technology, Vol. 12 No. 2 2006

Since our purpose is to segment the peak, we need to apply watershed transform to
the grayscale image –f, resulting in the Catchment basins {CB1, CB2, ….} and the
region of the watershed WS. In addition, Let’s denote
∂CBi = {x ∈ WS | x is adjacent to CBi } ,
namely the watershed surrounding the CBi.
Therefore we can reach the following conclusions:
1) ∀ CBi, there is only one regional maximum of f in CBi, denoted as RMAXi. That is
to say, if limited in CBi, f is a peak.
2) ∀CBi , let hi = max{ f ( x) | x ∈ ∂CBi } , ∀h ,
if h ≥ hi ,then ∀RMAX j , j ≠ i, RMAX j ∉ REC LSh ( f ) ( RMAX i ) ;
if h < hi ,then ∃RMAX j , j ≠ i, RMAX j ∈ REC LSh ( f ) ( RMAX i ) .
That is to say that hi is the height at which the top hat peak corresponding to the re-
gional maximum RMAXi should be cut off. Therefore we can extract this top hat peak
according to the height hi and obtain the following algorithm for top hat peak extrac-
tion.

3.2 Algorithm for Top Hat Peak Extraction

Let f denote the grayscale image. The algorithm for top hat peak extraction can be
written as follows:
Hat Peak Extract (f)
Apply Watershed Transform to the –f to attain {CBi}
and WS
for all CBi
Search for the maximum height hi on ∂CBi
Let top hat peak fi=0
for all x ∈ CBi
if f(x) >= hi, let fi(x) = f(x) – hi; end if
end for
end for;
end process;
At last we get TP(f) = {fi};

4 Application of Peak Analysis

In this section, we will represent the application of Peak Analysis to measure the
quantum dots on the AFM photos. The results of the experiments are quite accurate
and insensitive to noise.

29
Feng Jin, Huaxiang Lu
Peak Analysis of Grayscale Image: Algorithm and Application

4.1 Atomic Force Microscopy (AFM) photo

AFM photo is the observation of the growing result of micro materials. On the photo
the intensity value of each pixel corresponds to the height of the growing material.
The proposed application of the Peak Analysis is based on the photo of the quantum
dots as well as quantum wells, which is characterized with following properties:
1) The substrate on which the quantum dots are grown is also fluctuating. Conse-
quently a simple threshold is not appropriate for the segmentation purpose, see
Fig 5(a). Another reason for the requirement of a more robust segmentation
technology is the widely presence of the obvious noise on the photo, see Fig
5(b).
2) The grown quantum dots and quantum wells are of diverse shapes: such as cir-
cles, annuluses, crescents and even more irregular shapes, see Fig 8(a). However
they are in common that they are all highlands that stand in a given height range
and span a range of size. Although quantum dots may not necessarily be a strict
Peak we defined above, they are sure to be one of the nodes (including the
whole subtree of the node) on the Peak Tree. Therefore searching the Peak Tree
is the exact way to extract the quantum dots.
3) AFM grayscale image is a two-variable function that has the characteristic of
fractal. Sorting by the size, there exist the same pattern from substrate, quantum
dots to noise, see Fig 5 (a) (b). Thus the size for qualified quantum dots are re-
quired to be defined in advance by the user.
4) Peak analysis is different from the problem of edge locating of Marr’s theory. If
we adopt the criterion of the maximum of the first differential, the quantum dots
we segment will be smaller than they really are. See Fig 6, according to the
maximum of first differential, we will get the part of A, greatly differing from
the desirable result of B.

(a) (b)
Fig 5 two kinds of quantum dots

30
International Journal of Information Technology, Vol. 12 No. 2 2006

Fig 6 the segmentation error resulted from the maximum of ∇f

4.2 Main processes to search for the quantum dots

Suppose we have applied peak analysis to the grayscale image f, and saved the result
in the peak tree PT(f). Now in order to locate the quantum dots, the remaining job is
to traverse the whole tree, visit each node (namely each peak) to first do some process
to the peak (the following Step 1) and then to judge if it is a qualified QD according
to its size, height and other attributes (Step 2 and 3).
Let’s denote the node (peak) being visited as fi.
1) Determining the existence of the substrate in the peak. If so, eliminate it.
One feature of peak analysis is to take into account only the altering trend of the
function value (the shape) of a peak while leave its altering speed (the slope)
alone. Please refer to Fig 6, where there exist two uncontinuous breaks of the
gradient of function f and the slow-decreasing part outside the breaks of the peak
f should be deemed as the substrate, which should be eliminated before the final
segmentation.
Since a sudden drop of the first differential of function f corresponds to a large
value of the second differential of f, which in multivariable function can be esti-
mated by the Laplacian value ( ∇ 2 f ) of f, we can judge the existence of sub-
strate by finding that in the lower part of the peak f there exist large abstract val-
ues of ∇ 2 f compared with those in the higher part of f. Let hsub denote the value
(height) of f where the high Laplacian value appears. In this way, by removing
the part of the peak that is lower than hsub, we can eliminate the substrate, as
shown in Fig 7.

(a) (b)
Fig 7 (a) Peak containing heterogeneous substrate (b) Peak without substrate

2) Denote pfi = ∑ f k , where fk is the node on the subtree of fi (including fi itself).

From the view of topography, pfi is whole part of the relief that stacks on the
peak fi. Let hi = max(fi), phi = max(pfi), namely the height of peak fi itself and the
height of the total height of mountain above fi separately.

31
Feng Jin, Huaxiang Lu
Peak Analysis of Grayscale Image: Algorithm and Application

3) Let NZD ( f i ) denote the nonzero domain of fi, extract the boundingbox of
NZD ( f i ) as BBox( NZD ( f i ) ), record the widths of this rectangle as w1,w2.
4) Let user input the qualified height range of QD as [Hmin, Hmax], size range as
[Wmin, Wmax], accompanied with the phi, w1, w2 to determine whether current
peak is a qualified QD.

4.3 Experiment Results

The program code of this paper is written in Matlab, and utilizes its watershed func-
tion in its image processing toolbox. To extract the peaks of a 256 by 256 image,
watershed generally need to be called 6~7 times, which takes most of the time of
process. To extract the whole QDs, a PC with PIII costs about 4~5 seconds.
Fig 8 and Fig 9 illustrate the segmentation results of some typical AFM photo. It
can be clearly seen that the segmentation results are quite correct and are unsensitive
to the existence of strong noise. In addition, a variety of shapes, such as annuluses,
circulars and rectangles, can all be identified.

5 Conclusion

Due to its intuitive excellent properties and fast calculation, Peak analysis prom-
ises to be a powerful tool in image processing. Its applications of denoising, image
filtering, and even image compression are our ongoing work.

(a) (b)

(c) (d)

32
International Journal of Information Technology, Vol. 12 No. 2 2006

Fig 8 AFM photos. Notice (d) contains quantum wells

(a) (b)

(c) (d)
Fig 9 Segmentation results of the corresponding images in Fig 8;

References

1. Luc Vincent and Pierre Soille: Watersheds in Digital Spaces: An Efficient Algorithm
Based on Immersion Simulations. IEEE Transactions of Pattern Analysis and Machine In-
telligence, vol. 13, no. 6, June 1991, pp. 583-598.
2. R. Jones: Connected filtering and segmentation using component trees. Comput. Vis.
Image Understanding, vol. 75, pp. 215–228, 1999.
3. Braga-Neto, U.; Goutsias, J.: Grayscale level connectivity: theory and applications. Image
Processing, IEEE Transactions on , Volume: 13 , Issue: 12 , Dec. 2004 Pages:1567 – 1580.
4. S. Beucher and C. Lantuejoul: Use of watershed in contour detection. International Work-
shop on Image Processing: Real-time edge and motion detection /estimation. Rennes,
France, 1979, pp. 17-21.
5. S. Beucher and F. Meyer: The morphological approach to segmentation: the watershed
transformation. Mathematical morphology in image processing, E. Dougherty, Ed. New
York: Marcel Dekker, 1993, pp. 433-481.Baldonado, M., Chang, C.-C.K., Gravano, L.,
Paepcke, A.: The Stanford Digital Library Metadata Architecture. Int. J. Digit. Libr. 1
(1997) 108–121.

33
Feng Jin, Huaxiang Lu
Peak Analysis of Grayscale Image: Algorithm and Application
Feng Jin got his Bachelor of EE from Tsinghua University, China.
From 2002, he joined the state key lab of artificial neural network,
Institute of Semiconductor, Chinese Academy of Science. During
the work in this lab, he focused on the study of image process and
image segmentation. In April 2005, he got his master degree.

Huaxiang Lu got his PhD in 1993 in Zhangjiang University. He

became the researcher in Institute of Semiconductor in 1997. His
main study fields include semiconductor neural network, power
management and so on.

34