Geometric model for visually debugging massive spatial datasets

Techniques herein are for generating geometric models. A method involves receiving a raw data set. Generation parameters include an abstraction function, a raw data set, a plurality of size pairs, and a quality interval. Each size pair comprises a view size and a portion size. The view size comprises an amount of display area. The portion size comprises an amount of raw data. For each size pair, associate a set of grid square sizes with the size pair. Each grid square size comprises a multiple of natural units. The quality interval contains a multiplicative product of the grid square size times a ratio of the view size to the portion size. Generate a set of geometric models based on the raw data set, the plurality of size pairs, the abstraction function, and the set of grid square sizes associated with the plurality of size pairs.

TECHNICAL FIELD

Embodiments relate generally to techniques for selecting geometric models from which display images may be generated. Specific techniques are included that use an incidence matrix to guide the selection.

BACKGROUND

The challenge of visualizing and interacting with a massive spatial or multidimensional dataset exists in many problem domains ranging from hotspots in chip design to stresses on the hull of a ship to displaying humungous matrices. Spatial data can grow along its physical dimensions or it can grow in terms of sheer density. Interactive visualization that is trivial to do with a small dataset becomes unwieldy if the data size is excessive.

A multitude of problem domains, like chip design, deal with massive spatial data. Design elements such as instances, transistor geometries, and other electrical elements are often projected on a Euclidean plane. Frequently there is a need to visualize such data to assist a human analyst. A good visual debugging tool provides an overview of phenomena to a user. The user can drill down on demand. Typically, the lifecycle of generating any visual involves devising a geometric model representing shapes in a virtual scene, using software graphics libraries to transfer the geometric model to a digital image, and using image processing to enhance the image further. Image processing is computationally expensive and hence done for visuals that are fairly static. Image processing traditionally is infeasible for dynamic images that change often, such as with a visual debugger that is able to almost instantaneously refresh.

DETAILED DESCRIPTION

Embodiments are described herein according to the following outline:1.0 General Overview2.0 Geometric Model Generation Generally2.1 Geometric Model Downscaling2.2 Eager Generation Of Geometric Models2.3 Size Parameters2.4 Image Quality Interval2.5 Selecting Geometric Models2.6 Populating Geometric Models With Data2.7 Cost Power Law Prunes NP-Hard Combinatorics3.0 Geometric Model Generation Process3.1 Selection Of Base Square Size3.2 Selecting A Geometric Model For Display Image Generation3.3 Maximizing Coverage Of Size Pairs During Geometric Model Generation3.4 Populating An Incidence Matrix And Calculating Unit Costs3.5 Using The Incidence Matrix To Select Base Square Size4.0 Unit Cost Of Generating A Given Geometric Model5.0 Hardware Overview6.0 Extensions and Alternatives
1.0. General Overview

Techniques are described herein for generating geometric models of raw data from which display images may later be generated. Raw data includes bulk empirical data that either represents spatial information or is otherwise amenable to spatial presentation. In an embodiment, a computer receives a raw data set. The computer also has metadata that guides geometric model generation. The metadata includes an abstraction function, an image quality interval, and size pairs. Each size pair has a view size and a portion size chosen by a visualization expert. The view size specifies an amount of display screen real estate. The portion size specifies an amount of the raw data set to consider.

Each geometric model to be generated has a Cartesian grid of a distinct grid square size. The computer associates grid square sizes with size pairs. Whether a given association is created depends on whether an image quality that is calculated from a given grid square size and given size pair fits within the image quality interval.

From the associated grid square sizes, the computer selects one to be the base square size. The computer also selects grid square sizes that are multiples of the base square size. For each selected grid square size, the computer generates a geometric model whose resolution is determined by the corresponding grid square size.

In an embodiment, an incidence matrix is used to select the base square size.

In an embodiment, a display image is generated from a geometric model.

2.0 Geometric Model Generation Generally

