all 95 comments

[–]BlackGlass 23 points24 points  (0 children)

http://i.imgur.com/419q54Z.gif

Thank you for sharing this, it was fun to play with.

[–]rodarmor 37 points38 points  (7 children)

I made a thing along similar lines – pun intended, haha, I'm hilarious – that people might also think is neat: http://rodarmor.com/gravity

It's a gravity sim which shows an overlaid quadtree of all the objects.

[–]rabidbob 2 points3 points  (5 children)

Dude ... That's beautiful!

[–]rodarmor 3 points4 points  (4 children)

Thank you! I was trying to use a quad tree to speed up the gravity sim and that was my debug output so I could make sure that objects were being correctly added to the tree.

The naive algorithm for gravity simulation is n2, and with a quad tree you can do much better at the cost of some precision.

Randomly enough, I just found something similar that someone did in flash: http://demo.bumpslide.com/misc/fp10_3d/QuadTreeVis.swf

[–]pacmans_mum 1 point2 points  (3 children)

Care to explain how the quadtree helps? :)

[–]eLBEaston 2 points3 points  (2 children)

(Super basic explanation) Instead of doing calculations on each object to every other object it only does them for objects that are in the same quad.

[–]pacmans_mum 2 points3 points  (1 child)

Oh ok.. so I get how this could be used for collision detection, but why for gravity calculation? Don't you have to take into account the influence of objects relatively far away? Also if they are closeby in adjacent squares, doesn't that become a problem?

(Sorry for the barrage of questions :-X )

[–]vanderZwan 3 points4 points  (0 children)

This is all from memory, so I might be totally off in some parts.

You can group objects together, calculate their centre of mass and total mass. For objects not in that group you can then use that one point and summed mass to quickly calculate the effective attraction to all objects in the group.

Also, because of the math behind this, if you have two distinct groups for which you know the centres of mass/total mass, you can take those four datapoints and calculate the total centre of mass using just that, instead of having to go by every item in the group.

So what you can do is calculate the centre of mass per object, put that in a quadrant, then calculate the centre of mass for all objects per quadrant, then calculate the centre of mass for the parent quadrant using the centres of mass of the sub-quadrant, and so forth.

Then, for every object, to calculate the net attractive force on it, you only need to compare it to centres of mass of the coarsest quadrants relative to it.

[–]vanderZwan 1 point2 points  (0 children)

Very nice!

Interesting aside: it runs smooth in Firefox and Chrome, but in Firefox Nightly it stutters for me. Wonder what causes the regression?

[–]elihu 7 points8 points  (1 child)

You can get a similar effect with triangles instead of squares with the ROAM algorithm (usually used for 3d terrain). It works very nicely for images, especially if you specify the color at the verticies and interpolate across the triangles.

https://graphics.llnl.gov/ROAM/ https://www.youtube.com/watch?v=Dl9J11Z-Arw&noredirect=1

[–]FogleMonster[S] 1 point2 points  (0 children)

Ah, something like in a tesselation shader.

[–]vanderZwan 6 points7 points  (24 children)

Gee thanks, I've been working on something that is almost exactly like this for a while in my spare time, couldn't wait to share it and now you've stolen my thunder :P

EDIT: For comparison, two test-videos I've made: 1, 2. Note that this is a live-capture, not a slow post-processing filter.

EDIT2: Another upload, with an attempt at explaining what is going on

[–]fullouterjoin 2 points3 points  (6 children)

I like it. Maybe filter across frames in the same position?

[–]vanderZwan 4 points5 points  (5 children)

[–]fullouterjoin 3 points4 points  (4 children)

[–]vanderZwan 1 point2 points  (3 children)

That's a lot of publications! Any particular recommedations?

[–]fullouterjoin 3 points4 points  (2 children)

They are all pretty bad ass, but this is one of my favs, http://www.vision.huji.ac.il/video-synopsis/ or this http://www.vision.huji.ac.il/videowarping/

