jgro@lia (Jeremy Grodberg) (10/18/90)
Does anyone have any references on raster image scaling that is *FAST*, even if it is slightly non-optimal. I need to do arbitrary scaling of 1-bit-per-pixel images as fast as possible, and am not too concerned with optimum averaging or stuffing of the reduced or expanded pixels. What I am concerned with is scaling a 2MB source image in 1-2 seconds on a SPARCstation. Note that I can't take advantage of simple power-of-2 optimizations. I know how to do this in a slow and laborious way, but how can this be done quickly and efficiently? -- Jeremy Grodberg "I don't feel witty today. Don't bug me." jgro@lia.com
falk@peregrine.Sun.COM (Ed Falk) (10/19/90)
In article <1990Oct18.014905.1846@lia> jgro@lia.com (Jeremy Grodberg) writes: > >Does anyone have any references on raster image scaling that is *FAST*, >even if it is slightly non-optimal. I need to do arbitrary scaling of >1-bit-per-pixel images as fast as possible, and am not too concerned with >optimum averaging or stuffing of the reduced or expanded pixels. What I >am concerned with is scaling a 2MB source image in 1-2 seconds on a >SPARCstation. Note that I can't take advantage of simple power-of-2 >optimizations. What you obviously want to do is drop rows and columns out of the image. The "simple power-of-2" method you refer to is the most obvious one, simply drop alternate rows and columns: for(i=0; i<out_height; ++i) for(j=0; j<out_width; ++j) output[i][j] = input[i*2][j*2] for other scale factors, you want to make a sort of Bresenham walk through the input. int iw,ih ; /* size of input image */ int ow,oh ; /* size of output image */ int ix,iy ; /* indices into input image */ int ox,oy ; /* indices into output image */ int cx,cy ; /* counters */ cx = -iw/2 ; cy = -ih/2 ; iy = ix = 0 ; for(oy=0; oy<oh; ++oy) { for(ox=0; ox<ow; ++ox) { output[oy][ox] = input[iy][ix] ; cx += iw ; while( cx > 0 ) { ++ix ; cx -= ow ; } } cy += ih ; while( cy > 0 ) { ++iy ; cy -= oh ; } } This should work for scaling in either direction. I haven't tried it. -ed falk, sun microsystems sun!falk, falk@sun.com card-carrying ACLU member.
dal@syntel.syntel.mn.org (Dale A. Schumacher) (10/20/90)
The following pseudo-code is from a rough draft of a paper I'm preparing for inclusion in Graphics Gems '91. It is in the public domain. src_x_size: integer; src_y_size: integer; source: array[0..src_x_size-1] of array[0..src_y_size-1] of pixel; dst_x_size: integer; dst_y_size: integer; destination: array[0..dst_x_size-1] of array[0..dst_y_size-1] of pixel; sx, sy, dx, dy: integer; begin dx <- 0; dy <- 0; while dy < dst_y_size do sy <- ((dy * src_y_size) / dst_y_size); while dx < dst_x_size do sx <- ((dx * src_x_size) / dst_x_size); destination[dx][dy] <- source[sx][sy]; endloop; endloop; end; ..... Dale Schumacher 399 Beacon Ave. .: .: (alias: Dalnefre') St. Paul, MN 55104-3527 ..:.. : nic.mr.net!bungia.mn.org!syntel!dal United States of America : :.:.: "The Bandit, master of the quick comeback, the left-handed compliment, :. :. and the subtle jab, the most dangerous verbal assassin in Arcadia, :...: dimly heard his higher reasoning faculties shut down." -metlay
rick@pangea.Stanford.EDU (Rick Ottolini) (10/26/90)
In article <A1346770260@syntel.syntel.mn.org> dal@syntel.syntel.mn.org (Dale A. Schumacher) writes: >The following pseudo-code is from a rough draft of a paper I'm preparing >for inclusion in Graphics Gems '91. It is in the public domain. > > >src_x_size: integer; >src_y_size: integer; >source: array[0..src_x_size-1] of array[0..src_y_size-1] of pixel; >dst_x_size: integer; >dst_y_size: integer; >destination: array[0..dst_x_size-1] of array[0..dst_y_size-1] of pixel; >sx, sy, dx, dy: integer; > >begin > dx <- 0; > dy <- 0; > while dy < dst_y_size do > sy <- ((dy * src_y_size) / dst_y_size); > while dx < dst_x_size do > sx <- ((dx * src_x_size) / dst_x_size); > destination[dx][dy] <- source[sx][sy]; > endloop; > endloop; >end; Two problems (at least): (1) When shrinking the high freqyency components of an image must be removed or else aliasing will result. A fast way to do this is to smooth with a (rectangular) window the degree of compression. (2) Pre-computing each axis of of sx and sy is even faster than above.
dal@com50.c2s.mn.org (Dale Schumacher) (10/29/90)
In article <1990Oct26.011905.16187@morrow.stanford.edu> rick@pangea.Stanford.EDU (Rick Ottolini) writes: >In article <A1346770260@syntel.syntel.mn.org> dal@syntel.syntel.mn.org (Dale A. Schumacher) writes: >>The following pseudo-code is from a rough draft of a paper I'm preparing >>for inclusion in Graphics Gems '91. It is in the public domain. >> >> >>src_x_size: integer; >>src_y_size: integer; >>source: array[0..src_x_size-1] of array[0..src_y_size-1] of pixel; >>dst_x_size: integer; >>dst_y_size: integer; >>destination: array[0..dst_x_size-1] of array[0..dst_y_size-1] of pixel; >>sx, sy, dx, dy: integer; >> >>begin >> dx <- 0; >> dy <- 0; >> while dy < dst_y_size do >> sy <- ((dy * src_y_size) / dst_y_size); >> while dx < dst_x_size do >> sx <- ((dx * src_x_size) / dst_x_size); >> destination[dx][dy] <- source[sx][sy]; >> endloop; >> endloop; >>end; > >Two problems (at least): First of all, the original requestor was specifically interested in fast and simple methods, and was not terribly concerned with accuracy. I should have known better than to post this pseudo-code without discussing its limitations as I DO discuss in my article. >(1) When shrinking the high freqyency components of an image must be removed >or else aliasing will result. A fast way to do this is to smooth with a >(rectangular) window the degree of compression. I am aware of several more accurate zooming methods, and realize the drawbacks of this one. Compare this algorithm, however, with some other simplistic methods. How often have you seen enlarging limited to integer zoom factors because a "repeat each pixel N times" algorithm is used, or reduction by "skip every Nth pixel". This method at least has the nice properties that it scales up or down with independent scaling along each axis (nice for fixing aspect-ratio problems) from any source size to any destination size and is deceptively simple to implement. I am trying to give people no more excuses for implementing thing like "integer zoom factors only". >(2) Pre-computing each axis of of sx and sy is even faster than above. This is pseudo-code, not source code. The intent here is to make the algorithm clear, not code it for maximum efficiency. I sure hope this algorithm, with all its limitations, is useful to someone.
rick@kimbal.lynn.ma.us (Rick Kimball) (10/30/90)
From article <1990Oct29.152500.15450@com50.c2s.mn.org>, by dal@com50.c2s.mn.org (Dale Schumacher): Has anyone implemented this as a function? I did and it was realitively fast but because the algorithm doesn't do any filtering when you make an image smaller it gets distorted. I'm looking for the equivalent of the MS-Windows StretchBlt function. Does anyone have an implementation that is fast and works best with large images that are scaled to small ones. Rick Kimball | INTERNET: rick@kimbal.lynn.ma.us | UUCP: ...!spdcc!kimbal!rick, ...!spt!kimbal!rick | POTS: (617) 599-8864
hitchner@riacs.edu (Lewis Hitchner) (11/07/90)
That should hardly be called "image scaling". All you are doing is sub-sampling, not scaling. Thus, you are also incurring all the bad aliasing effects caused by reducing the sample rate of a non-band limited image. Try your algorithm on a checkerboard image and "scale" your result by 1/2n where n is the no. of pixels in each block of the checkerboard. You might want to refer to any of the standard textbooks on digital signal processing or on digital image processing for a complete explanation of correct scaling methods (most of these texts are named "Digital Signal Processing" or "Digital Image Processing" with minor variations on those names -- popular textbooks are by the authors: Pratt, Gonzales & Wintz, Anil Jain, Castleman, Oppenheim & Schafer, Rosenfeld & Kak). Lew Hitchner RIACS at NASA Ames