It's true, exercising will help A LOT.
I used to blush EVERY class when I thought someone was looking in my direction; it didn't matter that I didn't care who they were, male or female I'd blush immediately when before I only blushed once and a while.
After that I started exercising to improve my self image, and began walking every day which lead up to jogging every day. Now I blush only once a week or so, which is SO much better than EVERY class.
So yeah, try exercising.