dave@gitpyr.gatech.EDU (David Corbin) (01/13/87)
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!daveewhac@well.UUCP (Leo 'Bols Ewhac' Schwab) (01/15/87)
In article <2872@gitpyr.gatech.EDU> dave@gitpyr.gatech.EDU (David Corbin) writes: >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")
begeman@milano.UUCP (01/15/87)
> In article <2872@gitpyr.gatech.EDU> dave@gitpyr.gatech.EDU (David Corbin) writes: > >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 arpa: begeman@mcc.com
sjrapaport@watcgl.UUCP (01/16/87)
In article <2406@well.UUCP> ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab) writes: >In article <2872@gitpyr.gatech.EDU> dave@gitpyr.gatech.EDU (David Corbin) writes: >>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. -steve @ watcomputer
michael@orcisi.UUCP (01/16/87)
Reminder: the subject is resampling "bitmaps" (i.e. single bit pixels). A couple of the recent postings were addressing pixel arrays in general.
sierchio@milano.UUCP (01/17/87)
In article <776@orcisi.UUCP>, michael@orcisi.UUCP writes: > 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? -- Michael Sierchio @ MCC Software Technology Program UUCP: ut-sally!im4u!milano!sierchio ARPA: sierchio@mcc.ARPA "WE REVERSE THE RIGHT TO SERVE REFUSE TO ANYONE"
ktureski@omnitor.UUCP (01/19/87)
> > In article <2872@gitpyr.gatech.EDU> dave@gitpyr.gatech.EDU (David Corbin) writes: > > >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
adp@hp-sdd.HP.COM (Tony Parkhurst) (01/19/87)
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!adp@nosc.arpa *
*******************************************************************************