Nerdsnipes

[eriador]

I have a feeling that just about everybody who frequents this board probably pays enough attention to xkcd to know what a nerdsnipe is. I have a habit of "nerdsniping" myself, by coming up with interesting problems. However, I usually don't know enough to solve them alone. So, I thought a thread would be the way to go.

Anyway, for our first problem, I was driving home yesterday when I saw a billboard that had been painted on the side of a building and was being painted over. They were about half done, so the ad still could be kinda made out, and I could piece together a rough idea of what it was saying. However, that got me thinking. Would it be possible to present information in such a way that if half was obscured, it could still be understood? If one assumes a certain pattern (such as paint the left half) it's easy... but let's get more abstract...

Is it possible to present visual information in two dimensions, such that if ANY 50% of the area (in any number of contiguous sections) were obscured, the ENTIRE meaning would be understandable? Of course, that can mean conceptually (every idea makes it across clearly) or literally (every single piece of data survives).

I can't even transmit a single bit without making assumptions about how the obfuscation works... what I'm saying is that we have to imagine our messages as a billboard, and overnight somebody is allowed to come and paint whatever they want on the billboard, as long as it doesn't change exactly 50% of our image. I can't think of a way of resisting that.

[zeroguy]

For people who haven't memorized every xkcd title.

Is it possible to present visual information in two dimensions, such that if ANY 50% of the area (in any number of contiguous sections) were obscured, the ENTIRE meaning would be understandable? Of course, that can mean conceptually (every idea makes it across clearly) or literally (every single piece of data survives).

No, not the latter one, certainly. If you could reliably transmit data even while losing 50% of it... that sounds like a hell of a lot better error correction system than anything I've ever heard of. A (3,1) hamming code is the best you can do, I think, which would allow for a one bit loss for three bits.

And due to the nature of the problem, any piece of data you want to send would have to use up over half of the billboard, since otherwise you could lose the half of the billboard that it's on. Then you've left less than half of the board for the rest of the data, which would then be completely lost. So you can't really transmit more than a single bit.

If you're not thinking of it in bits, though, and rather thinking with, say, actual colors you could put on a billboard, then you can sort of do it. Fill the billboard with a color, and map that color to a number with some mapping. Since the wavelength of light via color is analog, the possibilities are infinite as to what color it can be, so you could transmit any number you wanted. So, just convert whatever information you wanted to transmit into a single number, and map that to a color, and paint the billboard that color.

Edt: it's late and I'm tired, and I'm almost certain some of what I've said there is wrong. Oh, well, will try to fix it later.

[eriador]

but if 50% is the color in which you've encoded your data, and 50% is an obscuring color how does one distinguish them?

[thatguy1944]

are we talking about computer based information or actual real life goodness??

[eriador]

Visual information. Computer or human read, as you wish.

[KennEnder]

Because you've said *ANY* 50% could be obscured, I think the only way to insure success would be to make the image 50% symmetrical. True, it's a special case, but the image would be recoverable each and every time. If not... highly doubtful.

[Eaquae Legit]

I don't need sniping. Just make it a starry night and I'll walk into trees all by myself!

[eriador]

Because you've said *ANY* 50% could be obscured, I think the only way to insure success would be to make the image 50% symmetrical. True, it's a special case, but the image would be recoverable each and every time. If not... highly doubtful.

Huh? What if I blanked out any occurrence of a specific pattern? You wouldn't be able bring it back :p

[KennEnder]

True enough... I guess I wasn't thinking of the "targeted" attack as such.

[zeroguy]

but if 50% is the color in which you've encoded your data, and 50% is an obscuring color how does one distinguish them?

Oh, sorry, I thought it was always black. You're saying we can't even tell what was covered up? Then, no, I don't think that's possible. Even if the error correction stuff I wrote up there was wrong (it is, working with the assumptions I had at the time), it's a rather moot point if this is the case.

In order to still be distinguishable, you'd have to have most patterns be "invalid", with valid patterns only occuring when you change over 50% of the area, otherwise you could obscure the image in that <50% space to represent a different valid image. Even if you do that, though, it only lets you determine if it has been obscured, and wouldn't let you determine what the original data was, since with 50% of the image changed, you don't have a majority of the data agreeing with each other, so you can't figure out what to trust.

I'm really not seeing how this could be possible. Is there any reason you might think this would be possible?

[eriador]

Nope. I agree with you.

[Slim]

Reading your topic, I was thinking of something. A guy who works for the government talked to our Software Engineering class a while back. One of the things he mentioned is the video feed from unmanned aircraft in enemy territory. There is bound to be errors -- a lot of them. However, typical streaming video will pause when it sees it has an error, and won't play until it has (or thinks it has) 100% accuracy.

This is bad.

