Who Expected That? Extreme close-ups create a Klein Bottle. | Hacker News Reader

Who Expected That? Extreme close-ups create a Klein Bottle.

thebigquestions.com

110 pointsColinWright32 comments

The klein bottle is relatively uninteresting. The technique which identified it is the interesting part here. The linked paper explains a method to take a high-dimensional point cloud and compute a 'bar code' which encodes fundamental geometric features of the solid of which the cloud is an approximation. Its a way of visualizing high-dimensional data without using dimensional reduction.

Does the point cloud approximate the shape, or does the shape approximate the point cloud? That distinction informed a recent discussion on the origin of the word "regression", which on the surface seems a weird term for curve-fitting, at least from my point of view.

I suppose the idea is that there is an underlying shape which the point cloud approximates. The fitted shape is then a statistical guess at the underlying shape. In which case it would be nice to see a proof that as more points are added the fitted shape eventually converges to the underlying shape.

from the article

"The full data set consists of roughly 8,000,000 points in E9. By normalizing with respect to mean intensity and restricting attention to high-contrast images (those away from the origin), the data set is projected to a set of points M a topological seven-sphere S7 ⊂ E8"

http://www.math.upenn.edu/~ghrist/preprints/barcodes.pdf

"a Klein bottle, which is a two-dimensional surface that can’t be squeezed into three dimensions, but fits perfectly well in nine (or for that matter in four). "

I'm having trouble squeezing this concept into my mind.

Well, a Möbius strip is a 2D surface that can't fit in 2 dimensions. Knots are 1D, and won't fit in 2 dimensions.

Is it common to refer to the Möbius strip as a 2D surface? You can't uniquely identify each point on its surface using only two dimensions, so I wouldn't call it a 2D surface at all. It lives in 3D, therefore it is a 3D surface, no?

Any small portion of the Möbius strip "looks like" a chunk of 2D object, but the entire object cannot be placed directly into 2-space. The surface of a sphere is a similar example.

Yes you can refer to each point by only two dimensions if you use a particular non-euclidian metric.

It's commonly called a non-orientable 2 dimensional manifold. Locally, it looks like a smooth deformation of the plane. The non-orientable bit is what distinguishes it (globally) from something more like a cylinder.

You can't uniquely identify each point on its surface using only two dimensions

Yes you can. Run a sharpie along the bottom edge of the paper so that it bleeds onto both sides of the paper. Now tape the ends of the strip together with a half twist to make a Möbius strip. Place a point anywhere on the strip. Draw a line through that point such that the line meets both edges of the strip at a right angle. Measure the distance along that line between your point and the darkened edge; call this x. Now, hold the Möbius strip in your left hand so that you're pinching it by the tape. With your right hand, run your finger along the strip, starting from the tape and moving to the right. Measure how far you have to move your finger in order to reach the line you drew; this could require up to two loops around the strip. Call this distance y. The tuple (x,y) uniquely identifies your point.

Wow. It took me a while to figure out what you were saying, but it was well said and I eventually got it. Thanks.

For the record, we use a similar trick on sphere-like surfaces, as latitude and longitude.

Oh dear, I just realized I dropped a sentence while I was composing this comment and now it's too late to edit. The beginning of it should read, "Yes you can. Cut out a long rectangular strip of paper. Run a sharpie..."

Alternately, just realize that the rectangular strip of paper has a natural set of coordinates, and nothing is lost by twisting and taping. You get a discontinuity at the tape, but that's not a problem.

If you disagree with the terminology, that's your opinion. A lot of terminology is kind of weird. "Klien Bottle" is called that because it was called "Klien Surface" in German, but "Surface" in German kind of sounds like "Flask", and they mistranslated. The name stuck because it was kind of appropriate.

I say it's a 2D surface, because while it lives in 3D, it's "thin" in one dimension. It's like saying a piece of paper is a 2D object.

And when I say "it can't live in 2D", I'm kind of lying - it can live in a weird kinky 2D space, but NOT a boring 2D plane. Well, you could smash it into a 2D plane, but it would self-intersect (get all smushed together, losing its shape). And by "shape", I mean topological properties ... but I hate jargon.

But a Mobius strip is a 2D surface which can't live in 2D (a boring flat 2D plane); in the same way a Klien Flask is a 2D surface which can't live in 3D; and a knot is a 1D surface which can't live in 1 or 2D. Press a knot into 2D, and it crosses itself (self-intersect). Force a knot into 2D, and it will break, or join up with itself (depending on the material).

Real mathematicians (i.e. not me) will say "manifold", not surface, but it's more or less the same thing.

Have you considered that this pattern may be a result of camera internal structure rather than structure of objects?

