Representation of Designs

This invention relates to the representation of designs, and, more particularly, to the representation of designs using pattern members, such as pattern blocks.

Many designs appear at normal viewing distances to be continuous renditions of color or shades of color. In fact, at every point, when the design is examined closely, it is formed by discreet elements of color, typically black or white or some combination of spectral components in the case of color photographs.

The half-tone process used for reproducing photographs in newspapers makes use of a fine black-white checkerboard to represent mid-range gray. Different sizes of white spots on a black background or black spots on a white background are used for other shades of gray.

Representations of continuous designs may be made in other ways as well. Thus, small patterns or symbols originally designed for other purposes can be used to produce a photographic effect, if the patterns or symbols are relatively small in comparison with the overall size of the picture and if they permit selection of the desired brightness level in the space occupied by the pattern or symbol.

Accordingly, pictures can be produced by ordinary typewriter characters so that even when the individual type characters are quite unrelated to an overall scene they can be combined to produce a meaningful macroscopic pictorial representation. This is because the eye of the viewer does not see the microstructure from a distance but instead perceives intermediate shades of coloration according to the ratio of coloration presented by the microstructural elements.

A detailed explanation of the use of structural elements to represent pictorial scenes is presented in "Computer Produced Grey Scales" by Ken Knowlton and Leon Harmon in Computer Graphics and Image Processing, Volume 1, No. 1, April 1972, pages 1 through 20.

While a wide variety of symbolic elements are available for use in representing designs, certain elements create special problems. Thus a die has only a limited number of representations. In particular a die has six sides with from one to six spots of one color on a background of a different color. Thus the use of a die as a pattern member can pose difficulties since the number of different picture elements is strictly limited. A similar limitation is presented by the domino. The sets available are called double-sixes, double-nines or double-twelves. The double-six includes all combinations from blank-blank to six-six. This is because each individual domino is made up of two areas, side by side, each of which may be blank or contain a number of spots. In the case of a six-six, each area contains six spots. Similarly the double-nine set contains all combinations up to nine-nine and the double-twelve set contains all combinations up to twelve-twelve. The dominoes pose special problems as picture elements since each includes two areas which are side by side. It is not enough to satisfy the constraints of one of the areas. If each domino is to be used as an integral member two pattern areas are used for each member placement.

Accordingly, it is an object of the invention to facilitate the representation of designs using patterned blocks. A related object is to facilitate the representation of designs using pattern members in the form of blocks which include marks of one color on a background of another color.

It is another object of the invention to achieve picture quality representation of designs using spotted pattern blocks. A related object is to use spotted pattern blocks in the form of dice and dominoes.

It is a further object of the invention to represent designs using pattern blocks containing multiple patterns, such as dominoes. A related object is to represent designs using game pieces which can be used in conventional gaming fashion once they have served their design purpose.

Still another object of the invention is to achieve the representation of designs using complete sets of pattern blocks. A related object is to represent designs using complete sets of dominoes, such as a specified plurality of a double-six, double-nine or a double-twelve set.

In accomplishing the foregoing and related objects, the invention provides a method of representing a design by pattern members, such as sets of dominoes, by subdividing the design into a plurality of subordinate areas; assigning a value to each subordinate area in accordance with the prescribed characteristic; coordinating the assigned values with the values of the pattern members; and substituting the coordinated pattern members into the sub-areas. The result is a pattern representation, for example by a plurality of complete sets of dominoes, of a prescribed design.

In accordance with one aspect of the invention the prescribed characteristic in accordance with which a value is assigned to each subordinate area, is brightness. In general terms brightness refers to the spectral intensity of the area. In specific terms it refers to the amount and nature of light absorbed or reflected by an area. In black and white terms brightness is at a maximum for an area which is white and is at a minimum for an area which is black. Brightness is at an intermediate level for the graduations of gray which exist between black and white.

In accordance with another aspect of the invention the brightness level of a sub-area represents the composite value of the brightness characteristics associated with the various parts of the sub-area. Thus, an area which contains black and white sub-elements will nevertheless have an intermediate gray level to which an assigned value can be given. Similar considerations apply to other monochromatic colors, and polychromatic representations can be treated on the basic of appropriate combinations of their monochromatic constituents.

