5
$\begingroup$

Imagine I have $N \approx 10^5$ clouds of points in an array of the form:

UPDATED

numClouds = 10^3;
cloudList = Table[Table[{RandomInteger[{0, 2}] + RandomReal[{-0.1, 0.1}], RandomInteger[{0, 2}] + RandomReal[{-0.1, 0.1}]}, {j, 1, RandomInteger[{0, 50}]}], {i, 1, numClouds}];

Notice that we generate points here by first randomly snapping them to a coordinate in an integer lattice, and then adding some real number valued noise:

ListPlot[Flatten[cloudList,1]]

I'd like to move a sliding window over cloudList of size $k$ (e.g. $k = 10$) where we take all of the points in {cloudList[[i]], cloudList[[i+1]], ..., cloudList[[i+k]]}, establish cliques for points within a Euclidean distance $d$ of one-another (i.e. if we can place a circle of diameter $d$ over a set of points, it's a clique), and then replace all of the points within each clique with the median or mean point value of the given clique. I would like to do this without disturbing the array structure of cloudList.

In terms of finding a fast way to grab all the points within a critical radius of $\frac{d}{2}$, we can use a poorly documented version of Nearest:

Nearest[data, x, {n, r}]
give up to the n nearest elements to x within a radius r

The above was from an answer by the user "ssch" (https://mathematica.stackexchange.com/users/1517/ssch) to my question: Selecting for 2D points that are within a threshold distance of an upper- and lower-bound number of points


Update - I neglected to specify what should occur when points can belong to more than one clique. The user belisarius (https://mathematica.stackexchange.com/users/193/belisarius), for example, asked about the cliques for a point set Tuples[{1, 0}, 2] where r = 3/2. Here, all four points belong to the same clique:

list = Tuples[{1, 0}, 2];
nf = Nearest[list];
nf[list[[1]], {Infinity, N[3/2]}]

out :: {{1, 1}, {1, 0}, {0, 1}, {0, 0}}

So we'd set each point in this clique to {1/2,1/2}.

However, if we set r = 1, we have Binomial[4, 3] = 4 seperate cliques with overlapping points:

{{1, 1}, {1, 0}, {0, 1}}
{{1, 0}, {1, 1}, {0, 0}}
{{0, 1}, {1, 1}, {0, 0}}
{{0, 0}, {1, 0}, {0, 1}}

To resolve this, I'd like to generate each clique as above, compute a mean for each clique, and where points fall in multiple cliques, to randomly assign these points the mean or median value selected with uniform probability from each clique. However, I'd be open to simpler solutions that are easier to implement.


(2nd) Update - I have changed the method of generating the random test set s.t. we now first snap a randomly generated test point to a bounded integer lattice coordinate, then add noise.


(3rd) Update - This is more of a note, but I would be fine employing a simple greedy algorithm to partition points into clusters, or using FindClusters with a EuclideanDistance distance function (this is slightly less comfortable since I'm not exactly sure what the underlying algorithm is).

$\endgroup$
6
  • $\begingroup$ In order to understand what is a clique of radius r == Sqrt[3/2] please consider the points Tuples[{1, 0}, 2] and tell us which ones are the "established cliques" that you want to replace by its mean point value.Thanks! $\endgroup$ Oct 29, 2013 at 9:03
  • $\begingroup$ @belisarius I've updated my question to specify what should happen if a point intersects multiple cliques. Please let me know if I can clear the matter up further? $\endgroup$
    – RTaylor
    Oct 29, 2013 at 9:07
  • $\begingroup$ Imagine then a uniform and dense point distribution in the unit square and r=1/10 ... you have almost the same number of possible cliques than points! $\endgroup$ Oct 29, 2013 at 9:20
  • 1
    $\begingroup$ @belisarius You're right - the way I'm specifying sample points is absurd. Let me think how to cluster them so that the test set makes more sense... $\endgroup$
    – RTaylor
    Oct 29, 2013 at 9:31
  • $\begingroup$ Clustering is implemented in Mathematica in a lot of ways. Search for "cluster" in the help system $\endgroup$ Oct 29, 2013 at 9:39

2 Answers 2

4
$\begingroup$

An alternative to using a clustering method would be to try one of the nonlinear filters. In this case, the MeanShiftFilter might be useful:

ListPlot[MeanShiftFilter[Flatten[cloudList, 1], 500, 0.5]]

enter image description here

This uses a sliding window approach and finds all the points in the neighborhood and then averages only those within the 0.5 radius. While this doesn't give you exact values, presumably you could quantize the resulting small blobs without too much trouble. You can get qualitatively the same results using the BilateralFilter as well:

BilateralFilter[Flatten[cloudList, 1], 200, 0.2]
$\endgroup$
8
  • $\begingroup$ This is a very reasonable thing to suggest (I suppose that the sliding window is of size $500$ here). Can I use this filter without flattening my data set, or losing the index for my data set? The problem is that I have a 1-to-1 correspondence between cloudList and another array, and I don't want to lose the index or scramble the elements. $\endgroup$
    – RTaylor
    Oct 29, 2013 at 18:29
  • $\begingroup$ If you want the best averaging, then you'll want to average over a lot of data... there are not many points in each of your cloudList[[i]]'s so you won't get very good averaging. But you should be able to un-flatten the filtered data if you want to recover the structure. Partition is the usual way to do this. $\endgroup$
    – bill s
    Oct 29, 2013 at 18:36
  • $\begingroup$ In terms of "unflattening" a list, I was also just reading through the set of fantastic answers to: mathematica.stackexchange.com/questions/30405/… $\endgroup$
    – RTaylor
    Oct 29, 2013 at 19:02
  • $\begingroup$ Can I assume that MeanShiftFilter will not scramble the input data points and will simply replace them with a mean value for the clique? In other words, if I flatten cloudList, apply MeanShiftFilter, and then unflatten it by inserting partitions, will there still be a 1-to-1 correspondence between elements in the pre- and post-processed arrays? $\endgroup$
    – RTaylor
    Oct 29, 2013 at 19:03
  • $\begingroup$ Obviously, you would need to check, but I believe the answer is yes. MeanShiftFilter processes things just like a moving average, except that the output at each point is calculated somewhat differently (the mean is taken not over all samples, but over all those nearby in value). $\endgroup$
    – bill s
    Oct 29, 2013 at 21:33
6
$\begingroup$

The natural choice is FindClusters[], and it will work quite well in these kind of situations, provided you are willing to experiment a little with its options:

s = FindClusters[Flatten[cloudList, 1], 
                DistanceFunction -> ((E^(SquaredEuclideanDistance[#1, #2]) - 1) &), 
                Method -> {"Agglomerate", "Linkage" -> "Complete"}]; 
ListPlot[s,  PlotMarkers -> Automatic]

Mathematica graphics

ListPlot[Mean /@ s, PlotStyle -> PointSize@Large]

Mathematica graphics

$\endgroup$
1
  • $\begingroup$ It's important for me that I restrict clusters to only existing within a certain sliding window for cloudList (points with an index in cloudList greater than the window size cannot be in the same cluster). Is there a way to easily enforce this? $\endgroup$
    – RTaylor
    Oct 30, 2013 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.