[Liquid!]

Please don't kill me for starting a new thread with this one. This may really need to be in random musings, however since the initial post was here I wanted to post this here. Either way, please don't flame me...

There was a guy that asked if it was possible to enhance images the way we've seen in Blade Runner. Thus, asking if you could enhance bitmap pictures back to a higher resolution, and with it reclaiming some of the lost picture information.

I actually think, that with enough horsepower, it would be possible to get a best guess picture, that would be able to partially reconstruct the low-resolution pic at a surprising level of accuracy. Before, you tell me to go take a hike. Stay with me for a sec.



(A)4 pixels are down-rezed to one pixel. Effectively cutting the picture in half, and losing the information of 4 distinct pixels of color, that are averaged into one. While using one pixel it is not possible to mathematically trace back to the 4 original pixels, it is possible to determine what combinations of 4 pixels were capable of producing the aforementioned one pixel, and thus producing a mathematical "set" of possibilities. To add to that problem (B), that even if you found the exact match you'd have to find their orientation. However, writing a very sophisticated algorithm that would allow the computer to "see" would allow to narrow down likely suspects from the aforementioned set. How? Write an algorithm that senses edge data, and constructs the most logical outlines of shapes, patterns, and edges, and thus aligns, and chooses the mostl likely 4 pixel combinations to compose the final picture. Now, while this sounds a bit futuristic, keep in mind that if the computer is given more than 4 pixels to analyze and thus has more data to establish patterns with the picture it becomes more probable that the computer will 'guess' correctly. I think it would be already possible given enough horsepower.


On another note, keep in mind that the CIA already posseses software that is able to capture "faces" from off-angles within a regular picture. In essence having taught the computer to "recognize" faces among other visual data. Quite a feat. Not only that, but then to extrapolate the measurements of the facial features and have it cross-referenced against a database of known offenders...

Like I have enough time for this...
-c

[CapnPyro]

Ack!@#

i have a bratwurst lodged in my throat now because of this post. i'd explain but it would take to long..

what your talking about certainly sounds possible, it'd help if there was a better picture format then jpeg or gif, something finer and higher quality. i guess with more dpi it can get to any quality, but im sure there is always something better

itll be intersting to read what the people who deal with this stuff thoughts are on it

-Capn

[Leon]

[ July 19, 2002: Message edited by: Leon ]

[Skeezer]

You know, this is the same kind of stuff I think about when I'm on the pot. hehe.

Glad to know someone else out there wastes their time thinking about theories and possibilities.

I think your theory is very plausible. Maybe you should go to the patents office just in case hehe.

-Skeez

[Matt Elder]

bit of an unusal post for you I would have thought. I think going from one colour back to four can only happen when the computer is 'taught' or given a set of rules. Unfortunately this doesn't always work well. Years ago I remember seeing a program on TV where they were trying to teach a computer how to recognise armoured tanks from a flat photograph. The results were quite interesting in the computer was able to do it quite well.

Then they gave it a field test using a live camera and the computer just couldn't do it. The reason was the camera was different and the photos came out slightly darker. The computer had only been 'trained' on lighter photos. It was looking for a pattern.

Thus getting back to your original point, the computer in going from one colour to 4 will be looking for some sort of pattern that it has already seen. If it hasn't seen it, it probably can't do it or do it well enough to justify it.

Also, in going from 1 colour to 4, made up of 4 values, there are millions of different combinations.

I saw a program on the national geographic channel yesterday about security survilance cameras. They did some tests and found that even to the human eye, if the lighting was changed slightly, people generally wouldn't be able to recognise a friend's face. The only way they could recognise someone was by their walking style, clothing, body shape ie other patterns.

If you give a computer enough rules or can teach it how to learn, maybe it could 'enhance' images but I'd have my reservations about it.

------------------
See ya on da flip side
Matt
http://www.mattelder.com

[Liquid!]

SKEEZ - Yup. I do my best work on the can...

