Searching \ for '[OT] Image rescaling algorithm' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=image+rescaling
Search entire site for: 'Image rescaling algorithm'.

Exact match. Not showing close matches.
PICList Thread
'[OT] Image rescaling algorithm'
2010\11\30@114732 by Isaac Marino Bavaresco

flavicon
face
Fellow listers,


I just published an algorithm I created to rescale images on my personal
page at piclist.com:
<http://www.piclist.com/Techref/member/IMB-yahoo-J86/image-rescale.htm>.

I think I am the first to invent it, but I may be wrong.

Any comments or reviews are welcome.


Best regards,

Isaac

__________________________________________________
Fale com seus amigos  de graça com o novo Yahoo! Messenger http://br.messenger.yahoo.com

2010\11\30@121433 by Mike Harrison

flavicon
face
On Tue, 30 Nov 2010 14:47:32 -0200, you wrote:

>Fellow listers,
>
>
>I just published an algorithm I created to rescale images on my personal
>page at piclist.com:
><http://www.piclist.com/Techref/member/IMB-yahoo-J86/image-rescale.htm>.
>
>I think I am the first to invent it, but I may be wrong.
>
>Any comments or reviews are welcome.

"I developed this algorithm to run efficiently on platforms without hardware floating-point support"

Why would anyone use floating point for image rescaling...?

2010\11\30@121628 by Olin Lathrop

face picon face
Isaac Marino Bavaresco wrote:
> I just published an algorithm I created to rescale images on my
> personal page at piclist.com:
> <http://www.piclist.com/Techref/member/IMB-yahoo-J86/image-rescale.htm>.
>
> I think I am the first to invent it, but I may be wrong.

Image processing and image scaling has been around for a long time.
Unfortunately the link you posted just goes to some source code.  Please
describe your algorithm so we can evaluate it.

The trick with image scaling is to not introduce aliasing when shrinking and
to not just replicate pixels when expanding.  For example, my IMAGE_RESIZE
program uses bi-cubic interpolation when expanding, and cosine squared
convolution when shrinking.


********************************************************************
Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
(978) 742-9014.  Gold level PIC consultants since 2000

2010\11\30@121833 by Olin Lathrop

face picon face
Mike Harrison wrote:
> Why would anyone use floating point for image rescaling...?

For lots of good reasons.  On many modern computers, floating point is not
much slower than interger operations, and is a obvious easy way to get a
essentially continuous brightness space with overflow and underflow handled..


********************************************************************
Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
(978) 742-9014.  Gold level PIC consultants since 2000

2010\11\30@124808 by Isaac Marino Bavaresco

flavicon
face
Em 30/11/2010 15:17, Olin Lathrop escreveu:
> Isaac Marino Bavaresco wrote:
>> I just published an algorithm I created to rescale images on my
>> personal page at piclist.com:
>> <www.piclist.com/Techref/member/IMB-yahoo-J86/image-rescale.htm>.
>>
>> I think I am the first to invent it, but I may be wrong.
> Image processing and image scaling has been around for a long time.
> Unfortunately the link you posted just goes to some source code.  Please
> describe your algorithm so we can evaluate it.

The comments try to explain the algorithm. As you can see, there are
more comments than C code there.
Some diagrams would help the understanding, but unfortunately I couldn't
spend any time on them yet.

> The trick with image scaling is to not introduce aliasing when shrinking and
> to not just replicate pixels when expanding.  For example, my IMAGE_RESIZE
> program uses bi-cubic interpolation when expanding, and cosine squared
> convolution when shrinking.

The goal of this algorithm was to be fast. It was conceived to do
anisotropic scaling on gray-scale images, to correct deformations
introduced by a prism and to bring its resolution (DPI) to a standard value..

For instance, the image's resolution was 352 DPI (X) by 560 DPI (Y), and
we needed the resolution to be 500 DPI on both axis. So we used this
algorithm to stretch on the X axis and shrink on the Y axis at the same
time.

Just for comparison, running in an ARM9 at 400MHz, another algorithm
using floating-point spent 1.5s to do the job, this algorithm took
around 50ms.


Isaac

__________________________________________________
Fale com seus amigos  de graça com o novo Yahoo! Messenger http://br.messenger.yahoo.com

2010\11\30@125126 by Dave Tweed

face
flavicon
face
Isaac Marino Bavaresco wrote:
> I just published an algorithm I created to rescale images on my personal
> page at piclist.com:
> <http://www.piclist.com/Techref/member/IMB-yahoo-J86/image-rescale.htm>.

