nonlinear antialiasing Re: [ptx] i would like to help.
juaquin anderson
anderson314159 at netscape.net
Wed Apr 14 14:47:15 BST 2004
Hi Pablo,
this is a rather long email.
i want to go over the considerations that have to do with the filter that i am going to write and how it will work into the stitcher. memory considerations is one subject. the particular programmers interface and libraries is the other subject. i will go over it in this email, which is a bit long, and then get to what exactly i need to write and debug this filter, and questions like what should the disk usage look like. i mostly wrote this to organize it for myself. you can skim to the end if you like.
i want to write the filter for flexible memory use so that it will be feasible on computers with very small memory, or for very large images. i pretty well have that worked out.
let me see if i understand the stitch program at least for the sake of the part of code that i intend to write.
the stitch program does some various things:
1)first grabs the .pto file which contains the filenames of all the input images, the parameters for the transformations, and info about the kind of output.
2)for each input image in the .pto file, the stitcher loads the image and the corresponding transformation parameters from the .pto, transforms it, producing a transformed output image which goes to disk for merging later.
the transformation involves sampling and a nonlinear mapping. the input image is sampled for each point of the output image. the loop goes over the output image pixel grid, and the transformation results in real (x,y) sample location which may result in a point between the integer pixel locations of the input image. this is where the interpolation happens, one of various kinds, nearest neighbor, bilinear, bicubic, sync, and such.
the filter would go before the remapping and be dependent on the parameters of the remapping and the grid sizes and the kind of projection.
this step depends on the kind of projection. maybe the output is planar or cylindrical or cubic or equiangular. my code will have some dependence on this. for wrap around in a cylinder, and some complexity where the mapping puts an input image across a cubes edges on the cubic projection. then theres wrap around in the cylinder, and equiangular may have funny qualities near the poles.
3) somewhere along the way there are masks produced. then there are merges by the masks. and the stitch program makes the output appropriate to the kind of projection specified in the .pto
thats basically the stitch program, if i understand correctly.
regarding the interpolation i really appreciate the link to Dersch's test rotations. very interesting. http://www.path.unimelb.edu.au/~dersch/interpolator/interpolator.html
in 2) is maybe where the code that i would write would go. it could be a subroutine call after loading an input image, before the sampling. or a command line utility applied before the remapping. a filtered version of each input image could be produced on disk, then loaded in for the mapping. if it is applied to each image, it could be a command line utility, which may be good? i think that it would be good to write it as a command line utility first so i can test it alone. i would like to do it that way first.
the filter would go in 2) just after loading the input image and before producing the output image. my code would apply a fast filter to the input image, and saying fast all depends, there are some memory use considerations. It seems like it has to somehow use floats. I haven't tried it with integers.
my code needs several things:
a) to be able to call the mapping inverse transformation function with the parameters appropriate for that particular input image. that is the transformation from the input images integer coordinates to the output image coordinates. integer to real transformation, the inverse of what the stitch program calls. i will use this not for sampling but to get a distance. i need to get it bent around the edge in the case of a cubic projections. I will write that in. i need to see what it looks like.
b) my code needs to know the exact form of the interpolation function. bicubic or bilinear may be best for my algorithm since it naturally compensates for the sync's effect.
c) of course my code needs to get hold of the input image, and to produce the filtered output image. it may be good for computers with limited ram for my code to be able to get the input image in bands twice, and produce the output in bands. if it is necessary to do the banding, i need to be able to get the last band first, and through the rest in reverse order, and then get them again in forwards order, and produce the output in forwards order as it is reading. read them twice, write the output once. not so bad for disk head movement.
d) then there may be some temp storage necessary. ideally, the image would be all in ram as single precision floats then the filter is all in place and lightning fast. otherwise there is some duplicated work. i am going to try to write it to load the image twice and produce the output once in order, if it can't do it in place.
let me tell you what this would look like. because it is important for the goals you have for memory usage. the algorithm is good in that it can be organized to use less ram in many ways. there are various possibility's. it would be good to know what your plans are if you are planning to work with images in tiles at any point in the future.
the algorithm works on the input images pixels. the fastest way of the filter is to work with the entire image as single floats and do the filter in place. for this possibility the whole image is in ram as floats.
memory requirement for the case of 6Mpixels input image:
for 6Mpixel is 24Mbytes per color plane.
the compute complexity is reasonably good, it looks like:
(number of pixels)*(4 passes)*((2 calls to inverse transformation)+(2 3d distance calcs)+(4)*(float product and sum))*(3 color planes)=(computes for the in place filter)
that is for 6mpixels:
6m*4*3*(2*inversemap()+2*distance3d()+vector4())=?
i think it will be a couple of seconds? the slowest thing is the inversemap, and the distance3d. i will see. I don't know what the inverse map looks like.
the algorithm can be restructured to work in a different order. this is done by breaking up the image into rectangles and processing them in a special order 4 times over. so it would be 4 times the above figure for timing and the time to produce the pieces and the time to load them each 4 times. this is reduced if the rectangles are horizontal bands. there it is equivalent to loading the image twice and producing the output in order.
memory requirement for this for a (sizex) by (sizey) image, broken into m by n pieces:
(3 color planes)*sizeof(single floats)*(sizex)*(sizey)/(m*n) + (m+1)*sizey + (n+1)*sizex=
so a large 6mpixel image can be feasibly filtered within a few megabytes with some disk use. the least swapping is to use horizontal bands but its different if you use tiles.
the bottom line is that compute complexity would be a couple of seconds each image and if the image must reside on disk, disk swapping would be equivalent to loading the image twice and saving the output once. the
filter is good, i tested its frequency response, for a different application, and it was very good. no aliasing. I haven't tested it for exactly this application. i think that it would be good for this application.
i want to write it and try it out in the form of a command line utility for testing, then it can be a couple of functions in the stitcher.
the input for the utility would be:
*the filename of the input image.
*the filename of the output image.
*the kind of projection.
*the parameters of the remapping, and i suppose there would be access to the remapping function library which i suppose would include an inverse mapping.
*the amount of ram to use so that my utility can organize its ram usage. sort of a figure to try to avoid sending the os into swapping.
if you could show me what you are using for the remapping. the header files and the calls. a snip of code. or a link?
there used to be image loading and saving functions when with the old sgi's. they would load and save images whole or in pieces, maybe as scan lines. it worked the same to load in any one of various formats and endians. is what you folks use like that? if you could tell me what you are using, the header files and the calls. a snip of code, or a link? i am sure there is a library for loading and saving images, maybe in pieces, thats simple to call.
i don't think that it will be more than a couple hundred lines. Its just a little complicated.
thanks for the links, and help.
maybe there is a sample code for a utility that does something with images?
thanks
Juaquin.
"Pablo d'Angelo" <pablo.dangelo at web.de> wrote:
>Hi Juaquin,
>
>> i want to help. i have alot of knowledge about algorithms and mathematics.
>>
>> i have had some experience with programming specialized pattern
>> recognition algorithms in the 80's.
>>
>> i have been trying to see where i could add to the effort. mabe i could
>> write a slick antialiasing algorithm. antialiasing is important for a
>> quality output.
>>
>> antialiasing is a tricky subject. especially where nonlinear projections
>> are involved. you want to filter out frequencys below 1/2 sample rate
>> before sampleing, but the nonlinear projection makes that tricky.
>
>Jep, thats true. I haven't noticed the effect when creating full resolution
>panoramas, but if the panorama is smaller, the aliasing becomes quite
>visible.
>
>> its hard to avoid two things, a slow algorithm, and a noisy signal.
>>
>> to get a realy clean anti aliasing, you could filter the signal, then sample it. but the nonlinear mappings make that tricky. you could sample with a bunch of samples spread out like a sync, but then it wouldn't be clean and it would be slow.
>>
>> i developed an algorithm that would be great for this application. it
>> works by filtering the input images before they are resampled and remaped.
>> it uses a filter that is fast to compute and is clean and correct for the
>> nonlinearitys of whatever mapping you apply. no big convolutions.
>>
>> i would like to write this code as a library or a utility.
>
>Great! Do you have a paper or something like that about the algorithm?
>
>> i don't have much experiance with this modern programming environment. i
>> don't know the programmers interface and librarys that you are useing. i
>> do have alot of experience writing in C.
>
>No problem, hope I can help out here. I'm currently reorganizing the
>stitching sourcecode, will check it into cvs soon.
>
>Basically there is one remapImage() function that loops over the image,
>calculates the transformation and interpolates. (Implemented interpolation
>functions are described on: http://www.path.unimelb.edu.au/~dersch/interpolator/interpolator.html )
>
>foreach x
> foreach y
> double sx,sy;
> transform.transformImgCoord(sx,sy,x,y);
> // make sure that the interpolator doesn't
> // access pixels outside.. Should we introduce
> // some sort of border treatment?
> if (sx < interp.size/2 -1
> || sx > srcSize.x-interp.size/2 - 1
> || sy < interp.size/2 - 1
> || sy > srcSize.y-interp.size/2 - 1)
> {
> // outside source image
> *alpha = 0;
> } else {
> // use given interpolator function.
> *remapped = interpol(src.first, sx, sy);
> *alpha = 255;
> }
>
>that stuff is in src/include/PT/ImageTransforms.h
>
>I'm currently working on that stuff, so please wait until I committed some
>the changes (in the next days), if you want to change the source.
>
>> the utility or library, needs as input the image and the parameters of the
>> projection remaping that is to be applied, and it needs to be able to
>> output a filtered image, of the same reolution. basicaly i need to know
>> that there is a particular tiff library. and the library that does the
>> transform from planar image to panorama image with (y,p,r,v,a,b,c).
>> basically the parameters for the nonlinear mapping.
>
>Ok, then you need the transform.transformImgCoord() function. Actually I'd
>like to incorporate your library into the stitching routine, instead of
>calling a separate antialias program (which we can provide nevertheless).
>
>Do you need the complete transformation for all the pixels, when
>antialiasing, or is the transformation of the current pixel (and maybe a
>neighbourhood) enought?
>
>I have been using the VIGRA image processing library, because it can easily
>be adjusted to work with different image types. But its a weird pice of
>software if you come straight from C.
>
>If you don't want to use it, and perfer to work with simple C, I can write a
>small program that outputs the transform for each image point (as tiff file, or
>raw double matrices). Then you can use whatever library you're familiar with,
>and I can port it to VIGRA, once the code is there.
>
>> i just need help getting started with writing a little utility. And testing it.
>
>Once you have that library/program, I can integrate that into the nona stitcher,
>and take care of that VIGRA library used inside hugin and nona.
>
>Thanks,
> Pablo
>
__________________________________________________________________
Introducing the New Netscape Internet Service.
Only $9.95 a month -- Sign up today at http://isp.netscape.com/register
Netscape. Just the Net You Need.
New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp
More information about the ptX
mailing list