In C, using the most basic operators, +, -, *, >>, << etc. (no
division pls, if possible, no multiply operation), to enlarge a 2-D
image data. We need a very very fast algorithm, with only integer
involved in the process.
The input is simply a byte array of image data, let it image[x].
The problem is to multiply the width and height of image[x] by a
factor of n, so the new image will have dimension of n*width by
n*height, where n is large around 20 - 60.
We are looking for the complete C code:
Input:
image_in; // the input image data byte array. (which is an rgb image
data, 24 biy per pixel.)
image_h; // original image height
image_w; // original image width
image_out; // the output image data byte array.
scale_factor; // an integer > 1 of scale factor
.
. (please fill in)
.
// we can use the image_out data here.
Or the algorithm that we can write in C for fast 2-D intepolation. |
Request for Question Clarification by
maniac-ga
on
04 Feb 2004 15:48 PST
Hello Picco,
I read your question with quite a bit of interest, but finding an
algorithm that has
- scaling using bilinear interpolation
- integer arithmetic only (otherwise called fixed point)
- no division
- prefer no multiplication
is very hard. There does not seem to be a public implementation like
this. I certainly did a lot of similar work in the mid 70's, but it
seems to be rare today.
I can provide an answer describing
- bilinear interpolation (lots of sites - good references)
- suggestions for doing fixed point arithmetic (personal experience, a few sites)
- suggestions for avoiding multiply / divide (personal experience)
but getting source code for all that seems to be unavailable.
If this kind of answer is OK, please also indicate the constraints you
have related to
- word size (8, 16, 32, 64)
- if you can do integer multiply with double precision result
- if you can do integer divide (double precision / single precision)
== single precision result and remainder
- if you can do single precision add / subtract with carry / borrow
- if you have serious limits in storing intermediate values / auxillary data
I realize that some of these may require machine code insertions - let
me know if you need help on that as well [if so, what processor /
compiler].
I am also a little concerned about the range of image magnification
(20-60) since bilinear interpolation may cause some effects you don't
expect. If adjacent pixels are relatively close in color, it should be
OK, but let's say RED is adjacent to GREEN and BLUE (perhaps a
dithered image), the result will go through a range of colors. You may
want to comment on that issue as well.
--Maniac
|
