The fast development of imaging techniques during last decades makes it possible to introduce intra-operative visualization as the integral part of surgical procedures. Therefore, the automated analysis of intra-operative ultrasound images is appreciated. The image processing, registration and visualization techniques help in better understanding and locate the operated region. To meet these needs, the paper presents an advanced algorithm for automated detection of tissue deformations caused by a biopsy needle. For this, feature set of Histogram of Gradients (HoG) is introduced. The extracted feature vectors are then used in image cell clustering step resulting in tissue deformation as well as biopsy needle detection. The applied there Kernelized Weighted C-Means clustering technique enables robust and accurate needle detection proven by sensitivity and specificity values at levels of 0.846 and 0.99, respectively.