1Image SpacesWhat might an image space be• Map each image to a point in a space.• Define a distance between two points in that space.• Maybe also a shortest path (morph).• We have already seen a simple version of this, in which each n-pixel image is mapped to a point in R^n, and Euclidean distance is used.– Also, we’ve considered linear subspaces (Eigenfaces, Fisherfaces). Each point is mapped to nearest location on the subspace.– Shortest path in R^n is just linear interpolation of the images, which doesn’t seem like the right morph.– What is shortest path with Eigenfaces?2Riemannian Manifold• More general notion of an image space– Can have different topology than Euclidean space.– Can represent non-linear subsets of images (more on this is a few weeks).– Can provide more general sense of distances.Manifold• “A smooth manifold of dimension m is a locally compact Hausdorff space M together with the following collection of data (henceforth called atlasor smooth structure) consisting of:– An open cover {Ui} of M– Continuous injective maps Fi: Ui->Rm(called charts or local coordinates) such that:( ) ( )smooth. is:mapn transitio the0 if1jmjijmjiiijiUUUUUUℜ⊂Ψ→ℜ⊂ΨΨΨ≠−Lectures on the Geometry of Manifolds by Nicolaescu.3Manifold - informal• A manifold is:– A set (collection of images) with the usual topological properties (eg., not discrete)– A mapping from the neighborhood of each point to Euclidean space of fixed dimension.– So that these mappings fit together smoothly.• Example: the surface of a sphere.• Example: any surface that is topologically a sphere.• The definition implies: At any point on the manifold, we can construct a tangent space.Riemann Manifold• A Riemann Manifold is a pair (M,g)consisting of a smooth manifold M and a metric g on the tangent bundle, i.e. a smooth symmetric positive definite tensor field on M. g is called a Riemann metric on M. • The tangent bundle is (informally) the collection of tangent spaces of M.4Riemann Manifold - intuition• We define a local distance on the manifold. – At any point, for any direction we move in, there is a local distance defined.– This distance is locally linear. If we define the distance for m orthogonal directions, the distance in any other direction is a linear combination of these.• Example: any surface in Euclidean space that is topologically a sphere with the usual Euclidean distance. Geodesic• Analogous to lines, geodesics are shortest paths between points.• Shortest paths locally, but not globally.– For any two points very close together on the geodesic, it is the shortest path.• Example: on a sphere, any two points are connected by two geodesic paths, along two directions of the great circle connecting them.5Why manifolds?• Seems like correct mathematical notion of an image space with distances.• Generality greater than Euclidean space.– Image space may be topologically like a sphere, not like Rn– Offers much more flexible distancesKendall’s shape space• Two sets of 2D points.• Mostly we assume there exists a correct one-to-one correspondence• And this correspondence is given.– This is very natural in morphometrics, where points are measured and labeled.– In vision we must solve for correspondence. Next class we’ll look at papers that do this.6Shape Space• What is shape? Qualities of points that don’t depend on translation, rotation or scale.• So describe points independent of similarity transformation.1. Remove translation.• Simplest way, translate so point 1 is at origin, then remove point one.• More elegant, translate center of mass to origin, remove a point.2. Scale so that sum ||Xi||^2 = 1.Resulting set of points is called pre-shape.Pre because we haven’t removed rotation yet.Notation: , U and X denote sets of normalized points. Points called Xi and Ui, with coordinates (xi,yi), (ui, vi).Pre-shape• If we started with n points, we now have n-1 so that:• sum xi^2 + yi^2 = 1.• So we can think of these coordinates as lying on a unit hypersphere in 2(n-1)-dimensional space.7Shape• If we consider all possible rotations of a set of normalized points, these trace out a closed, 1D curve in pre-shape space.• Distances between shapes can be thought of as distances between these curves.– Notice that to compute distance, without loss of generality we can assume that one set of points (U) does not rotate, since rotating both point sets by the same amount doesn’t change distances.Procrustes Distances• Full Procrustes Distance. DF– min(s, θ) ||U – sXR(θ).|| That is, we find a scaling and rotation of X that minimizes the euclideandistance to U. (R(θ) means rotate by θ).• Partial Procrustes Distance. DP– min(θ) ||U – XR(θ)||. That is, rotate X to minimize the euclidean distance to U.• Procrustes Distance. ρ– Rotate X to minimize the geodesic distance on the sphere from X to U.8Linear Pose Solving• We can linearly find optimal similarity transformation that matches X to U. (ie., minimize sum ||AXi-Ui||^2, where A is a similarity transformation. – This is asymmetric between X and U.• In same way we can linearly compute Full ProcrustesDistance.– This is symmetric.– Leads immediately to other procrustes distances.Linear Pose: 2D rotation, translation and scaleθθθθθθsin,coswith 111...111...cossinsincos...212121212121sbsayyyxxxtabtbayyyxxxttsvvvuuunnyxnnyxnn==  −  −= • Notice a and b can take on any values.• Equations linear in a, b, translation.• Solve exactly with 2 points, or overconstrained system with more.sabas =+=θcos229Similarity Matching• Given point sets X and U, compare by finding similarity transformation A that minimizes ||AX-U||.– X = points X1, …Xn. U = points U1…Un.– Find A to minimize sum ||AXi – Ui||^2– This is just a straightforward, linear problem.• Taking derivatives with respect to four unknowns of A gives four linear equations in four unknowns.Issues with this approach• It is asymmetric.– Ok when comparing a model to an image.– Not so sensible for comparing two shapes.10• Note that we now also know how to calculate the Full Procrustes Distance. This is just a least-squares solution to the overconstrained problem:  − 