Position of object on image without AI/ML — Jump flooding algorithm
Idea — select object on image as image mask and generate SDF to get position of this object. Also use Mipmap layers to optimize logic.
Implementation — links provided in description.
This is not tutorial.
Content:
- Single frame JFA base implementation — by Inigo Quilez.
- Optimized realtime JFA — by Flyguy on Shadertoy.
- SDF to single position-coordinate.
- Overview of possible Mipmap optimizations.
- Object detection using only Mipmap layer — by FabriceNeyret2.
Single frame JFA base implementation:
Jump flooding algorithm on Wikipedia.
Great implementation by Inigo Quilez — Signed Jump Flooding.
Signed Jump Flooding, to create a SIGNED distance field of a shape of which we only know it’s inside and outside regions.
This implementtion use 10 to 16 passes to generate SDF to mask.
And for-loop use alot-of-texture-steps((passes x2)² per pass) to build SDF.
But result is very high quality.
it is possible to do in real time — that will cost 10–16 “compute-layers” — fine for most of modern GPUs performance but can be optimized.
Optimized realtime JFA:
Van Damme — Distance — by Flyguy on Shadertoy.
It better for real time use — because there only:
for(int i = -1; i <= 1; i++)
{
for(int j = -1; j <= 1; j++)And only 6-passes — used single cubemap buffer and every cube-face look on other-previous cube fase to build JFA.
(this why it delayed by 6 frames from video — can be improved by procesing 6 buffers one after other)
Because this is so “cheap” by performance — it will work literally on anything — performance can be calculated linearly.
((Multiply image resolution x*y) x3x3) x6
For 256x256 image it will be 3538944 iterations — multiply by 100(~number of operations per iteration) = around 400MHz single core processor can be enough to preceess it in real time.
Screenshot on top of this article is from this implementation — screenshot displaying SDF-normal arows.
SDF to single position-coordinate:
Simple — get multiple points-normals and calculate center.
(summ of vectors)
To get better position of center — more points needed.
But summ of multiple points — is Mipmap.
You can just apply mipmap layer to SDF and get better position with less points.
Overview of possible Mipmap optimizations:
Not a single JFA algorithm above use Mipmaps.
When core of JFA — is loop in some range of pixels to “blur the edge”.
I think Mipmaps can be used in JFA to find object bound-box, to get center-position, and even to implement full JFA thru mipmaps.
Object detection using only Mipmap layer:
Notice:
FabriceNeyret2 blog — GPmipmap Mipmap Advanced tricks.
Cotext — dynamic centering Britney FabriceNeyret2 Shadertoy shader.
And — tracking van damme(almost free)2.
Look at these implementations — used only Mipmap layer to get position of mask.
And as “algorithm” — is single line textureLod(iChannel1, vec2(.5), 99.)
Just read last Mipmap layer — last Mipmap layers is "average summ of all pixels".
Very interesting and impressive discovery by FabriceNeyret2!
This is so cheap by compute-performance — it require no compute, just memory reading and Mipmaps calculation can be done on hardware level — literally just scale-connect memory linearly — no compute.