In accordance with another aspect of the invention, the number of brighness levels assigned to the various subordinate areas of the design exceeds the number of values of pattern members. Thus, in the case of dominoes which have areas with ten brightness levels, ranging from black for a blank area to a value of ten for an area with nine spots (a blank having a value of one) the number of original levels may exceed ten. In one embodiment, it is convenient to use thirty-six brightness levels but in general the brightness levels could be about ten-fold the maximum value of any pattern member so that a preferred embodiment could make use of possibly 100 brightness levels in the cae of a double-nine set of dominoes. Similar considerations apply to other sets of dominoes, as well as to other forms of pattern members.

In accordance with another aspect of the invention, the values assigned to the subordinate areas are evaluated to produce a suitable fit with the pattern members. One technique for accomplishing the evaluation is to consider the subordinate areas in pairs. If two horizontal pairs are initially chosen the same areas are also considered as vertical pairs. The evaluation is made in terms of optimizing a characteristic such as "pair unbalance". One measure of unbalance is given by the absolute value of the difference in brightness levels of adjoining sub-areas. If the sum of unbalances for horizontally adjoining areas is not as great for a specified subordinate area as that for vertically constituted subordinate areas, the latter is chosen. The subordinate areas that are evaluated can be any multiple of pair areas. In one embodiment of the invention, two- and three-pair areas are taken as the evaluated subordinate area with two of the pair areas extending in one direction, i.e. horizontal or vertical, and the (optional) third area extending in the other direction.

In accordance with a further aspect of the invention, the coordinated pattern members are substituted for the subordinate areas by assigning all of an a priori given collection of pattern members such as an integral number of complete sets of dominoes.

Other aspects of the invention will become apparent after considering several illustrative embodiments taken in conjunction with the drawings in which:

FIG. 1A is a quantized representation of a photograph which is to be represented by three complete sets of double-nine dominoes;

FIG. 1B is an enlarged view of the upper left hand corner of FIG. 1A;

FIG. 2 is a plot of picture cell pairs on a triangular representation of domino kinds;

FIG. 3A is a plot showing the assignment of dominoes by considering sets in order of decreasing average, as well as the order of considering sets and the kinds in each set;

FIG. 3B is a plot showing the assignment of dominoes by considering sets in order of decreasing unbalance, as well as the order of considering sets and the kinds in each set;

FIG. 3C is a plot showing the assignment of dominoes by a preferred hybrid system, including order of sets and the members of each;

FIG. 4A is a representation of FIG. 1A with substitute values of pattern members in accordance with FIGS 3A through 3C;

FIG. 4B is an enlarged view of the upper left hand corner of FIG. 5A; FIG. 5A is the resultant representation of a photograph using three sets of double-nine domino pattern members in accordance with FIG. 4A; and

FIG. 5B is the resultant representation of a photograph using twenty-four sets of double-nine dominoes.

With reference to the drawings, FIG. 1A shows, in part, the result of representing a photograph P by three hundred and thirty picture elements or cells, each in the form of a square, in a grid that is fifteen elements wide and twenty-two elements high. It will be appreciated that the picture P in FIG. 1A is completely fanciful, and that in ordinary practice the picture P has a prescribed pattern.

The cells are, illustratively, to be organized so that the photograph can be represented by dominoes. Since each domino consists of two cells with zero to nine dots in each cell, the values used in the cells have been adjusted to range between -0.5 and +9.5. The intent is that the ideal representation will be the nearest integer in number of dots: 0, 1, 2 . . . 8,9.

With the value of each picture element or cell selected on a scale from -0.5 to +9.5, -0.5 indicates total darkness and +9.5 indicates white. The intermediate values represent an average of the lightness and darkness. Thus, a level of 4.5 at the middle of the range represents a gray scale where the darkness is balanced by the lightness to produce an intermediate gray visual effect.

The cell values are further arranged by "histogram leveling", a wellknown general procedure for the redistribution of data, to have a relatively uniform distribution throughout the range from -0.5 to +9.5. A histogram is defined graphically as a representation of a frequency distribution by rectangles whose widths represent class intervals and whose heights represent corresponding frequencies. When the brightness is measured to the nearest hundredth, this range provides 1,000 levels. It will be understood that 100 levels are also adequate and that the corresponding range is from -0.5 to +9.5.

The representation is to be made using dominoes. Since each domino has two areas, the picture elements of FIG. 1A are grouped in pairs.

