Nerdsnipes

Talk about anything under the sun or stars - but keep it civil. This is where we really get to know each other. Everyone is welcome, and invited!
eriador
KillEvilBanned
Posts: 2512
Joined: Sat Oct 21, 2006 4:02 pm
Location: North Plains, OR (read Portland)

Nerdsnipes

Postby eriador » Sun Mar 30, 2008 1:34 pm

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
Commander
Commander
Posts: 2741
Joined: Wed Sep 27, 2006 4:29 pm
Title: 01111010 01100111
First Joined: 0- 8-2001
Location: Where you least expect me.
Contact:

Postby zeroguy » Mon Mar 31, 2008 3:10 am

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.
Proud member of the Canadian Alliance.

dgf hhw

eriador
KillEvilBanned
Posts: 2512
Joined: Sat Oct 21, 2006 4:02 pm
Location: North Plains, OR (read Portland)

Postby eriador » Mon Mar 31, 2008 9:08 am

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
Soldier
Soldier
Posts: 75
Joined: Sun Mar 23, 2008 12:00 pm
Location: underground

Postby thatguy1944 » Mon Mar 31, 2008 11:22 am

are we talking about computer based information or actual real life goodness??
Seriously... just say ih (internal ha) from now on

because it never really is a laugh out loud...

Image

eriador
KillEvilBanned
Posts: 2512
Joined: Sat Oct 21, 2006 4:02 pm
Location: North Plains, OR (read Portland)

Postby eriador » Mon Mar 31, 2008 1:02 pm

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

KennEnder
Toon Leader
Toon Leader
Posts: 764
Joined: Sat Sep 30, 2006 8:21 pm
Title: Secret Agent Man
First Joined: 0- 0-2000
Location: USA

Postby KennEnder » Mon Mar 31, 2008 2:13 pm

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.
Share this dragon - If you do - Lucky end - For them and you! Petra

Eaquae Legit
Speaker for the Dead
Speaker for the Dead
Posts: 5185
Joined: Tue Sep 26, 2006 6:30 pm
Title: Age quod agis
First Joined: 04 Feb 2002
Location: ^ Geez, read the sign.

Postby Eaquae Legit » Mon Mar 31, 2008 2:47 pm

I don't need sniping. Just make it a starry night and I'll walk into trees all by myself!
"Only for today, I will devote 10 minutes of my time to some good reading, remembering that just as food is necessary to the life of the body, so good reading is necessary to the life of the soul." -- Pope John XXIII

eriador
KillEvilBanned
Posts: 2512
Joined: Sat Oct 21, 2006 4:02 pm
Location: North Plains, OR (read Portland)

Postby eriador » Mon Mar 31, 2008 3:12 pm

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
Toon Leader
Toon Leader
Posts: 764
Joined: Sat Sep 30, 2006 8:21 pm
Title: Secret Agent Man
First Joined: 0- 0-2000
Location: USA

Postby KennEnder » Mon Mar 31, 2008 5:25 pm

True enough... I guess I wasn't thinking of the "targeted" attack as such.
Share this dragon - If you do - Lucky end - For them and you! Petra

zeroguy
Commander
Commander
Posts: 2741
Joined: Wed Sep 27, 2006 4:29 pm
Title: 01111010 01100111
First Joined: 0- 8-2001
Location: Where you least expect me.
Contact:

Postby zeroguy » Tue Apr 01, 2008 3:17 am

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?
Proud member of the Canadian Alliance.

dgf hhw

eriador
KillEvilBanned
Posts: 2512
Joined: Sat Oct 21, 2006 4:02 pm
Location: North Plains, OR (read Portland)

Postby eriador » Tue Apr 01, 2008 9:17 am

Nope. I agree with you.

Slim
Soldier
Soldier
Posts: 278
Joined: Thu Oct 05, 2006 6:25 pm
Title: Peacocks can't Lurk
Location: Mutter's Spiral

Postby Slim » Wed Apr 02, 2008 9:30 am

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.
A signature so short, it's
Slim

KennEnder
Toon Leader
Toon Leader
Posts: 764
Joined: Sat Sep 30, 2006 8:21 pm
Title: Secret Agent Man
First Joined: 0- 0-2000
Location: USA

Postby KennEnder » Wed Apr 02, 2008 12:38 pm

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.
Share this dragon - If you do - Lucky end - For them and you! Petra