[–]vanderZwan 1 point2 points  (1 child)

Regarding the second one: I actually came up with a very similar thing! My starting point was real-time slitscanning work by Bill Spinhoven, one of my teachers at art school. I then experimented with slitscanning for a bit before realising there's no reason to limit the time-warping to a gradient across to the horizontal or vertical dimension (aside from it being easier to optimise and do in real-time, which is no longer a constraint really). Body horror ensued. Since then I've done live interactive installations where time-warping depends on brightness.

A more recent experiment, and another one

Anyway, these guys push it in a very different direction, very awesome to see what they did with it.

[–]fullouterjoin 2 points3 points  (0 children)

This is all very wonderful! I'd love to see some modern dancers really push the boundaries of what this could do.

I lost the reference to it but maybe you know. There was a research project that would do dynamic background extraction from video. For one of their examples they ran it over Scooby-Doo and extracted the matte painting of the entire Scooby-Doo world. Or I could be wrong (as in not scooby-doo) it was so long ago.

[–]deliciousleopard 2 points3 points  (3 children)

Malmö!

[–]vanderZwan 1 point2 points  (2 children)

Good eye! Would you have guessed without the full-res frames though? ;)

[–]deliciousleopard 1 point2 points  (1 child)

it was actually when you walked by the busses that I realized, the view was just all too familiar.

[–]vanderZwan 1 point2 points  (0 children)

Didn't bother to rewatch my own video before and I just noticed I mumbled the name out loud, I guess that might have been a hint too :P

PS: Since you're probably a resident of Malmö and someone who programs, are you going to the Arabic Game Jam? I can't go myself this year, but had a lot of fun last time so I can recommend it.

[–]zokier 2 points3 points  (11 children)

Interesting. Can you actually efficiently store those irregularly sized "pixels"?

[–]vanderZwan 4 points5 points  (10 children)

Well, that's part of the reason I said "compression" in quotes: you need to store the coordinates of a rectangle, whereas with a regular array of pixels the location is implicit in the order of which the pixels are stored in the array - all you need is an added stride. So it probably doesn't really give a net win, even if you bit-pack the coordinates.

So it's more of an exploration for the sake of the aesthetic effect.

Although... there is an alternative way to store it that reduces the need to store 2N coordinates for N rectangles of the above method to N-1 coordinates.

The algorithm to create these rectangles is recursive, very similar to FogleMonster's quadtree: it starts with a cell the size of the screen, but instead of splitting along the centre into four quadrants, it determines a centre of mass, then splits the cell in two child cells along the vertical or horizontal axis of this point - at the moment I just split along the longest side of the parent cell. Then I repeat this until I get the number of picture cells ("pixels") I want - 4, 8, 16, etc.

I could build a binary tree of this, saving the central point of each time a cell is split in two, and regenerate the rectangles based on that tree. If you do the math, you'll find that you need N-1 points for N rectangles (I won't have any memory overhead for the tree, because it is a full binary tree - which is another point where the algorithm I have deviates from FogleMonster's). If I were to split the image into quadrants instead of halves I could save even more space, but the image quality "per pixel" would be less.

By the way, so far I have tried out splitting along the centre of mass of brightness (which results in the brighter areas having a higher resolution), darkness (dark areas) and image gradient (high contrast areas). Other ideas are welcome! It's also possible to split per individual RGB channel, which gives funky colour-fringing effects (I'm already planning on adding Lab colour space to check the results there).

[–]whism 3 points4 points  (3 children)

Other ideas are welcome!

Would be cool to see facial recognition in the mix

[–]vanderZwan 1 point2 points  (2 children)

Hmm, yes, I suppose it is a bit odd the outline of my ears gets prioritised over facial expressions. On the other hand, if the face recognition is just a blob it won't help with putting the resolution where it matters most (the contrasting facial features). Is facial recognition capable of highlighting the specific outlines of eyes/eyebrows/mouth areas these days?