FIG. 1illustrates a block diagram of example computer100that generates geometric models of various resolutions from raw data based on quality criteria, in which techniques described herein may be practiced. Computer100may be a personal computer, embedded computer such as a single board computer, system on a chip, smartphone, network appliance, rack server such as a blade, mainframe, virtual machine, any other computer able to convert raw data into geometric models, or any aggregation of these computers. Computer100includes geometric models170, to be generated by computer100, and generation parameters110.

Although geometric models170may be raster graphics images in dot matrix format, geometric models170are not intended for display. Rather, geometric models170are an intermediate format from which display images may later be generated. Geometric models170may be encoded in any format from which display images may be generated with less computation than would be needed to generate display images directly from raw data set130. As such, geometric models170need not be encoded as raster graphics images, in dot matrix format, or in any graphics image format. Indeed, geometric models170might not directly involve visual data. For example, geometric models170may be heat maps composed of grid squares, with each grid square encoding a temperature, which is not visual data.

Generation parameters110is a collection of various information needed to intelligently determine the quantity, resolution, and content of geometric models170. Generation parameters110includes abstraction function120, quality interval140, size pairs150, and grid square sizes160. Generation parameters110may reside as isolated data, such as in a database or data file or as constants that are hard coded into a codebase.

Raw data set130may arrive at computer100by networked file transfer, remote messaging, interactive entry, other mechanisms of data ingestion, or combinations of these. Raw data set130includes bulk empirical data that either represents spatial information or is otherwise amenable to spatial presentation. For example, raw data set130may be a collection of polygons that each represents a very large scale integration (VLSI) circuit device, such as a transistor. Within raw data set130, these polygons may be encoded as vector graphics or other geometric primitives that are not rasterized, thereby making generation of geometric models170computationally expensive due to needing to perform rasterization.

Furthermore, because geometric models170may instead encode non-visual data, such as temperature, rasterization may be more complex than merely rendering polygons of raw data set130. For example if a geometric model170is a heat map of a VLSI circuit, then the temperature of a grid square may depend not only on which microelectronic devices occupy the grid square, but also which devices are nearby, how the devices are interconnected, and whatever additional computation is involved in distilling a local temperature value.

The complexity of calculating the value of a grid square is encapsulated in abstraction function120. Abstraction function120performs geometric and other mathematical aggregate operations that combine or adjust local shapes and data points that overlap, interfere, or otherwise have a combined effect and may depend on the size of the grid square. Aggregate operations may be statistical such as a maximum, a minimum, a count, a mean, a variance, a median, or a mode.

Additionally, raw data set130may exceed, by sheer volume, the presentation capacity of a user terminal such as a personal computer. For example, lossless presentation based on raw data set130might need screen real estate available only by aggregating dozens of computer display monitors. Without those monitors, lossless presentation of raw data set130might entail an hour of tedious scrolling within one display monitor. During rasterization of raw data set130, computer100may have the capacity and time needed to individually determine each natural data point of raw data set130. However, the human eye might not perceive so high a resolution, and the display personal computer might be unable to lively present such detail. Also, full resolution may have an excessive network transmission cost. As such, lossy compression is desirable, which is achieved by downscaling into a Cartesian grid that is coarser than the natural details of raw data set130.

Downscaling achieves a reduction of visual resolution that involves demagnification as if from a zoomed out vantage point such that fine details shrink until oversimplified or otherwise lost. Downscaling introduces problems such as maintaining image quality.

Each of geometric models170covers the entire geometric extent of raw data set130. However, each geometric model170has its own unique amount of downscaling or coarseness as specified by which grid square size160is used to generate a the geometric model170.

Grid square size160specifies the density of a geometric model170. Grid square size160defines the Cartesian grid into which raw data set130is rasterized. A small grid square size160defines a fine Cartesian grid. A large grid square size160defines a coarse Cartesian grid. The amount of downscaling and lossy compression imposed during generation of a geometric model170is proportional to the grid square size160used during generation. If grid square size160has a value of 1, then the least visual information is lost when generating a geometric model170. The visualization expert chooses what is a maximum grid square size160well before geometric models170are generated.

