Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Wave function collapse algorithm

github.com

Post reply on HN
Print view View original

111–120 of 127 posts

Re: Show HN: Wave function collapse algorithm

#111

Post by ExUtumno »

mathgenius wrote: post #100
ExUtumno wrote: post #81

Earlier quoted context omitted.

About harder and easier to satisfy, the question of how the rate at which the algorithm runs into contradictions depends on the input is not easy at all. There is no simple correlations between the contradiction rate and the size of the input. But the first thing you'll notice if you feed it an image with a lot of patterns, is that it will work very slowly. Yeah, the corpus thing can be done if we cut out rare patter…

I wonder if it would be interesting to purposely search for tilesets that maximize contradiction rate. What would those things look like?

A very good question! The opposite of it is also important, can we follow some heuristics while creating tilesets to minimize contradiction rates, but not making tilesets easy? I don't know. If someone knows please tell me.

Re: Show HN: Wave function collapse algorithm

#112

Post by ExUtumno »

abecedarius wrote: post #102

As I understand it: this treats image generation as constraint satisfaction. The constraints are that each NxN patch appears in the source image. The satisfaction method is arc consistency https://en.wikipedia.org/wiki/AC-3_algorithm , except, when that settles down prematurely, pick the least-constrained patch and make a random valid choice, then continue. (If this leads to getting stuck, then give up instead of bac…

Yes, (C1) is a constraint problem. But we also want to satisfy (C2) as close as possible, otherwise we could have just colored some outputs in a single color.

Re: Show HN: Wave function collapse algorithm

#113

Post by ExUtumno »

wyager wrote: post #106
ExUtumno wrote: post #89

Earlier quoted context omitted.

If you use overlapping model (there are 2 models in the repo) with 1xN patterns, it would be a the same as (N-1)th order Markov chain.

Can you explain the difference between the overlapping and non-overlapping models?

In overlapping models we store probabilities for NxN blocks of colors/tiles. In non-overlapping models we store probabilities for individual colors/tiles.

Re: Show HN: Wave function collapse algorithm

#114

Post by abecedarius »

ExUtumno wrote: post #112
abecedarius wrote: post #102

As I understand it: this treats image generation as constraint satisfaction. The constraints are that each NxN patch appears in the source image. The satisfaction method is arc consistency https://en.wikipedia.org/wiki/AC-3_algorithm , except, when that settles down prematurely, pick the least-constrained patch and make a random valid choice, then continue. (If this leads to getting stuck, then give up instead of bac…

Yes, (C1) is a constraint problem. But we also want to satisfy (C2) as close as possible, otherwise we could have just colored some outputs in a single color.

Yes, I took that to mean, when you're making a random valid choice, the weights come from the input distribution.

I don't understand about "a single color" unless you mean setting all output pixels to the same color, which would only satisfy the constraints if the input has an NxN patch all one color.

I hope my comment didn't seem to imply that the work seemed unoriginal. I don't think that; I wanted to check my reading.

Re: Show HN: Wave function collapse algorithm

#115

Post by ExUtumno »

mirekrusin wrote: post #98

Can this approach be used to generate "missing parts" in unfinished song? If composer has few good parts but is too lazy to finish the whole piece, for example? Or to "extend" Moonlight for example?

There are special approaches to generating music. The best for ratio of quality/complexity that I know of are Markov constraints https://www.youtube.com/watch?v=buXqNqBFd6E and WaveNet. I don't think WFC offers something useful and new for generation of music.

Re: Show HN: Wave function collapse algorithm

#116

Post by ExUtumno »

abecedarius wrote: post #114
ExUtumno wrote: post #112

Earlier quoted context omitted.

Yes, (C1) is a constraint problem. But we also want to satisfy (C2) as close as possible, otherwise we could have just colored some outputs in a single color.

Yes, I took that to mean, when you're making a random valid choice, the weights come from the input distribution. I don't understand about "a single color" unless you mean setting all output pixels to the same color, which would only satisfy the constraints if the input has an NxN patch all one color. I hope my comment didn't seem to imply that the work seemed unoriginal. I don't think that; I wanted to check my read…

