00:00
so so I think you for showing up and believe this is morning and HA was conversion morning this morning so paid for a lot the downstairs with extra double shots retirement of then you need to use the large cups of the ways overflows and and now they know I've been here for and I was in such a rush that the still have
00:22
my it be forgotten and machines the mission was called it's still not have coffee you my got anyway so I hope to contribute I'm in economics I hope to contribute things to posterity and I think my most likely contribution is a saying which is the early bird gets too weak so I think you're you're an example of this today I also found out this morning showing up at 7 and that the early bird gets to claim a lot of stairs because they don't turn on the elevator so uh uh and I found out once a lot and that my graduate students had fallen asleep while putting together the slides so we'll see up this dog goes I greatly welcome you know well in that will teach you you wind and so far of here 3 weeks ago and they did this there should be something more in undergraduate studies student contract anyway so this
01:19
is an academic project about image resizing in resampling of and and again the top but as you might see of the out and try to remember this turning business how C and how I understand everything but I have to master students uh working on this as well as various collaborators uh that actually there's more collaborators and this uh for example but at some point plant uh very important helping hand and that there's been some talk about how to get programming good
02:00
quality programming done uh uh for open source projects I just want to make a suggestion is that if if you know a graduate student or a actually an undergraduate student to seems promising or even someone who's been industry analysts take a break somewhere where there's a lot of snow for a long time so shaken snowshoe from my home to to where I work uh these little lines here cross-country ski trails in the winter this is golf in the summer this white spot is a beach uh there's a small ski hill off-screen as well as the best buy and the Toys R Us in a downtown at an excellent the French and English music scene this is a the French islands in northern Ontario the the Quincy they were ordered Ontario francophones you know there are no you're too young yes maybe they were the 1st famous uh blob of a lot let's write the work quintuplets who came from the were basically born in the shed anyway so maybe what you could do is you this is a bit different than actually paying someone to program you could you could set up some some sort of scholarship for a master students to work on what he or she wants to do but if they take their money this is hopefully something you also want done in and prossage really good at leveraging right so will add more money and this this masters of computers a computational
03:31
science is actually set up so we can take people from various backgrounds domain requirement being you must be able to program OK but if if you've not done much college Matthew you'll suffer In some courses and for in for 2 years in 1st year pardon me but but that you should be able to be program and the project of your love for at least that 1 of the 2 years it takes to complete these things on my
03:57
students completing this in 18 months but she's a she's very bright and hard working and organized anyway so this is not the worst place to spend 2 years if you don't mind good winter boots
04:10
on so this is a resampling talk as I mentioned it was somebody who was a favorite contribution to humankind is the early bird gets to we describe somebody who does things at the last minute at all so that's the other star goes so 1st of all maybe I'm hoping all of you know who was 3 7 years but just in case uh resampling is any operation where basically you change the geometry of the image somehow this is a bit of a reductive definition but but it works so enlarging shrinking image-making thumbnails warping that point perspective rotating this is all resampling the basic underlying operation
04:50
is a sampling so I'm going to talk about a few novel resample orders and as you can see there's the tiles that have to do with the various groups of robbery where the mean people involved in every project uh so Anthony system is 1 of the the main developers of ImageMagick which which of course the main developers Christie also known as John Christie and anyway Frederick white house things a lot on the image magic forms OK so basically did this said this new method called the James this is not a misspelling there's a sinc function which is which is constructed using the assigned to the trigonometric sine function sign x over x and the gene function is 2 be equivalent so a lot of uh classical samplers or receptors that you guys use their built from uh basically comes out of audio signal processing right body signals are are 1 dimensional the this kind it's an it's an amplitude and time
06:06
and the 1 of the points I want to make is that you're not getting the best bang out of the box is if you use you use a tensor method meaning if you use a a one-dimensional method twice to do something two-dimensional you're missing something somehow there's a OK so 1 of my research that met 1 of the things I do is I don't fully two-dimensional schemes and therefore resampling and of course I take inspiration from
06:35
from elsewhere In this particular case the the
06:40
inspiration is Paul Egbert who wrote the original soon program as a graduate student in 1986 I believe which is the basis for image magic so it's there's an offer even do I think he's contributed very little code directly but in a sense is contributed everything uh anyway so the the the the point I'm going to make in this part of the talk is that you can real you can look at presenting a single it's texture mapping or do it as if it was texture mapping so that when you're doing texture mapping and that Akbar 20 which which is quite common really what you have is when you want to know the value near a location on your output image you you're going do this by averaging and in some sense some sort of reconstruction this is conceptual but it's not quite accurate but it's OK in in a circle centered at the location of interest OK so that's the way it did the values of an average there obtained by pulling back that little circle back to where your data comes from when you're doing texture mapping the here it's of perspective transformation uh uh what what you're doing is you're you're you're in apple and the inverse of the transformation you're pulling back you want to know where these values come from right this is going ancestry tuple that these little circles back to the origin all image that you are applying perspective to and it turns out that with perspective and affine transformations in linear transformations circles and actually all ellipses are mapped to ellipses and since the inverse of perspectives for is a perspective uh you get the did you get this when you pull back so now you have this ellipse sees that sits on your input image and some of them are small which means that it interpolatory scheme like bicubic uh or by linearity might work OK and some of them are baby and they are also not circles right some of them the the might enlarge the might and large things barely for example the the right ellipses barely wider than the little circle right so you don't gradually pixels and direction that is very long so you grab a lot of them in the other direction and spend a lot of the work that I do with the students has to do with it uh fixing schemes using information about the length of the minor and major axes the weights and the and the length of these ellipses OK so I
09:17
didn't I think 1 way of describing it whether method doesn't show results so here's the test I a tiny image this is the public image image magic is the roles picture where not larger 20 times so this is
09:32
the new method and this is the enlargement with the new method and I'm saying it's better than playing so in a sense what it is an improved lane shows it's a high quality link shows so here's land chose this is standard line shows got computed carefully with ImageMagick uh using AGRI mode uh so let me show you again now you can see the image magic commands at the top uh you need to have a fairly recent image magic for this to work uh so now you can resize 2 different ways ImageMagick without having to program things very you can do things lots of ways in which magic but there's too easy with easy ways there's the resize way which has been there for 20 in some years and there's that this stored tree size weight which uses elliptical weighted averaging but actually in a modified version from like Egbert and other people considered so now I'm going to just a tiny anecdotes it's it's that Hagberg original elliptical weighted every hour averaging which is a popular splatting method is that it he called it HQ others you know it's HQ uh EW EW is elliptical weighted of averaging OK and uh and and and people like it a lot because it was the in high quality method right and of course now there's a there's text that appeared at but actually HQ it why it's not that high quality unless you're dealing with distant or license in and I find it kind of numerous that my 1st contribution to graphics open source it came from code that was taken by somebody on deviant heartening for comics in that there was a discussion on the game side where know what to do we what will never work with the new thing which is giggle in and out said OK fine i'll do something else and then somebody grabbed this from my website and then like repackaged and called it because I had given acronyms like he in the QHE felt this would not market things too much cycling something deviant hot spots if you call that high quality clean-cut PG art and the the PT won't get mad at you and will centered on how it's gives your supply just nature there's no cyber breasts so what somebody mentioned right again and anyway so so and so then that he called it each q size of something like this and it became popular because it was high quality so anyway so basically with this method is it's it's it's taking various ingredients form various smart people and and getting it to fit together just right there there's no there's 1 kind new ideas and there but really it's it's a think there's all these pieces but nobody has but then just right we put them just right anyway so and so 1 of them has to do with doing at a doing clamping of the ellipse is this the right way because you don't want to indices to be smaller than these this you have at the beginning but you still have the nature of this Egbert has a quick and dirty way which led to incredible bad uh when you were enlarging for example so we fix that we fix a few other things and we also have a way of computing this extremely fast we used without using trigonometric functions so we do what we do trigonometry without 3 3 of the so so what can I show you about this I think you're able to see that uh uh the the jaggies are much more much reduced the it's slightly more blurry right is maybe not it's kind of hard to tell doesn't make sense right and the the halo is also reduced look look at the bottom there's less halo the review it's partly because uh the the the function that the gene function decays faster than the sinc function in doing so in my opinion this is a killer scheme OK right just to compare this is the default resides in image magic popular methods the bicubic Mitchell Mitchell about uh no I'm not there yet OK so this is a very popular methods the Mitchell which is a good compromise Mitchell naturali uh anyway and what's so notice there's no question it is our methods better and that many no I'm this answer and biased but and I'm right all of the the of
14:22
so um so you're going to I'm not gonna cover all the topics that I put on my incredibly ambitious 20 minute talk that apologies anyway so this is the what was the basis of the best solution but it's a window into the method the base of the windowed method is the the basis function so this is the cut this is using the same the 1 the sink in tensor order going away notice these ripples This is the checker boat checkerboard mode right it's these alternating and up and down things that follow the square pattern pattern and the grid so this is why you get these jaggies now in and you can also notice that it's a low-pass filter but actually if let's say it's not as good a low-pass filter because the corners of the frequency response are clipped with the best 1 doesn't make sense and notice it's I don't know you you show this year to your grammar was of course an open source free anyway and see which 1 do you think will work better and it was no
15:28
contest but and also works beautifully for downsampling uh and it also works great for working and that it should not take too long to get that someday all implementations and those in the room involved with these groups know what the meaning of soon when I write it who still waiting for a
15:51
sabbatical OK or unemployment so I can get some pursues programming them so as the weakness weakness compared to let classical angels it's it's not an interpolatory method when that means basically is that even if you're doing something even if you take your image and you happen to decide to resize to exactly the same size at exactly the same alignment you will not get the original image it will pass at a little bit but doesn't make sense it's not major about so if this bothers you I know how to fix this this is when using a later part of this talk basically what you do is you take the standard line shows and then you blend blended with the new 1 OK in such a way that when you are close to to doing the you no-op operation then the old line shows which is interpolatory but as more artifacts dominates the computation right the don't make sense OK so so I so now the next topic of my talk I met
16:59
that minutes yeah yeah yeah 11 0 my god only so I so I hope I put these slides right yes I get a kick out deserved that lottery which is waiting for me OK so um uh this is another scheme this is not in a what that this is not at the Ecole weighted averaging method this is an interpolatory method so basically what it does doesn't reconstructs the surface so this is not good for making thumbnails it's only good for rotating enlarging or maybe reducing just a little bit doesn't make sense so it's a complete different it's also in nonlinear scheme the previous methods I showed you were all of them are linear methods meaning what you'd get uh if if you if you were if you resample if you lot to images and you average them you get the same thing as if you average to imagine new and larger that some your scheme on as I make sense this is a non-linear method there is a slope millimeter built and there the submit limiters called but the thing that's special about this 1 is that it's boat shop and he'll freeze a actually there's a bit of a library there there is a possibility of finding my them out of here know but you cannot never speak out of that the local values of course by linear nearest neighbor do this but they're incredibly either blurry or jaguar you doesn't make sense in which B-spline smoothing quadratic spline smoothing all the Gaussian blur also also it has no way low but it's very blurry so what it is is this nonlinear guide manages to balance blurriness which it with the heel freeness doesn't make sense OK so unless you care about being a free this is not for you and as I mentioned it's only good for
18:53
up or feeling or saying but it so I took the simplest non all he will free method it's by linear and I'm doing the exact test as the force of course by earlier is both a blurry and Jaguar right actually get these ridges value is the most annoying method ever but it's great to but it's annoying OK so that this is the new 1 I think that by doing these methods on the posted at some of the OK so and I don't know if you can take that also our eyes create heal themselves when we look at high contrast lines right with the frequency response of brains nonlinear arises nonlinear but it's pretty shocked OK and it's but it's pretty it's basically you free the methods jaggy little bit doesn't make sense OK so it's it's this is the best I could come up with it took me 3 years and so and but it runs pretty fast it's the ones once you're you're a library is set up so that there's not too much waste this is from this I'm saying this from memory this is about 3 times lower than a standard by bicubic and it doesn't take much data distances quite mild it's quite small so five-by-five take away the 4 corners right and bicubic is a 4 by 4 so this can run really fast ball and those which go fast well it's already and it's in the 2 now I come to
20:24
Jacobian adaptation so what you have is you have a favorite method for enlarging and rotating and doing things that are upsampling right then you have a favorite method for downside employing it could even be Gaussian blur right about making images smaller taking lots of pixels and having 1 representative speaker pixel so given that many methods on a jack of all trades the uh uh change it walk length so this is a pretty good jack-of-all-trades but it's here week a little bit right and it's a bit blurry and in no way you know that I just showed you just good for up and saying but not bound right you pick your favorite of 1 or the other and then uh you go OK so how do I get a jack sampler that does all this so the obvious answer if 1 of you knows references words been done I love is you blend them and you blend them using measures of what the transformation you do at that point of course if you're doing warping right and you can approximate locally the transformation you're doing your work by an affine transformation which of course would be trivial right it if it's a stretch in all directions the linear aperture summation of this is the there is a make sense right so there may be where the called degeneracy theory but 1 way or another it's not too easy to tell everyone who implements a geometric operations you need to return a reasonable approximation of the reasonable I find right it's a translation plus a linear approximation of the transformation at every point doesn't make sense if you have a formula for this you can do it by computing the Jacobian matrix so and so then what you do with these give you these ellipses so then we can compute the lengths of these 2 axes and and what you can do is this is you can see the scheme that is good for down this seemed as good for us OK use it in an amount proportional to the I'm using uh the reverse transformation right to the product but there were there to the product of
22:40
these uh singular values of these access lines and and give the rest of the contribution to the other and make sense if you do it right when you go up you're going only use the good up sampling scheme and as you move away from going up a rotating so if you're going to increase the strength of the downsampling scheme and there's good reasons to use these formulas that I just described extremely tersely and probably 1 of the so once again the
23:08
basis is treating everything like a texture mapping a and that these are the slides that I
23:16
downloaded at 4 2 9 OK so Cheney glasses always on the the the so this is how the you know you know there's a good of sampling scheme this is uh elliptical weighted averaging triangle it's using attempt it's using a clone right by linear is is is this so world did do it through the version about here you get a cone right so that gives you a filter which enable a very bad approximation of logic I of the of the and and so this year and this is the result of enlarging so it turns out that this stain stocks at enlarging so you fix things so that here is 1 so this is not use that also these 2 images are site was that makes sense and you can do this on a pixel-by-pixel basis even though here's the Colombians constants of the this constant now to
24:09
reduce I don't you know it was not very good so this image is very this image here is very close to the result is very close to this 1 this was done with something which is currently In this sense the as yet branch of it's called lower you know OK and rotation by then
24:30
the rotation takes a circle and a standard like this so it's like an upstream does that make sense so once again the equal to 1 and this image is exactly the result of that nonlinear he'll free methods and what you could do is you squish
24:48
right so then you're going to hear about this image is fairly close to this but not as much as if I had squished equally in both directions I make sense so you can take any 2 schemes and then you have formula could to compute the data and then you just plug OK give me this much of the good for up this 1 of the good for down the that OK I mean
25:14
OK so so I'm going to be very very fast but the so I I have to so as it turns out some of you program resampling methods and this I am stunned at the lack of publicly available optimize code for doing various things as simple as going by linear so I'm gonna show it but if you have a balladeer sampler an integer arithmetic unfold arithmetic actually and and my collaborator John up it was a fantastic programmer and benchmarker will attest to this if you can almost certainly do better than using lookup tables by using optimized code OK so e-mail me maybe next time I come now show you formulas I have this for balance here I I have this for all the bicubic so I have this for lane shows the kernel involuntary involves trends so I can replace those by polynomials computed with the boosting + + minimax library which I adopted so I can do men and relative errors of absolute there the Bessel functions are a royal pain in the neck to compute I can replace them with highly accurate polynomials you liked flop standby power minus 5 from 0 to 3 you get the idea of the and uh so these are works in progress but if you want speed and you some of them they're just like filters like black men all this they always given in standard form but actually you can remove half the trades by just using trigonometric identities doesn't make sense so I'm talking about this kind of stuff is the simple formulas that people and that's at an angle how can I do this fast and uh so that's pretty much it and if you
26:58
have questions that I have a Gmail account thank you for this week be so most of this that and the questions uh yeah actually don't need to do this and they can show you beautiful Sudbury Ontario where I was still final
27:25
exams to the so what's your question so are it's
27:28
wonderful to see this and energetic I wonder if you see whether or not this my people on a lot of other type of things like for example our for a whole whole far away do you think it is from being poured something like say blender or something like that for you want to take a look at them and I guess I in just you know the composite image resizing or something like you know that the actual scaling of textures as they to this stuff about it at the treaty is it is a bit more programming work right so uh it will attest that when I see soon I mean 3 years talking about this being said these things move faster so if there is interest and these are perfect for demand-driven systems this makes sense right you know right it's it's not play ImageMagick which is a data-driven it's is demand-driven so uh into the should not be much harder but I have a few our articles and stuff to publish 1st so I'd say could get started on this probably next summer but if I get either interested grad students or or probably the lot by high-profile product like blend the right it may happen faster but don't hold your breath the answer your question of course I want to go to treaty and so on to cope with Mars Iraq knowledge is you it more slowly Adam is not commodity right now I ask him but is you and the recent National marked merged samplers branch and most of you know uh but we want to clean it up a bit and we want to remove stuff actually and and also I need to ask you personally about there is no we fix the Jacobian matrix stuff in our branch and and somebody else fix that differently in mass the assignee to ask you can we use our weight OK so the answer is basically soon but let us do a little bit of ironing out and that it's come another little comment as well as that image magic there is already a problem to large forests of available receptors but at least thank you for having moved away from the idea that parametres for the resampling in addition to choosing the reason why knowledge of the parameters for you and love that is saying defaults and that's better than asking the user hold you wanted the 2 out of the yes if you you know you're telling allowed your monthly reminder of what you don't like it that that that I'll definitely take into account and did I want to mention something however is that uh ImageMagick has a forest of craziness but there is the faults although I have mixed feelings about this because I protested this choice 1 of the defaults is a method I designed which its name the probably do but you don't see it when you use it because it's the default doesn't make sense so a forest you can have 1 tree out of it if you want yeah this is a place where can just really care about is in my own low-speed because this would be too fast for me what I want a better image scaling for creators will uh and unfortunately I could it this is a very sad thing that I called faster and I write articles uh there was a lot of discussion in the image magic forms OK so you can find eucalypt do I don't use license like Martian X you know and and so you can find in and out of their use that you can also e-mail me and if I get request like I I can to put together summaries for people contact me faster than I write articles for publication to it and then I can say OK what do you need what's good for you I have a fairly big thing is I have a fairly big picture of the whole forest of image magic methods and more doesn't make sense so you can get a family but we like these artifacts we don't like these artifacts and on and on and on and on and on and I can buy think this will work for you I think this will work for you there's another thing I want to mention before I get shut up it's that uh I'm actually doing a lot of consulting these these having to do with making and thumbnails and compressing them for a web OK so if some of you have expertise in this I would love you to snatch me and say you should do this like this so you should not do this like that or whatever doesn't make sense I check from grad students by consulting work which of course need to take off that the because of the administrators find out all get in trouble OK so that you thank you you're welcome