Image sharpness and smoothness suffer when downscaling is not optimized for a combination of a particularly sized region of raw data set130with a particular display resolution. Another problem with downscaling is its heavy computational load, which is unsuited for interactive use, even though most visual applications are interactive. The computational intensity of rasterization and downscaling may exceed the capacity of a personal computer, even though most visualization occurs at a personal computer.

2.2 Eager Generation of Geometric Models

Computer100avoids these problems by decoupling rasterization and downscaling from display image generation. This decoupling enables computer100to perform rasterization and downscaling to geometric models170and then defer display image generation for a later time or delegate display image generation to another computer such as a display terminal, which may be a personal computer. For example, computer100may have data storage and processing capacity much greater than that of the personal computer that eventually generates, or at least displays, corresponding display images.

Decoupling of rasterization and downscaling from image generation by computer100is temporal as well as architectural. Computer100eagerly generates geometric models170in advance and well before display image generation or presentation occurs. This enables a personal computer to show, almost instantaneously, display images that may have taken computer100several minutes or hours to generate, including generating geometric models170as an intermediate format. However, eager generation of geometric models170introduces additional problems, such as uncertainty as to which display monitor resolution will later be available and which zoom level will be desired.

2.3 Size Parameters

To overcome the problems introduced by eager generation of geometric models170, including downscaling of raw data set130, computer100utilizes abstraction function120, quality interval140, size pairs150, and grid square sizes160, as parameters that guide rasterization and downscaling during generation of geometric models170. As such, computer100potentially uses all of the information within generation parameters110to generate geometric models170.

A visualization may be shown on any of various display monitors having different screen resolutions. Eagerly generating geometric models170for all possible combinations of display resolution and zoom level is combinatorially intractable. A small subset of combinations, intelligently selected for high utility, is needed to guide computer100in the generation of geometric models170.

Computer100uses size pairs150as that high utility subset of display combinations. According to an embodiment, these combinations may be chosen by a person with expertise in evaluating image quality and visualization. After the visualization expert defines size pairs150, these pairs may be reused for many raw data sets130. Each size pair150includes portion size154.

Portion size154defines a rectangular extent within raw data set130, but is not dedicated to any particular region of raw data set130. For example, raw data set130may represent microelectronic circuitry details for a VLSI having sub-wavelength lithographic features including a billion transistors. As such, the natural resolution of raw data set130might be as coarse as 200 microns×200 microns per data point or possibly as fine as 10 nanometers×10 nanometers per data point.

Portion size154may be a rectangle sized to some multiple of the data point size to encompass some percentage of raw data set130. Portion size154effectively defines an initial zoom level. The smaller is portion size154, then the more initial magnification or zooming in is achieved, and the less raw data will be included in geometric models170generated with portion size154. However, portion sizes154are merely proposals that guide computer100during selection of a particular grid square size160to use when generating a geometric model170. Although each portion size154specifies a portion, all geometric models170cover the entire geometric extent of raw data set130.

Each size pair150also includes view size152. View size152defines a rectangular extent within a display monitor, but is not dedicated to any particular region of raw data set130. For example, a common modern display monitor size is 1,366 pixels×768 pixels. If intended for that common monitor size, view size152may specify any rectangle that does not exceed the monitor size. For example, if an expert decides that a user will often seek a visualization that fills only half of the display monitor, then view size152may be correspondingly smaller than the monitor size. The expert may choose a variety of display viewport sizes that are various fractions of a given display monitor size. Likewise, the expert may identify a variety of display monitor sizes based on market preferences that are current or recent.

