L1-minimization: Possible high-quality image-reconstruction?

[RobbieThe1st]

A couple months ago, I got the February, 2010 edition of Wired magazine. Amongst the other articles, I found one very interesting one, about the L1-minimization algorithm. You can read the article on line Here.
Now, I'm sure it isn't perfect, and can't create something from nothing, but if this algorithm can do what it appears, it could mean essentially lossless, if not "improved"-higher resolution images from low-quality source(say old DMFA archives).

As it is, the current best method for 'improving' artwork I have seen is to use Vectorization software, but such software isn't perfect and does lose detail, though it can do a pretty nice job of improving quality.

Now, when I googled up this algorithm, I found a fair bit of information... but I don't understand one bit of it. I'm -not- a mathematics professor. It does look interesting though.

Any thoughts?

-Robbie

[Turnsky]

the problem being, that programs that would utilise such things would be -expensive-

[GabrielsThoughts]

I always wondered how those pictures in  crime drama shows went from "here's a undefined mosaic block" to OMG! HD qaulity awesome."   I somehow assumed it had something to do with make believe NASA technology or something to the affect of it hadn't been invented yet. Now that it has....I'm eagerly anticipating the moment this becomes available to the public. I'm sure the Pro photographers will whine about it for a while and there'll be a whole "Digital imaging isn't REAL photography" as if it required less skill to shoot an image with a digital camera than a Polaroid or Classic 35 mm. I'm guessing the time taken for processing is more of a skill than taking the actual photograph. 

[RobbieThe1st]

the problem being, that programs that would utilise such things would be -expensive-

Until some darn MIT student goes and makes a GPL version for Linux...

[Keleth]

Sometimes a decent way to do artwork for future resolutions is to make that artwork in Vector based applications.

Example if you put together a piece of artwork in photoshop, you can export it as an AI or a EPS, Both of which are vector based and let's you change the sizing of it without ever losing quality.


Why some people just don't start with that I'll never know o_o

[Merlin]

Vector can be much more time-consuming than just scribbling in photoshop, though. I mean, to export to an illustrator file it's exporting paths, and a lot of people don't use paths in photoshop because it can be kind of annoying.

Plus you can't really use it when all your lines have been scanned, anyway.


I hear the rasterbater program is pretty good at resizing images though, and it's free. Mind you it's generally used for resizing images to absurd sizes, but apparently it works well and is free.


though I might have to look into the vectorising software Robbie posted about, ithat looks awesome.

[Tapewolf]

Why some people just don't start with that I'll never know o_o

I think it's a "one-size-fits-all" problem.  There are lots of scenarios where vectors are best, and lots where they're a really, really bad fit.

Aside from the problem of using a scan as a base, which could be worked around by redrawing it in vectors (I believe Turnsky does or did do that), there's whole classes of effects that can't really be applied to vectors.

Some of those, like motion effects, gaussian blur etc. could be implemented as a step in the rendering chain, but you'd very quickly end up with something that that takes minutes just to redraw the screen and makes editing in realtime impossible, and you'd probably end up with some quite nasty z-order related artifacts.

I haven't used Coreldraw for about 10 years, I can't really afford Illustrator and I haven't got to grips with Inkscape, but is it possible to do this, for example?
1. Draw complex background
2. Draw a circle in the foreground
3. Cut an irregular hole in the circle so that the background shows through

To implement that, you'd either have to make the program deconstruct the circle into some kind of concave polygon - which will make it look pretty bad if the image is rescaled to be larger - or write some kind of rule into the polygon renderer that says "Draw all of it except where it intersects with this other polygon".

Or, say you've drawn a circle and now want to slice a chunk out of it and drag it elsewhere, like a slice that's been moved slightly away from a pie? 
It might be able to do that by deconstructing the thing into a series of arcs, but basically things like this are going to cause some serious headaches in terms of breaking the object geometry down and converting it into something else.  I can easily imagine something like Inkscape just not supporting that so that you have to delete the circle and create two arc objects instead.

Smear effects are also going to be difficult to do.

That aside, a lot of the stuff which Robbie or I would want to resize no longer exists in its original format, so we'd still be stuck with a raster version of it, even if the original was an SVG file or something.

