Это проблема оптимизации по двум целям: размер ограничивающей рамки и ошибка (в относительных расстояниях). Таким образом, у вас есть парето-фронт возможных решений, каждое из которых оптимизировано для различных компромиссов между размером ограничивающей рамки и ошибкой.
Проблема будет намного проще, если вы установите границу для одной из своих целей и просто решите, насколько лучше вы можете сделать для другой цели с учетом этой границы. Таким образом, вы можете либо сказать: «Учитывая определенный размер ограничивающей рамки, как я могу минимизировать ошибку?» или «учитывая максимально допустимую ошибку, как я могу минимизировать размер ограничивающей рамки?»
Я собираюсь предположить, что вы, скорее всего, имеете в виду конкретный размер ограничивающей рамки, а не конкретную максимальную ошибку, поэтому давайте начнем с предположения о ограничивающей рамке и постараемся свести к минимуму ошибку назначения точек уникальным позициям в этой ограничивающей рамке. коробка.
Вы захотите использовать метод оптимизации, который хорошо справляется с дискретным характером вашей проблемы. Я бы пошел с имитацией отжига.
Начнем с хорошего исходного кода
Учитывая размер ограничивающей рамки, вы можете масштабировать все изображение до размера ограничивающей рамки... но некоторые точки окажутся в одном и том же положении. Назовите это "наивным позиционированием":
.........................................
. . . . .
. . 2 3 . . .
. 1 . . . 4 .
.........................................
. . . . .
. . . . .
. . . . .
.........................................
. . . . .
. . . . .
. . 5 . . 6 .
.........................................
. 7 . . . .
. 8 . . . .
. . . . .
.........................................
Хорошо, мы можем справиться с этим. Определите ордер по вашим позициям. Вы можете сделать это наивно (слева направо, сверху вниз) или так, чтобы лучше сохранить локальность (кривая Гильберта). Мы будем перебирать эти позиции и, когда найдем позицию с более чем одной точкой, попытаемся распределить дополнительные точки между доступными пустыми позициями, когда это будет целесообразно.
Keep a queue of DisplacedPoints
Keep a stack of EmptyPositions
Iterate over positions in the order you've chosen:
If this position is empty,
Push this position onto EmptyPositions
Else If this position has more than one point,
Enqueue all but one of these points into DisplacedPoints
Placement: While there are remaining DisplacedPoints and remaining EmptyPositions,
Let candidatePoint = DiplacedPoints.Peek
Let candidatePosition = EmptyPositions.Peek
Let currentDisplacement = the distance from the current position to candidatePoint's naive position
Let candidateDisplacement = the distance from candidatePosition to candidatePoint's naive position
If currentDisplacement >= candidateDisplacement,
place candidatePoint in candidatePosition
pop candidatePosition off EmptyPositions
dequeue candidatePoint off DisplacedPoints
Else break out of Placement loop
While there are remaining DisplacedPoints and remaining EmptyPositions,
Dequeue a DisplacedPoint D, pop an EmptyPosition E, and put D into E
Если это слишком сложно, более простой подход состоит в том, чтобы просто перебирать позиции; когда вы столкнетесь с позицией со слишком большим количеством очков, поставьте в очередь дополнительные очки, а всякий раз, когда вы столкнетесь с пустой позицией, удалите из нее очко. Если вы достигли конца, а в очереди все еще есть точки, выполните итерацию в обратном порядке по позициям (больше не должно быть более одной точки) и удалите точки из очереди в пустые места.
Это ни в коем случае не будет оптимальным решением. Это всего лишь довольно хорошее первое предположение, чтобы смоделировать отжиг с хорошим стартом.
Выполнение целевой функции
Наивная целевая функция будет чем-то вроде суммы (по всем парам точек) квадрата разницы между (расстоянием между точками в исходном изображении) и (расстоянием между точками в уменьшенном изображении, умноженным на коэффициент масштабирования). Но с 20 тысячами точек это примерно 400 миллионов квадратов различий! Мы можем ускорить сходимость к хорошему решению, начав с простой, но быстрой целевой функции, чтобы добиться начального прогресса, а затем переключившись на более дорогие (и правильные) функции позже, чтобы получить более тонкие различия.
Самая быстрая и глупая целевая функция, которую вы можете использовать, — это O(n): суммируйте по всем точкам их расстояние от их собственного наивного позиционирования.
Более медленная, но более правильная целевая функция назначает каждой точке «релевантных соседей»: для каждой точки P мы возьмем точки, находящиеся в окрестности 3x3 позиций, окружающих наивное позиционирование P*. Теперь вы можете суммировать по всем точкам P сумму (по всем соответствующим соседям P) квадрата разницы между расстоянием изображения и (масштабированным) заданным расстоянием положения.
*поскольку расстояние от A до B такое же, как расстояние от B до A, поскольку точка X является одним из соответствующих соседей P, мы не должны рассматривать P как одного из соответствующих соседей X. Воспользовавшись этим, вы получите ускорение в 2 раза.
После того, как эти более быстрые целевые функции приблизили вас к оптимальным, вы можете использовать наивную целевую функцию, указанную выше (сумма по всем парам квадратов разницы расстояний). Я не уверен, что вы на самом деле хотите этого — наивная целевая функция хочет сохранить структуру дальних расстояний, но вы можете заботиться только о сохранении расстояний между соседями.
РЕДАКТИРОВАТЬ: Общая идея масштабирования должна работать, но вместо того, чтобы делать наивное масштабирование, а затем корректировать его постфактум, другой подход заключается в том, чтобы сделать само масштабирование более разумным.
Рассмотрите возможность использования масштабирования с учетом содержимого. Многократно чередуйте масштабирование по горизонтали и вертикали, чтобы сохранить общую форму как можно ближе к оригиналу.
Чтобы сохранить пространственные отношения между соседними точками, вы можете настроить функцию энергии, используемую при создании шва. Начните с присвоения значения 1.0 позициям с точкой и 0.0 позициям без точек и примените размытие по Гауссу. Это приведет к тому, что генерация шва будет предпочитать вырезать большие пустые пространства, прежде чем начнет сжимать небольшие пространства между соседними точками.
Если это слишком дорого/сложно, вы можете попробовать более простой метод:
Возьмем исходный пример (различные тождества, присвоенные точкам):
0 0 1 0 0
2 0 0 0 0
0 3 0 4 0
0 0 0 0 0
0 5 0 0 6
Найдите средние координаты x и y ваших точек. В этом примере среднее положение находится справа внизу от 3. Логически разделите массив на четыре квадранта, которые встречаются в среднем положении.
0 0|1 0 0
2 0|0 0 0
0_3|0_4_0
0 0|0 0 0
0 5|0 0 6
Теперь каждый квадрант можно обрабатывать независимо. В каждом квадранте есть два выровненных по сетке направления, которые указывают на центр (например, в верхнем левом квадранте вниз и вправо указывают на центр). Мы чередуем эти два направления, перемещая точки в соседние пустые места. Если ни одно из направлений не дает улучшения, вы закончили с этим квадрантом.
Итак, взяв в качестве примера верхний правый квадрант, мы будем перемещать точки вниз...
0 0|0 0 0
2 0|1 0 0
0_3|0_4_0
0 0|0 0 0
0 5|0 0 6
Обратите внимание, что мы не выталкиваем 4 за границу квадранта. Затем мы пытаемся нажать влево:
0 0|0 0 0
2 0|1 0 0
0_3|4_0_0
0 0|0 0 0
0 5|0 0 6
Затем мы пытаемся нажать вниз, но на самом деле ничего не движется. Попробуйте сдвинуться влево, и все равно ничего не сдвинется. Верхний правый квадрант готов. Таким же образом построим другие квадранты:
0 0|0 0 0
0 2|1 0 0
0_3|4_0_0
0 5|6 0 0
0 0|0 0 0
Теперь найдите ограничивающую рамку точек и обрежьте:
2 1
3 4
5 6
person
Jerry Federspiel
schedule
13.08.2015
