Ignace Master

8/9/2019 Ignace Master

1/117

PATTERN SPECTRA ALGORITHMS FOR PATTERN RECOGNITION

by

TCHANGOU TOUDJEU IGNACE

Submitted in fulfilment of the requirements for the degree

MAGISTER TECHNOLOGIAE: ELECTRONIC ENGINEERING

In the

Graduate School of Electrical and Electronic Engineering

FACULTY OF ENGINEERING

TSHWANE UNIVERSITY OF TECHNOLOGY

Supervisor: Prof Barend J. van Wyk

Co-Supervisor: Prof. Michael A. van Wyk

November 2006


2/117

____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY 1


3/117

PATTERN SPECTRA FOR PATTERN RECOGNITION

____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY i

DECLARATION

I hereby declare that the dissertation submitted for the degree M Tech: Electronic

Engineering, at Tshwane University of Technology, is my own original work and has not

previously been submitted to any other institution of higher education. I further declare that all

sources cited or quoted are indicated and acknowledged by means of a comprehensive list of

references.

I. Tchangou Toudjeu

Copyright Tshwane University of Technology 2006


4/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY ii

To my dear parents


5/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY iii

ACKNOWLEDGMENTS

I would like to express my sincere gratitude and appreciation to: my supervisors, Prof. Barend

J. van Wyk and Prof. M.A. van Wyk for their positive attitude and guidance toward the

successful completion of this project.

Furthermore, I would like to thank FSATIE for all the facilities that I received to complete

this project. I thank the following people:

Mr Pierre Abeille, Director of FSATIE.

Mr Damien Chatelain for consultation.

My colleague students and all who assisted me when I needed help.

Special thanks go to Tshwane University of Technology, FSATIE and NRF [Grant number

TRD2005070100036] for their financial support.

Thanks to my dear mother for her support and encouragements.


6/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY iv

ABSTRACT

This dissertation deals with the application of pattern spectra algorithms to images of materials

of different types, for the purpose of pattern classification. As materials are often best

characterized by their texture, pattern spectra constitute a very important tool for texture

analysis. Two granulometric techniques and their resultant pattern spectra are discussed,

namely morphological granulometries based on structural openings and linear granulometries

based on the linear openings. Both are used to extract global image information. A novel

algorithm, not based on mathematical morphology called slope pattern spectra is also

proposed. The resulting pattern spectra from both the granulometric techniques and the

proposed algorithm are used in conjunction with a neural network to solve two pattern

recognition problems, namely classification and characterization (regression). Experiments are

conducted to compare the discussed pattern spectra algorithms in terms of speed and accuracy.

From the results it is evident that the slope pattern spectra algorithm is a fast and robust

alternative to granulometric-based techniques.


7/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY v

CONTENTS

PAGE

DECLARATION..........................................................................................................................i

ACKNOWLEDGMENTS......................................................................................................... iii

ABSTRACT ...............................................................................................................................iv

CONTENTS ................................................................................................................................v

LIST OF FIGURES................................................................................................................. viii

LIST OF TABLES ......................................................................................................................x

GLOSSARY...............................................................................................................................xi

CHAPTER 1................................................................................................................................1

INTRODUCTION.......................................................................................................................1

1.1 Background..................................................................................................................11.2 Problem statement .......................................................................................................2

1.2.1 Sub-problem 1 .....................................................................................................21.2.2 Sub-problem 2 .....................................................................................................31.2.3 Sub-problem 3 .....................................................................................................3

1.3 Methodology................................................................................................................31.4 Dissertation outline......................................................................................................4

CHAPTER 2................................................................................................................................6

LITERATURE REVIEW............................................................................................................6

2.1 Texture.........................................................................................................................62.2 Texture analysis...........................................................................................................72.3 Mathematical morphology...........................................................................................82.4 Granulometries ..........................................................................................................102.5 Some applications of morphological techniques .......................................................11

2.6 Texture classification.................................................................................................112.7 Summary....................................................................................................................12

CHAPTER 3..............................................................................................................................13

MATHEMATICAL MORPHOLOGY .....................................................................................13

3.1 Basic definitions ........................................................................................................133.1.1 Binary image .....................................................................................................14


8/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY vi

3.1.2 Grayscale image ................................................................................................143.1.3 Structuring element ...........................................................................................15

3.2 Binary morphological operations ..............................................................................163.2.1 Binary dilation ...................................................................................................183.2.2 Binary erosion ...................................................................................................19

3.2.3 Binary opening ..................................................................................................203.2.4 Binary closing....................................................................................................213.3 Grayscale morphological operations .........................................................................22

3.3.1 Grayscale dilation..............................................................................................233.3.2 Grayscale erosion ..............................................................................................243.3.3 Grayscale opening .............................................................................................253.3.4 Grayscale closing...............................................................................................26

3.4 Summary....................................................................................................................27

CHAPTER 4..............................................................................................................................28

GRANULOMETRIES ..............................................................................................................28

4.1 Basic concept .............................................................................................................284.2 Morphological granulometries and pattern spectrum................................................31

4.2.1 Size distribution.................................................................................................324.2.2 Pattern spectrum ................................................................................................35

4.3 Linear grayscale granulometries and pattern spectrum .............................................374.3.1 Linear grayscale granulometries........................................................................374.3.2 Horizontal pattern spectrum ..............................................................................40

4.4 Opening trees and grayscale granulometries .............................................................444.5 Summary....................................................................................................................46

CHAPTER 5..............................................................................................................................47

SLOPE PATTERN SPECTRA .................................................................................................47

5.1 Integral image ............................................................................................................475.2 Proposed algorithm....................................................................................................535.3 Summary....................................................................................................................56

CHAPTER 6..............................................................................................................................57

EXPERIMENTAL DESIGN.....................................................................................................57

6.1 The proposed supervised system ...............................................................................57

6.2 Feature extraction ......................................................................................................586.3 Neural networks.........................................................................................................596.3.1 Classification (Seed images) .............................................................................596.3.2 Regression (HSLA steel images).......................................................................616.3.3 Network training................................................................................................62

6.4 Implementation details of the proposed system ........................................................636.4.1 Sample images for classification (Seed images) ...............................................636.4.2 Sample image for regression (HSLA steel images)...........................................64


9/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY vii

6.4.3 Pattern spectra implementation .........................................................................666.4.4 Classification implementation for seed images .................................................666.4.5 Regression implementation for steel images .....................................................67

6.5 Summary....................................................................................................................67

CHAPTER 7..............................................................................................................................69

EXPERIMENTAL RESULTS AND DISCUSSION................................................................69

7.1 Experimental results ..................................................................................................697.1.1 Data acquisition results......................................................................................697.1.2 Pattern spectra results ........................................................................................707.1.3 Classification results for seed images................................................................717.1.4 Regression results for steel images....................................................................72

7.2 Discussion..................................................................................................................747.3 Summary....................................................................................................................76

CHAPTER 8..............................................................................................................................77CONCLUSION AND FUTURE WORK..................................................................................77

