System for delineating and annotating areal regions

Abstract

A system for delineating partially- or fully-bounded areal regions of a map utilizes deformable templates, which it dynamically expands and contorts to conform to the boundaries of the regions. The system segments the map into a number of cells, with each cell relating, for example, to a pixel. The system then defines an 'energy' field for the floor plan by assigning cells corresponding to boundary edges predetermined minimum energy values, cells corresponding to boundary interiors predetermined maximum energy values, and each non-boundary cell an energy value defined by the distance of the cell from the closest boundary edge cell. The system then iteratively manipulates a template over a selected region of the floor plan in an attempt to minimize the 'potential' of the template, which is defined by a potential function that includes a 'total energy score' and various size and test terms that encourage desired template deformations. The system determines the total energy score, by (i) scan converting the template sides, (ii) weighting the energy values of the cells through which the sides pass based on the lengths of the sides passing through the cells, and (iii) summing the scores. After determining the potential for all possible new locations for each of the vertices, the system selects next locations for each of the vertices and, as necessary, moves the vertices to these next locations to complete an iteration. At various times, the system raises the energy field and updates the template by altering the number of vertices. The system ends its manipulations of the template when it has performed a predetermined number of iterations or, in an energy field at its ceiling values, either the template vertices do not move between iterations or the potential of the template does not change. A user may then edit the template to conform the template more closely to the selected region. A user may also specify certain constraints on template deformation. In response, the system uses a modified potential function for controlling the deformation of the template.