2 * Copyright (c) 1999-2000 Image Power, Inc. and the University of
4 * Copyright (c) 2001-2003 Michael David Adams.
8 /* __START_OF_JASPER_LICENSE__
10 * JasPer License Version 2.0
12 * Copyright (c) 1999-2000 Image Power, Inc.
13 * Copyright (c) 1999-2000 The University of British Columbia
14 * Copyright (c) 2001-2003 Michael David Adams
16 * All rights reserved.
18 * Permission is hereby granted, free of charge, to any person (the
19 * "User") obtaining a copy of this software and associated documentation
20 * files (the "Software"), to deal in the Software without restriction,
21 * including without limitation the rights to use, copy, modify, merge,
22 * publish, distribute, and/or sell copies of the Software, and to permit
23 * persons to whom the Software is furnished to do so, subject to the
24 * following conditions:
26 * 1. The above copyright notices and this permission notice (which
27 * includes the disclaimer below) shall be included in all copies or
28 * substantial portions of the Software.
30 * 2. The name of a copyright holder shall not be used to endorse or
31 * promote products derived from the Software without specific prior
34 * THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS
35 * LICENSE. NO USE OF THE SOFTWARE IS AUTHORIZED HEREUNDER EXCEPT UNDER
36 * THIS DISCLAIMER. THE SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS
37 * "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
38 * BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
39 * PARTICULAR PURPOSE AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. IN NO
40 * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
41 * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
42 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
43 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
44 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. NO ASSURANCES ARE
45 * PROVIDED BY THE COPYRIGHT HOLDERS THAT THE SOFTWARE DOES NOT INFRINGE
46 * THE PATENT OR OTHER INTELLECTUAL PROPERTY RIGHTS OF ANY OTHER ENTITY.
47 * EACH COPYRIGHT HOLDER DISCLAIMS ANY LIABILITY TO THE USER FOR CLAIMS
48 * BROUGHT BY ANY OTHER ENTITY BASED ON INFRINGEMENT OF INTELLECTUAL
49 * PROPERTY RIGHTS OR OTHERWISE. AS A CONDITION TO EXERCISING THE RIGHTS
50 * GRANTED HEREUNDER, EACH USER HEREBY ASSUMES SOLE RESPONSIBILITY TO SECURE
51 * ANY OTHER INTELLECTUAL PROPERTY RIGHTS NEEDED, IF ANY. THE SOFTWARE
52 * IS NOT FAULT-TOLERANT AND IS NOT INTENDED FOR USE IN MISSION-CRITICAL
53 * SYSTEMS, SUCH AS THOSE USED IN THE OPERATION OF NUCLEAR FACILITIES,
54 * AIRCRAFT NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL
55 * SYSTEMS, DIRECT LIFE SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH
56 * THE FAILURE OF THE SOFTWARE OR SYSTEM COULD LEAD DIRECTLY TO DEATH,
57 * PERSONAL INJURY, OR SEVERE PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH
58 * RISK ACTIVITIES"). THE COPYRIGHT HOLDERS SPECIFICALLY DISCLAIM ANY
59 * EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR HIGH RISK ACTIVITIES.
61 * __END_OF_JASPER_LICENSE__
65 * Tree-Structured Filter Bank (TSFB) Library
67 * $Id: jpc_tsfb.c,v 1.1 2005/05/22 18:33:06 malaterre Exp $
70 /******************************************************************************\
72 \******************************************************************************/
76 #include "jasper/jas_malloc.h"
77 #include "jasper/jas_seq.h"
84 /******************************************************************************\
86 \******************************************************************************/
88 #define bandnotovind(tsfbnode, x) ((x) / (tsfbnode)->numhchans)
89 #define bandnotohind(tsfbnode, x) ((x) % (tsfbnode)->numhchans)
91 static jpc_tsfb_t *jpc_tsfb_create(void);
92 static jpc_tsfbnode_t *jpc_tsfbnode_create(void);
93 static void jpc_tsfbnode_destroy(jpc_tsfbnode_t *node);
94 static void jpc_tsfbnode_synthesize(jpc_tsfbnode_t *node, int flags, jas_seq2d_t *x);
95 static void jpc_tsfbnode_analyze(jpc_tsfbnode_t *node, int flags, jas_seq2d_t *x);
96 static void qmfb2d_getbands(jpc_qmfb1d_t *hqmfb, jpc_qmfb1d_t *vqmfb,
97 uint_fast32_t xstart, uint_fast32_t ystart, uint_fast32_t xend,
98 uint_fast32_t yend, int maxbands, int *numbandsptr, jpc_tsfbnodeband_t *bands);
99 static void jpc_tsfbnode_getbandstree(jpc_tsfbnode_t *node, uint_fast32_t posxstart,
100 uint_fast32_t posystart, uint_fast32_t xstart, uint_fast32_t ystart,
101 uint_fast32_t xend, uint_fast32_t yend, jpc_tsfb_band_t **bands);
102 static int jpc_tsfbnode_findchild(jpc_tsfbnode_t *parnode, jpc_tsfbnode_t *cldnode);
103 static int jpc_tsfbnode_getequivfilters(jpc_tsfbnode_t *tsfbnode, int cldind,
104 int width, int height, jas_seq_t **vfilter, jas_seq_t **hfilter);
106 /******************************************************************************\
108 \******************************************************************************/
110 jpc_tsfb_t *jpc_tsfb_wavelet(jpc_qmfb1d_t *hqmfb, jpc_qmfb1d_t *vqmfb, int numdlvls)
114 jpc_tsfbnode_t *curnode;
115 jpc_tsfbnode_t *prevnode;
117 if (!(tsfb = jpc_tsfb_create())) {
121 for (dlvlno = 0; dlvlno < numdlvls; ++dlvlno) {
122 if (!(curnode = jpc_tsfbnode_create())) {
123 jpc_tsfb_destroy(tsfb);
127 prevnode->children[0] = curnode;
128 ++prevnode->numchildren;
129 curnode->parent = prevnode;
131 tsfb->root = curnode;
135 curnode->numhchans = jpc_qmfb1d_getnumchans(hqmfb);
136 if (!(curnode->hqmfb = jpc_qmfb1d_copy(hqmfb))) {
137 jpc_tsfb_destroy(tsfb);
142 curnode->numhchans = 1;
145 curnode->numvchans = jpc_qmfb1d_getnumchans(vqmfb);
146 if (!(curnode->vqmfb = jpc_qmfb1d_copy(vqmfb))) {
147 jpc_tsfb_destroy(tsfb);
152 curnode->numvchans = 1;
154 curnode->maxchildren = curnode->numhchans * curnode->numvchans;
155 for (childno = 0; childno < curnode->maxchildren;
157 curnode->children[childno] = 0;
164 static jpc_tsfb_t *jpc_tsfb_create()
167 if (!(tsfb = jas_malloc(sizeof(jpc_tsfb_t)))) {
174 void jpc_tsfb_destroy(jpc_tsfb_t *tsfb)
177 jpc_tsfbnode_destroy(tsfb->root);
182 /******************************************************************************\
184 \******************************************************************************/
186 void jpc_tsfb_analyze(jpc_tsfb_t *tsfb, int flags, jas_seq2d_t *x)
189 jpc_tsfbnode_analyze(tsfb->root, flags, x);
193 static void jpc_tsfbnode_analyze(jpc_tsfbnode_t *node, int flags, jas_seq2d_t *x)
195 jpc_tsfbnodeband_t nodebands[JPC_TSFB_MAXBANDSPERNODE];
199 jpc_tsfbnodeband_t *band;
202 jpc_qmfb1d_analyze(node->vqmfb, flags | JPC_QMFB1D_VERT, x);
205 jpc_qmfb1d_analyze(node->hqmfb, flags, x);
207 if (node->numchildren > 0) {
208 qmfb2d_getbands(node->hqmfb, node->vqmfb, jas_seq2d_xstart(x),
209 jas_seq2d_ystart(x), jas_seq2d_xend(x), jas_seq2d_yend(x),
210 JPC_TSFB_MAXBANDSPERNODE, &numbands, nodebands);
211 y = jas_seq2d_create(0, 0, 0, 0);
213 for (bandno = 0, band = nodebands; bandno < numbands; ++bandno, ++band) {
214 if (node->children[bandno]) {
215 if (band->xstart != band->xend && band->ystart != band->yend) {
216 jas_seq2d_bindsub(y, x, band->locxstart, band->locystart,
217 band->locxend, band->locyend);
218 jas_seq2d_setshift(y, band->xstart, band->ystart);
219 jpc_tsfbnode_analyze(node->children[bandno], flags, y);
223 jas_matrix_destroy(y);
227 void jpc_tsfb_synthesize(jpc_tsfb_t *tsfb, int flags, jas_seq2d_t *x)
230 jpc_tsfbnode_synthesize(tsfb->root, flags, x);
234 static void jpc_tsfbnode_synthesize(jpc_tsfbnode_t *node, int flags, jas_seq2d_t *x)
236 jpc_tsfbnodeband_t nodebands[JPC_TSFB_MAXBANDSPERNODE];
240 jpc_tsfbnodeband_t *band;
242 if (node->numchildren > 0) {
243 qmfb2d_getbands(node->hqmfb, node->vqmfb, jas_seq2d_xstart(x),
244 jas_seq2d_ystart(x), jas_seq2d_xend(x), jas_seq2d_yend(x),
245 JPC_TSFB_MAXBANDSPERNODE, &numbands, nodebands);
246 y = jas_seq2d_create(0, 0, 0, 0);
247 for (bandno = 0, band = nodebands; bandno < numbands; ++bandno, ++band) {
248 if (node->children[bandno]) {
249 if (band->xstart != band->xend && band->ystart != band->yend) {
250 jas_seq2d_bindsub(y, x, band->locxstart, band->locystart,
251 band->locxend, band->locyend);
252 jas_seq2d_setshift(y, band->xstart, band->ystart);
253 jpc_tsfbnode_synthesize(node->children[bandno], flags, y);
257 jas_seq2d_destroy(y);
260 jpc_qmfb1d_synthesize(node->hqmfb, flags, x);
263 jpc_qmfb1d_synthesize(node->vqmfb, flags | JPC_QMFB1D_VERT, x);
267 /******************************************************************************\
269 \******************************************************************************/
272 int jpc_tsfb_getbands(jpc_tsfb_t *tsfb, uint_fast32_t xstart, uint_fast32_t ystart,
273 uint_fast32_t xend, uint_fast32_t yend, jpc_tsfb_band_t *bands)
275 jpc_tsfb_band_t *savbands;
278 bands[0].xstart = xstart;
279 bands[0].ystart = ystart;
280 bands[0].xend = xend;
281 bands[0].yend = yend;
282 bands[0].locxstart = xstart;
283 bands[0].locystart = ystart;
284 bands[0].locxend = xend;
285 bands[0].locyend = yend;
286 bands[0].orient = JPC_TSFB_LL;
287 bands[0].synenergywt = JPC_FIX_ONE;
290 jpc_tsfbnode_getbandstree(tsfb->root, xstart, ystart,
291 xstart, ystart, xend, yend, &bands);
293 return bands - savbands;
296 static void jpc_tsfbnode_getbandstree(jpc_tsfbnode_t *node, uint_fast32_t posxstart,
297 uint_fast32_t posystart, uint_fast32_t xstart, uint_fast32_t ystart,
298 uint_fast32_t xend, uint_fast32_t yend, jpc_tsfb_band_t **bands)
300 jpc_tsfbnodeband_t nodebands[JPC_TSFB_MAXBANDSPERNODE];
301 jpc_tsfbnodeband_t *nodeband;
304 jpc_tsfb_band_t *band;
308 qmfb2d_getbands(node->hqmfb, node->vqmfb, xstart, ystart, xend, yend,
309 JPC_TSFB_MAXBANDSPERNODE, &numnodebands, nodebands);
310 if (node->numchildren > 0) {
311 for (nodebandno = 0, nodeband = nodebands;
312 nodebandno < numnodebands; ++nodebandno, ++nodeband) {
313 if (node->children[nodebandno]) {
314 jpc_tsfbnode_getbandstree(node->children[
315 nodebandno], posxstart +
316 nodeband->locxstart - xstart, posystart +
317 nodeband->locystart - ystart, nodeband->xstart,
318 nodeband->ystart, nodeband->xend,
319 nodeband->yend, bands);
324 assert(numnodebands == 4 || numnodebands == 3);
325 for (nodebandno = 0, nodeband = nodebands; nodebandno < numnodebands;
326 ++nodebandno, ++nodeband) {
327 if (!node->children[nodebandno]) {
329 band->xstart = nodeband->xstart;
330 band->ystart = nodeband->ystart;
331 band->xend = nodeband->xend;
332 band->yend = nodeband->yend;
333 band->locxstart = posxstart + nodeband->locxstart -
335 band->locystart = posystart + nodeband->locystart -
337 band->locxend = band->locxstart + band->xend -
339 band->locyend = band->locystart + band->yend -
341 if (numnodebands == 4) {
342 switch (nodebandno) {
344 band->orient = JPC_TSFB_LL;
347 band->orient = JPC_TSFB_HL;
350 band->orient = JPC_TSFB_LH;
353 band->orient = JPC_TSFB_HH;
360 switch (nodebandno) {
362 band->orient = JPC_TSFB_HL;
365 band->orient = JPC_TSFB_LH;
368 band->orient = JPC_TSFB_HH;
375 jpc_tsfbnode_getequivfilters(node, nodebandno, band->xend - band->xstart, band->yend - band->ystart, &hfilter, &vfilter);
376 band->synenergywt = jpc_fix_mul(jpc_seq_norm(hfilter),
377 jpc_seq_norm(vfilter));
378 jas_seq_destroy(hfilter);
379 jas_seq_destroy(vfilter);
385 /******************************************************************************\
387 \******************************************************************************/
389 static jpc_tsfbnode_t *jpc_tsfbnode_create()
391 jpc_tsfbnode_t *node;
392 if (!(node = jas_malloc(sizeof(jpc_tsfbnode_t)))) {
397 node->numchildren = 0;
398 node->maxchildren = 0;
405 static void jpc_tsfbnode_destroy(jpc_tsfbnode_t *node)
407 jpc_tsfbnode_t **child;
409 for (childno = 0, child = node->children; childno < node->maxchildren;
410 ++childno, ++child) {
412 jpc_tsfbnode_destroy(*child);
416 jpc_qmfb1d_destroy(node->hqmfb);
419 jpc_qmfb1d_destroy(node->vqmfb);
431 static void qmfb2d_getbands(jpc_qmfb1d_t *hqmfb, jpc_qmfb1d_t *vqmfb,
432 uint_fast32_t xstart, uint_fast32_t ystart, uint_fast32_t xend,
433 uint_fast32_t yend, int maxbands, int *numbandsptr, jpc_tsfbnodeband_t *bands)
435 jpc_qmfb1dband_t hbands[JPC_QMFB1D_MAXCHANS];
436 jpc_qmfb1dband_t vbands[JPC_QMFB1D_MAXCHANS];
443 jpc_tsfbnodeband_t *band;
446 jpc_qmfb1d_getbands(hqmfb, 0, xstart, ystart, xend, yend,
447 JPC_QMFB1D_MAXCHANS, &numhbands, hbands);
450 hbands[0].start = xstart;
451 hbands[0].end = xend;
452 hbands[0].locstart = xstart;
453 hbands[0].locend = xend;
456 jpc_qmfb1d_getbands(vqmfb, JPC_QMFB1D_VERT, xstart, ystart, xend,
457 yend, JPC_QMFB1D_MAXCHANS, &numvbands, vbands);
460 vbands[0].start = ystart;
461 vbands[0].end = yend;
462 vbands[0].locstart = ystart;
463 vbands[0].locend = yend;
465 numbands = numhbands * numvbands;
466 assert(numbands <= maxbands);
467 *numbandsptr = numbands;
468 for (bandno = 0, band = bands; bandno < numbands; ++bandno, ++band) {
469 hbandno = bandno % numhbands;
470 vbandno = bandno / numhbands;
471 band->xstart = hbands[hbandno].start;
472 band->ystart = vbands[vbandno].start;
473 band->xend = hbands[hbandno].end;
474 band->yend = vbands[vbandno].end;
475 band->locxstart = hbands[hbandno].locstart;
476 band->locystart = vbands[vbandno].locstart;
477 band->locxend = hbands[hbandno].locend;
478 band->locyend = vbands[vbandno].locend;
479 assert(band->xstart <= band->xend &&
480 band->ystart <= band->yend);
481 if (band->xstart == band->xend) {
482 band->yend = band->ystart;
483 band->locyend = band->locystart;
484 } else if (band->ystart == band->yend) {
485 band->xend = band->xstart;
486 band->locxend = band->locxstart;
491 static int jpc_tsfbnode_getequivfilters(jpc_tsfbnode_t *tsfbnode, int cldind,
492 int width, int height, jas_seq_t **hfilter, jas_seq_t **vfilter)
496 jpc_tsfbnode_t *node;
497 jas_seq2d_t *hfilters[JPC_QMFB1D_MAXCHANS];
498 jas_seq2d_t *vfilters[JPC_QMFB1D_MAXCHANS];
506 if (!(hseq = jas_seq_create(0, 1))) {
509 jas_seq_set(hseq, 0, jpc_inttofix(1));
510 if (!(vseq = jas_seq_create(0, 1))) {
513 jas_seq_set(vseq, 0, jpc_inttofix(1));
518 numhchans = jpc_qmfb1d_getnumchans(node->hqmfb);
519 if (jpc_qmfb1d_getsynfilters(node->hqmfb, width, hfilters)) {
522 if (!(tmpseq = jpc_seq_upsample(hseq, numhchans))) {
525 jas_seq_destroy(hseq);
527 if (!(tmpseq = jpc_seq_conv(hseq, hfilters[bandnotohind(node, cldind)]))) {
530 jas_seq_destroy(hfilters[0]);
531 jas_seq_destroy(hfilters[1]);
532 jas_seq_destroy(hseq);
536 numvchans = jpc_qmfb1d_getnumchans(node->vqmfb);
537 if (jpc_qmfb1d_getsynfilters(node->vqmfb, height, vfilters)) {
540 if (!(tmpseq = jpc_seq_upsample(vseq, numvchans))) {
543 jas_seq_destroy(vseq);
545 if (!(tmpseq = jpc_seq_conv(vseq, vfilters[bandnotovind(node, cldind)]))) {
548 jas_seq_destroy(vfilters[0]);
549 jas_seq_destroy(vfilters[1]);
550 jas_seq_destroy(vseq);
554 cldind = jpc_tsfbnode_findchild(node->parent, node);
566 jas_seq_destroy(hseq);
569 jas_seq_destroy(vseq);
575 static int jpc_tsfbnode_findchild(jpc_tsfbnode_t *parnode, jpc_tsfbnode_t *cldnode)
579 for (i = 0; i < parnode->maxchildren; i++) {
580 if (parnode->children[i] == cldnode)
587 jpc_tsfb_t *jpc_cod_gettsfb(int qmfbid, int numlevels)
593 qmfbid = JPC_QMFB1D_FT;
596 qmfbid = JPC_QMFB1D_NS;
606 hqmfb = jpc_qmfb1d_make(qmfbid);
608 tsfb = jpc_tsfb_wavelet(hqmfb, hqmfb, numlevels);
610 jpc_qmfb1d_destroy(hqmfb);