libftsh
A Fast Transform for Spherical Harmonics
|
Best non-decreasing dyadic partition search. More...
#include "libftsh.h"
Defines | |
#define | ENTEREXIT 0 |
Functions | |
int | dyadic_gsearch (Dyadic_Gsearch_Save *dy_gs_save) |
void | dyadic_gsearch_init (Dyadic_Gsearch_Save *dy_gs_save, int num_levels) |
void | dyadic_gsearch_free (Dyadic_Gsearch_Save *dy_gs_save) |
Best non-decreasing dyadic partition search.
Summary:
The memory for all the objects used in the search are held in a structure of type Dyadic_Gsearch_Save. Declare one of these:
Dyadic_Gsearch_Save dy_gs_save;
To initialize this structure, call
dyadic_gsearch_init(&dy_gs_save,num_levels);
with num_levels the number of dyadic levels to use.
Then compute whatever basis you are using and load in the costs: costfull[level][within] should contain the full bell cost of the within^th interval the level^th level (2^level intervals on level). Similarly for costasym.
Then call this routine to do the search itself. Returns the minimal cost, which is also stored in dy_gs_save.costfull[dy_gs_save.best_level][0].
dyadic_gsearch(&dy_gs_save);
You can then do other basis expansions (with the same num_levels) and searchs.
When you are ready to free the memory, call
dyadic_gsearch_free(&dy_gs_save);
int dyadic_gsearch | ( | Dyadic_Gsearch_Save * | dy_gs_save | ) |
This routine implements a `best non-decreasing dyadic partition' search. It finds the partition with lowest cost under the restriction that an interval's right neighbor is either the same size or one size (2x) larger. Generally this is to be used with local cosine. When an interval's left neighbor is the same size, we use a regular full sized bell and put the cost of this expansion in .cost_full[][]. When the left neighbor is smaller we shrink the left edge of the bell, making it asymmetric and yielding .cost_asym[][].
The search tree is grown from the left, with an interval having children its allowed right neighbors. The cost of a partition is the cost of a path from the left edge to the right edge. Since each interval has two costs, the path into an interval is also important.
| _--------------O | |/ | /| _-----O-------|--------->O | O-|-/ _--|--------/ | \| | / | | | |~--O---|-->O----|--->O----|---->O |
The generic decision step is: assume the current node's children contain the minimal cost of a path from them to the right. Compare these costs and ADD the smaller to the full and asym costs of the current node. We process intervals in order of the x-coordinate of their center, starting at the right.
INPUTS: dy_gs_save -- a structure holding memory for the costs, branching and ordering of interval. See the declaration of the structure Dyadic_Gsearch_Save for the full description of its fields.
OUTPUTS: returns the minimal cost, and also stores it in dy_gs_save.costfull[dy_gs_save.best_level][0]. To determine the partition chosen, start at [best_level][0] and follow .branching[][], which has values one of {RIGHTEDGE=0, SAMESIZE=1, UPSIZE=2}
void dyadic_gsearch_free | ( | Dyadic_Gsearch_Save * | dy_gs_save | ) |
This function frees the structure Dyadic_Gsearch_Save used by dyadic_gsearch and initialized by dyadic_gsearch_init.
INPUTS: dy_gs_save -- a pointer to the structure to free
OUTPUT: none
void dyadic_gsearch_init | ( | Dyadic_Gsearch_Save * | dy_gs_save, |
int | num_levels | ||
) |
This function initializes the structure Dyadic_Gsearch_Save for use by dyadic_gsearch. Memory can be freed by dyadic_gsearch_free.
INPUTS:
OUTPUT: dy_gs_save -- memory is allocated and some things filled in.