הגדלת הSTACK בvisual c 2005

[Ghosthunter]

היי,

אני מבצע בC כמה פעולות שדורשות גישות מרובות לפונקציות, ולצערי גודל הSTACK הסטנדרטי לא מספיק.

האם יש דרך להגדיל אותו?

תודה.

עריכה: מצאתי את \stack. אני אנסה להשתמש בזה. איפה בידיוק צריך לרשום את זה?

עריכה 2: אמרתי לקומפיילר שינסה להכניס כמה שיותר פונקציות כINLINE. כנראה שזה עזר מכיוון שעכשיו אני לא מקבל ERROR שהוא התמלא.

[Zelig]

תעצור בבקשה. זה נשמע כאילו אתה מנסה לפתור את הבעיה הלא נכונה.

באיזה מערכת הפעלה אתה עובד? למיטב זכרוני ב-win32 כל thread יכול לקבל עד 1MB של STACK (אשר גודל באופן אוטמטי). אם אתה עובד ב-DOS אז זה פחות, אבל עדיין אמור להספיק לכל מה שאתה עושה. מערכות embedded ומערכות ישנות מוגבלות ב-stack אבל עדיין יש מספיק. בכל שימוש סביר אתה בכלל לא אמור להתקל בבעיה.

בעצם מה אתה מנסה לעשות?

בכל מקרה הפתרון שמצאת נשמע לא טוב. זה פתרון שביר, שיכול להפסיק לעבוד אם תוסיף משתנה, או פונקציה, או שתעדכן לגרסה חדשה של הקומפיילר.

גם להגדיר הכל INLINE זה לא רעיון טוב שכן זה מגדיל מאוד את הקוד, ועדיין לא מבטיח שבאמת יהיה inline.

פתרונות טובים יותר לבעיות מחסנית:

* אל תגדיר מבנים (struct) גדולים על המחסנית. תגדיר מבנים קטנים יותר, או שתגדיר אותם מחוץ למחסנית (זכרון דינמי, משתנים גלובליים, סטטיים וכו').

* תעבוד עם אלגוריתם איטרטיבי במקום רקורסיבי.

* תשנה את האלגוריתם כך שיעבוד עם מחסנית שאתה בנית במקום מחסנית של המעבד (יש גרסאות של qsort שממומשות כך).

* פחות קריאות עמוקות לפונקציות.

[Ghosthunter]

אני לא יוצר מבני נתונים בכלל.

הבעיה שאני רוצה לפתור היא כזו:

יש לי מטריצה, ואני מעוניין למצוא מלבן חוסם של צורה כלשהי(שמוגדרת ע"י רצף אחדים אחד ליד השני) בגודל מסויים.

דוגמא:

[attachment deleted by admin]

[עמיר]

אם הבנתי נכון, תנסה להסתכל במימוש ב CGAL של הנושא:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Principal_component_analysis/Chapter_main.html

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Principal_component_analysis_ref/Function_bounding_box.html#Cross_link_anchor_1045

http://www.cgal.org/Manual/3.2/include/CGAL/bounding_box.h

[Ghosthunter]

אני מקבל מטריצה, שהיא בעצם MASK של פריים מסויים, ואני אמור לבדוק אם יש צורות בגודל מסויים. הפתרון שהראת לא מתאים.

[Zelig]

אכן principle component analysis לא מתאים כאן. הוא מועיל לחישוב bounding box מינימלי של סטים של נקודות. מה שיש לנו כאן זה מטריצה ולא סט של נקודות, ומחפשים BB מקביל לצירים ולא כללי.

האם אתה מחפש מלבן חוסם של צורה ספציפית או של כל הצורות בגודל (שטח/היקף/רדיוס) מסוים, מה שנקרא לפעמים blob analysis?

בכל מקרה באיזה אלגוריתם אתה משתמש וכמה stack יש לך? לשתי הבעיות יש אלגוריתמים איטרטיביים ואני לא מבין למה נגמר לך ה-STACK.

[Ghosthunter]

אני מחפש מלבן חוסם של כל הצורות בגודל מסויים.

אני מבצע משהו דומה לסריקה לעומק של גרף.

כרגע, כל תא שאני נמצא בו אני מסמן בצבע כלשהו, בודק את המיקום שלו ביחס למינימום ולמקסימום של שיעורי הX והY, והולך מקום אחד למעלה, אחד למטה, ימינה ושמאלה.

[Zelig]

זה גרסה רקורסיבית של flood fill, והיא פתרון ממש לא מעשי - בין השאר בגלל עומק הרקורסיה, כפי שכבר ראית.

קיימים אלגוריתמים יותר מהירים, איטרטיבים, ועדיין פשוטים למימוש והבנה. כרגע שכחתי את השם, מייד אמצא אותו.

עריכה:

יש לטכניקה הזו כל מני שמות וכל מני שיטות ואופטימיזציות, אבל הרעיון הבסיסי מתואר כאן:

http://homepages.inf.ed.ac.uk/rbf/HIPR2/label.htm

וגם פה (אבל מבולגן יותר): http://www.cse.msu.edu/~stockman/CV/F05Lectures/Weeks1_9/week01-connectedComponents.ppt

מה שאתה צריך לעשות זה בנוסף ללעקוב אחרי התווית ("צבע") של כל צורה, גם לעקוב אחרי השטח שלה (כלומר מספר הפיקסלים), וכן ניתן יחסית בקלות לעקוב אחרי ה-bounding box של כל אובייקט, ועוד כל מני פרמטרים. בסוף כאשר מקשרים בין תוויות שהיו שונות אבל אתה יודע שהן בעצם אותה צורה, צריך כמובן לחבר את השטחים וכן לעדכן את ה-bounding box.

לבסוף כל מה שנשאר זה לעבור בטבלה על הצורות בעלות שטח (גודל) שעונה על הדרישה - וה-bounding box כבר חושב!

זו טכניקה מאוד חזקה ושימושית, ויש לה אין-ספור וריאציות. שמות שהיא ידועה בהם:

object labeling

blob analysis

object segmentation

connected component labeling

ועוד.

[עמיר]

האמת שכן, נזכרתי שיש משהו כזה, אבל לא ממש התעמקתי בזה (פעם היתה לי שאלה על איך לממש איתור של רכיבים בתמונה ואני גם ישר הלכתי על הפתרון הרקורסיבי שהיה ברור לי שהוא לא יעיל למדי. אחרי זה אמרו לי על השיטה האיטרטיבית של הצביעה ומעקב).

[Zelig]

נו, יש התקדמות?

[Ghosthunter]

כן, עבדתי על זה קצת(לא יצא לי הרבה זמן). אני צריך לעבוד עוד על הלוגיקה ומקרי הקצה הרבים. זה מה שעשיתי עד עכשיו:

int max_min_cell[256];//on which cell the max and min are saved
int min_x[256];//what is the min x
int max_x[256];//what is the max x
int min_y[256];//what is the min y
int max_y[256];//what is the max y
int color = 0;
int i, j;

//assume we have less than 256 objects
//hopefully ps will be 2*rows for less pf
for(i=0;i<rows;++i)
{
	for(j=0;j<cols;++j)
	{
		if(mask[i][j]==1)
		{
			if(j>=1 && colors[i][j-1]!=0)
			{
				colors[i][j] = colors[i][j-1];
				max_x[max_min_cell[colors[i][j]]] = j;
				if(i>=1 && colors[i-1][j]!=0 && colors[i-1][j]!=colors[i][j])
				{//connect 2 colors to one.
					if(min_x[max_min_cell[colors[i-1][j]]] < min_x[max_min_cell[colors[i][j]]])
						min_x[max_min_cell[colors[i][j]]] = min_x[max_min_cell[colors[i-1][j]]];
					if(max_x[max_min_cell[colors[i-1][j]]] > max_x[max_min_cell[colors[i][j]]])
						max_x[max_min_cell[colors[i][j]]] = max_x[max_min_cell[colors[i-1][j]]];
					if(min_y[max_min_cell[colors[i-1][j]]] < min_y[max_min_cell[colors[i][j]]])
						min_y[max_min_cell[colors[i][j]]] = min_y[max_min_cell[colors[i-1][j]]];
					max_min_cell[colors[i-1][j]] = max_min_cell[colors[i][j]];
				}
			}
			else if(i>=1 && colors[i-1][j]!=0)
			{
				colors[i][j] = colors[i-1][j];
				max_y[max_min_cell[colors[i][j]]] = i;
			}
			else
			{
				colors[i][j] = ++color;
				max_min_cell[color] = color;
				min_x[color] = j;
				max_x[color] = j;
				min_y[color] = i;
				max_y[color] = i;
			}
		}
		else
			colors[i][j] = 0;
	}

}

עדיין לא קימפלתי אז יתכן שיהיו כמה בעיות. אני אייעל את הקוד(שימוש במצביעים במקום ][ וכו) מאוחר יותר(אחרי סיום הלוגיקה ובדיקת האלגוריתם).

ד.א. מה שעזר לי היה השקף האחרון במצגת שהבאת. תודה רבה!

[עמיר]

אוקי, נראה לי שהצלחתי לפתור את הבעיה (בהנחה שהבנתי אותה כמו שהתכוונת) ללא הסתכלות באף חומר עזר ובצורה איטרטיבית. השיטה לא יעילה, אבל הצלחתי ממש מהר לפתור את הבעיה. הרצתי את המטריצה שהבאת בעמוד הקודם, האם זה הפלט הצפוי למטריצה ?

Run time for an 10X12 matrix with 31 pixels on and 9 items on took 0 ms

Item #2 Bounding Box: [0,5,0,6]

Item #9 Bounding Box: [1,1,3,1]

Item #11 Bounding Box: [2,3,3,4]

Item #22 Bounding Box: [6,1,6,3]

Item #25 Bounding Box: [0,7,6,11]

Item #27 Bounding Box: [8,0,8,0]

Item #29 Bounding Box: [8,3,8,4]

Item #30 Bounding Box: [6,7,8,7]

Item #31 Bounding Box: [8,10,8,10]

המספריים מציינים את הקורדינטות X, Y של נקודת המינימום ואחרי זה המקסימום של המלבן החוסם את הצורה. (אני מחשיב נקודות שמחוברות באלכסון כחלק מאותה צורה).

רק להבין כמה האלגוריתם לא יעיל (למרות שעובד) על קלט רנדומלי:

Run time for an 1024X768 matrix with 275441 pixels on and 24095 items on took 89657 ms

ואחרי אופטימזציה קלה:

Run time for an 1024X768 matrix with 275137 pixels on and 24309 items on took 1328 ms

[Ghosthunter]

כן, זהו הפלט שציפיתי לו. מה השיטה האיטרטיבית שהשתמשת בה? אתה יכול לרשום נקודות חשובות באלגוריתם?

תודה.

[עמיר]

אני לא יודע מה הדרישות ריצה שאתה צריך בשביל המימוש שלך (מהירות / זכרון או סתם שירוץ), אבל בגדול השתמשתי בשפה מונחת עצמים. האובייקטים:

תא - אובייקט שיודע ישירות מי השכנים שלו ע"י מערך במקום קורדינטות (חוסך בדיקת מקרי קצה), ויש לו יכולת מעבר על השכנים ומיזוג החלקים שלהם (כל תא שייך בכל רגע נתון לחלק אחד).

חלק - אובייקט שמכיל מידע אודות צורה יחודית שמזוהה, הוא מכיל רשימה של כל התאים שלו ואת הגודל של ה bounding box שלו.

אני ממיר את הקלט למטריצה של אובייקטים של תאים (את החלק הזה אפשר לשפר ע"י יצירה חד פעמית בהתחלה ו/או מיפוי הקלט למצביע למטריצת הקלט). אני מתחיל לעבור לינארית על המטריצה של תאים, כאשר בכל תא צבוע אני יוצר עבורו חלק ועובר על השכנים של התא וממזג את כל החלקים שלהם. בתהליך המיזוג אני משנה את המבציע בכל תא מהחלק הקודם לחלק החדש, מוחק את החלק הקודם מרשימת החלקים הכוללת באולגיתם ומכניס את החדש (ומחשב ב 4 בדיקות פשוטות את ה BB החדש של החלק החדש).

לבסוף מקבלים רשימה כוללת של כל החלקים במטריצת הקלט כולל פרטים כמו ה BB, הגודל שלכם וכו'.

אני מקווה שהצלחתי להבהיר את הדרך.

עוד אופטימיזציה קלה:

Run time for an 1024X768 matrix with 275029 pixels on and 24188 items on took 657 ms

[Ghosthunter]

איזה סוג אופטימיזציה עשית? באלגוריתם או בקוד עצמו?