Can't you express your algorithm in anything other than source code?
It's very difficult to pick an algorithm out of a specific implementation.
How about some math or diagrams?

> I think I am the first to invent it, but I may be wrong.
> Any comments or reviews are welcome.

It looks like a very roundabout way to do ordinary linear interpolation,
but it's hard to be sure. Normally, you'd just iterate over the destination
pixels and interpolate among the nearest four source pixels.

-- Dave Twee

2010\11\30@134322 by Isaac Marino Bavaresco

flavicon
face
Em 30/11/2010 15:51, Dave Tweed escreveu:
> Isaac Marino Bavaresco wrote:
>> I just published an algorithm I created to rescale images on my personal
>> page at piclist.com:
>> <www.piclist.com/Techref/member/IMB-yahoo-J86/image-rescale.htm>.
> Can't you express your algorithm in anything other than source code?
> It's very difficult to pick an algorithm out of a specific implementation..
> How about some math or diagrams?


Yes, I can. Unfortunately I hadn't the time to draw some nice diagrams
(I did, but only on paper, by hand) explaining what is happening with
source and destination pixels.
When I get some spare time I will create some descriptive material.


>> I think I am the first to invent it, but I may be wrong.
>> Any comments or reviews are welcome.
> It looks like a very roundabout way to do ordinary linear interpolation,
> but it's hard to be sure. Normally, you'd just iterate over the destination
> pixels and interpolate among the nearest four source pixels.
>
> -- Dave Tweed


The goal here is to minimize operations. As you can see, there is no
division inside the loops, and the multiplications are kept to a minimum.


Isaac



__________________________________________________
Fale com seus amigos  de graça com o novo Yahoo! Messenger http://br.messenger.yahoo.com

2010\11\30@163844 by Isaac Marino Bavaresco

flavicon
face
part 1 4541 bytes content-type:text/plain; charset="iso-8859-1" (decoded quoted-printable)

OK, here is an explanation of my algorithm:


I will explain how the rescaling is done for one line of pixels (width)
in a gray-scale image. The rescaling on the height follows the same
principle.

First, let's imagine that both images have the same width (units of
measure) but different number of pixels, so the pixels of the image with
less pixels are wider than the pixels of the image with more pixels.

The width of the pixels of the destination image is always 1.0, so if we
are enlarging the image (increasing the number of pixels), then the
width of the pixels of the source image is greater than 1.0. If we are
shrinking (reducing the number of pixels), then the width of the pixels
of the source image is smaller than 1.0.

Let's suppose we want to enlarge one line from 3 pixels to 5 pixels. We
must pair both the source and destination pixels: (fig. 1)

After pairing, we must imagine additional borders inside pixels (dotted
lines), mirroring the borders between the pixels of the other line
(source or destination), effectively creating sub-pixels. (fig. 2)

The width of each sub-pixel is the width of the intersection between the
source and destination pixel that it covers.

The value of each destination pixel is the sum of one or more
sub-pixels. The contribution of each sub-pixel to the intensity of the
destination pixel is the sub-pixel width multiplied by the intensity of
the source pixel that contains it.

For instance, destination pixel D1 is composed by only one sub-pixel (S1
* 1.0).
Destination pixel D2 is composed by two sub-pixels ( S1 * 0.66 + S2 *
0.33 ).
And so on.

The sum of the width of all sub-pixels that compose each destination
pixel is always 1.0, so we don't need to do a division, just sum the
products of the sub-pixel widths by the origin pixel values.


Algorithmically:

fws = 1.6;    // Width of the source pixel
fwd = 1.0;    // Width of the destination pixel
acc    = 0;   // Accumulator
si    = 0;    // Source pixel index
di    = 0;    // Destination pixel index

while( di < dstimgwidth ){
   fw  = min( fws, fwd );     // Sub-pixel width
   acc    += srcimg[si] * fw; // Add the sub-pixel contribution

   fws -= fw;                 // Subtract the already used portion of
the source pixel

   if( fws == 0 ){            // Current source pixel exausted
       fws = 1.6;             // Reload source pixel width
       si++;                  // Next source pixel
   }

   fwd -= fw;                 // Subtract the already used portion of
the destination pixel

   if( fwd == 0 ){            // Finished calculation of current
destination pixel
       fwd = 1.0;             // Reload destination pixel width
       dstimg[di] = acc;      // Save calculated destination pixel
       di++;                  // Next destination pixel
       acc = 0;               // Zero accumulator for next destination
pixel
   }
}