As such, the expert may identify a dozen or so view sizes152. Likewise, the expert may define tens or more portion sizes154. These view sizes152may be exhaustively paired with these portion sizes154to achieve hundreds of pairings. However, the visualization expert then identifies a subset of these pairings that are expected to be needed most often and visually appear best. This expertly chosen subset of pairings is the extent of size pairs150.

2.4 Image Quality Interval

AlthoughFIG. 1shows a line that represents an association between grid square sizes160and size pairs150, this association may be initially absent in generation parameters110. Computer100may need to determine this association, which is many-to-many. Computer100may associate a given size pair150with more than one grid square size160. Likewise, computer100may associate a given grid square size160with more than one size pair150. Determination of this association is arithmetic and based on numeric attributes of grid square size160, size pair150, and quality interval140.

Quality interval140is a range of positive real numbers having a lower bound and an upper bound. Image quality measures how many display monitor pixels are needed to draw one grid square of a geometric model170. A small image quality value indicates high fidelity of geometric model170to raw data set130. A large image quality value indicates high compression within geometric model170. Quality interval140is chosen well before generation of geometric models170by the visualization expert. Experimentation revealed that an inclusive range of 1.5 to 4 is optimal for quality interval140during visualization based on modern VLSI design rules for feature sizes and popular modern display terminal sizes.

Computer100uses quality interval140to determine which size pairs150to associate with which grid square sizes160. Computer100makes this determination by calculating the image quality of a possible association between a given size pair150and a given grid square size160. Computer100performs this calculation according to a mathematical formula that multiplies the grid square size160times the ratio of view size152to portion size154. If and only if the formula result falls within quality interval140, then computer100makes an association between a given size pair150and a given grid square size160.

2.5 Selecting Geometric Models

Each of geometric models170represents the same area of a plane of a fixed natural size, such as 1,000×1,000 square microns. Each grid square size160has a value that is the length of a side of a unit square in a Cartesian grid and measured in units natural to raw data set130, such as microns. Each geometric model170is generated using a unique grid square size160. As such, multiple geometric models170do not share a grid square size160. Likewise, there are not more geometric models170than grid square sizes160. However there may be more grid square sizes160than geometric models170, in which case some grid square sizes160are not used to generate any geometric model170.

Not all grid square sizes160need be associated with size pairs150. Unassociated grid square sizes160are not used to generate a geometric model170. Furthermore, computer100detects a base square size that is which grid square size160is associated with the most size pairs150. According to criteria explained later herein, grid square sizes160that are smaller than the base square size are unlikely to be used to generate geometric model170. Only grid square sizes160that are multiples of the base square size are likely to be used to generate a geometric model170. However many grid square sizes160are used to generate a geometric model170determines how many geometric models170that computer100generates, since each grid square size160is used to generate at most one geometric model170.

2.6 Populating Geometric Models With Data

After identifying which geometric models170to generate, computer100fills them with data. Computer100first generates a finest geometric model170by using the base square size. Computer100populates the finest geometric model170by iteratively applying abstraction function120to the details of raw data set130. The finest geometric model170has a Cartesian grid with a unit square that matches the base square size. Each invocation of abstraction function120calculates a value for one unit square within the finest geometric model170. Once populated, the finest geometric model170can be used as a data source for downscaling to various degrees to populate the remaining geometric models170.

Computer100only uses grid square sizes160that are multiples of the base square size to generate the remaining geometric models170. This regularity of involved grid square sizes160simplifies the downscaling needed to populate the remaining geometric models170. Population of the finest geometric model170is the only one that involves rasterization from raw data set130. Population of the remaining geometric models170is based on the data in the finest geometric model170.

2.7 Cost Power Law Prunes Np-Hard Combinatorics

For example,FIG. 2depicts portion230of finest geometric model240and portion210of another geometric model220. Four base squares (BA, BB, BC, and BD) of finest geometric model240fit into a unit square, such as unit square B, of geometric model220. Because of this neat fitting, a computer need not apply an abstraction function to a raw data set to populate geometric model220with values. The computer may instead minimize computation by applying the abstraction function to the data of portion230to determine a value for unit square B. As such, the computer may derive the remaining geometric models by downscaling finest geometric model240.

