Intelligent scaling of bit-mapped graphics (Help!)

Intelligent scaling of bit-mapped graphics (Help!)

Post by David Corb » Tue, 02 Jan 1990 16:44:00



I am looking for information (programs, algorithms, references to texts)
on how to scale a bit-mapped image from one resolution to another, in an
intelligent manner.  For example, say I have an image that was 'grabbed'
from a screen with 640x400 pixels.  Now, I want to print this image at
the same size, but my printer has a higher resolution, so if I print it
without modification, it will be smaller.  

 Any suggestions at all would be appreciated.  Please send me mail,
 as I don't read this newsgroup.  Thank you very much.

--
David Corbin
Atlanta, GA
...!{akgua,allegra,amd,hplabs,ihnp4,masscomp,ut-ngp}!gatech!gitpyr!dave

 
 
 

Intelligent scaling of bit-mapped graphics (Help!)

Post by Leo 'Bols Ewhac' Schw » Tue, 02 Jan 1990 03:38:00



>I am looking for information (programs, algorithms, references to texts)
>on how to scale a bit-mapped image from one resolution to another, in an
>intelligent manner....

>David Corbin
>Atlanta, GA
>...!{akgua,allegra,amd,hplabs,ihnp4,masscomp,ut-ngp}!gatech!gitpyr!dave

        I, too, would be interested in such information.  Mail or net
postings; makes no difference to me.

        Thanks in advance.

_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
Leo L. Schwab                           ihnp4!ptsfa!well!ewhac
The Guy in The Cape                             ..or..
                                        well ---\
"Work FOR?  I don't work FOR               dual ----> !unicom!ewhac
anybody.  I'm just having fun."            hplabs -/       ("AE-wack")

 
 
 

Intelligent scaling of bit-mapped graphics (Help!)

Post by bege.. » Tue, 02 Jan 1990 14:05:00



> >I am looking for information (programs, algorithms, references to texts)
> >on how to scale a bit-mapped image from one resolution to another, in an
> >intelligent manner....

Ok, here goes.  There may be cheaper ways, but in my book there's
one *right* way.  What you have is an interpolation problem.  Imagine
your image (1st resolution) as a set of sampled data values.  What
you want is to derive other data values which are "in between" these.

What you need to do is find a surface-fitting algorithm.  You will
feed it your data as (X, Y, Z==pixel_value) tuples.  The algorithm
will fit a surface to the data.  Then you can use the surface to
compute New_Z = f(New_X, New_Y) where f is the interpolation function
as applied to the surface.

This software falls into the domain of Numerical Analysis.  I don't
know of any public domain code which I can point you to, but I know
that lots of PD NA software *does* exist.  

By the way, there will be a number of different surface-fitting
algorithms to choose from - usually differing in the order of the
polynomials used and your ability to "tension" the surface to remove
any spikey anomalies which the mathematical representation of your
original data may have introduced.  Hit your local Numerical Analyst
for guidance here.

Good luck!

-------
        Of all the things I've lost, I miss my mind the most.

Michael L. Begeman              Microelectronics and Computer Technology Corp
Software Technology Program     Austin (where the sun always shines) Texas

uucp:   {ihnp4, seismo, harvard, gatech, pyramid}!ut-sally!im4u!milano!begeman

 
 
 

Intelligent scaling of bit-mapped graphics (Help!)

Post by sjrapap.. » Tue, 02 Jan 1990 01:14:00




>>I am looking for information (programs, algorithms, references to texts)
>>on how to scale a bit-mapped image from one resolution to another, in an
>>intelligent manner....

A simple but expensive way:  map each new pixel onto the spot corresponding
to its centre on the old image.  Average the colors of all pixels that are
covered, weighting the average by area covered.  You now have a sloppy-looking
reproduction of your original image.  Most of the errors are high-frequency
noise, though, so you can clean it up a lot by running it through
a digital low-pass filter.  There it is.

I've never tried this myself, but it sounds feasible.  


 
 
 

Intelligent scaling of bit-mapped graphics (Help!)

Post by mich.. » Tue, 02 Jan 1990 14:46:00


Reminder: the subject is resampling "bitmaps" (i.e. single bit pixels).

A couple of the recent postings were addressing pixel arrays in general.

 
 
 

Intelligent scaling of bit-mapped graphics (Help!)

Post by sierc.. » Tue, 02 Jan 1990 15:03:00



> Reminder: the subject is resampling "bitmaps" (i.e. single bit pixels).

> A couple of the recent postings were addressing pixel arrays in general.

