% This file is part of the Stanford GraphBase (c) Stanford University 1992 \def\title{GB\_\thinspace MONA} @i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES! \prerequisites{GB\_\thinspace GRAPH}{GB\_\thinspace IO} @* Introduction. This GraphBase module contains the |mona| subroutine, which creates rectangular matrices of data based on Leonardo da Vinci's {\sl Gioconda\/} (aka Mona Lisa). It also contains the |plane_mona| subroutine, which constructs undirected planar graphs based on |mona|, and the |bi_mona| subroutine, which constructs undirected bipartite graphs. Another example of the use of |mona| can be found in the demo program |assign_mona|. @(gb_mona.h@>= extern long* mona(); extern Graph *plane_mona(); extern Graph *bi_mona(); @ The subroutine call `|mona(m,n,d,m0,m1,n0,n1,d0,d1,area)|' constructs an $m\times n$ matrix of integers in the range $[0\,.\,.\,d\mskip1mu]$, based on the information in \.{mona.dat}. Storage space for the matrix is allocated in the memory area called |area|, using the normal GraphBase conventions explained in |gb_graph|. The entries of the matrix can be regarded as pixel data, with 0~representing black and $d$~representing white, and with intermediate values representing shades of gray. The data in \.{mona.dat} has 360 rows and 250 columns; the rows are numbered 0 to 359 from top to bottom, and the columns are numbered 0 to 249 from left to right. The output of |mona| is generated from a rectangular section of the picture consisting of |m1-m0| rows and |n1-n0| columns; more precisely, |mona| uses the data in positions $(k,l)$ for |m0<=k=d1|, and to $\lfloor d(D-|d0|)/(|d1|-|d0|)\rfloor$ if |d0<=D360|, |m1|~is changed to 360; if |n1=0| or |n1>250|, |n1|~is changed to~250; then if |m| is zero, it is changed to~|m1-m0|; if |n| is zero, it is changed to~|n1-n0|. If |d| is zero, it is changed to~255; if |d1| is zero, it is changed to |255(m1-m0)(n1-n0)|. After these substitutions have been made, the parameters must satisfy \hbox{|m0(n1-n0)/n|, it will be compressed in the vertical dimension. If you want to reduce the original image to binary data, with the value~0 wherever the original pixels are less than some threshold value~|t| and the value~1 whenever they are |t| or more, call |mona(m,n,1,m0,m1,n0,n1,@t}\penalty0{@>0,t*(m1-m0)*(n1-n0),area)|. The subroutine call |mona(1000,1000,255,0,250,0,250,0,0,area)| produces a million pixels from the upper part of the original image. This matrix contains more entries than the original data in \.{mona.dat}, but of course it is not any more accurate; it has simply been obtained by linear interpolation. Mona Lisa's famous smile appears in the $16\times32$ subarray defined by |m0=104|, |m1=120|, |n0=101|, |n1=133|. A string |mona_id| is constructed, showing the actual parameter values used by |mona| after defaults have been supplied. @= #define smile @t\quad@> m0=104,m1=120,n0=101,n1=133 extern char mona_id[]; @ @= char mona_id[]="mona(360,250,9999999999,359,360,249,250,9999999999,9999999999)"; @ If the |mona| routine encounters a problem, it returns |NULL| (\.{NULL}), after putting a nonzero number into the external variable |panic_code|. This code number identifies the type of failure. Otherwise |mona| returns a pointer to the newly created array. (The external variable |@!panic_code| is defined in |gb_graph|.) @d panic(c) @+{@+panic_code=c;@+gb_alloc_trouble=0;@+return NULL;@+} @f Graph int /* |gb_graph| defines the |Graph| type and a few others */ @f Vertex int @f Arc int @f Area int @ The \Cee\ file \.{gb\_mona.c} begins as follows. (Other subroutines come later.) @p #include "gb_io.h" /* we will use the |gb_io| routines for input */ #include "gb_graph.h" /* we will use the |gb_graph| data structures */ @# @@; @@; @@; @# long *mona(m,n,d,m0,m1,n0,n1,d0,d1,area) unsigned m,n; /* number of rows and columns desired */ unsigned long d; /* maximum pixel value desired */ unsigned m0,m1; /* input will be from rows $[|m0|\,.\,.\,|m1|)$ */ unsigned n0,n1; /* and from columns $[|n0|\,.\,.\,|n1|)$ */ unsigned long d0,d1; /* lower and upper threshold of raw pixel scores */ Area area; /* where to allocate the matrix that will be output */ {@+@@; @; @; @; return matx; } @ @= long *matx=NULL; /* the matrix constructed by |mona| */ register int k,l; /* the current row and column of output */ register int i,j; /* all-purpose indices */ int cap_M,cap_N; /* |m1-m0| and |n1-n0|, dimensions of the input */ int cap_D; /* |d1-d0|, scale factor */ @ @= if (m1==0 || m1>MAX_M) m1=MAX_M; if (m1<=m0) panic(bad_specs+1); /* |m0| must be less than |m1| */ if (n1==0 || n1>MAX_N) n1=MAX_N; if (n1<=n0) panic(bad_specs+2); /* |n0| must be less than |n1| */ cap_M=m1-m0;@+cap_N=n1-n0; if (m==0) m=cap_M; if (n==0) n=cap_N; if (d==0) d=MAX_D; if (d1==0) d1=MAX_D*cap_M*cap_N; if (d1<=d0) panic(bad_specs+3); /* |d0| must be less than |d1| */ if (d1>=0x80000000) panic(bad_specs+4); /* |d1| must be less than $2^{31}$ */ cap_D=d1-d0; sprintf(mona_id,"mona(%u,%u,%lu,%u,%u,%u,%u,%lu,%lu)",m,n,d,m0,m1,n0,n1,d0,d1); @ @= matx=gb_alloc_type(m*n,@[long@],area); if (gb_alloc_trouble) panic(no_room+1); /* no room for the output data */ @ @= @; @; @; @* Elementary image processing. As mentioned in the introduction, we can envisage the input as a giant $mM\times nN$ matrix, into which an $M\times N$ image is placed by replication of pixel values, and from which an $m\times n$ image is derived by summation of pixel values and subsequent scaling. Here |M=m1-m0| and |N=n1-n0|. Let $(\kappa,\lambda)$ be a position in the giant matrix, where $0\le\kappa= int *cur_pix; /* current position within |in_row| */ int lambda; /* right boundary in giant for the input pixel in |cur_pix| */ int lam; /* the first giant column not yet used in the current row */ int next_lam; /* right boundary in giant for the output pixel in column~|l| */ @ @= lambda=n;@+cur_pix=in_row+n0; for (l=lam=0; l=lambda) cur_pix++,lambda+=n; if (lambda= kappa=0; out_row=matx; for (k=kap=0; k=kappa) { @; kappa+=m; } if (kappa; kap=nk; }@+while (kap; } @ @= int kappa; /* bottom boundary in giant for the input pixels in |in_row| */ int kap; /* the first giant row not yet used */ int next_kap; /* bottom boundary in giant for the output pixel in row~|k| */ int f; /* factor by which current input sums should be replicated */ int *out_row; /* current position in |matx| */ @* Integer scaling. Here's a general-purpose routine to compute$\lfloor na/b\rfloor$exactly without risking integer overflow, given integers$n\ge0$and$0= static int na_over_b(n,a,b) int n,a,b; {@+int nmax=el_gordo/a; /* the largest $n$ such that $na$ doesn't overflow */ register int r,k,q,br; int a_thresh, b_thresh; if (n<=nmax) return (n*a)/b; a_thresh=b-a; b_thresh=(b+1)>>1; /* $\lceil b/2\rceil$ */ k=0; do {@+bit[k]=n&1; /* save the least significant bit of $n$ */ n>>=1; /* and shift it out */ k++; }@+while (n>nmax); r=n*a;@+ q=r/b;@+ r=r-q*b; @; return q; } @ @= static int bit[30]; /* bits shifted out of |n| */ @ @= do {@+k--;@+ q<<=1; if (r= if (*out_row<=d0) *out_row=0; else if (*out_row>=d1) *out_row=d; else *out_row=na_over_b(d,*out_row-d0,cap_D); @* Input data format. The file \.{mona.dat} contains 360 rows of pixel data. Each row appears on 10 consecutive lines of the file; each line contains the data for 25 pixels; each pixel is represented by two hexadecimal digits. The tenth and final line of each row is followed by a period. @= if (gb_open("mona.dat")!=0) panic(early_data_fault); /* couldn't open the file; |io_errors| tells why */ for (i=0;i= for (i=m1;i= for (j=0,cur_pix=&in_row[0];;j++,cur_pix++) {@+register int dd; dd=gb_digit(16); *cur_pix=16*dd+gb_digit(16); if (j%25==24) { if (j= static int in_row[MAX_N]; @* Planar graphs. We can obtain a large family of planar graphs based on digitizations of Mona Lisa by the following simple scheme: Each matrix of pixels defines a set of connected regions containing pixels of the same value. (Two pixels are considered adjacent if they share an edge.) These connected regions are taken to be vertices of an undirected graph; two vertices are adjacent if the corresponding regions have at least one pixel edge in common. We can also state the construction another way. If we take any planar graph and collapse two adjacent vertices, we obtain another planar graph. Suppose we start with the planar graph having $mn$ vertices $[k,l]$ for $0\le k0$ and to $[k-1,l]$ when $k>0$. Then we can attach pixel values to each vertex, after which we can repeatedly collapse adjacent vertices whose pixel values are equal. The resulting planar graph is the same as the graph of connected regions that was described in the previous paragraph. The subroutine call |plane_mona(m,n,d,m0,m1,n0,n1,d0,d1)| constructs the planar graph associated with the digitization produced by |mona|. The description of |mona|, given earlier, explains the significance of parameters |m|, |n|, |d|, |m0|, |m1|, |n0|, |n1|, |d0|, and |d1|. There will be at most $mn$ vertices, and the graph will be simply an $m\times n$ grid unless |d| is small enough to permit adjacent pixels to have equal values. The graph will also become rather trivial if |d| is too small. Utility fields |first_pixel| and |last_pixel| give, for each vertex, numbers of the form $k*n+l$, identifying the topmost/leftmost and bottommost/rightmost positions $[k,l]$ in the region corresponding to that vertex. Utility fields |internal_rows| and |internal_cols| in the |Graph| record contain the values of |m| and~|n|; thus, in particular, the value of |n| needed to decompose |first_pixel| and |last_pixel| into individual coordinates can be found in |g->internal_cols|. The original pixel value of a vertex is placed into its |pixel_value| utility field. @d pixel_value x.i @d first_pixel y.i @d last_pixel z.i @d internal_rows u.i @d internal_cols v.i @p Graph *plane_mona(m,n,d,m0,m1,n0,n1,d0,d1) unsigned m,n; /* number of rows and columns desired */ unsigned long d; /* maximum value desired */ unsigned m0,m1; /* input will be from rows $[|m0|\,.\,.\,|m1|)$ */ unsigned n0,n1; /* and from columns $[|n0|\,.\,.\,|n1|)$ */ unsigned long d0,d1; /* lower and upper threshold of raw pixel scores */ {@+@@; init_area(working_storage); @