Fractals/Iterations in the complex plane/btm

How to identify outer boundaries in a 2D grid of points? names boundary delineation edge detection contour tracing Types one component at a time ( boundary tracing) all components at a time ( edge detection) BTM Boundary trace method ( BTM) wikipedia : boundary tracing Image Processing, Analysis, and Machine Vision Milan Sonka, Vaclav Hlavac, and Roger Boyle Boundary tracing of a binary digital region can be thought of as a segmentation technique that identifies the boundary pixels of the digital region. Boundary tracing is an important first step in the analysis of that region. definition Boundary is a topological notion. However, a digital image is no topological space. Therefore, it is impossible to define the notion of a boundary in a digital image mathematically exactly. Most publications about tracing the boundary of a subset S of a digital image I describe algorithms which find a set of pixels belonging to S and having in their direct neighborhood pixels belonging both to S and to its complement I - S. According to this definition the boundary of a subset S is different from the boundary of the complement I – S which is a topological paradox. To define the boundary correctly it is necessary to introduce a topological space corresponding to the given digital image. Such space can be a two-dimensional abstract cell complex. It contains cells of three dimensions: the two-dimensional cells corresponding to pixels of the digital image, the one-dimensional cells or “cracks” representing short lines lying between two adjacent pixels, and the zero-dimensional cells or “points” corresponding to the corners of pixels. The boundary of a subset S is then a sequence of cracks and points while the neighborhoods of these cracks and points intersect both the subset S and its complement I – S. The boundary defined in this way corresponds exactly to the topological definition and corresponds also to our intuitive imagination of a boundary because the boundary of S should contain neither elements of S nor those of its complement. It should contain only elements lying between S and the complement. This are exactly the cracks and points of the complex. This method of tracing boundaries is described in the book of Vladimir A. KovalevskyKovalevsky, V., Image Processing with Cellular Topology, Springer 2021, and in the web site.http://www.kovalevsky.de, Lecture "Tracing Boundaries in 2D Images" Algorithms Algorithms used for boundary tracing:Contour Tracing Algorithms Square tracing algorithmAbeer George Ghuneim: square tracing algorithm Moore-neighbor tracing algorithm Radial sweep Abeer George Ghuneim: The Radial Sweep algorithm Theo Pavlidis’ algorithm Abeer George Ghuneim: Theo Pavlidis' Algorithm A generic approach using vector algebra for tracing of a boundary can be found at.Vector Algebra Based Tracing of External and Internal Boundary of an Object in Binary Images, Journal of Advances in Engineering Science Volume 3 Issue 1, January–June 2010, PP 57–70 An extension of boundary tracing for segmentation of traced boundary into open and closed sub-section is described at.Graph theory based segmentation of traced boundary into open and closed sub-sections, Computer Vision and Image Understanding, Volume 115, Issue 11, November 2011, pages 1552–1558 Square tracing algorithm The square tracing algorithm is simple, yet effective. Its behavior is completely based on whether one is on a black, or a white cell (assuming white cells are part of the shape). First, scan from the upper left to right and row by row. Upon entering your first white cell, the core of the algorithm starts. It consists mainly of two rules: If you are in a white cell, go left. If you are in a black cell, go right. Keep in mind that it matters how you entered the current cell, so that left and right can be defined. public void GetBoundary(byte[,] image) { for (int j = 0; j < image.GetLength(1); j++) for (int i = 0; i < image.GetLength(0); i++) if (image[i, j] == 255) // Found first white pixel SquareTrace(new Point(i, j)); } public void SquareTrace(Point start) { HashSet<Point> boundaryPoints = new HashSet<Point>(); // Use a HashSet to prevent double occurrences // We found at least one pixel boundaryPoints.Add(start); // The first pixel you encounter is a white one by definition, so we go left. // Our initial direction was going from left to right, hence (1, 0) Point nextStep = GoLeft(new Point(1, 0)); Point next = start + nextStep; while (next != start) { // We found a black cell, so we go right and don't add this cell to our HashSet if (image[next.x, next.y] == 0) { next = next - nextStep; nextStep = GoRight(nextStep); next = next + nextStep; } // Alternatively we found a white cell, we do add this to our HashSet else { boundaryPoints.Add(next); nextStep = GoLeft(nextStep); next = next + nextStep; } } } private Point GoLeft(Point p) => new Point(p.y, -p.x); private Point GoRight(Point p) => new Point(-p.y, p.x); Moore-neighbor tracing algorithm thumb|The Moore neighborhood is composed of nine cells: a central cell and the eight cells which surround it. The idea behind the formulation of Moore neighborhood is to find the contour of a given graph. This idea was a great challenge for most analysts of the 18th century, and as a result an algorithm was derived from the Moore graph which was later called the Moore Neighborhood algorithm. Algorithm:codeproject article: tracing-boundary-in-d-image-using-moore-neighborho by Udaya K Unnikrishnan Traverse 2D matrix in row wise Set the first nonzero pixel as S(Starting of the boundary) Set the current pixel as p ; Add this non zero pixel into a boundary pixel list Set the previous pixel from where p is entered as b (Backtracked pixel ) Take a 3 * 3 neighborhood of p and search for the next clockwise nonzero pixel from b in clockwise direction Repeat the steps 3 to 5 until p is same as S The pseudocode for the Moore-Neighbor tracing algorithm is Input: A square tessellation, T, containing a connected component P of black cells. Output: A sequence B (b1, b2, ..., bk) of boundary pixels i.e. the contour. Define M(a) to be the Moore neighborhood of pixel a. Let p denote the current boundary pixel. Let c denote the current pixel under consideration i.e. c is in M(p). Let b denote the backtrack of c (i.e. neighbor pixel of p that was previously tested) Begin Set B to be empty. From bottom to top and left to right scan the cells of T until a black pixel, s, of P is found. Insert s in B. Set the current boundary point p to s i.e. p=s Let b = the pixel from which s was entered during the image scan. Set c to be the next clockwise pixel (from b) in M(p). While c not equal to s do If c is black insert c in B Let b = p Let p = c (backtrack: move the current pixel c to the pixel from which p was entered) Let c = next clockwise pixel (from b) in M(p). else (advance the current pixel c to the next clockwise pixel in M(p) and update backtrack) Let b = c Let c = next clockwise pixel (from b) in M(p). end If end While End Termination condition The original termination condition was to stop after visiting the start pixel for the second time. This limits the set of contours the algorithm will walk completely. An improved stopping condition proposed by Jacob Eliosoff is to stop after entering the start pixel for the second time in the same direction you originally entered it. BSM/J BSM = Boundary Scanning Method This algorithm is used when dynamical plane consist of two of more basins of attraction. For example for c=0. It is not appropiate when interior of filled Julia set is empty, for example for c=i. Description of algorithm : for every pixel of dynamical plane do : compute 4 corners ( vertices) of pixel ( where lt denotes left top, rb denotes right bottom, ... ) check to which basin corner belongs ( standard escape time and bailout test ) if corners do not belong to the same basin mark it as Julia set Examples of code program in PascalPascal program fo BSM/J by Morris W. Firebaugh via convolution with a kernel Boundary scanning and complex dynamics by Mark McClure Dictionary image 2D “segmented” image (an image with foreground pixels labeled 1 and background pixels labeled zero) = binary image connectedness and neighberhood 4 8 boundary = boundary contour = contour inner boundary (outermost pixels of foreground) outer boundary (innermost pixels of background): trace ( tracing) Contour Tracing Algorithms by Abeer George Ghuneim papers Boundary tracing in binary images Wilhelm Burger · Mark J. Burge: Digital Image Processing An algorithmic introduction using Java Video Mandelbrot Animation (Boundary Tracing / Recursion) by Gnarly Charley Code fractint Java code ( from the video) by Gnarly Charley ( charlesk26 ) Tracing Boundary in 2D Image Using Moore Neighborhood Approach in C++ by Udaya K Unnikrishnan Moore Neighbor Contour Tracing Algorithm in C++ BY ERIK SMISTAD Potrace(TM) is a tool for tracing a bitmap by Peter Selinger Traces the boundary of a set of points ( python) Source code for 'Modern Algorithms for Image Processing' by Vladimir Kovalevsky See also Pathfinding Curve sketching Chain code Pixel connectivity Optimization problem Hole Detection boundary cleaning: the jagged boundaries are cleaned (smoothed) in order to obtain a pleasant shape References