using a sobel operator - edge detection

[HugoRune]

right about the bias and the solarize -negate. But my other point was that your abs and sqrt of square are redundant. That was why I suggested you either do the abs or the compose mutliply -evaluate pow 0.5. You don't need both.

They are redundant in principle, but I need the abs to work around non-HDRI clipping of negative values.
I have to remove the bias bevore I square each pixel, otherwise the results will be totally off.
And when I remove the bias, negative values are clipped, so I use the abs() first to prevent that.

[fmw42]

but I was pointing out if you are using abs, then no point for -compose multiply on both then -compose plus -evaluate pow 0.5

[HugoRune]

but I was pointing out if you are using abs, then no point for -compose multiply on both then -compose plus -evaluate pow 0.5

Sorry, I don't follow. Do you mean that I can leave out a step and still get the same result?
As far as I understand there are two standard ways to calculate a sobel:
The exact way: sqrt (sobelX^2 + sobelY^2)
The approximation: abs(sobelX) + abs(sobelY)

Now, if I want to use the exact way on non-HDRI imagemagick, I have to do
sqrt (abs(sobelX)^2 + abs(sobelY)^2), which is equivalent to sqrt (sobelX^2 + sobelY^2), but prevents clipping

Granted, the approximation is good enough that in most cases I can get almost the same result by simply adding abs(sobelX) + abs(sobelY).

But if the goal is to calculate the exact sobel on non-HDRI, I see no way to go without abs and compose-multiply

[fmw42]

This should be sufficent and should be equivalent to abs(X) + abs(Y)

convert zelda3.JPG -evaluate multiply 0.125 ^
( -clone 0 -bias 50% -convolve "-1,0,1,-2,0,2,-1,0,1" -solarize 50% -negate -level 50%,100% ) ^
( -clone 0 -bias 50% -convolve "1,2,1,0,0,0,-1,-2,-1" -solarize 50% -negate -level 50%,100% ) ^
-delete 0 -compose plus -composite zelda_4_4.png


No point in doing this which is like sqrt (abs(X)^2 + abs(Y)^2) as the point of the sqrt ( of the square) was to make sure that negatives were treated like positive, ie.. like doing an abs. But you have no negatives at this point as you already have the equivalent of the abs(X) and abs(Y):

convert zelda3.JPG -evaluate multiply 0.125 ^
( -clone 0 -bias 50% -convolve "-1,0,1,-2,0,2,-1,0,1" -solarize 50% -negate -level 50%,100% ) ^
( -clone 0 -bias 50% -convolve "1,2,1,0,0,0,-1,-2,-1" -solarize 50% -negate -level 50%,100% ) ^
-delete 0 ^
( -clone 0 -clone 0 -compose multiply -composite ) ^
( -clone 1 -clone 1 -compose multiply -composite ) ^
-delete 0,1 -compose plus -composite -gamma 2 ^
zelda_4_4.png

Unless I miss something as I am still no HDRI and cannot switch and test under normal Q16

[HugoRune]

This should be sufficent and should be equivalent to abs(X) + abs(Y)

I think we are misunderstanding each other. I know that I can do the equivalent of abs(X) + abs(Y) to get a good approximation of the sobel operator.
Indeed, that is probably what I will use in most cases, since it is faster than the exact version.

My point was just that if one wants to calculate the exact sobel operator without HDRI for some reason, one has to do it the complicated way,
since sqrt(x^2 + y^2) is not equal to abs(x) + abs(y).

for example
sqrt( (1/2)^2 + (1/2)^2 ) = 0.707106
abs(1/2) + abs(1/2) = 1

[fmw42]

correct, but you don't buy much by adding the sqrt processing if you already have done the abs.

[fmw42]

Doing some tests, it appears that the convolution is not normalized by the sum of the absolute values of the kernel values. ( I did some filtering with different pre-multiplication factors and needed to divide by 8 with this filter to get a result that was not full dynamic range, i.e. did not reach full white for the positive edges. I did not check code).

