Jump to content


Photo

Video data interpolation question for the Von Neumanns


  • Please log in to reply
14 replies to this topic

#1 Chris Millar

Chris Millar
  • Basic Members
  • PipPipPipPip
  • 1642 posts
  • Other

Posted 27 November 2009 - 06:42 AM

Hello all,

Say you're scaling up a video frame by a factor of 4, 16, 64... - i.e. a 100x100 pixel frame would become 200x200 and so on ...

What is the easiest way in terms of computation or at least understanding to do this ?

I was thinking due to the relative simplicity (?) of the factors involved and the inherent lack of some artifacts due to those factors that maybe bicubic/bilinear interpolation might be redundant ? I don't think a nearest neighbor style will suffice for the application - something between the two in terms of complexity ?

Also if say I wanted a 64x scale - is that simply an iterative process of each successive output ? 100x100 >scale> 200x200 >scale> 400x400 etc... or can you get the 800x800 immediately ? I suppose it depends on the algorithm, but would the output be any different anyway ?

Channel/bit depth is not-important for the purposes of the discussion - it's more a spatial consideration for now... Nor is what program to use to do it for me ;)

Hope I've explained this well.

Any help appreciated,
Chris
  • 0

#2 Phil Rhodes

Phil Rhodes
  • Sustaining Members
  • 11934 posts
  • Other

Posted 27 November 2009 - 02:41 PM

Simpler interpolations work well enough for small increases (doubling, say). Linear filtering in particular starts turning everything into a field of what looks a bit like cross shapes if you scale up a lot (say, 64 times). Imagine what old-style computer graphics boards used to do to low-res texture images when you viewed them up close:

Posted Image
Most techniques for doing this involve scaling up the image by simply adding pixels, then low-pass filtering (blurring, basically) the result. What we see is a very basic low-pass filter that only operates in a couple of dimensions. More advanced scaling uses cleverer filtration in more vectors, and takes care to have optimal low-pass cutoff (see Lanczos).

P
  • 0

#3 Keith Walters

Keith Walters
  • Sustaining Members
  • 2219 posts
  • Other
  • Sydney Australia

Posted 27 November 2009 - 05:42 PM

Hello all,

Say you're scaling up a video frame by a factor of 4, 16, 64... - i.e. a 100x100 pixel frame would become 200x200 and so on ...

What is the easiest way in terms of computation or at least understanding to do this ?

I was thinking due to the relative simplicity (?) of the factors involved and the inherent lack of some artifacts due to those factors that maybe bicubic/bilinear interpolation might be redundant ? I don't think a nearest neighbor style will suffice for the application - something between the two in terms of complexity ?

Also if say I wanted a 64x scale - is that simply an iterative process of each successive output ? 100x100 >scale> 200x200 >scale> 400x400 etc... or can you get the 800x800 immediately ? I suppose it depends on the algorithm, but would the output be any different anyway ?

Channel/bit depth is not-important for the purposes of the discussion - it's more a spatial consideration for now... Nor is what program to use to do it for me ;)

Hope I've explained this well.

Any help appreciated,
Chris


  • 0

#4 Chris Millar

Chris Millar
  • Basic Members
  • PipPipPipPip
  • 1642 posts
  • Other

Posted 27 November 2009 - 08:24 PM

Most techniques for doing this involve scaling up the image by simply adding pixels, then low-pass filtering (blurring, basically) the result.


hmmm - ok - interesting ! - so not much of the original data is left intact at the original points ?

I was thinking of a kind of 'weighted nearest neighbor' approach - I'm sure its been thought about before, but basically each pixel to be interpolated was averaged over the 4 closest original data points...

Using the original pixel pitch as the working unit and imagining interpolating the top right pixel of the 4 new pixels:

The closest is 0.35 units close to its nearest neighbor which is actually the original pixel value.
The next two are 0.79 units close which is the distance to the pixels to the right and top.
The last is 1.06 units close - the ah, um, top top right right pixel at 45deg to the original

Trust me on these numbers for now ;)

So each value will be averaged but with a weight inversely proportional to the distances away from the interpolated point...

I think this should give satisfactory results (?) - higher resolutions would be achieved by repeat iterations of the process on the output of the latter iteration, I'll eventually chuck in some test patterns to see if the iterative process throws in any unwanted artifacts.

