(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 6.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[     16670,        506]
NotebookOptionsPosition[     15163,        455]
NotebookOutlinePosition[     15581,        471]
CellTagsIndexPosition[     15538,        468]
WindowFrame->Normal
ContainsDynamic->False*)

(* Beginning of Notebook Content *)
Notebook[{

Cell[CellGroupData[{
Cell["Symmetry and the Wraparound Problem", "Title",
 CellChangeTimes->{{3.41811592059375*^9, 3.418115924046875*^9}, {
  3.42182906053125*^9, 3.421829063546875*^9}}],

Cell["\<\
Wavelet Workshop
June 4-7, 2008
University of St. Thomas\
\>", "Subtitle",
 CellChangeTimes->{{3.421426484890625*^9, 3.42142648821875*^9}}],

Cell["\<\
Catherine Beneteau
Caroline Haddad
David Ruch
Patrick Van Fleet\
\>", "Subsubtitle",
 CellChangeTimes->{{3.42144927371875*^9, 3.42144928703125*^9}}],

Cell[CellGroupData[{

Cell["The Problem", "Section",
 CellChangeTimes->{{3.418115960890625*^9, 3.418115965734375*^9}}],

Cell["\<\
Below is a matrix we would use to apply a (5, 3) biorthogonal wavelet \
transform to a vector of length 8:\
\>", "Text",
 CellChangeTimes->{{3.41811597559375*^9, 3.418116021*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"Clear", "[", 
   RowBox[{"ht", ",", "gt"}], "]"}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"r1", "=", 
   RowBox[{"RotateLeft", "[", 
    RowBox[{
     RowBox[{"Join", "[", 
      RowBox[{
       RowBox[{"Array", "[", 
        RowBox[{"ht", ",", "3", ",", 
         RowBox[{"-", "1"}]}], "]"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", 
         RowBox[{"{", "11", "}"}]}], "]"}]}], "]"}], ",", "1"}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Ht", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RotateRight", "[", 
      RowBox[{"r1", ",", 
       RowBox[{"2", "*", "k"}]}], "]"}], ",", 
     RowBox[{"{", 
      RowBox[{"k", ",", "0", ",", "6"}], "}"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"r2", "=", 
   RowBox[{"RotateLeft", "[", 
    RowBox[{
     RowBox[{"Join", "[", 
      RowBox[{
       RowBox[{"Array", "[", 
        RowBox[{"gt", ",", "5", ",", 
         RowBox[{"-", "1"}]}], "]"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", 
         RowBox[{"{", "9", "}"}]}], "]"}]}], "]"}], ",", "1"}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Gt", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RotateRight", "[", 
      RowBox[{"r2", ",", 
       RowBox[{"2", "*", "k"}]}], "]"}], ",", 
     RowBox[{"{", 
      RowBox[{"k", ",", "0", ",", "6"}], "}"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Wt", "=", 
   RowBox[{"Join", "[", 
    RowBox[{"Ht", ",", "Gt"}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{"MatrixForm", "[", "Wt", "]"}]}], "Input",
 CellChangeTimes->{{3.41811604346875*^9, 3.418116121765625*^9}, {
  3.418116546765625*^9, 3.418116637796875*^9}, {3.418117588765625*^9, 
  3.418117589015625*^9}, {3.42182919665625*^9, 3.421829196765625*^9}}],

Cell["\<\
If we use the (5, 3) biorthogonal spline filter pair, on the vector v = \
(1,2,3,4,....,31,32) the output is: \
\>", "Text",
 CellChangeTimes->{{3.41811614009375*^9, 3.41811621990625*^9}}],

Cell[BoxData[{
 RowBox[{"<<", 
  "DiscreteWavelets`DiscreteWavelets`"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"h", ",", "ht"}], "}"}], "=", 
   RowBox[{"SplineFilters", "[", 
    RowBox[{"2", ",", "2"}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"v", "=", 
   RowBox[{"Range", "[", 
    RowBox[{"1", ",", "32"}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{"ListPlot", "[", 
  RowBox[{"v", ",", 
   RowBox[{"PlotStyle", "\[Rule]", 
    RowBox[{"PointSize", "[", ".015", "]"}]}]}], 
  "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"wt", "=", 
   RowBox[{"BWT1D", "[", 
    RowBox[{"v", ",", 
     RowBox[{"{", 
      RowBox[{"h", ",", "ht"}], "}"}], ",", 
     RowBox[{"NumIterations", "\[Rule]", "1"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"WaveletVectorPlot", "[", 
  RowBox[{"wt", ",", 
   RowBox[{"PointSize", "\[Rule]", ".015"}]}], "]"}]}], "Input",
 CellChangeTimes->{{3.41811622390625*^9, 3.41811633478125*^9}, {
  3.41811636525*^9, 3.418116368734375*^9}, {3.418117590078125*^9, 
  3.41811759021875*^9}, {3.421829195078125*^9, 3.4218291951875*^9}}],

Cell["\<\
You see the effects of the three wraparound rows.  In particular, the first \
element of the lowpass portion should be a weighted average of values at the \
beginning of the vector, but instead uses the values 1, 2 and 32.  There are \
two wraparound rows in the highpass portion that cause similar problems.\
\>", "Text",
 CellChangeTimes->{{3.418116376953125*^9, 3.418116514109375*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["The Solution", "Section",
 CellChangeTimes->{{3.4181166480625*^9, 3.418116651515625*^9}}],

Cell[TextData[{
 "For odd - length symmetric filter pairs, we can modify the transform by \
exploiting the symmetry and \"periodizing\" ",
 StyleBox["v",
  FontWeight->"Bold"],
 ".  Here's how.  "
}], "Text",
 CellChangeTimes->{{3.418116656671875*^9, 3.418116730890625*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"v", "=", 
   RowBox[{"{", 
    RowBox[{
    "v1", ",", "v2", ",", "v3", ",", "v4", ",", "v5", ",", "v6", ",", "v7", 
     ",", "v8"}], "}"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{"TableForm", "[", "v", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"vp", "=", 
   RowBox[{"Join", "[", 
    RowBox[{"v", ",", 
     RowBox[{"Reverse", "[", 
      RowBox[{"Take", "[", 
       RowBox[{"v", ",", 
        RowBox[{"{", 
         RowBox[{"2", ",", "7"}], "}"}]}], "]"}], "]"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"TableForm", "[", "vp", "]"}]}], "Input",
 CellChangeTimes->{{3.418095397640625*^9, 3.418095419484375*^9}, {
  3.4181167415*^9, 3.41811675196875*^9}, {3.418117591671875*^9, 
  3.418117591828125*^9}, {3.421829193484375*^9, 3.42182919359375*^9}}],

Cell[TextData[{
 "We next apply the top portion of the biorthogonal wavelet transform to ",
 StyleBox["vp",
  FontWeight->"Bold"],
 "."
}], "Text",
 CellChangeTimes->{{3.4181167671875*^9, 3.418116814484375*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"Clear", "[", "ht", "]"}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"r1", "=", 
   RowBox[{"RotateLeft", "[", 
    RowBox[{
     RowBox[{"Join", "[", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"a", ",", "b", ",", "c"}], "}"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", 
         RowBox[{"{", "11", "}"}]}], "]"}]}], "]"}], ",", "1"}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Ht", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RotateRight", "[", 
      RowBox[{"r1", ",", 
       RowBox[{"2", "*", "k"}]}], "]"}], ",", 
     RowBox[{"{", 
      RowBox[{"k", ",", "0", ",", "6"}], "}"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"MatrixForm", "[", "Ht", "]"}], "\[IndentingNewLine]", 
 RowBox[{"TableForm", "[", 
  RowBox[{"Ht", ".", "vp"}], "]"}]}], "Input",
 CellChangeTimes->{{3.4180954513125*^9, 3.418095511328125*^9}, {
   3.418095557625*^9, 3.418095559671875*^9}, {3.41809564446875*^9, 
   3.418095671484375*^9}, 3.418116035609375*^9, {3.41811681640625*^9, 
   3.418116853953125*^9}, {3.41811759353125*^9, 3.418117593671875*^9}, {
   3.42182919159375*^9, 3.421829191703125*^9}}],

Cell["\<\
At first glance, there is nothing special happening.  But let's redo the \
computation and make the elements in ht symmetric.\
\>", "Text",
 CellChangeTimes->{{3.418116860875*^9, 3.418116918171875*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"r1", "=", 
   RowBox[{"RotateLeft", "[", 
    RowBox[{
     RowBox[{"Join", "[", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"a", ",", "b", ",", "a"}], "}"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", 
         RowBox[{"{", "11", "}"}]}], "]"}]}], "]"}], ",", "1"}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Ht", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RotateRight", "[", 
      RowBox[{"r1", ",", 
       RowBox[{"2", "*", "k"}]}], "]"}], ",", 
     RowBox[{"{", 
      RowBox[{"k", ",", "0", ",", "6"}], "}"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"MatrixForm", "[", "Ht", "]"}], "\[IndentingNewLine]", 
 RowBox[{"TableForm", "[", 
  RowBox[{"Ht", ".", "vp"}], "]"}]}], "Input",
 CellChangeTimes->{{3.41809564725*^9, 3.41809565103125*^9}, {
  3.418116924515625*^9, 3.418116926828125*^9}, {3.418117595640625*^9, 
  3.418117595765625*^9}, {3.421829117734375*^9, 3.421829118515625*^9}, {
  3.421829190203125*^9, 3.42182919034375*^9}}],

Cell["\<\
The first element is a weighted average of the first TWO elements in v and \
the last three elements are mirror images of elements 2 - 4.  Moreover, \
elements 2 - 4 are the results we expect when we apply the BWT to v!!

So we take as the lowpass portion the first four elements of the output!

We can do the same sort of thing with the highpass portion:\
\>", "Text",
 CellChangeTimes->{{3.418116934953125*^9, 3.418117053046875*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"r2", "=", 
   RowBox[{"RotateLeft", "[", 
    RowBox[{
     RowBox[{"Join", "[", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"d", ",", "e", ",", "f", ",", "g", ",", "i"}], "}"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", 
         RowBox[{"{", "9", "}"}]}], "]"}]}], "]"}], ",", "1"}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Gt", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RotateRight", "[", 
      RowBox[{"r2", ",", 
       RowBox[{"2", "*", "k"}]}], "]"}], ",", 
     RowBox[{"{", 
      RowBox[{"k", ",", "0", ",", "6"}], "}"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"MatrixForm", "[", "Gt", "]"}]}], "Input",
 CellChangeTimes->{{3.418095692421875*^9, 3.418095743953125*^9}, {
   3.418095793328125*^9, 3.4180958136875*^9}, {3.418117063875*^9, 
   3.418117066265625*^9}, {3.4181175975*^9, 3.418117597625*^9}, 
   3.421829135484375*^9, {3.421829188875*^9, 3.421829189*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"r2", "=", 
   RowBox[{"RotateLeft", "[", 
    RowBox[{
     RowBox[{"Join", "[", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{
         RowBox[{"-", "d"}], ",", "e", ",", 
         RowBox[{"-", "f"}], ",", "e", ",", 
         RowBox[{"-", "d"}]}], "}"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", 
         RowBox[{"{", "9", "}"}]}], "]"}]}], "]"}], ",", "1"}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Gt", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RotateRight", "[", 
      RowBox[{"r2", ",", 
       RowBox[{"2", "*", "k"}]}], "]"}], ",", 
     RowBox[{"{", 
      RowBox[{"k", ",", "0", ",", "6"}], "}"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"MatrixForm", "[", "Gt", "]"}], "\[IndentingNewLine]", 
 RowBox[{"TableForm", "[", 
  RowBox[{"Gt", ".", "vp"}], "]"}]}], "Input",
 CellChangeTimes->{{3.418095770546875*^9, 3.41809577915625*^9}, {
  3.4181170799375*^9, 3.418117116625*^9}, {3.41811759921875*^9, 
  3.41811759934375*^9}, {3.42182918759375*^9, 3.421829187734375*^9}}],

Cell["\<\
Note now that the two wraparound rows have been replaced by weighted \
differences of the first four and last three elements in v, respectively.  \
The two middle rows are what we would get if we applied the BWT to v, and the \
last three elements are mirror images of the first three elements.  So we \
take as the highpass portion the first four elements of the output!!\
\>", "Text",
 CellChangeTimes->{{3.418117125890625*^9, 3.418117210578125*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["The Wraparound Fix", "Section",
 CellChangeTimes->{{3.418117213546875*^9, 3.41811722146875*^9}}],

Cell[TextData[{
 "If (h, ht) is an odd-length biorthogonal filter pair and we wish to apply \
it to vector v of length N and avoid wraparound effects, we do the following:\
\n\n1) For the 2N-2 length vector ( ",
 Cell[BoxData[
  RowBox[{
   SubscriptBox["v", "1"], ",", "...", ",", " ", 
   SubscriptBox["v", "N"], ",", " ", 
   SubscriptBox["v", 
    RowBox[{"N", "-", "1"}]], ",", " ", "...", " ", ",", 
   SubscriptBox["v", "2"]}]]],
 ")\n2) Apply the BWT to this vector\n3) Keep the first N/2 elements of the \
lowpass portion and the highpass portion, respectively as our modified \
wavelet transform."
}], "Text",
 CellChangeTimes->{{3.418117228828125*^9, 3.41811731965625*^9}, {
  3.418117459578125*^9, 3.41811749771875*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["A Numerical Example", "Section",
 CellChangeTimes->{{3.418117331703125*^9, 3.41811733453125*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"v", "=", 
   RowBox[{"Range", "[", 
    RowBox[{"1", ",", "32"}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"h", ",", "ht"}], "}"}], "=", 
   RowBox[{"SplineFilters", "[", 
    RowBox[{"2", ",", "2"}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"wt1", "=", 
   RowBox[{"BWT1D", "[", 
    RowBox[{"v", ",", 
     RowBox[{"{", 
      RowBox[{"h", ",", "ht"}], "}"}], ",", 
     RowBox[{"NumIterations", "\[Rule]", "1"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"wt2", "=", 
   RowBox[{"BWT1D", "[", 
    RowBox[{"v", ",", 
     RowBox[{"{", 
      RowBox[{"h", ",", "ht"}], "}"}], ",", 
     RowBox[{"NumIterations", "\[Rule]", "1"}], ",", 
     RowBox[{"Boundary", "\[Rule]", "Reflective"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"ListPlot", "[", 
  RowBox[{"v", ",", 
   RowBox[{"PlotStyle", "\[Rule]", 
    RowBox[{"PointSize", "[", ".015", "]"}]}]}], 
  "]"}], "\[IndentingNewLine]", 
 RowBox[{"WaveletVectorPlot", "[", 
  RowBox[{"wt1", ",", 
   RowBox[{"PointSize", "\[Rule]", ".015"}], ",", 
   RowBox[{"PlotLabel", "\[Rule]", "\"\<Wraparound Rows\>\""}]}], 
  "]"}], "\[IndentingNewLine]", 
 RowBox[{"WaveletVectorPlot", "[", 
  RowBox[{"wt2", ",", 
   RowBox[{"PointSize", "\[Rule]", ".015"}], ",", 
   RowBox[{"PlotLabel", "\[Rule]", "\"\<No Wraparound Rows\>\""}]}], 
  "]"}]}], "Input",
 CellChangeTimes->{{3.4181173396875*^9, 3.418117446125*^9}, {
  3.4181176010625*^9, 3.418117601203125*^9}, {3.4218291858125*^9, 
  3.42182918596875*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["Questions", "Section",
 CellChangeTimes->{{3.418117503703125*^9, 3.418117504359375*^9}}],

Cell["\<\
Here are some questions :

1) How would you (if possible) invert the process??  
2) If you can invert the process, can you write down the matrix that yields \
the modified transform and its inverse?
3) How do you modify the process for even length filter pairs?
4) Does this idea work if the filters are NOT symmetric?\
\>", "Text",
 CellChangeTimes->{{3.4181175124375*^9, 3.418117573171875*^9}, {
  3.418117604625*^9, 3.418117615671875*^9}}]
}, Open  ]]
}, Open  ]]
},
WindowSize->{1016, 651},
WindowMargins->{{0, Automatic}, {Automatic, 0}},
FrontEndVersion->"6.0 for Microsoft Windows (32-bit) (April 20, 2007)",
StyleDefinitions->FrontEnd`FileName[{"Creative"}, "NaturalColor.nb", 
  CharacterEncoding -> "WindowsANSI"]
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[590, 23, 165, 2, 73, "Title"],
Cell[758, 27, 149, 5, 96, "Subtitle"],
Cell[910, 34, 158, 6, 89, "Subsubtitle"],
Cell[CellGroupData[{
Cell[1093, 44, 96, 1, 75, "Section"],
Cell[1192, 47, 189, 4, 29, "Text"],
Cell[1384, 53, 1874, 57, 162, "Input"],
Cell[3261, 112, 198, 4, 29, "Text"],
Cell[3462, 118, 1136, 31, 142, "Input"],
Cell[4601, 151, 398, 6, 47, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[5036, 162, 95, 1, 75, "Section"],
Cell[5134, 165, 274, 7, 29, "Text"],
Cell[5411, 174, 815, 21, 102, "Input"],
Cell[6229, 197, 211, 6, 29, "Text"],
Cell[6443, 205, 1207, 32, 122, "Input"],
Cell[7653, 239, 212, 4, 29, "Text"],
Cell[7868, 245, 1057, 29, 102, "Input"],
Cell[8928, 276, 445, 9, 119, "Text"],
Cell[9376, 287, 997, 27, 82, "Input"],
Cell[10376, 316, 1099, 31, 102, "Input"],
Cell[11478, 349, 462, 7, 65, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[11977, 361, 102, 1, 75, "Section"],
Cell[12082, 364, 732, 16, 101, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[12851, 385, 103, 1, 75, "Section"],
Cell[12957, 388, 1592, 45, 162, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[14586, 438, 94, 1, 75, "Section"],
Cell[14683, 441, 452, 10, 119, "Text"]
}, Open  ]]
}, Open  ]]
}
]
*)

(* End of internal cache information *)