8.1 Conclusions ...............................................................................................................778.2 Future work ...............................................................................................................78

BIBLIOGRAPHY .....................................................................................................................80

APPENDIX A...........................................................................................................................89

Mixture sample images and their pattern spectra ......................................................................89

APPENDIX B ...........................................................................................................................95

HSLA sample images and their pattern spectra.........................................................................95


10/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY viii

LIST OF FIGURES

PAGE

Figure 3.1: A binary image........................................................................................................14

Figure 3.2: Grayscale image......................................................................................................15

Figure 3.3: (a) Cross SE, (b), Diamond SE and (c) Horizontal Line SE. The cross mark is.....15

the reference pixel or center pixel. ............................................................................................15

Figure 3.4: Example of complement, union and intersection....................................................17

Figure 3.5: Translation operation on image A by t . ..................................................................17

Figure 3.6: Dilation of image A by the structuring elementB . ...............................................19

Figure 3.7: Erosion of imageA by the structuring elementB . .................................................20

Figure 3.8: Opening of image A by the structuring elementB ................................................21

Figure 3.9: Closing of image A by the structuring elementB . ................................................22

Figure 3.10: Grayscale image representation. ...........................................................................23

Figure 3.11: Grayscale dilation. ................................................................................................24

Figure 3.12: Grayscale erosion..................................................................................................25

Figure 3.13: Grayscale opening.................................................................................................26

Figure 3.14: Grayscale closing..................................................................................................27

Figure 4.1:A sequence of increasing structuring elements for 2= , 4= , 6= and 8= .

...................................................................................................................................................33

Figure 4.2: A decreasing family of openings of an image of seeds...........................................34

Figure 4.3: An image of mixed seeds (left), its size distribution (middle) and its cumulative

normalized size distribution (right). ..........................................................................................35

Figure 4.4: Pattern spectrum of the image of seeds..................................................................36


11/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY ix

Figure 4.5: Illustration of a line segment...................................................................................37

Figure 4.7: Cross-section ofIwith a maximumM ..................................................................41

Figure 4.8: Illustration of linear grayscale algorithm for a line with two maxima....................42

Figure 4.9: Illustration of the horizontal pattern spectrum of the mixed seeds image shown in

the left of figure 4.2...................................................................................................................43

Figure 4.10: Opening tree representation of the cross-section shown in figure 4.8. The leaves

of the tree represent the image pixels........................................................................................44

Figure 5.1: The value at the point ( )yx, corresponds to the sum of all pixels in the shaded

area.............................................................................................................................................48

Figure 5.2: A line segment and its integral representation........................................................49

Figure 5.3: Illustration of a cross section of a line from an image, its integral representation

and a curve corresponding to the integral line segment indicating two increasing slope

segments: the 1st one going from the 1st pixel to the 4th pixel and the 2nd one from the 6th pixel

till the 8th pixel...........................................................................................................................51

Figure 5.4: Slope pattern spectrum of a mixed seed image.......................................................55

Figure 6.1: Flowchart of the proposed classification system. ...................................................58

Figure 6.2: A feed-forward network architecture. ...............................................................61

Figure 6.3: Examples of seed sample images...........................................................................64

Figure 6.4: Examples of HSLA sample images. .......................................................................65

Figure 7.1: Regression results obtained when using morphological scheme............................72Figure 7.2: Regression results obtained when using linear scheme. .........................................73

Figure 7.3: Regression results obtained when using slope scheme...........................................73


12/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY x

LIST OF TABLES

PAGE

Table 4.1: Algorithm of a horizontal granulometry for a line of image I(Vincent, 2000:126-

127)............................................................................................................................................42

Table 4.2: Algorithm of a linear granulometry of the grayscale image Ifrom its opening tree

representation.............................................................................................................................45

Table 5.1: Proposed slope pattern spectra algorithm.................................................................54

Table 6.1: Mixture of seeds.......................................................................................................63

Table 7.1: Execution time of different feature extraction techniques for four sample images

shown in Appendix A and B. ....................................................................................................71

Table 7.2: Classification results.................................................................................................71

Table 7.3: Performance measures of the regression..................................................................73


13/117


____________________________________________________________________________FSATIE - TSHWANE UNIVERSITY OF TECHNOLOGY xi

GLOSSARY

HSLA: High Strength Low Allow.

K-NN: K-Nearest Neighbour.

LPS: Linear Pattern Spectra.

LUT: Look Up Table.

MPS: Morphological Pattern Spectra.

MSE: Mean Square Error.

SE: Structuring Element.

SPS: Slope Pattern Spectra.

SS: Slope Segment.

ISS: Increasing Slope Segment.


14/117



CHAPTER 1

If we knew what it was we were doing, it would not be called research, would it?

(Albert Einstein)Research is what Im doing when I dont know what Im doing(Werner von Braun)

INTRODUCTION

1.1 BackgroundSince texture is an important surface feature, many industrial materials such as wood, steel, or

mixed materials such as seeds can be characterized by their texture. The detection of defects or

classification for quality control can be done using texture analysis.

The relationship between physical properties and texture can be understood by investigating

the diversity of morphologies and their characteristics. The development of computational

vision techniques to address these issues should therefore focus on the determination of grain

size of particles, morphological characteristics and micro-morphology. A pattern spectrum is a

useful tool for texture analysis since it extracts the size distribution of grains.

Some previous work addressing these issues include mathematical morphology techniques for

the analysis of the civil engineering materials (Coster and Chermant, 2001), image analysis for

macro-segregation in a high-carbon continuously cast steel (Straffelini and Molinari, 1997),

the examination of hydrogen interaction in carbon steel by means of quantitative micro-

structural and feature descriptions (Sozanska et al. 2001), the influence of mixed grain size


15/117



distributions on the toughness in high strength steels (From and Sanderstrom, 1999) and many

similar contributions focusing on mathematical morphology techniques.

The focus of this project will be to characterize the size or shape of different grains present in

material samples. It is envisaged that the determination of the grain size of particles,

morphological characteristics and the dispersion and orientation of grains can be captured by

pattern spectra. A pattern spectrum quantifies the morphological and statistical characteristics

of different phases observed. By representing images of different materials samples by their

pattern spectra, the problems such as classification or characterization can be reduced to a

pattern recognition problem. Recent contributions to morphological and fast granulometric

methods are investigated and a novel algorithm for pattern spectra, not based on mathematical

morphology, is presented.

1.2 Problem statementThe purpose of this work is to develop a fast and robust pattern spectrum algorithm for the

classification and characterization (regression) of materials as an alternative to morphology

based pattern spectra methods.

1.2.1 Sub-problem 1Investigate and implement morphology based pattern spectra methods.


16/117



1.2.2 Sub-problem 2Develop and implement the novel slope pattern spectra algorithm as a fast and accurate

alternative to morphology based pattern spectra methods.

1.2.3 Sub-problem 3Conduct experiments to determine the efficiency and robustness of the proposed slope pattern