The military decided that it would be better to sacrifice accuracy to have a constantly streaming video. Even if that means only 10% accuracy, but at least you have something. That correlates to your problem: can someone tell what something is if 50% is altered? Maybe not, but in my case it is video as opposed to just an image, so it is always changing, and the portion that is inaccurate would always be changing. The human brain is pretty smart and can likely figure out what is going on. But as far as an algorithm to determine what the altered portions actually are in an image or video, I doubt one exists.

[KennEnder]

The human brain is pretty smart and can likely figure out what is going on.

I would agree with that. I remember watching a lot of "snowy" TV as a kid, and even though the signal was really bad, we could just make out enough to know what it was and even enjoy it! There were times when you would only catch glimpses of the action, but it was enough to follow along.

But could we teach that to a computer? Maybe not anytime real soon.

[zeroguy]

The human brain is pretty smart and can likely figure out what is going on. But as far as an algorithm to determine what the altered portions actually are in an image or video, I doubt one exists.

I don't know; this seems like it could be doable, if not already done. There are techniques to filter out audio noise at least, why not video? Since noise from transmission errors would theoretically be similar, you could train it to find noise.

The difference between that and eri's problem is that static noise, while theoretically could be anything, in practice tends to be recognizable. So, we're assuming someone hasn't deliberately tampered with it.

[Bean_wannabe]

And static noise would not often get rid of a whole 50% of a message

[Dr. Mobius]

The human brain is pretty smart and can likely figure out what is going on.

I would agree with that. I remember watching a lot of "snowy" TV as a kid, and even though the signal was really bad, we could just make out enough to know what it was and even enjoy it! There were times when you would only catch glimpses of the action, but it was enough to follow along.

Yeah, the scrambled porn channels were pretty awesome back before the internet made them obsolete.

[KennEnder]

I know this isn't the same thing, but if you haven't seen it before, it's pretty incredible! The human brain can make sense of pretty random things; read this for example: (I've read this before, but got this copy from here)

Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.


as for this

And static noise would not often get rid of a whole 50% of a message

No offense, but that's HOGWASH. Static noise can and DOES wipe out every signal we generate, given enough distance or interference sources, so there must be quite a few portions that have lost more than 50%. Ever listen to a radio as you leave the city? Worse and worse until finally it's gone! Old analog signals for TV (probably where the term "white noise" originated) and radio could get pretty washed out - far worse than 50%, I'm sure, but since tuning wasn't electronic, it didn't depend on strength or coherence to "lock it in" or anything, only knowing where the signal was supposed to be. (Note: new TV's are "smart" and give you the "blue screen of death" if the signal is not good enough, but not the TVs of old!)

[Grignr]

Grignr?

[Bean_wannabe]

Sorry - what I meant to say was static noise would not often get rid of 50% of the message and us still be able to understand it - more than about 40% radio interference and you give up and switch it off

[KennEnder]

Sorry - what I meant to say was static noise would not often get rid of 50% of the message and us still be able to understand it - more than about 40% radio interference and you give up and switch it off

That may be true enough... I have no idea at what point, scientifically, it becomes incomprehensible. That would be interesting to learn! At what point does it become a chore to listen to, and at what point does it become completely hopeless? Anyone have some info on that... or perhaps we've strayed too far from our original Nerdsnipe?

[Bean_wannabe]

The title is plural

[eriador]

Hey... keep going. This is fascinating. I'll chip in if I have something to say.

[KennEnder]

I'm going to keep digging, but this is my initial attempt at looking for an answer.

A student with normal hearing needs an SNR of only about 10 dB for good comprehension.

I got that from here.

It doesn't really answer the question, but it is a starting point.

[zeroguy]

Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

Fehtrur rcraeseh has denimreted taht if you lvaee the fsrit and lsat lrettes in pcale, but rsrevee the rset of the lrettes, it bemoces mcuh mroe dluciffit to raed.

Edit: also: http://www.mrc-cbu.cam.ac.uk/~mattd/Cmabrigde/

I'm going to keep digging, but this is my initial attempt at looking for an answer.

A student with normal hearing needs an SNR of only about 10 dB for good comprehension.

I got that from here.

It doesn't really answer the question, but it is a starting point.

Well, we may not find an answer, because losing 50% of an audio signal doesn't seem to make a lot of sense when I thought about it for a little bit. In an analog audio signal, you just add frequencies to the waveform for noise; you never really "lose" the original data. How do you get to 50%?

[Bean_wannabe]

Sorry - what's SNR?

[KennEnder]

SNR = Signal to Noise Ratio.

And when the SNR is 0 db (decibels), half the signal is noise and half is the audio signal you want... that would be 50%.

And from what I have been able to glean, 50% is not really a problem for us to understand (although, like you said, the actual signal is still there, it's more a matter of filtering, I guess). In fact, what I've read indicates that we might be able to understand stuff that's as low as -15 db... which is a LOT less than 50%!