I wonder using this method what the effect would be in throwing in all the image pixels weighted in this fashion - beyond a certain distance the weight would be so low that the impact would be below the bit-depth of the channel anyway - but there must be some effect for the addition or non-addition of closer pixels which begs the question: at which pixel distance do you stop? - maybe the 'top right' one isn't required ?

I don't have a way of playing with this yet - except 1d versions on paper - ha ha - so its a bit of a head scratcher.

Are there any beginnerish books that deal with this sort of carry on - especially with regard to video data ?

Keith - you got me wondering what you had typed up there :ph34r:
  • 0

#5 Keith Walters

Keith Walters
  • Sustaining Members
  • 2219 posts
  • Other
  • Sydney Australia

Posted 27 November 2009 - 11:30 PM

Keith - you got me wondering what you had typed up there :ph34r:

Erk. I just hit the "Post" button and went out for a while. Didn't actually look at the actual post. I could just claim I had nothing to say, but this was what I meant to post (fortunately typed up in Notepad)

Hello all,

Say you're scaling up a video frame by a factor of 4, 16, 64... - i.e. a 100x100 pixel frame would become 200x200 and so on ...

What is the easiest way in terms of computation or at least understanding to do this ?

I was thinking due to the relative simplicity (?) of the factors involved and the inherent lack of some artifacts due to those factors that maybe bicubic/bilinear interpolation might be redundant ? I don't think a nearest neighbor style will suffice for the application - something between the two in terms of complexity ?

Also if say I wanted a 64x scale - is that simply an iterative process of each successive output ? 100x100 >scale> 200x200 >scale> 400x400 etc... or can you get the 800x800 immediately ? I suppose it depends on the algorithm, but would the output be any different anyway ?

Channel/bit depth is not-important for the purposes of the discussion - it's more a spatial consideration for now... Nor is what program to use to do it for me ;)

Hope I've explained this well.

Any help appreciated,
Chris


First of all I don't really know anything about electronics, semiconductor theory, sampling theory, computer programming, video processing algorithms, successive approximation/entropy feedback techniques, JPEG, MPEG or any of that that other sh!t. I just make this stuff up by stealing bits from Wikipedia, hacking into the Fraunhofer Institute's network (oh all right, sifting through their dumpster for discarded printouts), and filling in the gaps with lines lifted from old Star Trek scripts. :lol:
(Don't know what I'm talking about? Try doing a search on this forum for the word "vaudeville" :rolleyes: )

There used to be some very clever people on this forum and elsewhere; but sadly, just about all of them have been hounded off or lost interest thanks to the tireless efforts of small but vocal group of 'tards, suffering total and apparently intractible delusions of self-relevance.

But, let's not be bitter about that, and all that to the side, I'm not entirely sure what question you are asking. Do you want to actually write your own software to do this, or do you just want to get some understanding of how it works, like for a term paper or something?

I did write some stuff about this for a magazine quite a few years back, but I can't lay my hands on the file at the moment. If I can find it I'll post more.

Early upscaling systems were essentially "dumb" devices, which used a fixed set of procedures to carry out the process. More recent software-based systems had a bit more "autonomy" over which particular algorithms would work best for a particular situation, but they were still limited to whatever situations the programmer had managed to anticipate beforehand.

Just about all modern software-based video processing systems work on a quite different principle based on negative feedback and multi-pass successive refinement. In virtually all cases the programmer will have no idea what actual processing steps took place to achieve a desired result .

A. The original image is stored in the computer memory
B. The processing algorithm is applied to produce a second version of the image
C. The processed image is compared with the original image on a pixel-by-pixel basis to measure the induced processing errors for each pixel; this error data is fed back into the processing algorithm to refine the process.
D. Rinse and repeat until the desired level of accuracy is achieved.

(In the case of an "up-rezzing" algorithm, the image will first be upscaled, and then downscaled again for comparison with the original image, down-rezzing being a much simpler process than up-rezzing).

Just about all image encoding systems (MPEG, JPEG Wavelet etc) use some variation of this principle: There are no actual "encoders" as such, they just successively feed different numbers into a decoder until it more or less "gives the right answer", and those numbers make up the "compressed" signal.

Upscaling or downscaling often involves little more than fiddling with the decoder equations to produce a different number of output pixels.

I have to say, if you have notions of developing your own software, you're likely to have a hard time equalling, let alone bettering what is already available. It's fun playing around with that stuff, but unless you have a particular job in mind that can't be done with any available software package, and/or you don't mind massively long render times, you're not likely to find it very practical.
  • 0

