Quantum Inspired Meta-heuristics for Image Analysis E-Book

Sandip Dey

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 381

Veröffentlichungsjahr: 2019

Beschreibung

Introduces quantum inspired techniques for image analysis for pure and true gray scale/color images in a single/multi-objective environment This book will entice readers to design efficient meta-heuristics for image analysis in the quantum domain. It introduces them to the essence of quantum computing paradigm, its features, and properties, and elaborates on the fundamentals of different meta-heuristics and their application to image analysis. As a result, it will pave the way for designing and developing quantum computing inspired meta-heuristics to be applied to image analysis. Quantum Inspired Meta-heuristics for Image Analysis begins with a brief summary on image segmentation, quantum computing, and optimization. It also highlights a few relevant applications of the quantum based computing algorithms, meta-heuristics approach, and several thresholding algorithms in vogue. Next, it discusses a review of image analysis before moving on to an overview of six popular meta-heuristics and their algorithms and pseudo-codes. Subsequent chapters look at quantum inspired meta-heuristics for bi-level and gray scale multi-level image thresholding; quantum behaved meta-heuristics for true color multi-level image thresholding; and quantum inspired multi-objective algorithms for gray scale multi-level image thresholding. Each chapter concludes with a summary and sample questions. * Provides in-depth analysis of quantum mechanical principles * Offers comprehensive review of image analysis * Analyzes different state-of-the-art image thresholding approaches * Detailed current, popular standard meta-heuristics in use today * Guides readers step by step in the build-up of quantum inspired meta-heuristics * Includes a plethora of real life case studies and applications * Features statistical test analysis of the performances of the quantum inspired meta-heuristics vis-à-vis their conventional counterparts Quantum Inspired Meta-heuristics for Image Analysis is an excellent source of information for anyone working with or learning quantum inspired meta-heuristics for image analysis.

Leseprobe

Table of Contents

Cover

Preface

Acronyms

1 Introduction

1.1 Image Analysis

1.2 Prerequisites of Quantum Computing

1.3 Role of Optimization

1.4 Related Literature Survey

1.5 Organization of the Book

1.6 Conclusion

1.7 Summary

Exercise Questions

2 Review of Image Analysis

2.1 Introduction

2.2 Definition

2.3 Mathematical Formalism

2.4 Current Technologies

2.5 Overview of Different Thresholding Techniques

2.6 Applications of Image Analysis

2.7 Conclusion

2.8 Summary

Exercise Questions

3 Overview of Meta‐heuristics

3.1 Introduction

3.2 Genetic Algorithms

3.3 Particle Swarm Optimization

3.4 Ant Colony Optimization

3.5 Differential Evolution

3.6 Simulated Annealing

3.7 Tabu Search

3.8 Conclusion

3.9 Summary

Exercise Questions

4 Quantum Inspired Meta‐heuristics for Bi‐level Image Thresholding

4.1 Introduction

4.2 Quantum Inspired Genetic Algorithm

4.3 Quantum Inspired Particle Swarm Optimization

4.4 Implementation Results

4.5 Comparative Analysis among the Participating Algorithms

4.6 Conclusion

4.7 Summary

Exercise Questions

Coding Examples

5 Quantum Inspired Meta‐Heuristics for Gray‐Scale Multi‐Level Image Thresholding

5.1 Introduction

5.2 Quantum Inspired Genetic Algorithm

5.3 Quantum Inspired Particle Swarm Optimization

5.4 Quantum Inspired Differential Evolution

5.5 Quantum Inspired Ant Colony Optimization

5.6 Quantum Inspired Simulated Annealing

5.7 Quantum Inspired Tabu Search

5.8 Implementation Results

5.9 Comparison of QIPSO with Other Existing Algorithms

5.10 Conclusion

5.11 Summary

Exercise Questions

Coding Examples

6 Quantum Behaved Meta‐Heuristics for True Color Multi‐Level Image Thresholding

6.1 Introduction

6.2 Background

6.3 Quantum Inspired Ant Colony Optimization

6.4 Quantum Inspired Differential Evolution

6.5 Quantum Inspired Particle Swarm Optimization

6.6 Quantum Inspired Genetic Algorithm

6.7 Quantum Inspired Simulated Annealing

6.8 Quantum Inspired Tabu Search

6.9 Implementation Results

6.10 Conclusion

6.11 Summary

Exercise Questions

Coding examples

7 Quantum Inspired Multi‐objective Algorithms for Multi‐level Image Thresholding

7.1 Introduction

7.2 Multi‐objective Optimization

7.3 Experimental Methodology for Gray‐Scale Multi‐Level Image Thresholding

7.4 Implementation Results

7.5 Conclusion

7.6 Summary

Exercise Questions

Coding Examples

8 Conclusion

Bibliography

Index

End User License Agreement

List of Tables

Chapter 4

Table 4.1 Optimum results of QIGA, GA [127,210] for three gray‐scale images Lena...

Table 4.5 Optimum results of QIGA, GA [127,210] for three gray‐scale images Lena...

Table 4.6 Optimum results of QIPSO and PSO [144] for three gray‐scale images Len...

Table 4.10 Optimum results of QIPSO and PSO [144] for three gray‐scale images Le...

Table 4.11 Experimental results of Han et al. [121] for three gray‐scale images ...

Table 4.15 Experimental results of Han et al. [121] for three gray‐scale images ...

Table 4.16 Optimum results of QIGA, GA [127,210] for three gray‐scale images Bab...