When the filter kernels sum to something positive then, the result is normalized by the sum of the kernels. But when they sum to zero, the result is not normalize. But it probably should be normalized by the sum of the absolute value of the kernels.


So in this case, 1,2,1,0,0,0,-1,-2,-1, the normalization should be to divide by 8. Thus the need to premultiply by 1/8=0.125, i.e. -evaluate multiply 0.125

[fmw42]

OK. Still in HDRI, but you do get some significant difference between using sqrt and just adding the abs

sqrt:

convert zelda3.JPG -evaluate multiply 0.5 \
\( -clone 0 -bias 50% -convolve "-1,0,1,-2,0,2,-1,0,1" -solarize 50% -level 0,50% -negate \) \
\( -clone 0 -bias 50% -convolve "1,2,1,0,0,0,-1,-2,-1" -solarize 50% -level 0,50% -negate \) \
\( -clone 1 -clone 1 -compose multiply -composite \) \
\( -clone 2 -clone 2 -compose multiply -composite \) \
-delete 0-2 -compose plus -composite -gamma 2 \
zelda3_grad7.png


abs:

convert zelda3.JPG -evaluate multiply 0.5 \
\( -clone 0 -bias 50% -convolve "-1,0,1,-2,0,2,-1,0,1" -solarize 50% -level 0,50% -negate \) \
\( -clone 0 -bias 50% -convolve "1,2,1,0,0,0,-1,-2,-1" -solarize 50% -level 0,50% -negate \) \
-delete 0 -evaluate multiply 0.5 -compose plus -composite \
zelda3_grad8.png


but the value in the last multiply could be changed to .707 to simulate sqrt(2)

I used an initial multiply by 0.5 to emphasize things to see better, but you can put that back to your value of 0.25 or 0.125 if you want.

[HugoRune]

doing some tests, it appears that the convolution is normalized by the sum of the absolute values of the kernel values. So in this case, 1,2,1,0,0,0,-1,-2,-1, even though they add to zero, the normalization will be to divide by 8.

I cannot reproduce that.
On my version, it looks like no normalization is taking place.

If there was normalization, the following pictures should be identical

convert -size 50x50 xc:black -fill white -draw "circle 25,25 20,10" -convolve "0,0,0,-1,1,0,0,0,0" test1.png

convert -size 50x50 xc:black -fill white -draw "circle 25,25 20,10" -convolve "0,0,0,-0.1,0.1,0,0,0,0" test2.png

convert -size 50x50 xc:black -fill white -draw "circle 25,25 20,10" -convolve "0,0,0,-10,10,0,0,0,0" test3.png

[anthony]

Okay this has been an interesting discussion, (which I have not been able to join in due to the weekend and family commitments). It is the first such serious and deep discussion on the convolve operator on the forums, and as such is a major test of its abilities in ImageMagick.

First -negate is a special type of -level operator, Just swap the arguments to produce a negative result!

Now HDRI does require compilation, and is used for highly mathematical situations. Basically it avoids the effects of 'clipping' negative values or very large values, as well as 'rounding' effects of storing very small numbers in integers. Both of which can be demonstrated using -level on non-HDRI imagemagick.

All the above work has mostly been to avoid such effects from being produced by -convolve .


So lets look at convolve. First it finds the 'average' value of any kernel supplied, and scales that kernel by that average. Then it adds any defined 'bias' to the result of each convolution. That is it will only normalize 'positive' kernels correctly!

The sobel kernel is

Code: Select all

-1 0 1
-2 0 2
-1 0 1

which when added up produces a average of zero, so no scaling is applied to the kernel. this is why dividing by 1/4 or doing something else works for this kernel, but not for other kernels. The largest positive result will be 4*white
We need that to be white.

However so as to avoid negatives you need a 50% bias, so really you want bias + maximum posible to be white. That is maximum posible must equal 50%!

Add bias and scale kernel (which as average = 0 does not automatically get scaled!) so 1+2+1 * scale => 0.5 OR divide by 8 (not 4!)

Code: Select all

   -bias 50% -convolve '-0.125,0.0,0.125,   -0.25,0.0,0.25,  -0.125,0.0,0.125'