spectra algorithm. The experiments will include classification using seed images and

characterization (regression) using High Strength Low Allow (HSLA) steel images.

1.3 MethodologyExperiments are conducted in this dissertation using two diverse types of materials: a mixture

of seeds and HSLA steel samples. The sample images of these materials are captured and

regrouped with respect to some pre-defined criteria.

Granulometric methods are implemented by means of simulations written in MATLAB. The

proposed slope pattern spectra algorithm is also implemented and comparisons are made in

terms of speed and classification accuracy.

Pattern spectra that result from both granulometric methods and the proposed slope pattern

spectra algorithm are used as features. These pattern spectra are fed to a neural network for

the classification and characterization (regression) of the materials.


17/117



1.4 Dissertation outlineThe main purposes of this dissertation are:

1. to provide an overview of mathematical morphology for image processing.

2. to investigate granulometric methods such as morphological granulometries

and linear granulometries.

3. to propose a new algorithm and a supervised system for classification and

characterization (regression).

Hence, in Chapter 2, a review of texture and texture analysis is presented. Mathematical

Morphology and granulometry as image analysis tools are introduced, as well as classification

using neural networks.

In Chapter 3, a review of the basic geometric characteristics of primitive morphology

operators are given. Some illustrative examples are also presented.

Chapter 4 is devoted to two granulometric methods: one based on morphological operations,

which sometimes is referred to as morphological granulometries and the other one based on

work done by Vincent (2000:119-133).

The proposed slope pattern spectra algorithm is described in Chapter 5.

The experimental design is presented in Chapter 6 by means of a proposed supervised system.


18/117



Experimental results are presented in Chapter 7 followed by a discussion of the simulation

results.

Chapter 8 concludes the dissertation and outlines future work.

In the Appendices, some experimental results are given. Sample images of seeds and their

respective pattern spectra are presented in Appendix A. Appendix B consists of the sample

images of HSLA steel and their respective pattern spectrum.


19/117



CHAPTER 2

The greatest challenge to any thinker is stating the problem in a way that will allow a solution.(Bertrand Russell)

LITERATURE REVIEW

Materials, in general when captured as sample images, are rich in visual information. These

sample images can be characterized by structure and texture. Structure and texture are the

same phenomena except at different scales: individual objects, when repeated in either a

random or a predictable manner, form a structure and when the repeating objects are not

distinguishable but the repeating pattern still is, a texture is formed. In this chapter, a short

review on texture analysis is presented. In addition, some applications based on pattern spectra

such as texture classification are also discussed.

2.1 TextureTexture can be defined as an image that is organized by a repeating pattern (Rosenfeld, 1982)

or un-repeating texture primitives, i.e. small particles such as grains. These primitive patterns

are sometimes referred to as textons (Brodatz, 1966). In Asano, Miyagawa and Fujio (2000),

textures in natural scenes contain particles of shape at various sizes since the shapes of these

particles depend on the materials of which the texture entities are made. Additionally, image

texture is generally a particular spatial arrangement of gray levels, with the property that the

gray level variations have to be of a rather high frequency, and that it presents a pseudo-

periodical character (Huet and Mattioli, 1996). Accordingly to these definitions, issues such as

feature extraction, and texture classification can be solved using texture analysis techniques.


20/117



2.2 Texture analysisSince feature extraction computes a characteristic of a digital image that is able to numerically

describe its texture properties (Meterka and Strzelecki, 1998), this is considered as the first

stage of texture analysis. Pattern spectra belongs to this stage and have been used for a variety

of image analysis tasks, including texture segmentation (Dougherty, Newell and Pelz,

1992:1181-1198 and Dougherty et al, 1992:40-60), texture discrimination (Yamamoto and

Kotani, 1998:57-64) and texture classification (Chen and Dougherty, 1992:931-942).

There are two main groups of texture analysis methods, namely statistical methods and

structural methods (Haralick, 1979:786-809). The former is more suitable for disordered

textures, where the spatial distribution of gray levels is more random than structured and the

latter is more suitable for ordered texture (Huet and Mattioli, 1996: 297).

Statistical methods do not attempt to explicitly understand the hierarchical structure of the

texture, but they indirectly extract image features by the non-deterministic properties that

govern the distributions and relationship between the gray levels of the image. An example of

a statistical method is the Fourier transform (Pratt as quoted by Alessandro et al, 2003: 400)

which, by means of an energy spectrum, reflects the grayscale periodicity (spatial frequency

spectrum) in the image. This is a fast technique but performs poorly in practice because of its

lacks of spatial localization (Alessandro etal, 2003:401-405; Meterka and Strzelecki, 1998:3).

These methods will not be discussed further since the emphasis of this work is on pattern

spectra.


21/117



Structural methods, on the other hand, describe texture by first defining primitives and

placement rules. These methods have an advantage over statistical ones since they can provide

a symbolic description of the image. Mathematical morphology provides a powerful tool for

structural texture analysis (Meterka and Strzelecki, 1998).

2.3 Mathematical morphologyMathematical morphology was born in 1964 from the investigation of the relationship between

the geometry of porous materials and their permeability done by Matheron and Serra at the

Ecole des Mines de Paris in Fontainebleau. It was first applied to binary images and then later

extended to grayscale images (Serra, 1988).

Soille (2005:2) simply defined mathematical morphology as a theory for the analysis of spatial

structures. This theory is thus a method of developing a quantitative description of the

geometrical structure of a signal or an image (Maragos and Scharfer, 1987). Hence

quantification consists of a transformation followed by a measurement (Serra, 1988).

Transformation in this framework refers to image processing and measurement refers to image

analysis.

Image processing constitutes any operation that with an image at the input produces an image

at the output. Mathematical morphology transformations operate as follows: sub-images, also

named structuring elements, interact with the original image to modify and extract

information. These structuring elements are related to textons in texture images. These

operations were initially only applied to binary images (image with two gray levels). When


22/117



dealing with other images such as a grayscale image (image with more than two gray levels),

it was required to first threshold or convert this image to binary before performing a binary

morphological operation. This was found to be inconvenient and resulted in a loss of

information. In 1978, this problem was remedied by Nakagawa and Rosenfeld (1978) which

linked the two basic operation of mathematical morphology, namely binary dilation and binary

erosion, to maximum and minimum filters when dealing with grayscale images. A

combination of these operations led to advanced operations such as opening, closing, hit-or-

miss transform, top-hat, etc. (Serra, 1982).

An important aspect of a morphological transformation is the choice of a proper structuring

element. In Kotani (1998:57-64) the structuring element is optimized to obtain the best

discrimination of textures in order to categorise them. Similar optimization was performed by

Asano, Miyagawa and Fujio (2000:479-482) for texture characterization. In Chapter 3, the

associated mathematical concepts with illustrative examples are presented.

Image analysis refers to any operation that with an image at the input produces numbers

(measurements) at the output. In Aubert, Jeulin and Hashimoto (2000:253-262),

morphological measurements such as granulometry and anti-granulometry distributions were

