1 /**
2 * Copyright (c) 2011, The University of Southampton and the individual contributors.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * * Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * * Neither the name of the University of Southampton nor the names of its
16 * contributors may be used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
23 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
26 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30 package org.openimaj.image.contour;
31
32 import org.openimaj.citation.annotation.Reference;
33 import org.openimaj.citation.annotation.ReferenceType;
34 import org.openimaj.image.FImage;
35 import org.openimaj.image.pixel.Pixel;
36 import org.openimaj.util.function.Operation;
37 import org.openimaj.util.pair.IndependentPair;
38
39 /**
40 * The neighbourhood border/contour tracing algorithm described in Appendix 1 of
41 * the Suzuki contour detection algorithm
42 *
43 * @author Sina Samangooei (ss@ecs.soton.ac.uk)
44 *
45 */
46 @Reference(
47 type = ReferenceType.Article,
48 author = { "Suzuki, S.", "Abe, K." },
49 title = "Topological Structural Analysis of Digitized Binary Image by Border Following",
50 year = "1985",
51 journal = "Computer Vision, Graphics and Image Processing",
52 pages = { "32", "46" },
53 month = "January",
54 number = "1",
55 volume = "30")
56 public class SuzukiNeighborStrategy extends ContourFollowingStrategy {
57 @Override
58 public void contour(FImage image, Pixel start, Pixel from, final Operation<Pixel> operation) {
59 directedContour(image, start, from, new Operation<IndependentPair<Pixel, boolean[]>>() {
60
61 @Override
62 public void perform(IndependentPair<Pixel, boolean[]> object) {
63 operation.perform(object.firstObject());
64 }
65 });
66 }
67
68 /**
69 * Directed contour following.
70 *
71 * @param image
72 * the image
73 * @param ij
74 * the first pixel
75 * @param i2j2
76 * the second pixel
77 * @param operation
78 * the operation to perform
79 */
80 public void
81 directedContour(FImage image, Pixel ij, Pixel i2j2, Operation<IndependentPair<Pixel, boolean[]>> operation)
82 {
83 Direction dir = Direction.fromTo(ij, i2j2);
84 Direction trace = dir.clockwise();
85 // find i1j1 (3.1)
86 Pixel i1j1 = null;
87 while (trace != dir) {
88 final Pixel activePixel = trace.active(image, ij);
89 if (activePixel != null) {
90 i1j1 = activePixel;
91 break;
92 }
93 trace = trace.clockwise();
94 }
95 if (i1j1 == null)
96 return; // operation never called, signals the starting pixel is
97 // alone! (3.1)
98
99 i2j2 = i1j1;
100 Pixel i3j3 = ij; // (3.2)
101 final boolean[] checked = new boolean[] {
102 /*
103 * N , NE ,E ,SE ,S ,SW ,W ,NW
104 */
105 false, false, false, false, false, false, false, false
106 };
107 while (true) {
108 dir = Direction.fromTo(i3j3, i2j2);
109 trace = dir.counterClockwise();
110 Pixel i4j4 = null;
111 resetChecked(checked);
112 while (true) {
113 i4j4 = trace.active(image, i3j3); // 3.3
114 if (i4j4 != null)
115 break;
116 checked[trace.ordinal()] = true;
117 trace = trace.counterClockwise();
118 }
119 operation.perform(IndependentPair.pair(i3j3, checked));
120 if (i4j4.equals(ij) && i3j3.equals(i1j1))
121 break; // 3.5
122 i2j2 = i3j3; // 3.5
123 i3j3 = i4j4; // 3.5
124 }
125 }
126
127 private void resetChecked(boolean[] checked) {
128 for (int i = 0; i < checked.length; i++) {
129 checked[i] = false;
130 }
131 }
132
133 }