| 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 |
} |