Our implementation

The algorithms available on this website depend on a technique that allows a convenient control of the angular resolution of the wedgelet scheme. Given an arbitrary angle $\theta$, we consider a decomposition of the image domain into parallel digitized lines all having angle $\theta$ with the horizontal axis. Then the (costly) first step of the minimization procedure is performed for all wedges arising by a split along one of these lines, using lookuptables. Angles can be treated consecutively, which keeps the allocation efforts within reasonable bounds. The number of angles enters linearly into the computation time. Thus our implementation allows an arbitrary transition

Let us quickly give an overview of the features, as they are accessible in the panel. The main purpose of the panel is to provide a platform for the convenient experimentation with wedgelets, with a rapid and convenient visualization of the results. We now give a short description of the panel; confer the page http://www.antsinfields.de/wedgelet/screenshots.html for a screenshot.

• Section "open pgm (ascii) file": This button has the obvious function. Currently we only support pgm (ascii) format; freely available software such as IrfanView (Windows) or GIMP (Linux) can be used for the conversion from other file formats.
• The "create new tree" button allocates the necessary memory for the following steps.
• The buttons in the "add model" section allow to perform a local minimization for the loaded image. Note that there is an array of such buttons. Here the different rows correspond to different choices of the underlying sets of wedges, in increasing order of complexity: "dyadic rectmodel" corresponds to taking dyadic squares as wedges. "wedge model explicit" allows the definition of angles in a direct manner; "wedge model" uses an incremental way of prescribing the angles. The "adaptive wedge model" row refers to a set of admissible angles that depends on the size of the dyadic interval. Clearly a dyadic square of $2^j \times 2^j$ can only resolve $O(2^j)$ angles, and the "adaptive wedge model" scheme reflects this observation. Thus we obtain a considerably better angular resolution than in the "wedge model", at a comparable computational cost.

  The columns of the array of buttons correspond to different ways of locally approximating the image. In addition to piecewise constant approximation of the image, we have also implemented piecewise affine and piecewise quadratic approximation. The generalization to piecewise linear approximation was already suggested by Willett and Nowak [3], who coined the term "platelets" for the resulting system of local approximants. Figure 2 below shows a comparison of locally constant vs. locally linear approximation.

  Since increase in model complexity necessarily implies a better approximation behaviour, the functional that is minimized in the more general setting is given by
  

  $$H_{\gamma,f} ( {\cal P},f_{{\cal P}} ) = \gamma \char93 (\mbox{Parameters }) + \Vert f - f_{{\cal P}} \Vert _2^2  ,$$ (2)

  
  
  where $\char93 (\mbox{Parameters })$ is the number of real parameters needed to code the different local approximations, i.e., 1 for constant, 3 for affine, and 6 for quadratic approximation. The price to pay is an obvious increase in computational complexity; in the quadratic case there are also some numerical stability issues to consider (see [2]). On the other hand, for images containing smooth color gradients, the use of higher order models allows a better approximation, as can be seen in Figure 2 below.

  An important additional feature of the implementation is that the different schemes can be used simultaneously. Note that the functional (2) allows to treat varying models within an image. In our implementation, the result of each additional local minimization step is stored separately, and considered later on in the global minimization procedure.

• The minimization section allows to fix the parameter $\gamma$. Pressing a button from the "open output" section then allows to view the result. The displayed minimization result is automatically updated after a new choice of $\gamma$. The parameter can be prescribed numerically or via sliders. Moving the "heavy drag slider" around while pressing the left mouse button allows to view the family of minimizers $(\widehat{{\cal P}}_\gamma,\widehat{f}_{\gamma} )$ for different $\gamma$ essentially in real time.
• The "open output" section allows the display of the minimization results. The "show array" button displays $\widehat{f}_{\gamma}$, the "show tree" button displays the partition $\widehat{{\cal P}}_\gamma$, and "show both" superimposes $\widehat{{\cal P}}_\gamma$ onto $\widehat{f}_{\gamma}$.
• The "report" button allows to view computation times and properties of the most recently computed global minimization step, such as psnr (in comparison to the original image) and number of active pieces. The button "remove models" removes the results of the local minimization steps, to allow starting over with a new model.

Figure 2: IBB North. $640 \times 480$ (a) Original image, (b) (b) locally constant approximation using 1000 wedges (c) locally affine approximation using 1000 parameters.