#6 Chris Millar

Chris Millar
  • Basic Members
  • PipPipPipPip
  • 1642 posts
  • Other

Posted 28 November 2009 - 12:15 AM

Do you want to actually write your own software to do this


Yes - but as a part of a larger application - the uprezzing part of it isn't intended to compete with any application that does that kind of thing as its main task, the user may even be blinded (if they choose) to this part of the program.

The real thrust or idea of the application doesn't require it conceptually but I can see at this stage that it would be on the wishlist from word go so thats why I'm thinking about it already - for whatever reason I'm getting my head got around it first.

It's fun playing around with that stuff, but unless you have a particular job in mind that can't be done with any available software package, and/or you don't mind massively long render times, you're not likely to find it very practical.


Yes, it is fun! - I'm drawing up 8x8 'frames' here at work in Melbourne with 1-bit initial values and doing it by hand between actual duties - next nut to crack is dealing with edges and what's for dinner.

And yes the full particular job/idea cant be done with any (one) available software package that I know. I'm not averse to using other applications to do component parts of it for me - matlab, jitter, some kind of home-baked (half-baked maybe) script living in a flame or maya or whatever tying it together - depending on which direction I take the user interface will be the last hurdle.

Its a one trick pony for sure but if it were used well could be pretty fresh - I'd like to keep as much of the code/algorithms in house as possible so any possible release of 'Barfscope V1.02 Plugin for AE' is ready to go without licensing/IP issues from other applications

practicality schmracticality ;)

reason for edit: I spelled 'schmracticality' incorrectly

Edited by Chris Millar, 28 November 2009 - 12:18 AM.

  • 0

#7 Chris Millar

Chris Millar
  • Basic Members
  • PipPipPipPip
  • 1642 posts
  • Other

Posted 28 November 2009 - 12:36 AM

QUOTE (Phil Rhodes @ Nov 27 2009, 11:41 AM)
Most techniques for doing this involve scaling up the image by simply adding pixels, then low-pass filtering (blurring, basically) the result.


hmmm - ok - interesting ! - so not much of the original data is left intact at the original points ?


Yup - I'm a dum dum

There are no original data points anyway - the original point becomes the four corners of the interpolated pixels...

hmmmm :rolleyes:

I can see how an iterative process would gradually reduce hard edges to poop - thinking now that in successive iterations that maybe data points from the original data set could still be used - they are afterall more um, 'legit' and spatially closer to the 'inner' inter-interpolated pixels.

Sorry, no access to a drawing program for a diagram ...

Dang, ha ha - I can see there is now an issue with this, as you get little 'pools' of more accurately interpolated pixels around the original data points, which might give artifacts.

OK - promise to think more before I type from now on
  • 0

#8 Keith Walters

Keith Walters
  • Sustaining Members
  • 2219 posts
  • Other
  • Sydney Australia

Posted 28 November 2009 - 12:51 AM

First of all I don't really know anything about electronics, semiconductor theory, sampling theory, computer programming, video processing algorithms, successive approximation/entropy feedback techniques, JPEG, MPEG or any of that that other sh!t. I just make this stuff up by stealing bits from Wikipedia, hacking into the Fraunhofer Institute's network (oh all right, sifting through their dumpster for discarded printouts), and filling in the gaps with lines lifted from old Star Trek scripts. :lol:
(Don't know what I'm talking about? Try doing a search on this forum for the word "vaudeville" :rolleyes: )

Bloody hell, who would have thought the word "vaudeville" would have appeared here so many times!
OK, if you're interested, go here
instead.

I don't know if I can continue this discussion though.
There doesn't seem to be any way I can sensibly segue this subject into a Vaudeville routine... :P

  • 0

#9 John Sprung

John Sprung
  • Sustaining Members
  • 4635 posts
  • Other

Posted 28 November 2009 - 02:05 AM

Hi, Chris --

It sounds like you might want to check out the writings of Charles Poynton:

http://www.poynton.com/

Have a look at his FAQ's, and if you find the explanations within reach, buy his book.



-- J.S.
  • 0

#10 Chris Millar

Chris Millar
  • Basic Members
  • PipPipPipPip
  • 1642 posts
  • Other

Posted 28 November 2009 - 02:13 AM

OK, if you're interested, go here


erm, that discussion is a bit besides the pixel no...(?)

John: Poynton huh - ok, thanks, I'll take a look
  • 0

#11 Phil Rhodes

