Trajectory-clustering-based methods have shown a good performance in counting moving objects in densely crowded scenes. However, they still fall into trouble in complex scenes, such as with the close proximity of moving objects, freely moving parts of objects, and different object size in different locations of the scene. This paper proposes a new method combining velocity and location-specific spatial clues in trajectories to deal with these problems. We first extract the velocities of a trajectory over its life-time. To alleviate confusion around the boundary regions between close objects, extracted velocity information is utilized to eliminate unreal-world feature points on objects' boundaries. Then, a function is introduced to measure the similarity of the trajectories integrating both of the spatial and the velocity clues. This function is employed in the Mean-Shift clustering procedure to reduce the effect of freely moving parts of the objects. To address the problem of various object sizes in different regions of the scene, we suggest a technique to learn the location-specific size distribution of objects in different locations of a scene. The experimental results show that our proposed method achieves a good performance. Compared with other trajectory-clustering-based methods, it decreases the counting error rate by about 10%.