Show HN: I built a tool to generate triangulated art from images

Re:Show HN: I built a tool to generate triangulated art from... by motohagiography on Thursday April 22, 2021 @09:35AM (#26902543)

Could this technique be used to index images for search? e.g. intuitively, the triangles and their layout seem to preseve more unique information about the image than a grid would, kind of like Vornoi partitions, or an entropy preserving sample.

This isn't my area of expertise at all, but intuitively it seems like if you treated the triangles as a graph, you could sample a minimal subgraph from an image and then search for other files that have a similar subgraph. It's conceptually like "geometric hash."

Is that what this technique is for, as it seems to have more applicaitons than just an image filter.

[ Parent | on HN ]

Re:Show HN: I built a tool to generate triangulated art from... by birktj on Thursday April 22, 2021 @11:20AM (#26903729)

Note that the subgraph isomorphism problem [1] is NP-complete (also for planar graphs). There are very efficient data structures like k-d trees [2] that can be used to efficiently search for points in euclidean spaces, doing something similar for graphs would be quite difficult.

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

[2]: https://en.wikipedia.org/wiki/K-d_tree

[EDIT]:

Graph canonization [3] on the other hand is not known to be either polynomial time solvable (I think it is for planar graphs though) or NP-complete and has implementations that are quite efficient in practice. It can be used to search for the exact same graph, but again extending to searching for similar graphs is probably quite difficult.

[3]: https://en.wikipedia.org/wiki/Graph_canonization

[ Parent | on HN ]

Re:Show HN: I built a tool to generate triangulated art from... by rh12503 on Thursday April 22, 2021 @10:05AM (#26902889)

I originally intended this to be a generative art side project, but there's been a magnitude of great ideas commented here!

The graph idea could work, but the algorithm produces slightly different results each time it is ran. It still could be really interesting to try!

[ Parent | on HN ]

Re:Show HN: I built a tool to generate triangulated art from... by motohagiography on Thursday April 22, 2021 @10:30AM (#26903152)

Was thinking that the adjacency matrix that describes the graph you extract from the image will produce a string you can chunk and do a fast search on, and then it's a standard similarity/distance string search in Redis, or a probabilistic filter.

The compute on the indexing images would be relatively expensive, but the speed of a similarity search would be super fast, with the caveat that I don't know how image search is done today, and it probably should do something like this anyway.

[ Parent | on HN ]