Tools disclosed herein comprise progressive, paint stroke based region recognition and selection tools. Using these tools, a user may partially paint a region of interest directly on an image (by using a paint brush or other similar tool). Unlike conventional selection tools, a user is not required to paint the entire region pixel-by-pixel. Rather the desired region is automatically and intelligently recognized based on the partial selection. This is accomplished via a progressive selection algorithm. In addition, these tools provide the ability to quickly execute such region selections on multi-megapixel images.