MATT: Hate to think that there is a "usual" post for myself. Hope that I continue to "dissappoint" you...

While the possibilities grow exponentially. I would guess to about 8 million per color channel in a CMYK scenario, that is far from a large number, especially if you consider that those are ALL possible combinations, WITHOUT having the computer analyze what is LIKELY to be the best scenario, AND not to mention that the human eye can't usefully differentiate a large percentage of the variations mentioned above. Let me try to make my previous post a bit clearer.




I'll try to run the numbers when I have a bit more time on my hands.

Hope I made myself a bit clearer...

[Matt Elder]

yeah I knew when I put this isn't your usual type of post that had come out wrong. There is a time to quit and count your loses so I'm not going to even try explaining that one.

Since I made that post I've seen the other thread so it makes a bit more sense now. When I came to the forum tonight (haven't been since this moring), yours was at the top with a 0 response so I replied.

Even when you have said, "here is an edge" that is a pattern that you've recognised. You know generally that at the back of a car, in the middle is a 'license' plate so you are searching for edges. You have been 'programmed' with this knowledge. You could do the same with a computer, but what if the licence plate is down in the bottom corner. Unless you tell a computer that is a possible solution, it won't be able to find it.

If you had greyscale colours, the numbers are dramatically reduced combinations. But then again, what if it is like a New York Licence plate (I'm stretching my memory from when I was in the states in '88) with the red, white and blue colours. Again a matter of programming in the different colour combinations. Otherwise the possible combinations are over 1e100. Might not seem like a lot but even with todays computers, it would take 2 years to do 1e80 calculations (I think that was the number when I did level 3 uni maths last year).



------------------
See ya on da flip side
Matt
http://www.mattelder.com

[Nex]

I have to agree to matt's comments.
the combinations are HUGE!

*Math ahead*

lets say you have 4 virtual pixels (vp) made up of CMYK that make your pixel. If the 4 vp's would be a definitive color and you would just interchage them on the 4 places then you come up with 16 combinations.
But the 4 vp's can have more than just one color set.

Lets say we have Cyan:20% in the pixel

then the vp's can have:
c1: 20 c2: 20 c3: 20 c4:20 or
c1: 10 c2: 10 c3: 30 c4:30
c1: 0 c2: 0 c3: 40 c4:40
c1: 80 c2: 0 c3: 0 c4:0
c1: 22 c2: 18 c3: 20 c4:20
.. and so on

all those make C:20% there are a LOT of combinations in there.

Then you have those combinations for every color cymk

*/math *

you come to horrendous numbers of combinations (of course a lot of those combinations would look pretty much the same, but that still leaves a huge number of possible combinations)

I think however that it is possible (with a lot of AI programming) to make the computer recognize some patterns and associate shapes to it, but why bother the computer with that when we are WAY better in those things.

I'd say that if the computer can read the licence plate on such a picture then you can read it yourself normally too.

the programs that actually DO this sharpen things for surveilance etc. are working on photos as far as I know (or maybe store it as a metaformat made of vectors and voxels?) not on such pixelated pictures.

Well thats my 0,0223 cents

Cya

------------------
- Nex

http://on.to/nex

[This message has been edited by Nex (edited November 25, 2000).]

[Frost]

I've mentioned this before in the other thread, but yes it is possible to get some kind of results, especially with larger forms, being to create a 2D-vector based equivalent of a bitmap by analysing antialising patterns, curve analysis, etc, which S-Spline (thanks Assa!) does to a certain degree.

In the picture of the license plate, it is impossible to get numbers/letters off it, no matter the horsepower, etc. It would generate too many possible combinations, and not only do these pixel patterns have to make sense within themselves, but also with neighbouring pixel patterns. Basically, if our minds cannot interpret it, neither can the computer... especially since every color channel is at best 8-bit precise in most formats which is insufficient... jpegs being the worse in that pixel color precision is trashed to hell based on the level of precision it was saved as, not to mention GIF and other 256-color or less paletted colors that destroy most colors. Any type of dithering pattern would be mistakenly taken as details or anything of the sort.

