| | 49 | * Discussion about the algorithm and literature |
| | 50 | >>Markus: |
| | 51 | >>I was reading through the literature that Moritz sent and think that the implementation of mean shift is relatively easy. The most complicated part is figuring out a method for adaptive bandwidth where the spatial and the range bandwidth might need to be adapted differently. |
| | 52 | >>As far as I understand, the mean shift method consists of two parts 1. change band values to become more similar to neighboring cells by use of a spatial and a range weighing kernel 2. identify connected components (cells with similar band values), this is also known as clusters or in GRASS as clumps (r.clump). For this part, a modified version of the r.clump code can be used |
| | 53 | >>All together, this seems much simpler than the current region growing method, e.g. the search trees used by region growing are not needed for mean shift. |
| | 54 | >> |
| | 55 | >>More technical: |
| | 56 | >>If I understand correctly, mean shift requires three parameters: |
| | 57 | >>spatial bandwidth, range (band value) bandwidth, and threshold to indicate when to stop adjusting band values (max difference < threshold). Apparently, result improve if the two bandwidths are adapted for each sampling window separately. As weighing function I suggest a Gauss kernel, this is already available at various places in the GRASS source code. For spatial weighing, a finite kernel is needed and the Gauss kernel is infinite. The spatial bandwidth could mean standard deviation in number of cells, the cap could be set at standard deviation times 3 or 4, making it a finite kernel. For the range weighing, an infinite Gauss kernel is fine because the range of observed values is restricted by the finite spatial kernel. See also r.resamp.filter which offers various finite and infinite kernels and an explanation of their difference. The existing methods to use either euclidean or manhattan distance can be used as is for mean shift. |
| | 58 | >>Suggested code structure for mean shift is in trunk r68482. |
| | 59 | >> |
| | 60 | >>The identification of connected components (neighboring cells with similar band value) would also need a threshold, maybe the same threshold as for the main mean shift algorithm can be used. |
| | 61 | >>Additionally, the already existing option to consider 4 or 8 neighbors can be acknowledged. |
| | 62 | >> |
| | 63 | >>I guess the mean shift algorithm will be faster and less memory intensive than the region growing algorithm. |
| | 64 | |
| | 65 | |
