Author Topic: Fractal interpolation (Read 10184 times)

Alhexx · « **on:** 2005-10-09 19:55:15 »

I just took a look at the last few post in Sain't FF7 High-Res Patch-Topic, and Otokoshi said something about Fractal Interpolation...
I googled for that and the best thing what I found on the first page was this:
http://www.dpreview.com/learn/?/Glossary/Digital_Imaging/Interpolation_01.htm

I think the result looks quite interesting...

However, does anyone have any closer information on fractal interpolation or even a source code or something like this...?

- Alhexx

- edit -
I just found this PDF, and I have to say that FI seems to be a *little bit* more complicated than bilinear and bicubic interpolation... :erm:

Cyberman · « **Reply #1 on:** 2005-10-10 01:33:56 »

Well fractal interpolation would work something like this.
Perform image analysis and generate a series of affine transformations matching the image information. Affine transforms are 2d scaling rotation and translation information. Find fractals that match the pattern scale rotate and translate. That's basically how it works. After creating a set of transforms, you are done. This is the basis for fractal compression. The nice thing about fractals is they are dimensionless. Thus you can scale the fractal which approximates the image pattern up and visably gain detail. The pattern is matched by an approximation (the fractal pattern). Poof there it is.

The issues are it's ASYMETRIC IE it takes forever to generate the affine transforms and match them with the proper fractal pattern. It takes practicallyno time by comparison to generate the new image from the transforms. This is the reason that fractal compression for video didn't 'take off' even thought it gave impressive compression and resolution independance of the original video, it had the downfall of having close to 100000:1 ratio of time to compress as opposed to decompress. Thus if it took 1/24th of a second to decompress a frame, it took 4000 seconds to compress it (or more than an hour) that ends up being way too much time and too expensive. Even with a large farm of processors. !000:1 (100 processors in parallel) is still 40 seconds per frame. a 2 hour movie 7200 seconds at 24 flps is 172800 frames and this ends up being 80 days time to compress 1 movie. Specialized hardware could reduce this.. but it's still a rediculously expensive proposition. These days it's less so, however it's been long enough .. that people aren't thinking about fractals for compression anymore.

Ok enough babbling I'll behave.

Cyb

Phyltre · « **Reply #2 on:** 2005-10-10 02:25:51 »

So you're saying that fractal interpolation couldn't be dynamic, like a camera lens?

Cyberman · « **Reply #3 on:** 2005-10-10 04:20:21 »

Quote from: Phyltre

So you're saying that fractal interpolation couldn't be dynamic, like a camera lens?

One way of looking at it. Even with todays DSP's one small scaling step may take several seconds to several minutes, depending on how far they've got the fractal pattern recognition from the 'good old days'

Cyb

Alhexx · « **Reply #4 on:** 2005-10-10 15:09:41 »

That's what I was expecting... nice results, but it needs a lifetime to interpolate... how disappointing -_-

- Alhexx

Otokoshi · « **Reply #5 on:** 2005-10-10 21:21:28 »

Thanks for your interest in my previous post Alhexx. And thanks Cyberman for such an in depth explanation. That is a great link that shows the different characteristics of interpolation by the way. I remember The SaiNt mentioning using bilinear interpolation for his project anyway. I am assuming that would be much easier to produce/process since bicubic interpolation is available on my Photoshop CS. Just curious to how this could be implemented?

Alhexx · « **Reply #6 on:** 2005-10-10 21:58:18 »

Bicubic is nearly the same as bilinear, but it takes even more time to calculate the new pixel.

Basically, that's the way it works:

Linear (aka Nearest-Neighbour):
The destination pixel is calculated from 1 source pixel (in other words: 1x1 pixels)

Bilinear:
The destination pixel is calculated from 4 pixels, in other words from a 2x2 pixels block. This produces nicer results, but is slower than linear.

Bicubic:
The destination pixel is calculated from, take a guess, 16 pixels, i.o.w. a 4x4 block.

As you see, generally all the algorithms work the same way, they just use a different amount of neighbour pixels to calculate the new pixel from.

The reason why you usually use bilinear filtering for games is because it is a good compromise between speed and quality...

However, I think I will take a look at that fractal interpolation as soon as I find a big block of free time in my life... :z

- Alhexx

Otokoshi · « **Reply #7 on:** 2005-10-10 22:19:54 »

My understanding is that FF7 engine uses pixel doubling for the fmv and nearest neighbor interpolation for the background images. If you could implement fractal interpolation would you have to heavily modify the engine to accomplish this? :z ZZzzzZZZ (dreaming you miraculously found a way to use fractals)

Alhexx · « **Reply #8 on:** 2005-10-10 22:50:02 »

erm... no, I seriously doubt that this can be done.

Besides, I have currently no idea how to implement a fractal algorithm...
So better forget that.

- Alhexx

Otokoshi · « **Reply #9 on:** 2005-10-10 22:57:31 »

Well you just shattered my dreams....THANKS! j/k

I hope to hear from The SaiNt soon about his progress on this interpolation. It's very facinating to me. Let alone all the great work put into the Hi-Res mod, he along with Reunion and countless others on these forums seem to have the midas touch to modding.

