In this paper we present parallel implementations of two vision tasks; stereo matching and image matching. Linear features are used as matching primitives. These implementations are performed on a fixed size mesh array and achieve processor-time optimal performance. For stereo matching, we proposeO(Nn3/P2) time algorithm on aP ×P processor mesh array, whereN is the number of line segments in one image,n is the number of line segments in a window determined by the object size, andP ⩽n. The sequential algorithm takesO(Nn3) time. For image matching, a partitioned parallel implementation is developed.O[((nm/P2) +P)nm] time performance is achieved on aP ×P processor mesh array, whereP2 ⩽nm. This leads to a processor-time optimal solution forP ⩽ (nm)1/3.