After this -solarize 50% will perform the equivelent of a abs() around the bias value
and a level with negation will re-stretch the image. That is we want '50%' (the bias) to be black, and 0% (maximum distance from bias) to be white...

Code: Select all

  -solarize 50%    -level 50%,0%

An alternative to this is of course to do a difference image against gray, and multiply by 2.

Code: Select all

  \( +clone -fill gray50 -colorize 100% \) -compose difference -composite -evaluate multiply 2

OR use FX operator (slow)


So for non-HDRI you get the best most accurate result using the following...

Code: Select all

   convert image.png \
         -bias 50% -convolve '-0.125,0.0,0.125,   -0.25,0.0,0.25,  -0.125,0.0,0.125' \
         -solarise 50%    -level 50%,0%    result.png

Of course anything that works for non-HDRI will work with HDRI as well, HDRI will just be a little more accurate due removing 'rounding' effects.



NOTE Their is proposals for the re-development of convolve as part of morphology
operators. the current 'auto scaling' of convolve currently gets in the way of morphology.


Question: convolve currently automatically scales!
But should convolve automatically scale and bias 'zero' kernels, such a sobel. That is should it adjust the kernel and bias so that minimum posible => black
and maximum posible => white?

Or should we remove all scale handling, and give this control back to the user?
as a scaling parameters (with posible automatic switches).

QUESTION; convolve does not understand the special nature of 'alpha' as a transparency mask. Should it be a posibility? Perhaps a 'channel' control flag?

[fmw42]

So lets look at convolve. First it finds the 'average' value of any kernel supplied, and scales that kernel by that average. Then it adds any defined 'bias' to the result of each convolution. That is it will only normalize 'positive' kernels correctly!

The filter is not an average or low pass, but an edge detector or high pass filter.

The largest positive result will be 4*white
We need that to be white.

Actually according to some test I just did it appears that IM will normalize by the sum of the values of the filter except when they add to zero. But it probably needs to be divided by 8 to achieve a nominal normalization, that is by the sum of the absolute values of the kernel.

Question: convolve currently automatically scales!
But should convolve automatically scale and bias 'zero' kernels, such a sobel. That is should it adjust the kernel and bias so that minimum posible => black
and maximum posible => white?

No, not automatically. And esp. as bias is unneeded in HDRI.


P.S. You get the same result by using -solarize 50% -level 0,50% -negate in place of -solarize 50% -negate -level 50,100%

[anthony]

So lets look at convolve. First it finds the 'average' value of any kernel supplied, and scales that kernel by that average. Then it adds any defined 'bias' to the result of each convolution. That is it will only normalize 'positive' kernels correctly!

The filter is not an average or low pass, but an edge detector or high pass filter.

The point is that its average is zero, which means convolve does NO normalizations at all!

However in the convolve/morphology developement it could easilly scale and bias these filters! I was also thinking it would be nice to be able to turn off normal
scaling anyway.

Actually according to some test I just did it appears that IM will normalize by the sum of the values of the filter except when they add to zero. But it probably needs to be divided by 8 to achieve a nominal normalization, that is by the sum of the absolute values of the kernel.

You did not read it completely!!!! It is 4 times. But to fit into the space provided by the bias which is 50% so that becomes 8 times!!!!!

Question: convolve currently automatically scales!
But should convolve automatically scale and bias 'zero' kernels, such a sobel. That is should it adjust the kernel and bias so that minimum posible => black
and maximum posible => white?

No, not automatically. And esp. as bias is unneeded in HDRI.

But then HDRI also does not need automatic scaling either

I have updated my morphology proposal notes (for when I get around to it) to
auto-scale and for kernels with negatives auto-bias results (typically resulting in a 50% bias). BUT allow the use of a '!' flag to mean no bias.

See my test site ...../im/STORE/morphology/CLI_proposal.txt
Sorry to others, this is a restricted URI, and not publically available.

[HugoRune]

(i just looked up the normalization, here it is just in case anyone else is interested in the code)

