/**
 * Copyright (c) 2011, The University of Southampton and the individual contributors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 *   *  Redistributions of source code must retain the above copyright notice,
 *      this list of conditions and the following disclaimer.
 *
 *   *  Redistributions in binary form must reproduce the above copyright notice,
 *      this list of conditions and the following disclaimer in the documentation
 *      and/or other materials provided with the distribution.
 *
 *   *  Neither the name of the University of Southampton nor the names of its
 *      contributors may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.openimaj.image.feature.dense.binarypattern;

import gnu.trove.list.array.TIntArrayList;
import gnu.trove.map.hash.TIntObjectHashMap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.openimaj.citation.annotation.Reference;
import org.openimaj.citation.annotation.ReferenceType;
import org.openimaj.image.FImage;
import org.openimaj.image.pixel.Pixel;

/**
 * Class for determining whether specific binary patterns are "uniform". Uniform
 * patterns have less than one 01 transition and one 01 transition when viewed
 * as a circular buffer.
 * <p>
 * The class caches lookup tables of uniform patterns on demand, with the
 * exception of the commonly used 8-bit patterns which are cached on
 * initialization.
 * 
 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
 * 
 */
@Reference(
                type = ReferenceType.Article,
                author = { "Ojala, T.", "Pietikainen, M.", "Maenpaa, T." },
                title = "Multiresolution gray-scale and rotation invariant texture classification with local binary patterns",
                year = "2002",
                journal = "Pattern Analysis and Machine Intelligence, IEEE Transactions on",
                pages = { "971 ", "987" },
                month = "jul",
                number = "7",
                volume = "24",
                customData = {
                                "doi", "10.1109/TPAMI.2002.1017623",
                                "ISSN", "0162-8828"
                })
public class UniformBinaryPattern {
        protected static TIntObjectHashMap<TIntArrayList> lut = new TIntObjectHashMap<TIntArrayList>();

        static {
                // pre-cache the table for 8-bit patterns as it is common
                lut.put(8, calculateUniformPatterns(8));
                // other patterns will be cached on demand
        }

        protected static TIntArrayList calculateUniformPatterns(int nbits) {
                final TIntArrayList result = new TIntArrayList();

                final boolean[] bits = new boolean[nbits];

                for (int i = 0; i < Math.pow(2, nbits); i++) {
                        Arrays.fill(bits, false);

                        for (int temp = i, j = 1; j <= nbits; j++) {
                                final int pow = (int) Math.pow(2, (nbits - j));

                                if (temp / pow > 0) {
                                        bits[j - 1] = true;
                                }
                                temp = temp % pow;
                        }

                        if (isUniform(bits)) {
                                result.add(i);
                        }
                }

                return result;
        }

        protected static boolean isUniform(boolean[] pattern) {
                int count = 0;

                for (int i = 0; i < pattern.length - 1; i++) {
                        if (pattern[i] != pattern[i + 1]) {
                                count++;
                        }
                }

                return count <= 2;
        }

        /**
         * Get a list of all the binary patterns of a given length that are
         * "uniform". Uniform patterns have less than one 01 transition and one 01
         * transition when viewed as a circular buffer.
         * 
         * The length must be between 1 and 32 bits.
         * 
         * @param nbits
         *            pattern length
         * @return set of patterns encoded as integers
         */
        public static TIntArrayList getUniformPatterns(int nbits) {
                if (nbits < 1 || nbits > 32)
                        throw new IllegalArgumentException("Only patterns with lengths between 1 and 32 bits are supported");

                TIntArrayList patterns = lut.get(nbits);

                if (patterns == null) {
                        patterns = calculateUniformPatterns(nbits);
                        lut.put(nbits, patterns);
                }

                return patterns;
        }

        /**
         * Check whether the given nbits pattern is uniform.
         * 
         * @param pattern
         *            the pattern
         * @param nbits
         *            the pattern length
         * @return true if uniform; false otherwise.
         */
        public static boolean isPatternUniform(int pattern, int nbits) {
                return getUniformPatterns(nbits).contains(pattern);
        }

        /**
         * Compute a binary map showing the locations of the specified pattern code.
         * 
         * @param patternImage
         *            the pattern data
         * @param code
         *            the code to extract
         * @return a binary {@link FImage} depicting the locations of the given code
         */
        public static FImage extractPatternImage(int[][] patternImage, int code) {
                final FImage image = new FImage(patternImage[0].length, patternImage.length);

                for (int y = 0; y < image.height; y++) {
                        for (int x = 0; x < image.width; x++) {
                                if (patternImage[y][x] == code) {
                                        image.pixels[y][x] = 1;
                                }
                        }
                }

                return image;
        }

        /**
         * Compute all binary maps for each possible pattern code given the number
         * of bits used to encode patterns.
         * 
         * @param patternImage
         *            the pattern data
         * @param nbits
         *            the number of bits for the patterns
         * @return an array of binary maps corresponding to each pattern
         */
        public static FImage[] extractPatternImages(int[][] patternImage, int nbits) {
                final TIntArrayList uniformPatterns = getUniformPatterns(nbits);

                final FImage[] images = new FImage[uniformPatterns.size() + 1];
                final int width = patternImage[0].length;
                final int height = patternImage.length;

                for (int y = 0; y < height; y++) {
                        for (int x = 0; x < width; x++) {
                                final int idx = uniformPatterns.indexOf(patternImage[y][x]);

                                if (images[idx + 1] == null) {
                                        images[idx + 1] = new FImage(width, height);
                                }

                                images[idx + 1].pixels[y][x] = 1;
                        }
                }

                return images;
        }

        /**
         * Compute all binary maps for each possible pattern code given the number
         * of bits used to encode patterns.
         * 
         * @param patternImage
         *            the pattern data
         * @param nbits
         *            the number of bits for the patterns
         * @return an array of binary maps corresponding to each pattern
         */
        public static boolean[][][] extractPatternMaps(int[][] patternImage, int nbits) {
                final TIntArrayList uniformPatterns = getUniformPatterns(nbits);

                final int width = patternImage[0].length;
                final int height = patternImage.length;
                final boolean[][][] maps = new boolean[uniformPatterns.size() + 1][height][width];

                for (int y = 0; y < height; y++) {
                        for (int x = 0; x < width; x++) {
                                final int idx = uniformPatterns.indexOf(patternImage[y][x]);

                                maps[idx + 1][y][x] = true;
                        }
                }

                return maps;
        }

        /**
         * Compute all pixels matching each possible pattern code given the number
         * of bits used to encode patterns.
         * 
         * @param patternImage
         *            the pattern data
         * @param nbits
         *            the number of bits for the patterns
         * @return an array of binary maps corresponding to each pattern
         */
        public static List<List<Pixel>> extractPatternPixels(int[][] patternImage, int nbits) {
                final TIntArrayList uniformPatterns = getUniformPatterns(nbits);

                final List<List<Pixel>> images = new ArrayList<List<Pixel>>(uniformPatterns.size() + 1);
                final int width = patternImage[0].length;
                final int height = patternImage.length;

                for (int i = 0; i < uniformPatterns.size() + 1; i++)
                        images.add(null);

                for (int y = 0; y < height; y++) {
                        for (int x = 0; x < width; x++) {
                                final int idx = uniformPatterns.indexOf(patternImage[y][x]);

                                if (images.get(idx + 1) == null) {
                                        images.set(idx + 1, new ArrayList<Pixel>());
                                }

                                images.get(idx + 1).add(new Pixel(x, y));
                        }
                }

                return images;
        }
}