Minima and maxima for dimensionality reduction

[boris-kz]

I was thinking of using minima and maxima for blob dimensionality reduction (right now we are using blob median for that).
It's a common practice and obviously useful in many cases, but I haven't seen any conceptual justification.
Now it seems me that's because extrema are generally more stable than other points, and stability is our core criterion.
I understand why this so in topographical maps: stability is inverse to erosion, which is proportional to slope.
Extrema have 0 slope, thus the slowest erosion.
But I don't know how to generalize this beyond topography?

This is regarding "unsupervised" value, leaving aside utilitarian value: these extrema are usually transportation obstacles, etc.

[kwcckw]

I was thinking of using minima and maxima for blob dimensionality reduction

The dimension here is referring to the actual pixel size or parameter size?

Now it seems me that's because extrema are generally more stable than other points, and stability is our core criterion.
I understand why this so in topographical maps: stability is inverse to erosion, which is proportional to slope.
Extrema have 0 slope, thus the slowest erosion.
But I don't know how to generalize this beyond topography?

For the generalization, are you look into converting this idea into some function so that we can use it for the dimension reduction purpose?

[kwcckw]

* I don't want to use Gaussians because it's a form of resolution reduction. I think resolution (a type of my filters) should only be reduced after evaluation per pattern, which means after a full cross-comp and clustering cycle. So, scale-space here is compositional hierarchy of patterns, not a spectrum of Gaussian kernels.

* Key points in SIFT are just another name for extrema? They may be more stable than blob averages / medians because their gradient (of the parameter over which the extrema is defined, which may also be gradient) is close to 0. That gradient is a measure of change, which is a complementary of stability.

Right, but they are computed via difference of gaussian (DoG), so it's the difference of 2 gaussian processed image, with different gaussian kernel value. I guess this is not suitable in our use case since the difference is obtained via the reduced image, so some information might be lost.

* Still need to think how this is related to strictly local gradient, which defines our blobs. The points with very low 2nd gradient (Laplacian) are similar to extrema, but not exclusive. That was incremental-derivation fork in old 3-fork version of intra_blob: https://github.com/boris-kz/CogAlg/blob/master/frame_2D_alg/Illustrations/intra_blob_3_fork_scheme.png
  Or incremental-range fork, it is selective for very low gradient.

* Orientation assignment in SIFT is by angle of gradient, same as ours?

It is computed via gradient direction but the final value is approximated into 36 bins of histogram, so may not be the same in our case.
Ref: https://medium.com/data-breach/introduction-to-sift-scale-invariant-feature-transform-65d7f3a72d40

Could you look at corner detectors, it sounds like our comp_angle? Corner would be a local minimum of ma (match of angle), although we currently compute deviation, not extrema.

From my initial checking on the pseudo code, looks like it's similar but different at the point when they are using extrema while we are using the sum of difference . First they use sobel filter to get x and y gradient, then they find the local maxima as corner by using 3x3 window filter. So this would be different with the sum of deviation in our case.
Ref: https://medium.com/data-breach/introduction-to-harris-corner-detector-32a88850b3f6

[boris-kz]

So, low deviation of gradient (-G) is not sufficient as a measure of extrema, it may also indicate flat areas.
But we also compute SAD as an inverse measure of match.

High deviation of SAD (-M) corresponds to either steep slope or steep extrema, and the later is when it is combined with low G. Thus, specific measure of extrema = -G * -M: directionally-compensated variation?