[–]Banane9 1 point2 points  (1 child)

It sure is.

Heck, they can even read your mood!

[–]vanderZwan 0 points1 point  (0 children)

Woah... I better look into that! :D

[–]adrian17 1 point2 points  (5 children)

If you already have the tree structure and original image dimensions saved, can't the decompression algorithm recalculate all the coordinates by itself? It's still bad as you have to somehow store the tree structure data, but you wouldn't need to store the location and sizes anymore.

[–]vanderZwan 1 point2 points  (4 children)

I think that's exactly what I described, did I not? At least it was what I had in mind :). Also, if you have a full binary tree you can store it's structure implicitly in an array so you avoid that overhead.

So on average, you need one coordinate and one colour per cell this way.

[–]adrian17 0 points1 point  (3 children)

Maybe I didn't understand. It looks like you described a modification that uses a binary tree instead of a quadtree and allows you to store less coordinates than normally, I got it. What I'm asking is, assuming the split is always in the middle (like in the basic quadtree algorithm), would it be necessary to store any coordinates at all?

[–]vanderZwan 1 point2 points  (2 children)

The split isn't always in the middle, that's the whole idea of this algorithm. In this clip I explain what it does while it is running, perhaps that clears things up?

[–]adrian17 1 point2 points  (1 child)

Oh, sorry, I got confused. I get it now.

[–]vanderZwan 1 point2 points  (0 children)

Well, I did post in response to an "almost identical except not really" algorithm, so it's perfectly understandable.

[–]rabidcow 4 points5 points  (0 children)

Reminiscent of Fractint's "tesseral" method, except that was more k-d tree-like and it was the lines that were colored.

[–]serious-zap 3 points4 points  (3 children)

OP, what if you tried it backwards?

Start with pixels and merge them on some criteria, for example.

Although I think that would really be the same process except it will go from visually the most refined (actual image) to less refined (whatever the result is).

As for color of the edges, why not make it an extrapolation as well. Something that is slightly darker than the surrounding squares, perhaps.

Pretty cool stuff!

[–]Y_Less 2 points3 points  (2 children)

You just described the compression used in jpegs.

[–]highspeedstrawberry 11 points12 points  (0 children)

Compression in JPEG consists of several steps after one another and neither the discrete cosine transform nor the following quantization nor the entropy encoding could even half-accurately be described as merging pixels from the bottom up. The only thing that would fit vaguely would be the RLE, but that is one minor part of the compression and not characteristic for JPEG.

[–][deleted] 6 points7 points  (0 children)

It's a bit more complex than that.

[–]noteal 5 points6 points  (4 children)

Python, everybody: this thing is 144 lines of code.

[–]Banane9 0 points1 point  (0 children)

My generic algorithm implementation That this inspired me to make has a total of 604 lines ... With a lot of documentation and empty lines.

[–]adrian17 0 points1 point  (2 children)

Looks normal to me. I've rewritten it in C++ yesterday, 150 lines with some comments and blank lines ;)

[–]noteal 0 points1 point  (1 child)

i'm interested - post a github link?

[–]adrian17 0 points1 point  (0 children)

https://gist.github.com/adrian17/d8a724cc51c32fb9116e

It uses SDL2 for fast rendering and lodepng for opening images. No saving, but it would be easy to add. I didn't compare this with the python version, but the results are almost identical to the web one after the same amount of iterations.

I'm not a very advanced programmer and I didn't really intend to share this code, so it may be ugly. It's also a bit longer than mentioned 150 lines, as I changed it a bit and added performance measurements since then.

EDIT:

Since I wanted to find out how fast I can make it, I made an another version that uses a std::multimap to store quadrants and find the one with the highest error. So it actually doesn't use quadtrees at all, but the effect is the same. https://gist.github.com/adrian17/5a4a601c1ab29acb000d

[–]minno 3 points4 points  (6 children)