Lissen, fella -- ya gotta say whatcha mean! You didn't say 1-bit pixels.

Bitmap refers to the fact that there is a portion of memory mapped
to the screen device. we don't say "byte-map" or "word-map". GET IT?

--


        UUCP:   ut-sally!im4u!milano!sierchio

        "WE REVERSE THE RIGHT TO SERVE REFUSE TO ANYONE"

 
 
 

Intelligent scaling of bit-mapped graphics (Help!)

Post by kture.. » Tue, 02 Jan 1990 12:59:00



> > >I am looking for information (programs, algorithms, references to texts)
> > >on how to scale a bit-mapped image from one resolution to another, in an
> > >intelligent manner....

> What you need to do is find a surface-fitting algorithm.  You will
> feed it your data as (X, Y, Z==pixel_value) tuples.  The algorithm
> will fit a surface to the data.  Then you can use the surface to
> compute New_Z = f(New_X, New_Y) where f is the interpolation function
> as applied to the surface.

True, but I think overly complex. Simply consider the problem as a pair of
2D passes ... to go from m*n to M*N, use a pass in X to interpolate the m
values into M, then another pass in Y interpolate those results from n to N.

You can use cubic interpolation if you like, but linear suffices visually.
In fact, you can cheat on that too ...

Consider the case where you wish to triple the width and height of the image,
Our usual resolution is 512*484. But to save time in tests, we'll compute at
"ninth res" and scale up to something close enough to 512*484. Using code in
the Ikonas bitslice, we can do the scale in a couple of seconds.

So here's what your pixels look like in the original scan line:

                abcde

And this is what you want to end up with (I chose to interpolate only):

                aIJbIJcIJdIJe

where I and J are interpolated values. Using linear interpolation, we get

                I = (2 * a + b) / 3
                J = (a + 2 * b) / 3

To avoid the division, I cheated, and used

                I = (3 * a + b) / 4     [really I = (a + a + a + b) >> 2]
                J = (a + 3 * b) / 4     [really J = (a + b + b + b) >> 2]

Visually, one could not tell which of the two methods was used (and our
animators have good eyes for such things!). As a simple example, suppose
a=1 and b=4. You'd expect the values for I and J to be 2 and 3 respectively.
And that's what the first method gives. The other method produces I=1.75
and J=3.25 ... the sum of a+I+J+b is the same however, and that's one reason
why the difference is negligible. Other factors include the way the pixels
are displayed on the screen (they cover more area than they should, and mix
together anyway).

Kevin M Tureski
Omnibus/Abel
2180 Yonge St. Toronto, Ontario, Canada  M4S 2B9

UUCP:   {allegra,decvax,ihnp4,utcsri}!watmath!omnitor!ktureski
QUOTE:  But some day you will be old enough to start reading fairy tales again.
                                                                   C. S. Lewis

 
 
 

Intelligent scaling of bit-mapped graphics (Help!)

Post by Tony Parkhur » Tue, 02 Jan 1990 14:48:00


I was unable to directly mail to you so here is a copy of the letter
I tried to send.  After seeing other responses to your request,
I think you will prefer this method due to the simplicity and
lower CPU required for the task.  However, some may argue that
this is not the proper method, but I think it will generate
acceptable results.  Have fun.

-----------------------(undelivered letter)-------------------------

     Your in luck, I just devised a simple agorithm to resize any
arbitrary size image to 640x400 for my Amiga.  You should not have any
problem modifying it to size the 640x400 images up to whatever
resolution you are using.  (simply change the 640x400 constants to your
final resolution, and change 'xsize' and 'ysize' to 640x400.)  Feel free
to use as you wish as long as not for huge profits (unless I get a share
:-) (also, if you are making a public domain printer driver, feel free
to use it.)

     First, a couple of caveats:

1  --  This algorithm does pixel averaging, therefore, when resizing to
       a lower resolution (not your case), it behave like a low-pass
       filter, and you will tend to lose fine detail.

2  --  depending on the actual ratio of sizing up, there may or may
       not be artifacts.  Try it and see how it looks.

3  --  The resizing is done first horizontally then vertically, therefore
       it is possible that some artifacts will be introduced at this level
       but it is not likely to make much difference.

        The program itself takes 4 input files (header, red, green and blue)
