Кривая рельефа в массив точек

Эта проблема почти идентична проблеме оцифровки сигнала (например, звука), где основной закон заключается в том, что сигнал на входе, частота которого слишком высока для частоты дискретизации, не будет отражаться в оцифрованном выходе. Таким образом, проблема заключается в том, что если вы проверите каждые 30 пикселей, а затем проверите середину, как предлагает bmorris591, вы можете пропустить это 7-пиксельное отверстие между точками выборки. Это говорит о том, что если есть 10 пиксельных функций, которые вы не можете позволить себе пропустить, вам нужно сканировать каждые 5 пикселей: ваша частота дискретизации должна быть в два раза выше самой высокой частоты, присутствующей в сигнале.

Одна вещь, которая может помочь улучшить ваш алгоритм, — это лучший поиск по y-измерению. В настоящее время вы ищете пересечение между небом и землей линейно, но бинарный поиск должен быть быстрее

int y = image.getHeight()/2; // Start searching from the middle of the image
int yIncr = y/2;
while (yIncr>0) {
    if (image.getRGB(x, y) == -16777216) {
        // We hit the terrain, to towards the sky
        y-=yIncr;
    } else {
        // We hit the sky, go towards the terrain
        y+=yIncr;
    }
    yIncr = yIncr/2;
}
// Make sure y is on the first terrain point: move y up or down a few pixels
// Only one of the following two loops will execute, and only one or two iterations max
while (image.getRGB(x, y) != -16777216) y++; 
while (image.getRGB(x, y-1) == -16777216) y--;

Возможны другие оптимизации. Если вы знаете, что на вашей местности нет обрывов, то вам нужно только искать в окне от lastY+maxDropoff до lastY-maxDropoff. Кроме того, если ваш ландшафт никогда не может быть таким же высоким, как все растровое изображение, вам также не нужно искать верхнюю часть растрового изображения. Это должно помочь высвободить некоторые циклы ЦП, которые вы можете использовать для x-сканирования местности с более высоким разрешением.

Я предлагаю найти граничные точки, которые существуют на границе между белыми и темными пикселями. После этого мы можем оцифровать эти точки. Для этого мы должны определить DELTA, которые указывают, какую точку мы должны пропустить, а какую добавить в список результатов.

DELTA = 3, Number of points = 223

DELTA = 5, Number of points = 136

DELTA = 10, Number of points = 70

Ниже я разместил исходный код, который печатает изображение и ищет точки. Надеюсь, вы сможете прочитать его и найти способ решить вашу проблему.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.awt.image.DataBufferByte;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Program {

    public static void main(String[] args) throws IOException {
        BufferedImage image = ImageIO.read(new File("/home/michal/Desktop/FkXG1.png"));
        PathFinder pathFinder = new PathFinder(10);
        List<Point> borderPoints = pathFinder.findBorderPoints(image);
        System.out.println(Arrays.toString(borderPoints.toArray()));
        System.out.println(borderPoints.size());

        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.getContentPane().add(new ImageBorderPanel(image, borderPoints));
        frame.pack();
        frame.setMinimumSize(new Dimension(image.getWidth(), image.getHeight()));
        frame.setVisible(true);
    }
}

class PathFinder {

    private int maxDelta = 3;

    public PathFinder(int delta) {
        this.maxDelta = delta;
    }

    public List<Point> findBorderPoints(BufferedImage image) {
        int width = image.getWidth();
        int[][] imageInBytes = convertTo2DWithoutUsingGetRGB(image);
        int[] borderPoints = findBorderPoints(width, imageInBytes);

        List<Integer> indexes = dwindlePoints(width, borderPoints);
        List<Point> points = new ArrayList<Point>(indexes.size());
        for (Integer index : indexes) {
            points.add(new Point(index, borderPoints[index]));
        }
        return points;
    }

    private List<Integer> dwindlePoints(int width, int[] borderPoints) {
        List<Integer> indexes = new ArrayList<Integer>(width);
        indexes.add(borderPoints[0]);
        int delta = 0;
        for (int index = 1; index < width; index++) {
            delta += Math.abs(borderPoints[index - 1] - borderPoints[index]);
            if (delta >= maxDelta) {
                indexes.add(index);
                delta = 0;
            }
        }
        return indexes;
    }

