package anotacja; import java.util.ArrayList; import java.util.List; public class BCSpatialValidation { public InvertedIndex[] index; public boolean[] active; public List[] polaczenia; //parametr filtrowania odleglosci //najleszpe wyniki osiagane sa dla wartosci parametru //pomiedzy 0.15 a 0.25 public float range = 0.2f; //parametr filtrowania par //jesli par jest bardzo duzo to uznajemy, ze nie ma sensu weryfikowac ich przestrzennie, //bo obrazy sa i tak bardzo podobne, a to jednoczesnie trwa bardzo dlugo // //sugerowana wartosc to tego parametru to 1000 //jesli weryfikacja przestrzenna trwa zbyt dlugo //to nalezy zmniejszyc ta wartosc lub zwiekszyc liczbe grup public int spatialLimit = 1000; //flaga do wyswietlania postawowych informacji w trybie DEBUG private static boolean DEBUG = false; private static float EPSILON = 0.00001f; public BCSpatialValidation(InvertedIndex[] index) { this.index = index; } @SuppressWarnings("unchecked") private void utworzPolaczenia() { this.polaczenia = new ArrayList[InvertedIndex.content.size()]; } public void indexPairs(QueryData data) { int[] grupy = data.groups; this.utworzPolaczenia(); for (int i = 0; i < grupy.length; i++) { InvertedIndex ind = index[grupy[i]]; //iterujemy tylko do przedostatniego elementu //bo ostatni element to marker zerowy for (int j = 0; j < ind.images.length - 1; j++) { int image = ind.images[j]; if (this.active[image]) { if (this.polaczenia[image] == null) { this.polaczenia[image] = new ArrayList(); } this.polaczenia[image].add(new int[]{i, grupy[i], j}); } } } } public float[] measure(QueryData data, boolean[] active, float[] bow) { this.active = active; float[] sim = new float[InvertedIndex.content.size()]; this.indexPairs(data); //przeliczenie normy L1 dla zapytania float queryL1 = 0; for (int i = 0; i < data.groups.length; i++) { int clust = data.groups[i]; queryL1 += InvertedIndex.idf[clust]; } float maxBow = 0; for (int i = 0; i < bow.length; i++) { maxBow = Math.max(maxBow, bow[i]); } for (int i = 0; i < InvertedIndex.content.size(); i++) { if (this.active[i]) { float spat = this.bcSim(data, i, queryL1); //jest duzo punktow, nie ma potrzeby liczyc if (Float.isInfinite(spat)) { spat = bow[i]; } //na wszelki wypadek zabezpieczenie przed bledami if (Float.isNaN(spat)) { spat = 0; } sim[i] = maxBow + spat; if (DEBUG) { System.out.println("Image: " + i + " BoW:" + bow[i] + " Sim:" + sim[i] + " Spt:" + spat + " Max:" + maxBow); } } else { sim[i] = bow[i]; } } return sim; } public float bcSim(QueryData data, int refImg, float queryL1) { List pairs = this.polaczenia[refImg]; //nalezy w tym miejscu sprawdzic wartosc NULL //jesli dwa obrazy nie maja przeciecia //to tablica nie bedzie utworzona if ((pairs == null) || (pairs.size() == 0)) { return 0; } if (DEBUG) { System.out.println("Pairs: " + pairs.size() + " " + InvertedIndex.content.get(refImg)); } if (pairs.size() > this.spatialLimit) { return Float.POSITIVE_INFINITY; } float[] normX1 = new float[pairs.size()]; float[] normX2 = new float[pairs.size()]; float[] normY1 = new float[pairs.size()]; float[] normY2 = new float[pairs.size()]; float[] normR1 = new float[pairs.size()]; float[] normR2 = new float[pairs.size()]; for (int i = 0; i < pairs.size(); i++) { int[] pair = pairs.get(i); normX1[i] = data.xCoord[pair[0]] / 256.0f; normX2[i] = this.index[pair[1]].xCoord[pair[2]] / 256.0f; normY1[i] = data.yCoord[pair[0]] / 256.0f; normY2[i] = this.index[pair[1]].yCoord[pair[2]] / 256.0f; normR1[i] = data.radius[pair[0]] / 256.0f; normR2[i] = this.index[pair[1]].radius[pair[2]] / 256.0f; } float hCurr = 0; float sum = 0; float max = this.range; max = max * max; for (int i = 0; i < pairs.size(); i++) { int[] pair = pairs.get(i); float support = 0; float norm = 0; int nCnt = 0; float r1 = normR1[i]; float r2 = normR2[i]; float ratio = r2 / r1; //sprawdz czy zero, jesli tak to przyjmij epsilon if (ratio == 0) { ratio = EPSILON; } //wspolczynnik podniesiony do kwadratu, bo nie liczymi pierwiastka euklidesa float ratioSqr = ratio;// * ratio; for (int j = 0; j < pairs.size(); j++) { int[] pairInner = pairs.get(j); if (data.groups[pairInner[0]] == data.groups[pair[0]]) { continue; } float d1x = normX1[i] - normX1[j]; float d1y = normY1[i] - normY1[j]; float d1 = d1x * d1x + d1y * d1y; float d2x = normX2[i] - normX2[j]; float d2y = normY2[i] - normY2[j]; float d2 = d2x * d2x + d2y * d2y; //dyskretyzacja wartosci moze wprowadzac bledne zera if (d1 == 0) { d1 = EPSILON; } if (d2 == 0) { d2 = EPSILON; } if ((d1 < max)||(d2 < max * ratioSqr)) { nCnt = nCnt + 1; norm = norm + InvertedIndex.idf[pairInner[1]]; } if ((d1 < max)&&(d2 < max * ratioSqr)) { float dratio = d2 / d1; float sratio = ratio > dratio ? dratio / ratio : ratio / dratio; support = support + sratio * InvertedIndex.idf[pairInner[1]]; //if (Float.isNaN(support)) { System.out.println("Sup NAN"); } } } if (norm > 0) { float nSupport = support / (float)norm; hCurr = hCurr + nSupport; //if (Float.isNaN(hCurr)) { System.out.println("CURR nan"); } if ((i == pairs.size() - 1) || (pair[1] != pairs.get(i + 1)[1])) { float idfCl = InvertedIndex.idf[pair[1]] * InvertedIndex.idf[pair[1]]; float cl = idfCl * hCurr / ((float)data.groups.length * InvertedIndex.len[refImg]); sum = sum + (float)Math.sqrt(cl); //if (Float.isNaN(sum)) { System.out.println("Sum NAN"); } hCurr = 0; } } } //normalizacja w stylu BC float n1 = queryL1 / data.groups.length; float n2 = InvertedIndex.nL1[refImg] / InvertedIndex.len[refImg]; float norm = (float)Math.sqrt(n1 * n2); sum = sum / norm; return sum; } }