Author Topic: Fast median algorithm  (Read 3327 times)

mineiro

  • Member
  • ****
  • Posts: 615
Re: Fast median algorithm
« Reply #150 on: August 04, 2020, 09:29:44 PM »
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

mineiro

  • Member
  • ****
  • Posts: 615
Re: Fast median algorithm
« Reply #151 on: August 04, 2020, 11:05:33 PM »
Hello sir guga;
I build this image years ago, can you apply your tool in this image and upload result?
Original image is .gif, if you adjust zoom to 50% and rotate/mirror/flip image you should get these others images showed below.
Original image:

This is what you can get from that image:








I'd rather be this ambulant metamorphosis than to have that old opinion about everything

daydreamer

  • Member
  • *****
  • Posts: 1350
  • building nextdoor
Re: Fast median algorithm
« Reply #152 on: August 05, 2020, 03:12:38 AM »
Hypnotoad :biggrin: :biggrin: :biggrin: :biggrin: :greensml: :greensml: :greensml: :greensml:


Oops ended up in game forum,preview of the soon to be released "froggy 2020"  :greenclp: :greenclp: :greenclp:
Quote from Flashdance
Nick  :  When you give up your dream, you die
*wears a flameproof asbestos suit*
Gone serverside programming p:  :D
I love assembly,because its legal to write
princess:lea eax,luke
:)

guga

  • Member
  • *****
  • Posts: 1274
  • Assembly is a state of art.
    • RosAsm
Re: Fast median algorithm
« Reply #153 on: August 05, 2020, 04:21:48 AM »
Hi Mineiro.

You mean, this ?



This is the result i´ve got after applying the code onto your image. But the tool is not finished. This part of the code i was fixing last night and seeing the results just for fun. The function was not supposed to do this :greensml: :greensml: :greensml:

But if you want the steps to do it, basically all i did was:

1 - Convert the image to gray
2 - Equalized the image (with a general histogram equalization algorithm, not Clahe)
3 - Applied the sobel algo over the resultant image
4 - Equalized the result again. So, i equalized over the generated sobel image)
5 - Applied the generated equalized image over the original colored one. But, the routine to do this only applies on high frequencies of sobel, all the rest is left as 0 (black).  The math to do this is: sqrt(((SobelG-128)*2)^2 + Luma^2). or a pseudocode:

If SobelG > 127
  NewPix =     sqrt(((SobelG-128)*2)^2 + Luma^2)
Else
   NewPix = 0
End_If

6 - Applied the value of NewPix (which is a new luma) on the original image with CieLab. So, i stored previously the values of Luma, a and b factor of CieLab of the original image and simply replaced the Luma on the original image with this new value.


But..again..this is not what the algo was supposed to do :mrgreen: :mrgreen: :mrgreen:. The goal is to apply sobel values over the whole image without ruining it to enhance the edges
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

guga

  • Member
  • *****
  • Posts: 1274
  • Assembly is a state of art.
    • RosAsm
Re: Fast median algorithm
« Reply #154 on: August 05, 2020, 04:27:45 AM »
Hypnotoad :biggrin: :biggrin: :biggrin: :biggrin: :greensml: :greensml: :greensml: :greensml:


Oops ended up in game forum,preview of the soon to be released "froggy 2020"  :greenclp: :greenclp: :greenclp:

 :greensml: :greensml: :greensml: :greensml: :greensml:
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

mineiro

  • Member
  • ****
  • Posts: 615
Re: Fast median algorithm
« Reply #155 on: August 05, 2020, 08:33:05 AM »
Hello sir guga;
Yes, I mean that. Thank you.
I just like to check if main image stand out over others.
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

Siekmanski

  • Member
  • *****
  • Posts: 2314
Re: Fast median algorithm
« Reply #156 on: August 06, 2020, 02:31:15 AM »
Played around with the Sobel Operator convolution calculations.
Simplifying the math and keeping it logical.
Reason, make them suitable for fast parallel SSE2.

Faster Sobel Operator Convolution:

Code: [Select]
         [-1 -2 -1 ]
SobelX = [ 0  0  0 ] = 0 degree
         [+1 +2 +1 ]

         [-1  0 +1 ]
SobelY = [-2  0 +2 ] = 90 degree
         [-1  0 +1 ]

         [ P1 P2 P3 ]