The initial representation, i.e. "tiling" of pairs is with a left-edge strip of vertical pairs. The term "tiling" refers to the fact that the domino pairs are arranged in a pattern much in the way that tiles are arranged. The remaining pairs in the tiling are in alternate horizontal and vertical groups. Thus, the second and third elements in the first two rows constitute a horizontal pair, along with the remaining pairs in the first two rows. Similarly, elements 2 and 3 in the next pair of rows constitute a vertical pair, along with the remaining elements in those rows. In the fifth and sixth rows, the first rows are duplicated, etc.

The upper left hand corner of FIG. 1A has been enlarged and reproduced in FIG. 1B. The vertical cell pair is shown with picture values of 5.06 and 6.72. The value 5.06 corresponds to slightly lighter than mid-level of 4.50. The value 6.72 is approximately midway betwen 4.50 and 9.50.

The representation is to be made using three complete sets of double-nine dominoes. Each double-nine set contains fifty-five dominoes since it ranges from double blank through the double nine or is, in effect one half of a matrix with ten columns and ten rows so that the total number is (10.div.2).times.(1+10) or 55.

Accordingly the total number of dominoes in three sets is 165. Since each domino has two areas the total number of picture elements in three sets of dominoes is 330 or the same number shown in FIG. 1A.

The 330 values for FIG. 1A are set forth in Table I as follows:

The number, size and arrangement of cells are such that two adjacent cells are to be covered by one domino (itself consisting of two cells of the same size, each having from zero to nine dots on its face). The range is from -0.5 to +9.5.

The complete set of pairings is called a "tiling". Tiling is effected throughout the picture shown that every cell is paired with one and only one adjacent cell. Each such pair of cells may be covered with one domino. Disregarding the brightness values of the picture cells and the number of spots on the domino cells, such tiling represents one geometric way of covering the picture area with dominoes.

In addition, each pair of picture cells may be represented by a point somewhere in the triangular region of FIG. 2. The construction coordinates of each cell in FIG. 2 are the two picture cell values. If the values are equal, the point will be on the 45.degree. diagonal. When, for example, the picture contains fifteen by twenty-two cells, there are exactly 165 such cell pairs. These are schematically represented by the 165 small dots in the triangle of FIG. 2.

Each pair of cells can be characterized by the "average" value of the two cells and by the "unbalance" of the pair. The latter refers to the highest minus the lowest value. These measurements are an additional or alternative set of coordinates for the plot of distribution of cell pairs as indicated in FIG. 2.

The invention provides a systematic way of assigning a given collection of dominoes with one domino to each picture cell pair, so as to represent light values of the original picture by domino dots on whole dominoes, i.e., pairs of areas. Since the dots on ordinary domino cells are of equal size, the larger the number of dots in a cell, the brighter the picture cell that such a domino cell would ideally represent.

Dominoes, for example, of a "double-nine" set, come in a discrete number of kinds, e.g. 0-0, 1-5, 6-9, etc., where the numbers for each kind stand for the number of dots in the two domino cells. As with pairs of picture cells, each kind of domino, for example 5-7, may be characterized by a high cell (e.g. 7), a low cell (e.g. 5), an average value (e.g. 6) and an unbalance (e.g. 2). Each kind of domino may thus be plotted as a position in the diagram of FIG. 2. There are exactly 55 kinds of dominoes in a double-nine set; they have been plotted as large dots.

The goal is to assign dominoes to cell pairs in such a way that each cell of each domino closely matches the value of the picture cell which it is to represent. In general there will be a mismatch for each identification of domino cell with picture cell. This may be taken to be, in value, the absolute value of the difference between the picture cell and the corresponding domino cell values. For each total representation of a picture by dominoes, it is possible to consider an overall badness of fit, which could, by way of example, be taken numerically to be the maximum mismatch, or the average mismatch, or the square root of the average of the squares of mismatches, etc.

With each collection of dominoes and a particular tiling of a particular picture, i.e, a complete set of pairings of picture cells, the objective is to make a good assignment of dominoes to picture cell pairs.

In general a fortuitous distribution of picture cell pairs will not be apparent. In particular, a typical picture, subjected to a "typical" paring of cells, will yield a plot very much like that exemplified in FIG. 2. There will be a high density of pairs near the 45.degree. diagonal, illustrative of the tendency of neighboring cells to have nearby brightness values.

