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.text.extraction.swt; 031 032import java.util.ArrayList; 033import java.util.Comparator; 034import java.util.HashSet; 035import java.util.List; 036import java.util.Set; 037 038import org.openimaj.image.pixel.Pixel; 039import org.openimaj.math.geometry.shape.Rectangle; 040import org.openimaj.util.pair.Pair; 041import org.openimaj.util.set.DisjointSetForest; 042 043/** 044 * This class models a candidate line of text, with one of more word candidates 045 * within it, from the {@link SWTTextDetector}. 046 * 047 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 048 * 049 */ 050public class LineCandidate extends Candidate { 051 protected List<LetterCandidate> letters = new ArrayList<LetterCandidate>(); 052 protected List<WordCandidate> words; 053 054 protected LineCandidate() { 055 } 056 057 /** 058 * Computes lines of text by merging pairs of characters that have similar 059 * directions. 060 * 061 * @param letters 062 * @param options 063 * @return 064 */ 065 protected static List<LineCandidate> extractLines(List<LetterCandidate> letters, SWTTextDetector.Options options) { 066 final List<Pair<LetterCandidate>> pairs = createLetterPairs(letters, options); 067 068 final Set<Set<Pair<LetterCandidate>>> sets = DisjointSetForest.partitionSubsets(pairs, 069 new Comparator<Pair<LetterCandidate>>() { 070 @Override 071 public int compare(Pair<LetterCandidate> pair1, Pair<LetterCandidate> pair2) { 072 final Pixel pair1d = computeDelta(pair1.firstObject(), pair1.secondObject()); 073 final Pixel pair2d = computeDelta(pair2.firstObject(), pair2.secondObject()); 074 075 if (pair1.firstObject() == pair2.firstObject() || pair1.secondObject() == pair2.secondObject()) 076 { 077 final int tn = pair1d.y * pair2d.x - pair1d.x * pair2d.y; 078 final int td = pair1d.x * pair2d.x + pair1d.y * pair2d.y; 079 // share the same end, opposite direction 080 if (tn * 7 < -td * 4 && tn * 7 > td * 4) 081 return 0; 082 } else if (pair1.firstObject() == pair2.secondObject() 083 || pair1.secondObject() == pair2.firstObject()) 084 { 085 final int tn = pair1d.y * pair2d.x - pair1d.x * pair2d.y; 086 final int td = pair1d.x * pair2d.x + pair1d.y * pair2d.y; 087 // share the other end, same direction 088 if (tn * 7 < td * 4 && tn * 7 > -td * 4) 089 return 0; 090 } 091 092 return 1; 093 } 094 095 private Pixel computeDelta(LetterCandidate firstObject, LetterCandidate secondObject) { 096 final Rectangle frect = firstObject.regularBoundingBox; 097 final Rectangle srect = secondObject.regularBoundingBox; 098 099 final int dx = (int) (frect.x - srect.x + (frect.width - srect.width) / 2); 100 final int dy = (int) (frect.y - srect.y + (frect.height - srect.height) / 2); 101 return new Pixel(dx, dy); 102 } 103 }); 104 105 final List<LineCandidate> chains = new ArrayList<LineCandidate>(); 106 for (final Set<Pair<LetterCandidate>> line : sets) { 107 final Set<LetterCandidate> lcs = new HashSet<LetterCandidate>(); 108 109 for (final Pair<LetterCandidate> p : line) { 110 lcs.add(p.firstObject()); 111 lcs.add(p.secondObject()); 112 } 113 114 if (lcs.size() < options.minLettersPerLine) 115 continue; 116 117 final LineCandidate lc = new LineCandidate(); 118 lc.letters = new ArrayList<LetterCandidate>(lcs); 119 120 // set the line 121 for (final LetterCandidate letter : lc.letters) 122 letter.line = lc; 123 124 lc.regularBoundingBox = LetterCandidate.computeBounds(lc.letters); 125 lc.words = WordCandidate.extractWords(lc, options); 126 127 chains.add(lc); 128 } 129 130 return chains; 131 } 132 133 /** 134 * Compute all likely pairs of letters on the basis that they close 135 * together, have similar stroke widths & similar heights. 136 * 137 * @param letters 138 * the candidate letters 139 * @param options 140 * the options 141 * @return a list of potentially valid pairs 142 */ 143 private static List<Pair<LetterCandidate>> createLetterPairs(List<LetterCandidate> letters, 144 SWTTextDetector.Options options) 145 { 146 final List<Pair<LetterCandidate>> pairs = new ArrayList<Pair<LetterCandidate>>(); 147 148 final int numLetters = letters.size(); 149 150 for (int j = 0; j < numLetters; j++) { 151 final LetterCandidate l1 = letters.get(j); 152 153 for (int i = j + 1; i < numLetters; i++) { 154 final LetterCandidate l2 = letters.get(i); 155 156 // similar stroke width (median ratio < 2) 157 if (Math.max(l1.medianStrokeWidth, l2.medianStrokeWidth) 158 / Math.min(l1.medianStrokeWidth, l2.medianStrokeWidth) > options.medianStrokeWidthRatio) 159 continue; 160 161 // similar height 162 if (Math.max(l1.regularBoundingBox.height, l2.regularBoundingBox.height) 163 / Math.min(l1.regularBoundingBox.height, l2.regularBoundingBox.height) > options.letterHeightRatio) 164 continue; 165 166 // similar color (technically intensity) 167 if (Math.abs(l1.averageBrightness - l2.averageBrightness) > options.intensityThreshold) 168 continue; 169 170 // small distance between 171 final double distance = l1.centroid.x - l2.centroid.x; 172 if (Math.abs(distance) > options.widthMultiplier 173 * Math.max(l1.regularBoundingBox.width, l2.regularBoundingBox.width)) 174 continue; 175 176 // approximately level 177 // FIXME: vertical text... 178 final int oy = (int) (Math.min(l1.regularBoundingBox.y + 179 l1.regularBoundingBox.height, 180 l2.regularBoundingBox.y + l2.regularBoundingBox.height) - 181 Math.max(l1.regularBoundingBox.y, 182 l2.regularBoundingBox.y)); 183 if (oy * options.intersectRatio < Math.min(l1.regularBoundingBox.height, 184 l2.regularBoundingBox.height)) 185 continue; 186 187 // tests passed... merge 188 pairs.add(new Pair<LetterCandidate>(l1, l2)); 189 } 190 } 191 192 return pairs; 193 } 194 195 /** 196 * Get the letters corresponding to this line. 197 * 198 * @return the letters 199 */ 200 public List<LetterCandidate> getLetters() { 201 return this.letters; 202 } 203 204 /** 205 * Get the words corresponding to this line 206 * 207 * @return the words 208 */ 209 public List<WordCandidate> getWords() { 210 return words; 211 } 212}