Post by thread:[OT] Image rescaling algorithm

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

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...?

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

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

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

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

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

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}> 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/ 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

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

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

On Tue, Nov 30, 2010 at 6:09 PM, Isaac Marino Bavaresco <spam_OUTisaacbavarescoTakeThisOuTyahoo.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

Em 1/12/2010 00:49, M. Adam Davis escreveu: > On Tue, Nov 30, 2010 at 6:09 PM, Isaac Marino Bavaresco > <.....isaacbavarescoKILLspam@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

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