Hacker News new | ask | show | jobs
by pfd1986 1855 days ago
I wonder if the number of lines can be a measure of Kolmogorov complexity for an image...

Neat idea regardless.

1 comments

It can certainly be a Minimum Description Length (MDL), which is a more general measure based on an arbitrary language (like "lines on a canvas").

Kolmogorov Complexity is the MDL when the language is Turing-complete; in that case I think the number of lines would be less interesting than the patterns in their arrangement. For example, we can arrange millions of lines in a spiral with very low Kolmogorov Complexity; whilst a handful of "random" lines could have a much higher complexity (since, without a pattern, we have to specify them all individually).

I mentioned it in a sibling, but I've written a very simple Python script which can be used as a test-bed for finding the Kolmogorov complexity of plotter-based images (using turtle graphics) http://chriswarbo.net/projects/turtleview