## 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)