Table 4.21 Optimum results of QIGA, GA [127,210] for three gray‐scale images Bab...

Table 4.22 Experimental results of Han et al. [121] for three gray‐scale images ...

Table 4.27 Experimental results of Han et al. [121] for three gray‐scale images ...

Table 4.28 Comparative performance analysis of QIGA and GA.

Table 4.29 Optimum results of QIGA, GA [127,210] for three gray‐scale images Len...

Table 4.31 Optimum results of QIGA, GA [127,210] for three gray‐scale images Len...

Table 4.32 Experimental results of Han et al. [121] for three gray‐scale images ...

Table 4.34 Experimental results of Han et al. [121] for three gray‐scale images ...

Chapter 5

Table 5.1 List of worst case time complexity for the proposed algorithms.

Table 5.2 Parameter set for the proposed QIGA, QIPSO, QIDE, QIACO, QISA, and QIT...

Table 5.3 Best results of QIGA, QIPSO, and QIDE for multi‐level thresholding for...

Table 5.6 Best results of QIACO, QISA, and QITS for multi‐level thresholding for...

Table 5.7 Average values of fitness

and standard deviation

of QIGA, QIPSO, QI...

Table 5.9 Average values of fitness

and standard deviation

of QIGA, QIPSO, QI...

Table 5.10 Data sets for QIGA, QIPSO, QIDE, QIACO, QISA, and QITS used in the Fr...

Table 5.11 Consensus results of multi‐level thresholding for Image1, ImageN30C30...

Table 5.12 Consensus results of multi‐level thresholding for Lena, B2, Barbara, ...

Table 5.13 Consensus results of multi‐level thresholding for Jetplane, Jungle, P...

Table 5.14 Best results of QIPSO, TSMO, MTT, MBF, PSO, and GA for multi‐level ...

Table 5.16 Best results of QIPSO, TSMO, MTT, MBF, PSO, and GA for multi‐level th...

Table 5.17 Average values of fitness

and standard deviation

of QIPSO, TSMO, M...

Table 5.19 Average values of fitness

and standard deviation

of QIPSO, TSMO, M...

Table 5.20 Data sets for QIPSO, TSMO, MTT, MBF, PSO, and GA used in the Friedman...

Table 5.21 Best results of QIACO, ACO, QISA, and SA for multi‐level thresholding...

Table 5.22 Average fitness (

) and standard deviation

values of QIACO, ACO, QI...

Table 5.23 Results of the two‐tailed

‐test.

Chapter 6

Table 6.1 Parameters specification for QIPSOMLTCI, PSO, QIACOMLTCI, ACO, QIDEMLT...

Table 6.2 Best results obtained from QIPSOMLTCI and PSO for multi‐level threshol...

Table 6.9 Best results obtained from CoDE and BSA for multi‐level thresholding o...

Table 6.10 Execution time

and PSNR of QIPSOMLTCI, PSO, QIACOMLTCI, ACO, QIDEMLT...

Table 6.11 Execution time

and PSNR of QIPSOMLTCI, PSO, QIACOMLTCI, ACO, QIDEMLT...

Table 6.12 Average fitness (

) and standard deviation

of QIPSOMLTCI, PSO, QIAC...

Table 6.13 Average fitness (

) and standard deviation

of QIPSOMLTCI, PSO, QIAC...

Table 6.14 Data sets used in QIPSOMLTCI, PSO, QIACOMLTCI, ACO, QIDEMLTCI, DE, Co...

Table 6.15 Best results obtained for QIPSOMLTCI, PSO, QIDEMLTCI, and DE for mult...

Table 6.16 Mean fitness (

) and standard deviation

of QIPSOMLTCI, PSO, QIDEMLT...

Table 6.17 Results of two‐tailed

‐test for multi‐level thresholding of test imag...

Table 6.18 Parameters specification for QIGAMLTCI, QISAMLTCI, QIPSOMLTCI, QIDEML...

Table 6.19 Best results obtained for QIGAMLTCI and QISAMLTCI for multi‐level thr...

Table 6.28 Best results obtained for BSA and CoDE for multi‐level thresholding o...

Table 6.29 Best results obtained for QIGAMLTCI and QISAMLTCI for multi‐level thr...

Table 6.38 Best results obtained for BSA and CoDE for multi‐level thresholding o...

Table 6.39 Computational time (

) of QIGAMLTCI, QISAMLTCI,QIDEMLTCI, QIPSOMLTCI,...

Table 6.40 Computational time (

) of QIGAMLTCI, QISAMLTCI,QIDEMLTCI, QIPSOMLTCI,...

Table 6.41 PSNR of QIGAMLTCI, QISAMLTCI, QIDEMLTCI, QIPSOMLTCI, GA, SA, DE, PSO,...

Table 6.42 PSNR of QIGAMLTCI, QISAMLTCI, QIDEMLTCI, QIPSOMLTCI, GA, SA, DE, PSO,...

Table 6.43 Data sets used in QIGAMLTCI, QISAMLTCI, QIPSOMLTCI, QIDEMLTCI, GA, SA...

Table 6.44 Data sets used in QIGAMLTCI, QISAMLTCI, QIPSOMLTCI, QIDEMLTCI, GA, SA...

Table 6.45 Difference between pairwise fitness values of the different technique...

Table 6.50 Difference between pairwise fitness values of the different technique...

Table 6.51 The median‐based estimation among the participating techniques for

, ...

Table 6.52 The median‐based estimation among the participating techniques for

