Cartesian coordinates warped as a Smith Chart

[RoGeorge]

The goal would be to have a small resolution webcam pointing to a piece of paper (640px/30Hz, or 1024px webcam at most), then to use OpenCV to show side by side the normal image and the morphed one.  Something like this at minute 6:15 (the video was made by offline processing the input frame by frame, not live morphing)



I've tried morphing a static picture (by running this code in Python notebooks https://github.com/stephencwelch/Imaginary-Numbers-Are-Real).  By all the video games and the GHz in a typical desktop/laptop I was expecting that to be very fast, but the Python code was taking about 10 seconds to warp a single frame.  I've only modified the mapping function from \[
    w = z^2 + 1
\] to \[
    w = 4 \cdot \frac{1-z}{1+z}
\] (as in the attached notebook).  Why does it take so long to calculate that on a 4GHz desktop?
(the pic of Max the dog is from Gyro:  https://www.eevblog.com/forum/chat/post-a-picture-of-your-dog/msg4821569/#msg4821569)

I've used OpenCV once, for trivial processing only, to change the contrast and detect some blinking pixels.  Since I'm lousy at programming, and not experienced with OpenCV, neither with video processing, I though I might ask first, before proceeding.

Is live morphing the video from a webcam feasible?
Want only to foul around by drawing pencil lines on a paper, and see that live as circle-arches on the screen, nothing more.

[Nominal Animal]

Is live morphing the video from a webcam feasible?

Just for fun, I checked how long it takes on an Intel Core i5-7200U to morph a 1920x1080 full-color image using an arbitrary mapping, and the answer was about 3 milliseconds.  So, real-time webcam morphing with a static mapping is definitely feasible.

I don't know how feasible it is with OpenCV, though.

The age-old mapping technique is to precalculate an array, one element per output pixel, identifying the source pixel (typically as the offset to the source image origin).  In C,
    uint32_t  *map;  // Dynamically allocated, map[HEIGHT][WIDTH]
    uint32_t  *src;  // Dynamically allocated, src[HEIGHT][WIDTH]
    uint32_t  *dst;  // Dynamically allocated, dst[HEIGHT][WIDTH]
where map is precalculated for each transform (including scaling) only once, i.e.
    map[dx + dy*WIDTH] = sx + sy*WIDTH;
where (dx,dy) is the transformed image point, (sx,sy) is the corresponding source image point, with dx=0..WIDTH-1, dy=0..HEIGHT-1, sx=0..WIDTH-1, and sy=0..HEIGHT-1.

You can reserve an extra pixel in the source and destination arrays, so that index WIDTH*HEIGHT can be used for pixels that cannot be mapped or map to outside the source image.

The actual mapping loop you do for each image frame, assuming 32-bit pixels, is then
    size_t  i = WIDTH * HEIGHT;
    while (i-->0)
        dst[i] = src[map[i]];
and as I already said, on old Intel Core i5-7200U this takes about 3 milliseconds with WIDTH=1920, HEIGHT=1080.

[DiTBho]

the Python code was taking about 10 seconds to warp a single frame...
...Why does it take so long to calculate that on a 4GHz desktop?

for the same reason why a dependency resolver algorithm written in Python takes ~2 minutes on an IDT MIPS@400Mhz whereas the C version of the same algorithm takes 40 seconds.

Python is good for prototyping, but it's a slow elephant 

[CatalinaWOW]

There are at least three elements to the behavior you are seeing.

The first is the language you use to implement the solution.  Python is an interpreted language, meaning that each time through all the code loops the computer translates the instructions into the appropriate machine code, and then does the actual work.  Compiled languages, including C do the translation to machine code once, and then can process the data with redoing all of that translation.  In both cases different implementations of the language may do more efficient jobs on each phase of the operation.  Which implementation is faster can actually depend on the type of algorithm being implemented.

The second is how cleverly the algorithm is arranged.  Nominal gave an example of this, recognizing that since the transformation doesn't change from frame to frame it can be pre computed.  This stage require either much research (or experience) or tremendous creativity.

The third is some kind of hybrid of the first two.  Modern personal computers have many computing resources, multiple cores in the processor, graphics processors and multiple speeds and quantities of memory.  Partition and allocation of execution of the problem to these resources is complex and usually doesn't happen in the default settings of the various coding systems.  In your test case you were probably using a single core in the processor, which was likely also hosting everything else happening in the machine, and probably not using the graphic processor at all.  Some compilers can do part or all of this, but I can provide no advice here.  Look into multi-threaded operations.

[DiTBho]

Labview, Matlab, and Octave are of the same level, and both are good for fast prototyping.
Labview and Matlab have a sort of external compiler suite for DSP-specific stuff.

[SiliconWizard]

Julia.

[tszaboo]

It's slow, because it's not pytonic. It's a common mistake, you are trying to write code in C (ie) and just translate that to python it's going to be slow.
You can rewrite the for loops to be a list comprehension, for starters, that would make it faster.
But the filtering that you are doing, do that with numpy. You can compare scalars with matrices.
You typically only want to write for loops if you are doing something very very specific.

[alm]

The first is the language you use to implement the solution.  Python is an interpreted language, meaning that each time through all the code loops the computer translates the instructions into the appropriate machine code, and then does the actual work.

No, this is not at all how Python works. When you execute a piece of Python code it will first compile all source code to byte code, not unlike Java bytecode. Or load the cached byte code if it was compiled before. This bytecode is then executed on a VM. This is definitely not as fast as the JVM, but that's not due to interpreter overhead, but rather the trade off of a more dynamic language vs a more static language.

The second is how cleverly the algorithm is arranged. 

I'd say this is number one. The benefit of switching to a more efficient language is peanuts (a factor 3 in the above example) compared to the orders of magnitude improvement that can be achieved with a better algorithm, although this may also be the hardest. I glanced at the algorithm and it looked like the type you'd write for teaching: naive and straight-forward.

In your test case you were probably using a single core in the processor, which was likely also hosting everything else happening in the machine, and probably not using the graphic processor at all.  Some compilers can do part or all of this, but I can provide no advice here.  Look into multi-threaded operations.

In Python the trick to dealing with large amounts of data is to have libraries like NumPy do the heavy lifting. These libraries use the same BLAS and LAPACK linear algebra libraries that are also used by Octave and MATLAB. Many BLAS/LAPACK implementations are multi threaded, so if you call those NumPy functions from Python, they should run very efficient multi-threaded C/Fortran code. The Python code just has to feed data to these functions.

[CatalinaWOW]

The first is the language you use to implement the solution.  Python is an interpreted language, meaning that each time through all the code loops the computer translates the instructions into the appropriate machine code, and then does the actual work.

No, this is not at all how Python works. When you execute a piece of Python code it will first compile all source code to byte code, not unlike Java bytecode. Or load the cached byte code if it was compiled before. This bytecode is then executed on a VM. This is definitely not as fast as the JVM, but that's not due to interpreter overhead, but rather the trade off of a more dynamic language vs a more static language.

The second is how cleverly the algorithm is arranged. 

I'd say this is number one. The benefit of switching to a more efficient language is peanuts (a factor 3 in the above example) compared to the orders of magnitude improvement that can be achieved with a better algorithm, although this may also be the hardest. I glanced at the algorithm and it looked like the type you'd write for teaching: naive and straight-forward.

In your test case you were probably using a single core in the processor, which was likely also hosting everything else happening in the machine, and probably not using the graphic processor at all.  Some compilers can do part or all of this, but I can provide no advice here.  Look into multi-threaded operations.

In Python the trick to dealing with large amounts of data is to have libraries like NumPy do the heavy lifting. These libraries use the same BLAS and LAPACK linear algebra libraries that are also used by Octave and MATLAB. Many BLAS/LAPACK implementations are multi threaded, so if you call those NumPy functions from Python, they should run very efficient multi-threaded C/Fortran code. The Python code just has to feed data to these functions.

I'll trust you on how Python is implemented, since I don't know the details and was merely quoting internet explanations.  However it works it is painfully slow compared to similar code fully compiled for the target processor.  In my experience far more than a factor of three slower, but I am sure it depends heavily on what you are doing.

I also agree that when appropriate libraries like NumPy do exactly as they are supposed to do and speed things up tremendously. The bottom line though is that Python, Matlab and Octave are intended to be easy to use ways to mash and crunch numbers.  People time is usually harder to come by than machine time so it is a appropriate for them to sacrifice speed to save people time.  Libraries can make this trade less painful, but they are not the right tools for something that needs speed and is done over and over again.

It is much like the difference between a 3D printer and an injection molding machine.  Both are great tools.  But not for the same jobs, even though they often can make the same parts.