Nội dung

Interactive Curve Modeling M. Sarfraz Interactive Curve Modeling With Applications to Computer Graphics, Vision and Image Processing M. Sarfraz, BSc, MSc, MSc, Phd Department of Information Science Kuwait University Safat, Kuwait and Department of Information and Computer Science King Fahd University of Petroleum and Minerals Dhahran, Saudi Arabia British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library Library of Congress Control Number: 2007926244 Printed on acid-free paper ISBN 978-1-84628-870-8 e-ISBN 978-1-84628-871-5 c Springer-Verlag London Limited 2008 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licences issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. 9 8 7 6 5 4 3 2 1 Springer Science+Business Media springer.com To the major contributors to my life: My primary school teacher M. Aslam My friends Ashfaq and Abid My father in memoriam My mother My wife My children Ihsan, Humaira, Inam, and Ikram Preface Interactive curve modeling techniques and their applications are extremely useful in a number of academic and industrial settings. Specifically, curve modeling plays a significant role in multidisciplinary problem solving. It is extremely useful in various situations like font design, designing objects, CAD/CAM, medical imaging and visualization, scientific data visualization, virtual reality, object recognition, etc. In particular, various problems like iris recognition, fingerprint recognition, signature recognition, etc. can also be intelligently solved and automated using curve techniques. In addition to its critical importance more recently, the curve modeling methods have also proven to be indispensable in a variety of modern industries, including computer vision, robotics, medical imaging, visualization, and even media. This book aims to provide a valuable source that focuses on interdisciplinary methods and to add up-to-date methodologies in the area. It aims to provide the user community with a variety of techniques, applications, and systems necessary for various real-life problems in the areas such as font design, medical visualization, scientific data visualization, archaeology, toon rendering, virtual reality, body simulation, outline capture of images, object recognition, signature recognition, industrial applications, and many others. Book Features It aims to collect and disseminate information in various disciplines including computer graphics, image processing, computer vision, pattern recognition, artificial intelligence, soft computing, shape analysis and description, curve and surface fitting, scientific visualization, shape abstraction and modeling, intelligent CAD systems, computational geometry, reverse engineering, and levels of details for curves and surfaces. The major goal of this book is to stimulate views and provide a source where students, researchers, and practitioners can find the latest developments in the field of interactive curve modeling and its applications. The book provides classical and up-to-date theory and practice to get the problems solved in diverse areas of science and engineering. All the chapters of the book will contribute toward curve modeling techniques, applications, and systems. The book will have the best possible utility for students, researchers, computer scientists, practicing engineers, and many others who seek classical and state-of-the-art techniques, applications, and systems with curve vii viii Preface modeling. It will be an extremely useful book for undergraduate senior students as well as graduate students in the areas of computer science, engineering, and other computational sciences. Suggested Course Outlines This book is designed to have around fifteen chapters. These chapters will contribute toward interactive curve modeling techniques, applications, systems, and tools. The book is planned to have the best possible utility for researchers, computer scientists, practicing engineers, and many others who seek classical and state-of-the-art techniques and applications for computer graphics, vision, and imaging. It will also be equally and extremely useful for undergraduate senior students as well as graduate students in the areas of computer science. It is also beneficial to students in other disciplines including computer engineering, electrical engineering, mechanical engineering, and mathematics. The book is equally beneficial to researchers and practitioners in the industry and academia. The book has been designed as a course book for undergraduate as well as graduate students in the area of computer science in particular. The main audience of the book are the communities related to the field of computer graphics, vision, and imaging. However, it can be useful for students in other disciplines like computer engineering, electrical engineering, mechanical engineering, mathematics, etc. The book is equally beneficial to researchers and practitioners in the industry. The book can formulate at least three courses as follows: Course I. As an undergraduate course, at senior level, Chaps. 1–3, 8, 9, 11 (any two corner detectors), 12 (any two methods), 13, and 14 (one heuristic approach) will comprise a full length three credit hours course for a semester of 15 weeks. This course can be conducted with practical projects of reasonable weight. Course II. As a graduate course consisting of Chaps. 1–4, 6–8 (self-study), 9, and 11–14 (one heuristic approach). This course should also have heavy projects for practical applications. Course III. As a slightly different graduate course, if the undergraduate course described in Course I is considered to be a prerequisite. This course can be designed with Chaps. 4–7, 9 (using other curve schemes in the book but different than those in Chap. 9), 11–13 (just a quick review), 14, and 15. This course design can also consist of some state-of-the-art topics together with good weighted projects. The researchers and practitioners can utilize the manuscript as a source as well as a reference book. Depending on their needs, they can study on pick and choose basis. They are also advised to study in their leisure time as it may prove to be fruitful to them. Preface ix Required Background As such, it is not required to possess a specific qualification as a prerequisite to any of the undergraduate Course I or graduate courses II or III mentioned above. But, the user of this book is presumed to have some knowledge of computer programming together with some basic mathematical topics including analytic geometry, linear algebra, and calculus. Acknowledgments This manuscript has been prepared after a lot of struggle and efforts. Many graduate students and colleagues around the globe have assisted toward its completion. It is worthwhile to mention Asif Masood, Zulfiqar Habib, M. Zawwar Hussain, S. Ali Rizvi, M. Balah, M. Riyazuddin, Humayun Baig, S. Arshad Raza, Murtaza Ali Khan, Faisal AbdulRazzak, and M.A. Siddiqui. The author is thankful to all of them for their valuable efforts and advice. A lot of credit is also due to various experts who reviewed the chapters and provided helpful feedback. It is not possible to forget my family here without whose help and support I would not have completed this work. Their love, support, and patience were tremendous throughout. In addition to thanking, I should also apologize for having taken much of their time during the conduct of my work. The author is happy to acknowledge the support of King Fahd University of Petroleum and Minerals (KFUPM) toward the compilation of this book, against the Book Project #ICS/GRAPHICS/306. This book project was a main source of funding to this book. A partial funded support of KFUPM, through another Research Project #ICS/REVERSE ENG./312, also contributed toward a couple of chapters. M. Sarfraz Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Strategy in the Construction of Theory . . . . . . . 1.2 Overview . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Splines . . . . . . . . . . . . . . . . . . . 1.2.2 Shape-Preserving Interpolation . . . . . . . 1.2.3 Functional Approximation . . . . . . . . . 1.2.4 Spiral Curves . . . . . . . . . . . . . . . . 1.2.5 Corner Detection and Curve Segmentation . 1.2.6 Vectorizing Planar Shapes . . . . . . . . . 1.2.7 Reverse Engineering . . . . . . . . . . . . 1.2.8 Multiresolution Framework . . . . . . . . . 1.3 Notation and Conventions . . . . . . . . . . . . . . 1.4 Review of Some Spline Methods . . . . . . . . . . 1.4.1 Cubic Spline . . . . . . . . . . . . . . . . 1.4.2 Spline Under Tension . . . . . . . . . . . . 1.4.3 Weighted Spline . . . . . . . . . . . . . . 1.4.4 Nu-spline . . . . . . . . . . . . . . . . . . 1.4.5 Weighted Nu-spline . . . . . . . . . . . . . 1.4.6 Beta Splines . . . . . . . . . . . . . . . . . 1.4.7 Sigma (σ) Splines . . . . . . . . . . . . . 1.4.8 B-Splines . . . . . . . . . . . . . . . . . . 1.4.9 Bézier Splines . . . . . . . . . . . . . . . 1.4.10 Hermite Splines . . . . . . . . . . . . . . . 1.5 Summary . . . . . . . . . . . . . . . . . . . . . . 1.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 8 9 9 10 10 11 11 13 13 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 21 23 24 24 26 Weighted Nu Splines . . . . . . 2.1 Introduction . . . . . . . 2.2 Some Spline Methods . . 2.2.1 Cubic Splines . . 2.2.2 Weighted Splines 2.2.3 Nu Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi xii Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 28 28 29 31 32 34 37 37 38 38 3 Rational Cubic Spline with Shape Control . . . . . . . . 3.1 Introduction . . . . . . . . . . . . . . . . . . . . 3.2 C 1 Piecewise Rational Cubic Hermite Interpolant 3.3 One-Parameter Rational Cubic Spline . . . . . . 3.4 Two-Parameter Rational Cubic Spline . . . . . . 3.5 Demonstration . . . . . . . . . . . . . . . . . . . 3.6 Freeform Curves . . . . . . . . . . . . . . . . . 3.7 Local Support Basis . . . . . . . . . . . . . . . . 3.8 Design Curve . . . . . . . . . . . . . . . . . . . 3.9 Shape Properties . . . . . . . . . . . . . . . . . . 3.10 Demonstration . . . . . . . . . . . . . . . . . . . 3.11 Nurbs . . . . . . . . . . . . . . . . . . . . . . . 3.12 Surfaces . . . . . . . . . . . . . . . . . . . . . . 3.13 Summary . . . . . . . . . . . . . . . . . . . . . 3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 41 42 44 49 51 55 56 58 60 64 64 70 71 71 4 Rational Sigma (σ ) Splines . . . . . . . . . . . 4.1 Introduction . . . . . . . . . . . . . . . 4.2 Generalized Rational Cubic Interpolant . 4.3 Interpolatory Rational σ -Splines . . . . 4.3.1 Shape Control . . . . . . . . . . 4.3.2 Some Special Cases . . . . . . 4.3.3 Examples . . . . . . . . . . . . 4.4 Freeform Rational σ -Splines . . . . . . 4.4.1 Shape Control . . . . . . . . . . 4.4.2 Some Special Cases . . . . . . 4.4.3 Examples . . . . . . . . . . . . 4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 75 76 77 77 78 78 81 84 85 87 91 5 Linear, Conic and Rational Cubic Splines . . 5.1 Introduction . . . . . . . . . . . . . . 5.2 The Rational Cubic Spline . . . . . . 5.2.1 Estimation of Tangent Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 93 95 97 2.3 2.4 2.5 2.6 2.2.4 Weighted Nu Splines . . 2.2.5 Demonstration . . . . . Freeform Weighted Nu Spline . 2.3.1 Local Support Basis . . 2.3.2 Design Curve . . . . . . 2.3.3 Shape Control . . . . . . 2.3.4 Demonstration . . . . . 2.3.5 Advantages and Features Surfaces . . . . . . . . . . . . . Summary . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contents 5.3 5.4 5.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 101 101 103 103 105 106 106 107 109 110 110 113 113 6 Shape-Preserving Rational Interpolation for Planar Curves 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . 6.2 The Rational Cubic Interpolant . . . . . . . . . . . 6.3 Interpolation of Convex Data . . . . . . . . . . . . 6.4 Interpolation of Monotonic Data . . . . . . . . . . 6.5 Interpolation of Convex and Monotonic Data . . . 6.6 Choice of Tangent Vectors . . . . . . . . . . . . . 6.7 Examples . . . . . . . . . . . . . . . . . . . . . . 6.8 Summary . . . . . . . . . . . . . . . . . . . . . . 6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 117 118 119 120 123 123 124 126 126 7 Visualization of Shaped Data by a Rational Cubic Spline 7.1 Introduction . . . . . . . . . . . . . . . . . . . . 7.2 Rational Cubic Spline with Shape Control . . . . 7.2.1 Shape Control Analysis . . . . . . . . . . 7.2.2 Determination of Derivatives . . . . . . . 7.2.2.1 Derivative Method I . . . . . . . 7.2.2.2 Derivative Method II . . . . . . 7.2.2.3 Derivative Method III . . . . . . 7.2.3 Examples and Discussion . . . . . . . . . 7.3 Positive Spline Interpolation . . . . . . . . . . . 7.3.1 Examples and Discussion . . . . . . . . . 7.4 Monotone Spline Interpolation . . . . . . . . . . 7.4.1 Examples and Discussion . . . . . . . . . 7.5 Convex Spline Interpolation . . . . . . . . . . . 7.5.1 Demonstration . . . . . . . . . . . . . . 7.6 Summary . . . . . . . . . . . . . . . . . . . . . 7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 129 133 134 135 135 135 136 136 139 142 145 148 148 153 154 154 5.6 5.7 5.8 Design Curve Analysis . . . . . . . . . . . . . Estimation of End Tangent Vectors . . . . . . . Conic Splines and Straight Line . . . . . . . . 5.5.1 Conic Arc in Cubic Spline . . . . . . . 5.5.2 Circular Spline . . . . . . . . . . . . . 5.5.3 Circular Arc . . . . . . . . . . . . . . . 5.5.3.1 Circular Arc for Given Radius . 5.5.3.2 Circular Arc for a Given Center 5.5.4 Elliptic Arc . . . . . . . . . . . . . . . 5.5.5 Intermediate Point Interpolation . . . . 5.5.6 Straight-Line Segment . . . . . . . . . Examples . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii . . . . . . . . . . . . . . . . . 8 Visualization of Shaped Data by Cubic Spline Interpolation . . . . . . . 157 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157