[superluser]

I hear the rasterbater program is pretty good at resizing images though, and it's free. Mind you it's generally used for resizing images to absurd sizes, but apparently it works well and is free.

Rasterbator is a halftoning program.  So long as you don't mind your stuff looking like



when it's close up, it will look fine when you're far enough away.  It's not really a resize algorithm, since you lose a lot of detail.

I haven't used Coreldraw for about 10 years, I can't really afford Illustrator and I haven't got to grips with Inkscape, but is it possible to do this, for example?
1. Draw complex background
2. Draw a circle in the foreground
3. Cut an irregular hole in the circle so that the background shows through

To implement that, you'd either have to make the program deconstruct the circle into some kind of concave polygon - which will make it look pretty bad if the image is rescaled to be larger - or write some kind of rule into the polygon renderer that says "Draw all of it except where it intersects with this other polygon".

Or, say you've drawn a circle and now want to slice a chunk out of it and drag it elsewhere, like a slice that's been moved slightly away from a pie?

Both of these are essentially solved problems (though not necessarily solved in the sense of efficient algorithms) in vector editing software today.  You're looking for things like union, difference, cut apart, and mask in Illustrator or Inkscape.

It does eat up CPU time if you've got a lot of nodes to consider, and the point about blur and smear is well put.  Everything you mentioned is a regular feature of every vector editing program I've used in the past few years (with the possible exception of some features in Scribus), but the blur and smear tools are probably too expensive to use regularly (I don't like their effects, so I rarely use them).

[Tapewolf]

Both of these are essentially solved problems (though not necessarily solved in the sense of efficient algorithms) in vector editing software today.  You're looking for things like union, difference, cut apart, and mask in Illustrator or Inkscape.

Cool.  Like I say, I haven't done any vector stuff myself for about 15 years and I didn't get into it very deeply then anyway.
Out of interest, can they do something like this:

http://www.project-future.org/strip.php?strip=87a

...where the second panel is basically a copy of the first, with the hue shifted in a given polygon, and the entire frame has been bent in a sinusoidal manner?
Again, these would probably have to be done as a postprocess effect, because they are innately raster effects, which would presumably give different results in different packages.  I'll have to look at the SVG format to see what these things are capable of nowadays.

How about pattern tiling of a surface?

http://www.project-future.org/strip.php?strip=98
...the last panel of that one was an interesting challenge to pull off.  If you can have alpha-blended feather-edged polygons, it should be doable.  Otherwise, I suspect you'd be fighting the program a lot.


EDIT:
From what I've seen, most of DMFA would work quite nicely in vectors.  Not that I'm suggesting Mab changes, mind.

[superluser]

Out of interest, can they do something like this:

http://www.project-future.org/strip.php?strip=87a

...where the second panel is basically a copy of the first, with the hue shifted in a given polygon, and the entire frame has been bent in a sinusoidal manner?
Again, these would probably have to be done as a postprocess effect, because they are innately raster effects, which would presumably give different results in different packages.  I'll have to look at the SVG format to see what these things are capable of nowadays.

How about pattern tiling of a surface?

http://www.project-future.org/strip.php?strip=98
...the last panel of that one was an interesting challenge to pull off.  If you can have alpha-blended feather-edged polygons, it should be doable.  Otherwise, I suspect you'd be fighting the program a lot.

Are you dealing with vector art to begin with, or with rasters?  If your workflow takes you from raster to vector and back to raster, you might be better off just sticking with a raster editor in some cases.

I'll deal with the second one first.  It's easy enough to make an opacity mask and use step and repeat to turn that into a pattern.  Inkscape also seems to have opacity masks, but I've never used them.  I wouldn't have any qualms about using a vector editor for that type of raster effect.

The first one is a lot trickier.  I think you can do that in Inkscape with envelope deformation, which probably means you can do the same thing in illustrator.  Changing hues is simply a matter of adding a semi-opaque layer mask with the desired color effect on top.

[Keleth]

http://designrfix.com/inspiration/vector-artwork-50-inspirational-creations

Check out that page, scroll down a little, those are all vector artwork.

Is that pretty enough?

Or, say you've drawn a circle and now want to slice a chunk out of it and drag it elsewhere, like a slice that's been moved slightly away from a pie?  
It might be able to do that by deconstructing the thing into a series of arcs, but basically things like this are going to cause some serious headaches in terms of breaking the object geometry down and converting it into something else.  I can easily imagine something like Inkscape just not supporting that so that you have to delete the circle and create two arc objects instead.

Yes, it's called the "Meld, Weld, Cut Out, Combine" etc tools. At least in Flexisign, but they exist in corel-draw and every other vector program I've played with as well.

I haven't used Coreldraw for about 10 years, I can't really afford Illustrator and I haven't got to grips with Inkscape, but is it possible to do this, for example?
1. Draw complex background
2. Draw a circle in the foreground
3. Cut an irregular hole in the circle so that the background shows through

. . If you mean. . . Layers? Then. . . Uh, Yes.

[Turnsky]

it's actually entirely plausible to do cel shading in illustrator, hell, i did that Daryill commish for tape entirely in illustrator 

[Tapewolf]

Yes, it's called the "Meld, Weld, Cut Out, Combine" etc tools. At least in Flexisign, but they exist in corel-draw and every other vector program I've played with as well.

Right.  After writing that, I figured that a lot of this was probably solvable with something like CSG in 3D modelling.  I wouldn't like to have to implement it myself, though.

Are you dealing with vector art to begin with, or with rasters?  If your workflow takes you from raster to vector and back to raster, you might be better off just sticking with a raster editor in some cases.

For what I'm doing at the moment, the source is always raster, and the end result is also raster.  However it's interesting to learn that most of the techniques I am using at present would be doable in a vector format.  I'm still not convinced it's a universal solution to every artistic problem, though.

it's actually entirely plausible to do cel shading in illustrator, hell, i did that Daryill commish for tape entirely in illustrator  

Yes, and that's why I was hoping to see the file, so I could take it apart and find out how it was made.  It's more complex effects I was skeptical about.

EDIT:

. . If you mean. . . Layers? Then. . . Uh, Yes.

No, I did not.  I was talking about creating a transparent intersection inside a primitive.  Cutting a hole in it, basically.

[Keleth]

Yes, it's called the "Meld, Weld, Cut Out, Combine" etc tools. At least in Flexisign, but they exist in corel-draw and every other vector program I've played with as well.

Right.  After writing that, I figured that a lot of this was probably solvable with something like CSG in 3D modelling.  I wouldn't like to have to implement it myself, though.

. . .What? No. 3D modelling has nothing to do with what I was talking about.

You make a square, you make a circle, you can overlap them and 'weld' them into one solid object.  Or you can 'cut out' the overlap, the not overlap, the difference, etc etc etc.

It has nothing to do with 3D modelling. I have no idea where you're getting that at all.

Those tools, combine, weld, cut out, etc are default tools that have existed for at least 14 years. At -least-. Because that's the year my copy of Corel is from.

No, I did not.  I was talking about creating a transparent intersection inside a primitive.  Cutting a hole in it, basically.

Yes, You can.

[Tapewolf]

It has nothing to do with 3D modelling. I have no idea where you're getting that at all.

I think the difference is that you're thinking about how to use the program as a user, and I'm thinking about how the program is actually working inside.

[Turnsky]

Yes, and that's why I was hoping to see the file, so I could take it apart and find out how it was made.  It's more complex effects I was skeptical about.

well if you wanted: http://www.ariannia.com/images/stuff/tapecommish1.rar 'ere you go.

[Keleth]

It has nothing to do with 3D modelling. I have no idea where you're getting that at all.

I think the difference is that you're thinking about how to use the program as a user, and I'm thinking about how the program is actually working inside.

Vector is a series of Mathematical equations to make a shape in a 2D space. Usually involving the border, known as a path, and the inside shape known as a a 'fill'.

Then when size is changed, the mathematical equations, keep the proper shape and dimensions, so it can be resized without pixelation. As it is not a grid, but a series of tubes.

Now just take a minute, just sit right there, Let me tell you a story of how I became a prince of a town called Bel-Air. . .

[superluser]

Vector is a series of Mathematical equations to make a shape in a 2D space. Usually involving the border, known as a path, and the inside shape known as a a 'fill'.

Some of the mathematical transforms involved are the same as 3D operations, and in some cases, they may take advantage of 3D code to speed up conversion and rendering times.  If, for example, you perform a transform that emulates a TV signal getting squeezed vertically, that's the same as a 3D longitudinal wave, and you can use 3D code to do that transform, since it's the exact same transform.

But what I really came back to say was that the native SVG format probably doesn't support many of these things.  The Inkscape extensions probably do, though.  The .ai format probably supports them, as well.

[Tapewolf]

Vector is a series of Mathematical equations to make a shape in a 2D space. Usually involving the border, known as a path, and the inside shape known as a a 'fill'.

At the end of the day what you're doing is taking a linked-list of primitives, usually polygons, and dumping them to the screen in z-order.

However, if we have something like this:


http://www.project-future.org/stuff/things/occlusion1.png

...it becomes a bit tricky.  Now, one way to do it might be to group them into several video buffers and composite them at the raster level, that would probably be simplest, actually, but it would require a fairly large amount of memory.

Alternatively, you could modify the polygon draw routine so that it simply doesn't draw the part where the polygons intersect.

I don't know if you remember the Crystal Dream 2 demo from '93, but if not:
http://www.youtube.com/watch?v=b3GUfM7qkCw
...the interesting part is around 2:30  (*).

...that's a similar kind of problem, and what I was saying was that the solution that Illustrator uses - whatever it does - is probably based on the same kind of technology that you'd find in a 3D game engine.  Specifically when I mentioned modelling, I was thinking in terms of CSG subtraction since it basically has the same end goal.  Of course, since I never fully managed to get my head around that I could be way off-base  

Now, from a purely 2D viewpoint, the other approach which springs to mind is to decompose the rectangle into a concave polygon like this:


http://www.project-future.org/stuff/things/occlusion2.png

...I think we're way off-topic now, but I'm fascinated by graphics algorithms, so sue me  

(* EDIT: 3:45 is also interesting, they bend the cube in much the same way I did for the VCR dropout.  No idea if it's being done inside the renderer or what, though)

well if you wanted: http://www.ariannia.com/images/stuff/tapecommish1.rar 'ere you go.

Thanks very much!

[Keleth]

At the end of the day what you're doing is taking a linked-list of primitives, usually polygons, and dumping them to the screen in z-order.

However, if we have something like this:


http://www.project-future.org/stuff/things/occlusion1.png

...it becomes a bit tricky.

You mean it becomes . . easy.

That's done with one or two clicks.

Seriously. It's easy.

[Alondro]

*Charles attempts to comprehend*   

*brain fried*

I haz a kooky... 

[VAE]

Is not difficulty to comprehend, once somebody explains it like this. But even though i am doing engineering i find most geometry rather scary.... Especially 3D geometry

[llearch n'n'daCorna]

You mean it becomes . . easy.

That's done with one or two clicks.

Seriously. It's easy.

Drath, I'm starting to suspect you're being deliberately thick. I'd just like you to know that it's gone past the joke stage, and that further elaboration will be viewed dimly.


Probably through the window of a brief lack of posts on your part.


Just so you know.

[Jack McSlay]

lol...
http://tvtropes.org/pmwiki/pmwiki.php/Main/EnhanceButton
Kinda ironic the series being parodied is the one of the few fictional crime investigation series that actually does research (I don't remember they doing anything that isn't plausible)

At the end of the day what you're doing is taking a linked-list of primitives, usually polygons, and dumping them to the screen in z-order.

However, if we have something like this:

http://www.project-future.org/stuff/things/occlusion1.png

...it becomes a bit tricky.  Now, one way to do it might be to group them into several video buffers and composite them at the raster level, that would probably be simplest, actually, but it would require a fairly large amount of memory.

That's quite easy to do, even in inkscape - just make two paths, make sure the inner path has an inverted order compared to the outer path and merge them. You can do that with masks too, but it's trickier.

The algorithm behind that I don't know, but I guess it has something to do with drawing until finding a line with an inverted order compared point of reference

(sorry for necroing an old thread, but this sub-forum doesn't have a lot of threads anyway and I think that was rather relevant)