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
|
/*
* tiling.c: Subimage permutation
*
* Written by: Ullrich Hafner
*
* This file is part of FIASCO (Fractal Image And Sequence COdec)
* Copyright (C) 1994-2000 Ullrich Hafner
*/
/*
* $Date: 2000/06/14 20:50:51 $
* $Author: hafner $
* $Revision: 5.1 $
* $State: Exp $
*/
#include "config.h"
#include <stdlib.h>
#include "pm_c_util.h"
#include "types.h"
#include "macros.h"
#include "error.h"
#include "image.h"
#include "misc.h"
#include "wfalib.h"
#include "tiling.h"
typedef struct var_list
{
int address; /* bintree address */
real_t variance; /* variance of tile */
} var_list_t;
#ifndef LITERAL_FN_DEF_MATCH
static qsort_comparison_fn cmpincvar;
#endif
static int
cmpincvar(const void * const value1,
const void * const value2) {
/*----------------------------------------------------------------------------
Sorts by increasing variances (quicksort sorting function)
-----------------------------------------------------------------------------*/
return
((var_list_t *) value1)->variance - ((var_list_t *) value2)->variance;
}
#ifndef LITERAL_FN_DEF_MATCH
static qsort_comparison_fn cmpdecvar;
#endif
static int
cmpdecvar(const void * const value1,
const void * const value2) {
/*----------------------------------------------------------------------------
Sorts by decreasing variances (quicksort sorting function).
-----------------------------------------------------------------------------*/
return
((var_list_t *) value2)->variance - ((var_list_t *) value1)->variance;
}
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 ("We do not know the tiling method.\n"
"Skipping image tiling step.");
tiling->exponent = 0;
}
}
}
|
