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.model.asm;
031
032import java.util.ArrayList;
033import java.util.List;
034
035import org.openimaj.citation.annotation.Reference;
036import org.openimaj.citation.annotation.ReferenceType;
037import org.openimaj.citation.annotation.References;
038import org.openimaj.image.FImage;
039import org.openimaj.image.Image;
040import org.openimaj.image.analysis.pyramid.SimplePyramid;
041import org.openimaj.image.model.asm.ActiveShapeModel.IterationResult;
042import org.openimaj.image.model.landmark.LandmarkModel;
043import org.openimaj.image.model.landmark.LandmarkModelFactory;
044import org.openimaj.image.processor.SinglebandImageProcessor;
045import org.openimaj.math.geometry.point.PointList;
046import org.openimaj.math.geometry.shape.PointDistributionModel;
047import org.openimaj.math.geometry.shape.PointDistributionModel.Constraint;
048import org.openimaj.math.geometry.transforms.TransformUtilities;
049import org.openimaj.math.matrix.algorithm.pca.PrincipalComponentAnalysis.ComponentSelector;
050import org.openimaj.util.pair.IndependentPair;
051
052import Jama.Matrix;
053
054/**
055 * Implementation of a basic Multi-resolution Active Shape Model. 
056 * The implementation allows different types of landmark appearance 
057 * models and can work with both colour and greylevel images.
058 * 
059 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
060 * 
061 * @param <I> Concrete type of {@link Image}
062 */
063@References(references = { 
064                @Reference(
065                                author = { "Cootes, T. F.", "Taylor, C. J." }, 
066                                title = "Statistical Models of Appearance for Computer Vision", 
067                                type = ReferenceType.Unpublished,
068                                month = "October",
069                                year = "2001",
070                                url = "http://isbe.man.ac.uk/~bim/Models/app_model.ps.gz"
071                ),
072                @Reference(
073                                type = ReferenceType.Inproceedings,
074                                author = { "Cootes, T F", "Taylor, C J", "Lanitis, A" },
075                                title = "Active shape models: Evaluation of a multi-resolution method for improving image search",
076                                year = "1994",
077                                booktitle = "Proc British Machine Vision Conference",
078                                pages = { "327", "", "336" },
079                                url = "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.141.4937&rep=rep1&type=pdf",
080                                editor = { "Hancock, E" },
081                                publisher = "BMVA Press",
082                                volume = "1"
083                )
084})
085public class MultiResolutionActiveShapeModel<I extends Image<?, I> & SinglebandImageProcessor.Processable<Float,FImage,I>> {
086        private int numLevels; //num resolutions
087        private ActiveShapeModel<I>[] asms;
088        private static float sigma = 0.5f;
089
090        /**
091         * Construct a {@link MultiResolutionActiveShapeModel} from the
092         * stack of provided {@link ActiveShapeModel}s. The ASMs should
093         * be arranged in order of decreasing resolution.
094         * 
095         * @param asms
096         */
097        public MultiResolutionActiveShapeModel(ActiveShapeModel<I>[] asms) {
098                this.numLevels = asms.length;
099                this.asms = asms;
100        }
101
102        /**
103         * Train a new {@link MultiResolutionActiveShapeModel} from the given
104         * data.
105         * 
106         * @param <I> Concrete type of {@link Image}
107         * @param numLevels number of levels in the pyramid (scales)
108         * @param selector a {@link ComponentSelector} for choosing significant EVs
109         * @param data annotated images for training
110         * @param constraint a {@link Constraint} for constraining plausible shapes from the {@link PointDistributionModel}.
111         * @param factory a {@link LandmarkModelFactory} for producing models of local appearance around the landmarks.
112         * @return a newly trained {@link MultiResolutionActiveShapeModel}.
113         */
114        public static <I extends Image<?, I> & SinglebandImageProcessor.Processable<Float,FImage,I>> MultiResolutionActiveShapeModel<I> 
115        trainModel(int numLevels, ComponentSelector selector, List<IndependentPair<PointList, I>> data, Constraint constraint, LandmarkModelFactory<I> factory) {
116                int nPoints = data.get(0).firstObject().size();
117
118                @SuppressWarnings("unchecked")
119                LandmarkModel<I>[][] ppms = new LandmarkModel[numLevels][nPoints];
120
121                for (int i=0; i<data.size(); i++) {
122                        SimplePyramid<I> pyr = SimplePyramid.createGaussianPyramid(data.get(i).secondObject(), sigma, numLevels);
123                        PointList pl = data.get(i).firstObject();
124
125                        for (int level=0; level<numLevels; level++) {
126                                Matrix scaling = TransformUtilities.scaleMatrix(1.0/Math.pow(2, level), 1.0/Math.pow(2, level));
127                                PointList tfpl = pl.transform(scaling);
128                                I image = pyr.pyramid[level];
129
130                                for (int j=0; j<nPoints; j++) {
131                                        if (ppms[level][j] == null) {
132                                                //scale so the effective search area gets bigger with levels
133                                                //i.e. if the "size" of the search area is 0.1 in the 0th level,
134                                                //it would be 0.1 * scaleFactor in the 1st level and thus cover
135                                                //more of the image
136                                                ppms[level][j] = factory.createLandmarkModel((float) Math.pow(2, level));
137                                        }
138
139                                        ppms[level][j].updateModel(image, tfpl.get(j), tfpl);
140                                }
141                        }
142                }
143
144                List<PointList> pls = new ArrayList<PointList>();
145                for (IndependentPair<PointList, I> i : data)
146                        pls.add(i.firstObject());
147
148                PointDistributionModel pdm = new PointDistributionModel(constraint, pls);
149                pdm.setNumComponents(selector);
150
151                @SuppressWarnings("unchecked")
152                ActiveShapeModel<I> [] asms = new ActiveShapeModel[numLevels]; 
153                for (int level=0; level<numLevels; level++) {
154                        asms[level] = new ActiveShapeModel<I>(pdm, ppms[level]);
155                }
156
157                return new MultiResolutionActiveShapeModel<I>(asms);
158        }
159
160        /**
161         * Perform multi-resolution fitting of the initial shape to
162         * the initial image.
163         * 
164         * @param initialImage the initial shape.
165         * @param initialShape the initial image.
166         * @return the fitted model parameters.
167         */
168        public IterationResult fit(I initialImage, PointList initialShape) {
169                SimplePyramid<I> pyr = SimplePyramid.createGaussianPyramid(initialImage, sigma, numLevels);
170
171                Matrix scaling = TransformUtilities.scaleMatrix(1.0/Math.pow(2, numLevels-1), 1.0/Math.pow(2, numLevels-1));
172
173                PointList shape = initialShape.transform(scaling);
174                Matrix pose = null;
175                double [] parameters = null;
176
177                double fit = 0;
178                for (int level=numLevels-1; level>=0; level--) {
179                        I image = pyr.pyramid[level];
180
181                        ActiveShapeModel<I> asm = asms[level];
182
183                        IterationResult newData = asm.fit(image, shape);
184
185                        if (level == 0)
186                                scaling = Matrix.identity(3, 3);
187                        else
188                                scaling = TransformUtilities.scaleMatrix(2, 2);
189
190                        shape = newData.shape.transform(scaling);
191                        pose = newData.pose.times(scaling);
192                        fit  = newData.fit;
193                        parameters = newData.parameters;
194                }
195
196                return new IterationResult(pose, shape, fit, parameters);
197        }
198
199        /**
200         * @return the {@link PointDistributionModel}
201         */
202        public PointDistributionModel getPDM() {
203                return asms[0].getPDM();
204        }
205}