1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
/*
* tiling.c: Subimage permutation
*
* Written by: Ullrich Hafner
*
* This file is part of FIASCO («F»ractal «I»mage «A»nd «S»equence «CO»dec)
* Copyright (C) 1994-2000 Ullrich Hafner <hafner@bigfoot.de>
*/
/*
* $Date: 2000/06/14 20:50:51 $
* $Author: hafner $
* $Revision: 5.1 $
* $State: Exp $
*/
#include "config.h"
#if STDC_HEADERS
# include <stdlib.h>
#endif /* not STDC_HEADERS */
#include "types.h"
#include "macros.h"
#include "error.h"
#include "image.h"
#include "misc.h"
#include "wfalib.h"
#include "tiling.h"
/*****************************************************************************
prototypes
*****************************************************************************/
static int
cmpdecvar (const void *value1, const void *value2);
static int
cmpincvar (const void *value1, const void *value2);
/*****************************************************************************
public code
*****************************************************************************/
typedef struct var_list
{
int address; /* bintree address */
real_t variance; /* variance of tile */
} var_list_t;
tiling_t *
alloc_tiling (fiasco_tiling_e method, unsigned tiling_exponent,
unsigned image_level)
/*
* Image tiling constructor.
* Allocate memory for the tiling_t structure.
* `method' defines the tiling method (spiral or variance,
* ascending or descending).
* In case of invalid parameters, a structure with tiling.exponent == 0 is
* returned.
*
* Return value
* pointer to the new tiling structure on success
*/
{
tiling_t *tiling = Calloc (1, sizeof (tiling_t));
if ((int) image_level - (int) tiling_exponent < 6)
{
tiling_exponent = 6;
warning (_("Image tiles must be at least 8x8 pixels large.\n"
"Setting tiling size to 8x8 pixels."));
}
switch (method)
{
case FIASCO_TILING_SPIRAL_ASC:
case FIASCO_TILING_SPIRAL_DSC:
case FIASCO_TILING_VARIANCE_ASC:
case FIASCO_TILING_VARIANCE_DSC:
tiling_exponent = tiling_exponent;
break;
default:
warning (_("Invalid tiling method specified. Disabling tiling."));
tiling_exponent = 0;
break;
}
return tiling;
}
void
free_tiling (tiling_t *tiling)
/*
* Tiling struct destructor:
* Free memory of 'tiling' struct.
*
* No return value.
*
* Side effects:
* structure 'tiling' is discarded.
*/
{
if (tiling->vorder)
Free (tiling->vorder);
Free (tiling);
}
void
perform_tiling (const image_t *image, tiling_t *tiling)
/*
* Compute image tiling permutation.
* The image is split into 2**'tiling->exponent' tiles.
* Depending on 'tiling->method', the following algorithms are used:
* "VARIANCE_ASC" : Tiles are sorted by variance.
* The first tile has the lowest variance
* "VARIANCE_DSC" : Tiles are sorted by variance.
* The first tile has the largest variance
* "SPIRAL_ASC" : Tiles are sorted like a spiral starting
* in the middle of the image.
* "SPIRAL_DSC" : Tiles are sorted like a spiral starting
* in the upper left corner.
*
* No return value.
*
* Side effects:
* The tiling permutation is stored in 'tiling->vorder'.
*/
{
if (tiling->exponent)
{
unsigned tiles = 1 << tiling->exponent; /* number of image tiles */
bool_t *tile_valid; /* tile i is in valid range ? */
tiling->vorder = Calloc (tiles, sizeof (int));
tile_valid = Calloc (tiles, sizeof (bool_t));
if (tiling->method == FIASCO_TILING_VARIANCE_ASC
|| tiling->method == FIASCO_TILING_VARIANCE_DSC)
{
unsigned address; /* bintree address of tile */
unsigned number; /* number of image tiles */
unsigned lx = log2 (image->width - 1) + 1; /* x level */
unsigned ly = log2 (image->height - 1) + 1; /* y level */
unsigned level = max (lx, ly) * 2 - ((ly == lx + 1) ? 1 : 0);
var_list_t *var_list = Calloc (tiles, sizeof (var_list_t));
/*
* Compute variances of image tiles
*/
for (number = 0, address = 0; address < tiles; address++)
{
unsigned width, height; /* size of image tile */
unsigned x0, y0; /* NW corner of image tile */
locate_subimage (level, level - tiling->exponent, address,
&x0, &y0, &width, &height);
if (x0 < image->width && y0 < image->height) /* valid range */
{
if (x0 + width > image->width) /* outside image area */
width = image->width - x0;
if (y0 + height > image->height) /* outside image area */
height = image->height - y0;
var_list [number].variance
= variance (image->pixels [GRAY], x0, y0,
width, height, image->width);
var_list [number].address = address;
number++;
tile_valid [address] = YES;
}
else
tile_valid [address] = NO;
}
/*
* Sort image tiles according to sign of 'tiling->exp'
*/
if (tiling->method == FIASCO_TILING_VARIANCE_DSC)
qsort (var_list, number, sizeof (var_list_t), cmpdecvar);
else
qsort (var_list, number, sizeof (var_list_t), cmpincvar);
for (number = 0, address = 0; address < tiles; address++)
if (tile_valid [address])
{
tiling->vorder [address] = var_list [number].address;
number++;
debug_message ("tile number %d has original address %d",
number, tiling->vorder [address]);
}
else
tiling->vorder [address] = -1;
Free (var_list);
}
else if (tiling->method == FIASCO_TILING_SPIRAL_DSC
|| tiling->method == FIASCO_TILING_SPIRAL_ASC)
{
compute_spiral (tiling->vorder, image->width, image->height,
tiling->exponent,
tiling->method == FIASCO_TILING_SPIRAL_ASC);
}
else
{
warning ("Unsupported image tiling method.\n"
"Skipping image tiling step.");
tiling->exponent = 0;
}
}
}
/*****************************************************************************
private code
*****************************************************************************/
static int
cmpincvar (const void *value1, const void *value2)
/*
* Sorts by increasing variances (quicksort sorting function).
*/
{
return ((var_list_t *) value1)->variance - ((var_list_t *) value2)->variance;
}
static int
cmpdecvar (const void *value1, const void *value2)
/*
* Sorts by decreasing variances (quicksort sorting function).
*/
{
return ((var_list_t *) value2)->variance - ((var_list_t *) value1)->variance;
}
|
