Debian Codegraph @

src/matcher/cuts.c

raw
1 /*
2 * cuts.c - finding "cuts signature" consisting of consecutive cut positions
3 */
4
5
6 /* We cut an image horizontally in such a way
7 * that below and above the cut the blackness is roughly the same.
8 * Than cutting each of the two pieces vertically in the same fashion.
9 * Then horizontally, and so on until SIGNATURE_SIZE - 1 cuts.
10 * The position of each cut is normalized into 0..255 and put into signature.
11 */
12
13 #include "../base/mdjvucfg.h"
14 #include <minidjvu/minidjvu.h>
15 #include <assert.h>
16
17
18 /* Stuff for not using malloc in C++
19 * (made by Leon Bottou; has no use in minidjvu,
20 * but left here for potential DjVuLibre compatibility)
21 */
22 #ifdef __cplusplus
23 # define MALLOC(Type) new Type
24 # define FREE(p) delete p
25 # define MALLOCV(Type,n) new Type[n]
26 # define FREEV(p) delete [] p
27 #else
28 # define MALLOC(Type) ((Type*)malloc(sizeof(Type)))
29 # define FREE(p) do{if(p)free(p);}while(0)
30 # define MALLOCV(Type,n) ((Type*)malloc(sizeof(Type)*(n)))
31 # define FREEV(p) do{if(p)free(p);}while(0)
32 #endif
33
34
35 typedef unsigned char byte;
36
37 static int32 sum_column_gray(byte **pixels, int32 x, int32 y1, int32 y2)
38 {
39 int sum = 0, y;
40 for (y = y1; y <= y2; y++) sum += pixels[y][x];
41 return sum;
42 }
43
44 static int32 sum_row_gray(byte *row, int32 x1, int32 x2)
45 {
46 int sum = 0, x, n = x2 - x1;
47 byte *p = row + x1;
48 for (x = 0; x <= n; x++) sum += p[x];
49 return sum;
50 }
51
52 static int32 sum_column_black_and_white(byte **pixels, int32 x, int32 y1, int32 y2)
53 {
54 int sum = 0, y;
55 for (y = y1; y <= y2; y++) if (pixels[y][x]) sum++;
56 return sum;
57 }
58
59 static int32 sum_row_black_and_white(byte *row, int32 x1, int32 x2)
60 {
61 int sum = 0, x, n = x2 - x1;
62 byte *p = row + x1;
63 for (x = 0; x <= n; x++) if (p[x]) sum++;
64 return sum;
65 }
66
67 static void make_vcut(int32 a, int32 l, int32 w, int32 h, byte **pixels,
68 byte *sig, int32 k,
69 int32 s_row(byte *, int32, int32),
70 int32 s_col(byte **, int32, int32, int32),
71 int32 size);
72
73 static void make_hcut(int32 a, int32 l, int32 w, int32 h,
74 byte **pixels, byte *sig, int32 k,
75 int32 s_row(byte *, int32, int32),
76 int32 s_col(byte **, int32, int32, int32),
77 int32 size)
78 {
79 int32 cut = 0; /* how many rows are in the top part */
80 int32 up_weight = 0;
81
82 if (k >= size) return;
83
84 if (a)
85 {
86 int32 last_row_weight = 0;
87
88 assert(w && h);
89
90 while ((up_weight << 1) < a)
91 {
92 last_row_weight = s_row(pixels[cut], l, l + w - 1);
93 up_weight += last_row_weight;
94 cut++;
95 }
96 cut--;
97 up_weight -= last_row_weight;
98 sig[k] = (byte) ((256 *
99 (cut * w + w * ((a >> 1) - up_weight) / last_row_weight))
100 / (w * h));
101 if (a - (up_weight << 1) > last_row_weight)
102 {
103 cut++;
104 up_weight += last_row_weight;
105 }
106 }
107 else
108 {
109 cut = h / 2;
110 sig[k] = 128;
111 }
112
113 make_vcut(up_weight, l, w, cut, pixels, sig, k << 1, s_row, s_col, size);
114 make_vcut(a - up_weight, l, w, h - cut, pixels + cut, sig, (k << 1) | 1, s_row, s_col, size);
115 }
116
117 static void make_vcut(int32 a, int32 l, int32 w, int32 h,
118 byte **pixels, byte *sig, int32 k,
119 int32 s_row(byte *, int32, int32),
120 int32 s_col(byte **, int32, int32, int32),
121 int32 size)
122 {
123 int32 cut = 0; /* how many columns are in the left part */
124 int32 left_weight = 0;
125
126 if (k >= size) return;
127
128 if (a)
129 {
130 int32 last_col_weight = 0;
131
132 assert(w && h);
133
134 while ((left_weight << 1) < a)
135 {
136 last_col_weight = s_col(pixels, l + cut, 0, h-1);
137 left_weight += last_col_weight;
138 cut++;
139 }
140 cut--;
141 left_weight -= last_col_weight;
142 sig[k] = (byte) ((256 *
143 (cut * h + h * ((a >> 1) - left_weight) / last_col_weight))
144 / (w * h));
145 if (a - (left_weight << 1) > last_col_weight)
146 {
147 cut++; left_weight += last_col_weight;
148 }
149 }
150 else
151 {
152 cut = w / 2;
153 sig[k] = 128;
154 }
155
156 make_hcut(left_weight, l, cut, h, pixels, sig, k << 1, s_row, s_col, size);
157 make_hcut(a - left_weight, l + cut, w - cut, h, pixels, sig, (k << 1) | 1, s_row, s_col, size);
158 }
159
160 static void get_signature(int32 width, int32 height, byte **pixels, byte *sig,
161 int32 s_row(byte *, int32, int32),
162 int32 s_col(byte **, int32, int32, int32),
163 int32 size)
164 {
165 int32 area = 0, i;
166 for (i = 0; i < height; i++)
167 {
168 area += s_row(pixels[i], 0, width - 1);
169 }
170 /* FIXME: sig[0] is wasted */
171 make_hcut(area, 0, width, height, pixels, sig, 1, s_row, s_col, size);
172 }
173
174 MDJVU_IMPLEMENT void mdjvu_get_gray_signature(byte **data, int32 w, int32 h,
175 byte *result, int32 size)
176 {
177 get_signature(w, h, data, result, sum_row_gray, sum_column_gray, size);
178 }
179
180 MDJVU_IMPLEMENT void mdjvu_get_black_and_white_signature
181 (byte **data, int32 w, int32 h,
182 byte *result, int32 size)
183 {
184 get_signature(w, h, data, result, sum_row_black_and_white, sum_column_black_and_white, size);
185 }