Geometric Model Computation is modeled as a class of problems called ‘set covering problems’ in combinatorial optimization, specifically a binary integer programming problem. Such problems are typically NP-hard unless some problem-specific constraint or property can be used to eliminate combinations in bulk. Such a property is exploited to reduce computation while intelligently selecting which geometric models to generate. The cost of choices follows a predictable power law, because a grid square size compresses space by the square of its value. Hence, cost changes predictably.

3.0 Geometric Model Generation Process

FIG. 3depicts a flow diagram of an example process for generating geometric models. For illustrative purposes,FIG. 3is discussed in relation toFIG. 1.

Step302is preparatory and not computational. In step302, a computer receives raw data set130from which geometric models170may be derived. Spatial dimensions associated with raw data set130may be expressed in natural units, such as microns.

Step302is preparatory and not computational. In step302, a computer receives metadata and raw data needed to determine a variety of complementary and sufficient geometric models. Computer100also receives raw data set130.

In step304, the computer analyzes metadata to determine a variety of complementary and sufficient geometric models. For example, computer100has metadata that includes abstraction function120, quality interval140, size pairs150, and grid square sizes160. Computer100associates grid square sizes160to size pairs150to decide how many geometric models170to generate and what size are their unit squares.

Computer100uses quality interval140to determine which size pairs150to associate with which grid square sizes160. Computer100makes this determination by calculating the image quality of a possible association between a given size pair150and a given grid square size160. Computer100performs this calculation according to a mathematical formula that multiplies the grid square size160times the ratio of view size152to portion size154. If and only if the formula result falls within quality interval140, then computer100makes an association between a given size pair150and a given grid square size160. Step304may involve heuristics and structures, such as an incident matrix and cost metrics, that are described later herein.

In step306, the computer generates the geometric models. During this step, computer100has already decided which geometric models170to generate. Computer100applies abstraction function120to raw data set130to populate a finest geometric model170. Computer100may then downscale the finest geometric model170using a variety of grid square sizes160to generate the remaining geometric models170. Computer100may save geometric models170to files in durable storage for later use during visual image generation.

3.1 Selection of Base Square Size

FIG. 4illustrates a block diagram of example computer400that heuristically generates geometric models of various resolutions from raw data based on quality criteria, in which techniques described herein may be practiced. Computer400may be an implementation of computer100. Computer400has data structures that include size pairs441-442and grid square sizes451-456.

Computer400begins geometric model determination by first selecting a base square size from the available grid square sizes. As explained before, computer400uses a quality interval to determine which size pairs441-442to associate with which grid square sizes451-456. Computer400makes this determination by calculating the image quality of a possible association between a given size pair and a given grid square size. If and only if the calculated image quality falls within the quality interval, then computer400makes an association between a given size pair and a given grid square size. The result of such association determinations is shown inFIG. 4. Associated with size pair441are grid square sizes451-453, respectively sized at 1-3 microns. Associated with size pair442are grid square sizes452-456, respectively sized at 2-6 microns.

The union of all associations is shown as associations410, which includes grid square sizes451-456because those grid square sizes are associated with size pairs. Of the grid square sizes in associations410, grid square sizes452-453are each associated with two size pairs, which are the most associations of all the grid square sizes in associations410. As such, most associated420includes only grid square sizes452-453. Most associated420is relevant to computer400because it contains the grid square sizes that are the initial candidates for being the base square size, which is crucial for determining geometric models.

As a heuristic, computer400begins by selecting the biggest grid square size of most associated420for consideration as the base square size. As such, computer400selects grid square size453to evaluate as a possible base square size.

