You can convert the blue-mask heathens by dropping a villager on them, but to convert the red- and yellow-masked guards you'll need to use the earthquake power.

Each time a master heathen (purple masks) is converted they drop one of the necklace pieces. You'll find the pieces on the ground near where each heathen was converted. They look rather like a collectable.