This edition first published 2014
© 2014 John Wiley & Sons Ltd

Registered office
John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com .

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

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 the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data

Dictionary of computer vision and image processing / R. B. Fisher, T. P. Breckon,
K. Dawson-Howe, A. Fitzgibbon, C. Robertson, E. Trucco, C. K. I. Williams. – 2nd edition.
  pages cm
  Includes bibliographical references.
  ISBN 978-1-119-94186-6 (pbk.)
 1. Computer vision–Dictionaries. 2. Image processing–Dictionaries. I. Fisher, R. B.
  TA1634.I45 2014
  006.3′703–dc23

2013022869

A catalogue record for this book is available from the British Library.

ISBN: 9781119941866

From Bob to Rosemary,
Mies, Hannah, Phoebe
and Lars

From Toby to Alison, my
parents and Amy

From Ken to Jane,
William and Susie

From AWF to Liz, to my
parents, and again to D

From Craig to Karen,
Aidan and Caitlin

From Manuel to Emily,
Francesca, and Alistair

Preface

This dictionary arose out of a continuing interest in the resources needed by students and researchers in the fields of image processing, computer vision and machine vision (however you choose to define these overlapping fields). As instructors and mentors, we often found confusion about what various terms and concepts mean for the beginner. To support these learners, we have tried to define the key concepts that a competent generalist should know about these fields.

This second edition adds approximately 1000 new terms to the more than 2500 terms in the original dictionary. We have chosen new terms that have entered reasonably common usage (e.g., those which have appeared in the index of influential books) and terms that were not included originally. We are pleased to welcome Toby Breckon and Chris Williams into the authorial team and to thank Andrew Fitzgibbon and Manuel Trucco for all their help with the first edition.

One innovation in the second edition is the addition of reference links for a majority of the old and new terms. Unlike more traditional dictionaries, which provide references to establish the origin or meaning of the word, our goal here was instead to provide further information about the term.

Another innovation is to include a few videos for the electronic version of the dictionary.

This is a dictionary, not an encyclopedia, so the definitions are necessarily brief and are not intended to replace a proper textbook explanation of the term. We have tried to capture the essentials of the terms, with short examples or mathematical precision where feasible or necessary for clarity.

Further information about many of the terms can be found in the references. Many of the references are to general textbooks, each providing a broad view of a portion of the field. Some of the concepts are quite recent; although commonly used in research publications, they may not yet have appeared in mainstream textbooks. Subsequently, this book is also a useful source for recent terminology and concepts. Some concepts are still missing from the dictionary, but we have scanned textbooks and the research literature to find the central and commonly used terms.

The dictionary was intended for beginning and intermediate students and researchers, but as we developed the dictionary it was clear that we also had some confusions and vague understandings of the concepts. It surprised us that some terms had multiple usages. To improve quality and coverage, each definition was reviewed during development by at least two people besides its author. We hope that this has caught any errors and vagueness, as well as providing alternative meanings. Each of the co-authors is quite experienced in the topics covered here, but it was still educational to learn more about our field in the process of compiling the dictionary. We hope that you find using the dictionary equally valuable.

To help the reader, terms appearing elsewhere in the dictionary are underlined in the definitions. We have tried to be reasonably thorough about this, but some terms, such as 2D, 3D, light, camera, image, pixel, and color were so commonly used that we decided not to cross-reference all of them.

We have tried to be consistent with the mathematical notation: italics for scalars (s), arrowed italics for points and vectors , and bold for matrices (M).

The authors would like to thank Xiang (Lily) Li, Georgios Papadimitriou, and Aris Valtazanos for their help with finding citations for the content from the first edition. We also greatly appreciate all the support from the John Wiley & Sons editorial and production team!

It is also our pleasure to introduce a new feature that appears in the Enhanced Ebook version of the dictionary - videos. In order to make clearer some of the terms and effects, 59 videos have been attached to the terms, such as for the terms ‘automated visual surveillance’ and ‘chroma keying‘. We hope that these videos will increase the value of the dictionary.

Numbers

1-norm: A specific case of the p-norm, the sum of the absolute values of the entries of a given vector , of length n. Also known as the taxicab (Manhattan) norm or the L1 norm. [Sho07]

