image

GENETIC LEARNING FOR ADAPTIVE IMAGE SEGMENTATION THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE ROBOTICS: VISION, MANIPULATION AND SENSORS Consulting Editor Takeo Kanade Other books in the series: SPACE-SCALE THEORY IN EARLY VISION, Tony Lindeberg ISBN 0-7923-9418 NEURAL NETWORK PERCEPTION FOR MOBILE ROBOT GUIDANCE, Dean A. Pomerleau ISBN: 0-7923-9373-2 DIRECTED SONAR SENSING FOR MOBILE ROBOT NA VIGA TlON, John J. Leonard, Hugh F. Durrant-Whyte ISBN: 0-7923-9242-6 A GENERAL MODEL OF LEGGED LOCOMOTION ON NATURAL TERRAINE, David J. Manko ISBN: 0-7923-9247-7 INTELLIGENT ROBOTIC SYSTEMS: THEORY, DESIGN AND APPLICATIONS, K. Valavanis, G. Saridis ISBN: 0-7923-9250-7 QUALITATIVE MOTION UNDERSTANDING, W. Burger, B. Bhanu ISBN: 0-7923-9251-5 NONHOLONOMIC MOTION PLANNING, Zexiang Li, 1.F. Canny ISBN: 0-7923-9275-2 SPACE ROBOTICS: DYNAMICS AND CONTROL, Yangsheng Xu, Takeo Kanade ISBN: 0-7923-9266-3 NEURAL NETWORKS IN ROBOTICS, George Bekcy, Ken Goldberg ISBN: 0-7923-9268-X EFFICIENT DYNAMIC SIMULATION OF ROBOTIC MECHANISMS. Kathryn W. Lilly ISBN: 0-7923-9286-8 MEASUREMENT OF IMAGE VELOCITY, David 1. Fleet ISBN: 0-7923-9198-5 INTELLIGENT ROBOTIC SYSTEMS FOR SPACE EXPLORATION, Alan A. Desrochers ISBN: 0-7923-9197-7 COMPUTER AIDED MECHANICAL ASSEMBLY PLANNING, L. Homen de Mello, S. Lee ISBN: 0-7923-9205-1 PERTURBATION TECHNIQUES FOR FLEXIBLE MANIPULATORS, A. Fraser, R. W. Daniel ISBN: 0-7923-9162-4 DYNAMIC ANALYSIS OF ROBOT MANUPULATORS: A Cartesian Tensor Approach, C. A. Balafoutis, R. V. Patel ISBN: 0-7923-9145-4 for Adaptive Image Segmentation BIR BHANU University of California Riverside, California, USA Genetic Learning • SUNGKEELEE Kyungpook National University Taegu, South Korea SPRINGER SCIENCE+BUSINESS MEDIA, LLC Library of Congress Cataloging-in-Publication Data Bhanu, Bir. Genetic learning for adaptive image segmentation / Bir Bhanu, Sungkee Lee. p. cm. --(The Kluwer international series in engineering and computer science ; 287. Robotics) Includes bibliographical references and index. ISBN 978-1-4613-6198-5 ISBN 978-1-4615-2774-9 (eBook) DOI 10.1007/978-1-4615-2774-9 1. Computer vision. 2. Image processing. 3. Machine learning. 1. Lee, Sungkee, 1956-. II. Title. III. Series. TA1634.B47 1994 006.3'7--dc20 94-22448 CIP Copyright (!:) 1994 by Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 1994 st edition 1994 Softcover reprint of the hardcover 1 Al! rights reserved. No part of this publicat ion may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photo-copying, recording, or otherwise, without the prior written permission of the publisher, Springer Science+Business Media, LLC. Printed on acid-free paper. CONTENTS LIST OF FIGURES PREFACE 1 INTRODUCTION 1.1 Definition of Image Segmentation 1.2 Characteristics of the Image Segmentation Problem 1.3 Parameter Selection 1.4 Multi-Level Vision and Image Segmentation 1.5 Adaptive Image Segmentation 1.6 Outline of this Book 2 IMAGE SEGMENTATION TECHNIQUES 2.1 Edge Detection 2.2 Region Splitting and Region Growing 2.3 The Phoenix Image Segmentation Algorithm 3 SEGMENTATION AS AN OPTIMIZATION PROBLEM 3.1 Representation of Segmentation Quality 3.2 Selection of an Optimization Technique 3.3 Genetic Algorithms for Optimization 4 BASELINE ADAPTIVE IMAGE SEGMENTATION USING A GENETIC ALGORITHM 4.1 Self-Optimizing Adaptive Image Segmentation System 4.2 Image Characteristics 4.3 Image Distance Measure IX XVII 1 2 4 7 9 12 15 15 16 18 25 25 28 31 39 39 41 44 vi Genetic Learningfor Adaptive Image Segmentation 4.4 Genetic Learning System 4.5 Image Segmentation Algorithm 4.6 Global and Local Segmentation Evaluation 4.7 Adaptive Image Segmentation Algorithm 5 BASIC EXPERIMENTAL RESULTS -IMAGERY INDOOR 5.1 Indoor Imagery Experiments 5.2 Training Experiments 5.3 Testing Experiments 5.4 Comparison of the Adaptive Image Segmentation with Other Techniques in Computer Vision 6 BASIC EXPERIMENTAL RESULTS -IMAGERY OUTDOOR 6.1 Outdoor Imagery Experiments 6.2 Training Experiments 6.3 Testing Experiments 6.4 Comparison of the Adaptive Image Segmentation with Other Techniques in Computer Vision 7 EVALUATING BASELINE EXPERIMENTS TECHNIQUE THE EFFECTIVENESS -FURTHER OF THE 7.1 Comparison of the Adaptive System with Random Search 7.2 Effectiveness of the Reproduction and Crossover Operators 7.3 Demonstration of the Learning Behavior 8 HYBRID SEARCH SCHEME SEGMENTATION FOR ADAPTIVE IMAGE 8.1 Integrating Genetic Algorithm and Hill Climbing 8.2 Experimental Results 9 SIMULTANEOUS OPTIMIZATION AND LOCAL EVALUATION MEASURES OF GLOBAL 9.1 Multio~jective Optimization with Genetic Algorithm 46 50 52 58 61 61 76 96 106 109 109 133 155 177 183 183 186 188 195 195 199 215 216 Contents 9.2 Adaptive Image Segmentation Using Multiobjective Optimization 9.3 Experimental Results 10 SUMMARY REFERENCES INDEX vii 218 220 255 261 269 LIST OF FIGURES Chapter 1 1.1 Parameter selection problem for image segmentation. 1.2 Example of the adaptive image segmentation task. 1.3 Conceptual design of the multi-level Computer Vision System. 1.4 Closed-loop adaptive image segmentation system. Chapter 2 2.1 Block diagram of the Phoenix segmentation algorithm. Chapter 3 3.1 Representation ofa typical objective function that must be optimized for adaptive image segmentation. 3.2 Segmentation quality surface for the image shown in Figure 1.2(a). Chapter 4 4.1 Block diagram of the adaptive image segmentation system. 4.2 Image statistics and external variables extracted from the image in Figure 1.2(a). 4.3 Representation of a knowledge structure used by the adaptive segmentation system. 4.4 Flow chart of genetic adaptation cycle. 6 8 9 10 21 26 27 40 42 45 47 x Genetic LearningJor Adaptive Image Segmentation 4.5 Example of one complete cycle through the adaptive image segmentation system. 4.6 Details of the crossover operation performed in the example shown in Figure 4.5. 4.7 Details of the mutation operation performed in the example shown in Figure 4.5. 4.8 Illustrations for the quality measures used in the adaptive image segmentation system. Chapter 5 5.1 Color images for the indoor experiments. 5.2 Ground truth car data for the indoor images. 5.3 Sobel and Roberts edge images for the indoor experiments. 5.4 Individual quality surfaces for Frame I in Figure 5.1. 5.5 Combined segmentation quality surfaces for all images in Figure 5.1. fi.ti Performance summary for the indoor imagery experiments. 5.7 Search point locations at each generation for Frame 1. 5.8 Initial and final search point locations for Frame 2. 5.9 Initial and final search point locations for Frame 3. 5.10 Initial and final search point locations for Frame 4. 5.11 Initial and final search point locations for Frame 5. 5.12 Initial and final search point locations for Frame 6. 5.13 Maximum and average segmentation performance at every generation for each frame in the indoor image database. 49 51 51 54 63 68 72 77 78 84 85 86 87 88 90 Contents 5.14 Segmented images for Frame 1 of the indoor experiments. 5.15 Segmented images for Frame 2 of the indoor experiments. 5.16 Segmented images for Frame 3 of the indoor experiments. 5.17 Segmented images for Frame 4 of the indoor experiments. 5.18 Segmented images for Frame 5 of the indoor experiments. 5.19 Segmented images for Frame 6 of the indoor experiments. 5.20 Performance comparison of the training and testing experiments on the indoor image database. 5.21 Initial and final search point locations for Frame 1 of the testing experiments. 5.22 Initial and final search point locations for Frame 2 of the testing experiments. 5.23 Initial and final search point locations for Frame 3 of the testing experiments. 5.24 Initial and final search point locations for Frame 4 of the testing experiments. 5.25 Initial and final search point locations for Frame 5 of the testing experiments. 5.26 Initial and final search point locations for Frame 6 of the testing experiments. 5.27 Maximum and average segmentation performance at every generation for each frame during the testing experiments. 5.28 Segmented images for the indoor testing experiments. 5.29 Comparison of the adaptive image segmentation system with default Phoenix performance and the traditional image segmentation approach. 5.30 Segmentation results for the adaptive technique, the default parameters, and the traditional approach. xi 91 92 93 93 94 95 97 98 99 100 101 102 103 104 105 107 108 xii Genetic Learningfor Adaptive Image Segmentation Chapter 6 6.1 Color images for the outdoor experiments. 6.2 Time of day and weather conditions for the outdoor images. 6.3 Ground truth data for the outdoor images. 6.4 Individual quality surfaces for Frame I in Figure 6.1. 6.5 Combined segmentation quality surfaces for all images in Figure 6.1. 6.6 Performance summary for the outdoor training experiments. 6.7 Search poin t locations at each generation fex Frame 1. 6.8 Initial and final search point locations ti)r Frame 3 of the outdoor training images. 6.9 Initial and final search point locations ti>r Frame 5 of the outdoor training images. 6.10 Initial and final search point locations t()r Frame 7 of the outdoor training images. 6.11 Initial and final search point locations for Frame 9 of the outdoor training images. 6.12 Initial and final search point locations for Frame II of the outdoor training images. 6.13 Initial and final search point locations for Frame 13 of the outdoor training images. 6.14 Initial and final search point locations fi)r Frame 15 of the outdoor training images. 6.15 Initial and final search point locations for Frame 17 of the outdoor training images. 110 115 116 118 122 134 135 142 143 144 145 146 147 148 149 Contents 6.16 Initial and final search poin t locations for Frame 19 of the outdoor training images. 6.17 Maximum and average segmentation performance at every generation for each frame in the training experiments. 6.18 Segmented images for Frame 1 of the outdoor training experiments. 6.19 Segmented images for the remaining outdoor training images. 6.20 Edge images for Frame 15 of the outdoor image database. 6.21 Performance comparison of the training and testing experiments on the outdoor imagery. 6.22 Initial and final search point locations for Frame 2 of the outdoor testing images. 6.23 Initial and final search point locations for Frame 4 of the outdoor testing images. 6.24 Initial and final search point locations for Frame 6 of the outdoor testing images. 6.25 Initial and final search point locations for Frame 8 of the outdoor testing images. 6.26 Initial and final search point locations for Frame 10 of the outdoor testing images. 6.27 Initial and final search poin t locations for Frame 12 of the outdoor testing images. 6.28 Initial and final search point locations for Frame 14 of the outdoor testing images. 6.29 Initial and final search point locations for Frame 16 of the outdoor testing images. 6.30 Initial and final search point locations for Frame 18 of the outdoor testing images. xiii 150 152 154 156 159 160 162 163 1 165 166 167 168 169 170 xiv Genetic Learningfor Adaptive Image Segmentation 6.31 Initial and final search point locations for Frame 20 of the outdoor testing images. 6.32 Maximum and average segmentation performance at every generation for each frame in the testing experiments. 6.33 Segmented images for the outdoor testing experiments. 6.34 Comparison of the adaptive image segmentation system with default Phoenix performance and the traditional image segmentation approach for the outdoor images. 6.35 Segmentation results for the adaptive technique, the default parameters, and the traditional approach. Chapter 7 7.1 Performance comparison of the adaptive image segmentation system with the random search technique. 7.2 Performance comparison of the pure genetic algorithm and its two variants. 7.3 Performance of the adaptive image segmentation system for the sequential experiments. 7.4 Comparison of the sequential and parallel experiments performed on the outdoor image database. Chapter 8 8.1 Block diagram of the adaptive image segmen tation system using the hybrid search scheme. 8.2 Performance summary for the hybrid scheme training experiments. 8.3 Performance comparison of the hybrid scheme and the baseline training experiments. 8.4 Search point locations visited at each generation of the hybrid scheme experiments for Frame 2 of the indoor image database. 171 172 174 179 180 185 187 190 192 197 202 204 205 Contents 8.5 Search point locations visited at each generation of the hybrid scheme experiments for Frame 3 of the outdoor image database. 8.6 Maximum and average segmentation performance at every generation of the hybrid scheme experiments for the selected frames. 8.7 Segmented images for Frame 2 of the indoor experiments. 8.8 Segmented images for Frame 3 of the outdoor experiments. 8.9 Performance comparison of the hybrid search scheme and the baseline testing experiments. Chapter 9 9.1 Block diagram of the adaptive image segmentation system using multiobjective optimization. 9.2 Global and local segmentation quality surfaces for Frame 2 of the indoor image database (Figure 5.1 (b) ). 9.3 Global and local segmentation quality surfaces for Frame 3 of the outdoor image database (Figure 6.1 (c)). 9.4 Performance summary for the multiobjective optimization training experiments. 9.5 Search point locations visited at each generation for Frame 2 of the indoor image database. 9.6 Search point locations visited at each generation for Frame 3 of the outdoor image database. 9.7 Global and local segmentation quality of each individual at each generation for Frame 2 of the indoor image database. 9.8 Global and local segmentation quality of each individual at each generation for Frame 3 of the outdoor image database. xv 208 211 212 213 214 219 223 224 225 226 232 235 236 xvi Genetic Learning for Adaptive Image Segmentation 9.9 Maximum and average fitness values of the global and local quality measures at each generation for the representative frames (frame 2, indoor image and frame 3, outdoor image). 9.10 Segmented images for Frame 2 of the indoor experiments. 9.11 Segmented images for Frame 3 of the outdoor exper-iments. 9.12 Performance comparison of the training and testing experiments for multiobjective optimization. 9.13 Search point locations for Frame 2 during the indoor testing experiments. 9.14 Search point locations fix Frame 4 during the outdoor testing experiments. 9.15 Global and local segmentation quality of each individual at each generation for Frame 2 during the indoor testing experimen ts. 9.16 Global and local segmentation quality of each individual at each generation for Frame 4 during the outdoor testing experiments. 9.17 Maximum and average fitness values of the global and local quality measures at each generation for the selected frames (frame 2, indoor image and frame 4, outdoor image) during the testing experiments. 9.18 Segmented images for Frame 2 of the indoor testing experiments. 9.19 Segmented images for Frame 4 of the outdoor testing experiments. 238 239 240 242 243 247 249 250 251 252 253 PREFACE Image segmentation is an old and difficult problem. It refers to the parti-tioning of an image into meaningful components. Generally, it is the first task of any automated image understanding process. All subsequent tasks, such as feature extraction, object detection, and object recognition, rely heavily on the quality of the segmentation. Currently, there are a large number of segmentation techniques that are available. However, these techniques rarely demonstrate the robustness re-quired for practical applications of image understanding, such as au-tonomous vehicle navigation, target recognition, photointerpretation, etc. The difficulty arises since the segmentation performance needs to be adapted to the changes in image quality. Image quality is affected by varia-tions in environmental conditions, imaging devices, time of day, etc. Thus, one of the fundamental weaknesses of current image segmentation algo-rithms is their inability to adapt the segmentation process as real-world changes are reflected in the image. Only after numerous modifications to an algorithm's control parameters can any current image segmentation technique be used to handle the diver-sity of images encountered in real-world applications. While there are threshold selection techniques which adapt to local image properties in a single image for image segmentation, these techniques do not adapt local thresholds from frame to frame so as to compensate for changes in images caused by variations in the environmental conditions. Also, they do not ac-complish any learning from experience to improve the performance of the system over time. To date, no segmentation algorithm has been developed which can automatically generate an \"ideal\" segmentation result in one pass (or in an open loop manner) over a range of scenarios encountered in prac-tical applications. Any technique, no matter how \"sophisticated\" it may be, will eventually yield poor performance if it does not adapt to the environ-mental variations. Therefore, in this research we attempt to address this fundamental limitation in developing \"useful\" computer vision systems for practical scenarios by developing a closed-loop system which automatically xviii Genetic Learning for Adaptive Image Segmentation adjusts the performance of the segmentation algorithm. The system is based on changing the control parameters of the segmentation algorithm such that it will be operational across a wide diversity of image characteristics and application scenarios. It is noted that the performance of the adaptive seg-mentation system is limited by the capabilities of the segmentation algo-rithm, but the results will be optimal for a given image based on the evalua-tion criteria that have been defined. This book presents the first closed-loop image segmentation system that in-corporates genetic algorithms to adapt the segmentation process to changes in image characteristics caused by variable environmental conditions, such as time of day, time of year, weather, etc. The goals of the adaptive image segmentation system presented in this book are to provide continuous adap-tation to normal environmental variations, to exhibit learning capabilities, and to provide robust performance when interacting with a dynamic envi-ronment. The research is directed towards adapting the performance of a well known existing segmentation algorithm (Phoenix) across a wide variety of environmental conditions which cause changes in the image characteris-tics. The book presents a large number of experimental results that demon-strate (a) the ability to adapt the segmentation performance in both indoor and outdoor color imagery, and (b) that learning from experience can be used to improve the segmentation perf()rmance over time. The feedback loop in the baseline approach consists of a genetic learning component, an image segmentation algorithm, and a segmented image evaluation component. A genetic learning subsystem optimizes segmenta-tion performance on each individual image and accumulates segmentation experience over time to reduce the effort needed to optimize subsequent images. Image characteristics and external image variables are represented both numerically and in symbolic form within the genetic knowledge struc-ture. Segmentation control parameters are represented and processed us-ing a binary string notation. Image segmentation performance is evaluated using multiple measures of segmentation quality. These quality measures include lflobal characteristics of the entire image as well as local features of individual object regions in the image. In the baseline approach, the global and local quality measures are used in combination. Many parallel and se-quential experiments are carried out to evaluate the effectiveness of the technique. The approach is compared with standard techniques used in Computer Vision for both consistency and quality of segmentation results. The comparison is also done with a random search approach and the ge-netic operators are evaluated for their effectiveness. Preface xix This book also explores a hybrid search scheme that combines genetic algo-rithms and hill climbing for adaptive image segmentation. It provides ex-perimental results and compares its performance and efficiency with that of the baseline approach that uses only the genetic algorithm. The book further develops the baseline adaptive image segmentation system for multiobjective optimization. The global and local quality measures are optimized simultaneously for adaptive image segmentation. Experimental results are provided and compared with the baseline approach. The adaptive segmentation system presented in this book is very fundamen-tal in nature and is not dependent on any specific segmentation algorithm or sensor data (visible, infrared, laser, etc.). The authors are grateful to Honeywell Systems and Research Center in Minneapolis, Minnesota, USA, where part of the technical work described in this book was performed. The work at Honeywell Inc. was supported by an Initiative Grant. The authors would like to thank Steve Savitt and Durga Panda for their support of this work. John Ming contributed to many useful discussions and helped in organizing some of the material presented here. Keith Levi provided useful comments in the early stages of this work. Wilhelm Burger helped with the layout of the book and provided useful comments. Subhodev Das, Boyle Mow, Xing Wu, Neil Braithwaite, .ling Peng, Jay Farrell, Ping Liang, Karen Speed, Jackie Miller and Flavia Ramey helped in the development of this book in its final form. The book was de-veloped while the authors were employed by the University of California, Riverside, USA and the Kyungpook National University, Taegu, South Korea. The authors are grateful to Dean Susan Hackwood at the University of California, Riverside for providing facilities to prepare the manuscript. The first author would like to acknowledge the support received from AFOSR/ ARPA under grant F49620-93-1-0624 for the time that has been spent in the development of this book.