Most of the examples in the repo have those NxN all one color patches. Or, without (C2) the algorithm would have generated completely empty integrated circuits, or completely grass terrain, which is really boring.

You understood right, it's constraints + probabilities.

Btw, I have different algorithm that satisfies (C2) perfectly, but not (C1): https://github.com/mxgmn/ConvChain

Re: Show HN: Wave function collapse algorithm

#117

Post by abecedarius »

ExUtumno wrote: post #116
abecedarius wrote: post #114

Earlier quoted context omitted.

Yes, I took that to mean, when you're making a random valid choice, the weights come from the input distribution. I don't understand about "a single color" unless you mean setting all output pixels to the same color, which would only satisfy the constraints if the input has an NxN patch all one color. I hope my comment didn't seem to imply that the work seemed unoriginal. I don't think that; I wanted to check my read…

Most of the examples in the repo have those NxN all one color patches. Or, without (C2) the algorithm would have generated completely empty integrated circuits, or completely grass terrain, which is really boring. You understood right, it's constraints + probabilities. Btw, I have different algorithm that satisfies (C2) perfectly, but not (C1): https://github.com/mxgmn/ConvChain

Thanks!

I might try this approach to generate formal poetry -- it's something I've done by backtracking before, and I'd considered doing something like your ConvChain.

Re: Show HN: Wave function collapse algorithm

#119

Post by throwathrowaway »

abecedarius wrote: post #114
ExUtumno wrote: post #112

Earlier quoted context omitted.

Yes, (C1) is a constraint problem. But we also want to satisfy (C2) as close as possible, otherwise we could have just colored some outputs in a single color.

Yes, I took that to mean, when you're making a random valid choice, the weights come from the input distribution. I don't understand about "a single color" unless you mean setting all output pixels to the same color, which would only satisfy the constraints if the input has an NxN patch all one color. I hope my comment didn't seem to imply that the work seemed unoriginal. I don't think that; I wanted to check my read…

Thank you for writing this (and your last comment) out explicitly. The quantum mechanics description confused me (and possibly other from reading the thread here). Although I can understand how that inspired this work in the first place.

The algorithm used is exactly what you described here. It wasn't obvious to me that probability density functions were not tracked (the algorithm only tracks which NxN patch are allowed at each location) and randomness only come into play when a random valid choice is made, and there each valid patch is chosen probability proportional to its number of occurrence in the input.

Re: Show HN: Wave function collapse algorithm

#120

Post by Balgair »

4bpp wrote: post #103
Balgair wrote: post #91

Fantastic stuff. I love it! As with most meachine learning stuff and these very cool ideas (of which I am very hazy on, esp their categorizations) I immediately want to use it for our lab's brain work. We have a LOT of 3-D images (per voxel is ~200nmx200nmx~600nm for a lot of 1028x1028 .tiff images all stitched together) and would love to feed these images BACKWARDS into this. IE we have the 'far field', and we want…

Sounds like an altogether easier problem, assuming you don't care to compensate for noise in your data somehow - supposing you want to identify all distinct m×n×k-sized "elements", simply use some appropriate rolling hash[1] (i.e. a hash of a window that you can update in constant time as you slide the window) as a key mapping to a list of "elements" you have seen so far with that hash, and only do pointwise comparis…

Whew, now that was a wikipedia binge. Thanks for the leaping off point! Unfortunately, our data is VERY noisy. We can do some techniques to smooth the data, but the unfortunate part is that the things that matter in biology are under the diffraction limit of light. Inherently, what we want out of the data will then be noisy. Gestalt structures are less noisy and these techniques can help with that (think using a fiber-optic read-out as you go into the brain for surgery so you know what region you are in), at least I think. Also, the 'elements' of our data set are unknown, but likely very large. Maybe in the 100s to 1000s, not 5 or 10. It turns out the brain is complicated, who knew?!

Still, thanks a ton for this info! I think it can really help with some computational bio stuff another lab is working on here (viral similarity in genes in your DNA)

Post reply on HN