, ...

Table 6.53 Best results obtained for QITSMLTCI and TS for multi‐level thresholdi...

Table 6.54 Mean fitness (

) and standard deviation

of QITSMLTCI and TS for mul...

Table 6.55 Test results of one‐tailed

‐test for Tulips and Barge at different le...

Chapter 7

Table 7.1 Parameters specification for QINSGA‐II, NSGA‐II, and SMS‐EMOA.

Table 7.2 Best results obtained for QINSGA‐II, NSGA‐II, and SMS‐EMOA for multi‐l...

Table 7.3 Execution time

of QINSGA‐II, NSGA‐II, and SMS‐EMOA for multi‐level th...

Table 7.4 Average fitness (

) and standard deviation

of QINSGA‐II, NSGA‐II, an...

Table 7.6 Statistical comparison of QINSGA‐II to NSGA‐II and SMS‐EMOA with refer...

Table 7.5 IGD and HV values of QINSGA‐II, NSGA‐II, and SMS‐EMOA for multi‐level ...

Table 7.7 Data sets used in QINSGA‐II, NSGA‐II, and SMS‐EMOA for the Friedman te...

Table 7.8 Best results for QISAMO and SAMO for bi‐level thresholding of Airplane...

Table 7.9 PSNR and computational time of best results of QISAMO and SAMO of Airp...

Table 7.10 Mean

and standard deviation

of QISAMO and SAMO of Airplane, Anhing...

Table 7.11 Best results of QIMOPSO, PSO, QIMOACO, and ACO.

Table 7.12 Mean fitness (

) and standard deviation

of QIMOPSO, PSO, QIMOACO, a...

Table 7.13 PSNR values of QIMOPSO, PSO, QIMOACO, and ACO.

List of Illustrations

Chapter 1

Figure 1.1 Steps in image analysis.

Chapter 4

Figure 4.1 QIGA flow diagram.

Figure 4.2 Quantum interference.

Figure 4.3 The solution matrix for bi‐level image thresholding.

Figure 4.4 The quantum crossover.

Figure 4.5 The quantum mutation.

Figure 4.6 QIPSO flow diagram.

