001 package util.wavelet;
002 import java.util.List;
003
004 /** Set of contiguous wavelet coefficients which exceed a noise threshold.
005 * A structure is defined in a scale with a noise threshold. A structure optionally
006 * contains a reference to its parent structure and a list children structures via
007 * interscale relationships.
008 * A Structure may be a part of a WObject.
009 * A Structure may be due noise if it posseses one of the following properties :
010 * <ol>
011 * <li>It contains very few pixels (the upper limit of which is application specific) and
012 * it is not connected to any other structure via an InterscaleRelationship</li>
013 * <li>It is located near the boundary of the signal, in which case it might be due to boundary effects</li>
014 * </ol>
015 *
016 * @author John Talbot
017 */
018 public class Structure implements Comparable {
019 /** The scale of the wavelet coefficients. Immutable. */
020 Scale scale;
021
022 /** The starting position where the multiresolution support switches from 0 to 1. Immutable. */
023 int start;
024
025 /** The ending position plus 1 where the multiresolution support switches from 1 to 0. Immutable. */
026 int end;
027
028 /** The parent structure. Null if there is no parent. Usually set by interscale relationship constructor. */
029 Structure parent;
030
031 /** The list of children. Empty list indicates no children. Usually set by interscale relationship constructor. */
032 java.util.List<Structure> children = new java.util.ArrayList<Structure>(4);
033
034 /** Set indexOfMaximum to this value to indicate that a LAZY evaluation is required. */
035 static final int NO_POSITION_OF_MAXIMUM = -1;
036
037 /** The index position of the maximum wavelet coefficient within this Structure (Lazy evaluation). Immutable once set. */
038 int positionOfMaximum = NO_POSITION_OF_MAXIMUM;
039
040 /**
041 * Construct the Structure.
042 * @param scale wavelet scale of the wavelet coefficients
043 * @param start starting position where the multiresolution support switches from 0 to 1
044 * @param end ending position plus 1, like Strings etc...)
045 */
046 public Structure(Scale scale, int start, int end) {
047 this.scale = scale;
048 this.start = start;
049 this.end = end;
050 }
051
052 /**
053 * Get the size of the structure as the number of coefficients.
054 * @return the number of coefficients in this structure
055 */
056 public int getSize() {
057 return end - start;
058 }
059
060 /**
061 * Does the given structure overlap this structure
062 * @param structure a structure which we are checking for overlap
063 * @return true if this structure overlaps the given structure
064 */
065 public boolean overlaps(Structure structure) {
066 return getOverlap(structure) != null;
067 }
068
069 /**
070 * Get the overlap structure between this structure and given structure.
071 * The method is symmetric however the structures must reside in scales which differ by exatly 1,
072 * otherwise null is returned.
073 * @param structure the structure in which overlap is sought
074 * @return a structure located in the structure with the largest scale number and containing the overlap between the structures
075 */
076 public Structure getOverlap(Structure structure) {
077 if (Math.abs(structure.getScaleNumber() - getScaleNumber()) != 1) return null;
078 int startOverlap = (getStart() >= structure.getStart()) ? getStart() : structure.getStart();
079 int endOverlap = (getEnd() <= structure.getEnd()) ? getEnd() : structure.getEnd();
080 if (startOverlap < endOverlap) {
081 Structure upperStructure = (getScaleNumber() > structure.getScaleNumber()) ? this : structure;
082 return new Structure(upperStructure.getScale(), startOverlap, endOverlap);
083 } else {
084 return null;
085 }
086 }
087
088 /**
089 * Is the given position contained in this structure.
090 * @param position the position
091 * @return true if the given position is contained in this structure
092 */
093 public boolean contains(int position) {
094 return getStart() <= position && position < getEnd();
095 }
096
097 /**
098 * Get the position of the maximum within this structure.
099 * @return the position of the maximum within this structure
100 */
101 public int getPositionOfMaximum() {
102 if (positionOfMaximum == NO_POSITION_OF_MAXIMUM) { // LAZY evaluation of indexOfMaximum
103 float maximum = -Float.MAX_VALUE; // potential BUG: (is this truly the largest negative floating point number?)
104 for (int i = getStart(); i < getEnd(); i++) {
105 float coefficient = scale.getValue(i);
106 if (coefficient > maximum) {
107 maximum = coefficient;
108 positionOfMaximum = i;
109 }
110 }
111 }
112 return positionOfMaximum;
113 }
114
115 /**
116 * Get the position at which the maximum wavelet coefficient occurs within the given bounds.
117 * Precondition : start ≤ startLocal ≤ end and start ≤ endLocal ≤ end.
118 * @param startLocal the lower boundary defining the range to search
119 * @param endLocal the upper boundary defining the range to search
120 * @return the position of the maximim within the given range
121 */
122 public int getPositionOfMaximum(int startLocal, int endLocal) {
123 float maximum = -Float.MAX_VALUE; // potential BUG: (is this truly the largest negative floating point number?)
124 int localPositionOfMaximum = NO_POSITION_OF_MAXIMUM;
125 for (int i = startLocal; i < endLocal; i++) {
126 float coefficient = scale.getValue(i);
127 if (coefficient > maximum) {
128 maximum = coefficient;
129 localPositionOfMaximum = i;
130 }
131 }
132 return localPositionOfMaximum;
133 }
134
135 /**
136 * Get the maximum wavelet coefficient.
137 * @return the maximum value within the given range
138 */
139 public float getMaximumValue() {
140 return scale.getValue(getPositionOfMaximum());
141 }
142
143 /**
144 * Get the maximum wavelet coefficient within the given range.
145 * @param startLocal the lower boundary defining the range to search
146 * @param endLocal the upper boundary defining the range to search
147 * @return the maximum value within the given range
148 */
149 public float getMaximumValue(int startLocal, int endLocal) {
150 return scale.getValue(getPositionOfMaximum(startLocal, endLocal));
151 }
152
153 /**
154 * Get the wavelet coefficients for this structure (zero everywhere else).
155 * @return the wavelet coefficients of this structure
156 */
157 public SimpleSignal getCoefficients() {
158 return getScale().getSubset(getStart(), getEnd());
159 }
160
161 /**
162 * Get the wavelet coefficients mask for this structure as ones with zeros everywhere else.
163 * @return the wavelet coefficient mask for this structure
164 */
165 public SimpleSignal getCoefficientsMask() {
166 SimpleSignal mask = new SimpleSignal(getScale().size());
167 for (int i = getStart(); i < getEnd(); i++) mask.setValue(i, 1f);
168 return mask;
169 }
170
171 /**
172 * Get the start position of this structure.
173 * @return the start position
174 */
175 public int getStart() {
176 return start;
177 }
178
179 /**
180 * Get the end position of this structure.
181 * @return the end position
182 */
183 public int getEnd() {
184 return end;
185 }
186
187 /**
188 * Get the parent structure or null if unparented.
189 * @return a structure representing a parent or null if unparented
190 */
191 public Structure getParent() {
192 return parent;
193 }
194
195 /**
196 * Set the parent structure. Usually set by the interscale relationship constructor.
197 * @param parent a structure representing a parent
198 */
199 public void setParent(Structure parent) {
200 this.parent = parent;
201 }
202
203 /**
204 * Get a list of children. Empty list if there are no children.
205 * @return a list of children structures
206 */
207 public java.util.List<Structure> getChildren() {
208 return children;
209 }
210
211 /**
212 * Add a child structure. Usually invoked by interscale relationship constructor.
213 * @param child the child structure
214 */
215 public void addChild(Structure child) {
216 children.add(child);
217 }
218
219 /**
220 * Get the scale which contains this structure.
221 * @return the Scale
222 */
223 public Scale getScale() {
224 return scale;
225 }
226
227 /**
228 * Get the scale number which contains this structure.
229 * @return the scale number
230 */
231 public int getScaleNumber() {
232 return scale.getScaleNumber();
233 }
234
235 /**
236 * Implemation of the Comparable interface to ease sorting in WOBject.
237 * @param structure the structure to compare to
238 * @return negative if position of this structure is less, zero if equal and positive if more
239 */
240 public int compareTo(Object structure) { // Can we use the generic version with type T ?
241 Structure structure2 = (Structure) structure;
242 int scaleNumber1 = getScaleNumber();
243 int scaleNumber2 = structure2.getScaleNumber();
244 if (scaleNumber1 != scaleNumber2)
245 return scaleNumber2 - scaleNumber1;
246 else {
247 int position1 = getStart();
248 int position2 = structure2.getStart();
249 if (position1 != position2)
250 return position2 - position1;
251 else {
252 position1 = getEnd();
253 position2 = structure2.getEnd();
254 return position2 - position1;
255 }
256 }
257 }
258
259 }