text-only page produced automatically by LIFT Text Transcoder Skip all navigation and go to page contentSkip top navigation and go to directorate navigationSkip top navigation and go to page navigation
National Science Foundation Home National Science Foundation - Mathematical & Physical Sciences (MPS)
Mathematical & Physical Sciences (MPS)
design element
MPS Home
About MPS
Funding Opportunities
Awards
News
Events
Discoveries
Publications
Advisory Committee
Career Opportunities
2013-2014 Distinguished Lecture Series
View MPS Staff
MPS Organizations
Astronomical Sciences (AST)
Chemistry (CHE)
Materials Research (DMR)
Mathematical Sciences (DMS)
Physics (PHY)
Office of Multidisciplinary Activities (OMA)
Proposals and Awards
Proposal and Award Policies and Procedures Guide
  Introduction
Proposal Preparation and Submission
bullet Grant Proposal Guide
  bullet Grants.gov Application Guide
Award and Administration
bullet Award and Administration Guide
Award Conditions
Other Types of Proposals
Merit Review
NSF Outreach
Policy Office
Other Site Features
Special Reports
Research Overviews
Multimedia Gallery
Classroom Resources
NSF-Wide Investments

Email this pagePrint this page

Discovery
Klein Bottle is a Real Natural in the Zoo of Geometric Shapes

Discovery could advance understanding of human vision and lead to powerful data compression techniques

Image of a two-dimensional representation of the Klein bottle topology.

A two-dimensional representation of the Klein bottle topology.
Credit and Larger Version

October 7, 2008

A picture may speak a thousand words, but Stanford mathematician Gunnar Carlsson is more interested in the shape of its data.

Thanks to computers, any photograph taken anywhere in the world can be reduced to a set of data that can itself be transformed into a multi-dimensional picture by plotting the data points according to their distance from the other points. In the mathematical sense, "distance" means how similar or dissimilar a point of data is to another data point. Points with a lot in common sit closely together while points with very little in common sit far apart.

"The notion of distance is a useful tool to those of us working in algebraic topology, because it allows us to study signatures that tell you the rough nature of a shape; for example, whether is it a circle, doughnut, sphere or any other member of the zoo of all possible shapes," Carlsson said. "This method of signatures has recently been extended to work for probability distributions, and allows one to study them geometrically." The ubiquitous Bell Curve, which describes the normal distribution of many features of data such as salary ranges and human height, produces the baseline, or most trivial, topological signature. For other kinds of data, more complicated signatures appear.

Topology, the field Carlsson and his colleagues work in, has its roots in Euclidean geometry but focuses on the qualitative features of a space, such as shape, rather than on quantitative measures such as size. Topologists pay special attention to a space's homology--whether or not it has any holes--and whether or not those holes persist even when the space is deformed.

For example, a teacup and a doughnut have the same topology because both can be deformed into the other's shape and back again without any tearing or resticking of the parts. These varying deformations, called "homeomorphisms," generate the same data signature and therefore convey fundamental information about a space.

Topologists also want to know how a space is connected to itself. Any subway rider has experienced the usefulness of connectedness when viewing a diagram of the track's system. Rather than concerning themselves with actual track distances, they typically pay more attention to how their destination station sits in relation to the other stations.

The topology of everyday examples seems pretty straightforward but when mathematicians work with abstract shapes in more than three dimensions, the game gets challenging fast. Not surprisingly, crunching data generated from thousands of black-and-white images of the natural world is far more complex than a simple Bell Curve plotting.

For the Stanford study, funded in part by three awards from the National Science Foundation, each data point represented a patch from one of the images. Each patch covered a space of three pixels by three pixels and was described mathematically by an array of nine gray-scale values. Each such array is considered a data point and there is a natural notion of distance. If one considers all the patches, one will include a very large number of "low contrast patches."

For example, the sky will have many patches in which one gray scale value occurs in all the pixels. In fact, such low contrast patches dominate the statistics and obscure all other features of the data if they are included.

Researchers at Brown University constructed the data set used by Carlsson's team by removing all the low-contrast patches, retaining only high contrast patches, such as those occurring on the horizon. The resulting data set sits in a nine dimensional space as there are nine coordinates for each patch.

"Humans can't see in nine dimensions so the topological signatures give us a substitute for vision in situation like this," Carlsson said. "We developed the PLEX software to determine the signatures of the shapes of this data set and others like it."