of arbitrary size(the header file has the size in it) where each pixel is
24 bits (8 bits red, 8 bits green and 8 bits blue) and outputs one file
which is 640x400 (but still has 24-bits per pixel aranged in the file
as  ...rgbrgbrgbrgbrgb...).  The output is like this becuase then I
run it into a different filter for dithering and diffusing etc.  It
should not be hard to modify for any reasonable format.

        The algorithm works like this (this is a conceptual model only,
the implementation is a little simpler) if my input has a res of 1197x872,
and my output is 640x400, I take the row of 1197 pixels and stretch it out
640 times, so there are 640 of the first pixel, 640 of the next and so forth.
Then, for output, I gather up 1197 pixels (add them together and divide by
1197) then output one pixel (I do this 640 times).  See how
640x1197 == 1197x640.  I do the same thing for rows (872 ==> 400).
Technically, the horizontal is resized before the verticle so there may
be additional artifacts, but not too likely.

     The implementation doesn't bother stretching the pixels since we
can assume that the pixels are replicas (that is part of the premise)
so, all we have to do is keep kounts of what we need and what we have.
hopefully, this will explain most of the inner workings of the program.

Also, only integer math is used, so it is pretty efficient and accurate,
and 32-bit integers should be uses (instead of 16-bit) because
1197 * 255 (max pixel value) > 32567.  However, since you will be working
with 4 bits per pixel (or whatever), you may be able to use 16-bit ints.

Lotsa luck ---  here is a shar file...

-----------------------------------------------------------------------

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#       picomp.c
# This archive created: Wed Jan 14 10:21:33 1987
export PATH; PATH=/bin:/usr/bin:$PATH
echo shar: "extracting 'picomp.c'" '(3473 characters)'
if test -f 'picomp.c'
then
        echo shar: "will not over-write existing file 'picomp.c'"
else
sed 's/^        X//' << \SHAR_EOF > 'picomp.c'
        X/*   Copyright (c) 1987  Tony Parkhurst   */
        X
        X/*     This may be used for non-profit only and copyright notice
        X    should remain intact.  Usual courtesy and customs.
        X    Feel free to include this in other non-profit software,
        X    but usual credit where due please.
        X*/
        X
        X/* picomp takes the image files of various sizes and compresses them
        X   to a 640 by 400 rgb image. */
        X
        X/* Usage: picomp image */
        X/* inputs are image.red image.green image.blue image.header,
        X   outputs image.rgb (640x400 rbyte, gbyte bbtye).  */
        X
        X/* basic algorithm is:  if image is 1197 x 942, then
        X   each of 1197 pixels is stretched out 640 times, then 1197
        X   are gathered at a time for 640 outputs... */
        X
        X#include <stdio.h>
        X
        X#define HRES 1280
        X#define VRES 1024
        X#define HAMI 640
        X#define VAMI 400
        X
        X
        X#define MIN(x,y) (x<y?x:y)
        X
        Xmain(argc,argv)
        Xint argc;
        Xchar *argv[];
        X{
        X
        Xint x,y,i,j,c,ik,ir,ig,ib,ok,or,og,ob,kount,xsize,ysize;
        Xint i_r[HAMI],i_g[HAMI],i_b[HAMI];
        Xint o_r[HAMI],o_g[HAMI],o_b[HAMI];
        Xint r,g,b,o_k,i_k;
        XFILE *fr,*fg,*fb,*fh,*frgb,*fopen();
        Xchar   nr[25],ng[25],nb[25],nh[25],nrgb[25];
        X
        Xif(argc < 2){
        X       fprintf(stderr,"Usage: %s image\n",argv[0]);
        X       exit(-2);
        X       }
        X
        X/* open the five files */
        Xsprintf(nr,"%s.red",argv[1]);
        Xsprintf(ng,"%s.green",argv[1]);
        Xsprintf(nb,"%s.blue",argv[1]);
        Xsprintf(nh,"%s.header",argv[1]);
        Xsprintf(nrgb,"%s.rgb",argv[1]);  /* this is for output */
        X
        Xfr=fopen(nr,"r");
        Xfg=fopen(ng,"r");
        Xfb=fopen(nb,"r");
        Xfh=fopen(nh,"r");
        Xfrgb=fopen(nrgb,"w");
        X
        Xif (fr == NULL || fg == NULL || fb == NULL || fh == NULL || frgb == NULL){
        X       perror("picomp: can't open file.\n");
        X       exit(-1);
        X       }
        X
        X/* get the size of the image */
        Xysize= getc(fh) + (int)getc(fh) * 256 ;
        Xxsize= getc(fh) + (int)getc(fh) * 256 ;
        X
        X
        Xi_k = 0;  /* init input row count */
        Xfor(y=0;y<VAMI;y++){
        X       for(x=0;x<HAMI;x++){
        X               o_r[x] = 0;
        X               o_g[x] = 0;
        X               o_b[x] = 0;
        X               o_k = ysize;
        X               }
        X      
        X       while(o_k){  /* while need more kounts */
        X               if(!i_k){  /* if none left, get another row */
        X                       i_k = VAMI;  /* 400 rows */
        X
        X       ik=0; /* init input pixel count */
        X       for(x=0;x<HAMI;x++)
        X               {
        X               or = 0; /* init pix holders */
        X               og = 0;
        X               ob = 0;
        X               ok = xsize;  /* kount needed for outputting */
        X               while(ok){
        X                       if(!ik){  /* no input, need another pixel */
        X                               ik = HAMI;  /* 640 kounts per pixel */
        X                               ir = getc(fr); /* get new pixel value */
        X                               ig = getc(fg);
        X                               ib = getc(fb);
        X                               } /* if (!ik) */
        X                       kount = MIN(ok,ik); /* which is smaller */
        X                       ok -= kount; /* knock off kount */
        X                       ik -= kount;
        X                       or += kount * ir;  /* add in kount pixel values */
        X                       og += kount * ig;
        X                       ob += kount * ib;
        X                       } /* while (ok) */
        X               /* ok, now average out the pixels for output */
        X               i_r[x] = or / xsize;
        X               i_g[x] = og / xsize;
        X               i_b[x] = ob / xsize;
        X               } /* for x */
        X
        X                       } /* if (!i_k) */
        X               kount = MIN(o_k,i_k); /* which is smaller */
        X               o_k -= kount; /* knock off kount */
        X               i_k -= kount;
        X               for(x=0;x<HAMI;x++){
        X                       o_r[x] += kount * i_r[x];  /* add in kount row values */
        X                       o_g[x] += kount * i_g[x];
        X                       o_b[x] += kount * i_b[x];
        X                       } /* for x */
        X               } /* while(o_k) */
        X       for(x=0;x<HAMI;x++){
        X               r = o_r[x] / ysize;  /* now average out for output */
        X               g = o_g[x] / ysize;
        X               b = o_b[x] / ysize;
        X
        X               if(r > 255 || r < 0){
        X                       fprintf(stderr,"Warning:  Red component out of range: %d\n",r);
        X                       }
        X               if(g > 255 || g < 0){
        X                       fprintf(stderr,"Warning:  Green component out of range: %d\n",g);
        X                       }
        X               if(b > 255 || b < 0){
        X                       fprintf(stderr,"Warning:  Blue component out of range: %d\n",b);
        X                       }
        X              
        X               putc(r,frgb);
        X               putc(g,frgb);
        X               putc(b,frgb);
        X
        X               }
        X
        X       } /* for y */
        X}