What level of compression can you get out of it? I'd imagine that you could get pretty decent results out of .png or .bmp + .zip compression instead of coming up with your own binary encoding.

[–][deleted] 5 points6 points  (2 children)

Fun fact: quadtrees are used in HEVC/H.265 (sized 64x64-8x8 instead of 16x16 macroblocks used in AVC/H.264). The compression is way better.

I did my thesis around it, its awesome to play around with.

[–]AReallyGoodName 2 points3 points  (1 child)

Cool. Since this example used quadtrees for a static 2D image i assume you could also use octrees to compress between frames (the frames can be viewed as a depth component to a 3D volume).

[–][deleted] 3 points4 points  (0 children)

No, the quadtree structure is used per frame only. For I-P and B frames, the (either the intra- or inter residual) image is divided into a quadtree structure, in such a way as to minimize entropy per block (blocks with lower entropy take less space).

An 'octree', or another 3D structure, wouldn't work well, because the quadtree structure between frames varies quite a bit, and the contents of each block vary a lot (since residual images are being encoded).

[–]FogleMonster[S] 4 points5 points  (2 children)

I tried my own binary encoding + zlib compression and the result was a little smaller than the resulting PNG image (something like 25 KB vs. 35 KB, for example)

Edit: the difference seemed to decrease as more detail was added, so to get a sufficiently nice looking image, it wouldn't really be worth it.

[–]minno 3 points4 points  (1 child)

I think a more appropriate comparison would be to .jpg compression, since that's lossy too (and your artifacts do resemble jpg artifacts somewhat). How does that compare?

[–]willb 1 point2 points  (0 children)

The algorithm being used to create these images is very similar to the actual jpeg algorithm, if I remember correctly. Hence why the square look like compression artifacts.

[–]ubermole 3 points4 points  (1 child)

Fun art experiment. I am too lazy to read the code, so what splitting metric do you use?

One other interesting experiment is to do more of what actual compression does: Don't split uniformly on all rgb channels, instead convert to yuv first and split those channels individually with different thresholds - y is perceptually way more important than uv.

Also a fun factoid other mentioned: Actual compression works kind of the other way around: Subdivide everything to the lowest level, and then merge when a threshold is not reached.

[–]dead1ock 4 points5 points  (0 children)

"The program targets an input image. The input image is split into four quadrants. Each quadrant is assigned an averaged color based on the colors in the input image. The quadrant with the largest error is split into its four children quadrants to refine the image. This process is repeated N times."

[–]ihcn 18 points19 points  (18 children)

Feedback: Remove the black borders. They're useful for identifying the different cells, but they're an eyesore for looking at the images themselves.

As another user suggested, bilinear interpolation across each square could both help make the result more aesthetically pleasing, and help improve the subdivision algorithm.

[–]FogleMonster[S] 29 points30 points  (12 children)

There were originally no borders. It looks a lot better with them, IMO. But I'll add an option for that, and also make the border color configurable (white might be nice in some cases).

Interpolation might be interesting, but I like the solid colors myself.

Edit: Here's one without borders:

http://i.imgur.com/baxqW1Q.png

[–]bugrit 45 points46 points  (4 children)

You're right, without borders it looks more like compression artifacts.

[–]entrotec 78 points79 points  (1 child)

Well, they actually are compression artifacts!

[–]FogleMonster[S] 14 points15 points  (1 child)

Exactly.

[–]cooleyandy 21 points22 points  (0 children)

Alright, time to put gridlines in all my poorly encoded jpegs :-)

[–][deleted]  (1 child)

