Generalizing the Mean-Shift Procedure

The mean-shift procedure [60,155,27,32,57] moves each point in a feature space to a weighted average of other points using a weighting scheme that is similar to Parzen windowing. We can also view this as moving points uphill on a PDF defined by placing a Parzen-window kernel at the points. Comaniciu and Meer [32] propose an iterative mean-shift algorithm for image intensities, where the PDF does not change with iterations, for image segmentation. Each grayscale or vector pixel intensity is drawn toward a local maximum in the corresponding PDF.

This section shows how UINTA relates to the mean-shift procedure. Consider, as an example, a gradient descent on the entropy of the grayscale pixel intensities. This gives

$$\frac {\partial \tilde x_t} {\partial \tau} = - \lambda \frac {\partial h (\tilde X)} {\partial \tilde x_t}$$

$$\approx - \frac {\lambda} {\vert\mathcal{T}\vert} \sum_{s \in \mathcal{A}... ...\tilde x_t - \tilde x_u, \Psi_1)} \Psi_1^{-1} (\tilde x_t - \tilde x_s) \Bigg),$$ (110)

where $\tau$ denotes the time-evolution variable. Finite forward differences, i.e.,

$$\tilde x_t^{m+1} = \tilde x_t^m - \lambda \frac {\partial h (\tilde X)} {\partial \tilde x_t^m},$$ (111)

with a time step $\lambda = \vert\mathcal{T}\vert \sigma^2$ give

$$\tilde x_t^{m+1} = \tilde x_t^m + \Bigg( \frac { \sum_{s \in \mathcal{A}_t} G_1 (\ti... ...mathcal{A}_t} G_1 (\tilde x_t^m - \tilde x_u^m, \Psi_1) } - \tilde x^m_t \Bigg)$$

$$= \sum_{s \in \mathcal{A}_t} \tilde x_s^m W_s (\tilde x_t^m, \tilde x_s^m, \Psi_1)$$ (112)

Each new pixel value $x_t^{m+1}$ is, therefore, a weighted average of a selection $\mathcal{A}_t$ of pixel values from the previous iteration $x_s^m$ with weights $W_s (\cdot) > 0$ such that

$$\forall t \in \mathcal{T}, \sum_s W_s (\tilde x_t^m, \tilde x_s^m, \Psi_1) = 1.$$ (113)

Taking $\mathcal{A}_t = \mathcal{T}$ gives exactly the mean-shift update proposed by Fukunaga [60]--note that UINTA updates the PDFs on which the samples climb every iteration. Thus the mean-shift algorithm is a gradient descent on the Shannon entropy [154,34] associated with the grayscale intensities of an image. In the mean-shift algorithm each sample $\tilde x_t$ is being attracted towards every other sample in $\mathcal{T}$, with a weighting term that diminishes with the distance between the two samples. The UINTA updates have the same form, except that it influences the weights not only by the distances between intensities $\tilde x_s$, but also by the distances between the neighborhoods ${\bf\tilde y}_s$. That is, pixels in the image with similar neighborhoods have a relatively larger impact on the weighted mean that drives the updates of the center pixels.