To address random measurement errors caused by edge anomalies in tooth-profile images during vision-based measurement, a sub-pixel edge detection algorithm for tooth profiles based on the Pauta criterion and the Frobenius norm is proposed. First, the local gear image is preprocessed using Gaussian filtering and dual-threshold gray-level binarization to obtain the pixel-level edge location of the tooth profile. Then, according to the properties of the involute curve and gear parameter calculation formulas, ten involute tooth-profile parameters corresponding to point Pk in the tooth-profile edge transition zone are determined, and a complete tooth-profile parameter information matrix is established. Based on the generation principle of the involute curve, the points in the tooth-profile edge transition zone are inversely mapped onto the base circle. By discretely dividing the base-circle phase angle τi, equal-arc-length quantized segmentation along the tangential direction of the pixel-level involute tooth-profile edge is achieved, thereby constructing a Bertrand gray surface model. Finally, the improved F-norm and the 2σ Pauta criterion are used to eliminate outliers in the Bertrand gray surface model Σi. The gray centroid method is then applied to the filtered points in the edge transition zone to detect the sub-pixel edge of the tooth profile, thereby obtaining the sub-pixel-level toothprofile edge location. Gear pitch measurement is realized by calculating the initial phase angle of the involute tooth-profile. The experimental results show that the single-pitch measurement results obtained using the proposed algorithm are close to those obtained using the improved Bertrand gray surface model-based visual pitch measurement algorithm, with a maximum deviation of 1.1 μm. Compared with the pitch measurement results obtained using a coordinate measuring machine, the proposed method achieves a maximum deviation of 2.3 μm, a mean deviation of 0.9 μm, and a standard deviation of 1.4 μm. These results demonstrate that the proposed improved F-norm based gray centroid sub-pixel edge detection algorithm rapidly and accurately detects single-pitch deviation. The proposed algorithm can meet the high precision requirements for pitch measurement of grade-5 spur gears.