Visual Computing: Geometry, Graphics, and Vision: Geomery, Graphics, and Vision (Charles River Media Graphics) [Hardcover]

I should say from the get-go that I know the author personally, and I've reviewed chapters before the book appeared. I think this book fills a great space between more applied computer vision or computer graphics books, and the more theoretical computational geometry books. It provides a host of practical problems that the author has encountered in his research at Sony Research Labs, and feeds tons of excellent theory to solve it. The theoretical part is made very accessible, even if it assumes some reasonable (college-level) mastery of linear algebra.

The biggest attraction of this book is that it lies at the confluence of several fields. Depending on your background, you may be more versed in the systems issues (vision or graphics), or the algorithmic issues (computational geometries). The first kind of person will really appreciate all the foundations they are given to solve the problems at hand. How to apply them is very well explained in the chapters by using hands-on examples, and ample illustration.

To give you a short idea of the table of contents (more information can be found on the author's book web site, easily found through google):

The chapter on images, for instance, does great job discussing Halftoning, Morphing, Color space, and Interpolation/Sampling/Convolution, and contains material that will be familiar to computer vision and graphics people.

On the other hand, the chapter on meshes (with discussion of half-edge and mesh data structures, and mesh smoothing/parameterization) will be very familiar to a computational geometer or graphics person.

The chapter on data structures includes what is usually found in advanced algorithm textbooks. The advantage of having it in such a context is that its presentation is much more adapted to immediate use. There is also practical considerations such as C++ implementation, and a separate chapter on the use of randomization as an algorithmic design technique. That chapter covers an important problem of point registration and geometric point matching that is very useful in camera registration and in photo merging.

The central piece (that takes 130 pages) is the discussion of coordinates (chapter 3, "The Coordinate Pipeline") which achieves the feat of presenting all that is useful for discussing images (2D), meshes (3D), or camera transformation (projective geometry) in a unified and very accessible presentation. This chapter also introduces a few fundamental tools like homographies and epipolar geometry, singular value decomposition (SVD), Plucker coordinates (for lines in space), conics and quadrics. It is a gem and will prove an invaluable reference in my library.

Finally beyond the algorithmic and application issue, the author concludes with a chapter on robustness, a problem that plagues all these applications. It discusses a set of techniques that can be used to eradicate or at least lessen floating-point precision-related crashes (which not just result in numerical inaccuracy, but can altogether prevent the successful completion of a program and generate all kinds of catastrophic failures).

To recap, this is an excellent books that puts into perspective techniques from more theoretical algorithm and geometry communities to use for vision and graphics problem, among other applications. It is geared towards researchers/developers of applications. It is not a research monograph, and can advantageously be used as a textbook for a graduate or advanced underdgraduate class.

This is not a "How did Photoshop do it?" kind of algorithm book. I would suggest that if you want to make good use of this book that you already have had a course on the theory of algorithms, and thus understand how to follow the derivation of whether an algorithm is O(n), O(nlgn), etc. That is because the author dedicates much space to determining what the time-efficiency of each algorithm is before he goes into the details. Next, the author talks about each algorithm in pseudocode, and then finally there is the actual C++ code for the algorithm itself. Not every algorithm involves OpenGL, because quite a few of them don't actually draw anything, they just support the drawing of images by other algorithms. The book is well illustrated. Whenever there might be a question about an algorithm that words or equations can't answer, there always seems to be a figure available to finish the job. The book has a very academic tone to it, and each chapter ends with extensive bibliographic notes. The following is the table of contents:

1. Overview - A fly-over of the entire book.

2. Abstract Data Structures - Talks about solutions to common problems that come up time and again in visual computing. Topics include the Fibonacci numbers, conversions between 1D and nD array indices, how to flood-fill an area using a queue, and detecting whether or not a set of line segments intersect. This may not seem to have much to do with data structures, but the book ties it all in.

3. Coordinate Pipelines - Subjects include translation between Euclidean and projective points, 2D polygon transformations, 3D mesh transformations, and how to render multiple views to one device display by using viewport mappings. OpenGL is used heavily in this chapter.

4. Images - An oddly titled chapter, because if you get right down to it, the whole book is technically about images. The topics include the simple task of displaying the RGB color cube in OpenGL as well as the more complex tasks of image warping, image compositing, halftoning, and dithering.

5. Meshes - Meshes come up often when drawing complex and realistic 3D figures. Topics include approximating a sphere by with a mesh and various remeshing experiments and algorithms with the "Stanford Bunny" as a subject of these experiments.

6. Animation - A brief overview of what it takes to make your images "move". I found this the least satisfying of the book's chapters. "Computer Animation" by Parent does a better job of discussing this topic, in my opinion.

7. Randomization - Topics include computing a uniformly random permutation, quick sort, selecting the nth smallest element of an array, and computing the scaled rigid transformation matching a given pair of segments. The author does a great job of discussing the algorithms, but comes up a bit short in the motivation for these algorithms in visual computing.

8. Higher Dimensions for 3D - Includes some good algorithms on computational geometry and how it ties into graphics. Topics include the k-means iterative clusteriing method, rasterizing a Voronoi diagram, and computing an approximation of the smallest enclosing ball in large dimensions. The author does a good job of tying in each algorithm to its significance in graphics.

9. Robustness - Discusses how to determine if certain algorithms are easily "broken". This discussion is done from the perspective of computing the area of triangles using floating point numbers and also determining if and only if two line segments intersect.

This book does not hold your hand on the issues of algorithm theory, C++ programming, OpenGL, or even basic computer graphics and image processing theory. You are expected to already know that material. This book is more about the algorithms that are applicable to geometry, graphics, and vision and what makes them useful, efficient, and robust. Highly recommended.

We are visually oriented people. As the old saying goes, a picture is worth a thousand words. And with the dramatic increases in computer power that have come about in recent years we can visually display things that not too many years ago took a whole room of equipment.

This book presents a concise one volume introduction to visualizing data structures. It is not specific to any one discipline. The biologist programming how to visualize DNA will get as much out of the book as will the game developer. The material is presented at the undergraduate student level where some programming experience, especially in C++ is a prerequisite.

While there is no CD in the book, there is a companion web site maintained at the publishers which includes the source code of examples given in the book as well as additional source codes of various algorithmic procedures as well as test data to check that the code is compiling correctly. Also on the web are pointers to useful resources related to the contents of each chapter.