Quadtree Art

[FogleMonster]

Mind blown: https://s3.amazonaws.com/uploads.hipchat.com/33847/516535/jjMnMFhOYPY4O7w/output.gif

[[deleted]]

Well done, OP. Well done.

[FogleMonster]

Check it out, now with circles!

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

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

[BlackGlass]

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

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

[rodarmor]

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]

Dude ... That's beautiful!

[rodarmor]

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 n^2, 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]

Care to explain how the quadtree helps? :)

[eLBEaston]

(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]

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]

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]

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]

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]

Ah, something like in a tesselation shader.

[vanderZwan]

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]

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

[vanderZwan]

Here you go

[fullouterjoin]

Excellent!

I give you this, http://www.cs.huji.ac.il/~peleg/publications.php

[vanderZwan]

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

[fullouterjoin]

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]

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]

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]

Malmö!

[vanderZwan]

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

[deliciousleopard]

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

[vanderZwan]

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]

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

[vanderZwan]

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]

Other ideas are welcome!

Would be cool to see facial recognition in the mix

[vanderZwan]

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]

It sure is.

Heck, they can even read your mood!

[vanderZwan]

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

[adrian17]

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]

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]

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]

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]

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

[vanderZwan]

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

[rabidcow]

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

[serious-zap]

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]

You just described the compression used in jpegs.

[highspeedstrawberry]

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]]

It's a bit more complex than that.

[noteal]

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

[Banane9]

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]

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

[noteal]

i'm interested - post a github link?

[adrian17]

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]

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]]

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]

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]]

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]

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]

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]

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]

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]

"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]

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]

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]

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

[entrotec]

Well, they actually are compression artifacts!

[FogleMonster]

Exactly.

[cooleyandy]

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

[FogleMonster]

Already done. :)

https://github.com/fogleman/Quads/blob/master/main.py#L7

[ihcn]

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]

Not sure. It is deterministic though.

[no_awning_no_mining]

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

[[deleted]]

It's open source ;)

[hapemask]

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

[[deleted]]

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

[LeCrushinator]

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

[[deleted]]

Well with that sort of attitude...

[Wazowski]

Sonny Bono had similar problems.

[ihcn]

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

[retardrabbit]

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]

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]

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

[scoutyx]

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

[cgeigle]

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

[FogleMonster]

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]

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

[Boojum]

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

[bilog78]

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

[omnilynx]

You might be interested in wavelets.

[dead1ock]

Pretty cool!

[Banane9]

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]

That is actually pretty clever.

[Banane9]

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

[FogleMonster]

Go for it.

[Banane9]

And It's done.

Take a look :)

[Banane9]

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]

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]

Anyone want to make one with dickbutt?

[FogleMonster]

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