As already explained, computer400only generates geometric models whose grid square size are multiples of the base square size. Because in this example the base square size is 3 microns wide, the only other grid square size that has a multiple of 3 is grid square size456, which is 6 microns wide. As such, computer400considers generating only two geometric models that respectively have unit square sizes of 3 microns and 6 microns. This is shown as efficient multiples of three430that contains only grid square sizes453and456. However many grid square sizes are in efficient multiples of three430is how many geometric models that computer400will generate.

3.2 Selecting a Geometric Model for Display Image Generation

Later, after geometric model generation and during interactive display, a presentation device may try to show a portion of a geometric model at some zoom level and inside a cropped screen real estate. The presentation device may perform complex steps such as selecting a geometric model, fetching it from storage, and generating a display image for painting the cropped screen real estate. For various reasons, the presentation device may logically decompose a display image into rectangular tiles, such as to generate or cache some image portions.

The presentation device may be a sophisticated workstation computer rendering to a video wall. Alternatively, the presentation device may be minimal and barely more than a digital picture frame. If unequipped to perform a step while generating a display image from a geometric model, the presentation device may delegate almost any operation to a more capable computer, such as computer400. For example, a digital picture frame is likely incapable of directly utilizing a geometric model in any way. The digital picture frame may instead retrieve, zoom, and crop a display image stored on a data storage grid. Another computer would be responsible for generating display images from geometric models and then storing the display images on the data storage grid. In other words, the presentation device may be a federation of devices of various purposes.

The presentation device must decide which geometric model to use to generate a display image. A naïve implementation may generate the display image from a randomly selected geometric model, so long as the geometric model involves the desired raw data set. However, a random selection likely results in a display image that appears poorly focused and damaged by too lossy compression. Instead of random selection, embodiments may select according to criteria that give more detailed images and minimize blur.

For example, an embodiment may process rendering parameters, such as cropping bounds or acceptable latency to select a geometric model. For example, if latency is a priority, a geometric model with a bigger unit square size might load faster. If quality is a priority, then a smaller unit square size might be better.

An embodiment of the presentation device might have access to size pairs441-442, and if so might also be configured to compare rendering parameters to size pairs441-442to select a geometric model. Although not shown, size pairs441-442each have a view size of screen real estate and a portion size of a geometric model, as shown inFIG. 1. As such, the client device attempts to crop and zoom according to actual parameters that are more similar to one of size pairs441-442than the other one.

If the crop and zoom parameters are more similar to size pair441, then a display image may be generated from the geometric model that has grid square size453. This is because grid square size453is the only grid square size within efficient multiples of three430that is associated with size pair441. On the other hand, size pair442is associated with both grid square sizes within efficient multiples of three430. Therefore, if the crop and zoom parameters are more similar to size pair442, then a display image may be generated from either the geometric model that has grid square size453or the geometric model that has grid square size456.

3.3 Maximizing Coverage Of Size Pairs During Geometric Model Generation

FIG. 5illustrates a block diagram of example computer500that evaluates a base square size and conditionally replaces it, in which techniques described herein may be practiced. Computer500may be an implementation of computer100. Computer500has data structures that include size pairs541-543, which are associated with grid square sizes551-556.

Using heuristics similar to those used inFIG. 4, most associated520contains only grid square sizes552-553, each of which is associated with two size pairs. However, although grid square size553is shown as the base square size within multiples of three530, this is an inferior choice of base square size. The problem is that size pair541is not associated with any grid square size within multiples of three530. Size pair541might correspond to especially common rendering parameters.

The harm of skipping an important size pair can be assessed by measuring a coverage ratio of size pairs associated with multiples of three530to size pairs associated with any grid square size. With grid square size553as the base square size as shown, the coverage ratio is only 2 out of 3 size pairs or 67%, which might be unacceptable. For example, a coverage ratio should be at least 90% in practice.