/*
Normalize kernel.
*/
...
gamma=0.0;
for (i=0; i < (long) (width*width); i++)
gamma+=kernel;
gamma=1.0/(fabs((double) gamma) <= MagickEpsilon ? 1.0 : gamma);
for (i=0; i < (long) (width*width); i++)
normal_kernel=gamma*kernel;

Question: convolve currently automatically scales!
But should convolve automatically scale and bias 'zero' kernels, such a sobel. That is should it adjust the kernel and bias so that minimum posible => black
and maximum posible => white?

Well automatically scaling/biasing can be confusing if it is unexpected.
If it is documented it can be very useful, even on HDRI, since the output image will with most formats still be clipped.

how about -convolve "autoscale:0,1,..."

for non-hdri (and maybe for hdri too) an option to do -convolve & abs() in one step would be useful too.
something like -convolve "abs:0,1,.."

First -negate is a special type of -level operator, Just swap the arguments to produce a negative result!

That is good to know, thanks!

[fmw42]

/*
Normalize kernel.
*/
...
gamma=0.0;
for (i=0; i < (long) (width*width); i++)
gamma+=kernel;
gamma=1.0/(fabs((double) gamma) <= MagickEpsilon ? 1.0 : gamma);
for (i=0; i < (long) (width*width); i++)
normal_kernel=gamma*kernel;

I don't read code very well. But on the surface this would appear to be normalizing by the sum of abs values of the kernel. But I don't see that in the convolve results. So I am confused. My tests seem to indicate otherwise. So I will have to re-do my tests to verify and demonstrate if confirmed when I can get to it.

Your results don't seem to indicate this either as you seem to need to divide by 8 (multiply by 0.125) to get results that seem reasonable (and come close to GIMP).

[anthony]

I don't read code very well. But on the surface this would appear to be normalizing by the sum of abs values of the kernel. But I don't see that in the convolve results. So I am confused. My tests seem to indicate otherwise. So I will have to re-do my tests to verify and demonstrate if confirmed when I can get to it.

It simply adds all values first then scales all values by its absolute, or 1.0 (do nothing) if the average was zero.

That is it really designed for kernels only containing positive values. Negative values or zero averaged kernels really stuff things up. I have always felt that in many ways this was wrong! Useful yes, but still wrong!

The proposal is...

Expand -convolve to call a library function to parse the provided kernel string, so as to allow a more varied kernel defination.

For example: expand the 'floating point list from...
'1,1,1,1,1,....'
to also allow for kernel definitions of the form....
'{geometry}:1,1,1,1,1,1....'
where {geometry} is of the form defining the width, and optionally the height, and center offset of the center point within the kernel, which will then nolonger need to be a odd size!

Internally the floating point array will be expanded to include 4 extra numbers
prepended on the front defining these values for passing the defined kernel on
into the 'convolve' function (no other call change is needed, though may break
other API's)

This string can also be further expanded to allow special 'morphological
kernels (starting with a string) such as...

'gaussian, {radius}x{sigma}' the normal gaussian bell curve kernel

and the typical morphological (boolean) kernels such as....

'square, {radius}' -- a square of size radius*2+1, defaulting to 3x3
'diamond, {radius}' -- a diamond kernel defaulting to a 3x3 diamond
'disk, {radius}' -- a morphological circle using floating point radius
'rectangle, {geometry}' -- a rectangle (or square) with more user control

For example:
-convolve 'disk,5' will convolve using a disk shaped area.

This will then mean that -gaussian is equivalent to a
-convolve 'gaussian,{args}'
which is essentually what IM is currently doing now.


convolve argument can thus be one of three types...
a ':' is present -- geometry present, followed by kernel values
negative or a number -- old style list of values (odd square array)
alphabetic -- pre-defined kernel type

I would leave autoscaling, but expand it to auto-bias as well if negatives are present (few people use or need HDRI). But also allow the {geometry} to have a '!' to turn off auto-scale/bias


Note the proposal goes on to 'morphology' operators which convolve could be regarded as simply an 'weighted sum' or 'weighted average' type of operation.