It is somehwat possible (as mentionned above with the CIA program) to get a 3D-shape from a bitmap image on specific things such as faces (replicating left/right sides to fill in the occlusion gaps), etc.

Anyway, if we can't see it ourselves, computers can't for sure -- that is a certainty.

[This message has been edited by Frost (edited November 25, 2000).]

[AndreCorrea]

I remenber seeing a program on the discovery channel about cars, and they showed "the technology of the future, now!" or whatever. Anyways they had cars that you drove with joysticks and cars that had computers control the distance from car to car. But the one that I found interesting and related to this post was the self driving car.

Basically what it did was look for the center lines in the road and the curb. The computer made an outline of the curb and lines and calculated at what speed turns had to be taken and how far from the curb they had to be. THe pictures were all in black and white, so if your trying to find a license plate number all you really need is a black and white picture, and then I'm sure some program could be made that finds edges. LIke the one that drives the car.

As for the CIA thing recognizing people faces I think its based on distances from nose to mouth and ear to neckline, eyes to eyes, nose to eyes, etc.. They just find an algorithm for your face, based on the distances of your features. That could work.

[This message has been edited by AndreCorrea (edited November 25, 2000).]

[FatPenguin]

A couple of people brought up the idea of using the computer to find edges in the image. The easiest way to do this would be to define an 'edge' as a significant change in value over a distance. I'm sure this would be easy enough to do with a cartoon character, but in real life or a photograph you run into some pretty big problems.




Tell any 5 year old to trace this car, they could give you a decent outline, with the windows drawn in and everything.

But look at the bottom of the car where it meets the shadow. There is no line ther at all. Look at the rear windshield, and you see a definate 'line' going diagonally across.


The only way a human would be able to explain his choice in outlines would be because he recognized it as a car, and the wheels 'should obvously look like that' or 'that's clearly just a reflection on the glass'.

You would have made some fairly amazing assumtions without thinking about it. Try getting a computer to assume this is a car, and you have a near impossible task on your hands.

[Visigoth]

Liquid;

Sound in theory, but ultimately futile in application. We used a very similar program (but for an entirely different purpose) at JPL in the imaging lab. Regarding what was said in the previous thread on this topic regarding using 4 lower resolution images to create a higher resolution image; Most of it is artistic liscense. Gratuitous use of a clone tool, and many translucent brushes, gradually painting in the details that were not there in the other images...Pretty much how it works. =| The images that come back from the Mars GVS are such low quality, it's amazing that they glean that much information [HA!] out of them.

~{V}~
P.S. I'll tell you what I worked on, in 2002 and 2020 when my NDA's wear off. ;P~

------------------
Your car is a fiberglass penis extension.

[Liquid!]

For those of you that are interested in some of the combinations. I hope I haven't made any mistakes here, but I think its a pretty fair approximation.
http://www.go-liquid.com/forum/math/mat.jpg
http://www.go-liquid.com/forum/math/mat2.jpg

NEX: The point is that at a certain level you may not be left with anything but a pixelated image. Such as the case in a license plate of a suspect taken by a security camera. I agree that the combinations are somewhat large, however not impossible, and that I think is the operative word. Actually I think its very much within the realm of possibility. Sophisticated, but possible.

FROST: As you can see there aren't that many combinations. While I think tracing the image with a 2d vector is part of the analysis, I think given enough horsepower you could present your human viewer with some interesting possibilities.

Keep in mind, that we are not talking about enhancing an image per se, but about the RE-CONSTRUCTION of said image... much more interesting if you ask me. I wouldn't want to entertain gif/jpgs, etc for the sake of this discussion, since I think its reasonable to assume that we are starting with a 'true' low-rez pic, rather than making this more difficult by introducing compression loss.

As far as the face recognition is concerned it is not somewhat possible. It is being done today. Trust me I was no less astonished to hear this than you might be.

