We present a novel algorithm for image denoising. Our algorithm is based on random walks over arbitrary neighbourhoods surrounding a given pixel. The size and shape of each neighbourhood are determined by the configuration and similarity of nearby pixels. Assuming that pixels within the neighbourhood of x0 are likely to have been generated by the same random process, we want the weights used to mix these pixels during denoising to depend on the similarity between them and x0. At the same time, we require the random walk to follow a smooth path from x0 to any other pixel in the neighbourhood, so the transition probabilities should also depend on the similarity between pairs of neighbouring pixels along any given path. With this in mind, we define a random walk originating at pixel x0 as an ordered sequence of pixels T0,k = {x0,x1, . . . ,xk} visited along the path from x0 to xk. Within this sequence, the probability of a transition between two consecutive pixels x j and x j+1 is defined to be