Encontrar mais próximo de pixel não-preta em uma rápida imagem
https://stackoverflow.com/questions/307445
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho uma imagem 2D aleatoriamente e escassamente espalhados com pixels.
dado um ponto na imagem, eu preciso saber a distância para o pixel mais próximo que não está na cor de fundo (preto).
Qual é a maneira mais rápida de fazer isso?
O único método que eu poderia vir acima com está construindo uma árvore-kd para os pixels. mas eu realmente gostaria de evitar tais pré-processamento caro. Além disso, parece que uma árvore-kd me dá mais do que eu preciso. Eu só preciso a distância para alguma coisa e eu não me importo sobre o que esse algo é.
Solução
Como Pyro diz, procure o perímetro de um quadrado que você continue se movendo para fora um pixel em um momento de seu ponto original (ou seja, aumentando a largura e altura por dois pixels de cada vez). Quando você bate um pixel não-negro, você calcular a distância (este é o seu primeiro cálculo caro) e, em seguida, continuar a procurar para fora até que a largura da sua caixa é duas vezes a distância até o primeiro ponto encontrado (quaisquer pontos além deste não pode estar mais perto do que seu pixel constatada original). Guardar todos os pontos não-negros que você encontrar durante esta parte, e depois calcular cada uma das suas distâncias para ver se algum deles estão mais próximos do seu ponto original.
Em um achado ideal, você só tem que fazer um cálculo da distância caro.
Atualizar : Porque você está calculando distâncias de pixel-a-pixel aqui (em vez de precisão arbitrária locais de ponto flutuante), você pode acelerar esse algoritmo substancialmente usando uma tabela de pesquisa pré-calculada ( apenas uma matriz de altura-a-largura) para dar-lhe a distância em função do x e y . Uma matriz de 100x100 custa essencialmente 40K de memória e tampas um 200x200 quadrados em torno do ponto original, e poupa o custo de fazer um cálculo da distância caro (se Pitágoras ou álgebra matricial) para cada pixel colorido que você encontrar. Esta matriz poderia mesmo ser pré-calculado e incorporado no seu aplicativo como um recurso, para poupar-lhe o tempo cálculo inicial (esta é provavelmente um exagero grave).
Update 2 : Além disso, existem maneiras de otimizar procura do perímetro quadrado. Sua busca deve começar nos quatro pontos que se cruzam os eixos e mover um pixel de cada vez para os cantos (você tem 8 pontos de buscas móveis, o que poderia facilmente fazer isso mais problemas do que vale a pena, dependendo dos requisitos do seu aplicativo). Assim que você localizar um pixel colorido, não há necessidade de continuar para os cantos, como os pontos restantes são todos mais longe da origem.
Depois do primeiro pixel encontrado, você pode restringir ainda mais a área de pesquisa adicional necessário para o mínimo, usando a tabela de referência para garantir que cada procurou ponto é mais perto do que o ponto encontrado (novamente a partir de eixos, e parar quando a distância limite for atingido). Esta segunda otimização provavelmente seria muito caro para empregar se você tivesse que calcular cada distância em tempo real.
Se o pixel mais próximo é dentro da caixa de 200x200 (ou o tamanho funciona para seus dados), você só vai procurar dentro de um círculo limitado pelo pixel, apenas fazendo pesquisas e <> comparações.
Outras dicas
Pessoalmente, eu ignorar a sugestão de uma tabela de pesquisa MusiGenesis'.
Calcular a distância entre pixels é não caro, especialmente quanto a este teste inicial, você não precisa a distância real por isso não há necessidade de tomar a raiz quadrada. Você pode trabalhar com a distância ^ 2, ou seja:
r^2 = dx^2 + dy^2
Além disso, se você estiver indo para fora um pixel de cada vez lembre-se que:
(n + 1)^2 = n^2 + 2n + 1
ou se nx é o valor atual e boi é o valor anterior:
nx^2 = ox^2 + 2ox + 1
= ox^2 + 2(nx - 1) + 1
= ox^2 + 2nx - 1
=> nx^2 += 2nx - 1
É fácil ver como isso funciona:
1^2 = 0 + 2*1 - 1 = 1
2^2 = 1 + 2*2 - 1 = 4
3^2 = 4 + 2*3 - 1 = 9
4^2 = 9 + 2*4 - 1 = 16
5^2 = 16 + 2*5 - 1 = 25
etc...
Assim, em cada iteração, portanto, você só precisa manter algumas variáveis ??intermediárias assim:
int dx2 = 0, dy2, r2;
for (dx = 1; dx < w; ++dx) { // ignoring bounds checks
dx2 += (dx << 1) - 1;
dy2 = 0;
for (dy = 1; dy < h; ++dy) {
dy2 += (dy << 1) - 1;
r2 = dx2 + dy2;
// do tests here
}
}
Tada! r ^ 2 cálculo com deslocamentos bit apenas, acrescenta e subtrai:)
É claro que, em qualquer CPU moderna decente cálculo r ^ 2 = dx * dx + dy * dy pode ser tão rápido quanto isso ...
Você não especificou como você deseja medir a distância. Eu vou assumir L1 (retilínea) porque é mais fácil; possivelmente essas idéias poderia ser modificado para L2 (euclidiano).
Se você só está fazendo isso por relativamente poucos pixels, em seguida, basta pesquisar para fora do pixel de origem em uma espiral até atingir um que não seja preta.
Se você está fazendo isso para muitos / todos eles, como sobre isto: construir uma matriz 2-D o tamanho da imagem, onde cada célula armazena a distância até o pixel que não seja preta mais próxima (e, se necessário, as coordenadas desse pixel). Fazer varreduras quatro linhas: esquerda para a direita, direita para a esquerda, de baixo para cima e de cima para baixo. Considere a esquerda para varrer direito; como vassouras, manter uma coluna de 1-D contendo o último pixel não seja preta visto em cada fileira, e marcar cada célula na matriz 2-D, com a distância a e / ou coordenadas desse pixel. O (n ^ 2).
Como alternativa, uma árvore k-d é um exagero; você poderia usar um quadtree. Apenas um pouco mais difícil de código do que o meu varredura linha, um pouco mais de memória (mas menos do que o dobro), e possivelmente mais rápido.
Pesquisar "Nearest busca vizinho", primeiro dois links no Google deve ajudá-lo.
Se você está apenas fazendo isso por 1 pixel por imagem, acho que sua melhor aposta é apenas uma busca linear, 1 pixel largura da caixa de fora de tempo. Você não pode tomar o primeiro ponto que você encontrar, se sua caixa de pesquisa é quadrado. Você tem que ter cuidado
Sim, a busca vizinho mais próximo é bom, mas não garante que você vai encontrar o 'mais próximo'. Movendo um pixel de cada vez irá produzir uma pesquisa quadrado - as diagonais será mais longe do que a horizontal / vertical. Se isso é importante, você vai querer verificar -. Continuar a expandir até que a horizontal absoluta tem uma distância maior do que a 'encontrado' pixel, e as distâncias em seguida, calcular em todos os pixels não-negros que foram localizados
Ok, isso soa interessante. Eu fiz uma versão c ++ de um soulution, eu não sei se isso ajuda você. Eu acho que funciona suficientemente rápido como é quase instantânea em uma matriz de 800 * 600. Se você tiver alguma dúvida basta perguntar.
Desculpe por quaisquer erros que eu fiz, é um código 10min ... Esta é uma versão iterativa (eu estava planejando em fazer um recursiva também, mas eu mudei de idéia). O algoritmo pode ser melhorado, não adicionando qualquer ponto para a matriz pontos que está a uma distância maior do ponto de partida, em seguida, o min_dist, mas isso envolve o cálculo para cada pixel (apesar de cor) a distância do ponto de partida.
Espero que ajude
//(c++ version)
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;
//ITERATIVE VERSION
//picture witdh&height
#define width 800
#define height 600
//indexex
int i,j;
//initial point coordinates
int x,y;
//variables to work with the array
int p,u;
//minimum dist
double min_dist=2000000000;
//array for memorising the points added
struct point{
int x;
int y;
} points[width*height];
double dist;
bool viz[width][height];
// direction vectors, used for adding adjacent points in the "points" array.
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int k,nX,nY;
//we will generate an image with white&black pixels (0&1)
bool image[width-1][height-1];
int main(){
srand(time(0));
//generate the random pic
for(i=1;i<=width-1;i++)
for(j=1;j<=height-1;j++)
if(rand()%10001<=9999) //9999/10000 chances of generating a black pixel
image[i][j]=0;
else image[i][j]=1;
//random coordinates for starting x&y
x=rand()%width;
y=rand()%height;
p=1;u=1;
points[1].x=x;
points[1].y=y;
while(p<=u){
for(k=0;k<=7;k++){
nX=points[p].x+dx[k];
nY=points[p].y+dy[k];
//nX&nY are the coordinates for the next point
//if we haven't added the point yet
//also check if the point is valid
if(nX>0&&nY>0&&nX<width&&nY<height)
if(viz[nX][nY] == 0 ){
//mark it as added
viz[nX][nY]=1;
//add it in the array
u++;
points[u].x=nX;
points[u].y=nY;
//if it's not black
if(image[nX][nY]!=0){
//calculate the distance
dist=(x-nX)*(x-nX) + (y-nY)*(y-nY);
dist=sqrt(dist);
//if the dist is shorter than the minimum, we save it
if(dist<min_dist)
min_dist=dist;
//you could save the coordinates of the point that has
//the minimum distance too, like sX=nX;, sY=nY;
}
}
}
p++;
}
cout<<"Minimum dist:"<<min_dist<<"\n";
return 0;
}
Estou certo de que este poderia ser feito melhor, mas aqui está um código que pesquisas o perímetro de um quadrado ao redor do pixel central, examinando o centro primeiro e móveis para os cantos. Se um pixel não for encontrado o perímetro (raio) é expandida até que ou o limite de raio é alcançado ou um pixel é encontrado. A primeira implementação foi um loop fazendo uma espiral simples em torno do ponto central, mas como observou que não encontrar o pixel mais próximo absoluta. criação de SomeBigObjCStruct dentro do loop foi muito lento - removê-lo do laço feito bom o suficiente ea abordagem em espiral é o que me acostumei. Mas aqui está esta implementação de qualquer maneira -. Cuidado, pouco ou nenhum teste feito
É tudo feito com a adição inteiro e subtração.
- (SomeBigObjCStruct *)nearestWalkablePoint:(SomeBigObjCStruct)point {
typedef struct _testPoint { // using the IYMapPoint object here is very slow
int x;
int y;
} testPoint;
// see if the point supplied is walkable
testPoint centre;
centre.x = point.x;
centre.y = point.y;
NSMutableData *map = [self getWalkingMapDataForLevelId:point.levelId];
// check point for walkable (case radius = 0)
if(testThePoint(centre.x, centre.y, map) != 0) // bullseye
return point;
// radius is the distance from the location of point. A square is checked on each iteration, radius units from point.
// The point with y=0 or x=0 distance is checked first, i.e. the centre of the side of the square. A cursor variable
// is used to move along the side of the square looking for a walkable point. This proceeds until a walkable point
// is found or the side is exhausted. Sides are checked until radius is exhausted at which point the search fails.
int radius = 1;
BOOL leftWithinMap = YES, rightWithinMap = YES, upWithinMap = YES, downWithinMap = YES;
testPoint leftCentre, upCentre, rightCentre, downCentre;
testPoint leftUp, leftDown, rightUp, rightDown;
testPoint upLeft, upRight, downLeft, downRight;
leftCentre = rightCentre = upCentre = downCentre = centre;
int foundX = -1;
int foundY = -1;
while(radius < 1000) {
// radius increases. move centres outward
if(leftWithinMap == YES) {
leftCentre.x -= 1; // move left
if(leftCentre.x < 0) {
leftWithinMap = NO;
}
}
if(rightWithinMap == YES) {
rightCentre.x += 1; // move right
if(!(rightCentre.x < kIYMapWidth)) {
rightWithinMap = NO;
}
}
if(upWithinMap == YES) {
upCentre.y -= 1; // move up
if(upCentre.y < 0) {
upWithinMap = NO;
}
}
if(downWithinMap == YES) {
downCentre.y += 1; // move down
if(!(downCentre.y < kIYMapHeight)) {
downWithinMap = NO;
}
}
// set up cursor values for checking along the sides of the square
leftUp = leftDown = leftCentre;
leftUp.y -= 1;
leftDown.y += 1;
rightUp = rightDown = rightCentre;
rightUp.y -= 1;
rightDown.y += 1;
upRight = upLeft = upCentre;
upRight.x += 1;
upLeft.x -= 1;
downRight = downLeft = downCentre;
downRight.x += 1;
downLeft.x -= 1;
// check centres
if(testThePoint(leftCentre.x, leftCentre.y, map) != 0) {
foundX = leftCentre.x;
foundY = leftCentre.y;
break;
}
if(testThePoint(rightCentre.x, rightCentre.y, map) != 0) {
foundX = rightCentre.x;
foundY = rightCentre.y;
break;
}
if(testThePoint(upCentre.x, upCentre.y, map) != 0) {
foundX = upCentre.x;
foundY = upCentre.y;
break;
}
if(testThePoint(downCentre.x, downCentre.y, map) != 0) {
foundX = downCentre.x;
foundY = downCentre.y;
break;
}
int i;
for(i = 0; i < radius; i++) {
if(leftWithinMap == YES) {
// LEFT Side - stop short of top/bottom rows because up/down horizontal cursors check that line
// if cursor position is within map
if(i < radius - 1) {
if(leftUp.y > 0) {
// check it
if(testThePoint(leftUp.x, leftUp.y, map) != 0) {
foundX = leftUp.x;
foundY = leftUp.y;
break;
}
leftUp.y -= 1; // moving up
}
if(leftDown.y < kIYMapHeight) {
// check it
if(testThePoint(leftDown.x, leftDown.y, map) != 0) {
foundX = leftDown.x;
foundY = leftDown.y;
break;
}
leftDown.y += 1; // moving down
}
}
}
if(rightWithinMap == YES) {
// RIGHT Side
if(i < radius - 1) {
if(rightUp.y > 0) {
if(testThePoint(rightUp.x, rightUp.y, map) != 0) {
foundX = rightUp.x;
foundY = rightUp.y;
break;
}
rightUp.y -= 1; // moving up
}
if(rightDown.y < kIYMapHeight) {
if(testThePoint(rightDown.x, rightDown.y, map) != 0) {
foundX = rightDown.x;
foundY = rightDown.y;
break;
}
rightDown.y += 1; // moving down
}
}
}
if(upWithinMap == YES) {
// UP Side
if(upRight.x < kIYMapWidth) {
if(testThePoint(upRight.x, upRight.y, map) != 0) {
foundX = upRight.x;
foundY = upRight.y;
break;
}
upRight.x += 1; // moving right
}
if(upLeft.x > 0) {
if(testThePoint(upLeft.x, upLeft.y, map) != 0) {
foundX = upLeft.x;
foundY = upLeft.y;
break;
}
upLeft.y -= 1; // moving left
}
}
if(downWithinMap == YES) {
// DOWN Side
if(downRight.x < kIYMapWidth) {
if(testThePoint(downRight.x, downRight.y, map) != 0) {
foundX = downRight.x;
foundY = downRight.y;
break;
}
downRight.x += 1; // moving right
}
if(downLeft.x > 0) {
if(testThePoint(upLeft.x, upLeft.y, map) != 0) {
foundX = downLeft.x;
foundY = downLeft.y;
break;
}
downLeft.y -= 1; // moving left
}
}
}
if(foundX != -1 && foundY != -1) {
break;
}
radius++;
}
// build the return object
if(foundX != -1 && foundY != -1) {
SomeBigObjCStruct *foundPoint = [SomeBigObjCStruct mapPointWithX:foundX Y:foundY levelId:point.levelId];
foundPoint.z = [self zWithLevelId:point.levelId];
return foundPoint;
}
return nil;
}
Você pode combinar muitas maneiras de acelerá-lo.
- Uma maneira de acelerar a pesquisa de pixels é usar o que eu chamo um mapa de pesquisa espacial. É basicamente um mapa downsampled (digamos de 8x8 pixels, mas é um trade-off) dos pixels nesse bloco. Os valores podem ser "sem pixels definir" "pixels parciais definidos" "todos os pixels definidos". Desta forma, uma leitura pode dizer se a / célula bloco ou é completa, parcialmente cheio ou vazio.
- digitalização de um box / retângulo ao redor do centro pode não ser ideal, pois existem muitos pixels / células que são muito, muito distante. I usar um algoritmo de círculo desenho (Bresenham) para reduzir a sobrecarga.
- lendo os valores de pixel matérias pode acontecer em lotes horizontais, por exemplo, um byte (para um tamanho de célula de 8x8 ou múltiplos dele), dword ou longo. Isso deve lhe dar um aumento de velocidade sério de novo.
- você também pode usar vários níveis de "mapas de pesquisa espaciais", seu novo uma troca.
Para o calculatation distância da tabela de pesquisa mencionado pode ser usado, mas é um (cache) largura de banda vs tradeoff velocidade de cálculo (Eu não sei como ele se comporta em uma GPU, por exemplo).
Gostaria de fazer uma tabela de pesquisa simples - para cada pixel, a distância precalculate para o mais próximo de pixel não-preto e armazenar o valor no mesmo deslocamento como o pixel correspondente. Claro que, desta forma você vai precisar de mais memória.