SHAR_EOF
if test 3473 -ne "`wc -c < 'picomp.c'`"
then
        echo shar: "error transmitting 'picomp.c'" '(should have been 3473 characters)'
fi
fi
exit 0
#       End of shell archive

--
**************** Insert 'Standard' Disclaimer here:  OOP ACK! *****************
*      Tony Parkhurst -- {hplabs|sdcsvax|ncr-sd|hpfcla|ihnp4}!hp-sdd!adp      *
*                        OR   hp-sdd!...@nosc.arpa                            *
*******************************************************************************

 
 
 

1. Scaling algorithms needed for bit-mapped images

Can anybody recommend good algorithms for scaling bit-mapped images.
Let's suppose I have an array, 512x512, which is the image, and I know
that I want to scale it to 2000x2000.  What would be the best algorithm
for scaling.  I have heard that using the sin x/x (sinc) function, then
applying a high pass filter works well.  What I need is some sample
source code to do this, or even references to books that explain this.

Any thoughts on this?

Mike McWhinney
Elja, Inc.

--
========================================================================
ELJA, Inc.  TEL: (414) 357-6771   FAX: (414) 357-9394

========================================================================

2. Graph relax Alg.

3. WANTED: bit map scaling

4. WIDESPREAD INCOMPETENCE AT BELL ATLANTIC

5. Bit map scaling

6. Invitation to Join a Guild of Christian Game-Software Authors

7. Bit map Scaling

8. Video/Audio animation suggestions for PC?

9. Scaling algorithms needed for bit-mapped images

10. Howto: copy 8 bit gray-scale pixmap in alpha channel of 32 bit pixmap

11. HELP Upgrading 8-bit INDY to 24-bit graphics

12. Intelligent conversion of colour to 1 bit?

13. Scaling bitmapped images - help wanted