العثور على أقرب غير الأسود بكسل في صورة سريعة
https://stackoverflow.com/questions/307445
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي صورة 2D بشكل عشوائي و أحيانا مبعثرة مع بكسل.
تعطى نقطة على الصورة, أنا بحاجة إلى إيجاد المسافة إلى أقرب بكسل التي لا لون الخلفية (أسود).
ما هي أسرع طريقة للقيام بذلك ؟
الطريقة الوحيدة أنا يمكن أن تأتي مع بناء دينار كويتي-شجرة بكسل.ولكن أريد حقا أن تجنب مثل هذه تكلفة تجهيزها.أيضا, يبدو أن د. ك-شجرة يعطيني أكثر مما أحتاج.أنا فقط بحاجة المسافة إلى شيء و لا يهمني ما هذا شيئا.
المحلول
وكما يقول بايرو، ابحث في محيط الساحة التي اصلتم السير من بكسل واحد في كل مرة من نقطة الأصلي (أي زيادة العرض والارتفاع من قبل اثنين من بكسل في كل مرة). عندما ضرب بكسل غير الأسود، لحساب المسافة (وهذا هو أول حساب تكلفة الخاص بك) ومن ثم مواصلة البحث الخارج حتى عرض المربع الخاص بك هو ضعف المسافة إلى نقطة وجدت الأولى (أي نقاط وراء هذا لا يمكن أن يكون أقرب من بكسل وجدت الأصلي). حفظ أي نقاط غير السوداء تجد خلال هذا الجزء، ثم حساب كل المسافات لمعرفة ما إذا كان أي منها أقرب من نقطة الأصلي.
في لاكتشاف المثالي، لديك فقط لجعل حساب واحد بعد مكلفة.
على تحديث : في لأنك حساب المسافات بكسل إلى بكسل هنا (بدلا من الدقة التعسفية العائمة مواقع نقاط)، يمكنك تسريع هذه الخوارزمية بشكل كبير باستخدام جدول بحث محسوبة مسبقا ( مجرد مجموعة الطول من العرض) لتعطيك المسافة بوصفها وظيفة من س و <م> ص . A 100x100 مجموعة التكاليف التي أساسا 40K من الذاكرة وتغطي ساحة الصور 200x200 حول النقطة الأصلية، وقطع الغيار لك تكلفة ممارسة لحساب المسافة مكلفة (سواء كان فيثاغورس أو مصفوفة الجبر) لكل بكسل اللون تجد. يمكن أن يكون حتى قبل احتساب هذه المجموعة وجزءا لا يتجزأ من التطبيق الخاص بك كمورد، لتجنيب لك وقت الحساب الأولي (وربما هذا هو افراط خطير).
على تحديث 2 : في أيضا، وهناك طرق لتحسين البحث في محيط مربع. يجب أن تبدأ البحث الخاص بك في أربع نقاط التي تتقاطع المحاور ونقل بكسل واحد في وقت واحد نحو الزوايا (لديك 8 نقاط البحث متحركة، والتي يمكن بسهولة جعل هذه المشاكل أكثر مما يستحق، اعتمادا على متطلبات التطبيق الخاص بك). بمجرد تحديد موقع بكسل اللون، ليست هناك حاجة لمواصلة نحو الزوايا، والنقاط المتبقية كلها مزيد من الأصل.
وبعد أول بكسل وجدت، يمكنك فرض مزيد من القيود على منطقة البحث الإضافية المطلوبة إلى الحد الأدنى باستخدام جدول البحث للتأكد من أن كل نقطة تفتيش هو أقرب من نقطة جدت (البدء مرة أخرى في محاور، ووقف عند المسافة وصلت إلى حد). وهذا من شأنه تحسين الثاني ربما يكون كبيرا مكلفة للغاية لتوظيف إذا كان لديك لحساب كل المسافة على الطاير.
إذا أقرب بكسل ضمن مربع الصور 200x200 (أو أيا كان حجم يعمل للبيانات الخاصة بك)، سوف فقط البحث ضمن دائرة تحدها بكسل، والقيام المشاهدة فقط و<> المقارنات.
نصائح أخرى
شخصيا كنت تجاهل MusiGenesis' اقتراح جدول بحث.
حساب المسافة بين وحدات البكسل لا مكلفة ، خاصة لهذا الاختبار الأولي لا تحتاج المسافة الفعلية لذلك ليس هناك حاجة إلى أخذ الجذر التربيعي.يمكنك العمل مع المسافة^2،.هـ:
r^2 = dx^2 + dy^2
أيضا, إذا كنت تريد الذهاب إلى الخارج بكسل واحد في كل مرة تذكر أن:
(n + 1)^2 = n^2 + 2n + 1
أو إذا nx هو القيمة الحالية ، الثور هو القيمة السابقة:
nx^2 = ox^2 + 2ox + 1
= ox^2 + 2(nx - 1) + 1
= ox^2 + 2nx - 1
=> nx^2 += 2nx - 1
فإنه من السهل أن نرى كيف يعمل هذا:
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...
لذا في كل التكرار ولذلك تحتاج فقط الاحتفاظ ببعض المتغيرات الوسيطة بالتالي:
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
}
}
تادا!r^2 حساب مع بعض التحولات ، ويضيف وينقص :)
بالطبع, على أي حديث لائق وحدة المعالجة المركزية حساب r^2 = dx*dx + dy*dy قد يكون سريع مثل هذا...
وأنت لم تحدد كيف تريد لقياس المسافة. سوف أفترض L1 (مستقيم الخطوط) لأنه من الأسهل. ربما يمكن تعديل هذه الأفكار لL2 (الإقليدية).
إذا كنت تفعل هذا فقط لعدد قليل نسبيا من بكسل، ثم عادل الخارج البحث من بكسل مصدر في دوامة حتى تصل واحدة nonblack.
إذا كنت تفعل هذا لكثير / كل منهم، وكيف حول هذا: بناء مجموعة 2-D حجم الصورة، حيث كل مخازن خلية المسافة إلى أقرب بكسل nonblack (وإذا لزم الأمر الإحداثيات، لذلك بكسل). هل أربعة الاحتلالات خط: من اليسار إلى اليمين، من اليمين إلى اليسار، أسفل إلى أعلى، ومن أعلى إلى أسفل. نظر اليسار إلى اكتساح اليمنى. كما كنت كنس، والحفاظ على العمود 1-D تحتوي على بكسل nonblack شوهد آخر مرة في كل صف، وعلامة كل خلية في مجموعة 2-D مع المسافة و / أو إحداثيات تلك النقطة. O (ن ^ 2).
وبدلا من ذلك، شجرة ك-د هي مبالغة. هل يمكن استخدام quadtree. فقط قليلا أكثر صعوبة إلى رمز من بلدي الاجتياح الخط، وأكثر من ذلك بقليل الذاكرة (ولكن أقل من ضعفي)، وربما أسرع.
والبحث "بحث النقطة الأقرب"، أول وصلات اثنين في جوجل يجب أن تساعدك.
إذا كنت تفعل هذا فقط ل1 بكسل لكل صورة، وأعتقد أن أفضل رهان هو مجرد البحث الخطي، 1 بكسل مربع العرض في وقت والخارج. لا يمكنك أن تأخذ النقطة الأولى تجد، إذا مربع البحث الخاص بك هو مربع. عليك أن تكون حذرا
نعم، أقرب البحث جار جيد، ولكن لا يضمن ستجد "أقرب". سوف تتحرك بكسل واحد الخروج في كل مرة يؤدي إلى بحث مربع - سوف الأقطار يكون أبعد من أفقي / رأسي. إذا كان هذا هو المهم، فأنت تريد أن تحقق - مواصلة توسيع حتى الأفقي المطلق وعلى مسافة أكبر من بكسل 'العثور على'، ومن ثم حساب المسافات على كل بكسل غير السوداء التي كانت موجودة
وطيب، وهذا يبدو للاهتمام. لقد تقدمت ج ++ نسخة من soulution، وأنا لا أعرف إذا كان هذا يساعدك. وأعتقد أنه يعمل بسرعة كافية كما انها لحظة تقريبا على 800 * 600 المصفوفة. إذا كان لديك أي أسئلة نطلب فقط.
ونعتذر عن أي أخطاء التي أخرجتها، انها رمز 10min ... هذه هي النسخة التكرارية (كنت تخطط على جعل واحدة متكررة جدا، ولكني غيرت رأيي). ويمكن تحسين خوارزمية بعدم إضافة أي نقطة إلى مجموعة نقاط وهذا هو لمسافة أكبر من نقطة البداية ثم min_dist، ولكن هذا ينطوي على حساب لكل بكسل (على الرغم من انها اللون) المسافة من نقطة البداية.
وعلى أمل أن يساعد
//(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;
}
وأنا متأكد من أن هذا يمكن عمله أفضل ولكن هنا بعض التعليمات البرمجية التي يبحث في محيط مربع حول بكسل المركز، دراسة مركز الأول وتتحرك نحو الزوايا. إذا لم يتم العثور بكسل محيط (نصف القطر) يتم توسيع حتى يتم التوصل إلى أي حد نصف قطر أو تم العثور على بكسل. كان أول تنفيذ حلقة عمل دوامة بسيطة حول نقطة المركز ولكن كما لاحظت أن لا يجد أقرب بكسل المطلق. كان إنشاء SomeBigObjCStruct في داخل الحلقة بطيئة جدا - إزالته من حلقة جعلت من جيدة بما فيه الكفاية والنهج دوامة هو ما اعتدنا. ولكن هنا هذا التطبيق على أي حال - حذار، قليل من دون اختبار القيام به
ويتم كل ذلك ومع إضافة عدد صحيح والطرح.
- (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;
و}
يمكنك الجمع بين العديد من الطرق لتسريع العملية.
- طريقة تسريع بكسل البحث هو استخدام ما أسميه المكانية بحث خريطة.هو في الأساس downsampled خريطة (قل من 8 × 8 بكسل ، ولكن المقايضة) بكسل في تلك الكتلة.يمكن أن تكون القيم "لا بكسل مجموعة" "جزئية بكسل مجموعة" "كل بكسل تعيين".هذه طريقة واحدة قراءة يمكن أن أقول إذا كتلة/الخليوي إما كامل ، جزئيا أو بشكل كامل فارغة.
- مسح مربع/مستطيل حول مركز قد لا تكون مثالية لأن هناك العديد من بكسل/الخلايا التي هي الآن بعيدا.يمكنني استخدام دائرة رسم خوارزمية (Bresenham) للحد من النفقات العامة.
- القراءة الخام بكسل القيم يمكن أن يحدث في أفقي دفعات ، على سبيل المثال بايت (على خلية حجم 8x8 أو مضاعفات) ، dword أو طويلة.هذا يجب أن تعطيك خطيرة تسريع مرة أخرى.
- يمكنك أيضا استخدام مستويات متعددة من "المكانية بحث خرائط" ، مرة أخرى المقايضة.
على مسافة calculatation المذكورة جدول بحث يمكن استخدامها ، ولكن (ذاكرة التخزين المؤقت)عرض النطاق الترددي مقابل حساب سرعة المقايضة (لا أدري كيف ينفذ على GPU على سبيل المثال).
وأود أن تفعل جدول بحث بسيط - لكل بكسل، وبعد المسافة precalculate إلى أقرب بكسل غير الأسود وتخزين قيمة في نفس تعويض كما بكسل المقابلة. وبطبيعة الحال، وبهذه الطريقة سوف تحتاج المزيد من الذاكرة.