zeroguy
Commander
Commander
Posts: 2741
Joined: Wed Sep 27, 2006 4:29 pm
Title: 01111010 01100111
First Joined: 0- 8-2001
Location: Where you least expect me.
Contact:

Postby zeroguy » Thu Apr 03, 2008 2:55 am

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.
Proud member of the Canadian Alliance.

dgf hhw

User avatar
Bean_wannabe
Soldier
Soldier
Posts: 485
Joined: Thu Nov 08, 2007 11:30 am
Title: I spy with my Fishy Eye
First Joined: 08 Nov 2007
Location: England

Postby Bean_wannabe » Thu Apr 03, 2008 10:29 am

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

Dr. Mobius
Speaker for the Dead
Speaker for the Dead
Posts: 2539
Joined: Thu Sep 28, 2006 12:11 pm
Title: Stayin' Alive
First Joined: 17 Aug 2002
Location: Evansville, IN

Postby Dr. Mobius » Thu Apr 03, 2008 12:27 pm

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.
The enemy's fly is down.
Image

KennEnder
Toon Leader
Toon Leader
Posts: 764
Joined: Sat Sep 30, 2006 8:21 pm
Title: Secret Agent Man
First Joined: 0- 0-2000
Location: USA

Postby KennEnder » Thu Apr 03, 2008 1:16 pm

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!)
Share this dragon - If you do - Lucky end - For them and you! Petra

User avatar
Grignr
Launchie
Launchie
Posts: 6
Joined: Thu Sep 28, 2006 2:57 am
Location: Kilimanjaro

Postby Grignr » Thu Apr 03, 2008 1:40 pm

Grignr?

User avatar
Bean_wannabe
Soldier
Soldier
Posts: 485
Joined: Thu Nov 08, 2007 11:30 am
Title: I spy with my Fishy Eye
First Joined: 08 Nov 2007
Location: England

Postby Bean_wannabe » Thu Apr 03, 2008 2:03 pm

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
Toon Leader
Toon Leader
Posts: 764
Joined: Sat Sep 30, 2006 8:21 pm
Title: Secret Agent Man
First Joined: 0- 0-2000
Location: USA

Postby KennEnder » Thu Apr 03, 2008 2:24 pm

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?
Share this dragon - If you do - Lucky end - For them and you! Petra

User avatar
Bean_wannabe
Soldier
Soldier
Posts: 485
Joined: Thu Nov 08, 2007 11:30 am
Title: I spy with my Fishy Eye
First Joined: 08 Nov 2007
Location: England

Postby Bean_wannabe » Thu Apr 03, 2008 2:44 pm

The title is plural

eriador
KillEvilBanned
Posts: 2512
Joined: Sat Oct 21, 2006 4:02 pm
Location: North Plains, OR (read Portland)

Postby eriador » Thu Apr 03, 2008 3:06 pm

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

KennEnder
Toon Leader
Toon Leader
Posts: 764
Joined: Sat Sep 30, 2006 8:21 pm
Title: Secret Agent Man
First Joined: 0- 0-2000
Location: USA

Postby KennEnder » Thu Apr 03, 2008 3:38 pm

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.
Share this dragon - If you do - Lucky end - For them and you! Petra

zeroguy
Commander
Commander
Posts: 2741
Joined: Wed Sep 27, 2006 4:29 pm
Title: 01111010 01100111
First Joined: 0- 8-2001
Location: Where you least expect me.
Contact:

Postby zeroguy » Fri Apr 04, 2008 3:19 am

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%?
Proud member of the Canadian Alliance.

dgf hhw

User avatar
Bean_wannabe
Soldier
Soldier
Posts: 485
Joined: Thu Nov 08, 2007 11:30 am
Title: I spy with my Fishy Eye
First Joined: 08 Nov 2007
Location: England

Postby Bean_wannabe » Fri Apr 04, 2008 10:32 am

Sorry - what's SNR?

KennEnder
Toon Leader
Toon Leader
Posts: 764
Joined: Sat Sep 30, 2006 8:21 pm
Title: Secret Agent Man
First Joined: 0- 0-2000
Location: USA

Postby KennEnder » Fri Apr 04, 2008 12:13 pm

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%!
Share this dragon - If you do - Lucky end - For them and you! Petra


Return to “Milagre Town Square”

Who is online

Users browsing this forum: No registered users and 2 guests