Author Topic: Fast median algorithm  (Read 3321 times)

Siekmanski

  • Member
  • *****
  • Posts: 2314
Re: Fast median algorithm
« Reply #105 on: July 27, 2020, 09:28:55 AM »
My idea is:

- load an image.
- convert the colors to gray colors to memory in real4 format.
- use real4 format for the sobel or median sobel.
  and save the real4 G results ( are always positive ) as bytes in memory ( for 100 images )
- then calculate the 100 pixels median of each x/y position in the 100 images.
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 #106 on: July 27, 2020, 02:27:39 PM »
A threshold won´t help on this case because we have no idea how much noise will be removed and neither were they could be located. We can have noise with 30 pixels near each other with intensity in between 150 that has the same intensity as the true watermark.


About the median calculation, the negative values are necessary because they do affect the result. Take for example these numbers:

Say we have 7 images and at Pos (x = 50, Y = 75) we have this values on each one of them:

Gy (at pos 50/75) of :-1, 5, -17,100,220,-50, 9 ( So, -1 for image1, 5 for image2, -17 for image 3 and so on...)

The median of these value (on that Pos) is 5

If we set all to positive, the median will result on a different value

Gy (at pos 50/75) = 1,5,9,17,50,100,220 = 17

And the way the algo works, it does not calculates the G (sobel) directly from each Gy and Gx. It computes the Sobel from the median of Gy and Gx. And this median is calculated among different images and not from the same image.

One the previous test (the one with a cleaner result) i made that way. I mean, i simply calculated the Sobel on each image and took the median of the Sobel from them to see the result. Although the image is cleaner, it still have some noise and the algo uses the median separatelly from each to generate a cleaner Sobel image.
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 #107 on: July 27, 2020, 02:33:16 PM »
My idea is:

- load an image.
- convert the colors to gray colors to memory in real4 format.
- use real4 format for the sobel or median sobel.
  and save the real4 G results ( are always positive ) as bytes in memory ( for 100 images )
- then calculate the 100 pixels median of each x/y position in the 100 images.

Thats what i did previously, but it´s not how the algo works. Since the resultant values of the median of Gx and Gy using negative and positive values are completely different then simply calculating the G directly from them, the resultant G will not be the same as the result i´ve got (even it is clean on this images i tested). Using separate medians of Gy and Gx to compute the final G is the way the algo is actually working, and it probably will clean the result even more, no matter if we use 100 images or more.

The 100 images it is not a rigid limit, it is set that way just to an approximation but, we can have cases that it will be needed more than that and cases we could need only a few images. It always depend on how much different they are. On video, for example, limiting to 100 images won´t work too good, because 100 images can easily represent the same scene, so we will have 100 images where the algo could fail.


In terms of values, take the values on the example i posted previously.

Imagine we have only 7 images and we are calculating the Sobel Gx and Gy at Pos (x = 50, Y = 75).

The correct way the algo is using is converting them to gray and calculating the Gx and Gy for each image (at that same pos). Like this:

Gy (at pos 50/75) :-1, 5, -17,100,220,-50, 9 ( So, -1 for image1, 5 for image2, -17 for image 3 and so on...)

The median of these value (on that Pos) is 5. (On this example, the result is positive, but, can be negative as well).

Say we have at Gx the values (at the same pos) like this:

Gx (at pos 50/75) = 1,5,9,17,50,100,220 = 17

So, for Pos (50/75) we have the resultant G = sqrt(5^2+17^2) = 17.72.... The correct result.


But...if we did as i did before we will have:

G (at pos 50/75) : sqrt((-1^2)+1^2), sqrt(5^2+5^2), sqrt((-17)^2+9^2) .....

G (at pos 50/75) = 1.41421356, 7.071068, 19.23538, 101.4347, 225.6103, 111.8034, 220.184

And the resultant G median  of the above values is (on the same pos): 101.4347 The incorrect value.


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 #108 on: July 27, 2020, 03:46:35 PM »
Guga,

I doubt there is an exhaustively good way to remove a watermark, just for practice I have done it with a few photos and the best after tweaking what you can is done by cloning areas close to where the water mark is. While the human eye is tolerant on many things, field depth is not one of them and cloning from about the same field depth keeps at least that aspect looking OK. On an image it is basically texture that your eye will pick if you get it wrong.

If you can sample the colour(s) used in the water mark you can try reducing that specific set of colours from the masked areas of the water mark. I have recently got a piece of Russian software that appears to be designed for altering images of people (mainly pretty girls) but it can do some useful things, it seems to do some form of AI cloning the close area and filling in the gaps. Its not perfect but it does look OK if you have a bit of practice.
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

guga

  • Member
  • *****
  • Posts: 1274
  • Assembly is a state of art.
    • RosAsm
Re: Fast median algorithm
« Reply #109 on: July 27, 2020, 04:14:45 PM »
Guga,

I doubt there is an exhaustively good way to remove a watermark, just for practice I have done it with a few photos and the best after tweaking what you can is done by cloning areas close to where the water mark is. While the human eye is tolerant on many things, field depth is not one of them and cloning from about the same field depth keeps at least that aspect looking OK. On an image it is basically texture that your eye will pick if you get it wrong.

If you can sample the colour(s) used in the water mark you can try reducing that specific set of colours from the masked areas of the water mark. I have recently got a piece of Russian software that appears to be designed for altering images of people (mainly pretty girls) but it can do some useful things, it seems to do some form of AI cloning the close area and filling in the gaps. Its not perfect but it does look OK if you have a bit of practice.

Hi Steve

I thought that too, until i saw the results of the google technique. What it did was, basically finds the areas of an image who have a watermark, then rebuild this watermark, then calculate the alfa (transparency) of them, and apply the inverse results. it works, on the same way as we are doing a layer in Photoshop or Paint Shop pro to insert a watermark. What it did was recover back the layers, including the  value of the alpha channel.

I don´t know which russian software is this, but, generally speaking (for videos), i saw some of those techniques being applied by russian apps (for virtualdub, for example), that they basically estimates where the watermark is and tries to cover it with the surrounded pixels. Some do a good job, others are lousy and the watermark always is blurred.

Those apps that alter people faces seems to use  a technique called "poisson reconstruction" (which, btw, that maybe used on the app you got) that is take an image from some place and putting onto another keeping the texture of the target face intact. (Similar to what deep face does) in videos, like these:

https://www.youtube.com/watch?v=AeRofGJ17Sk

In what concerns deep face (aka deep fake - although i don´t like the term) the technique is amazing, specially for image reconstruction.  With deep face and other techniques we can take an video from 1910 for example, and simply rebuild it completely, making it appears as it was shot today.

The technology evolving image processing is advancing day-by-day and is extraordinary the possibilities of usage.  The same thing goes for audio. Adobe developed a couple of years ago an  research app that could take the voice of someone and simply rebuild it to sounds like another one. The demonstration video i saw, the guy simply took the voice of someone, used it as a database, and then start typing  some text he wanted the app to read.  Then, the algo read the text and used the voice automatically generated to simulate the speech. It is a way advanced text to speech technique with natural results that can mimic the voice of anyone. This, btw, is also interesting for me, because we can recreate lost dubs of old movies easily using this technique bringing to life the sound of  golden actors/dubbers dead long time ago.

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 #110 on: July 27, 2020, 08:29:32 PM »
Hi Marinus



I think i´ve got it working as expected. :thumbsup: :thumbsup: :thumbsup:

Take a look at this image and compare with the previous one




This method, indeed, eliminates almost all the noise from the watermark. So, it seems that this is the correct path to go. I´ll move on the next part of the algo that involves cropping the watermark and see what happens.

So, the correct way to reach untill this step is:

1 - Convert N images to gray
2 - Calculate the Sobel Gx and Gy for each one of them. So we will have 2*N new images representing both sobels)
3 - Calculate the median of all Gx found (without changing their signs) , calculating on each pixel at that same position for all images (as explained on previous threads).
4 - Calculate the median of all Gy Found (without changing their signs), calculating on each pixel at that same position for all images (as explained on previous threads).
5 - With the resultant medians in step 4, then we calculate the final Sobel G
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 #111 on: July 27, 2020, 08:56:21 PM »
 :cool:

That looks perfect.  :thumbsup: :thumbsup:
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 #112 on: July 28, 2020, 05:39:39 AM »
Hi Marinus

I´m working on the cropping. I analyzed how the cropping routine "crop_watermark" in the python version works.  For what i saw so far, they set a threshold on the resultant image and set the coordinates of the rectangle formed by it.

So, once we found a Sobel of the medians of Gx and Gy, the routine simply normalizes the values of this image (the edges, in fact) and set a threshold. If the pixels are higher then 0.4 then all those pixels are turned onto White (255), otherwise they are settled to black (0). It creates a kind of 'shape' formed by the watermark, and it then gets the coordinates of all pixels settled with white and get the max and min pos to see where they starts and where they ends, calculating the X and Y pos to the 1st  white pixel until the last one, he do this in the width and on the height. Simulating a sort of shape of the area of the watermark (in fact, it creates a rectangle around the watermark).

The problem is that, i fixed the sobel operator to avoid the extrapolating the values, resulting on a image cleaner and with edges more thin. Therefore, when i set the threshold to 0.4, it results on a loss of the edges on the resultant shape. It also happens on the python version, but i cannot evaluate the result of the python because my PC freezes when i go further with it and with visual studio.

I analyzed the resultant image i create in PaintShop Pro and found that, maybe i can use the median again of all pixels on the generated result to set a better threshold biased on the texture of the resultant image itself, rather then guessing like it is done in the python version.

I´ll do this and check the results and maybe, do some fine tuning on the fix i made on sobel to allow enhancing the image on user choice when sobel finds the bad pixels. In theory, adjusting the "threshold" directly through sobel errors may fix the cropping routine as well, since all medians of the whole image should be more equalized.

Using the same threshold as in the python version and with 50 images as a guidance, it generated this shape. Threshold 0.4:


Setting the threshold to 0.2, the other lines of the shape starts to appear on the real watermark. T 0.2



I can also try later using a sobel of the resultant sobel to see what happens. It also could be more useful, since my sobel adaptation tends to equalize the whole image. The main problem is the fact that maybe passing another sobel filter on the resultant median of sobel could also result in more noise that would demand cropping again.

I´ll see what is better to do.

For now, i have a couple of strategies:

1 - Get the median of the resultant sobel to set the proper threshold.
2 - Adjust my adaptation of the sobel filter to it better handles in what do do with bad pixels
3 - Do strategies 1 and 2 together
4 - Apply a sobel of the sobel and do the steps 1 and 2 above.
5 - Use Scharr operator rather then sobel. (The problem in doing this, is the fact that the python version don´t uses it at all and it could be even harder to follow what they are actually doing.) So, we can exchange the edge operator filter only after we suceed to make this huge white elephant sing :greensml: :greensml: :greensml: :greenclp: :greenclp: :greenclp:
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 #113 on: July 28, 2020, 07:14:20 AM »
Great progress.  :cool:

I'm not that far yet, still working on the graphics tool for these operations.
It's cool to experiment, we can learn a lot from it.  :biggrin:
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 #114 on: July 28, 2020, 07:32:32 AM »
Sure...We can learn a lot from this. Those image processing techniques are awesome :smiley: :smiley: :smiley:

I´m doing tests on the results and i can discard one of the strategies.


Step  4 Can be discarded. Applying a sobel over a sobel generates noise (btw...beautiful images :greensml: :greensml: :greensml:). But, it can be used to fix sobel operator even further, since from the resultant images you can see the errors in the borders.

Take a look at this animated blob little 'coronga' monster i created :mrgreen: :mrgreen: :mrgreen:



The watermark got a severe flu :mrgreen: :mrgreen: :mrgreen:

I applied an iteration of 10 times to achieve this. generated the sobel from the medians and then applied sobel over sobel over sobel....10 times :greenclp: :greenclp:

The 2nd iteration worked to enhance the thinner edges, but added some noise in between areas that were supposed to be black. So, we can discard this step.

I´ll apply step1 and see what happens
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

daydreamer

  • Member
  • *****
  • Posts: 1350
  • building nextdoor
Re: Fast median algorithm
« Reply #115 on: July 28, 2020, 10:12:43 AM »
Congrats guga,enough Iterations you can sell it as new Godzilla  :greenclp:

can't it be fixed with some filter out single alone pixels?
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 #116 on: July 28, 2020, 12:37:36 PM »
Congrats guga,enough Iterations you can sell it as new Godzilla  :greenclp:

can't it be fixed with some filter out single alone pixels?
:greensml: :greensml: :greensml: :greensml:

Probably it wouldn´t help that much on the way the algo works already. When the final sobel is applied it already removes all isolated pixels. I´m working with different watermarks and trying to see what exactly the algorithm is doing on each one of them. For example this last test i made, it did a quite perfect job in refining the edges and eliminating a lot of noise. The problem is that since i fixed the sobel operator, when it is needed to create a shape for the watermark, it removes the edges that are too dark thinking that it is also noise.

Of course, this happens if the images i´m scanning are not enough (100 is not enough if the images are similar to each other) or have similar textures etc.

If i use the same method as in the python version, it also won´t work, because i can´t actually see the result on python to compare what it is doing with what i´m doing. In python, for example, it uses a threshold that the user chooses to remove the bad pixels, but this won´t work on all images set and i want it to be completely automatic as it is written in the google article.

So, instead using a user made threshold i´ll make a test using the standard deviation of the generated image to calculate a threshold. The STD i´ll most likely use the Minimum Standard Deviation which is closer to error cases in statistics, i presume.

Once i get the value from the Standard Deviation i can then calculate the median of the whole image to establish a threshold (if needed, because if the result is ok, i can simply use the std removal and voilá :mrgreen: :bgrin: :bgrin:).

I need only to see how the algo behave with different images in order to try to see if there is a sort of pattern on all of them.  Because if after using the standard deviation to set a threshold, it still have some issues when creating the shape, i´ll have no alternative, except:
1 - Allow more user control on this.
2 - Review the fine tune i made in sobel operator to it allows some errors  and noise (I really don´t want it to, but...if that could help on the final result of creating the shape, i´ll have to do it)
3 - If all fails or still result in something weird, i´ll use scharr operator and see what happens.

Since i understood how to crop the image and what exactly the python version is doing on this stage, then i can try adjusting the initial analysis of the algo before going further rebuilding the watermark or before loading the image from where the watermark should be detected from.

The main problem is that there´s no magic bullet. We need to do it in try and error, trying to understand how google made it, and also how the python version works for that. The most important is make this beast works somehow. If we succeed, then we can try adjust it, refine, optimize and so on.
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 #117 on: July 30, 2020, 04:42:07 AM »
Hi Marinus, here is the code for the Sobel Function i made (Unoptimized yet. I want to guarantee the result is perfect before  do any optimization). And check the results using the variation of your algo JJ did :angelic: :angelic: I have some questins to make to him, but i´ll do it later.

Code: [Select]

; Equates used  as flags to the type of fix we want onto the sobel operator.
[SOBEL_FIX_TRUNCATE 0] ; Normal result. Only truncated all above the limits of -255 and 255
[SOBEL_FIX_SIMPLE 1] ; common adjust of the edges. Much better.

; Equates used on the matrix
[FloatMatricesInt.M1Dis 0
 FloatMatricesInt.M2Dis 4
 FloatMatricesInt.M3Dis 8
 FloatMatricesInt.M4Dis 12
 FloatMatricesInt.M5Dis 16
 FloatMatricesInt.M6Dis 20
 FloatMatricesInt.M7Dis 24
 FloatMatricesInt.M8Dis 28
 FloatMatricesInt.M9Dis 32]

[Size_Of_FloatMatricesInt 36]

[Float_SobleVarG: R$ 180.3122292025696187222153123367365]; 255/sqrt(2)) . This is a variable used to speed up the math when computing the G

;;

    SobelGetGPLusEx
        Calculates the Sobel operator for a given amount of pixels stored opn a 3x3 matrix
   
    Parameters:

        pMatrix(In):    The Inputed pixels stored on a 3x3 matrix where the Sobel edges are calculated. The input values must be in Real4 format from 0 to 255. (No integer yet. I´ll adapt to handle integers later)
                        To make easier understand, the matrix is written using equates and the values must be previously calculated and filled.
                        The format of the matrix is:
                       
                        M1 M2 M3
                        M4 M5 M6
                        M7 M8 M9
                       
                        So, at Point M1, Pixel at pos X0, Y0
                               Point M2, Pixel at pos X1, Y0
                               Point M3, Pixel at pos X2, Y0
                               Point M4, Pixel at pos X0, Y1
                               Point M5, Pixel at pos X1, Y1
                               Point M6, Pixel at pos X2, Y1
                               Point M7, Pixel at pos X0, Y2
                               Point M8, Pixel at pos X1, Y2
                               Point M9, Pixel at pos X2, Y2

        pOutSobelX(out): Pointer to a variable that will Store the SobelX value (Magnitude in X direction. I.e.: Gx).
                         The stored value can be negative, positive or zero. All in Real4 format from -1 to 1

        pOutSobelY(out): Pointer to a variable that will Store the SobelY value (Magnitude in Y direction. I.e.: Gy).
                        The stored value can be negative, positive or zero. All in Real4 format from -1 to 1

        pOutSobel(Out): Pointer to a variable that will Store the Sobel value (Total Magnitude of the pixel. I.e.: G).
                        The output is a positive Integer value from 0 to 255. The magnitude of Sobel operator is given by:
                            G = sqrt(Gx^2+Gy^2)

        FixType(In):    A flag able to fix the Sobel operator when it exceeds the limits of -1 to 1 (Normalized)
                        It´s common to the Sobel Operator extrapolates the resultant limits (-255 to 255. Or -1 to 1, normalized)
                        We can see values (unormalized) in the order of -600, 482, 265, -258, -780 etc etc
                       
                        Currently, in order to fix that 2 Flags can be used:
                       
                        SOBEL_FIX_TRUNCATE (Value = 0). Simply truncates the values of Gx and Gy to -1 (if the result is too dark) or 1 (If the result is too bright)
                        SOBEL_FIX_SIMPLE  (Value = 1). Fix the values adjusting the extrapolation to it stays within the limits.
                                                       The math envolving is this fix is: FixedValue = OldValue/(255*(floor(|OldValue|/255)+1))
                       
        pDegree(Out/Optional): A Pointer to a variable to store the Angle formed by the pixel. Sobel Operator can be used to calculate the angle (direction) of the Pixel.
                               It outputs the angle in Degrees. The format of the output is always in real4 format from 0º to 360º.
                               This parameter can be &NULL if you don´t want to exprt the angle.

        Return Values:
                    The function does not return any value.

    Example of usage:

    [MyMatrix: F$ 25, 200, 30
                  100, 45, 75
                  0, 81, 255]

        call SobelGetGPlusEx MyMatrix, MySobelX, MySobelY, MySobel, SOBEL_FIX_SIMPLE, &NULL
   
;;

Proc SobelGetGPLusEx:
    Arguments @pMatrix, @pOutSobelX, @pOutSobelY, @pOutSobel, @FixType, @pDegree
    Local @pReturn, @DataCheck, @Divisor, @FractionX, @FractionY, @Floor, @YAxis, @XAxis
    Structure @TempAxis 16, @SobelYAxisDis 0, @SobelXAxisDis 8
    Uses edi, edx, ecx, eax

    finit

    mov edi D@pMatrix

    ; To calculate Gx^2 later. Therefore Gx = M3+M9 + 2*(M6-M4) - (M7+M1)
    fld F$edi+FloatMatricesInt.M6Dis | fsub F$edi+FloatMatricesInt.M4Dis | fmul R$Float_Two
    fadd F$edi+FloatMatricesInt.M3Dis | fadd F$edi+FloatMatricesInt.M9Dis
    fsub F$edi+FloatMatricesInt.M7Dis | fsub F$edi+FloatMatricesInt.M1Dis
    lea ecx D@DataCheck | fistp F$ecx
    .If D@DataCheck = 0

        fldz | fstp F@FractionX

    .Else_If D@DataCheck <s 0-255 ; Blacks. Edge too dark.

        If D@FixType = SOBEL_FIX_TRUNCATE ;  Truncate the value to -1. The default Sobel behaviour (It truncates to -255 or 255. But, since we are using normalized version we set the limits to -1 and 1)
            fld R$Float_MinusOne | fstp F@FractionX
        Else ; SOBEL_FIX_SIMPLE. FixedValue = OldValue/(255*(floor(|OldValue|/255)+1))
            xor edx edx | mov ecx 255 | mov eax D@DataCheck | neg eax | div ecx | inc eax | imul eax 255 | mov D@Divisor eax
            fild D@DataCheck | fidiv F@Divisor |  fstp F@FractionX
        End_If

    .Else_If D@DataCheck >s 255 ; Whites. Edge too brigth.

        If D@FixType = SOBEL_FIX_TRUNCATE ;  Truncate the value to -1. The default Sobel behaviour (It truncates to -255 or 255. But, since we are using normalized version we set the limits to -1 and 1)
            fld1 | fstp F@FractionX
        Else ;  SOBEL_FIX_SIMPLE. FixedValue = OldValue/(255*(floor(OldValue/255)+1))
            xor edx edx | mov ecx 255 | mov eax D@DataCheck | div ecx | inc eax | imul eax 255 | mov D@Divisor eax
            fild D@DataCheck | fidiv F@Divisor |  fstp F@FractionX
        End_If

    .Else
        fild D@DataCheck | fmul R$Float_One_255 | fstp F@FractionX
    .End_If
    mov eax D@pOutSobelX | mov ecx D@FractionX | mov D$eax ecx

    ; To calculate Gy^2 later. Therefore Gy = M7+M9 + 2*(M8-M2) - (M3+M1)
    fld F$edi+FloatMatricesInt.M8Dis | fsub F$edi+FloatMatricesInt.M2Dis | fmul R$Float_Two
    fadd F$edi+FloatMatricesInt.M7Dis | fadd F$edi+FloatMatricesInt.M9Dis
    fsub F$edi+FloatMatricesInt.M3Dis | fsub F$edi+FloatMatricesInt.M1Dis
    lea ecx D@DataCheck | fistp F$ecx
    .If D@DataCheck = 0
        fldz | fstp F@FractionY
    .Else_If D@DataCheck <s 0-255 ; Blacks. Edge too dark. FixedValue = OldValue/(255*(floor(|OldValue|/255)+1))
        If D@FixType = SOBEL_FIX_TRUNCATE ;  Truncate the value to -1. The default Sobel behaviour (It truncates to -255 or 255. But, since we are using normalized version we set the limits to -1 and 1)
            fld R$Float_MinusOne | fstp F@FractionY
        Else ; SOBEL_FIX_SIMPLE ;  FixedValue = OldValue/(255*(floor(|OldValue|/255)+1))
            xor edx edx | mov ecx 255 | mov eax D@DataCheck | neg eax | div ecx | inc eax | imul eax 255 | mov D@Divisor eax
            fild D@DataCheck | fidiv F@Divisor |  fstp F@FractionY
        End_If
    .Else_If D@DataCheck >s 255 ; Whites. Edge too brigth. FixedValue = OldValue/(255*(floor(OldValue/255)+1))
        If D@FixType = SOBEL_FIX_TRUNCATE ;  Truncate the value to -1. The default Sobel behaviour (It truncates to -255 or 255. But, since we are using normalized version we set the limits to -1 and 1)
            fld1 | fstp F@FractionY
        Else ; SOBEL_FIX_SIMPLE;  FixedValue = OldValue/(255*(floor(OldValue/255)+1))
            xor edx edx | mov ecx 255 | mov eax D@DataCheck | div ecx | inc eax | imul eax 255 | mov D@Divisor eax
            fild D@DataCheck | fidiv F@Divisor |  fstp F@FractionY
        End_If
    .Else
        fild D@DataCheck | fmul R$Float_One_255 | fstp F@FractionY
    .End_If
    mov eax D@pOutSobelY | mov ecx D@FractionY | mov D$eax ecx

    ; Output the Angle (in degrees) if needed
    If D@pDegree <> 0
        lea eax D@SobelYAxisDis | fld F@FractionY | fstp R$eax
        lea edx D@SobelXAxisDis | fld F@FractionX | fstp R$edx
        call atan2 eax, edx, &True
        mov eax D@pDegree | fstp F$eax
    End_If

    ; And finally create the Sobel G after Gx and Gy are already fixed

    ; Soble = sqrt((255*FractionX)^2+(255*FractionY)^2)) = G = sqrt(Gx^2+Gy^2)
    ; since FractionX and FractionY can have a maximum of 1 and -1, therefore sobleMax = (255/sqrt(2)) * sqrt(FractionX^2+FractionY^2)

    fld F@FractionX | fmul ST0 ST0 | fld F@FractionY | fmul ST0 ST0 | faddp ST1 ST0 | fsqrt | fmul R$Float_SobleVarG
    lea edx D@pReturn
    fistp F$edx
    mov eax D@pReturn
    If eax > 255
        mov eax 255
    End_If
    mov ecx D@pOutSobel | mov D$ecx eax