analysed for surface texture classification. Two of the important morphological functions used

for image measurements are granulometric and anti-granulometric distribution functions

which characterize the size of objects of an image. The former uses morphological opening,

sometimes referred to as structural opening. The latter uses morphological closing which is

also referred to as structural closing.


23/117



2.4 GranulometriesThe concept of granulometries has been introduced by Matheron (1967, 1975) in the late

sixties for analyzing objects and structure sizes in the images. Granulometries originally were

formulated for binary images (Dougherty, 1992:72-77) and were referred to as morphological

granulometries involving sequences of openings or closings with structuring elements of

increasing sizes. Other types of granulometries (anti-granulometries) named algebraic

granulometries were introduced by Serra (1988) based on algebraic opening (closing).

Although the granulometries during this period gave adequate descriptions of sizes and shapes

of objects in the images, they remained prohibitively costly on non-specialized hardware

because of their computation time. For this reason, Vincent (2000:119-133) proposed fast

granulometric methods for the extraction of global image information from grayscale images.

Moreover, granulometries as morphological image analysis tools were found particularly

useful for the estimation object sizes in binary and grayscale images. They were also useful for

characterizing textures based on their granulometric curves or pattern spectra (Vincent,

1996:273).

In Matheron (1967), granulometric analysis is often compared to a sifting process, where an

image is sifted through a series of sieves with increasing mesh size. Each mesh size removes

more than the previous one until the image finally becomes blank. The morphology-based

pattern spectrum can be seen as a signature provided by the rate at which an image is sifted.

Maragos (1989:709) has introduced the concept of an oriented pattern spectrum which enables

the extraction of 1D line structures of an image that live in a 2D space. The structuring


24/117



element is a line segment forming an angle with the horizontal. In Werman and Peleg as

quoted by Maragos (1989:709), oriented openings are used for texture analysis.

2.5 Some applications of morphological techniquesDi Ruberto et al (2000:397 ) used morphological operators to detect and classify malaria

parasites in stained blood slides for the purpose of evaluating the parasitaemia of the blood.

Granulometries based on disk-shaped elements were used to capture information on cells and

parasite nuclei. The resulting pattern spectra characterized two predominant particle sizes in

the image, namely the nuclei of the trophozoites (3-7 pixels) and the red blood cells (15-25

pixels). Moreover, Colome-Serra et al (1992:1934-1935) employed greyscale granulometries

as a quantification technique to measure chronic renal damage. This method was found time

consuming.

2.6 Texture classificationTexture classification is the grouping of test samples into classes accordingly to some

criterion. There are two types of classification namely unsupervised classification and

supervised classification. The former is when the classes are not defined a priori and is not

often used for texture applications. The latter corresponds to the case where the classes are

defined a priori and is usually referred to as classification. There are many types of classifiers.

Among them the most used are statistical k-nearest neighbour (k-NN) and neural networks.

Though the k-NN classifier is simple and efficient, a large amount of memory is required,

resulting in slow performance. Since the focus of this work is not on neural networks, readers

are encouraged to consult Bishop (1995) for more detail.


25/117



2.7 SummarySome materials are best characterized by their texture. Texture was defined in Section 2.1. The

concept of texture analysis was discussed in Section 2.2. Mathematical morphology and

granulometries were briefly introduced in Section 2.3 and Section 2.4 respectively. Some

applications using morphological techniques were presented in Section 2.5. Lastly, texture

classification was described in Section 2.6.


26/117



CHAPTER 3

I don't see how an epigram, being a bolt from the blue, with no introduction or cue, ever gets itself writ(William James)

MATHEMATICAL MORPHOLOGY

Mathematical morphology is a general method for processing images based on set theory,

where images are presented as a set of points or pixels on which operations such as union and

intersection are performed (Bleau, Guise, & Leblanc 1992:1). Mathematical morphology was

developed by Matheron (1975) and Serra (1988) at the Ecole des Mines de Paris in

Fontainebleau. This theory has first been applied to binary images and later extended to

grayscale images.

3.1 Basic definitionsAn image, in general, consists of a set or collection of pixels belonging to objects in the image.

A pixel is defined as an image unit. Alternatively an image can also be defined as a function of

two real variables, i.e. ( , )I x y representing an amplitude or a pixel value. For the rest of this

review, we will only consider binary and grayscale images. We will therefore restrict to the

domain to 2Z .

In Vincent and Soille (1991), a two-dimensional grayscale image is defined as follows:

Definition 3.1 (Two-dimensional grayscale image) Let I be a two-dimensional grayscale

image whose domain is denoted 2ID Z .Itakes discrete gray values in a given range [ ]N,0 ,


27/117



where N is an arbitrary positive integer. Letting p be any arbitrary pixel ofI , we can define

a two-dimensional grayscale image as

{ }2 0,1,...,

:( )

ID N

Ip I p

Z

. (3.1)

3.1.1 Binary imageBased on Definition 3.1, a binary image corresponds to a two-dimensional grayscale image

with two gray levels { }1,0 , the range, being 1. A binary image is also defined as a black and

white image for it only has pixels of 1 or 0, corresponding to white and black respectively.

Figure 3.1 shows an example of a binary image.

Figure 3.1: A binary image.

3.1.2 Grayscale imageIn this chapter, we defined a grayscale image as a two-dimensional grayscale image with a

limited range. Referring to Definition 2.1, Nequals 255 implies 256 gray levels { }255,,1,0 .

Gray levels 0 and 255 correspond to black and white respectively. Figure 3.2 shows an

example of a grayscale image.


28/117



Figure 3.2: Grayscale image.

3.1.3 Structuring elementThe morphology of an image relies on the analysis of images using elementary patterns or

structuring elements which can be considered as templates. (Awcock & Thomas, 1995:167). A

structuring element, denoted by SE, is as an image subset of 2Z used to analyse the

topography of the image. For each structuring element we need to define its shape, size and its

center. These three characteristics are subject to the information needed to be extracted from

the image. Figure 3.3 illustrates different type of structuring elements.

(a) Cross (b) Diamond (c) Line SE

Figure 3.3: (a) Cross SE, (b), Diamond SE and (c) Horizontal Line SE. The cross mark is

the reference pixel or center pixel.


29/117



Additionally, a structuring element can also be characterized as a flat or non-flat structuring

element. When the intensity values are identical, constituting a uniform platform, this is

referred to as a flat structuring element. In most cases the flat structuring element is a binary

sub-image. On the contrary, the structuring element can be composed of different intensity

values such a grayscale sub-image. This is called non-flat structuring element. The structuring

elements used in this dissertation are flat structuring elements.

3.2 Binary morphological operationsBinary image processing operations have been collectively described as morphological

operations (Serra, 1982; Coster and Chermant, 1985; Dougherty and Astola, 1994, 1999;

Soille, 1999). The most popular operations are dilation and erosion, and their combinations

lead to more advanced morphological operations such as opening and closing.

As known from Awcock and Thomas (1995:165), binary mathematical morphology owes its