2D coordinate system : A system uniquely associating two real numbers to any point of a plane. First, two intersecting lines (axes) are chosen on the plane, usually perpendicular to each other. The point of intersection is the origin of the system. Second, metric units are established on each axis (often the same for both axes) to associate numbers to points. The coordinates Px and Py of a point, P, are obtained by projecting P onto each axis in a direction parallel to the other axis and reading the numbers at the intersections: [JKS95:1.4]

2D image: A matrix of data representing samples taken at discrete intervals. The data may be from a variety of sources and sampled in a variety of ways. In computer vision applications, the image values are often encoded color or monochrome intensity samples taken by digital cameras but may also be range data. Some typical intensity values are: [SQ04:4.1.1]

2D pose estimation: A special case of 3D pose estimation. A fundamental open problem in computer vision where the correspondence between two sets of 2D points is found. The problem is defined as follows: Given two sets of points and , find the Euclidean transformation (the pose) and the match matrix {Mjk} (the correspondences) that best relates them. A large number of techniques has been used to address this problem, e.g., tree-pruning methods, the Hough transform and geometric hashing. [HJL+89]

2D projection: A transformation mapping higher dimensional space onto two-dimensional space. The simplest method is to simply discard higher dimensional coordinates, although generally a viewing position is used and the projection is performed.

For example, the main steps for a computer graphics projection are as follows: apply normalizing transform to 3D point world coordinates; clip against canonical view volume; project onto projection plane; transform into viewport in 2D device coordinates for display. Commonly used projection functions are parallel projection and perspective projection. [JKS95:1.4]

2.1D sketch: A lesser variant of the established 2.5D sketch, which captures the relative depth ordering of (possibly self-occluding) scene regions in terms of their front-to-back relationship within the scene. By contrast, the 2.5D sketch captures the relative scene depth of regions, rather than merely depth ordering: [NM90]

2.5D model: A geometric model representation corresponding to the 2.5D image representation used in the model to (image) data matching problem of model-based recognition: [Mar82] An example model is:

3D coordinate system: Same as 2D coordinate system but in three dimensions: [JKS95:1.4]

3D data: Data described in all three spatial dimensions. See also range data, CAT and NMR. [WP: 3D_data_acquisition_and_object_reconstruction] An example of a 3D data set is:

3D motion estimation: An extension of motion estimation whereby the motion is estimated as a displacement vector in 3. [LRF93]

3D motion segmentation: An extension to motion segmentation whereby motion is segmented within an 3 dataset. [TV07]

3D object : A subset of 3. In computer vision, often taken to mean a volume in 3 that is bounded by a surface. Any solid object around you is an example: table, chairs, books, cups; even yourself. [BB82:9.1]

3D pose estimation : The process of determining the transformation (translation and rotation) of an object in one coordinate frame with respect to another coordinate frame. Generally, only rigid objects are considered; models of those objects exist a priori and we wish to determine the position of the object in an image on the basis of matched features. This is a fundamental open problem in computer vision where the correspondence between two sets of 3D points is found. The problem is defined as follows: Given two sets of points and , find the parameters of a Euclidean transformation (the pose) and the match matrix {Mjk} (the correspondences) that best relates them. Assuming the points correspond, they should match exactly under this transformation. [TV98:11.2]

3D reconstruction: The recovery of 3D scene information and organization into a 3D shape via e.g., multi-view geometry: [HZ00:Ch. 10]

3D shape descriptor : An extension to regular shape descriptor approaches to consider object shape in 3. [Pri12:Ch. 17]

3D skeleton: A 3D extension of an image skeleton defining a tree-like structure of the medial axes of a 3D object (akin to the form of a human stick figure in the case of considering a person as a 3D object). See also medial axis skeletonization: [Sze10:12.6] See example below:

3D SURF: A 3D extension to the SURF descriptor that considers the characterization of local image regions in 3 via either a volumetric voxel-based or a surface-based representation. [KPW+10]

4 connectedness: A type of image connectedness in which each rectangular pixel is considered to be connected to the four neighboring pixels that share a common crack edge. See also 8 connectedness: [SQ04:4.5] Four pixels connected to a central pixel (*):

Four groups of pixels joined by 4 connectedness:

4D representation (3D-spatial + time): A 3D times series data representation whereby 3D scene information is available over a temporal sequence. An example would be a video sequence obtained from stereo vision or some other form of depth sensing: [RG08:Ch. 2]

8 connectedness: A type of image connectedness in which each rectangular pixel is considered to be connected to all eight neighboring pixels. See also 4 connectedness: [SQ04:4.5] Eight pixels connected to a central pixel (*):