1 /* minidjvu - library for handling bilevel images with DjVuBitonal support
2 *
3 * cuts.c - finding "cuts signature" consisting of consecutive cut positions
4 *
5 * Copyright (C) 2005 Ilya Mezhirov
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program. If not, see <http://www.gnu.org/licenses/>.
19 *
20 *
21 * minidjvu is derived from DjVuLibre (http://djvu.sourceforge.net)
22 * All over DjVuLibre there is a patent alert from LizardTech
23 * which I guess I should reproduce (don't ask me what does this mean):
24 *
25 * ------------------------------------------------------------------
26 * | DjVu (r) Reference Library (v. 3.5)
27 * | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
28 * | The DjVu Reference Library is protected by U.S. Pat. No.
29 * | 6,058,214 and patents pending.
30 * |
31 * | This software is subject to, and may be distributed under, the
32 * | GNU General Public License, either Version 2 of the license,
33 * | or (at your option) any later version. The license should have
34 * | accompanied the software or you may obtain a copy of the license
35 * | from the Free Software Foundation at http://www.fsf.org .
36 * |
37 * | The computer code originally released by LizardTech under this
38 * | license and unmodified by other parties is deemed "the LIZARDTECH
39 * | ORIGINAL CODE." Subject to any third party intellectual property
40 * | claims, LizardTech grants recipient a worldwide, royalty-free,
41 * | non-exclusive license to make, use, sell, or otherwise dispose of
42 * | the LIZARDTECH ORIGINAL CODE or of programs derived from the
43 * | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
44 * | General Public License. This grant only confers the right to
45 * | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
46 * | the extent such infringement is reasonably necessary to enable
47 * | recipient to make, have made, practice, sell, or otherwise dispose
48 * | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
49 * | any greater extent that may be necessary to utilize further
50 * | modifications or combinations.
51 * |
52 * | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
53 * | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
54 * | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
55 * | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
56 * +------------------------------------------------------------------
57 */
58
59
60 /* We cut an image horizontally in such a way
61 * that below and above the cut the blackness is roughly the same.
62 * Than cutting each of the two pieces vertically in the same fashion.
63 * Then horizontally, and so on until SIGNATURE_SIZE - 1 cuts.
64 * The position of each cut is normalized into 0..255 and put into signature.
65 */
66
67 #include "mdjvucfg.h"
68 #include "minidjvu.h"
69 #include <assert.h>
70
71
72 /* Stuff for not using malloc in C++
73 * (made by Leon Bottou; has no use in minidjvu,
74 * but left here for potential DjVuLibre compatibility)
75 */
76 #ifdef __cplusplus
77 # define MALLOC(Type) new Type
78 # define FREE(p) delete p
79 # define MALLOCV(Type,n) new Type[n]
80 # define FREEV(p) delete [] p
81 #else
82 # define MALLOC(Type) ((Type*)malloc(sizeof(Type)))
83 # define FREE(p) do{if(p)free(p);}while(0)
84 # define MALLOCV(Type,n) ((Type*)malloc(sizeof(Type)*(n)))
85 # define FREEV(p) do{if(p)free(p);}while(0)
86 #endif
87
88
89 typedef unsigned char byte;
90
sum_column_gray(byte ** pixels,int32 x,int32 y1,int32 y2)91 static int32 sum_column_gray(byte **pixels, int32 x, int32 y1, int32 y2)
92 {
93 int sum = 0, y;
94 for (y = y1; y <= y2; y++) sum += pixels[y][x];
95 return sum;
96 }
97
sum_row_gray(byte * row,int32 x1,int32 x2)98 static int32 sum_row_gray(byte *row, int32 x1, int32 x2)
99 {
100 int sum = 0, x, n = x2 - x1;
101 byte *p = row + x1;
102 for (x = 0; x <= n; x++) sum += p[x];
103 return sum;
104 }
105
sum_column_black_and_white(byte ** pixels,int32 x,int32 y1,int32 y2)106 static int32 sum_column_black_and_white(byte **pixels, int32 x, int32 y1, int32 y2)
107 {
108 int sum = 0, y;
109 for (y = y1; y <= y2; y++) if (pixels[y][x]) sum++;
110 return sum;
111 }
112
sum_row_black_and_white(byte * row,int32 x1,int32 x2)113 static int32 sum_row_black_and_white(byte *row, int32 x1, int32 x2)
114 {
115 int sum = 0, x, n = x2 - x1;
116 byte *p = row + x1;
117 for (x = 0; x <= n; x++) if (p[x]) sum++;
118 return sum;
119 }
120
121 static void make_vcut(int32 a, int32 l, int32 w, int32 h, byte **pixels,
122 byte *sig, int32 k,
123 int32 s_row(byte *, int32, int32),
124 int32 s_col(byte **, int32, int32, int32),
125 int32 size);
126
make_hcut(int32 a,int32 l,int32 w,int32 h,byte ** pixels,byte * sig,int32 k,int32 s_row (byte *,int32,int32),int32 s_col (byte **,int32,int32,int32),int32 size)127 static void make_hcut(int32 a, int32 l, int32 w, int32 h,
128 byte **pixels, byte *sig, int32 k,
129 int32 s_row(byte *, int32, int32),
130 int32 s_col(byte **, int32, int32, int32),
131 int32 size)
132 {
133 int32 cut = 0; /* how many rows are in the top part */
134 int32 up_weight = 0;
135
136 if (k >= size) return;
137
138 if (a)
139 {
140 int32 last_row_weight = 0;
141
142 assert(w && h);
143
144 while ((up_weight << 1) < a)
145 {
146 last_row_weight = s_row(pixels[cut], l, l + w - 1);
147 up_weight += last_row_weight;
148 cut++;
149 }
150 cut--;
151 up_weight -= last_row_weight;
152 sig[k] = (byte) ((256 *
153 (cut * w + w * ((a >> 1) - up_weight) / last_row_weight))
154 / (w * h));
155 if (a - (up_weight << 1) > last_row_weight)
156 {
157 cut++;
158 up_weight += last_row_weight;
159 }
160 }
161 else
162 {
163 cut = h / 2;
164 sig[k] = 128;
165 }
166
167 make_vcut(up_weight, l, w, cut, pixels, sig, k << 1, s_row, s_col, size);
168 make_vcut(a - up_weight, l, w, h - cut, pixels + cut, sig, (k << 1) | 1, s_row, s_col, size);
169 }
170
make_vcut(int32 a,int32 l,int32 w,int32 h,byte ** pixels,byte * sig,int32 k,int32 s_row (byte *,int32,int32),int32 s_col (byte **,int32,int32,int32),int32 size)171 static void make_vcut(int32 a, int32 l, int32 w, int32 h,
172 byte **pixels, byte *sig, int32 k,
173 int32 s_row(byte *, int32, int32),
174 int32 s_col(byte **, int32, int32, int32),
175 int32 size)
176 {
177 int32 cut = 0; /* how many columns are in the left part */
178 int32 left_weight = 0;
179
180 if (k >= size) return;
181
182 if (a)
183 {
184 int32 last_col_weight = 0;
185
186 assert(w && h);
187
188 while ((left_weight << 1) < a)
189 {
190 last_col_weight = s_col(pixels, l + cut, 0, h-1);
191 left_weight += last_col_weight;
192 cut++;
193 }
194 cut--;
195 left_weight -= last_col_weight;
196 sig[k] = (byte) ((256 *
197 (cut * h + h * ((a >> 1) - left_weight) / last_col_weight))
198 / (w * h));
199 if (a - (left_weight << 1) > last_col_weight)
200 {
201 cut++; left_weight += last_col_weight;
202 }
203 }
204 else
205 {
206 cut = w / 2;
207 sig[k] = 128;
208 }
209
210 make_hcut(left_weight, l, cut, h, pixels, sig, k << 1, s_row, s_col, size);
211 make_hcut(a - left_weight, l + cut, w - cut, h, pixels, sig, (k << 1) | 1, s_row, s_col, size);
212 }
213
get_signature(int32 width,int32 height,byte ** pixels,byte * sig,int32 s_row (byte *,int32,int32),int32 s_col (byte **,int32,int32,int32),int32 size)214 static void get_signature(int32 width, int32 height, byte **pixels, byte *sig,
215 int32 s_row(byte *, int32, int32),
216 int32 s_col(byte **, int32, int32, int32),
217 int32 size)
218 {
219 int32 area = 0, i;
220 for (i = 0; i < height; i++)
221 {
222 area += s_row(pixels[i], 0, width - 1);
223 }
224 /* FIXME: sig[0] is wasted */
225 make_hcut(area, 0, width, height, pixels, sig, 1, s_row, s_col, size);
226 }
227
mdjvu_get_gray_signature(byte ** data,int32 w,int32 h,byte * result,int32 size)228 MDJVU_IMPLEMENT void mdjvu_get_gray_signature(byte **data, int32 w, int32 h,
229 byte *result, int32 size)
230 {
231 get_signature(w, h, data, result, sum_row_gray, sum_column_gray, size);
232 }
233
mdjvu_get_black_and_white_signature(byte ** data,int32 w,int32 h,byte * result,int32 size)234 MDJVU_IMPLEMENT void mdjvu_get_black_and_white_signature
235 (byte **data, int32 w, int32 h,
236 byte *result, int32 size)
237 {
238 get_signature(w, h, data, result, sum_row_black_and_white, sum_column_black_and_white, size);
239 }
240