ANDRE- that is close to the principle being used.

FAT - You're only interested in value changes, you do not need to have the computer trace a car. Also keep in mind that the computer can distinguish by a much larger range of colors and subtleties that the human eye cannot perceive, thus being able to run progressive runs to analyze pattern distinctions.

VISI: Analyzing rock formations might be quite a bit more difficult due to the somewhat randomness associated with it. However, even within those guidelines I think it would be possible to gain useful re-constructions of low resolution images.

Phew. Sorry to sound this dry about it.

[This message has been edited by Liquid! (edited November 25, 2000).]

[This message has been edited by Liquid! (edited November 25, 2000).]

[Fruitbat]

Liquid,
That is a very nice start to the algorithm and with a few modifications we could make it VERY manageable.

If you just do it by guess work the permiutaions are huge but you can throw out so many false answers straight up.
For starters you can force the computer to pick only colors that are inside the original color palette of the picture itself.
then you can start to look at the shapes as well. Obviously a straight line will tend to continue straight, ect. With a human to guide the process this is definatly not Buck Rogers technology. I don't need to perfect the algorithm to show that is do-able, but there are tons more refinements that could be made to make it work more efficeintly.

I was a mathmatics Major in college, so I do have some understanding of how computers solve problems.

The very fact that I can think of several possible algothms to enhance a digtal image combined with the fact that this technology would be extreamly useful to: CIA, Law Enforcement, NSA, FBI, Spy Satellites, Scanners, and digital camera makers, data compression, and almost every major visual technology company out there...almost garentees that there is either a working program out there now or else there are people creating it right now.

What algoritm does a scanner use to enhance the resolution beyond what it can actually read? (I'm asking because I don't kow but it seems related.)

Consider how JPG compression works:
We take larger blocks of color and average them out in a way that makes them blend together naturally. A low res image is essencially a blocks of color that have yet to be averaged out. I am not suggesting JPG compression algorithms are the answer to reading the lisence plate, (I realize the process is done in reverse) but rather showing that we already use simalar processes in everyday technology.

[Fruitbat]

Oh I forgot.
F.P.
The edge problem is ALREADY SOLVED (though not perfectly of course). Photoshop's magnetic lasso is usually pretty accurate for me, even in dark problem areas.

[Muzman]

The point was, I think, that if there is no differentiation in colour data then a computer cannot even guess the outline without first being trained in car form. Even if the contrast still exists at a data level, texture from the ground and the photograin itself will make it impossible for the computer to tell what's what.
But, I guess it would be enough to clue a human in on what it was. I seem to remember something about that face recognition software working in a simillar way; it's all about collecting the vague possibiities and showing them to a person for the final judgement.

[Liquid!]

FRUITBAT: I wish I had the time to do an algorhithm for this. I can't help but to think that this is quite possible. I'm sure that is just my own ignorance coming to light regarding the matter.

Argh. Must invent the 36 hour day.
-c

[maxwell]

This isn't exactly what this topic is about, but it seems close enough to warrant mentioning.

There's a really cool paper from SIGGRAPH 2000 about computerized "inpainting" -- automatically reconstructing parts of an image which are obscured or damaged.

You can see an example in this animation



You can find out more at the main site:
http://www.ee.umn.edu/users/marcelo/restoration.html

Max

[Matt Elder]

Liquid! I had a look at your 'math' that you'd done on the subject and at first glance (I haven't thought about it too deeply), it seems OK. My point was more the fact that Cyan was one of 4 'components'. Thus now if you take Cyan with 94million combinations, interweave that will the other 3 at 94 million combinations, this number is all of a sudden VERY large. Even with 'smart' techniques to eliminate some of these combinations (even if you could get rid of half), when you are talking numbers with 100 zeros, the order of magnitude becomes important (ie decreasing the combinations by half will still mean that you have a number with 100 zeros - for example). Maybe I've missed the point.

