Abstract: X-ray computed tomography (X-ray CT) technology as a non-destructive testing method has been widely used to evaluate the air void structure and void-related distresses in asphalt mixtures. In this study, air void structural features of asphalt mixtures during rutting deformation procedure was investigated at the meso-structural level based on X-ray CT and digital image processing techniques. A volume-equivalent ball-and-stick model was proposed to characterize the changes of void connectivity. The distribution and shape features of air voids were described using the variation coefficient of modified annular-sector segmentation, positional eccentricity ratio, and sphericity, respectively. Results indicate that the influencing mechanism of permanent deformation on the air void structure of asphalt mixtures varies with the type of mixtures. Air voids are more heterogeneous and discrete in stone mastic asphalt (SMA-13) mixture compared to dense-graded asphalt concrete (AC-13), particularly for those with volume less than 0.01 mm³. Moreover, the air void connectivity and distribution in SMA-13 is more susceptible to load as the coarse aggregates tend to shift their positions during deformation. Although the rutting deformation increases the horizontal inhomogeneity of air voids in both mixtures, it reduces the vertical inhomogeneity of AC-13 but increases that of the SMA-13. Loading complicates and disperses the void geometry of AC-13 mixture whereas the opposite is true for SMA-13, foreboding that SMA mixtures maintain the potential to resist rutting failure after one hour of loading compared to AC types. In general, the topological characteristics of air voids within asphalt mixtures and their dynamic response during permanent deformation are principally dependent on mixture gradations.