1. A method for region extraction, the method comprising: obtaining, by one or more computing devices, an occupancy grid comprising a first plurality of cells; designating, by the one or more computing devices, a second plurality of cells as a plurality of centroids, the second plurality of cells being a subset of the first plurality of cells; and performing, by the one or more computing devices, a plurality of assignment iterations, each assignment iteration comprising: assigning, by the one or more computing devices, each of the first plurality of cells to one of the plurality of centroids based on a cost formula such that a plurality of regions respectively associated with the plurality of centroids are formed, wherein the region for each centroid comprises all of the cells assigned to such centroid; reassigning, by the one or more computing devices, one or more of the first plurality of cells to one or more respective alternate regions, the one or more reassigned cells having been included in one or more problem areas of one or more of the plurality of regions; and relocating, by the one or more computing devices, the plurality of centroids to be the respective means of the plurality of regions.