Monday, August 24, 2009

Image scaling and GCD (greatest common divisor)

Whilst embedding an image in a wiki page I found it was too big (wide) and therefore caused lots of layout issues. The obvious solution to this was to scale the image (by editing the HTML and adding a style attribute style="width:80%;") unfortunately this caused the image (a diagram) to be unreadable - due to image artefacts.

After looking at the image properties, I saw the cause of problem - its dimensions (865 x 596). As there is no common divisor of these two numbers there is now way to scale it down without one of the dimensions being rounded - for example at a scale of ½ the dimensions become (432.5 x 298). And you can't have half a pixel...

So I suspect (intuitively rather than by proof) that images scale best if they have a GCD (greatest common divisor), a quick port of the binary GCD from wikipedia in C#:

        static uint gcd(uint u, uint v)
        {
            int shift;

            /* GCD(0,x) := x */
            if (u == 0 || v == 0)
                return u | v;

            /* Let shift := lg K, where K is the greatest power of 2
               dividing both u and v. */
            for (shift = 0; ((u | v) & 1) == 0; ++shift)
            {
                u >>= 1;
                v >>= 1;
            }

            while ((u & 1) == 0)
                u >>= 1;

            /* From here on, u is always odd. */
            do
            {
                while ((v & 1) == 0)  /* Loop X */
                    v >>= 1;

                /* Now u and v are both odd, so diff(u, v) is even.
                   Let u = min(u, v), v = diff(u, v)/2. */
                if (u < v)
                {
                    v -= u;
                }
                else
                {
                    uint diff = u - v;
                    u = v;
                    v = diff;
                }
                v >>= 1;
            } while (v != 0);

            return u << shift;
        }
Port of code from wikipedia

1 comment:

fe said...

ok before anyone beats me up on this, yes you can have half a pixel - but its not pretty (see ClearType and sub-pixel text rendering)