The invention deals with this problem in two steps:

1. By a systematic procedure to achieve first a more nearly optimal distribution of cell pairs over the triangular area of FIG. 2; and

2. By subdividing the distribution thus achieved into regions, one for each domino type, in a way which tends to minimize the "badness" of fit as previously discussed.

The foregoing two procedures are described as occuring in sequence but it will be apparent that they can overlap in ways that may be described as "interactive", "backtracking", "trial and error", "heuristic", etc. It will be readily understood that the process can be aided by a diagram in the form exemplified in FIG. 2, upon which a judgment can be made as to the effectiveness of the first step, including the unlikely possibility of over-maximizing the average picture cell pair unbalance.

The objective of the first step, for most pictures, is to maximize the average unbalance of picture cell pairs. This is done by starting in some overall cell pairing, such as that exhibited in FIG. 1A, and by modifying the pairings in subareas so as to increase either the maximum unbalance or the average unbalance of the sub-area.

One possibility is alternative pairings. As suggested by FIGS. 4A and 4B, each 2.times.2 picture cell area could alternatively be designated as two horizontal pairs (rows 1 and 2, columns 2 and 3) or two vertical pairs (rows 1 and 2, columns 4 and 5). It can in general be asserted that for each vertically adjacent pair of horizontal pairs, the alternative pairing should be asserted if it increases the maximum (or the average) unbalance of the subarea.

Similarly, for a 2-high by 3-wide sub-area of picture cells, such as that exhibited in FIG. 1B, there is one alternative set of pairings consisting of a vertical pair on the right and two horizontal pairs on the left (there is still another alternative pairing consisting of three side-by-side vertical pairings).

Thus, one way of seeking an overall optimal set of pairings is to start with some overall set of pairings and search through the picture systematically, attempting to replace local patterns of pairings such as those illustrated above, with other local patterns covering, in each case the same sub-areas but with an increased average unbalance.

An example is given in TABLE II, below, for eight columns and six rows. It will be appreciated that TABLE II represents only the upper left-hand portion of TABLE I.

Consider the alternative vertical tiling for this subarea and compute its sum of the absolute difference (.SIGMA.d). If the new sum is greater, replace the former tiling by the new one.

Then consider the converse change, i.e. from vertical to horizontal. If this change increases the total difference, it should be adopted. This procedure is summarized in Chart I below: (from columns 2 and 3 of rows 1 and 2)

where the sequence is followed only when it optimizes the slope. Here form (a), unexceeded by (b), is retained.

Likewise, find and consider the sub-areas two cells wide by three cells high as shown in CHART II, (columns 2 and 3, rows 2,3 and 4) and leave each subarea or replace it by its alternate, whichever has the greatest sum of differences.

Where the double headed arrow indicates selection of the form with the greatest difference. Here form (a) is maximum, since 0.06+0.83+2.23=3.12 for (b) is less than 0.00+1.05+4.17=5.22 for (a).

Similarly find and consider the sub-areas two cells high by three cells wide as shown in Chart III (columns 1,2 and 3, rows 1 and 2) and leave each sub-area or replace it by its alternate, whichever has the greatest difference.

Here (a) is maximum since 1.66+0.28+0=1.94 for (a) is greater than 0.83+0.55+0=1.38 for (b).

An alternative way is to consider potential pairs (a potential pair of cells is considered to be a pair of two adjacent cells not currently paired). All potential pairs of cells can be listed in order of unbalance, starting with the greatest unbalance. An attempt is then made to find some local re-pairing which realizes the first potential pairing and furthermore increases the average unbalance of the sub-area. If this is possible, the new pairings are established and the list of potential pairs is updated by appropriate addition and removal of entries, and the process is repeated. If the first potential pair cannot be realized by a reasonable amount of effort, then the second potential pair on the list is attempted. The process is continued until no potential pairing on the list can be achieved, considering neighborhoods up to the size and complexity that can be dealt with conveniently, by re-pairing of a local neighborhood in a way that increases average unbalance. The process is guaranteed to terminate because increasing the average unbalance of a sub-area increases the average for the whole picture, whereas there must exist some absolute maximum possible average unbalance for a particular picture.

