Because of its ability to preserve signal edges while filtering out impulsive noises, median filtering is widely used in signal processing applications, e.g. deinterlacing. An edge-based median filtering (EMF) algorithm is proposed for adaptive deinterlacing. A criterion of motion vector reliability (MVR) is also introduced for better interpolation. For each motion compensated block, two motion vectors between opposite-parity fields and one between same-parity fields are taken into account. Experiments show that the proposed MVR and EMF are both very efficient. Outputs of the proposed EMF are much more similar to original progressive videos than those of objectively best EMF methods nowadays, without obvious visual distortions. Finally, the proposed EMF and MVR criterion are shown to be suitable for texture-based adaptive deinterlacing.