You can do this one of two ways:
1. Rephrase the segment qualification Smart Lists within Velocity:
2. Use the segments themselves directly:
The advantage of the former is that you can eliminate some segmentations entirely, provided their criteria can be echoed in Velocity (for example, they don't rely on Activity History). And you only get a limited number of segmentations.
The advantage of the latter is that if you've already set up your Smart Lists and/or they require a deeper peek into Lead characteristics, you can reuse the segment memberships in any permutation.