Pixels = [ P4 P5 P6 ]
         [ P7 P8 P9 ]
Code: [Select]
Convolution with simplified math:
GradientX = (P7 + 2*P8 + P9) - (P1 + 2*P2 + P3)         ; - if edge is on the left side, + if on the right side
GradientY = (P3 + 2*P6 + P9) - (P1 + 2*P4 + P7)         ; - if edge is on the top side, + if on the bottom side
Code: [Select]
Convolution without multiplications:
GradientX = (P7 + P8 + P8 + P9) - (P1 + P2 + P2 + P3)   ; - if edge is on the left side, + if on the right side
GradientY = (P3 + P6 + P6 + P9) - (P1 + P4 + P4 + P7)   ; - if edge is on the top side, + if on the bottom side

Now we can use fast SIMD, shuffle them in place and add them together and do 2 subtractions.  :cool:
Creative coders use backward thinking techniques as a strategy.

guga

  • Member
  • *****
  • Posts: 1274
  • Assembly is a state of art.
    • RosAsm
Re: Fast median algorithm
« Reply #157 on: August 06, 2020, 03:40:25 AM »
Great  :thumbsup: :thumbsup: :thumbsup: :thumbsup:

Also we need to normalize the result, right ?
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7531
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Fast median algorithm
« Reply #158 on: August 06, 2020, 06:14:32 AM »
I have not really kept up with this topic but it sounds like an algorithm that does sharpening and smoothing, depending on the settings. I use an ffmpeg option for doing this type of work on 1080 and 4k video.
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

Siekmanski

  • Member
  • *****
  • Posts: 2314
Re: Fast median algorithm
« Reply #159 on: August 06, 2020, 06:33:51 AM »
Great  :thumbsup: :thumbsup: :thumbsup: :thumbsup:

Also we need to normalize the result, right ?

Maybe, maybe not, that's the question.  :biggrin:
Have to implement it first, and see if threshold clamping is an option.

Just finished a routine to save the gray color conversions to memory.
It handles 4 pixels at once and takes care of any possible "rest pixels".
It has a Stride for the width, wich is always a multiple of 16 bytes, no matter if the bitmap width is not divisible by 4.
Works like charm and is very fast.
I wrote it for SSE2 but it can be made faster for SSE4.1 if needed.
And this routine is a good candidate for multithreading if it is needed in realtime video processing.

Hi Hutch,

It's for edge detection in bitmaps.
guga want's to use it for removing watermarks.
I collaborate with him to learn a few new things.
Creative coders use backward thinking techniques as a strategy.

guga

  • Member
  • *****
  • Posts: 1274
  • Assembly is a state of art.
    • RosAsm
Re: Fast median algorithm
« Reply #160 on: August 06, 2020, 08:36:43 AM »
I have not really kept up with this topic but it sounds like an algorithm that does sharpening and smoothing, depending on the settings. I use an ffmpeg option for doing this type of work on 1080 and 4k video.

Hi Steve

The algorithm is to detect edges on a image (or video). What i´m trying to do is adapt a amazing algorithm developed by google that removes watermarks and makes the image be perfect. And later (if we suceed) this can be adapted to do the same for videos.

FFMpeg, for example, have a built in function (or plugin, i don´t remember) that removes the logo of videos or watermarks etc, but it is far from perfect. With google algorithm we can extend the functionality to remove whatever imperfections we have on a video or image.

It was designed to remove watermarks, but, in fact, it can remove all sort of imperfections, such as lens crack on a camera, fog, scratches, spots, dirt etc. So, whatever is in front of the image that works as a unwanted layer can be completely removed.

For example, if we have a video containing scenes that were ruined by a lens crack such as the image below:


This can be completely removed (as long the layer (watermark, crack, dirt etc) is fixed). It´s an amazing algorithm and seems to produce a quite perfect result. But it is a hell to port , since it´s written in python and i don´t know python language, i´m struggling to understand the logic behinds it.

Note: Also, if we would apply the same logic (and with some extra work), then we could also remove any background (or any other object) from a video or image and replace with whatever we want (as long the background is fixed) on a way faster, easier and more accurate then premiere, Mocha etc.
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

guga

  • Member
  • *****
  • Posts: 1274
  • Assembly is a state of art.
    • RosAsm