Best regards,

Isaac



Em 30/11/2010 16:43, Isaac Marino Bavaresco escreveu:
{Quote hidden}


part 2 10575 bytes content-type:image/jpeg; name="figure 1.jpg" (decode)


part 3 14406 bytes content-type:image/jpeg; name="figure 2.jpeg" (decode)


part 4 181 bytes content-type:text/plain; name="ATT00001.txt"
(decoded base64)

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2010\11\30@170201 by Olin Lathrop

face picon face
Isaac Marino Bavaresco wrote:
> The value of each destination pixel is the sum of one or more
> sub-pixels. The contribution of each sub-pixel to the intensity of the
> destination pixel is the sub-pixel width multiplied by the intensity
> of the source pixel that contains it.

So you're box filtering.  The contribution from whatever parts of whatever
input pixels overlay a output pixels are just averaged, and nothing outside
a output pixel contributes to its value.  That's definitely better than
point sampling, and will be good enough for some purposes.

What will you be doing with the rescaled images?


********************************************************************
Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
(978) 742-9014.  Gold level PIC consultants since 2000

2010\11\30@180955 by Isaac Marino Bavaresco

flavicon
face
Em 30/11/2010 20:02, Olin Lathrop escreveu:
> Isaac Marino Bavaresco wrote:
>> The value of each destination pixel is the sum of one or more
>> sub-pixels. The contribution of each sub-pixel to the intensity of the
>> destination pixel is the sub-pixel width multiplied by the intensity
>> of the source pixel that contains it.
> So you're box filtering.  The contribution from whatever parts of whatever
> input pixels overlay a output pixels are just averaged, and nothing outside
> a output pixel contributes to its value.  That's definitely better than
> point sampling, and will be good enough for some purposes.
>
> What will you be doing with the rescaled images?


They are fingerprint images for biometric identification.


Isaac
__________________________________________________
Fale com seus amigos  de graça com o novo Yahoo! Messenger http://br.messenger.yahoo.com

2010\11\30@214912 by M. Adam Davis

face picon face
On Tue, Nov 30, 2010 at 6:09 PM, Isaac Marino Bavaresco
<spam_OUTisaacbavarescoTakeThisOuTspamyahoo.com.br> wrote:
> Em 30/11/2010 20:02, Olin Lathrop escreveu:
>> What will you be doing with the rescaled images?
>
> They are fingerprint images for biometric identification.

Doesn't the final fingerprint algorithm convert the image to a vector,
or pseudo-vector image?  Perhaps one can skip the image processing
step if one updates the vector conversion routine to handle various
input sizes.

-Ada

2010\11\30@222746 by Isaac Marino Bavaresco

flavicon
face
Em 1/12/2010 00:49, M. Adam Davis escreveu:
> On Tue, Nov 30, 2010 at 6:09 PM, Isaac Marino Bavaresco
> <.....isaacbavarescoKILLspamspam@spam@yahoo.com.br> wrote:
>> Em 30/11/2010 20:02, Olin Lathrop escreveu:
>>> What will you be doing with the rescaled images?
>> They are fingerprint images for biometric identification.
> Doesn't the final fingerprint algorithm convert the image to a vector,
> or pseudo-vector image?  Perhaps one can skip the image processing
> step if one updates the vector conversion routine to handle various
> input sizes.
>
> -Adam


The algorithm expects the images to have the same resolution on both
axis. It suffers a lot of processing before it is vectorized and the
minutiae are extracted.

It is fact that processing images with different resolutions (enrolling
with one resolution and matching with another) difficults slightly the
identification, even if the different resolutions are accounted for
(compensated).

I agree that perhaps it may be possible to correct the aspect ratio
after the image is vectorized, but I don't know if it won't compromise
the quality of the resulting data.


Best regards,

Isaac

__________________________________________________
Fale com seus amigos  de graça com o novo Yahoo! Messenger http://br.messenger.yahoo.com

2010\11\30@234858 by RussellMc

face picon face
My friend Ken says

There are some very good image scaling (and other transformations)
algorithms on the AntiGrain website.

As it's name suggests, it is dedicated to eliminating (or at least
minimising as far as possible) the granularity imposed by the discrete
pixel nature of digital images.

There are both C and Pascal implementations of most of the algorithms
- many with pre-compiled demos to download and run

More... (looser matching)
- Last day of these posts
- In 2010 , 2011 only
- Today
- New search...