The linked paper shows how the klein bottle maps onto the space. Basically, grids which have an orientation (horizontal or vertical stripes) are more common and join together to form a klein bottle. That tendency towards orientation might be an artefact of the camera or might be because cameras are usually held horizontal or vertical relative to the sky.

The paper notes that the vertical lines are gravity aligned, not camera aligned.

The paper desperately needs a accompanying translation from extreme mathematician to mortal PhD level.

The second (expository) paper is pretty readable. I have only the barest grasp of algebraic topology but I believe I have a rough high-level understanding of what it is doing. It would be interesting to implement their barcode program independently to test whether or not I really understand.

The comment is interesting. He? argues that any 2 manifold with no edges would be likely to end up as a Klein bottle. The question is then why a 2 manifold. Well, the thing we're asking about is a 2d picture, right? Maybe that has something to do with it. Let's suppose we tried the same trick using 3x3x3 pixel representations of STL models — might that turn out to be form a simple edge less 3 manifold embedded in 27 dimensional space? (perhaps for simplicity we could use 2x2x2 cubes and look at 8 dimensional space... In essence we're talking about a population of 2d data arbitrarily but consistently mapped into higher dimensional space and we discover it maps to a 2 manifold.

Are you talking about things like sensor noise and chromatic aberration? It would be interesting to see if downsampling the image beforehand affects the result.

However, it's hard to separate image patterns from camera structure insofar as linear projection is a result of camera structure.

I was thinking about CFA mosaic and JPG compression, I think these may introduce some axis aligned artifacts. But maybe they took it into account (using raw format?) or effect is not relevant in this case.

Even in raw format, all digital cameras apply some amount of sharpening [1] even when the setting is "off" in the camera menu. Also, all raw format conversion software (Lightroom, Capture One, etc.) applies sharpening by default.

I could imagine that a sharpening algorithm could transform a random distribution into something with structure. That the authors appear to not reference camera or image sharpening anywhere in the paper is somewhat worrisome.

[1] http://en.wikipedia.org/wiki/Unsharp_masking

It's mentioned in the abstract of [1], but not really expanded upon.

[1] http://www.dam.brown.edu/people/mumford/Papers/DigitizedVisi...

Shouldn't zoomed photographs of smooth objects have mostly identical pixels, with the 9-dimension coordinates clustering around the all-pixels-at-the-same-intensity axis?

Edit: Oh, the papers mention this is about feature extraction and they filter for high-contrast patches.

Yeah, not mentioning the filtering for high contrast makes this more confusing than it need be. Actually, the main link is worse than just not mentioning it... it says "randomly choose 3-by-3 pixel patches" and leaves it at that. Saying "random" rather than "random then filtered" is worse then just saying nothing and letting the reader guess that maybe there is something going on in the choosing.

Does this allow for better compression, for example?

I don't know about compression (though there's allegedly some research using fractals in video compression, but I have no idea if and how that works), but there is image pattern recognition method that is very similar. It's called Local Binary Patterns and it cuts image into square blocks and uses a clever way to turn that blocks into binary string, for example 3x3 pixels block into 8 bits. You run this process across a texture, and get a histogram of features the texture has, like corners, black spots, white spots, gradients and similar. LBP is also inherently invariant to lightning (it uses "lighter than/darker than" instead of absolute values) and there are modifications that make it rotation invariant too (rotating the strings to biggest sequence of ones, for example).

It's pretty smart, really.

This strongly reminds me of the Bible Code[1], or rather of the Moby Dick Code[2]

Take any large body of work, manipulate it in some way, then patterns will emerge that make it resemble something else.

I mean seriously: they take a photo and reduce it down to a 3x3 square, arbitrarily convert the numerical values of those pixels to numbers, then take those nine numbers as 9-dimensional coordinates. The result is a surface that looks a little bit like a Klien bottle, but isn't really, since the surface is 4-dimensional instead of 2.

[1] http://en.wikipedia.org/wiki/Bible_code

[2] http://cs.anu.edu.au/people/bdm/dilugim/moby.html

This is a terribly incorrect trivialization of the work they did. The idea is not to observe some meaningless pattern emerge. Instead, they're trying to describe the statistics of random 3x3 pixels taken from photographs of nature (in fact, only of the luminosity of each pixel, hence the black-and-white photos). At a first thought, you'd expect this to be completely random, but it looks like there is a certain statistical structure to it. You only find this structure far-fetched because you're reading a blogger's vulgarization of the scientific paper whose concepts you're not familiar with.

Unlike the unreasonable bible and Moby Dick codes, this has practical applications in image manipulation and compression.

Error establishing database connection

Reply on news.ycombinator.com