Alhexx · « **Reply #10 on:** 2005-10-11 15:54:23 »

Another question:

I'm not sure if everybody here know what I was talking about when saying "Fractal Interpolation". All the stuff I read here reminds me more of "Fractal Compression".

I meant interpolation in sense of scaling images, as bilinear interpolation, and not compressing them... or is this the same?!?

- Alhexx

The SaiNt · « **Reply #11 on:** 2005-10-11 16:20:27 »

Well a Fractal Interpolation involves finding the correct fractal coefficients first and with them you can generate pictures that are resolution-free, this being used as fractal interpolation.
Also since storing the coefficients required to generate the image happen to take less space than most normal compression schemes, (more so the larger the image), it's also known as Fractal compression

Cyberman · « **Reply #12 on:** 2005-10-12 05:31:29 »

I thought my little diatrab mentioned this LOL!

Fractals are dimensionless <-- very important to remember.
Because of this patterns in a NATURAL image can be matched to a fractal and easily scaled. Since the pattern has no dimension. This means if you scale it by say 1.359265 it will EXACTLY fit, since it is not dependant on any linear or integral value. Your image will scale much more smoothly if it's say a tree or water. Things without enough information to establish the choatic pattern of a fractal (IE man made objects) probably will not scale well using a fractal pattern, in any case once you have the pattern scaling is a snap.

Fractal interpolation is just a very poor 'word twist' of what is really going on. You still have to do all the same things you have to do for fractal compression in order to perform the 'interpolation', which is actually the wrong terminology and perhaps the author should be kicked for it. Interpolation is techically something different. Nearest neighbor is actually interpolation, where as bilinear and bicubic are not, interpolation is a subset of data fitting. All of these are scaling algorythms or data fitting algorythms. By the way Bicubic exists from 3d meshes etc and real world use in engineering for approximating curves etc of real sampled data. The concept is that it not only does it have a curve that flows through the points it also has the same slopes (you can take the derivative of a cubic curve and that is important in numeric approximation) and thus is a more acurate approximation when you scaling the data up. The asumption has always been that there are smooth transitions between the points. For an image this is not true especially when dealing with natural objects. This is where using fractal patterns become a useful tool.

Cyb

Alhexx · « **Reply #13 on:** 2005-10-12 15:43:25 »

Okay, I think I understand now

Thanx, Cyberman

- Alhexx

- edit - Edited after Otokoshi's reply
Just to make sure I really understand it now:
When scaling images using fractal *cough*interpolation*cough*, the source image is first compressed using fractals, and after that, it's decompressed to the destination dimensions, right?

Otokoshi · « **Reply #14 on:** 2005-10-12 16:36:27 »

Quote

'interpolation', which is actually the wrong terminology and perhaps the author should be kicked for it

Yikes! I hope you are referring to the author to the link Alhexx supplied, and not the one who started this whole silly discussion...me

Thats not the first place I have seen it mentioned as fractal interpolation, but as you said, it is not the correct terminology and I apologize. Checked wikipedia and it's almost the same definition posted by Cyberman. Once again your knowledge has me falling backwards in awe

I swear this forum has the most knowledgable community behind these games! Most gamming fan forums I have seen have morons who release NEW SKIN PACKS or Def Leopard MUSIC ADDONS and are hailed as heroes. Very impressed with all of the effort towards various projects and just helping others out!

Alhexx · « **Reply #15 on:** 2005-10-12 19:00:46 »

Oh, yay, wikipedia.
I just typed fractal into the german wikipedia site, and I found some interesting infos.

And I have found a link to a german article about fractals in games, and the author mentioned the good old 64kb-demos. Maybe some of the older members still remember this topic.

- Alhexx

Cyberman · « **Reply #16 on:** 2005-10-13 04:57:27 »

Quote from: Otokoshi

Quote
'interpolation', which is actually the wrong terminology and perhaps the author should be kicked for it

Yikes! I hope you are referring to the author to the link Alhexx supplied, and not the one who started this whole silly discussion...me Thats not the first place I have seen it mentioned as fractal interpolation, but as you said, it is not the correct terminology and I apologize. Checked wikipedia and it's almost the same definition posted by Cyberman. Once again your knowledge has me falling backwards in awe I swear this forum has the most knowledgable community behind these games! Most gamming fan forums I have seen have morons who release NEW SKIN PACKS or Def Leopard MUSIC ADDONS and are hailed as heroes. Very impressed with all of the effort towards various projects and just helping others out!

LOL no I was not considering kicking you.

Just the person displaying the poor choice of calling it Interpolation (in the article). It just says "Hey look at these results".

Allhex there was an article in Byte Magazine (which I use to get a long time ago) that had a detailed explaination of fractal compression. They even gave standard fractal patterns used for the data fitting. I think they were a leaf pattern and a few others.

In summary, you break the image up into pieces approximateable by the fractal patterns. Then use a convient number to scale too. That's as simple as I can say it. Generating the image from the fractal information is quite fast, however I only have the random number variant (slow version) instead of the interitive algo. I've not played with it literally for 16 years LOL.

Cyb