    private int[] findBorderPoints(int width, int[][] imageInBytes) {
        int[] borderPoints = new int[width];
        int black = Color.BLACK.getRGB();
        for (int y = 0; y < imageInBytes.length; y++) {
            int maxX = imageInBytes[y].length;
            for (int x = 0; x < maxX; x++) {
                int color = imageInBytes[y][x];
                if (color == black && borderPoints[x] == 0) {
                    borderPoints[x] = y;
                }
            }
        }
        return borderPoints;
    }

    private int[][] convertTo2DWithoutUsingGetRGB(BufferedImage image) {
        final byte[] pixels = ((DataBufferByte) image.getRaster().getDataBuffer()).getData();
        final int width = image.getWidth();
        final int height = image.getHeight();
        final boolean hasAlphaChannel = image.getAlphaRaster() != null;

        int[][] result = new int[height][width];
        if (hasAlphaChannel) {
            final int pixelLength = 4;
            for (int pixel = 0, row = 0, col = 0; pixel < pixels.length; pixel += pixelLength) {
                int argb = 0;
                argb += (((int) pixels[pixel] & 0xff) << 24); // alpha
                argb += ((int) pixels[pixel + 1] & 0xff); // blue
                argb += (((int) pixels[pixel + 2] & 0xff) << 8); // green
                argb += (((int) pixels[pixel + 3] & 0xff) << 16); // red
                result[row][col] = argb;
                col++;
                if (col == width) {
                    col = 0;
                    row++;
                }
            }
        } else {
            final int pixelLength = 3;
            for (int pixel = 0, row = 0, col = 0; pixel < pixels.length; pixel += pixelLength) {
                int argb = 0;
                argb += -16777216; // 255 alpha
                argb += ((int) pixels[pixel] & 0xff); // blue
                argb += (((int) pixels[pixel + 1] & 0xff) << 8); // green
                argb += (((int) pixels[pixel + 2] & 0xff) << 16); // red
                result[row][col] = argb;
                col++;
                if (col == width) {
                    col = 0;
                    row++;
                }
            }
        }

        return result;
    }
}

class ImageBorderPanel extends JPanel {

    private static final long serialVersionUID = 1L;

    private BufferedImage image;
    private List<Point> borderPoints;

    public ImageBorderPanel(BufferedImage image, List<Point> borderPoints) {
        this.image = image;
        this.borderPoints = borderPoints;
    }

    @Override
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.drawImage(image, 0, 0, null);

        Graphics2D graphics2d = (Graphics2D) g;

        g.setColor(Color.YELLOW);
        for (Point point : borderPoints) {
            graphics2d.fillRect(point.x, point.y, 3, 3);
        }
    }
}

В моем исходном коде я использовал пример из этого вопроса:

• Java - получить массив пикселей из изображения

Наиболее эффективным решением (в отношении требуемых точек) было бы разрешить переменное расстояние между точками по оси X. Таким образом, для большой плоской части потребуется очень мало точек/образцов, а для сложных ландшафтов потребуется больше.

В обработке 3D-сетки есть хороший алгоритм упрощения сетки под названием «квадратичное схлопывание ребер», который вы можете адаптировать к своей задаче.

Вот идея, переведенная на вашу проблему - на самом деле она становится намного проще, чем исходный алгоритм 3D:

1. Представьте свою кривую со слишком большим количеством точек.
2. Для каждой точки измерьте ошибку (т.е. разницу с гладкой местностью), если вы ее уберете.
3. Удалите точку, дающую наименьшую ошибку.
4. Повторяйте до тех пор, пока вы не уменьшите количество точек достаточно далеко или ошибки не станут слишком большими.

Чтобы быть более точным относительно шага 2: Учитывая точки P, Q, R, ошибка Q представляет собой разницу между аппроксимацией вашей местности двумя прямыми линиями, P->Q и Q->R, и аппроксимацией вашей местности всего одной линией P->R.

Обратите внимание, что при удалении точки только ее соседи нуждаются в обновлении своего значения ошибки.