Time-domain velocity and moveout parameters can be directly obtained from local event slopes, which are estimated on the prestack seismic gathers. In practice, there are always some errors in the estimated local slopes, especially in low signal-to-noise ratio (S/N) situations. Thus, subsurface velocity information may be hidden in the image domain spanned by velocity and other moveout parameters. We have developed an accelerated clustering algorithm to find cluster centers without prior information about the number of clusters. First, plane-wave destruction is implemented to estimate the local event slopes. For every sample in the seismic gathers, we obtain the estimations of velocity and its location in the image domain, according to the local event slopes. These mapped data points in the new domain exhibit the structure of groups. We represent these points by a mixture distribution model. Then, the cluster centers of the mixture distribution model are located, which correspond to maximum likelihood velocities of the main subsurface structures. Approximate velocity uncertainties bounds are used to select centers corresponding to reflections. Finally, interpolation is performed on the clustered unevenly sampled knot velocities to build the effective velocity model on regular grids. With synthetic and field data examples, we have determined that the proposed automatic velocity estimation method can give a stacking velocity model and a time migration velocity model with relatively high accuracy.