Polygon Drawing Comparison - August 2006

Introduction

Erica Liszewski was an intern at the USGS until July 2006 and an alumna of the Northern Arizona University Computer Science Department. During her internship, she built two new tools for GLIMSView. The Output Spreadsheet tool converts the pixel values of an image in a region of interest defined by a selected polygon to a delimited text format suitable for import into spreadsheets and other data analysis applications. The Image Polygon Calculator automatically draws polygons around regions selected based on a comparison operation provided by the user, based loosely on the Threshold tool built by Dan Mingus.

Status

The Output Spreadsheet tool is complete. The Image Polygon Calculator is in the final phases of refinement. Erica has left the USGS to pursue a Masters degree in Computer Science. Deborah Lee Soltesz has taken over development and maintenance of these new tools.

Polygon Drawing Tool Development

The Image Polygon Calculator drawing algorithm tends to fall apart in cases where it is faced with multiple paths to follow (such as lines intersecting a polygon, lines that fork, etc.), resulting in many small lines where a single polygon should be drawn. Deborah has been working on several modifications to Erica's original work to improve these results.

Deborah modified the basic algorithm so that when the algorithm reaches a dead-end, it backs up to a fork or split in the line it was following, trims that path off and turns it into a line, and continues along another path to complete the polygon.

The part of the algorithm Deborah is currently working on refining is the path-picking procedure. When the algorithm meets a "fork in the road," the path-picking procedure determines which path the algorithm will choose to follow. There are three path-picking algorithms currently being explored and available for use in the Image Polygon Calculator tool.

• Basic Path Picking Algorithm: The original algorithm written by Erica Liszewski (with minor modifications mentioned earlier). In this algorithm, the next path to follow is based on weighting horizontal and vertical directions more highly than diagonal directions.
• Tweak 1 - Directional Momentum: In this algorithm, the next path to follow is based on weighting the last direction of travel highest. If the algorithm cannot continue to follow the same direction it has been going, it looks increasingly to the left and right of the original direction of travel for a new path to take.
• Tweak 2 - Longest Path: In this algorithm, the next path to follow is based on which path leads the farthest, under the presumption that short paths lead to dead-ends and long paths lead back to the start of the polygon (thus completing the polygon).

The images presented here show the basic map of selected pixels that the polygon drawing algorithm will use, and three runs of GLIMSView's Image Polygon Calculator using each of the three path-picking algorithms.

View images

Future Developments

The highest priority development is to refine the polygon drawing algorithm to acheive the best and most accurate results. When that is completed, additional functionality will be added, such as:

• Selection Preview: A preview of the selection resulting from the provided comparison function will be provided (similar to the preview in the Threshold tool).
• Save selection map: The user will be able to save an image of the selection map, a two color image that could be used as a classification image in other applications.
• Favorites: The user will be able to add the current comparison operation in a list for use in later sessions. This will also include a management tool to allow the user to re-order and remove operations from the list.
• History: Operations will be saved to history so they can be recalled easily.
• Classification Map Tool: A new tool, based on the Image Polygon Calculator, that allows the user to generate a raster classification layer (instead of polygons). This tool will depend on extending GLIMSView's capabilities to include opening multiple images into the same workspace, and creating multiple work layers for both raster and vector data.