Changes between Version 16 and Version 17 of barSoftwareGapFillDetails

Timestamp:

07/28/11 16:33:07 (13 years ago)

Author:

pmajka

Comment:

--

barSoftwareGapFillDetails

@@ -6 +6 @@
 The most common defect encountered in digital (e.g. PDF) versions of published atlases are gaps in structures' outlines. It commonly happens when two contour lines which should touch are drawn so that they leave a little space in between. Such an arrangement may not be visible in a printed atlas but it greatly disturbs tracing process where every pixel may influence the results. In this case the structure being traced overtakes the space of its neighbour through the broken contour which we call leaking of the structure (see figure below).
 
-[[Image(debug_100_99_vBrain_step_0.gif)]]
+  [[Image(debug_100_99_vBrain_step_0.gif)]]
+
+  '''Figure 1''': Examples of gaps in structures contours.
 
 Fragment of rasterized contor slide based on Paxinos and Franklin ''The Mouse Brain In Stereotaxic Coordinates, third edition''.
 
-Leaking structures are handled in 3dBAR by ''gap filling'' algorithm, an extension of the basic tracing procedure. The algorithm requires single input parameter – `MaxGrowLevel` describing maximal size of the gaps that will be closed during tracing of a particular area. The algorithm creates multiple (`n=MaxGrowLevel+1`) copies of initial input bitmap, each with the contours expanded using the [http://en.wikipedia.org/wiki/Dilation_%28morphology%29 dilation filter]  approximately by one pixel.
+Leaking structures are handled in 3dBAR by ''gap filling'' algorithm, an extension of the basic tracing procedure.
+The main idea behind this algorithm is to expand the contours by applying [http://en.wikipedia.org/wiki/Dilation_%28morphology%29 dilation filter] filter until the boundary closes.
 
-[[Image(debug_460_461_VO_step_0-anim.gif)]]
+The algorithm requires single input parameter – `MaxGrowLevel` describing maximal size of the gaps that may be closed during tracing of a particular area. 
 
-Consecutive flood-filled areas are dilated the same number of times as the boundaries were grown to make the area of the resulting path unbiased. If it remains stable or slightly lowers (less than 2% in our implementation) at consecutive stages of the algorithm it means that most probably the boundaries of the structure in question do not have any gaps (see Fig. 3).
+First, the initial bitmap is duplicated. Dilation filter is applied to the copy and the result is
+also cached. This procedure is repeated `MaxGrowLevel` times. Each application of the
+dilation filter causes the boundaries of the structures to grow approximately 1 pixel in diameter.
+As a result, `MaxGrowLevel+1` bitmaps are cached with the first being the rasterized version of the original contour slide (see Figure 2 below).
 
-[[Image(debug_460_461_VO_step_0-anim-AOP.gif)]]
+  [[Image(debug_460_461_VO_step_0-anim.gif)]]
 
-  '''Figure 3''': Structure without gaps does not express significant changes of its area across different stages of algorithm (see table below).
+  '''Figure 2''': Consecutive application of dilation filter to rasterized contour slide.
+
+Structure areas on each cached bitmap are flood-filled and then dilated the same number of times as the boundaries were grown to ensure that the area of the resulting path stays unbiased. If it remains stable or slightly lowers (less than 2% in our implementation) at consecutive stages of the algorithm it means that most probably the boundaries of the structure in question do not have any gaps (see Fig. 3).
+
+  [[Image(debug_460_461_VO_step_0-anim-AOP.gif)]]
+
+  '''Figure 3''': Structure without gaps does not express significant changes of its area across different stages of the algorithm (see table below).
   ||= growlevel =||= area of the structure in pixels =||
   ||  0          ||  51124  ||
@@ -28 +40 @@
 
 
-[[Image(debug_460_461_VO_step_0-anim-VO.gif)]]
+If the reduction of flooded area at certain stage of filter application is grater than defined threshold (15-20% in our implementation), it means that boundary gap must have been closed (see Figure 4 below). After finding the optimal number of border expansions (denoted by `growlevel`) the corresponding bitmap is passed to [http://potrace.sourceforge.net/ PoTrace]. 
+
+  [[Image(debug_460_461_VO_step_0-anim-VO.gif)]]
 
   '''Figure 4''': Structure with gap(s) in it's contour expresses significant changes of its area.
@@ -41 +55 @@
   ||  5          ||  84309  ||
 
-If the reduction of flooded area at certain stage of filter application is grater than defined threshold (15-20% in our implementation), it means that boundary gap must have been closed (see Figure 4 above). After finding the optimal number of border expansions (denoted by `growlevel`) and the bitmap is passed to [http://potrace.sourceforge.net/ PoTrace]. 
 
-The gap filling algorithm is applied individually for each seed label thus different regions may be processed with different value of `GrowLevel`. Information about which `GrowLevel` was used to trace a particular path is stored in its attributes.
+The gap filling algorithm is applied individually for each seed label thus different regions may be processed with different value of `growlevel`. Information about which `growlevel` was used to trace a particular path is stored in its attributes.
 
 === Preconfiguration ===
 
-The gap filling algorithm may also be preconfigured during the preparation of a contour slide. Preconfiguration is carried out by assigning `bar:growlevel`
+The gap filling algorithm may be preconfigured during the preparation of a contour slide. The preconfiguration is carried out by assigning `bar:growlevel`
 attribute to the label used as the seed for tracing. The value of this attribute
 should be an integer between -1 and `MaxGrowLevel`.  Assigning `-1` means
-that `GrowLevel` is undefined and has to be selected automatically, `0` means
+that `growlevel` is undefined and has to be selected automatically, `0` means
 that gap filling should not be used for this particular label. Other values
 denote the number of dilation filter applications. 
@@ -56 +69 @@
 === Algorithm efficacy and limitations ===
 
-Exemplary result of the gap filling algorithm applied to 47 paths from 13th coronal section (2.1mm ant. from bregma) from Paxinos and Franklin ''The Mouse Brain In Stereotaxic Coordinates, third edition''.
+Table below summarizes result of the gap filling algorithm applied to 47 paths from 13th coronal section (2.1mm ant. from bregma) from Paxinos and Franklin ''The Mouse Brain In Stereotaxic Coordinates, third edition''.
 
 ||= optimal grow level =||= number of paths =||
@@ -63 +76 @@
 ||  2       ||  10  ||
 
-The performance of the algorithm depends on the initial size of the structure and on the resolution of input data but in practice, already for structures on the order of diameter around 10 pixels, gap detection works well. Intensive use of this algorithm may distort or even erase the some (particularly narrow) structures. There is no specific mechanism implemented against such behaviour but in practice we have not encountered problems of this type. If a very accurate reconstruction is required, the best policy is to prepare a precise contour slide so there is no need to apply gap filling.
+The performance of the algorithm depends on the initial size of the structure and on the bitmap resolution. Intensive use of this algorithm may distort or even erase some (particularly narrow) structures. There is no specific mechanism implemented against such behaviour. If a very accurate reconstruction is required, the best policy is to carefully prepare contour slides adjusting stroke width and slice resterization resolution so there is no need to apply gap filling.
 
 {{{