KI_RGBQuant/Quant.java

import java.util.ArrayList;
import java.util.Collections;

/**
 * Funktionen, um quantifizierungs-Punkte zu finden
 * 
 * @author Alexander Kimmig
 * @version 1.0
 */
public class Quant
{
    /**
     * Führt eine vollständige RGB-Qunatfizierung durch, Lädt die Datei
     * input.jpg im Projektordner und speichert das Ergebnis in output.jpg
     * 
     * @param count Anzahl, wie viele Quantifizierungs-Punkte gefunden werden solle
     * @param epoch Anzahl, wie viele Epochen durchlaufen werden sollen
     * @throws Exception falls Datei nicht existiert
     */
    public static void quantize(int count, int epoch) throws Exception {
        ArrayList<RGB> ipoints = Image.readFile("./input.jpg");

        ArrayList<RGB> quants = findQuants(count, epoch, ipoints);

        for (int i = 0; i < ipoints.size(); i++) {
            RGB p = ipoints.get(i);
            RGB t = findNearest(quants, p);
            p.r = t.r;
            p.g = t.g;
            p.b = t.b;
        }
        
        Image.writeFile("./input.jpg", "./output.jpg", ipoints);
    }
    
    /**
     * Findet Quantenpunkte
     * 
     * @param count Anzahl, wie viele Quantifizierungs-Punkte gefunden werden solle
     * @param epoch Anzahl, wie viele Epochen durchlaufen werden sollen
     * @param ipoints RGB-Datenpunkte des Bildes
     * 
     * @return ArrayList<RGB> mit den Quantenpunkten 
     * @throws Exception falls Datei nicht existiert
     */
    public static ArrayList<RGB> findQuants(int count, int epoch, ArrayList<RGB> ipoints) throws Exception {
        ArrayList<RGB> qpoints = new ArrayList<>();
        
        // Füge neue, zufällige Punkte hinzu
        for (int i = 0; i < count; i++) {
            qpoints.add(new RGB(true));
        }
        
        for (int i = 0; i < epoch; i++) {
            // Epoche durchlaufen
            doEpoch(ipoints, qpoints);
            // nich bewegte Quantenpunkte versetzen
            if (i < epoch-1) resetQuants(qpoints);
        }
        
        return qpoints;
    }
    
    /**
     * Epoche durchlaufen
     * 
     * @param ipoints RGB-Bildpunkte
     * @param qpoints bisherige Quantenpunkte -> werden direkt verändert
     */
    public static void doEpoch(ArrayList<RGB> ipoints, ArrayList<RGB> qpoints) {
        /*
         * WICHTIG: Bildpunkte mischen, da ansonsten die Punkte linear durchgegangen werden.
         * Bei großen Flächen am Ende (rechts unten) werden sonst viele Quantenpunkte in diesen
         * Bereich gezogen
         * 
         * Ausprobieren: deaktivieren und das Beispielbild "sonnenaufgang"
         */
        Collections.shuffle(ipoints);
        
        /*
         * Eine Epoche: alle Bildpunkte einmal durchlaufen
         */
        for (RGB t : ipoints) {
            // jeweils den nächstliegenden Quantenpunkt finden
            RGB q = findNearest(qpoints, t);
            
            // gegangener Weg speichern
            q.walk += t.diff2(q);
            q.count++;
            
            // den Punkt verschieben
            q.r = (q.r + t.r) / 2;
            q.g = (q.g + t.g) / 2;
            q.b = (q.b + t.b) / 2;
        }
        
        for (RGB tmp : qpoints) {
            // falls Punkt verschoben: berechne mittlere gegangene Weglänge
            if (tmp.count > 0) {
                tmp.walk = Math.max(1, tmp.walk / tmp.count);
            }
        }
    }
    
    /**
     * Versetzt die Quantenpunkte, die im letzten Schritt nicht versetzt wurden, d.h.
     * diejenigen, die zu weit von der Punktwolke entfernt sind.
     * 
     * Hierfür setze diejenigen, die nicht gegangen sind in die Nähe derjeniger Punkte,
     * die besonders weit gelaufen sind (da dort ggf. underfitted)
     * 
     * @param qpoints Quantenpunkte
     * @return int wie viele Punkte wurden versetzt
     */
    public static int resetQuants(ArrayList<RGB> qpoints) {
        int reset = 0;
        for (int i = 0; i < qpoints.size(); i++) {
            // finde denjenigen Punkt, der am wenigsten gelaufen ist
            RGB min = findMinWalk(qpoints);
            // wenn es keinen gibt oder dieser auch weit gelaufen ist, dann breche ab
            if (min == null || min.walk > 5) break;
            
            // finde denjenigen, der am weitesten gelaufen ist (dessen Bereich underfitted ist)
            RGB max = findMaxWalk(qpoints);
            // breche ab, falls dieser insgesamt auch sehr wenig gelaufen ist
            if (max.walk < 25) break;
            
            // passe den Wert an, damit dieser beim nächsten Schleifendurchlauf nicht mehr direkt gefunden wird
            max.walk -= 36;
            
            // setze den Nichtläufer zum Weitläufer
            min.setTo(max);
            // und variiere dessen Positionen um maximal ±5
            min.jitter(5);
            // walk = -1 -> nicht mehr weiter in diesem Durchlauf betrachten (nicht mehr als Minimum finden)
            min.walk = -1;
            // zähle die Anzahl der versetzten Punkte
            reset++;
        }
        
        // setze gelaufene Wege aller Punkte zurück
        for (RGB q : qpoints) {
            q.walk = q.count = 0;
        }
        
        return reset;
    }
    
    /**
     * Finde denjenigen Punkt in der Liste, der am wenigsten weit gelaufen ist
     * 
     * @param quants Punktliste
     * @return RGB der Punkt, der am wenigsten gelaufen ist oder null
     */
    private static RGB findMinWalk(ArrayList<RGB> quants) {
        RGB min = null;
        for (RGB tmp : quants) {
            if (tmp.walk >= 0 && (min == null || tmp.walk < min.walk)) {
                min = tmp;
            }
        }
        return min;
    }
    
    /**
     * Finde denjenigen Punkt in der Liste, der am weitesten gelaufen ist
     * 
     * @param quants Punktliste
     * @return RGB der Punkt, der am weitesten gelaufen ist
     */
    private static RGB findMaxWalk(ArrayList<RGB> quants) {
        RGB max = quants.get(0);
        for (RGB q : quants) {
            if (q.walk > max.walk) max = q;
        }
        return max;
    }
    
    /**
     * Finde den Punkt in der Liste der die kürzeste Distanz zum Zielpunkt hat
     * 
     * @param points Liste der Punkte
     * @param target Zielpunkt
     * @return RGB Punkt mit kürzestem Abstand
     */
    public static RGB findNearest(ArrayList<RGB> points, RGB target) {
        RGB nearest = points.get(0);
        int mind = target.diff2(nearest);
        
        for (RGB p : points) {
            int d = target.diff2(p);
            if (d < mind) {
                nearest = p;
                mind = d;
            }
        }
        
        return nearest;
    }
}