Say I want to quantitively evaluate the effectiveness of several color-to-grayscale conversion algorithms, which can be considered as lossy compression. Would entropy be a good indicator?
To calculate the entropy of a file, I first convert it to a byte stream with
hexdump(1) or some other methods (see below). Next, this stream of bytes is considered as a Markov chain, and its transition matrix is estimated by examining consecutive bytes, from which entropy is calculated. The stationary distribution can be estimated by counting all bytes in the file if needed.
There are three caveats, however:
- Sometimes you need to use longer "byte"s. For example, if the file is encoded with UTF-16, then an atomic unit should contain exactly 16 bits. Fortunately, almost all pictures use True color (24-bit), or 8-bit or RGB respectively, so this won't be a big problem.
- Pictures are inherently 2D structures, and
hexdumpbasically coerces them to 1D linear structures, but that's inappropriate. The file should be traversed in another way so that the positional change is as smooth as possible, like
* > * * > * * > * > * > * / / / /----<----/ * * * * * > * > * > * | / / / | <- GOOD /----<----/ <- BAD * * * * * > * > * > * / / / /----<----/ * > * * > * * > * > * > *
- The input and output of algorithms to be compared against each other must be the same.
Any thought is appreciated!