Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
imgscale.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: imgscale.cpp (Formerly dyn_prog.c)
3  * Description: Dynamic programming for smart scaling of images.
4  * Author: Phil Cheatle
5  * Created: Wed Nov 18 16:12:03 GMT 1992
6  *
7  * (C) Copyright 1992, Hewlett-Packard Ltd.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  *
18  **********************************************************************/
19 
20 /*************************************************************************
21  * This is really Sheelagh's code that I've hacked into a more usable form.
22  * It is used by scaleim.c All I did to it was to change "factor" from int to
23  * float.
24  *************************************************************************/
25 /************************************************************************
26  * This version uses the result of the previous row to influence the
27  * current row's calculation.
28  ************************************************************************/
29 
30 #ifdef _MSC_VER
31 #pragma warning(disable:4244) // Conversion warnings
32 #endif
33 
34 #include "mfcpch.h"
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include "errcode.h"
38 
39 #define f(xc, yc) ((xc - factor*yc)*(xc - factor*yc))
40 
41 #define g(oldyc, yc, oldxc, xc) (factor*factor*(oldyc - yc)*(oldyc - yc)/(abs(oldxc - xc) + 1))
42 
43 void
44 dyn_exit (const char s[]) {
45  fprintf (stderr, "%s", s);
46  err_exit();
47 }
48 
49 
50 void dyn_prog( //The clever bit
51  int n,
52  int *x,
53  int *y,
54  int ymax,
55  int *oldx,
56  int *oldy,
57  int oldn,
58  float factor) {
59  int i, z, j, matchflag;
60  int **ymin;
61  float **F, fz;
62 
63  /* F[i][z] gives minimum over y <= z */
64 
65  F = (float **) calloc (n, sizeof (float *));
66  ymin = (int **) calloc (n, sizeof (int *));
67  if ((F == NULL) || (ymin == NULL))
68  dyn_exit ("Error in calloc\n");
69 
70  for (i = 0; i < n; i++) {
71  F[i] = (float *) calloc (ymax - n + i + 1, sizeof (float));
72  ymin[i] = (int *) calloc (ymax - n + i + 1, sizeof (int));
73  if ((F[i] == NULL) || (ymin[i] == NULL))
74  dyn_exit ("Error in calloc\n");
75  }
76 
77  F[0][0] = f (x[0], 0);
78  /* find nearest transition of same sign (white to black) */
79  j = 0;
80  while ((j < oldn) && (oldx[j] < x[0]))
81  j += 2;
82  if (j >= oldn)
83  j -= 2;
84  else if ((j - 2 >= 0) && ((x[0] - oldx[j - 2]) < (oldx[j] - x[0])))
85  j -= 2;
86  if (abs (oldx[j] - x[0]) < factor) {
87  matchflag = 1;
88  F[0][0] += g (oldy[j], 0, oldx[j], x[0]);
89  }
90  else
91  matchflag = 0;
92  ymin[0][0] = 0;
93 
94  for (z = 1; z < ymax - n + 1; z++) {
95  fz = f (x[0], z);
96  /* add penalty for deviating from previous row if necessary */
97 
98  if (matchflag)
99  fz += g (oldy[j], z, oldx[j], x[0]);
100  if (fz < F[0][z - 1]) {
101  F[0][z] = fz;
102  ymin[0][z] = z;
103  }
104  else {
105  F[0][z] = F[0][z - 1];
106  ymin[0][z] = ymin[0][z - 1];
107  }
108  }
109 
110  for (i = 1; i < n; i++) {
111  F[i][i] = f (x[i], i) + F[i - 1][i - 1];
112  /* add penalty for deviating from previous row if necessary */
113  if (j > 0)
114  j--;
115  else
116  j++;
117  while ((j < oldn) && (oldx[j] < x[i]))
118  j += 2;
119  if (j >= oldn)
120  j -= 2;
121  else if ((j - 2 >= 0) && ((x[i] - oldx[j - 2]) < (oldx[j] - x[i])))
122  j -= 2;
123  if (abs (oldx[j] - x[i]) < factor) {
124  matchflag = 1;
125  F[i][i] += g (oldy[j], i, oldx[j], x[i]);
126  }
127  else
128  matchflag = 0;
129  ymin[i][i] = i;
130  for (z = i + 1; z < ymax - n + i + 1; z++) {
131  fz = f (x[i], z) + F[i - 1][z - 1];
132  /* add penalty for deviating from previous row if necessary */
133  if (matchflag)
134  fz += g (oldy[j], z, oldx[j], x[i]);
135  if (fz < F[i][z - 1]) {
136  F[i][z] = fz;
137  ymin[i][z] = z;
138  }
139  else {
140  F[i][z] = F[i][z - 1];
141  ymin[i][z] = ymin[i][z - 1];
142  }
143  }
144  }
145 
146  y[n - 1] = ymin[n - 1][ymax - 1];
147  for (i = n - 2; i >= 0; i--)
148  y[i] = ymin[i][y[i + 1] - 1];
149 
150  for (i = 0; i < n; i++) {
151  free (F[i]);
152  free (ymin[i]);
153  }
154  free(F);
155  free(ymin);
156 
157  return;
158 }