pie in the sky – Massive backwards compatability in OpenSCAD

OpenSCAD includes dozens (hundreds) of images that it uses to create backwards compatability.

But they are typically small examples that touch on one feature or bug.

Ideally we would test against thousands of .scad files from thingiverse.com and elsewhere and use those to test for backwards compatability on each new release of OpenSCAD.

There is a problem. The current way regression testing works, OpenSCAD stores a png file of each ‘expected image’, then renders an image, and compares the result against the ‘expected image’ to do the regression test. To render and store a .png file of all those examples would mean hundreds of megabytes of PNG files would be filling up the openscad source distribution. In fact, the bulk of the OpenSCAD source distribution would just be .png files for backwards compatability testing. (also called ‘regression testing’ by the way)

So how can we fix this?

Well, there are ways to create ‘hashes’ of images…. small little bits of data that are ‘digested’ versions of the image that, if you run the same ‘digester’ on other images, will be alike. Such ‘image hashing’ means that you can compare one image to another – even if you only have the hash of one of the images and not the actual image itself. You can just ‘digest’ to hash and compare the hash.

Image DNA is the commercial product that does this. It is used to fight against child porn because ISPs or websites can simply store the hashes of known CP images and the compare user uploads against those hashes – without having to actually store CP images themselves, and without having to have anyone manually compare. (Now, in reality, Google and Facebook and other sites may employ people from low-wage countries to manually ‘flag’ criminal CP images …. the thing about pedophiles is that they tend to keep sharing the same images over and over and over again over the years with each other… so that is why the image hash works without needing any manual intervention, other than someone having to put the image in a government database and hash it in the first place)

Anyways. Gross. So lets move on.

There is an open source way to do image hashing as well. It’s in this project:

http://www.imgseek.net/

It uses Wavelets. Wavelet theory is kind of like Fourier Transform theory. You see a digital  image in a computer is just a bunch of numbers in a row. And if you ‘fit’ a curve to it, like a sine wave, or Wavelet, you can sort of re-represent the image as curves instead of digital bits.

Here is a massively over-simplified example. We have an image. Then we take just a single scan-line of it, from left to right, right over the middle of the big red circle. We pretend this line is about  17 numbers long in pixels – which we draw as a graph, with each number representing the color of the pixel.

But we can re-write it as three sine curves using only 7 numbers. Curve one is from a to b, curve to is from b to c (it’s rather flat), and curve three is from c to d. D is 17 away from ‘a’ so we gave it the number 17. The height of the sine wave is in between.  (We assume the ‘points’ are all at 0 height. Told you it was over-simplified). But you hopefully get the idea.

Image

If you modify the image a little bit – say, make the circle a little bit lighter shade of red, then the ‘curve’ wont really change all that much. In fact, if you ‘split’ the image into ‘components’, like Color and Brightness, then you can, say, have two curves – and the brightness curve will change while the color curve wont.

In fact the JPEG algorithm works a lot like this. It breaks the image into a bunch of curves and then throws out the ‘small’ curves – leaving only big ones. That’s why its ‘lossy’ compression – it loses information. But the human eye doesn’t notice so much because it can adapt to those small losses of information.

Anyways. So the Wavelet functions are a really fancy version of this, they work a lot better than my crude drawing, and better than sine waves too apparently. They are More Better.

And so you can generate a ‘hash’, sort of, based on these waves. I dont understand how exactly you get to the hash, but…

I’d imagine when it comes to compare the hashes, it does something like comparison of the curves to see if they are within a certain distance of each other.

Basically, it asks the question “Do the curves match?”. Then if they do, you will know the images match, at least as far as a human being is concerned when looking at them. The images dont have to be ‘exactly identical’ down to the pixel, but they can be really close and get a ‘match’.

This simialr to something called ‘Perceptual Diff’, and there are some open source implementations out there that do this, like Hector Yee’s. But this ‘hashing’ thing is taking that concept to the next level.

So what does all this mean for regression testing and backwards compatability?

Well, the ‘image hash’, theoretically, takes up a tiny amount of space on a disk compared to an actual images.

So. Imagine, perhaps, that OpenSCAD could simply come with thousands of ‘image hashes’ in its regression test folder instead of actual PNG images. Where as PNG images would take hundreds of megabytes to store, the hashes could be stored in maybe a megabyte or two.

Then, maybe OpenSCAD could download a bunch of scad files from thingiverse, render them, and then do a hash-compare of the rendered image to the image hash it has stored in its regression testing folder.

If the test failed, then, and only then, we could actually retrieve the ‘expected’ image from some place, perhaps a separate github archive that just contains a bunch of actual png images.

This is all pure theory. Any piece of it might not work or be based on bad assumptions. However it seems worth a pondering.

Advertisements

About donbright

https://patreon.com/donbright https://github.com/donbright http://dwitter.net/u/donbright
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s