Figure 4.7 Original test images (a) Lena, (b) Peppers, (c) Woman, (d) Baboon, (...

Figure 4.8 Thresholded images of Lena, Peppers and Woman using Otsu's method [1...

Figure 4.9 Convergence curve for Otsu's method [192] for QIGA.

Figure 4.10 Convergence curve for Ramesh's method [207] for QIGA.

Figure 4.11 Convergence curve for Li's method [158] for QIGA.

Figure 4.12 Convergence curve for correlation coefficient [26,145,226] for QIGA...

Figure 4.13 Convergence curve for Shanbag's method [234] for QIGA.

Figure 4.14 Convergence curve for Otsu's method [192] for QIPSO.

Figure 4.15 Convergence curve for Ramesh's method [207] for QIPSO.

Figure 4.16 Convergence curve for Li's method [158] for QIPSO.

Figure 4.17 Convergence curve for correlation coefficient [26,145,226] for QIPS...

Figure 4.18 Convergence curve for Shanbag's method [234] for QIPSO.

Figure 4.19 Convergence curve for Otsu's method [192] for GA and PSO.

Figure 4.20 Convergence curve for Ramesh's method [207] for GA and PSO.

Figure 4.21 Convergence curve for Li's method [158] for GA and PSO.

Figure 4.22 Convergence curve for correlation coefficient [26,145,226] for GA a...

Figure 4.23 Convergence curve for Shanbag's method [234] for GA and PSO.

Figure 4.24 Look‐up table of Han et al. for Lena for

and

.

Figure 4.25 Look‐up table of Han et al. for Peppers for

and

.

Figure 4.26 Look‐up table of Han et al. for Woman for

and

.

Figure 4.27 Convergence curve of Otsu's method [192] for Han et al. [121].

Figure 4.28 Convergence curve of Ramesh's method [207] for Han et al. [121].

Figure 4.29 Convergence curve of Li's method [158] for Han et al. [121].

Figure 4.30 Convergence curve of correlation coefficient [26,145,226] for Han e...

Figure 4.31 Convergence curve of Shanbag's method [234] for Han et al. [121].

Figure 4.32 Thresholded images of Lena, Peppers and Woman using Otsu's method [...

Figure 4.33 Thresholded images of Baboon, Peppers and Corridor using Wu's metho...

Figure 4.34 Thresholded images of Baboon, Peppers, and Corridor using Silva's m...

Figure 4.35 Convergence curve of Wu's method [274] for QIGA.

Figure 4.36 Convergence curve of Renyi's method [220] for QIGA.

Figure 4.37 Convergence curve of Yen's method [277] for QIGA.

Figure 4.38 Convergence curve of Johannsen's method [135] for QIGA.

Figure 4.39 Convergence curve of Silva's method [236] for QIGA.

Figure 4.40 Convergence curve of Linear Index of Fuzziness [130,257] for QIGA.

Figure 4.41 Thresholded images of Baboon, Peppers, and Corridor using Wu's meth...

Figure 4.42 Thresholded images of Baboon, Peppers, and Corridor using Silva's m...

Figure 4.43 Convergence curve of Wu's method [274] for Han et al. [121].

Figure 4.44 Convergence curve of Renyi's method [220] for Han et al. [121].

Figure 4.45 Convergence curve of Yen's method [277] for Han et al. [121].

Figure 4.46 Convergence curve of Johannsen's method [135] for Han et al. [121].

Figure 4.47 Convergence curve of Silva's method [236] for Han et al. [121].

Figure 4.48 Convergence curve of Linear Index of Fuzziness [130,257] for Han et...

Figure 4.49 Thresholded images of Lena and Barbara using Brink's method [34] in...

Figure 4.50 Convergence curve of Brink's method [34] for QIGA.

Figure 4.51 Convergence curve of Pun's method [206] for QIGA.

Figure 4.52 Convergence curve of Kapur's method [140] for QIGA.

Figure 4.53 Thresholded images of Lena and Barbara using Brink's method [34] in...

Figure 4.54 Convergence curve of Brink's method [34] for Han et al. [121].

Figure 4.55 Convergence curve of Pun's method [206] for Han et al. [121].

Figure 4.56 Convergence curve of Kapur's method [140] for Han et al. [121].

Figure 4.57 Sample code of Func

, Func

, and Func

for QIGA.

Figure 4.58 Sample code of Func

, Func

, Func

, Func

, and Func

for QIGA.

Figure 4.59 Sample code of Func

and Func

for QIGA.

Chapter 5

Figure 5.1 Quantum orthogonality.

Figure 5.2 The solution matrix for multi‐level image thresholding.

Figure 5.3 Original synthetic images with (a) complex backgrounds and (b) low c...

Figure 5.4 Synthetic images: (a) Noise‐30,Contrast‐30, (b) Noise‐30,Contrast‐80...

Figure 5.5 Original test images (a) B2, (b) Boat, (c) Cameraman, (d) Jetplane, ...

Figure 5.6 For

, images (a)–(d), for Image1, (e)–(h), for ImageN30C30, (i)–(l)...

Figure 5.7 For

, images (a)–(d), for Lena, (e)–(h), for B2, (i)–(l), for Barba...

Figure 5.8 For

, images (a)–(d), for Jetplane, (e)–(h), for Pinecone, (i)–(l),...

Figure 5.9 For

, convergence curves of the proposed algorithms (a) for Image1,...

Figure 5.10 For

, convergence curves of the proposed algorithms (a) for Lena, ...

Figure 5.11 For

, convergence curves of the proposed algorithms (a) for Jetpla...

Figure 5.12 For

, convergence curves of the proposed algorithms (a) for Image1...

Figure 5.13 For

, convergence curves of the proposed algorithms (a) for Lena, ...

Figure 5.14 For

, convergence curves of the proposed algorithms (a) for Jetpla...

Figure 5.15 For

, convergence curves of the comparable algorithms (a) for Imag...

Figure 5.16 For

, convergence curves of the comparable algorithms (a) for Lena...

Figure 5.17 For

, convergence curves of the comparable algorithms (a) for Jetp...

Figure 5.18 For

, convergence curves of the comparable algorithms (a) for Imag...

Figure 5.19 For

, convergence curves of the comparable algorithms (a) for Lena...

Figure 5.20 For

, convergence curves of the comparable algorithms (a) for Jetp...

Figure 5.21 Sample code of Func

, Func

, Func

, and Func

for QIACO.

Figure 5.22 Sample code of Func

, Func

and Func

for QIACO.

Figure 5.23 Sample code of Func

and Func

for QIDE.

Figure 5.24 Sample code of Func

, Func

, and Func

for QIDE.

Figure 5.25 Sample code of Func

, Func

, Func

, and Func

for QITS.

Chapter 6

Figure 6.1 Original test images (a) Airplane, (b) Fruits, (c) House, (d) Sailbo...

Figure 6.2 Original test images (a) Baboon, (b) Bird, (c) Elephant, (d) Seaport...

Figure 6.3 For

, images (a)–(d), for Airplane, (e)–(h), for Fruits, (i)–(l), f...

Figure 6.4 For

, images (a)–(d), for Barbara, (e)–(h), for Lostlake, (i)–(l), ...

Figure 6.5 Convergence curves for

, (a) Airplane, (b) Fruits, (c) House, (d) S...

Figure 6.6 Convergence curves for

, (a) Barbara, (b) Lostlake, (c) Anhinga, (d...

Figure 6.7 Convergence curves for

, (a) Airplane, (b) Fruits, (c) House, (d) S...

Figure 6.8 Convergence curves for

, (a) Barbara, (b) Lostlake, (c) Anhinga, (d...

Figure 6.9 For

, images (a)–(c), for Baboon, (d)–(f), for Bird, (g)–(i), for E...

Figure 6.10 For

, images (a)–(c), for Monolake, (d)–(f), for Mona Lisa, (g)–(i...

Figure 6.11 For

, images (a)–(c), for Baboon, (d)–(f), for Bird, (g)–(i), for ...

Figure 6.12 For

, images (a)–(c), for Monolake, (d)–(f), for Mona Lisa, (g)–(i...

Figure 6.13 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.14 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.15 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.16 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.17 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.18 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.19 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.20 Convergence curves (1:QIGAMLTCI, 2:QISAMLTCI, 3:QIPSOMLTCI, 4:QIDEM...

Figure 6.21 Sample code of Func

1

for QIPSOMLTCI.

Figure 6.22 Sample code of Func

2

, Func

3

, Func

4

, Func

5

, and Func

6

for QIPSOMLTCI...

Figure 6.23 Sample code of Func

7

for QIPSOMLTCI.

Figure 6.24 Sample code of Func

8

for QIPSOMLTCI.

Figure 6.25 Sample code of Func

1

, Func

2

, and Func

3

for QISAMLTCI.

Figure 6.26 Sample code of Func

4

and Func

5

for QISAMLTCI.

Figure 6.27 Sample code of Func

6

and Func

7

for QISAMLTCI.

Chapter 7

Figure 7.1 Original test images (a) Anhinga, (b) Couple, (c) Desert, (d) Greenp...

Figure 7.2 For

, images (a)–(c), for Lena, (d)–(f), for Peppers, (g)–(i), for ...

Figure 7.3 For

, convergence curves (a)–(c), for Lena, (d)–(f), for Peppers, (...

Figure 7.4 For

, convergence curves (a)–(c), for

, (d)–(f), for

, (g)–(i), f...

Figure 7.5 Sample code of Func

, Func

, and Func

for QINSGA‐II.

Figure 7.6Figure 7.6 Sample code of Func

and Func

for QINSGA‐II.

Figure 7.7Figure 7.7 Sample code of Func

for QINSGA‐II.

Figure 7.8Figure 7.8 Sample code of Func

, Func

, Func

, and Func

for QINSGA‐I...

Figure 7.9 Sample code of Func

and Func

for QINSGA‐II.

Guide

Cover

Table of Contents

Begin Reading

Pages

iii

vi

v

xiii

xiv

xv

xvi

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

157

158

159

160

161

162

163

164

165

166

167

168

169

170

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

301

302

303

304

305

306

307

308

309

310

311

313

314

315

316

317

318

320

321

322

323

324

325

326

327

328

329

333

334

335

336

337

338

339

340

341

344

345

346

348

349

350

351

352

353

354

355

356

357

358

E1

Quantum Inspired Meta‐heuristics for Image Analysis

Sandip Dey

Global Institute of Management and TechnologyKrishnanagar, Nadia,West BengalIndia

Siddhartha Bhattacharyya

RCC Institute of Information TechnologyKolkataIndia

Ujjwal Maulik

Jadavpur UniversityKolkataIndia

Copyright

This edition first published 2019

© 2019 John Wiley & Sons Ltd

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Sandip Dey, Siddhartha Bhattacharyya, and Ujjwal Maulik to be identified as the authors of this work has been asserted in accordance with law.

Registered Offices

John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

Editorial Office

The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print‐on‐demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of Warranty

While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging‐in‐Publication Data

Names: Dey, Sandip, 1977‐ author. | Bhattacharyya, Siddhartha, 1975‐ author.

 | Maulik, Ujjwal, author.

Title: Quantum Inspired Meta-heuristics for Image Analysis / Dr. Sandip Dey

 (Global Institute of Management and Technology Krishnanagar, Nadia, West Bengal, India),

 Professor Siddhartha Bhattacharyya (RCC Institute of Information Technology, Kolkata, India),

 Professor Ujjwal Maulik (Jadavpur University, Kolkata, India).

Description: Hoboken, NJ : Wiley, 2019. | Includes bibliographical references

 and index. |

Identifiers: LCCN 2019001402 (print) | LCCN 2019004054 (ebook) | ISBN

 9781119488774 (Adobe PDF) | ISBN 9781119488781 (ePub) | ISBN 9781119488750

 (hardcover)

Subjects: LCSH: Image segmentation. | Image analysis. | Metaheuristics. |

 Heuristic algorithms.

Classification: LCC TA1638.4 (ebook) | LCC TA1638.4 .D49 2019 (print) | DDC

 006.4/2015181–dc23

LC record available at https://lccn.loc.gov/2019001402

Cover Design: Wiley

Cover Image: © issaro prakalung/Shutterstock

Sandip Dey would like to dedicate this book to the loving memory of his father, the late Dhananjoy Dey, his mother Smt. Gita Dey, his wife Swagata Dey Sarkar, his children Sunishka and Shriaan, his siblings Kakali, Tanusree, Sanjoy and his nephews Shreyash and Adrishan.

Siddhartha Bhattacharyya would like to dedicate this book to his father, the late Ajit Kumar Bhattacharyya, his mother, the late Hashi Bhattacharyya, his beloved wife Rashni Bhattacharyya, and Padmashree Professor Ajoy Kumar Ray, Honorable Chairman, RCC Institute of Information Technology, Kolkata, India.

Ujjwal Maulik would like to dedicate this book to his son Utsav, his wife Sanghamitra and all his students and friends.

Preface

In the present information era, the processing and retrieval of useful image information and multimedia‐based data, for the purpose of faithful and realistic analysis, are supposed to be of the highest importance. One significant image processing chore is to separate objects or other important information in digital images through thresholding of the image under consideration. Efficient techniques are required in order to develop an appropriate analysis of noisy and noise‐free image data to obtain suitable object‐specific information.

The soft computing approaches have certain tools and techniques among various other approaches, which integrate intelligent thinking and principles. Fuzzy logic, Neural networks, Fuzzy sets, and Evolutionary Computation are used as the computing framework, which successfully combines these intelligent principles.

This book attempts to address the problem of image thresholding using classical algorithms. Attempts have also been made to take out the intrinsic limitations in the present soft computing methods as initiated by theoretical investigations. New versions of quantum inspired meta‐heuristics algorithms have also been introduced, taking into cognizance the time and space complexity of present approaches.

The introductory chapter of the book presents a brief summary on image analysis, quantum computing, and optimization. The chapter highlights quantum solutions of NP‐complete problems in brief. This introductory chapter also presents a related literature survey using different approaches, such as quantum‐based approaches, meta‐heuristic‐based approaches and multi‐objective‐based approaches. The chapter also discusses the scope and organization of the book.

Chapter 2 focuses on the review of image analysis. This chapter discusses the mathematical formalism of image segmentation technique. It also highlights different digital image analysis approaches. It also throws light on popular image thresholding techniques in the binary, multi‐level and gray‐scale domains. A short summary of the applications of image analysis is also presented. Finally, the chapter ends with a relevant conclusion; a chapter summary and a set of exercise questions are provided.

Chapter 3 focuses on the overview of some popular meta‐heuristics. The fundamentals of each of them are briefly discussed in this chapter. Pseudo‐code of the corresponding meta‐heuristic is also presented after each section. The summary of the chapter and a set of exercise questions are provided at the end of this chapter.

Chapter 4 addresses the intrinsic limitations of classical algorithms to deal with image data for binary thresholding. The chapter develops two different quantum‐based standard conventional algorithms for binary image thresholding. The basic quantum computing principles have been recognized to develop the proposed approaches. The features of quantum computing have been properly linked with the framework of popular classical algorithms for the formation of the proposed algorithms. Experiments have been conducted with different combinations of the parameter settings. The proposed algorithms are compared with several other algorithms. The implementation results are presented for the proposed algorithms and other comparable algorithms.

In line with the objectives of Chapter 4, several novel versions of quantum inspired classical algorithms are proposed in Chapter 5. This chapter concentrates on the functional modification of the quantum inspired meta‐heuristic algorithms as an attempt to extend them to multi‐level and gray‐scale domain. Application of the proposed algorithms is demonstrated on a set of synthetic/real‐life gray‐scale images. As a sequel to these algorithms, experiments were conducted with several other algorithms for comparative purposes. The experiments were conducted with different parameter values. Implementation results are reported for all the participating algorithms.

Parallel extensions to these quantum inspired classical algorithms are presented in Chapter 6. This approach introduces thresholding of color image information. The parallel operation of the proposed framework reduces the time complexity of the color image thresholding. Application of the proposed versions of quantum inspired algorithms is exhibited using thresholding of multi‐level and color images. As a result of the comparative study, the proposed algorithms are compared with other popular algorithms. Implementation results with several parameter adjustments are reported.

Chapter 7 introduces several quantum inspired multi‐objective algorithms using different approaches. First, an NSGA‐II‐based quantum inspired algorithm is proposed in a multi‐objective framework. Later, several quantum inspired classical algorithms are developed in a multi‐objective flavor for bi‐level, multi‐level and gray‐scale image thresholding.

Different parameters settings are used for the clarification of proposed algorithms. Application of these algorithms is demonstrated on several real‐life grayscale images. A number of other popular algorithms are used for comparative purposes. The test results are reported for all of the participating algorithms.

Finally, the concluding chapter ends the book. This chapter presents an outlook of future directions of research in this area.

Sodepur

2 November 2018

Sandip Dey

Siddhartha Bhattacharyya

Ujjwal Maulik

Acronyms

ACO

Ant Colony Optimization

AI

Artificial Intelligence

BSA

Backtracking Search Optimization Algorithm

CNOT

Controlled NOT Gate

CoDE

Composite DE

DE

Differential Evolution

EA

Evolutionary Algorithm

EC

Evolutionary Computation

EP

Evolutionary Programming

ES

Evolutionary Strategies

GA

Genetic Algorithm

GP

Genetic Programming

HDQ

Heuristic Search Designed Quantum Algorithm

HV

Hypervolume

IGD

Inverted Generational Distance

MA

Metropolis Algorithm

MADS

Mesh Adaptive Direct Search

MBF

Modified Bacterial Foraging

MDS

Multidirectional Search

MODE

Multi‐Objective Differential Evolutionary Algorithm

MOEA

Multi‐Objective Evolutionary Algorithm

MOGA

Multi‐Objective Genetic Algorithm

MOO

Multi‐Objective Optimization

MOSA

Multi‐Objective Simulated Annealing

MRI

Magnetic Resonance Imaging

MTT

Maximum Tsallis entropy Thresholding

NM

Nelder‐Mead

NPGA

Niched‐Pareto Genetic Algorithm

NSGA‐II

Non‐dominated Sorting Genetic Algorithm II

NSGA

Non‐dominated Sorting Genetic Algorithm

OCEC

Organizational Coevolutionary algorithm for Classification

PAES

Pareto Archived Evolution Strategy

PESA

Pareto Envelope‐based Selection Algorithm

PET

Positron Emission Tomography

PO

Pareto Optimal

PSNR

Peak Signal‐to‐Noise Ratio

PSO

Particle Swarm Optimization

QC

Quantum Computer

QEA

Quantum Evolutionary Algorithm

QFT

Quantum Fourier Transform

QIACO

Quantum Inspired Ant Colony Optimization

QIACOMLTCI

Quantum Inspired Ant Colony Optimization for Color Image Thresholding

QIDE

Quantum Inspired Deferential Evolution

QIDEMLTCI

Quantum Inspired Deferential Evolution for Color Image Thresholding

QIEA

Quantum Inspired Evolutionary Algorithms

QIGA

Quantum Inspired Genetic Algorithm

QIGAMLTCI

Quantum Inspired Genetic Algorithm for Color Image Thresholding

QIMOACO

Quantum Inspired Multi‐objective Ant Colony Optimization

QIMOPSO

Quantum Inspired Multi‐objective Particle Swarm Optimization

QINSGA‐II

Quantum Inspired NSGA‐II

QIPSO

Quantum Inspired Particle Swarm Optimization

QIPSOMLTCI

Quantum Inspired Particle Swarm Optimization for Color Image Thresholding

QISA

Quantum Inspired Simulated Annealing

QISAMLTCI

Quantum Inspired Simulated Annealing for Color Image Thresholding

QISAMO

Quantum Inspired Simulated Annealing for Multi‐objective algorithms

QITS

Quantum Inspired Tabu Search

QITSMLTCI

Quantum Inspired Tabu Search for Color Image Thresholding

RMSE

Root mean‐squared error

SA

Simulated Annealing

SAGA

Simulated Annealing and Genetic Algorithm

SC

Soft Computing

SOO

Single‐Objective Optimization

SPEA2

Strength Pareto Evolutionary Algorithm 2

SPEA

Strength Pareto Evolutionary Algorithm

SVM

Support Vector Machines

TS

Tabu Search

TSMO

Two‐Stage Multithreshold Otsu

TSP

Travelling Salesman Problems

VEGA

Vector‐Evaluated Genetic Algorithm

X‐ray

X‐radiation

1Introduction

A quantum computer, as the name suggests, fundamentally works on several quantum physical characteristics. It is also considered as the field of study, primarily focused on evolving computer technology using the features of quantum theory, which expounds the nature of energy and substance and its behavior on the quantum level, i.e., at the atomic and subatomic level. Developing a quantum computer would mark an advance in computing competency far superior to any current computers. Thus, the use of quantum computers could be an immense improvement on current computers because they have enormous processing capability, even exponentially, compared to classical computers. The supremacy of processing is gained through the capacity of handling multiple states at once, and performing tasks exploiting all the promising permutations in chorus. The term quantum computing is fundamentally a synergistic combination of thoughts from quantum physics, classical information theory, and computer science.

Soft computing (SC), introduced by Lotfi A. Zadeh [282], manages the soft meaning of thoughts. SC, comprising a variety of thoughts and practices, is fundamentally used to solve the difficulties stumbled upon in real‐life problems. This can be used to exploit the uncertainty problem almost with zero difficulty. This can also handle real‐world state of affairs and afford lower solution costs [29]. The advantageous features of SC can best be described as leniency of approximation, vagueness, robustness, and partial truth [103,215]. This is a comparatively novel computing paradigm which involves a synergistic amalgamation of essentially several additional computing paradigms, which may include fuzzy logic, evolutionary computation, neural networks, machine learning, support vector machines, and also probabilistic reasoning. SC can combine the aforementioned computing paradigms to offer a framework for designing many information processing applications that can function in the real world. This synergism was called computational intelligence by Bezdek [24]. These SC components are different from each other in more than one way. These can be used to operate either autonomously or conjointly, depending on the application domain.

Evolutionary computation (EC) is a search and optimization procedure which uses biological evolution inspired by Darwinian principles [14,83,136]. It is stochastic and delivers robust search and optimization methods. It starts with a pool of trial solutions in its search space, which is called the population. Numerous in‐built operators are generally applied to each individual of the population, which may cause population diversity and also leads to better solutions. A metric, called the fitness function (objective function), is employed to determine the suitability of an individual in the population at any particular generation. As soon as the fitness of the existing individuals in the population is computed, the operators are successively applied to produce a new population for the successive generations. Distinct examples of EC may include the Differential Evolution [242], Genetic Algorithms [127,210], Particle Swarm Optimization [144], and Ant Colony Optimization [196], to name but a few. Simulated annealing [147] is another popular example of meta‐heuristic and optimization techniques in this regard. This technique exploits the features of statistical mechanics concerning the behavior of atoms at very low temperature to find minimal cost solutions of any given optimization problem. EC techniques are also useful when dealing with several conflicting objectives, called the multi‐objective evolutionary techniques. These search procedures provide a set of solutions, called optimal solutions. Some typical examples of these techniques may include the multi‐objective differential evolutionary algorithm (MODE) [275], the multi‐objective genetic algorithm (MOGA) [172,183], and multi‐objective simulated annealing (MOSA) [237], to name but a few.

Fuzzy logic tenders more elegant alternatives to conventional (Boolean) logic. Fuzzy logic is able to handle the notion of partial truth competently [139,141,215,282,283]. A neural network is a computing framework comprising huge numbers of simple, exceedingly unified processing elements called artificial neurons, which add up to an elemental computing primitive [82,102,150]. Machine learning is a kind of intelligent program which works on example data. It learns from previous experiences and is used to enhance the performances by optimizing a given criterion [5,156,178]. Support vector machines (SVM) are known to be the collection of supervised learning techniques. SVMs are very useful in regression and classification analysis [38,50]. SVMs are fit to handle a number of real‐life applications, including text and image classification, or biosequences analysis, to name but a few [38,50]. Nowadays SVMs are often used as the standard and effective tool for data mining and machine learning activities. Probabilistic reasoning can be defined as the computational method which uses certain logic and probability theory to handle uncertain circumstances [201,202].

Many researchers utilize the basic features of quantum computing in various evolutionary algorithmic frameworks in the soft computing discipline. The underlying principles of quantum computing are injected into different meta‐heuristic structures to develop different quantum inspired techniques. In the context of image analysis, the features are extracted both from pictographic and non‐numeric data and are used in these algorithms in different ways [27]. This chapter provides an insight into the various facets of the quantum computing, image segmentation, image thresholding, and optimization. This chapter is arranged into a number of relevant sections. Section 1.1 presents an overview of the underlying concepts of image analysis. A brief overview of image segmentation and image thresholding is discussed in this section. Section 1.2 throws light on the basics of quantum computing in detail. Section 1.3 discusses the necessity of optimization in the real world. This section presents different types of optimization procedures with their application in the real world. Apart from the above issues, this chapter also presents a short description of the literature survey on related topics. Different types of approaches in this regard are in detail presented in Section 1.4. The organization of the book is presented in Section 1.5. The chapter concludes in Section 1.6. It also shows the direction of research that can be used as future reference. A brief summary of the chapter is given in Section 1.7. In Section 1.8, a set of questions related to the theme of the chapter is presented.

1.1 Image Analysis

Image analysis has a vital role in extracting relevant and meaningful information from images. There are few automatic or semi‐automatic techniques, called computer/machine vision, pattern recognition, image description, image understanding to name but a few, used for this purpose. Image segmentation can be thought of as the most fundamental and significant step in several image analysis techniques. A good example of image analysis may involve the organized activities of the human eye with the brain. Computer‐based image analysis can be thought of as the best alternative which may reduce human effort in order to make this process faster, more efficient, and automatic. Image analysis has numerous applications in a variety of fields such as medicine, biology, robotics, remote sensing, and manufacturing. It also makes a significant contribution in different industrial activities such as process control, quality control, etc. For example, in the food industry, image analysis plays a significant role to ensure the uniform shape, size and texture of the final food products.

In medical image analysis, clinical images of different views are captured to diagnose and detect diseases in relation to body organs, and study standard physiological procedures for future references. These investigations can be accomplished through images attained from various imaging technologies, such as magnetic resonance imaging (MRI), radiology, ultrasound, etc. For example, image analysis methodology is of the utmost importance in cancer detection and diagnosis [44], thus it helps the physician to ensure accurate treatment for their patient. In the context of cancer treatment, several features like shape, size, and homogeneity of a tumor are taken into consideration when classifying and diagnosing cancer images. Different image analysis algorithms can be introduced that can help radiologists to classify tumor images.

Figure 1.1 Steps in image analysis.

The steps involved in image analysis are presented in Figure 1.1[112]. Each step is discussed in the following in brief.

Image acquisition

: This is the first step of every vision system. Image acquisition means acquiring a digital image. After obtaining the image successfully, several processing approaches can be used on the image in order to fulfill the different vision tasks required nowadays. However, if the image cannot be acquired competently, the anticipated tasks may perhaps not be completed successfully by any means.

Image pre‐processing

: This step involves improving the image to be suitable for analysis. In this phase, the quality of image is improved by introducing different techniques, such as contrast enhancement, noise contraction, and sharpening of image. The output image can be sent to perform the next step.

Image segmentation

: In this step, the image is partitioned into several regions and the regions of interest are taken out from the input image.

Feature extraction

: This step converts the input image to a number of features on the basis of the traits of the segmented image. Resulting from the discovery of certain facts some data are obtained as the output of this step.

Pattern classification

: This is the final step of image analysis. The extracted features obtained in the last phase are used to classify the given image.

Various techniques can be applied to execute the steps in image analysis depending on the intended application. So, the selected technique for performing each step is of the utmost importance to achieve the desired results from the proposed algorithm.

1.1.1 Image Segmentation

Segmentation separates the patterns into a number of uniform, non‐overlapping and homogeneous regions or segments (classes), in which the members of any particular segment are similar to each other and the members in the different segments possess dissimilarity among themselves [9,22,87,133,166,194,203,252,258]. The patterns carrying the similar features are known to be clusters/segments. Segmentation is equally effective for localizing and identifying object‐specific features both from nonnumeric and pictorial datasets. The challenges lie in the attempt to emulate human perception and intelligence to extract underlying objects accurately. The foremost objective of the segmentation process is to detect the pertinent and meaningful data by taking out the redundant part embedded within. The foundation of a segmentation technique is basically contingent on the assortment of the representation of data elements, the proximity measurement between them and also their grouping. Thus, certain metrics are commonly used for measuring the similarity or difference between the patterns. So far, segmentation has been successfully applied in diverse fields, which may include different engineering disciplines like electrical engineering, mechanical engineering, and others. Apart from that, it has also been widely used in various other fields, such as remote sensing, machine learning, robotic vision, pattern recognition, artificial intelligence, economics, medical sciences, and many others.

Formally, the term “Image segmentation” is defined as follows:

(1.1)

(1.2)

where it is assumed that an image, is segmented into number of regions, namely, [153,162,193]. A comprehensive exploration of diverse segmentation methods is available in the literature [27,97,231]. Of late, color image segmentation has become a trusted addition in many areas of application [112,152,229,248,264]. A color pixel is typically manifested as a mixture of different color constituents. The synthesis of different color constituents in color images usually enhances an enormous amount of intrinsic computational complexities in respect of color image processing. As a result, it becomes more challenging to take them up in real‐life situations. Some typical examples of color image segmentation may include robotics, object recognition, and data compression to name but a few [27]. A pixel in a color image is recognized in multidimensional color space, which basically enhances the processing complexity in real‐life applications. Compared to image segmentation in monochrome image, a higher number of parameters is required to be tuned for optimality in color image segmentation [27].

1.1.2 Image Thresholding