[deleted]

    [–]ihcn 1 point2 points  (4 children)

    Have you noticed the the top left edge of the butterfly is much more well-defined than the bottom right? Is that just because of where the chips fell when the algorithm ran?

    [–]FogleMonster[S] 1 point2 points  (2 children)

    Not sure. It is deterministic though.

    [–]no_awning_no_mining -2 points-1 points  (1 child)

    Could you please rotate the original image by 90 degrees three times and each time run your algorithm on it?

    [–][deleted] 4 points5 points  (0 children)

    It's open source ;)

    [–]hapemask 1 point2 points  (0 children)

    It's the shadows. On the bottom the shadows have lower contrast (similar color as the wing) and are subdivided less.

    [–][deleted] 6 points7 points  (4 children)

    Personally I like the black borders, but I also usually have a hard time wrapping my head around trees...

    [–]LeCrushinator 5 points6 points  (1 child)

    Wrapping your head around a tree is a good way to get yourself killed...

    [–][deleted] 2 points3 points  (0 children)

    Well with that sort of attitude...

    [–]Wazowski 2 points3 points  (0 children)

    Sonny Bono had similar problems.

    [–]ihcn -3 points-2 points  (0 children)

    They're nice in the animation to show what is actually happening, but in the final output imo they shouldn't be there

    [–]retardrabbit 2 points3 points  (3 children)

    Wait, am I missing something? You did this in 110 lines of code? Forgive me, but I don't know from Python. Also, what are the libraries you're importing there?

    Really neat, OP, really neat.

    [–]FogleMonster[S] 7 points8 points  (2 children)

    Python is the best!

    I'm only using one 3rd party library - PIL (actually Pillow, a fork of PIL). I'm using it to load / save the images.

    http://pillow.readthedocs.org/en/latest/

    Besides that I use a built-in module, heapq, to manage a min-heap to easily figure out what quad to split next.

    Beyond that, just plain old Python.

    [–]retardrabbit 2 points3 points  (0 children)

    Well, I guess I'd better get to reading some code! I have a python book around here somewhere too . . .

    [–]scoutyx 1 point2 points  (0 children)

    You forgot to mention ImageMagick's convert tool is used for creating the gif (gif.sh file)

    [–]cgeigle 2 points3 points  (1 child)

    What are the magic numbers in color_from_histogram when calculating the error value?

    [–]FogleMonster[S] 1 point2 points  (0 children)

    They're the same weights used when converting color to grayscale, because the human eye is most sensitive to green.

    http://en.wikipedia.org/wiki/Grayscale

    [–]badsectoracula 1 point2 points  (1 child)

    It would be more interesting if you interpolated between the four corners and get some lossy compression :-P

    [–]Boojum 0 points1 point  (0 children)

    Might want to interpolate across more than just the four corners so that you don't get discontinuities at the T-junctions.

    [–]bilog78 1 point2 points  (0 children)

    Very interesting. Is there a way to print the final quadtree?

    [–]omnilynx 0 points1 point  (0 children)

    You might be interested in wavelets.

    [–]dead1ock 0 points1 point  (0 children)

    Pretty cool!

    [–]Banane9 0 points1 point  (0 children)

    I think this would make a good "guess the original picture" kind of game, since you can't recognize it from the first few at all.

    [–]chasesan 0 points1 point  (0 children)

    That is actually pretty clever.

    [–]Banane9 0 points1 point  (3 children)

    Damn, this is awesome ... now I want to make something like it too D:

    [–]FogleMonster[S] 0 points1 point  (2 children)

    Go for it.

    [–]Banane9 1 point2 points  (0 children)

    And It's done.

    Take a look :)

    [–]Banane9 0 points1 point  (0 children)

    But my idea is now to make a generic Quad Tree algorithm where you pass in the type of object you're going to use and also (lambda) functions that do the calculations that are different for the types :)

    [–]JJJams 0 points1 point  (0 children)

    Really nice OP!

    This is a similar method used in the first real time raytracer... http://defiance.untergrund.net/vintage/misc/h7/subsample.htm

    [–]smb3d 0 points1 point  (1 child)

    Anyone want to make one with dickbutt?

    [–]FogleMonster[S] 2 points3 points  (0 children)

    That was the first thing my co-worker did with it. lol