origin to set theory and deals with form and structure. In addition to the standard set

operations such as union, intersection, inclusion and complement{ }c,,, , morphology

depends extensively on the translation operation. Therefore, from the Minkowski set

operations, the fundamental morphological operations are defined.

In this section, a square pixel representation is used to illustrate the effect of morphologicaloperations, starting with the standard set operations. The foreground is the filled squares or

pixels and the rest, which can be expressed as the complement of the foreground, are called

background. Figure 3.4 demonstrates the intersection, union and the complement operations.


30/117



A B cA

Figure 3.4: Example of complement, union and intersection.

Definition 3.2 (Translation)LetA be an image. The translation ofA by the point t denoted

by tA is defined by

{ }AatatAAt +=+= | . (3.2)

A t tA

Denotes the origin and the coordinates of the translation vector.

Figure 3.5: Translation operation on image A by t.

Figure 3.5 shows how the foreground pixels are shifted with respect to the translation vector t.

BA BA


31/117



Definition 3.3 (Minkowskis operations) Given two sets or vectors A and B ,

Minkowski addition is defined as

)( bABABb

+=

(3.3)

and Minkowski subtraction as

A B ( )b B

A b

= + (3.4)

where Bb .

Using Minkowskis formulism and the translation notation, morphological operations are

defined in the next section.

3.2.1 Binary dilationDefinition 3.4 (Dilation)The dilation of a binary image A by structure element B , denoted by

A B , is defined as

bb BA B A = . (3.5)

By stepping the reference point or center of the structuring element over each pixel of the

foreground (object in the image to be eroded) until all the foreground pixels of the structuring

element fit over the foreground of the image, and then considering the union of foreground

pixels, the dilated image is produced. Figure 3.6 illustrates an example of dilation which

modifies an imageA with respect to a cross structuring elementB . Dilation, in general,

enlarges features in the image by adding pixels and fills small holes in the image.


32/117



A B BA

Figure 3.6: Dilation of image A by the structuring elementB .

3.2.2 Binary erosionDefinition 3.5 (Erosion)The erosion of a binary image A by structuring element B , denoted

by A B, is defined as

A B bb B

A

= , (3.6)

or

A ( )B bb BA= , (3.7)

where }|{ BbbB = is the transposed form of the structuring element set.

Erosion of a binary image by a structuring element can be described intuitively by template

translation. Contrarily to dilation, after stepping the structuring element until all its foreground

pixels fit over the foreground of the image, only the intersection of foreground pixels of theimage and the structuring element are considered to produce an eroded image. Erosion, in

general, shrinks the image by removing foreground pixels in the image and eliminates objects

smaller than the structuring element. This operation is illustrated in Figure 3.7.


33/117



A B A B

Figure 3.7: Erosion of imageA by the structuring elementB .

3.2.3 Binary openingErosion is often used to remove noisy pixels or unsuitable small objects from an image.

Regrettably, this morphological operation also shrinks objects in the image. To overcome this

inconveniency, a morphological operation named opening is introduced. Opening is created by

erosion followed by dilation.

Definition 3.6 (Opening) The opening of a binary image A by a structuring element B ,

denoted by BA , is defined as

(A B = A B ) B . (3.8)

The opening operation separates connected objects and smoothes object contours. Figure 3.8

shows how the object contour in the imageA is smoothed from both the inside and the

outside.


34/117



A B BA

Figure 3.8: Opening of image A by the structuring elementB .

A geographical metaphor can be employed to appropriately describe the effect of opening:

opening smoothes object coastlines, eliminates small islands and cuts narrow isthmuses

(Awcock & Thomas, 1995:171). This operation, by means of its effect on an image, was found

to be a suitable precursor to studies of size distributions (Kraus et al, 1993:2).

3.2.4 Binary closingInversely, closing is created by performing dilation followed by erosion.

Definition 3.7 (Closing) The closing of a binary image A by a structuring element B ,

denoted by BA , is defined as

( )A B A B = B. (3.9)

The closing operation smoothes object contours in the image, especially from the outside and

can also fill small holes as illustrated in Figure 3.9. The smoothing effect of the object contour

highly depends on the characteristics of the structuring element.


35/117



A B BA

Figure 3.9: Closing of image A by the structuring elementB .

Due to the duality existing between opening and closing, closing can also be used for studies

of distributions of particles.

3.3 Grayscale morphological operationsReal world images are grayscale images. Binary images can be obtained by thresholding

grayscale images. This threshold operation often causes loss of information and introduces

significant errors in segmenting objects from the background that leads to poor results when

performing morphological operations on binary images (Hussain, 1991). For this reason, the

theory of mathematical morphology has been extended to grayscale images and signals (Serra,

1982). This extension can be realized in various ways (Bangham and Marshall, 1998:117-

128). Moreover binary morphological operations can be applied to grayscale images by

considering this kind of image equivalent to a stack of binary images as seen in Figure 3.9.

This method requires the use of a threshold or Look Up Table (LUT) technique for the

decomposition of grayscale image into a stack. Therefore binary operations as described

earlier in Section 3.3 are applied to each stack to give a new set of stacks. Hence the new set


36/117



of stacks corresponds to the decomposition of the resulting grayscale image. Consequently, for

256 gray level images, 256 thresholds, 256 binary morphological operations and 255

summations are performed. Practically, this method as an extension to grayscale images is

time consuming.


37/117



Using the extremum operation, grayscale dilation can be express as

( ) ( ) )(max bxfxf BbB += , (3.11)

where b denotes the position of point inside the structuring element set B relative to the

center or origin of the structuring element and x denotes the position of point relative to the

origin of the grayscale image f .

To obtain grayscale dilation, a structuring element is scanned over the image and at each

position only the maximum value lying within the structuring element at that position is taken.

Grayscale Image Grayscale Dilation

Figure 3.11: Grayscale dilation.

This operation grows the white regions of the original image and the dilated image looks

brighter.

3.3.2 Grayscale erosionDefinition 3.9 (Grayscale erosion) The erosion of a grayscale image f by a structuring

element B , denoted by ( )fB , is defined as


38/117



( ) bBbB ff = . (3.12)

Using the extremum operation, grayscale erosion can be express as

( ) ( ) )(min bxfxf BbB += . (3.13)

Grayscale erosion is obtained by proceeding the same way as in grayscale dilation, but only

the minimum value laying in the structuring element is taken.

Grayscale Image Grayscale Erosion

Figure 3.12: Grayscale erosion.

Contrarily to grayscale dilation, this operation shrinks white regions. Thus the eroded image

looks darker. Figure3.12 shows the effect of grayscale erosion.

3.3.3 Grayscale openingDefinition 3.10 (Grayscale opening)The opening of a grayscale image f by a structuring



39/117



( ) ( )[ ]ff BBB = . (3.14)

Using the extremum operation, grayscale opening can be express as

( )( ) ( ))(minmax bxfxf BbBbB += . (3.15)

Grayscale Image Grayscale Opening

Figure 3.13: Grayscale opening.

Figure 3.13 shows how an opening of a grayscale image by a disk-shaped structuring, removes

high intensity points.

3.3.4 Grayscale closingDefinition 3.11 (Grayscale closing) The closing of a grayscale image f by a structuring



40/117



( ) ( )[ ]ff BBB = . (3.16)

Using the extremum operation, grayscale closing can be express as

( )( ) ( ))(maxmin bxfxf BbBbB += . (3.17)

Grayscale Image Grayscale Closing

Figure 3.14: Grayscale closing.

Figure 3.14 illustrates the effect of closing on a grayscale image by a disk- shaped structuring

element with a three-pixel diameter. This operation fills holes in the image by removing low

valued points.

3.4 Summary

Section 3.1 provided basic definitions dealing with mathematical morphology: binary andgrayscale images and structuring elements as sub-images were defined. Binary morphological

operations were elaborated on Section 3.2. Some illustrative examples were also presented.

The last section was concerned with grayscale morphological operations.


41/117



CHAPTER 4

The important thing is never to stop questioning(Albert Einstein)

GRANULOMETRIES

In Chapter 3, we reviewed primitive morphological operators and their basic geometric

characteristics. More advanced operations are constructed by combining these operators.

Granulometries are considered as morphological filters involving sequences of openings or

closings in order to extract global information from the image (Serra, 1982, 1988).

Granulometries were conceived by Matheron (1975) and first applied to binary images and

then to grayscale images to infer particle size distributions (Tscheschel, Stoyan & Hilfer,

2000:57) and characterize or classify textures (Soille, 1999; Vanrell & Vitria, 1993:152-161;

Chen & Dougherty, 1992) or shapes (Maragos, 1989:701-716). Granulometries in general are

used as a precursor in the classification of features in images of materials. In this chapter,

morphological granulometries and linear granulometries are discussed in detail.

4.1 Basic conceptGranulometries are comparable to a sieving process (Matheron, 1967; Jones & Soille, 1996).

Considering a heap of mixed seeds (or granules), to analyze how many seeds in the heap fit

into several classes, certain sieves with increasing hole sizes are used. The seeds that fall

through a given sieve size in the mesh are then removed. Hence, each set corresponding to a

mesh of a specific sieve size gives information on the seeds in the heap. The result of this

process leads to a discrete function expressing the amount of seeds for each specific sieve size.


42/117



From a morphological point of view, these sieves with increasing hole sizes are replaced by a

sequence of openings or closings with structuring elements of increasing size. As quoted by

Vincent (2000:119), these morphological operations have led Matheron (1975) to define a

granulometry as follows:

Definition 4.1 (Granulometry) Let ( ) 0= be a family of image transformations

depending on a parameter. This family constitutes a granulometry if and only if the

following properties are satisfied:

0 , is increasing, (4.1)

0 , is anti-extensive, (4.2)

0 , 0 , ),max( == . (4.3)

Relatively to the analogy mentioned above, Definition 4.1 implies that a granulometry is a

transformation, depending on a size parameter , that satisfies the three properties

enumerated as:

1. Increasing: if we divide the initial seeds into two subsetsA and B such thatB contains

A, the filtering is said to be increasing if the B filteredcontains A filtered. (see

Equation 4.7).

2. Anti-extensive: seeds non-filtered are a subset of the initial seeds in the heap. (see

Equation 4.8).

3. Idempotent or absorption: if we filter at two different sizes, we obtain the same result

no matter the order. (see Equation 4.9).


43/117



An opening is an operation which is increasing, anti-extensive and idempotent. An equivalent

definition to Definition 4.1 is proposed by Vincent (2000:119):

Definition 4.2 (Granulometry as proposed by Vincent)Let ( ) 0= be a family of

image transformations depending on a unique parameter . Then ( ) 0= is a

granulometry if and only if it forms a decreasing family of openings, that is

0 , is an opening, (4.4)

0 , 0 , . (4.5)

This definition implies that the opening can be either a morphological opening or an algebraic

opening leading to either a morphological granulometry or algebraic granulometry (Serra,

1988) respectively.

Furthermore, a closing which is a morphological operation that is increasing, extensive andidempotent (Serra, 1982; Vincent, 1997:119-120) can be used to define a granulometry by

closings as follows:

Definition 4.3 (Granulometry by closings)An increasing family of closings, that is such

that

0 , 0 , , (4.6)

is a granulometry by closings also named anti-granulometry.


44/117



The type of object size distribution differs for opening and closing operations. Granulometry

by openings can infer a size distribution of lighter objects as opposed to a granulometry by

closings inferring a size distribution of darker objects (refer to Figure 3.12 and Figure 3.13).

In the next section, most of the definitions are based on previous work of Dougherty

(1992:161, 1992:7-21), Maragos (1989:701-716) and Vincent (1994:43-102). Due to duality,

the morphological opening operation is considered to describe different types of size

distributions.

4.2 Morphological granulometries and pattern spectrumSince a binary image is also defined as a grayscale image with only two gray levels, this

section is devoted to grayscales images. Grayscale morphological granulometries are then

considered as granulometries using structural operations (i.e. operations based on a structuring

element). These filters as proposed by Matheron (1975) must satisfy Definition 4.1 which

means they must be openings. Not all types of openings satisfy the absorption property

(Equation 4.3), therefore they can not be used as granulometries (Nacken, 1994). For this

reason, the choice of the structuring element is important. However, Matheron has

characterized granulometries based on morphological openings as follows (Matheron as

quoted by Vincent (2000:119)):

Definition 4.4 (Characterization)Let B be a compact set of n . The family ( ) 0= of

openings by the homothetic { }BbbB = | , of B is a granulometry if and only if B is

convex.


45/117



The structuring element can be a rectangle, a hexagon, or a line, which are then referred to as a

rectangular granulometry, disk granulometry, or linear granulometry, respectively. A disc

structuring element is used here for demonstration. In the next sections, the following

assumptions are made: ( )pf is the grayscale image, B the parametric disc structuring

element with r, the radius, and ( )rF the granulometry function, with ( ) ,0r . A sum

projection of ( )rF is referred to as a size distribution, and its first derivative as a pattern

spectrum (Maragos, 1989: 701716 & Soille, 1999:25-58).

4.2.1 Size distributionA size distribution is a set of openings r with r from some ordered set that satisfies the

following properties:

Increasingness: ( ) ( )r rf g f g , (4.7)

Anti-extensivity: ( ) ffr , (4.8)

Absorption: ( )( ) ( )( )ff srsr ,max = . (4.9)

As shown in Chapter 3, an opening is a morphological operation obtained by producing a

erosion followed by a dilation. Therefore a set of openings with 0r , the scaling parameter,

is defined as

( ) ( ) ( )max min ( )r B b B b Bf f f x b = = + , (4.10)


46/117



which, when using the function-set notation, can be written as

( ) Bffr = . (4.11)

The homothetic B ofB with B being a disk structuring element, are illustrated in Figure

4.1.

Figure 4.1:A sequence of increasing structuring elements for 2= , 4= , 6= and

8= .

Furthermore, a size distribution function can be obtained by performing a series of

morphological openings with a sequence of structuring elements of increasing size (Figure

4.1). This function maps each structuring element to the number of objects or image pixels

removed during the opening operation with the corresponding structuring element. Figure 4.2

illustrates how, from an increasing family of structuring element, a decreasing family of

openings is produced.


47/117



Figure 4.2: A decreasing family of openings of an image of seeds.

As seen in Figure 4.2, objects in the image are removed or the intensity values of pixels

reduced progressively. By making a sum projection (sum of pixels) of opened images (images

obtained from an opening operation) on a scale-axis, a decreasing function known as a size

distribution, is defined as:

Definition 4.5 (Size distribution)

Let ( )rF be a measure of the image ( )pf , by assuming that ( )pf is bounded, at 0=r ,

( ) ( )= pfF 0 and at a larger value of r ( ) 0=rF , a size distribution denoted by ( )rF is

defined by

( ) ( )= prBfrF . (4.12)

Equation 4.12 is further used to derive a normalized size distribution defined as

Definition 4.6 (Normalized size distribution)

The normalized size distribution denoted by ( )r and defined as


48/117



( )( )( )0

1F

rFr = , (4.13)

is a cumulative distribution known as the granulometric size distribution of ( )pf with respect

to the structuring element B with ( )rF being the volume of rBf and ( )0F the volume of

original image ( )pf .

An illustration of the size distribution and its normalized size distribution are shown in Figure

4.3.

0 5 10 15 200

2

4

6

8

10x 10

6

radius

Volum

e

0 5 10 15 200

0.2

0.4

0.6

0.8

1

radius

Volum

e

Size Distribution Normalized Size DistributionMixed seeds

Figure 4.3: An image of mixed seeds (left), its size distribution (middle) and its

cumulative normalized size distribution (right).

4.2.2 Pattern spectrumSize distributions can be used to generate morphological pattern spectra, which resume the

action of a size distribution on a specific image (Urbach & Wilkinson, 2002:305). A pattern

spectrum is defined as the first derivative of the normalized size distribution.


49/117



Definition 4.7 (Pattern spectrum)

Let ( )rN' be the first discrete derivative of the cumulative distribution function ( )r , the

pattern spectrum denoted by ( )rP is the discrete density function, which is defined by

0>r , ( ) ( )rNrP '= ( ) ( )rNrN += 1 . (4.14)

This function is also called a granulometric curve. An example of a pattern spectrum is shown

in Figure 4.4. This pattern spectrum corresponds to the image of seeds in Figure 4.3.

0 5 10 15 200

0.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16

radius

Volume

Pattern Spectrum

Figure 4.4: Pattern spectrum of the image of seeds.

The pattern spectrum is considered as a result of the quantification of the rate at which the

grayscale image ( )pf is being sieved. This method is useful for size and shape analysis of

granular images (Dougherty, 1992 and Maragos, 1989). In Chapter 6, this method has been

implemented for the classification seed images and for the characterization of steel images.


50/117



4.3 Linear grayscale granulometries and pattern spectrumHaralick et al (1991:560-565) has proposed an algorithm that allows the computation of

granulometry functions with respect to any family of homothetic elements. This explicitly

means that the base element or structuring element does not have to be convex. In this section,

a line structuring element is used to preserve some characteristics in the images. This

structuring element can be used in any direction (horizontal, vertical or at a specified angle) to

generate a pattern spectrum in order to simplify size or shape analysis. This method is also

computational efficiency compared to the use of a set of morphological structuring elements

which is computationally costly and intensive; therefore relatively slow (Vincent, 2000:122).

The method described here is the linear grayscale granulometry proposed by Vincent

(2000:126-128), based on openings.

4.3.1 Linear grayscale granulometriesIn this context, we consider a grayscale image I as defined in Chapter 3 and the structuring

element to be line segment nL as illustrated in Figure 4.5.

pixelsn

nL

1+

=

Figure 4.5: Illustration of a line segment.

The left and right neighbours of a pixel p belonging to the line segment considered in the

domainID are denoted by ( )lN p and ( )rN p respectively.


51/117



The effect of an opening by nL , 0n on a grayscale image Iis analyzed in this section. The

structuring element nL can be in any direction. In order to facilitate the description of this

approach, we merely deal with a horizontal line segment as a structuring element and the

horizontal maximum defined as follows:

Definition 4.8 (Horizontal line segment)

A horizontal line segment S , of length ( )Sl is defined as a set of pixels { }110 ,,, nppp such

that for ni


52/117



Therefore, by means of Definitions 4.8 and 4.9, an opening equivalent to the standard

morphological opening of an image I by a structuring element B denoted by BI is

proposed by Vincent (2000:126) as:

Definition 4.10 (Linear opening)

Consider a horizontal maximum { }110 ,,, = npppM , its length ( ) nMl = and M p

nk , ( )( ) ( )kI L p I p is calculated as

o y m < , the intensity values ( )I p and p Maximum 2 implies that the

opened region around the Maximum 2 remains unchanged

( ) ( ) ( )( )yI L p I p= .


53/117



o For y m= , the intensity values at the location of the maximum 2 changes to the

maximum of its neighbours (right and left, also see Equation 4.21). Hence the

m-th bin is removed and the resulting cross-section is less than the original

cross-section.

o y m > , the intensity values at the location of theMaximum 2 changes to lower

values than the maximum of the right neighbour and the left neighbour of

Maximum 2.

Equations 4.18 and 4.19 can be reduced to one equation: k n , ( )( ) ( )kI L p I p


54/117



Figure 4.7: Cross-section ofIwith a maximumM.

Figure 4.7 illustrates how the horizontal pattern spectrum is derived. By multiplying the height

( )21 hh by ( )Ml , we get the volume of the shaded area which corresponds to the local

contribution of this maximum to the ( )Ml -th bin of the horizontal pattern spectrum (Vincent,

2000:126).

As described in Section 4.3.1, the horizontal opening of size ( )Ml on the maximum Mcreates

a new plateau P at height equal to ( )( ) ( )( ){ }0 1max ,l r nI N p I N p . This plateau P contains

the maximum Mand may correspond itself to a maximum of nI L . In the case when it is a

maximum, its contribution to the ( )l P -th bin of the pattern spectrum can be computed.

Consequently, the pattern spectrum of a grayscale image Iis realized as follows: each line of

I is scanned from the left to the right. Each horizontal maximum of current line is then

identified, and its contribution to ( )0PS I is determined. If the new plateau containing the

previous maximum becomes a maximum, the contribution of this maximum to pattern

spectrum is computed as well. This process is iterated until the plateau formed is no longer a

2h

( )Ml

1h

Maximum M


55/117



maximum or until the horizontal line considered is covered. The next maximum of current line

is then considered, etc. until the line considered is covered. This process is illustrated by

Figure 4.8.

Figure 4.8: Illustration of linear grayscale algorithm for a line with two maxima.

Therefore the pattern spectrum is expressed as

( ) ( ) ( )( )( )[ ] [ ] max ,l rPS n PS n n I P I p I p= + , (4.21)

and the algorithm to generate the pattern spectrum is shown in Table 4.1.

Table 4.1: Algorithm of a horizontal granulometry for a line of image I(Vincent,

2000:126-127).

Initialize pattern spectrum: for each 0n > , [ ] 0PS n

For each maximum Mof this line (in any order) do:

- Let P M be the current maximum considered

- While P is a horizontal maximum, do:

( )l lp N P , neighbour of P to the left;


56/117



( )r rp N P , neighbour of P to the right;

( )n l P , length of horizontal maximum P ;

Add contribution of maximum P to n -th bin of pattern spectrum:

( ) ( ) ( )( )( )[ ] [ ] max ,l rPS n PS n n I P I p I p= + ;

For any pixel p in P :

( ) ( ) ( )( )max ,l rI P I p I p ;

P new plateau of pixels formed after opening of size n of P ;

- Put special marker on the left and right of the current plateau P so that

while processing subsequent maxima, we already know that this region

is a plateau and can skip over it;

The horizontal pattern spectrum corresponding to a sample image shown in Figure 4.3 is

illustrated in Figure 4.9.

0 50 100 1500

0.5

1

1.5

2

2.5

3

3.5

4

4.5x 10

5 Horizontal Pattern Spectrum

Length(n)

Volume

Figure 4.9: Illustration of the horizontal pattern spectrum of the mixed seeds image

shown in the left of figure 4.2.


57/117



This algorithm (Table 4.1) offers a very efficient, useful and accurate way to characterize a

grayscale image by extracting global size information directly from it. Additionally, the

execution time of this algorithm has eased the use of grayscale granulometries more

systematically. The results of implementing this algorithm on images of seed mixtures and

steel materials are presented in Chapter 6.

4.4 Opening trees and grayscale granulometriesThe concept of an opening tree is generally proposed as a gray level extension of the opening

transform or a grayscale generalization of the concept of granulometry functions. As known

from the grayscale granulometry when the size of the opening increases, the values of each

pixel decreases monotonically. In Vincent (1996:273-280), an opening tree was used to

compactly represent the successive values of each pixel of a cross-section when performing

linear openings of increasing size in any direction. Figure 4.8 illustrates how the opening tree

can be used to capture the entire granulometric information for the cross-section shown in

Figure 4.6.

Figure 4.10: Opening tree representation of the cross-section shown in figure 4.8. The

leaves of the tree represent the image pixels.


58/117



Each node denoted by ( ),h n represents the value h for the linear opening of size n . This

representation facilitates the computation of the pattern spectrum. This is mostly applied to

image of big size. An algorithm using the opening tree representation is illustrated in Table

4.2.

Table 4.2: Algorithm of a linear granulometry of the grayscale image Ifrom its opening

tree representation.

Initialize each bin of the pattern spectrum: for each 0n > , [ ] 0PS n

For each pixel p ofI do:

- ( )v I p ;

- ( ),h n node pointed at by p ;

- While ( ),h n exists, do:

[ ] [ ] ( )PS n PS n v h + ;

v h ;

( ),h n next node down to the tree;

Though the algorithm in Table 4.2 is less efficient than the algorithm described in Table 4.1, it

easily generalizes the computation of granulometries using maxima of linear opening in

several orientations.


59/117



4.5 SummaryTwo granulometric techniques were described in this chapter. The morphological

granulometry which uses convex structuring elements such as square, disk etc. was elaborated

on Section 4.3. The linear granulometry which used a horizontal line segment as a simple

structuring element was also discussed. Pattern spectra obtained from the morphological

granulometry were more descriptive than those obtained from the linear granulometry. In

terms of execution time the linear granulometry performed faster than the morphological

granulometry. An extension of the linear greyscale granulometry which is based on opening

trees was discussed in Section 4.4.


60/117



CHAPTER 5

To copy others is necessary but to copy oneself is pathetic(Pablo Picasso)

SLOPE PATTERN SPECTRA

A novel algorithm using integral images, to derive slope pattern spectra is proposed in this

chapter. Although many pattern spectra algorithms have their roots in mathematical

morphology the proposed algorithm does not have its roots in mathematical morphology.

Granulometries by means of their resulting pattern spectra constitute a useful tool for textureor image analysis since they are used to characterize size distributions. The slope pattern

spectra algorithm similar to morphological or linear granulometries extracts increasing slope

segments as pattern spectra. This slope pattern spectra algorithm is proposed as a fast and

robust alternative to granulometric methods.

5.1 Integral imageImage features, called integral image features, can be computed very rapidly by means of an

intermediate representation of an image called the integral image by Viola and Jones (2001).

These features are also referred to as summed area tables by Crow (1984:207-212) and

Lienhard & Maydt (2002:155-162). Moreover, the value of the integral image at location

( )yx, is the sum of all the grayscale pixel values above and to the left. In Viola and Jones

(2001) this is illustrated as in Figure 5.1 with reference to Definition 5.1.


61/117



Figure 5.1: The value at the point ( )yx, corresponds to the sum of all pixels in the

shaded area.

Definition 5.1 (Integral image)

Let ( )yxi , be a grayscale image. The corresponding integral image ( )yxii , is defined as

( ) ( )

=

yyxx

yxiyxii','

',', , (5.1)

and it can be computed in one pass over the original image using

( ) ( ) ( )

( ) ( ) ( )

+=

+=

yxsyxiiyxii

yxiyxsyxs

,,1,

,1,,, (5.2)

where ( )yxs , is the cumulative row and ( ) 01, =xs and ( ) 0,1 = yii .

According to Mitri et al (2005), the above definition can be reduced to

( ) ( ) = =

=

x

x

y

y

yxiyxii0' 0'

',', . (5.3)

In the next section, we will apply the integral image technique on a horizontal line segment

(see Definition 4.7).


62/117



By taking a horizontal line segment S of length ( )Sl , and applying the integral image

transformation on it, a horizontal line segment of the same length is obtained. Therefore we

propose a definition for this representation:

Definition 5.2 (Integral horizontal line segment)

An integral horizontal line segment IS , of length ( )l IS n= is a horizontal line segment

{ }110 ,,, nppp in the integral image ( )pF of a grayscale image ( )pf such that

0for i n < , ( ) ( )0

i

i k

k

F p f p=

= , (5.4)

and

0 1for i n < , ( ) ( )( )i r iF p F N p . (5.5)

An integral horizontal line segment is illustrated by Figure 5.2.

Figure 5.2: A line segment and its integral representation.

The right neighbour pixel is the sum of all left neighbour pixels. A growth in pixel value is

observed as we move toward the right. Hence the resulting integral image is monotonically

increasing. It is important to mention that the pixel intensity value may exceed 255, but as


63/117



underlined in D

Documents

Ignace Master