And that signature surprised everyone. In addition to a circle, which other mathematicians had anticipated, they got something completely unexpected and far more contorted: a two-dimensional Klein bottle.

A Klein bottle is a three-dimensional version of a mobius strip. If you've never heard of either one it's probably because you're not a mathematician. The latter is a really simple concept. Take a strip of paper, twist it once and tape the ends together. Let your finger trace one side all the way around the track and you'll wind up right back where you started.

Although it may appear to have two sides, a Mobius strip is an object with only one surface and one edge. Your finger never has to jump sides to trace the strip's entire surface or edge. A Klein bottle is a more complex and goofy looking version of the same concept because the neck of the bottle disappears into itself in such a way that there is no outside or inside, just one continuous surface. A true Klein bottle needs at least four dimensions; in other words, it can't be blown from glass. As humans only see in three dimensions, the fourth dimension must be inferred from a three-dimensional representation.

"The Klein bottle given by the data in this study is actually represented in nine dimensions," Carlsson said. "Two- and three-dimensional representations exist, as in the picture accompanying this article, which help people visualize the topology, but they are not completely faithful to the original shape."

The Stanford team published their research results in a paper titled "On the local behavior of spaces of natural images" in the January issue of the International Journal of Computer Vision.

The discovery of a Klein bottle shape in the database of natural images, intriguing enough in itself, may provide a short cut to new mathematical discoveries and technological advances.

"The most obvious outcome is it might well lead to a better way of compressing huge sets of photographic data," Carlsson said. DARPA, the Defense Advanced Research Projects Agency, supplied extensive funding for the research. "The Defense Department is interesting in developing a lot of sophisticated methods of analyzing data," Carlsson noted. "They believe this research might someday be of use."

The results also dovetailed with findings by a group of Dutch vision scientists who study human vision. The Dutch scientists actually collected the original database of natural images used by the Stanford researchers for their own work on the primary visual cortex. A paper describing their study titled "Topological Structure of Population Activity in Primary Visual Cortex" appeared in the Journal of Vision earlier this year.

"It turns out that neurons in that part of the brain tend to fire when the eyes see the high-contrast stimuli which make up the Klein bottle," Carlsson said. "So the human visual system seems to have a built-in response to these statistics. Perhaps the brain has its own advanced data compression method based on a Klein bottle topology." He anticipates additional studies to investigate further the link between vision and the Klein bottle.

Based on their findings, Carlsson and his team are considering several related studies. "What kind of signature would we see if we analyzed X-rays?" he mused. "The data would have a much narrower scope and some obvious differences--in an X-ray, white isn't a patch of sky, it's something dense like bone. We can't really predict the signature so it's something we'd like to look into."

Asked if he might ever use the PLEX software to analyze something like great works of art, he replied: "We'd have to encode color, it's definitely not gray scale. That would be a whole different modality." His team is already investigating one other "modality" by considering data from images taken while the camera was moving. "It's still gray scale," he remarked. "We've got to learn to walk before we can fly."

--  Diane Banegas, National Science Foundation (703) 966-0316 dbanegas@nsf.gov
--  Christopher W. Stark, National Science Foundation (703) 292-4869 cstark@nsf.gov

Investigators
Gunnar Carlsson
Tamal Dey
Persi Diaconis
Leonidas Guibas
Tigran Ishkhanov
Joshua Tenenbaum

Related Institutions/Organizations
Stanford University

Locations
California

Related Programs
Topology
Statistics
Probability
Computational Mathematics

Related Awards
#0406992 Homotopy Theoretic Investigations in Higher K-theory, High-dimensional Data Analysis, and High Dimensional Manifold Theory
#0138456 CARGO: Shape Analysis From Point Cloud Data
#0101364 FRG: Topological methods in data analysis

Total Grants
$2,246,320

Related Agencies
Defense Advanced Research Projects Agency

Related Websites
Preprint: A Topological Analysis of the Space of Natural Images” by Gunnar Carlsson & Tigran Ishkhanov, Stanford University Department of Mathematics.: http://comptop.stanford.edu/preprints/tigran-paper2.pdf

Photo of Stanford mathematician Gunnar Carlsson.
Stanford mathematician Gunnar Carlsson.
Credit and Larger Version

Image of a klein bottle with bands removed to show the interior connection.
Klein bottle with bands remove to reveal the interior connection.
Credit and Larger Version



Email this pagePrint this page
Back to Top of page