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:

  1. 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.
  2. Pictures are inherently 2D structures, and hexdump basically 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
*   *   *   *               * > * > * > *
  /   /   /                  /----<----/
* > *   * > *               * > * > * > *
  1. The input and output of algorithms to be compared against each other must be the same.

Any thought is appreciated!

  • $\begingroup$ Please define quality and/or effectiveness of a data conversion. (Effective? Colour before, greyscale after: 100% effective. But data reduction rather than compression: good luck with trying to decompress/recreating something resembling the original) I can't see a difference in "smooth"ness between GOOD and BAD. There are quit a number of space-filling curves, Hilbert the one coming to my mind first. $\endgroup$ – greybeard Apr 21 '19 at 7:17
  • $\begingroup$ @greybeard Actually the definition is what I'm asking in the question! Vaguely speaking, I want to quantify the loss of information in a sensible way, but I have no idea which property to focus on. GOOD is more smooth because the positional difference of two consecutive points is at most two (move up/down one pixel, then move left/right on pixel), whereas BAD forces the sampler to go all the way left to the beginning of the next line. I suppose the smoother the better, because pixels on a picture generally have space continuousness. The Hilbert curve seems even better than GOOD, by the way! $\endgroup$ – nalzok Apr 21 '19 at 7:28
  • $\begingroup$ en.wikipedia.org/wiki/Image_quality $\endgroup$ – Bulat Apr 21 '19 at 7:42
  • $\begingroup$ (I mis"read" your BAD sketch, seeing horizontal scans alternating in direction. I can see worse, now.) $\endgroup$ – greybeard Apr 21 '19 at 7:45
  • 1
    $\begingroup$ What exactly is the definition of "effectiveness"? That sounds subjective. What is or isn't a good indicator sounds like a matter of opinion, too, if effectiveness is not clearly defined in the question. Those kinds of questions aren't a good fit here; we're looking for questions that can be objectively answered. If you're asking how to quantify effectiveness, you'll probably need to first figure out what exactly you mean by that effectiveness. $\endgroup$ – D.W. Apr 21 '19 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.