/* Last edited on 2013-03-24 23:53:02 by stolfilocal */ /* ---------------------------------------------------------------------- */ /* from FloatImage.magnify */ // static final int up_w[] = { +3, -12, +5, +40, +5, -12, +3 }; // static final int up_w[] = { -7, 5, 24, 5, -7 }; /* from FloatImage */ /* ---------------------------------------------------------------------- Compute the width (or height) of the image returned by {downsample} when given an image whose width (resp. height) is {size_old} and a specified {filter_size}. */ public static int downsampled_image_size(int size_old) { /* Currently, the width and height of the downsampled image will be half those of the original, rounded up by 1/2 pixel or 1 pixel (in the hope of preserving more information along the edges). Thus images with 0,1,2,3,4,5,6,7,8,9,50,51,52,53 columns will yield downsampled images with 1,1,2,2,3,3,4,4,5,5,26,26,27 columns, respectively. */ return FloatFilter.downsampled_signal_size(size_old, filter_size); } /* ---------------------------------------------------------------------- Compute the width (or height) of the signal returned by {downsample} with a specified {filter_size} when given an signal whose size along the downsampled acis is {size_old}. */ public static int downsampled_signal_size(int size_old,int filter_size) { /* The width and height of the downsampled signal will be half those of the original, rounded up by 1/2 sample or 1 sample (in the hope of preserving more information along the edges). Thus signals with 0,1,2,3,4,5,6,7,8,9,50,51,52,53 columns will yield downsampled signals with 1,1,2,2,3,3,4,4,5,5,26,26,27 columns, respectively. */ return size_old/2 + 1; } /* FloatImage: */ /* === BINARY MULTISCALE DECOMPOSITION ==================================== */ /* Weights for downsampling with each filter size: */ /* The weights in each row must add to exactly 1.0. */ /* !!! Not sure these are optimal !!! */ static final double dn_w[][] = { { }, { 1 / 2.0, 1 / 2.0 }, { 1 / 4.0, 2 / 4.0, 1 / 4.0 }, { 1 / 8.0, 3 / 8.0, 3 / 8.0, 1 / 8.0 }, { 1 / 16.0, 4 / 16.0, 6 / 16.0, 4 / 16.0, 1 / 16.0 }, { 1 / 32.0, 5 / 32.0, 10 / 32.0, 10 / 32.0, 5 / 32.0, 1 / 32.0 }, }; /* ---------------------------------------------------------------------- Reduces a given image {img_old} to about half size in both directions, using a rectangular downsampling filter (window weight table) with {filter_size} by {filter_size} taps. Each channel is downsampled independently. If {avg_old} and {avg_new} are null, the procedure assumes that {img_old} is an /intensity image/, where each sample is proportional to the weighted average of the light power or energy falling onto some area of the imaging sensor (without gamma encoding). Thus, the samples of the downsampled image {img_new} will be weighted averages of the samples in {img_old}. If {avg_old} and {avg_new} are non-null, the procedure assumes that {img_old} is a /variance image/, where each pixel is the weighted variance of light intensity in some area of the sensor. In that case, it expects {avg_old} to be the original intensity image corresponding to {img_old}, and {avg_new} to be the downsampled version of {avg_old}, obtained by {downsmaple} with the same filter order; and it will add to each sample of {img_new} the weighted variance of the samples of {avg_old} with respect to the sample of {avg_new}. The precise dimensions of the downsampled image are defined by the procedure {FloatSignalFilter.downsampled_signal_size}. In principle it will have one column (or row) for every two of the original; but it may be shaved or padded slightly along the edges, and these adjustments may depend on the parity of {filter_size}. */ public static FloatImage downsample (FloatImage img_old, int filter_size, FloatImage avg_old, FloatImage avg_new) { int nc = img_old.nc; int nx_old = img_old.nx; int ny_old = img_old.ny; /* Compute the size of the downsampled image: */ int nx_new = FloatSignalFilter.downsampled_signal_size(nx_old, filter_size); int ny_new = FloatSignalFilter.downsampled_signal_size(ny_old, filter_size); /* Decide if we are downsmapling a variance image instead of an intensity one: */ boolean is_var_image = (avg_old != null); assert(is_var_image == (avg_new != null)); if (is_var_image) { /* Validate dimensions of {avg_old,avg_new}: */ assert(avg_old.nc == nc); assert(avg_old.nx == nx_old); assert(avg_old.ny == ny_old); assert(avg_new.nc == nc); assert(avg_new.nx == nx_new); assert(avg_new.ny == ny_new); } FloatImage img_new = new FloatImage(nc, nx_new, ny_new); for (int c = 0; c < nc; c++) { for (int yn = 0; yn < ny_new; yn++) { /* Adjust the vertical filter order if needed near the top and bottom edges: */ int yorder = max_downsampling_filter_size(yn, filter_size, ny_old); /* If {ny_new} was properly chosen, every new row must overlap a symetric set of old rows: */ assert(yorder > 0); /* Get old row {yo_min} corresponding to filter tap 0 for new row {yn}: */ int yo_min = downsampling_tapped_pixel_index(yn, 0, yorder); double[] wy = dn_w[yorder]; /* Filter weights for Y. */ for (int xn = 0; xn < nx_new; xn++) { /* Adjust the horizontal filter order if needed near the left and right edges: */ int xorder = max_downsampling_filter_size(xn, filter_size, nx_old); /* If {nx_new} was properly chosen, every new column must overlap a symetric set of old columns: */ assert(xorder > 0); /* Get old column {xo_min} corresponding to filter tap 0 for new column {xn}: */ int xo_min = downsampling_tapped_pixel_index(xn, 0, xorder); double[] wx = dn_w[xorder]; /* Filter weights for X. */ /* Get the position {pn} of the sample {c,xn,yn} in {img_new}: */ int pn = nc*(yn*nx_new + xn) + c; /* If we are downsampling a variance image, get the mean intensity {a_new} in the window: */ double a_new = (is_var_image ? (double)avg_new.smp[pn] : 0.0); /* Accumulate the weighted sum of old samples around pixel {xn,yn}. */ double sumvw = 0.0; double sumw = 0.0; for (int ky = 0; ky < yorder; ky++) { int yo = yo_min + ky; assert((yo >= 0) && (yo = 0) && (xo < nx_old)); /* Compute the weight {w} from the window: */ double w = wy[ky]*wx[kx]; /* Get the matching sample value from {img_old}: */ int po = nc*(yo*nx_old + xo) + c; double v = img_old.smp[po]; /* If we are downsampling a variance image, add the mean-shift term: */ if (is_var_image) { double a_old = avg_old.smp[po]; v += (a_old - a_new)*(a_old - a_new); } /* Accumulate it: */ sumw += w; sumvw += v*w; } } assert(sumw == 1.0); /* Yes, exactly. */ /* Compute average and save in new image: */ float a_new = (float)(sumvw/sumw); img.smp[pn] = a_new; } } } return img_new; } /* Weights for upsampling: */ /* The weights in each row must add to exactly 1.0. */ /* !!! Not sure these are the right ones to use !!! */ static final double up_w[][] = { { 1 / 2.0, 1 / 2.0 }, { 1 / 4.0, 2 / 4.0, 1 / 4.0 }, { 1 / 8.0, 3 / 8.0, 3 / 8.0, 1 / 8.0 }, { 1 / 16.0, 4 / 16.0, 6 / 16.0, 4 / 16.0, 1 / 16.0 }, { 1 / 32.0, 5 / 32.0, 10 / 32.0, 10 / 32.0, 5 / 32.0, 1 / 32.0 }, }; /* ---------------------------------------------------------------------- Expands an image {img_old} to about double size, using an upsampling filter (window weight table) of {filter_size} by {filter_size} elements. Can be used to expand both intensity images (with linear scale) and variance images. Each channel is expanded independently. The width {nx_new} and height {ny_new} of the expanded image are specified by the client and must be compatible with {downsample}; namely, one must have {img_old.nx == FloatSignalFilter.downsampled_signal_size(nx_new, filter_size)}, and the same for {ny_new}. Thus there are only two possible values for each size, differing by 1 pixel. */ public static FloatImage upsample(FloatImage img_old, int nx_new, int ny_new, int filter_size) { int nc = img_old.nc; int nx_old = img_old.nx; int ny_old = img_old.ny; /* Validate the requested image size: */ assert(nx_new >= 0); assert(ny_new >= 0); assert(nx_old == FloatSignalFilter.downsampled_signal_size(nx_new, filter_size)); assert(ny_old == FloatSignalFilter.downsampled_signal_size(ny_new, filter_size)); /* Allocate the new image, assuming it is filled with zeros: */ FloatImage img_new = new FloatImage(nc, nx_new, ny_new); for (int c = 0; c < nc; c++) { for (int yn = 0; yn < ny_new; yn++) { /* Adjust the vertical filter order if needed near the top and bottom edges: */ int yorder = max_downsampling_filter_size(yn, filter_size, ny_old); /* If {ny_new} was properly chosen, every new row must overlap a symetric set of old rows: */ assert(yorder > 0); /* Get old row {yo_min} corresponding to filter tap 0 for new row {yn}: */ int yo_min = downsampling_tapped_pixel_index(yn, 0, yorder); double[] wy = up_w[yorder]; /* Filter weights for Y. */ for (int xn = 0; xn < nx_new; xn++) { /* Adjust the horizontal filter order if needed near the left and right edges: */ int xorder = max_downsampling_filter_size(xn, filter_size, nx_old); /* If {nx_new} was properly chosen, every new column must overlap a symetric set of old columns: */ assert(xorder > 0); /* Get old column {xo_min} corresponding to filter tap 0 for new column {xn}: */ int xo_min = downsampling_tapped_pixel_index(xn, 0, xorder); double[] wx = up_w[xorder]; /* Filter weights for X. */ /* Accumulate in window: */ double sumw = 0; double sumvw = 0; for (int ky = 0; ky < up_n; ky++) { /* Get old row {yo} (if any) corresponding to weight {up_w[ky]}: */ int yo2 = yn + ky - up_r; if ((yo2 % 2) == 0) { int yo = yo2/2; if ((yo >= 0) && (yo < ny_old)) { for (int kx = 0; kx < up_n; kx++) { /* Get old col {xo} (if any) corresponding to weight {up_w[kx]}: */ int xo2 = xn + kx - up_r; if ((xo2 % 2) == 0) { int xo = xo2/2; if ((xo >= 0) && (xo < nx_old)) { double w = (double)up_w[ky]*up_w[kx]; /* Get the matching old sample value: */ int po = nc*(yo*nx_old + xo) + c; double v = img_old.smp[po]; /* Accumulate: */ sumvw += v*w; sumw += w; } } } } } } float a_new = (float)(sumw == 0 ? 0.0 : sumvw/sumw); int pn = nc*(yn*nx_new + xn) + c; img_new.smp[pn] = a_new; } } } return img_new; } /* ---------------------------------------------------------------------- */ /* from FloatImageSegment.java */ /* ---------------------------------------------------------------------- Draws the ellipses of the segments in {seg} onto {img} cycling the colors of {rgb}. */ private void draw_segment_ellipses(FloatImageSegment[] seg, float[][] rgb, FloatImage img) { if (rgb != null) { assert(rgb.length > 0); } int iseq = 0; for (int i = 0; i < seg.length; i++) { FloatImageSegment segi = seg[i]; FloatImagePaint.paint_general_ellipse(img, segi.center, segi.axes, 1, color); iseq = iseq + 1; } } /* ---------------------------------------------------------------------- */ /* from WordCand.java */ /* ---------------------------------------------------------------------- Remove the last element from this word cand: */ public void drop_elem() { /* Expand the element list if needed: */ assert this.nel >= 2; this.nel--; } /* ---------------------------------------------------------------------- Append the element {L} to a clone of this word cand,recomputing its score. Assumes that {L.xmax} and {L.xmin} are strictly to the right of the last element in {W}: */ public void append_elem(WordCandElem L) { WordCand W1 = this.clone(this.nel + 1); /* Expand the element list if needed: */ int mel = this.els.length; if (this.nel == mel) { this.els = java.util.Arrays.copyOf(this.els, 2*mel + 1); } this.els[this.nel] = L; /* Save the old score and recompute the score: */ double sold = W.score; this.recompute_score(W); this.nel++; } /* ---------------------------------------------------------------------- */ /* from CharGrouper.java */ private static double midline_score(double m, double MLsmax) { double dev = MLsmax; double zd = m/dev; return Math.exp(-0.5*zd*zd); } private static double log_gaussian(double z, double dev) { double zd = z/dev; return - 0.5*Math.log(2*Math.PI) - Math.log(dev) - 0.5*zd*zd; } /* ---------------------------------------------------------------------- Recomputes the word cand's score, given the max absolute slope {MLsmax} of the word's midline, the range {[hmin _ hmax]} of valid body heights, the total image height htot, and the maximum gap between characters. */ private void recompute_score(WordCand W) { if (W.els.length == 1) { W.score = this.minScore; } else { /* Get topline and baseline: */ double[] BL = W.compute_ref_line(null, 0); double[] TL = W.compute_ref_line(null, 1); /* Compute an initial score {sslope} from the midline's slope: */ double MLslope = (TL[1] + BL[1])/2; double sslope = midline_score(MLslope, this.MLsmax); if (sslope == 0) { W.score = 0; return; } /* Check alignment of intermediate elements: */ /* Every intermediate element is required to fit the topline and baseline. */ /* Namely the topline must not be closer to double h0 = L0.ybas - L0.ytop; double h1 = L1.ybas - L1.ytop; double mh = (h1 - h0)/(x1 - x0); /* Slope of topline relative to baseline. */ double logPrF = 0; /* Log of prob density for the boxes, assuming non-word. */ double logPrT = 0; /* Log of prob density for the boxes, assuming word. */ /* Log of probability density for center {y} and body height {h} of a random element: */ double logPrFOne = - (Math.log(this.htot) + Math.log(this.hmax - this.hmin)); for (int iel = 1; iel < W.els.length-1; iel++) { WordCandElem Li = W.els[iel]; /* Get letter's center ordinate {yi} and body height {hi}: */ double yi = (Li.ybas + Li.ytop)/2; double hi = Li.ybas - Li.ytop; /* Compute expected center ordinate {ye} and expected body height {he}: */ double ye = y0 + my*(Li.xctr - x0); double he = h0 + mh*(Li.xctr - x0); /* If false, assume uniform probability for {yi} in {[0_htot]}, for {hi} in {[hmin_hmax]}: */ logPrF += logPrFOne; /* If true, assume Gaussian probability for {yi} around {ye}, for {hi} around {he}: */ logPrT += log_gaussian(yi - ye, this.ysigma) + log_gaussian(hi - he, this.hsigma); } /* Scale probabilities to minimize risk of overflow */ double logPrM = Math.max(logPrF, logPrT); logPrF -= logPrM; logPrT -= logPrM; /* Compute probability of cand being true by Bayes: */ double prT = this.probTrue*Math.exp(logPrT); double prF = (1 - this.probTrue)*Math.exp(logPrF); W.score = smy*prT/(prT + prF); } } // Each word candidate has an /estimated baseline/ {W.BL}, a mean // straight line of the base points of its elements; and an /estimated // topline/ {W.TL}, a mean straight line of their top points. The // score {W.score} of the word candidate depends on the number of // elements in {W}, on the spacing bewtween successive elements, and on // the alignment of the base points and top points of those elements with the // lines {W.BL} and {W.TL}. // For each box {B} that is processed, the module keeps track of the // maximum score {smax} among all open candidates to which {B} has been // added. In particular, if {B} was not added to any existing ord // candidate, then {smax} is zero. If {smax} is less than a second // threshold {ssmin}, then the module creates four new open word // candidates containing just the box {B} with the four possible values // of {.ytop} and {.ybas}. /* ---------------------------------------------------------------------- Compute {Pr(T|X)} given {log(Pr(X&T))} and {log(Pr(X&F))}, where {T} and {F} are two mutually exclusive and exhaustive events, by Bayes formula. */ private static double bayes(double logPrT, double logPrF) { /* Scale probabilities to minimize risk of overflow */ double logPrM = Math.max(logPrF, logPrT); logPrF -= logPrM; logPrT -= logPrM; /* Compute probability of cand being true by Bayes: */ double prT = Math.exp(logPrT); double prF = Math.exp(logPrF); return prT/(prT + prF); } /* ---------------------------------------------------------------------- Append the element {L} to a clone of the word cand {W}, provided the result has score {semin} or more, and returns that score. Otherwise returns {null}. Assumes that {box_seems_appendable(W, L.box)} is true. */ public WordCand try_to_append_elem(WordCand W, WordCandElem L) { /* Quick check: */ if (! this.element_seems_appendable(W, L)) { return null; } else { /* Try to append {L}: */ WordCand W1 = this.append_element(W, L); if (W1.score >= this.semin) { return W1; } else { if (debug) { dbgD(6,"!semin", W1.score); } return null; } } } /* */