Once a near optimal distribution of pairing has been established, the second step of the procedure is invoked. This consists of groupings of pairings of picture cells for domino assignments. This can most conveniently be described by considering in sequence various sets of domino kinds which share some common property and which have not been used previously in the process. For example, the dominoes (7-8, 6-9) would be members of a set with an average of 7.5, whereas (5-6, 6-7, 7-8, 8-9) would be in a set with an unbalance of 1. If the 8-9 dominoes have been "used previously" as members of some other set, then the actual "unbalance of 1" set of interest would no longer contain 8-9's.

Assignment by considering successive sets of domino kinds is demonstrated in FIG. 3A. Consider first the set (9-9) to be assigned to a 22.times.15 cell picture; there are exactly three 9-9 dominoes in this set. This is the set with the highest average (9.0) and the correct assignment is to the three picture cell pairs having the highest average. The next set of kinds (8-9) is similarly assigned to the next three highest-average picture cell pairs, taking care to orient each domino so as to associate the 9-end with the brightest picture cell. The third set is (7-9, 8-8). These six dominoes are assigned to the next six highest-average picture cell pairs, with the qualification that the three of these with the greatest unbalance are assigned the 7-9's, whereas the three with the least unbalance are assigned the 8-8's. Successive sets of dominoes are thus chosen as indicated by the groupings of FIG. 3A, until finally the three remaining cell pairs (those with least average) are assigned the set with average 0, and the overall assignment is complete. The entire procedure can be carried out in reverse order, starting with the 0-0's and ending with the 9-9's, producing an identical result.

The procedure of FIG. 3A may be summarized as follows:

1. Determine the number of dominoes in the set with the highest (later the next highest, etc.) average.

2. Next determine the number of kinds of dominoes in the set.

3. Identify this number of picture cell pairs--those (which remain uncovered by dominoes) with the highest averages.

4. Divide the identified picture cell pairs into groups of highest unbalance, next highest, etc.

5. Assign the dominoes with the greatest unbalance to picture cells with greatest unbalance, etc.

The set members are summarized in TABLE III below:

Alternatively, but similarly, one could proceed as indicated in FIG. 3B by considering first the set with the greatest unbalance (9), then the next largest (8), etc. By way of example, suppose that the 0-9 set, then the (0-8, 1-9) set have been assigned, and the next step is to assign the (0-7, 1-8, 2-9) set, i.e., the set with unbalance equal to 7. This requires finding the nine unassigned picture cell pairs with greatest unbalance; these will be divided into subsets of three with lowest average, three with intermediate average and three with highest average. To these three sets of three each will be assigned the 0-7, the 1-8 and the 2-9 dominoes respectively. The process is continued in accordance with FIG. 3B until all dominoes have been assigned.

It will be readily understood that the "outlying" dominoes are used systematically from one corner or side of the array of unused dominoes, so as to avoid ending with an unused, isolated set or group remote from the unused picture cell pairs. Here the implied measure of distance is understood in terms of the diagram of FIG. 2. Another, and preferred, procedure is that of FIG. 3C, which proceeds over the regions of domino space from the corners. Still other possible orders of using dominoes for assignment will be evident from the foregoing examples.

Dominoes in accordance with the groupings indicated above are next used to realize the desired design. The result is shown partially in FIG. 4A, with the upper left corner enlarged in FIG. 4B.

The 330 values for FIG. 4A are set forth in TABLE IV below:

The complete mapping is shown in FIG. 5A. The same original picture could alternatively be represented by 2,640 picture elements and ultimately represented by 1,320 dominoes (24 complete double-nine sets) as shown in FIG. 5B.

When the value of each picture element is originally selected on a scale of from 0 to 36, with 0 indicating total darkness, 36 indicating white, the 330 values of FIG. 1A become as set forth in TABLE V below.

It again is possible to coordinate paired elements of TABLE V with the dominoes directly, but it is preferable to enhance the coordination before doing so.

It should be clear that generalization of the above procedure pertains to different sizes of pictures, different numbers of sets of dominoes, and different kinds of domino sets, e.g. double six and double 12.

Other familiar objects may be used to represent picture cells, for example dice which have different numbers of spots on their facets.

While various aspects of the invention have been set forth by the drawings and specification, it is to be understood that the foregoing detailed description is for illustration only and that various changes in parts, as well as the substitution of equilvalent constituents for those shown and described may be made without departing from the spirit and scope of the invention as set forth in the appended claims.