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

101–110 of 127 posts

Re: Show HN: Wave function collapse algorithm

#101

Post by krylon »

ExUtumno wrote: post #86
toxik wrote: post #77

Earlier quoted context omitted.

This will be abstract, but you seem to know your abstract algebra -- is it possible to do this kind of thing with graphs? It should be, right? And we all know code can be constructed with graphs, so… voila, you can generate code, no?

What do you mean by "code can be constructed with graphs"?

I suppose the GP refers to compilers/interpreters parsing source code into abstract syntax trees (ASTs).

Re: Show HN: Wave function collapse algorithm

#102

Post by abecedarius »

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 backtracking.)

Is that the idea? The description wasn't completely clear to me.

Re: Show HN: Wave function collapse algorithm

#103

Post by 4bpp »

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 comparison (to see if you have seen that exact pattern before) if the hashes match. Assuming you don't have too many distinct elements, this should give you performance close to linear in the size of your data.

[1] https://en.wikipedia.org/wiki/Rolling_hash

Re: Show HN: Wave function collapse algorithm

#105

Post by kereta »

netsec_burn wrote: post #31
vinchuco wrote: post #26

Earlier quoted context omitted.

>with the help of ideas from quantum mechanics. >so it doesn't do the actual quantum mechanics, but it was inspired by QM.

Yea, my only disagreement here is the name.

Same here. Came here looking for a breakthrough in Quantum Physics :)

Re: Show HN: Wave function collapse algorithm

#106

Post by wyager »

ExUtumno wrote: post #89
wyager wrote: post #61

Earlier quoted context omitted.

Just to make sure I understand, if I were to use 1D WFC with 1xN tiles, would it be the same as an (N-1)th order Markov chain? Or would it be a 1st-order Markov chain with (N-1) simultaneous outputs?

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?

Re: Show HN: Wave function collapse algorithm

#108

Post by abecedarius »

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…

(I should've said most-constrained)

Re: Show HN: Wave function collapse algorithm

#109

Post by palunon »

krylon wrote: post #101
ExUtumno wrote: post #86

Earlier quoted context omitted.

What do you mean by "code can be constructed with graphs"?

I suppose the GP refers to compilers/interpreters parsing source code into abstract syntax trees (ASTs).

Or maybe to things like PureData, Unreal Engine blueprints, etc

Re: Show HN: Wave function collapse algorithm

#110

Post by dgreensp »

fitzwatermellow wrote: post #97
ExUtumno wrote: post #35

Earlier quoted context omitted.

Thanks! Efros' and Leung's method doesn't satisfy the (C1) condition. The closest previous work is Paul Merrel's model synthesis. WFC and texture synthesis serve similar purposes: they produce images similar to the input image. However, the definition of what is "similar" is different in each case. If you have a high def input with noise (like realistic rocks and clouds) then you really want to to use texture synthes…

Thanks for the reply! So what I'm really after is a way to iteratively "perturb" the sample in such a way that the resulting texture will smoothly reflect those changes. Take a look at this rough illustration: Op-Art Texture Synthesis http://imgur.com/a/1IKN3 You mentioned rotation and mirroring type bitmap ops in your algorithm. But how do we precisely apply a series of dynamic filters to the input to "evolve" the p…

You might be interested in this work showing texture synthesis over a 2d surface with non-uniform geometry, rotation, scale, or even velocity: http://hhoppe.com/proj/apptexsyn/
Post reply on HN