Interesting that someone mentioned the lasso tool in PhotoShop. The thing with this is that you'd determine the rough proximity of where the edge is in the first place, something I thought this post was examining determining from scratch.

------------------
See ya on da flip side
Matt
http://www.mattelder.com

[Liquid!]

MATT: On the second sheet I show that its actually 5,997,600 at Cyan alone [at 100% ink], not 94million. 94 Million is at 100 permutations, NOT at how many permutations it takes to ADD to 100. Sorry about the confusion.

Now 5,997,600 combinations are still fairly large. And theoretically you could argue that you'd have to multiply this number by four. However, it isn't that easy. First off the smaller the number the less possibilities exist. The 5,997,600 is assuming the absolute maximum of 100 inklimit, which when considered with the other four would quickly have to be topped off at BLACK since most of the higher ink limits display as pure black anyhow. This little tidbit already decreases the numbers drastically. All of this still before any "intelligent" analysis of the picture has been done to eliminate further possiblities...

I am fairly confident with the right supporting algorithms, edge analysis, color frequency and probability, and limitation of colors to only the spectrum the human eye perceives you'd get very surprising results.

Just my thinking...

[EDIT]

MAX: Thanks for the Article. That's pretty damn cool and is definitively related! I think something similar would/could be used for reconstruction, however I'm going to digest the article first..

-c


[This message has been edited by Liquid! (edited November 27, 2000).]

[Matt Elder]

Oh that does it. You've challenged me and I'm going to work this one out (when I get some time that is)

------------------
See ya on da flip side
Matt
http://www.mattelder.com

[Liquid!]

MATT- Sounds great!

I'm just a lowly color-monkey anyhoo!

-c

[Matt Elder]

OK. I guess the first thing is whether or not I understand the CMYK as a 'negative' process. I understand that RGB is 'additive' (like computer monitors etc). I went and spoke to one of my maths professors at uni and he came up with 8 million combinations. (using integer values only ie 1%, 2%, 3% but not 1.5% or anything that wasn't a whole number).

I was just wondering if you could explain and direct me to a good explaination (on the web) of how the 'negative' colour process works as I'm just a 'lowly' engineer and all this art stuff is way over my head

------------------
See ya on da flip side
Matt
http://www.mattelder.com

[Liquid!]

quote:

---

Originally posted by Matt Elder:
OK. I guess the first thing is whether or not I understand the CMYK as a 'negative' process. I understand that RGB is 'additive' (like computer monitors etc). I went and spoke to one of my maths professors at uni and he came up with 8 million combinations. (using integer values only ie 1%, 2%, 3% but not 1.5% or anything that wasn't a whole number).

I was just wondering if you could explain and direct me to a good explaination (on the web) of how the 'negative' colour process works as I'm just a 'lowly' engineer and all this art stuff is way over my head

---

I don't think its really of any importance. RGB has a higher Gamut and thus more potential possibilities. I would keep it simple for now. Also additive/subtractive display is just that a means to display colors print vs. CRT.

Either way while my equations for permutations are accurate I found a fatal flaw. I mistakenly assumed two digit addition for the averaging. It would have to be 4. The main problem for the calculation then becomes - How many possible ways can you add x using four variables where is x <=400, and no variable is > 100?

I.E. How many different ways can you add up to 400 using four variables each no larger than 100 (and thus an end target variable of 100% [400/4]). Answer = 1. [C100M100Y100K100].

However, this becomes a bit more perplexing if you ask how many different ways can you add up to 200 [thus a end target pixel value of 50% [200/4]]? That gets tricky.

Anyone? Anyone? Bueller?

Only way I can think of is to write a quicky counter program which I can't do since I don't have a compiler installed.


While I'm pretty damn interested in the actual answer to this, I think this post went waaaaaay off-topic, and is hardly considered Digital Art, plus very much of a "specialized" post to say the least. So I will stop posting to this silly thread, before someone decides to put me into the "Idiots that post here" thread, if I haven't made the cut already...

Matt, I would still love to get the idea from your match prof. Let me know if you have it.

Thanks.


[This message has been edited by Liquid! (edited November 28, 2000).]

[sacrelicious]

What the hell are you doing up this late?

------------------
mmm... sacrelicious

[Matt Elder]

hmmm... still a bit confused on defining the problem. Aren't we just looking for the number of different possible colour combinations arising from 4 parameters, or looking for the total number of different combinations that add to a value? ie

there will only be:

4 combinations that can add to 1
x combinations that can add to 2
xx combinations that can add to 3
xxx combinations that can add to 4

etc (note each x represents the fact that the combinations are growing)

Thus the growth is going to be an exponential function that is going to grow very quickly. This is because each time you want to add to one number higher, you introduce an additional number into the value set (or is this jibberish to you?).

I'm sure you've heard the story:
Work for me today - I give you 1cent
Work for me the day after - I double your pay
Work for me the day after that - I double your pay
etc.
I'll do this for 30 days, will you take it?

If I'm intepreting it correctly, the question that you've posed is effectively similar to this, only much more suped up and has a limit of 400

K is black right?! So if K =100%, doesn't matter what the other 3 are, it will always be black. This reduces the calculation significantly and was factored into that figure of 8 million. But this is just for integer values and not 1.1%, 1.2%, 1.3% etc. If you could have any possible fraction of a percent, the answer is easy - there are infinite combinations. What is the threshold to the human eye?

I guess there are two questions:

1) How does CMYK work? Can you have any combination of CMYK from 0,0,0,0 - 400,400,400,400 that will each create a unique colour (barring the black 'quirk')

2) what specifically is the question that you are asking? How many combinations of colour are possible? How many differeent ways can you make 1 combination (then sum all or these up) or something different?