Inadequate coverage may be cured by switching the base square size to a slightly smaller grid square size within most associated520. In this example, grid square size552is the only other one within most associated520. Although not shown, with grid square size552as the base square size, multiples530would instead contain only grid square sizes that are multiples of 2 instead of 3. As such, multiples530would contain only grid square sizes552,554, and556because their widths respectively are 2, 4, and 6 microns, which are multiples of 2. That gives 100% coverage.

3.4 Populating an Incidence Matrix and Calculating Unit Costs

FIG. 6illustrates example incidence matrix600that may be used when selecting a base square size, in which techniques described herein may be practiced. Incidence matrix600has size pair610and table rows621-622and641-645. Size pair610is a header column that lists pairs of numbers. The first number of each pair is the width, in natural units such as microns, of a square portion of the geometric models. The second number of each pair is the pixel width of a display image.

Grid square size621is a header row that lists grid square sizes in natural units such as microns. Cost622is a header row that lists a cost for each grid square size. Cost accounts for concerns such as compute, transport, and storage of a geometric model. Cost is defined as the inverse of the area of a Cartesian unit square of a geometric model.

Each square listed in grid square size621corresponds to a geometric model. The finest geometric model has a 1×1 grid square size and a cost of 1. The next finest geometric model has a 2×2 grid square size and a cost of 0.25. As the grid square size increases, the corresponding geometric model gets coarser, and the cost decreases. Indeed, a coarse geometric model costs less than a fine geometric model. The coarse geometric model needs less space and processing. This is especially true during geometric model generation, where geometric models are generated by downscaling a finest geometric model, the one with the base square size as its grid square size.

Cost is important for efficiency. A naïve embodiment may ignore cost and generate a geometric model for every desired grid square size. An optimized embodiment avoids generating a geometric model for some grid square sizes, such as those that increase cost without increasing coverage.

InFIG. 6, a thick black box is drawn around the binary cells of incidence matrix600. These binary cells have actual data, shown as blanks and checkmarks, which are not headers. This core of incidence matrix600is also known as a logical matrix, a binary matrix, a relation matrix, or a Boolean matrix. A checkmark indicates an association between a size pair and a grid square size.

As explained forFIG. 1, a quality interval determines which size pairs to associate with which grid square sizes. The determination is made by calculating the image quality of a possible association between a given size pair and a given grid square size. This calculation uses a mathematical formula that multiplies the grid square size times the ratio of display view size to portion size. If and only if the formula result falls within quality interval, then an association is made between a given size pair and a given grid square size.

For example, one row of incidence matrix600has a size pair of 1,000×1,500. The ratio of display view size to portion size is 1,500/1,000=1.5. To calculate image quality, this ratio is multiplied by whichever grid square size is contemplated. For example, a 2×2 grid square has a width of 2, which gives an image quality of 2×1.5=3, which is within a quality interval having a range of 1.5 to 4. As such, the 2×2 grid square size should be associated with the 1,000×1,500 size pair. Hence, a checkmark is shown in the cell at the intersection of the 2×2 column and the 1,000×1,500 row of incidence matrix600.

However, if image quality is recalculated with the 3×3 grid square size, then image quality is 3×1.5=4.5, which is not within the quality interval having a range of 1.5 to 4. As such, the 3×3 grid square size should not be associated with the 1,000×1,500 size pair. Hence, there is no checkmark in the cell at the intersection of the 3×3 column and the 1,000×1,500 row of incidence matrix600.

3.5 Using the Incidence Matrix to Select Base Square Size

Rows641-645of incidence matrix600can be automatically derived from the binary matrix within incidence matrix600. Associations641is a row of incidence matrix600that counts how many checkmarks each column of the binary matrix has. Each checkmark denotes an association.

Frequency642is a row of incidence matrix600that ranks how many checkmarks each column of the binary matrix has, relative to the other columns. Base square size643is a row of incidence matrix600that designates which column has the grid square size of the finest geometric model to be generated. Grid square sizes may be prioritized for evaluation as candidates for base square size. The priority may be according to frequency642, with ties going to the bigger grid square size.

