According to one embodiment, a feature extraction device includes an obtaining unit that obtains image data having a plurality of pixels. The device includes a pixel feature calculation unit that calculates first pixel features and second pixel features of each of the pixels, which are different from each other, and a classification unit that classifies a pair of pixels by using the first features for at least some of the plurality of pixels. The device includes a co-occurrence frequency calculation unit that calculates a co-occurrence frequency representing a frequency of co-occurrence of the second pixel features of the first pixel and the second pixel features of the second pixel for the set for which a result of the classification by the classification unit is consistent.