Re: Fast median algorithm
« Reply #161 on: August 06, 2020, 09:36:43 AM »
Great  :thumbsup: :thumbsup: :thumbsup: :thumbsup:

Also we need to normalize the result, right ?

Maybe, maybe not, that's the question.  :biggrin:
Have to implement it first, and see if threshold clamping is an option.

Just finished a routine to save the gray color conversions to memory.
It handles 4 pixels at once and takes care of any possible "rest pixels".
It has a Stride for the width, wich is always a multiple of 16 bytes, no matter if the bitmap width is not divisible by 4.
Works like charm and is very fast.
I wrote it for SSE2 but it can be made faster for SSE4.1 if needed.
And this routine is a good candidate for multithreading if it is needed in realtime video processing.

Hi Hutch,

It's for edge detection in bitmaps.
guga want's to use it for removing watermarks.
I collaborate with him to learn a few new things.

Hi Marinus

In SSE2, please. So it would be good to people uses in older machines. Also, i don´t have the way to port it to SSE4 with RosAsm yet. (Didn´t implemented SSE3 and SSE4 opcodes yet onto it)


Btw... how do i multiply 4 Floats (or dword) in SSE2 register with one single Float ? And also how to add or subtract specific floats from a register ?

Ex:

Say i have in xmm0 this:

15 25 99 100

and i want to multiply each one of these values with let´s say 1.5

How do i do it ?


I´m asking to see how to port to SSE this:

Gx = A*(M1+M7-M3-M9) + D*(M4-M6)
Gy = A*(M1+M3-M7-M9) + B*(M2-M8)
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

Siekmanski

  • Member
  • *****
  • Posts: 2314
Re: Fast median algorithm
« Reply #162 on: August 06, 2020, 09:58:12 AM »
Code: [Select]
15 25 99 100 in xmm0

movss  xmm1,FLT4(1.5) ; move a single float in xmm1
shufps xmm1,xmm1,0      ; xmm1 =  1.5,  1.5,   1.5,   1.5
mulps  xmm0,xmm1        ; xmm0 = 22.5, 37.5, 148.5, 150.0

subtract and add single floats:
Code: [Select]
subss xmm0,xmm1
addss xmm0,xmm1

subtract and add 4 floats at once:
Code: [Select]
subps xmm0,xmm1
addps xmm0,xmm1
Creative coders use backward thinking techniques as a strategy.

guga

  • Member
  • *****
  • Posts: 1274
  • Assembly is a state of art.
    • RosAsm
Re: Fast median algorithm
« Reply #163 on: August 06, 2020, 11:41:46 AM »
Code: [Select]
15 25 99 100 in xmm0

movss  xmm1,FLT4(1.5) ; move a single float in xmm1
shufps xmm1,xmm1,0      ; xmm1 =  1.5,  1.5,   1.5,   1.5
mulps  xmm0,xmm1        ; xmm0 = 22.5, 37.5, 148.5, 150.0

subtract and add single floats:
Code: [Select]
subss xmm0,xmm1
addss xmm0,xmm1

subtract and add 4 floats at once:
Code: [Select]
subps xmm0,xmm1
addps xmm0,xmm1

Great. Thank you a lot. I´ll give a try in optimize one routine a little bit before go further with the crop_watermark routine.


Take a look at the result after using the normalization. It found the watermark from only 3 true different images among 107 similar ones.   :thumbsup: :thumbsup: :thumbsup:

So, to identify the watermark, we mainly need a couple of different images, indeed :) This will be awesome if we succeed to port it to work with videos :thumbsup: :thumbsup: :thumbsup:


Note: The image is a bit too dark, because i didn´t enhanced the edges pixels. For now, it seems not to be necessary to create the shape :)
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7531
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Fast median algorithm
« Reply #164 on: August 06, 2020, 12:29:17 PM »
Hi Guga,

I think I understand what you are doing and an edge detection algo is a lot more useful than just removing water marks, it can also be used for both smoothing rough images or sharpening slightly blurry ones. What I suggested originally was a technique that I have been using for years, close proximity cloning to get the field depth correct and match the texture where possible.



The original on the left, the modified on the right. I used some Russian software to remove the buttons and manually cloned the background to get rid of the insignia. My comment is you can do both as both techniques have their advantages and between them the watermarks you want to remove can be filled in with a texture that maintains the correct field depth.
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy: