Fast median algorithm

[nidud]

deleted

[Siekmanski]

Hi guga,

-> I found it where VisualStudio generated negative values. It was the way the python version was created. It does not calculate the media of G directly, it calculate the median of Gx and later the median of Gy and only after it, it compute the value of G = sqrt (MedianGx^2 + MedianGy^2)

This comment from you is the reason I wrote a 6 numbers sorting routine.

The Median Matrix holds only positive numbers ( pixel values are never negative )
Therefore the calculation for the average middle numbers is correct.

And don't forget you only have to sort 6 values per matrix!!!

Code Select Expand

To calculate the edges on the X axis

     [ X X X ]
Gx = [ 0 0 0 ]
     [ X X X ]

To calculate the edges on the Y axis
     
     [ X 0 X ]
Gy = [ X 0 X ]
     [ X 0 X ]


You only need these 6 numbers. ( X's in the matrices )
For the Sobel Matrix convolution as for the Median Matrix calculations.

( You can save the Gray Color pixel conversion calculations as floating point )
( So you need no conversions from integer and floating point between all the calculation )

For the Median Matrix calculation you only read the 6 [X] pixel values ( always positive ) sort them, get the Median and that's the Gx and Gy.
No convolution needed as with the Sobel coefficients.

The G values should always be positive. ( they represent the new pixel color )

[guga]

Hi guga,

-> I found it where VisualStudio generated negative values. It was the way the python version was created. It does not calculate the media of G directly, it calculate the median of Gx and later the median of Gy and only after it, it compute the value of G = sqrt (MedianGx^2 + MedianGy^2)

This comment from you is the reason I wrote a 6 numbers sorting routine.

The Median Matrix holds only positive numbers ( pixel values are never negative )
Therefore the calculation for the average middle numbers is correct.

And don't forget you only have to sort 6 values per matrix!!!

Code Select Expand

To calculate the edges on the X axes

     [ X X X ]
Gx = [ 0 0 0 ]
     [ X X X ]

To calculate the edges on the Y axes
     
     [ X 0 X ]
Gy = [ X 0 X ]
     [ X 0 X ]


You only need these 6 numbers. ( X's in the matrices )
For the Sobel Matrix convolution as for the Median Matrix calculations.

( You can save the Gray Color pixel conversion calculations as floating point )
( So you need no conversions from integer and floating point between all the calculation )

For the Median Matrix calculation you only read the 6 [X] pixel values ( always positive ) sort them, get the Median and that's the Gx and Gy.
No convolution needed as with the Sobel coefficients.

The G values should always be positive. ( they represent the new pixel color )

Hi Marinus, ok. But i´m getting a bit confused because this is not what the python version seems to be doing. For what i understood, the sequence of functions are those 2 parts.

1 - Call the function estimate_watermark

This function will export 2 buffers containing the median of Sobelx and SobelY calculated from N images . It will export them in Wm_x and Wm_y like this:

a) Create the sobel x and y on all N images

Code Select Expand

    gradx = list(map(lambda x: cv2.Sobel(
        x, cv2.CV_64F, 1, 0, ksize=KERNEL_SIZE), images))
    grady = list(map(lambda x: cv2.Sobel(
        x, cv2.CV_64F, 0, 1, ksize=KERNEL_SIZE), images))

So, here we have 100 (or N) Memory Buffers where it is stored the SobelX and Sobel Y on each image individually. So:

GradX from image 1 will contain the sobelx from image1. So, we can called it GradX(1)
GradY from image 1 will contain the sobely from image1. So, we can called it GradY(1)

GradX from image 2 will contain the sobelx from image2. So, we can called it GradX(2)
GradY from image 2 will contain the sobely from image2. So, we can called it GradY(2)

GradX from image N will contain the sobelx from image1. So, we can called it GradX(N)
GradY from image N will contain the sobely from image1. So, we can called it GradY(N)

At the end we have N*2 Memory Buffers containing the sobel (Gx and Gy) from all the N images.

b) After it calculate the sobelx and y on all images it then take their median to export on only 2 new buffers (Wm_x and Wm_y), as below:

Code Select Expand

    # Compute median of grads
    print("Computing median gradients.")
    Wm_x = np.median(np.array(gradx), axis=0)
    Wm_y = np.median(np.array(grady), axis=0)

So, this function it is not creating the G on each image, but calculating the median of Gx and Gy from all images to later compute the resultant G from those values as below.

the median calculated from here is at each given position on all N images from where Gradx and GradY were created.

So:
At pos (x = 0, Y = 0), it will get the SobelX and SobelY from images 1 to N and calculate their median and then put the resultant 2 (Gx and Gy) values on Wm_x and Wm_y at the same pos (x = 0, y =  0)
At pos (x = 1, Y = 0), it will get the SobelX and SobelY from images 1 to N and calculate their median and then put the resultant 2 (Gx and Gy) values on Wm_x and Wm_y at the same pos (x = 1, y =  0)

and keep doing it untill all Coordinates were calculated.



2 - Call the function crop_watermark

This function will calculate the median G value from the previously created Wm_x and Wm_y

Code Select Expand

    W_mod = np.sqrt(np.square(gradx) + np.square(grady))

From this part it is taking the 2 memory buffers created to store the median Gx and Gy to calculate the G from only those 2 memory buffers that will be saved in W_mod


So, what is the strategy ? Use your new FastMedianFP to compute median on what ? I really got a bit lost right now.

[Siekmanski]

 

Let's experiment with real image data and see what kind of junk we can create. 
See if the median matrix method is better or worse than the sobel convolution method.

[guga]

 

Ok, i´ll give a try, but what i do next ? Use your new median algo to compute the median from what and where ?


I´ve got lost

[guga]

Ok, i´ll try to do this and see what result i got. Maybe inverting the order that was made in python version should also works.

1 - Create the median of greys on all N images and save this on one single memory buffer
2 - Create the Sobel from this new image.

[Siekmanski]

Just step for step I think, before we lose track.
This weekend I have some more time.
If you like it ( otherwise you might think I will hijack your project, of course I don't want that ), I can code the image loader, save some bytes in memory etc.
Show the original image on screen and next to it show the different edge detection images routines.
Later we can figure out ( if we succeed... ) how to do the watermark stuff.
Haven't looked into that part yet.

[daydreamer]

Just step for step I think, before we lose track.
This weekend I have some more time.
If you like it ( otherwise you might think I will hijack your project, of course I don't want that ), I can code the image loader, save some bytes in memory etc.
Show the original image on screen and next to it show the different edge detection images routines.
Later we can figure out ( if we succeed... ) how to do the watermark stuff.
Haven't looked into that part yet.

That image processing is that similar to search and replace black pixels surrounding lighter pixels with grey ?
postprocessed antialias, compared to line/oval /text outputted with antialias for example gdi+

[Siekmanski]

Hi Magnus,

Could be something like that, for now it feels like magic.

[guga]

Just step for step I think, before we lose track.
This weekend I have some more time.
If you like it ( otherwise you might think I will hijack your project, of course I don't want that ), I can code the image loader, save some bytes in memory etc.
Show the original image on screen and next to it show the different edge detection images routines.
Later we can figure out ( if we succeed... ) how to do the watermark stuff.
Haven't looked into that part yet.

Sure :thumbsup:That would be very nice Thank you a lot

The part that estimate the watermark don´t seems to be so hard. It´s just a matter of try to find what the exactly the estimate_watermark function is doing in the python version so we can optimize it further. Sobel is a good way to get the edges, but if we succeed to make it work as expected, we can later extend the estimation of the watermark to use other matrices as well, like Scharr operators.

I made one single function to work specifically for sobel called 'SobelGetGPLusEx" (as posted previously), that is able to fix the sobel errors forcing the data to stay within the 0-255 limits (already normalized to 0...1) without cutting, but we can also use as input a matrix on whatever operator we want (and, perhaps on whatever size) and make the same fixes using only one single function.

Currently i was working on the next part that is the crop_watermark function, but i´ll go back now and made the test directly using the median of the gray values to calculate the sobel values and see what the resultant image looks like. Don´t know if changing the order exposed in the python version would improve, but...it´s  worth o give a try.

[Siekmanski]

Cool  , we are a team now. 

The goal is to get the location of the watermark with the most suitable edge detection technique.
In a movie the watermark is static and always the same color while the background changes between dark to light.
So when taking the median of multiple frames, the watermark will show up as a brighter color as the surrounding background, I think?

[guga]

That image processing is that similar to search and replace black pixels surrounding lighter pixels with grey ?
postprocessed antialias, compared to line/oval /text outputted with antialias for example gdi+

Hi Magnus. For what i understood of the articles and the python code, the very 1st step is a simple edge recognition of all images you feed in. You take the median of the edges on all images in order to create a new one. The newly created image will result on the edges that are present in all images altogether. To identify the edges, the algorithm uses Sobel operator (Which is great for this task, btw),  but, of course, it can be extended to use others that are better like Scharr for example. Of course, no matter what operator we use we will always need to fix them since all of them simply cut off values (frequencies) that are outside the normal range of 0-255, which, btw, is not desired and this is the main reason why you see in sobel images those extremely thick lines on the edges or noise that is generated etc. (I´m quite sure that on Scharr the same fix must be done too). So, the fix and adaptation i made on sobel is a must in whatever operator is used.

What the algorithm does to estimate the edges (watermark) is basically this: For example, if you have a sequence of images that contains a watermark, or a lens defect of the camera, a crack on the lens or whatever other imperfection that are present on all images, the 1st thing to do is identify and enhance only those imperfections (or watermarks, in this case) and create a newly image containing only the enhanced edges found on all of them.

After the detection on all images, it will result on something like this:



This is the easier part (well.. kind of )

The next step is crop this new image which envolves using a threshold toexclude the pixels that are darker then a specific limit (The python version seems to use a limit of 0.4), then he crop the resultant image and generate some sort of map containing only 1 or 0 (i presume).

This is the final part of the crop_watermark function used in python, but i didn´t understood what it is doing when reach this:
return gradx[xm:xM, ym:yM, :], grady[xm:xM, ym:yM, :]


After it, is time to identify the watermark on the image you want it to be removed.

On this part, the algo do the same thing again, but only in the image from where you want to remove the watermark. So it will detect the edges of one single image (this time using canny), then calculates the chanfer distance between the edges of the loaded image and the edges of the watermark you previously estimated, and crop the image somehow (don´t know how to do it yet). It then returns a rectangle corresponding to the area where the edges were detected (so, a rectangle around the detected watermark).
Perhaps this rectangle is just to visualize the watermark being detected, as it happens when you do a face recognition and those squares shows up all around your face.

The next step is make a rebuild of the watermarked area using poisson_reconstruct algorithm

This is what i understood what the algorithm is doing so far. It´s half the way to remov the watermark, but the rest of the code and other functions i don´t know exactly what are they doing yet

[guga]

Cool  , we are a team now. 

The goal is to get the location of the watermark with the most suitable edge detection technique.
In a movie the watermark is static and always the same color while the background changes between dark to light.
So when taking the median of multiple frames, the watermark will show up as a brighter color as the surrounding background, I think?

Great !

About the goal..Exactly That´s why on the image i posted previously the watermarks showed up. On movies (or whatever other sequence of images), if the watermark is fixed (or other imperfection, like lens crack, fixed dirt, etc) this will always shows in all images. The 1st (and easier) task is detect.

The next step is as i explained above to magnus. It involves doing a similar thing to the image we want the watermark to be removed. The rest of the techniques we will need to do step by step because i´m not fully understood what the python functions are doing. I choosed to use the python version as a guidance, because the original google article contain too much math symbols i´m not fully understand.

[guga]

Hi Marinus

Some results of the new test.

This time i used the median of the grays to compute the resultant sobel and the result is that the image is too noisy




On the other method (image below), the watermark were detected without that amount of noises.

So, the better is create the Gy and Gx for all images (separately). So, if we are feeding the algo with 100 images we will need to generate a map for 100 images containing only Gx and 100 images containing only Gy.

And then, take the median of Gy and GY and only after it calculate the Sobel (G) from those median of gy and gx

With the olderr (and better) method, the image is clearer as below




So, an algo to calculate the median of floats (negative and positive) is, indeed, necessary

[Siekmanski]

Maybe setting a threshold will improve things?

-> So, an algo to calculate the median of floats (negative and positive) is, indeed, necessary

Why? you could do it with byte integers.