EndP


Atan function used:
Code: [Select]

[Float_AtanPiFactor: R$ (180/3.1415926535897932384626433832795)]
[Float360: R$ 360]

; Macros used to simulate If/Else/EndIf using Fpu
[Fpu_If | fld #3 | fld #1 | fcompp | fstsw ax | fwait | sahf | jn#2 R0>>]
[Fpu_Else_If | jmp R5>> | R0: | fld #3 | fld #1 | fcompp | fstsw ax | fwait | sahf | jn#2 R0>>]
[Fpu_Else | jmp R5>> | R0:]
[Fpu_End_If | R0: | R5:]


Proc atan2:
    Arguments @pY, @pX, @ConvDegree
    Structure @TempStorage 16, @HueDis 0
    Uses eax, ebx, ecx

    mov ebx D@pY
    mov ecx D@pX

    fld R$ebx
    fld R$ecx
    fpatan
    fstsw ax
    wait
    shr ax 1
    jnb L2>
        fclex | stc | xor eax eax | ExitP
L2:

    .If D@ConvDegree = &TRUE
        fmul R$Float_AtanPiFactor | fst R@HueDis
        Fpu_If R@HueDis < R$FloatZero
            fadd R$Float360
        Fpu_Else_If R@HueDis >= R$Float360
            fsub R$Float360
        Fpu_End_If
    .End_If

    clc
    mov eax &TRUE

EndP



Results:
1 - Using more then 100 different images to create the proper watermark.


2 - Using 50 images from where only 3 where actually completely different from each other to create the watermark




As you can see, the second image have more visible noise because almost all images in the directory was similar to each other. I took from 3 different scenes only, so, at the end we have only 3 different images completely different to compare. But, you can see that even with only 3 real different scenes it properly identified the watermark.

Now it´s time to check if i ported correctly JJ´s version of your algo that can handles float (real4) and negatve values. :azn:
« Last Edit: July 30, 2020, 08:19:26 AM by guga »
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 #118 on: July 30, 2020, 07:08:27 AM »
 :thumbsup:

Can't wait to see the results on my screen.
Writing the Edge detection Graphics tool takes more time than I thought.  :biggrin:
« Last Edit: July 30, 2020, 08:24:14 AM by Siekmanski »
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 #119 on: July 31, 2020, 06:57:54 AM »
Different results using Scharr operator

Applied Scharr without any theshold - Noises all over the place



Applied Scharr using a threshold of 254 (so, only pixels with 255 are used)




As you can see, Scharr Operator produces a LOT of noise when the medians are applied (on the same way as we did for Sobel). This is explained because Schar detect/enhances more edges then Sobel. On single images, i mean, for general use, Scharr may result on a more accurate image, but in what concerns identifying differences of several images, it fails miserably because the noises are extrapolated all over the resultant image. The only "good" stuff is that since all pixels marked with 255 are 100% sure that belongs to edges, Scharr could be used to create the shapes of the objects (as showed in the 2nd image) using a threshold to discard all pixels below or equal to 254.

The problem is that it still will have noise, and still won´t be able to identify details in the images that are not edge, in fact. Like the internal parts of the watermark, holes etc. The result of the Medians of Scharr are, basically a rough shape of the watermark or common areas of several images. It did quite a good job creating the shape of the watermark, except the fact that it produced noise all over the true edges.

This cannot be fixed on the normal way. So Scharr operator is out of the scope to this algo we are creating (at least, for now) :greensml: :greensml:

I´ll make a couple of more tests on the math involving the matrix to try identify the relation between the neighbor pixels of the matrix and the values we use in the different operator.s It seems to me that the matrix pos at "M1" can be completelly discarded of the computation, but i´m not sure yet.

I´ll make a couple of more tests today.
« Last Edit: July 31, 2020, 09:51:18 AM by guga »
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