Questions mean shift noise removal and color reduction

Questions and postings pertaining to the usage of ImageMagick regardless of the interface. This includes the command-line utilities, as well as the C and C++ APIs. Usage questions are like "How do I use ImageMagick to create drop shadows?".
User avatar
fmw42
Posts: 22081
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: Questions mean shift noise removal and color reduction

Post by fmw42 » 2017-08-06T16:24:25-07:00

The k-means, with SD normalisation* result looks pretty good. Where did the SD normalization idea come from? I did not see that in the reference?

What p value did you use for your harmonic mean approach?

Have you tried the expectation maximization technique at that reference and also at https://en.wikipedia.org/wiki/Expectati ... _algorithm

snibgo
Posts: 9380
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Questions mean shift noise removal and color reduction

Post by snibgo » 2017-08-06T17:53:04-07:00

I got the idea from the reference:
Before clustering, all datasets used in both experiments are shifted
and re-scaled to give each dimension zero mean and unit variance.
This is the standard z-score transformation. This can be a good idea
before using algorithms based on distance metrics, as it gives the
same influence to each dimension.
I simply scale two of the channels down, to roughly equalise the SDs of the three channels. Does equalising the mean also change the result? I don't know.

For harmonic P, I used 3.5.

For fuzzy R, I used 1.5.

No, I haven't tried expectation maximization.

My k-means result is very similar to yours. I use a different measure for tolerance (I stop only when all the channels are below the specified value), so our results are not identical

I apply the methods to the three colour channels. The image may be in any colorspace.

For image segmentation, the reference uses five dimensions: x, y, l, u and v. I intend to add an option for including x and y.

I also intend to add sensible handling of alpha.
snibgo's IM pages: im.snibgo.com

User avatar
fmw42
Posts: 22081
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: Questions mean shift noise removal and color reduction

Post by fmw42 » 2017-08-06T19:42:30-07:00

snibgo wrote:
2017-08-06T17:53:04-07:00
I got the idea from the reference:
Before clustering, all datasets used in both experiments are shifted
and re-scaled to give each dimension zero mean and unit variance.
This is the standard z-score transformation. This can be a good idea
before using algorithms based on distance metrics, as it gives the
same influence to each dimension.
I simply scale two of the channels down, to roughly equalise the SDs of the three channels. Does equalising the mean also change the result? I don't know.

For image segmentation, the reference uses five dimensions: x, y, l, u and v. I intend to add an option for including x and y.

I also intend to add sensible handling of alpha.

I must have missed that paragraph. I see it now. But you would need work in HDRI mode to normalize by mean.

Equalizing both mean and std is what is done in Normalize Cross Correlation to make the pair of images have common statistics. That allows it to be less sensitive to brightness and contrast changes.

The five dimensional kmeans, is just the mean-shift. See

https://en.wikipedia.org/wiki/Mean_shift
http://comaniciu.net/Papers/MsAnalysis.pdf
http://www2.math.cycu.edu.tw/TEACHER/MS ... -shift.pdf
http://homepages.inf.ed.ac.uk/rbf/CVonl ... nShift.pdf
http://www5.informatik.uni-erlangen.de/ ... 13-MCF.pdf
https://www.intechopen.com/books/advanc ... mean-shift
http://www.hpl.hp.com/techreports/2009/HPL-2009-217.pdf

snibgo
Posts: 9380
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Questions mean shift noise removal and color reduction

Post by snibgo » 2017-08-10T08:33:05-07:00

Some cool results: cluster by fuzzy k-means method, with the best number of colours between 1 and 9. Show the clustered image. Then map the original to the selected colours, with dithering.

Code: Select all

%IMDEV%convert faces.png ( +clone -process 'kcluster m fuzzy jump 1,9' +write faces_fz.png -write mpr:MAP +delete ) -map mpr:MAP faces_fzm.png
Image

Image
snibgo's IM pages: im.snibgo.com

aigo
Posts: 29
Joined: 2017-06-26T12:02:47-07:00
Authentication code: 1151

Re: Questions mean shift noise removal and color reduction

Post by aigo » 2017-08-17T07:51:07-07:00

snibgo wrote:
2017-08-06T15:47:55-07:00
I get these results with an unpublished process module, based on http://people.csail.mit.edu/tieu/notebo ... amerly.pdf

k-means, without SD normalisation:

Image

k-means, with SD normalisation*:

Image

fuzzy k-means, without SDN:

Image

k-harmonic, without SDN:

Image

* SD normalisation is: before the process, multiply channels by ratio of standard deviations, to make SDs roughly equal in each channel. After the process, divide by the same numbers.
Hi Snibgo,

Thank you for this.

Can you please provide access to this module? Maybe as a bash script?

Thanks!

Aigo.

snibgo
Posts: 9380
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Questions mean shift noise removal and color reduction

Post by snibgo » 2017-08-17T08:36:23-07:00

It is now published. Full details at K-clustering, with source code at Process modules.

The source code is in C, so it becomes callable from within an IM "convert" or "magick" command. (Caution: I haven't tested it with v7.) You need to be able to build IM.

Feel free to translate it into bash or any language you want. The process iterates towards a solution. I don't know how to write that as a script and get good performance (ie with no file I/O at each iteration).
snibgo's IM pages: im.snibgo.com

User avatar
fmw42
Posts: 22081
Joined: 2007-07-02T17:14:51-07:00
Location: Sunnyvale, California, USA

Re: Questions mean shift noise removal and color reduction

Post by fmw42 » 2017-08-17T16:38:08-07:00

snibgo, I reviewed your work and it is extremely thorough. I liked the enhancements that you made to the basic kmeans clustering.

1) Different kinds of means
2) Different initializations for the color to use to start
3) Finding the optimum number of colors

Great job and especially making it into a -process module (Magick Filter)

Thanks.

snibgo
Posts: 9380
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Questions mean shift noise removal and color reduction

Post by snibgo » 2017-08-17T23:52:31-07:00

Thanks, Fred. I'm especially pleased with "jump" to find the optimum number of colours.

I've just found a bug: it doesn't process palette files correctly. I'll probably fix that today.
snibgo's IM pages: im.snibgo.com

Post Reply