001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.image.camera.calibration;
031
032import java.io.IOException;
033import java.net.MalformedURLException;
034import java.util.ArrayList;
035import java.util.Collections;
036import java.util.List;
037
038import org.openimaj.image.FImage;
039import org.openimaj.image.MBFImage;
040import org.openimaj.image.analyser.ImageAnalyser;
041import org.openimaj.image.colour.RGBColour;
042import org.openimaj.image.contour.Contour;
043import org.openimaj.image.contour.SuzukiContourProcessor;
044import org.openimaj.image.processing.algorithm.FilterSupport;
045import org.openimaj.image.processing.algorithm.MinMaxAnalyser;
046import org.openimaj.image.typography.hershey.HersheyFont;
047import org.openimaj.math.geometry.shape.RotatedRectangle;
048import org.openimaj.util.pair.FloatIntPair;
049import org.openimaj.video.VideoDisplay;
050import org.openimaj.video.VideoDisplayAdapter;
051import org.openimaj.video.capture.VideoCapture;
052
053/**
054 * Analyser for performing a fast check to see if a chessboard is in the input
055 * image.
056 * 
057 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
058 */
059public class FastChessboardDetector implements ImageAnalyser<FImage> {
060        private static final float BLACK_LEVEL = 20.f / 255f;
061        private static final float WHITE_LEVEL = 130.f / 255f;
062        private static final float BLACK_WHITE_GAP = 70.f / 255f;
063
064        private static final float MIN_ASPECT_RATIO = 0.3f;
065        private static final float MAX_ASPECT_RATIO = 3.0f;
066        private static final float MIN_BOX_SIZE = 10.0f;
067
068        private int patternHeight;
069        private int patternWidth;
070        private boolean result;
071
072        /**
073         * * Construct with the given pattern size
074         * 
075         * @param patternWidth
076         *            the pattern width
077         * @param patternHeight
078         *            the pattern height
079         */
080        public FastChessboardDetector(int patternWidth, int patternHeight) {
081                this.patternWidth = patternWidth;
082                this.patternHeight = patternHeight;
083        }
084
085        private void quickThresh(FImage in, FImage out, float thresh, boolean inverse) {
086                int low = 0;
087                int high = 1;
088
089                if (inverse) {
090                        low = 1;
091                        high = 0;
092                }
093
094                for (int y = 0; y < in.height; y++) {
095                        for (int x = 0; x < in.width; x++) {
096                                out.pixels[y][x] = in.pixels[y][x] > thresh ? low : high;
097                        }
098                }
099        }
100
101        @Override
102        public void analyseImage(FImage src) {
103                final FImage thresh = new FImage(src.width, src.height);
104
105                final MinMaxAnalyser mma = new MinMaxAnalyser(FilterSupport.BLOCK_3x3);
106                src.analyseWith(mma);
107
108                final FImage white = mma.min;
109                final FImage black = mma.max;
110
111                result = false;
112                for (float threshLevel = BLACK_LEVEL; threshLevel < WHITE_LEVEL && !result; threshLevel += (20.0f / 255f))
113                {
114                        final List<FloatIntPair> quads = new ArrayList<FloatIntPair>();
115
116                        quickThresh(white, thresh, threshLevel + BLACK_WHITE_GAP, false);
117                        getQuadrangleHypotheses(SuzukiContourProcessor.findContours(thresh), quads, 1);
118
119                        quickThresh(black, thresh, threshLevel, true);
120                        getQuadrangleHypotheses(SuzukiContourProcessor.findContours(thresh), quads, 0);
121
122                        final int minQuadsCount = patternWidth * patternHeight / 2;
123                        Collections.sort(quads, FloatIntPair.FIRST_ITEM_ASCENDING_COMPARATOR);
124
125                        // now check if there are many hypotheses with similar sizes
126                        // do this by floodfill-style algorithm
127                        final float sizeRelDev = 0.4f;
128
129                        for (int i = 0; i < quads.size(); i++)
130                        {
131                                int j = i + 1;
132                                for (; j < quads.size(); j++)
133                                {
134                                        if (quads.get(j).first / quads.get(i).first > 1.0f + sizeRelDev)
135                                        {
136                                                break;
137                                        }
138                                }
139
140                                if (j + 1 > minQuadsCount + i)
141                                {
142                                        // check the number of black and white squares
143                                        final int[] counts = new int[2];
144                                        countClasses(quads, i, j, counts);
145                                        final int blackCount = (int) Math.round(Math.ceil(patternWidth / 2.0)
146                                                        * Math.ceil(patternHeight / 2.0));
147                                        final int whiteCount = (int) Math.round(Math.floor(patternWidth / 2.0)
148                                                        * Math.floor(patternHeight / 2.0));
149                                        if (counts[0] < blackCount * 0.75 ||
150                                                        counts[1] < whiteCount * 0.75)
151                                        {
152                                                continue;
153                                        }
154                                        result = true;
155                                        break;
156                                }
157                        }
158                }
159        }
160
161        void countClasses(List<FloatIntPair> pairs, int idx1, int idx2, int[] counts)
162        {
163                // counts.assign(2, 0);
164                // counts[2] = 0; // why?
165                for (int i = idx1; i != idx2; i++)
166                {
167                        counts[pairs.get(i).second]++;
168                }
169        }
170
171        void getQuadrangleHypotheses(Contour contours, List<FloatIntPair> quads, int classId) {
172                for (final Contour seq : contours.contourIterable()) {
173                        // can assume the the contour is simple, thus making convex hull
174                        // computation much faster
175                        final RotatedRectangle box = seq.minimumBoundingRectangle(true);
176
177                        final float boxSize = Math.max(box.width, box.height);
178                        if (boxSize < MIN_BOX_SIZE)
179                        {
180                                continue;
181                        }
182
183                        final float aspectRatio = box.width / Math.max(box.height, 1);
184                        if (aspectRatio < MIN_ASPECT_RATIO || aspectRatio > MAX_ASPECT_RATIO)
185                        {
186                                continue;
187                        }
188                        quads.add(new FloatIntPair(boxSize, classId));
189                }
190        }
191
192        /**
193         * Check whether the last image analysed with {@link #analyseImage(FImage)}
194         * was likely to contain a suitable chessboard pattern.
195         * 
196         * @return true if pattern detected; false otherwise
197         */
198        public boolean chessboardDetected() {
199                return this.result;
200        }
201
202        /**
203         * Simple test program
204         * 
205         * @param args
206         * @throws MalformedURLException
207         * @throws IOException
208         */
209        public static void main(String[] args) throws MalformedURLException, IOException {
210                final FastChessboardDetector fcd = new FastChessboardDetector(9, 6);
211                final VideoDisplay<MBFImage> vd = VideoDisplay.createVideoDisplay(new VideoCapture(640,
212                                480));
213                vd.setCalculateFPS(true);
214                vd.addVideoListener(new VideoDisplayAdapter<MBFImage>() {
215                        @Override
216                        public void beforeUpdate(MBFImage frame) {
217                                fcd.analyseImage(frame.flatten());
218                                frame.drawText(fcd.result + "", 100, 100, HersheyFont.FUTURA_LIGHT,
219                                                20, RGBColour.RED);
220                                System.out.println(vd.getDisplayFPS());
221                        }
222                });
223        }
224}