Phil Rhodes
  • Sustaining Members
  • 11934 posts
  • Other

Posted 28 November 2009 - 02:50 AM

Vaudeville


All together now:

Oh mammy, my little mammy,
I'd walk a million miles for one of your smiles,
My mammy.

  • 0

#12 John Sprung

John Sprung
  • Sustaining Members
  • 4635 posts
  • Other

Posted 28 November 2009 - 02:54 AM

All together now:

Oh mammy, my little mammy,
I'd walk a million miles for one of your smiles,
My mammy.


Just be sure you're not on after Fink's Mules....



-- J.S.
  • 0

#13 Chris Millar

Chris Millar
  • Basic Members
  • PipPipPipPip
  • 1642 posts
  • Other

Posted 28 November 2009 - 03:12 AM

You guys know I actually work in theatre ? automation though, not the muppet show...
(and yes don't we all just wonder sometimes)

I quit - hang on, no - oops, did that yesterday hmmm

I need a job - :D
  • 0

#14 Keith Walters

Keith Walters
  • Sustaining Members
  • 2219 posts
  • Other
  • Sydney Australia

Posted 28 November 2009 - 08:56 PM

erm, that discussion is a bit besides the pixel no...(?)

Only that in the second line of the title of this thread you mentioned my and Phil's names in your list of Forum Savants. In the thread I gave the link to, I was amused by method by which Jim Jannard begged to differ, hence my frivilous suggestion that my primary purpose there was only to recycle old Vaudeville material anyway; and that any technical insights I may have given anyone were an accidental by-product of this. :rolleyes:

(Turned out at the time he was being buffeted by the twin emotional storms of turning the big "Six-Oh", and the fact that certain authorititive folks on other forums were implying his cheap camera wasn't quite as good as some dear cameras...)

Anyway, it's not that unusual for threads to wander off course. If it results in people receiving new insights, well that can't be a bad thing, but if it just turns into a boring diatribe between "the usual suspects" then that's not a good thing.
  • 0

#15 Keith Walters

Keith Walters
  • Sustaining Members
  • 2219 posts
  • Other
  • Sydney Australia

Posted 28 November 2009 - 09:20 PM

All together now:

Oh mammy, my little mammy,
I'd walk a million miles for one of your smiles,
My mammy.

Surely that belongs in this thread :lol:
Are Movie Theaters days numbered?

Vaudedville was not just about song and dance men, it was in many ways the remote ancestor of daytime TV scheduling.
By the mid-19th century, most large cities had a well-organized infrastructure of performance halls, artists and agents. Vaudeville Halls (AKA "Music Halls" in the UK) had a regular schedule of performances that were eerily reminiscent of TV programming schedules nearly a century later. There would be one-act plays, musical performances, conjurers, stand-up comedians, animal acts, popular science talks and even "commercials" (done live of course).
With most halls, you simply paid an admission charge and you could stay as long as you liked, again, eerily reminiscent of TV programming.

Agents would make bookings and organize transport for their performers, (which is incidentally the origin of the stranglehold the Teamsters' Union still holds in US film production).
There were "First Rate" and "Second Rate" payment schedules. First Rate artists generally required a stage setup beforehand, and so the Second Raters' job was usually to perform in front of the closed curtains while this was done. These were usually stand-up comedians, animal impersonators and the like.
Ironically, when the first practical movie projectors became available in the mid-1890s, they were enthusiastically received by Vaudeville Halls as a new novelty "filler" between the "real" acts. However they eventually became so popular that many Vaudeville Halls wound up converted into full-time movie theatres.
  • 0


Metropolis Post

FJS International, LLC

Broadcast Solutions Inc

Paralinx LLC

Visual Products

CineTape

Rig Wheels Passport

The Slider

Gamma Ray Digital Inc

Abel Cine

CineLab

Ritter Battery

Technodolly

Glidecam

Willys Widgets

Tai Audio

Wooden Camera

Media Blackout - Custom Cables and AKS

Opal

rebotnix Technologies

Aerial Filmworks

Media Blackout - Custom Cables and AKS

Technodolly

Aerial Filmworks

Abel Cine

Tai Audio

Gamma Ray Digital Inc

CineLab

The Slider

Willys Widgets

Opal

CineTape

Visual Products

Glidecam

rebotnix Technologies

Rig Wheels Passport

Wooden Camera

FJS International, LLC

Metropolis Post

Paralinx LLC

Ritter Battery

Broadcast Solutions Inc