Quantum Inspired Meta-heuristics for Image Analysis

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. 

SANDIP DEY, PHD, is an Associate Professor and Chair in the department of Computer Science & Engineering at the Global Institute of Management and Technology, Krishnanagar, Nadia, West Bengal, India.

SIDDHARTHA BHATTACHARYYA, PHD, is the Principal of RCC Institute of Information Technology, Kolkata, India.

UJJWAL MAULIK, PHD, is the Chair of and Professor in the Department of Computer Science and Engineering, Jadavpur University, Kolkata, India.

Preface xiii

Acronyms xv

1 Introduction 1

1.1 Image Analysis 3

1.1.1 Image Segmentation 4

1.1.2 Image Thresholding 5

1.2 Prerequisites of Quantum Computing 7

1.2.1 Dirac’s Notation 8

1.2.2 Qubit 8

1.2.3 Quantum Superposition 8

1.2.4 Quantum Gates 9

1.2.4.1 Quantum NOT Gate (Matrix Representation) 9

1.2.4.2 Quantum Z Gate (Matrix Representation) 9

1.2.4.3 Hadamard Gate 10

1.2.4.4 Phase Shift Gate 10

1.2.4.5 Controlled NOT Gate (CNOT) 10

1.2.4.6 SWAP Gate 11

1.2.4.7 Toffoli Gate 11

1.2.4.8 Fredkin Gate 12

1.2.4.9 Quantum Rotation Gate 13

1.2.5 Quantum Register 14

1.2.6 Quantum Entanglement 14

1.2.7 Quantum Solutions of NP-complete Problems 15

1.3 Role of Optimization 16

1.3.1 Single-objective Optimization 16

1.3.2 Multi-objective Optimization 18

1.3.3 Application of Optimization to Image Analysis 18

1.4 Related Literature Survey 19

1.4.1 Quantum-based Approaches 19

1.4.2 Meta-heuristic-based Approaches 21

1.4.3 Multi-objective-based Approaches 22

1.5 Organization of the Book 23

1.5.1 Quantum Inspired Meta-heuristics for Bi-level Image Thresholding 24

1.5.2 Quantum Inspired Meta-heuristics for Gray-scale Multi-level Image Thresholding 24

1.5.3 Quantum Behaved Meta-heuristics for True Color Multi-level Thresholding 24

1.5.4 Quantum Inspired Multi-objective Algorithms for Multi-level Image Thresholding 24

1.6 Conclusion 25

1.7 Summary 25

Exercise Questions 26

2 Review of Image Analysis 29

2.1 Introduction 29

2.2 Definition 29

2.3 Mathematical Formalism 30

2.4 Current Technologies 30

2.4.1 Digital Image Analysis Methodologies 31

2.4.1.1 Image Segmentation 31

2.4.1.2 Feature Extraction/Selection 32

2.4.1.3 Classification 34

2.5 Overview of Different Thresholding Techniques 35

2.5.1 Ramesh’s Algorithm 35

2.5.2 Shanbag’s Algorithm 36

2.5.3 Correlation Coefficient 37

2.5.4 Pun’s Algorithm 38

2.5.5 Wu’s Algorithm 38

2.5.6 Renyi’s Algorithm 39

2.5.7 Yen’s Algorithm 39

2.5.8 Johannsen’s Algorithm 40

2.5.9 Silva’s Algorithm 40

2.5.10 Fuzzy Algorithm 41

2.5.11 Brink’s Algorithm 41

2.5.12 Otsu’s Algorithm 43

2.5.13 Kittler’s Algorithm 43

2.5.14 Li’s Algorithm 44

2.5.15 Kapur’s Algorithm 44

2.5.16 Huang’s Algorithm 45

2.6 Applications of Image Analysis 46

2.7 Conclusion 47

2.8 Summary 48

Exercise Questions 48

3 Overview of Meta-heuristics 51

3.1 Introduction 51

3.1.1 Impact on Controlling Parameters 52

3.2 Genetic Algorithms 52

3.2.1 Fundamental Principles and Features 53

3.2.2 Pseudo-code of Genetic Algorithms 53

3.2.3 Encoding Strategy and the Creation of Population 54

3.2.4 Evaluation Techniques 54

3.2.5 Genetic Operators 54

3.2.6 Selection Mechanism 54

3.2.7 Crossover 55

3.2.8 Mutation 56

3.3 Particle Swarm Optimization 56

3.3.1 Pseudo-code of Particle Swarm Optimization 57

3.3.2 PSO: Velocity and Position Update 57

3.4 Ant Colony Optimization 58

3.4.1 Stigmergy in Ants: Biological Inspiration 58

3.4.2 Pseudo-code of Ant Colony Optimization 59

3.4.3 Pheromone Trails 59

3.4.4 Updating Pheromone Trails 59

3.5 Differential Evolution 60

3.5.1 Pseudo-code of Differential Evolution 60

3.5.2 Basic Principles of DE 61

3.5.3 Mutation 61

3.5.4 Crossover 61

3.5.5 Selection 62

3.6 Simulated Annealing 62

3.6.1 Pseudo-code of Simulated Annealing 62

3.6.2 Basics of Simulated Annealing 63

3.7 Tabu Search 64

3.7.1 Pseudo-code of Tabu Search 64

3.7.2 Memory Management in Tabu Search 65

