Cellular Automata in Image Processing and Geometry (Emergence, Complexity and Computation (10))

The book presents findings, views and ideas on what exact problems of image processing, pattern recognition and generation can be efficiently solved by cellular automata architectures. This volume provides a convenient collection in this area, in which publications are otherwise widely scattered throughout the literature. The topics covered include image compression and resizing; skeletonization, erosion and dilation; convex hull computation, edge detection and segmentation; forgery detection and content based retrieval; and pattern generation. The book advances the theory of image processing, pattern recognition and generation as well as the design of efficient algorithms and hardware for parallel image processing and analysis. It is aimed at computer scientists, software programmers, electronic engineers, mathematicians and physicists, and at everyone who studies or develops cellular automaton algorithms and tools for image processing and analysis, or develops novel architectures and implementations of massive parallel computing devices. The book will provide attractive reading for a general audience because it has do-it-yourself appeal: all the computer experiments presented within it can be implemented with minimal knowledge of programming. The simplicity yet substantial functionality of the cellular automaton approach, and the transparency of the algorithms proposed, makes the text ideal supplementary reading for courses on image processing, parallel computing, automata theory and applications. Cover......Page 1 1.1 Introduction and Motivation......Page 15 1.2.1 Principle of Chaotic Scan......Page 19 1.2.2 Properties of the Chaotic Counters......Page 21 1.2.3 Designing Good Chaotic Counters as Hybrid CellularAutomata......Page 24 1.2.4 Message Recovery and Examples......Page 26 1.3.1 The General Framework of Dictionary Based Compression......Page 29 1.3.2 Learning CA-Based Dictionaries and Performance Evaluation of the CA-VQ System......Page 30 1.4 Hardware Description and Synthesis of CA Using AlgebraicNormal Form......Page 34 References......Page 35 2.1 Introduction......Page 38 2.2.1 CA Fundamentals......Page 42 2.2.2 Canny Edge Detector......Page 43 2.3.1 Edge Detection......Page 44 2.3.2 CA Resizing......Page 45 2.3.3 Remapping Process......Page 46 2.4 Experimental Results......Page 47 2.5 Hardware Implementation......Page 53 2.6 Discussion and Conclusions......Page 55 References......Page 56 3.1 Introduction......Page 59 3.2 Skeletonizing Algorithms......Page 61 3.3 Guo and Hall Algorithm......Page 63 3.4 Cellular Automata......Page 65 3.5 Parallel Implementation......Page 67 3.5.1 Examples......Page 68 3.6 Conclusions......Page 72 4.1 Introduction......Page 76 4.2 Mathematical Morphology......Page 78 4.3 Quantum-dot Cellular Automata......Page 80 4.4.2 Circuit Design......Page 84 4.5 QCA Implementation of Morphological Operations......Page 86 4.5.1 QCA Implementation of Morphological Erosion......Page 87 4.5.2 QCA Implementation of Morphological Dilation......Page 88 References......Page 91 5.1 Introduction......Page 96 5.2 Boundary Detection......Page 97 5.3 Edge Detection in Intensity Images......Page 100 5.4 Post-processing of Edges......Page 103 5.4.1 A Simple Edge Linking Scheme......Page 104 5.5 Experiments......Page 105 5.6 Conclusions......Page 111 References......Page 112 Copy-Move Forgery Detection Using CellularAutomata......Page 115 6.1 Introduction......Page 116 6.3 Copy-Move Forgery Detection (CMFD)......Page 117 6.3.1 Block-Based Method for CMFD......Page 119 6.3.2 Possible Feature Vectors......Page 121 6.4.1 Representation of Image in Binary......Page 122 6.4.2 Plain CMF......Page 126 6.4.3 Application on Post-processed Images......Page 129 6.6 Conclusion......Page 132 References......Page 133 7.1 Introduction......Page 136 7.2 Scenario 1: Using Cellular Automata and LUDecomposition......Page 138 7.2.1 Proposed Model......Page 139 7.3.1 Proposed Model......Page 143 7.4 Dataset and Experimental Results......Page 145 7.4.1 Performance and Visual Quality......Page 146 7.4.3 True and False Alert......Page 147 7.4.5 Secret Key Sensitivity......Page 148 7.4.6 Diffusion......Page 150 7.5 Limitations......Page 151 7.6 Conclusion and Future Work......Page 153 References......Page 154 8.2 Content-Based Image Retrieval: A Background......Page 155 8.3.1 Noise Reduction......Page 157 8.3.2 Edge Detection......Page 160 8.3.4 Colour Matching and Histograms......Page 161 8.3.5 Shape Matching......Page 163 8.4 Practical Case Study: Recognition of LEGO Bricks......Page 164 References......Page 168 The Application of Cellular Automaton inMedical Semiautomatic Segmentation......Page 171 9.1 Introduction......Page 172 9.2 Cellular Automaton Segmentation Rule......Page 174 9.3.1 Labels in Image Plane......Page 176 9.3.2 Regional Cellular Automaton Segmentation......Page 177 9.3.3 Volume Cellular Automaton Segmentation......Page 181 9.4 Block Cellular Automaton Segmentation in MedicalApplications......Page 185 References......Page 188 10.1 Notational and Naming Convention......Page 191 10.2 Introduction......Page 192 10.3 The Angular Point of View......Page 194 10.3.2 Complete θ -Convex Hull......Page 195 10.4 The Metrical Point of View......Page 196 10.4.1 Majority Rule and Metric Convexity......Page 198 10.4.2 Complete Metric Convex Hulls......Page 200 10.5.1 Pairwise Construction in Euclidean Space......Page 204 10.5.2 (Metric) Gabriel Graphs in Cellular Spaces......Page 206 10.6 The Complete Cellular Automaton......Page 209 References......Page 211 11.1 Building Envelope and Daylighting......Page 213 11.2 Why Cellular Automata to Drive Shading of BuildingEnvelopes?......Page 215 11.2.1 The Nomenclature......Page 217 11.3 One-Dimensional Cellular Automata Applied on Surfaces......Page 219 11.3.3 Half-Distance Automata......Page 220 11.3.4 Higher Order Cellular Automata......Page 221 11.3.5 Other Regular Tessellations: Hexagonal and Triangular......Page 223 11.3.6 PFSS on Triangular Grid: PFSST......Page 227 11.4 Two-Dimensional Cellular Automata on Surfaces......Page 228 11.4.1 Triangular Cellular Automata......Page 230 11.5 Application of Evolutionary Algorithms for Optimizationof CA Shading......Page 231 11.6 Prototypes......Page 234 References......Page 236 Pattern Formation Using Cellular Automata andL-Systems: A Case Study in Producing IslamicPatterns......Page 240 12.1 Introduction......Page 241 12.2 Preliminary Definitions and Terminologies......Page 244 12.3 Proposed Method......Page 245 12.3.1 Ma’qeli Character Generation Using MargolusNeighborhood......Page 246 12.3.2 Word and Sentence Generation Using Ma’qeli Patterns......Page 247 12.3.3 Holy Word Formation Using L-Systems......Page 248 12.4 Experimental Results......Page 251 12.4.2 Ma’qeli Script Generation Using 2D SynchronousCellular Automata......Page 252 12.4.3 Holy Words Formation Using L-Systems......Page 256 References......Page 257 13.1 Creative Projects Based on Cellular Automata Systems......Page 260 13.2 The Fluid Automata Project......Page 263 13.3.1 Fluid Simulation......Page 264 13.3.2 Flow Visualization......Page 268 13.4 Single-User Interaction Techniques......Page 271 13.5 Multi-user Interaction Techniques......Page 272 13.6 The Annular Genealogy Project......Page 273 13.7 Conclusion......Page 275 References......Page 277 References......Page 280