P.S. Maybe you should close this thread and start one in Random Musings'

P.S.S - if you do, please make a comment here
------------------
See ya on da flip side
Matt
http://www.mattelder.com

[This message has been edited by Matt Elder (edited November 28, 2000).]

[This message has been edited by Matt Elder (edited November 28, 2000).]

[mantis]

HOLY MONKEYS! Liquid! are you from the actual liquid.com coloring team or are you just bsing? I always wanted to ask the liquid guys a billion things on their coloring effects but they never respond to my emails.

Your work on "battle chasers" was amazing, even though the inking sucked.

sorry for being off-topic but this is too good. . .

------------------
I killed the king of deceit, wake me up in anarchy. I made a garden out of blood, not superiority.
. Kein Mitleid F�r Die Mehrheit .

Arpan . B
[email protected]
currently down. . .

[Ferox]

This is a late reply, so I don't know if anyone will see it...

Anyways, you guys should look into Fractal Image compression. Fractal image compression represents an image in terms of affline transformations of itself; this representation is _resolution independent_! That means a properly fractally compressed image can be decoded to any resolution, and detail as encoded will be "filled in".

Of course, this isn't perfect, and won't produce any miracles... but it actually works fairly well (and is very general!). The Microsoft Encarta encyclopedia utilizes Fractal image compression, I believe, when magnifying its images.

I don't have a URL on hand, but it should be easy to find web resources on fractal image compression.

[synj]

ouch, my head guys. you're hurting my head.

if susie travels by car at 50 mph and the train is going at 70mph and they both want to reach point B but the train takes a 21.24 minute break..

-synj www.synj.net

[Ben Barker]

I think it would just be cheaper and better for the CIA to get cutting edge, higher res film and cameras and crap on their spy satellites. It's already pretty mind blowing. Couldn't they read a newspaper from space like, 8 years ago? Imagine what they can do now.
You can guess what the data used to be, but the data is gone for good. You might be able to do this to some degree if a computer worked with a human who gave it hints. You might be able to write one just for liscense plates that would be decent. But there is no way to reconstruct what has been lost. Bicubic upsampling, heh. That would rock.