3.7.3 Parameters Used in Tabu Search 65

3.8 Conclusion 65

3.9 Summary 65

Exercise Questions 66

4 Quantum Inspired Meta-heuristics for Bi-level Image Thresholding 69

4.1 Introduction 69

4.2 Quantum Inspired Genetic Algorithm 70

4.2.1 Initialize the Population of Qubit Encoded Chromosomes 71

4.2.2 Perform Quantum Interference 72

4.2.2.1 Generate Random Chaotic Map for Each Qubit State 72

4.2.2.2 Initiate Probabilistic Switching Between Chaotic Maps 73

4.2.3 Find the Threshold Value in Population and Evaluate Fitness 74

4.2.4 Apply Selection Mechanism to Generate a New Population 74

4.2.5 Foundation of Quantum Crossover 74

4.2.6 Foundation of Quantum Mutation 74

4.2.7 Foundation of Quantum Shift 75

4.2.8 Complexity Analysis 75

4.3 Quantum Inspired Particle Swarm Optimization 76

4.3.1 Complexity Analysis 77

4.4 Implementation Results 77

4.4.1 Experimental Results (Phase I) 79

4.4.1.1 Implementation Results for QEA 91

4.4.2 Experimental Results (Phase II) 96

4.4.2.1 Experimental Results of Proposed QIGA and Conventional GA 96

4.4.2.2 Results Obtained with QEA 96

4.4.3 Experimental Results (Phase III) 114

4.4.3.1 Results Obtained with Proposed QIGA and Conventional GA 114

4.4.3.2 Results obtained from QEA 117

4.5 Comparative Analysis among the Participating Algorithms 120

4.6 Conclusion 120

4.7 Summary 121

Exercise Questions 121

Coding Examples 123

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

5.1 Introduction 125

5.2 Quantum Inspired Genetic Algorithm 126

5.2.1 Population Generation 126

5.2.2 Quantum Orthogonality 127

5.2.3 Determination of Threshold Values in Population and Measurement of Fitness 128

5.2.4 Selection 129

5.2.5 Quantum Crossover 129

5.2.6 Quantum Mutation 129

5.2.7 Complexity Analysis 129

5.3 Quantum Inspired Particle Swarm Optimization 130

5.3.1 Complexity Analysis 131

5.4 Quantum Inspired Differential Evolution 131

5.4.1 Complexity Analysis 132

5.5 Quantum Inspired Ant Colony Optimization 133

5.5.1 Complexity Analysis 133

5.6 Quantum Inspired Simulated Annealing 134

5.6.1 Complexity Analysis 136

5.7 Quantum Inspired Tabu Search 136

5.7.1 Complexity Analysis 136

5.8 Implementation Results 137

5.8.1 Consensus Results of the Quantum Algorithms 142

5.9 Comparison of QIPSO with Other Existing Algorithms 145

5.10 Conclusion 165

5.11 Summary 166

Exercise Questions 167

Coding Examples 190

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

6.1 Introduction 195

6.2 Background 196

6.3 Quantum Inspired Ant Colony Optimization 196

6.3.1 Complexity Analysis 197

6.4 Quantum Inspired Differential Evolution 197

6.4.1 Complexity Analysis 200

6.5 Quantum Inspired Particle Swarm Optimization 200

6.5.1 Complexity Analysis 200

6.6 Quantum Inspired Genetic Algorithm 201

6.6.1 Complexity Analysis 203

6.7 Quantum Inspired Simulated Annealing 203

6.7.1 Complexity Analysis 204

6.8 Quantum Inspired Tabu Search 204

6.8.1 Complexity Analysis 206

6.9 Implementation Results 207

6.9.1 Experimental Results (Phase I) 209

6.9.1.1 The Stability of the Comparable Algorithms 210

6.9.2 The Performance Evaluation of the Comparable Algorithms of Phase I 225

6.9.3 Experimental Results (Phase II) 235

6.9.4 The Performance Evaluation of the Participating Algorithms of Phase II 235

6.10 Conclusion 294

6.11 Summary 294

Exercise Questions 295

Coding Examples 296

7 Quantum Inspired Multi-objective Algorithms for Multi-level Image Thresholding 301

7.1 Introduction 301

7.2 Multi-objective Optimization 302

7.3 Experimental Methodology for Gray-Scale Multi-Level Image Thresholding 303

7.3.1 Quantum Inspired Non-dominated Sorting-Based Multi-objective Genetic Algorithm 303

7.3.2 Complexity Analysis 305

7.3.3 Quantum Inspired Simulated Annealing for Multi-objective Algorithms 305

7.3.3.1 Complexity Analysis 307

7.3.4 Quantum Inspired Multi-objective Particle Swarm Optimization 308

7.3.4.1 Complexity Analysis 309

7.3.5 Quantum Inspired Multi-objective Ant Colony Optimization 309

7.3.5.1 Complexity Analysis 310

7.4 Implementation Results 311

7.4.1 Experimental Results 311

7.4.1.1 The Results of Multi-Level Thresholding for QINSGA-II, NSGA-II, and SMS-EMOA 312

7.4.1.2 The Stability of the Comparable Methods 312

7.4.1.3 Performance Evaluation 315

7.5 Conclusion 327

7.6 Summary 327

Exercise Questions 328

Coding Examples 329

8 Conclusion 333

Bibliography 337

Index 355

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.