This is not necessarily exclusive max | min by design, but I think it will be effectively pretty exclusive anyway?
Still not sure how to relate this measure of extrema to separate G and M we are using now.
(I wrote it before seeing Chee's post).

[boris-kz]

From my initial checking on the pseudo code, looks like it's similar but different at the point when they are using extrema while we are using the sum of difference . First they use sobel filter to get x and y gradient, then they find the local maxima as corner by using 3x3 window filter. So this would be different with the sum of deviation in our case.
Ref: https://medium.com/data-breach/introduction-to-harris-corner-detector-32a88850b3f6

Thanks Chee! So, I think my description above is a better way to quantify extrema, and they don't have to be singular.

[kwcckw]

From my initial checking on the pseudo code, looks like it's similar but different at the point when they are using extrema while we are using the sum of difference . First they use sobel filter to get x and y gradient, then they find the local maxima as corner by using 3x3 window filter. So this would be different with the sum of deviation in our case.
Ref: https://medium.com/data-breach/introduction-to-harris-corner-detector-32a88850b3f6

Thanks Chee! So, I think my description above is a better way to quantify extrema, and they don't have to be singular.

Right, but i think those extrema also can start with some singular point? Then by grouping them with some methodology, they could be sorted into certain form of extrema?

[kwcckw]

So, low deviation of gradient (-G) is not sufficient as a measure of extrema, it may also indicate flat areas.
But we also compute SAD as an inverse measure of match.

High deviation of SAD (-M) corresponds to either steep slope or steep extrema, and the later is when it is combined with low G. Thus, specific measure of extrema = -G * -M: directionally-compensated variation?

This is not necessarily exclusive max | min by design, but I think it will be effectively pretty exclusive anyway?
Still not sure how to relate this measure of extrema to separate G and M we are using now.
(I wrote it before seeing Chee's post).

At this point i'm also don't have a better suggestion yet, and i cannot sure whether -G * -M is suitable or not. However, let say we want to test it out, how do you intend to compare and evaluate which method is more suitable? By output some visualization with image data? Or just test with some simple data array?

[boris-kz]

Singular extrema make things a lot simpler, but I think this simplification is artificial. Replacing them with blobs of above-average values is a lot more accurate, I can think of no good reason for non-maximum suppression? Those values should represent approximate peaks: areas of directionally-symmetrical (low G) high local variation (SAD).

So, it should be (ave_G - G) * SAD - ave_product_of_the_two?
These areas maybe more stable than simply low-SAD (high M) areas because it's a kind of internal contrast:
G is low despite SAD being high. Still haven't quite conceptualized it yet.

Yes, it's best to visualize these blobs with real images.

[boris-kz]

It doesn't hold in every case, but I think average SAD = 1.41 average G.
How would you define this ratio? It's basic math, we shouldn't have to experiment.

[kwcckw]

It doesn't hold in every case, but I think average SAD = 1.41 average G.
How would you define this ratio?

So for G, it is computed from 2 directional elements and it is computed via square root of square sum.

for SAD, we are computing it from the sum of 8 directional differences.

So maybe 1.41 /4? Since SAD is using 8 directions while G is using 2 directions?

It's basic math, we shouldn't have to experiment.

Maybe just experiment with different kernel size and see the trend of the output images?

[boris-kz]

Oh, ok I was thinking of 2x2 kernel, where there are only 2 directions.
So, in 3x3 it's 1.41 / 4, for the case where Gy and Gx are equal.
But to the extent that they are not equal, I think the ratio is lower than 1.41?
BTW, I think it should look better with 5x5 kernels.

[kwcckw]

Oh, ok I was thinking of 2x2 kernel, where there are only 2 directions.
So, in 3x3 it's 1.41 / 4, for the case where Gy and Gx are equal.
But to the extent that they are not equal, I think the ratio is lower than 1.41?
BTW, I think it should look better with 5x5 kernels.

right, the ratio should be lower than 1.41. Also there are some mistakes in the previous code, when rng = 2, there should be 16 directional images and the directional images should be increases when the rng increases. I will post here when i have the updated results.

[kwcckw]

from my testing, i can see the edges in e_ become more more distinct when the rng increases, but the trade-off is losing information since we lost more information when the rng increases.

rng=1

rng=2

rng=3

rng=4

rng=5

rng=6

rng=7

rng=8

rng=9

rng=10

[boris-kz]

Thanks Chee! I think resolution is lost by design, your shift_img does the same skipping we built in comp_r?
That made sense when comp_r was designed for flat blobs, but now it's performed to analyze high-variation (high-m) areas.
So, we need comp_rng without skipping: it should compute kernels for each pixel, without output interpolation?

[kwcckw]

Thanks Chee! I think resolution is lost by design, your shift_img does the same skipping we built in comp_r?

Yes, it shifts and skip based on the rng number, it should be similar with our current work.

If rng = 1 (3x3), distance between kernel = 2, number of shifted images = 8
If rng = 2 (5x5), distance between kernel = 3, number of shifted images = 16
If rng = 3 (7x7), distance between kernel = 4, number of shifted images = 24
and so on.

That made sense when comp_r was designed for flat blobs, but now it's performed to analyze high-variation (high-m) areas.
So, we need comp_rng without skipping: it should compute kernels for each pixel, without output interpolation?

With this, the resolution should be better, i will try that later. Also for the current code, i'm using diametrically opposed images to compute the difference instead of using differences between center image and each directional image, do you think differences between center image and each directional image will be better?

[boris-kz]

m should definitely be computed for each direction separately, g is probably fine with diametrically opposed comparison.

[kwcckw]

okay, right now dy__, dx__ and g are computed via diametrically opposed comparison, while m is computed via each directional differences. So i guess no changes are needed on those computation.

[kwcckw]

without the skipping, the output when rng increases would looks like those sobel kernel with larger kernel size:

rng = 1

rng = 2

rng = 3

rng = 4

rng = 5

rng = 6

rng = 7

rng = 8

rng = 9

rng = 10

[kwcckw]

gr also looks quite interesting, but edges in e_ looks cleaner:

[kwcckw]

So, in this image we have unidirectional edges, which means that m is is generally proportional to g. That's why there is very little difference between m and e. We can make it bigger by using g*2 or *3?

actually i tried with raccoon image and using g*3 in computing e__, i can see edges in e__ looks better a bit comparing with m__ now, but i'm not sure whether is the effect of scaling since i'm scaling all negative values to positive.
intra_comp0.zip

It should be different with bidirectional edges (ridges): thin dark / light lines on light / dark background. Maybe hair strands in raccoon, or text, using large kernels?

Yes, i'm testing with rng of 1 to 10, and with input raccoon image. Now, e__ looks better when rng is low (rng = 1), but when rng gets bigger, it's hardly to see any difference between e__ and m__.

But m (SAD) does look a lot better than g for edge detection, do you know why people use g?

I don't have much info on this, and actually i never heard of SAD until now. Maybe it's called another term but i'm didn't aware of it. Or it's just don't have any people using this approach in any of the published work yet.

BTW, it would look better with dark contours: displayed intensity should be inverse to g / m / e.

Yes, i just pushed another edit to display dark contours and bright edges.

[boris-kz]

So, m - g is distinct when g cancels-out within a kernel: we have two edges with opposite angle, or thin ridge.
But that only works if kernel size ~ ridge width. Most images have ridges of various width, so the effect is hardly noticeable for any given kernel size. The exception would be text: letters are composed of fixed-width lines.

Maybe it's called another term but i'm didn't aware of it. Or it's just don't have any people using this approach in any of the published work yet.

That's highly unlikely, SAD is an established term, and simpler to compute than G. G is useful when you need to consider direction, but we can still use SAD for magnitude.

[kwcckw]

Yes you are right. I found some previous works on SAD and most of them related to matching application.

https://www.researchgate.net/publication/220501047_Faster_image_template_matching_in_the_sum_of_the_absolute_value_of_differences_measure

https://www.sciencedirect.com/science/article/pii/S2215016120303149

However, a brief reading in wiki shows that SAD can be used for object recognition as well, but need some edge detection to complement it:

https://en.wikipedia.org/wiki/Sum_of_absolute_differences

So, m - g is distinct when g cancels-out within a kernel: we have two edges with opposite angle, or thin ridge.
But that only works if kernel size ~ ridge width. Most images have ridges of various width, so the effect is hardly noticeable > for any given kernel size. The exception would be text: letters are composed of fixed-width lines

so if the kernel size is too small and ridge size is large, it might not able to detect the edges since there is no distinct changes detected. And if the kernel size is large and ridge size is small, the detected edges may not notice-able or distinct enough. So maybe a feedback system to change the kernel size dynamically after we perform some 1st level of processing on certain section of image (blob by blob)?

[boris-kz]

That paper is on template matching, not edge detection.

So maybe a feedback system to change the kernel size dynamically after we perform some 1st level of processing on certain section of image (blob by blob)?

Ridge width also changes within a blob. So, I don't see any consistent way to use e, except for text and hand drawings.
It may not be needed, we will combine the two edges of a ridge after comparing them, in comp_blob.

[kwcckw]

That paper is on template matching, not edge detection.

So maybe a feedback system to change the kernel size dynamically after we perform some 1st level of processing on certain section of image (blob by blob)?

Ridge width also changes within a blob. So, I don't see any consistent way to use e, except for text and hand drawings.
It may not be needed, we will combine the two edges of a ridge after comparing them, in comp_blob.

Alright, maybe after we have some initial results in comp_blob, we can compare their output and evaluate again.