Recent evidence suggests that quantitative assessment of microcirculatory dysfunction may indicate certain disease states [1, 2, 3]. Relevant microcirculatory hemodynamic parameters include total vessel density, density of perfused vessels, proportion of perfused vessels, and perfusion heterogeneity index. In one non-invasive, clinical approach, a handheld video microscope placed under the tongue records images of blood flow in small (< 20µm) and medium (approximately 20–100µm) diameter vessels. Hemodynamic parameters are computed from measurements of vessel geometry and blood flow rates. Current technology is limited by poor dynamic range, low resolution, poor image stability, and pressure artifacts. Video images are analyzed quantitatively and semi-quantitatively by trained image analysts using a time-consuming, semi-automated techniques for vessel segmentation, and blood flow measurements. Space-time images are generated for quantitative velocity estimation. We propose a novel line detection method to automatically estimate the orientation of red blood cell (RBC) or plasma gap traces in space-time images. Velocities of RBCs can then be calculated based on the estimated orientation. The proposed automated method for velocity estimation was implemented for 80 vessels and compared with visual estimation of reference slope in space-time diagrams by a trained image analyst. Finally, the proposed method is compared with a Hough transform based velocity estimation method.