According to frequency642, grid square sizes 5×5 and 6×6 are most frequently associated with size pairs. However, a base square size of 5×5 or 6×6 lacks coverage. Only half of the rows have checkmarks in either the 5×5 or 6×6 column, which is only 50% coverage. And, there are no efficient multiples of 5 or 6 to increase the coverage by contributing additional columns.

Because 5×5 and 6×6 are too big to be the base square size, the grid square sizes that are the next most frequently associated with size pairs are evaluated as candidates for base square size. Frequency642shows ALMOST in the 1×1 and 2×2 columns, so these columns are the next candidates. Grid square size 2×2 is bigger than grid square size 1×1, so grid square size 2×2 is evaluate first as a candidates to be the base square size. Base square size643shows that grid square size 2×2 is the base square size.

Efficient multiple644is a row of incidence matrix600that shows that 2, 4, and 6 are efficient multiples of 2, the base square width. Generating three geometric models with 2×2, 4×4, and 6×6 grid square sizes provides an adequate 90% coverage, because only the 400×1500 row of the binary matrix lacks a checkmark for those grid square sizes. However, this is not the cheapest set of geometric models that achieves 90% coverage.

For example, according to the binary matrix, all of the rows covered with checkmarks in the 4×4 column also have checkmarks in the 6×6 column. That means that the 4×4 column provides no coverage beyond what the 6×6 column provides. As such, the 4×4 grid square size is redundant since it does not increase coverage. Geometric model645is a row of incidence matrix600that designates which geometric models will be generated. Even though the 4×4 grid square size is an efficient multiple of the base square size, the 4×4 grid is not designated for generation because it is redundant.

Even though not all of the efficient multiples are used in this example, using efficient multiples helps quickly select a feasible set of geometric models. That is, efficient multiples accomplishes pruning of the solution space. When there are contiguous checkmarks on a row for a given size pair, then any grid square size within the contiguous range has similar coverage and so is likely to be redundant. There is not much value in simultaneously searching solution branches of contiguous columns. Efficient multiples cause searches to have some separation within the solution space, which is a more efficient way of searching for an optimum.

4.0 Unit Cost of Generating a Given Geometric Model

InFIG. 6, the example solution has two geometric models, which are 2×2 and 6×6, that achieve 90% coverage. However, another solution with two geometric models, which are 1×1 and 6×6, also achieves 90% coverage. Cost determines which solution should be generated. The cost622row of incidence matrix600shows the cost of each geometric model. The cost of a solution is the sum of costs of geometric models in the solution. The 1×1 costs 1, and the 6×6 costs 0.03, for a total solution cost of 1+0.03=1.03. The 2×2 costs 0.25, and the 6×6 costs 0.03, for a total solution cost of 0.25+0.03=0.28, which is cheaper than 1.03. Therefore the solution with 2×2 and 6×6 should be generated, and not the solution with 1×1 and 6×6. So long as a coverage percentage exceeds a threshold, such as 90% or 95%, a cheaper solution is preferable over a higher cost solution with higher coverage, such as 100%.

Cost is predictable. The marginal cost of adding higher multiples is very small. Once a geometric model is made at base square size, computing other geometric models is trivial. There is no need to iterate through the raw data set for each additional geometric model that is generated.

5.0 Hardware Overview

Computer system700further includes a read only memory (ROM)708or other static storage device coupled to bus702for storing static information and instructions for processor704. A storage device710, such as a magnetic disk, optical disk, or solid-state drive is provided and coupled to bus702for storing information and instructions.

As used herein, the terms “first,” “second,” “certain,” and “particular” are used as naming conventions to distinguish queries, plans, representations, steps, objects, devices, or other items from each other, so that these items may be referenced after they have been introduced. Unless otherwise specified herein, the use of these terms does not imply an ordering, timing, or any other characteristic of the referenced items.

6.0 Extensions and Alternatives